Part 7 · Bytecode

Compiling plans to a resumable VM

SQLite doesn't walk a plan tree. It compiles the query into a flat program for a register machine and runs that one instruction at a time. Because all of that machine's state is plain data, you can stop a query anywhere, save it, and pick it up later.

Every executor so far has been a tree of objects. In part 2 each operator had a Next() that called its child's Next(). A row came back up through the stack, and the stack itself held where we were: which outer row the join was on, how far into the inner input it had got, how many rows the limit had already passed. That works, and it's how Postgres runs queries. But part of the query's state lives in the host language's call stack, and you can't hand a call stack to someone else.

This part takes the other path. We compile the physical plan from part 6 into a program for a small virtual machine: a flat list of instructions, a program counter, numbered registers, and a few cursors and ephemeral tables. Then we look at what that buys us: pausing after any instruction, a budget measured in instructions, and snapshots you can write to disk and restore into a different VM.

Reading SQLite's bytecode

Start with the real thing. SQLite's EXPLAIN prints the program it would run. Here is a small aggregate query:

sqlite> create table t(a int, b int);
sqlite> explain select a, sum(b) from t where b > 10 group by a;
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     45    0                    0   Start at 45
1     SorterOpen     1     2     0     k(1,B)         0
2     Integer        0     2     0                    0   r[2]=0; clear abort flag
3     Null           0     5     5                    0   r[5..5]=NULL
4     Gosub          4     41    0                    0
5     OpenRead       0     2     0     2              0   root=2 iDb=0; t
6     Rewind         0     14    0                    0
7       Column         0     1     7                    0   r[7]= cursor 0 column 1
8       Le             8     13    7     BINARY-8       84  if r[7]<=r[8] goto 13
9       Column         0     0     12                   0   r[12]= cursor 0 column 0
10      Column         0     1     13                   0   r[13]= cursor 0 column 1
11      MakeRecord     12    2     7                    0   r[7]=mkrec(r[12..13])
12      SorterInsert   1     7     0                    0   key=r[7]
13    Next           0     7     0                    1
14    OpenPseudo     2     7     2                    0   2 columns in r[7]
15    SorterSort     1     44    0                    0   GROUP BY sort
16      SorterData     1     7     2                    0   r[7]=data
17      Column         2     0     6                    0   r[6]= cursor 2 column 0
18      Compare        5     6     1     k(1,B)         0   r[5] <-> r[6]
19      Jump           20    24    20                   0
20      Move           6     5     1                    0   r[5]=r[6]
21      Gosub          3     34    0                    0   output one row
22      IfPos          2     44    0                    0   if r[2]>0 then r[2]-=0, goto 44; check abort flag
23      Gosub          4     41    0                    0   reset accumulator
24      Column         2     1     14                   0   r[14]=t.b
25      AggStep        0     14    11    sum(1)         1   accum=r[11] step(r[14])
26      If             1     28    0                    0
27      Column         2     0     9                    0   r[9]=t.a
28      Integer        1     1     0                    0   r[1]=1; indicate data in accumulator
29    SorterNext     1     16    0                    0
30    Gosub          3     34    0                    0   output final row
31    Goto           0     44    0                    0
32    Integer        1     2     0                    0   r[2]=1; set abort flag
33    Return         3     0     0                    0
34    IfPos          1     36    0                    0   if r[1]>0 then r[1]-=0, goto 36; Groupby result generator entry point
35    Return         3     0     0                    0
36    AggFinal       11    1     0     sum(1)         0   accum=r[11] N=1
37    Copy           9     15    0                    0   r[15]=r[9]
38    Copy           11    16    0                    0   r[16]=r[11]
39    ResultRow      15    2     0                    0   output=r[15..16]
40    Return         3     0     0                    0   end groupby result generator
41    Null           0     9     11                   0   r[9..11]=NULL
42    Integer        0     1     0                    0   r[1]=0; indicate accumulator empty
43    Return         4     0     0                    0
44    Halt           0     0     0                    0
45    Transaction    0     0     1     0              1   usesStmtJournal=0
46    Integer        10    8     0                    0   r[8]=10
47    Goto           0     1     0                    0

SQLite 3 output, unedited. Each instruction has up to five operands; most are register numbers, cursor numbers, or jump targets.

It looks dense, but it breaks into a few blocks:

addrs	what it is
0, 45–47	Prologue. `Init` jumps to the end, which starts a read transaction, loads the constant `10` into `r8` once, and jumps back to 1. Constants are hoisted out of every loop.
1–4	Setup. Open a sorter (an ephemeral sorted table), clear the abort flag, set "previous group key" `r5` to NULL, call the reset-accumulator subroutine.
5–13	The scan loop. Open cursor 0 on `t`; `Rewind` (jump to 14 if empty); read column `b`; `Le` is the WHERE clause, inverted: if `b <= 10` jump to 13 and skip the row. Otherwise pack `(a, b)` into a record and insert it into the sorter. `Next` jumps back to 7 while rows remain.
14–15	Pipeline break. Sort the sorter. This is the point where every input row must have been seen.
16–29	The group loop. Walk sorted records. `Compare` the current `a` against the previous group key. On a change: emit the previous group (`Gosub 34`) and reset the accumulator (`Gosub 41`). Then `AggStep` adds `b` into `sum`.
30–31	Emit the last group, then halt.
34–40	Output subroutine. If the accumulator has data: finalize `sum`, copy key + sum into contiguous registers 15–16, `ResultRow`.
41–43	Reset subroutine. NULL the accumulator registers, mark it empty.

Three things to notice.

The plan has become control flow. There is no Scan or Aggregate object anywhere. The scan is the loop from 6 to 13, the WHERE clause is a conditional jump, and the GROUP BY is a sort followed by a loop that detects key changes. (SQLite chose a sort-based aggregate here, the "sort aggregate" from part 4, because there's no index on a to deliver rows in order.)
Even the subroutine calls are in registers. Gosub 3 34 stores the return address in r3 and jumps; Return 3 jumps to whatever r3 holds. Nothing lives on the C call stack between instructions.
ResultRow is where the VM yields. When execution reaches address 39, sqlite3_step() saves the program counter (40), points the caller at registers 15–16, and returns SQLITE_ROW. The next call to sqlite3_step() continues the interpreter loop at address 40, with no extra machinery.

Our machine

Our VM is a smaller cousin of SQLite's, with the instruction set from DESIGN.md. Its entire state is:

struct VMState
  pc          int                    -- address of the next instruction
  regs        map[int]Value          -- numbered registers
  cursors     map[int]{table, pos}   -- a cursor over immutable data is just two numbers
  hashTables  map[int]{buckets, seek}   -- ephemeral: join build sides
  aggTables   map[int]{groups, it}      -- ephemeral: GROUP BY accumulators
  halted      bool

Every field is plain data: ints, values, maps of rows. No closures, no iterator objects, no pointers into the host's stack. The interpreter is a loop around a switch:

function step(prog, db, s, fuel) -> (row, status)
  loop
    if s.halted then return (null, Done)
    if fuel == 0 then return (null, OutOfFuel)      -- budget exhausted, state intact
    fuel = fuel - 1
    ins  = prog[s.pc]
    next = s.pc + 1
    match ins.op
      case Column    -> s.regs[ins.p3] = db[cursor.table].rows[cursor.pos][ins.p2]
      case Gt        -> s.regs[ins.p3] = compare3(s.regs[ins.p1], s.regs[ins.p2])
      case IfNot     -> if s.regs[ins.p1] != true then next = ins.p2
      case Next      -> cursor.pos += 1; if cursor.pos < len(rows) then next = ins.p2
      case HashSeek  -> if no bucket for s.regs[ins.p2] then next = ins.p3
      case ResultRow ->
        s.pc = next                                    -- advance first: resume AFTER the yield
        return (s.regs[ins.p1 .. ins.p1+ins.p2), Row)
      case Halt      -> s.halted = true; return (null, Done)
      ...
    s.pc = next

There are two ways out of the loop besides halting: a row is ready, or the fuel ran out. Both leave s in a state that the next step() call continues from. The caller never has to know which instruction the VM was in the middle of. It wasn't in the middle of one, because instructions are atomic.

Compiling a plan: produce and consume

How do you get from a plan tree to a flat program? The trick is Thomas Neumann's produce/consume model (the HyPer paper in the reading list). SQLite's code generator has the same shape, though it doesn't use the names. Each operator gets one compile function:

gen(node, consume)
  -- emit code that produces node's rows, one at a time.
  -- for each row, call consume(regs): a callback that emits the code to run
  -- while that row sits in those registers.

consume is a compile-time callback, not a runtime one. When gen calls it, the parent operator's code is emitted in place, inside the child's loop. The operators nest at compile time so that at run time there's just one flat loop:

gen(Scan(table), consume)
  emit OpenScan c, table
  emit Rewind c, done                   -- empty? skip the loop
  top:
  for each column i: emit Column c, i, r[base+i]
  consume(r[base ..])                   -- parent's code goes HERE, inside the loop
  emit Next c, top
  done:

gen(Filter(pred, child), consume)
  gen(child, regs ->
    r = genExpr(pred, regs)
    emit IfNot r, skip
    consume(regs)                       -- only reached when pred is true
    skip:)

gen(Limit(n, child), consume)
  counter = constReg(n)
  gen(child, regs ->
    consume(regs)
    emit DecrJumpZero counter, halt)    -- n rows out? jump straight to Halt

gen(HashJoin(left, right, lkey, rkey), consume)
  emit HashOpen h
  gen(right, regs ->                    -- build: a complete loop of its own
    emit HashInsert h, genExpr(rkey, regs), regs)
  gen(left, regs ->                     -- probe: runs inside the left loop
    emit HashSeek h, genExpr(lkey, regs), none
    top:
    for each right column i: emit HashColumn h, i, r[base+i]
    consume(regs ++ r[base ..])
    emit HashNext h, top                -- next match for the same probe row
    none:)

gen(Aggregate(keys, aggs, child), consume)
  emit AggOpen a
  gen(child, regs -> emit AggStep a, keyRegs, valRegs)   -- loop 1: accumulate
  emit AggRewind a, done                                  -- pipeline break
  top:
  for each output column i: emit AggColumn a, i, r[base+i]
  consume(r[base ..])                                     -- loop 2: emit groups
  emit AggNext a, top
  done:

Notice the difference between operators. Filter, Project, Limit, and the probe side of a hash join just wrap their parent's code: they pipeline. The hash join's build side and the aggregate are pipeline breakers. They finish one loop, materialize into an ephemeral table, and start a new loop over that table. A compiled query is a sequence of pipelines, each one a tight loop with no function calls inside it.

Pick a query below and click a node to see exactly which instructions it emitted. The Filter is two instructions in the middle of the probe loop (its constant 1 is hoisted into the prologue). The HashJoin is spread across two separate loops.

Compare this with part 2's iterators. In the Volcano model the parent pulls (child.Next()); here the child pushes into its parent's code. Push-based pipelines are what HyPer, Umbra, and DuckDB use. DuckDB pushes vectors through pipelines; HyPer compiles each pipeline to machine code. Our compiler emits bytecode instead, which keeps it small enough to read and step through.

Running it

Here is the compiled program for a join with a filter and a LIMIT, running on the toy dataset. Step 1 executes one instruction. Run to next row keeps going until ResultRow yields. step(fuel) calls the VM with a budget: it returns OutOfFuel as soon as that many instructions have executed, even in the middle of building the hash table.

Then try the important part. Take a Snapshot partway through, run on to the end, then Restore into fresh VM. The restored VM is built from nothing but the JSON you see. It continues exactly where the snapshot was taken and yields the same rows.

One guess before you start:

Things worth watching:

Addresses 2–9 are the build loop: orders go into hash table 0 before a single customer is read. Bo (id = 2) probes and misses, so HashSeek jumps straight to Next.
The filter o.qty > 1 is Gt followed by IfNot. Ada's second order (qty 1) fails it and jumps to HashNext.
After the second row, DecrJumpZero takes the counter in r1 to zero and jumps to Halt. Di is never read. In the iterator model, LIMIT just stops calling Next(); here it's a jump.
In the GROUP BY program, the first loop (AggStep) only accumulates. No row comes out until AggRewind starts the second loop.

Why "state is data" is the whole point

Any executor can pause between rows. Part 2's iterators already do: Next() returns one row, and the caller decides when to ask for the next. The question is what else you can do with a paused query. That depends on where the state lives.

Tree of iterators, paused inside a hash-join build

Limit.Next()
  Project.Next()
    Filter.Next()
      HashJoin.Next()
        buildTable()          ← here
          Scan(orders).Next()

state: 6 host stack frames, locals
       in each, iterator objects
       holding closures

VM, paused at the same moment

{ "pc": 5,
  "regs": {"1":2,"2":12,"3":1,"4":101,
           "5":1,"14":1},
  "cursors": {"0":{"table":"orders",
                   "pos":2}},
  "hashTables": {"0":{"buckets":{
     "1":[[10,1,100,2],[11,1,101,1]]}}},
  "halted": false }

On the left, the query "is" six host stack frames. You can't pause it in the middle of buildTable() without blocking a thread, and you can't move those frames to another process. On the right, the query is a JSON value you could put in a database row.

	pause between rows	pause mid-operator	serialize & resume elsewhere
Materializing tree (sqlglot's executor)	no	no	no
Volcano iterators (part 2)	yes	no: a blocking build runs inside one `Next()`	in principle; state is scattered across objects
Coroutines / Java virtual threads	yes	yes	no: frames aren't data
Bytecode VM	yes	yes, after any instruction	yes: pc + registers + cursors + tables

Virtual threads deserve a closer look, because they're the obvious "just use the host" answer on the JVM. A virtual thread can park anywhere, cheaply, and that covers suspension. But the parked state is a chain of JVM stack frames. You can't write it to disk, send it to another node, or inspect it to see how far along the query is. The VM's state can do all three.

Fuel: budgets you can enforce from inside

Because step() counts instructions, a budget is a number you pass in. A caller can run a query in slices of 10,000 instructions and check a deadline, a cancellation flag, or a memory high-water mark between slices. Cancellation is cooperative by construction: the VM can't be stuck anywhere the check can't reach, because every instruction is a check point.

The alternative is ugly, and you may have met it: an interpreter that can hang inside a single host call, where the only lever is to interrupt the host thread from outside and then throw the whole context away because you can't trust its state afterward. A fuel-driven VM never needs that. Out of fuel is a normal return value, and the state it leaves behind is consistent.

What makes a snapshot hard

Cursors over mutable data. Our cursor is (table, pos) because the toy tables never change. Over a real table, "position 2" means nothing after an insert. You need a snapshot id (MVCC) or an immutable input, such as a CSV upload frozen at upload time.
Large ephemeral state. A snapshot taken mid-build carries the half-built hash table. That's fine for thousands of rows and expensive for millions. The answer is to snapshot at pipeline boundaries when you can, or spill ephemeral tables to storage and snapshot only a reference.
The program must be identical. The snapshot refers to addresses and register numbers, so restoring requires the same compiled program. Store the program, or a hash of the plan and compiler version, next to the state.

sqlglot's executor is roughly the opposite design. It turns each SQL expression into a Python source string and evals it, which is closure compilation for expressions (part 1). But it runs the plan DAG step by step, and each step materializes a whole Table before the next starts. So there's no yield point inside a query at all: execute() returns when everything is done. Its planner steps (Scan, Join, Aggregate, Sort, SetOperation) map almost one-to-one onto our pipelines, though. A compiler like the one above could consume sqlglot's Plan directly.

What it costs

Nothing is free. The VM pays an interpretation tax: a switch dispatch for every instruction, for every row. The join program above spends about a dozen instructions per joined row, nearly all of them shuffling single values between registers. SQLite accepts that because its bottleneck is usually I/O and its priority is size and portability.

Analytical engines answer it in one of two ways:

Vectorize (MonetDB/X100, DuckDB): every operation works on a batch of about 2,048 values, so one dispatch is spread over thousands of rows. A Column fills a vector; Gt produces a selection vector; the loops inside each operation are tight enough for the CPU (or the JVM's JIT) to optimize.
Compile (HyPer, Umbra): generate machine code per pipeline, so there's no dispatch at all. On the JVM this means generating JVM bytecode at runtime, which is what Calcite does with Janino. It's fast, but it puts a code generator and class loader in your query path.

There's a middle ground that keeps everything this post is about: vector registers. Keep the same design (pc, registers, cursors, ephemeral tables, fuel, snapshot), but make each register hold a batch of values instead of one. Column reads 1,024 values, Gt compares them all, IfNot becomes "filter the selection vector", and ResultRow yields a batch. Dispatch cost is divided by the batch size, and the state is still a JSON-able map of registers.

The integrated engine

Everything from the series is in go/engine and clojure/src/engine. SQL text goes through a parser and binder into a logical plan. The part-6 planner reads statistics and picks a join order and algorithms, producing a physical plan. That plan runs on either executor: the iterator tree from parts 2–5, or this part's compiler and VM. The two must agree on every query in queries/golden.sql, and the tests check that they do.

$ go run ./cmd/engine
> \program
> SELECT c.city, count(*) FROM customers c JOIN orders o ON o.customer_id = c.id GROUP BY c.city
  ... the bytecode listing, then the rows ...
> \vm            -- toggle the executor
> \explain on    -- show the physical plan with estimates

go/lesson07/bytecode.go · clojure/src/lesson07/bytecode.clj (ns lesson07.bytecode): the compiler, the VM, and a demo that runs a query in small fuel slices, snapshots mid-flight, restores into a new VM, and checks the results match. Run with go run ./cmd/lesson07 or clojure -M -m lesson07.bytecode. The full engine: go run ./cmd/engine -vm or clojure -M -m engine.main --vm.

Or run it right here: open the terminal (the Go demo, compiled to WebAssembly).

Write the machine and the compiler: the fetch/dispatch loop with fuel, ResultRow's yield-and-resume, and the produce/consume code generation for a Filter and a nested-loop join. The exercise track for this part (vm-step-loop, compile-filter, compile-nl-join, plus vm-cursor-ops in Go and vm-result-row in Clojure) strips those function bodies out of the lesson and leaves the tests. Fill them in until the tests pass:

cd go && go test ./exercises/lesson07/
cd clojure && clojure -M:ex -d ex -n exercises.lesson07.bytecode-test

Hints and the full list are in the exercises page.

A query is resumable when its state is data rather than a call stack. Compiling the plan into flat bytecode is one clean way to get there: the plan becomes loops and jumps, pipeline breakers become ephemeral tables, ResultRow becomes a return, and pc + registers + cursors + tables is everything you need to stop, save, budget, and resume.