Running in your browser · 84 KB WebAssembly

Try to break the ceiling.

Below is a two-table join you control. The true row count is computed by actually building the relations and counting matches. The ceiling comes from samkhya, compiled to WebAssembly and running here — it sees only the row counts and distinct counts, never the data.

Move anything you like. The ceiling must never fall below the truth. If you ever get it to, you have found a bug worth reporting.

For what it is worth, a scripted sweep of 73,205 configurations through this same binary — every combination of row counts, distinct counts and skew levels — found 0 violations, with the tightest ratio landing at exactly 1.000×. Your turn.

Relation A — orders

rows 10

distinct join keys 10

Relation B — line items

rows 100

distinct join keys 10

Data shape

skew — rows piled on one key 100%

At 100% the surplus rows all share a single key — the worst case, and the shape that exposed the old bound as unsound.

True outputcounted from the data

—

samkhya ceilingproved, never sees the data

—

Cartesian productthe bound without statistics

—

Holds The ceiling is at or above the true output.

configurations tried 0 violations found 0 tightest so far —

What the ceiling is allowed to know

Four numbers: two row counts and two distinct-key counts. From those it derives a bound on the degree — how many rows can share one key — as rows − distinct + 1, and multiplies along the join. It never looks at a single value.

import init, { joinCeiling } from './demo/pkg/samkhya_wasm.js';
await init();

// rows, flattened edge pairs, distinct counts
joinCeiling([rowsA, rowsB], [0, 1], [distinctA, distinctB]);

That is the same function, from the same 84 KB binary, that the npm package exports. Nothing on this page is simulated.

Why "all keys unique" is the interesting preset

Set both distinct counts equal to their row counts and the degree bound collapses to 1 on each side. The ceiling becomes exactly min(rowsA, rowsB) — and the true output is exactly that too. A foreign-key join is where a provable bound happens to also be a tight one, which is why it matters that analytical workloads are mostly foreign-key joins.

Now drag distinct down while leaving rows alone. The ceiling climbs, because fewer distinct keys means more rows can collide — and the truth climbs with it. Watch the gap: that is the price of not knowing the data.