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

nodedb_sql/planner/bitmap_emit/
predicate.rs
