lance_select/result.rs
1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright The Lance Authors
3
4//! Certainty-tagged wrappers around a row-address mask returned by a
5//! scalar-index expression evaluation.
6//!
7//! These types model the three possible degrees of knowledge an index
8//! search can return:
9//!
10//! * [`Exact`] — the mask is the precise answer; no recheck needed.
11//! * [`AtMost`] — the mask is a *superset* of the true answer; the rows
12//! inside the mask must be rechecked against the predicate.
13//! * [`AtLeast`] — the mask is a *subset* of the true answer; the rows
14//! outside the mask must be rechecked against the predicate.
15//!
16//! The boolean algebra (`Not`/`BitAnd`/`BitOr`) is implemented on both
17//! [`NullableIndexExprResult`] (the form during evaluation, carrying SQL
18//! three-valued logic via [`NullableRowAddrMask`]) and
19//! [`IndexExprResult`] (the form consumed by the read planner, after
20//! `drop_nulls` collapses NULL rows into FALSE).
21//!
22//! [`Exact`]: IndexExprResult::Exact
23//! [`AtMost`]: IndexExprResult::AtMost
24//! [`AtLeast`]: IndexExprResult::AtLeast
25
26use crate::mask::{NullableRowAddrMask, RowAddrMask};
27
28/// Result of an index search before NULL rows are dropped. Carries
29/// three-valued-logic information via [`NullableRowAddrMask`].
30#[derive(Debug)]
31pub enum NullableIndexExprResult {
32 Exact(NullableRowAddrMask),
33 AtMost(NullableRowAddrMask),
34 AtLeast(NullableRowAddrMask),
35}
36
37impl std::ops::Not for NullableIndexExprResult {
38 type Output = Self;
39
40 fn not(self) -> Self {
41 // Flip certainty: NOT(AtMost) → AtLeast, NOT(AtLeast) → AtMost.
42 // NULL info is preserved by `NullableRowAddrMask::not` (it flips
43 // AllowList ↔ BlockList without touching the `nulls` field), which
44 // is the 3VL-correct negation: TRUE↔FALSE swap, NULL stays NULL.
45 match self {
46 Self::Exact(mask) => Self::Exact(!mask),
47 Self::AtMost(mask) => Self::AtLeast(!mask),
48 Self::AtLeast(mask) => Self::AtMost(!mask),
49 }
50 }
51}
52
53impl std::ops::BitAnd<Self> for NullableIndexExprResult {
54 type Output = Self;
55
56 fn bitand(self, rhs: Self) -> Self {
57 match (self, rhs) {
58 (Self::Exact(lhs), Self::Exact(rhs)) => Self::Exact(lhs & rhs),
59 (Self::Exact(lhs), Self::AtMost(rhs)) | (Self::AtMost(lhs), Self::Exact(rhs)) => {
60 Self::AtMost(lhs & rhs)
61 }
62 (Self::Exact(exact), Self::AtLeast(_)) | (Self::AtLeast(_), Self::Exact(exact)) => {
63 // We could do better here, elements in both lhs and rhs are known
64 // to be true and don't require a recheck. We only need to recheck
65 // elements in lhs that are not in rhs
66 Self::AtMost(exact)
67 }
68 (Self::AtMost(lhs), Self::AtMost(rhs)) => Self::AtMost(lhs & rhs),
69 (Self::AtLeast(lhs), Self::AtLeast(rhs)) => Self::AtLeast(lhs & rhs),
70 (Self::AtMost(most), Self::AtLeast(_)) | (Self::AtLeast(_), Self::AtMost(most)) => {
71 Self::AtMost(most)
72 }
73 }
74 }
75}
76
77impl std::ops::BitOr<Self> for NullableIndexExprResult {
78 type Output = Self;
79
80 fn bitor(self, rhs: Self) -> Self {
81 match (self, rhs) {
82 (Self::Exact(lhs), Self::Exact(rhs)) => Self::Exact(lhs | rhs),
83 (Self::Exact(lhs), Self::AtMost(rhs)) | (Self::AtMost(rhs), Self::Exact(lhs)) => {
84 // We could do better here, elements in lhs are known to be true
85 // and don't require a recheck. We only need to recheck elements
86 // in rhs that are not in lhs
87 Self::AtMost(lhs | rhs)
88 }
89 (Self::Exact(lhs), Self::AtLeast(rhs)) | (Self::AtLeast(rhs), Self::Exact(lhs)) => {
90 Self::AtLeast(lhs | rhs)
91 }
92 (Self::AtMost(lhs), Self::AtMost(rhs)) => Self::AtMost(lhs | rhs),
93 (Self::AtLeast(lhs), Self::AtLeast(rhs)) => Self::AtLeast(lhs | rhs),
94 (Self::AtMost(_), Self::AtLeast(least)) | (Self::AtLeast(least), Self::AtMost(_)) => {
95 Self::AtLeast(least)
96 }
97 }
98 }
99}
100
101impl NullableIndexExprResult {
102 /// Project NULL rows out of the result.
103 ///
104 /// Under a `WHERE` clause, NULL is treated as FALSE — so `drop_nulls`
105 /// removes them from `AllowList`s (NULL rows are not selected) and
106 /// folds them into `BlockList`s (NULL rows are still blocked).
107 pub fn drop_nulls(self) -> IndexExprResult {
108 match self {
109 Self::Exact(mask) => IndexExprResult::Exact(mask.drop_nulls()),
110 Self::AtMost(mask) => IndexExprResult::AtMost(mask.drop_nulls()),
111 Self::AtLeast(mask) => IndexExprResult::AtLeast(mask.drop_nulls()),
112 }
113 }
114}
115
116/// Result of an index search after NULL rows have been dropped. This is
117/// what the read planner consumes.
118#[derive(Debug)]
119pub enum IndexExprResult {
120 /// The answer is exactly the rows in the allow list minus the rows
121 /// in the block list.
122 Exact(RowAddrMask),
123 /// The answer is at most the rows in the allow list minus the rows
124 /// in the block list. Some of the rows in the allow list may not be
125 /// in the result and will need to be filtered by a recheck. Every
126 /// row in the block list is definitely not in the result.
127 AtMost(RowAddrMask),
128 /// The answer is at least the rows in the allow list minus the rows
129 /// in the block list. Some of the rows in the block list might be in
130 /// the result. Every row in the allow list is definitely in the
131 /// result.
132 AtLeast(RowAddrMask),
133}
134
135impl IndexExprResult {
136 pub fn row_addr_mask(&self) -> &RowAddrMask {
137 match self {
138 Self::Exact(mask) => mask,
139 Self::AtMost(mask) => mask,
140 Self::AtLeast(mask) => mask,
141 }
142 }
143
144 pub fn discriminant(&self) -> u32 {
145 match self {
146 Self::Exact(_) => 0,
147 Self::AtMost(_) => 1,
148 Self::AtLeast(_) => 2,
149 }
150 }
151}