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