Blog - kimserey lam

Jul 22, 2026

OLAP – Phase 9 Query Planner and Optimizer

The parser produces an AST — a syntactic representation of the SQL query. But the AST doesn’t know whether table names exist, what types columns have, or how to execute the query efficiently. This phase bridges the gap with three components: a binder that resolves names and types, an optimizer that rewrites the logical plan for efficiency, and a physical planner that maps logical operators to executable physical operators.

The pipeline is: AST → Binder → Logical Plan → Optimizer → Physical Planner → Physical Plan.

Jul 18, 2026

OLAP – Phase 8 SQL Parser

The execution engine from Phases 5-7 works, but it requires manually constructing operator trees and expression objects in Go code. A real database accepts SQL text from users. This phase builds a SQL parser that converts a SQL string into an Abstract Syntax Tree (AST) — a structured representation that the planner (Phase 9) can transform into a physical execution plan.

The parser has two stages: a lexer that splits the SQL string into tokens, and a recursive descent parser that builds the AST from the token stream.

Jul 15, 2026

OLAP – Phase 7 Hash Join

Analytical queries rarely touch a single table. “Revenue by region” needs to join orders with regions. “Sales by product category” needs to join sales with products with categories. The hash join is the standard OLAP join algorithm — it builds a hash table from one table (the smaller one), then probes it with the other (the larger one), achieving O(n + m) complexity instead of nested-loop’s O(n x m).

This phase implements the HashJoinOperator with support for INNER and LEFT joins, including NULL key handling.

Jul 11, 2026

OLAP – Phase 6 Hash Aggregation

The scan/filter/project pipeline from Phase 5 processes rows one batch at a time — it’s a streaming operation where each batch flows through independently. Aggregation (GROUP BY with SUM, COUNT, AVG) is fundamentally different: it needs to see all the data before producing any output. This makes it a pipeline breaker — it consumes all input, builds an internal state, then emits results.

This phase implements GROUP BY aggregation using a hash table: the HashAggregateOperator, the GroupByHashTable, and five aggregate functions (COUNT, SUM, AVG, MIN, MAX).

Jul 08, 2026

OLAP – Phase 5 Vectorized Expressions and Scan/Filter/Project

The storage layer can persist and read columnar data. Now we need to query it. This phase builds the execution engine’s foundation: expressions that evaluate on entire vectors at once (2048 rows per call), and three physical operators — SeqScan, Filter, and Projection — that form the basic query pipeline.

The key insight is vectorized execution: instead of evaluating amount > 100 one row at a time, we evaluate it on 2048 rows at once in a tight loop. This eliminates per-row function call overhead and lets the CPU pipeline and cache work efficiently.

Jul 04, 2026

OLAP – Phase 4 Table, Catalog, and Bulk Loading

Phases 1-3 built the storage primitives — vectors, row groups, column segments, and compression. But there’s no concept of a “table” yet. There’s no way to define a schema (CREATE TABLE), no way to add rows one at a time, no way to bulk-load from a CSV, and no way to persist and reload the database across restarts.

This phase adds the Table (schema + row groups + append state), the Catalog (table registry with JSON manifest), and a CSV loader for bulk ingestion.

Jul 01, 2026

OLAP – Phase 3 Compression

Columnar storage has a property that row-based storage doesn’t: values in a column tend to be similar. A status column might have only 5 distinct values across millions of rows. A timestamp column is monotonically increasing. A year column spans a narrow range. Compression codecs exploit these patterns to shrink data 5-10x, and because columns are stored independently, each column gets the codec that fits its data best.

This phase implements four compression codecs — RLE, Dictionary, Bitpacking, and Delta — with automatic selection that tries all applicable codecs and picks the smallest.

Jun 27, 2026

OLAP – Phase 2 Columnar Storage

Phase 1 gave us in-memory vectors and data chunks. But a database needs to persist data to disk and read it back. The challenge is designing a disk format that preserves the benefits of columnar layout: read only the columns you need, skip entire sections when the data can’t match your query.

This phase builds two structures: RowGroups (horizontal partitions of a table, each holding up to 122,880 rows) and ColumnSegments (one column’s serialized data within a row group, annotated with min/max zone maps).

Jun 24, 2026

OLAP – Phase 1 Vectors and DataChunks

The fundamental difference between OLTP and OLAP databases is how they store and process data. An OLTP database like PostgreSQL stores rows — when you insert a customer record, all columns (name, email, balance) sit together on one page. An OLAP database like DuckDB stores columns — all names sit together, all emails sit together, all balances sit together. This layout is what makes analytical queries fast: SELECT SUM(balance) FROM customers only touches the balance column, ignoring everything else.

This phase builds the two foundational data structures of a columnar engine: Vectors (typed columnar arrays) and DataChunks (batches of column vectors).

Jun 20, 2026

OLTP – Phase 10 Transactions, Concurrency, REPL, and Server

The database is fully functional — it can store data, run SQL, use indexes, and survive crashes. But it’s missing three things that make a database a database:

Transactions: grouping multiple operations into an atomic unit (BEGIN/COMMIT/ROLLBACK)
Concurrency control: preventing multiple connections from corrupting each other’s data
An interface: a way for users and applications to actually connect and run queries

This phase ties everything together. The WAL from Phase 9 gave us durability (the “D” in ACID). Now we add atomicity (“A”) via transactions, and isolation (“I”) via locking.

Jun 17, 2026

OLTP – Phase 9 Write-Ahead Log (WAL)

Everything we’ve built so far has a fatal flaw: if the power goes out, data is lost. The buffer pool keeps dirty pages in memory and flushes them to disk lazily. A crash before that flush means those changes vanish.

The write-ahead log solves this. Before changing any data page, we write a description of the change to a separate, sequential log file. If the database crashes, we replay the log on restart and reconstruct the lost changes. This guarantees durability — the “D” in ACID.

The key insight: writing to a sequential log file is cheap. It’s one append to one file, always at the end. Writing random data pages is expensive — they’re scattered across multiple files. So we make the cheap write first (WAL), and let the expensive writes (data pages) happen whenever convenient. If we crash before the data pages are written, the WAL has everything we need to recover.

In PostgreSQL, this is xlog.c, xlogrecord.h, and xlogrecovery.c.

Jun 13, 2026

OLTP – Phase 8 B-Tree Index

Without an index, every query scans every row. WHERE id = 42 on a million-row table reads all million rows to find one. That’s O(n) — slow.

A B+ tree index is a sorted data structure that maps key values (like id) to the physical location of rows (page number + slot). It enables O(log n) lookups — finding a row in a million-row table reads 3-4 pages instead of thousands.

This is the same reason a book index exists: instead of reading every page to find “B-tree,” you check the index at the back, which tells you the page number directly.

Jun 10, 2026

OLTP – Phase 7 Query Executor (The Integration Phase)

Before this phase, the parser and storage engine were separate systems. The parser could turn SQL into an AST, and the storage engine could read/write rows — but they didn’t talk to each other. Queries were still built manually in Go code.

Phase 7 connects everything. The Executor takes a SQL string, parses it, looks up the table in the catalog, converts the AST to an execution plan, runs it, and returns results.

Jun 06, 2026

OLTP – Phase 6 SQL Parser

Until now, every query is built manually in Go — constructing executor nodes and expression structs by hand. That works for testing, but a real database needs to understand SQL text. Phase 6 adds a parser that turns a SQL string like SELECT name, age FROM users WHERE age > 25 into a tree of Go structs (an AST) that the executor can work with. This phase is pure syntax — no storage, no execution. It takes a string and produces a data structure.

Jun 03, 2026

OLTP – Phase 5 Buffer Pool Manager

Every time the database reads a row, it calls HeapFile.ReadPage() which seeks to a position in the file, reads 4096 bytes from disk, and copies them into memory. When a sequential scan reads page 0, then page 1, then page 0 again — it reads page 0 from disk twice. The OS has a page cache that might help, but the database can’t control or rely on it.

Phase 5 adds a buffer pool: a fixed-size array of page-sized slots in memory. When you need a page, the pool checks if it’s already cached. If so, you get the in-memory copy instantly. If not, it reads from disk and caches it for next time.

This is the single biggest performance optimization in any database. Everything else — indexes, query optimization, parallel scans — builds on top of having fast page access.