Struct AttributeDegree 

pub struct AttributeDegree { /* private fields */ }

Upper bound on how many rows of one relation can share a single value of one join attribute.

Soundness obligation

max_degree must be at least the true maximum degree. Every constructor in this type either derives that guarantee or documents it as the caller’s obligation. Supplying an under-estimate silently makes the resulting ceiling unsound, which defeats the entire point of the envelope.

Implementations

impl AttributeDegree

pub const fn unknown(rows: u64) -> Self

The weakest sound degree: every row could share one value.

Always correct, never informative — a graph built entirely from these yields the Cartesian product.

Examples

use samkhya_core::degree::AttributeDegree;

assert_eq!(AttributeDegree::unknown(500).max_degree(), 500);

pub const fn from_distinct(rows: u64, distinct: u64) -> Self

Derive a degree bound from a row count and a distinct-value count: maxdeg ≤ rows − distinct + 1.

Assign one row to each of the distinct values, then pile every remaining row onto a single value. Nothing can beat that concentration.

Soundness obligation

distinct must be a lower bound on the true number of distinct values. The arithmetic subtracts it, so an over-stated distinct count under-states the degree and yields a ceiling below the truth — the exact failure this module exists to prevent.

This matters because the obvious source is the wrong one: HllSketch::estimate is approximately unbiased and two-sided, so it exceeds the truth about half the time. Use from_hll_floor, which takes a value that is never above the truth.

A distinct of zero (unknown) or greater than rows (an inconsistent reading) falls back to unknown rather than producing an unsound value.

Examples

use samkhya_core::degree::AttributeDegree;

// A key column: every value occurs once.
assert_eq!(AttributeDegree::from_distinct(100, 100).max_degree(), 1);
// 100 rows over 10 values: at worst 91 share one value.
assert_eq!(AttributeDegree::from_distinct(100, 10).max_degree(), 91);
// Unknown distinct count degrades safely.
assert_eq!(AttributeDegree::from_distinct(100, 0).max_degree(), 100);

pub const fn from_upper_bound(rows: u64, upper_bound: u64) -> Self

Use a directly measured or sketch-derived upper bound on the degree.

Soundness obligation

upper_bound must be greater than or equal to the true maximum degree. A Count-Min sketch satisfies this by construction: its frequency estimates never fall below the truth, so the maximum estimate over the inserted keys is a sound bound. An exact scan obviously satisfies it too. A sampled or averaged statistic does not.

The value is capped at rows, since no relation can have a degree above its own row count.

Examples

use samkhya_core::degree::AttributeDegree;

assert_eq!(AttributeDegree::from_upper_bound(1_000, 37).max_degree(), 37);
// Capped at the row count.
assert_eq!(AttributeDegree::from_upper_bound(20, 999).max_degree(), 20);

pub fn from_hll_floor(rows: u64, sketch: &HllSketch) -> Self

Derive a sound degree bound from an HLL sketch of the join column.

Uses HllSketch::nonzero_registers, a distinct-count floor, rather than the two-sided point estimate — see from_distinct for why that distinction decides whether the resulting ceiling is sound.

The floor saturates at the register count, so on a high-cardinality column this degrades toward unknown rather than toward a wrong answer. A Count-Min sketch (from_count_min) bounds far more tightly when one is available.

Examples

use samkhya_core::degree::AttributeDegree;
use samkhya_core::sketches::HllSketch;

let mut hll = HllSketch::new(12).unwrap();
for i in 0..1_000u32 { hll.add(&i.to_le_bytes()); }

let degree = AttributeDegree::from_hll_floor(1_000, &hll);
// Sound: never below the true maximum degree of 1.
assert!(degree.max_degree() >= 1);
assert!(degree.max_degree() <= 1_000);

pub fn from_count_min(rows: u64, sketch: &CountMinSketch) -> Self

Derive a sound degree bound from a Count-Min sketch of the join column — the tightest source available without an exact scan.

For any key k, true_freq(k) <= estimate(k) <= max counter, so the sketch’s largest counter bounds every key’s degree at once. Returns unknown when the sketch has saturated, because that chain of inequalities depends on Count-Min’s never-undercount property, which u32 saturation breaks.

This is the link that makes the ceiling portable: a Count-Min sketch written into a Puffin sidecar by one engine yields a provable join ceiling in another, with no shared catalog and no re-scan.

Examples

use samkhya_core::degree::AttributeDegree;
use samkhya_core::sketches::CountMinSketch;

let mut cms = CountMinSketch::with_defaults();
for _ in 0..9 { cms.add(b"hot-key", 1); }
for _ in 0..2 { cms.add(b"cold-key", 1); }

let degree = AttributeDegree::from_count_min(11, &cms);
// Bounds the true maximum degree of 9 from above, and beats the
// row count the caller would otherwise have to assume.
assert!(degree.max_degree() >= 9);
assert!(degree.max_degree() <= 11);

pub const fn max_degree(&self) -> u64

The bounded maximum degree.

Trait Implementations

impl Clone for AttributeDegree

fn clone(&self) -> AttributeDegree

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Copy for AttributeDegree

impl Debug for AttributeDegree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Eq for AttributeDegree

impl PartialEq for AttributeDegree

fn eq(&self, other: &AttributeDegree) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl StructuralPartialEq for AttributeDegree