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. Zero means unbounded.
	Tolerance dtype.Interval

	// 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 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 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
)

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
}

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 }

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.

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

	// MaintainOrder keeps an inner join's rows in the left input's order, by
	// keeping the build_side rule from exchanging its inputs. Every other kind
	// keeps its order regardless.
	MaintainOrder bool

	// 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 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 Resolve(ctx context.Context, n Node) (Node, error)

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 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. 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 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
}

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.

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
}

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. Required.
	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 Unnest's rule does not apply ¶

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 is required and Index is not.

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