nodedb_sql/planner/bitmap_emit/
predicate.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! Selective-predicate analysis for bitmap-producer emission.
4//!
5//! Inspects a `SqlPlan` scan or index-lookup node and returns a `BitmapHint`
6//! when the node qualifies for bitmap pushdown:
7//!
8//! - Equality on a `Ready` indexed column (`WHERE col = const`)
9//! - IN-list on a `Ready` indexed column with ≤ 1024 values
10//! - `SqlPlan::DocumentIndexLookup` (already a single-field equality lookup)
11//!
12//! Range predicates with low selectivity are excluded when no statistics are
13//! available — no selectivity guess is made. Only deterministic, index-backed
14//! shapes are emitted.
15//!
16//! The hint carries the collection name, index field, and the predicate value(s)
17//! so the converter layer can build an `IndexedFetch` physical sub-plan.
18
19use crate::types::{CompareOp, FilterExpr, SqlPlan, SqlValue};
20
21/// Maximum IN-list cardinality for which bitmap emission is attempted.
22const MAX_IN_LIST: usize = 1024;
23
24/// A bitmap-producer hint: the plan child qualifies for bitmap pushdown.
25#[derive(Debug, Clone)]
26pub struct BitmapHint {
27    /// Collection whose indexed field will be scanned.
28    pub collection: String,
29    /// Canonical field path (e.g. `$.email` or plain column name).
30    pub field: String,
31    /// Equality value, or the first value when the predicate is an IN-list.
32    pub primary_value: SqlValue,
33    /// Additional values for IN-list expansion (empty for equality).
34    pub extra_values: Vec<SqlValue>,
35}
36
37/// Inspect `plan` and return a `BitmapHint` if the plan qualifies for bitmap
38/// pushdown, or `None` if the plan should run without a prefilter.
39///
40/// Only exact-match shapes on `Ready` indexed columns are considered.
41/// Ranges are never emitted (no statistics available to confirm selectivity).
42pub fn analyze(plan: &SqlPlan) -> Option<BitmapHint> {
43    match plan {
44        // Already a single-field equality index lookup — always qualifies.
45        SqlPlan::DocumentIndexLookup {
46            collection,
47            field,
48            value,
49            ..
50        } => Some(BitmapHint {
51            collection: collection.clone(),
52            field: field.clone(),
53            primary_value: value.clone(),
54            extra_values: Vec::new(),
55        }),
56
57        // Plain scan: inspect WHERE filters for indexed-column equality / IN-list.
58        SqlPlan::Scan {
59            collection,
60            filters,
61            ..
62        } => {
63            // The `SqlPlan::Scan` does not directly carry `IndexSpec` list — that
64            // lives on `TableInfo` which the engine-rules layer consumed when it
65            // chose *not* to rewrite to `DocumentIndexLookup`. However, when the
66            // engine rules DID rewrite to `DocumentIndexLookup`, the caller should
67            // match the first arm above.
68            //
69            // For plain `Scan` nodes we can still detect equality/in-list filters
70            // but we have no way to confirm the column is indexed here — the planner
71            // already had that information. We conservatively return `None` so we
72            // never emit a sub-scan that would do a full table scan disguised as a
73            // bitmap producer. Only the `DocumentIndexLookup` arm (already
74            // index-backed) is emitted unconditionally.
75            //
76            // Future: if `Scan` carries index metadata, extend this arm.
77            analyze_scan_filters(collection, filters)
78        }
79
80        _ => None,
81    }
82}
83
84/// Attempt to extract an equality or bounded IN-list hint from scan filters.
85///
86/// Returns `Some` only when exactly one equality or bounded IN-list predicate
87/// is present at the top level. Conjunctions with more than one equality are
88/// not emitted (too broad; the full scan is cheaper than two lookups).
89///
90/// This is called for plain `Scan` nodes whose engine rules could not confirm
91/// a `Ready` index. Returns `None` to be safe.
92fn analyze_scan_filters(collection: &str, filters: &[crate::types::Filter]) -> Option<BitmapHint> {
93    // Conservative: only emit when there is exactly one filter and it is an
94    // equality or a small IN-list. The caller (engine rules) would have promoted
95    // this to `DocumentIndexLookup` if the index was `Ready`; we skip here to
96    // avoid spurious full-collection sub-scans as "bitmap producers".
97    if filters.len() != 1 {
98        return None;
99    }
100    match &filters[0].expr {
101        FilterExpr::Comparison {
102            field,
103            op: CompareOp::Eq,
104            value,
105        } => Some(BitmapHint {
106            collection: collection.to_string(),
107            field: field.clone(),
108            primary_value: value.clone(),
109            extra_values: Vec::new(),
110        }),
111        FilterExpr::InList { field, values }
112            if !values.is_empty() && values.len() <= MAX_IN_LIST =>
113        {
114            let mut iter = values.iter().cloned();
115            let primary = iter.next()?;
116            Some(BitmapHint {
117                collection: collection.to_string(),
118                field: field.clone(),
119                primary_value: primary,
120                extra_values: iter.collect(),
121            })
122        }
123        _ => None,
124    }
125}
nodedb_sql/planner/bitmap_emit/predicate.rs

nodedb_sql/planner/bitmap_emit/
predicate.rs
