Metadata-Version: 2.4
Name: samkhya
Version: 1.2.2
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Information Technology
Classifier: License :: OSI Approved :: Apache Software License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Rust
Classifier: Topic :: Database
Classifier: Topic :: Database :: Database Engines/Servers
Classifier: Topic :: Software Development :: Libraries
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Requires-Dist: pytest>=7 ; extra == 'test'
Provides-Extra: test
Summary: A provable join-cardinality ceiling and portable statistics sketches, for query planning
Keywords: cardinality,sketches,hyperloglog,bloom-filter,count-min-sketch,histogram,query-optimizer
Home-Page: https://github.com/singhpratech/samkhya
Author: Prateek Singh
License: Apache-2.0
Requires-Python: >=3.9
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM
Project-URL: Homepage, https://github.com/singhpratech/samkhya
Project-URL: Issues, https://github.com/singhpratech/samkhya/issues
Project-URL: Repository, https://github.com/singhpratech/samkhya

# 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

```bash
pip install samkhya
```

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

## Sketches

```python
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.

```python
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.

