samkhya — Python bindings

Python bindings for samkhya: four portable statistics sketches (HyperLogLog, Bloom, Count-Min, equi-depth histogram) and a provable join-cardinality ceiling — an upper bound the join provably cannot exceed. Compiled Rust behind a stable-ABI (abi3-py39) wheel: no Rust toolchain at install time, one wheel per platform for CPython 3.9+.

Install

pip install samkhya

From a source checkout of this directory: pip install maturin, then maturin develop --release (editable) or maturin build --release.

Sketches

import samkhya

# Precision 14 gives 2^14 = 16384 registers; relative error ~0.8%.
hll = samkhya.HllSketch(14)
for i in range(1000):
    hll.add(str(i).encode("utf-8"))
print(round(hll.estimate()))          # ~1000

# Sketches merge, and serialise for transport (e.g. an Iceberg Puffin blob).
second = samkhya.HllSketch(14)      # same precision, or merge raises
second.add(b"1001")
hll.merge(second)
restored = samkhya.HllSketch.from_bytes(hll.to_bytes())
assert restored.estimate() == hll.estimate()

BloomFilter(n_items, fp_rate), CountMinSketch(width, depth), and EquiDepthHistogram(boundaries, counts) follow the same shape, including to_bytes / from_bytes. Full signatures are in the type stubs: https://github.com/singhpratech/samkhya/blob/main/samkhya-py/python/samkhya/__init__.pyi

The join ceiling

join_ceiling computes a spanning-tree degree ceiling: sound for bag semantics, and exactly tight on foreign-key joins.

import samkhya

rows = [10.0, 100.0]        # 10 orders, 100 line items
joins = [(0, 1)]            # relation 0 joins relation 1
distinct = [10.0, 10.0]     # 10 distinct order keys on both sides

print(samkhya.join_ceiling(joins, rows, distinct))  # 100.0 — the true size
print(samkhya.product_bound(rows))                  # 1000.0

Without distinct_counts the ceiling degrades to the Cartesian product: given only row counts and which pairs are joined, every row can carry the same key value, so nothing below the product is provable.

distinct_counts must be a lower bound on the true distinct count. The degree is derived as rows - distinct + 1, so an overstated distinct count understates the degree and makes the ceiling unsound. Do not feed it HllSketch.estimate(), which is two-sided and exceeds the truth about half the time. Use an exact count, a Count-Min-derived bound, or the Rust-side AttributeDegree::from_hll_floor. Entries that are zero, larger than the row count, or absent degrade safely to "no degree information" rather than to a wrong answer.

distinct_counts is indexed per relation, not per (relation, join column): if a relation joins on several columns, pass the smallest count among them, which overstates the degree and stays sound.

Function reference

• join_ceiling(joins, card_estimates, distinct_counts=None) -> float The bound to use; joins is a list of (left_idx, right_idx).
• product_bound(card_estimates) -> float — Cartesian product fallback.
• agm_bound(joins, card_estimates) -> float — compatibility shim. Its selectivity field is ignored since 1.2; it returns the product.
• selectivity_estimate(joins, card_estimates) -> float — the pre-1.2 agm_bound value, renamed for what it is. An estimate, not a ceiling: it lands below the true cardinality routinely. Never clamp to it.

Changed in 1.2 — soundness fix

A 2026-07-24 audit found the bound family shipped through 1.1 was not sound: it returned ceilings below the true cardinality in 2,179 of 3,704 measured bound-evaluations (58.8%), from multiplying a ceiling by selectivities in [0, 1], which can only shrink it. 1.2 replaces that path with the degree ceiling above: 0 violations, same trials. Two published headline numbers are withdrawn: a 40.95x bound-tightness figure and a 1.038x JOB-Slow speedup.

Errors

Recoverable core errors — out-of-range sketch parameters, malformed serialised payloads, a merge across precisions — raise samkhya.SamkhyaError, a subclass of Exception.

Scope

This wheel exposes the sketches and the ceiling functions, nothing else: no query-engine integration, feedback store, or correction loop — those live in the Rust crates at https://github.com/singhpratech/samkhya. The theorem, its proof, and the full degree-source API are documented at https://docs.rs/samkhya-core under samkhya_core::degree.

Licensed under Apache-2.0.