Repository: qdrant/qdrant
File: lib/segment/src/index/query_estimator.rs (Rust)

Code before:
    }
    let expected_count = expected_should_estimation(estimations.iter().map(|x| x.exp), total);
    CardinalityEstimation {
        primary_clauses: clauses,
        min: estimations.iter().map(|x| x.min).max().unwrap_or(0),
        exp: expected_count,
        max: min(estimations.iter().map(|x| x.max).sum(), total),
    }
}

pub fn combine_min_should_estimations(
    estimations: &[CardinalityEstimation],
    min_count: usize,
    total: usize,
) -> CardinalityEstimation {
    // Guard edge-cases to keep estimator semantics aligned with filter checker:
    // - min_count == 0  => trivially satisfied for all points
    // - min_count > N   => unsatisfiable
    //
    // Also prevents pathological allocation paths in combinations(min_count).
    if min_count == 0 {
        return CardinalityEstimation::exact(total);
    }
    if min_count > estimations.len() {
        return CardinalityEstimation::exact(0);
    }

    /*
    | First estimate cardinality of intersections and then combine the estimations
    | ex) min_count : 2, # of estimations : 4
    | |(A ⋂ B) ∪ (A ⋂ C) ∪ (A ⋂ D) ∪ (B ⋂ C) ∪ (B ⋂ D) ∪ (C ⋂ D)|
     */
    let intersection_estimations = estimations
        .iter()
        .combinations(min_count)
        .map(|intersection| {
            combine_must_estimations(&intersection.into_iter().cloned().collect_vec(), total)
        })
        .collect_vec();

    combine_should_estimations(&intersection_estimations, total)
}

pub fn combine_must_estimations(
    estimations: &[CardinalityEstimation],
    total: usize,
) -> CardinalityEstimation {
    let min_estimation = estimations
        .iter()
        .map(|x| x.min)
        .fold(total as i64, |acc, x| {

Review comment (suggestion):
The current implementation already estimates nicely, but it is not protected against overallocation. Perhaps a simpler fix would be to:
```suggestion
    // Prevent pathological allocation paths in combinations(min_count).
    if min_count > estimations.len() {
        return CardinalityEstimation::exact(0);
    }
```

Code after:
    }
    let expected_count = expected_should_estimation(estimations.iter().map(|x| x.exp), total);
    CardinalityEstimation {
        primary_clauses: clauses,
        min: estimations.iter().map(|x| x.min).max().unwrap_or(0),
        exp: expected_count,
        max: min(estimations.iter().map(|x| x.max).sum(), total),
    }
}

/// Estimate cardinality for `min_should` (at least `min_count` conditions).
///
/// Returns zero immediately when `min_count` exceeds the number of
/// estimations, which matches filter semantics and avoids generating
/// impossible combinations.
pub fn combine_min_should_estimations(
    estimations: &[CardinalityEstimation],
    min_count: usize,
    total: usize,
) -> CardinalityEstimation {
    // Prevent pathological allocation paths in combinations(min_count)
    if min_count > estimations.len() {
        return CardinalityEstimation::exact(0);
    }

    /*
    | First estimate cardinality of intersections and then combine the estimations
    | ex) min_count : 2, # of estimations : 4
    | |(A ⋂ B) ∪ (A ⋂ C) ∪ (A ⋂ D) ∪ (B ⋂ C) ∪ (B ⋂ D) ∪ (C ⋂ D)|
     */
    let intersection_estimations = estimations
        .iter()
        .combinations(min_count)
        .map(|intersection| {
            combine_must_estimations(&intersection.into_iter().cloned().collect_vec(), total)
        })
        .collect_vec();

    combine_should_estimations(&intersection_estimations, total)
}

pub fn combine_must_estimations(
    estimations: &[CardinalityEstimation],
    total: usize,
) -> CardinalityEstimation {
    let min_estimation = estimations
        .iter()
        .map(|x| x.min)
        .fold(total as i64, |acc, x| {
            max(0, acc + (x as i64) - (total as i64))
        }) as usize;