rudb_plan/expr.rs
1//! Bound expressions.
2//!
3//! The taxonomy is DuckDB's, minus the classes M0 cannot produce. A comparison is not a function
4//! and a conjunction is not a comparison, because the optimizer's rewrites in
5//! `spec/09-optimizer.md` section 9.2 are written against exactly those shapes: comparison
6//! normalization needs to enumerate comparisons, filter pushdown needs to split conjunctions, and
7//! predicate transfer in 9.5 needs to find equijoin comparisons without pattern matching on a
8//! function called `=`. Arithmetic is a function, because nothing in the optimizer treats `+`
9//! differently from `abs`.
10
11use crate::{ExprRef, Slice, StrRef, ValueRef};
12
13/// Which column, by identity rather than by name.
14///
15/// The binder gives every operator that introduces columns a table index, and a column is that
16/// index plus a position. Two columns called `id` from two sides of a join are two bindings and
17/// there is no ambiguity to resolve, which is the entire reason the bound plan has no names in it.
18#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
19pub struct ColumnBinding {
20 /// The index of the operator that produces the column.
21 pub table: u32,
22 /// The position of the column in that operator's output.
23 pub column: u32,
24}
25
26impl ColumnBinding {
27 /// A binding to the column at `column` of the operator numbered `table`.
28 #[must_use]
29 pub fn new(table: u32, column: u32) -> Self {
30 Self { table, column }
31 }
32}
33
34/// One bound expression.
35///
36/// The type of an expression is not in here. It lives in a parallel vector in [`Plan`], indexed by
37/// the same [`ExprRef`], because a [`LogicalType`] owns a `Vec` for its nested cases and putting
38/// one inside every variant would make the common variants three times larger for the benefit of
39/// the rare ones.
40///
41/// [`Plan`]: crate::Plan
42/// [`LogicalType`]: rudb_common::LogicalType
43#[derive(Debug, Clone, PartialEq, Eq)]
44pub enum Expr {
45 /// A reference to a column of some operator's output.
46 Column(ColumnBinding),
47 /// A literal, folded constant, or bound parameter value.
48 Constant(ValueRef),
49 /// A cast to the expression's own type.
50 ///
51 /// The target is the type stored for this expression, not a second copy of it, so there is no
52 /// way for a cast to disagree with its own result type.
53 Cast {
54 /// What is being cast.
55 input: ExprRef,
56 /// Whether a failed cast yields null instead of raising.
57 try_cast: bool,
58 },
59 /// A binary comparison.
60 Compare {
61 /// Which comparison.
62 op: CompareOp,
63 /// Left operand.
64 left: ExprRef,
65 /// Right operand.
66 right: ExprRef,
67 },
68 /// An `AND` or `OR` over two or more operands.
69 ///
70 /// Flat rather than binary, because filter pushdown splits a conjunction into its parts and a
71 /// right-leaning tree of two-argument `AND`s makes that a recursion instead of a loop.
72 Conjunction {
73 /// Which connective.
74 op: ConjunctionOp,
75 /// Two or more operands, into the expression list pool.
76 children: Slice,
77 },
78 /// A scalar function, already resolved to one overload by the binder.
79 ///
80 /// The name is the resolved function's name and not the name the user wrote, so `a + b` is a
81 /// call to `+` and an alias in the catalog has already been followed.
82 Function {
83 /// The resolved function name.
84 name: StrRef,
85 /// The arguments, into the expression list pool.
86 args: Slice,
87 },
88 /// An aggregate function.
89 ///
90 /// An aggregate appears only as a direct element of [`Node::Aggregate`]'s aggregate list.
91 /// Anything downstream that wants the result refers to it with a [`ColumnBinding`] into the
92 /// aggregate's table index, which is why that node has one. [`Plan::validate`] checks this,
93 /// and the textual form relies on it: an aggregate and a scalar function print the same way,
94 /// and it is the slot they are printed in that says which is which.
95 ///
96 /// [`Node::Aggregate`]: crate::Node::Aggregate
97 /// [`Plan::validate`]: crate::Plan::validate
98 Aggregate {
99 /// The resolved aggregate name.
100 name: StrRef,
101 /// The arguments, into the expression list pool.
102 args: Slice,
103 /// Whether duplicate input rows are collapsed before aggregating.
104 distinct: bool,
105 /// The `FILTER (WHERE ...)` predicate, if there is one.
106 filter: Option<ExprRef>,
107 },
108 /// A searched `CASE`.
109 ///
110 /// There is no simple `CASE` here. `CASE x WHEN 1 THEN ...` is rewritten to the searched form
111 /// by the binder, because two representations of one thing is two code paths in every pass
112 /// that touches either.
113 Case {
114 /// The `WHEN`/`THEN` pairs, in order, into the arm pool.
115 arms: Slice,
116 /// The `ELSE`, if there is one. Absent means null.
117 otherwise: Option<ExprRef>,
118 },
119}
120
121/// One `WHEN`/`THEN` pair of a [`Expr::Case`].
122#[derive(Debug, Clone, Copy, PartialEq, Eq)]
123pub struct Arm {
124 /// The condition.
125 pub when: ExprRef,
126 /// The result if the condition is true.
127 pub then: ExprRef,
128}
129
130/// One key of a [`Node::Sort`](crate::Node::Sort).
131///
132/// Both flags are always set to something concrete. SQL's defaults are a parser concern, and a
133/// bound plan that still says "unstated" is a plan whose output order depends on who reads it.
134#[derive(Debug, Clone, Copy, PartialEq, Eq)]
135pub struct SortKey {
136 /// What to sort on.
137 pub expr: ExprRef,
138 /// Descending rather than ascending.
139 pub descending: bool,
140 /// Nulls before non-nulls rather than after.
141 pub nulls_first: bool,
142}
143
144/// Which comparison a [`Expr::Compare`] performs.
145#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
146pub enum CompareOp {
147 /// `=`, null in either operand yields null.
148 Equal,
149 /// `<>`.
150 NotEqual,
151 /// `<`.
152 Less,
153 /// `<=`.
154 LessOrEqual,
155 /// `>`.
156 Greater,
157 /// `>=`.
158 GreaterOrEqual,
159 /// `IS DISTINCT FROM`, which is total: two nulls are not distinct.
160 DistinctFrom,
161 /// `IS NOT DISTINCT FROM`, the null-safe equality.
162 NotDistinctFrom,
163}
164
165impl CompareOp {
166 /// The spelling used in the textual form.
167 #[must_use]
168 pub fn symbol(self) -> &'static str {
169 match self {
170 Self::Equal => "=",
171 Self::NotEqual => "<>",
172 Self::Less => "<",
173 Self::LessOrEqual => "<=",
174 Self::Greater => ">",
175 Self::GreaterOrEqual => ">=",
176 Self::DistinctFrom => "IS DISTINCT FROM",
177 Self::NotDistinctFrom => "IS NOT DISTINCT FROM",
178 }
179 }
180
181 /// Every comparison, in the order the reader tries them.
182 ///
183 /// A spelling that is a prefix of another has to come after it, or `<` matches the front of
184 /// `<=` and the reader produces the wrong operator on text that was perfectly well formed.
185 /// There is a test below that holds this list to that.
186 pub(crate) const SPELLINGS: [Self; 8] = [
187 Self::NotDistinctFrom,
188 Self::DistinctFrom,
189 Self::NotEqual,
190 Self::LessOrEqual,
191 Self::GreaterOrEqual,
192 Self::Equal,
193 Self::Less,
194 Self::Greater,
195 ];
196
197 /// The comparison that holds exactly when this one does with the operands swapped.
198 ///
199 /// Used by comparison normalization, which wants the constant on one fixed side.
200 #[must_use]
201 pub fn flip(self) -> Self {
202 match self {
203 Self::Less => Self::Greater,
204 Self::LessOrEqual => Self::GreaterOrEqual,
205 Self::Greater => Self::Less,
206 Self::GreaterOrEqual => Self::LessOrEqual,
207 other => other,
208 }
209 }
210}
211
212/// Which connective a [`Expr::Conjunction`] uses.
213#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
214pub enum ConjunctionOp {
215 /// `AND`.
216 And,
217 /// `OR`.
218 Or,
219}
220
221impl ConjunctionOp {
222 /// The spelling used in the textual form.
223 #[must_use]
224 pub fn keyword(self) -> &'static str {
225 match self {
226 Self::And => "AND",
227 Self::Or => "OR",
228 }
229 }
230}
231
232#[cfg(test)]
233mod tests {
234 use super::*;
235
236 #[test]
237 fn flipping_a_comparison_twice_is_the_comparison() {
238 for op in CompareOp::SPELLINGS {
239 assert_eq!(op.flip().flip(), op, "{} does not flip back", op.symbol());
240 }
241 }
242
243 #[test]
244 fn the_equalities_are_their_own_flip() {
245 for op in [CompareOp::Equal, CompareOp::NotEqual, CompareOp::NotDistinctFrom] {
246 assert_eq!(op.flip(), op, "{} should not care about operand order", op.symbol());
247 }
248 }
249
250 #[test]
251 fn every_comparison_has_exactly_one_spelling() {
252 let mut seen: Vec<&str> = CompareOp::SPELLINGS.iter().map(|op| op.symbol()).collect();
253 seen.sort_unstable();
254 let count = seen.len();
255 seen.dedup();
256 assert_eq!(seen.len(), count, "two comparisons print the same way");
257 }
258
259 /// The reader matches spellings in `SPELLINGS` order and stops at the first hit, so a spelling
260 /// that is a prefix of a later one would never be reached. Without this, moving `Less` up the
261 /// list would make every `<=` in every dump read back as `<` and the round trip would fail
262 /// somewhere far away from the edit that caused it.
263 #[test]
264 fn no_spelling_is_reachable_only_after_a_prefix_of_it() {
265 for (index, op) in CompareOp::SPELLINGS.iter().enumerate() {
266 for earlier in &CompareOp::SPELLINGS[..index] {
267 assert!(
268 !op.symbol().starts_with(earlier.symbol()),
269 "{} is tried after {}, which is a prefix of it",
270 op.symbol(),
271 earlier.symbol()
272 );
273 }
274 }
275 }
276}