How SQLite actually works under the hood

SQLite is the most widely deployed database engine on the planet. It is inside every iPhone, Android device, browser, television, and airplane flight system. Yet, many software engineers view it as a black box: a single C file that magically reads and writes to a single disk file without needing a standalone server process.

How does SQLite execute transactions with ACID guarantees, zero network latency, and memory safety?

This deep dive walks through SQLite’s internal architecture: the Lemon parser compiler, the register-based VDBE (Virtual Database Engine), B-Tree page organization, the Pager subsystem, and the Write-Ahead Log (WAL).

1. The High-Level Pipeline

Unlike client-server databases like PostgreSQL or MySQL that communicate over TCP sockets, SQLite runs in-process as an embedded library. When you invoke sqlite3_step(), the execution flow cascades through five distinct layers:

  SQL Query String
         │
         ▼
┌──────────────────┐
│  Tokenizer &     │  Lexical scanner + Lemon LALR(1) parser
│  Lemon Parser    │
└────────┬─────────┘
         ▼
┌──────────────────┐
│ Code Generator   │  Emits low-level bytecode instructions
└────────┬─────────┘
         ▼
┌──────────────────┐
│   VDBE Engine    │  Register-based virtual machine executing opcodes
└────────┬─────────┘
         ▼
┌──────────────────┐
│  B-Tree & Cursor │  Organizes pages into table and index B-trees
└────────┬─────────┘
         ▼
┌──────────────────┐
│ Pager & WAL Log  │  Page cache, concurrency control, atomic transactions
└────────┬─────────┘
         ▼
    OS / VFS API      (POSIX pread/pwrite, Windows file locking)

2. The VDBE: SQLite’s Internal Bytecode Machine

At the heart of SQLite is the Virtual Database Engine (VDBE). SQLite does not interpret the SQL abstract syntax tree directly. Instead, its compiler compiles SQL statements into a stream of bytecode instructions.

You can inspect the generated bytecode for any query using SQLite’s built-in EXPLAIN:

EXPLAIN SELECT name FROM users WHERE id = 42;

This outputs a sequence of opcodes:

addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------
0     Init           0     8     0                    00  Start at addr 8
1     OpenRead       0     2     0     2              00  Open cursor 0 on root page 2
2     Integer        42    1     0                    00  r[1] = 42
3     SeekRowid      0     7     1                    00  Seek cursor 0 to rowid r[1]
4     Column         0     1     2                    00  r[2] = cursor[0].column[1]
5     ResultRow      2     1     0                    00  Output r[2] to client
6     Halt           0     0     0                    00  Finish
7     Close          0     0     0                    00  Close cursor
8     Transaction    0     0     0                    00  Begin read transaction
9     Goto           0     1     0                    00  Jump to addr 1

The VDBE operates on an array of numbered registers (r[1], r[2]). Notice opcode SeekRowid: because id is SQLite’s internal rowid, it executes a binary search through the B-Tree in $O(\log N)$ time, avoiding a sequential table scan entirely.

3. Storage Layout: B-Trees and Pages

SQLite stores databases in uniform, fixed-size Pages (by default $4\,096$ bytes, or $4\text{ KB}$).

The database file is partitioned into two types of B-Trees:

1. Table B-Trees (B+Trees): Internal nodes contain only rowids and page pointers. Leaf pages store the actual user payload data (columns, strings, blobs).
2. Index B-Trees: Keys are the indexed values; payloads contain the associated rowid.

Page Structure

Every $4\text{ KB}$ page begins with an internal header, an array of 2-byte cell pointers, and cells allocated from the bottom of the page upward:

┌────────────────────────────────────────────────────────┐
│ Page Header (8 or 12 bytes: flags, freeblock, cell ct) │
├────────────────────────────────────────────────────────┤
│ Cell Pointer Array (offsets into page content)         │
├────────────────────────────────────────────────────────┤
│                     Unallocated Space                  │
│                            ▼                           │
│                            ▲                           │
├────────────────────────────────────────────────────────┤
│ Cells (Payload data, Record headers, Varints)          │
└────────────────────────────────────────────────────────┘

By growing the pointer array forward and the cell records backward, SQLite avoids internal page fragmentation during inserts.

4. The Pager Subsystem and WAL Mode

The Pager layer enforces ACID transactions. In traditional Rollback Journal mode, writing a page required writing the old page to a .journal file, syncing disk, writing to the DB, and deleting the journal. Readers blocked writers, and writers blocked readers.

In modern applications, SQLite is operated in WAL (Write-Ahead Log) mode:

PRAGMA journal_mode=WAL;

How WAL Concurrency Works

In WAL mode, original pages in the .db file are never modified directly during an active transaction.

Client Read  ───────────────► 1. Check WAL index (wal-index shm)
                                 Found? Read latest page from db-wal
                                 Not found? Read original page from db

Client Write ───────────────► 2. Append new page version to db-wal

1. Writers append updated pages sequentially to the end of db-wal. Sequential append writes are orders of magnitude faster than random-access disk updates.
2. Readers read the latest version of a page from the WAL if present; otherwise, they fall back to the original database file.
3. No Lock Contention: A writer never blocks readers, and readers never block the writer. Multiple processes can read simultaneously while a writer is writing.

The Checkpoint Process

When the WAL file reaches a configured threshold (default: $1\,000$ pages), SQLite initiates a checkpoint:

1. Copies modified pages from db-wal back to their canonical locations in db.
2. Flushes disk caches using fsync.
3. Resets the WAL write offset back to zero without deleting the file.

5. Performance Rule of Thumb

Because SQLite is embedded directly into the host process address space, calling sqlite3_step() avoids socket marshaling, JSON serialization, and loopback latency:

Summary

SQLite’s simplicity is deceptive. Beneath its single-file footprint lies a world-class compiler pipeline, a register-based virtual machine, an elegant page-aligned B-tree layout, and a zero-allocation concurrent WAL logger.

Understanding these internal layers turns SQLite from a casual local prototyping database into one of the most reliable production datastores in your systems engineering toolkit.