Portable cardinality correction · Rust SDK
Put a model in your query optimizer —
without letting it wreck the plan.
samkhya lets any engine correct its own row-count estimates with feedback — a gradient-boosted tree, TabPFN, even an LLM. Its load-bearing guarantee is never-regress at the bound level: every corrected estimate is clamped under a provable ceiling. A miscalibrated model or a hallucinating LLM can never push the optimizer past a bound it can prove.
Why this is hard
Optimizers live or die on the row counts they guess.
A wrong estimate picks a wrong plan
Every join order, build side, and hash-vs-merge choice rides on cardinality — how many rows a subquery will emit. Guess a join is small when it's huge and the planner picks a strategy that falls over at runtime.
Models estimate better — sometimes
Learned and feedback-driven estimators beat textbook formulas on the queries they've seen. The literature is a decade deep. But their failure mode is the problem.
A confident wrong model is worse than none
An estimator that hallucinates a huge cardinality can talk the optimizer into a catastrophic plan. That single-tail risk is why production optimizers keep models at arm's length.
samkhya's answer isn't a better model — it's a floor under the worst case. Bolt any estimator on, and cap its output with a ceiling you can prove from the data's own degree sequences. The model can help; it cannot hurt past the bound.
How it works
Three mechanisms, each failing safe toward the engine's native plan.
01 — THE GUARANTEE
Never-regress, at the bound level
Before a corrected estimate reaches the planner, samkhya clamps it under LpJoinBound — a provable pessimistic ceiling, an LP relaxation over ℓp-norms of degree sequences (the idea from Zhang et al., LpBound, SIGMOD 2025 Best Paper — not a reimplementation). No machine learning in the bound itself.
The ceiling is the minimum of a family of provable bounds: ProductBound ≥ {ChainBound, AgmBound} ≥ LpJoinBound. With no feedback yet, cold start falls back to the engine's own estimate. A correction can only ever move the estimate within a range the math already trusts.
corrector proposes 1,000,000 → clamped to 6
02 — PORTABILITY
One stats sidecar, every engine
Classical sketches — HLL, Bloom, Count-Min, equi-depth and 2-D correlated histograms — are serialized into versioned, KIND-tagged blobs inside an Iceberg Puffin sidecar. The same file an ELT job writes at midnight is loaded — unchanged — through Iceberg and handed to DataFusion at noon and DuckDB at three.
No engine owns the statistics; the sidecar does. Strict validation rejects corrupt, duplicate, stale, or schema-mismatched payloads before they reach a planner.
HLL · histogram · CMS
written once · read unchanged
03 — THE CONTRIBUTION
One Corrector trait, swappable backends
The estimator is a plug. fn correct(&features) -> Option<u64> — return a corrected row count, or abstain. Every backend is gated behind a Cargo feature flag and capped from above by the same safety envelope, so swapping the model never changes the guarantee.
- GBT — sub-megabyte gradient-boosted tree (gbdt-rs). The production default; ships on by default.
- TabPFN-2.5 — opt-in transformer evaluator behind
tabpfn_http; P95 31 ms on an RTX 4090 Laptop. - LLM-pluggable — HTTP corrector, Python (FastAPI) and Node (TypeScript) transports, same wire contract. Anthropic / OpenAI / Ollama / dummy references.
Where it makes a difference
The value isn't a speedup number. It's what the guarantee unlocks.
samkhya's honest end-to-end speedup on real join workloads is modest (see the numbers below). The difference it makes is structural — four places where a provable floor and a portable stat layer change what's possible.
Stop recomputing stats per engine
A Parquet/Iceberg lake queried by DataFusion, DuckDB, and batch jobs normally rebuilds statistics in each engine's private format. samkhya makes one Puffin sidecar the shared source of truth — compute the sketch once, consume it everywhere, with identical validation.
Correct estimates without patching the optimizer
You rarely get to rewrite DataFusion's or DuckDB's planner. samkhya integrates at the table-provider and pre-join-rule boundary: corrected, clamped statistics reach the physical plan through public extension points — no fork, no vendored optimizer.
Try an LLM in the optimizer, sleep at night
Because the clamp bounds the blast radius, you can evaluate an aggressive estimator — TabPFN, an LLM — on production-shaped workloads without betting plan stability on it. The worst a bad prediction does is get clamped to a bound the engine already trusts.
Every number pre-registered — including the misses
In the lineage of the "How Good Are Query Optimizers, Really?" line of work, samkhya reports BCa confidence intervals, Wilcoxon tests, and BH-FDR corrections — and publishes the hypotheses it falsified. For teams that need trustworthy measurement, the methodology is the deliverable.
The honest numbers
Measured, not projected — the falsified rows stay in.
Every figure is pre-registered and reported with its confidence interval and receipt. Where a target was missed, the row says so. That's the point.
| What | Measured | CI / significance | Verdict |
|---|---|---|---|
| JOB-Slow end-to-end vs DataFusion 46 real IMDb · n=55 paired · warm cache |
1.038× geomean 17W / 38T / 0L |
BCa [1.026, 1.056] Wilcoxon p=3.0×10⁻⁶ |
≥1.35× falsified real, but small |
| Never-regress guarantee corrected estimate vs provable ceiling |
0 bound violations | proptest + fuzz enforced | holds |
| Mixed / adversarial workload 7 pre-registered patterns A–G |
0.949× geomean ~5% slower; cold-start +12.4% |
per-pattern CIs in receipt | H-G falsified reported on purpose |
| LpJoinBound vs AGM tightness synthetic star-5, p=1 · bound/truth ratio, not wallclock |
40.95× tighter | BCa [30.93, 47.45] p=1.73×10⁻⁶, n=30 |
scoped → 1.00× under p=2/∞ |
| TabPFN-2.5 inference latency RTX 4090 Laptop · B=8 L=128 |
31.15 ms P95 | BCa [29.39, 35.32] | H1-A pass |
| HLL precision p=14, n=10⁶ |
0.676% RSE | BCa [0.535%, 0.848%] vs Flajolet 0.8125% envelope |
within envelope |
Pre-registered JOB-Slow upper bounds (≥1.35× / ≥1.50× / ≥1.6×) were all falsified by the WAVE4-F campaign. The corrector effect is statistically real; the effect size is small. Attributions — warm-cache only, CSV-not-Parquet, n=2 budget cap — are named in the evidence log.
Architecture
Five layers. Each replaceable. Each fails toward the native plan.
The cross-engine matrix
| DataFusion | Production | three-layer integration, DataFusion 46 |
| Iceberg / Arrow | Production | Puffin read/write, field-ID binding |
| DuckDB | Beta | Rust-client path; native ext scaffold |
| Polars | Beta | series→sketch; optimizer hook pending |
| Postgres | Scaffold | pgrx-shaped, feature-gated |
See the guarantee run, no dataset, no setup:
# prints: corrector 1,000,000 → clamped to 6
cargo run -p samkhya-core \
--example honest_demo --features lp_solver