spg_engine/
brin.rs

1//! v7.38.11 — read a range predicate's bounds so a BRIN index can say
2//! which slots the scan may skip.
3//!
4//! Lives in its own module, and is `#[cold]` `#[inline(never)]`, for a
5//! measured reason: v7.38.8's conjunct reorder cost two shapes it did
6//! not even touch 17 % and 20 % purely by being compiled into the file
7//! that holds the row loop. This runs once per plan; it has no business
8//! near that loop's code layout.
9
10use alloc::vec::Vec;
11use core::sync::atomic::AtomicU64;
12
13/// Diagnostic only: how often the reader ran, and how often it produced
14/// a slot list. Cheap enough to leave in — one relaxed add per plan.
15pub static PROBE_ENTERED: AtomicU64 = AtomicU64::new(0);
16/// See [`PROBE_ENTERED`].
17pub static PROBE_PRUNED: AtomicU64 = AtomicU64::new(0);
18use core::ops::Range;
19
20use spg_sql::ast::{BinOp, Expr};
21use spg_storage::{Table, Value};
22
23/// The slots a BRIN index cannot rule out for `where_`, or `None` when
24/// nothing about this query and table lets it rule anything out.
25///
26/// `None` means "no opinion" and the caller scans as before. It is
27/// returned for a table with no BRIN index, a predicate with no bound
28/// on a BRIN column, and — deliberately — for a predicate this reader
29/// does not fully understand. Declining is always safe; the danger is
30/// only ever in claiming a range can be skipped.
31#[cold]
32#[inline(never)]
33pub(crate) fn candidate_slots(where_: &Expr, table: &Table) -> Option<Vec<Range<usize>>> {
34    PROBE_ENTERED.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
35    for col_pos in table.brin_columns() {
36        let name = table.schema().columns.get(col_pos)?.name.as_str();
37        let (lo, hi) = bounds_on(where_, name);
38        if lo.is_none() && hi.is_none() {
39            continue;
40        }
41        if let Some(slots) = table.brin_candidate_slots(col_pos, lo, hi) {
42            PROBE_PRUNED.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
43            return Some(slots);
44        }
45    }
46    None
47}
48
49/// Walk the AND-chain and collect the tightest lower and upper bound on
50/// `col_pos`.
51///
52/// Only conjuncts joined by AND count. An OR anywhere above a bound
53/// makes it unusable — `a < 5 OR b > 9` does not restrict `a` — so this
54/// simply does not descend into one.
55fn bounds_on(e: &Expr, col: &str) -> (Option<i64>, Option<i64>) {
56    let mut lo: Option<i64> = None;
57    let mut hi: Option<i64> = None;
58    let mut stack = alloc::vec![e];
59    while let Some(cur) = stack.pop() {
60        match cur {
61            Expr::Binary {
62                lhs,
63                op: BinOp::And,
64                rhs,
65            } => {
66                stack.push(lhs);
67                stack.push(rhs);
68            }
69            Expr::Binary { lhs, op, rhs } => {
70                let Some((op, lit)) = normalise(lhs, *op, rhs, col) else {
71                    continue;
72                };
73                let Some(k) = spg_storage::brin_scalar(&lit) else {
74                    continue;
75                };
76                match op {
77                    // `x > k` cannot be tightened to `k + 1` here: the
78                    // summary comparison is `>=`-shaped and a range
79                    // whose max IS k still has to be visited so the
80                    // predicate itself can reject it.
81                    BinOp::Gt | BinOp::GtEq => lo = Some(lo.map_or(k, |p: i64| p.max(k))),
82                    BinOp::Lt | BinOp::LtEq => hi = Some(hi.map_or(k, |p: i64| p.min(k))),
83                    BinOp::Eq => {
84                        lo = Some(lo.map_or(k, |p: i64| p.max(k)));
85                        hi = Some(hi.map_or(k, |p: i64| p.min(k)));
86                    }
87                    _ => {}
88                }
89            }
90            _ => {}
91        }
92    }
93    (lo, hi)
94}
95
96/// `(op, literal)` with the column on the left, or `None` if this is
97/// not a comparison between THIS column and a literal.
98fn normalise(lhs: &Expr, op: BinOp, rhs: &Expr, col: &str) -> Option<(BinOp, Value<'static>)> {
99    let lit_of = |e: &Expr| match e {
100        Expr::Literal(l) => Some(crate::eval::literal_to_value(l)),
101        _ => None,
102    };
103    let is_col = |e: &Expr| matches!(e, Expr::Column(c) if c.name == col);
104    if is_col(lhs) {
105        return lit_of(rhs).map(|v| (op, v));
106    }
107    if is_col(rhs) {
108        // `5 < x` is `x > 5`.
109        let flipped = match op {
110            BinOp::Lt => BinOp::Gt,
111            BinOp::LtEq => BinOp::GtEq,
112            BinOp::Gt => BinOp::Lt,
113            BinOp::GtEq => BinOp::LtEq,
114            other => other,
115        };
116        return lit_of(lhs).map(|v| (flipped, v));
117    }
118    None
119}
spg_engine/brin.rs

spg_engine/
brin.rs
