samkhya v1.1: Never Regress — Putting a Model in Your Query Optimizer Without Letting It Wreck the Plan

samkhya is a Rust SDK that lets a model — a gradient-boosted tree, TabPFN-2.5, even an LLM — correct the row-count estimates your query optimizer runs on, under a provable ceiling that a hallucinating model can never breach. This is the deep dive: the never-regress clamp, the portable Iceberg sidecar, the three swappable backends, and the honest benchmark I pre-registered and then failed — reported as such.

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 entire 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 turns out to be a thousand, or streams a thousand it thought were ten. 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 swappable backends, and the benchmark I pre-registered and then failed.

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 so it learns the shape of your data — 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's load-bearing idea is to separate the suggestion from the guarantee. A corrector — any 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 is pure combinatorics on the data's structure, so it holds regardless of what the model believes.

The effect is best seen with the library's own worked example. An over-eager corrector proposes one million rows for a join whose true cardinality is six. Watch what the clamp does:

The bounds are computed from the join's structure, not the model's opinion. A corrector proposing 1,000,000 is clamped to the LpJoinBound ceiling of 6 — the true count. The model can suggest; it cannot exceed a bound the library can prove.

That is the never-regress 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." The upside is "measurably better when the model has signal." One important 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. Architecturally it's three layers stacked so the safety layer is 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" actually means here: DuckDB, DataFusion, Polars, Postgres, Iceberg, and gpudb all read the same portable payload.
A single Corrector trait. One pluggable surface — propose a corrected estimate given the sketches and whatever feedback exists. This trait is the contribution: 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 has no configuration that can turn it off softly; it's the floor of the design.

Three backends behind one trait

Because correction and safety are separated, the corrector is genuinely swappable, and samkhya ships three reference backends — each gated 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_http feature, for when you have a GPU and want more accuracy.
LLM-pluggable (opt-in). An HTTP corrector that ships 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. Yes, 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 are measured against their own pre-registered bars:

TabPFN-2.5's P95 inference latency is 31.15 ms — comfortably inside the 50 ms budget for sitting in the plan loop. Its q-error reduction over the default GBT is a real but modest 7.84% — direction confirmed, magnitude below the 15% target and reported as falsified.

The honest numbers — including the one I failed

Here is where most library READMEs get shy. samkhya pre-registers its targets and reports every result, including the ones that missed. 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, run against unmodified DataFusion:

On real IMDb queries samkhya never loses a single query — 17 wins, 38 ties, 0 regressions — which is exactly what the never-regress clamp is supposed to buy. But the geomean speedup is 1.038×, far below the ≥1.35× I pre-registered; that target is falsified and reported as such. On an adversarial workload it's about 5% slower.

Read that scoreboard honestly, because it's the whole point of the project. The 0 losses is the guarantee paying off: the clamp did its job and nothing regressed. But the effect size is small — a 1.038× geomean, statistically real (BCa 95% CI [1.026, 1.056], Wilcoxon p=3×10⁻⁶, with false-discovery correction flagging 24 of 55 queries) yet nowhere near the ≥1.35× I wrote down in advance. Three pre-registered upper-bound targets — ≥1.6× join-heavy, ≥1.35× aggregate, ≥1.50× headline — were all falsified, and the receipts name exactly 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, roughly 5% off, with a worst cold-start cell at +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:

On a synthetic star-5 join with uniform skew, the LpJoinBound is 40.95× tighter than the classic AGM worst-case bound (CI [30.93, 47.45]). The honest caveat, stated in the same breath: under heavy-hitter cells (p=2 / p=∞) that advantage collapses to about 1.00×. It's bound tightness, not wallclock.

Why ship a benchmark you failed

Because a number you pre-register and then report even when it embarrasses you is worth more than a number 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 kind of "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 you the losses next to the wins. For an input this deep in the critical path, "never worse, sometimes better, and I'll show you the receipts" is a stronger promise than 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 you can make 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. Start with cargo add samkhya-core — or, if you live in Python, pip install samkhya (the PyO3 bindings ship as a single abi3 wheel) — then build a Puffin sidecar from a column and hand it to the DataFusion adapter. The full quick start is in the repo, and the samkhya project page is a one-page tour — problem, method, the honest numbers, and a live demo command.

Sources

samkhya project page — the one-page overview: problem, method, the honest numbers, and a live demo
samkhya on GitHub — README, architecture, and the bench-results/ receipts for every number above
Rust: samkhya-core on crates.io · docs.rs — Python: samkhya on PyPI (pip install samkhya)
Apache Iceberg — Puffin file format spec
LpBound: Zhang et al., SIGMOD 2025 (Best Paper) — the pessimistic-cardinality idea samkhya's clamp is built on (independent implementation)

Every figure in this post is copied from the samkhya README's "Measured headlines" table and its linked receipts (WAVE4-F + WAVE5-L2). Synthetic microbenchmarks are scoped to exactly what they measure; the real-workload JOB-Slow number is the honest headline.