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