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 /// The columns of rows something below already picked out, read back from the file by ordinal.
174 ///
175 /// This is the top half of late materialisation. A `SELECT * FROM hits ORDER BY EventTime LIMIT
176 /// 10` over a hundred and five columns needs one column to decide which ten rows win and all
177 /// hundred and five of those ten rows afterwards, and a plan that carries the wide rows through
178 /// the top N reads the whole file to throw almost all of it away. The rewrite in
179 /// `rudb-opt`'s `late` module narrows the scan under the top N to the ordering columns plus the
180 /// row's ordinal inside its file, and puts this above it to read the rest for the rows that
181 /// survived.
182 ///
183 /// The ordinals come out of the input rather than being counted here, because the operator that
184 /// counted them is the scan and everything between the scan and here may have dropped rows. The
185 /// column that holds them is [`Self::Fetch::row`], and the scan produced it because the rewrite
186 /// turned `file_row_number` on.
187 ///
188 /// The produced columns are the whole row and not only the deferred part, so the answer is one
189 /// read of the file at the ordinals rather than a stitch of what was carried with what was
190 /// fetched. That costs the ordering column a second read of a few pages and saves the plan above
191 /// this from having any idea the rewrite happened.
192 Fetch {
193 /// The input, which carries each row's ordinal inside the file.
194 input: NodeRef,
195 /// The table index the produced columns bind against, which is the one the node this
196 /// replaced produced, so that nothing above has to be rebound.
197 index: u32,
198 /// The file, into the expression list pool. One constant path, because a row ordinal only
199 /// says which row when there is one file it could be in.
200 args: Slice,
201 /// The produced columns with their types, into the field pool.
202 columns: Slice,
203 /// The input column holding the ordinal, which has to be `BIGINT`.
204 row: ExprRef,
205 },
206 /// Rows of a catalog table read back by their table-wide ordinal.
207 TableFetch {
208 input: NodeRef,
209 index: u32,
210 catalog: StrRef,
211 schema: StrRef,
212 table: StrRef,
213 columns: Slice,
214 row: ExprRef,
215 },
216 /// Duplicate elimination, over the whole row or over named expressions.
217 Distinct {
218 /// The input.
219 input: NodeRef,
220 /// The `DISTINCT ON` expressions, into the expression list pool. Empty means the whole
221 /// row, which is plain `DISTINCT`.
222 on: Slice,
223 },
224 /// A join with a condition.
225 Join {
226 /// The left input.
227 left: NodeRef,
228 /// The right input.
229 right: NodeRef,
230 /// Which join.
231 kind: JoinKind,
232 /// The conditions, into the expression list pool, combined with `AND`. Empty is a join
233 /// with no condition, which for an inner join is a cross product and for an outer join
234 /// is not.
235 conditions: Slice,
236 },
237 /// An unconditional cross product.
238 ///
239 /// Separate from a [`Node::Join`] with no conditions because join ordering treats them
240 /// differently: a cross product has no edge in the join graph and section 9.4's dynamic
241 /// program enumerates connected subgraphs.
242 CrossProduct {
243 /// The left input.
244 left: NodeRef,
245 /// The right input.
246 right: NodeRef,
247 },
248 /// `UNION`, `EXCEPT` or `INTERSECT`.
249 SetOp {
250 /// The left input.
251 left: NodeRef,
252 /// The right input.
253 right: NodeRef,
254 /// Which operation.
255 kind: SetOpKind,
256 /// Whether duplicates are kept.
257 all: bool,
258 /// The table index the produced columns bind against, since the output is neither side's
259 /// columns.
260 index: u32,
261 },
262}
263
264impl Node {
265 /// The keyword this operator prints as, which is also what the reader dispatches on.
266 #[must_use]
267 pub fn keyword(&self) -> &'static str {
268 match self {
269 Self::Get { .. } => "Get",
270 Self::Dummy => "Dummy",
271 Self::Values { .. } => "Values",
272 Self::TableFunction { .. } => "TableFunction",
273 Self::Filter { .. } => "Filter",
274 Self::Project { .. } => "Project",
275 Self::Aggregate { .. } => "Aggregate",
276 Self::Sort { .. } => "Sort",
277 Self::Limit { .. } => "Limit",
278 Self::TopN { .. } => "TopN",
279 Self::Fetch { .. } => "Fetch",
280 Self::TableFetch { .. } => "TableFetch",
281 Self::Distinct { .. } => "Distinct",
282 Self::Join { .. } => "Join",
283 Self::CrossProduct { .. } => "CrossProduct",
284 Self::SetOp { .. } => "SetOp",
285 }
286 }
287
288 /// The inputs, in printing order.
289 ///
290 /// Two slots rather than a `Vec`, because no logical operator in this set has three inputs and
291 /// the printer walks this on every node of every dump. A caller wants
292 /// `node.children().into_iter().flatten()`.
293 #[must_use]
294 pub fn children(&self) -> [Option<NodeRef>; 2] {
295 match *self {
296 Self::Get { .. } | Self::Dummy | Self::Values { .. } | Self::TableFunction { .. } => {
297 [None, None]
298 }
299 Self::Filter { input, .. }
300 | Self::Project { input, .. }
301 | Self::Aggregate { input, .. }
302 | Self::Sort { input, .. }
303 | Self::Limit { input, .. }
304 | Self::TopN { input, .. }
305 | Self::Fetch { input, .. }
306 | Self::TableFetch { input, .. }
307 | Self::Distinct { input, .. } => [Some(input), None],
308 Self::Join { left, right, .. }
309 | Self::CrossProduct { left, right }
310 | Self::SetOp { left, right, .. } => [Some(left), Some(right)],
311 }
312 }
313
314 /// How many inputs this operator takes.
315 #[must_use]
316 pub fn arity(&self) -> usize {
317 self.children().into_iter().flatten().count()
318 }
319
320 /// The table index this operator introduces, if it introduces one.
321 #[must_use]
322 pub fn table_index(&self) -> Option<u32> {
323 match *self {
324 Self::Get { index, .. }
325 | Self::Values { index, .. }
326 | Self::TableFunction { index, .. }
327 | Self::Project { index, .. }
328 | Self::Fetch { index, .. }
329 | Self::TableFetch { index, .. }
330 | Self::Aggregate { index, .. }
331 | Self::SetOp { index, .. } => Some(index),
332 _ => None,
333 }
334 }
335}
336
337/// Which join.
338///
339/// `Semi` and `Anti` are here because subquery unnesting produces them directly, per section 9.2,
340/// and a semi join expressed as a join plus a distinct is a semi join the executor cannot
341/// recognise.
342#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
343pub enum JoinKind {
344 /// Rows that match on both sides.
345 Inner,
346 /// Every left row, padded with nulls where the right does not match.
347 Left,
348 /// Every right row, padded with nulls where the left does not match.
349 Right,
350 /// Both of the above at once.
351 Full,
352 /// Left rows that have at least one match, each emitted once.
353 Semi,
354 /// Left rows that have no match.
355 Anti,
356 /// Left rows paired with their match, or with nulls, at most one right row each. What a
357 /// correlated scalar subquery unnests to.
358 Single,
359 /// The nth left row with the nth right row, which is DuckDB's `POSITIONAL JOIN`.
360 Positional,
361}
362
363impl JoinKind {
364 /// The spelling used in the textual form.
365 #[must_use]
366 pub fn keyword(self) -> &'static str {
367 match self {
368 Self::Inner => "INNER",
369 Self::Left => "LEFT",
370 Self::Right => "RIGHT",
371 Self::Full => "FULL",
372 Self::Semi => "SEMI",
373 Self::Anti => "ANTI",
374 Self::Single => "SINGLE",
375 Self::Positional => "POSITIONAL",
376 }
377 }
378
379 /// Every join kind, which is what the reader searches.
380 pub(crate) const ALL: [Self; 8] = [
381 Self::Inner,
382 Self::Left,
383 Self::Right,
384 Self::Full,
385 Self::Semi,
386 Self::Anti,
387 Self::Single,
388 Self::Positional,
389 ];
390}
391
392/// Which set operation.
393#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
394pub enum SetOpKind {
395 /// Rows from either side.
396 Union,
397 /// Rows from the left that are not on the right.
398 Except,
399 /// Rows on both sides.
400 Intersect,
401}
402
403impl SetOpKind {
404 /// The spelling used in the textual form.
405 #[must_use]
406 pub fn keyword(self) -> &'static str {
407 match self {
408 Self::Union => "UNION",
409 Self::Except => "EXCEPT",
410 Self::Intersect => "INTERSECT",
411 }
412 }
413
414 /// Every set operation, which is what the reader searches.
415 pub(crate) const ALL: [Self; 3] = [Self::Union, Self::Except, Self::Intersect];
416}
417
418#[cfg(test)]
419mod tests {
420 use super::*;
421 use crate::Slice;
422
423 /// Every node in one list, so that a variant added without a keyword, without a child slot or
424 /// without an entry in the reader's dispatch table fails here rather than at the first dump
425 /// that happens to contain one.
426 fn one_of_each() -> Vec<Node> {
427 vec![
428 Node::Get {
429 catalog: 0,
430 schema: 0,
431 table: 0,
432 alias: 0,
433 index: 0,
434 columns: Slice::EMPTY,
435 },
436 Node::Dummy,
437 Node::Values { index: 0, columns: Slice::EMPTY, rows: Slice::EMPTY },
438 Node::TableFunction {
439 index: 0,
440 function: 0,
441 args: Slice::EMPTY,
442 options: Slice::EMPTY,
443 settings: Slice::EMPTY,
444 columns: Slice::EMPTY,
445 },
446 Node::Filter { input: 0, predicate: 0 },
447 Node::Project { input: 0, index: 0, exprs: Slice::EMPTY, names: Slice::EMPTY },
448 Node::Aggregate { input: 0, index: 0, groups: Slice::EMPTY, aggregates: Slice::EMPTY },
449 Node::Sort { input: 0, keys: Slice::EMPTY },
450 Node::Limit { input: 0, count: None, offset: 0 },
451 Node::Distinct { input: 0, on: Slice::EMPTY },
452 Node::Join { left: 0, right: 1, kind: JoinKind::Inner, conditions: Slice::EMPTY },
453 Node::CrossProduct { left: 0, right: 1 },
454 Node::SetOp { left: 0, right: 1, kind: SetOpKind::Union, all: true, index: 0 },
455 ]
456 }
457
458 #[test]
459 fn every_operator_has_its_own_keyword() {
460 let mut keywords: Vec<&str> = one_of_each().iter().map(Node::keyword).collect();
461 let count = keywords.len();
462 keywords.sort_unstable();
463 keywords.dedup();
464 assert_eq!(keywords.len(), count, "two operators print the same keyword");
465 }
466
467 #[test]
468 fn arity_agrees_with_the_child_slots() {
469 for node in one_of_each() {
470 let counted = node.children().into_iter().flatten().count();
471 assert_eq!(node.arity(), counted, "{} disagrees with itself", node.keyword());
472 }
473 }
474
475 /// A child slot that is `None` before a slot that is `Some` would make the printer emit the
476 /// right input as the left one, and the reader would accept it.
477 #[test]
478 fn the_child_slots_are_filled_from_the_front() {
479 for node in one_of_each() {
480 let slots = node.children();
481 assert!(
482 !(slots[0].is_none() && slots[1].is_some()),
483 "{} has a right input and no left one",
484 node.keyword()
485 );
486 }
487 }
488
489 #[test]
490 fn only_the_operators_that_introduce_columns_have_a_table_index() {
491 for node in one_of_each() {
492 let expected = matches!(
493 node,
494 Node::Get { .. }
495 | Node::Values { .. }
496 | Node::TableFunction { .. }
497 | Node::Project { .. }
498 | Node::Aggregate { .. }
499 | Node::SetOp { .. }
500 );
501 assert_eq!(
502 node.table_index().is_some(),
503 expected,
504 "{} is on the wrong side of the table index rule",
505 node.keyword()
506 );
507 }
508 }
509
510 #[test]
511 fn every_join_kind_and_set_operation_is_in_the_list_the_reader_searches() {
512 assert_eq!(JoinKind::ALL.len(), 8);
513 assert_eq!(SetOpKind::ALL.len(), 3);
514 let mut names: Vec<&str> = JoinKind::ALL.iter().map(|k| k.keyword()).collect();
515 names.sort_unstable();
516 names.dedup();
517 assert_eq!(names.len(), JoinKind::ALL.len(), "two join kinds print the same keyword");
518 }
519}