Skip to content

v1.2.1 — the ceiling becomes provable

Choose a tag to compare

View all tags
@singhpratech singhpratech released this 24 Jul 23:47
v1.2.1
d0e1347

Three of the four bounds shipped through v1.1 returned ceilings below the true join cardinality — 2,179 violations in 3,704 measured bound-evaluations. This release repairs them: 0 violations, and on a foreign-key join the ceiling is exactly the true output.

(v1.2.1 is v1.2.0 plus corrected package descriptions — no code change. v1.2.0's crates.io description still advertised "LpBound envelopes", the exact bound family it deprecated.)

Fixed — bound soundness

  • LpJoinBound added one cover constraint per predicate; AGM needs one per attribute, plus full weight for any relation carrying a private column. ceiling(&[10, 100], &[(0,1)]) returned 10 for a foreign-key join that emits 100 rows. Invisible on a triangle — the only shape the tests used.
  • AgmBound's min × max shortcut drops every relation but two. Three 3-row relations chained on one key value join to 27 rows; it returned 9. Now deprecated, returns ProductBound.
  • ChainBound divided the product by max(D_i, D_j) — a uniform-distribution estimate, not a bound. Under skew: truth 260, returned 80.
  • The tightness harness computed (bound / truth).max(1.0), turning every violation into a perfect-tightness reading. It averaged 2,179 violations into its headline and could not have reported one.
  • samkhya-py's agm_bound multiplied a ceiling by caller selectivities, which can only shrink it. Renamed the old behaviour to selectivity_estimate.

Added

  • samkhya-core::degree — a spanning-tree degree ceiling, sound for bag semantics, exactly tight on foreign-key/star/chain shapes. Degrees from a row count, a distinct-count floor, or a Count-Min sketch.
  • samkhya-wasm → npm install samkhya — 84 KB WebAssembly, generated TypeScript types.
  • samkhya-qdrant — provable match-count ceilings for filtered vector search.
  • The corrector can finally be trained and measured. The bench CLI previously had no option that could attach one.
  • tests/soundness_degree.rs — 6 properties × 2,048 cases that brute-force the true join and assert ceiling ≥ truth. The old suite only compared bounds to each other, which holds fine for a family that is wrong together.

Withdrawn

  • 40.95× bound tightness — computed from instances where the bound had fallen below the truth. Corrected: 1.070×.
  • 1.038× JOB-Slow speedup — the "corrected" arm contained no corrector; all four trials were OOM-killed at 55 of 113 queries; removing the cold baseline trial takes it to 1.013×.

Both reproduced against committed raw data in 20_bound_soundness.md and OPEN_AUDIT_ITEMS.md.

Install: cargo add samkhya-core · pip install samkhya · npm install samkhya
Try it: interactive demo — 73,205 configurations swept, 0 violations.

LLM disclosure. The prose in this project, these release notes included, was written with LLM assistance. I am the sole human author of the code and of the analysis, and every number above has been checked against the committed data it cites.

Assets 2
Loading