Rehearse these out loud. For each component: the question an interviewer asks, your 30-second spoken answer, the follow-up they push with, and the trap to avoid. Every claim here is traceable to the code (file references included).
The two to over-prepare: #4 (B+ tree) and #8 (WAL) — that's where the depth gets tested.
| Thing | Value | Where |
|---|---|---|
| Page size | 4096 bytes (matches SQLite default) | storage/page.py PAGE_SIZE |
| B+ tree max keys / node | 254 (so fan-out up to 255 children) | index/btree.py DEFAULT_MAX_KEYS |
| B+ tree height for millions of keys | 2–3 levels | fan-out math |
| Buffer pool policy | LRU, write-back, default capacity 64 | storage/buffer_pool.py |
| WAL logging | full-page-image redo (physical) | wal/log.py |
| WAL record | [MAGIC][page_no][length][crc32][data] |
wal/log.py |
| Cost unit | page accesses, not CPU comparisons | planner/optimizer.py |
| Equality selectivity | 1/n_distinct (default 0.1) |
planner/statistics.py |
| Range selectivity | 1/3 (no histograms) |
planner/statistics.py |
| RowId | (page_no, slot) |
storage/heap_file.py |
| Test count | 337 passing | pytest |
Answer: The SQL string goes through a lexer into tokens, then a recursive-descent
parser builds an AST. The optimizer looks at the WHERE predicate, the table statistics,
and the available indexes, and estimates the cost of each access path — a full table scan vs.
an index scan — and picks the cheaper one. That choice becomes a tree of volcano-model
operators (IndexScan → Projection). Execution is pull-based: the top operator's
next() pulls a row from its child, down to the scan that reads pages through the buffer
pool, which serves them from RAM or reads them from disk via the pager. Every write
along the way goes through the WAL first.
Follow-up — "Where does the catalog fit?" The catalog is the system's self-describing
metadata — which tables, columns, and indexes exist, plus statistics. Both the optimizer and
executor read it; it's how the engine knows users has an index on id.
Trap: Don't say "it runs the query." Name the stages — that pipeline IS the architecture, and tracing one row end-to-end is the most common opener.
Answer: A page (4KB) is the unit of disk I/O — we always read/write whole blocks because a disk seek costs the same whether you read 50 bytes or 4096. Rows are variable-length and must be deletable/movable without breaking the index entries pointing at them, so I use a slotted page: a slot directory grows inward from the front, record bytes grow inward from the back, and free space is the gap between. The key trick: a row's identity is its slot number, not its byte offset. An index points at "page p, slot i". If the page is later compacted and the bytes move, only the slot's stored offset changes — the slot number, and every index entry, stays valid.
Follow-up — "What's a RowId?" (page_no, slot). The physical address an index leaf
stores to get from a key back to the row.
Trap: Don't claim you compact pages — you don't yet. Be honest: "delete marks the slot
dead (0,0) and the slot can be reused, but the record bytes aren't reclaimed until
compaction, which is future work." Knowing your own simplification is a plus.
Answer: A bounded, write-back LRU cache of pages between the upper layers and the
pager. Three mechanisms: (1) cache with identity — get_page(n) returns the same
in-memory Page object on a repeat call, so callers mutate in place; (2) dirty tracking +
lazy write-back — a mutated page is marked dirty and written back only on eviction or
explicit flush, so a page touched 100 times costs one write; (3) LRU eviction —
implemented with an OrderedDict, every access does move_to_end, so the victim is always at
the front, written first only if dirty. All O(1).
Follow-up — "Biggest weakness?" No pinning. A production pool pins a page in use so it can't be evicted while a caller holds a reference — otherwise you risk a lost update. QueryX is single-threaded and finishes with one page before fetching the next, so I omit pinning by contract. That's the honest limit.
Trap: Don't say "LRU is best." Mention real systems often use CLOCK (a cheaper LRU approximation) or scan-resistant policies like LRU-K / 2Q, because one big sequential scan can flush a pure-LRU cache of all its hot pages.
Answer: Two properties make it a B+ tree: all data lives in the leaves (internal nodes hold only separator keys to route searches, keeping them dense and the tree shallow), and leaves are linked in sorted order. The payoff is range scans: descend once to the first leaf, then walk the leaf chain — no re-traversal per key. A plain B-tree stores values in internal nodes too, so it can't stream a range like that. Each node is one 4KB page, so fan-out is large (up to ~254 keys/node) and the tree stays 2–3 levels deep for millions of keys. The cost that matters is page reads, O(log_b n) with a large base b — not comparisons.
On a split: insert goes to the correct leaf; if it overflows max_keys, the leaf splits in
two and the smallest key of the right half is copied up as a separator. If the parent
overflows it splits too — but an internal split promotes the middle key (moves it up, not
copies). If the root splits, a new root is created and the tree gains a level. That root-ward
growth keeps it balanced.
Follow-up — "leaf vs internal split?" Leaf split copies the separator up (the key still exists as real data in the leaf). Internal split promotes the middle key up (it's a router, not data, so it moves). Getting this distinction right is a strong signal.
Follow-up — "delete?" Honest: QueryX does leaf-only delete — the entry is removed, but underfull nodes aren't merged/rebalanced and separators are left in place. Search stays correct because a separator needn't be live data. Cost is space: a delete-heavy tree can get underfull and isn't reclaimed. Postgres/SQLite do rebalance.
Trap: Don't say "O(log n) because balanced" and stop. The gold is "O(log_b n) page reads, and the real cost is disk seeks, not the comparisons inside a node." That sentence is the whole reason B+ trees exist.
Answer: Hash index is O(1) average for equality (col = v) — one probe. But it has
no order, so it can't do range scans, ORDER BY, </>, or prefix queries — those need
the B+ tree's sorted leaf chain. So: hash for equality-only point lookups; B+ tree for anything
involving order. My optimizer encodes exactly this — a hash index is only considered for =,
never a range op.
Trap: Don't oversell hash as "always faster." Its O(1) is average; it degrades with collisions, can't help ordered queries, and is painful to grow (rehashing). That's why B+ trees are the default index in real databases, not hash.
Answer: Cost is in page accesses — the dominant real cost — not CPU comparisons. A
SeqScan costs ≈ num_data_pages. An IndexScan costs ≈ descent + matched_rows, where
descent is tree height (≈ log_fanout(rows), ~1 for a hash). So an index wins only when
descent + matched < num_data_pages — which mirrors why real databases ignore an index for
an unselective predicate (returning half the table makes the scan cheaper, because the index
adds random I/O on top). To estimate matched I use System R / Selinger selectivity:
equality = 1/n_distinct (or 0.1), range = 1/3 (no histograms), AND multiplies
(independence), OR = s1 + s2 − s1·s2, NOT = 1 − s. EXPLAIN prints the chosen plan,
its cost, and the SeqScan alternative's cost.
Follow-up — "where does the estimate go wrong?" Correlated columns — independence
breaks. WHERE city='NYC' AND state='NY' is estimated as the product of two selectivities, but
they're 100% correlated, so the real result is far bigger. That's exactly where real optimizers
struggle without multi-column stats. Also n_distinct is computed once at index-build and
row_count goes stale after mutations — production runs ANALYZE; QueryX doesn't.
Trap: Don't invent histograms or join reordering — you don't have them. The honest scope ("single-table access-path selection, Selinger selectivities, no histograms") is a complete, defensible story.
Answer: Every operator implements the same iterator interface: open(), next(),
close(). Execution is pull-based / demand-driven: the root calls next() on its child,
down to the scan. Two wins: (1) composability — operators don't know their children's
types, so they snap into any plan tree; (2) pipelining + early termination — rows flow one
at a time without materializing intermediates, so LIMIT 10 over a million rows stops after 10
and the scan never reads the rest.
Follow-up — "downside / how do modern engines differ?" One next() per row means
per-tuple function-call overhead — millions of tiny calls. Modern analytical engines
(DuckDB, Postgres improvements) use vectorized execution (batches of ~1000 rows) or
compiled plans. Tie-in: my sibling project PacketQL has a vectorized executor (1024-row
batches) — so I've implemented both models and can compare them directly.
Trap: Don't confuse pull (volcano) with push-based execution. And know which operators are
blocking — Sort must consume all input before emitting the first row, breaking
pipelining; Filter/Projection are non-blocking.
8. "You said crash recovery. Explain the WAL and the exact crash you protect against." (makes it a database, not a storage engine — expect grilling)
Answer: Write-ahead logging: before a data page is modified on disk, its new image is
first appended to a log and flushed. The ordering is the whole point — the log record reaches
durable storage before the data page changes. QueryX logs full page images (physical
redo), framed [MAGIC][page_no][length][crc32][data]. On startup the pager replays the log,
REDO-ing each image against the data file. Because each record is a whole page image,
replay is idempotent — reapplying a correct page is harmless, reapplying a torn/stale one
repairs it. After replay, the data file is fsynced and the log is checkpointed (truncated).
The exact crash window: crash after the log record is durable but before the data page is written (or while half-written — a torn page). On restart the logged image is replayed and the page is made whole. A crash mid-append of the log record itself is caught by the CRC + length check: replay stops at the first record with a short header, bad magic, or failing CRC, discarding the torn tail — the all-or-nothing guarantee for the last in-flight write.
Follow-up — "what don't you handle?" Two honest limits: (1) redo-only, no undo — no
multi-statement transactions, so nothing to roll back; production uses ARIES (analysis →
redo → undo). (2) Durability policy — I flush() each record to the OS but only fsync at
checkpoint, so I survive a process crash but a power-loss could lose the last few records;
a production WAL fsyncs per commit (batching via group commit).
Follow-up — "vs Postgres?" Postgres logs logical/physiological records with LSNs and does full-page writes only for the first modification of a page after a checkpoint (to guard torn pages), not every write like I do. Logical logging is far more space-efficient; full-page-image logging is simpler and trivially idempotent — the trade I made.
Trap: Don't say "the WAL saves everything." Name the precise window (log durable → data not yet written) and admit the power-loss gap. Precision here is the difference between "read about WAL" and "built one."
- "The real cost is disk seeks, not comparisons — that's why fan-out and page size matter."
- "A slotted page makes a row's identity its slot number, so the row can move without invalidating any index."
- "The optimizer ignores an index for an unselective predicate on purpose — a scan beats random I/O when you're returning much of the table."
- "WAL is just an ordering rule: log durably before you apply. Everything else is detail."
- "I built both execution models — volcano in QueryX, vectorized in PacketQL — so I can argue the trade-off from experience, not theory."
See also: DESIGN.md for the BNF grammar, per-phase failure analysis, and the full Postgres/SQLite comparison. Sibling project: PacketQL (columnar + vectorized).