Struct ChainBound 

pub struct ChainBound {
    pub distinct_counts: Vec<u64>,
}

Degree-derived chain-join upper bound.

Takes a per-relation distinct-key count and converts it into a sound bound on the relation’s maximum join degree, maxdeg_i ≤ |R_i| − D_i + 1, then applies the spanning-tree degree ceiling from crate::degree. Falls back to ProductBound when no equality predicates are supplied.

Caller obligation

distinct_counts[i] must be the distinct-value count of the join key relation i carries, and it must not over-state the truth — an HLL reading that comes back high would relax the derived degree bound in the unsafe direction. crate::sketches::HllSketch readings should be used at or below their estimate, not above it.

Soundness note (changed in 1.2.0)

Through v1.1 this bound divided the Cartesian product by max(D_i, D_j) per predicate. That formula is a uniform-distribution estimate, not an upper bound: under skew it lands below the true cardinality. Concretely, two 20-row relations with 5 distinct keys each and 16 rows piled on one key join to 260 rows, while the old formula returned 80. The bound now returns 320 for that instance — larger, and actually provable. See crate::degree for the theorem.

Examples

use samkhya_core::lpbound::{ChainBound, UpperBound};

// A foreign-key join: 10 orders, 100 line items, 10 distinct keys on
// both sides. Bounds exactly at the true output of 100 rows.
let cb = ChainBound::new(vec![10, 10]);
assert_eq!(cb.ceiling(&[10, 100], &[(0, 1)]), 100);

Fields

distinct_counts: Vec<u64>

Implementations

impl ChainBound

pub fn new(distinct_counts: Vec<u64>) -> Self

Construct a chain-join bound from per-relation distinct-key counts.

Examples

use samkhya_core::lpbound::{ChainBound, UpperBound};

// Two 1000-row relations over a key with 100 distinct values: at
// worst 901 rows share one value, so the ceiling is 1000 * 901.
let cb = ChainBound::new(vec![100, 100]);
assert_eq!(cb.ceiling(&[1_000, 1_000], &[(0, 1)]), 901_000);

Trait Implementations

impl UpperBound for ChainBound

fn ceiling( &self, relations: &[u64], equality_predicates: &[(usize, usize)], ) -> u64

Compute the inclusive ceiling for a join.