ch06Expressions and vectorised kernels

What you build: An expression tree evaluated a row at a time and a batch at a time, a model of branch prediction and of vector lanes, and a filter kernel with no branch on the data.

The question#

What does it cost to compute an expression for every row, and why do engines work a batch at a time?

Part II made your engine read less. What it does read, it has to compute. Every condition in a WHERE and every column in a SELECT is evaluated for every row that reaches it, and from ch01 on, your operators have done that with kernels from pyarrow.compute, a whole column at once, without asking what the alternative would cost. This chapter builds the alternative, a row at a time, and counts the difference in the two places it shows: the work of deciding what to run, and the work the processor does for each value.

Observe#

The query computes a price with tax on the orders whose unit price is over a hundred, and whose quantity is over two, written clumsily on purpose:

-- ch06, Expressions and vectorised kernels: expressions a planner rewrites
-- before it runs them. A product of constants, a sum it can move to the other
-- side, and a division it cannot.
SELECT order_id, amount * (1 + 20 / 100) AS with_tax
FROM 'fixtures/orders-sorted.parquet'
WHERE amount / quantity > 50 * 2
  AND quantity + 1 > 3;

DuckDB’s plan, from EXPLAIN:

┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│          order_id         │
│          with_tax         │
│                           │
│         ~800 Rows         │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│  ((amount / CAST(quantity │
│    AS DOUBLE)) > 100.0)   │
│                           │
│         ~800 Rows         │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│       PARQUET_SCAN        │
│    ────────────────────   │
│         Function:         │
│        PARQUET_SCAN       │
│                           │
│        Projections:       │
│           amount          │
│          quantity         │
│          order_id         │
│                           │
│          Filters:         │
│ quantity>2 AND quantity IS│
│          NOT NULL         │
│                           │
│         ~4000 Rows        │
└───────────────────────────┘

1. DuckDB computed the constants before it ran anything. The query says 50 * 2; the filter says 100.0. Working out every part of an expression that depends on no column, once, when the query is planned, is constant folding.
2. It moved a sum to the other side. quantity + 1 > 3 became quantity > 2, a comparison of a column with a constant, and so a test the scan can push down, as in ch03.
3. It made the types explicit. amount / quantity became amount / CAST(quantity AS DOUBLE): dividing always gives a double, so the whole number is converted first.

Each condition and each computed column is an expression tree: the leaves are columns and constants, and each inner node is an operator applied to the values of the nodes below it. DuckDB rewrote the trees, then ran what was left, a few thousand values at a time.

Predict, then measure#

A filter must decide, for every row, whether to keep it. Code that decides does so with a branch: an if that jumps one way or the other. A processor does not wait to learn which way a branch goes. It keeps a branch predictor, which guesses from the way the branch went before, and starts on the guessed path at once. A right guess costs nothing. A wrong guess, a misprediction, throws away the work started on the wrong path. The book’s model of a predictor keeps a two-bit counter for each branch, which moves towards “taken” each time the branch is taken and back each time it is not.

Your engine can find the rows that pass a test in two ways. With a branch, it asks if of each value and appends the position when the test passes. Without one, it writes every position to the next free slot and moves the slot on by the test’s result, one or nought, so the value decides what is kept and never which instruction runs next.

Predict the mispredictions of three cases on the orders in date order. First, a test on the date that keeps the first half of the year, with a branch. Second, a test on the amount that keeps about half the rows, scattered at random through the file, with a branch. Third, the same test without one.

The panel draws what your engine and the model counted when the book was built. Its button runs the same kernels again in your browser.

• The same test, run the same way, is cheap on a run and dear at random. On the date, the branch went one way for half the file and the other way for the rest, and the predictor was wrong only where it turned. On the amount, the branch went either way at random, and the predictor was wrong about half the time.
• Without a branch, the data cannot fool the predictor. Only the loop’s own branch is left, and it goes the same way every time but the last.
• The worst case is a test that keeps about half. The curve under the cases runs the random test at thresholds from nearly every row to none. A test that keeps almost everything or almost nothing is predicted well with a branch, because it nearly always goes the same way.

The model counts wrong guesses. Your processor pays for them in time. The panel below keeps the values over fifty from a million, stored once in order and once shuffled: first with pyarrow’s filter, then with DuckDB. pyarrow’s filter takes a run of kept or dropped values a machine word at a time, and decides value by value, with a branch, only where the two mix. DuckDB’s comparison kernels have no branch on the data. The test is written v + 0 > 50 so that DuckDB tests every value; a bare v > 50 would let it skip the sorted table’s row groups by their bounds, as ch04’s scan does, and the timing would be of that.

• pyarrow is several times slower on the shuffled values. The same values, the same test, the same values kept: only the order differs. Sorted, the kept values are one run, taken a word at a time. Shuffled, they mix everywhere, and every value is a decision the processor guesses wrong about half the time.
• DuckDB takes about the same time on both. Its kernel writes every position and moves on by the result, as your kernel without a branch does, so the order of the values cannot fool the predictor. Press the button again: the gap between its two moves from run to run, and is noise.

Building it#

The tree#

An expression is one of three things: a column, a constant, or an operator applied to other expressions. Your engine has no parser yet, so the plan writes the trees out:

# An expression is a tree of three kinds of node. Frozen, so a tree can be shared and compared.

@dataclass(frozen=True)
class Column:
    """A column of the batch, by name."""

    name: str

    def __str__(self) -> str:
        return self.name

@dataclass(frozen=True)
class Literal:
    """A constant, the same for every row."""

    value: object

    def __str__(self) -> str:
        return repr(self.value)

@dataclass(frozen=True)
class Call:
    """An operator applied to the values of its arguments, each an expression itself."""

    op: str
    args: tuple[Expression, ...]

    def __str__(self) -> str:
        if len(self.args) == 2:
            return f"({self.args[0]} {self.op} {self.args[1]})"
        return f"{self.op}({', '.join(map(str, self.args))})"

Expression = Column | Literal | Call

A row at a time#

The obvious evaluator walks the tree for each row: look at the node, decide what it is, compute its arguments, apply its operator to one value. Every decision is made again for every row:

def evaluate_row(expr: Expression, row: dict, counts: Counts | None = None, unit: VectorUnit | None = None):
    """The expression's value for one row, given as a dict of the row's columns: each node is
    visited once for this row alone."""
    if counts is not None:
        counts.dispatches += 1
    match expr:
        case Column(name):
            return row[name]
        case Literal(value):
            return value
        case Call(op, args):
            values = [evaluate_row(a, row, counts, unit) for a in args]
            if unit is not None:
                unit.run(1)
            return SCALARS[op](*values)
    raise TypeError(f"not an expression: {expr!r}")

A batch at a time#

The evaluator your engine uses walks the tree once per batch instead. At each operator node it calls a kernel, which applies the operator to every value of the batch in a loop compiled ahead of time, with no decision about the tree inside it. Evaluating a batch at a time is vectorised execution:

def evaluate(
    expr: Expression, batch: pa.RecordBatch, counts: Counts | None = None, unit: VectorUnit | None = None
):
    """The expression's value for every row of ``batch``, a batch at a time: each node is visited
    once, and each operator runs as one kernel over the whole batch."""
    if counts is not None:
        counts.dispatches += 1
    match expr:
        case Column(name):
            return batch.column(name)
        case Literal(value):
            return pa.scalar(value)
        case Call(op, args):
            values = [evaluate(a, batch, counts, unit) for a in args]
            if unit is not None:
                unit.run(batch.num_rows)
            return KERNELS[op](*values)
    raise TypeError(f"not an expression: {expr!r}")

Both evaluators count dispatches, the nodes they visit. Given a vector unit, both also count the instructions their operators would run. A processor’s vector instructions, SIMD (single instruction, multiple data), apply one operation to several values at once, one in each lane of a wide register. A kernel over a whole array fills every lane; code that computes one value at a time uses one lane and leaves the others idle:

class VectorUnit:
    """Instructions of ``lanes`` lanes: one instruction computes up to ``lanes`` values."""

    lanes: int = LANES
    instructions: int = 0
    """Instructions run."""
    values: int = 0
    """Values computed: the lanes that did useful work."""

    def run(self, values: int) -> None:
        """Apply one operation to ``values`` values: as many instructions as it takes to cover
        them, the last one perhaps part full."""
        self.instructions += -(-values // self.lanes)
        self.values += values

    def counters(self) -> dict[str, int]:
        return {
            "instructions": self.instructions,
            "lanes_used": self.values,
            "lanes": self.instructions * self.lanes,
        }

The query’s two trees, evaluated over the orders a row at a time and in batches of several sizes:

• A row at a time, the evaluator decides far more often than it computes. It visits every node of both trees for every row, constants included.
• Batches divide the decisions by their size. A batch of a few thousand rows makes one decision per node for all of them.
• Batches fill the lanes. One value at a time uses one lane of each instruction. Even small batches use nearly every lane, and the instructions fall by the number of lanes.
• Past a few thousand rows, larger batches save almost nothing more. The decisions are already few.

Time the same evaluations, a row at a time and in batches of three sizes:

• Time follows the decisions. A row at a time is the slowest by far, and each larger batch is faster, for the same rows kept and the same prices computed.
• In Python a decision is dear. Each is a function call of the interpreter’s, so the gap between a row and a batch at a time is wider here than in a compiled engine, where a decision costs a few cycles. The counters give the ratio of decisions; the time says what each one costs on this interpreter.

The two kernels#

The predictor the panel ran:

class Predictor:
    """A two-bit saturating counter for each branch in the code, named by the caller."""

    branches: int = 0
    """Branches run."""
    mispredictions: int = 0
    """Branches that went the other way from the counter's guess."""
    state: dict[str, int] = field(default_factory=dict, repr=False)
    """Each branch's counter: 0 and 1 predict not taken, 2 and 3 predict taken."""

    def branch(self, site: str, taken: bool) -> bool:
        """Run the branch ``site`` one way, count whether the guess was wrong, learn, and return
        ``taken``, so the call can sit where the branch's condition would."""
        counter = self.state.get(site, 1)
        self.branches += 1
        if (counter >= 2) != taken:
            self.mispredictions += 1
        self.state[site] = min(3, counter + 1) if taken else max(0, counter - 1)
        return taken

The two ways to find the rows that pass, the second with no branch on the data:

def select_with_branch(values: Sequence, test: Callable[[object], bool], predictor: Predictor) -> list[int]:
    """The positions of the values that pass, found with an ``if``: one branch per value, going
    the way the test went."""
    kept = []
    for i, value in enumerate(values):
        if predictor.branch("the test", test(value)):
            kept.append(i)
        predictor.branch("the loop", i + 1 < len(values))
    return kept

def select_without_branch(
    values: Sequence, test: Callable[[object], bool], predictor: Predictor
) -> list[int]:
    """The positions of the values that pass, found without a branch on the data: every position
    is written to the next free slot, and the slot moves on by the test's result, one or nought.
    Only the loop's own branch is left, and it goes the same way every time but the last."""
    kept = [0] * len(values)
    n = 0
    for i, value in enumerate(values):
        kept[n] = i
        n += int(test(value))
        predictor.branch("the loop", i + 1 < len(values))
    return kept[:n]

Give the kernel without a branch an if of its own, and run the panel’s report on your edit: its mispredictions come back.

The plan#

The plan is chapter 1’s shape: a scan, a filter and a projection. The filter and the projection evaluate the query’s trees exactly as it writes them, because your engine has no planner yet to fold them or move them into the scan:

WITH_TAX_WHERE = Call(
    "and",
    (
        Call(">", (Call("/", (Column("amount"), Column("quantity"))), Call("*", (Literal(50), Literal(2))))),
        Call(">", (Call("+", (Column("quantity"), Literal(1))), Literal(3))),
    ),
)
WITH_TAX = Call("*", (Column("amount"), Call("+", (Literal(1), Call("/", (Literal(20), Literal(100)))))))

def with_tax(root: Path) -> Operator:
    """queries/with_tax.sql, operator by operator, each expression evaluated as a tree a batch at
    a time, as the query writes it: there is no planner yet to rewrite it (ch06)."""
    scan = Scan(root / "fixtures" / "orders-sorted.parquet", ["order_id", "amount", "quantity"])
    kept = Filter(scan, str(WITH_TAX_WHERE), partial(evaluate, WITH_TAX_WHERE))
    return Project(
        kept, {"order_id": partial(evaluate, Column("order_id")), "with_tax": partial(evaluate, WITH_TAX)}
    )

The book’s tests evaluate many random trees both ways and require the same values, and hold the counters to the model’s rules: k nodes over r rows make k times r dispatches a row at a time, and the kernel without a branch mispredicts at most twice.

Compare#

Your plan beside DuckDB’s:

• Both hand up the same rows, with the same prices. Folding 1 + 20 / 100 changes when the constant is computed, not what it is.
• DuckDB’s filter tests fewer rows. It moved quantity > 2 into its scan, so its filter sees only the rows the scan kept. Your filter tests every row with the whole tree, constants and all. Part IV builds the planner that makes these rewrites.
• DuckDB works a vector at a time. Its operators pass vectors of a fixed size, a couple of thousand values, small enough that a vector’s columns stay in the cache between operators, as ch02 measured. Its source shows comparison kernels that find the passing rows as your kernel without a branch does: they write every position and move on by the result.
• DuckDB does not report its dispatches, branches or instructions. Nor does any engine’s profile. The counts are your engine’s and the model’s.

What this cannot tell you#

• What a misprediction costs on another processor. The model counts wrong guesses, not the cycles each one wastes, which depend on the processor. A modern processor loses on the order of a dozen or more cycles to each. The timing above shows what they cost on yours.
• How a real predictor guesses. Real predictors remember the history of many branches together and would learn some patterns the two-bit counter cannot, such as a branch that alternates. Random data fools them all.
• Whether a compiler used vector instructions. The vector unit assumes every kernel fills its lanes. A real kernel does only if the compiler, or its author, made it so; the model gives every value eight bytes, where narrower types would fit more to a register.
• How fast Python is. Your evaluator’s dispatches are Python function calls, far dearer than the virtual calls a compiled engine makes. The counts compare the two ways of evaluating, not your engine with DuckDB.
• What the batch size does to memory. The model gives a batch of every row the fewest decisions. A real engine keeps its batches small enough to stay in the cache, which the evaluator’s counters do not see.

What this means for your design#

• Let the planner fold what it can, and write predicates it can push. quantity > 2 can reach the scan; quantity + 1 > 3 can only if the planner rewrites it. Write the column alone on one side where you can, and check the plan.
• Mind the tests that keep about half at random. A filter on a column in random order, which keeps about half, is the worst case for a branch. Engines avoid it with kernels that do not branch on the data; your own code, in a user-defined function, may not.
• Sort by what you filter on, for the processor too. The same test on sorted data made a run the predictor learned at once. Sorting helped the scan’s statistics in ch03; it helps the filter’s branches as well.
• Prefer engines and functions that work a batch at a time. A user-defined function that receives one row per call brings back the row-at-a-time evaluator, with a decision per row and one lane per instruction. One that receives an Arrow array does not.

Key takeaways#

Problems#

There are three problems. The first two are code with tests; the third is a slow query to diagnose, with no test. Write your answers to the first two in the workbench, and run the graders there. Your answers stay in this browser, and Reset to the stubs starts again.

6.1 Fold the constants. Write fold: the same tree with every part that depends on no column computed once and replaced by a constant, as DuckDB did to 50 * 2. The graders fold the chapter’s trees and many random ones, then evaluate both over the orders and require the same values, and require that no part without a column is left, and that every column stays.

6.2 Always wrong. Write always_wrong: a run of outcomes of one branch that the two-bit predictor gets wrong every time, from whichever of its four states it starts in. The graders run the book’s predictor on your outcomes, from each state, for many lengths.

6.3 Diagnose the slow filter. No test. A colleague finds that the chapter’s random test, amount over its middle value, filters much faster once the orders are sorted by amount, though it keeps the same rows and compares the same values:

Why does the order of the rows change the cost of the same comparisons? What does the kernel without a branch do on each order, and why? The colleague proposes to store the orders by amount from now on. What would that cost the queries of ch03 and ch04, and what would you propose instead? A good answer explains the predictor’s counter on each order, and weighs the filter’s branches against the scan’s statistics.

Where to go next#

• Where vectorised execution comes from. Peter Boncz, Marcin Zukowski and Niels Nes, MonetDB/X100: Hyper-Pipelining Query Execution, CIDR 2005: the paper that introduced evaluating a vector of values per call, and measured what a tuple at a time costs.
• Branches in database kernels. Kenneth Ross, Selection Conditions in Main Memory, ACM TODS 2004: filters with and without branches, and how to choose between them by selectivity.
• Vectorised against compiled. Timo Kersten and others, Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask, VLDB 2018: the other way to remove the decisions, by compiling the whole query, measured against vectors.
• DuckDB’s own kernels. DuckDB’s source, in src/include/duckdb/common/vector_operations/, holds the loops that apply one operator to a vector, and the select loops that write every position and move on by the result.
• Arrow’s kernels. The Arrow compute documentation lists the kernels your engine calls, and how they handle nulls and types.

Built from commit dc21108.