Why SQLite Uses Bytecode Instead of a Tree of Objects
SQLite's original author explains why it compiles SQL into bytecode instead of walking a tree of objects, and where each approach honestly wins.
We draw query plans as trees, so it’s easy to assume a tree is what a query is. SQLite is the counterexample: it compiles SQL into bytecode and runs the program step by step — and that one choice changes how you explain, debug, pause, size, and parallelize a query.
Source
By: SQLite (D. Richard Hipp)
Type: Engineering article
It’s worth saving because a database engine rarely explains its own internals this openly: written from the perspective of SQLite’s original author, it argues for bytecode over the tree-of-objects design used by MySQL and PostgreSQL — and still spells out the two places where the tree wins.
What compiling SQL to bytecode buys, and what it costs
Every SQL engine does the same two-step dance: translate your SQL text into a prepared statement, then execute that statement to produce rows. A prepared statement is just the SQL rewritten in a form the computer can work with. The interesting decision is what that object looks like inside, and the essay frames it as a choice between the two designs that dominate the field: MySQL and PostgreSQL represent the statement as a tree of objects that the engine executes by walking, while SQLite compiles it into bytecode for a virtual machine.
“Bytecode” here isn’t quite what the Java virtual machine or WebAssembly means by it. Those consist almost entirely of low-level operations — arithmetic, comparisons, conditional jumps, memory moves. SQLite’s bytecode has those too, but it mixes in high-level database primitives: OP_Column extracts a value from the row a cursor points at (a cursor being a pointer into a table’s data or index), OP_SeekGE moves a cursor to the first entry at or above a key, OP_Next advances a cursor and jumps away when the entries run out. The essay’s summary is that this is “a list of database primitives that are to be run in a particular order” — a recipe for a cook who already knows how to sauté.
The tree camp’s structure usually gets called an AST, and the essay spends real care unpicking that label. An abstract syntax tree is what a parser naturally produces from formal text. But before such a tree can execute, symbols must be resolved, semantic rules checked, and optimizations applied — and after those passes the tree resembles the original SQL so little that calling it an AST is, in the author’s words, a misuse of the term. His preferred description is a dataflow program: a directed graph of nodes, each doing one small piece of the computation and handing results onward.
So why pick bytecode? The first advantage is that a flat program is readable. Every SQLite instruction is one opcode plus five operands, so a whole prepared statement renders as a six-column table — which is exactly what prefixing a query with EXPLAIN gives you. A tree of objects has no such consistent shape: the objects differ wildly, any table would need far more than six columns, and the rendering problem is hard enough that, as far as the author knows, no tree-based engine publishes EXPLAIN output at SQLite’s level of detail.
Readability then buys debuggability. Bytecode draws a sharp line between the front end (parsing and analysis) and the back end (storage and evaluation), so when a query returns wrong or slow results, the bytecode tells you which half is misbehaving. Debugging builds of SQLite go further with PRAGMA vdbe_trace=ON, which prints a running trace of the program as it executes.
The advantage I hadn’t considered is incremental execution. A bytecode program can run until it produces its first row, then pause until the application steps it again. Pausing a tree-walk is different: you’d have to unwind the stack back to the caller while saving enough state to resume later, something the author calls “sufficiently difficult that I have never seen it actually done.” Client/server databases never needed this — the server runs each statement to completion and ships back the full reply in one go. But SQLite is a library running in the application’s address space, sharing its stack, so a query that yields row by row isn’t a nicety; it’s how the C API’s sqlite3_step() model works at all.
Then there’s size. During preparation both the AST and the bytecode exist in memory simultaneously, but the AST is discarded and its memory recycled before sqlite3_prepare() even returns. Since prepared statements are cached and can live a long time while preparation is fleeting, the smaller steady-state footprint is what counts.
Speed comes last, and the honesty here is the essay’s best move. The author believes bytecode runs faster because each step requires fewer decisions — and he immediately flags that word. Nobody has spent the years needed to build equivalent bytecode and tree versions of one engine for a fair comparison, and benchmarks across engines can’t separate query processing from client/server message overhead. It’s a belief, labelled as one.
The essay then gives the tree design its due, which is why I trust the rest of it. Once bytecode is generated, the algorithm is fixed; changing it means generating a new program. A tree-of-objects plan is mutable, so a query can re-tune itself mid-flight based on its own progress. And dataflow programs parallelize naturally: run each node on its own thread with threadsafe queues between nodes, and no synchronization is needed inside a node. That’s exactly what large analytic workloads (OLAP) on big multi-core servers want. SQLite’s focus is transaction processing (OLTP) on internet-of-things devices — embedded, single-threaded, stop-and-resume — so the two tree advantages are ones it rarely misses.
My take
Read quickly, this looks like a 5–2 victory for bytecode. Read carefully, the scoreboard is an artifact of the deployment model. Two of the five advantages — incremental execution and the long-term memory footprint — only matter because SQLite is a library sharing the host’s stack instead of a server that finishes statements before replying. Swap in a big parallel analytic server and the two advantages trees keep, runtime replanning and easy parallelism, become the ones that dominate. The transferable method isn’t “compile to bytecode”; it’s “pick the internal representation that matches how execution is delivered.” The other thing I didn’t expect is the candour — a performance claim openly labelled a belief models how to write about speed without overclaiming.
Where this is useful
- Reading SQLite
EXPLAINoutput — the listing is a six-column program table, not a tree, and it becomes followable once you look for the cursor loops. - Deciding between compiling to code and walking objects in your own interpreter, rule engine, or query language.
- Evaluating database-engine debates — this maps which internal choices serve embedded OLTP versus server-side OLAP.
- Less useful for benchmark predictions: the author himself says no fair side-by-side speed comparison exists.
Apply this: Open a SQLite shell, pick a query with a WHERE clause, and run
EXPLAINbefore it. Scan the listing for the open–seek–next pattern that implements your filter — that loop is the bytecode design made visible.
What I want to remember
Remember: SQLite compiles SQL to bytecode because it’s a library that must share the host’s stack — pausing a flat program mid-row is easy, pausing a tree-walk is not. Choose internal representations to match the execution model, not the benchmark.