Table of contents
Open Table of contents
Context
SQLite is the most widely deployed database engine in history. It runs on every smartphone, inside every web browser, in airplanes, cars, and satellites. Unlike client-server databases (MySQL, PostgreSQL), SQLite is an embedded database — it is a C library that links directly into your application. There is no separate server process, no network protocol, no configuration. You call a function, and it reads or writes a single file on disk.
Despite its simplicity from the outside, SQLite’s internals are remarkably well-engineered. A SQL query passes through a compiler frontend (tokenizer, parser, code generator), gets compiled to bytecode, runs on a register-based virtual machine, which talks to a B-tree storage layer, which talks to a pager that manages disk I/O and crash recovery.
How a SQL query travels through SQLite
"SELECT name FROM users WHERE age > 25"
|
v
+------------------+
| Tokenizer | breaks SQL text into tokens
+--------+---------+
|
v
+------------------+
| Parser | builds an abstract syntax tree (AST)
| (Lemon LALR) |
+--------+---------+
|
v
+------------------+
| Code Generator | translates AST into bytecode
+--------+---------+
|
v
+------------------+
| VDBE (Virtual | executes bytecode instructions
| Database | like a small CPU
| Engine) |
+--------+---------+
|
v
+------------------+
| B-Tree Layer | organizes rows in balanced trees
+--------+---------+
|
v
+------------------+
| Pager | reads/writes fixed-size pages
| (page cache) | handles transactions & WAL
+--------+---------+
|
v
+------------------+
| OS Interface | file I/O, locking, mmap
| (VFS) |
+--------+---------+
|
v
[ disk file ]The entire source code is roughly 160,000 lines of C (in the amalgamation build, it ships as one .c file and one .h file). Let’s walk through each layer from top to bottom.
The Compiler Frontend: From SQL Text to Bytecode
Tokenizer
The tokenizer (src/tokenize.c) scans the SQL string character by character and emits tokens. SQLite’s tokenizer is hand-written (not generated by lex/flex) for speed and small binary size.
// Simplified view of the tokenizer loop
int sqlite3GetToken(const unsigned char *z, int *tokenType) {
int i;
switch (*z) {
case ' ': case '\t': case '\n': case '\r': {
// skip whitespace
for (i = 1; z[i] && isspace(z[i]); i++) {}
*tokenType = TK_SPACE;
return i;
}
case '(': { *tokenType = TK_LP; return 1; }
case ')': { *tokenType = TK_RP; return 1; }
case ';': { *tokenType = TK_SEMI; return 1; }
case '+': { *tokenType = TK_PLUS; return 1; }
// ... hundreds more cases for operators, keywords, literals
}
}For our example query SELECT name FROM users WHERE age > 25, the tokenizer produces:
TK_SELECT "SELECT"
TK_ID "name"
TK_FROM "FROM"
TK_ID "users"
TK_WHERE "WHERE"
TK_ID "age"
TK_GT ">"
TK_INTEGER "25"Parser
SQLite’s parser is generated by Lemon, a parser generator written by SQLite’s creator D. Richard Hipp. Lemon is similar to yacc/bison but produces reentrant, thread-safe code with fewer conflicts. The grammar lives in src/parse.y — roughly 1,700 lines that define the entire SQL dialect SQLite supports.
A simplified grammar rule for SELECT:
// From parse.y (simplified)
cmd ::= SELECT selcollist from where_opt groupby_opt having_opt
orderby_opt limit_opt.
selcollist ::= expr(A) as(B). {
A.pList = sqlite3ExprListAppend(pParse, 0, A.pExpr);
}
from ::= FROM seltablist. {
// attach the table list to the Select node
}
where_opt ::= WHERE expr(X). {
// X becomes the WHERE clause expression tree
}The parser builds an internal Select structure — essentially an AST (Abstract Syntax Tree) that represents the query. This structure contains pointers to the column list, the table source, the WHERE expression tree, ORDER BY, GROUP BY, and so on.
Code Generator
The code generator (src/select.c, src/where.c, and others) is the heart of the compiler. It walks the AST and emits bytecode instructions for the VDBE. This is also where the query planner lives — it decides which indexes to use, what join order to pick, and whether to use a covering index or a full table scan.
For our query, the code generator must decide: is there an index on users.age? If yes, use an index seek. If not, do a full table scan and check each row.
You can see the generated bytecode for any query using EXPLAIN:
sqlite> EXPLAIN SELECT name FROM users WHERE age > 25;
addr opcode p1 p2 p3 p4 p5
---- ------------- ---- ---- ---- ------------- --
0 Init 0 12 0 0
1 OpenRead 0 2 0 3 0
2 Rewind 0 10 0 0
3 Column 0 2 0 0
4 Le 1 9 0 collseq(BINARY) 0
5 Column 0 1 0 0
6 ResultRow 0 1 0 0
7 Next 0 3 0 1
8 Goto 0 10 0 0
9 Goto 0 7 0 0
10 Halt 0 0 0 0
11 Integer 25 1 0 0
12 Goto 0 1 0 0Let’s read this like a program:
Bytecode execution flow
Init ──> Goto line 1
|
v
Integer 25 ──> store 25 in register 1
|
v
OpenRead ──> open cursor 0 on the "users" table (B-tree root page 2)
|
v
Rewind ──> move cursor to the first row
| ┌──────────────┐
v | |
Column 0,2 ──> read column 2 (age) | loop body |
| | |
v | |
Le reg1 ──> if age <= 25, skip to Next ──────>| |
| | |
v (age > 25) | |
Column 0,1 ──> read column 1 (name) | |
| | |
v | |
ResultRow ──> emit one result row | |
| | |
v | |
Next ──> advance cursor; if more rows ────────┘
| go back to Column
v (no more rows)
Halt ──> doneThe VDBE: SQLite’s Virtual Machine
The Virtual Database Engine (VDBE) in src/vdbe.c is a register-based virtual machine that executes the bytecode. Think of it as a small CPU with about 190 opcodes, each doing one focused operation: open a table, read a column, compare values, jump to another instruction, insert a row, and so on.
The core execution loop is a giant switch statement:
// Simplified from src/vdbe.c
int sqlite3VdbeExec(Vdbe *p) {
Op *aOp = p->aOp; // array of bytecode instructions
Op *pOp; // current instruction
Mem *aMem = p->aMem; // register file (array of values)
int pc = 0; // program counter
for (pc = p->pc; ; pc++) {
pOp = &aOp[pc];
switch (pOp->opcode) {
case OP_Init: {
// jump to the initialization address
pc = pOp->p2 - 1;
break;
}
case OP_Integer: {
// store an integer constant in a register
aMem[pOp->p2].u.i = pOp->p1;
aMem[pOp->p2].flags = MEM_Int;
break;
}
case OP_OpenRead: {
// open a read cursor on a B-tree
// p1 = cursor number, p2 = root page
VdbeCursor *pCur = allocateCursor(p, pOp->p1);
sqlite3BtreeCursor(pDb->pBt, pOp->p2, 0, pCur->uc.pCursor);
break;
}
case OP_Column: {
// extract column p2 from the row at cursor p1
// store result in register p3
sqlite3VdbeSerialGet(
payloadOfCursor(pOp->p1), pOp->p2, &aMem[pOp->p3]
);
break;
}
case OP_Le: {
// compare register p3 with register p1
// if p3 <= p1, jump to p2
if (aMem[pOp->p3].u.i <= aMem[pOp->p1].u.i) {
pc = pOp->p2 - 1;
}
break;
}
case OP_ResultRow: {
// the current register values form one output row
// hand them to the callback or step() caller
p->pc = pc + 1;
return SQLITE_ROW;
}
case OP_Next: {
// advance the cursor; if there are more rows, jump to p2
rc = sqlite3BtreeNext(pCur, 0);
if (rc == SQLITE_OK) {
pc = pOp->p2 - 1; // loop back
}
break;
}
case OP_Halt: {
return SQLITE_DONE;
}
// ... ~185 more opcodes
}
}
}Why a virtual machine instead of directly interpreting the AST?
- Separation of concerns. The compiler handles the hard optimization decisions once. The VM just runs instructions.
- Prepared statements. You compile a query once (
sqlite3_prepare_v2), then run it many times with different parameters (sqlite3_bind_*+sqlite3_step). The bytecode stays in memory. - Predictable performance. Each opcode does a small, bounded amount of work. No recursive tree walks during execution.
The B-Tree Layer: Where Rows Live
Below the VM sits the B-tree module (src/btree.c — one of the largest files at ~10,000 lines). SQLite uses two types of B-trees:
Table B-Trees (B+ tree variant) Index B-Trees
================================ ================================
- Leaf nodes store the full row data - Leaf nodes store index key +
- Internal nodes store only keys rowid (pointer to table row)
(rowids) and child page pointers - Used for secondary indexes
- One per table - One per CREATE INDEX
- Key = rowid (64-bit integer) - Key = indexed column values
[internal page] [internal page]
/ | \ / | \
[leaf] [leaf] [leaf] [leaf] [leaf] [leaf]
row 1 row 4 row 7 (age=20, (age=25, (age=30,
row 2 row 5 row 8 rid=3) rid=1) rid=7)
row 3 row 6 row 9 (age=22, (age=28, (age=35,
rid=5) rid=2) rid=4)Page Structure
Every B-tree node occupies exactly one page (default 4096 bytes). A page has a small header followed by an array of cells:
Page layout (4096 bytes default)
+--------------------------------------------------+
| Page header (8-12 bytes) |
| - page type (leaf/interior, table/index) |
| - number of cells |
| - offset to first free block |
| - offset to cell content area |
+--------------------------------------------------+
| Cell pointer array |
| [offset1] [offset2] [offset3] ... |
| (2 bytes each, sorted by key) |
+--------------------------------------------------+
| Unallocated space |
| |
+--------------------------------------------------+
| Cell content area (grows from bottom up) |
| cell3: [size][rowid][col1][col2][col3] |
| cell2: [size][rowid][col1][col2][col3] |
| cell1: [size][rowid][col1][col2][col3] |
+--------------------------------------------------+The cell pointer array is always sorted by key, but cell contents are stored in insertion order (growing from the end of the page upward). To insert into the middle, SQLite only needs to shift a few 2-byte pointers, not the actual data. When a page fills up, a page split occurs — half the cells move to a new page, and a key is promoted to the parent.
Record Format
Each cell stores a row in SQLite’s record format. The row is self-describing — a header tells you the type and size of each column:
Record format for a single row
+-------------------+-------------------+
| Header | Body |
+-------------------+-------------------+
| header_size (var) | col1 data |
| type1 (var) | col2 data |
| type2 (var) | col3 data |
| type3 (var) | ... |
| ... | |
+-------------------+-------------------+
Serial types (selected):
0 → NULL (0 bytes in body)
1 → 8-bit integer (1 byte)
2 → 16-bit integer (2 bytes)
3 → 24-bit integer (3 bytes)
4 → 32-bit integer (4 bytes)
5 → 48-bit integer (6 bytes)
6 → 64-bit integer (8 bytes)
7 → IEEE 754 float (8 bytes)
8 → integer 0 (0 bytes)
9 → integer 1 (0 bytes)
N≥12, even → blob of (N-12)/2 bytes
N≥13, odd → text of (N-13)/2 bytesThis is why SQLite has flexible typing — the type is stored per-value, not per-column. A column declared as INTEGER can hold text, a blob, or NULL. SQLite uses “type affinity” to prefer certain types, but it never rejects a value for being the wrong type.
The Pager: Pages, Cache, and Crash Safety
The pager (src/pager.c) sits between the B-tree layer and the operating system. Every read or write goes through it. The pager has three jobs:
- Page cache. Keep recently used pages in memory to avoid re-reading from disk.
- Transaction management. Ensure that a group of changes either all commit or all roll back.
- Crash recovery. If the process crashes or loses power mid-write, the database must not be corrupted.
Pager architecture
B-tree layer
|
| "give me page 5" / "write page 5"
v
+------------------------------------------+
| Pager |
| |
| +-------------+ +-----------------+ |
| | Page cache | | Journal / WAL | |
| | (hash table | | (crash safety) | |
| | of pages) | | | |
| +-------------+ +-----------------+ |
| |
+------------------------------------------+
|
v
OS file I/O (via VFS)
|
v
[database.db] [database.db-wal] [database.db-journal]Rollback Journal Mode (Traditional)
In the default journal mode, before modifying any page, the pager copies the original page content into a separate journal file. If the transaction commits, the journal is deleted. If the process crashes, the next connection finds the journal and copies the original pages back — effectively undoing the incomplete transaction.
Rollback journal: write sequence
1. BEGIN
2. Read page 5 from database file
3. Copy original page 5 into journal file ← backup
4. Modify page 5 in cache
5. Copy original page 8 into journal file ← backup
6. Modify page 8 in cache
7. fsync the journal file ← ensure backup is safe
8. Write modified pages 5, 8 to database ← apply changes
9. fsync the database file
10. Delete the journal file ← marks commit as done
11. COMMIT complete
Crash recovery:
- If crash before step 7: journal is incomplete → discard it
Database was never modified → still consistent
- If crash between 7 and 10: journal is complete → replay it
Copy original pages from journal back to database → undo
- If crash after 10: journal is gone → commit succeededWAL Mode (Write-Ahead Logging)
Since SQLite 3.7.0 (2010), there is an alternative: WAL mode. Instead of backing up original pages and modifying them in-place, new versions of pages are appended to a separate WAL file. The original database file is never modified during a transaction.
WAL mode: write sequence
database.db database.db-wal
+----------+ +-------------------+
| page 1 | | WAL header |
| page 2 | | |
| page 3 | | frame 1: page 5' | ← modified page 5
| page 4 | | frame 2: page 8' | ← modified page 8
| page 5 | | frame 3: commit | ← commit marker
| page 6 | | |
| page 7 | | (later tx) |
| page 8 | | frame 4: page 3' |
+----------+ | frame 5: commit |
+-------------------+
Reading page 5:
1. Search WAL from newest to oldest for page 5
2. If found → return the WAL version (page 5')
3. If not found → read from database.db
Checkpointing:
Periodically, a "checkpoint" copies WAL pages back to the
database file and resets the WAL. This is the only time
the database file changes.WAL mode has a crucial advantage: readers and writers do not block each other. A writer appends to the WAL while readers continue reading from the database file (or from earlier WAL frames). This is possible because the WAL is append-only — a reader sees a consistent snapshot as of the last commit frame it observed.
WAL concurrency
Writer Reader A Reader B
------ -------- --------
begin tx begin tx
append page 5' (sees WAL up to begin tx
append page 8' frame 0 — empty) (sees WAL up to
append commit frame 0)
(WAL now has 3 frames) reads page 5 from
database.db reads page 5 from
begin another tx (original version) database.db
append page 3'
append commit end tx
(WAL now has 5 frames) end tx
begin tx
(now sees WAL up to
frame 3 — picks up
the first commit)
reads page 5' from WALSQLite maintains a small WAL index (the -shm file) using shared memory. This index maps page numbers to their latest frame in the WAL, so lookups are O(1) instead of scanning the entire WAL.
The VFS: Portability Layer
At the very bottom, the Virtual File System (src/os_unix.c, src/os_win.c) abstracts away platform differences. The VFS defines methods like:
xOpen,xClose— open/close a filexRead,xWrite— read/write at a byte offsetxSync— fsync (flush to durable storage)xLock,xUnlock— advisory file locks for concurrencyxFileSize,xTruncate— manage file size
This abstraction is why SQLite runs on everything from Linux servers to bare-metal embedded systems. You can register a custom VFS to store the database in memory, on a network share, in an encrypted container, or even in a WebAssembly environment (which is how SQLite runs in browsers via WASM).
Putting It All Together: Life of a Write
Let’s trace an INSERT statement end-to-end:
INSERT INTO users (name, age) VALUES ('Alice', 30); Step 1: Compile
───────────────
Tokenizer → tokens: INSERT, INTO, ID("users"), LP, ID("name"),
COMMA, ID("age"), RP, VALUES, LP, STRING("Alice"),
COMMA, INTEGER(30), RP
Parser → Insert AST node:
table = "users", columns = [name, age],
values = [("Alice", 30)]
Code Generator → Bytecode:
0 Init 0 7 0
1 OpenWrite 0 2 0 3 // open cursor on users table
2 NewRowid 0 1 0 // generate next rowid → reg 1
3 String8 0 2 0 "Alice" // reg 2 = "Alice"
4 Integer 30 3 0 // reg 3 = 30
5 MakeRecord 2 2 4 // encode regs 2-3 → record in reg 4
6 Insert 0 4 1 // insert record (reg 4) with key (reg 1)
7 Halt 0 0 0
Step 2: Execute (VDBE)
──────────────────────
OP_OpenWrite → calls btree to open a write cursor on root page 2
OP_NewRowid → finds the next available rowid (max existing + 1)
OP_String8 → loads "Alice" into register 2
OP_Integer → loads 30 into register 3
OP_MakeRecord→ serializes into SQLite record format:
header: [3, 23, 4] (header_size=3, text(5 bytes), 32-bit int)
body: "Alice" ++ 0x0000001E
OP_Insert → calls sqlite3BtreeInsert()
Step 3: B-tree insert
─────────────────────
btree receives: key = new_rowid, data = serialized record
1. Walk from root to the correct leaf page
2. If leaf has space → insert cell into the page
3. If leaf is full → split the page:
a. Allocate a new page
b. Move half the cells to the new page
c. Insert a divider key into the parent
d. If parent overflows → split recursively
Step 4: Pager (WAL mode)
────────────────────────
Before modifying the leaf page:
1. The page is already in the page cache (from the walk)
2. Mark the page as "dirty"
At COMMIT:
3. Write all dirty pages as new WAL frames
4. Write a commit frame
5. fsync the WAL file → transaction is now durableWhy SQLite Is Fast (and When It Is Not)
SQLite is optimized for a specific use case: single-process, moderate-concurrency, local storage. Here is where it shines and where it struggles:
Strengths Weaknesses
───────── ──────────
Zero overhead for embedded use Single-writer bottleneck:
(no IPC, no serialization, only one write transaction
no network round-trips) at a time
Reads are extremely fast No replication, no
(direct file I/O, mmap support) built-in high availability
Tiny memory footprint Large concurrent write loads
(configurable cache size, will queue and serialize
often < 1 MB)
Robust crash recovery No query parallelism
(decades of testing via (one thread per query)
billions of test cases)
Single-file deployment No stored procedures,
(easy backup: just copy the file) no user-defined aggregates
in the traditional senseSQLite’s test suite deserves special mention. It achieves 100% branch coverage — every branch in the source code is taken at least once during testing. The test suite is roughly 600 times larger than the source code itself. This is a major reason SQLite is trusted in safety-critical systems like aircraft.
References
- SQLite Architecture Documentation — https://www.sqlite.org/arch.html
- The SQLite Bytecode Engine (VDBE) — https://www.sqlite.org/opcode.html
- SQLite File Format — https://www.sqlite.org/fileformat2.html
- Write-Ahead Logging in SQLite — https://www.sqlite.org/wal.html
- SQLite Source Repository — https://github.com/nicbarker/sqlite (GitHub mirror)
- D. Richard Hipp, “SQLite: Past, Present, and Future,” VLDB 2022 — https://www.vldb.org/pvldb/vol15/p3535-gaffney.pdf
- How SQLite Is Tested — https://www.sqlite.org/testing.html