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/// How a window frame measures its bounds.
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub enum WindowUnit {
20 Rows,
21 Range,
22 Groups,
23}
24
25/// One end of a window frame.
26#[derive(Debug, Clone, Copy, PartialEq, Eq)]
27pub enum WindowBound {
28 UnboundedPreceding,
29 Preceding(ExprRef),
30 CurrentRow,
31 Following(ExprRef),
32 UnboundedFollowing,
33}
34
35/// Which peers a window frame removes after its bounds are applied.
36#[derive(Debug, Clone, Copy, PartialEq, Eq)]
37pub enum WindowExclude {
38 NoOthers,
39 CurrentRow,
40 Group,
41 Ties,
42}
43
44/// The complete frame shared by a compatible run of window expressions.
45#[derive(Debug, Clone, Copy, PartialEq, Eq)]
46pub struct WindowFrame {
47 pub unit: WindowUnit,
48 pub start: WindowBound,
49 pub end: WindowBound,
50 pub exclude: WindowExclude,
51}
52
53/// One logical operator.
54///
55/// Children are the inputs, in the order [`Node::children`] returns them, which is the order they
56/// print in and the order the reader expects.
57#[derive(Debug, Clone, PartialEq, Eq)]
58pub enum Node {
59 /// A base table scan.
60 ///
61 /// The projection is in `columns`, so a scan of two columns of a 105-column table is a two
62 /// column scan in the plan and not a filter over a wide one. `spec/09-optimizer.md` section
63 /// 9.2 calls projection pushdown the difference between 20 GB and 200 MB on ClickBench, and
64 /// this is the field it pushes into.
65 Get {
66 /// The catalog name.
67 catalog: StrRef,
68 /// The schema name.
69 schema: StrRef,
70 /// The table name.
71 table: StrRef,
72 /// The alias the query used, which is what an error message should say.
73 alias: StrRef,
74 /// The table index that this scan's columns bind against.
75 index: u32,
76 /// The projected columns with their types, into the field pool.
77 columns: Slice,
78 },
79 /// One row and no columns.
80 ///
81 /// What `SELECT 1` sits on top of. Not an empty result: an empty result produces no rows and
82 /// `SELECT 1` produces one, and conflating them is how a scalar subquery starts returning
83 /// nothing instead of null.
84 Dummy,
85 /// Literal rows.
86 ///
87 /// Every row has the same length as `columns`, which [`Plan::validate`](crate::Plan::validate)
88 /// checks, because a ragged `VALUES` is a wrong answer rather than a crash.
89 Values {
90 /// The table index that these columns bind against.
91 index: u32,
92 /// The output columns with their types, into the field pool.
93 columns: Slice,
94 /// The rows, into the row pool, each row a slice of the expression list pool.
95 rows: Slice,
96 },
97 /// A function call where a table goes, such as `range(10)`.
98 ///
99 /// The arguments are expressions rather than numbers, because `range(2 + 3)` is a legal call
100 /// and folding it here would mean the plan could not be printed back as what was written. They
101 /// cannot refer to a column: a table function that sees the row on its left is `LATERAL`, which
102 /// is a different node and is not here yet.
103 ///
104 /// A separate node from [`Node::Values`] even though `range(3)` and `VALUES (0), (1), (2)`
105 /// produce the same rows, because the one that produces three million rows should be three
106 /// numbers in the plan rather than three million expressions in it.
107 TableFunction {
108 /// The table index that this call's columns bind against.
109 index: u32,
110 /// Which function, as its own canonical name.
111 function: StrRef,
112 /// The arguments, into the expression list pool.
113 args: Slice,
114 /// The names of the named parameters the call was written with, into the name pool.
115 ///
116 /// `read_csv('f.csv', delim=';')` keeps the `delim` here rather than only in whatever the
117 /// binder made of it, because the executor opens the file a second time and has to open it
118 /// the same way. A parameter the binder answers on its own, such as `binary_as_string`,
119 /// is here too, so that a plan prints back as the call that was written.
120 options: Slice,
121 /// What each of those names was given, into the expression list pool and the same length.
122 ///
123 /// Constants, every one of them. The binder refuses anything else, because a parameter can
124 /// decide what the columns are and the columns are settled there.
125 settings: Slice,
126 /// The produced columns with their types, into the field pool.
127 columns: Slice,
128 },
129 /// A predicate over the input, keeping the rows where it is true.
130 ///
131 /// True, not "not false". A null predicate drops the row, which is SQL's rule and is the
132 /// difference between `WHERE` and `CHECK`.
133 Filter {
134 /// The input.
135 input: NodeRef,
136 /// The predicate, which has to be `BOOLEAN`.
137 predicate: ExprRef,
138 },
139 /// A projection, producing a new set of columns from the input's.
140 Project {
141 /// The input.
142 input: NodeRef,
143 /// The table index the produced columns bind against.
144 index: u32,
145 /// The expressions, into the expression list pool.
146 exprs: Slice,
147 /// One output name per expression, into the name list pool.
148 ///
149 /// Names are carried through the whole plan rather than attached at the root, because the
150 /// thing a person reads a plan dump to answer is usually which column this is, and a dump
151 /// with the names stripped out answers that with a number.
152 names: Slice,
153 },
154 /// A grouped or ungrouped aggregation.
155 ///
156 /// The output is the group expressions followed by the aggregates, in that order, and that is
157 /// what a binding into `index` means. An ungrouped aggregate has an empty `groups` and still
158 /// produces exactly one row, including over an empty input.
159 Aggregate {
160 /// The input.
161 input: NodeRef,
162 /// The table index the produced columns bind against.
163 index: u32,
164 /// The group expressions, into the expression list pool.
165 groups: Slice,
166 /// The aggregate expressions, into the expression list pool. Every element is an
167 /// [`Expr::Aggregate`](crate::Expr::Aggregate) and this is the only place one may appear.
168 aggregates: Slice,
169 },
170 /// Window expressions that share one partition, ordering, and frame.
171 Window {
172 /// Rows over which the windows are evaluated.
173 input: NodeRef,
174 /// The table index of the appended window result columns.
175 index: u32,
176 /// Expressions that divide the input into independent partitions.
177 partition: Slice,
178 /// The ordering within each partition.
179 order: Slice,
180 /// The complete frame shared by this compatible expression run.
181 frame: WindowFrame,
182 /// Direct [`Expr::Window`](crate::Expr::Window) expressions appended to the input columns.
183 expressions: Slice,
184 },
185 /// An ordering.
186 Sort {
187 /// The input.
188 input: NodeRef,
189 /// The keys in priority order, into the sort key pool.
190 keys: Slice,
191 },
192 /// A row count limit and an offset.
193 ///
194 /// Both are constants. `LIMIT` over an expression is legal SQL and DuckDB evaluates it before
195 /// the plan runs, so by the time it is here it is a number or the query did not bind.
196 Limit {
197 /// The input.
198 input: NodeRef,
199 /// How many rows to emit, or all of them.
200 count: Option<u64>,
201 /// How many rows to skip first.
202 offset: u64,
203 },
204 /// A sort with a limit over it, which never holds more rows than the limit can emit.
205 ///
206 /// The same answer as a [`Node::Limit`] over a [`Node::Sort`] and a different amount of work.
207 /// A sort has to see every row before it can emit the first one, so it holds the whole input;
208 /// this holds the rows that could still come out and throws the rest away as it goes, which on
209 /// `ORDER BY x LIMIT 10` over a hundred million rows is ten rows rather than a hundred million.
210 ///
211 /// `count` is not optional, because `LIMIT ALL` over a sort is a sort and there would be nothing
212 /// to bound. The offset is part of the node rather than left above it, since the rows that are
213 /// skipped still have to be found to be skipped, so what this has to keep is `count + offset`.
214 TopN {
215 /// The input.
216 input: NodeRef,
217 /// The keys in priority order, into the sort key pool.
218 keys: Slice,
219 /// How many rows to emit.
220 count: u64,
221 /// How many rows to skip first.
222 offset: u64,
223 },
224 /// The columns of rows something below already picked out, read back from the file by ordinal.
225 ///
226 /// This is the top half of late materialisation. A `SELECT * FROM hits ORDER BY EventTime LIMIT
227 /// 10` over a hundred and five columns needs one column to decide which ten rows win and all
228 /// hundred and five of those ten rows afterwards, and a plan that carries the wide rows through
229 /// the top N reads the whole file to throw almost all of it away. The rewrite in
230 /// `rudb-opt`'s `late` module narrows the scan under the top N to the ordering columns plus the
231 /// row's ordinal inside its file, and puts this above it to read the rest for the rows that
232 /// survived.
233 ///
234 /// The ordinals come out of the input rather than being counted here, because the operator that
235 /// counted them is the scan and everything between the scan and here may have dropped rows. The
236 /// column that holds them is [`Self::Fetch::row`], and the scan produced it because the rewrite
237 /// turned `file_row_number` on.
238 ///
239 /// The produced columns are the whole row and not only the deferred part, so the answer is one
240 /// read of the file at the ordinals rather than a stitch of what was carried with what was
241 /// fetched. That costs the ordering column a second read of a few pages and saves the plan above
242 /// this from having any idea the rewrite happened.
243 Fetch {
244 /// The input, which carries each row's ordinal inside the file.
245 input: NodeRef,
246 /// The table index the produced columns bind against, which is the one the node this
247 /// replaced produced, so that nothing above has to be rebound.
248 index: u32,
249 /// The file, into the expression list pool. One constant path, because a row ordinal only
250 /// says which row when there is one file it could be in.
251 args: Slice,
252 /// The produced columns with their types, into the field pool.
253 columns: Slice,
254 /// The input column holding the ordinal, which has to be `BIGINT`.
255 row: ExprRef,
256 },
257 /// Rows of a catalog table read back by their table-wide ordinal.
258 TableFetch {
259 input: NodeRef,
260 index: u32,
261 catalog: StrRef,
262 schema: StrRef,
263 table: StrRef,
264 columns: Slice,
265 row: ExprRef,
266 },
267 /// Duplicate elimination, over the whole row or over named expressions.
268 Distinct {
269 /// The input.
270 input: NodeRef,
271 /// The `DISTINCT ON` expressions, into the expression list pool. Empty means the whole
272 /// row, which is plain `DISTINCT`.
273 on: Slice,
274 },
275 /// A join with a condition.
276 Join {
277 /// The left input.
278 left: NodeRef,
279 /// The right input.
280 right: NodeRef,
281 /// Which join.
282 kind: JoinKind,
283 /// The conditions, into the expression list pool, combined with `AND`. Empty is a join
284 /// with no condition, which for an inner join is a cross product and for an outer join
285 /// is not.
286 conditions: Slice,
287 },
288 /// A join whose right input can refer to columns produced by its left input.
289 ///
290 /// Binding emits this for a correlated subquery. The unnesting pass has to replace every one
291 /// before execution, so the executor never evaluates the right input once per left row.
292 DependentJoin {
293 /// The outer input whose columns the right side may reference.
294 left: NodeRef,
295 /// The correlated input.
296 right: NodeRef,
297 /// Which result shape the subquery needs.
298 kind: JoinKind,
299 /// Conditions introduced while binding the subquery.
300 conditions: Slice,
301 },
302 /// An unconditional cross product.
303 ///
304 /// Separate from a [`Node::Join`] with no conditions because join ordering treats them
305 /// differently: a cross product has no edge in the join graph and section 9.4's dynamic
306 /// program enumerates connected subgraphs.
307 CrossProduct {
308 /// The left input.
309 left: NodeRef,
310 /// The right input.
311 right: NodeRef,
312 },
313 /// `UNION`, `EXCEPT` or `INTERSECT`.
314 SetOp {
315 /// The left input.
316 left: NodeRef,
317 /// The right input.
318 right: NodeRef,
319 /// Which operation.
320 kind: SetOpKind,
321 /// Whether duplicates are kept.
322 all: bool,
323 /// The table index the produced columns bind against, since the output is neither side's
324 /// columns.
325 index: u32,
326 },
327}
328
329impl Node {
330 /// The keyword this operator prints as, which is also what the reader dispatches on.
331 #[must_use]
332 pub fn keyword(&self) -> &'static str {
333 match self {
334 Self::Get { .. } => "Get",
335 Self::Dummy => "Dummy",
336 Self::Values { .. } => "Values",
337 Self::TableFunction { .. } => "TableFunction",
338 Self::Filter { .. } => "Filter",
339 Self::Project { .. } => "Project",
340 Self::Aggregate { .. } => "Aggregate",
341 Self::Window { .. } => "Window",
342 Self::Sort { .. } => "Sort",
343 Self::Limit { .. } => "Limit",
344 Self::TopN { .. } => "TopN",
345 Self::Fetch { .. } => "Fetch",
346 Self::TableFetch { .. } => "TableFetch",
347 Self::Distinct { .. } => "Distinct",
348 Self::Join { .. } => "Join",
349 Self::DependentJoin { .. } => "DependentJoin",
350 Self::CrossProduct { .. } => "CrossProduct",
351 Self::SetOp { .. } => "SetOp",
352 }
353 }
354
355 /// The inputs, in printing order.
356 ///
357 /// Two slots rather than a `Vec`, because no logical operator in this set has three inputs and
358 /// the printer walks this on every node of every dump. A caller wants
359 /// `node.children().into_iter().flatten()`.
360 #[must_use]
361 pub fn children(&self) -> [Option<NodeRef>; 2] {
362 match *self {
363 Self::Get { .. } | Self::Dummy | Self::Values { .. } | Self::TableFunction { .. } => {
364 [None, None]
365 }
366 Self::Filter { input, .. }
367 | Self::Project { input, .. }
368 | Self::Aggregate { input, .. }
369 | Self::Window { input, .. }
370 | Self::Sort { input, .. }
371 | Self::Limit { input, .. }
372 | Self::TopN { input, .. }
373 | Self::Fetch { input, .. }
374 | Self::TableFetch { input, .. }
375 | Self::Distinct { input, .. } => [Some(input), None],
376 Self::Join { left, right, .. }
377 | Self::DependentJoin { left, right, .. }
378 | Self::CrossProduct { left, right }
379 | Self::SetOp { left, right, .. } => [Some(left), Some(right)],
380 }
381 }
382
383 /// How many inputs this operator takes.
384 #[must_use]
385 pub fn arity(&self) -> usize {
386 self.children().into_iter().flatten().count()
387 }
388
389 /// The table index this operator introduces, if it introduces one.
390 #[must_use]
391 pub fn table_index(&self) -> Option<u32> {
392 match *self {
393 Self::Get { index, .. }
394 | Self::Values { index, .. }
395 | Self::TableFunction { index, .. }
396 | Self::Project { index, .. }
397 | Self::Fetch { index, .. }
398 | Self::TableFetch { index, .. }
399 | Self::Aggregate { index, .. }
400 | Self::Window { index, .. }
401 | Self::SetOp { index, .. } => Some(index),
402 _ => None,
403 }
404 }
405}
406
407/// Which join.
408///
409/// `Semi` and `Anti` are here because subquery unnesting produces them directly, per section 9.2,
410/// and a semi join expressed as a join plus a distinct is a semi join the executor cannot
411/// recognise.
412#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
413pub enum JoinKind {
414 /// Rows that match on both sides.
415 Inner,
416 /// Every left row, padded with nulls where the right does not match.
417 Left,
418 /// Every right row, padded with nulls where the left does not match.
419 Right,
420 /// Both of the above at once.
421 Full,
422 /// Left rows that have at least one match, each emitted once.
423 Semi,
424 /// Left rows that have no match.
425 Anti,
426 /// Left rows paired with their match, or with nulls, at most one right row each. What a
427 /// correlated scalar subquery unnests to.
428 Single,
429 /// Every left row plus a nullable boolean saying whether its condition matched the right side.
430 /// A null means no row matched and at least one comparison was unknown.
431 Mark,
432 /// The nth left row with the nth right row, which is DuckDB's `POSITIONAL JOIN`.
433 Positional,
434}
435
436impl JoinKind {
437 /// The spelling used in the textual form.
438 #[must_use]
439 pub fn keyword(self) -> &'static str {
440 match self {
441 Self::Inner => "INNER",
442 Self::Left => "LEFT",
443 Self::Right => "RIGHT",
444 Self::Full => "FULL",
445 Self::Semi => "SEMI",
446 Self::Anti => "ANTI",
447 Self::Single => "SINGLE",
448 Self::Mark => "MARK",
449 Self::Positional => "POSITIONAL",
450 }
451 }
452
453 /// Every join kind, which is what the reader searches.
454 pub(crate) const ALL: [Self; 9] = [
455 Self::Inner,
456 Self::Left,
457 Self::Right,
458 Self::Full,
459 Self::Semi,
460 Self::Anti,
461 Self::Single,
462 Self::Mark,
463 Self::Positional,
464 ];
465}
466
467/// Which set operation.
468#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
469pub enum SetOpKind {
470 /// Rows from either side.
471 Union,
472 /// Rows from the left that are not on the right.
473 Except,
474 /// Rows on both sides.
475 Intersect,
476}
477
478impl SetOpKind {
479 /// The spelling used in the textual form.
480 #[must_use]
481 pub fn keyword(self) -> &'static str {
482 match self {
483 Self::Union => "UNION",
484 Self::Except => "EXCEPT",
485 Self::Intersect => "INTERSECT",
486 }
487 }
488
489 /// Every set operation, which is what the reader searches.
490 pub(crate) const ALL: [Self; 3] = [Self::Union, Self::Except, Self::Intersect];
491}
492
493#[cfg(test)]
494mod tests {
495 use super::*;
496 use crate::Slice;
497
498 /// Every node in one list, so that a variant added without a keyword, without a child slot or
499 /// without an entry in the reader's dispatch table fails here rather than at the first dump
500 /// that happens to contain one.
501 fn one_of_each() -> Vec<Node> {
502 vec![
503 Node::Get {
504 catalog: 0,
505 schema: 0,
506 table: 0,
507 alias: 0,
508 index: 0,
509 columns: Slice::EMPTY,
510 },
511 Node::Dummy,
512 Node::Values { index: 0, columns: Slice::EMPTY, rows: Slice::EMPTY },
513 Node::TableFunction {
514 index: 0,
515 function: 0,
516 args: Slice::EMPTY,
517 options: Slice::EMPTY,
518 settings: Slice::EMPTY,
519 columns: Slice::EMPTY,
520 },
521 Node::Filter { input: 0, predicate: 0 },
522 Node::Project { input: 0, index: 0, exprs: Slice::EMPTY, names: Slice::EMPTY },
523 Node::Aggregate { input: 0, index: 0, groups: Slice::EMPTY, aggregates: Slice::EMPTY },
524 Node::Sort { input: 0, keys: Slice::EMPTY },
525 Node::Limit { input: 0, count: None, offset: 0 },
526 Node::Distinct { input: 0, on: Slice::EMPTY },
527 Node::Join { left: 0, right: 1, kind: JoinKind::Inner, conditions: Slice::EMPTY },
528 Node::DependentJoin {
529 left: 0,
530 right: 1,
531 kind: JoinKind::Single,
532 conditions: Slice::EMPTY,
533 },
534 Node::CrossProduct { left: 0, right: 1 },
535 Node::SetOp { left: 0, right: 1, kind: SetOpKind::Union, all: true, index: 0 },
536 ]
537 }
538
539 #[test]
540 fn every_operator_has_its_own_keyword() {
541 let mut keywords: Vec<&str> = one_of_each().iter().map(Node::keyword).collect();
542 let count = keywords.len();
543 keywords.sort_unstable();
544 keywords.dedup();
545 assert_eq!(keywords.len(), count, "two operators print the same keyword");
546 }
547
548 #[test]
549 fn arity_agrees_with_the_child_slots() {
550 for node in one_of_each() {
551 let counted = node.children().into_iter().flatten().count();
552 assert_eq!(node.arity(), counted, "{} disagrees with itself", node.keyword());
553 }
554 }
555
556 /// A child slot that is `None` before a slot that is `Some` would make the printer emit the
557 /// right input as the left one, and the reader would accept it.
558 #[test]
559 fn the_child_slots_are_filled_from_the_front() {
560 for node in one_of_each() {
561 let slots = node.children();
562 assert!(
563 !(slots[0].is_none() && slots[1].is_some()),
564 "{} has a right input and no left one",
565 node.keyword()
566 );
567 }
568 }
569
570 #[test]
571 fn only_the_operators_that_introduce_columns_have_a_table_index() {
572 for node in one_of_each() {
573 let expected = matches!(
574 node,
575 Node::Get { .. }
576 | Node::Values { .. }
577 | Node::TableFunction { .. }
578 | Node::Project { .. }
579 | Node::Aggregate { .. }
580 | Node::SetOp { .. }
581 );
582 assert_eq!(
583 node.table_index().is_some(),
584 expected,
585 "{} is on the wrong side of the table index rule",
586 node.keyword()
587 );
588 }
589 }
590
591 #[test]
592 fn every_join_kind_and_set_operation_is_in_the_list_the_reader_searches() {
593 assert_eq!(JoinKind::ALL.len(), 9);
594 assert_eq!(SetOpKind::ALL.len(), 3);
595 let mut names: Vec<&str> = JoinKind::ALL.iter().map(|k| k.keyword()).collect();
596 names.sort_unstable();
597 names.dedup();
598 assert_eq!(names.len(), JoinKind::ALL.len(), "two join kinds print the same keyword");
599 }
600}