Crate rudb_exec 

Operators, morsels, the scheduler, hash tables, sorting and spilling.

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

This is tier 0 of spec/08-codegen.md section 8.1: a pull based tree of operators, one variant per logical operator the binder can produce, every one of them written the simplest way that is correct. Tier 0 is never removed and never optional, because it is the reference every faster tier is differentially tested against, and a reference that is clever is a reference nobody can read the answer out of when the clever tier disagrees with it.

What pull based means here and what it does not mean

Operator::next returns the next Chunk or None when there are no more. A pipeline of a scan, a filter and a projection is three of those calls deep and nothing is materialized between them. An operator that cannot answer without seeing all of its input, which is the aggregate, the sort, the join build side, the distinct and the set operations, does all of its work on the first call to next and then hands out what it built one chunk at a time. That is what spec/07-execution.md calls a pipeline breaker and it is the boundary the morsel driven scheduler will later cut pipelines at.

What this is not is the scheduler. There is one thread, the morsels a source hands out are all read by it, and the hash join is a nested loop. Every one of those is M1 or later work and every one of them replaces an operator here without changing the tree that builds it, because the thing that builds the tree is build and the thing it builds against is a trait with two methods.

The move to push

The interface every operator ends up behind is in rudb-pipeline, and they moved to it one at a time rather than in one commit. Every one of them is there now. The table scan, the dummy scan, the series, the file scan, the values list and the strategies table are Source implementations, the filter, the projection, the limit and the cross product are Stream implementations, and the sort, the top N, the distinct, the set operations, the aggregate and the join are Sink implementations. All of them take &self and are handed the mutable part separately, so one of them can be instantiated on as many threads as F4 wants without copying its predicate or its key list.

A source is the one of the three that is shared rather than instanced, so the position it is up to is an atomic and a morsel goes to whoever asks for it first. What a morsel covers is each source’s own business: one stored chunk for a table scan, a run of sixteen chunks for a series because those rows are worked out rather than read, and the whole file list for a file scan, since both file readers are a position in a file and cannot be asked for the tenth chunk without having read the nine before it.

What is left of the pull side is the shape of the tree and the adapters that drive it, which is adapt and nothing else.

Being in the shape is not the same as being parallel. The aggregate holds its hash table in the instance, which is where it has to be, and merging two of those tables needs a serialize and a combine per aggregate that nothing implements yet, so a second instance is refused rather than answered wrongly. That is the one place where F4 has work left in an operator rather than in the scheduler.

An operator with two inputs is two pipelines with an edge between them, and the set operation and the join are both built that way. The side that has to finish first ends in a gather::Gather, which holds its rows and does nothing else, and the side that uses it reads them through a handle. That edge is the one the scheduler will read off the plan, and for the join it is where the hash table goes when #62 replaces the nested loop.

The cross product sits on that edge too, and it is the operator that made rudb-pipeline grow a Progress::Again. One of its input chunks becomes as many output chunks as its right side has, which a stream could not say and a sink could only answer by holding the whole product. Its right side is kept as chunks rather than rows, by the other sink in gather, because it replays them as they stand.

A sink finalises into a buffer::Buffered, which is a separate source that reads the finished chunks back out, rather than handing them back from finalize. That split is what makes the parallel read possible later and it costs nothing now.

adapt is the one thing that knows how to put a pushing operator in a pulling tree, and now that every operator has moved it is the whole of the pull side. What it does not do yet is cut the tree into pipelines and hand them to run_serial, which is the next step and the one that deletes this file rather than changing it.

Why a schema per operator

A bound plan refers to columns by ColumnBinding, which is a table index and a position, and a chunk is a row of vectors with no names on it. Something has to turn one into the other, and that something is Schema: it is what an operator says it produces, it carries the binding alongside the name and the type, and Schema::position_of is the whole of expression column resolution. Building it is where the operators agree with the binder about what a table index means, and it is checked rather than assumed, because a schema that is one column out produces a wrong answer instead of an error.

Structs

Prepared

One or more bound expressions, flattened and resolved against a schema.

Schema

One operator’s output columns.

Scratch

The per chunk working space of one Prepared.

Traits

Operator

A source of chunks.

Functions

build

Builds the operator tree for a plan’s root, for a query nothing will stop.

build_measured

Builds the operator tree, reporting what every operator in it did into report.

build_with

Builds the operator tree for a plan’s root, stoppable through this token and held to this budget.

evaluate

Evaluates one expression over a chunk, producing one vector as long as the chunk.

evaluate_all

Evaluates a list of expressions over one chunk.

registries

Every registry in the process, assembled the first time somebody asks.

written

How this bound expression is written in an error message.