akar_storage/
predicate.rs

1//! Zone map predicate skipping for column scans.
2//!
3//! Uses column min/max statistics to determine whether a column chunk
4//! can be skipped during a scan, avoiding unnecessary I/O.
5//!
6//! Ported from C++ `src/include/storage/predicate/` (column_predicate.h,
7//! constant_predicate.h, null_predicate.h) and `src/storage/predicate/`.
8
9use std::cmp::Ordering;
10
11use akar_common::types::Value;
12
13/// Result of checking a zone map against a predicate.
14#[derive(Debug, Clone, Copy, PartialEq, Eq)]
15pub enum ZoneMapCheckResult {
16    /// Cannot determine — must scan the chunk.
17    AlwaysScan = 0,
18    /// Predicate definitely won't match — safe to skip.
19    SkipScan = 1,
20}
21
22/// Statistics for a column chunk, used for zone map predicate checking.
23#[derive(Debug, Clone)]
24pub struct ColumnChunkStats {
25    /// Minimum value in the chunk (None if unknown).
26    pub min: Option<Value>,
27    /// Maximum value in the chunk (None if unknown).
28    pub max: Option<Value>,
29    /// Whether the chunk is guaranteed to have no nulls.
30    pub guaranteed_no_nulls: bool,
31    /// Whether the chunk is guaranteed to have all nulls.
32    pub guaranteed_all_nulls: bool,
33}
34
35impl ColumnChunkStats {
36    pub fn new(min: Option<Value>, max: Option<Value>) -> Self {
37        Self {
38            min,
39            max,
40            guaranteed_no_nulls: true,
41            guaranteed_all_nulls: false,
42        }
43    }
44
45    /// Create stats for an all-null chunk.
46    pub fn all_nulls() -> Self {
47        Self {
48            min: None,
49            max: None,
50            guaranteed_no_nulls: false,
51            guaranteed_all_nulls: true,
52        }
53    }
54
55    /// Update min/max with a new value.
56    ///
57    /// Works for every ordered primitive `Value` type (numeric, Bool, String,
58    /// Date/Timestamp variants, InternalID). Null values are not ordered: they
59    /// clear `guaranteed_no_nulls` and leave min/max untouched so a later
60    /// non-null value is not compared against a `Null` sentinel.
61    ///
62    /// Values whose type cannot be ordered relative to the existing min/max
63    /// (mismatched types, Blob/List/Map/...) are ignored for the min/max
64    /// bounds — the stats stay conservative and never cause a wrong
65    /// `SkipScan` (P52.22).
66    pub fn update(&mut self, val: &Value) {
67        if matches!(val, Value::Null) {
68            self.guaranteed_no_nulls = false;
69            return;
70        }
71        self.guaranteed_all_nulls = false;
72        match (&self.min, &self.max) {
73            (None, None) => {
74                self.min = Some(val.clone());
75                self.max = Some(val.clone());
76            }
77            (Some(min), Some(max)) => {
78                if value_cmp(val, min) == Some(Ordering::Less) {
79                    self.min = Some(val.clone());
80                }
81                if value_cmp(val, max) == Some(Ordering::Greater) {
82                    self.max = Some(val.clone());
83                }
84            }
85            _ => unreachable!(),
86        }
87    }
88}
89
90/// Order two `Value`s of the same primitive kind.
91///
92/// Returns `Some(ordering)` when the pair is comparable, `None` otherwise
93/// (mismatched types or non-ordered kinds such as Blob/List/Map/Union).
94fn value_cmp(a: &Value, b: &Value) -> Option<Ordering> {
95    let ord = match (a, b) {
96        (Value::Bool(x), Value::Bool(y)) => x.cmp(y),
97        (Value::Int64(x), Value::Int64(y)) => x.cmp(y),
98        (Value::Int32(x), Value::Int32(y)) => x.cmp(y),
99        (Value::Int16(x), Value::Int16(y)) => x.cmp(y),
100        (Value::Int8(x), Value::Int8(y)) => x.cmp(y),
101        (Value::UInt64(x), Value::UInt64(y)) => x.cmp(y),
102        (Value::UInt32(x), Value::UInt32(y)) => x.cmp(y),
103        (Value::UInt16(x), Value::UInt16(y)) => x.cmp(y),
104        (Value::UInt8(x), Value::UInt8(y)) => x.cmp(y),
105        (Value::Int128(x), Value::Int128(y)) => x.cmp(y),
106        (Value::UInt128(x), Value::UInt128(y)) => x.cmp(y),
107        (Value::Double(x), Value::Double(y)) => x.partial_cmp(y)?,
108        (Value::Float(x), Value::Float(y)) => x.partial_cmp(y)?,
109        (Value::String(x), Value::String(y)) => x.cmp(y),
110        (Value::Date(x), Value::Date(y)) => x.cmp(y),
111        (Value::Timestamp(x), Value::Timestamp(y)) => x.cmp(y),
112        (Value::TimestampTz(x), Value::TimestampTz(y)) => x.0.cmp(&y.0),
113        (Value::TimestampNs(x), Value::TimestampNs(y)) => x.cmp(y),
114        (Value::TimestampMs(x), Value::TimestampMs(y)) => x.cmp(y),
115        (Value::TimestampSec(x), Value::TimestampSec(y)) => x.cmp(y),
116        // InternalID orders by table, then offset.
117        (Value::InternalID(x), Value::InternalID(y)) => (x.table_id, x.offset).cmp(&(y.table_id, y.offset)),
118        _ => return None,
119    };
120    Some(ord)
121}
122
123// ==================== Check helpers ====================
124
125/// Check if a value falls within [min, max].
126fn in_range<T: PartialOrd>(min: &T, max: &T, val: &T) -> bool {
127    val >= min && val <= max
128}
129
130/// Zone map check for constant-value comparison predicates.
131/// Returns `SkipScan` if the predicate cannot possibly match the zone.
132fn check_constant_predicate<T: PartialOrd>(min: &T, max: &T, constant: &T, op: &str) -> ZoneMapCheckResult {
133    match op {
134        "=" | "==" => {
135            if !in_range(min, max, constant) {
136                return ZoneMapCheckResult::SkipScan;
137            }
138        }
139        "!=" | "<>" => {
140            if constant == min && constant == max {
141                return ZoneMapCheckResult::SkipScan;
142            }
143        }
144        ">" => {
145            if constant >= max {
146                return ZoneMapCheckResult::SkipScan;
147            }
148        }
149        ">=" => {
150            if constant > max {
151                return ZoneMapCheckResult::SkipScan;
152            }
153        }
154        "<" => {
155            if constant <= min {
156                return ZoneMapCheckResult::SkipScan;
157            }
158        }
159        "<=" if constant < min => {
160            return ZoneMapCheckResult::SkipScan;
161        }
162        _ => {}
163    }
164    ZoneMapCheckResult::AlwaysScan
165}
166
167/// Check whether a column chunk with the given stats can be skipped
168/// based on a predicate `(column op constant)`.
169///
170/// Returns `SkipScan` if the chunk definitely doesn't match.
171pub fn check_zone_map(stats: &ColumnChunkStats, op: &str, constant: &Value) -> ZoneMapCheckResult {
172    let (Some(min), Some(max)) = (&stats.min, &stats.max) else {
173        return ZoneMapCheckResult::AlwaysScan;
174    };
175
176    // Type-based dispatch for comparison
177    match (min, max, constant) {
178        (Value::Bool(a), Value::Bool(b), Value::Bool(c)) => check_constant_predicate(a, b, c, op),
179        // Integers (all widths)
180        (Value::Int64(a), Value::Int64(b), Value::Int64(c)) => check_constant_predicate(a, b, c, op),
181        (Value::Int32(a), Value::Int32(b), Value::Int32(c)) => check_constant_predicate(a, b, c, op),
182        (Value::Int16(a), Value::Int16(b), Value::Int16(c)) => check_constant_predicate(a, b, c, op),
183        (Value::Int8(a), Value::Int8(b), Value::Int8(c)) => check_constant_predicate(a, b, c, op),
184        (Value::UInt64(a), Value::UInt64(b), Value::UInt64(c)) => check_constant_predicate(a, b, c, op),
185        (Value::UInt32(a), Value::UInt32(b), Value::UInt32(c)) => check_constant_predicate(a, b, c, op),
186        (Value::UInt16(a), Value::UInt16(b), Value::UInt16(c)) => check_constant_predicate(a, b, c, op),
187        (Value::UInt8(a), Value::UInt8(b), Value::UInt8(c)) => check_constant_predicate(a, b, c, op),
188        (Value::Int128(a), Value::Int128(b), Value::Int128(c)) => check_constant_predicate(a, b, c, op),
189        (Value::UInt128(a), Value::UInt128(b), Value::UInt128(c)) => check_constant_predicate(a, b, c, op),
190        // Floats
191        (Value::Double(a), Value::Double(b), Value::Double(c)) => check_constant_predicate(a, b, c, op),
192        (Value::Float(a), Value::Float(b), Value::Float(c)) => check_constant_predicate(a, b, c, op),
193        // String
194        (Value::String(a), Value::String(b), Value::String(c)) => check_constant_predicate(a, b, c, op),
195        // Temporal
196        (Value::Date(a), Value::Date(b), Value::Date(c)) => check_constant_predicate(a, b, c, op),
197        (Value::Timestamp(a), Value::Timestamp(b), Value::Timestamp(c)) => check_constant_predicate(a, b, c, op),
198        (Value::TimestampTz(a), Value::TimestampTz(b), Value::TimestampTz(c)) => {
199            // TimestampTZ is a bare i64 (no Ord impl) — compare the inner value.
200            check_constant_predicate(&a.0, &b.0, &c.0, op)
201        }
202        (Value::TimestampNs(a), Value::TimestampNs(b), Value::TimestampNs(c)) => check_constant_predicate(a, b, c, op),
203        (Value::TimestampMs(a), Value::TimestampMs(b), Value::TimestampMs(c)) => check_constant_predicate(a, b, c, op),
204        (Value::TimestampSec(a), Value::TimestampSec(b), Value::TimestampSec(c)) => {
205            check_constant_predicate(a, b, c, op)
206        }
207        // InternalID: order by (table_id, offset) so rows from different
208        // tables never alias each other (P52.22).
209        (Value::InternalID(a), Value::InternalID(b), Value::InternalID(c)) => check_constant_predicate(
210            &(a.table_id, a.offset),
211            &(b.table_id, b.offset),
212            &(c.table_id, c.offset),
213            op,
214        ),
215        // Mixed/unknown types — fall back to AlwaysScan (never wrong-skip)
216        _ => ZoneMapCheckResult::AlwaysScan,
217    }
218}
219
220/// Check a null predicate against chunk stats.
221/// `is_null` is true for `IS NULL`, false for `IS NOT NULL`.
222pub fn check_null_zone_map(stats: &ColumnChunkStats, is_null: bool) -> ZoneMapCheckResult {
223    if is_null {
224        if stats.guaranteed_no_nulls {
225            return ZoneMapCheckResult::SkipScan;
226        }
227    } else if stats.guaranteed_all_nulls {
228        return ZoneMapCheckResult::SkipScan;
229    }
230    ZoneMapCheckResult::AlwaysScan
231}
232
233#[cfg(test)]
234mod tests {
235    use super::*;
236    use akar_common::types::{Date, InternalID};
237
238    fn int_stats(min: i64, max: i64) -> ColumnChunkStats {
239        ColumnChunkStats::new(Some(Value::Int64(min)), Some(Value::Int64(max)))
240    }
241
242    #[test]
243    fn test_eq_in_range() {
244        let stats = int_stats(10, 20);
245        assert_eq!(
246            check_zone_map(&stats, "=", &Value::Int64(15)),
247            ZoneMapCheckResult::AlwaysScan
248        );
249    }
250
251    #[test]
252    fn test_eq_out_of_range() {
253        let stats = int_stats(10, 20);
254        assert_eq!(
255            check_zone_map(&stats, "=", &Value::Int64(25)),
256            ZoneMapCheckResult::SkipScan
257        );
258    }
259
260    #[test]
261    fn test_eq_below_range() {
262        let stats = int_stats(10, 20);
263        assert_eq!(
264            check_zone_map(&stats, "=", &Value::Int64(5)),
265            ZoneMapCheckResult::SkipScan
266        );
267    }
268
269    #[test]
270    fn test_gt_all_below() {
271        let stats = int_stats(10, 20);
272        // constant > max → nothing in chunk can match
273        assert_eq!(
274            check_zone_map(&stats, ">", &Value::Int64(25)),
275            ZoneMapCheckResult::SkipScan
276        );
277    }
278
279    #[test]
280    fn test_gt_some_above() {
281        let stats = int_stats(10, 20);
282        assert_eq!(
283            check_zone_map(&stats, ">", &Value::Int64(5)),
284            ZoneMapCheckResult::AlwaysScan
285        );
286    }
287
288    #[test]
289    fn test_lt_all_above() {
290        let stats = int_stats(10, 20);
291        // constant < min → nothing in chunk can match
292        assert_eq!(
293            check_zone_map(&stats, "<", &Value::Int64(5)),
294            ZoneMapCheckResult::SkipScan
295        );
296    }
297
298    #[test]
299    fn test_lt_some_below() {
300        let stats = int_stats(10, 20);
301        assert_eq!(
302            check_zone_map(&stats, "<", &Value::Int64(25)),
303            ZoneMapCheckResult::AlwaysScan
304        );
305    }
306
307    #[test]
308    fn test_gte_eq_max_not_skip() {
309        let stats = int_stats(10, 20);
310        // constant == max → >= can match
311        assert_eq!(
312            check_zone_map(&stats, ">=", &Value::Int64(20)),
313            ZoneMapCheckResult::AlwaysScan
314        );
315    }
316
317    #[test]
318    fn test_gte_gt_max() {
319        let stats = int_stats(10, 20);
320        // constant > max → >= can't match
321        assert_eq!(
322            check_zone_map(&stats, ">=", &Value::Int64(21)),
323            ZoneMapCheckResult::SkipScan
324        );
325    }
326
327    #[test]
328    fn test_lte_eq_min_not_skip() {
329        let stats = int_stats(10, 20);
330        assert_eq!(
331            check_zone_map(&stats, "<=", &Value::Int64(10)),
332            ZoneMapCheckResult::AlwaysScan
333        );
334    }
335
336    #[test]
337    fn test_lte_lt_min() {
338        let stats = int_stats(10, 20);
339        assert_eq!(
340            check_zone_map(&stats, "<=", &Value::Int64(9)),
341            ZoneMapCheckResult::SkipScan
342        );
343    }
344
345    #[test]
346    fn test_not_eq_single_value() {
347        let stats = int_stats(15, 15);
348        // constant == min == max → not_eq can't match
349        assert_eq!(
350            check_zone_map(&stats, "!=", &Value::Int64(15)),
351            ZoneMapCheckResult::SkipScan
352        );
353    }
354
355    #[test]
356    fn test_not_eq_range() {
357        let stats = int_stats(10, 20);
358        // constant within range → might match
359        assert_eq!(
360            check_zone_map(&stats, "!=", &Value::Int64(15)),
361            ZoneMapCheckResult::AlwaysScan
362        );
363    }
364
365    #[test]
366    fn test_null_predicate_is_null_no_nulls() {
367        let stats = ColumnChunkStats {
368            min: Some(Value::Int64(1)),
369            max: Some(Value::Int64(10)),
370            guaranteed_no_nulls: true,
371            guaranteed_all_nulls: false,
372        };
373        assert_eq!(check_null_zone_map(&stats, true), ZoneMapCheckResult::SkipScan);
374    }
375
376    #[test]
377    fn test_null_predicate_is_null_has_nulls() {
378        let stats = ColumnChunkStats {
379            min: Some(Value::Int64(1)),
380            max: Some(Value::Int64(10)),
381            guaranteed_no_nulls: false,
382            guaranteed_all_nulls: false,
383        };
384        assert_eq!(check_null_zone_map(&stats, true), ZoneMapCheckResult::AlwaysScan);
385    }
386
387    #[test]
388    fn test_null_predicate_is_not_null_all_nulls() {
389        let stats = ColumnChunkStats {
390            min: None,
391            max: None,
392            guaranteed_no_nulls: false,
393            guaranteed_all_nulls: true,
394        };
395        assert_eq!(check_null_zone_map(&stats, false), ZoneMapCheckResult::SkipScan);
396    }
397
398    #[test]
399    fn test_no_stats_always_scan() {
400        let stats = ColumnChunkStats::new(None, None);
401        assert_eq!(
402            check_zone_map(&stats, "=", &Value::Int64(5)),
403            ZoneMapCheckResult::AlwaysScan
404        );
405    }
406
407    #[test]
408    fn test_string_zone_map() {
409        let stats = ColumnChunkStats::new(
410            Some(Value::String("apple".into())),
411            Some(Value::String("banana".into())),
412        );
413        // "cherry" > "banana" → skip
414        assert_eq!(
415            check_zone_map(&stats, "=", &Value::String("cherry".into())),
416            ZoneMapCheckResult::SkipScan
417        );
418        // "avocado" within [apple, banana] → scan
419        assert_eq!(
420            check_zone_map(&stats, "=", &Value::String("avocado".into())),
421            ZoneMapCheckResult::AlwaysScan
422        );
423    }
424
425    #[test]
426    fn test_internal_id_zone_map() {
427        let stats = ColumnChunkStats::new(
428            Some(Value::InternalID(InternalID { offset: 0, table_id: 1 })),
429            Some(Value::InternalID(InternalID {
430                offset: 100,
431                table_id: 1,
432            })),
433        );
434        assert_eq!(
435            check_zone_map(
436                &stats,
437                "=",
438                &Value::InternalID(InternalID {
439                    offset: 50,
440                    table_id: 1
441                })
442            ),
443            ZoneMapCheckResult::AlwaysScan
444        );
445        assert_eq!(
446            check_zone_map(
447                &stats,
448                "=",
449                &Value::InternalID(InternalID {
450                    offset: 200,
451                    table_id: 1
452                })
453            ),
454            ZoneMapCheckResult::SkipScan
455        );
456    }
457
458    #[test]
459    fn test_double_zone_map() {
460        let stats = ColumnChunkStats::new(Some(Value::Double(1.5)), Some(Value::Double(9.5)));
461        assert_eq!(
462            check_zone_map(&stats, ">", &Value::Double(10.0)),
463            ZoneMapCheckResult::SkipScan
464        );
465        assert_eq!(
466            check_zone_map(&stats, "<", &Value::Double(1.0)),
467            ZoneMapCheckResult::SkipScan
468        );
469    }
470
471    #[test]
472    fn test_column_chunk_stats_update() {
473        let mut stats = ColumnChunkStats::new(None, None);
474        stats.update(&Value::Int64(5));
475        assert_eq!(stats.min, Some(Value::Int64(5)));
476        assert_eq!(stats.max, Some(Value::Int64(5)));
477
478        stats.update(&Value::Int64(3));
479        assert_eq!(stats.min, Some(Value::Int64(3)));
480        assert_eq!(stats.max, Some(Value::Int64(5)));
481
482        stats.update(&Value::Int64(10));
483        assert_eq!(stats.min, Some(Value::Int64(3)));
484        assert_eq!(stats.max, Some(Value::Int64(10)));
485    }
486
487    #[test]
488    fn test_column_chunk_stats_null_tracking() {
489        let mut stats = ColumnChunkStats::new(None, None);
490        assert!(stats.guaranteed_no_nulls, "empty chunk has no nulls");
491
492        stats.update(&Value::Null);
493        assert!(
494            !stats.guaranteed_no_nulls,
495            "appending Null must clear guaranteed_no_nulls"
496        );
497        assert_eq!(stats.min, None, "Null must not become min");
498        assert_eq!(stats.max, None, "Null must not become max");
499
500        stats.update(&Value::Int64(5));
501        assert_eq!(stats.min, Some(Value::Int64(5)));
502        assert_eq!(stats.max, Some(Value::Int64(5)));
503        assert!(!stats.guaranteed_no_nulls, "flag stays cleared after a null");
504        assert!(!stats.guaranteed_all_nulls, "non-null value clears all-nulls");
505
506        stats.update(&Value::Null);
507        assert_eq!(stats.min, Some(Value::Int64(5)), "later Null must not corrupt min/max");
508        assert_eq!(stats.max, Some(Value::Int64(5)));
509        assert_eq!(
510            check_null_zone_map(&stats, true),
511            ZoneMapCheckResult::AlwaysScan,
512            "IS NULL must scan when chunk has nulls"
513        );
514    }
515
516    #[test]
517    fn test_column_chunk_stats_all_nulls() {
518        let mut stats = ColumnChunkStats::new(None, None);
519        stats.update(&Value::Null);
520        stats.update(&Value::Null);
521        assert!(!stats.guaranteed_no_nulls);
522        assert_eq!(stats.min, None);
523        assert_eq!(stats.max, None);
524    }
525
526    #[test]
527    fn test_bool_zone_map_and_stats() {
528        // Bool min/max must track correctly: false < true (P52.22).
529        let mut stats = ColumnChunkStats::new(None, None);
530        stats.update(&Value::Bool(true));
531        stats.update(&Value::Bool(false));
532        assert_eq!(stats.min, Some(Value::Bool(false)));
533        assert_eq!(stats.max, Some(Value::Bool(true)));
534
535        // Single-value chunk: "!=" against that value can skip; "=" can't.
536        let single = ColumnChunkStats::new(Some(Value::Bool(true)), Some(Value::Bool(true)));
537        assert_eq!(
538            check_zone_map(&single, "!=", &Value::Bool(true)),
539            ZoneMapCheckResult::SkipScan
540        );
541        assert_eq!(
542            check_zone_map(&single, "=", &Value::Bool(true)),
543            ZoneMapCheckResult::AlwaysScan
544        );
545        assert_eq!(
546            check_zone_map(&single, "=", &Value::Bool(false)),
547            ZoneMapCheckResult::SkipScan
548        );
549    }
550
551    #[test]
552    fn test_date_zone_map_and_stats() {
553        // Date min/max must track (P52.22) so a scan never wrong-skips.
554        let mut stats = ColumnChunkStats::new(None, None);
555        stats.update(&Value::Date(Date(10)));
556        stats.update(&Value::Date(Date(5)));
557        stats.update(&Value::Date(Date(20)));
558        assert_eq!(stats.min, Some(Value::Date(Date(5))));
559        assert_eq!(stats.max, Some(Value::Date(Date(20))));
560
561        assert_eq!(
562            check_zone_map(&stats, "=", &Value::Date(Date(25))),
563            ZoneMapCheckResult::SkipScan
564        );
565        assert_eq!(
566            check_zone_map(&stats, "=", &Value::Date(Date(10))),
567            ZoneMapCheckResult::AlwaysScan
568        );
569    }
570
571    #[test]
572    fn test_internal_id_zone_map_respects_table_id() {
573        // Regression for P52.22: InternalID is ordered by (table_id, offset).
574        // A chunk holding only table-1 rows must NOT be skipped for a constant
575        // with the same offset but a different table — every row matches.
576        let stats = ColumnChunkStats::new(
577            Some(Value::InternalID(InternalID { table_id: 1, offset: 5 })),
578            Some(Value::InternalID(InternalID { table_id: 1, offset: 5 })),
579        );
580        assert_eq!(
581            check_zone_map(&stats, "!=", &Value::InternalID(InternalID { table_id: 2, offset: 5 })),
582            ZoneMapCheckResult::AlwaysScan
583        );
584        assert_eq!(
585            check_zone_map(&stats, "=", &Value::InternalID(InternalID { table_id: 2, offset: 5 })),
586            ZoneMapCheckResult::SkipScan
587        );
588    }
589}
akar_storage/predicate.rs

akar_storage/
predicate.rs
