Tiny VM ISA

DistributedBytecode VMReference

Beta Works · surface still evolving · the ISA is stable within wire v17; new opcodes require a wire version bump, and every one so far has had one

The instruction word

One instruction is one little-endian 64-bit word, byte-identical to the wire crate’s Instruction { opcode, flags, reg_a, reg_b, imm }, so a frame’s instruction block is cast straight into the VM’s code slice — there is no decode step.

bits  0..8   opcode
bits  8..16  flags
bits 16..24  reg_a      (destination / first operand)
bits 24..32  reg_b      (second operand)
bits 32..64  imm        (column index, literal, jump delta, slot, or packed operands)

Two-address form: an ALU op writes its result into reg_a. Jumps are relative to the current program counter. Falling off the end of the code ends the row.

Registers and state

• 256 general registers, 64 bits each, persisting across rows of one block. Programs use the low registers as an expression stack; accumulators are reserved from the top (255 downwards).
• A NULL byte per register: a register holding NULL always holds 0 as well. That single invariant keeps the jumps NULL-free — JMP_FALSE fires on NULL because the value is 0 — while the value ops need one test so that NULL = NULL does not compute to 1.
• Per-column packed cursors for nullable columns (below).
• Join state: a per-row composite-hash accumulator, the current match record, and a resume index into a 1:N match list.

Opcodes

Opcode	Code	Form	Semantics
HALT	0x00	—	End the row.
LOAD_COL	0x01	a, imm=col	a ← column col at the current row. With NULLABLE, through the rank dictionary; a NULL row loads 0 and marks a NULL.
LOAD_IMM	0x02	a, imm	a ← sign-extended 32-bit literal.
ADD	0x10	a, b	a += b (wrapping).
SUB	0x11	a, b	a -= b (wrapping).
MUL	0x12	a, b	a *= b (wrapping).
DIV	0x13	a, b	Signed a /= b. A zero divisor makes a NULL — never a fault.
EQ	0x20	a, b	a ← 1 if equal, else 0.
GT	0x21	a, b	a ← 1 if a > b (signed). < is a swapped GT.
NOT	0x22	a	a ← 1 if a == 0. !=, <=, >= are EQ/GT plus NOT.
JMP_FALSE	0x30	a, imm	Jump by imm if a == 0 (or NULL).
JMP_TRUE	0x31	a, imm	Jump by imm if a != 0.
YIELD_MATCH	0x40	—	Emit the current row. With WITH_OFFSETS, its offset is appended to the materialize chunk.
YIELD_COL	0x41	a, imm=slot	Write a into output column slot for this row (slot-major). Must precede the row’s YIELD_MATCH.
ACC_SUM	0x50	acc, b	acc += b unless b is NULL. acc starts NULL.
ACC_COUNT	0x51	acc, b	acc += 1 unless b is NULL. Starts 0.
ACC_MAX	0x52	acc, b	Signed max, NULL-skipping; starts NULL.
ACC_MIN	0x53	acc, b	Signed min, NULL-skipping; starts NULL.
HASH_PROBE	0x60	a, imm	Probe the broadcast table with the row’s composite hash. Hit: a ← build row offset, select match k. Miss: jump by imm.
HASH_ACC	0x61	key, val, imm	Group by key; apply accumulator imm & 0xFF of kind imm >> 8 (0 SUM, 1 COUNT, 2 MAX, 3 MIN) to val. NULL keys share one group; NULL values are skipped.
HASH_MIX	0x62	a	Fold a into the row’s composite hash. A NULL component poisons the hash so the probe misses.
LOAD_BUILD	0x63	a, imm=col	a ← embedded column col of the current match record, NULL per its validity mask.
HASH_PROBE_OUTER	0x64	a, imm	As HASH_PROBE on a hit. On a miss, NULL-extend a and every later LOAD_BUILD, then jump by imm — to the materialisation phase. LEFT JOIN.

Flags

Flag	Bit	On	Meaning
NULL_IS_FALSE	0	comparisons	Reserved: a NULL operand makes the comparison false rather than NULL.
UNSIGNED	1	comparisons	Reserved: unsigned ordering.
NULLABLE	2	LOAD_COL	The column’s stripe is packed; address it through the null bitmap and rank dictionary.
WITH_OFFSETS	3	YIELD_MATCH	Append each yielded row’s offset to the materialize chunk (a join’s build input).

The packed-stripe trap and the rank dictionary

Fixed-width .acf stripes are packed: a NULL row occupies zero bytes. Reading data[row * 8] on a column with NULLs mis-keys every row after the first NULL and still returns plausible integers — nothing fails loudly. So:

• A nullable column travels to the VM as stripe + null bitmap + RankDictionary. The packed index of a row is the bitmap’s rank (the number of valid rows before it), answered in O(1).
• Rows are visited in order, so most lookups are row == last + 1: one bit test advances a per-column cursor. Any other row — the first, or a resume after a chunk flush — seeks through the dictionary once.
• The safety valve: VmState::new refuses a program that reads a bitmapped column without NULLABLE. The worker answers EXEC_ABORT. This is tested by compiling the same query with the column declared dense and asserting the refusal.

Program shape and the four loops

Before the row loop starts, the VM reads the program once (Shape::of) and picks one of four loops, each holding only the arms it can execute:

Loop	Chosen when	Arms
Filter	no yields of columns, no accumulators, no probe	conditionals, jumps, YIELD_MATCH
Materialize	YIELD_COL present	Filter + YIELD_COL
Aggregate	ACC_* or HASH_ACC present	conditionals + accumulators + group table
Join	HASH_PROBE / HASH_PROBE_OUTER present	Materialize + HASH_MIX, probes, LOAD_BUILD

Each loop is also monomorphised on nullability. A dense program runs with no NULL bookkeeping at all; a program with a nullable column, a DIV, or a join runs the NULL-tracking instantiation. The common arms are duplicated across the four loops on purpose: a shared helper is one function again, which is what spilled registers.

Shape::of refuses programs that mix an aggregate with a row yield, mix plain and grouped accumulators, exceed 16 output slots or 16 accumulators, or use join ops without a probe.

Yielding, chunking and resuming

The caller owns every output buffer. execute_into(start, matches, cells, valid) runs rows [start, row_count) and stops when the chunk fills, reporting the row to resume from. The worker flushes the chunk and calls again — that is the whole streaming mechanism, and it needs no buffer larger than one chunk however many rows the answer has.

• Offsets: 4,092 per chunk (4,092 × 16 B + 64 B header fills the 64 KiB ring exactly).
• Cells: the row cap is derived from the ring for the program’s slot count.
• Aggregates never truncate; a full group table stops with bad_opcode = HASH_ACC and the worker refuses rather than merging groups.
• A YIELD_COL on a full buffer truncates at the row start, so the row is re-run whole on resume.

1:N joins and the mini-cursor

A key with N build rows yields N pairs. On a hit the probe selects match k; if k + 1 < count, the row is re-run from pc = 0 with k + 1 before the outer loop advances. The re-run is reached both by falling off the end and by a skip jump, so a pair filtered out by a post-probe conjunct still advances the list. A chunk cut mid-list stores k in the VM so the resume re-enters the list where it stopped instead of re-emitting pairs. Tested with a three-row list pushed through seven-slot chunks.

Cost

Measure	Value
Dispatch, mock block	0.78–0.98 ns per instruction (build-dependent)
Dense 1 M-row filter, 7.4 M instructions	5.8 ms → 0.78 ns per instruction, 5.8 ns per row
Nullable 1 M-row filter, 4.3 M instructions	4.8 ms → 1.12 ns per instruction
Heap allocations per chunk	0 (asserted with a counting allocator)

Cluster Execution Engine →

Where the VM sits in the orchestrator/worker design.

Bytecode Compiler →

How each SQL shape becomes one of these programs.

Wire Protocol Versions →

The frames that carry programs in and results out.