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///
58/// `PartialEq` and not `Eq`, because [`Node::LimitPercent`] holds a percentage as a `f64`.
59/// [`Value`](rudb_common::Value) is the same shape for the same reason.
60#[derive(Debug, Clone, PartialEq)]
61pub enum Node {
62 /// A base table scan.
63 ///
64 /// The projection is in `columns`, so a scan of two columns of a 105-column table is a two
65 /// column scan in the plan and not a filter over a wide one. `spec/09-optimizer.md` section
66 /// 9.2 calls projection pushdown the difference between 20 GB and 200 MB on ClickBench, and
67 /// this is the field it pushes into.
68 Get {
69 /// The catalog name.
70 catalog: StrRef,
71 /// The schema name.
72 schema: StrRef,
73 /// The table name.
74 table: StrRef,
75 /// The alias the query used, which is what an error message should say.
76 alias: StrRef,
77 /// The table index that this scan's columns bind against.
78 index: u32,
79 /// The projected columns with their types, into the field pool.
80 columns: Slice,
81 },
82 /// One row and no columns.
83 ///
84 /// What `SELECT 1` sits on top of. Not an empty result: an empty result produces no rows and
85 /// `SELECT 1` produces one, and conflating them is how a scalar subquery starts returning
86 /// nothing instead of null.
87 Dummy,
88 /// Literal rows.
89 ///
90 /// Every row has the same length as `columns`, which [`Plan::validate`](crate::Plan::validate)
91 /// checks, because a ragged `VALUES` is a wrong answer rather than a crash.
92 Values {
93 /// The table index that these columns bind against.
94 index: u32,
95 /// The output columns with their types, into the field pool.
96 columns: Slice,
97 /// The rows, into the row pool, each row a slice of the expression list pool.
98 rows: Slice,
99 },
100 /// A function call where a table goes, such as `range(10)`.
101 ///
102 /// The arguments are expressions rather than numbers, because `range(2 + 3)` is a legal call
103 /// and folding it here would mean the plan could not be printed back as what was written. They
104 /// cannot refer to a column: a table function that sees the row on its left is `LATERAL`, and
105 /// that is [`Node::LateralFunction`].
106 ///
107 /// A separate node from [`Node::Values`] even though `range(3)` and `VALUES (0), (1), (2)`
108 /// produce the same rows, because the one that produces three million rows should be three
109 /// numbers in the plan rather than three million expressions in it.
110 TableFunction {
111 /// The table index that this call's columns bind against.
112 index: u32,
113 /// Which function, as its own canonical name.
114 function: StrRef,
115 /// The arguments, into the expression list pool.
116 args: Slice,
117 /// The names of the named parameters the call was written with, into the name pool.
118 ///
119 /// `read_csv('f.csv', delim=';')` keeps the `delim` here rather than only in whatever the
120 /// binder made of it, because the executor opens the file a second time and has to open it
121 /// the same way. A parameter the binder answers on its own, such as `binary_as_string`,
122 /// is here too, so that a plan prints back as the call that was written.
123 options: Slice,
124 /// What each of those names was given, into the expression list pool and the same length.
125 ///
126 /// Constants, every one of them. The binder refuses anything else, because a parameter can
127 /// decide what the columns are and the columns are settled there.
128 settings: Slice,
129 /// The produced columns with their types, into the field pool.
130 columns: Slice,
131 },
132 /// A table function evaluated once per row of its input, which is what `LATERAL` means.
133 ///
134 /// `FROM t, range(t.n)` is this. A table function's arguments are what produce its rows rather
135 /// than something read over rows that already exist, so there is nothing underneath one for a
136 /// domain to be pushed into and nothing the rules in the unnesting pass can rewrite it into.
137 /// This is the operator those rules stop at: the domain goes in on the left, the arguments read
138 /// it, and the call is made once per row of it.
139 ///
140 /// The output is the input's columns followed by the function's, which is a cross product whose
141 /// right side is allowed to change per left row. That is what lets the join putting the rows
142 /// back beside their outer row sit above this and read the domain columns where it reads them
143 /// everywhere else.
144 ///
145 /// Only the series family reaches here. A reader takes a file name, the binder settles the
146 /// columns by opening the file, and a name that is not a constant is refused there, so a
147 /// correlated `read_csv` never gets this far.
148 LateralFunction {
149 /// The rows the call is made against, one call per row.
150 input: NodeRef,
151 /// The table index that this call's columns bind against.
152 index: u32,
153 /// Which function, as its own canonical name.
154 function: StrRef,
155 /// The arguments, into the expression list pool, read against a row of `input`.
156 args: Slice,
157 /// The names of the named parameters the call was written with, into the name pool.
158 options: Slice,
159 /// What each of those names was given, into the expression list pool and the same length.
160 settings: Slice,
161 /// The produced columns with their types, into the field pool, not counting the input's.
162 columns: Slice,
163 },
164 /// A predicate over the input, keeping the rows where it is true.
165 ///
166 /// True, not "not false". A null predicate drops the row, which is SQL's rule and is the
167 /// difference between `WHERE` and `CHECK`.
168 Filter {
169 /// The input.
170 input: NodeRef,
171 /// The predicate, which has to be `BOOLEAN`.
172 predicate: ExprRef,
173 },
174 /// A projection, producing a new set of columns from the input's.
175 Project {
176 /// The input.
177 input: NodeRef,
178 /// The table index the produced columns bind against.
179 index: u32,
180 /// The expressions, into the expression list pool.
181 exprs: Slice,
182 /// One output name per expression, into the name list pool.
183 ///
184 /// Names are carried through the whole plan rather than attached at the root, because the
185 /// thing a person reads a plan dump to answer is usually which column this is, and a dump
186 /// with the names stripped out answers that with a number.
187 names: Slice,
188 },
189 /// A grouped or ungrouped aggregation.
190 ///
191 /// The output is the group expressions followed by the aggregates, in that order, and that is
192 /// what a binding into `index` means. An ungrouped aggregate has an empty `groups` and still
193 /// produces exactly one row, including over an empty input.
194 Aggregate {
195 /// The input.
196 input: NodeRef,
197 /// The table index the produced columns bind against.
198 index: u32,
199 /// The group expressions, into the expression list pool.
200 groups: Slice,
201 /// The aggregate expressions, into the expression list pool. Every element is an
202 /// [`Expr::Aggregate`](crate::Expr::Aggregate) and this is the only place one may appear.
203 aggregates: Slice,
204 },
205 /// Window expressions that share one partition, ordering, and frame.
206 Window {
207 /// Rows over which the windows are evaluated.
208 input: NodeRef,
209 /// The table index of the appended window result columns.
210 index: u32,
211 /// Expressions that divide the input into independent partitions.
212 partition: Slice,
213 /// The ordering within each partition.
214 order: Slice,
215 /// The complete frame shared by this compatible expression run.
216 frame: WindowFrame,
217 /// Direct [`Expr::Window`](crate::Expr::Window) expressions appended to the input columns.
218 expressions: Slice,
219 },
220 /// An ordering.
221 Sort {
222 /// The input.
223 input: NodeRef,
224 /// The keys in priority order, into the sort key pool.
225 keys: Slice,
226 },
227 /// A row count limit and an offset.
228 ///
229 /// Both are constants. `LIMIT` over an expression is legal SQL and DuckDB evaluates it before
230 /// the plan runs, so by the time it is here it is a number or the query did not bind.
231 Limit {
232 /// The input.
233 input: NodeRef,
234 /// How many rows to emit, or all of them.
235 count: Option<u64>,
236 /// How many rows to skip first.
237 offset: u64,
238 },
239 /// A limit written as a share of the input rather than as a row count.
240 ///
241 /// `LIMIT 30 PERCENT` over ten rows is three rows, and it is a node of its own rather than a
242 /// [`Node::Limit`] with another field for three reasons. The share is of the whole input, so
243 /// this cannot emit anything until it has counted every row, where a plain limit hands each
244 /// chunk on as it arrives and stops the scan early. The rewrites that fire on a plain limit are
245 /// wrong here: a filter pushed under this one changes how many rows there are to take a share
246 /// of, and the sort underneath it cannot become a top n because the count is not known until
247 /// the sort has finished. And the pin builds a separate `Limit Percent` operator for it, which
248 /// is the same split one layer down.
249 ///
250 /// The percentage is between nought and a hundred inclusive, checked while the query is bound,
251 /// because that is where the pin refuses `LIMIT 101 PERCENT` too. The offset is applied after
252 /// the share has been worked out, so `LIMIT 30 PERCENT OFFSET 2` over ten rows is three rows
253 /// starting at the third.
254 LimitPercent {
255 /// The input.
256 input: NodeRef,
257 /// The share of the input to emit, from nought to a hundred.
258 percent: f64,
259 /// How many rows to skip first.
260 offset: u64,
261 },
262 /// A sort with a limit over it, which never holds more rows than the limit can emit.
263 ///
264 /// The same answer as a [`Node::Limit`] over a [`Node::Sort`] and a different amount of work.
265 /// A sort has to see every row before it can emit the first one, so it holds the whole input;
266 /// this holds the rows that could still come out and throws the rest away as it goes, which on
267 /// `ORDER BY x LIMIT 10` over a hundred million rows is ten rows rather than a hundred million.
268 ///
269 /// `count` is not optional, because `LIMIT ALL` over a sort is a sort and there would be nothing
270 /// to bound. The offset is part of the node rather than left above it, since the rows that are
271 /// skipped still have to be found to be skipped, so what this has to keep is `count + offset`.
272 TopN {
273 /// The input.
274 input: NodeRef,
275 /// The keys in priority order, into the sort key pool.
276 keys: Slice,
277 /// How many rows to emit.
278 count: u64,
279 /// How many rows to skip first.
280 offset: u64,
281 },
282 /// The columns of rows something below already picked out, read back from the file by ordinal.
283 ///
284 /// This is the top half of late materialisation. A `SELECT * FROM hits ORDER BY EventTime LIMIT
285 /// 10` over a hundred and five columns needs one column to decide which ten rows win and all
286 /// hundred and five of those ten rows afterwards, and a plan that carries the wide rows through
287 /// the top N reads the whole file to throw almost all of it away. The rewrite in
288 /// `rudb-opt`'s `late` module narrows the scan under the top N to the ordering columns plus the
289 /// row's ordinal inside its file, and puts this above it to read the rest for the rows that
290 /// survived.
291 ///
292 /// The ordinals come out of the input rather than being counted here, because the operator that
293 /// counted them is the scan and everything between the scan and here may have dropped rows. The
294 /// column that holds them is [`Self::Fetch::row`], and the scan produced it because the rewrite
295 /// turned `file_row_number` on.
296 ///
297 /// The produced columns are the whole row and not only the deferred part, so the answer is one
298 /// read of the file at the ordinals rather than a stitch of what was carried with what was
299 /// fetched. That costs the ordering column a second read of a few pages and saves the plan above
300 /// this from having any idea the rewrite happened.
301 Fetch {
302 /// The input, which carries each row's ordinal inside the file.
303 input: NodeRef,
304 /// The table index the produced columns bind against, which is the one the node this
305 /// replaced produced, so that nothing above has to be rebound.
306 index: u32,
307 /// The file, into the expression list pool. One constant path, because a row ordinal only
308 /// says which row when there is one file it could be in.
309 args: Slice,
310 /// The produced columns with their types, into the field pool.
311 columns: Slice,
312 /// The input column holding the ordinal, which has to be `BIGINT`.
313 row: ExprRef,
314 },
315 /// Rows of a catalog table read back by their table-wide ordinal.
316 TableFetch {
317 input: NodeRef,
318 index: u32,
319 catalog: StrRef,
320 schema: StrRef,
321 table: StrRef,
322 columns: Slice,
323 row: ExprRef,
324 },
325 /// Duplicate elimination, over the whole row or over named expressions.
326 Distinct {
327 /// The input.
328 input: NodeRef,
329 /// The `DISTINCT ON` expressions, into the expression list pool. Empty means the whole
330 /// row, which is plain `DISTINCT`.
331 on: Slice,
332 },
333 /// A join with a condition.
334 Join {
335 /// The left input.
336 left: NodeRef,
337 /// The right input.
338 right: NodeRef,
339 /// Which join.
340 kind: JoinKind,
341 /// The conditions, into the expression list pool, combined with `AND`. Empty is a join
342 /// with no condition, which for an inner join is a cross product and for an outer join
343 /// is not.
344 conditions: Slice,
345 /// Which input is gathered whole before the other one starts.
346 ///
347 /// The binder emits [`BuildSide::Right`] for everything, because at binding time there is
348 /// nothing to choose with. `rudb_opt`'s `sides` pass overwrites it from an estimate, and
349 /// the executor honours whatever it finds here.
350 build: BuildSide,
351 },
352 /// A join whose right input can refer to columns produced by its left input.
353 ///
354 /// Binding emits this for a correlated subquery. The unnesting pass has to replace every one
355 /// before execution, so the executor never evaluates the right input once per left row.
356 DependentJoin {
357 /// The outer input whose columns the right side may reference.
358 left: NodeRef,
359 /// The correlated input.
360 right: NodeRef,
361 /// Which result shape the subquery needs.
362 kind: JoinKind,
363 /// Conditions introduced while binding the subquery.
364 conditions: Slice,
365 },
366 /// An unconditional cross product.
367 ///
368 /// Separate from a [`Node::Join`] with no conditions because join ordering treats them
369 /// differently: a cross product has no edge in the join graph and section 9.4's dynamic
370 /// program enumerates connected subgraphs.
371 CrossProduct {
372 /// The left input.
373 left: NodeRef,
374 /// The right input.
375 right: NodeRef,
376 },
377 /// A `WITH name AS MATERIALIZED (...)`, which is run once and read wherever it is named.
378 ///
379 /// The left input is the definition and the right input is the query that reads it. They are
380 /// in that order because that is the order they run in: the definition is a pipeline breaker
381 /// whichever operators are in it, since nothing above may start until the rows are all there.
382 ///
383 /// A plain `WITH` is not this. The reference binary inlines one at every use whatever its
384 /// shape and however many times it is named, and the only decision left is whether the rows
385 /// are needed at all, which is why an unused one is dropped rather than run for nothing.
386 MaterializedCte {
387 /// The query whose rows are held.
388 definition: NodeRef,
389 /// The query that reads them, which is where every [`Node::CteScan`] for this one is.
390 body: NodeRef,
391 /// The name it was written with, which is what the printer and an error message say.
392 name: StrRef,
393 /// Which materialisation this is, matching the `cte` of the scans that read it.
394 ///
395 /// A number of its own rather than the table index, because a scan binds against its own
396 /// index and two scans of one materialisation have two of those.
397 cte: u32,
398 /// The held columns with their types, into the field pool.
399 columns: Slice,
400 },
401 /// A read of a [`Node::MaterializedCte`] that has already run.
402 ///
403 /// A leaf, the same way a table scan is. What it reads was computed by a node above it rather
404 /// than by a node under it, which is the one place in the plan where that is true, and it is
405 /// why the materialisation holds its body as an input rather than sitting beside it.
406 CteScan {
407 /// The table index that this read's columns bind against.
408 index: u32,
409 /// Which materialisation it reads.
410 cte: u32,
411 /// The name it was written with.
412 name: StrRef,
413 /// The produced columns with their types, into the field pool.
414 columns: Slice,
415 },
416 /// `UNION`, `EXCEPT` or `INTERSECT`.
417 SetOp {
418 /// The left input.
419 left: NodeRef,
420 /// The right input.
421 right: NodeRef,
422 /// Which operation.
423 kind: SetOpKind,
424 /// Whether duplicates are kept.
425 all: bool,
426 /// The table index the produced columns bind against, since the output is neither side's
427 /// columns.
428 index: u32,
429 },
430}
431
432impl Node {
433 /// The keyword this operator prints as, which is also what the reader dispatches on.
434 #[must_use]
435 pub fn keyword(&self) -> &'static str {
436 match self {
437 Self::Get { .. } => "Get",
438 Self::Dummy => "Dummy",
439 Self::Values { .. } => "Values",
440 Self::TableFunction { .. } => "TableFunction",
441 Self::LateralFunction { .. } => "LateralFunction",
442 Self::Filter { .. } => "Filter",
443 Self::Project { .. } => "Project",
444 Self::Aggregate { .. } => "Aggregate",
445 Self::Window { .. } => "Window",
446 Self::Sort { .. } => "Sort",
447 Self::Limit { .. } => "Limit",
448 Self::LimitPercent { .. } => "LimitPercent",
449 Self::TopN { .. } => "TopN",
450 Self::Fetch { .. } => "Fetch",
451 Self::TableFetch { .. } => "TableFetch",
452 Self::Distinct { .. } => "Distinct",
453 Self::Join { .. } => "Join",
454 Self::DependentJoin { .. } => "DependentJoin",
455 Self::CrossProduct { .. } => "CrossProduct",
456 Self::MaterializedCte { .. } => "MaterializedCte",
457 Self::CteScan { .. } => "CteScan",
458 Self::SetOp { .. } => "SetOp",
459 }
460 }
461
462 /// The inputs, in printing order.
463 ///
464 /// Two slots rather than a `Vec`, because no logical operator in this set has three inputs and
465 /// the printer walks this on every node of every dump. A caller wants
466 /// `node.children().into_iter().flatten()`.
467 #[must_use]
468 pub fn children(&self) -> [Option<NodeRef>; 2] {
469 match *self {
470 Self::Get { .. }
471 | Self::Dummy
472 | Self::Values { .. }
473 | Self::TableFunction { .. }
474 | Self::CteScan { .. } => [None, None],
475 Self::Filter { input, .. }
476 | Self::Project { input, .. }
477 | Self::Aggregate { input, .. }
478 | Self::Window { input, .. }
479 | Self::Sort { input, .. }
480 | Self::Limit { input, .. }
481 | Self::LimitPercent { input, .. }
482 | Self::TopN { input, .. }
483 | Self::Fetch { input, .. }
484 | Self::TableFetch { input, .. }
485 | Self::Distinct { input, .. }
486 | Self::LateralFunction { input, .. } => [Some(input), None],
487 Self::Join { left, right, .. }
488 | Self::DependentJoin { left, right, .. }
489 | Self::CrossProduct { left, right }
490 | Self::SetOp { left, right, .. } => [Some(left), Some(right)],
491 Self::MaterializedCte { definition, body, .. } => [Some(definition), Some(body)],
492 }
493 }
494
495 /// How many inputs this operator takes.
496 #[must_use]
497 pub fn arity(&self) -> usize {
498 self.children().into_iter().flatten().count()
499 }
500
501 /// The table index this operator introduces, if it introduces one.
502 #[must_use]
503 pub fn table_index(&self) -> Option<u32> {
504 match *self {
505 Self::Get { index, .. }
506 | Self::Values { index, .. }
507 | Self::TableFunction { index, .. }
508 | Self::LateralFunction { index, .. }
509 | Self::Project { index, .. }
510 | Self::Fetch { index, .. }
511 | Self::TableFetch { index, .. }
512 | Self::Aggregate { index, .. }
513 | Self::Window { index, .. }
514 | Self::CteScan { index, .. }
515 | Self::SetOp { index, .. } => Some(index),
516 _ => None,
517 }
518 }
519}
520
521/// Which join.
522///
523/// `Semi` and `Anti` are here because subquery unnesting produces them directly, per section 9.2,
524/// and a semi join expressed as a join plus a distinct is a semi join the executor cannot
525/// recognise.
526#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
527pub enum JoinKind {
528 /// Rows that match on both sides.
529 Inner,
530 /// Every left row, padded with nulls where the right does not match.
531 Left,
532 /// Every right row, padded with nulls where the left does not match.
533 Right,
534 /// Both of the above at once.
535 Full,
536 /// Left rows that have at least one match, each emitted once.
537 Semi,
538 /// Left rows that have no match.
539 Anti,
540 /// Left rows paired with their match, or with nulls, at most one right row each. What a
541 /// correlated scalar subquery unnests to.
542 Single,
543 /// Every left row plus a nullable boolean saying whether its condition matched the right side.
544 /// A null means no row matched and at least one comparison was unknown.
545 Mark,
546 /// The nth left row with the nth right row, which is DuckDB's `POSITIONAL JOIN`.
547 Positional,
548}
549
550impl JoinKind {
551 /// The spelling used in the textual form.
552 #[must_use]
553 pub fn keyword(self) -> &'static str {
554 match self {
555 Self::Inner => "INNER",
556 Self::Left => "LEFT",
557 Self::Right => "RIGHT",
558 Self::Full => "FULL",
559 Self::Semi => "SEMI",
560 Self::Anti => "ANTI",
561 Self::Single => "SINGLE",
562 Self::Mark => "MARK",
563 Self::Positional => "POSITIONAL",
564 }
565 }
566
567 /// Every join kind, which is what the reader searches.
568 pub(crate) const ALL: [Self; 9] = [
569 Self::Inner,
570 Self::Left,
571 Self::Right,
572 Self::Full,
573 Self::Semi,
574 Self::Anti,
575 Self::Single,
576 Self::Mark,
577 Self::Positional,
578 ];
579
580 /// The same join with its two inputs the other way round, for the kinds where there is one.
581 ///
582 /// Swapping the inputs of a `LEFT` join makes a `RIGHT` join and the other way round, because
583 /// the kind names a side. `INNER` and `FULL` name neither and are their own mirror. The rest
584 /// return `None`: `SEMI`, `ANTI`, `SINGLE` and `MARK` produce the left side's rows, or a
585 /// column about them, so their left input is not a side but the subject, and `POSITIONAL`
586 /// pairs the nth with the nth, which no reordering of one input preserves.
587 #[must_use]
588 pub fn mirrored(self) -> Option<Self> {
589 match self {
590 Self::Inner => Some(Self::Inner),
591 Self::Left => Some(Self::Right),
592 Self::Right => Some(Self::Left),
593 Self::Full => Some(Self::Full),
594 Self::Semi | Self::Anti | Self::Single | Self::Mark | Self::Positional => None,
595 }
596 }
597}
598
599/// Which input of a join is gathered whole before the other one starts.
600///
601/// A join is two inputs and a dependency edge between them: one side is finished and held, and then
602/// the other side's rows are matched against what was held. This says which side that is. It is
603/// where the hash table goes when the hash join in #62 lands, and it is the side today's nested
604/// loop turns into chunks and rescans once per row of the other one.
605///
606/// Which side that should be is not a property of the join and is not decided here. It is decided
607/// by [`sides`](../../rudb_opt/sides/index.html) from a cardinality estimate, and the rule it uses
608/// belongs to whichever operator is reading this, not to the flag.
609#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
610pub enum BuildSide {
611 /// The right input, which is what the binder emits and what every join did before this existed.
612 #[default]
613 Right,
614 /// The left input, which means the executor swaps the two and puts the answer back in order.
615 Left,
616}
617
618impl BuildSide {
619 /// The spelling used in the textual form.
620 #[must_use]
621 pub fn keyword(self) -> &'static str {
622 match self {
623 Self::Right => "right",
624 Self::Left => "left",
625 }
626 }
627
628 /// Both sides, which is what the reader searches.
629 pub(crate) const ALL: [Self; 2] = [Self::Right, Self::Left];
630}
631
632/// Which set operation.
633#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
634pub enum SetOpKind {
635 /// Rows from either side.
636 Union,
637 /// Rows from the left that are not on the right.
638 Except,
639 /// Rows on both sides.
640 Intersect,
641}
642
643impl SetOpKind {
644 /// The spelling used in the textual form.
645 #[must_use]
646 pub fn keyword(self) -> &'static str {
647 match self {
648 Self::Union => "UNION",
649 Self::Except => "EXCEPT",
650 Self::Intersect => "INTERSECT",
651 }
652 }
653
654 /// Every set operation, which is what the reader searches.
655 pub(crate) const ALL: [Self; 3] = [Self::Union, Self::Except, Self::Intersect];
656}
657
658#[cfg(test)]
659mod tests {
660 use super::*;
661 use crate::Slice;
662
663 /// Every node in one list, so that a variant added without a keyword, without a child slot or
664 /// without an entry in the reader's dispatch table fails here rather than at the first dump
665 /// that happens to contain one.
666 fn one_of_each() -> Vec<Node> {
667 vec![
668 Node::Get {
669 catalog: 0,
670 schema: 0,
671 table: 0,
672 alias: 0,
673 index: 0,
674 columns: Slice::EMPTY,
675 },
676 Node::Dummy,
677 Node::Values { index: 0, columns: Slice::EMPTY, rows: Slice::EMPTY },
678 Node::TableFunction {
679 index: 0,
680 function: 0,
681 args: Slice::EMPTY,
682 options: Slice::EMPTY,
683 settings: Slice::EMPTY,
684 columns: Slice::EMPTY,
685 },
686 Node::LateralFunction {
687 input: 0,
688 index: 0,
689 function: 0,
690 args: Slice::EMPTY,
691 options: Slice::EMPTY,
692 settings: Slice::EMPTY,
693 columns: Slice::EMPTY,
694 },
695 Node::Filter { input: 0, predicate: 0 },
696 Node::Project { input: 0, index: 0, exprs: Slice::EMPTY, names: Slice::EMPTY },
697 Node::Aggregate { input: 0, index: 0, groups: Slice::EMPTY, aggregates: Slice::EMPTY },
698 Node::Sort { input: 0, keys: Slice::EMPTY },
699 Node::Limit { input: 0, count: None, offset: 0 },
700 Node::LimitPercent { input: 0, percent: 50.0, offset: 0 },
701 Node::Distinct { input: 0, on: Slice::EMPTY },
702 Node::Join {
703 left: 0,
704 right: 1,
705 kind: JoinKind::Inner,
706 conditions: Slice::EMPTY,
707 build: BuildSide::default(),
708 },
709 Node::DependentJoin {
710 left: 0,
711 right: 1,
712 kind: JoinKind::Single,
713 conditions: Slice::EMPTY,
714 },
715 Node::CrossProduct { left: 0, right: 1 },
716 Node::SetOp { left: 0, right: 1, kind: SetOpKind::Union, all: true, index: 0 },
717 ]
718 }
719
720 #[test]
721 fn every_operator_has_its_own_keyword() {
722 let mut keywords: Vec<&str> = one_of_each().iter().map(Node::keyword).collect();
723 let count = keywords.len();
724 keywords.sort_unstable();
725 keywords.dedup();
726 assert_eq!(keywords.len(), count, "two operators print the same keyword");
727 }
728
729 #[test]
730 fn arity_agrees_with_the_child_slots() {
731 for node in one_of_each() {
732 let counted = node.children().into_iter().flatten().count();
733 assert_eq!(node.arity(), counted, "{} disagrees with itself", node.keyword());
734 }
735 }
736
737 /// A child slot that is `None` before a slot that is `Some` would make the printer emit the
738 /// right input as the left one, and the reader would accept it.
739 #[test]
740 fn the_child_slots_are_filled_from_the_front() {
741 for node in one_of_each() {
742 let slots = node.children();
743 assert!(
744 !(slots[0].is_none() && slots[1].is_some()),
745 "{} has a right input and no left one",
746 node.keyword()
747 );
748 }
749 }
750
751 #[test]
752 fn only_the_operators_that_introduce_columns_have_a_table_index() {
753 for node in one_of_each() {
754 let expected = matches!(
755 node,
756 Node::Get { .. }
757 | Node::Values { .. }
758 | Node::TableFunction { .. }
759 | Node::LateralFunction { .. }
760 | Node::Project { .. }
761 | Node::Aggregate { .. }
762 | Node::SetOp { .. }
763 );
764 assert_eq!(
765 node.table_index().is_some(),
766 expected,
767 "{} is on the wrong side of the table index rule",
768 node.keyword()
769 );
770 }
771 }
772
773 #[test]
774 fn every_join_kind_and_set_operation_is_in_the_list_the_reader_searches() {
775 assert_eq!(JoinKind::ALL.len(), 9);
776 assert_eq!(SetOpKind::ALL.len(), 3);
777 let mut names: Vec<&str> = JoinKind::ALL.iter().map(|k| k.keyword()).collect();
778 names.sort_unstable();
779 names.dedup();
780 assert_eq!(names.len(), JoinKind::ALL.len(), "two join kinds print the same keyword");
781 }
782}