Vectorized execution — process batches, not tuples

Pulling one row at a time through a chain of virtual function calls (Volcano) is interpreter overhead; processing 8192 column values per call lets the compiler emit SIMD inner loops and amortizes dispatch cost across the batch.

Previously

The bytes on disk are now tiny. But pulling tiny bytes through the CPU one row at a time still leaves a 50x performance win on the table — it depends on how the executor walks those bytes.

Scene 04

Vectorized execution: process batches, not tuples

Watch
Try it
Predict
Capture

What to watch for

Same query on both panels: scan a column, filter, aggregate over 1M rows. The top panel walks one tuple at a time; the bottom panel walks 8192-row batches. Watch the race bar — and the virtual-call counter on each side.

Implementation

Highlighted lines are the ones running in the diagram right now.

Volcano.executeQuery()

tuple-at-a-time: one virtual next() per row per operator

1def execute(plan):
2    op = plan.root          # Aggregate -> Filter -> Scan
3    while True:
4        row = op.next()     # virtual dispatch, every row
5        if row is EOF:
6            break
7        # 3M virtual calls for 1M rows (3 operators deep)
8        # SIMD lanes idle — no contiguous array to vectorize
9        accumulate(row)

Vectorized.executeQuery()

batch-at-a-time: one dispatch per 8192 values

1def execute(plan):
2    op = plan.root          # operators consume + produce Blocks
3    while True:
4        block = op.nextBlock()   # 8192 column values per call
5        if block is EOF:
6            break
7        # one virtual call per BATCH, not per row
8        # block.col is a contiguous array -> SIMD kernel
9        accumulateBlock(block)

Filter.apply(block)

the SIMD kernel — or the per-row escape hatch

1def apply(block):
2    if predicate.isNativeKernel():
3        # tight loop -> AVX2 (8 int32) / AVX-512 (16)
4        for i in range(block.n):
5            out[i] = block.col[i] > threshold
6        return block.select(out)
7    # opaque UDF: planner can't prove what it does
8    for i in range(block.n):
9        out[i] = python_udf(block.col[i])  # FFI per row
10    return block.select(out)

Sources

Where this sits in Build a columnar OLAP store (ClickHouse / Druid style)

Scene 04 of 13, in the Speedups act — Compression and vectorized execution — where the orders of magnitude live.. Tuple-at-a-time Volcano is interpreter overhead; processing 1024–8192 column values per call lets the CPU emit SIMD inner loops.

Up next. Vectorized execution wants thousands of values per call. That sets a hard rule for writes too — they have to arrive in batches, not one row at a time, or the per-column overhead crushes the engine.

All 13 scenes in Build a columnar OLAP store (ClickHouse / Druid style) · Every curriculum

Built with Arqly

Every scene in Build a columnar OLAP store (ClickHouse / Druid style) builds on the one before it.All 13 Build a columnar OLAP store (ClickHouse / Druid style) scenes