Struct ChainBound 

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

Frequency-moment chain-join upper bound.

Assumes each equality predicate (i, j) joins on a single key whose distinct-value count is given by distinct_counts[i] and distinct_counts[j]. The bound is:

|R_i ⋈ R_j| ≤ |R_i| * |R_j| / max(D_i, D_j)

(Uniform-distribution worst case; tight in expectation when join keys are evenly spread.) Applied sequentially across all equality predicates: the result of each join feeds the next bound.

Tighter than AgmBound for tree / chain joins where each relation has a non-trivial distinct-key count. Falls back to ProductBound when no equality predicates are supplied.

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, joining on a key with 100 distinct values:
// ceiling = 1000 * 1000 / max(100, 100) = 10_000.
let cb = ChainBound::new(vec![100, 100]);
assert_eq!(cb.ceiling(&[1_000, 1_000], &[(0, 1)]), 10_000);

Trait Implementations

impl UpperBound for ChainBound

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

Compute the inclusive ceiling for a join.