Every SQL query optimizer runs on a guess. Before it picks a join order it asks a question it usually can't answer well — how many rows will this step produce? — and the whole plan hangs off that number. Get it wrong by a few orders of magnitude, which optimizers routinely do on multi-join queries, and the planner cheerfully builds a hash table for a billion rows that turn out to be a thousand. Bad row-count estimates are the single most reliable way to turn a good schema into a slow one.
samkhya — Sanskrit सांख्य, "enumeration," the classical discipline of counting reality's constituents honestly — is an engine-agnostic Rust SDK whose only job is to make those counts less wrong, and to do it safely. Safely is the whole trick. The moment you let a learned model correct the optimizer's estimates, you've handed the most performance-critical number in the system to something that can be miscalibrated, stale, or — if it's an LLM — outright hallucinating. samkhya's answer is a guarantee it calls never-regress at the bound level: a corrected estimate is clamped under a ceiling the library can prove, so a bad model can never push the optimizer past a bound it can defend.
This is the deep dive — the clamp, the architecture, the three swappable backends, and the benchmark I pre-registered and then failed, reported as such.
The optimizer's oldest bug: it doesn't know how many rows
Cardinality estimation is decades old and still unsolved in practice. Engines lean on histograms and independence assumptions that fall apart the instant columns correlate or joins compose. The errors don't just accumulate; they multiply down a join tree, so a modest per-predicate mistake becomes a catastrophic whole-plan one. The academic fix is well known — feed real execution feedback back into the estimator — but feedback-driven correction has a dangerous failure mode: a correction that's wrong in the other direction makes the plan worse than the naïve estimate you started with. You can't ship a "usually helps" optimizer input. You need one that can't hurt.
Never-regress: a ceiling a model can't argue with
samkhya separates the suggestion from the guarantee. A corrector proposes a number. Then that number is clamped from above by a provable pessimistic ceiling before the optimizer ever sees it. The ceiling is an LpJoinBound: an LP relaxation over the ℓp-norms of the join's degree sequences, inspired by Zhang et al.'s LpBound (SIGMOD 2025 Best Paper — the idea, not a reimplementation), with no machine learning anywhere in it. It's pure combinatorics on the data's structure, so it holds regardless of what the model believes.
The library's own worked example says it best. An over-eager corrector proposes one million rows for a join whose true cardinality is six:
That is the guarantee in one picture: a hallucinating model gets pinned to a ceiling it can't breach, and with no feedback yet — a cold start — samkhya falls back to the engine's own native estimate. The worst case is "the engine you already had." One honesty note the library insists on: this is a guarantee about the bound, not about wallclock. On some workloads samkhya is slower; the benchmarks below say exactly where.
The shape: one sidecar, one trait, one ceiling
samkhya is a library, not a service — no daemon, no background thread, no GPU in the default build, and the whole 13-crate workspace compiles in under two minutes on a laptop with no network. Three layers, safety always last:
-
Portable stats via Iceberg Puffin sidecars. Classical sketches — HyperLogLog, Bloom, Count-Min, equi-depth and 2D correlated histograms — are serialized into versioned,
KIND-tagged blobs inside an Iceberg Puffin file. The same sidecar an ELT pipeline writes is loaded, unchanged, and handed to the DataFusion and client-side DuckDB adapters. No engine owns the stats; the sidecar does. That's what "engine-agnostic" means: DuckDB, DataFusion, Polars, Postgres, Iceberg, and gpudb all read the same portable payload. -
A single
Correctortrait. One pluggable surface: propose a corrected estimate given the sketches and whatever feedback exists. Swap the backend without touching the engine integration or the safety layer. - The LpBound envelope — never regress. Every proposal, from every backend, passes through the clamp above before it reaches the planner. This layer is the floor of the design; there's no soft switch to turn it off.
Three backends behind one trait
Because correction and safety are separated, the corrector is genuinely swappable. samkhya ships three reference backends, each behind a Cargo feature flag and all capped by the same LpBound ceiling:
- GBT (default). A sub-megabyte gradient-boosted-tree backend (gbdt-rs). No GPU, always on, boring in the best way — this is what ships.
-
TabPFN-2.5 (opt-in). A tabular foundation model behind the
tabpfn_httpfeature, for when you have a GPU and want more accuracy. - LLM-pluggable (opt-in). An HTTP corrector shipping dual transport in v1.0: a canonical Python FastAPI server (port 8766) and a parity Node TypeScript port (port 8767) speaking the same wire contract, each with four reference backends — Anthropic, OpenAI, local Ollama, and a dummy. You can put an LLM in the query-optimizer loop precisely because the clamp means it can't hurt you.
The two backends worth putting numbers on, each measured against its own pre-registered bar:
The honest numbers — including the one I failed
Here is where most READMEs get shy. samkhya pre-registers its targets and reports every result, including the misses. The headline real-workload number comes from the actual Join-Order Benchmark — JOB-Slow, 55 paired warm-cache queries from the 113-query IMDb suite, against unmodified DataFusion:
Read that scoreboard honestly, because it's the whole point. The 0 losses is the guarantee paying off — the clamp did its job and nothing regressed. But the effect is small: a 1.038× geomean, statistically real (BCa 95% CI [1.026, 1.056], Wilcoxon p=3×10⁻⁶) yet nowhere near the ≥1.35× I pre-registered. That target — along with ≥1.6× join-heavy and ≥1.50× headline — is falsified, and the receipts name why: warm-cache only, CSV not Parquet, a small query budget, OOM past one heavy query. On a deliberately adversarial workload of seven patterns, samkhya is slower — a 0.949× cross-pattern geomean, ~5% off, worst cold-start cell +12.4%. That row exists on purpose.
The one microbenchmark that shines is the bound's tightness — how close the provable ceiling sits to the truth, which is what makes the clamp useful rather than vacuous:
Here's the measured-headlines table, straight from the repo:
| Headline | Measured | Significance |
|---|---|---|
| JOB-Slow vs DataFusion (real IMDb, n=55) — pre-reg ≥1.35× FALSIFIED | geomean 1.038×; 17W / 38T / 0L | CI [1.026, 1.056]; p=3×10⁻⁶ |
| Adversarial A–G (7 patterns) — reported on purpose | 0.949× (~5% slower); worst +12.4% | per-pattern CIs in receipts |
| LpJoinBound vs AGM tightness (star-5, p=1) | 40.95× tighter | CI [30.93, 47.45]; p=1.73×10⁻⁶ |
| TabPFN-2.5 latency (RTX 4090 Laptop) | P95 31.15 ms (< 50 ms) | CI [29.39, 35.32] |
| TabPFN-2.5 q-error reduction vs GBT | 7.84% (target 15% — magnitude falsified) | CI [2.21, 14.62]; p=1.04×10⁻⁵ |
Why ship a benchmark you failed
Because a number you pre-register and then report even when it embarrasses you is worth more than one you reverse-engineered from whatever your library happened to do. The falsified 1.35× isn't a bug in the write-up; it is the write-up. A cardinality corrector that quietly cherry-picked its wins would be exactly the "usually helps" input you can't trust in a planner. samkhya's pitch is the opposite: a small, real, statistically-defensible improvement on honest workloads, a provable ceiling that guarantees you never regress, and a benchmark table that shows the losses next to the wins. For an input this deep in the critical path, "never worse, sometimes better, and here are the receipts" beats a headline multiple.
Where it fits, and how to try it
samkhya is Apache-2.0, single-author, and built to drop into embedded analytical engines rather than replace them. If you run DuckDB, DataFusion, Polars, Postgres, or an Iceberg lakehouse and your multi-join plans occasionally fall off a cliff, the value proposition is narrow and honest: portable stats you write once and read everywhere, a corrector as simple (GBT) or as ambitious (an LLM) as you like, and a clamp that means the ambitious option can't cost you a regression.
cargo add samkhya-core # Rust
pip install samkhya # Python — PyO3 bindings, single abi3 wheel
Build a Puffin sidecar from a column and hand it to the DataFusion adapter — the full quick start, the architecture, and every receipt behind the numbers above are in the repo. For a one-page tour with a live demo command, see the samkhya project page.
Repo & receipts: project page · samkhya on GitHub · crates.io · PyPI — pip install samkhya · docs.rs · Iceberg Puffin spec
Every figure here is copied from the samkhya README's "Measured headlines" table and its linked bench-results/ receipts. Synthetic microbenchmarks are scoped to exactly what they measure; the real-workload JOB-Slow number is the honest headline.
Top comments (4)
I was particularly intrigued by the concept of the
LpJoinBoundceiling, which ensures that even a miscalibrated model can't push the optimizer past a bound it can defend. The fact that this ceiling is based on pure combinatorics, inspired by Zhang et al.'s LpBound, and doesn't rely on machine learning, provides a strong foundation for the "never-regress" guarantee. I'd love to explore how this approach compares to other cardinality estimation techniques, such as those using Bayesian networks or graphical models, in terms of accuracy and performance trade-offs. How do you see samkhya'sLpJoinBoundceiling interacting with more complex query patterns, such as those involving subqueries or common table expressions?Thanks! The thing that clears it up: the ceiling isn't really estimating
anything — it never guesses the true row count, it just computes a number the
join provably can't exceed, from plain counting, no model or training. So it
isn't competing with a Bayesian network; it's more like a seatbelt around one.
A learned model is built to be accurate and usually is, on the queries it's
seen — but it can also be confidently wrong and talk the planner into a
terrible plan. The ceiling is the opposite: never especially accurate, but
never wrong in the dangerous direction. So the move isn't "pick one" — put your
smart estimate underneath the dumb-but-safe ceiling and keep both.
On subqueries and CTEs, it mostly depends on whether the planner turns them into
joins first — a lot of IN / EXISTS / derived-table stuff gets flattened into
joins anyway, and those are in scope. GROUP BY is a nice case: the result can't
have more rows than there are distinct groups, which is exactly what the HLL
sketch already knows, so you get a clean ceiling for free. Recursive CTEs it
won't touch, and for plain intermediate results the bound gets looser because I
only keep those stats on base tables. But it's still never below the truth, and
whenever it can't bound something cleanly it just steps back and lets the
engine's own estimate stand — so the worst these cases do is give you less help,
never a worse plan.
Sure absolutely !
Some comments may only be visible to logged-in visitors. Sign in to view all comments.