Put an LLM in your query planner without letting it wreck the plan.

What the ceiling actually guarantees.

Everybody wants a language model in the query planner. Almost nobody ships one, and the blocker was never capability — it is blast radius.

A planner does not fail gracefully on a bad row count. Ask a model how many rows a six-way join emits, get back a confidently wrong number, and the optimizer builds a hash table on the wrong side and exhausts memory. The expected case is fine. The tail eats you. That asymmetry is why "let's try an LLM here" has stayed a demo for three years.

A ceiling changes the shape of that risk. The model's answer is clamped under a number derived by counting, so the worst thing a hallucination can do is be ignored. Transport failure, timeout, a malformed reply, a provider outage — every one returns Ok(None) and the engine falls back to its own estimate. The model is allowed to be wrong; it is not allowed to be load-bearing.

What is measured, and what is not

The transport floor is measured. The benefit is not: every live-LLM accuracy cell in the campaign is marked projected, pending API keys, and this page will not pretend otherwise.

Worse, and more usefully — samkhya's own gradient-boosted corrector made things worse on held-out queries in the one honest measurement taken so far: q-error geomean 13.46 without it, 26.41 with it, fitted on a single usable row.

Every query engine guesses, and the guesses compound.

Before running a query, a database estimates how many rows each step will produce. Those estimates decide the plan: which side to build the hash table on, what join order to take, how much memory to reserve.

The estimates are often wrong, and wrong multiplicatively — a modest error at the bottom of a six-table join becomes a thousandfold error at the top. It is the most common reason a query that should take two seconds takes four minutes.

Everyone knows a model could learn to correct this from past queries. Almost nobody ships one, for a single reason: a model that is usually right and occasionally catastrophically wrong is worse than a dumb estimator that is consistently mediocre. One hallucinated row count and the planner picks something that exhausts memory.

samkhya's answer is not a better model. It is a ceiling to put underneath one — a number derived by counting, with no model involved, that the join cannot exceed. Clamp the model to it and it can be as wrong as it likes without moving the planner past a bound that has been proved. A seatbelt, not a faster car.

Why build a bound instead of a better estimator.

samkhya started next to another project. I maintain a GPU-accelerated analytical engine, and the thing that kept hurting was never the kernels — it was the planner acting on a row count that was off by three orders of magnitude.

The obvious move is to learn the correction. The literature has said so for a decade, and it works: feed a model the plan shape and past observations, and it will beat the cost model's guesses on the queries it has seen. I built that. It is the Corrector trait, and it is still in the box.

Then I tried to imagine putting it in front of anything I cared about, and could not. The problem is not the average case, it is the shape of the distribution. A learned estimator that is right 95% of the time and catastrophically wrong 5% of the time is worse to operate than a crude one that is mediocre every time — because the crude one is predictable, and predictability is what capacity planning, memory limits and on-call rotations are built on. Nobody wants to explain that the query planner got creative at 3am.

So the bet is inverted. Rather than make the estimate better, make the failure bounded. Compute a number the join provably cannot exceed, by counting rather than learning, and clamp whatever the model says underneath it. The model keeps its upside on the queries it understands. Its downside stops at a number that has been proved.

Everything else in samkhya follows from that one decision. The sketches exist because the bound needs statistics. The Puffin sidecar exists because those statistics are worth more when they travel between engines than when they are locked in one. The corrector is a trait with swappable backends rather than a fixed model, because if the clamp is what provides the safety then the backend is genuinely an operator's choice — trees today, a foundation model tomorrow, whatever exists in three years.

The name is the Sanskrit सांख्य — enumeration, counting. A classical school whose discipline was counting reality's constituents honestly. That turned out to be a higher bar than intended.

The ceiling, and why it holds.

Given only row counts and which pairs of relations are joined, nothing below the Cartesian product is sound — put every row of every relation on one key value and the equi-join degenerates to a cross product. To beat it you need one more statistic: a bound on the degree, how many rows can share a single value of a join attribute.

It holds for bag semantics — duplicates included — which is what engines actually execute, and it is exactly tight on the foreign-key joins that dominate analytical workloads.

Where the degrees come from

Any over-estimate of the true maximum degree keeps the ceiling sound. Three sources, cheapest first:

The Count-Min route is what makes the ceiling portable. For any key k, true_freq(k) ≤ estimate(k) ≤ max counter, because Count-Min never undercounts. That sketch already rides in samkhya's Puffin sidecar — so a bound proved from statistics written by one engine holds in another, with no shared catalog and no re-scan.

The trap worth naming

The distinct-count derivation subtracts, so it needs a count that is never above the truth. An HLL point estimate is two-sided — it exceeds the truth about half the time — and feeding it in produces a ceiling below the truth. The API therefore ships from_hll_floor, which counts non-zero registers and so can only under-count. Every constructor either derives the guarantee or states the obligation on the caller.

How a project that measures everything shipped an unsound bound twice.

Not through carelessness with tests. Through tests that checked the wrong thing, and a metric that deleted its own failure signal. Two published headline numbers did not survive it.

The tests checked bounds against each other

The property suite ran 1,024 cases per property and asserted LpJoinBound ≤ AgmBound ≤ ProductBound, plus finiteness and monotonicity. All green. Every one of those invariants holds perfectly well for a family of bounds that are all wrong together. Nothing ever compared a bound to a true cardinality.

The fix is one test: generate small relation instances, brute-force the real join, assert ceiling ≥ truth. Six properties, 2,048 cases each. It fails immediately on the old code.

The harness clamped away the evidence

The tightness campaign did materialise instances and compute ground truth. Then it reported:

let r_lp = (lp_b / truth).max(1.0);

A ratio below 1.0 is precisely the signal that a bound has fallen below the truth. .max(1.0) turned every such case into exactly 1.0 — indistinguishable from a perfectly tight sound bound. The campaign averaged 2,179 violations into its headline and was structurally incapable of reporting one.

What was actually wrong

Every witness is a concrete instance whose true cardinality was counted by brute force, not argued.

Every claim, and what it rests on.

Including the ones that did not survive. A project whose selling point is honest measurement does not get to quietly drop the rows that failed.

Why the JOB-Slow number went

It was published as a cardinality-correction result. Reading the committed run scripts: no --corrector flag is passed, so the runner attaches nothing — and the flag's only non-none value was identity, which returns the baseline unchanged. The bench CLI had no option that could attach a trained corrector at all. The two arms differed by exactly one thing: whether portable sidecar statistics were injected.

Alongside that: all four trials exited 137 (OOM-killed) at query 15d against a header announcing 113; arm order was fixed so the coldest run sat in the baseline, and removing it takes 1.038× to 1.013×; every query had two trials per arm, where the smallest attainable exact p is 0.167, so the "24 of 55 significant" count is an artefact of a degenerate bootstrap; and the published q-error is 1.0 everywhere because every JOB query is SELECT MIN(...).

The finding underneath is real, and better than the headline it replaced: portable sidecar statistics, with no model anywhere, moved a real workload at all. That deserves publishing as what it is, after an honest re-run.

Three ways in, one byte format.

A sketch written in a browser deserialises unchanged in a Rust query engine. That is the portability claim, and it is the same code path in every binding.

The ceiling, in JavaScript

import init, { HllSketch, joinCeiling } from 'samkhya';
await init();

const hll = new HllSketch(12);
for (const row of rows) hll.add(row.orderKey);

// 10 orders joined to 100 line items over 10 distinct keys.
joinCeiling([10, 100], [0, 1], [10, 10]);  // 100 — exactly the truth
joinCeiling([10, 100], [0, 1], []);          // 1000 — the product

84 KB WebAssembly, generated TypeScript definitions, no server and no native module.

The ceiling, in Rust

use samkhya_core::degree::{AttributeDegree, JoinGraph, JoinRelation};

let orders = JoinRelation::new(10)
    .with_degree(ORDER_KEY, AttributeDegree::from_distinct(10, 10));
let lineitem = JoinRelation::new(100)
    .with_degree(ORDER_KEY, AttributeDegree::from_distinct(100, 10));

let graph = JoinGraph::new(vec![orders, lineitem]).with_edge(0, 1, ORDER_KEY);
assert_eq!(graph.ceiling(), 100);

Training a corrector without fooling yourself

The harness separates the three steps so a held-out measurement is enforceable rather than aspirational. Freezing the model between steps 2 and 3 is the point: a model written before the evaluation queries ran cannot have seen them.

# 1. Record plan features on a training subset.
samkhya-bench run --suite synthetic --feedback train.db --only S1,S2,S3,S4,S5

# 2. Fit and freeze.
samkhya-bench train --feedback train.db \
    --template samkhya-bench-synthetic --out model.json

# 3. Evaluate on the complement — queries the model has never seen.
samkhya-bench run --suite synthetic --exclude S1,S2,S3,S4,S5 \
    --corrector gbt --model model.json

Skip the split and you measure memorisation. On this suite that reads as q-error improving 4.58 → 1.86; the honest held-out run shows it worsening 13.46 → 26.41. Same model, same code, opposite conclusion.

Where it runs, and where it cannot.

Optimizer integration needs a process you control. The portable sidecar does not — it is a file, and anything that reads Iceberg can consume it. That asymmetry is the real shape of this project.

What is still wrong.

The same audit raised questions this release does not close. They are listed because leaving them unlisted would be the more comfortable choice.

• The JOB-Slow campaign needs a real re-run — with a corrector actually attached, randomised arm order, enough memory to finish all 113 queries, and more than two trials per arm.
• The ceiling has no end-to-end measurement. It is unit-tested and property-tested; its effect on real plan quality is unmeasured. That is the largest hole in the empirical story, and it concerns the project's central contribution.
• Per-join-node q-error is not aggregated. The collection machinery exists; the whole-query metric currently reported is structurally pinned at 1.0 and carries no signal.
• Bloom sizing receipts predate their own fix and need re-running.
• Cyclic queries bound loosely. The hypergraph LP returns the true AGM bound but needs an attribute schema plus a declaration that relations carry no private columns; deriving that automatically is not implemented.

Full register, with each item marked reproduced, credible-but-unverified, or open, in OPEN_AUDIT_ITEMS.md.

Start with the demo — it computes every number it prints.

Or try the live one: a two-table join you control, with the true output counted from the data and the ceiling computed beside it by the same WebAssembly binary the npm package ships. A scripted sweep of 73,205 configurations through it found zero violations — the page invites you to look for the first.

cargo run -p samkhya-core --example honest_demo --features lp_solver

cargo add samkhya-core

pip install samkhya

npm install samkhya

Eleven crates on crates.io. The JavaScript package is built and verified but not yet published.