plan

type Aggregate ¶

type Aggregate struct {
	Input Node
	Keys  []expr.Node
	Aggs  []expr.Node

	// MaintainOrder emits groups in first-appearance order rather than in hash
	// order. Without it the output order is genuinely unspecified, and tests that
	// assume otherwise are flaky.
	//
	// # What it costs, stated as a number rather than as "time and memory"
	//
	// Nothing at all when the aggregation fits in memory: the group table is already
	// built in first-appearance order, so the flag changes no work.
	//
	// When it SPILLS the cost is two things. Every routed row carries an extra int64
	// input ordinal into its partition file, and the result cannot stream — first
	// appearance interleaves resident and spilled groups, so emitting the group
	// created at input row 3 requires partition 9's aggregation to be finished. The
	// whole answer is materialised and permuted at the end, so an ordered spilling
	// group-by peaks at budget + result rather than at budget. The result is
	// O(distinct keys), which is what a non-spilling aggregation holds anyway.
	//
	// BenchmarkGroupBySpillingOrdered beside BenchmarkGroupBySpilling is the measured
	// figure.
	MaintainOrder bool
}

Aggregate groups rows and reduces each group.

The output is one row per distinct key: the key columns first, in the order written, then the aggregate columns.

Also a PIPELINE BREAKER, and the one that motivates Accumulator.Merge: a parallel or spilling implementation computes partial aggregates independently and combines them, so every aggregate must be expressible as (init, step, merge, finish) rather than as a single pass.

func (a *Aggregate) Children() []Node

func (a *Aggregate) Label() string

func (a *Aggregate) Schema() (*dtype.Schema, error)

func (a *Aggregate) WithChildren(kids []Node) Node

type AsOfJoin ¶

type AsOfJoin struct {
	Left, Right Node

	// LeftOn and RightOn are the ORDERING key — exactly one column per side, the one
	// the nearest-key search runs over.
	LeftOn, RightOn expr.Node

	// By are exact-match keys applied BEFORE the search, so a trade matches only
	// quotes for its own symbol. Empty means one global group.
	LeftBy, RightBy []expr.Node

	Strategy AsOfStrategy

	// Tolerance bounds how far the search may reach, for a temporal key. Zero means
	// unbounded unless ToleranceGiven, when it admits only an exact match, as a
	// Polars tolerance of zero does (step 315).
	Tolerance      dtype.Interval
	ToleranceGiven bool

	// NumTolerance bounds it for a numeric key, when set (step 315).
	NumTolerance AsOfNumber

	// Coalesce says whether the ordering key is merged, as Polars' coalesce: by
	// default when both sides name it alike, never with CoalesceOff, where the right
	// one is kept, suffixed on a collision (step 315). The by-keys are always merged.
	Coalesce CoalesceMode

	// AllowExactMatches lets a right key EQUAL to the left key match. Default true,
	// so the zero value of the option struct is the ordinary behaviour; the physical
	// planner carries the resolved value.
	AllowExactMatches bool

	Suffix string
}

AsOfJoin matches each left row to the NEAREST right row rather than to an equal one.

It is a LEFT join with a different match rule ¶

Every left row survives; the right columns are null when nothing is near enough. That is why Layout below delegates to a synthesised Join rather than deriving a second output schema: join_layout.go calls itself "the single authority on a join's output", and the collision, suffixing and key-merging algorithm is exactly what that sentence exists to stop being copied.

Why a separate node rather than another JoinKind ¶

Join has no slot for a strategy, a tolerance or an exact-match flag, and its predicates — Keyed, filtersLeft, leftCanBeNull — all read as statements about EQUI semantics. A kind that quietly meant "nearest" would make every one of them subtly wrong rather than obviously absent.

Both sides must be sorted on On, and it is CHECKED ¶

The nearest-key search is a binary search over a sorted run. ursus-api.md's example calls SetSorted, an unchecked assertion; step 14 already decided that question for GroupByDynamic and the answer does not change here. Pushdown's doc puts it best: a capability claim that is trusted but wrong returns wrong rows silently.

func (a *AsOfJoin) Children() []Node

func (a *AsOfJoin) Label() string

func (a *AsOfJoin) Layout() (*JoinLayout, error)

func (a *AsOfJoin) Schema() (*dtype.Schema, error)

func (a *AsOfJoin) WithChildren(kids []Node) Node

type AsOfNumber ¶ added in v0.6.7

type AsOfNumber struct {
	Set   bool
	IsInt bool
	Int   int64
	Float float64
}

AsOfNumber is a numeric key's tolerance (step 315): an integer, exact, or a float.

func (n AsOfNumber) AsFloat() float64

func (n AsOfNumber) String() string

type AsOfStrategy ¶

type AsOfStrategy uint8

AsOfStrategy picks which neighbouring right row a left row matches.

const (
	// AsOfBackward is the default: the LAST right key at or before the left key.
	// "Attach the most recent quote to each trade."
	AsOfBackward AsOfStrategy = iota
	// AsOfForward is the first right key at or after the left key.
	AsOfForward
	// AsOfNearest is whichever of those two is closer, ties going backward.
	AsOfNearest
)

func (s AsOfStrategy) String() string

type Cache ¶ added in v0.5.0

type Cache struct {
	ID    int
	Input Node
}

Cache marks a subtree the query uses at more than one place, so it runs once.

Why it is needed ¶

A LazyFrame shares nodes: `agg := scan.GroupBy(k).Agg(..)` used in a join and again under a max is ONE *Aggregate with two parents. Resolve is a TransformUp, which copies a shared subtree into each place it is reached, and the engine then ran it twice. PDS-H q15 does exactly that with its per-supplier revenue, which was most of why it ran at 10.5× Polars (step 141).

How it stays one ¶

MarkShared wraps each shared subtree in a Cache with an ID BEFORE Resolve. The copies Resolve makes are each under a Cache with the same ID, and the physical planner runs the first copy it plans and has every Cache of that ID replay it.

That is only right if every copy computes the same rows, so the optimizer treats a Cache as a barrier: predicate pushdown and projection pushdown both stop at a node they do not know and optimize below it as a fresh root, and the build-side rule gives every copy the same answer to whether its rows must keep their order. The copies are rewritten by the same rules from the same tree, and come out the same.

The price of the barrier: a filter above one site is not pushed into the shared subtree, and every site sees every column the subtree produces. MarkShared caches only subtrees with a join, an aggregate or a sort in them, where computing once is worth more than that (step 143).

A Cache with ID 0 is one LazyFrame.Cache asked for, before MarkShared numbers it.

func (c *Cache) Children() []Node

func (c *Cache) Label() string

func (c *Cache) Schema() (*dtype.Schema, error)

func (c *Cache) WithChildren(kids []Node) Node

type Caps ¶

type Caps struct {
	// Projection: the source can return a subset of columns.
	Projection bool
}

Caps describes what a source can do for itself.

A source that cannot honour a pushdown is not penalised: the physical planner inserts the equivalent operator above the scan. The logical plan always records the projection and predicate regardless, so Explain shows the user's intent and the optimizer's reasoning stays source-independent.

Predicate support is deliberately NOT here — see PredicatePushdown. A single bool cannot express it correctly, because whether a source can honour a predicate depends on the predicate.

type CoalesceMode ¶

type CoalesceMode uint8

CoalesceMode is tri-state, and that is not over-engineering.

The user-facing option has three states — unset, on, off — and unset is not equal to either: it means "merge for Inner/Left/Right/Semi/Anti, keep both for Full". A bool field would make a hand-built node's zero value mean Coalesce(false), which is not what the public API produces for the same input. CoalesceAuto as the zero value makes the node and the API agree by construction, which is the same reason Pushdown's zero value is Unsupported.

const (
	CoalesceAuto CoalesceMode = iota
	CoalesceOn
	CoalesceOff
)

type ConcatMode ¶

type ConcatMode uint8

ConcatMode says how much a Union will reconcile.

const (
	// ConcatStrict requires the same columns, in the same order. Types still
	// promote and nullability still widens — see Union's doc for why those are not
	// a relaxation.
	ConcatStrict ConcatMode = iota

	// ConcatDiagonal takes the union of the columns, filling a frame's missing ones
	// with nulls.
	ConcatDiagonal

	// ConcatRelaxed and ConcatDiagonalRelaxed are ConcatStrict and ConcatDiagonal
	// meeting a column's types at dtype.Supertype, which may round or make text, as
	// Polars' vertical_relaxed and diagonal_relaxed do, where the others meet them
	// exactly (step 307).
	ConcatRelaxed
	ConcatDiagonalRelaxed
)

func (m ConcatMode) Relaxed() bool

func (m ConcatMode) String() string

type ConstEvaluator ¶

type ConstEvaluator interface {
	// Fold evaluates n, which is guaranteed to contain no column references, and
	// returns the equivalent literal.
	//
	// Returning (nil, false, nil) declines: an expression the folder does not
	// handle is left exactly as it was. An ERROR is different and must be
	// propagated as "do not fold" by the caller, never as a query failure — see
	// foldExpr.
	Fold(n expr.Node, in *dtype.Schema) (expr.Node, bool, error)
}

ConstEvaluator folds an all-literal expression to a single literal.

Why this is an interface rather than a call into internal/kernel ¶

Folding needs a real evaluator, and there is exactly one correct one — the kernel the executor itself uses. Anything else is a second implementation of promotion, overflow and null semantics, and the whole point of folding is that the answer cannot differ from what the query would have computed.

But internal/kernel is L30 and reaching it from here would drag Arrow, the allocator and GOEXPERIMENT=simd into a package that today imports none of them. design/logical.md §13 states what that buys: this layer's tests run "without an executor, without Arrow, and without a Parquet file", so a plan can be built, resolved, optimized and explained with no data anywhere. TestPlanPackageNeedsNoArrow asserts it rather than trusting it.

So the evaluator is INJECTED, from a layer that already has Arrow. Nothing in this signature names an Arrow type, which is what makes that work: the rule below is written once and simplifies with or without a folder attached. Without one — which is what this package's own tests see — every structural rewrite still runs, and only Lit⊕Lit is skipped.

type Distinct ¶

type Distinct struct {
	Input Node
	// Subset restricts the comparison to these columns. nil means every column.
	Subset []string
}

Distinct removes duplicate rows.

It shares the hash table and row encoder with Aggregate — a distinct is an aggregation with no aggregates — but is a separate node so the optimizer can reason about it (it preserves the schema exactly, which Aggregate does not). Distinct keeps the first row of each distinct key.

There is deliberately no MaintainOrder here ¶

There used to be, copied from Aggregate, and it was never assigned, never read and not even rendered by Label(). Unlike Sort.Limit — which step 9 found dead and WOKE UP, because ArgTopK was waiting behind it — this one had no implementation to switch to: distinctOp is a streaming filter that keeps the first row per key and emits in input order unconditionally, so `MaintainOrder = false` meant nothing. A flag whose only evidence of purpose is its own doc comment is worse than no flag, because the next reader believes it.

func (d *Distinct) Children() []Node

func (d *Distinct) Label() string

func (d *Distinct) Schema() (*dtype.Schema, error)

func (d *Distinct) WithChildren(kids []Node) Node

type ExplainOptions ¶

type ExplainOptions struct {
	// Schema annotates each node with its output schema. Verbose, but it is the
	// fastest way to see where a type went wrong.
	Schema bool
	// Projection shows the column pruning a scan ended up with, and how many of
	// the source's columns that is. This is the visible evidence that pushdown
	// happened, so it is on by default.
	Projection bool
}

ExplainOptions controls Explain's output.

func DefaultExplainOptions() ExplainOptions

type Explode ¶ added in v0.3.0

type Explode struct {
	Input   Node
	Columns []string
}

Explode turns each row's list into one row per element.

It is the operation that makes a List column useful rather than merely readable: after it, every kernel, aggregate and join that already exists applies to the elements. Nothing else about lists has to be built first.

An empty list produces a row ¶

[10, 11]   ->  two rows, 10 and 11
[]         ->  ONE row, null
null       ->  ONE row, null

An empty list vanishing would be the other plausible rule, and it is wrong for two reasons. It would silently drop rows — the height only looks wrong if someone checks it — and it would make exploding two columns together incoherent, because the two would disagree about how many rows a pair of empty lists produces. Polars makes the same choice.

The consequence is worth stating because it looks like a bug from either side: **explode ERASES the empty-versus-null distinction.** A List column keeps them apart carefully — they differ only in the validity bit, and data.NewList's doc is mostly about not confusing them — and after this node they are the same row. That is correct. The distinction is a property of a list, and once the list is gone there is nothing left to carry it.

Several columns explode together ¶

They are exploded as ONE operation rather than one after another, because exploding twice would give the cross product where the caller means the zip. Every named column must therefore have the same length in a given row; a mismatch is an error naming the row rather than a truncation.

func (e *Explode) Children() []Node

func (e *Explode) Label() string

func (e *Explode) Schema() (*dtype.Schema, error)

func (e *Explode) WithChildren(kids []Node) Node

type Filter ¶

type Filter struct {
	Input Node
	Preds []expr.Node
}

Filter keeps rows where every predicate is true.

Preds is a conjunct slice rather than a single AND tree so that predicate pushdown can move conjuncts independently — the common case is that some conjuncts can reach the scan and others cannot.

Null semantics ¶

A row is kept iff the predicate is VALID AND TRUE. A null predicate drops the row, matching SQL's WHERE. This is worth stating explicitly because the alternative (treating null as true) is a plausible-looking choice that silently changes results, and because `Not(p)` therefore does not partition the rows: a row where p is null is dropped by both `Filter(p)` and `Filter(Not(p))`.

func (f *Filter) Children() []Node

func (f *Filter) Label() string

func (f *Filter) Schema() (*dtype.Schema, error)

func (f *Filter) WithChildren(kids []Node) Node

type Flags ¶

type Flags struct {
	ProjectionPushdown bool
	PredicatePushdown  bool
	LimitPushdown      bool
	SimplifyExprs      bool

	// JoinPredicatePushdown gates the Join ARM of predicate pushdown, separately
	// from the rest of the rule. It is the newest and by far the most dangerous
	// piece of the optimizer — the legality table has four barrier cells whose
	// violation returns different rows with no error — so it gets its own switch.
	JoinPredicatePushdown bool

	// CollapseCrossJoin folds a filter above a cross join into a real join
	// condition. It is what turns JoinWhere from an O(|L|x|R|) loop into a hash
	// join, so switching it off is how you measure what it is worth — and how you
	// check that it is an optimisation rather than a change of answer.
	CollapseCrossJoin bool

	// BuildSide lets an inner join hash its smaller input, by exchanging the
	// inputs when the right one is estimated much larger. See buildSide.
	BuildSide bool

	// RuntimeFilters lets a join's built keys filter its probe side where the probe
	// key comes from, below the operators between (step 167).
	RuntimeFilters bool

	// ShareSubplans runs a subtree the query uses at more than one place once,
	// and replays it at each. It is applied before Resolve, by MarkShared, rather
	// than as a rule: once Resolve has copied a shared subtree, nothing says the
	// copies were one. See Cache.
	ShareSubplans bool
}

Flags switches individual rules off.

This exists for two reasons that both matter: benchmarking the value of a rule, and bisecting a wrong answer down to the rule that caused it. An optimizer you cannot turn off one piece at a time is an optimizer you cannot debug.

func DefaultFlags() Flags

func NoFlags() Flags

type HStack ¶

type HStack struct {
	Inputs []Node
	Labels []string
	// Extend pads a frame shorter than the others with nulls, as Polars'
	// concat(how="horizontal_extend") does, where HStack refuses it (step 307).
	Extend bool
}

HStack places frames side by side: same rows, columns concatenated.

Structurally unlike Union, despite reading like its twin ¶

Union appends rows and can stream, because a row belongs to exactly one child. HStack pairs rows ACROSS children, and nothing in the engine aligns batch boundaries between independent pipelines — child A may deliver 8192 rows while child B delivers 100. So it buffers, and it is the only operation here that has to.

Column names must be distinct across the inputs. Silently suffixing, as the join does, would be wrong: a join has a principled left/right asymmetry to name the suffix after, and here the inputs are peers.

Labels, when set, are the expressions a Select's inputs compute (step 258), which a height mismatch names instead of frame numbers; nil for a frame's HStack.

func (h *HStack) Children() []Node

func (h *HStack) Label() string

func (h *HStack) Schema() (*dtype.Schema, error)

func (h *HStack) WithChildren(kids []Node) Node

type Join ¶

type Join struct {
	Left, Right Node

	// LeftOn[i] is matched against RightOn[i]. Equal lengths, enforced by
	// resolveJoin. Empty for JoinCross and non-empty for every other kind.
	LeftOn, RightOn []expr.Node

	Kind JoinKind

	// Suffix is appended to a colliding right column name. "" means
	// DefaultJoinSuffix, so the zero value is the ordinary behaviour.
	Suffix string

	Coalesce   CoalesceMode
	NullsEqual bool // zero value false: a null key matches nothing, as in SQL
	Validate   JoinValidation

	// Order is the row order the join promises, Polars' maintain_order (step 314).
	// The zero value promises none. Any other keeps the build_side rule from
	// exchanging the inputs; a Rightward one has the physical join build its left
	// input and probe with its right, and a join that spills sorts its rows back.
	Order JoinOrder

	// SwapAtRuntime is set by the build_side rule on a join whose inputs it could
	// exchange, whether or not its estimates made it: the physical join may then
	// exchange them itself, by their actual sizes (step 162). The rule proves the
	// rest: an inner join, nothing above it depending on its order, SwapJoin exact.
	SwapAtRuntime bool

	// Publish is the slot this join publishes its build side's keys to, for the
	// RuntimeFilter the runtimeFilters rule placed on its probe side; nil when none
	// was (step 167).
	Publish *RuntimeSlot

	// Residual is evaluated per candidate PAIR, before the match verdict, and is
	// SEMI/ANTI ONLY.
	//
	// # Why it cannot be a Filter above the join
	//
	// A semi join emits a left row once if ANY right row matches. Filtering its
	// output filters left rows that already survived, which answers a different
	// question: `EXISTS(r : k(r) == k(l) AND p(l, r))` is not
	// `EXISTS(r : k(r) == k(l)) AND p(l, ...)` — the second has no r to name.
	//
	// Inner needs none of this. There a pair IS the output row, so the residual is
	// exactly a Filter above the join, which is what JoinWhere and
	// collapse_cross_join do and why they needed no operator change.
	//
	// Names resolve against PairLayout, not Layout: Semi and Anti output the left
	// schema alone, so the predicate's right-hand columns exist in no schema this
	// node publishes.
	Residual []expr.Node
}

Join combines two inputs.

The first two-child node ¶

Every other plan node has exactly one child. The generic traversals — Walk, TransformUp, Explain, and both pushdown rules' default branches — were already written N-ary and need nothing. What does need care is anything that reasons about a SIDE, because left keys name left columns and right keys name right columns; see Expressions and rule_projection.

Self-joins ¶

lf.Join(lf, ...) is legal. The plan is then a shared subtree rather than a DAG, so Walk and TransformUp visit it twice, Resolve resolves it twice (idempotent — resolveScan short-circuits on Full != nil), Explain prints it twice, and the physical planner opens the source twice. All acceptable, none surprising once stated. Under a memory limit the build side is partitioned to disk on the join key and the buckets are replayed one at a time, so an equi-join over more data than memory works. The ORDER of the output then depends on the limit — see WithMemoryLimit — and there is deliberately no flag to opt out, because restoring probe order would mean holding an output that can be larger than both inputs.

func (j *Join) Children() []Node

func (j *Join) HasResidual() bool

func (j *Join) Label() string

func (j *Join) Layout() (*JoinLayout, error)

func (j *Join) PairLayout() (*JoinLayout, error)

func (j *Join) Schema() (*dtype.Schema, error)

func (j *Join) WithChildren(kids []Node) Node

type JoinColumn ¶

type JoinColumn struct {
	Side  JoinSide
	Index int // ordinal in THAT side's input schema

	// CoalesceWith is the RIGHT input ordinal whose value merges into this column,
	// or -1. Only ever set on a FromLeft column. The operator emits
	// coalesce(left, right); Schema records the promoted type.
	CoalesceWith int
}

JoinColumn is the provenance of one output column, positionally aligned with JoinLayout.Schema.

type JoinKind ¶

type JoinKind uint8

JoinKind is the shape of a join.

const (
	// JoinInner is the zero value and the universal default: only matching pairs.
	JoinInner JoinKind = iota
	JoinLeft           // every left row; right columns null where unmatched
	JoinRight          // every right row; the mirror
	JoinFull           // every row from both sides
	JoinSemi           // left rows with at least one match — a filter
	JoinAnti           // left rows with no match — the inverse of semi
	JoinCross          // cartesian product, no keys
)

func (k JoinKind) Keyed() bool

func (k JoinKind) String() string

type JoinLayout ¶

type JoinLayout struct {
	Schema  *dtype.Schema
	Columns []JoinColumn // len == Schema.Len()

	// KeyTypes[i] is the promoted type in which key pair i is COMPARED. Both sides
	// cast to it. This is the expr.Binding lesson: the evaluator must use the
	// resolved type rather than re-deriving it, or two copies of the promotion
	// rules drift.
	KeyTypes []dtype.DataType
}

JoinLayout is the single authority on a join's output.

Why this returns more than a schema ¶

Step 2's audit found WithColumns.Schema() and resolveWithColumns() had implemented DIFFERENT semantics, which surfaced as "the optimizer produced a plan whose schema does not resolve". The fix was one function.

A join has a worse version of the same exposure, because the physical operator needs more than the schema: it needs to know, per output column, which side and which ordinal to gather from, and which right column to merge with. Returning only a *dtype.Schema would force the operator to re-derive "which right columns did I drop, which did I rename" — a second implementation of the collision algorithm, which would diverge.

So Layout returns everything, and Schema() is a one-line projection of it.

type JoinOrder ¶ added in v0.6.7

type JoinOrder uint8

JoinOrder is the row order a join promises: Polars' maintain_order (step 314).

Left and LeftRight are one order here: the left input's rows in their order, each row's matches in the right's, and then a Right or Full join's unmatched right rows in theirs. Right and RightLeft are its mirror. Polars' Left promises less than its LeftRight, the order of a row's matches; ursus keeps both.

const (
	JoinOrderNone JoinOrder = iota
	JoinOrderLeft
	JoinOrderRight
	JoinOrderLeftRight
	JoinOrderRightLeft
)

func (o JoinOrder) Rightward() bool

func (o JoinOrder) String() string

func (o JoinOrder) Valid() bool

type JoinSide ¶

type JoinSide uint8

JoinSide says which input an output column came from.

const (
	FromLeft JoinSide = iota
	FromRight
)

type JoinValidation ¶

type JoinValidation uint8

JoinValidation asserts a cardinality, erroring when the data violates it.

The first term names the LEFT frame, matching pandas and Polars: ManyToOne on orders.Join(customers) asserts that the customers are unique.

ursus-api.md calls accidental fan-out "the single most common analytics bug", which is the whole reason this exists.

const (
	ValidateNone       JoinValidation = iota
	ValidateOneToOne                  // keys unique on BOTH sides
	ValidateOneToMany                 // keys unique on the LEFT
	ValidateManyToOne                 // keys unique on the RIGHT
	ValidateManyToMany                // no constraint
)

func (v JoinValidation) RequiresLeftUnique() bool

func (v JoinValidation) RequiresRightUnique() bool

func (v JoinValidation) String() string

type Limit ¶

type Limit struct {
	Input Node
	N     int
}

Limit keeps at most N rows from the start of its input.

It is in the skeleton because head() is the first thing anyone types when exploring, and because it gives slice pushdown somewhere to land later.

func (l *Limit) Children() []Node

func (l *Limit) Label() string

func (l *Limit) Schema() (*dtype.Schema, error)

func (l *Limit) WithChildren(kids []Node) Node

type LocalRule ¶

type LocalRule interface {
	Name() string

	// Match returns a replacement for n, or (n, false, nil) to leave it alone.
	// Children are already rewritten when it is called.
	//
	// It may return a node with a DIFFERENT schema; Local declines the rewrite in
	// that case rather than trusting the rule. That is deliberate: the alternative
	// is every rule re-deriving the check, and the one that forgets returns wrong
	// columns with no error anywhere.
	Match(n Node, f Flags) (Node, bool, error)
}

LocalRule is the easy case: a pure node-to-node replacement, applied bottom-up with children already rewritten.

design/logical.md §8.1 specified this alongside Rule and RunMode; the two pushdowns shipped without it because each needs to carry state DOWN the tree (the required-column set, the predicates being moved) and so had to own its own traversal. A rule that only ever looks at one node and its already-rewritten children needs none of that, and writing the sweep again per rule is how a walk acquires four subtly different copies — see Expressions' own doc for the case where that already happened.

It is thin because TransformUp exists, and that is not what earns it a file ¶

The traversal below is four lines. What earns this adapter its place is the GUARD it wraps every Match in: a local rewrite is accepted only when the replacement resolves to the same schema as what it replaced. Optimizer.Run verifies that at the ROOT of the plan, which is exactly where a rewrite buried under a Filter or a Join is invisible — the root schema of `Filter(bad) -> Scan` is the scan's schema no matter what `bad` became.

type MergeSorted ¶

type MergeSorted struct {
	Left, Right Node

	// Key names the sorted column. One column, by name, because both schemas must
	// already be identical — there is no side to disambiguate.
	Key string
}

MergeSorted interleaves two frames that are already sorted on a key, keeping the result sorted.

It is not a join and not a concat ¶

A Union concatenates: every row of the first frame, then every row of the second, and the result is sorted only if the second's first row follows the first's last. A merge interleaves, so the result is sorted whenever both inputs were. Nothing is matched and no row is dropped — the output height is always the sum.

Both inputs must be sorted on Key, and it is CHECKED ¶

Same discipline as GroupByDynamic and the as-of join: a sortedness claim that is trusted but wrong produces a result that is merely in the wrong order, with no error — which is worse here than elsewhere, because the whole point of the operator is the order.

func (m *MergeSorted) Children() []Node

func (m *MergeSorted) Label() string

func (m *MergeSorted) Schema() (*dtype.Schema, error)

func (m *MergeSorted) WithChildren(kids []Node) Node

type Node ¶

type Node interface {
	// Schema returns the node's output schema. Valid only on a resolved plan;
	// it never reads data.
	Schema() (*dtype.Schema, error)

	// Children returns the input nodes, in order.
	Children() []Node

	// WithChildren returns a copy of this node with new children. It is how every
	// rewrite is expressed: no rule ever mutates a node in place.
	WithChildren([]Node) Node

	// Label is the single-line description used by Explain, without children.
	Label() string
	// contains filtered or unexported methods
}

Node is one relational operation.

Sealed by the unexported planNode method, so a type switch over Node is exhaustive by construction. The package is internal, but the identifier is exported because ursus, ursus/sql and the physical planner all consume it.

func MarkShared(root Node, auto bool) Node

func Resolve(ctx context.Context, n Node) (Node, error)

func SwapJoin(j *Join) Node

func TransformUp(n Node, fn func(Node) (Node, error)) (Node, error)

type Optimizer ¶

type Optimizer struct {

	// Verify checks the plan after every rule: that the root schema is unchanged,
	// and — see verifyStructure — the two properties the root schema cannot show.
	// On in the tests and in Explain, where a broken plan would otherwise render as
	// a clean golden file; off in Collect by default, because it costs a schema
	// resolution per node per rule.
	Verify bool
	// contains filtered or unexported fields
}

Optimizer applies rules to a resolved plan.

func NewOptimizer() *Optimizer

func (o *Optimizer) Run(n Node, flags Flags) (Node, error)

func (o *Optimizer) SetConstEvaluator(e ConstEvaluator)

type Pivot ¶ added in v0.6.7

type Pivot struct {
	Input     Node
	OnColumns Node
	Index     []string
	On        []string
	Values    []string

	// Names are the new columns' names, value by value, and within one value a row
	// of OnColumns at a time.
	Names []string

	// Empty says each value's empty cell follows the cells; otherwise the count
	// does.
	Empty bool
}

Pivot spreads a long table wide (step 303, P1 of v0.6.7-scope.md): Polars' pivot, lazy as Polars' LazyFrame.pivot is, its new columns given.

k  on  v                k  x  y
1  x   10      ->       1  10 20
1  y   20               2  30 null
2  x   30

Its input is an aggregate ¶

The root package builds Input as GroupBy(Index..., On...).MaintainOrder(): a row for each index and On values that meet, in the order each pair first appears, its cells reduced over the pair's rows. Pivot only lays those rows out, a column for each row of OnColumns, so the group-by does the work, and spills past a limit as any group-by does. Pivot holds the pairs.

Polars builds its pivot as one aggregate by the index, a cell a new column, each a filter of the value by its On values. Built so here, that is a pass over the input for every new column: 27 times the time at a thousand columns.

OnColumns, a second child ¶

The new columns' On values are a frame, a column for each of On, typed as it, a row for each new column of one value: an in-memory scan the root package builds, as HStack's frames are. A child rather than a field, because this package holds no data (design/logical.md §13); the physical planner reads it.

A cell the index and its On values never meet ¶

Polars' cell is the aggregate of the values that fall in it, so one that none fall in is the aggregate of none: a sum's 0, a count's 0, a mean's null. With Empty, each value's cells are followed by its cell over no values, which the group-by computes as the aggregate of a filter that keeps nothing, and a cell never met is that. Without an aggregate, a count follows the cells instead: a cell never met is null, and one of two rows or more is refused, as Polars' item refuses it.

Input's columns are therefore, in order: Index, On, a cell for each of Values, then either an empty cell for each of Values or the count.

func (p *Pivot) Children() []Node

func (p *Pivot) InputWidth() int

func (p *Pivot) Label() string

func (p *Pivot) Schema() (*dtype.Schema, error)

func (p *Pivot) Width() int

func (p *Pivot) WithChildren(kids []Node) Node

type PredicatePushdown ¶

type PredicatePushdown interface {
	Source

	// ClassifyPredicates reports, for each conjunct in preds and in the same
	// order, how completely this source can honour it.
	//
	// The returned slice MUST have exactly len(preds) entries. A source that
	// violates this is treated as supporting nothing — see ClassifyPredicates,
	// the package-level helper, which is the only thing the optimizer calls.
	//
	// It must be a pure function of preds: the optimizer may call it more than
	// once, and it runs long before any data is read.
	ClassifyPredicates(preds []expr.Node) []Pushdown
}

PredicatePushdown is implemented by a Source that can use predicates itself.

It is optional, in the same way source.Openable is: a Source that does not implement it is fully usable and simply gets its filtering done above the scan. The optional-interface shape is what makes Unsupported the default for every source that has not thought about the question.

type Project ¶

type Project struct {
	Input Node
	Exprs []expr.Node
}

Project computes a new set of columns from its input.

This backs Select. After Resolve, every expression produces exactly one column, so the output schema is one field per element of Exprs, in order.

func (p *Project) Children() []Node

func (p *Project) Label() string

func (p *Project) Schema() (*dtype.Schema, error)

func (p *Project) WithChildren(kids []Node) Node

type Pushdown ¶

type Pushdown uint8

Pushdown says how completely a source can honour ONE predicate conjunct.

Why this is not a bool ¶

The obvious `Caps.Predicate bool` is wrong in two independent ways, and both return wrong ROWS rather than an error.

First, capability is per-conjunct. In `x > 5 AND lower(y) = 'z'` a Parquet source can use the first against row-group statistics and can do nothing with the second. Filter.Preds is already a conjunct slice precisely so that conjuncts move independently; a single bool forces an all-or-nothing decision over a set whose members differ.

Second, and worse: honouring a predicate is not the same as SATISFYING it. Row-group pruning skips groups that provably contain no match, but every surviving group still holds non-matching rows. A source that reports "yes I handle predicates" and is then trusted to have applied them exactly returns those extra rows to the user. Silent, data-dependent, and invisible on any fixture small enough to fit in one row group.

const (
	// Unsupported: the source cannot use this conjunct. The Filter stays above
	// the Scan and the conjunct is not recorded on the Scan at all.
	//
	// THIS IS THE ZERO VALUE, deliberately. A short slice, a missing switch arm,
	// a source that forgets to answer — every accident lands here, and the
	// consequence of landing here is a slower plan rather than a wrong one.
	Unsupported Pushdown = iota

	// Inexact: the source may use this conjunct to skip data, but what it returns
	// is a SUPERSET of the matching rows. The conjunct goes into the Scan AND
	// stays in a Filter above it. This is what Parquet row-group pruning is.
	Inexact

	// Exact: the source returns exactly the matching rows, with the same null
	// semantics the engine would apply (a row survives iff the predicate is valid
	// and true). Only then may the Filter be removed.
	//
	// Claim this only if it is true. It is the one value that deletes a correctness
	// check from the plan.
	Exact
)

func ClassifyPredicates(src Source, preds []expr.Node) []Pushdown

func (p Pushdown) String() string

type Reverse ¶

type Reverse struct{ Input Node }

Reverse emits rows in the opposite order.

A full pipeline breaker: the last input row is the first output row, so nothing can be emitted until the input ends. Memory is O(rows), like Sort's — and unlike Sort it does no comparison, so it is the cheapest possible breaker and a useful shape to have written when external buffering arrives.

func (r *Reverse) Children() []Node

func (r *Reverse) Label() string

func (r *Reverse) Schema() (*dtype.Schema, error)

func (r *Reverse) WithChildren(kids []Node) Node

type RowEstimator ¶ added in v0.4.0

type RowEstimator interface {
	// EstimatedRows reports the source's row count, and false when it does not
	// know one — a CSV file, or a Parquet source whose footers have not been read.
	EstimatedRows() (int64, bool)
}

RowEstimator is a Source that can say how many rows it holds without reading them: an in-memory frame's length, the row counts in Parquet footers. It is optional, and an estimate rather than a promise — the build_side rule uses it to choose which side of a join to hash, and a wrong one costs speed, never an answer.

type RowIndex ¶

type RowIndex struct {
	Input  Node
	Name   string
	Offset uint32
}

RowIndex prepends a column numbering the rows from Offset.

It is a node rather than an expression ¶

`CumCount(false).Over()` computes the same numbers, and does it through the window sink — a pipeline breaker holding every row. A row index needs none of that: it is a counter that crosses batch boundaries, which is the third operator shape (stateful and streaming, like limitOp and distinctOp) rather than the second.

It also joins the list of things that depend on the driver delivering batches in input order. Numbering rows is meaningless otherwise.

func (r *RowIndex) Children() []Node

func (r *RowIndex) Label() string

func (r *RowIndex) Schema() (*dtype.Schema, error)

func (r *RowIndex) WithChildren(kids []Node) Node

type Rule ¶

type Rule interface {
	Name() string
	Apply(Node, Flags) (Node, bool, error)
}

Rule is one optimizer rewrite.

A rule takes a resolved plan and returns a rewritten one plus whether it changed anything. It must be SOUND: the rewritten plan must produce the same rows, in the same order, with the same schema. The optimizer verifies the schema half of that automatically — see Optimizer.Run.

Errors (step 179, audit row O12) ¶

A rule never adds an error the plan did not have: that is why predicate pushdown holds back a conjunct that can fail (fallible) and treats a join that validates its keys as a barrier. And it never removes one from a value the answer reads: `x OR true` is folded to true only when x cannot fail, since the query that evaluates x fails, and Polars' does too.

Whether a value nothing reads is computed is not promised either way. Today it is: a column a later Select leaves out is still computed, and a strict cast in it that fails fails the query. Polars and DuckDB drop such a column, its errors with it, and a rule here may come to as well. Apply receives the Flags so a rule can gate an individual ARM, not just its own existence. Predicate pushdown needs that: moving a filter through a join is far riskier than moving one through a sort, and "turn off all predicate pushdown" is too blunt a tool to bisect with when the two live in one recursive sweep.

func Local(r LocalRule) Rule

type RunMode ¶

type RunMode uint8

RunMode says how often the driver applies a rule.

const (
	// Once: the rule reaches its own fixed point internally, so a second pass
	// would be wasted work. Pushdowns are like this — one top-down sweep places
	// every projection.
	Once RunMode = iota
	// UntilStable: the rule makes local improvements that may enable each other,
	// so it is re-applied until nothing changes. Constant folding is like this.
	UntilStable
)

type RuntimeFilter ¶ added in v0.6.0

type RuntimeFilter struct {
	Input Node
	Key   string
	Slot  *RuntimeSlot
}

RuntimeFilter keeps the rows of Input whose Key may be among the keys the join that publishes Slot builds: every row until the join publishes, and after that the rows whose key it has. The join drops the rest anyway, so dropping them here, below the operators between, is a saving and never a change of answer (rule runtimeFilters, step 167).

func (r *RuntimeFilter) Children() []Node

func (r *RuntimeFilter) Label() string

func (r *RuntimeFilter) Schema() (*dtype.Schema, error)

func (r *RuntimeFilter) WithChildren(kids []Node) Node

type RuntimeSlot ¶ added in v0.6.0

type RuntimeSlot struct {
	ID int
	// contains filtered or unexported fields
}

RuntimeSlot is where a join publishes its build side's keys once its build is complete, for a RuntimeFilter on its probe side to read (step 167). What it holds is the physical layer's; the plan only carries it from the join to the filter.

func (s *RuntimeSlot) Publish(v any)

func (s *RuntimeSlot) Published() any

type Scan ¶

type Scan struct {
	Src  Source
	Full *dtype.Schema // the source's whole schema; set by Resolve

	// Projection is the exact column list to emit, in order. nil = all columns.
	Projection []string

	// Predicate holds conjuncts the source claimed it could use, and NOTHING
	// about what it guarantees. A conjunct here may be Exact (removed from the
	// plan) or Inexact (still present in a Filter above this node) — the Scan does
	// not record which, because it does not need to: whatever the source fails to
	// remove, the surviving Filter removes.
	//
	// A conjunct reaches this field only via predicatePushdown, which asks the
	// source with ClassifyPredicates first. Putting one here by hand asserts that
	// the source can honour it.
	Predicate []expr.Node

	// MaxRows is a hint that no more than this many rows will be consumed. 0 means
	// unlimited — chosen so the zero value is "read everything", since the failure
	// mode of a mistaken 0 with the opposite convention is an empty result.
	//
	// It is a HINT. A source may return more, and the Limit node that produced it
	// always remains in the plan to enforce the bound.
	MaxRows int
}

Scan reads from a Source.

Projection nil means "every column"; a non-nil (possibly empty) slice is the exact set to produce, in that order. Projection pushdown fills it in, which is the entire reason Scan exists as a distinct node from Source: the optimizer needs somewhere to record what it worked out.

Full is the source's complete schema, captured during Resolve so that later phases never need I/O or a context to answer a schema question.

Projection is the EMIT set, not the READ set ¶

Projection is what the scan produces, and it is what Schema reports. The columns the source must decode are a superset: a conjunct in Predicate that was classified Exact is deleted from the plan entirely, so nothing above the scan mentions its columns, yet the source cannot evaluate it without reading them.

Filter(c > 5).Select(a)   with c > 5 Exact
  =>  Scan{Projection: [a], Predicate: [c > 5]}

The source reads {a, c} and emits {a}. That is not a wart to be fixed by widening Projection — widening it would make the scan emit a column the plan above does not expect, changing the output schema. It is a documented part of the contract; see source.ScanSpec, which says the same thing to implementors.

func (s *Scan) Children() []Node

func (s *Scan) Label() string

func (s *Scan) ReadSet() []string

func (s *Scan) Schema() (*dtype.Schema, error)

func (s *Scan) WithChildren(kids []Node) Node

func (s *Scan) WithMaxRows(n int) *Scan

func (s *Scan) WithProjection(cols []string) *Scan

type Slice ¶

type Slice struct {
	Input  Node
	Offset int
	Len    int
}

Slice keeps Len rows starting at Offset.

Streaming, not a breaker: it counts rows past and stops, so it never holds more than one batch. Head is the Offset == 0 special case and stays its own node because limit pushdown recognises it structurally.

A negative Len means "to the end", which is how a caller says "drop the first n rows" without knowing the height.

func (s *Slice) Children() []Node

func (s *Slice) Label() string

func (s *Slice) Schema() (*dtype.Schema, error)

func (s *Slice) WithChildren(kids []Node) Node

type Sort ¶

type Sort struct {
	Input Node
	Keys  []SortKey
	// Limit > 0 means only the first Limit rows are needed, which turns a full
	// sort into a bounded top-k. Set by the limit-pushdown rule.
	Limit int
}

Sort orders rows.

This is a PIPELINE BREAKER: it must see every input row before it can emit the first output row. It is therefore an Operator rather than a BatchOp, and it is where memory pressure first becomes real — which is why the streaming engine's external merge sort has this node as its target.

func (s *Sort) Children() []Node

func (s *Sort) Label() string

func (s *Sort) Schema() (*dtype.Schema, error)

func (s *Sort) WithChildren(kids []Node) Node

func (s *Sort) WithLimit(n int) *Sort

type SortKey ¶

type SortKey = expr.OrderKey

SortKey is one component of an ordering.

An alias rather than a second declaration: a window carries its own ordering and internal/expr may not import internal/plan, so the type has to live at the lower level. Two structurally identical types would be two places for the null-placement rule to drift apart.

type Source ¶

type Source interface {
	// Name identifies the source in Explain output, e.g. "parquet" or "memory".
	Name() string

	// Describe is a short human-readable detail line, e.g. a path or a row count.
	Describe() string

	// Schema returns the full schema of the source, before any projection.
	Schema(ctx context.Context) (*dtype.Schema, error)

	// Caps reports which pushdowns the source can honour itself.
	Caps() Caps
}

Source is a thing a Scan can read from.

This is ursus's TableProvider equivalent, and it is public from the start because "plug in your own source" is a first-class use case, not an afterthought — an engine whose only inputs are the file formats its authors happened to implement is much less useful than one you can point at your own storage.

Note Schema takes a context: resolving a Parquet footer or inferring a CSV schema is real I/O, and a schema request that cannot be cancelled would be a hole in the cancellation story.

type Tail ¶

type Tail struct {
	Input   Node
	N       int
	Limited bool
	Len     int
}

Tail keeps the last N rows.

Why it is not a Slice with a negative offset ¶

Slice can stream because it knows where to start. Tail cannot: which rows are the last N is unknown until the input ends. It holds a ring of the most recent N rows — O(N) memory, not O(input), so it is bounded but not free, and it is the only operator here that buffers.

A slice from the end (step 291) ¶

With Limited it keeps only the first Len of those rows, fewer by as many as the input falls short of N: Polars' slice(-N, Len), rows [height-N, height-N+Len) of the input, clipped to it. So of six rows, N 7 and Len 2 keep row 0 alone, as the window starts a row before the input does.

func (t *Tail) Children() []Node

func (t *Tail) Label() string

func (t *Tail) Schema() (*dtype.Schema, error)

func (t *Tail) WithChildren(kids []Node) Node

type TemporalGroup ¶

type TemporalGroup struct {
	Input Node

	// Index is the temporal column the windows are cut from. It must resolve to a
	// Date or Datetime, and the operator verifies at run time that it arrives sorted.
	Index expr.Node

	// Keys are extra CATEGORICAL partitions — DynamicOptions.GroupBy. Windows are cut
	// independently inside each one, so a per-service hourly rollup is one node.
	Keys []expr.Node
	Aggs []expr.Node

	// Rolling picks the window generator: false is the grid, true is one per row.
	Rolling bool

	Every, Period, Offset dtype.Interval
	Closed                expr.Closed

	// A dynamic group's options, as Polars' group_by_dynamic's (step 187):
	// WindowLabel is "left", the window's start and the default, "right", its end,
	// or "datapoint", its first row's instant; StartBy is "window", the grid and the
	// default, "datapoint", the first row, or a weekday, which a weekly grid starts
	// on; Boundaries adds _lower_boundary and _upper_boundary before the index.
	WindowLabel string
	StartBy     string
	Boundaries  bool

	// RowOrder answers a keyed rolling group's windows in their rows' order, not a
	// bucket at a time: an expression's rolling over a partition, mapped back onto
	// the frame's rows (step 337). A rolling window is made as its row arrives, so
	// its number is its row's place.
	RowOrder bool
}

TemporalGroup is GroupByDynamic and Rolling, which are one node because they are one algorithm with two window generators.

Both reduce to "aggregate a RANGE of rows" ¶

The naive reading is alarming: one row can belong to several windows, and every aggregate operator here indexes group state by row. But both operators require the index column SORTED, and that changes the shape completely —

If rows are ordered by the index, every temporal window covers a CONTIGUOUS RUN
of rows. A window is not a set of row ids; it is a pair (lo, hi).

— which is what lets one mechanism serve both, and lets both reuse every existing accumulator unchanged. All nineteen aggregates work in a temporal window on the day this node lands, including the two that refuse to spill, because nothing about kernel.Accumulator moves.

Where they differ ¶

GroupByDynamic  windows come from a GRID: offset + k*every, each period long.
                They exist even when no row falls in them, which is the whole
                difference from GroupBy(truncate(ts, every)) and the reason a
                gap in a time series shows up as a zero rather than as nothing.

Rolling         one window per ROW, ending at that row's own timestamp and
                reaching back by period. Output height equals input height.

It is a pipeline breaker, and the Explain sketch in the API doc is aspirational ¶

ursus-api.md shows GROUP_BY_DYNAMIC as `streaming: yes`, which is achievable on a sorted index — a window can be emitted as soon as the input passes its end. This implementation buffers instead, because the grid's extent is derived from the observed [min, max] and because that is what makes empty windows fall out for free. The cost is O(rows), the same as windowSink's and for the same reason.

func (t *TemporalGroup) Children() []Node

func (t *TemporalGroup) Label() string

func (t *TemporalGroup) Schema() (*dtype.Schema, error)

func (t *TemporalGroup) WithChildren(kids []Node) Node

type Union ¶

type Union struct {
	Inputs []Node
	Mode   ConcatMode
}

Union stacks frames vertically — the first n-ary node in the plan.

Arity was the cheap part; reconciliation is the cost ¶

Join's doc records that adding the first TWO-child node cost almost nothing in traversal — "the generic traversals were already written N-ary and need nothing" — and everything in SIDEDNESS. A Union has no sides: every child produces the same output, so none of Join's layout, suffixing or per-side pushdown machinery has an analogue here.

What it has instead is a schema that is a function of ALL its children jointly, where every other node's is a function of one.

Strict is not schema equality ¶

dtype.Field compares by struct equality, and that includes Nullable — which is "a static property of the schema, not a count of nulls actually present". So two frames differing only in a nullability flag are NOT Equal, and refusing to concatenate them would be absurd: it is the ordinary result of filtering one of them. Strict therefore means "the same columns in the same order", with types promoted and nullability unioned.

The schema is never cached ¶

Deliberately, for the reason JoinLayout gives: projection pushdown narrows a child through WithChildren, and a cached reconciliation would go stale exactly then.

func (u *Union) Children() []Node

func (u *Union) Label() string

func (u *Union) Schema() (*dtype.Schema, error)

func (u *Union) WithChildren(kids []Node) Node

type Unnest ¶ added in v0.3.0

type Unnest struct {
	Input   Node
	Columns []string
}

Unnest replaces a struct column with its fields.

It is to Struct what Explode is to List: the operation after which the nested column is gone and every kernel, aggregate, join and sort that already exists applies to what was inside it. Nothing else has to be built first.

id | person                  ->   id | age  | city
 1 | {age: 30, city: "NY"}         1 | 30   | "NY"
 2 | {age: null, city: null}       2 | null | null
 3 | null                          3 | null | null

It is simpler than Explode in three ways ¶

The row count does not change, so there is no gather. There is no zip, so unnesting several columns needs no agreement between them. And what it changes is only the schema — the fields already have the right length, because a struct's fields are parallel to it rather than indexed by it.

Rows 2 and 3 come out the same, and that is the erasure ¶

A present struct holding nulls and an absent struct produce identical output, in the same way explode collapses an empty list into a null one. The distinction belongs to the struct, and unnest is what consumes the struct. Before it, `IsNull()` tells them apart; after it, nothing can.

func (u *Unnest) Children() []Node

func (u *Unnest) Label() string

func (u *Unnest) Schema() (*dtype.Schema, error)

func (u *Unnest) WithChildren(kids []Node) Node

type Unpivot ¶ added in v0.3.0

type Unpivot struct {
	Input Node

	// On is the value columns, melted into the variable/value pair. Empty melts
	// nothing.
	On []string

	// Index is the columns carried through unchanged. Empty means every column
	// that is not in On, computed against the input schema.
	Index []string

	// VariableName and ValueName are the two invented columns. "" means the
	// defaults above, so the zero value is the ordinary behaviour.
	VariableName string
	ValueName    string
}

Unpivot turns several value columns into two: which column, and what it held.

id  jan  feb            id  variable  value
1   10   20     ->      1   jan       10
2   30   40             1   feb       20
                        2   jan       30
                        2   feb       40

Row-major, which is NOT Polars' order ¶

Polars stacks k frames vertically, so it emits every row's `jan`, then every row's `feb`. This emits every variable for row 0, then row 1.

The reason is batch-size invariance. This is a BatchOp — one batch in, one batch out — so a vertical stack would give batch 1's `jan`s, then batch 1's `feb`s, then batch 2's `jan`s: the row ORDER would depend on the batch size, which is a property of how the query ran rather than of what it asked for. Row-major is the order a streaming operator can produce, and it is the same order at every batch size.

The alternative was to desugar into Union{Project, Project, ...}, one arm per value column, which gives Polars' order and gets projection pushdown for free. It is wrong here for a reason that has nothing to do with order: all k arms share one input subtree, the physical planner has no memoisation and there is no CTE node, so the input would be SCANNED K TIMES. Twelve month columns would read the file twelve times.

Index defaults to the rest, and so, before it reaches here, does On ¶

Unnest refuses to default its column list because "naming them keeps the frame's width a property of the query rather than of whatever the file happens to contain". The same argument would apply to defaulting On — an added source column would silently start being melted. It does not apply to Index: an added column is KEPT, which is what anyone would want. So On was required and Index was not.

Polars' on=None melts every column not in the index, and since step 304 the root package's Unpivot does too, writing On out against the schema when it is called: the node still names what it melts, which projection pushdown keeps in full. On may be empty when Index names every column: nothing is melted, no row comes out, and the value column is of the Null type, as Polars answers.

func (u *Unpivot) Children() []Node

func (u *Unpivot) IndexColumns(in *dtype.Schema) []string

func (u *Unpivot) Label() string

func (u *Unpivot) Schema() (*dtype.Schema, error)

func (u *Unpivot) WithChildren(kids []Node) Node

type Window ¶

type Window struct {
	Input Node

	// Exprs are the windows to compute. Every one is an *expr.Window wrapped in an
	// *expr.Alias naming its temporary, which is what lets Schema resolve them
	// through the ordinary path.
	Exprs []expr.Node
}

Window computes windowed expressions and APPENDS them to its input's schema.

Why it is a node at all ¶

A user never writes one. `Select(Col("x").Mean().Over(Col("g")))` mentions no window operator, the way `GroupBy(k).Agg(...)` mentions an aggregation — so the node is synthesised during Resolve, spliced beneath the Project or WithColumns whose expressions contained windows, with each window subtree replaced by a reference to a `__winN` temporary.

The alternative was to extract windows in the PHYSICAL planner, the way extractAggs pulls aggregates out of an Aggregate's expressions. That works and costs two things worth more than it saves: Explain would not show that a window is being computed, and the optimizer could not see it — which matters because a window is a predicate-pushdown barrier and a rule cannot refuse to cross a node it cannot observe.

It appends rather than replaces ¶

Output is the input schema plus one field per expression. That is what makes the Project above it work: it evaluates over the original columns and the temporaries side by side, so `Col("x").Sub(Col("x").Mean().Over(g))` needs no special case — the subtraction is ordinary arithmetic over two ordinary columns.

func (w *Window) Children() []Node

func (w *Window) Label() string

func (w *Window) Schema() (*dtype.Schema, error)

func (w *Window) WithChildren(kids []Node) Node

type WithColumns ¶

type WithColumns struct {
	Input Node
	Exprs []expr.Node
}

WithColumns adds or replaces columns, keeping everything else.

It is distinct from Project rather than sugar over `Project(All(), newcols...)` because the replace-in-place semantics matter: recomputing an existing column must leave it in its original position, not move it to the end. Users notice column order, and a rewrite that reshuffles it on every recomputation is endlessly annoying.

func (w *WithColumns) Children() []Node

func (w *WithColumns) Label() string

func (w *WithColumns) Schema() (*dtype.Schema, error)

func (w *WithColumns) WithChildren(kids []Node) Node