Crate rudb_plan 

The logical plan, its textual form, and the parser that reads that form back.

Rank 9 in the layer rule. See xtask/layers.toml and spec/18-package-layout.md.

This is the bound logical plan: what the binder produces, what the optimizer rewrites, and what the physical planner consumes. spec/04-architecture.md calls it “a bound logical plan with fully resolved types”, and both halves of that are enforced here rather than assumed. Every expression carries a LogicalType that is stored next to it, and every column reference is a ColumnBinding naming the operator that produced the column and the position within that operator’s output. There are no names in an expression and nothing in this crate looks anything up in a catalog. Name resolution happened in the binder and a plan that still needs it is a plan that is not bound.

The textual form

spec/00-README.md requires that every layer has a textual form and a round-trip parser, and that requirement is the reason this crate exists before there is an optimizer to rewrite anything. A plan prints as an indented tree, two spaces a level, parent before children:

Project #2 [#1.0::VARCHAR AS SearchPhrase, #1.1::BIGINT AS c]
  Limit 10 offset 0
    Sort [#1.1::BIGINT DESC NULLS LAST]
      Aggregate #1 groups=[#0.0::VARCHAR] aggregates=[count_star()::BIGINT]
        Filter (#0.0::VARCHAR <> ''::VARCHAR)::BOOLEAN
          Get memory.main.hits AS hits #0 [SearchPhrase::VARCHAR]

Plan::parse reads that back, and printing the result produces the same text. That fixed point is a test rather than a claim, and it is the thing that makes a plan diffable across a rewrite, fuzzable on its own, and bisectable when a pass starts returning a wrong answer.

Every expression is written form::TYPE. The annotation is on every node and not only on the ones where a reader would need it, because the alternative is a parser that has to re-derive types, and re-deriving types means consulting the function catalog, and a dump that cannot be read without a catalog is not a dump. It is verbose. It is also exact, and exact is the whole job here.

Why an arena

Nodes, expressions and their lists all live in flat vectors and refer to each other by u32 index, the same shape rudb_parse::Ast uses. A plan is rewritten many times by spec/09-optimizer.md’s fixed pass sequence, and a rewrite of a boxed tree is a traversal that allocates at every node. It also makes a plan one owned value that clones with three memcpys, which is what lets a pass be a pure function from plan to plan without that being expensive.

The cost is that a reference is a number and a number can point at the wrong thing. Plan::validate is the answer to that, and it is what section 9.1 means by the invariant every pass has to preserve.

What is not here yet

Window functions, subquery expressions, correlated references, UNNEST, lambdas, prepared statement parameters, and everything on the write side. The M0 transformer cannot produce any of them, so a representation for them here would be a representation nothing has ever constructed, which is a representation that is wrong in a way nobody finds out about. Neither Expr nor Node is #[non_exhaustive], which is deliberate: adding a plan node should stop the build in every optimizer pass that has to decide what to do about it.

Structs

Arm

One WHEN/THEN pair of a Expr::Case.

ColumnBinding

Which column, by identity rather than by name.

Plan

A bound logical plan.

Slice

A contiguous run in one of Plan’s pools.

SortKey

One key of a Node::Sort.

Enums

CompareOp

Which comparison a Expr::Compare performs.

ConjunctionOp

Which connective a Expr::Conjunction uses.

Expr

One bound expression.

JoinKind

Which join.

Node

One logical operator.

SetOpKind

Which set operation.

Type Aliases

ExprRef

A reference to an expression in Plan’s expression arena.

NodeRef

A reference to a node in Plan’s node arena.

StrRef

A reference to an interned string in Plan’s string table.

ValueRef

A reference to a constant in Plan’s value table.