rudb_plan/node.rs
1//! Logical operators.
2//!
3//! One variant per operator, covering what the M0 binder can produce out of what the transformer
4//! in `rudb-parse` can produce. That is a smaller set than DuckDB's and it is smaller on purpose:
5//! an operator here that nothing constructs is an operator whose textual form, whose validation
6//! and whose rewrite rules have never been run, and the first thing that happens when the binder
7//! finally emits one is that all three turn out to be wrong.
8//!
9//! Every operator that introduces new columns carries a table index, which is the left half of a
10//! [`ColumnBinding`](crate::ColumnBinding). [`Node::Filter`], [`Node::Sort`], [`Node::Limit`],
11//! [`Node::Distinct`] and [`Node::Join`] do not have one, because they pass their input's columns
12//! through unchanged and a binding that survives a filter should not have to be rewritten by it.
13
14use crate::{ExprRef, NodeRef, Slice, StrRef};
15
16/// One logical operator.
17///
18/// Children are the inputs, in the order [`Node::children`] returns them, which is the order they
19/// print in and the order the reader expects.
20#[derive(Debug, Clone, PartialEq, Eq)]
21pub enum Node {
22 /// A base table scan.
23 ///
24 /// The projection is in `columns`, so a scan of two columns of a 105-column table is a two
25 /// column scan in the plan and not a filter over a wide one. `spec/09-optimizer.md` section
26 /// 9.2 calls projection pushdown the difference between 20 GB and 200 MB on ClickBench, and
27 /// this is the field it pushes into.
28 Get {
29 /// The catalog name.
30 catalog: StrRef,
31 /// The schema name.
32 schema: StrRef,
33 /// The table name.
34 table: StrRef,
35 /// The alias the query used, which is what an error message should say.
36 alias: StrRef,
37 /// The table index that this scan's columns bind against.
38 index: u32,
39 /// The projected columns with their types, into the field pool.
40 columns: Slice,
41 },
42 /// One row and no columns.
43 ///
44 /// What `SELECT 1` sits on top of. Not an empty result: an empty result produces no rows and
45 /// `SELECT 1` produces one, and conflating them is how a scalar subquery starts returning
46 /// nothing instead of null.
47 Dummy,
48 /// Literal rows.
49 ///
50 /// Every row has the same length as `columns`, which [`Plan::validate`](crate::Plan::validate)
51 /// checks, because a ragged `VALUES` is a wrong answer rather than a crash.
52 Values {
53 /// The table index that these columns bind against.
54 index: u32,
55 /// The output columns with their types, into the field pool.
56 columns: Slice,
57 /// The rows, into the row pool, each row a slice of the expression list pool.
58 rows: Slice,
59 },
60 /// A function call where a table goes, such as `range(10)`.
61 ///
62 /// The arguments are expressions rather than numbers, because `range(2 + 3)` is a legal call
63 /// and folding it here would mean the plan could not be printed back as what was written. They
64 /// cannot refer to a column: a table function that sees the row on its left is `LATERAL`, which
65 /// is a different node and is not here yet.
66 ///
67 /// A separate node from [`Node::Values`] even though `range(3)` and `VALUES (0), (1), (2)`
68 /// produce the same rows, because the one that produces three million rows should be three
69 /// numbers in the plan rather than three million expressions in it.
70 TableFunction {
71 /// The table index that this call's columns bind against.
72 index: u32,
73 /// Which function, as its own canonical name.
74 function: StrRef,
75 /// The arguments, into the expression list pool.
76 args: Slice,
77 /// The produced columns with their types, into the field pool.
78 columns: Slice,
79 },
80 /// A predicate over the input, keeping the rows where it is true.
81 ///
82 /// True, not "not false". A null predicate drops the row, which is SQL's rule and is the
83 /// difference between `WHERE` and `CHECK`.
84 Filter {
85 /// The input.
86 input: NodeRef,
87 /// The predicate, which has to be `BOOLEAN`.
88 predicate: ExprRef,
89 },
90 /// A projection, producing a new set of columns from the input's.
91 Project {
92 /// The input.
93 input: NodeRef,
94 /// The table index the produced columns bind against.
95 index: u32,
96 /// The expressions, into the expression list pool.
97 exprs: Slice,
98 /// One output name per expression, into the name list pool.
99 ///
100 /// Names are carried through the whole plan rather than attached at the root, because the
101 /// thing a person reads a plan dump to answer is usually which column this is, and a dump
102 /// with the names stripped out answers that with a number.
103 names: Slice,
104 },
105 /// A grouped or ungrouped aggregation.
106 ///
107 /// The output is the group expressions followed by the aggregates, in that order, and that is
108 /// what a binding into `index` means. An ungrouped aggregate has an empty `groups` and still
109 /// produces exactly one row, including over an empty input.
110 Aggregate {
111 /// The input.
112 input: NodeRef,
113 /// The table index the produced columns bind against.
114 index: u32,
115 /// The group expressions, into the expression list pool.
116 groups: Slice,
117 /// The aggregate expressions, into the expression list pool. Every element is an
118 /// [`Expr::Aggregate`](crate::Expr::Aggregate) and this is the only place one may appear.
119 aggregates: Slice,
120 },
121 /// An ordering.
122 Sort {
123 /// The input.
124 input: NodeRef,
125 /// The keys in priority order, into the sort key pool.
126 keys: Slice,
127 },
128 /// A row count limit and an offset.
129 ///
130 /// Both are constants. `LIMIT` over an expression is legal SQL and DuckDB evaluates it before
131 /// the plan runs, so by the time it is here it is a number or the query did not bind.
132 Limit {
133 /// The input.
134 input: NodeRef,
135 /// How many rows to emit, or all of them.
136 count: Option<u64>,
137 /// How many rows to skip first.
138 offset: u64,
139 },
140 /// Duplicate elimination, over the whole row or over named expressions.
141 Distinct {
142 /// The input.
143 input: NodeRef,
144 /// The `DISTINCT ON` expressions, into the expression list pool. Empty means the whole
145 /// row, which is plain `DISTINCT`.
146 on: Slice,
147 },
148 /// A join with a condition.
149 Join {
150 /// The left input.
151 left: NodeRef,
152 /// The right input.
153 right: NodeRef,
154 /// Which join.
155 kind: JoinKind,
156 /// The conditions, into the expression list pool, combined with `AND`. Empty is a join
157 /// with no condition, which for an inner join is a cross product and for an outer join
158 /// is not.
159 conditions: Slice,
160 },
161 /// An unconditional cross product.
162 ///
163 /// Separate from a [`Node::Join`] with no conditions because join ordering treats them
164 /// differently: a cross product has no edge in the join graph and section 9.4's dynamic
165 /// program enumerates connected subgraphs.
166 CrossProduct {
167 /// The left input.
168 left: NodeRef,
169 /// The right input.
170 right: NodeRef,
171 },
172 /// `UNION`, `EXCEPT` or `INTERSECT`.
173 SetOp {
174 /// The left input.
175 left: NodeRef,
176 /// The right input.
177 right: NodeRef,
178 /// Which operation.
179 kind: SetOpKind,
180 /// Whether duplicates are kept.
181 all: bool,
182 /// The table index the produced columns bind against, since the output is neither side's
183 /// columns.
184 index: u32,
185 },
186}
187
188impl Node {
189 /// The keyword this operator prints as, which is also what the reader dispatches on.
190 #[must_use]
191 pub fn keyword(&self) -> &'static str {
192 match self {
193 Self::Get { .. } => "Get",
194 Self::Dummy => "Dummy",
195 Self::Values { .. } => "Values",
196 Self::TableFunction { .. } => "TableFunction",
197 Self::Filter { .. } => "Filter",
198 Self::Project { .. } => "Project",
199 Self::Aggregate { .. } => "Aggregate",
200 Self::Sort { .. } => "Sort",
201 Self::Limit { .. } => "Limit",
202 Self::Distinct { .. } => "Distinct",
203 Self::Join { .. } => "Join",
204 Self::CrossProduct { .. } => "CrossProduct",
205 Self::SetOp { .. } => "SetOp",
206 }
207 }
208
209 /// The inputs, in printing order.
210 ///
211 /// Two slots rather than a `Vec`, because no logical operator in this set has three inputs and
212 /// the printer walks this on every node of every dump. A caller wants
213 /// `node.children().into_iter().flatten()`.
214 #[must_use]
215 pub fn children(&self) -> [Option<NodeRef>; 2] {
216 match *self {
217 Self::Get { .. } | Self::Dummy | Self::Values { .. } | Self::TableFunction { .. } => {
218 [None, None]
219 }
220 Self::Filter { input, .. }
221 | Self::Project { input, .. }
222 | Self::Aggregate { input, .. }
223 | Self::Sort { input, .. }
224 | Self::Limit { input, .. }
225 | Self::Distinct { input, .. } => [Some(input), None],
226 Self::Join { left, right, .. }
227 | Self::CrossProduct { left, right }
228 | Self::SetOp { left, right, .. } => [Some(left), Some(right)],
229 }
230 }
231
232 /// How many inputs this operator takes.
233 #[must_use]
234 pub fn arity(&self) -> usize {
235 self.children().into_iter().flatten().count()
236 }
237
238 /// The table index this operator introduces, if it introduces one.
239 #[must_use]
240 pub fn table_index(&self) -> Option<u32> {
241 match *self {
242 Self::Get { index, .. }
243 | Self::Values { index, .. }
244 | Self::TableFunction { index, .. }
245 | Self::Project { index, .. }
246 | Self::Aggregate { index, .. }
247 | Self::SetOp { index, .. } => Some(index),
248 _ => None,
249 }
250 }
251}
252
253/// Which join.
254///
255/// `Semi` and `Anti` are here because subquery unnesting produces them directly, per section 9.2,
256/// and a semi join expressed as a join plus a distinct is a semi join the executor cannot
257/// recognise.
258#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
259pub enum JoinKind {
260 /// Rows that match on both sides.
261 Inner,
262 /// Every left row, padded with nulls where the right does not match.
263 Left,
264 /// Every right row, padded with nulls where the left does not match.
265 Right,
266 /// Both of the above at once.
267 Full,
268 /// Left rows that have at least one match, each emitted once.
269 Semi,
270 /// Left rows that have no match.
271 Anti,
272 /// Left rows paired with their match, or with nulls, at most one right row each. What a
273 /// correlated scalar subquery unnests to.
274 Single,
275 /// The nth left row with the nth right row, which is DuckDB's `POSITIONAL JOIN`.
276 Positional,
277}
278
279impl JoinKind {
280 /// The spelling used in the textual form.
281 #[must_use]
282 pub fn keyword(self) -> &'static str {
283 match self {
284 Self::Inner => "INNER",
285 Self::Left => "LEFT",
286 Self::Right => "RIGHT",
287 Self::Full => "FULL",
288 Self::Semi => "SEMI",
289 Self::Anti => "ANTI",
290 Self::Single => "SINGLE",
291 Self::Positional => "POSITIONAL",
292 }
293 }
294
295 /// Every join kind, which is what the reader searches.
296 pub(crate) const ALL: [Self; 8] = [
297 Self::Inner,
298 Self::Left,
299 Self::Right,
300 Self::Full,
301 Self::Semi,
302 Self::Anti,
303 Self::Single,
304 Self::Positional,
305 ];
306}
307
308/// Which set operation.
309#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
310pub enum SetOpKind {
311 /// Rows from either side.
312 Union,
313 /// Rows from the left that are not on the right.
314 Except,
315 /// Rows on both sides.
316 Intersect,
317}
318
319impl SetOpKind {
320 /// The spelling used in the textual form.
321 #[must_use]
322 pub fn keyword(self) -> &'static str {
323 match self {
324 Self::Union => "UNION",
325 Self::Except => "EXCEPT",
326 Self::Intersect => "INTERSECT",
327 }
328 }
329
330 /// Every set operation, which is what the reader searches.
331 pub(crate) const ALL: [Self; 3] = [Self::Union, Self::Except, Self::Intersect];
332}
333
334#[cfg(test)]
335mod tests {
336 use super::*;
337 use crate::Slice;
338
339 /// Every node in one list, so that a variant added without a keyword, without a child slot or
340 /// without an entry in the reader's dispatch table fails here rather than at the first dump
341 /// that happens to contain one.
342 fn one_of_each() -> Vec<Node> {
343 vec![
344 Node::Get {
345 catalog: 0,
346 schema: 0,
347 table: 0,
348 alias: 0,
349 index: 0,
350 columns: Slice::EMPTY,
351 },
352 Node::Dummy,
353 Node::Values { index: 0, columns: Slice::EMPTY, rows: Slice::EMPTY },
354 Node::TableFunction {
355 index: 0,
356 function: 0,
357 args: Slice::EMPTY,
358 columns: Slice::EMPTY,
359 },
360 Node::Filter { input: 0, predicate: 0 },
361 Node::Project { input: 0, index: 0, exprs: Slice::EMPTY, names: Slice::EMPTY },
362 Node::Aggregate { input: 0, index: 0, groups: Slice::EMPTY, aggregates: Slice::EMPTY },
363 Node::Sort { input: 0, keys: Slice::EMPTY },
364 Node::Limit { input: 0, count: None, offset: 0 },
365 Node::Distinct { input: 0, on: Slice::EMPTY },
366 Node::Join { left: 0, right: 1, kind: JoinKind::Inner, conditions: Slice::EMPTY },
367 Node::CrossProduct { left: 0, right: 1 },
368 Node::SetOp { left: 0, right: 1, kind: SetOpKind::Union, all: true, index: 0 },
369 ]
370 }
371
372 #[test]
373 fn every_operator_has_its_own_keyword() {
374 let mut keywords: Vec<&str> = one_of_each().iter().map(Node::keyword).collect();
375 let count = keywords.len();
376 keywords.sort_unstable();
377 keywords.dedup();
378 assert_eq!(keywords.len(), count, "two operators print the same keyword");
379 }
380
381 #[test]
382 fn arity_agrees_with_the_child_slots() {
383 for node in one_of_each() {
384 let counted = node.children().into_iter().flatten().count();
385 assert_eq!(node.arity(), counted, "{} disagrees with itself", node.keyword());
386 }
387 }
388
389 /// A child slot that is `None` before a slot that is `Some` would make the printer emit the
390 /// right input as the left one, and the reader would accept it.
391 #[test]
392 fn the_child_slots_are_filled_from_the_front() {
393 for node in one_of_each() {
394 let slots = node.children();
395 assert!(
396 !(slots[0].is_none() && slots[1].is_some()),
397 "{} has a right input and no left one",
398 node.keyword()
399 );
400 }
401 }
402
403 #[test]
404 fn only_the_operators_that_introduce_columns_have_a_table_index() {
405 for node in one_of_each() {
406 let expected = matches!(
407 node,
408 Node::Get { .. }
409 | Node::Values { .. }
410 | Node::TableFunction { .. }
411 | Node::Project { .. }
412 | Node::Aggregate { .. }
413 | Node::SetOp { .. }
414 );
415 assert_eq!(
416 node.table_index().is_some(),
417 expected,
418 "{} is on the wrong side of the table index rule",
419 node.keyword()
420 );
421 }
422 }
423
424 #[test]
425 fn every_join_kind_and_set_operation_is_in_the_list_the_reader_searches() {
426 assert_eq!(JoinKind::ALL.len(), 8);
427 assert_eq!(SetOpKind::ALL.len(), 3);
428 let mut names: Vec<&str> = JoinKind::ALL.iter().map(|k| k.keyword()).collect();
429 names.sort_unstable();
430 names.dedup();
431 assert_eq!(names.len(), JoinKind::ALL.len(), "two join kinds print the same keyword");
432 }
433}