We Shipped a “Provable” Bound. It Wasn’t Provable.

samkhya exists to make one sentence true: a query optimizer should be able to take a number from a machine-learning model without the model being able to wreck the plan.

The mechanism is a ceiling — a join-cardinality upper bound you can prove, which the corrected estimate is clamped under. A model is allowed to be wrong below the ceiling. It is not allowed to be wrong above it. That asymmetry is the entire safety argument, and it is the reason the library is worth using at all.

In July I ran an audit that materialized the actual output of 926 join queries and compared each one against the ceiling the library had been reporting for them.

The ceiling came in below the true answer in 2,179 of 3,704 bound-evaluations. Fifty-eight point eight percent.

Not loose. Not conservative. Below. The number the join provably could not exceed was, most of the time, smaller than the number of rows the join actually returned. Which means it was never a bound. It was one more estimate wearing the word “provable.”

This post is what broke, how a green test suite hid it, the repair that took violations to zero, and everything I had to retract on the way out.

The oldest bug in the optimizer

Before any of the machine learning, there is a plainer problem. To pick a join order, an optimizer has to guess how many rows each join will return. Every engine does this with summary statistics and independence assumptions that are, politely, optimistic.

The errors would be survivable if they stayed put. They do not. A join tree multiplies: an estimate that is 3× off at the bottom feeds the next join, which is 3× off on top of that, and six levels up you are three orders of magnitude wrong about the size of an intermediate result. The optimizer has by then confidently chosen a hash join and a memory budget for a table it thinks has ten thousand rows and which actually has ten million.

This is why cardinality estimation attracts machine learning. A learned model really can do better than independence assumptions on the workloads it has seen. The problem is what happens on the workloads it hasn’t.

A regression here is not a slightly slower query. It is a plan that never finishes.

Why a ceiling, and not a better guess

So samkhya’s bet was never “the model will be accurate.” It was “the model can be audited by arithmetic.”

You compute, from statistics you already have, a number the join cannot exceed no matter what the data looks like. Then you let whatever corrector you like — gradient-boosted trees, TabPFN, a language model — produce an estimate, and you clamp it under that number. The corrector can be miscalibrated, drifting, or hallucinating outright. It still cannot push the optimizer past a limit that arithmetic controls.

That is a good design. It is only a good design if the wall is actually where you say it is.

The audit: materialize the truth, then check

The v1.1 test suite was green. What it was checking, though, was internal consistency — bounds against each other, bounds against sketch outputs, invariants that all lived on the same side of the question. Nothing in it executed a join and counted the rows that came out.

So that is what the audit did. 1,080 trials — four join topologies × three sizes × three ℓ_p regimes × thirty repetitions. 154 were thrown out because the materialized truth overflowed u64, which left 926 audited trials. Four bounds evaluated on each: 3,704 bound-evaluations, each one compared against a row count that had actually been produced.

Three of the four bounds failed.

ChainBound was unsound in 96% of trials. LpJoinBound in 77%. AgmBound in 63%. ProductBound held at zero — and ProductBound is the trivial one, the straight product of relation sizes, the loosest and least useful bound in the set. The only one that survived was the one doing the least work.

Five joins that walked straight through the ceiling

Aggregates make this sound abstract. The individual cases do not.

Take the first one, because it is the most embarrassing and the most instructive. A textbook foreign-key join: orders with 10 rows, lineitem with 100, every lineitem pointing at an order. The true output is 100 rows. Anyone who has written SQL knows it is 100 rows.

v1.1 reported a provable ceiling of 10.

A corrector clamped under that ceiling would have been forced to tell the optimizer that a join returning 100 rows returns at most 10 — and the clamp would have looked like the safety feature doing its job. The four-relation star is worse in ratio: truth 128, ceiling 2.

How a green suite hid three broken bounds

Each failure had a specific, boring cause, and none of them were subtle once you were looking:

• LpJoinBound — the fractional-edge-cover LP was missing per-attribute constraints. It checked coverage per predicate and quietly ignored private columns, so it solved a smaller problem than the one it claimed to solve.
• AgmBound — computed min(product, |R_min| · |R_max|). On any join of more than two relations, that expression throws away every relation except two. It is not a bound on the query; it is a bound on a sub-query nobody asked about.
• ChainBound — applied a uniform-distribution estimator where a ceiling was required. Uniformity is an assumption about the data, not a fact about it, and skew broke it instantly.

That last one is the whole lesson in miniature. An estimator and a bound are different objects with different obligations. An estimator is allowed to be wrong in both directions; that is what makes it an estimator. A bound has one job, in one direction, and a bound that is wrong in the forbidden direction is not a loose bound — it is a false statement. Somewhere in v1.1, an estimator got called a bound, and the type system had no opinion about it.

I would like to say I caught this by being careful. I caught it by finally comparing against something outside the system.

The repair: multiply degrees along a spanning tree

The fix in v1.2.0 replaces all of it with a single degree-based construction, and the thing I like about it is that it needs no new statistics.

Take the join graph, pick any spanning tree, root it anywhere. Start with the cardinality of the root relation. Walk each tree edge and multiply by the maximum degree across that edge — the largest number of rows on the far side that any single row on the near side can match. That product is a ceiling, and it is a ceiling for a reason you can hold in your head: every output row is some root row, extended along the tree, and each extension is capped by that edge’s maximum degree.

Non-tree edges are ignored, which is safe: extra join predicates can only filter, never add. And the degrees come from statistics already sitting in the Puffin sidecar — HyperLogLog distinct counts and Count-Min sketches that samkhya was writing anyway.

On the foreign-key join that produced a ceiling of 10, the new construction returns 100. Not a safe over-estimate of 100. Exactly 100 — the true output, which is also the tightest sound ceiling that exists for that query.

Re-run the audit, same harness, same trials:

What else came down with it

Once you find one measurement that could not detect its own failure, you have to assume you have others. I did.

The 40.95× bound-tightness figure is withdrawn. It was computed against the bounds that turned out to be unsound, so it was measuring how tight a wrong number was.

The 1.038× JOB-Slow speedup is withdrawn, and so is the entire campaign behind it. The audit found that the arm labelled “corrected” contained no corrector — the benchmark had no flag to attach a trained corrector in the first place. All four trials were OOM-killed at query 55 of 113. Run-order confound accounts for roughly two-thirds of the 3.8% effect that was there. And the root cardinality was always 1, which makes q-error meaningless as a validation metric on that harness. What actually got published was a portable-statistics result under a cardinality-correction headline.

The TabPFN-2.5 q-error claim was pre-registered at a 15% improvement. It measured 7.84%. The direction held; the magnitude threshold I had committed to in advance did not. Pre-registration is only worth something if you report the miss, so: it missed.

And the one I find genuinely useful — on held-out queries, the corrector made estimates worse, geomean q-error going from 13.46 to 26.41. That is a model actively degrading the thing it was added to improve. It is also the exact scenario the ceiling exists for, observed in the wild, in my own benchmark, against my own model.

What I actually believe now

Three things, and only the first is about databases.

A bound needs an adversary, not a test. Every assertion in the v1.1 suite was written by the same person who wrote the bound, in the same frame of mind, checking the same assumptions. Consistency tests cannot catch a shared misconception — they are made of it. The only test that found anything was the one that left the system entirely and materialized ground truth.

Report the direction you lose in. samkhya’s mixed-workload penalty is 0.949× — about 5% slower — and that number is in the README because a benchmark suite where you win everything is a benchmark suite you designed after seeing the results. The corrector-makes-it-worse number is in there for the same reason.

Retract loudly, in the same place you claimed. The withdrawn figures are not quietly gone from the docs; they are marked withdrawn, with the raw data committed and the open items enumerated. A project that only publishes its wins is telling you exactly one thing about its numbers: that you cannot check them.

And plenty is still open. The ceiling has never been measured inside a real query plan — there is no experiment in the repo that runs it in DataFusion and reports the effect on plan quality, which is, awkwardly, the actual claim. The documented reproduction commands do not run as written. Four sections remain credible but untraced to raw data. Those are listed as open, because they are.

The part that survived

The ceiling is sound now: 0 violations in 3,704 bound-evaluations, exact on foreign-key joins, computed from sketches you already have, in a build that also happens to be 84 KB of WebAssembly with TypeScript types if you want it in a browser.

But the claim I am comfortable making is narrower than the one I started with, and I think it is the better claim. It is not that a model will improve your query plans. On my own held-out set, mine made them worse.

It is that you can now find out — on your workload, with your data — without the experiment being able to hurt you.

That is what a ceiling is for.

Try it

cargo add samkhya-core · pip install samkhya · npm install samkhya

Apache-2.0, 15-crate workspace, no GPU in the default build. The soundness audit and the open items are committed in bench-results/ — start there rather than with the README if you want to know what to trust.

Sources

• bench-results/20_bound_soundness.md — the violation table and the five counterexamples
• bench-results/OPEN_AUDIT_ITEMS.md — withdrawn claims and everything still unresolved
• github.com/singhpratech/samkhya — source, verified-numbers table, Apache-2.0