Handmade PostgreSQL

20 min Ready to play Handmade PostgreSQL 1/5 — The Server Reinvent the Wheel· 10 tasks· ~24 reviews Part one of the Handmade PostgreSQL campaign: the database becomes a server. Not a REPL that reads a file — a process that binds a port, accepts many clients at once, keeps their sessions apart and its data shared, and stays up when a client sends nonsense. Everything after this part is built on the shape frozen here, so the shape comes first and the SQL stays deliberately thin: CREATE TABLE, INSERT, SELECT . Part two turns that into a real engine. The two commands You declare both, and they are captured into session memory — any language, any entry point. serve: <command> started as: <command> <port> <datadir> sql: <command> started as: <command> <port> The server (serve:) listens on TCP <port>, keeps its data under <datadir>, serves clients concurrently, and runs until it is killed. The client (sql:) connects to 127.0.0.1:<port>, reads SQL from stdin, prints the server's replies to stdout, and exits 0. It is a client: it holds no data of its own and answers nothing on its own. With no server on that port it prints a line starting ERROR: and exits non-zero. Two processes, one socket. Every check in this campaign drives your database by starting your server and talking to it with your client — which is why ERROR: connection refused is graded as carefully as a SELECT. The reply format Frozen for the whole campaign. Every statement produces exactly one acknowledgement line, except SELECT, which prints its rows first: Rows print their values joined by a single | — no header, no padding, no trailing delimiter. Column order is the SELECT list; means declared order. Row order is insertion order until an ORDER BY says otherwise. Two types exist: INT prints as plain decimal, TEXT prints verbatim and unquoted, NULL prints as the empty string. An empty result is the single line SELECT 0. A failing statement never closes the connection and never stops the server. Graded data contains no |, no newlines and no edge whitespace, so the comparison stays exact. Embedding PostgreSQL, SQLite, DuckDB or any existing engine — or shelling out to one — is not building one. The socket handling, the parser and the storage are yours. The ladder Set up: declare serve:, sql: and test: (10) Bind to a port (10) One statement, one reply (10) Many statements on one connection (20) Concurrent clients (40) One database, many connections (40) The client is a client (20) A bad statement does not drop the connection (20) Shut down when asked (20) Review: how you built it (150, judged) databasesqlnetworking +2 Open

25 min Locked Handmade PostgreSQL 2/5 — The SQL Engine Reinvent the Wheel· 10 tasks· ~24 reviews Part two of the Handmade PostgreSQL campaign: the thin SQL of part one becomes an engine. A statement stops being a shape you recognise and starts being something you parse into a tree, plan into an operation over a table, and execute row by row. This session continues the server you built in part one, in the same repository. Nothing about how it is started changes; what changes is how much of SQL it understands. The two commands, unchanged serve: <command> started as: <command> <port> <datadir> sql: <command> started as: <command> <port> The server listens on TCP <port>, keeps its data under <datadir>, serves many clients at once and runs until it is killed. The client connects to 127.0.0.1:<port>, reads SQL from stdin, prints the server's replies to stdout and exits 0. Every check here starts your server, talks to it through your client, and compares what comes back. The reply format Frozen in part one and not restated: one acknowledgement line per statement, rows printed |-joined before the SELECT <n> trailer, UPDATE <n> and DELETE <n> counting the rows they touched, ERROR: <text> for anything that fails without dropping the session. Part two finally puts the UPDATE and DELETE rows of that table to work. Row order stays insertion order until an ORDER BY says otherwise. Graded data carries no |, no newlines and no edge whitespace, so every comparison is exact. Embedding PostgreSQL, SQLite, DuckDB or any existing engine — or shelling out to one — is not building one. The parser, the planner and the executor are yours. The ladder Set up: carry part one's server into this session (10) Projection: name the columns you want (20) WHERE on equality (20) WHERE on <, >, <=, >=, <> (40) AND and OR (20) UPDATE … SET … WHERE … (40) DELETE FROM … WHERE … (40) ORDER BY, LIMIT and OFFSET (40) COUNT, SUM, MIN, MAX and GROUP BY (60) Review: how you built the engine (150, judged) databasesqlparser +2 Open

30 min Locked Handmade PostgreSQL 3/5 — The Storage Engine Reinvent the Wheel· 10 tasks· ~24 reviews Part three of the Handmade PostgreSQL campaign: the database stops living in memory. Pages on disk, a log that is written before the answer is spoken, and a recovery pass that turns a half-finished directory back into a database. The two commands, unchanged serve: <command> started as: <command> <port> <datadir> sql: <command> started as: <command> <port> The server listens on TCP <port>, keeps its data under <datadir> and runs until it is killed. The client connects to 127.0.0.1:<port>, reads SQL from stdin, prints the server's replies to stdout and exits 0. The reply format was frozen in part one — acknowledgement lines, rows joined by a single |, ERROR: for anything that fails — and it is not restated here because it has not moved. This part continues parts one and two: many clients at once, one shared database, a session that survives a bad statement, and the query engine you built — WHERE, ORDER BY, UPDATE, DELETE. The first check re-earns all of it before anything new is asked of you. What this part adds to the contract BEGIN; prints BEGIN, COMMIT; prints COMMIT, ROLLBACK; prints ROLLBACK. The statements between a BEGIN and its COMMIT are one unit — all of them or none of them — and ROLLBACK undoes everything since the BEGIN: inserts vanish, updated rows come back exactly as they were. A transaction belongs to the connection that opened it. A statement outside a transaction autocommits, and it must be durable the moment its acknowledgement line is printed. The ack is a promise: once INSERT 1 has reached stdout, that row survives anything — including the process dying on the very next byte. One statement exists only for the test harness: CRASH; terminates the server process instantly, mid-flight, with no clean shutdown — no flushing of pending work, no tidy save-on-exit. It simulates the power cord leaving the wall, and the next server started on that data directory must recover: everything acknowledged outside a transaction and every committed transaction is there, everything uncommitted is gone. That is the whole trick the checks play: they cannot see inside your engine, so they kill it and read what is left. Write the intent to a log, flush it, acknowledge, then apply — and every check below passes. Save-on-exit passes none of the ones that matter. Embedding PostgreSQL, SQLite, DuckDB or any existing engine — or shelling out to one — is not building one. The pages, the log and the recovery are yours. The ladder Set up: re-earn parts one and two (10) Data survives a restart (40) The schema survives too (20) The data directory holds the data (20) BEGIN and COMMIT in one breath (20) ROLLBACK leaves no trace (40) The acknowledgement is a promise (60) Uncommitted work dies with the process (40) Recovery replays once, not twice (20) Review: how you built the storage (150, judged) databasestoragedurability +2 Open

30 min Locked Handmade PostgreSQL 4/5 — Indexes and Plans Reinvent the Wheel· 10 tasks· ~24 reviews Part four of the Handmade PostgreSQL campaign: the database gets fast, and learns to say how. Parts one through three gave you a server, an engine and the statements that read and change rows. This part adds the two things that separate a table scan from a database — an index, and a plan that admits which one it used. The two commands, unchanged serve: <command> started as: <command> <port> <datadir> sql: <command> started as: <command> <port> The server binds TCP <port>, keeps its data under <datadir>, serves many clients at once and runs until killed. The client connects to 127.0.0.1:<port>, reads SQL from stdin, prints the replies to stdout and exits 0 — and exits non-zero with an ERROR: line when nothing is listening. The reply format was frozen in part one and is not restated here: one acknowledgement line per statement, SELECT prints its rows |-joined first, a failure prints ERROR: <text> and the session carries on. Everything parts one through three earned is re-checked on the first rung, so a codebase carried over honestly pays from the first probe. The bulk loader on the last rungs sends many rows per statement — INSERT INTO t VALUES (…),(…),(…); — and reads back the single INSERT <n> the frozen contract already promises. That is not a new statement, only the shape of one you already reply to. What this part adds to the contract Two additions, and nothing else: CREATE INDEX <name> ON <table> (<column>); replies with exactly CREATE INDEX. Index names are unique per database: creating one that already exists is an ERROR: line, and the session continues. An index survives a restart, like everything else under <datadir>. EXPLAIN <select>; prints the plan it would run: one line per plan node, outermost node first, each line starting with the node name in capitals — SEQ SCAN, INDEX SCAN, FILTER, SORT, LIMIT, AGGREGATE — followed by a space and whatever detail you want to give. After the plan lines comes the trailer EXPLAIN <n>, where n is the number of plan lines printed. Only the leading node keyword is graded; the detail after it is yours to design. EXPLAIN SELECT * FROM t WHERE k = 42; INDEX SCAN t using ix_t_k (k = 42) EXPLAIN 1 The plan has to be the truth. When an index covers the column a query filters on by equality, the plan says INDEX SCAN and the lookup really goes through the index; when no index covers it, the plan says SEQ SCAN. A planner that prints INDEX SCAN unconditionally is graded the same as one that prints it never — the rungs ask both questions of the same table. Embedding PostgreSQL, SQLite, DuckDB or any existing engine — or shelling out to one — is not building one. The index structure, the planner and the storage are yours. The ladder Set up: carry parts one to three forward (10) CREATE INDEX, twice is an error, and it survives a restart (20) EXPLAIN a sequential scan (20) The planner picks the index — and knows when not to (40) Indexed lookups are exact, before and after the index (40) The index stays honest through UPDATE and DELETE (40) Range scans over an index (40) A hundred thousand rows and a hundred lookups (60) Eight readers and one writer at the same time (40) Review: how you made it fast (150, judged) databaseindexesperformance +2 Open

30 min Locked Handmade PostgreSQL 5/5 — Distribution Reinvent the Wheel· 10 tasks· ~24 reviews Part five, the finale of the Handmade PostgreSQL campaign: one database becomes several. A second copy of your server follows the first and answers reads from it. A single table stops being a single heap and becomes a set of partitions the planner can skip. This continues parts one through four. The server, the SQL engine, the storage and the indexes are the ones you already built — nothing here replaces them, everything here sits on top. The ladder opens by re-checking that the four parts below it still work. The two commands Unchanged, and still captured into session memory: serve: <command> started as: <command> <port> <datadir> sql: <command> started as: <command> <port> The reply format is the one frozen in part one — one acknowledgement line per statement, SELECT printing its rows |-joined first, failures printing ERROR: <text> without closing the session. It is not restated here; it has not moved. What this part adds Three additions, and they are the whole contract of part five. A third argument makes a replica <command> <port> <datadir> <primary_port> Started with a fourth word, your server comes up as a replica of the primary listening on 127.0.0.1:<primary_port>. It binds <port> and keeps its own copy under its own <datadir> — the two servers never share a directory. A replica answers SELECT like any server. A statement that would write — INSERT, UPDATE, DELETE, CREATE TABLE — replies with an ERROR: line and changes nothing. The replica is a copy, not a second opinion. What it copies is everything: the rows already on the primary when it starts (the initial copy), the rows written while it is connected (the stream), and the rows written while it was down (the catch-up when it comes back on its own data directory). How you move them — a log you ship, pages you send, statements you replay — is yours to choose and yours to write down. WAIT <n>; WAIT 1; -> WAIT 1 Sent to the primary, WAIT <n>; blocks until at least <n> replicas have acknowledged everything committed so far, then replies WAIT <n> where <n> is how many acknowledged. This is the handle that makes replication testable without sleeping and hoping: a check writes, waits, and reads the replica. WAIT never blocks forever. If the count it was asked for has not been reached after a few seconds it gives up and answers anyway — WAIT 0 with nobody following, or an ERROR: line. A WAIT that hangs is a failed WAIT. Partitioned tables CREATE TABLE <t> (<columns>) PARTITION BY RANGE (<col>) PARTITIONS <n>; -> CREATE TABLE The key column is INT. The table's rows live in <n> partitions named <t>_p0 … <t>_p<n-1>, and each partition owns a contiguous, ascending slice of the key. The slices are fixed and deliberately boring, so that your engine and a check agree without inventing a bounds syntax: partition i owns the keys from i × 1000 up to but not including (i + 1) × 1000. Keys at or above <n> × 1000 land in the last partition; keys below zero land in the first. INSERT routes each row to the partition its key falls in and replies as always, INSERT <n>. SELECT FROM <t>; reads every partition and returns every row in insertion order — a partitioned table still behaves like one table. SELECT FROM <t>_p3; reads that one partition, as a table in its own right. EXPLAIN <select>; reports the plan and, for a partitioned table, prints one PARTITION <name> line for each partition the plan will scan, in partition order, before its EXPLAIN acknowledgement. A select filtered by the key with WHERE <col> = <value> prints exactly one — that is pruning. An unfiltered select prints all of them. Whatever else your EXPLAIN already prints from part four stays; only the PARTITION lines are graded. Embedding PostgreSQL, SQLite, DuckDB or any existing engine — or shelling out to one — is not building one. The replication and the partitioning are yours, same as the socket, the parser and the pages before them. The ladder Set up: the commands, and parts one to four still standing (10) A replica connects (20) The replica starts with what was already there (40) Writes stream to the replica (40) The replica is read-only (20) The replica catches up after being down (40) WAIT acknowledges, and never hangs (40) Rows route to partitions (40) EXPLAIN prunes the partitions it does not need (60) Review: how you built it (150, judged) databasereplicationpartitioning +2 Open

Handmade PostgreSQL

The shape, frozen in part one

The parts

How it is scored