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 window function, evaluated by the [`Node::Window`](crate::Node::Window) that lists it.
109 Window {
110 /// The resolved scalar, aggregate, or dedicated window function name.
111 name: StrRef,
112 /// Function arguments over the window input.
113 args: Slice,
114 /// Whether duplicate argument tuples are collapsed first.
115 distinct: bool,
116 /// An aggregate filter, when the window call has one.
117 filter: Option<ExprRef>,
118 /// Whether null arguments are skipped by functions that support the modifier.
119 ignore_nulls: bool,
120 /// The order the call reads the rows of its frame in, into the sort key pool, empty when
121 /// the call wrote no `ORDER BY` inside its brackets.
122 ///
123 /// This is not the window's own ordering. The one in the `OVER` lays the partition out and
124 /// decides which rows are in the frame at all, and this one decides what order the call
125 /// sees them in once they are, which is why `first_value(v ORDER BY v DESC)` is the largest
126 /// `v` in the frame and not the first row of it.
127 order: Slice,
128 },
129 /// A searched `CASE`.
130 ///
131 /// There is no simple `CASE` here. `CASE x WHEN 1 THEN ...` is rewritten to the searched form
132 /// by the binder, because two representations of one thing is two code paths in every pass
133 /// that touches either.
134 Case {
135 /// The `WHEN`/`THEN` pairs, in order, into the arm pool.
136 arms: Slice,
137 /// The `ELSE`, if there is one. Absent means null.
138 otherwise: Option<ExprRef>,
139 },
140 /// A function written inline, which is only ever an argument of a function that takes one,
141 /// such as the second argument of `list_transform`.
142 ///
143 /// Its parameters are bound as the columns of a table of their own, numbered the way an
144 /// operator's output is, and read with [`Expr::LambdaParam`]. The type recorded for it is its
145 /// body's, since there is no type for a function and the one its caller needs is the body's.
146 Lambda {
147 /// The table index its parameters are bound under.
148 table: u32,
149 /// The parameters as they were written, into the name list pool, which is what an error
150 /// message quotes a body with.
151 params: Slice,
152 /// What it computes from them.
153 body: ExprRef,
154 },
155 /// One parameter of an enclosing [`Expr::Lambda`].
156 ///
157 /// Not an [`Expr::Column`], although the body reads it the same way when it runs, because no
158 /// operator produces it. A pass that moves, prunes or renumbers columns has to be able to tell
159 /// one apart from a column without knowing which lambda it is inside, and a variant of its own
160 /// is what lets it.
161 LambdaParam(ColumnBinding),
162}
163
164/// One `WHEN`/`THEN` pair of a [`Expr::Case`].
165#[derive(Debug, Clone, Copy, PartialEq, Eq)]
166pub struct Arm {
167 /// The condition.
168 pub when: ExprRef,
169 /// The result if the condition is true.
170 pub then: ExprRef,
171}
172
173/// One key of a [`Node::Sort`](crate::Node::Sort).
174///
175/// Both flags are always set to something concrete. SQL's defaults are a parser concern, and a
176/// bound plan that still says "unstated" is a plan whose output order depends on who reads it.
177#[derive(Debug, Clone, Copy, PartialEq, Eq)]
178pub struct SortKey {
179 /// What to sort on.
180 pub expr: ExprRef,
181 /// Descending rather than ascending.
182 pub descending: bool,
183 /// Nulls before non-nulls rather than after.
184 pub nulls_first: bool,
185}
186
187/// Which comparison a [`Expr::Compare`] performs.
188#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
189pub enum CompareOp {
190 /// `=`, null in either operand yields null.
191 Equal,
192 /// `<>`.
193 NotEqual,
194 /// `<`.
195 Less,
196 /// `<=`.
197 LessOrEqual,
198 /// `>`.
199 Greater,
200 /// `>=`.
201 GreaterOrEqual,
202 /// `IS DISTINCT FROM`, which is total: two nulls are not distinct.
203 DistinctFrom,
204 /// `IS NOT DISTINCT FROM`, the null-safe equality.
205 NotDistinctFrom,
206}
207
208impl CompareOp {
209 /// The spelling used in the textual form.
210 #[must_use]
211 pub fn symbol(self) -> &'static str {
212 match self {
213 Self::Equal => "=",
214 Self::NotEqual => "<>",
215 Self::Less => "<",
216 Self::LessOrEqual => "<=",
217 Self::Greater => ">",
218 Self::GreaterOrEqual => ">=",
219 Self::DistinctFrom => "IS DISTINCT FROM",
220 Self::NotDistinctFrom => "IS NOT DISTINCT FROM",
221 }
222 }
223
224 /// Every comparison, in the order the reader tries them.
225 ///
226 /// A spelling that is a prefix of another has to come after it, or `<` matches the front of
227 /// `<=` and the reader produces the wrong operator on text that was perfectly well formed.
228 /// There is a test below that holds this list to that.
229 pub(crate) const SPELLINGS: [Self; 8] = [
230 Self::NotDistinctFrom,
231 Self::DistinctFrom,
232 Self::NotEqual,
233 Self::LessOrEqual,
234 Self::GreaterOrEqual,
235 Self::Equal,
236 Self::Less,
237 Self::Greater,
238 ];
239
240 /// The comparison that holds exactly when this one does with the operands swapped.
241 ///
242 /// Used by comparison normalization, which wants the constant on one fixed side.
243 #[must_use]
244 pub fn flip(self) -> Self {
245 match self {
246 Self::Less => Self::Greater,
247 Self::LessOrEqual => Self::GreaterOrEqual,
248 Self::Greater => Self::Less,
249 Self::GreaterOrEqual => Self::LessOrEqual,
250 other => other,
251 }
252 }
253}
254
255/// Which connective a [`Expr::Conjunction`] uses.
256#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
257pub enum ConjunctionOp {
258 /// `AND`.
259 And,
260 /// `OR`.
261 Or,
262}
263
264impl ConjunctionOp {
265 /// The spelling used in the textual form.
266 #[must_use]
267 pub fn keyword(self) -> &'static str {
268 match self {
269 Self::And => "AND",
270 Self::Or => "OR",
271 }
272 }
273}
274
275#[cfg(test)]
276mod tests {
277 use super::*;
278
279 #[test]
280 fn flipping_a_comparison_twice_is_the_comparison() {
281 for op in CompareOp::SPELLINGS {
282 assert_eq!(op.flip().flip(), op, "{} does not flip back", op.symbol());
283 }
284 }
285
286 #[test]
287 fn the_equalities_are_their_own_flip() {
288 for op in [CompareOp::Equal, CompareOp::NotEqual, CompareOp::NotDistinctFrom] {
289 assert_eq!(op.flip(), op, "{} should not care about operand order", op.symbol());
290 }
291 }
292
293 #[test]
294 fn every_comparison_has_exactly_one_spelling() {
295 let mut seen: Vec<&str> = CompareOp::SPELLINGS.iter().map(|op| op.symbol()).collect();
296 seen.sort_unstable();
297 let count = seen.len();
298 seen.dedup();
299 assert_eq!(seen.len(), count, "two comparisons print the same way");
300 }
301
302 /// The reader matches spellings in `SPELLINGS` order and stops at the first hit, so a spelling
303 /// that is a prefix of a later one would never be reached. Without this, moving `Less` up the
304 /// list would make every `<=` in every dump read back as `<` and the round trip would fail
305 /// somewhere far away from the edit that caused it.
306 #[test]
307 fn no_spelling_is_reachable_only_after_a_prefix_of_it() {
308 for (index, op) in CompareOp::SPELLINGS.iter().enumerate() {
309 for earlier in &CompareOp::SPELLINGS[..index] {
310 assert!(
311 !op.symbol().starts_with(earlier.symbol()),
312 "{} is tried after {}, which is a prefix of it",
313 op.symbol(),
314 earlier.symbol()
315 );
316 }
317 }
318 }
319}