pub enum Node {
Show 23 variants
Get {
catalog: StrRef,
schema: StrRef,
table: StrRef,
alias: StrRef,
index: u32,
columns: Slice,
},
Dummy,
Values {
index: u32,
columns: Slice,
rows: Slice,
},
TableFunction {
index: u32,
function: StrRef,
args: Slice,
options: Slice,
settings: Slice,
columns: Slice,
},
LateralFunction {
input: NodeRef,
index: u32,
function: StrRef,
args: Slice,
options: Slice,
settings: Slice,
columns: Slice,
},
Filter {
input: NodeRef,
predicate: ExprRef,
},
Project {
input: NodeRef,
index: u32,
exprs: Slice,
names: Slice,
},
Aggregate {
input: NodeRef,
index: u32,
groups: Slice,
aggregates: Slice,
},
Window {
input: NodeRef,
index: u32,
partition: Slice,
order: Slice,
frame: WindowFrame,
expressions: Slice,
},
Sort {
input: NodeRef,
keys: Slice,
},
Limit {
input: NodeRef,
count: Bound,
offset: Bound,
},
LimitPercent {
input: NodeRef,
percent: Share,
offset: Bound,
},
TopN {
input: NodeRef,
keys: Slice,
count: u64,
offset: u64,
},
Fetch {
input: NodeRef,
index: u32,
args: Slice,
columns: Slice,
row: ExprRef,
},
TableFetch {
input: NodeRef,
index: u32,
catalog: StrRef,
schema: StrRef,
table: StrRef,
columns: Slice,
row: ExprRef,
},
Distinct {
input: NodeRef,
on: Slice,
},
Join {
left: NodeRef,
right: NodeRef,
kind: JoinKind,
conditions: Slice,
build: BuildSide,
},
LinkJoin {
child: NodeRef,
parent: NodeRef,
kind: JoinKind,
conditions: Slice,
rid: ExprRef,
},
DependentJoin {
left: NodeRef,
right: NodeRef,
kind: JoinKind,
conditions: Slice,
},
CrossProduct {
left: NodeRef,
right: NodeRef,
},
MaterializedCte {
definition: NodeRef,
body: NodeRef,
name: StrRef,
cte: u32,
columns: Slice,
},
CteScan {
index: u32,
cte: u32,
name: StrRef,
columns: Slice,
},
SetOp {
left: NodeRef,
right: NodeRef,
kind: SetOpKind,
all: bool,
index: u32,
},
}Expand description
One logical operator.
Children are the inputs, in the order Node::children returns them, which is the order they
print in and the order the reader expects.
PartialEq and not Eq, because Node::LimitPercent holds a percentage as a f64.
Value is the same shape for the same reason.
Variants§
Get
A base table scan.
The projection is in columns, so a scan of two columns of a 105-column table is a two
column scan in the plan and not a filter over a wide one. spec/09-optimizer.md section
9.2 calls projection pushdown the difference between 20 GB and 200 MB on ClickBench, and
this is the field it pushes into.
Fields
Dummy
One row and no columns.
What SELECT 1 sits on top of. Not an empty result: an empty result produces no rows and
SELECT 1 produces one, and conflating them is how a scalar subquery starts returning
nothing instead of null.
Values
Literal rows.
Every row has the same length as columns, which Plan::validate
checks, because a ragged VALUES is a wrong answer rather than a crash.
Fields
TableFunction
A function call where a table goes, such as range(10).
The arguments are expressions rather than numbers, because range(2 + 3) is a legal call
and folding it here would mean the plan could not be printed back as what was written. They
cannot refer to a column: a table function that sees the row on its left is LATERAL, and
that is Node::LateralFunction.
A separate node from Node::Values even though range(3) and VALUES (0), (1), (2)
produce the same rows, because the one that produces three million rows should be three
numbers in the plan rather than three million expressions in it.
Fields
options: SliceThe names of the named parameters the call was written with, into the name pool.
read_csv('f.csv', delim=';') keeps the delim here rather than only in whatever the
binder made of it, because the executor opens the file a second time and has to open it
the same way. A parameter the binder answers on its own, such as binary_as_string,
is here too, so that a plan prints back as the call that was written.
LateralFunction
A table function evaluated once per row of its input, which is what LATERAL means.
FROM t, range(t.n) is this. A table function’s arguments are what produce its rows rather
than something read over rows that already exist, so there is nothing underneath one for a
domain to be pushed into and nothing the rules in the unnesting pass can rewrite it into.
This is the operator those rules stop at: the domain goes in on the left, the arguments read
it, and the call is made once per row of it.
The output is the input’s columns followed by the function’s, which is a cross product whose right side is allowed to change per left row. That is what lets the join putting the rows back beside their outer row sit above this and read the domain columns where it reads them everywhere else.
Only the series family reaches here. A reader takes a file name, the binder settles the
columns by opening the file, and a name that is not a constant is refused there, so a
correlated read_csv never gets this far.
Fields
Filter
A predicate over the input, keeping the rows where it is true.
True, not “not false”. A null predicate drops the row, which is SQL’s rule and is the
difference between WHERE and CHECK.
Project
A projection, producing a new set of columns from the input’s.
Fields
Aggregate
A grouped or ungrouped aggregation.
The output is the group expressions followed by the aggregates, in that order, and that is
what a binding into index means. An ungrouped aggregate has an empty groups and still
produces exactly one row, including over an empty input.
Fields
aggregates: SliceThe aggregate expressions, into the expression list pool. Every element is an
Expr::Aggregate and this is the only place one may appear.
Window
Window expressions that share one partition, ordering, and frame.
Fields
frame: WindowFrameThe complete frame shared by this compatible expression run.
expressions: SliceDirect Expr::Window expressions appended to the input columns.
Sort
An ordering.
Limit
A row count limit and an offset.
Both are a Bound, which is a number when the query said one and a column of the input
when it wrote something the binder could not settle. See Bound for what puts the value
in that column and who reads it.
Fields
LimitPercent
A limit written as a share of the input rather than as a row count.
LIMIT 30 PERCENT over ten rows is three rows, and it is a node of its own rather than a
Node::Limit with another field for three reasons. The share is of the whole input, so
this cannot emit anything until it has counted every row, where a plain limit hands each
chunk on as it arrives and stops the scan early. The rewrites that fire on a plain limit are
wrong here: a filter pushed under this one changes how many rows there are to take a share
of, and the sort underneath it cannot become a top n because the count is not known until
the sort has finished. And the pin builds a separate Limit Percent operator for it, which
is the same split one layer down.
A share the binder worked out is between nought and a hundred inclusive, checked while the
query is bound, because that is where the pin refuses LIMIT 101 PERCENT too. The offset is
applied after the share has been worked out, so LIMIT 30 PERCENT OFFSET 2 over ten rows is
three rows starting at the third.
Both fields can be read off the rows instead of being a number written down here, for the
same reason a plain limit’s count can. LIMIT (SELECT 30)% OFFSET (SELECT 2) holds two
numbers nobody has before the query runs, so each arrives as a column of the input and is
read off the first chunk. See Share and Bound.
Fields
offset: BoundHow many rows to skip first. Never Bound::All, which is not an offset.
TopN
A sort with a limit over it, which never holds more rows than the limit can emit.
The same answer as a Node::Limit over a Node::Sort and a different amount of work.
A sort has to see every row before it can emit the first one, so it holds the whole input;
this holds the rows that could still come out and throws the rest away as it goes, which on
ORDER BY x LIMIT 10 over a hundred million rows is ten rows rather than a hundred million.
count is not optional, because LIMIT ALL over a sort is a sort and there would be nothing
to bound. The offset is part of the node rather than left above it, since the rows that are
skipped still have to be found to be skipped, so what this has to keep is count + offset.
Fields
Fetch
The columns of rows something below already picked out, read back from the file by ordinal.
This is the top half of late materialisation. A SELECT * FROM hits ORDER BY EventTime LIMIT 10 over a hundred and five columns needs one column to decide which ten rows win and all
hundred and five of those ten rows afterwards, and a plan that carries the wide rows through
the top N reads the whole file to throw almost all of it away. The rewrite in
rudb-opt’s late module narrows the scan under the top N to the ordering columns plus the
row’s ordinal inside its file, and puts this above it to read the rest for the rows that
survived.
The ordinals come out of the input rather than being counted here, because the operator that
counted them is the scan and everything between the scan and here may have dropped rows. The
column that holds them is Self::Fetch::row, and the scan produced it because the rewrite
turned file_row_number on.
The produced columns are the whole row and not only the deferred part, so the answer is one read of the file at the ordinals rather than a stitch of what was carried with what was fetched. That costs the ordering column a second read of a few pages and saves the plan above this from having any idea the rewrite happened.
Fields
index: u32The table index the produced columns bind against, which is the one the node this replaced produced, so that nothing above has to be rebound.
TableFetch
Rows of a catalog table read back by their table-wide ordinal.
Fields
Distinct
Duplicate elimination, over the whole row or over named expressions.
Fields
Join
A join with a condition.
Fields
conditions: SliceThe conditions, into the expression list pool, combined with AND. Empty is a join
with no condition, which for an inner join is a cross product and for an outer join
is not.
build: BuildSideWhich input is gathered whole before the other one starts.
The binder emits BuildSide::Right for everything, because at binding time there is
nothing to choose with. rudb_opt’s sides pass overwrites it from an estimate, and
the executor honours whatever it finds here.
LinkJoin
A join answered by reading a stored forward link rather than by building a hash table.
spec/graph/05-execution.md section 5.2. The condition is child.fk = parent.pk for a
declared relationship whose forward link is stored, and the child side reaches the join
with its row id intact. Where a Self::Join builds one side and probes it with the
other, this reads one link value beside the child’s own columns and emits the parent’s
projected columns as gathers into the parent’s column vectors. There is no build side,
no hash table, no probe and no materialization of the parent per child row.
It is a node of its own rather than a flag on Self::Join because the two are different
operators with different shapes: this one has a driving side and no gathered side, so the
pipeline under it is one pipeline rather than two, and a reader of an explain output that
saw Join with a flag would have to know the flag to know what ran.
Nothing produces this unless the graph sections are on. Section 3.1 says deleting every
graph section from a file must change no answer, only the time, so every plan holding one
of these is a plan the optimizer could have written as a Self::Join over the same two
inputs, and the rule that rewrites it says so by construction.
Fields
parent: NodeRefThe parent input.
Never scanned as a pipeline. It is here so that the column bindings above this node keep naming the scan they named, so that the projection pushdown pass can still see which of the parent’s columns are wanted, and so that dropping back to a hash join is a change of node rather than a re-plan.
kind: JoinKindInner, left, semi or anti. Section 5.2 handles no others: right and full need the parent rows nothing pointed at, which is the backward direction.
conditions: SliceThe join condition, into the expression list pool. Exactly one equality, which is what makes this shape recognizable at all.
rid: ExprRefThe child column holding the row id the link is indexed by, which has to be BIGINT.
Named here rather than looked for by the builder, the same way Self::Fetch names
its ordinal. The rule that writes this node is the one thing that has proved the row id
survives to here, by way of crate::rids_of, and a builder that went looking for the
column by name afterwards would be trusting a name where the rule trusted an analysis.
DependentJoin
A join whose right input can refer to columns produced by its left input.
Binding emits this for a correlated subquery. The unnesting pass has to replace every one before execution, so the executor never evaluates the right input once per left row.
Fields
CrossProduct
An unconditional cross product.
Separate from a Node::Join with no conditions because join ordering treats them
differently: a cross product has no edge in the join graph and section 9.4’s dynamic
program enumerates connected subgraphs.
MaterializedCte
A WITH name AS MATERIALIZED (...), which is run once and read wherever it is named.
The left input is the definition and the right input is the query that reads it. They are in that order because that is the order they run in: the definition is a pipeline breaker whichever operators are in it, since nothing above may start until the rows are all there.
A plain WITH is not this. The reference binary inlines one at every use whatever its
shape and however many times it is named, and the only decision left is whether the rows
are needed at all, which is why an unused one is dropped rather than run for nothing.
Fields
body: NodeRefThe query that reads them, which is where every Node::CteScan for this one is.
CteScan
A read of a Node::MaterializedCte that has already run.
A leaf, the same way a table scan is. What it reads was computed by a node above it rather than by a node under it, which is the one place in the plan where that is true, and it is why the materialisation holds its body as an input rather than sitting beside it.
Fields
SetOp
UNION, EXCEPT or INTERSECT.
Implementations§
Source§impl Node
impl Node
Sourcepub fn keyword(&self) -> &'static str
pub fn keyword(&self) -> &'static str
The keyword this operator prints as, which is also what the reader dispatches on.
Sourcepub fn children(&self) -> [Option<NodeRef>; 2]
pub fn children(&self) -> [Option<NodeRef>; 2]
The inputs, in printing order.
Two slots rather than a Vec, because no logical operator in this set has three inputs and
the printer walks this on every node of every dump. A caller wants
node.children().into_iter().flatten().
Sourcepub fn table_index(&self) -> Option<u32>
pub fn table_index(&self) -> Option<u32>
The table index this operator introduces, if it introduces one.