Next-Level Benchmarking Overfitting

In my recent blog post I remarked that database benchmarking is in a crisis because AI agents start to overfit on individual benchmarks with questionable techniques, which drives execution times towards zero. This has happened with TPC-D in the past, and broke the benchmark. TPC-H tries to fight that with rules, but most people who publish (unofficial) TPC-H results simply ignore the rules. In combination with overly eager AI agents, this leads to brutal overfitting.

We are seeing the next level of that with the GenDB-V system. The corresponding paper commands “Stop Handcrafting Your Engine! GenDB-V: Towards AI-Generated and Formally Verified Database Systems”, and reports speedups of 22× to 61× over Umbra and DuckDB, and all that in a fully verified system. These are indeed impressive claims, and would suggest that traditional database engines are in trouble.

Taking a step back, though, it should be clear that a performance improvement of a factor of 22 over Umbra is infeasible, at least if we are talking about traditional query processing. At SF10, the 22 TPC-H queries read roughly 15GB of (compressed) base data, and on a 9950X3D Umbra runs all queries in a total of roughly 540ms. On that machine the memory touched for data divided by the memory bandwidth (54GB/s) alone is about 280ms; anything below that is infeasible. Better compression might bring that down a bit, but not by an order of magnitude.

Unsurprisingly, the most dramatic gains of GenDB-V come from precomputation. The agents have carefully handcrafted auxiliary data structures for each query, which are computed at load time, and which avoid most of the work. The physical design is heavily tuned to the queries, too, for example, there is an extra structure that lists the supplier rows in s_acctbal DESC order, which makes Q2 trivial. Similar per-query data structures are built for most queries. And we see that in the performance numbers: Several queries already run in near-constant time at SF100: Q2 in 0.7 ms, Q17 in about 15 ms and Q4 in about 17 ms on one thread. That is the TPC-D symptom, without stored aggregates.

There is also a “plain-array” mode, which, at first glance, is more fair, as it avoids these excessive preparations and also reports performance improvements of just roughly a factor of 3, which seems achievable. But when looking closely, we see that here the agents did something even more insane: They hard-coded their knowledge about the data generator. They “know” that each customer k will be at row k-1. And they know that dbgen numbers the i-th order 32·(i/8) + i%8, so key k should be at row 8·(k/32) + k%32 − 1. Which makes the join in query Q18 super cheap.

How does all this fit together with the claim of a fully verified database engine? Well, the code does check if the hard-coded knowledge about the data generator holds in practice, e.g., by checking if the guessed join partner row is correct. If not, it falls back to a super slow generic nested loop implementation, but as that never happens with the official TPC-H data generator, that code path is irrelevant in the reported experiments.

Which brings me back to my original blog post claim: Letting AI agents optimize for a given database benchmark makes the benchmark useless. They will do their best to find insane tricks to speed up this particular benchmark, but none of that would work in a real system. The high tuning and synthesis time aside, deleting a single tuple (or inserting one in the middle) can most likely cause the whole approach to fall off a cliff, as it forces the slow fallback path. Which is not something you want in a production system.

The Benchmarking Crisis

Goodhart’s law, that any measurable target stops being useful when people start optimizing for it, very much holds in database benchmarking. That is not new, of course. Famously, TPC-D got retired when people optimized so much for it that the query runtimes converged towards zero due to excessive caching. TPC-H fixed that by declaring itself to be an ad-hoc benchmark, and explicitly forbidding things like exploiting knowledge about the workload or caching results (and a number of other optimizations).

We now see the same problem with the ClickBench benchmark, heavily accelerated by today’s use of AI code generation. If you tell an AI to make the queries faster, it will make the queries faster, regardless of whether this is a generally plausible approach or not. For example, the pgrust implementation performs group-by aggregations on string columns purely on the hash value, ignoring the long string content. That is a great performance boost, of course, and works for this benchmark, but can produce wrong results. Is it faster? Yes. Is it a plausible optimization? Probably not. And it does many other things: For example, ClickBench repeats certain predicates across queries, and thus pgrust caches the predicate, completely eliminating the query cost the second time. Or for query Q17, which returns tuples grouped by userid, it makes use of the fact that a) tuples are roughly clustered by userid, and b) the query specifies a limit clause without order by. Thus any userid will do, and it never reads most of the data. A human would not do these tiny micro-optimizations, because they are unlikely to be relevant in general use cases, but an AI can of course look at each query in detail and tune for it.

Part of the problem is, of course, ClickBench itself. The benchmark is not well specified in what is permitted and what is not, there is no update stream, the queries are very simple, share predicates, are underspecified, etc. But the fundamental problem is independent of that concrete benchmark: The moment we start aggressively optimizing for a specific benchmark, the benchmark stops being very useful. Historically, that pressure was reduced a bit by the requirement that systems be generally useful. That is, they did not just want to perform well in benchmarks but also to be useful for their customers. That is, of course, not a concern for vibe-coded execution engines.

It is not clear what to do about it. Our SQLStorm proposal tried to address this by having tens of thousands of queries, which makes overfitting harder. No human would fine-tune their system to such a huge workload. But with AI tools we could even investigate ten thousand queries in detail if needed, so that is not a real defense.

I think that to be meaningful, a benchmark has to a) like TPC-H, be ad-hoc, and forbid exploiting prior knowledge and any form of intermediate result caching. If we don’t do that, execution times converge towards zero. And b) the benchmark has to include some form of update stream, as otherwise overly aggressive read-only or read-mostly systems will always outperform systems that offer full transactional support. And c) the benchmark has to be truly ad-hoc, in the sense that the systems tested have to be older than the benchmark. One way to fight Goodhart’s law would be to (automatically) come up with a new benchmark from time to time, and then measure the systems that existed before the benchmark. The caching/pre-computation problem still remains, of course, but at least that would prevent the over-aggressive adjustment to just one specific benchmark.

Interestingly, the machine learning community has struggled with exactly the same problem for years, and we should probably borrow some of their ideas. Kaggle competitions, for example, rank submissions on a hidden test set that participants never see, which makes overfitting on the public data pointless. Similarly, benchmarks like LiveBench regularly release new questions to make sure that models cannot have seen them during training. For database benchmarking that could mean keeping the actual benchmark queries secret and only publishing a representative sample for development, or, even better, generating a fresh workload for every evaluation round. SQLStorm already uses generated queries, so producing a new query set from time to time would be fairly easy. We would probably want a more generic approach (higher variety in schemas, update streams, transactions, etc.), but that seems to be a direction that would help keep benchmarks meaningful.

Measuring the Performance of Deterministic Exceptions

I have always been interested in Zero-Overhead Deterministic Exceptions from P0709, as they promised a nicer implementation model and they are much easier to integrate into JIT-compiled code. Some people forbid regular C++ exceptions, due to code size and performance concerns, which are concerns that P0709 explicitly wants to address. Unfortunately, there was no implementation available. But now, with LLMs, doing this kind of experiment is much more tractable. I basically gave the official P0709 specification to an LLM, and it built a first prototype in one shot. Admittedly my initial enthusiasm cooled down a bit after I found a lot of problems and corner cases, but after about one day of work I was able to build a reasonable prototype, which is something that would easily have taken me weeks or even months in the past. I tested it with complex code, and it handled everything fine, but note that it is still not production ready (e.g., Itanium ABI only).

That prototype now allows us to quantify the differences between exception implementations. P0709 describes two ways to implement them: Either pass a hidden pointer to an error state to all functions that are marked with throws (we call this strategy pointer here), or use the carry bit to indicate errors and pass the error itself in registers if the bit is set (we call this strategy carry). That is a very nifty approach suggested by Herb Sutter, but it somewhat clashes with some of the function epilogues (e.g., on Windows), and such a flag is not available on all platforms. We thus introduced a third variant register here that simply uses another unused caller-saved register as an error indicator, which is more portable. The classic C++ exception handling mechanism we call dynamic.

Microbenchmarks

We first run some microbenchmarks to see the overall effects. These over-emphasize the differences as the benchmarks basically do nothing besides function calls (ns per outer call):

Test	failures	dynamic	pointer	register	carry
int through 8 calls	0%	6.02	6.09	6.08	6.16
	1%	17.5	7.10	6.31	6.33
	10%	101	7.59	6.85	6.88
	50%	467	9.48	9.26	9.11
forwarding chain, 8 tail calls	0%	1.54	1.34	1.52	1.59
	50%	188	4.74	4.31	4.28
void through 4 calls	0%	3.00	3.09	3.05	3.06
	1%	9.82	3.33	3.32	3.31
16-byte struct (two registers)	0%	3.01	3.24	3.06	3.06
32-byte struct in memory	0%	5.40	6.06	5.75	5.44
	1%	11.3	6.03	5.60	5.43
	50%	314	6.26	5.93	5.92
pointer, single call	0%	0.75	0.95	0.75	0.75
	50%	188	3.66	3.29	3.08

We notice several things. First, the pointer strategy often has noticeable overhead due to additional memory instructions, and is inferior to the other two. register and carry are nearly identical, which, given the fragility of the carry approach, means that register seems to be the preferred choice. Compared to classical C++ exceptions, performance of register is within 1-2% on the happy path, where no exception occurs, and it is dramatically faster, up to orders of magnitude, if exceptions indeed occur.

A more realistic workload

These numbers over-inflate the differences because the functions do so little work. As a more plausible workload, we use RapidJSON and benchmark the performance on the nativejson-benchmark, optionally corrupting some inputs to trigger exceptions. RapidJSON can be configured to report failures by error codes instead of exceptions; we call that strategy codes here.

The full results are here; we show a selection below. What the numbers basically show is 1) deterministic exceptions with the register strategy have the same performance and the same code sizes as explicit error codes, 2) performance differences from traditional C++ exceptions are largely within the noise even on the happy path, and 3) in the case of errors they are vastly superior to traditional C++ exceptions.

Happy path: SAX parsing

MB/s, higher is better, best of 5 runs; in parentheses: change relative to codes.

	codes	dynamic	pointer	register	carry
canada.json	1635.8	1606.6 (-1.8%)	1665.1 (+1.8%)	1606.1 (-1.8%)	1603.3 (-2.0%)
citm_catalog.json	2212.7	2216.0 (+0.1%)	2356.3 (+6.5%)	2206.3 (-0.3%)	2341.5 (+5.8%)
twitter.json	1365.2	1376.5 (+0.8%)	1425.4 (+4.4%)	1377.5 (+0.9%)	1472.0 (+7.8%)

Happy path: retired instructions per parse

Instructions (perf stat), lower is better; in parentheses: change relative to codes.

	codes	dynamic	pointer	register	carry
sax canada.json	49555378	49903680 (+0.7%)	50294221 (+1.5%)	50850829 (+2.6%)	50738702 (+2.4%)
sax citm_catalog.json	20552806	20212949 (-1.7%)	20761272 (+1.0%)	20802928 (+1.2%)	20730816 (+0.9%)
sax twitter.json	11758968	11547972 (-1.8%)	11799096 (+0.3%)	11850736 (+0.8%)	11813765 (+0.5%)

Errors: small documents, a fraction of them corrupted

ns per document, lower is better, best of 5 runs; in parentheses: change relative to codes.

	codes	dynamic	pointer	register	carry
0%	1726.1	1692.2 (-2.0%)	1729.3 (+0.2%)	1720.5 (-0.3%)	1721.0 (-0.3%)
1%	1707.3	1812.3 (+6.2%)	1703.3 (-0.2%)	1707.7 (+0.0%)	1713.9 (+0.4%)
10%	1600.8	1848.9 (+15.5%)	1597.3 (-0.2%)	1598.3 (-0.2%)	1614.3 (+0.8%)
50%	1256.5	1895.7 (+50.9%)	1263.6 (+0.6%)	1264.2 (+0.6%)	1275.3 (+1.5%)
100%	868.6	1934.7 (+122.7%)	871.8 (+0.4%)	869.3 (+0.1%)	882.1 (+1.6%)

Size of the parser

Bytes of all GenericReader functions, GenericDocument::ParseStream and parseSAX (into which parts of the parser are inlined); in parentheses: change relative to codes.

	codes	dynamic	pointer	register	carry
code	17191	18162 (+5.6%)	17540 (+2.0%)	17204 (+0.1%)	17289 (+0.6%)
unwind info	1292	1500 (+16.1%)	1340 (+3.7%)	1268 (-1.9%)	1248 (-3.4%)
exception tables	0	388	0	0	0
total	18483	20050 (+8.5%)	18880 (+2.1%)	18472 (-0.1%)	18537 (+0.3%)

Conclusion

Given that “exceptions” might not always be that exceptional (e.g., when parsing large amounts of user input), deterministic exceptions indeed seem to be a very good idea, and P0709 indeed should be adopted by the C++ standard. Not that this is likely to happen, given the lack of progress on this front, but now we at least have numbers to talk about.

Safe Optimistic Lock Coupling

As the number of CPU cores keeps growing, the scalability of concurrent data structures becomes increasingly important. A data structure that works fine on 4 cores can become a bottleneck on 32, not because of algorithmic limitations, but because of how it synchronizes access.

We illustrate that with a simple binary tree. Usually these data structures are protected by some kind of lock:

struct Node {
   mutex lock;
   
   key_type key;
   value_type value;
   Node* left, *right;
};
struct Tree {
   mutex lock;
   Node* root;
};

When searching a value, we can traverse the data structure, lock the parts of the data we are currently touching, and release locks when we are done (“lock coupling”):

option<value_type> Tree::lookup(key_type key) {
   lock.lock_shared();
   mutex* currentLock = &lock;
   Node* iter = root;
   option<value_type> result;
   while (iter) {
      if (key == iter->key) {
         result = iter->value;
         break;
      }
      Node* next = (key < iter->key) ? iter->left : iter->right;
      if (next) next->lock.lock_shared();
      currentLock->unlock();
      currentLock = next ? &next->lock : nullptr;
      iter = next;
   }
   currentLock->unlock();
   return result;
}

While conceptually simple, lock coupling has quite poor performance in practice. The problem is that it creates contention on the locks, in particular for the root node. Every lookup goes through the root node, thus the root node is constantly locked and unlocked. While there is no semantic contention between lookups, as all readers can read the root concurrently, there is physical contention on the lock itself, which limits scalability. This can be seen below, with concurrent lookups in a tree of 100,000 elements, executed on a 16-core / 32-thread 9950X3D.

Lookup scalability: no locking vs lock coupling

This contention problem can be solved by using Optimistic Lock Coupling, a synchronization technique where readers do not perform any writes. The key idea here is that writers lock as usual, and increase a version number when they are done updating. Readers read the version number before access, read the elements they are interested in, and then re-check the version number. If the version number changed (or the element is currently locked), the read fails and the reader tries again. In (slightly simplified) code it looks like this:

struct Node {
   version_lock lock;
   
   key_type key;
   value_type value;
   Node* left, *right;
};
struct Tree {
   version_lock lock;
   Node* root;
};

option<value_type> Tree::lookup(key_type key) {
   restart: lock_guard guard = lock.lock_optimistic();
   Node* iter = root;
   if (!guard.validate()) goto restart;
   option<value_type> result;
   while (iter) {
      auto currentKey = iter->key;
      if (!guard.validate()) goto restart;
      if (key == currentKey) {
         auto currentValue = iter->value;
         if (!guard.validate()) goto restart;
         result = currentValue;
         break;
      }
      iter = (key < currentKey) ? iter->left : iter->right;
      if (!guard.validate()) goto restart;
      auto nextGuard = iter->lock.lock_optimistic();
      if (!guard.validate()) goto restart;
      guard = nextGuard;
   }
   return result;
}

It is not that different from the classic lock coupling code above, except that we always have to check for concurrent writes before acting on the read values. The great benefit of this strategy is that the lookup code is purely read-only, which allows it to scale nicely with the number of cores:

Lookup scalability: all strategies

While Optimistic Lock Coupling offers excellent performance, it is a bit dangerous to use. If you act upon a value before validating, you effectively have a race condition in your code. In this small example it is clear when we have to validate, but in complex code fragments it is easy to forget to validate.

The best way to mitigate that is to get compiler support, by encoding the fact that we need to validate in the type system. We can achieve that by representing unvalidated values as a dedicated type, and having only the lock guard expose that value. Conceptually it looks like this (variants that validate multiple values omitted for simplicity):

template <class T>
class unvalidated {
   T value;
   friend class lock_guard;
};
class lock_guard {
   ...
   template <class T>
   optional<T> validate(unvalidated<T> value);
};

Basically we only allow access to the original value by validating, which makes that construct safe. But how do we ensure that code properly wraps everything in unvalidated<T>? By exposing only an optimistic view over the data. Conceptually we do the following:

struct Node {
   class OptimisticView;
   ... // as above
};
template <class T>
class OptimisticPtr
{
   T* rawPtr;
   public:
   // We cannot use operator-> here unfortunately due to C++ constraints
   typename T::OptimisticView data() const { return T::OptimisticView(rawPtr); }
};
// Exposes each member as unvalidated<T> value
class Node::OptimisticView {
   class Node* rawData;
   public:   
   unvalidated<key_type> key() { return unvalidated(atomic_ref(rawData->key).load(memory_order_relaxed)); }
   unvalidated<value_type> value() { return unvalidated(atomic_ref(rawData->value).load(memory_order_relaxed)); }
   unvalidated<OptimisticPtr<Node>> left() { return unvalidated(OptimisticPtr(atomic_ref(rawData->left).load(memory_order_relaxed))); }
   unvalidated<OptimisticPtr<Node>> right() { return unvalidated(OptimisticPtr(atomic_ref(rawData->right).load(memory_order_relaxed))); }
   unvalidated<lock_guard> lock() { return unvalidated(lock_guard(atomic_ref(rawData->lock).load(memory_order_seq_cst))); }
};

Note that the lock() accessor returns an unvalidated<lock_guard>: before we can hand off to the next node’s lock, we must first validate the current guard to ensure we actually read a valid lock. This ensures that lock acquisition itself is part of the validated chain.

With this design, the optimistic code only accesses data via an OptimisticPtr, which makes it impossible to access the data without prior validation. This greatly improves the robustness of the approach. It is a bit annoying that we have to manually implement accessor functions in the OptimisticView, but hopefully the compiler will do that in the future automatically.

Using these abstractions, our lookup code now becomes:

option<value_type> Tree::lookup(key_type key) {
   restart: lock_guard guard = lock.lock_optimistic();
   auto iterOpt = guard.validate(getRootOptimistic());
   if (!iterOpt) goto restart;
   OptimisticPtr<Node> iter = *iterOpt;
   option<value_type> result;
   while (iter) {
      auto currentKey = guard.validate(iter.data().key());
      if (!currentKey) goto restart;
      if (key == *currentKey) {
         auto currentValue = guard.validate(iter.data().value());
         if (!currentValue) goto restart;
         result = *currentValue;
         break;
      }
      auto next = guard.validate((key < *currentKey) ? iter.data().left() : iter.data().right());
      if (!next) goto restart;
      iter = *next;
      auto nextGuard = guard.validate(iter.data().lock());
      if (!nextGuard) goto restart;
      guard = *nextGuard;      
   }
   return result;
}

The code is nearly identical to the unsafe version above, but now it becomes impossible to forget to validate, as the compiler complains otherwise. This makes this highly attractive concurrency paradigm robust and easy to use for all kinds of data structures.

In summary, Optimistic Lock Coupling gives us near-lockfree read scalability while still supporting safe concurrent writes. And by encoding validation requirements in the type system, we get the performance benefits without sacrificing correctness. The compiler catches the mistakes that would otherwise become subtle race conditions at runtime.