Output contract

Every string a test may check is defined here, once. Tutorial pages quote this page, tests assert it, implementations print it. When an implementation and a test disagree, this page decides which one is wrong. If this page is silent, fix this page first.

It describes what the program prints, never how the program works.

Sections 1 to 13 are the contract of The Core Engine. Sections 14 to 21 are the contract of Flexible Storage: they hold everything earlier unless they say otherwise, and section 21 lists each thing they change, with the stage that changes it. Sections 22 to 31 are the contract of Memory and Space, in the same way, and section 31 lists what they change. Sections 32 to 38 are the contract of Transactions and Recovery, and section 38 lists what they change. Sections 39 to 51 are the contract of Querying, and section 51 lists what they change. Sections 52 to 64 are the contract of Indexes and the Optimizer, and section 64 lists what they change. Sections 65 to 79 are the contract of Joins and Relations, and section 79 lists what they change. Sections 80 to 91 are the contract of Sessions and Concurrency, and section 91 lists what they change. Sections 92 to 103 are the contract of the Server track, which is optional and runs from a test kit on the learner's machine (section 92); it changes no earlier section, adding the server and the pooler beside the REPL.

Guiding choice: for everything c-droid already prints consistently, this page writes that behaviour down unchanged. The exception is error codes, which are redesigned in section 3. Other new decisions are marked (new).

1. General rules

All output goes to stdout. Lines end with \n. Output is UTF-8.
Output is deterministic: no timings, no addresses, nothing that depends on iteration order. The one exception is the [TIME] line of explain analyze (section 61), which tests never read.
One table exists in this part: users (id, name, email). id is an unsigned 32-bit integer and the primary key. name and email are strings of at most 27 bytes.
Keywords and debug command names are case-insensitive. Identifiers and values keep the case they were typed in.
Input lines are trimmed of leading and trailing whitespace. An empty line prints nothing.
A statement may be up to 4096 bytes long (new).
Each stage says what it requires, never what is still forbidden. An implementation may do more than its stage asks — accept more input, report an error a later stage introduces — and the tests of that stage still pass.

2. Command line and REPL

Invocation	Behaviour
no arguments	interactive session on `droid.db` in the working directory
`--db <path>`	use `<path>` as the database file
`-c "<command>"`	run one command, print its output, exit. No welcome line, no prompt
`--db <path> -c "<command>"`	both, in either order

An interactive session first prints one line starting with Welcome to droid.
The prompt is the single character > with no space and no newline, printed before each read.
.exit and end of input both end the session: the program prints exiting.. good bye!, saves the database (section 8), and exits with status 0.
From the persistence stage on, the database file is opened before the welcome line. A file that cannot be used prints its error line and nothing else (section 8).
.help prints exactly:

Available commands:
.exit - Exit the program
.help - Show this help message

In the repl stage the loop knows meta commands and nothing else, so every other line — including anything that looks like SQL — is 00105 (new). From the lexer stage on, a line that is not a meta command goes to the SQL front end instead and comes back with a lexer or parser code, so 00105 can no longer happen: the repl cases that assert it are format cases, and lexer is the stage that retires them.
Exit status: 0 for a normal session, even if commands in it failed. -c exits 1 when its command printed an error (new). A command line error or a database that cannot be opened exits 1. From begin-commit, .crash exits 3, and from wal-write so does a fail-point (sections 33 and 35).
The REPL always continues after an error.

3. Errors

An error is one line: [ERROR:SSCCC] message. SS names the component that detected the problem, CCC the condition inside it. One condition has one code, and a code never changes meaning. Tests assert the code and never the message text, so messages are free to be as helpful as the implementation likes.

Lexer and parser errors end with at col N, where N is the 1-based column in the line as typed (after trimming). An optional second line HINT: ... may follow any error; tests never require it.

A line produces at most one error. The first layer that fails reports it and the layers after it do not run: launch #; is the lexer's 00202, never also the parser's 00301. Nothing else from that line is printed before or after the error, except its optional HINT: line.

An error ends the line, not the session. Only two kinds of error end the program: a command line that cannot be understood (00101, 00102, 00106 from io-counters, 00107 from external-sort, and 01901 and 01902 from server-listen) and a database file that cannot be used (00603, 00604, from the persistence stage, 00608, from file-header, and 00609 for page 0 at open, from page-checksums). Each prints its one line and exits 1.

A failed statement changes nothing: no row, no partial update.

Component ranges

`SS`	Component	First used in
`01`	command line, REPL, debug command arguments	The Core Engine
`02`	lexer	The Core Engine
`03`	parser	The Core Engine
`04`	names and types (tables, columns, value types, limits)	The Core Engine
`05`	row codec debug commands	The Core Engine
`06`	pager and database file	The Core Engine
`07`	B+Tree	The Core Engine
`08`	statement execution (INSERT, UPDATE, DELETE)	The Core Engine
`09`	planner and `explain`	The Core Engine
`10`	output modes	The Core Engine
`11`	catalog and DDL	Flexible Storage
`12`	buffer pool, free list, space management	Memory and Space
`13`	transactions	Transactions and Recovery
`14`	write-ahead log and recovery	Transactions and Recovery
`15`	expressions, NULLs, sorting, grouping	Querying
`16`	indexes, constraints, statistics	Indexes and the Optimizer
`17`	joins, foreign keys, subqueries	Joins and Relations
`18`	sessions, locks, isolation	Sessions and Concurrency
`19`	server and protocol	The Server Track

A later part adds codes inside its own range and never renumbers an earlier one.

Codes in this part

The ranges follow the order in which the stages introduce each component, and the last column names the stage where a code first appears, so a failing test points at a tutorial page. The number itself names the component, not the stage: stages can be inserted or moved, and a code must never change meaning.

Code	Condition	Introduced in
`00101`	unknown command line option	`repl`
`00102`	a command line option is missing its argument (`-c`, `--db`)	`repl`
`00103`	unknown meta command (a line starting with `.`)	`repl`
`00104`	a debug command has an unknown subcommand or an invalid argument (`pager foo`, `pager get abc`, `btree find x`)	`lexer`
`00105`	the REPL cannot recognise the line at all — only reachable in `repl`, where there is no SQL front end yet to hand it to	`repl`
`00201`	unterminated string literal	`lexer`
`00202`	unexpected character	`lexer`
`00301`	the statement does not start with a known keyword	`parser`
`00302`	any other syntax error	`parser`
`00303`	INSERT lists a different number of columns and values	`parser`
`00401`	unknown table	`btree-leaf`
`00402`	unknown column	`btree-leaf`
`00403`	value type does not match the column (a string for `id`, a number for a text column)	`row-serialization`
`00404`	integer out of range for `id` (not in 0..4294967295)	`row-serialization`
`00405`	string longer than 27 bytes	`row-serialization`
`00406`	INSERT does not provide `id` (what the other columns left out get: sections 14, 41 and 50)	`btree-leaf`
`00501`	`serialize` was given nothing, or a statement that is not an INSERT (syntax, name and type errors keep their own codes)	`row-serialization`
`00502`	malformed or over-long hex input to `deserialize`	`row-serialization`
`00601`	page number out of bounds or not allocated	`pager`
`00602`	page limit reached	`pager`
`00603`	the database file cannot be opened or created	`persistence`
`00604`	the database file's size is not a multiple of the page size	`persistence`
`00701`	INSERT of an `id` the table already has	`btree-search`
`00702`	a node is full and the split that would relieve it does not exist yet: a leaf before `btree-leaf-split`, the root internal node before `btree-internal-split`	`btree-leaf`
`00801`	UPDATE tried to change the primary key	`delete-update`
`00901`	`explain` was given nothing (syntax, name and type errors in its statement keep their own codes)	`volcano-executor`
`01001`	unknown output mode	`result-set`

Codes added in Flexible Storage

Code	Condition	Introduced in
`00407`	a row that would be larger than 1000 bytes once encoded (section 15): an INSERT, an UPDATE, `serialize`, or the catalog row of a CREATE TABLE; until `overflow-pages` (section 29), after which it no longer happens	`varlen-btree-leaf`
`00408`	a column named twice in one list: the columns of a CREATE TABLE, the columns of an INSERT, the assignments of an UPDATE; from `alter-table`, ADD COLUMN of a name the table already has (section 50)	`create-table`
`00503`	`deserialize` was given bytes that are not a row of the table (section 15)	`varlen-rows`
`00605`	`page insert`: the record does not fit in the page	`slotted-page`
`00606`	a `page` command on a page that is not a slotted page	`slotted-page`
`00607`	a `page` command names a slot that does not exist or is deleted	`slotted-page`
`00608`	the database file is not a droid database: page 0 does not start with the magic, or has a version or page size this program does not read	`file-header`
`00609`	a page read from the file does not match its checksum (section 20); for page 0, at open, it ends the program	`page-checksums`
`00703`	`btree dump` of a page that is not a B+Tree node	`file-header`
`01101`	CREATE TABLE of a table that already exists	`create-table`
`01102`	a column type that is not `INT` or `VARCHAR(n)` with `n` from 1 to 65535	`create-table`
`01103`	the first column of a CREATE TABLE is not `INT`; from `primary-key-rowid`, a column marked `PRIMARY KEY` is not `INT` (section 53)	`create-table`

Some Core Engine codes name users, id or 27 bytes. In Flexible Storage they keep their condition and apply to every table: 00401 is any table that does not exist, 00402 any column its table does not have, 00403 a value of the wrong type for its column, 00404 a number out of 0..4294967295 for any INT column, 00405 a string longer than its column's VARCHAR(n), 00406 an INSERT that does not give the first column, and 00801 an UPDATE that assigns the first column. There is one code for a table that does not exist, 00401, in every stage.

Codes added in Memory and Space

Code	Condition	Introduced in
`00106`	`--cache-pages` is not a number from 1 to 1000	`io-counters`
`01201`	a page must come into the buffer pool and every page in it is pinned	`pin-unpin`
`01202`	`pager unpin` of a page that is not pinned	`pin-unpin`
`01203`	`pager free` of a page that is already free	`free-list`
`01204`	`pager free 0`: the header is never freed	`free-list`

00102 covers --cache-pages with no number after it, as it covers -c and --db, and from external-sort --sort-memory too.

Codes added in Transactions and Recovery

Code	Condition	Introduced in
`01301`	BEGIN while a transaction is open	`begin-commit`
`01302`	COMMIT, or from `rollback` ROLLBACK, while no transaction is open	`begin-commit`
`01303`	the open transaction is too large: a page must come into the buffer pool, and every page in it is pinned or changed by the open transaction, at least one of them only changed (section 33). It ends the transaction	`begin-commit`
`01304`	a statement that cannot run inside a transaction: VACUUM, and from `checkpoint` CHECKPOINT	`begin-commit`

The log has no error of its own: a log that is damaged, cut short or not a log at all is read up to its last good record (section 35), and anything after that is ignored.

Codes added in Querying

Code	Condition	Introduced in
`00107`	`--sort-memory` is not a number from 1 to 1000000	`external-sort`
`01104`	a column the table cannot take: a `NOT NULL` column with no `DEFAULT` added to a table that has rows, or a `DEFAULT` on the first column (section 50)	`alter-table`
`01501`	division or remainder by zero, met while evaluating an expression for a row (section 40)	`expressions`
`01502`	an integer result outside the signed 64-bit range, met while evaluating an expression for a row (section 40)	`expressions`
`01503`	a NULL for a column that cannot hold one: a `NOT NULL` column given NULL or left out of an INSERT, the first column given NULL (leaving it out is `00406`), or a `NOT NULL` column assigned NULL by an UPDATE (section 41); from `alter-table`, a column declared `NOT NULL DEFAULT NULL` (section 50)	`nulls`
`01504`	a sort's temporary file cannot be created, written or read (section 45); the statement fails	`external-sort`
`01505`	LIMIT or OFFSET is not followed by a number from 0 to 4294967295 (section 46); the parser reports it, though its code is in this part's range	`limit-offset`
`01506`	a call of a function that does not exist, with the wrong number of arguments, or with `` where it is not `COUNT()` (section 47)	`aggregates`
`01507`	a column outside an aggregate, next to an aggregate, with no GROUP BY to give it one value (section 47); from `group-by-having`, a column outside an aggregate that is not grouped (section 48)	`aggregates`
`01508`	an aggregate where none is allowed: in a WHERE, or inside another aggregate's argument (section 47), or, from `group-by-having`, in a GROUP BY key (section 48), or, from `nested-loop-join`, in an `ON` condition (section 67)	`aggregates`
`01509`	with SELECT DISTINCT, an ORDER BY key that is not an item of the select list (section 49)	`distinct`

Codes added in Indexes and the Optimizer

Code	Condition	Introduced in
`01601`	a second primary key: a CREATE TABLE that marks two columns `PRIMARY KEY`, or an ADD COLUMN marked `PRIMARY KEY`, since every table already has a key (section 53)	`primary-key-rowid`
`01602`	CREATE INDEX with a name an index already has, on any table (section 54)	`create-index`
`01603`	DROP INDEX or `index check` of a name no index has (section 54)	`create-index`
`01604`	a value of more than 255 bytes to put in an index (section 54)	`create-index`
`01605`	an INSERT or UPDATE that would give a row the value another row has in a unique index (section 57)	`unique-constraint`
`01606`	CREATE UNIQUE INDEX over a table where two rows already share a value (section 57)	`unique-constraint`
`01607`	ANALYZE of a table that does not exist (section 59)	`analyze-stats`
`01608`	`explain analyze` of anything but a SELECT (section 61)	`explain-analyze`

Codes added in Joins and Relations

Code	Condition	Introduced in
`01701`	a qualifier that names no FROM entry: `x.c` or `x.*` where no entry of the FROM is called `x`, including a table's own name once it has an alias (section 66)	`qualified-names`
`01702`	a bare column name that more than one FROM entry has (section 67)	`nested-loop-join`
`01703`	two FROM entries with the same name: the same table twice with no alias, or an alias used twice (section 67)	`nested-loop-join`
`01704`	an INSERT or UPDATE that gives a foreign key column a value no row of the parent table has (section 75)	`foreign-keys`
`01705`	`REFERENCES` a column that is neither its table's key nor the one column of a unique index (section 75)	`foreign-keys`
`01706`	`REFERENCES` a column of another type: an `INT` column referencing a `VARCHAR` one, or the other way round (section 75)	`foreign-keys`
`01707`	a DELETE of a parent row that a child row references through a `RESTRICT` foreign key, or an UPDATE that changes a target value a child row references (section 76)	`fk-delete-actions`
`01708`	DROP TABLE or TRUNCATE of a table another table's foreign key references, without `CASCADE`; DROP INDEX of the unique index a foreign key targets (section 76)	`fk-delete-actions`
`01709`	a scalar subquery handed up more than one row, met while running (section 77)	`subqueries-uncorrelated`
`01710`	a scalar or IN subquery whose select list is not exactly one column (section 77)	`subqueries-uncorrelated`

00108 is --join followed by anything but nl, inl, hash, merge or auto (section 67), from nested-loop-join; like 00107 it ends the program with status 1, and --join with nothing after it is 00102.

00109 is --join-memory followed by anything but a number from 1 to 1000000 (section 71), from hash-join-spill; it ends the program with status 1, and --join-memory with nothing after it is 00102.

From primary-key-rowid, 01103 is a key column that is not INT: a column marked PRIMARY KEY (section 53). A first column that is not INT is no longer an error. 00406, 00801, 01104 and 01503, which name the first column, name the table's key column (section 53).

From expressions, 00403 also covers an operator whose operands have types it does not take, and a WHERE that is not a condition (section 40). Its condition is the same: a value of the wrong type for where it is used.

Codes added in Sessions and Concurrency

Code	Condition	Introduced in
`01801`	a bad session prefix: `@` not followed by digits giving a number from 1 to 1000 and then a space (section 81)	`sessions`
`01802`	CHECKPOINT or VACUUM while another session has a transaction open (section 81)	`sessions`
`01803`	a line for a session whose statement is waiting for a lock (section 85)	`lock-waits`
`01804`	the statement's transaction was chosen as a deadlock victim and rolled back (section 86)	`deadlock`
`01805`	SET TRANSACTION while the session's transaction is open (section 88)	`isolation-levels`

Codes added in the Server track

Code	Condition	Introduced in
`01901`	a server flag cannot be understood: `--server` without `--port`, a port that is not a number from 0 to 65535, a `--wire` the program does not speak, a `--max-connections` or `--idle-timeout-ms` out of its range (section 97), or a server flag without `--server` (section 93)	`server-listen`
`01902`	the port cannot be listened on, for instance because it is in use (section 93)	`server-listen`
`01903`	over the PostgreSQL protocol, a statement other than COMMIT or ROLLBACK in a failed transaction (section 96)	`pg-errors-txn-status`
`01904`	over the PostgreSQL protocol, a message the server does not expect, or a broken StartupMessage (sections 94 and 96)	`pg-errors-txn-status`
`01905`	a protocol version the server does not speak (sections 94 and 96)	`pg-errors-txn-status`
`01906`	a connection over `--max-connections` (section 97)	`pg-connection-lifecycle`
`01907`	a session idle for `--idle-timeout-ms` (section 97)	`pg-connection-lifecycle`
`01908`	a parked statement cancelled by a CancelRequest (section 97)	`pg-connection-lifecycle`
`01909`	the server is shutting down (section 97)	`pg-connection-lifecycle`
`01910`	PREPARE of a name the session already uses (section 98)	`sql-prepare`
`01911`	EXECUTE or DEALLOCATE of a name the session does not use (section 98)	`sql-prepare`
`01912`	EXECUTE with a different number of values than the statement has parameters (section 98)	`sql-prepare`
`01913`	an EXECUTE value that is not of its parameter's type (section 98)	`sql-prepare`
`01914`	a parameter number that does not appear, below the highest one used (section 98)	`sql-prepare`
`01915`	Execute or Describe of a portal the session does not have (section 99)	`pg-extended`
`01916`	Bind with a different number of values than the statement has parameters (section 99)	`pg-extended`
`01917`	a format code that is not 0, text (section 99)	`pg-extended`
`01918`	a Parse type that is neither 0 nor the type the parameter is given (section 99)	`pg-extended`
`01919`	a new plan whose result has other columns than the prepared statement had (section 100)	`plan-cache`
`01920`	a `droid-pool` flag that cannot be understood (section 101)	`pool-session`
`01921`	a Query on the pooler's admin connection other than `SHOW POOLS` (section 101)	`pool-session`
`01922`	the pooler lost its server connection, or cannot open one (section 101)	`pool-session`
`01923`	a client waited `--query-wait-timeout-ms` for a server connection (section 102)	`pool-transaction`

What changes in `c-droid` today

Today	Condition	Becomes
`00200`	unknown option	`00101`
`00201`	missing argument for `-c`	`00102`
`00303` + `Syntax error` (two lines)	`.foo`	`00103`, one line
`00302` + `Syntax error in command`	missing closing quote	`00201`, one line
`00303` + `Syntax error in command`	unexpected character	`00202`, one line
`00301`	unrecognised statement keyword	`00301` (unchanged)
`00302`	syntax error	`00302` (unchanged)
`00302`	column count differs from value count	`00303`
no error	`insert ... values ('x', ...)` with a string for `id`	`00403`
`00400`	`serialize` without a valid INSERT	`00501`
`00201` + `00502` + `00301` + `Syntax error` (four lines)	`pager get` out of bounds	`00601`, one line
`00601`	`btree dump` of a page that does not exist	`00601` (same number, now the pager's)
`00601` then a success message	duplicate key	`00701`, and no success message
`Error: Row not found`	DELETE or UPDATE matching nothing	not an error (see 10)

4. Lexer — `tokenize <sql>`

One line per token, [<TYPE> - <text>], in source order. <text> is the token as typed; for strings, the content without the quotes.

Type	Matches
`KEYWORD_<UPPERCASE WORD>`	`select insert into values from where update set delete` (any case)
`IDENTIFIER`	a letter or `_`, then letters, digits, `_`
`NUMBER`	digits
`STRING`	`'...'` on one line; no escape sequences
`SYMBOL`	one of `, ( ) ; = * < >`

tokenize select ID from users; prints [KEYWORD_SELECT - select], [IDENTIFIER - ID], … On an error nothing but the error line is printed.

A word is read to its end before it is classified: selectivity and fromage are identifiers, not a keyword followed by the rest. A keyword keeps the case it was typed in: UPDATE prints [KEYWORD_UPDATE - UPDATE].
A number is digits. This part never needs decimals or negative literals, and no test uses them: an implementation may reject 1.5 and -1 with 00202 or read them as numbers. From expressions, - is a symbol and -1 is two tokens (section 40). Digits followed by letters are two tokens: 1abc is [NUMBER - 1], [IDENTIFIER - abc].
A string ends at the first quote after the opening one. '' is one empty string and prints [STRING - ]; 'it''s' is two strings, it and s.
Whitespace separates tokens and is never printed. A symbol ends the token before it, so id=1 is three tokens.
There is no end-of-input token. tokenize with nothing after it prints nothing.
The column in at col N counts from the start of the line, tokenize included. For 00201 it is the column of the opening quote; for 00202, of the character itself.

5. Parser — `ast <sql>`

Statement: INSERT|SELECT|UPDATE|DELETE
Table: <table>
Columns: [c1, c2]        (INSERT: the column list. SELECT: the select list, `[*]` for `*`. UPDATE: the assigned columns. Absent for DELETE)
Values: [1, 'dan']       (INSERT and UPDATE only. Strings in single quotes, numbers bare)
Where: <column> <op> <value>   (only when a WHERE clause is present)

Grammar accepted in this part (every statement ends with ;):

INSERT INTO t (c, ...) VALUES (v, ...);
SELECT * | c, ... FROM t [WHERE c op v];
UPDATE t SET c = v, ... [WHERE c op v];
DELETE FROM t [WHERE c op v];
op is =, < or >
v  is a NUMBER or a STRING

From expressions a WHERE holds an expression, and Where: prints it as section 40 says; for one comparison of a column with a value the line is the same as here.

ast only parses. It does not check table or column names.

The lines come in the order above, and a line is absent when the statement has no such part: no Where: without WHERE, no Columns: or Values: for DELETE.
Names are printed as typed (Users stays Users). Values are printed as in Values:, strings in single quotes and numbers as their digits, in Where: too.
The columns and values keep the order they were typed in; nothing is sorted or filled in.
ast is required to check the shape only. Unknown tables and columns, wrong types and numbers out of range have their own codes (section 3), required from the stages that introduce them; an implementation may report them in ast earlier, and no test sends them.
If the line cannot be tokenized, the lexer's error is the one printed and the parser does not run.
The column in at col N is the first character of the token the parser could not accept, counted from the start of the line, ast included. If the line ends too early, it is one past the last character. For 00301 it is the first word of the statement; for 00303, the ) that closes the value list.

6. Row format — `serialize <insert>` and `deserialize <hex>`

A row is exactly 60 bytes, always, whatever its values:

Bytes	Field	Encoding
0–3	`id`	unsigned 32-bit integer, least significant byte first (little-endian)
4–31	`name`	the string's UTF-8 bytes, then zero bytes up to the end of the field
32–59	`email`	the same, in its own 28 bytes

A string holds at most 27 bytes, so the last byte of each string field is always zero. The limit counts bytes, not characters. Byte order is a rule of the format, not of the machine: id 305419896 (0x12345678) is 78 56 34 12 on every computer.

[SERIALIZE] 01 00 00 00 64 61 6e 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 64 40 65 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

serialize insert into users (id, name, email) values (1, 'dan', 'd@e'); prints the one line above: [SERIALIZE] followed by the 60 bytes, each as two lowercase hex digits, separated by single spaces. The columns may be listed in any order; the bytes are the same.
Errors, each one line and no [SERIALIZE] line:
- a syntax error keeps the parser's code and column (serialize insert into; is 00302 at col 22: the column counts from the start of the line, serialize included);
- serialize with nothing after it, or with a statement that is not an INSERT: 00501;
- a value of the wrong type (a string for id, a number for name or email): 00403;
- an id outside 0..4294967295: 00404;
- a string longer than 27 bytes: 00405. It is never cut short to fit.
deserialize <hex bytes> reads bytes separated by spaces, each exactly two hex digits (either case), and prints three lines:

[DESERIALIZE] Field id = 1
[DESERIALIZE] Field name = dan
[DESERIALIZE] Field email = d@e

A string field is read up to its first zero byte; an empty one prints nothing after = . Fewer than 60 bytes are padded with zeros (new). A token that is not two hex digits (zz, 0, 0x01), or more than 60 bytes, is error 00502 and prints no [DESERIALIZE] line.

Constants: page size 4096 bytes, at most 1000 pages. In the pager stage pages live in memory only; from the persistence stage on they are backed by the database file.

Command	Output
`pager status`	`[PAGER] Status: total_pages=<n> cached=<m>` — `m` is how many pages are in memory
`pager alloc`	`[PAGER] Alloc: page <n> (4096 bytes, zeroed)` — pages are numbered from 0 in order
`pager get <n>`	`[PAGER] Get page <n>: CACHE_HIT` or `[PAGER] Get page <n>: CACHE_MISS (loaded from disk)`
`pager write <n> <text>` (new)	`[PAGER] Write page <n>: <k> bytes` — stores the text at the start of the page, followed by a zero byte
`pager read <n>` (new)	`[PAGER] Read page <n>: '<text>'` — the bytes up to the first zero byte

A fresh database has total_pages=0. Nothing allocates page 0 until a command needs it (see 9).

A page number is decimal digits. Anything else, -1 included, or no number at all, is 00104.
A page exists once it has been allocated. get, read or write of any other page is 00601, whether it is under the 1000-page limit or not, and allocates nothing.
The 1001st alloc is 00602 and allocates nothing: total_pages stays at 1000.
cached counts the pages held in memory. In the pager stage every allocated page is in memory, so cached equals total_pages and get always prints CACHE_HIT. CACHE_MISS first happens in the persistence stage, for a page of an existing file not read yet.
write takes the rest of the line after the page number and one space, spaces inside included. <k> is its length in bytes. The bytes after the zero byte are left as they were, so writing hi over hello world reads back hi. A line is at most 4096 bytes, so the text always fits in the page with its zero byte.
alloc gives a page of 4096 zero bytes, so read of a page nothing has written prints ''.

8. Persistence

From the persistence stage on, the pages of section 7 are backed by the database file: --db <path>, or droid.db in the working directory.

The file is the pages in order and nothing else: page n is the 4096 bytes at offset n × 4096. There is no header, no gap and no padding, so the file's size is always total_pages × 4096 once a session has ended. A page that was allocated and never written is 4096 zero bytes in the file.

Opening. The program opens the file before it prints anything, the welcome line included. A missing file is created, empty. total_pages is the file's size divided by 4096, and an empty file is a database with no pages. Opening reads no page, so a fresh session on an existing file starts with cached=0. Opening never changes the file.

Pages on first use. A page that is in the file but not in memory is read from the file the first time any command needs it. pager get of such a page prints [PAGER] Get page <n>: CACHE_MISS (loaded from disk); every later get of it prints CACHE_HIT. pager read and pager write load it the same way without saying so, and cached counts it from then on. A write to a page from the file changes only the bytes it writes (section 7): the rest of the page keeps what the file held.

Saving. When the session ends, by .exit, by the end of input, or after the one command of -c, every page that was allocated or written in the session is written to its place in the file. A session that only reads leaves the file byte for byte as it was. No page leaves memory before the session ends in this part, so the end of the session is the one moment that must save.

Limits. The 1000-page limit counts the pages in the file: with a file of 1000 pages, alloc is 00602. get, read and write of a page past the last one are 00601.

Files that cannot be used. Each ends the program before the session starts: the error line is the only output, no command is read, the file is not changed, and the exit status is 1.

Condition	Code
the path cannot be opened or created as a file (it is a directory, or its directory does not exist)	`00603`
the file's size is not a multiple of 4096	`00604`

Two paths never share anything: what one session writes to one file is not in another.

The B+Tree (section 9) keeps its root in page 0 and creates it only when the file has no pages. A file that already has pages already has its tree.

9. B+Tree

Test-mode constants, deliberately small so tests stay fast: a leaf holds at most 8 cells; an internal node holds at most 3 keys. (With 60-byte rows a real leaf would hold about 63 cells and an internal node about 500 keys.) A full leaf splits into halves of 4 and 5 cells, either way round, and a full internal node into 2 keys on the left and 1 on the right (see "Splitting a leaf" and "Splitting an internal node"). Which way a leaf divides is not part of the contract; the internal split is. Tests check the invariants below, and the exact shape of the internal split.

Invariants every tree must satisfy:

the root is page 0, always, and is created the first time any btree command or SQL statement needs the tree, and only when the file has no pages (section 8): creating it allocates page 0 as an empty root leaf, so total_pages goes from 0 to 1;
keys are in ascending order within every node (from the btree-search stage; in btree-leaf a new cell goes after the last one, and its tests insert keys in ascending order so either way passes); all leaves are at the same depth;
a separator key equals the smallest key in the subtree to its right;
no leaf has more than 8 cells, no internal node more than 3 keys;
following the leaves in order visits every key exactly once, ascending.

Node pages

A node is one page. Every integer is unsigned and little-endian, as in the row format (section 6). The first 14 bytes are the header, the same for both kinds of node:

Bytes	Field	Value
0	node type	`1` leaf, `2` internal (from `btree-leaf-split`). `0` is never a node
1	is root	`1` for page 0, `0` for every other node
2–5	parent page	the page of the internal node that points here; `0` for the root
6–9	count	a leaf's number of cells, an internal node's number of keys
10–13	link	a leaf's next leaf, `0` when there is none (the root is never anyone's next leaf); an internal node's right child

A leaf stores its cells from byte 14, one after the other with no gaps. A cell is 64 bytes: the key as a 4-byte integer, then the 60-byte row of section 6, whose own first 4 bytes are the same id. Cell i starts at byte 14 + 64 × i. The bytes after the last cell are not part of the node, whatever they hold; in a leaf that has only been inserted into, never split, they are zero.

An internal node (from btree-leaf-split) holds keys and the pages of its children, never rows. After the header come its count entries of 8 bytes each, one after the other with no gaps: the page of a child as a 4-byte integer, then a key as a 4-byte integer. Entry i starts at byte 14 + 8 × i. The header's link field is the right child, so a node with n keys has n + 1 children:

Child	Holds the keys
the child in entry 0	below key 0
the child in entry `i`	from key `i − 1` up to, not including, key `i`
the right child (the link field)	key `n − 1` and above

A key equal to a separator is in the subtree to its right. The bytes after the last entry are not part of the node either.

A real internal node of 4096 bytes would hold (4096 − 14) / 8 = 510 keys, rounded down. The tests use 3.

A new root leaf is therefore 01 01 followed by 4094 zero bytes.

A real leaf of 4096 bytes would hold (4096 − 14) / 64 = 63 cells, rounded down. The tests use 8, so a full leaf takes eight inserts, not sixty-three; the layout is the same.

Debug commands

Command	Output
`btree dump [page]` (default 0), leaf	`[BTREE] Page <p>: type=LEAF num_cells=<n>` then per cell `[BTREE] Cell <i>: key=<k> (60 bytes)`
`btree dump [page]`, internal	`[BTREE] Page <p>: type=INTERNAL num_keys=<n> right_child=<page>` then per key `[BTREE] Key <i>: key=<k> (child_page=<page>)`
`btree find <key>`	`[BTREE] Find key=<k>: FOUND (page=<p> cell=<i>)` then `[BTREE] Row: id=<id> name='<name>' email='<email>'`, or `[BTREE] Find key=<k>: NOT_FOUND`
`btree structure`	`[BTREE] Tree depth: <d>` then one line per node, depth-first, children left to right, indented two more spaces per level: `[BTREE] INTERNAL (page=<p> keys=[k1,k2])` and `[BTREE] LEAF (page=<p> cells=<n> keys=[k1,k2,...])`

btree dump of a page that was never allocated is 00601; a page number that is not digits is 00104, as for pager get. btree dump prints the cells in the order they are stored, cell 0 first.

btree find needs a key: btree find alone, a key that is not digits (abc, -1) and a key past 4294967295 are 00104, since none of them can be an id. A key that could be one and is not in the tree is NOT_FOUND, which is not an error. page and cell say where the key is at the moment of the search: cells move when a smaller key is inserted, so the cell of a key is its rank in the leaf, counting from 0. The Row: line prints each string as stored, without the zero bytes that pad it, so an empty string is ''. Like every btree command, btree find on a file with no pages creates the root first.

From the btree-search stage the leaf is sorted: a new cell goes at the position that keeps the keys ascending, and the cells after it move one cell towards the end. An INSERT whose id is already a key is 00701 and changes nothing: no cell is added or changed, and no success line is printed. Keys compare as unsigned integers, so 4294967295 is the largest.

INSERT prints Insert statement executed successfully (section 10) once the row is in the leaf. A ninth cell does not fit in a leaf: before btree-leaf-split that INSERT is 00702 and changes nothing, and from btree-leaf-split on the leaf splits instead.

Splitting a leaf (from `btree-leaf-split`)

A leaf that already holds 8 cells takes the ninth in its place among the keys and divides the nine in two: the lower keys stay on the left, the higher go to a new leaf on the right, 4 and 5 cells, either way round. The first key of the right leaf becomes the separator between the two in their parent. The split prints nothing of its own: the INSERT prints its usual line.

A leaf that is not the root keeps its page for the left half. The right half goes to one new page, and the parent gains the separator, with the new page as the child just after the old one.
The root leaf cannot keep its page, because the root is always page 0. The split allocates two new pages, the left half going to the first and the right half to the second, and page 0 becomes an internal node with one key, the separator: its entry points at the left page and its right child is the right page. On a file whose only page was the root, those are pages 1 and 2.
The right leaf's link is what the left leaf's link was, and the left leaf now links to the right one, so the leaves still chain in key order.
A split allocates those pages and no other, so total_pages counts the tree's nodes (plus any page pager alloc made). If the pages cannot be allocated, the INSERT is 00602 and changes nothing.
Every header stays true after a split: a node's parent field is the internal node that points at it (page 0 for both leaves of the first split), and only page 0 has is-root 1.
The duplicate check comes first. An INSERT of a key the tree already has is 00701, even into a full leaf, and splits nothing.

Splitting an internal node (from `btree-internal-split`)

A split below an internal node gives it one more key. An internal node that already holds 3 keys then has 4 keys and 5 children, one key too many, and splits too:

The middle key moves up to the parent. It is not kept in either half: an internal key is only a signpost, and unlike a leaf's separator, which stays in the right leaf as a cell, it has no row to keep.
The keys below it stay on the left and the keys above it go right: 2 keys on the left and 1 on the right, so the promoted key is always the third of the four. (The other way round would work as well; the contract fixes this one so that every later tree drawn in these pages is the one your engine builds.) Each child goes with the keys around it: the left node's right child is the child just before the promoted key, and the right node starts with the child just after it.
A node that is not the root keeps its page for the left half. The right half goes to one new page, and the parent gains the promoted key, with the new page as the child just after the old one. That can fill the parent, which then splits the same way, up to the root.
The root keeps page 0. Its halves go to two new pages, the left half to the first, and page 0 becomes an internal node with one key, the promoted one, over them. The tree is one level deeper, and this is the only way it gets deeper.
Pages are allocated from the bottom up: the new leaf's page first, then the page or pages of each internal split, in order up the tree.
Parent fields follow the children. Every node that moves under a new internal node has that node's page as its parent: the children of the right half, and when the root splits, every child it had. The leaves themselves, their cells and their links do not change.

In a tree of more than one leaf, btree find reports the page of the leaf that holds the key and the key's rank in that leaf as its cell, counting from 0.

A tree with only a root leaf has depth 1. DELETE removes the cell and nothing else in this part: leaves may become empty and separators may go stale; both are valid, and no page is freed (section 10, "UPDATE and DELETE").

How deep a tree may grow depends on the stage: before btree-leaf-split the root leaf is all there is, and before btree-internal-split the root internal node cannot split either, so the tree stops at depth 2 and the next insert that would need a fifth leaf fails with 00702. A test for one of those stages keeps its row count inside what the stage can hold. Any 20 rows, in any order, fit at depth 2: the split that would need a fifth leaf comes with four leaves, the full one holding 8 cells and each of the other three at least the 4 a split leaves, so 20 rows are already there before it. From btree-internal-split on nothing stops the tree growing but the page limit: an INSERT whose splits cannot allocate every page they need is 00602 and changes nothing.

The tree grows only at the root, which is why every leaf is always at the same depth. With the test-mode limits a tree of depth d holds at most 8 × 4^(d − 1) rows: 32 at depth 2, 128 at depth 3. So 33 rows or more are always depth 3 or deeper, and 129 or more depth 4 or deeper.

10. SQL results

SELECT, in table mode (the default):

id | name | email
1 | dan | d@e
(1 rows)

The header lists the selected columns (* means all three, in table order), separated by |, and each row gives the values of those columns in the same order: select email, id from users; prints email | id and then lines like d@e | 1. Rows come in ascending id order. The footer is always (<n> rows), also for 0 and 1. An empty table prints the header and (0 rows). A string prints as stored, without its padding zeros. A SELECT from a table that is not users is 00401, of a column users does not have 00402. SELECT is introduced by the btree-search stage; WHERE filters from the where-filter stage.

Other statements print Insert statement executed successfully, Update statement executed successfully, Delete statement executed successfully. From the result-set stage on the line ends with the affected count (new): Delete statement executed successfully (2 rows). An INSERT always affects one row: Insert statement executed successfully (1 rows). A statement that fails prints its error and no success line, in every stage.

UPDATE and DELETE without WHERE affect every row. Matching no rows is not an error (new): the statement succeeds with (0 rows). (This replaces Error: Row not found.)

WHERE compares one column with one value, with =, < or >. Numbers compare as numbers and text compares bytewise. The parser accepts all three from the parser stage, and a WHERE clause filters with all three wherever it filters; the index-scan stage adds no operator, only the IndexScan plan for = and ranges on id.

WHERE (from the `where-filter` stage)

select <columns> from users where <column> <op> <value>; prints the rows for which the comparison is true, and only those: the same header as without WHERE, the matching rows in ascending id order, and a footer that counts the rows printed. No match is not an error: the header and (0 rows). The WHERE column does not have to be in the select list.

id compares with a number, as unsigned 32-bit integers: where id > 5 includes 4294967295.
name and email compare with a string byte by byte, each byte an unsigned number, the way the bytes are stored. Case matters, and every capital letter comes before every small one: 'Bob' < 'ada' < 'bob'. A string that is the start of another is smaller than it: 'bo' < 'bob'. The empty string is smaller than every other string.
A string longer than 27 bytes is not an error in a WHERE clause. It compares like any other string, so = matches no row with it, since no stored string is that long.
The statement is checked before any row is read, in this order, and the first check that fails prints its code and nothing else: the table (00401), the columns of the select list (00402), the WHERE column (00402), the type of the value (00403: a string compared with id, or a number with name or email), and an id value past 4294967295 (00404).
From index-scan on the [EXEC] line of section 13 follows the footer.

UPDATE and DELETE (from the `delete-update` stage)

update users set <column> = <value>, ... [where ...]; and delete from users [where ...]; change every row the WHERE selects, or every row without one, and print Update statement executed successfully (<n> rows) or Delete statement executed successfully (<n> rows), <n> the rows changed, then the [EXEC] line of section 13. The WHERE selects rows exactly as it does for SELECT, and plans the same scan (section 12), under an Update (table=users) or Delete (table=users) node.

UPDATE replaces the values of the assigned columns in each selected row and keeps the others. The row keeps its key and its place: btree find reports the same page and cell before and after. id cannot be assigned, not even to the value it has: 00801.
DELETE removes each selected row's cell from its leaf; the cells after it in that leaf move one cell towards the start. Nothing else changes: no page is freed, no leaf is merged or removed, no separator changes. A leaf may end up empty, and btree structure shows it as LEAF (page=<p> cells=0 keys=[]); pager status counts the same pages as before. A later insert goes to the leaf its key leads to, empty or not, and a key that was deleted can be inserted again.
The statement is checked before any row changes, and the first check that fails prints its code and nothing else: the table (00401); then each assignment in the order written, its column (00402), id (00801), its value's type (00403) and length (00405); then the WHERE column (00402), its value's type (00403) and range (00404). A statement that fails changes nothing.
An UPDATE or DELETE that selects no row succeeds with (0 rows).

11. Output modes (from the `result-set` stage) (new)

.mode table and .mode csv choose how SELECT prints its rows, from that line to the end of the session. They print nothing. Every session starts in table mode, the mode of section 10, and every -c run is a session of its own. The mode's name is case-insensitive (.mode CSV works). .mode with no name, with a name that is not table or csv, or with anything after the name is 01001, and the mode stays what it was. .help does not change.

In CSV mode a SELECT prints a header line, the selected column names separated by ,, then one line per row, the values separated by ,, and no (n rows) footer. A SELECT that matches no row prints the header line alone.

A field is written as it is, unless it contains a , or a ". Then it is written between two ", and each " inside it is written twice: a,b is "a,b", say "hi" is "say ""hi""".
An empty string is an empty field: a row with only an id is 2,,.
Numbers are never quoted, and spaces are never a reason to quote: a b is a b.

Only SELECT's rows change with the mode. Every line that starts with [ (errors, [EXEC], [PLAN], debug output), the success lines of INSERT, UPDATE and DELETE and the lines of .help are the same in both modes.

12. Plans — `explain <sql>` (from the `volcano-executor` stage)

explain prints the plan and executes nothing.

[PLAN] <the statement as typed, without the final ;>
[PLAN]   └── <Node>
[PLAN]       └── <Child>

The first line is [PLAN] , one space, then the statement as it was typed after explain: the spaces after explain, the final ; and any spaces before it are dropped, and nothing else changes. Keywords keep their case, and spaces inside the statement stay as they were. The node lines follow, the top node first: [PLAN] , two spaces, └── and the node, and each level below is indented four more spaces. Nodes:

Node	When
`SeqScan (table=users)`	reading every row
`Filter (<column> <op> <value>)` (new: its own node)	a WHERE that the scan below cannot apply itself
`IndexScan (table=users, key=<k>)`	`WHERE id = <k>` (from the `index-scan` stage; before it, this is a Filter over a SeqScan)
`IndexScan (table=users, range: id > <k>)` or `id < <k>` (new)	a range on `id`
`Insert (table=users)`	INSERT, no child
`Update (table=users)`, `Delete (table=users)`	with the scan that finds the rows as child (from the `delete-update` stage)

Values render as in ast: strings quoted, numbers bare. The column is one of id, name and email. From expressions a Filter holds any expression, and an IndexScan is planned from the key bounds among the WHERE's conjuncts (section 40); every plan of this section stays the same.

explain checks the statement as running it would, and a statement that could not run prints its error and no [PLAN] line: the parser's codes, then 00401, 00402, 00403 and 00404 in the order of section 10. explain with nothing after it is 00901. explain reads no row and changes nothing, so it never reports what only running can find: an INSERT of an id the table already has still prints its plan.

13. Execution counter (from the `index-scan` stage) (new)

After the result of every SELECT the program prints [EXEC] rows_examined=<n>: the number of rows the scan at the bottom of the plan read from the tree and handed up. In table mode it follows the (n rows) footer; in CSV mode, the last row, or the header when there is none. UPDATE and DELETE print it too, after their success line, from the delete-update stage. A statement that fails prints its error and no [EXEC] line, and explain, which runs nothing, prints none.

A SeqScan hands up every row of the table, so it examines them all, whatever a Filter above it keeps: a full scan of 30 rows examines 30, and so does WHERE name = 'user3'.
An IndexScan finds its first row through the tree and hands up only the rows its condition keeps. WHERE id = 25 examines 1, or 0 when the key is absent. WHERE id > 25 over ids 1..30 examines 5, and WHERE id < 4 examines 3. The key it looks at to know the range has ended is not a row it hands up, and is not counted.
An empty table examines 0.

From index-scan on, a WHERE on id, with =, < or >, is planned as an IndexScan with no Filter above it (section 12). A WHERE on name or email is still a Filter over a SeqScan. The rows printed are exactly the same as with the plans of volcano-executor; only the plan and the counter differ.

14. Flexible Storage: general rules

Types. A column is INT, an unsigned 32-bit integer from 0 to 4294967295 as id has always been, or VARCHAR(n), a string of at most n bytes, n from 1 to 65535 (its length is stored in 2 bytes, section 15). The limit counts bytes, not characters.
The key. The first column of every table is its primary key and is an INT. Rows are kept in ascending key order, keys compare as unsigned integers, and no two rows share a key (00701).
The users table. Until create-table one table exists without being created, users, whose columns are id INT, name and email. Its strings hold at most 27 bytes, as in section 6, until the B+Tree stores variable-length rows; from varlen-btree-leaf they hold at most 1000 bytes, since a short string no longer pays for the room a long one could take. From create-table on no table exists until a CREATE TABLE makes it, and a test that needs users first runs create table users (id int, name varchar(1000), email varchar(1000));.
The row limit. From varlen-btree-leaf on a row is at most 1000 bytes once encoded (section 15), so that any four cells fit in one leaf (section 17). A row that would be larger is 00407, even when each of its strings is within its column's limit.
Statements are still at most 4096 bytes (section 1), so a line holding two strings of 1000 bytes is well within it. An implementation that reads shorter lines fails the tests of this part.
Values. An INT column takes a number and a VARCHAR column a string (00403). A column an INSERT leaves out is 0 if it is an INT and the empty string if it is a VARCHAR; the first column cannot be left out (00406). From nulls a column left out is NULL (section 41).
Names of tables and columns are compared as bytes, so they are case-sensitive: users and Users are two tables. Type names and keywords are not: int, INT and Int are one type.
Everything that said users or id in sections 10 to 13 says the table and its first column from create-table on: result headers list the table's columns in table order, plan nodes name the table (SeqScan (table=products)), and an IndexScan is planned for a WHERE on the first column, whatever its name (range: pid > 5).

15. Variable-length rows (from `varlen-rows`)

A row stores each string with its length in front of it, and no more bytes than the string has. Every integer is unsigned and little-endian, as in section 6.

Bytes	Field	Value
0–3	`row_size`	the length of the whole row in bytes, these 4 included
4–5	`column_count`	the number of columns the table has
6 on	`null_bitmap`	`ceil(column_count / 8)` bytes, all zero in this part
then	the columns, in table order	an `INT` is 4 bytes; a `VARCHAR` is its length in 2 bytes, then that many bytes

A users row with three columns has a 1-byte bitmap, so its fields start at byte 7, and it is 15 + len(name) + len(email) bytes long. (1, 'dan', 'd@e') is 21 bytes where section 6 takes 60:

15 00 00 00 03 00 00 01 00 00 00 03 00 64 61 6e 03 00 64 40 65

With both strings empty it is 15 bytes; with both at 27 bytes it is 69, more than the 60 of the fixed format: the length prefixes and the header are the price of storing only what is there. Nothing in this part sets a bit of the null bitmap and nothing reads one: the header holds it, and the column count, so that NULLs and added columns in later parts do not change the format again. A table of 9 columns has a 2-byte bitmap.

serialize <insert> prints three lines:

[SERIALIZE] Row size: 21 bytes
[SERIALIZE] Layout: row_size:4@0 column_count:2@4 null_bitmap:1@6 id:4@7 name_len:2@11 name:3@13 email_len:2@16 email:3@18
[SERIALIZE] Bytes: 15 00 00 00 03 00 00 01 00 00 00 03 00 64 61 6e 03 00 64 40 65

Layout: names every field in the order it is stored, as <field>:<size>@<offset>, separated by single spaces. An INT column c is c:4@<o>; a VARCHAR column c is c_len:2@<o> then c:<n>@<o + 2>, and an empty string is still listed, as c:0@<o>.
Bytes: is the row, each byte as two lowercase hex digits separated by single spaces.
The columns of the INSERT may be listed in any order and may leave columns out (section 14): the row is the same. serialize checks its statement as the INSERT would, with the codes of sections 5, 6 and 14, and never reads the tree, so an id the table already has is not an error. From varlen-btree-leaf a row larger than 1000 bytes is 00407; from create-table serialize takes an INSERT into any table.

deserialize <hex bytes> reads the bytes as a row of users and prints one line per column, as in section 6:

[DESERIALIZE] Field id = 1
[DESERIALIZE] Field name = dan
[DESERIALIZE] Field email = d@e

The bytes are read as in section 6. A token that is not two hex digits, or more than 1000 bytes, is 00502. Nothing is padded any more.
Bytes that are not a row of users are 00503, with no [DESERIALIZE] line: no bytes at all, fewer bytes than the header and fields need, a row_size that is not the number of bytes given, a column_count that is not the table's, a string whose length runs past the end of the row or past its column's limit, and bytes left over after the last field.
A row whose null bitmap is not all zero is not something this part defines; no test sends one. From nulls the bitmap marks NULL columns (section 41).
From create-table on, deserialize still reads a row of users, and is 00401 when the file has no users table.

16. Slotted pages (from `slotted-page`)

A slotted page holds records of any length. A directory of slots grows from the front of the page, the records grow from its end, and the free space is the gap between them. A record is named by its slot, and a slot keeps its number while the record moves.

The header is 16 bytes: the node header of section 9, with the same fields in the same places, and one field after it. Every integer is unsigned and little-endian.

Bytes	Field	Value
0	page type	`3` for a page made by `page init`; `1` for a leaf from `varlen-btree-leaf` (section 17)
1	is root	`0` on a page made by `page init`
2–5	parent page	`0` on a page made by `page init`
6–9	slot count	the number of slots, deleted ones included
10–13	link	`0` on a page made by `page init`
14–15	record start	the offset of the lowest record; `4096` when the page has none

Slot i is the 4 bytes at 16 + 4 × i: the record's offset in the page, then its length, 2 bytes each. A deleted slot is offset 0 and length 0; no record can start at 0, where the header is. The page's free space is every byte no header, slot or live record uses:

free_space = 4096 − 16 − 4 × slot_count − the lengths of the live records

It counts the bytes a deleted record leaves behind (a hole) as soon as the record is deleted, before anything moves.

Command	Output
`page init <n>`	`[PAGE] Init page <n>: free_space=4080`
`page insert <n> <text>`	`[PAGE] Insert page <n>: slot=<i> offset=<o> length=<len>`
`page read <n> <slot>`	`[PAGE] Read page <n> slot <i>: '<text>'`
`page delete <n> <slot>`	`[PAGE] Delete page <n>: slot=<i>`
`page compact <n>`	`[PAGE] Compact page <n>: free_space=<f>`
`page dump <n>`	`[PAGE] Page <n>: type=SLOTTED slots=<k> free_space=<f>`, then for each slot from 0, `[PAGE] Slot <i>: offset=<o> length=<len>` or `[PAGE] Slot <i>: deleted`

page init works on any allocated page and makes it an empty slotted page: the whole page is zeroed, then the header above is written. The other commands need a page page init made: any other page is 00606.
A page that was never allocated is 00601. A page or slot number that is not digits, a missing argument and an empty text are 00104. A slot past the last one, or deleted, is 00607 for read and delete.
page insert takes the rest of the line after the page number and one space, as pager write does (section 7), and stores its bytes with no zero byte after them: the record's length is the text's length in bytes.
Which slot. A new record takes the lowest deleted slot; when there is none it takes a new slot at the end of the directory.
Whether it fits. It fits when its length, plus 4 if it needs a new slot, is at most free_space. A record that does not fit is 00605, and the page is unchanged.
Where it goes. A record is written just below the record start: its offset is record start − length, and it becomes the new record start. When that would overlap the slot directory, the page is compacted first, as page compact does, and then written the same way. So the first record of a page ends at byte 4096.
page delete marks the slot deleted and nothing else: the record's bytes stay where they were, the record start does not move, the slot count does not change, and the other slots keep their numbers and offsets. free_space grows by the record's length.
page compact moves the live records so they sit together at the end of the page in slot order: the lowest live slot's record ends at byte 4096, the next one's just below it, and so on. Every slot keeps its number and length, deleted slots stay deleted, the record start becomes the lowest record's offset, and free_space does not change.
page read prints the record's bytes between single quotes, as pager read does.
Slotted pages are pages of the pager, so they are saved and reopened as in section 8.

A worked page, from page init 1:

Command	Output
`page insert 1 alpha`	`slot=0 offset=4091 length=5`
`page insert 1 bravo charlie`	`slot=1 offset=4078 length=13`
`page insert 1 delta`	`slot=2 offset=4073 length=5` — `free_space` is now `4080 − 12 − 23 = 4045`
`page delete 1 1`	slot 1 is deleted; `free_space` is `4058`; slots 0 and 2 have not moved
`page compact 1`	slot 0 stays at `4091`, slot 2 moves to `4086`; `free_space=4058`
`page insert 1 echo`	`slot=1 offset=4082 length=4`: the deleted slot is taken again

17. B+Tree leaves on slotted pages (from `varlen-btree-leaf`)

A leaf is a slotted page of type 1. Its header is the one of section 16, with the meanings of section 9: is root, parent page, the count is its number of cells, the link is its next leaf. Slot i is cell i, and the slots are in ascending key order. A cell is the key as a 4-byte integer followed by the row of section 15, so its length is 4 + row_size. Where a cell's bytes sit in the record area is not part of the contract; only the order of the slots is. A leaf has no deleted slots: deleting a cell removes its slot. A new root leaf is 01 01, zeros up to byte 14, 00 10 (a record start of 4096), and zeros to the end of the page.

Internal nodes are those of section 9, unchanged: the same 14-byte header, 8-byte entries, and at most 3 keys in test mode. Only leaves change.

Capacity is in bytes. The limit of 8 cells is gone: a new cell fits in a leaf when its length plus 4 for its slot is at most the leaf's free_space, counted as in section 16. With rows of 21 bytes a leaf holds 4080 / 29 = 140 of them, rounded down. The row limit of section 14 means any four cells fit in an empty leaf (4 × (4 + 1000 + 4) = 4032, and 4080 are free), so a split always leaves two halves that fit.

Real engines size leaves the same way. The internal-node limit of 3 keys stays a test-mode constant: a real internal node would hold 510, and a tree of depth 3 would need tens of thousands of rows instead of a few hundred.

btree dump of a leaf now prints how full it is, and each cell's row size:

[BTREE] Page <p>: type=LEAF num_cells=<n> free_space=<f>
[BTREE]   Cell <i>: key=<k> (<row_size> bytes)

btree dump of an internal node, btree find and btree structure print what section 9 says.

Inserting. A cell that fits is placed in the leaf and its slot goes where the keys stay in order. A cell that does not fit splits the leaf, with the page, link, parent and allocation rules of section 9. Where the cells divide:

in varlen-btree-leaf, anywhere that leaves both halves non-empty and each fitting its page, dividing by count included;
from varlen-btree-split, by bytes: the cells, in key order with the new one among them, divide at the point where the two halves' used bytes, each cell's length plus 4 for its slot, are as close as they can be. When two points are equally close, either. The halves then differ by at most one cell and its slot.

00702 does not happen to a leaf in this part: a leaf that is full splits.

Deleting a row removes its cell's slot, and the slots after it move one place towards the start. free_space grows by the cell's length plus 4 at once, whether the bytes move or not. Nothing else changes, as in section 10: no leaf is merged and no page is freed.

Updating a row keeps its key. When the new cell fits in its leaf once the old one is gone, it stays in that leaf at the same cell. When it does not, the leaf splits as for an INSERT of the new cell, and btree find may report another page and cell. A new row larger than 1000 bytes is 00407. A statement that fails changes nothing (section 3).

18. The file header (from `file-header`)

Page 0 stops being a tree's root and becomes the file's header. Every integer is unsigned and little-endian.

Bytes	Field	Value
0–7	magic	the 8 ASCII bytes `droid db`: `64 72 6f 69 64 20 64 62`
8–11	version	`1`
12–15	page size	`4096`
16–19	root	the root page of the file's first tree: `users` until `create-table`, the catalog from `create-table` on (section 19); `0` while there is none
20–4095		zero

Created on first allocation. A file with no pages gets its header the first time anything allocates a page: page 0 becomes the header, and then the page that was asked for is allocated. pager alloc on an empty file prints [PAGER] Alloc: page 1 (4096 bytes, zeroed) and leaves total_pages=2. Opening still never changes the file, and a session that allocates nothing leaves an empty file empty.
Checked on open. Opening a file that has pages reads page 0 and checks it before the welcome line: a wrong magic, a version other than 1 or a page size other than 4096 is 00608, handled as section 8's files that cannot be used. So a session on an existing file starts with cached=1.
A tree's root is where its record says. The users tree's root is the page in the header's root field. It is created the first time a command needs the tree and the field is 0: the root leaf is allocated, after the header if the file had no pages, and its page is written to the field. On a fresh file the first SQL statement makes page 0 the header and page 1 the root.
The root never moves. Every rule of section 9 that says page 0 means the root's page: it is the only node with is-root 1, it has parent 0, and when it splits it keeps its page and its halves go to new pages. A tree's recorded root page never changes.
db header prints the header in one line, and creates it first on a file with no pages:

[DB] Header: magic='droid db' version=1 page_size=4096 root=<p>

Tree commands name a table. btree structure [table] and btree find [table] <key> work on that table's tree, and on users without one; a word that is not digits is a table name. So btree find abc and btree find -1 look for a table and are 00401 when there is none, where section 9 made them 00104; with a table named, a missing key or one that cannot be an id is still 00104: btree find users, btree find users abc, btree find users -1. btree dump [page] without a page dumps the users root. btree dump of a page that is not a node, the header included, is 00703.

19. Tables and the catalog (from `create-table`)

CREATE TABLE t (c type, ...);
type is INT or VARCHAR(n)

create and table are keywords: tokenize prints [KEYWORD_CREATE - create] and [KEYWORD_TABLE - table]. Type names are identifiers, and the parser takes any identifier as a type, with an optional (<number>) after it; which types exist is checked after parsing. ast prints:

Statement: CREATE TABLE
Table: products
Columns: [id int, title varchar(40), price int]

Each column is its name, one space and its type as typed, with (n) written without spaces. A table has at least one column: create table t (); is 00302.

A CREATE TABLE is checked before anything changes, and the first check that fails prints its code and nothing else: the table does not exist yet (01101); then each column in the order written, its type (01102) and its name, not used by an earlier column (00408); then the first column is INT (01103); then the catalog row fits (00407). It prints Create table statement executed successfully, with no count. explain prints its plan as CreateTable (table=<t>) and creates nothing.

The catalog is a B+Tree like any table's, rows and leaves as in sections 15 and 17, whose root is the header's root field. Its rows have four columns, id INT, name VARCHAR(65535), root INT and columns VARCHAR(65535):

id is the key: 1 for the first table created, then one more than the largest id in the catalog;
name is the table's name as typed;
root is the page of the table's root, which never changes (section 18);
columns is the column list as catalog list prints it: each column's name as typed, one space and its type in capitals, INT or VARCHAR(n), separated by , .

The catalog is not a table: no SQL statement can name it. Its root is allocated by the first CREATE TABLE, after the header if the file had no pages, and each CREATE TABLE then allocates its table's root leaf before writing the catalog row. So on a fresh file the header is page 0, the catalog page 1, the first table's root page 2 and the second's page 3.

catalog list prints the tables in id order:

[CATALOG] Tables: 2
[CATALOG]   users root=2 (id INT, name VARCHAR(1000), email VARCHAR(1000))
[CATALOG]   products root=3 (id INT, title VARCHAR(40), price INT)

A file with no tables prints [CATALOG] Tables: 0 and nothing else.

Rows of a table are encoded by its columns (section 15), and SELECT, INSERT, UPDATE, DELETE, explain, serialize and the btree commands work on any table, with the names of section 14. The Row: line of btree find gives each column as <name>=<value>, strings between single quotes: [BTREE] Row: id=1 title='lamp' price=30.

Schema validation (from schema-validation). Every statement is checked against the catalog after it parses and before any row is read, for every table, with the codes of section 3 as section 14 extends them. The parser's codes come first, so a value list of the wrong length is 00303 whatever the table. Then, in this order, the first check that fails is the one reported:

Statement	Checks, in order
INSERT, and `serialize`	the table (`00401`); then each column in the order written: its name is a column of the table (`00402`) and not one named earlier in the list (`00408`), then its value's type (`00403`), range (`00404`) and length (`00405`); then the first column is given (`00406`); then the row fits in 1000 bytes (`00407`)
SELECT	the table (`00401`); the columns of the select list (`00402`); the WHERE column (`00402`), its value's type (`00403`) and range (`00404`)
UPDATE	the table (`00401`); then each assignment in the order written: its column (`00402`), not assigned earlier in the statement (`00408`), not the first column (`00801`), then its value's type (`00403`), range (`00404`) and length (`00405`); then the WHERE as for SELECT
DELETE	the table (`00401`); the WHERE as for SELECT

A column belongs to its table: a column of another table is 00402.
A value's range is 0..4294967295 for every INT column, and its length is the n of its column's VARCHAR(n), counted in bytes.
A string in a WHERE that is longer than its column's n is not an error, as in section 10: it compares like any other string, so = matches no row with it.
A statement that fails prints its code and nothing else and changes nothing. explain runs the same checks and prints no [PLAN] line for a statement that fails them. What only running can find is still not a check: an INSERT of a key the table has, or an UPDATE whose new row would pass 1000 bytes (section 17).

20. Page checksums (from `page-checksums`)

The last 4 bytes of every page, bytes 4092 to 4095, are its trailer: the CRC32 of bytes 0 to 4091 of that page, little-endian. Every page has one, whatever it holds: the header, B+Tree nodes, slotted pages, pages that only pager alloc and pager write touched, and, from Memory and Space, free pages and overflow pages.

CRC32 is the checksum of zlib, PNG and Ethernet (polynomial 0xEDB88320, reflected, starting from 0xFFFFFFFF and inverted at the end). The CRC32 of the ASCII bytes 123456789 is 0xCBF43926: check yours against it before anything else.

Written with the page. Whenever a page is written to the file, its trailer is computed from the bytes the page holds at that moment. Nothing checks or prints the trailer of a page in memory: only the file's copy has to be right.
Checked when read. Whenever a page is read from the file (section 8, "pages on first use"), its bytes 0 to 4091 are checked against its trailer before anything uses them. A page that does not match is 00609: the command that needed it prints that line and nothing else, changes nothing and prints no rows. The page is not kept in memory, so the next command that needs it reads it and checks it again. Whether the good pages that command read stay in memory is not part of the contract.
A statement that meets a bad page after it has changed rows. An UPDATE or DELETE that spans several leaves may already have changed some when it reaches a damaged one. Undoing those changes is what ROLLBACK is for, and it arrives with Transactions and Recovery; until then what such a statement leaves behind is not defined, and no test sends one. A statement whose first page, or whose only table page, is bad changes nothing.
Page 0 at open. Opening checks the magic, the version and the page size first (00608), then page 0's trailer: a mismatch is 00609, handled as section 8's files that cannot be used.
The page ends at 4092. Nothing but the trailer may use the last 4 bytes, so every layout that ran to the end of the page now ends at byte 4092. A slotted page's records end at 4092, its record start is 4092 when it has none, and its free space is counted from there:

free_space = 4092 − 16 − 4 × slot_count − the lengths of the live records

page init prints free_space=4076, a new root leaf is 01 01, zeros up to byte 14, fc 0f (a record start of 4092) and zeros up to the trailer, and a leaf holds 4076 / 29 = 140 rows of 21 bytes, rounded down. Any four cells of the largest size still fit in an empty leaf (4 × (4 + 1000 + 4) = 4032). The header's fields, internal nodes and pager write never reach byte 4092, so they do not change.

db verify checks every page of the file and prints one line, then one line per page that does not match, in ascending page order:

[DB] Verify: pages=<total_pages> bad=<k>
[DB]   Page <p>: checksum mismatch

A page that is already in memory counts as good: it was checked when it was read, or made in this session. Every other page is read from the file and checked as any read is, so a good page stays in memory afterwards, unless a smaller pool has to evict it (section 22), and a bad one does not. db verify changes nothing. On a file with no pages it prints [DB] Verify: pages=0 bad=0 and creates nothing.

The trailer is detection, not repair: the program never rewrites a page it found bad, and nothing uses its bytes.

21. What Flexible Storage changes

Each change is made by one stage, which retires the earlier cases that checked the old contract, by name, in the manifest. Every other earlier case carries on and must still pass.

Earlier contract	Section	Changed by	Now
a row is 60 bytes; `serialize` prints them as one hex line; `deserialize` pads short input	6	`varlen-rows`	section 15
a leaf is at most 8 cells of 64 bytes from byte 14; `btree dump` prints `(60 bytes)`	9	`varlen-btree-leaf`	section 17
a string holds at most 27 bytes, so 28 is `00405`	1, 6	`varlen-btree-leaf`	1000 bytes for `users` (section 14)
a full leaf splits into 4 and 5 cells	9	`varlen-btree-leaf`	any split that fits, then by bytes from `varlen-btree-split` (section 17)
an UPDATE keeps its row's page and cell	10	`varlen-btree-leaf`	unless the new row no longer fits its leaf (section 17)
page 0 is the root of the only tree	8, 9	`file-header`	page 0 is the header; roots are recorded (section 18)
opening reads no page; the first `pager alloc` of a file is page 0	7, 8	`file-header`	section 18
`btree find <word>` with a word that is not digits is `00104`	9	`file-header`	the word is a table name, `00401` when there is no such table (section 18)
a file of zeroed pages opens	8	`file-header`	page 0 must be a header, `00608` (section 18)
`users` exists without being created	1	`create-table`	tests create it first (section 14)
`create` and `table` are identifiers	4	`create-table`	keywords (section 19)
a slotted page's records end at byte 4096; `page init` prints `free_space=4080`; a leaf holds 4080 bytes	16, 17	`page-checksums`	they end at 4092, before the trailer: `free_space=4076` (section 20)
a page in the file is its bytes and nothing else; any file of whole pages with a good header opens	8, 18	`page-checksums`	every page carries a trailer, checked on read (`00609`); a file written without one does not open (section 20)

22. Memory and Space: general rules

The buffer pool. The pages in memory are the buffer pool, and it holds at most a fixed number of them, its frames. --cache-pages <n> sets that number, from 1 to 1000, for the session: droid --db x.db --cache-pages 3. It may come before or after --db and -c. Without it the pool has 1000 frames, as many as the file can have pages, so no page ever has to leave memory and everything earlier behaves exactly as before. A value that is not digits, 0 or past 1000 is 00106; the flag with nothing after it is 00102. Both end the program before the database file is opened, so they come before any error about the file.
Requests. A command requests a page each time it needs the page's bytes. A request for a page in the pool is a hit. Any other request is a miss: the page is read from the file, checked (section 20) and put in the pool. A page the file does not have yet, made by an allocation, comes into the pool without a request, since there is nothing to read.
Making room. A page that comes into a full pool takes the frame of a page that leaves it: an eviction. A page that changed in memory since it was read or last written is dirty, and is written to the file before its frame is reused. Which page leaves is free until clock-eviction (section 25), except that a pinned page never leaves (section 24).
A page that fails its checksum (section 20) is a miss and a read like any other, and makes room like any other: a page evicted for it stays evicted, and the frame it would have taken is left empty.
Saving is as in section 8: when the session ends every dirty page is written. A page that left the pool earlier was written then, so the file ends up the same whatever the pool's size.
pager status is unchanged: cached counts the pages in the pool, never more than its frames.
Small pools and SQL. The pager commands work with any pool, down to one frame. Every other command, SQL included, is only required to work with a pool of at least 16 frames, and only from pin-unpin: before pins, nothing stops a statement's own pages from leaving while it works, so in io-counters SQL is only run with the default pool. With fewer it may need more pinned pages at once than the pool holds and fail with 01201, and what it changed before that is not defined; no test sends one.
SQL results do not change in this part, with one exception, overflow pages, which lift the row limit (section 29). What changes is what the counters, the debug commands and the file show.

23. Counting I/O (from `io-counters`)

pager stats prints the pool's counters, counted from the start of the session:

[PAGER] Stats: reads=<r> writes=<w> hits=<h> misses=<m> evictions=<e>

Counter	Counts
`reads`	pages read from the file
`writes`	pages written to the file
`hits`	requests for a page already in the pool
`misses`	requests for a page not in the pool
`evictions`	pages that left the pool to make room for another

Opening a file that has pages reads page 0 (section 18): a session on such a file starts with reads=1 misses=1. A new file, or an empty one, starts with every counter at 0.
Every miss is one read and every read is a miss, so reads and misses are always equal. A real engine reads ahead of its misses and they differ; this one does not.
pager flush writes every dirty page to the file and prints [PAGER] Flush: <k> pages written. The pages stay in the pool, no longer dirty, and a page that is not dirty is not written, so a second pager flush prints 0 pages written.

Which counts are exact. Opening, and these commands, request exactly the pages they name, once each, and nothing else:

Command	Requests
`pager get <n>`, `pager read <n>`, `pager write <n> <text>`	page `n`, once
`pager pin <n>` (from `pin-unpin`)	page `n`, once
`pager stats`, `pager status`, `pager flush`, `pager frames`, `pager unpin <n>`, `pager clock`	nothing

pager write makes its page dirty, and so does pager alloc for the page it makes; get, read and pin do not. So the counters after a session of these commands are exact as long as no eviction had a choice to make: while no page is evicted, or when only one page in the pool is unpinned, as with --cache-pages 1. From clock-eviction (section 25) the victim is fixed, and they are exact with any pool. Every other command, pager alloc and pager free included, requests whatever pages it needs, as many times as it likes: after those, tests check only what is true of any engine that follows the rules above, such as reads being at least the number of different pages a statement had to read.

With the default pool no page is evicted, and no page is read twice in one session (except one that failed its checksum, which is never kept), so reads never exceeds the largest total_pages of the session.
A full scan of a table reads every leaf of its tree. With a pool too small to keep them, a second scan reads them again.

24. Pinning (from `pin-unpin`)

A page is pinned while a command uses it, and a pinned page never leaves the pool. Each page has a pin count: a request pins the page, and the command unpins it when it is done with it. Only a page with a pin count of 0 can be evicted.

Command	Output
`pager pin <n>`	`[PAGER] Pin page <n>: pin=<k>`, `k` the count after it
`pager unpin <n>`	`[PAGER] Unpin page <n>: pin=<k>`
`pager frames`	`[PAGER] Frames: <used> of <frames>`, then one line per page in the pool, in ascending page order: `[PAGER] Page <p>: pin=<k> dirty=<0 or 1>`

pager pin requests the page and leaves it pinned when the command ends: it stays pinned until as many pager unpin of it, or the end of the session. Pins add up: pinning a page twice needs two unpins.
pager unpin of a page whose count is 0, in the pool or not, is 01202 and changes nothing. A page that was never allocated is 00601, for both commands, and a page number that is not digits is 00104.
No pin outlives its command. After every command, whether it succeeded or failed, the only pinned pages are those pager pin pinned and pager unpin has not yet unpinned, each with that count. After a failed INSERT, a SELECT on a deep tree or a statement that stopped on an error, pager frames shows pin=0 on every page nobody pinned by hand.
A full pool of pinned pages. When a page must come into the pool, the pool is full and every page in it is pinned, the command is 01201: it prints that line, the page does not come in, and nothing changes.
dirty is exact after the pager commands of section 23; after anything else it only has to be 1 on a page whose bytes changed since the file last had them.

25. Clock replacement (from `clock-eviction`)

From this stage the page that leaves the pool is chosen by the clock, exactly. The frames are numbered from 0 to frames − 1, each has a reference bit, and a hand points at one frame. The pool starts with every frame empty and the hand at frame 0.

A hit sets the reference bit of the page's frame to 1.
A page coming in goes to the lowest-numbered empty frame when there is one, with its bit set to 1. The hand does not move.
When no frame is empty, the hand sweeps. At each frame: a pinned page is passed over and its bit left as it is; a bit of 1 is set to 0 and the hand moves on; a bit of 0 on an unpinned page makes that page the victim, and the hand moves one frame past it. The new page takes the victim's frame with its bit set to 1. Moving on from the last frame goes to frame 0. The hand has moved once a victim is chosen, even when reading the new page then fails (section 22): the victim has left, the frame stays empty, and the hand stays one past it.
Every page pinned: 01201 (section 24), and the hand stays where it was.

pager clock prints the hand, then every frame in order:

[PAGER] Clock: hand=<i> frames=<n>
[PAGER]   Frame <i>: page=<p> ref=<0 or 1> pin=<k>
[PAGER]   Frame <i>: empty

A worked sequence, on a file of 5 pages with --cache-pages 3. Opening reads page 0, so frame 0 holds page 0 with its bit at 1 before the first command:

Command	What happens	Frames 0, 1, 2 after it	Hand
`pager get 1`	miss, lowest empty frame	0 (ref 1), 1 (ref 1), 2 empty	0
`pager get 2`	miss, lowest empty frame	0 (1), 1 (1), 2 (1)	0
`pager get 3`	miss, full: frames 0, 1, 2 are cleared, frame 0 is the victim	3 (1), 1 (0), 2 (0)	1
`pager get 1`	hit	3 (1), 1 (1), 2 (0)	1
`pager get 4`	miss: frame 1 is cleared, frame 2 is the victim	3 (1), 1 (0), 4 (1)	0

Page 2 leaves, not page 1: page 1 was used again, and the clock gave it a second chance. Evicting in the order pages came in would have thrown out page 1.

Real engines approximate "least recently used", because true LRU means updating a list on every hit. The clock needs one bit per frame and does no work on a hit but set it.

26. The free list (from `free-list`)

A page that is no longer needed goes on the free list, and allocation takes from the list before it makes the file longer. The list lives in the file: its head and length are in the header, and each free page holds the number of the next.

The header (section 18) gains two fields. A file with no free pages has zeros there, so every header written before this stage is already right:

Bytes	Field	Value
20–23	free list head	the first free page; `0` when there is none (page 0 is never free)
24–27	free pages	how many pages are on the list

A free page is page type 4 at byte 0, the next free page at bytes 10 to 13 (0 for the last), the same place a node keeps its link, and zeros everywhere else up to the trailer.

Command	Output
`pager free <n>`	`[PAGER] Free: page <n>`
`db freelist`	`[DB] Free list: pages=<k> chain=[<p1>,<p2>,...]`, the pages from the head, in list order; `pages=0 chain=[]` when it is empty

Freeing makes the page a free page whose next is the old head, and puts it at the head: the last page freed is the first reused. The count goes up by 1.
Allocating, by pager alloc or by anything that needs a page, takes the head when the list is not empty: the head becomes its next, the count goes down by 1, the page is zeroed, and pager alloc prints [PAGER] Alloc: page <n> (4096 bytes, zeroed) with its number. Only an empty list makes the file longer. So total_pages and the file's size never go down in this part, except by VACUUM (section 30).
pager free of a page that was never allocated is 00601, checked first, so pager free 0 on a file with no pages is 00601; of page 0, 01204; of a page already on the list, 01203. Each changes nothing. Pins do not matter to pager free: a pinned page is freed and stays pinned. pager free does not check what the page holds: freeing a page a tree still uses breaks the tree, and no test does it.
A free page is not a node and not a slotted page: btree dump of it is 00703 and a page command on it 00606. pager get, read and write work on it as on any page.
db header prints the line of section 18, unchanged: the free list is shown by db freelist. On a file with no pages db freelist prints [DB] Free list: pages=0 chain=[] and creates nothing.
When one statement frees several pages, the stage that adds the statement says the order in which they join the list: DROP TABLE and TRUNCATE in section 27, merges and a shrinking root in section 28. Where it says nothing, the order is not part of the contract.

27. DROP TABLE and TRUNCATE (from `drop-table`)

DROP TABLE [IF EXISTS] t;
TRUNCATE [TABLE] t;

drop, truncate, if and exists are keywords: tokenize prints [KEYWORD_DROP - drop] and so on. ast prints:

Statement	`ast`
`drop table t;`	`Statement: DROP TABLE`, `Table: t`
`drop table if exists t;`	`Statement: DROP TABLE IF EXISTS`, `Table: t`
`truncate table t;`, `truncate t;`	`Statement: TRUNCATE TABLE`, `Table: t`

DROP TABLE frees every page of the table's tree, and from overflow-pages its overflow pages, and removes its row from the catalog. It prints Drop table statement executed successfully, with no count. The table no longer exists: any statement that names it is 00401, and a CREATE TABLE may use its name again. The next CREATE TABLE's id is one more than the largest left in the catalog (section 19).
TRUNCATE removes every row and keeps the table: it frees every page of the tree except the root, which becomes an empty leaf on the same page, so the catalog row does not change. It prints Truncate table statement executed successfully, with no count.
The order pages are freed in is post-order: for an internal node, each child's pages, children in key order (the right child last), then the node itself. Each page goes on the head of the free list as section 26 says, so after a DROP the old root is the head and the leftmost leaf is the tail. TRUNCATE frees in the same order and stops before the root. For the tree
```
[BTREE] INTERNAL (page=2 keys=[5])
[BTREE]   LEAF (page=3 cells=4 keys=[1,2,3,4])
[BTREE]   LEAF (page=4 cells=4 keys=[5,6,7,8])
```
DROP frees 3, 4, 2, and db freelist prints pages=3 chain=[2,4,3]; TRUNCATE frees 3 and 4, and prints pages=2 chain=[4,3].
A table that does not exist is 00401 for both, and changes nothing. With IF EXISTS, DROP of a table that does not exist succeeds with the same line and changes nothing.
explain prints DropTable (table=<t>) or TruncateTable (table=<t>) and changes nothing. It checks as running would, so a table that does not exist is 00401 and no plan, except under IF EXISTS, where the plan is printed.

28. Borrow and merge (from `btree-merge`)

From this stage a DELETE, or an UPDATE that makes rows smaller, keeps every node other than the root at least a quarter full, and the tree gets shorter when it can.

Minimum fill. A leaf is below minimum when its used bytes, each cell's length plus 4 for its slot, are less than 1019, a quarter of the 4076 an empty leaf has free. An internal node is below minimum when it has no key left, only one child. The root has no minimum.

A node below minimum is fixed with one sibling: the node just before it under the same parent, or, for a parent's first child, the node just after it.

Merge when the two fit in one node: for leaves, when their used bytes together are at most 4076; for internal nodes, when their keys and the separator between them make at most 3 keys. The left node of the two keeps its page and takes the right one's cells, or, for internal nodes, the separator and then the right one's keys and children. The right node's page is freed (section 26), its separator and its entry leave the parent, and the left leaf's link becomes what the right leaf's was. Children that moved have the left node's page as their parent.
Borrow when they do not fit: their cells are divided again as a leaf split divides them (section 17, by bytes), or their keys, with the separator between them, as an internal split divides them (section 9, one key moving up). No page is allocated or freed. The separator between them becomes the first key of the right leaf, or the key that moved up.
A merge takes a key from the parent, which can leave the parent below minimum in turn; it is fixed the same way, up to the root.
Pages join the free list as they are freed, bottom up. A merge frees its right node's page at once, before the parent is looked at; a merge one level up frees its page next; a shrinking root frees its child's page last. Each joins at the head (section 26), so db freelist shows the last page freed first.
The root shrinks when it is an internal node left with no key: its only child's contents move into the root's page, the child's page is freed, and the tree is one level shorter. The root keeps its page, as it does when it splits (section 18), and the recorded root never changes. It is still the only node with is-root 1, with parent 0, and the child's children have the root's page as their parent. When the child was a leaf, the root is a leaf again, with no next leaf.
One row at a time. The result is the tree you get by removing, or updating, the rows one at a time in ascending key order, and fixing any node below minimum after each one. A borrow divides as a split does: two internal nodes end with 2 keys on the left and 1 on the right, the third of the four keys moving up (section 9), and leaves divide by bytes, where a tie between two points goes either way. A test that checks an exact tree uses rows whose sizes leave no tie; elsewhere it checks the invariants.
A separator is still a bound, not always the smallest key to its right: every key to its left is smaller than it and every key to its right is at least it. Deleting a leaf's first key does not change the separator above it.
The catalog is a B+Tree like any other and follows the same rules when DROP TABLE removes its rows.

After a DELETE that removes every row, the table's tree is its root, an empty leaf, and every other page it had is on the free list.

29. Overflow pages (from `overflow-pages`)

A row larger than 1000 bytes no longer fails: it keeps the start of its bytes in its cell and the rest in a chain of overflow pages.

A row of at most 1000 bytes is stored exactly as before (section 17).
A larger row has a cell of 1004 bytes: the key as a 4-byte integer, the first 996 bytes of the row of section 15, then the first overflow page as a 4-byte integer. The row's own row_size, in those first bytes, says how long it is, which is how a reader knows a chain follows. A cell is never longer than 1004 bytes, so any four cells still fit in an empty leaf.
An overflow page is page type 5 at byte 0, the number of the row's bytes it holds at bytes 6 to 9, the next page of the chain at bytes 10 to 13 (0 for the last), and those bytes from byte 16, at most 4000 per page. The rest of the page is zero up to the trailer. A row of s bytes has a chain of ceil((s − 996) / 4000) pages, all full but the last. In create table notes (id int, body varchar(65535));, a row with a body of 10,000 bytes is 10,013 bytes, and its 9,017 remaining bytes fill 3 pages of 4000, 4000 and 1017.
Allocating. An INSERT allocates the chain first, first page first, before the cell goes into its leaf and before any split. When the pages cannot all be allocated the statement is 00602 and changes nothing.
Freeing. A chain is freed from its last page to its first, so its first page ends up the head of the free list and a new chain of the same length takes the same pages in the same order. A DELETE frees the row's chain before the cell leaves its leaf, and so before any merge (section 28). An UPDATE frees the old row's chain and then allocates the new row's, if it has one, so a row that stays the same size reuses its pages. DROP TABLE and TRUNCATE free the chains of the rows they remove: in the post-order of section 27, a leaf's chains, its rows in key order, come just before the leaf itself.
btree dump of a leaf adds two fields to the cell of a row that has a chain, and only to it:

[BTREE]   Cell <i>: key=<k> (<row_size> bytes) overflow=<first page> pages=<chain length>

SELECT, btree find, WHERE comparisons and [EXEC] counts see the whole row, as if it were in the cell. rows_examined counts rows, not pages.
Limits. The 1000-byte row limit is gone and 00407 no longer happens: a row is limited by its columns, each VARCHAR(n) at most 65535 bytes, and by the page limit. The catalog's columns is a VARCHAR(65535) like any other, so a CREATE TABLE whose column list would be longer is 00405, in the place section 19 gave 00407. serialize of a row over 1000 bytes prints the whole row in the three lines of section 15. A statement, and any line, may be up to 131072 bytes. pager write still writes into one page: text longer than 4091 bytes is 00104. deserialize keeps its own limit of 1000 bytes (section 15).
An overflow page is not a node and not a slotted page: btree dump of it is 00703 and a page command on it 00606.

30. VACUUM (from `vacuum`)

This engine leaves no dead rows behind: a DELETE removes the cell, a leaf compacts itself when an insert needs the room (section 16), and emptied pages go to the free list (section 28). So space inside the file is reused without any sweep, and SQL results never depend on VACUUM. VACUUM does not repack half-empty leaves either: a leaf at least a quarter full stays as it is, and its free bytes are reused by the next insert that lands there. What it does is give the free pages back to the operating system: the file gets shorter.

VACUUM;

vacuum is a keyword. ast prints Statement: VACUUM and explain prints Vacuum. The tests only send VACUUM; with nothing after it.

With N pages in the file and F of them free, VACUUM leaves N − F pages and none free:

Every page in use at a number of N − F or more moves to a free page below N − F: the highest such page first, each to the lowest free page left. A moved page keeps its bytes except the numbers that name pages, and everything that named its old number names the new one: its parent's entry, its children's parent field, the leaf that links to it, the overflow page or cell that points to it, and, for a root, the catalog row's root, or the header's root field for the catalog's own root. VACUUM is the only thing that ever moves a tree's root.
A page that nothing points at, such as one that only pager write touched, moves too, with its bytes.
Then total_pages is N − F, the free list is empty (head 0, count 0), the pages past the end leave the pool without being written, and when the session ends the file is N − F pages long.
What VACUUM does while pager pin holds a page it would move or release is not defined; no test pins a page by hand before a VACUUM.

It prints its success line, then a report:

Vacuum statement executed successfully
[VACUUM] pages_moved=<m> pages_released=<F> bytes_released=<F × 4096>

pages_moved is the number of pages in use at N − F or above, which is also the number of free pages below it. A file with no free pages prints pages_moved=0 pages_released=0 bytes_released=0 and does not change. SQL results after VACUUM are the same as before it; only page numbers change.

"Vacuum" means two things. In PostgreSQL an UPDATE or DELETE leaves the old row version in the table, and VACUUM must sweep those away. InnoDB changes rows in place and keeps old versions in its undo log; a DELETE only marks the row, and a background purge thread removes it, so nobody runs a sweep by hand; shrinking the file is a separate job, OPTIMIZE TABLE in MySQL and VACUUM in SQLite. This VACUUM is that one.

31. What Memory and Space changes

As in section 21, each change is made by one stage, which retires the earlier cases that checked the old contract, by name, in the manifest.

Earlier contract	Section	Changed by	Now
no page leaves memory before the session ends	8	`io-counters`	only with the default pool; a smaller one evicts, and writes dirty pages as they leave (section 22)
`drop`, `truncate`, `if` and `exists` are identifiers	4, 5	`drop-table`	keywords (section 27)
`vacuum` is an identifier	4	`vacuum`	a keyword (section 30)
`db verify` leaves every good page it read in memory	20	`io-counters`	unless a smaller pool evicts it (section 22)
DELETE frees no page and merges no leaf; leaves may be empty; `pager status` counts the same pages	9, 10, 17	`btree-merge`	nodes below a quarter full borrow or merge, and freed pages go to the free list (section 28)
a row larger than 1000 bytes is `00407`: INSERT, UPDATE, `serialize` and the catalog row of CREATE TABLE	14, 15, 17, 19	`overflow-pages`	the row is stored with an overflow chain (section 29)
a statement is at most 4096 bytes	1, 14	`overflow-pages`	131072 bytes (section 29)
a line is at most 4096 bytes, so `pager write` text always fits its page	7	`overflow-pages`	text longer than 4091 bytes is `00104` (section 29)
a catalog row over 1000 bytes is `00407`	19	`overflow-pages`	a column list over 65535 bytes is `00405` (section 29)
a tree's root page never changes; the file never gets shorter	18, 26	`vacuum`	VACUUM moves pages, roots included, and shortens the file (section 30)

32. Transactions and Recovery: general rules

One connection. One session runs one transaction at a time. Nothing here is about two sessions at once: locks, isolation levels and MVCC belong to Sessions and Concurrency.
Four statements, each a keyword and nothing else before its ;:

Statement	Prints	`ast`	`explain`	From
`BEGIN;`	`Begin statement executed successfully`	`Statement: BEGIN`	`Begin`	`begin-commit`
`COMMIT;`	`Commit statement executed successfully`	`Statement: COMMIT`	`Commit`	`begin-commit`
`ROLLBACK;`	`Rollback statement executed successfully`	`Statement: ROLLBACK`	`Rollback`	`rollback`
`CHECKPOINT;`	`Checkpoint statement executed successfully`, then a report (section 37)	`Statement: CHECKPOINT`	`Checkpoint`	`checkpoint`

begin, commit, rollback and checkpoint are keywords from the stage that adds them: tokenize prints [KEYWORD_BEGIN - begin] and so on. ast prints the one line, and explain prints its node as it prints Vacuum (section 30), runs nothing, and checks nothing, so explain commit; with no transaction open prints its plan. An implementation may accept BEGIN TRANSACTION; or START TRANSACTION;; no test sends them.

What a transaction holds. The statements that change rows or tables are INSERT, UPDATE, DELETE, CREATE TABLE, DROP TABLE and TRUNCATE. Between BEGIN and COMMIT they all belong to one transaction. Outside one, each runs as a transaction of its own, committed when it succeeds: autocommit. SELECT and explain change nothing and are in a transaction only in the sense that they see its changes. VACUUM never runs inside one (01304).
A transaction changes pages. A page is changed by a transaction when one of its statements wrote to the page, allocated it or freed it, even if its bytes end up as they were. Reading a page does not change it.
Debug commands are outside transactions. The commands that change pages directly (pager alloc, pager write, pager free, page init, page insert, page delete) behave as in earlier parts, whether a transaction is open or not, and are saved as they were (section 22). What they do to a page an open transaction has changed is not defined; no test does that. The commands that show pages (btree dump, pager get, pager read, db header, db freelist and the rest) show the pages as they are in memory, the open transaction's changes included.
The second file. From wal-write the database has a log beside it, named by adding .wal to the database path: --db data/x.db has data/x.db.wal, and the default droid.db has droid.db.wal. Before wal-write there is no second file.
Crashes. Tests stop the program in the middle of its work with .crash (section 33) and, from wal-write, with fail-points (section 35). A crash ends the program at once: nothing more is printed and nothing more is written. Tests also change the files between two sessions, as a disk or a power cut would: cut the log short, change one of its bytes, or delete it.
SQL results are the same as in earlier parts for any session that commits what it runs. What this part changes is which changes survive a crash or a session that ends with a transaction open.

33. BEGIN and COMMIT (from `begin-commit`)

The state. A session is IDLE or IN_TRANSACTION. It starts IDLE. BEGIN moves it to IN_TRANSACTION; COMMIT, and from rollback ROLLBACK, move it back.

Command	Output
`tx status`	`[TX] Status: IDLE`, or `[TX] Status: IN_TRANSACTION pages=<k>`, `k` the number of different pages the open transaction has changed so far

A page counts once however often it changes. Right after BEGIN, pages=0. An INSERT into a leaf with room changes that leaf and nothing else, so it adds 1.

BEGIN while a transaction is open is 01301: the open transaction carries on unchanged. COMMIT with none open is 01302, and changes nothing.
Inside a transaction, each statement sees the changes of the ones before it.
A statement that fails inside a transaction changes nothing, as anywhere (section 3), and the transaction stays open with what the statements before it did: a duplicate key, an unknown column or a value of the wrong type fails that one statement, and a COMMIT after it commits the rest. 01303 is the one error that ends the transaction.
Durable at commit. When COMMIT prints its line, every page the transaction changed is in the database file. An autocommit statement's own line means the same for that statement. Until wal-write the pages are written straight to the database file; sections 35 and 37 change how.
Nothing uncommitted reaches the file. A page changed by the open transaction is never written to the database file before the commit: when a page must come into a full pool, eviction passes over it exactly as it passes over a pinned page (sections 24 and 25), leaving its reference bit as it is. When no page in the pool can leave, and at least one of them is held only because the open transaction changed it, the statement is 01303: it prints that line, the whole transaction is discarded, every page it changed goes back to the bytes it had when the transaction began, a page it allocated past the end of the file leaves, and the session is IDLE. In autocommit the transaction is that one statement, which changes nothing. When every page in the pool is pinned, the error is still 01201.
Small pools and SQL, again. Section 22 requires SQL to work with a pool of 16 frames. From this stage the pool must also hold every page the open transaction changed, so that holds for a transaction that changes at most 8 pages. A larger one may be 01303 with 16 frames, and with the default pool of 1000 frames it never is. A single-row statement on a deep tree can change several pages, merges and freed pages included; tests that use 16 frames keep each transaction to 8 pages or fewer, and the cases about 01303 send far more.
pager flush writes every dirty page except those the open transaction changed.
The end of a session. .exit, the end of input and the end of a -c command discard an open transaction, as 01303 does, and then save as before (section 22): the file gets every commit and nothing of the open transaction.
.crash ends the program at once with exit status 3. It prints nothing, not even the goodbye line, and writes nothing more to any file: the open transaction is lost, and so is any page a debug command changed and nothing has written yet. Every commit survives it. .help does not list it: it is there for tests.
VACUUM inside a transaction is 01304, and the transaction carries on unchanged. In autocommit it runs as before.

34. ROLLBACK (from `rollback`)

ROLLBACK discards the open transaction: every page it changed goes back to the bytes it had at BEGIN, a page it allocated past the old end of the file leaves, and so pager status, db header, db freelist, the catalog and every table are as they were at BEGIN. It prints its line and the session is IDLE. ROLLBACK with no transaction open is 01302.
DDL rolls back too. A CREATE TABLE, DROP TABLE or TRUNCATE inside a transaction is undone like any other change: the catalog is pages, and those pages go back.
A statement that fails after it changed pages is undone before its error line, inside a transaction or in autocommit: an UPDATE or DELETE that meets a page failing its checksum (00609) after it changed rows on other leaves, or a statement that runs out of pages (00602) in the middle of a split, changes nothing. Section 20 left this undefined; from here it is not. The transaction stays open with what the statements before it did.
Rolling back writes nothing to the database file. Until checkpoint the bytes it restores are the file's own. From checkpoint a page may hold a commit the file does not have yet (section 37): it goes back to those bytes, and stays dirty until something writes it.

35. The write-ahead log (from `wal-write`)

From this stage a commit goes to the log before the database file. Every integer is unsigned and little-endian.

The log file starts with a 16-byte header:

Bytes	Field	Value
0–7	magic	the 8 ASCII bytes `droidwal`: `64 72 6f 69 64 77 61 6c`
8–11	version	`1`
12–15	page size	`4096`

Records follow the header back to back, with no gap and no padding:

Bytes	Field	Value
0–3	length	the record's length in bytes, these 4 included: 4116 for a page record, 20 for a commit record
4–7	transaction	the transaction's id
8–11	type	`1` page, `2` commit
12–15	page	the page's number; `0` in a commit record
16–4111	image	page records only: the page's 4096 bytes as the database file would hold them, its trailer (section 20) included
last 4	checksum	the CRC32 of section 20 over every byte of the record before it

LSN. A record's log sequence number is its byte offset in the log file: the first record's is 16, and each next one is the one before plus its length.
Transaction ids are given at commit: one more than the largest id in the log, or 1 when the log has no record. So ids in the log always go up.
Committing, from this stage, is these steps in this order:
1. a page record for every page the transaction changed, in ascending page number, each holding the page as it is at the commit;
2. a commit record;
3. the log is synced to disk;
4. the pages are written to the database file, in ascending page number. Section 37 removes this step.
The commit prints its line after the last step. The rule the log exists for: no page the transaction changed reaches the database file before its commit record is in the log and synced. A transaction that changed no page writes nothing to the log, not even a commit record.
The log is created by the first commit that writes to it, with its header. A session that commits no change creates no log.
A clean end of session (.exit, end of input, the end of -c) discards an open transaction, saves as before, and then empties the log. Emptying leaves the log holding exactly the 16-byte header above, so a log whose own header was damaged gets a correct one. A log that does not exist stays absent. After a crash, the log keeps what it had.
Reading the log. Records are read from the first, and the log ends at its last good record: a record cut short, whose length is not 4116 or 20, whose type does not match its length, or whose checksum does not match ends it, and every byte from there on is ignored. A log shorter than its header, or whose header is not the one above, has no records.
wal status reads the log file and prints its size in bytes and its good records:

[WAL] Status: size=<bytes> records=<n>
[WAL]   Record <i>: lsn=<lsn> tx=<id> type=PAGE page=<p>
[WAL]   Record <i>: lsn=<lsn> tx=<id> type=COMMIT

i counts from 1. Without a log file it prints [WAL] Status: size=0 records=0; an empty log is size=16 records=0. size is the whole file, any bytes past the last good record included.

Fail-points. The environment variable DROID_FAILPOINT names a point in the program's work. The first time the program reaches it, the program ends exactly as .crash does: exit status 3, nothing more printed, nothing more written. A name the program does not know, or a point the session never reaches, does nothing.

Fail-point	Where the program stops
`before_commit_record`	at a commit, after the page records are written to the log and before the commit record
`after_log_sync`	at a commit, after the log is synced and before any page of the commit is written to the database file
`mid_page_write`	after the first page of a commit is written to the database file and before the next; with one page, after it. From `crash-recovery` recovery's writes count, and from `checkpoint` a checkpoint's

The counters of section 23 count the database file only: writing the log is not a write.
VACUUM is not logged. It runs with no transaction open, writes the pages it moved, shortens the file and syncs it before it prints its line, rather than when the session ends, and leaves the log empty. A crash in the middle of a VACUUM is not defined; no test makes one.
Until crash-recovery, what a session does with a log that a crash left behind is not defined. Tests read such a log from the file, or with wal status in the same session.

36. Crash recovery (from `crash-recovery`)

Recovery runs when the program opens a database whose log has at least one good record. It comes after the checks of section 8 (00603, 00604) and before those of sections 18 and 20 (00608, 00609 for page 0), so recovery can repair the header page:

Read the log's good records (section 35).
A transaction is committed when its commit record is among them. For every page record of a committed transaction, in log order, write its image to that page of the database file, making the file longer when the page is past its end. Page records of every other transaction are ignored.
Sync the database file, then empty the log.
Print one line, before the welcome line, and before the output of a -c command:

[WAL] Recovery: records=<r> replayed=<c> discarded=<d>

r is the number of good records, c of committed transactions, d of transactions that have page records and no commit record. A log that is missing, empty or has no good record prints nothing; one with no good record is emptied all the same. A later part may add fields after discarded=<d>, each a space and name=<number>, and may log more records per commit: tests that are not about this line's format read replayed and discarded and leave the rest free.

Idempotent. Writing the same images twice gives the same file, so a crash during recovery (mid_page_write) is followed by the same recovery at the next open, with the same line.
Recovery's reads and writes are not counted: the counters of section 23 start after it.
After a crash, every committed transaction is in the database and nothing of any other: rows, the catalog, pager status and db freelist are what the last commit left.

37. Checkpoints (from `checkpoint`)

From this stage a commit stops at step 3 of section 35: the log holds the commit, and the commit prints its line once the log is synced. The pages stay in the pool, dirty, and reach the database file later, by eviction (a committed page may leave: its records are in the log), pager flush, a checkpoint or the end of the session. Until then the database file does not have them, and a crash leaves them to recovery.

A checkpoint writes every dirty page to the database file in ascending page number, syncs it, and empties the log. CHECKPOINT; runs one and prints:

Checkpoint statement executed successfully
[WAL] Checkpoint: pages=<k> records=<r>

k is the number of pages written, r the number of good records the log had. With nothing to do it prints pages=0 records=0 and writes nothing. CHECKPOINT inside a transaction is 01304, and the transaction carries on unchanged.

A clean end of session is a checkpoint, with no line printed.
VACUUM starts with a checkpoint, with no line printed, so the log is empty and the database file has every committed page before it moves any (section 35).
A crash in the middle of a checkpoint (mid_page_write) leaves the log as it was, so the next open recovers every committed transaction.

Real engines also checkpoint on their own when the log reaches a size: SQLite after 1000 pages, PostgreSQL every checkpoint_timeout or max_wal_size. This engine checkpoints only when asked and at a clean end, so the log's contents are always known to a test.

38. What Transactions and Recovery changes

As in section 21, each change is made by one stage, which retires the earlier cases that checked the old contract, by name, in the manifest.

Earlier contract	Section	Changed by	Now
a statement's changes reach the file at eviction, `pager flush` or the end of the session	8, 22	`begin-commit`	at its commit (section 33)
any unpinned page may be evicted	22, 25	`begin-commit`	not one the open transaction changed (section 33)
any SQL works with a pool of 16 frames	22	`begin-commit`	when its transaction changes at most 8 pages (section 33)
`begin` and `commit` are identifiers	4	`begin-commit`	keywords (section 32)
`rollback` is an identifier	4	`rollback`	a keyword (section 32)
what a statement leaves when it fails after changing rows is not defined	20	`rollback`	it changes nothing (section 34)
VACUUM shortens the file when the session ends	30	`wal-write`	before it prints its line (section 35)
opening never changes the database file	8, 18	`crash-recovery`	recovery writes committed pages from the log (section 36)
a commit writes its pages to the database file	33, 35	`checkpoint`	to the log; the file gets them later (section 37)
`checkpoint` is an identifier	4	`checkpoint`	a keyword (section 32)

39. Querying: general rules

Tables. Every table is made by CREATE TABLE, as from create-table (section 19). Tests of this part create their own tables; the names of section 14 hold for every table.
Results are those of section 10 in table mode and section 11 in CSV mode: a header, the rows, (<n> rows) in table mode, then the [EXEC] line of section 13.
Row order. A scan hands up rows in ascending key order, and every operator of this part keeps the order it is given unless it is one that orders rows. So a SELECT without ORDER BY prints its rows in ascending key order, here as in every earlier part.
The [EXEC] line. A stage of this part may add a field after rows_examined=<n>, each a space and name=<number>, and does so only for a statement whose plan has the node that counts it. A test that is not about such a field reads rows_examined and leaves the rest free.
A statement that fails while it runs (01501, 01502, 01504, and from subqueries-uncorrelated 01709) prints its error line and nothing else: no header, no row, no footer and no [EXEC] line, however many rows it had already examined. An UPDATE or DELETE that fails changes nothing, as section 34 says of any statement that fails after changing pages. Inside a transaction, the transaction stays open with what the statements before it did, as for any statement that fails (section 33). explain evaluates nothing, so it never prints these codes.

40. Expressions (from `expressions`)

A WHERE clause holds an expression: a tree of operators over columns and literals. The WHERE of SELECT, UPDATE and DELETE is an expression from this stage; the select list, the values of INSERT and the assignments of UPDATE are not changed by it.

Tokens. and, or and not are keywords: tokenize prints [KEYWORD_AND - and] and so on. The symbols are those of section 4 and eight more:

Symbol	Meaning
`<=` `>=`	at most, at least
`!=` `<>`	not equal: two spellings of one operator
`+` `-`	add, subtract; `-` before an operand is unary minus
`*` `/` `%`	multiply, divide, remainder; `` is also the `` of `select *`

A two-character symbol is read as one token when its two characters are next to each other: <= is [SYMBOL - <=], and < = is two tokens, < and =. ! not followed by = is 00202. A - is always its own token, so -1 is [SYMBOL - -] and [NUMBER - 1] (section 4 let this be either way before; from this stage it is two tokens).

Grammar, from the loosest operator to the tightest:

Level	Operators	Groups
1	`OR`	left to right
2	`AND`	left to right
3	`NOT` (prefix)	applies to everything at level 4 and tighter after it
4	`=` `!=` `<>` `<` `>` `<=` `>=`	at most one per level: `a = 1 = 2` is `00302` at the second `=`
5	`+` `-`	left to right
6	`*` `/` `%`	left to right
7	`-` (prefix, unary minus)	applies to the operand after it
8	a column, a number, a string, or `( <expression> )`

So a = 1 or b = 2 and c = 3 is a = 1 or (b = 2 and c = 3), not a = 1 and b = 2 is (not (a = 1)) and b = 2, a + b * 2 is a + (b * 2), and a - b - 1 is (a - b) - 1. Parentheses change the shape and leave nothing in the tree. A number is digits, a string is quoted, and a word that is not a keyword is a column. An expression that ends too early, a ( without its ), or an operator where an operand belongs is 00302, at the column of section 5.

Printing an expression. ast, explain and later stages print an expression in one way:

a column as typed, a number as its digits, a string between single quotes;
a binary operator as its left operand, a space, the operator, a space and its right operand. AND and OR are printed in capitals, however they were typed; a symbol is printed as typed, so <> stays <>;
NOT as NOT, a space and its operand; unary minus as - and its operand, with no space;
every operand that is not a column or a literal is put between parentheses. Nothing else is.

Typed	Printed
`id = 5`	`id = 5`
`a = 1 or b = 2 and c = 3`	`(a = 1) OR ((b = 2) AND (c = 3))`
`(a = 1 or b = 2) and c = 3`	`((a = 1) OR (b = 2)) AND (c = 3)`
`not a = 1 and b = 2`	`(NOT (a = 1)) AND (b = 2)`
`a + b * 2 = 7`	`(a + (b * 2)) = 7`
`-a - -1 > 0`	`((-a) - (-1)) > 0`

ast prints the WHERE as Where: <expression>, in the place of section 5. It still only parses, and checks neither names nor types.

Types. A value is an INT, a VARCHAR or a truth value. A column has its column's type, a number is an INT and a string a VARCHAR.

Operator	Takes	Gives
`+` `-` `*` `/` `%`, unary minus	two `INT`s (one for unary minus)	an `INT`
`=` `!=` `<>` `<` `>` `<=` `>=`	two `INT`s, or two `VARCHAR`s	a truth value
`AND` `OR`	two truth values	a truth value
`NOT`	a truth value	a truth value

An operator given anything else is 00403, and so is a WHERE whose expression is not a truth value: where name > 5, where a + name = 1, where a and where not a are all 00403. The message may say where; tests read the code.

Checks. The statement is checked before any row is read, in this order, and the first check that fails prints its code and nothing else. The checks of sections 10 and 19 come first, as they were, up to the WHERE; then:

every column of the WHERE, in the order written, is a column of the table (00402);
every operator, each one after its operands, from the left (00403), and then the WHERE as a whole is a truth value (00403);
every number of the WHERE, in the order written, is at most 4294967295 (00404).

Values. An INT column holds 0 to 4294967295, and so does a number as typed. Arithmetic works on signed 64-bit integers, so an expression may go below zero or past 4294967295 on the way: a - 5 < 0 holds for every a below 5, -a < 0 for every a above 0, and a * 2 > 4294967295 for every a above 2147483647. A result outside the signed 64-bit range is 01502.

/ divides and drops the fraction, towards zero: 7 / 2 is 3 and -7 / 2 is -3. % is what is left, with the sign of its left operand: 7 % 2 is 1 and -7 % 2 is -1. Either of them with a right operand of 0 is 01501.
INTs compare as numbers; VARCHARs compare byte by byte, as in section 10, so '10' < '9'.
!= and <> hold when = does not.

Evaluation. The WHERE is evaluated once for each row the scan hands up, and a row is kept when it gives true. AND and OR evaluate their left operand first and leave the right one alone when the left decides: false for AND, true for OR. Every other operator evaluates its operands, the left one first. So b != 0 and a / b = 2 never divides by zero, and a / b = 2 on a row whose b is 0 is 01501 (section 39). A table with no row evaluates nothing.

Plans. The WHERE is split into its conjuncts: the expressions joined by ANDs at its top, with an AND inside one of them, at any depth of parentheses, splitting it again. a = 1 and (b = 2 and c = 3) has three conjuncts, a = 1 or b = 2 and c = 3 one. A conjunct is a key bound when it is the table's first column, an operator =, <, >, <= or >=, and a number, in that order: id >= 3 is one, 3 <= id, id = 1 + 1 and not id = 3 are not.

With no key bound, the plan is a Filter holding the whole WHERE over a SeqScan, as in section 12.
Otherwise the plan is an IndexScan. The first = key bound in the order written is its key: IndexScan (table=<t>, key=<k>). With no =, the first lower bound (> or >=) and the first upper bound (< or <=) are its range, lower first: range: id >= 3, range: id < 6, range: id >= 3 AND id <= 5.
Whatever is left of the WHERE once the key bounds the IndexScan uses are taken out goes into a Filter above it, printed as an expression: each AND that loses one of its operands is replaced by the other. When nothing is left there is no Filter.

WHERE	Plan, top first
`name = 'bob'`	`Filter (name = 'bob')`, `SeqScan (table=t)`
`id >= 3 and id <= 5`	`IndexScan (table=t, range: id >= 3 AND id <= 5)`
`id <= 5 and id >= 3`	`IndexScan (table=t, range: id >= 3 AND id <= 5)`
`id >= 3 and a = 1`	`Filter (a = 1)`, `IndexScan (table=t, range: id >= 3)`
`a = 1 and id = 4 and id > 2`	`Filter ((a = 1) AND (id > 2))`, `IndexScan (table=t, key=4)`
`id = 4 or id = 5`	`Filter ((id = 4) OR (id = 5))`, `SeqScan (table=t)`

UPDATE and DELETE plan the same scan under their node. Every WHERE of section 12 is a single key bound or none, so its plan does not change. An IndexScan hands up the rows whose key its key or range admits, and those are the rows rows_examined counts (section 13): id >= 3 and id <= 5 over keys 1 to 8 examines 3.

LIKE, functions such as LOWER or COALESCE, and other value types are not in this part: they belong to the optional SQL surface track, and each is a new kind of node in the same tree.

41. NULL (from `nulls`)

NULL is a value of no type that means unknown: any column but the first may hold it.

Tokens. null and is are keywords: [KEYWORD_NULL - null], [KEYWORD_IS - is].
The literal. NULL is an operand wherever a number or a string may stand: in a WHERE, in the values of an INSERT and in the assignments of an UPDATE. It fits any type: c = NULL, name = NULL and NULL + 1 are not 00403, and NULL may be given to any column. It takes the type its operator needs and changes nothing else: a comparison still takes two INTs or two VARCHARs, so (a = 1) = NULL is 00403, as (a = 1) = (b = 2) is. ast and explain print it as NULL, in Values: too: Values: [1, NULL, 'x'].
IS NULL. <operand> IS NULL and <operand> IS NOT NULL stand at the level of the comparisons (section 40), one per level, and give true or false, never unknown. They take an operand of any type. They print as a IS NULL and a IS NOT NULL, the operand in parentheses when it is not a column or a literal: (a + 1) IS NULL. not a is null is NOT (a IS NULL).

Three truth values. A truth value is true, false or unknown. Each comparison and each arithmetic operator with a NULL operand gives unknown or NULL: c = NULL is unknown whatever c holds, NULL = NULL too, and c + 1 is NULL when c is. NOT, AND and OR follow these tables:

`NOT`
true	false
false	true
unknown	unknown

`AND`	true	false	unknown
true	true	false	unknown
false	false	false	false
unknown	unknown	false	unknown

`OR`	true	false	unknown
true	true	true	true
false	true	false	unknown
unknown	true	unknown	unknown

A WHERE keeps a row when its expression is true, so it drops the rows where it is false and the rows where it is unknown: where c = NULL and where c != NULL both keep no row, and where not (c = 1) keeps no row whose c is NULL. where NULL is allowed and keeps no row.
Evaluation is as in section 40. AND leaves its right operand alone only when the left is false, and OR only when it is true: an unknown left side evaluates the right. An arithmetic operator with a NULL operand gives NULL without dividing, so NULL / 0 is NULL, not 01501.
A NULL is never a key bound: id = NULL is a conjunct for the Filter.

Columns that may not be NULL. CREATE TABLE takes NOT NULL after a column's type: create table t (id int, name varchar(20) not null, age int);. ast prints such a column as its name, its type as typed and NOT NULL: Columns: [id int, name varchar(20) NOT NULL, age int], and the catalog's column list (section 19) as name VARCHAR(20) NOT NULL, so catalog list shows it. The first column is never NULL, whether or not it is declared NOT NULL, and is printed as declared.

A column an INSERT leaves out is NULL (section 14 made it 0 or the empty string, before there was a NULL). An INSERT that gives NULL to, or leaves out, a NOT NULL column is 01503; one that gives NULL to the first column is 01503 too, and one that leaves the first column out is still 00406. An UPDATE that assigns NULL to a NOT NULL column is 01503.
The checks of section 19 run in their order. 01503 comes after 00406 and before 00407, in one pass over the table's columns in table order: the first column that is NULL, given or left out, and may not be, is the one reported. In an UPDATE it comes with each assignment, after its value's type. explain runs these checks as the statement would, so explain of such an INSERT is 01503 and prints no plan.

Storage. The null bitmap of section 15 is in use: bit i % 8 of bitmap byte i / 8, counting bits from the least significant, is set when column i is NULL, counting columns from 0 in table order. A NULL column has no bytes: no length, no value. The first column's bit is never set.

serialize insert into t (id, name, age) values (1, NULL, 30);
[SERIALIZE] Row size: 15 bytes
[SERIALIZE] Layout: row_size:4@0 column_count:2@4 null_bitmap:1@6 id:4@7 age:4@11
[SERIALIZE] Bytes: 0f 00 00 00 03 00 02 01 00 00 00 1e 00 00 00

Layout: leaves out every NULL column, since it is not stored.
deserialize prints a NULL column as [DESERIALIZE] Field <name> = NULL. A bitmap bit set for the first column, or for a column past column_count, is 00503.
btree find prints a NULL column as <name>=NULL, with no quotes: [BTREE] Row: id=1 name=NULL age=30.

Printing. In table mode a NULL is printed as NULL: 1 | NULL | 30. In CSV mode it is an empty field, as an empty string is: 1,,30.

42. IN and BETWEEN (from `in-between`)

in and between are keywords: [KEYWORD_IN - in], [KEYWORD_BETWEEN - between]. They add two predicates to the expressions of sections 40 and 41:

<operand> [NOT] BETWEEN <low> AND <high>
<operand> [NOT] IN (<item>, ...)

Where they stand. At the level of the comparisons (section 40, level 4), one per level, as IS NULL is (section 41). The operand, <low>, <high> and each item are expressions of level 5 and tighter (arithmetic, a column, a literal, NULL, or a parenthesised expression), so the AND of a BETWEEN belongs to it: a between 1 and 5 and b = 2 is the BETWEEN, then AND b = 2. NOT written before BETWEEN or IN belongs to them. not a in (1, 2) is NOT over the IN, which means the same.
Syntax errors (00302): an IN list with no item, in (); an IN without its parentheses, in 1; a BETWEEN without its AND, between 1; a NOT after an operand that is not followed by IN or BETWEEN, a not = 1; and a second predicate at the same level, a in (1) = b.
They are rewritten by the parser. Neither one is a node of its own. The parser builds the comparisons they stand for, and everything after it (printing, checks, evaluation, NULLs and plans) works on the rewritten tree, by the rules already in sections 40 and 41:

Typed	Rewritten into
`a between 1 and 5`	`(a >= 1) AND (a <= 5)`
`a not between 1 and 5`	`NOT ((a >= 1) AND (a <= 5))`
`a in (1, 2, 3)`	`((a = 1) OR (a = 2)) OR (a = 3)`
`a in (7)`	`a = 7`
`a not in (1, 2)`	`NOT ((a = 1) OR (a = 2))`

The operand is copied into each comparison, written as typed: a + 1 between 2 and 3 is ((a + 1) >= 2) AND ((a + 1) <= 3). ast and explain print the rewritten tree, as section 40 prints any expression.

What follows from the rewrite, which the tests check:
- BETWEEN includes both ends, and with <low> above <high> it keeps no row: between 5 and 1.
- A NULL operand gives unknown, so neither the predicate nor its NOT keeps the row.
- A NULL item in an IN list makes every row that matches no other item unknown: a in (1, NULL) keeps the rows where a is 1, and a not in (1, NULL) keeps no row.
- Types are those of the comparisons: a in (1, 'x') and name between 1 and 5 are 00403.
- id between 3 and 5 gives two conjuncts that are key bounds, so its plan is IndexScan (table=t, range: id >= 3 AND id <= 5). An IN is an OR, never a key bound, so id in (2, 4) is a Filter over a SeqScan.

Real engines keep IN as a node of its own and compare against a list or a hash set, which a long list needs. A rewrite is enough here, and it shows that both are shorthand for what the engine already does.

43. Projection (from `projection`)

The select list of a SELECT is * or a list of items separated by ,. An item is an expression (sections 40 and 41), optionally followed by AS and a name: select name, id * 2 as dbl from t;. as is a keyword: [KEYWORD_AS - as]. * stands alone, so select *, id from t; is 00302; an AS with no name after it is 00302 too.

Headers. An item's header is its alias when it has one. Otherwise it is the item printed as in section 40: a column's header is its name as typed, as before, id * 2 is id * 2, a + b * 2 is a + (b * 2) and 'x' is 'x'. Two items may have the same header. In CSV mode the header line follows the quoting of section 11.
Values. Each row prints each item's value, in the order of the list: an INT as its digits, with a - in front when it is below zero; a VARCHAR as stored; a NULL as section 41 says; a truth value as true or false, and unknown as NULL. An item made only of literals gives the same value on every row: select 1 from t; prints one 1 per row.
Checks. After the table (00401), in this order, and the first that fails is reported: every column of the select list in the order written, then every column of the WHERE (00402); the operators of the select list's items in order, then those of the WHERE and the WHERE as a whole (00403); the numbers of the select list, then those of the WHERE (00404). An item may be of any type, a truth value included.
An alias names an output column only. The WHERE cannot use it: select id * 2 as dbl from t where dbl > 2; is 00402 when t has no column dbl. An alias may be the name of a column of the table, and the WHERE then means the column.
Evaluation. The items are evaluated for each row the WHERE keeps, after it, from the left. A row the WHERE drops is not projected, so select a / b from t where b != 0; never divides by zero. An error while evaluating fails the statement (section 39).
ast prints the select list as Columns: [<item>, ...], each item printed as in section 40, then AS <alias> when it has one, the alias as typed: Columns: [id * 2 AS dbl, name]. Columns: [*] is unchanged.
The plan. A select list that is not * puts a Project (cols=[<item>, ...]) node at the top of the plan, items printed as in ast, above the scan or the Filter:

[PLAN] select name, id * 2 as dbl from t where a = 1
[PLAN]   └── Project (cols=[name, id * 2 AS dbl])
[PLAN]       └── Filter (a = 1)
[PLAN]           └── SeqScan (table=t)

select * has no Project node, as before. rows_examined does not change: a Project reads no row of its own.

44. ORDER BY (from `order-by`)

SELECT <select list> FROM t [WHERE <expression>] [ORDER BY <key> [ASC | DESC], ...];

order, by, asc and desc are keywords. Each key is an expression, sorted ascending unless DESC follows it. ORDER BY with no key, or a key followed by both ASC and DESC, is 00302. ORDER BY belongs to SELECT only: after the WHERE of an UPDATE or a DELETE it is 00302.

Aliases. A key that is a name alone, and the alias of an item of the select list, means that item, even when the table has a column of that name; when two items have that alias, the first one written. Anywhere else a name is a column of the table: an alias inside a larger key, order by dbl + 1, is 00402 when the table has no column dbl. A key that is a number alone is not defined here; no test sends one.
Order. Rows are compared by the first key; when it is equal, by the second; and so on. INTs compare as signed numbers, VARCHARs byte by byte (section 10), truth values with false before true. NULL comes before every value, so NULLs come first under ASC and last under DESC, and two NULLs are equal.
Stable. Rows whose keys are all equal keep the order they arrived in, which is ascending key order (section 39). So a tie is broken by the first column, ascending, whatever the direction of the keys.
Checks. After the table (00401): every column of the select list, then of the WHERE, then of the keys (00402); the operators of the select list, the WHERE, then the keys (00403); then the numbers, in the same order (00404). A key may be of any type.
Evaluation. The keys are evaluated for each row the WHERE keeps; an error while evaluating fails the statement (section 39). Rows that are not kept are not sorted.
ast prints a line after Where:, or after Columns: when there is no WHERE: Order: [<key> <ASC|DESC>, ...], each key printed as in section 40, its direction in capitals whether it was written or not: Order: [dept ASC, salary + bonus DESC].
The plan gets a Sort (key=<key> <ASC|DESC>, ...) node, keys as in ast, above the scan or the Filter and below the Project:

[PLAN] select id from emp where salary > 50 order by dept, salary desc
[PLAN]   └── Project (cols=[id])
[PLAN]       └── Sort (key=dept ASC, salary DESC)
[PLAN]           └── Filter (salary > 50)
[PLAN]               └── SeqScan (table=emp)

No sort for the key order. When the first key is the table's first column, ascending, the rows already arrive in that order and, since the first column is unique, the other keys can never decide: the plan has no Sort node and is the plan without ORDER BY. A first key that is an alias counts when its item is the first column. order by id desc has a Sort.
A Sort reads every row below it before it hands up the first, and counts no row of its own: rows_examined is the scan's, as before.

45. Sorting on disk (from `external-sort`)

The limit. --sort-memory <rows> is the most rows a Sort holds in memory at once, from 1 to 1000000; without it, 10000. It goes anywhere among the options, as --cache-pages does (section 22). A value that is not a number in that range is 00107, and the option with nothing after it 00102: either ends the program with exit status 1.

Runs. A Sort given more rows than its limit cannot sort them all in memory. It takes them as they arrive, in runs of at most <rows> rows: each run is sorted, as section 44 sorts, and written to the temporary file, as soon as the buffer is full and another row arrives; the runs are then merged into one order, and the rows are handed up from the merge. The rows that come out, and their order, are exactly those of section 44, whatever the limit: rows equal on every key still come out in the order they arrived, across runs as within one.

The counter. The [EXEC] line of a statement whose plan has a Sort ends with sort_runs=<r>:

[EXEC] rows_examined=100 sort_runs=10

r is ceil(n / <rows>) for the n rows that reached the Sort: one run when they fit, which is sorted in memory and never written, and 0 when no row reached it. A plan with no Sort (no ORDER BY, or ORDER BY the first column, section 44) prints no sort_runs.

The temporary file is <db path>.tmp, beside the database: --db data/x.db has data/x.db.tmp. A statement creates it when it writes its first run and deletes it when it ends, whether it succeeds or fails, so between statements it never exists. Its contents are the implementation's to choose; pages of 4096 bytes are the natural layout. It is not part of the database:

nothing in it is logged, and it belongs to no transaction: a sort inside a transaction sees the transaction's rows, and a ROLLBACK has nothing in it to undo;
the counters of section 23 count the database file only, so writing and reading runs is not counted;
a SELECT that spills changes neither the database file nor the log.

At open, a <db path>.tmp that a crash left behind is deleted, before recovery (section 36). A temporary file that cannot be created, written or read is 01504: the statement fails as section 39 says, and its file, if any, is deleted. No test makes the temporary file fail, since no portable setup can; the code is here so an implementation has one line to print when it does.

A fail-point of section 35 stops the program in the middle of a spill:

Fail-point	Where the program stops
`sort_spill`	after a `Sort` has written its first run to the temporary file, before it reads any run back

A Sort whose rows fit never writes a run, so it never reaches sort_spill.

Small pools. A spilling Sort works with a pool of 16 frames, as all SQL does (section 22), whatever its limit.

explain is unchanged: the plan does not say whether a Sort will spill, since that depends on how many rows reach it.

Real engines size the limit in bytes, not rows: PostgreSQL's work_mem is 4 MB by default, SQLite's sorter uses its page cache. A limit in rows keeps the numbers in the tests easy to check.

46. LIMIT and OFFSET (from `limit-offset`)

SELECT ... FROM t [WHERE ...] [ORDER BY ...] [LIMIT <count> [OFFSET <skip>]];

limit and offset are keywords. The SELECT skips its first <skip> rows, 0 when OFFSET is not written, and then prints at most <count> rows. Each of <count> and <skip> is a number alone, from 0 to 4294967295. The parser checks it: when the token after LIMIT or OFFSET is not a number (a name, a string, a -, a (, the ;) or is a number past that range, it reports 01505 at that token's column, as it reports its own codes (section 5), so no other check runs. Anything after the number that is not OFFSET or the end is a syntax error, 00302: limit 1 + 1. OFFSET without LIMIT before it is 00302, and so are LIMIT and OFFSET on UPDATE and DELETE.

Which rows. The rows are those the SELECT gives without LIMIT, in the same order, and LIMIT keeps the ones from position <skip> + 1 to <skip> + <count>. Without ORDER BY that order is ascending key order (section 39), so limit 2 is always the two smallest keys the WHERE keeps. A <skip> past the last row gives no row, and limit 0 gives no row: either prints the header and (0 rows), with no error.
The plan has a Limit (count=<count>, offset=<skip>) node at the top, above everything else, the Project included: Limit (count=5, offset=0) when OFFSET is not written. ast prints a line Limit: count=<count>, offset=<skip> after Order:, or after the last line before it.
A Limit stops asking. Asked for a row, a Limit asks the node below it for rows, throws away the first <skip>, and hands up the next <count>. Once it has handed up its last row it asks for no more, and with limit 0 it asks for none: not even a Sort below it runs, so order by name limit 0 examines no row and prints sort_runs=0. Nothing below it does work it does not ask for, so rows_examined (section 13) counts only the rows the scan handed up before the Limit stopped:

Query over ids 1 to 1000	`rows_examined`
`limit 5`	5
`limit 10 offset 100`	110: skipped rows are still read
`where id % 10 = 0 limit 3`	30: the Filter reads rows until it has passed three
`order by name limit 5`	1000: a `Sort` reads every row before it hands up the first
`order by id limit 5`	5: no `Sort` (section 44)
`limit 0`	0
`offset 5000`	1000

Errors below a Limit. An expression is evaluated only for rows that are asked for, so a row the Limit never asks for cannot fail the statement: select a / b from t limit 1 succeeds when only a later row has b = 0. The rows a Limit skips are asked for, from the Project below it like any other, so they are projected and can fail: select a / b from t limit 1 offset 500 fails when row 500 has b = 0. A Sort evaluates its keys for every row it reads, as before.

47. Aggregates (from `aggregates`)

Function calls. A name followed by ( is a call: count(*), sum(a * b). There are five functions, named in any case, each taking one argument: COUNT, SUM, AVG, MIN and MAX; COUNT also takes *. They are aggregates: each reads many rows and gives one value. Their names are not keywords, so a column may still be called count; only a name directly followed by ( is a call. A call of any other name, a call with no argument or more than one, and * in any call but COUNT, are 01506.

Aggregate	Takes	Gives	Over the rows it reads
`COUNT(*)`		`INT`	the number of rows
`COUNT(e)`	any type	`INT`	the number of rows where `e` is not NULL
`SUM(e)`	`INT`	`INT`	the sum of the values that are not NULL; NULL when there are none
`AVG(e)`	`INT`	`DECIMAL`	their mean, to two decimals; NULL when there are none
`MIN(e)`, `MAX(e)`	`INT` or `VARCHAR`	the same type	the smallest or largest value that is not NULL, compared as in section 44; NULL when there are none

Anything else as the argument is 00403. A SUM outside the signed 64-bit range is 01502, and so is an AVG whose running total leaves it.

DECIMAL is the one type only AVG gives: a number with exactly two decimals, the mean rounded half away from zero (AVG of 1 and 2 is 1.50, of 1, 1 and 2 is 1.33, of 1, 2 and 2 is 1.67, of -1 and -2 is -1.50). It prints with its two decimals and a - when below zero. It compares with an INT or a DECIMAL as numbers do, and sorts as one; any arithmetic on it is 00403.

One group. A SELECT whose select list holds an aggregate treats the rows the WHERE keeps as one group and prints one row, even when no row is kept: COUNT is then 0 and every other aggregate NULL.

Outside an aggregate, the select list may hold literals and expressions of aggregates (sum(a) + count(*)), but no column: a bare column next to an aggregate is 01507, since one row has no single value for it to show. ORDER BY follows the same rule.
An aggregate is not allowed in a WHERE, nor inside another aggregate's argument: 01508.
Each aggregate's argument is evaluated for every row the WHERE keeps, in order; an error fails the statement (section 39).
Headers and ast print a call as its name in capitals, (, its argument printed as in section 40 or *, and ): COUNT(*), SUM(a * b), so select count(*) from t has the header COUNT(*). A call counts as a column or a literal does for section 40's parentheses: SUM(c) + COUNT(*), not (SUM(c)) + (COUNT(*)).
select * with an aggregate in its ORDER BY is 01507, since * is every column, bare.

Checks, in the order of section 43, with two more: function names and argument counts (01506) with the column names, in the order written, a call's name before its argument (so foo(nope) is 01506); then where aggregates stand (01507, 01508) before the types.

The plan. An Aggregate (aggs=[<call>, ...]) node sits below the Project and above the Filter or the scan, listing each different call once, in the order the statement first writes it:

[PLAN] select count(*), sum(c) + count(*) from t where a > 1
[PLAN]   └── Project (cols=[COUNT(*), SUM(c) + COUNT(*)])
[PLAN]       └── Aggregate (aggs=[COUNT(*), SUM(c)])
[PLAN]           └── Filter (a > 1)
[PLAN]               └── SeqScan (table=t)

An Aggregate reads every row below it before it hands up its one row; rows_examined is the scan's.

48. GROUP BY and HAVING (from `group-by-having`)

SELECT ... FROM t [WHERE ...] [GROUP BY <key>, ...] [HAVING <condition>] [ORDER BY ...] [LIMIT ...];

group and having are keywords; by already is (section 44).

Groups. Each GROUP BY key is an expression over the table's columns; an alias is not a key, and an aggregate in a key is 01508. The rows the WHERE keeps are split into groups: two rows are in the same group when every key has the same value in both, NULL being the same as NULL. Keys are compared one by one, as values, so ('ab', 'c') and ('a', 'bc') are two groups. Each group gives one row, and every aggregate of the statement is computed over that group's rows.
What a group can show. Outside an aggregate, the select list, the HAVING and the ORDER BY may use only what has one value per group: a GROUP BY key, written as the key is (the same expression, printed the same way, section 40), a column that is a key on its own, literals, and aggregates. Anything else holding a column is 01507: select name, count(*) from emp group by dept, and select * from emp group by dept, since * is every column. A select list with no aggregate is allowed: it gives each group once.
HAVING is a condition on groups, evaluated once per group after its aggregates are finished, and keeps the groups for which it is true. It may hold aggregates, also ones the select list does not show. A HAVING that is not a truth value is 00403. HAVING without GROUP BY makes all the kept rows one group, as section 47 does, so select count(*) from t having count(*) > 100 prints the header and (0 rows), and a bare column beside it is 01507: select id from t having id > 1.
Order. Without ORDER BY, groups come out in the order their first row arrived: rows arrive in ascending key order, so a group comes where its smallest first-column value would. ORDER BY sorts the groups, and may sort by an aggregate: order by count(*) desc.
Checks, in the order of sections 43 and 47, with the GROUP BY keys after the WHERE and the HAVING after the keys at each step: columns (00402), calls (01506), where aggregates and columns stand (01507, 01508), types (00403), numbers (00404).
ast prints Group: [<key>, ...] after Where: and Having: <condition> after it, each printed as in section 40.

Two plans. A HashAggregate keeps one state for each group it has seen, found by the group's key values, and works on rows in any order. A SortAggregate needs the rows of each group to arrive together, and then keeps only one state at a time. The rows arrive in ascending first-column order, so the plan is a SortAggregate when the first GROUP BY key is the table's first column alone, and a HashAggregate otherwise. Both give the groups in the same order, the order above.

[PLAN] select dept, count(*) from emp where salary > 50 group by dept having count(*) > 1 order by dept
[PLAN]   └── Project (cols=[dept, COUNT(*)])
[PLAN]       └── Sort (key=dept ASC)
[PLAN]           └── Filter (COUNT(*) > 1)
[PLAN]               └── HashAggregate (keys=[dept], aggs=[COUNT(*)])
[PLAN]                   └── Filter (salary > 50)
[PLAN]                       └── SeqScan (table=emp)

The node is HashAggregate (keys=[<key>, ...], aggs=[<call>, ...]) or SortAggregate (...) with the same fields; aggs=[] when the statement has no aggregate. A HAVING is a Filter above it. A statement with no GROUP BY keeps the Aggregate node of section 47.

The counter. The [EXEC] line of a statement whose plan has a HashAggregate or a SortAggregate ends with groups=<g>, the number of groups formed, before HAVING drops any. A HashAggregate forms every group before it hands up the first; a SortAggregate forms each group as it is asked for one, so under a Limit that stops early it counts only those: select id from t group by id limit 2 prints groups=2. It comes after sort_runs when both are there: [EXEC] rows_examined=8 sort_runs=1 groups=4.

49. DISTINCT (from `distinct`)

SELECT DISTINCT <select list> ... prints each different output row once. distinct is a keyword, written right after SELECT; select distinct from t is 00302.

Duplicates. Two output rows are the same when every item has the same value in both, NULL being the same as NULL, as in a GROUP BY (section 48). The values are compared one by one, so ('ab', 'c') and ('a', 'bc') are two rows.
Which one stays. The first of each set of equal rows, in the order the rows reach the Distinct, so without ORDER BY the rows come out in first-seen order.
It does not block. A Distinct hands a row up as soon as it has not seen it before, so a Limit above it stops it early: select distinct dept from emp limit 2 stops reading when it has two departments.
ORDER BY with DISTINCT sorts the different rows, so every key must be an item of the select list: an alias, or an expression that prints as an item prints (section 40), so order by salary/50 matches the item salary / 50. Any other key is 01509, checked after the column names (00402) and before where aggregates and columns stand (01507, 01508): select distinct dept from emp order by nope is 00402.
The plan has a Distinct node, above the Project and below the Sort and the Limit:

[PLAN] select distinct dept from emp where salary > 50 order by dept limit 2
[PLAN]   └── Limit (count=2, offset=0)
[PLAN]       └── Sort (key=dept ASC)
[PLAN]           └── Distinct
[PLAN]               └── Project (cols=[dept])
[PLAN]                   └── Filter (salary > 50)
[PLAN]                       └── SeqScan (table=emp)

Under a Distinct node the Sort sorts the rows the Distinct hands up, so it sits above it; in every other plan it stays below the Project, as in section 44. When the select list is *, or holds the table's first column alone as an item, every row is already different: the plan has no Distinct node.

ast prints Distinct: true after Columns: for a SELECT DISTINCT, and nothing otherwise.

COUNT(DISTINCT e) counts the different values of e that are not NULL, compared as above. It prints as COUNT(DISTINCT e), in a header, in ast and in aggs=[...], and works with and without GROUP BY. DISTINCT inside any other call, or COUNT(DISTINCT *), is 01506.

50. ALTER TABLE ADD COLUMN (from `alter-table`)

ALTER TABLE t ADD COLUMN c type [NOT NULL] [DEFAULT v];

alter, add, column and default are keywords. It adds one column at the end of the table and prints Alter table statement executed successfully.

DEFAULT gives a column the value it takes when nothing else gives one: v is a number, a string or NULL, checked against the column as an INSERT's value is (00403, 00404, 00405). CREATE TABLE takes it too, after the type and after NOT NULL when both are written: create table t (id int, active int not null default 1);. A column with no DEFAULT has NULL as its default. A DEFAULT on the first column is 01104; NOT NULL DEFAULT NULL is 01503. In a CREATE TABLE each column is checked in the order written, as section 19 says, with its DEFAULT after its name: the DEFAULT's type, range and length, then 01503, then 01104 for the first column. So create table bad (id int default 5, name float); is 01104.
INSERT gives a column it leaves out the column's default (section 41 is the case of a NULL default), so a NOT NULL column with a DEFAULT may be left out.
The checks, before anything changes, in this order: the table (00401); the column's type (01102), its name not used by another column (00408); its DEFAULT's type, range and length; NOT NULL DEFAULT NULL (01503); from primary-key-rowid, a column marked PRIMARY KEY (01601, section 53); then a NOT NULL column with no DEFAULT on a table that has a row (01104; on an empty table it is allowed); then the catalog row fits (as in section 29).
No row is rewritten. ALTER changes the table's catalog row and nothing else. A row keeps the column_count it was written with (section 15); a row with fewer columns than the table reads each missing column as that column's default. So after add column active int default 1 every old row reads active as 1, and after add column note varchar(10) as NULL. INSERT and UPDATE write a row with every column the table has, so an UPDATE of an old row stores it whole, its key and its place in the tree unchanged.
Every reader sees the new column: select * and its header, WHERE, ORDER BY, GROUP BY and the aggregates, btree find (which prints the default for a column an old row lacks), serialize and catalog list. deserialize reads a row of users with a column_count from 1 up to the table's, a missing column as its default; 0, or more than the table's, is still 00503.
The catalog prints the column with NOT NULL and then DEFAULT <v> when they are declared, v printed as a literal is (section 40): [CATALOG] t root=2 (id INT, name VARCHAR(20), active INT NOT NULL DEFAULT 1).
Transactions. ALTER is DDL like CREATE TABLE: inside a transaction it changes pages the transaction owns, and ROLLBACK takes it back (section 34). Since it changes only the catalog, an ALTER of a table of any size changes one page when the catalog row stays in its leaf: tx status shows pages=1.
ast prints Statement: ALTER TABLE, Table: <t> and Add: <column>, the column as CREATE TABLE's Columns: prints one with DEFAULT <v> after it: Add: active int NOT NULL DEFAULT 1. CREATE TABLE's Columns: prints DEFAULT the same way. explain prints AlterTable (table=<t>) and changes nothing.

Dropping and renaming columns are not here: DROP COLUMN needs every row rewritten, or a way to mark a stored column as gone. Both are the optional extra drop-rename-column.

51. What Querying changes

As in section 21, each change is made by one stage, which retires the earlier cases that checked the old contract, by name, in the manifest.

Earlier contract	Section	Changed by	Now
WHERE is one column, `=`, `<` or `>`, and one value	5, 10	`expressions`	an expression (section 40)
`and`, `or` and `not` are identifiers	4	`expressions`	keywords (section 40)
`-1` may be one token or two; `+ - / % ! <= >=` are `00202`	4	`expressions`	symbols (section 40)
an `IndexScan` is planned for a WHERE that is one comparison of the key with a number	12, 13	`expressions`	for the key bounds among the conjuncts, with a `Filter` for the rest (section 40)
a column an INSERT leaves out is `0` or the empty string	14	`nulls`	NULL (section 41)
the null bitmap is all zero, and a row with a bit set is not defined	15	`nulls`	a bit per NULL column (section 41)
`null` and `is` are identifiers	4	`nulls`	keywords (section 41)
a column is a name and a type; `ast` `Columns:` and `catalog list` print only those	19	`nulls`	`NOT NULL` after the type, printed by both (section 41)
`explain` of an INSERT prints its plan	12	`nulls`	runs the `01503` check first, and prints no plan when it fails (section 41)
`in` and `between` are identifiers	4	`in-between`	keywords (section 42)
`as` is an identifier	4	`projection`	a keyword (section 43)
a select list is `*` or column names; the plan of a SELECT is its scan, with a `Filter`	5, 10, 12	`projection`	items are expressions with aliases, under a `Project` node unless the list is `*` (section 43)
`order`, `by`, `asc` and `desc` are identifiers	4	`order-by`	keywords (section 44)
the `[EXEC]` line is `rows_examined` alone	13	`external-sort`	`sort_runs=<r>` follows it when the plan has a `Sort` (section 45)
`limit` and `offset` are identifiers	4	`limit-offset`	keywords (section 46)
in an expression, a name followed by `(` is a syntax error	5	`aggregates`	a call of an aggregate (section 47)
`group` and `having` are identifiers	4	`group-by-having`	keywords (section 48)
the `[EXEC]` line ends with `sort_runs` at most	13	`group-by-having`	`groups=<g>` follows when the plan has a `HashAggregate` or a `SortAggregate` (section 48)
`distinct` is an identifier	4	`distinct`	a keyword (section 49)
a table's columns never change after CREATE TABLE; a row's `column_count` is always the table's	15, 19	`alter-table`	ADD COLUMN, and old rows with fewer columns (section 50)
`alter`, `add`, `column` and `default` are identifiers	4	`alter-table`	keywords (section 50)
a column an INSERT leaves out is NULL	41	`alter-table`	the column's DEFAULT, NULL when it has none (section 50)
a column is a name, a type and `NOT NULL`	19, 41	`alter-table`	`DEFAULT <v>` after them, in CREATE TABLE, `ast` and `catalog list` (section 50)

52. Indexes and the Optimizer: general rules

Tables, results and the [EXEC] line are those of section 39. Tests of this part create their own tables.
The key. Every table has exactly one key, and its rows are kept in ascending key order in the table's B+Tree, as the first column's have been since section 14. Section 53 says which column is the key; whatever earlier sections say of "the first column" as the key, they say of it.
Row order. A SELECT without ORDER BY prints its rows in ascending key order, as before.

53. PRIMARY KEY and the hidden rowid (from `primary-key-rowid`)

CREATE TABLE t (name VARCHAR(20), id INT PRIMARY KEY);

primary and key are keywords: [KEYWORD_PRIMARY - primary] and [KEYWORD_KEY - key]. PRIMARY KEY comes after a column's type, before, between or after its NOT NULL and DEFAULT (section 50), at most once in a column (a second is 00302).

Which column is the key, decided when the table is created and never changed:

the column marked PRIMARY KEY, wherever it stands;
with no column marked, the first column, when it is INT: every table created before this stage is keyed this way, and still is;
otherwise, a hidden rowid.

The key column is an INT (01103) and cannot hold NULL, whether or not it is declared NOT NULL (01503). It has no DEFAULT (01104). An INSERT must give it (00406), an UPDATE cannot assign it (00801), and no two rows share it (00701). A WHERE bound on it is a key bound (section 40), so the plan is an IndexScan whatever the column's position:

Table	WHERE	Plan
`t (name VARCHAR(20), id INT PRIMARY KEY)`	`id = 5`	`IndexScan (table=t, key=5)`
`t (a INT, b INT PRIMARY KEY)`	`a = 5`	`Filter (a = 5)`, `SeqScan (table=t)`

The checks of a CREATE TABLE are those of sections 19 and 50, with the key in place of the first column. Which column is the key is read from the column list before any check: the first column marked PRIMARY KEY, else the first column when it is INT. The table does not exist yet (01101); then each column in the order written: its type (01102), its name (00408), its DEFAULT's type, range and length, NOT NULL DEFAULT NULL (01503); then, for a column marked PRIMARY KEY, that it is INT (01103) and that no earlier column was marked (01601); then, for the key column, that it has no DEFAULT (01104). Then the catalog row fits. A first column that is not INT is no longer checked. So:

CREATE TABLE	Result
`t (a int default 5, id int primary key)`	accepted: `a` is not the key
`t (a varchar(5) primary key)`	`01103`
`t (id int default 5, name float)`	`01104`, at the first column, as in section 50
`t (id int primary key default 1, b int primary key)`	`01104`, at `id`, before `b` is checked
`t (id int primary key default null)`	`01104`: a key column has no `DEFAULT`, NULL included

ADD COLUMN with PRIMARY KEY is 01601, whatever the column's type: a table always has a key already. It is checked after the column's DEFAULT and NOT NULL DEFAULT NULL (01503), and before a NOT NULL column with no DEFAULT on a table that has rows (01104).

The hidden rowid. A table keyed by a hidden rowid is keyed by an INT that no column holds:

rowid names it, in a SELECT, UPDATE or DELETE, wherever a column can be read: the select list, WHERE, ORDER BY, GROUP BY, an aggregate's argument. Its header is rowid. A bound on it is a key bound: where rowid = 2 is IndexScan (table=t, key=2).
It is not a column. * does not include it, so select *, its header and catalog list show only the declared columns. An INSERT column list or an UPDATE assignment naming it is 00402, and so is rowid anywhere in a statement on a table keyed by a column.
Values. The first INSERT into the table gets rowid 1, and each INSERT gets one more than the last rowid given, so rows come back in insertion order. A rowid is never given twice: deleting a row, even the last one, does not make its rowid free again, across sessions too.
Kept in the catalog. A rowid table's catalog row (section 19) has a fifth column, next_rowid INT, the rowid the next INSERT gets: 1 when the table is created. A table keyed by a column has the four columns of section 19, as before. An INSERT into a rowid table changes its catalog row, so the change is part of the statement and of its transaction: a committed INSERT's rowid survives a crash (section 36), and ROLLBACK takes next_rowid back with the rows (section 34), so the rowids of rows that were rolled back are given again. A statement that fails takes no rowid. TRUNCATE (section 27) keeps next_rowid as it is, so the first row after it does not get 1 again.
A table that has a column named rowid and no key column is not tested; there rowid means the column. A rowid table never holds 4294967295 rows in a test.

Printing. ast prints PRIMARY KEY after a column's NOT NULL and DEFAULT, whatever order they were typed in: Columns: [name varchar(20), id int NOT NULL PRIMARY KEY]. catalog list prints it the same way, after the type in capitals: [CATALOG] t root=2 (name VARCHAR(20), id INT PRIMARY KEY). A table keyed by an INT first column, or by a hidden rowid, prints no marker. The btree commands of a rowid table take its rowid as the key, and the Row: line of btree find gives the declared columns.

54. Secondary indexes (from `create-index`)

CREATE INDEX idx ON t (name);
DROP INDEX idx;

index and on are keywords: [KEYWORD_INDEX - index] and [KEYWORD_ON - on]. An index is a second B+Tree over one column of a table. CREATE INDEX prints Create index statement executed successfully and DROP INDEX Drop index statement executed successfully, with no count.

What an index holds. One entry per row of the table, NULLs included. An entry's key is the row's value in the indexed column followed by the row's table key (section 53), and an entry has no other payload. Entries are kept in ascending order of that pair, compared left to right:

INT values compare as unsigned numbers, VARCHAR values as bytes, a shorter string that is a prefix of a longer one first ('ab' before 'abc', 'B' before 'b'), and NULL before any value;
two entries with the same value compare by their table key.

So no two entries are equal even when values repeat. An index never stores a page or slot number: rows move when leaves split, merge or are moved by VACUUM, and their keys do not. Finding a row through an index is two descents, one in the index for the entry, one in the table for the row with the entry's table key.

The index tree is a B+Tree by the rules of the table's: its nodes are slotted pages (section 17) with a node type of their own, an internal node holds at most 3 keys, and nodes split, borrow and merge as sections 9, 17 and 28 say, by the bytes of their cells. A value of more than 255 bytes is not indexed (01604), so many entries fit in a leaf. The index's root is allocated by CREATE INDEX and, like a table's, moves only under VACUUM.

The checks, before anything changes, in this order: the table (00401); the column (00402); the index name not used by any index (01602); then every row's value is at most 255 bytes (01604). Index names are global, one name space for every table, separate from table names. CREATE INDEX may name the table's key column; such an index is never used by a plan. rowid is not a column, so an index on it is 00402.

Building. CREATE INDEX reads the table once and writes an entry for every row. Afterwards index check holds (below).

The catalog records each index: its name, its table, its column and its root page, in the catalog tree, so CREATE INDEX and DROP INDEX are part of transactions and recovery like CREATE TABLE. How an index's catalog record is encoded is free. catalog list lists tables only.

DROP INDEX frees every page of the index's tree and removes its record. DROP of a name no index has is 01603. DROP TABLE drops the table's indexes with it, their pages freed and their names free again. TRUNCATE empties them: each keeps its root, as an empty leaf, and frees its other pages. ALTER TABLE ADD COLUMN changes no index. VACUUM moves index pages like any other, and an index's root is updated in its catalog record as a table's is (section 30).

Until index-maintenance, no test writes to a table that has an index: what INSERT, UPDATE and DELETE do to an index is that stage's (section 55).

Commands.

Command	Prints
`indexes`	`[INDEX] Indexes: <n>`, then one line per index in the order they were created: `[INDEX] <name> on <table> (<column>) root=<page>`
`index check <name>`	`[INDEX] Check <name>: OK entries=<n>` when the index has exactly one entry for each row of its table, with that row's value and key, and its entries in order; otherwise `[INDEX] Check <name>: BROKEN entries=<n> rows=<m>`

index check of a name no index has is 01603; index with no subcommand or any subcommand but check, or index check with no name, is 00104. Neither command changes anything.

Plans. A conjunct of the WHERE (section 40) is an index bound when it is a column that has an index, =, and a literal of the column's type, in that order: name = 'n250' is one, name = upper and 'n250' = name are not. The plan:

a key bound on the table's key gives the IndexScan of section 40, as before;
otherwise, the first index bound in the order written gives an IndexScan on its column's index, the index created first when a column has two: IndexScan (table=<t>, index=<index>, key=<value>), the value printed as in a Filter;
otherwise, a Filter over a SeqScan.

What is left of the WHERE goes into a Filter above the scan, as in section 40. An IndexScan with no index= reads the table's own tree; one with index= reads that index, then the table for each entry it keeps.

Index on	WHERE	Plan, top first
`name`	`name = 'bob'`	`IndexScan (table=t, index=idx, key='bob')`
`name`	`name = 'bob' and n > 3`	`Filter (n > 3)`, `IndexScan (table=t, index=idx, key='bob')`
`name`	`id = 4 and name = 'bob'`	`Filter (name = 'bob')`, `IndexScan (table=t, key=4)`
`name`	`name = 'bob' and id > 3`	`Filter (name = 'bob')`, `IndexScan (table=t, range: id > 3)`: a range on the key is a key bound too
`name`	`name > 'b'`	`Filter (name > 'b')`, `SeqScan (table=t)`

UPDATE and DELETE plan the same scans under their node.

Counters. An IndexScan on an index hands up the rows of the entries whose value is its key, and those are the rows rows_examined counts: name = 'n250' over 500 distinct names examines 1, and a value no row has examines 0. The [EXEC] line gains index_lookups=<k> right after rows_examined=<n> when the plan has an IndexScan on an index: k is the number of rows looked up in the table through an entry. Here k equals rows_examined; they differ from composite-covering.

[EXEC] rows_examined=1 index_lookups=1

Printing. ast prints Statement: CREATE INDEX, Index: <name>, Table: <t>, Columns: [<column>]; and Statement: DROP INDEX, Index: <name>. explain prints CreateIndex (index=<name>, table=<t>) and DropIndex (index=<name>) and changes nothing. Like explain of a CREATE TABLE, it runs the checks first and prints only the error of one that fails.

55. Keeping indexes true (from `index-maintenance`)

From this stage every statement that writes a table's rows writes each of its indexes too, in the same statement, so that index check (section 54) holds after every statement, committed or not:

Statement	Each index of the table
INSERT	gains the new row's entry
DELETE	loses the entry of each deleted row
UPDATE that assigns the indexed column	loses the row's old entry and gains its new one; an assignment of the value the row already has changes nothing in the index
UPDATE that does not assign the indexed column	is not written: none of its pages changes
TRUNCATE	is emptied, as section 54 says

Checks. A value of more than 255 bytes for an indexed column is 01604: for an INSERT after the checks of section 19, for an UPDATE after the checks of its assignments. It is a check, so it comes before what only writing finds, such as a key the table already has (00701), and the statement changes nothing.
One statement, one change. A statement that fails changes no index, whatever it had already written: an INSERT of a key the table already has (00701) leaves no entry behind, as it leaves no row. Index pages are pages, so section 34 already says how: ROLLBACK, a statement that fails and recovery after a crash (section 36) take index pages back exactly as they take table pages back.
Rows are found before they change. An UPDATE or DELETE changes the rows its WHERE matched before it changed any, each once, whatever its scan. So update t set name = 'b' where name = 'a' planned on an index on name changes every row that had 'a', and none of them twice, even though the entries it writes land in the index it is reading.
Plans and counters are those of section 54 for UPDATE and DELETE as for SELECT: an UPDATE or DELETE whose WHERE has an index bound uses the index, and its [EXEC] line has index_lookups.

> update t set n = 0 where name = 'n7';
Update statement executed successfully (1 rows)
[EXEC] rows_examined=1 index_lookups=1

Pages. In a transaction, tx status counts index pages with the table's. An UPDATE of one row that assigns only columns no index has changes the table's leaf alone: pages=1 when the row stays in its leaf. One that assigns an indexed column changes the index's leaves too: pages=2 or more.

56. Duplicates, ranges and order in an index (from `index-duplicates-ranges`)

Nothing about an entry changes: it was built for this stage. A value that repeats makes entries that differ in their table key (section 54), so an index needs no list of rows per value, and a range is a walk along the leaves.

Index bounds. A conjunct of the WHERE is an index bound when it is a column that has an index, an operator =, <, >, <= or >=, and a literal of the column's type, in that order, as a key bound is (section 40). name >= 'b' is one; 'b' <= name, name is null and name = null are not.

Plans, in this order:

a key bound on the table's key gives the IndexScan of section 40;
otherwise the first = index bound in the order written gives IndexScan (table=<t>, index=<i>, key=<value>), as in section 54;
otherwise the column of the first index bound in the order written is the scan's column: its first lower bound (> or >=) and its first upper bound (< or <=) are the range, lower first, printed as a range on the table's key is: IndexScan (table=t, index=idx, range: name >= 'b' AND name < 'c');
otherwise a Filter over a SeqScan.

The index used for a column is the one created first. What is left of the WHERE goes into a Filter above the scan, as in section 40.

Index on	WHERE	Plan, top first
`name`	`name >= 'b' and name < 'c'`	`IndexScan (table=t, index=idx, range: name >= 'b' AND name < 'c')`
`name`	`name > 'b' and n = 1`	`Filter (n = 1)`, `IndexScan (table=t, index=idx, range: name > 'b')`
`name`, `n`	`name > 'b' and n = 1`	`Filter (name > 'b')`, `IndexScan (table=t, index=by_n, key=1)`
`name`	`name is null`	`Filter (name IS NULL)`, `SeqScan (table=t)`

What a range admits. Values compare as section 54 orders them: INT as unsigned numbers, VARCHAR as bytes with a prefix first. NULL is in no range and equals nothing: an index scan never hands up a row whose value is NULL, as the comparison it stands for would be unknown (section 41). An IndexScan on an index hands up the rows of the entries its key or range admits, counted by rows_examined and index_lookups alike. The entry it reads to know the range has ended is not a row and is not counted.

Row order. An IndexScan on an index hands up its rows in the order of their entries: by value, then by table key. So a SELECT without ORDER BY whose plan reads an index prints its rows in that order, and section 52's "ascending key order" holds for the other plans. ORDER BY sorts the rows it is given as section 44 says, whatever the scan.

Sections 44 and 48 lean on rows arriving in ascending key order. They hold as written for a scan that hands rows up in that order: a SeqScan, an IndexScan of the table's own tree, and an = scan of an index (its entries share one value, so they come in key order). For a range scan of an index:

ORDER BY on the table's key, ascending, is not skipped: the plan has its Sort;
rows that tie on every ORDER BY key keep the order the scan handed them up, by value then by key;
GROUP BY whose first key is the table's key is a HashAggregate, not a SortAggregate;
groups with no ORDER BY come out in the order their first row arrived, which is index order.

> select id, name from t where name >= 'b' and name < 'c';
id | name
7 | b
2 | ba
5 | bz
(3 rows)
[EXEC] rows_examined=3 index_lookups=3

57. UNIQUE (from `unique-constraint`)

CREATE UNIQUE INDEX by_email ON t (email);
CREATE TABLE t (id INT, email VARCHAR(40) UNIQUE);

unique is a keyword: [KEYWORD_UNIQUE - unique]. A unique index is an index of section 54 that also refuses a second row with the same value. It is built, kept, planned and dropped as any index is.

Inline. UNIQUE after a column's type, before, between or after its other options (NOT NULL, DEFAULT, PRIMARY KEY), at most once in a column (a second is 00302), makes CREATE TABLE create a unique index on that column right after the table, named <table>_<column>_key: create table t (id int, email varchar(40) unique); creates t_email_key. When that name is taken the CREATE TABLE is 01602 and creates nothing; that check comes last, after every check of section 53 and after the catalog row fits. ADD COLUMN takes no UNIQUE (00302): create the index after it.
What conflicts. Two rows conflict when their values in the column are equal and not NULL. Only the value is compared, never the table key that follows it in the entry. NULLs never conflict, so any number of rows may hold NULL.
INSERT and UPDATE. A row that would conflict with another row is 01605, and the statement changes nothing. It is found after every other check, as 00701 is: for an INSERT the key (00701) first, then each unique index in the order they were created. An UPDATE checks each row as it changes it, in the order it found them (section 55), so an UPDATE that would give two rows one value fails as a whole: with values 1 and 2, update u set n = 2 is 01605 when it reaches row 1, and changes nothing. An UPDATE that leaves a row's value as it was never conflicts with that row.
CREATE UNIQUE INDEX over a table where two rows already conflict is 01606, after the checks of section 54, and creates nothing: no index, no page left allocated, the name still free.
Printing. indexes ends a unique index's line with UNIQUE: [INDEX] t_email_key on t (email) root=4 UNIQUE. ast prints Statement: CREATE UNIQUE INDEX, then the lines of section 54; in a CREATE TABLE's Columns: it prints UNIQUE after NOT NULL and DEFAULT and before PRIMARY KEY. catalog list does not show it: the index is not a column. explain prints CreateIndex (index=<name>, table=<t>, unique).

> insert into t (id, email) values (2, 'a@x');
[ERROR:01605] email 'a@x' is already in t_email_key

58. Composite keys and index-only scans (from `composite-covering`)

CREATE INDEX by_city_age ON t (city, age);
CREATE UNIQUE INDEX by_ab ON t (a, b);

Several columns. An index may list one or more columns of its table, each once (00402 for a column the table does not have, 00408 for one listed twice). Its entry's key is the row's value in each column, in the order listed, then the table key; entries compare column by column, left to right, by the rules of section 54, then by the table key. A NULL in any column is stored like any value and sorts first in its column. The 255-byte limit of 01604 is on the values of the entry together, each counted by its bytes (4 for an INT, its length for a VARCHAR, 0 for NULL): two VARCHAR values of 150 bytes in one entry are 01604.

indexes lists the columns in order: [INDEX] by_city_age on t (city, age) root=6. ast prints Columns: [city, age]. Inline UNIQUE stays on one column (section 57).

UNIQUE on several columns. Two rows conflict when they are equal in every column of the index and none of those values is NULL: on (a, b), ('a', 1) and ('a', 2) do not conflict, and ('a', NULL) twice does not either.

Which conjuncts an index can use. An index helps a WHERE through a prefix of its columns: = index bounds on its first column, its second, and so on, as many in a row as the WHERE has, then at most one range on the next column. On (city, age): city = 'x' uses one column, city = 'x' and age = 30 two, city = 'x' and age > 20 one = and a range; age = 30 alone uses none, since the entries are not in age order. Index bounds are the conjuncts of section 56; the first lower and first upper bound on the range column form the range.

Plans, in this order:

a key bound on the table's key gives the table's IndexScan (section 40);
otherwise, of the indexes whose first column has an = index bound, the one that uses the most = bounds, then the one with a range after them, then the one whose first column's = comes first in the order written, then the one created first;
otherwise, take the first index bound in the order written whose column is the first column of some index: the index created first among those that start with that column, with its range (section 56);
otherwise a Filter over a SeqScan.

The scan prints its = values in index column order, after key=, in parentheses when the index has more than one column, and its range after them:

Index on	WHERE	Scan
`(city, age)`	`city = 'x' and age = 30`	`IndexScan (table=t, index=ca, key=('x', 30))`
`(city, age)`	`age = 30 and city = 'x'`	`IndexScan (table=t, index=ca, key=('x', 30))`
`(city, age)`	`city = 'x'`	`IndexScan (table=t, index=ca, key=('x'))`
`(city, age)`	`city = 'x' and age > 20`	`IndexScan (table=t, index=ca, key=('x'), range: age > 20)`
`(city, age)`	`city > 'm'`	`IndexScan (table=t, index=ca, range: city > 'm')`
`(city, age)`	`age = 30`	`Filter (age = 30)`, `SeqScan (table=t)`
`(city, age)`	`age > 3 and city > 'm'`	`Filter (age > 3)`, `IndexScan (table=t, index=ca, range: city > 'm')`: only a first column starts a range

A one-column index prints as in sections 54 and 56: key='x', range: name > 'b'. What is left of the WHERE goes into a Filter above the scan.

A scan of an index hands up its rows in key order only when = fixes every column of the index: otherwise they come by the columns it leaves free, and section 56's rules for a range scan apply (ORDER BY on the key keeps its Sort, GROUP BY on the key is a HashAggregate).

Index-only scans. An index covers a statement when every column the statement reads is one of the index's columns or the table's key (a rowid included): the columns of the select list, the WHERE, ORDER BY, GROUP BY, HAVING and every aggregate's argument; select * reads every column. A SELECT whose chosen scan reads an index that covers it reads no row of the table: the scan hands up what the entries hold, and is printed IndexOnlyScan with the same details:

[PLAN] select city, id from t where city = 'x'
[PLAN]   └── Project (cols=[city, id])
[PLAN]       └── IndexOnlyScan (table=t, index=ca, key=('x'))

rows_examined counts the entries an IndexOnlyScan hands up, as for any scan, and index_lookups is 0, since no row is looked up: [EXEC] rows_examined=3 index_lookups=0. Covering never changes which index is chosen, only how the chosen one is read. UPDATE and DELETE always read the row: their scans are never index-only. From this stage an earlier plan whose index covers the statement prints IndexOnlyScan in place of IndexScan, with the same rows.

59. ANALYZE and statistics (from `analyze-stats`)

ANALYZE t;

analyze is a keyword: [KEYWORD_ANALYZE - analyze]. ANALYZE reads the whole table once, computes its statistics, stores them in the catalog in place of any it had, and prints Analyze statement executed successfully. A table name is required (analyze; is 00302), and a table that does not exist is 01607.

What is counted:

Statistic	Meaning
`rows`	the number of rows
`pages`	the number of pages of the table's tree, internal nodes and overflow pages included
per column `ndv`	the number of distinct values that are not NULL, compared as section 54 compares them: `'B'` and `'b'` are two
per column `min`, `max`	the smallest and largest value that is not NULL, by the order of section 54; NULL when the column has no such value
per column `nulls`	the number of rows whose value is NULL

A rowid (section 53) is not a column and has no line. A table with no row has rows=0, its root leaf as its one page, and in each column ndv=0 min=NULL max=NULL nulls=0.

Never automatic. Statistics change only when ANALYZE runs. INSERT, UPDATE, DELETE, TRUNCATE, VACUUM and ALTER TABLE leave them as they were, however far the table drifts from them; a column added after the last ANALYZE has no statistics line until the next one. DROP TABLE drops them with the table.

Stored in the catalog, so they survive reopening and follow transactions: ANALYZE inside a transaction changes catalog pages the transaction owns, and ROLLBACK brings back the statistics the table had before (section 34). How they are encoded is free.

stats <table> prints them, and changes nothing:

[STATS] t rows=1000 pages=42
[STATS]   id ndv=1000 min=1 max=1000 nulls=0
[STATS]   city ndv=10 min='c0' max='c9' nulls=5

One line for the table, then one per column in table order, indented two spaces after [STATS]. Values print as literals do (section 40): numbers bare, strings in single quotes, NULL as NULL. A table that has never been analysed prints [STATS] t no statistics. stats of a table that does not exist is 00401; stats with no table is 00104.

Printing. ast prints Statement: ANALYZE and Table: <t>. explain takes no ANALYZE statement (explain analyze t; is 00302): from explain-analyze, explain analyze begins EXPLAIN ANALYZE (section 61), and explain analyze t; is 00301.

PostgreSQL also keeps a histogram and the most common values of each column, and runs ANALYZE by itself once enough rows have changed. Distinct counts with a minimum and a maximum are enough for the estimates of section 60; a histogram would only make them closer on skewed data.

60. Estimates, cost and choosing a scan (from `cost-model`)

From this stage the planner of a SELECT, UPDATE or DELETE on a table with statistics (section 59) estimates how many rows each node hands up, prices each scan it could use, and takes the cheapest. On a table with no statistics nothing changes: the rules of sections 40, 54, 56 and 58 choose the scan, and explain prints no estimates. ANALYZE is never automatic, so a test that wants the planner to count must run it.

All arithmetic is on integers or exact fractions, so every implementation prints the same numbers. In this section R and P are the rows and pages of the table's statistics, and ndv, min, max and nulls those of a column.

Selectivity of a conjunct (section 40), a fraction from 0 to 1:

Conjunct	Selectivity
`c = v`, `c` a column, `v` a literal	`1 / ndv`; `0` when `ndv` is 0
`c < v`, `c <= v`, `c > v`, `c >= v`, `c` an `INT` column, `v` a number	`(v − min) / (max − min + 1)`, `(v − min + 1) / (…)`, `(max − v) / (…)`, `(max − v + 1) / (…)`, each clamped to 0..1; `0` when `min` is NULL
`c is null`, `c is not null`	`nulls / R`, `(R − nulls) / R`; `0` when `R` is 0
any other conjunct (a VARCHAR range, OR, NOT, IN, an expression)	`1 / 3`

A literal on the left counts as "any other". The conjuncts of a WHERE multiply: a node's estimated rows are floor(R × s1 × s2 × …) over every conjunct applied at that node or below it, computed exactly before the floor. So over 1000 rows with ages 0 to 99, age < 5 is floor(1000 × 5/100) = 50, and age < 5 and city = 'c1' with ten cities is floor(1000 × 5/100 × 1/10) = 5.

Estimated rows of each node:

Node	Rows
`SeqScan`	`R`
`IndexScan`, `IndexOnlyScan`	`R` times the selectivities of the conjuncts the scan uses, floored
`Filter`	its input's conjuncts and its own, as above
`Project`, `Sort`, `TopN`	as its child
`Limit`	the smaller of its child's rows and its LIMIT plus OFFSET
`Aggregate` with no GROUP BY	`1`
`HashAggregate`, `SortAggregate`, `Distinct`	as its child

Cost of a scan, in page reads. Dt is the number of levels of the table's tree and Di of the index's tree, read when planning (a root that is a leaf is one level); E is the scan's estimated rows:

Scan	Cost
`SeqScan`	`P`
`IndexScan` of the table's tree (a key bound)	`Dt + ceil(E × P / R)`; `Dt` when `R` is 0
`IndexScan` of an index	`Di + E × Dt`
`IndexOnlyScan`	`Di + ceil(E / 100)`

Every other node costs what its child costs: only scans read pages in this model.

Choosing. A key bound on the table's key gives the table's IndexScan, as before. Otherwise the candidates are a SeqScan and, for each index whose first column has an index bound, the scan section 58 would make of it, an IndexOnlyScan when the index covers the statement (always a plain IndexScan for UPDATE and DELETE). The one with the lowest cost wins; a tie goes to the SeqScan, then to the index created first. So an index stops being used when it would find too many rows: every row it finds costs a descent of the table.

Printing. On a table with statistics every node of explain ends with (rows=<E> cost=<C>):

[PLAN] select * from t where city = 'c7'
[PLAN]   └── IndexScan (table=t, index=by_city, key='c7') (rows=1 cost=<C>)

Here <C> is Di + 1 × Dt for that table and index. A statement node (Update, Delete) prints none; the scan under it does. The [EXEC] line does not change.

Details, so every implementation prints the same numbers:

c = NULL keeps no row: selectivity 0.
The rowid (section 53) has no statistics line: rowid = v is 1 / R (0 when R is 0), any other conjunct on it 1 / 3. A column added after the last ANALYZE has no line either, and every conjunct on it is 1 / 3.
A Filter above an aggregate (a HAVING) has its child's estimate times its own conjuncts, each 1 / 3 since they read aggregates or groups: over an Aggregate with no GROUP BY that is floor(1 × 1/3) = 0.
E in a scan's cost is the scan's floored estimate, the selectivities of every bound it uses multiplied: id >= 999 over keys 1 to 1000 is 2 rows and costs Dt + ceil(2 × P / R).
Dt and Di are counted at plan time from the root down; a root that is a leaf is 1.
Candidates are compared in this order: the SeqScan first, then the indexes in the order they were created; a later one replaces the best so far only when it is strictly cheaper.
Each index is priced as the scan section 58 would make of it alone, index-only for a SELECT it covers.

Stale statistics are believed. The planner trusts the statistics it has, however old. After update t set city = 'x' turns 2000 distinct cities into one, the plan above still says rows=1 and still reads the index, and running it shows the price: rows_examined=2000 index_lookups=2000. After ANALYZE, ndv=1 makes the estimate 2000, the index costs Di + 2000 × Dt, and the plan is a SeqScan.

61. EXPLAIN ANALYZE (from `explain-analyze`)

EXPLAIN ANALYZE SELECT ...;

explain analyze runs the SELECT's plan to the end, throws its rows away, and prints the plan with what each node actually did beside what the planner expected:

[PLAN] select * from t where v = 'c7'
[PLAN]   └── IndexScan (table=t, index=by_v, key='c7') (rows=1 cost=6) (actual rows=1 pages=6)
[TIME] 0.214 ms

The first line is [PLAN] and the SELECT as typed after explain analyze, by the rules of section 12.
Each node line is the line explain prints (section 60: with (rows=<E> cost=<C>) when the table has statistics, without it otherwise), then (actual rows=<A> pages=<P>).
- A is the number of rows the node handed up to its parent, or, for the top node, out of the plan.
- P is the number of different pages the node itself read from the pool while it ran, its children's not counted: every page of the table's tree a SeqScan visited, the index pages and table pages an index IndexScan visited, the index pages alone of an IndexOnlyScan, and 0 for every node that reads no page (Filter, Project, Sort, Limit, the aggregates). A page counts once per node however often it was read, and whether it was in the pool already or not.
Then one line starting with [TIME] , whose rest is free: tests never read it. It is the only place a timing may appear (section 1).
No result rows, no header, no footer and no [EXEC] line are printed.

A node that is never asked for a row hands up 0 and reads 0 pages, even if it found its first leaf when the plan was opened. Page by page:

a SeqScan counts the pages on its way down to the first leaf and every leaf it walks;
an IndexScan of the table's key counts its descent and every leaf it walks, the one it reads to see that the range has ended included;
an IndexScan of an index counts the index pages it visits and the table pages of every lookup;
an IndexOnlyScan counts index pages only;
a Sort reads its temporary file (section 45), which is not the pool: 0. A plan stops early when its top node needs no more rows, as it does without explain analyze (section 46): under limit 5, a scan of 1000 rows hands up 5.

Only a SELECT can follow explain analyze: an INSERT, UPDATE, DELETE or any other statement is 01608, and runs nothing. Text that is no statement at all, as in explain analyze t;, is 00301, as it is after explain. The SELECT is checked as running it would be, and a check that fails prints its error and no [PLAN] line; an error while it runs (section 39) prints its error line and nothing else.

62. Logical plans and three rewrites (from `rewrite-rules`)

From this stage the planner works in two steps. It first builds a logical plan, which says what the SELECT asks for and nothing about how; then it rewrites it with exactly three rules, and only then chooses scans (sections 40 to 60). A rewrite never changes the rows a statement prints, nor their order.

The logical plan. explain logical <select> prints it, by the rules of section 12, and runs nothing. It is the plan explain printed before this stage with three differences:

the scan is Get (table=<t>): no key, index or range is chosen yet;
the whole WHERE, as typed, is one Filter right above the Get, with no bound taken out;
a HashAggregate or SortAggregate is printed Aggregate (keys=[...], aggs=[...]).

It prints no estimates. Only a SELECT may follow explain logical: any other statement is 00302. logical is not a keyword: tokenize prints it as an identifier, and only explain reads it.

[PLAN] select name from t where city = 'x' and 2 > 1
[PLAN]   └── Project (cols=[name])
[PLAN]       └── Filter ((city = 'x') AND (2 > 1))
[PLAN]           └── Get (table=t)

Rule 1, constant folding. In the WHERE and the HAVING, every subexpression that reads no column and calls no aggregate is evaluated once, while planning, by the rules of sections 40 and 41, and replaced by its value: `id = 2

3becomesid = 5, so it is a key bound; 'a' = 'a'becomestrue. A subexpression whose evaluation fails (01501, 01502`) is left as written, and fails only if a row reaches it, as before. Then, among the conjuncts:

a conjunct that is true is dropped;
a conjunct that is false or NULL keeps no row: the Filter and the scan under it are replaced by one node, Empty, which hands up no row and reads nothing, so the statement examines 0 rows. A SELECT with an aggregate and no GROUP BY still prints its one row (COUNT(*) is 0).
in the HAVING, a conjunct that is false or NULL is printed false and keeps no group. With GROUP BY it reads no column, so rule 2 moves it to the WHERE, where it becomes Empty; with no GROUP BY it stays in the HAVING's Filter, so the one aggregate row is dropped.

The select list and ORDER BY are not folded, so headers do not change.

Rule 2, HAVING pushdown. A conjunct of the HAVING that calls no aggregate and reads only columns that are GROUP BY keys moves to the end of the WHERE: group by dept having dept = 'eng' filters rows before they are grouped, so fewer groups are formed (groups= counts fewer), and the moved conjunct may become a key or index bound. When the HAVING loses every conjunct, its Filter goes.

Rule 3, index condition pushdown. When the scan is an IndexScan of an index (not an IndexOnlyScan), each conjunct left for the Filter above it that reads only the index's columns and the table key moves into the scan, which tests it on the entry before looking the row up. The scan prints those conjuncts after its key or range, as filter: <expression>, joined by AND in the order written; the Filter above keeps the rest, and goes when nothing is left. rows_examined and index_lookups count only the entries that pass:

[PLAN] select * from t where city = 'x' and age % 2 = 0
[PLAN]   └── IndexScan (table=t, index=ca, key=('x'), filter: (age % 2) = 0)

With an index on (city, age) and ten rows of city 'x', five of them with an even age, this examines 5 rows with 5 lookups, where --no-rewrite looks up all 10 and lets the Filter drop five.

Details.

Folding replaces constant subexpressions wherever they are, but simplifies only whole conjuncts: (1 = 1) or city = 'q' prints Filter (true OR (city = 'q')). A folded truth value prints true or false; a string as a string literal; NULL as NULL. An integer result outside 0..4294967295, or one whose evaluation fails, is left as written, with its children unfolded.
Empty under an UPDATE or DELETE changes 0 rows and examines 0. With statistics it prints (rows=0 cost=0), and under explain analyze (actual rows=0 pages=0).
HAVING pushdown happens only with a GROUP BY: without one, a HAVING that is false keeps no row, while the same conjunct in the WHERE would leave one row of aggregates. A GROUP BY key counts only when it is the bare column; a conjunct that reads no column at all moves too.
filter: holds the moved conjuncts as one expression, joined by AND in the order written and printed as section 40 prints it: filter: ((age % 2) = 0) AND (age != 25). A conjunct that reads no column counts as reading only the index's. Pushdown into the index happens after the scan is chosen, so it does not change costs; the scan's rows= multiplies in the moved conjuncts, and actual rows counts the entries that pass. It applies under UPDATE and DELETE too.
explain logical prints no estimates; a SELECT with no WHERE is just its Get under the nodes above, and an ORDER BY that needs no Sort (section 44) has none there either.

--no-rewrite on the command line turns all three rules off: plans are those of section 60, and every statement prints the same rows as with the rules on. Tests use it to show that a rewrite changes how much is read, never what is printed.

63. Top-N and ordered index scans (from `topn-index-order`)

Two ways to avoid sorting everything. Neither changes the rows a statement prints or their order (section 44); they change the plan, sort_runs and how much is read.

Top-N. When a Sort hands its rows up to a Limit, with nothing between them but a Project, and the Limit's count is at least 1, the Sort is replaced by TopN (key=<keys as in Sort>, n=<count + offset>). A TopN keeps only the best n rows it has seen so far, so it never needs more memory than n rows, and it hands up the same rows, in the same order, as the Sort would have handed up first: ties keep the order they arrived in (section 44). It is used only when n is at most --sort-memory (section 45); otherwise the Sort stays, and spills as before.

[PLAN] select name from t order by name limit 5 offset 10
[PLAN]   └── Limit (count=5, offset=10)
[PLAN]       └── Project (cols=[name])
[PLAN]           └── TopN (key=name ASC, n=15)
[PLAN]               └── SeqScan (table=t)

A TopN writes no run: the [EXEC] line keeps its sort_runs field, with 0. It reads every row below it, so rows_examined does not change. It replaces a Sort right under the Limit or under a Project right under it, the Sort of a DISTINCT included; explain logical never shows one.

Ordered index scans. An index hands up its entries in its own order: by its first column, then its second, then the table key, NULL first in each (section 58). A one-key ORDER BY <c> ASC, c a column, needs no sort when the chosen scan reads an index whose columns before c are all fixed by = and whose next column is c: the scan already hands up the rows in that order, ties in key order, exactly as section 44 sorts them. The plan then has no Sort (and no TopN), and the scan prints order=asc last:

[PLAN] select name from t order by name limit 3
[PLAN]   └── Limit (count=3, offset=0)
[PLAN]       └── Project (cols=[name])
[PLAN]           └── IndexScan (table=t, index=by_name, order=asc)

Under a Limit, such a scan stops once the Limit has its rows: limit 3 examines 3 rows with 3 lookups.

Choosing it. An index whose first column is c may be chosen for the order alone, with no bound: it then reads every entry, NULLs included, and prints no key or range. On a table with no statistics it is chosen when the statement has an ORDER BY of that one key and no key bound or index bound chooses another scan (rules 1 to 3 of section 58). On a table with statistics it is one more candidate of section 60, priced Di + E × Dt with E the rows the Limit needs (count + offset) when the statement has a Limit and the scan has no Filter above it, or all the rows the scan would hand up otherwise; an IndexOnlyScan is Di + ceil(E / 100). Its rival, a SeqScan with a Sort or TopN, costs P.
Which statements. A SELECT with no GROUP BY and no aggregate, whose one ORDER BY key is a column (or an alias of one) other than the table's key, which section 44 already orders. The scan gives the order only when the number of its leading = columns is exactly the position of c: when c itself is fixed by =, the Sort stays. Without statistics, an order-only scan is tried only when no key bound and no index bound chose a scan, the index created first among those whose first column is c, index-only when it covers the statement. With statistics, the order-only candidates are compared after the others, each replacing the best so far only when strictly cheaper; "no Filter above it" means the WHERE has no conjunct at all. An order-only scan prints rows=R, as section 60 says of a scan that uses no conjunct, and the cost computed with the E above.
DESC. Leaves are linked one way, so this engine never reads an index backwards: ORDER BY <c> DESC keeps its Sort or TopN.
Ranges and estimates follow sections 56 and 60: order=asc is printed after the key, range and filter: of the scan, and its estimate after that.

64. What Indexes and the Optimizer changes

As in section 21, each change is made by one stage, which retires the earlier cases that checked the old contract, by name, in the manifest.

Earlier contract	Section	Changed by	Now
the first column is the key, and a first column that is not `INT` is `01103`	14, 19	`primary-key-rowid`	the key is the `PRIMARY KEY` column, else an `INT` first column, else a hidden rowid (section 53)
`primary` and `key` are identifiers	4	`primary-key-rowid`	keywords (section 53)
`00406`, `00801`, `01104`, `01503` and the key bounds of section 40 name the first column	3, 40, 41, 50	`primary-key-rowid`	they name the key column (section 53)
a catalog row has four columns	19	`primary-key-rowid`	a rowid table's has a fifth, `next_rowid` (section 53)
`index` and `on` are identifiers	4	`create-index`	keywords (section 54)
the catalog holds tables only; DROP TABLE, TRUNCATE and VACUUM know only tables' trees	19, 27, 30	`create-index`	the catalog records indexes too, and those statements carry a table's indexes with it (section 54)
an `IndexScan` reads the table's own tree	12, 40	`create-index`	with `index=<name>`, it reads that index and then the table (section 54)
the `[EXEC]` line is `rows_examined`, then `sort_runs` and `groups`	13, 39	`create-index`	`index_lookups=<k>` follows `rows_examined` when the plan has an `IndexScan` on an index (section 54)
an INSERT, UPDATE or DELETE writes the table's tree	10, 15	`index-maintenance`	it writes each of the table's indexes too, in the same statement (section 55)
only `=` on an indexed column uses its index	54	`index-duplicates-ranges`	`<`, `>`, `<=` and `>=` do too, as a range (section 56)
a SELECT without ORDER BY prints its rows in ascending key order	39, 52	`index-duplicates-ranges`	in index order when its plan reads an index (section 56)
`unique` is an identifier	4	`unique-constraint`	a keyword (section 57)
a column's options are `NOT NULL`, `DEFAULT` and `PRIMARY KEY`	50, 53	`unique-constraint`	and `UNIQUE`, which creates an index with the table (section 57)
an index has one column	54, 57	`composite-covering`	one or more, used through a prefix of them (section 58)
an index scan looks every row up in the table	54	`composite-covering`	an `IndexOnlyScan` reads only the index when it covers the SELECT, with `index_lookups=0` (section 58)
`analyze` is an identifier	4	`analyze-stats`	a keyword (section 59)
the scan is chosen by rules	40, 54, 56, 58	`cost-model`	on a table with statistics, by estimated cost; the rules stay for a table without (section 60)
a plan node prints its name and details	12	`cost-model`	and `(rows=<E> cost=<C>)` on a table with statistics (section 60)
an index chosen by rule is read index-only whenever it covers the SELECT, but covering never changes the choice	58	`cost-model`	on a table with statistics, covering lowers the cost and can change the choice (section 60)
timings appear nowhere	1	`explain-analyze`	only on the `[TIME]` line of `explain analyze`, which tests never read (section 61)
a key bound is the key, an operator and a number; an expression is not	40	`rewrite-rules`	constant subexpressions of the WHERE are folded first, so `id = 2 + 3` is a key bound (section 62)
a WHERE that can never hold is a `Filter` over a scan	40	`rewrite-rules`	`Empty`, which reads nothing (section 62)
a HAVING is a `Filter` above the aggregate	48	`rewrite-rules`	a conjunct on grouping columns alone moves to the WHERE (section 62)
a `Filter` above an index scan tests rows after the lookup	54, 58	`rewrite-rules`	conjuncts on the index's columns move into the scan as `filter:` (section 62)
the command line options are `--db`, `-c`, `--cache-pages` and `--sort-memory`	2	`rewrite-rules`	and `--no-rewrite` (section 62)
ORDER BY is a `Sort` unless the key order gives it	44	`topn-index-order`	a `TopN` under a Limit, and no `Sort` when an index scan gives the order (section 63)
a scan of an index is chosen only for a bound	54, 56, 58, 60	`topn-index-order`	also for the order of a one-key ORDER BY (section 63)

65. Joins and Relations: general rules

Tables, results and the [EXEC] line are those of sections 39 and 52. Tests of this part create their own tables.
Row order. A SELECT that reads one table prints its rows in the order of section 56, as before. A SELECT that joins tables prints them in the order its join gives, which the section of each join states. Outside the one case per join that reads that order, tests of a join use an ORDER BY that fixes the place of every row.
Counters over a whole plan. rows_examined is the number of rows handed up by every scan of the plan, added up over all its scans and over every time each one runs; index_lookups is added up the same way. A plan with one scan that runs once counts as it always has.

66. Names, aliases and the binder (from `qualified-names`)

SELECT u.name FROM users u WHERE u.id = 1;
SELECT u.name FROM users AS u;

Before a statement is planned, every name in it is looked up and tied to one table and one column. This is the binder: until now it had one table to look in, and from here a FROM may hold several.

The dot. . is a symbol: u.name is [IDENTIFIER - u], [SYMBOL - .], [IDENTIFIER - name].
FROM entries. A SELECT's FROM names a table, followed by an optional alias, with or without AS: from users u, from users as u. The alias is an identifier. Each table the FROM names is an entry, and an entry's name is its alias when it has one, its table's name otherwise.
References. A column is written bare, name, or qualified, u.name. In q.c, q must be the name of an entry (01701), and an alias hides its table's name: select users.id from users u is 01701. c must then be a column of that entry's table (00402); u.rowid reads the hidden rowid of section 53. A bare c is the column c of the entry whose table has one, alias or not (00402 when none has): select name from users u reads u.name.
q.* in a select list is every column of entry q, in table order. Unlike *, it may stand among other items: select u.*, u.id * 2 from users u. Its q is checked as a qualifier is (01701). It is an item only: anywhere else, and with an AS after it, it is 00302.
Headers. An item that is a column, bare or qualified, has the column's name as its header: select u.name from users u prints the header name. Any other item keeps the header of section 43, printed as typed: u.id * 2. An AS alias still wins.
Everywhere a column can stand in a SELECT, a qualified name can too: the select list, WHERE, GROUP BY, HAVING, ORDER BY and an aggregate's argument. In ORDER BY a bare name may still mean an item's alias (section 44); a qualified name is always a column.
Same column, any spelling. Where an earlier section compares two expressions by how they print (a GROUP BY key and the select list, section 48; DISTINCT and its ORDER BY, section 49), a column compares by the column it is bound to: with from emp e, select dept ... group by e.dept is allowed.
UPDATE and DELETE take no alias. Whether they accept a qualified name is not tested.
Checks. The FROM's table is checked first (00401). Then, at each place an earlier section checks a column (00402), in the same order, a reference is checked by its qualifier (01701) and then its column (00402); an item q.* by its qualifier.

Plans. A scan of an entry with an alias prints it after the table: SeqScan (table=users, alias=u), IndexScan (table=users, alias=u, key=1). A scan of an entry with no alias prints as before. The alias comes right after the table on every scan: IndexScan (table=users, alias=u, index=by_name, key='x'). Every other node prints its expressions as typed, as before. A bound may be qualified: u.id = 1 is a key bound and u.name = 'x' an index bound, and a range prints its column as typed: range: u.id >= 3.

explain logical prints what the binder made of the statement: every column reference with its entry's name in front, even one typed bare, in every node; and Get (table=<t>, alias=<a>) for an entry with an alias. AS aliases of the select list are printed as in section 43, and q.* as typed. An ORDER BY key that is an item's alias is not a column reference, and stays bare: Sort (key=d ASC).

[PLAN] select name, count(*) from users u where id > 1 group by name
[PLAN]   └── Project (cols=[u.name, COUNT(*)])
[PLAN]       └── Aggregate (keys=[u.name], aggs=[COUNT(*)])
[PLAN]           └── Filter (u.id > 1)
[PLAN]               └── Get (table=users, alias=u)

A statement with no alias is bound to its table's name: explain logical select name from t prints Project (cols=[t.name]) over Get (table=t).

ast prints Table: <t> AS <alias> for a FROM with an alias, whether AS was typed or not, and Table: <t> without one, as before. Columns are printed as typed: Columns: [u.name, u.*].

67. Joining tables: the nested loop (from `nested-loop-join`)

SELECT ... FROM a, b [WHERE ...];
SELECT ... FROM a [INNER] JOIN b ON <condition> [WHERE ...];
SELECT ... FROM a CROSS JOIN b;

join, inner and cross are keywords; on already is (section 54).

The FROM is a list of entries (section 66) read left to right. After the first, each entry comes after ,, after CROSS JOIN, or after JOIN or INNER JOIN with an ON and a condition after it. JOIN without its ON, and CROSS JOIN or , with one, are 00302. A FROM may have any number of entries: from a join b on ... join c on ....

What a join means. Joining A and B gives every pair of a row of A and a row of B, each pair one row with A's columns then B's, for which the condition is true. , and CROSS JOIN have no condition, so they give every pair. Entries join left to right: a, b, c joins a with b, then that with c. The WHERE then keeps the joined rows for which it is true. So for these joins ON and WHERE mean the same: from a join b on X where Y gives the rows of from a, b where X and Y. A condition is a truth value (00403 otherwise), and a pair for which it is unknown is dropped, so a NULL never joins: a row whose user_id is NULL pairs with no user under o.user_id = u.id.

Names.

Two entries of one FROM cannot have the same name (01703): from users join users on ... is 01703, and from users a join users b on a.id = b.id, a self join, is two entries of one table.
A bare column that more than one entry has is ambiguous (01702): with users (id, name) and orders (id, user_id, total), select id from users u join orders o on u.id = o.user_id is 01702, and select u.id ... and select total ... are not.
An ON condition may name its own entry and the entries before it. A qualifier naming an entry written after it is 01701, as for any name that is not an entry there.
* is every column of every entry, entry by entry in FROM order, each in table order: select * from users u join orders o on ... has the header id | name | id | user_id | total.

Checks, in the order of section 66: the FROM's entries in the order written, each one's table (00401) and then its name (01703); then the columns, the ON conditions coming after the select list and before the WHERE, each in the order written. A bare name is checked for 00402 and then for 01702 where section 66 checks it. Types (00403) and numbers (00404) follow the same order.

The plan. The WHERE and every ON are split into conjuncts (section 40), and each conjunct goes where it can first be tested:

a conjunct that reads one entry's columns goes down to that entry's scan, which plans it as a single table's WHERE would be planned (sections 40 to 63): a key bound, an index bound, or a Filter above the scan;
a conjunct that reads two or more entries goes to the lowest join that has all of them below it, and is that join's condition;
a conjunct that reads no column stays in a Filter above the top join. Folded by rule 1 of section 62, a true conjunct is dropped and a false or NULL one keeps no row: the whole FROM, every join and scan, is replaced by one Empty, as for one table.

A HAVING conjunct that rule 2 of section 62 moves to the WHERE is then placed like any other conjunct of the WHERE. A join's conjuncts come in the order they are written in the statement: those of its ON first, then those of the WHERE, so from users u join orders o on u.id = o.user_id where o.total > u.id prints on: (u.id = o.user_id) AND (o.total > u.id).

Joins are left-deep, in FROM order: the left child of each join is the join of the entries before it, or the first entry's scan; the right child is one entry's scan. A join node prints its condition after on:, its conjuncts joined by AND in the order they are written in the statement and printed as in section 40, or nothing when it has none:

[PLAN] select u.name, o.total from users u join orders o on u.id = o.user_id where u.id > 1 and o.total > 10
[PLAN]   └── Project (cols=[u.name, o.total])
[PLAN]       └── NestedLoopJoin (on: u.id = o.user_id)
[PLAN]           ├── IndexScan (table=users, alias=u, range: u.id > 1)
[PLAN]           └── Filter (o.total > 10)
[PLAN]               └── SeqScan (table=orders, alias=o)

Drawing two children. A node with two children prints the left one first, with ├── , and the right one last, with └── . A node's line is [PLAN] , its prefix, its branch (├── or └── ) and the node. The top node's prefix is two spaces. A child's prefix is its parent's prefix followed by four spaces when the parent was drawn with └── , and by │ (a vertical bar and three spaces) when it was drawn with ├── :

[PLAN] select * from a, b, c
[PLAN]   └── NestedLoopJoin
[PLAN]       ├── NestedLoopJoin
[PLAN]       │   ├── SeqScan (table=a)
[PLAN]       │   └── SeqScan (table=b)
[PLAN]       └── SeqScan (table=c)

A select list that is * has no Project node, with a join as without one, select distinct * included. The nodes above the joins are those of a single table, in the same places: Filter for a HAVING, aggregates, Project, Distinct, Sort or TopN, Limit. Three rules of a single table lean on rows arriving in one scan's order, and do not apply to a plan with a join: ORDER BY always has its Sort (or TopN), never skipped by section 44 or by an ordered index scan (section 63), unless section 72 skips it; GROUP BY is always a HashAggregate; and DISTINCT always has its Distinct node.

ast prints the first entry on its Table: line (section 66) and then, right after it and before Columns:, one line per joined entry, in the order written: Join: CROSS <t> for , and CROSS JOIN, and Join: INNER <t> ON <condition> for JOIN and INNER JOIN, the table followed by AS <alias> when it has one, and the condition printed as typed, as section 40 prints an expression: Join: INNER orders AS o ON u.id = o.user_id. From left-outer-join, a LEFT JOIN prints Join: LEFT <t> ON <condition>, whether OUTER was typed or not.

explain logical prints a join as Join (on: <condition>), its ON condition as typed but qualified as section 66 says, or Join for , and CROSS JOIN, over its two Gets; the WHERE is one Filter above the top Join, as for one table.

Running a nested loop. For each row of its left child, in order, a NestedLoopJoin starts its right child again from the beginning and pairs the left row with each of its rows, handing up each pair for which the condition is true. So its rows come in left order, and for each left row in right order: a SELECT with a nested loop and no ORDER BY prints its rows in that order. The right child runs once for every left row, and every run counts (section 65): joining 3 users and 4 orders examines 3 + 3 × 4 = 15 rows. A left child with no row never starts the right one.

In explain analyze (section 61) each node counts its own work: a scan's actual rows adds up the rows it handed up over every run, and its pages the pages it read itself, each once, so two scans of a join each print their own. A join node reads no page: pages=0.

--join <algorithm> on the command line names the algorithm every join of the statement uses: nl, inl, hash, merge or auto, the default. Anything else after it is 00108, and nothing after it is 00102; either ends the program with status 1. It goes anywhere among the options, as --sort-memory does. A join for which the named algorithm cannot be used is a nested loop, and explain shows it; the section of each algorithm says when it can be used. In this stage every algorithm is a nested loop, auto included.

Estimates. A plan with a join prints the estimates of section 60 from join-algorithm-choice (section 73), which says how a join is estimated. Until then the tests of this part explain joins only over tables without statistics.

UPDATE and DELETE read one table: they take no join.

A block nested loop reads the left child a block of rows at a time and runs the right child once per block, not once per row: the same pairs with far fewer runs. MySQL used it before hash joins. It is an optimisation of the same idea, and the counters here are those of the plain loop.

68. LEFT JOIN (from `left-outer-join`)

SELECT ... FROM a LEFT [OUTER] JOIN b ON <condition> [WHERE ...];

left and outer are keywords. LEFT JOIN and LEFT OUTER JOIN are the same, and need their ON (00302 without it). They mix with the joins of section 67, still left to right: a left join b on ... join c on ... joins a with b, then that with c.

What it means. A LEFT JOIN gives the rows the same inner join would, and also, for each row of its left side that pairs with no row of its right side, one row with the left row's columns and NULL in every column of the right side: the left row, padded. So every left row appears at least once.

> select u.name, o.id from users u left join orders o on u.id = o.user_id order by u.id, o.id;
name | id
ada | 10
ada | 12
bob | 11
cy | NULL
(4 rows)

The WHERE comes after the join, so it sees padded rows like any other: a NULL in a padded column makes a comparison unknown, and the row is dropped. ON and WHERE are no longer the same:

Query over `users u left join orders o`	Keeps `cy`, who has no order?
`on u.id = o.user_id and o.total > 5`	yes: the condition picks which orders pair, then `cy` is padded
`on u.id = o.user_id where o.total > 5`	no: `cy`'s padded `o.total` is NULL, and the WHERE drops it
`on u.id = o.user_id and u.id > 1`	yes, and `ada` is padded too: no order pairs with a user the condition refuses
`on u.id = o.user_id where o.id is null`	only `cy`: the users with no order

Placing conjuncts (section 67) changes for a LEFT JOIN, so that no conjunct drops a row the join must keep:

a conjunct of its ON that reads only its right entry goes down to that entry's scan, as before: it picks which right rows can pair;
every other conjunct of its ON stays in its condition, even one that reads only the left side: going down, it would remove left rows that must still be padded;
a conjunct of the WHERE that reads the right entry of a LEFT JOIN cannot go below that join. It goes to the lowest join above it that has all the entries it reads, as that join's condition, or, when that is the LEFT JOIN itself, to a Filter right above it. A WHERE conjunct that reads only entries on the left of the LEFT JOIN goes down as before. A conjunct of a later inner join's ON that reads a LEFT JOIN's right entry is placed the same way as such a WHERE conjunct: a left join b on ... join c on b.x = 1 tests b.x = 1 above the LEFT JOIN;
a conjunct of its ON that reads no column stays in its condition too: Empty (section 67) replaces the FROM only for a constant of the WHERE or of an inner join's ON, so left join orders o on 1 = 0 pads every left row with the condition false.

A LEFT JOIN whose ON conjuncts all went down prints no condition: NestedLoopJoin (left).

The plan. The join prints left, before its condition: NestedLoopJoin (left, on: u.id = o.user_id); explain logical prints Join (left, on: ...).

[PLAN] select u.name from users u left join orders o on u.id = o.user_id and u.id > 1 and o.total > 5 where o.id is null
[PLAN]   └── Project (cols=[u.name])
[PLAN]       └── Filter (o.id IS NULL)
[PLAN]           └── NestedLoopJoin (left, on: (u.id = o.user_id) AND (u.id > 1))
[PLAN]               ├── SeqScan (table=users, alias=u)
[PLAN]               └── Filter (o.total > 5)
[PLAN]                   └── SeqScan (table=orders, alias=o)

Running it as a nested loop. For each left row the right child runs as in section 67; when it ends and no pair was handed up for that left row, the join hands up the left row padded. So a padded row comes in left order, where that row's pairs would have been, and rows_examined is that of the inner join. Each algorithm of this part supports LEFT JOIN, and its section says how.

Aggregates over padding. COUNT(o.id) skips the NULL of a padded row and COUNT(*) does not, so a user with no orders counts 0 and 1.

RIGHT JOIN is a LEFT JOIN with its sides swapped, and FULL OUTER JOIN pads both sides; neither is in this part, and both use the mechanism here. NATURAL JOIN and USING are shorthand for an equality on columns of the same name.

69. Index nested loop join (from `index-nested-loop-join`)

A nested loop reads its whole right side once per left row. When the right side is one table and the condition fixes a column that table can find by key or by index, the join can look up each left row's partners instead: an index nested loop join. With --join inl (section 67) every join that can use one does.

When it can be used. The join's right child is one entry's scan, and its condition has a conjunct <r> = <l> or <l> = <r> where <r> is a column of the right entry and <l> a column of an entry on the left, and <r> is the right table's key or the first column of one of its indexes. The first such conjunct in the order written is the lookup. It uses the table's key when <r> is the key, otherwise the index created first among those whose first column is <r>. Anything else is a nested loop (section 67): no such conjunct, an operator other than =, an expression on either side, or an index on <r> that does not start with it.

The plan. The join prints IndexNestedLoopJoin (on: <condition>), its whole condition as a NestedLoopJoin prints it, left, first for a LEFT JOIN. Its right child is the lookup: an IndexScan whose key is the left column, as typed, and every other conjunct that section 67 would have sent to that entry's scan goes into a Filter above it, with rule 3 of section 62 moving into the scan the ones it can when the lookup is an IndexScan of an index (never into an IndexOnlyScan). That scan is an IndexOnlyScan when the index covers every column the statement reads of that entry (section 58).

[PLAN] select u.name, o.total from users u join orders o on u.id = o.user_id
[PLAN]   └── Project (cols=[u.name, o.total])
[PLAN]       └── IndexNestedLoopJoin (on: u.id = o.user_id)
[PLAN]           ├── SeqScan (table=users, alias=u)
[PLAN]           └── IndexScan (table=orders, alias=o, index=by_user, key=u.id)

Looking up by the table's key prints the key the same way: IndexScan (table=users, alias=u, key=o.user_id). The key is the one left column, without parentheses, on a composite index too: key=u.id.

Running it. For each left row, in order, the join takes the left column's value and runs the right scan for that one value, as section 54 runs <r> = <value>, then tests the rest of its condition on each pair. A NULL value looks nothing up and pairs with nothing; under a LEFT JOIN its row is padded, and so is a left row whose lookup finds no partner. Its rows come in left order, and for each left row in the order the lookup hands them up: for an index, by value then by table key (section 56).

Counters. rows_examined counts the rows every lookup hands up, and index_lookups the rows found through an index entry (section 54); a lookup by the table's key adds no index_lookups. With 100 users, each with 2 of 200 orders, and an index on orders (user_id), the users-to-orders join examines 100 + 200 = 300 rows with index_lookups=200, where a nested loop examines 100 + 100 × 200 = 20100.

Loops in explain analyze. From this stage every node on the right side of a NestedLoopJoin or an IndexNestedLoopJoin ends its explain analyze part with loops=<L>, the number of times it was started: (actual rows=200 pages=<P> loops=100). Every start counts, one per left row: a lookup of a NULL value that finds nothing, and a run whose left row ends up padded, are runs too. <A> adds up the rows it handed up over all its runs, and <P> counts each page it read once, over all its runs. A node anywhere else prints no loops, as before.

70. Hash join (from `hash-join`)

A hash join reads its right child once, into a hash table keyed by the join columns, and then reads its left child once, looking each left row's partners up in the table. Each input is read once, whatever their sizes. With --join hash (section 67) every join that can use one does.

When it can be used. The join's condition has at least one conjunct <l> = <r> or <r> = <l> where <l> is a column of an entry on its left and <r> a column of an entry on its right. Every such conjunct is a hash key, in the order written; the other conjuncts are the residual. A condition with no such conjunct (<, an expression, none at all) is a nested loop.

Running it.

Build. The join reads its right child to the end, before it asks its left child for any row, so the build side is read, and counted, even when the left side has none. Each row whose hash keys are all not NULL goes into the hash table under its key values; a row with a NULL key goes nowhere, since it can equal nothing.
Probe. Then it reads its left child, row by row. A row with a NULL key pairs with nothing. Otherwise the join finds the build rows whose key values equal the row's, compared as values (section 40): rows that only share a hash value are not partners. It tests the residual on each pair and hands up the pairs for which it is true, in the order those build rows were read.
LEFT JOIN. A left row that hands up no pair is padded (section 68). The left side is the probe side, so each left row is seen exactly once.

How keys are hashed is free. A good hash spreads different keys; a correct join never trusts it alone.

Row order. Probe order, and for each left row its partners in the order the build side handed them up: a SELECT with a hash join and no ORDER BY prints its rows that way.

The plan prints HashJoin (on: <condition>), its whole condition as a NestedLoopJoin prints it, with left, first for a LEFT JOIN. Its left child is the probe side and its right child the build side. Neither child is restarted, so neither prints loops in explain analyze.

[PLAN] select u.name, o.total from users u join orders o on u.id = o.user_id
[PLAN]   └── Project (cols=[u.name, o.total])
[PLAN]       └── HashJoin (on: u.id = o.user_id)
[PLAN]           ├── SeqScan (table=users, alias=u)
[PLAN]           └── SeqScan (table=orders, alias=o)

Counters. The [EXEC] line of a statement whose plan has a HashJoin gains hash_build_rows=<b> hash_probe_rows=<p> right after index_lookups, or after rows_examined when there is no index_lookups, and before sort_runs: b is the number of rows the build sides handed up and p the number the probe sides handed up, NULL keys included, added up over every HashJoin of the plan. With 100 users and 200 orders, users u join orders o builds on orders:

[EXEC] rows_examined=300 hash_build_rows=200 hash_probe_rows=100

71. When the build side does not fit (from `hash-join-spill`)

The limit. --join-memory <rows> is the most build rows a HashJoin holds in memory, from 1 to 1000000; without it, 10000. It goes anywhere among the options. A value that is not a number in that range is 00109, and the option with nothing after it 00102: either ends the program with status 1.

Spilling. A HashJoin whose build side hands up at most <rows> rows works as in section 70. One whose build side hands up more spills, and joins in partitions:

It reads the whole build side. When the row after the <rows>-th arrives, it writes the rows it holds, and every build row after them, to the temporary file of section 45. Once the build side has ended, having handed up b rows (NULL keys included, the number hash_build_rows shows), it splits them into P = ceil(b / <rows>) partitions by a hash of their keys: rows with equal keys always land in the same partition. Rows with a NULL key are dropped, as before.
It reads the whole probe side, and writes each row to the partition its keys hash to, with the same hash and the same P. A probe row with a NULL key is in no partition: it pairs with nothing, and under a LEFT JOIN it is handed up padded.
Then, for each partition, it builds a hash table from that partition's build rows, and probes it with that partition's probe rows, as section 70 says, padding under a LEFT JOIN.

A partition may hold more than <rows> rows when many rows share one key, which no hash can split. It is joined in memory all the same: the limit decides how many partitions there are, and the join never fails for it.

What changes and what does not. A spilled join hands up exactly the rows the same join hands up without spilling, but in no promised order: a SELECT whose rows must come in an order needs an ORDER BY. The temporary file follows section 45: created when the first row is written, deleted when the statement ends, not logged, not counted by the counters of section 23, and not part of the database, so a SELECT that spills changes neither the database file nor the log. A statement that both sorts and spills a hash join uses the one temporary file for both; how its pages are shared is free. A spilling join works with a pool of 16 frames, as all SQL does.

The counter. The [EXEC] line of a statement whose plan has a HashJoin gains partitions=<P> right after hash_probe_rows: P as above for a join that spilled and 1 for one that did not, added up over every HashJoin of the plan. hash_build_rows and hash_probe_rows count as before.

[EXEC] rows_examined=300 hash_build_rows=200 hash_probe_rows=100 partitions=20

explain does not change: whether a join spills depends on how many rows reach it.

This is a grace hash join. Real engines size the limit in bytes, choose the partition count ahead of time from estimates, and split a partition again when it is still too large; PostgreSQL's work_mem bounds each hash table, and EXPLAIN ANALYZE reports its "Batches".

72. Sort-merge join (from `sort-merge-join`)

A merge join walks two inputs sorted on the join key side by side, as the merge of an external sort walks its runs, and pairs the rows whose keys are equal. With --join merge (section 67) every join that can use one does.

When it can be used is when a hash join can (section 70): every conjunct <l> = <r> between a column on the left and a column on the right is a merge key, in the order written, and the rest is the residual. With no merge key the join is a nested loop.

Sorted inputs. Both inputs must arrive in ascending order of their merge keys, compared as section 44 compares, NULL first. An input that does not is sorted: the plan puts a Sort (key=<column> ASC, ...) above it, its keys being that side's merge key columns in order, which sorts by sections 44 and 45 (--sort-memory, runs, sort_runs). An input already arrives in that order, and gets no Sort, when it is one entry's SeqScan or IndexScan of its table's own tree, or a Filter right over one (a Filter keeps the order it is given), and its one merge key column is that table's key.

Running it. The join reads both sides in order:

a row whose merge key holds a NULL equals nothing: it is skipped, and under a LEFT JOIN a left one is handed up padded;
while the current left and right keys differ, the side with the smaller key moves on, a left row it passes with no partner being padded under a LEFT JOIN;
when they are equal, every left row with that key pairs with every right row with that key: for each such left row, in order, each such right row, in order, the residual tested on each pair. Duplicates on both sides give every pair: three left rows and three right rows with one key give nine;
when to stop: an inner join stops as soon as either side ends, and reads no more rows of the other. A LEFT JOIN stops when its left side ends, since every left row has been handed up; when its right side ends first, it reads the remaining left rows and hands each up padded.

Row order. Merge key order. Within one key, left order, then right order, as above; a padded row comes where its key puts it, so rows with a NULL key come first.

No sort above it. The output is in merge key order, so a SELECT whose top join is a MergeJoin, with nothing between it and the ORDER BY but a Project (no Filter, aggregate or Distinct), and whose ORDER BY is one key, ascending, that is the left column of the first merge key (or, for an inner join, the right column) has no Sort: section 44's rows would come out in exactly this order.

The plan prints MergeJoin (on: <condition>), left, first for a LEFT JOIN, over its left input and its right input, each with its Sort when it needs one:

[PLAN] select u.name, o.total from users u join orders o on u.id = o.user_id
[PLAN]   └── Project (cols=[u.name, o.total])
[PLAN]       └── MergeJoin (on: u.id = o.user_id)
[PLAN]           ├── SeqScan (table=users, alias=u)
[PLAN]           └── Sort (key=o.user_id ASC)
[PLAN]               └── SeqScan (table=orders, alias=o)

The counter. The [EXEC] line of a statement whose plan has a MergeJoin gains merge_comparisons=<c> after the hash fields (when there are any) and before sort_runs: the number of times a left row's merge key was compared with a right row's, added up over every MergeJoin. How a merge walks its groups decides the exact number, so it is not fixed here, but it is bounded: when the keys of each side are all different and not NULL, every comparison moves past at least one row, so c is at most the left rows plus the right rows, and at least the pairs it hands up, since each pair's keys are compared. Tests read those bounds. sort_runs counts the runs of every Sort of the plan, those under the join included.

73. Choosing a join algorithm (from `join-algorithm-choice`)

From this stage --join auto, the default, chooses each join's algorithm by cost, as section 60 chooses a scan. It does so when every table the statement reads has statistics (section 59). When one does not, nothing changes: every join is a nested loop, and no node prints an estimate. A forced algorithm (--join nl, inl, hash, merge) is used as before, and its plan prints estimates under the same condition: every table the statement reads has statistics.

Estimated rows of a join, from the estimates of its two children, L and R rows, each the floored number its node prints and each already counting the conjuncts pushed below the join. For an IndexNestedLoopJoin, R is the right table's rows under the right side's own conjuncts, as a scan of it would estimate them, without the lookup: the lookup's equality is the join's condition and is counted there, once. The join's estimate is the same whatever its algorithm:

Condition	Selectivity
each conjunct `<l> = <r>`, a column of each side, both with a statistics line	`1 / max(ndv_l, ndv_r)`; `0` when both `ndv` are 0
each other conjunct of the condition	`1 / 3`

The join's rows are floor(L × R × s1 × s2 × …), computed exactly before the floor, and L × R with no condition (,, CROSS JOIN). A LEFT JOIN's rows are the larger of that and L. ndv is the column's in its own table's statistics (section 59), wherever the join sits. A column with no statistics line (a rowid, a column added after the last ANALYZE) makes its conjunct 1 / 3. Nodes above a join estimate from it as section 60 says: a Filter multiplies in its conjuncts, a Sort or Project keeps its child's rows.

Cost of each algorithm, with C(x) the cost of child x and rows(x) its estimated rows, left child L, right child R:

Join	Cost
`NestedLoopJoin`	`C(L) + rows(L) × C(R)`
`IndexNestedLoopJoin`	`C(L) + rows(L) × lookup`
`HashJoin`	`C(L) + C(R) + 2 × rows(R) + rows(L)`, plus `C(L) + C(R)` again when `rows(R)` is above `--join-memory`
`MergeJoin`	`C(L) + C(R) + sort(L) + sort(R) + rows(L) + rows(R)`, where `sort(x)` is `rows(x)` when that input needs a `Sort` (section 72) and `0` when it does not

lookup is the cost section 60 gives the lookup's scan for one value, <r> = <value>: with R and P the right table's statistics and E = floor(R × 1 / ndv) of the column <r> (ndv = R for the table's key), an IndexScan of the table's key costs Dt + ceil(E × P / R), one of an index Di + E × Dt, and an IndexOnlyScan Di + ceil(E / 100). The lookup's scan prints that one run: (rows=<E> cost=<lookup>). A Sort under a MergeJoin prints its child's rows and cost, as any Sort does; the join's sort(x) is what it adds.

Choosing. For each join, from the bottom up, the candidates are the algorithms of sections 67 to 72 that can be used for it: a nested loop always, and an index nested loop, a hash join and a merge join when their sections allow. The cheapest wins; on a tie the first in this order: NestedLoopJoin, IndexNestedLoopJoin, HashJoin, MergeJoin. The scans under it are those section 60 chooses for each table, except that the right child of an index nested loop is its lookup. Joins stay in FROM order until join-order (section 74).

Printing. With every table analysed, every node prints (rows=<E> cost=<C>), the join nodes included:

[PLAN] select * from a join b on a.k = b.k
[PLAN]   └── NestedLoopJoin (on: a.k = b.k) (rows=6 cost=5)
[PLAN]       ├── SeqScan (table=a) (rows=4 cost=1)
[PLAN]       └── SeqScan (table=b) (rows=6 cost=1)

Here a has 4 rows with 4 distinct k and b 6 rows with 3, each in one leaf: the join keeps floor(4 × 6 / 4) = 6 rows; a nested loop costs 1 + 4 × 1 = 5, a hash join 1 + 1 + 2 × 6 + 4 = 18 and a merge join, sorting both, 1 + 1 + 4 + 6 + 4 + 6 = 22.

Stale statistics are believed, as in section 60: the plan may be a poor one, and the rows are always right.

74. Join order (from `join-order`)

With three tables or more, the order of the joins decides how large every result in between is. From this stage, under --join auto with every table analysed (section 73), a FROM of three entries or more whose joins are all inner (,, CROSS JOIN, [INNER] JOIN) is joined in the cheapest left-deep order, which may not be the order written.

The orders tried. Every permutation of the FROM's entries is an order: its first entry, joined with its second, that with its third, and so on, each join's right child one entry's scan. With an inner join ON and WHERE mean the same (section 67), so for each order the conjuncts of every ON and of the WHERE are placed again by section 67's rules: each one at the scan of the one entry it reads, or at the lowest join that has all its entries. An order that joins an entry with no conjunct linking it to the entries before it is a cross product, and is skipped, unless every order has one. A conjunct links an entry when it reads that entry and every other entry it reads comes before it in the order, which is where section 67 would place it.

The cheapest. In each order, each join's algorithm is chosen from the bottom up as section 73 chooses it, and the order's cost is the cost of its top join. The order with the lowest cost wins. On a tie, the order that comes first when the orders are listed by the FROM positions of their entries, compared left to right: the order as written comes first of all, and when it is skipped as a cross product, the next order by positions that is not.

Estimates are those of section 73 at every join: L is the estimate of everything joined so far, and ndv of a column is its own table's.

What does not change. Every column belongs to its entry wherever the entry lands, so select * still lists the entries in FROM order, and the rows are the same. Only the plan, and the order of rows when there is no ORDER BY, can change. explain logical prints the order as written.

Not reordered, and joined as written: a FROM of two entries, a FROM with a LEFT JOIN anywhere in it, a statement reading a table with no statistics, and every statement under a forced --join.

[PLAN] select * from x join y on x.k = y.k join z on y.m = z.m
[PLAN]   └── NestedLoopJoin (on: x.k = y.k) (rows=6 cost=9)
[PLAN]       ├── NestedLoopJoin (on: y.m = z.m) (rows=6 cost=3)
[PLAN]       │   ├── SeqScan (table=z) (rows=2 cost=1)
[PLAN]       │   └── SeqScan (table=y) (rows=6 cost=1)
[PLAN]       └── SeqScan (table=x) (rows=4 cost=1)

Here x has 4 rows (4 distinct k), y 6 rows (3 distinct k, 2 distinct m) and z 2 rows (2 distinct m), each in one leaf. x and z share no conjunct, so the orders that join them first are skipped. Of the four left, x, y, z costs 11, y, x, z and y, z, x cost 13, and z, y, x costs 9: z ⋈ y is a nested loop of 1 + 2 × 1 = 3 keeping floor(2 × 6 / 2) = 6 rows, and joining x to it costs 3 + 6 × 1 = 9.

Left-deep plans keep every right child a single table, which an index nested loop needs. Bushy plans, where both sides of a join may be joins, and the dynamic programming that real planners use to avoid trying every permutation (PostgreSQL switches to a genetic search past 12 tables) are the same idea at a larger scale.

75. Foreign keys (from `foreign-keys`)

CREATE TABLE orders (id INT PRIMARY KEY, user_id INT REFERENCES users (id), total INT);

references is a keyword: [KEYWORD_REFERENCES - references]. REFERENCES <table> (<column>) is a column option, written after the column's type, before, between or after its other options, at most once in a column (a second is 00302). It makes the column a foreign key: the table is the child, the table it names the parent, and the column it names the target. ADD COLUMN takes no REFERENCES (00302); adding a column to a child keeps its foreign keys.

The target is the parent's key column (section 53), or the one column of a unique index of the parent (sections 57 and 58), and has the same type as the foreign key column, INT for INT and VARCHAR for VARCHAR whatever the lengths. The parent may be the table being created, a self-reference: manager_id INT REFERENCES employees (id) in employees, whose target is its own key or a column it marks UNIQUE.

The checks of a CREATE TABLE are those of sections 53 and 57, and then, for each column with REFERENCES, in the order written: the parent exists, or is the table itself (00401); the target is one of its columns (00402); the target is its key or the one column of a unique index (01705); the types match (01706). They come after the catalog row fits and before the name of an inline UNIQUE's index is checked (01602, section 57).

What a foreign key enforces. Every value of the column that is not NULL is the target value of some row of the parent. NULL is always allowed and checks nothing. A value an INSERT gives by leaving the column out, its DEFAULT (section 50), is checked like a value written in the statement.

An INSERT whose foreign key value is not NULL and that no parent row has is 01704. The check is the last one, after the key (00701) and every unique index (01605), and one column after another in table order.
An UPDATE that assigns a foreign key column is checked row by row, in the order its rows were found (section 55), each value as an INSERT's is. One row that fails fails the statement, which changes nothing.
The check sees the table as the statement has written it so far, so a row may reference itself, and a self-referencing INSERT may name its own key: insert into employees (id, manager_id) values (3, 3) succeeds.
Checks are immediate: each statement is checked as it runs, inside a transaction too, and a statement that fails changes nothing and leaves the transaction open with what came before it (section 33).

A check is a lookup. A foreign key check finds the parent row as a SELECT of <target> = <value> would, by the parent's key or its unique index, never by scanning, and it counts in the statement's [EXEC] line like any scan (section 65): an UPDATE of one child row whose new value is found by the parent's key examines 1 + 1 = 2 rows, and through a unique index adds one index_lookups. No index is created on the foreign key column itself.

What the parent may do, including a DROP INDEX of the unique index a foreign key targets, is section 76's: until fk-delete-actions, no test deletes or updates a parent row that a child references, or drops a parent table.

Printing. ast prints REFERENCES <table>(<column>) after a column's other options: Columns: [id int PRIMARY KEY, user_id int REFERENCES users(id)]. catalog list prints it the same way, after PRIMARY KEY: [CATALOG] orders root=4 (id INT PRIMARY KEY, user_id INT REFERENCES users(id), total INT). Foreign keys are kept in the catalog with their table, so they survive reopening and follow transactions.

> insert into orders (id, user_id, total) values (1, 99, 5);
[ERROR:01704] no row of users has id 99

76. RESTRICT, CASCADE and DROP TABLE CASCADE (from `fk-delete-actions`)

CREATE TABLE orders (id INT PRIMARY KEY, user_id INT REFERENCES users (id) ON DELETE CASCADE);
DROP TABLE users CASCADE;

restrict and cascade are keywords. ON DELETE RESTRICT or ON DELETE CASCADE may follow a column's REFERENCES <table> (<column>), and says what a DELETE of a parent row does to the child rows that reference it. Without it the foreign key is RESTRICT.

DELETE of parent rows. A DELETE finds its rows first (section 55). Then, for each row it deletes, in that order, and for each foreign key that references the table, the foreign keys taken in the order their tables were created and their columns in table order, it searches the child for the rows whose foreign key value is that row's target value:

RESTRICT: if there is one, the DELETE is 01707, and the whole statement changes nothing;
CASCADE: those child rows are deleted too, in the same statement, with their index entries, and each of them is a parent row deleted in its turn, so its own children are searched the same way: users to orders to items.

The statement is one change: if a search anywhere in the cascade finds a RESTRICT child, it is 01707, and nothing is deleted at any level. A row the cascade reaches twice is deleted once. A self-referencing table cascades within itself.

Each row is deleted before its children are searched, so the search sees the table as the statement has left it so far (section 75): a row that references only itself can be deleted under RESTRICT, but delete from r, where row 2 references row 1, is 01707 under RESTRICT when it reaches row 1 first, since row 2 is still there. The checks are immediate; one at the end of the statement, as PostgreSQL's NO ACTION does, is not in this part.

The success line counts the rows the DELETE found, whether it removed each one itself or a cascade removed it first: Delete statement executed successfully (1 rows) for one user, however many orders went with them.

A search is a scan. The child is searched as a SELECT * of <foreign key> = <value> on the child would be: through an index whose first column is the foreign key column if the child has one (the one created first when it has several), otherwise by reading the whole child. Every search counts in the [EXEC] line like any scan (section 65), and index_lookups is printed when a scan of the plan or any search read an index. No index is created on a foreign key column for you, and this is what it costs: deleting one user among 200 orders examines 1 + 200 rows without an index on orders (user_id), and 1 + 2 with one, for a user with two orders.

UPDATE of a parent. An UPDATE that changes a target value that some child row references is 01707, whatever the foreign key's action: ON UPDATE is not in this part. A key column cannot be updated at all (section 53), so this is an UPDATE of a unique target column. Its search is a search like a DELETE's, and counts in the [EXEC] line.

DROP TABLE of a table that a foreign key of another table references is 01708, and so is TRUNCATE of it; a table's references to itself do not count. TRUNCATE takes no CASCADE (00302). DROP TABLE <t> CASCADE (and DROP TABLE IF EXISTS <t> CASCADE) first drops every foreign key of another table that references t, then drops t. The child tables keep their columns and their rows, values included; the column is no longer a foreign key, so catalog list no longer prints its REFERENCES, and later INSERTs are not checked. DROP INDEX of the unique index a foreign key targets is 01708.

Transactions. A cascade is pages changed by one statement, so ROLLBACK, a failed statement and recovery take it back as section 34 says, index entries included.

Printing. ast and catalog list print ON DELETE CASCADE after REFERENCES <table>(<column>) for a cascading foreign key, and nothing more for a restricting one, written or not: user_id INT REFERENCES users(id) ON DELETE CASCADE. ast of drop table users cascade; prints Statement: DROP TABLE, Table: users and Cascade: true.

ON DELETE SET NULL and SET DEFAULT change the child rows instead of deleting them; ON UPDATE CASCADE follows a changed target value; a foreign key may cover several columns; and a check may be deferred to COMMIT. Each is the same search with a different action, and none is in this part.

77. Subqueries that run once (from `subqueries-uncorrelated`)

A subquery is a SELECT, without its ;, in parentheses inside an expression of another SELECT. exists is already a keyword (section 27). There are three forms:

Form	Gives
`(SELECT ...)`, a scalar subquery, wherever an operand may stand	its one value: NULL when it hands up no row; `01709` when it hands up more than one
`<operand> [NOT] IN (SELECT ...)`	as an IN list of the values it hands up (section 42), below
`[NOT] EXISTS (SELECT ...)`	true when it hands up at least one row, false otherwise: never unknown

A subquery is a whole SELECT, with its own FROM, WHERE, GROUP BY, HAVING, ORDER BY and LIMIT, and may hold subqueries itself. The tests use subqueries in the WHERE and the select list of a SELECT; elsewhere they are not tested.

One column. A scalar or IN subquery selects exactly one column, * over a one-column table included; any other number is 01710, a check. An EXISTS subquery may select anything: only whether a row comes matters.
Types. A scalar subquery has its column's type, and x IN (SELECT c ...) compares x with c as = does, 00403 when their types do not compare: by value, so an INT 5 is in a subquery of DECIMAL (an AVG) that hands up 5.00.
IN is true when some value it hands up equals the operand. Otherwise it is unknown when the operand is NULL or one of the values is NULL, and false when there is no such NULL or when it hands up no row at all. NOT IN is NOT of that, so a single NULL among the values makes x NOT IN (...) unknown for every x it does not contain: where id not in (select user_id from orders) keeps no row when some order's user_id is NULL, as section 42's a not in (1, NULL) does.
EXISTS stops at the first row: its subquery is asked for one row and no more, as under LIMIT 1 (section 46). A Sort or an aggregate inside it still reads every row below it before handing up that first one, and those rows count.

Names. A subquery's FROM is its own: its entries are named, and its columns bound, inside it (section 66). This section's subqueries name only their own entries; section 78 adds the names of the query around them.

Checks. A subquery is checked as a SELECT, at the place where the expression holding it is checked, and its first failing check is the statement's. Its own checks come first, then its column count (01710): (select id, nope from t) is 00402.

Run once. A subquery that names nothing outside itself is uncorrelated: its result cannot change from one row to the next, so it runs once, the first time its expression is evaluated, and that result (its value, its set of values, or whether it had a row) is used for every row after. A subquery whose expression is never evaluated never runs: under a WHERE that keeps no row, a subquery in the select list does not run. Its scans count in the statement's [EXEC] line, as every scan does (section 65), each run once.

Plans. In an expression, the n-th subquery of the statement, counting the (SELECT of each in the order they are written, nested ones included, prints as (subquery <n>): total > (subquery 1), id IN (subquery 1), EXISTS (subquery 2), NOT (EXISTS (subquery 2)) for NOT EXISTS, NOT (id IN (subquery 1)) for NOT IN. Each of these is an operator, not a column or a literal, so as an operand it is put between parentheses (section 40): (id IN (subquery 1)) AND (NOT (EXISTS (subquery 2))). A conjunct that holds a subquery is never a key bound, an index bound or a filter: of rule 3; it stays in a Filter, or a join condition, placed as any conjunct. The node that evaluates an expression holding a subquery (a Filter, a Project, a join, and for a subquery in ORDER BY or HAVING the Sort or the aggregate) gets the subquery's plan as a child after its others, under Subquery (<n>, once):

[PLAN] select id from orders where total > (select avg(total) from orders)
[PLAN]   └── Project (cols=[id])
[PLAN]       └── Filter (total > (subquery 1))
[PLAN]           ├── SeqScan (table=orders)
[PLAN]           └── Subquery (1, once)
[PLAN]               └── Project (cols=[AVG(total)])
[PLAN]                   └── Aggregate (aggs=[AVG(total)])
[PLAN]                       └── SeqScan (table=orders)

ast, explain logical and a select list item's header (section 43) print subqueries the same way: select (select max(total) from orders) from users has the header (subquery 1). In explain analyze, the Subquery node and every node below it end with loops=<L>, the number of times the subquery ran (section 69): 1 here, or 0 if it never ran. Its actual rows are the rows it handed up over all its runs.

78. Subqueries that run per row (from `subqueries-correlated`)

A subquery may name the entries and columns of the queries around it. One that does is correlated: its result depends on the row being evaluated, so it runs again for each one.

SELECT u.name FROM users u WHERE EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id);

Nested scopes. Each SELECT is a scope with the entries of its FROM. A name is looked up in the scope where it is written first, then in the scope around it, and so on outwards:

a bare column is the column of the innermost scope that has an entry with such a column; within that scope the rules of section 67 hold (01702 when two of its entries have it, in an outer scope too);
a qualified q.c finds the innermost scope with an entry named q (01701 when none has), then its column c (00402);
so an inner name hides an outer one: in select id from users u where exists (select 1 from orders o where id = 10), the inner id is o.id. An entry may have the name of an entry outside it.
Names never travel the other way: an entry of a subquery is not an entry of the query around it, and naming it there is 01701 (qualified) or 00402 (bare).

A column of an outer scope is an outer reference. Inside the subquery it is a value fixed for each run, and stands where a literal may in a bound, on the right: o.user_id = u.id is an index bound of section 56 when orders has an index on user_id, printed key=u.id, o.id > u.id a range on the key, and otherwise they are a Filter; u.id = o.user_id, the column on the right, is never a bound, as section 40 says of a literal on the left. For estimates it is not a literal: a conjunct with an outer reference is "any other" of section 60, 1 / 3. A subquery with at least one outer reference, at any depth inside it, is correlated; one with none is uncorrelated and runs once, as section 77 says.

Running. A correlated subquery runs each time its expression is evaluated, with the outer row's values: once per row of the Filter, Project or join that evaluates it, and only for the rows that reach it. Every run counts in [EXEC] (section 65). EXISTS still stops at its first row, each run. Scalar, IN and EXISTS give what section 77 says, 01709 included for any run that hands up two rows. So a scalar subquery in the select list can count each user's orders:

> select u.name, (select count(*) from orders o where o.user_id = u.id) from users u;
name | (subquery 1)
ada | 2
bob | 1
cy | 0
(3 rows)

Plans. A correlated subquery's node is Subquery (<n>, per row); in explain analyze its loops=<L> is the number of runs, the rows that reached its expression.

[PLAN] select u.name from users u where exists (select 1 from orders o where o.user_id = u.id)
[PLAN]   └── Project (cols=[u.name])
[PLAN]       └── Filter (EXISTS (subquery 1))
[PLAN]           ├── SeqScan (table=users, alias=u)
[PLAN]           └── Subquery (1, per row)
[PLAN]               └── Project (cols=[1])
[PLAN]                   └── Filter (o.user_id = u.id)
[PLAN]                       └── SeqScan (table=orders, alias=o)

A conjunct holding a correlated subquery reads the entries its outer references name, and is placed by section 67 at the lowest place that has them all.

Real planners turn EXISTS and IN subqueries into semi-joins and NOT EXISTS into anti-joins, so that the algorithms of this part can run them, and NOT IN, because of its NULL rule, into something more careful. Running the subquery per row is the baseline those rewrites must agree with.

79. What Joins and Relations changes

As in section 21, each change is made by one stage, which retires the earlier cases that checked the old contract, by name, in the manifest.

Earlier contract	Section	Changed by	Now
`.` is `00202`	4	`qualified-names`	a symbol (section 66)
a FROM names a table, and a column is a bare name	5, 43	`qualified-names`	a table with an optional alias, and a column bare or qualified (section 66)
`explain logical` prints columns as typed	62	`qualified-names`	qualified by their FROM entry's name (section 66)
`join`, `inner` and `cross` are identifiers; a FROM has one entry	4, 66	`nested-loop-join`	keywords, and a FROM joins its entries (section 67)
`rows_examined` counts the rows of the one scan at the bottom of the plan	13	`nested-loop-join`	it adds up every scan of the plan, every time it runs (sections 65 and 67)
a plan is one chain of nodes, each drawn with `└──`	12	`nested-loop-join`	a join has two children, drawn with `├──` and `│` (section 67)
the command line options are `--db`, `-c`, `--cache-pages`, `--sort-memory` and `--no-rewrite`	2	`nested-loop-join`	and `--join` (section 67)
`left` and `outer` are identifiers; every join is an inner join	4, 67	`left-outer-join`	keywords, and LEFT JOIN pads left rows that pair with nothing (section 68)
a join's right side is read whole for every left row	67	`index-nested-loop-join`	with `--join inl`, looked up by key or index (section 69)
`explain analyze` prints `(actual rows=<A> pages=<P>)`	61	`index-nested-loop-join`	and `loops=<L>` on the right side of a nested loop (section 69)
the `[EXEC]` line is `rows_examined`, `index_lookups`, `sort_runs` and `groups`	13, 39, 54	`hash-join`	`hash_build_rows=<b> hash_probe_rows=<p>` come before `sort_runs` when the plan has a `HashJoin` (section 70)
a `HashJoin` holds its whole build side in memory	70	`hash-join-spill`	above `--join-memory` rows it joins in partitions through the temporary file, `partitions=<P>` after `hash_probe_rows` (section 71)
the command line options end with `--join`	2	`hash-join-spill`	and `--join-memory` (section 71)
a join gives no order an ORDER BY can use	67	`sort-merge-join`	a `MergeJoin` gives merge key order, and ORDER BY on its key has no `Sort` (section 72)
the `[EXEC]` line has no `merge_comparisons`	13	`sort-merge-join`	`merge_comparisons=<c>` before `sort_runs` when the plan has a `MergeJoin` (section 72)
`--join auto` is a nested loop	67	`join-algorithm-choice`	the cheapest algorithm when every table has statistics (section 73)
a plan with a join prints no estimates	60, 67	`join-algorithm-choice`	with every table analysed, every node prints `(rows=<E> cost=<C>)` (section 73)
joins are planned in FROM order	67, 73	`join-order`	inner joins over analysed tables, in the cheapest left-deep order (section 74)
`references` is an identifier; a column's options are `NOT NULL`, `DEFAULT`, `UNIQUE` and `PRIMARY KEY`	4, 57	`foreign-keys`	a keyword, and `REFERENCES <table> (<column>)` makes a foreign key (section 75)
`restrict` and `cascade` are identifiers; nothing is said of a parent's DELETE, UPDATE or DROP	4, 27, 75	`fk-delete-actions`	keywords; RESTRICT refuses (`01707`), CASCADE deletes the children, DROP TABLE checks dependencies (`01708`) and takes `CASCADE` (section 76)
an expression holds columns, literals and calls	40	`subqueries-uncorrelated`	a SELECT in parentheses is a subquery, and `exists`, a keyword since section 27, starts one (section 77)
a subquery names only its own entries	77	`subqueries-correlated`	names resolve outwards through nested scopes, and a subquery naming an outer column runs per row (section 78)

80. Sessions and Concurrency: general rules

Many sessions, one process, one thread. From sessions a line may run on behalf of one of several sessions, each with its own transaction (section 81). The program still reads one line at a time and finishes what it can before it reads the next, so the order of the input lines decides everything: the test script is the scheduler. Nothing in this part depends on timing, and no test sleeps.
What belongs to a session: whether a transaction is open, its id, its undo records (section 82), the locks it holds and the statement it is waiting with (sections 84 and 85), its isolation level and its read view (sections 87 and 88). Everything else is shared: the database file, the buffer pool, the catalog, the output mode of .mode and the command line options.
Transaction ids. Every transaction gets an id when it starts: one more than the last id given in this run of the program, and 1 for the first. A transaction starts at BEGIN, or, in autocommit, when a statement that may change rows or tables starts to run: INSERT, UPDATE, DELETE, CREATE TABLE, DROP TABLE, TRUNCATE, ALTER TABLE, CREATE INDEX, DROP INDEX or ANALYZE, once the lexer and the parser have accepted it, so one that then fails a check of its names or values has used an id. SELECT, explain and debug commands start no transaction. These ids are not the transaction ids of the log, which are given at commit (section 35); the two never meet.
Older and younger. A transaction with a smaller id is older. Deadlocks choose the youngest (section 86) and read views compare ids (section 87).
SQL results for one session that commits what it runs are those of every earlier part. An input with no @ prefix at all behaves exactly as before, line for line: it is session 1, untagged.

81. Sessions (from `sessions`)

The prefix. A line that starts with @ names its session: @, then digits giving a number from 1 to 1000, then one space, then the rest of the line, which runs as session n would run it. A line with no prefix runs as session 1. A session exists from the first line that names it, whatever that line holds; session 1 always exists.

@2 begin;
@2| Begin statement executed successfully

Tags. Every line printed for a prefixed line starts with @<n>| , n written without leading zeros: results, the [EXEC] line, plan lines, debug output, errors and their HINT: lines. Lines printed for a line with no prefix have no tag, so @1 select ... and select ... print the same lines, the first tagged and the second not.
A bad prefix is 01801, untagged, and the line runs nowhere: @, @0, @x, @1001, and digits with no space after them (@2select). The line is trimmed before the prefix is read (section 1), so @2 with nothing after it is @2, also 01801. Leading zeros are allowed: @02 is session 2, tagged @2| . The rest after the space is trimmed again, and it is what the lexer reads: the column of a lexer or parser error counts from the start of the rest, not of the whole line.
Meta commands belong to the whole program. After a prefix they do what they always do, and what they print is tagged: @2 .exit ends the program.
tx status (section 33) reports the session of its line. Each session is IDLE or IN_TRANSACTION on its own, and BEGIN, COMMIT, ROLLBACK, 01301 and 01302 are about that session alone. An error in one session's statement changes nothing in another's transaction.
Autocommit beside an open transaction. A statement outside a transaction runs and commits on its own (section 32) while other sessions have transactions open.

sessions prints one line per session that exists, in ascending order:

[SESSIONS] <n> trx=<id> state=<state> waits_for=<m> iso=<level>

Field	Value
`trx`	the id of the session's open transaction (section 80); `0` when none is open
`state`	`IDLE` with no transaction open, `ACTIVE` with one open, `WAITING` while a statement of the session waits for a lock (from `lock-waits`, section 85)
`waits_for`	the session it waits for (section 85); `0` when it is not waiting
`iso`	`REPEATABLE_READ`, `READ_COMMITTED` or `SERIALIZABLE`: the session's isolation level (from `isolation-levels`, section 88); `REPEATABLE_READ` until then

sessions with anything after it is 00104. It changes nothing.

The end of the program. .exit, the end of input and the end of a -c command roll back the open transaction of every session, in ascending session order, printing nothing, and then save as section 33 says. .crash loses every open transaction.
What needs every transaction closed. CHECKPOINT and VACUUM write or move pages that open transactions may have changed. Inside the session's own transaction they are 01304, as before; with no transaction open in their own session and one open in another session, they are 01802. Either way they change nothing.
Pages of open transactions. The rules of section 33 about the open transaction hold for every open transaction: no page any of them changed is written to the database file before that transaction ends; pager flush skips them all; and 01303 happens when every page in the pool is pinned or changed by some open transaction, at least one of them only changed. It ends the transaction of the session whose statement needed the page, and only that one.
Reading another session's changes. In this stage a statement reads rows as they are on the page, another open transaction's changes included. Locks (section 84) and read views (section 87) change what a read sees; until then no test reads rows another open transaction changed.
Two transactions, one page. ROLLBACK still puts back the pages a transaction changed as they were at its BEGIN (section 34). That is only right while no other open transaction changes the same pages: two open transactions that change one page, a leaf, the header (by allocating or freeing a page) or the catalog, are not defined in this stage, and no test makes them. undo-log makes them defined (section 82).

82. Row-level undo (from `undo-log`)

Page copies stop being how a transaction is taken back. From this stage every change a transaction makes to a row leaves one undo record, and ROLLBACK applies them.

Change	Its undo record holds	Applying it
INSERT of a row	the table and the row's key	deletes the row with that key
UPDATE of a row	the table, the key and the whole row as it was	puts that row back under its key
DELETE of a row	the table and the whole row as it was	inserts that row again

What leaves records. Every row an INSERT, UPDATE or DELETE changes, one record per row, foreign key cascades included (section 76). Index entries leave none: putting a row back writes its indexes as the statement would (section 55). The catalog's rows are rows: CREATE TABLE and CREATE INDEX insert one, ALTER TABLE and ANALYZE update one, DROP TABLE and DROP INDEX delete one, and each leaves its record.
Applying them. ROLLBACK applies the transaction's records newest first, each as the statement it reverses would run: by key, wherever the row is now, writing indexes and overflow pages (section 29) and splitting or merging leaves as that statement would. Putting a row back restores the index entries the row had, whatever is there now: an entry already there is not added twice, and one the row should not have is taken out, so a statement that failed between writing a row and writing its indexes is taken back whole. Nothing reverses a split, a merge or an allocation: the pages a transaction allocated stay, and leave only if putting rows back merges them away. So after ROLLBACK the rows, the indexes (index check is OK) and the catalog are as they were at BEGIN, and pager status, db freelist and page numbers may not be.
Trees that come and go. A tree's pages are not rows. When a transaction creates a table or an index, undoing its catalog record also frees the new tree's pages. When it drops a table or an index, or truncates a table, the old tree's pages are freed only when it commits, in the order section 27 gives; until then they stay as they were, and undoing the catalog record finds them there. TRUNCATE in autocommit is as section 27 says; inside a transaction it gives the table a new empty root, recorded by updating its catalog row, so its old tree is freed at commit and the new root when it is undone.
Everything that took back pages takes back rows now: ROLLBACK (section 34), a statement that fails after it changed rows, which applies its own records back to where it started (section 34), 01303 (section 33) and the end of the program (section 81). What they leave is what they left before, with the difference above about pages.
Pages that undo changed are logged. ROLLBACK, 01303, the end of the program, and an autocommit statement that fails after it changed rows, once they have applied the records, log every page the transaction changed and every page applying its records changed, exactly as a commit logs its pages (section 35): page records in ascending page number, a commit record with the next log transaction id, a sync. A page left as it was still counts: a split half that undo never touched again must not reach the file unlogged. With no such page, as for a statement that failed before changing a row, they log nothing. So nothing undo changed is left held. While records are applied, the pool may hold more pages than its frames, since every frame may hold a page of the transaction being rolled back, as 01303 leaves it; the extra pages leave as usual once they are logged.
Records last as long as their transaction. A transaction's records are dropped when it ends, by COMMIT or by ROLLBACK. An autocommit statement's are dropped when it commits. Records live in memory in this stage; undo-recovery puts them in pages when a crash could need them (section 83).
Two transactions, one page, which section 81 left undefined, is now defined: each transaction's records take back its own rows and nothing else, so rolling back one leaves the other's rows on the same leaf as they are. Two open transactions changing the same row are still not defined until lock-waits (section 85), and neither is one transaction changing a table another open transaction created or dropped.
Crashes with two sessions. A commit logs the pages its transaction changed (section 35), and such a page may also hold a row another open transaction changed. What a crash leaves after that is not defined until undo-recovery (section 83). With one session nothing changes.

undo status prints one line:

[UNDO] records=<n> pages=<p> oldest_view=<t> purgeable=<k>

Field	Value
`records`	the undo records every session holds, added up
`pages`	the undo pages in the file (section 83); `0` until `undo-recovery`
`oldest_view`	the id of the transaction whose read view is the oldest open one (section 87); `0` when no view is open, and always until `read-views`
`purgeable`	the records purge could drop now (section 90); `0` until `read-views`

undo with no subcommand or any subcommand but status, or undo status with anything after it, is 00104. It changes nothing.

InnoDB keeps the same records in its undo log: an insert record holds the key, an update record the columns as they were. It never undoes a page split either; a rolled-back B+Tree is the same set of rows in a tree that may have a different shape.

83. Undo after a crash (from `undo-recovery`)

A commit may log a page that holds another open transaction's change (section 82). After a crash, redo puts that change back, and only the other transaction's undo records can take it out again. So from this stage those records reach the log with the page.

Undo pages. An undo page is page type 6 at byte 0. It holds undo records of one transaction; how they are laid out after byte 0 is the engine's own, as long as recovery can read them back and tell whose they are. Undo pages are allocated like any page, from the free list first (section 26), and form one chain from the header:

Bytes	Field	Value
28–31	undo pages	the first undo page; `0` when there is none

A header written before this stage has a zero there, so it is already right. An undo page is not a node: btree dump of it is 00703, and a page command 00606. db verify checks it like any page.

Committing, from this stage, is these steps:

When another session has a transaction open, its undo records that are in no undo page yet are written to undo pages. With no other transaction open nothing happens here, so one session never makes an undo page.
The committing transaction's own undo pages, if it had any, are freed, and its records dropped. This comes before the log is written, so the freeing is logged with the commit: after a crash, recovery never finds a committed transaction's records.
A page record is logged for every page changed since it was last logged, by any transaction, undo pages included, in ascending page number; then the commit record, and the log is synced (section 35). With one session these are exactly the pages the transaction changed, as before.

A page is logged from the moment a commit logs it until it changes again. Section 33's rule becomes: a page that an open transaction changed since it was last logged is never written to the database file. A logged page may be written, by eviction, pager flush or the end of the session, even if it holds an open transaction's change, because the undo records of that change are logged too. 01303 counts only the pages that rule holds back.

Ending without a commit. ROLLBACK, 01303 and the end of the program free the transaction's undo pages once its records are applied, and then log the pages they changed as section 82 says, taking steps 1 and 3 above as a commit does.
undo status counts the undo pages in pages.

Recovery (section 36) gains a second pass. After the committed page images are written:

Undo. Every transaction whose undo records are in the undo pages is one that never committed, since a commit frees its own (from read-views, marks them committed instead: section 87). Each is rolled back as ROLLBACK does, newest record first, and its undo pages are freed, one transaction after another in ascending transaction id.
Then the database file is synced and the log emptied, as before.

The line gains the number of transactions the undo pass rolled back:

[WAL] Recovery: records=<r> replayed=<c> discarded=<d> rolled_back=<u>

rolled_back=0 when there were none. Recovery runs only when the log has a good record, as before, and that is always so when an undo page is in the file: only a commit writes one, and only a checkpoint or a clean end empties the log, which section 81 runs only when no transaction is open.

Idempotent again. The undo pass changes pages in memory only; they reach the file at step 2. A crash during it leaves the log as it was, and the next open does the same work and prints the same line.
Fail-point. mid_undo: during recovery, after the undo pass has applied its first record, before anything more is written.

Fail-point	Where the program stops
`mid_undo`	in recovery's undo pass, after its first record is applied

Real engines (ARIES, InnoDB) log undo the same way, as ordinary page changes, and recover in the same two passes: redo history, then roll back the losers. InnoDB writes undo for every transaction; this engine writes it only when another session's commit forces it, so one session's log is unchanged.

84. Locks (from `row-locks`)

From this stage every transaction asks a lock manager for a lock before it reads or writes, and keeps every lock it got until it ends: strict two-phase locking. An autocommit statement's locks are kept until it commits, or until it fails and is undone.

Resources and modes. A lock is on a table, named <table>, or on a row, named <table>:<key>, the row's key (section 53: its primary key, or its hidden rowid). Its mode is one of four:

Mode	Means
`S`	shared: reading the row, or the whole table
`X`	exclusive: changing the row, or the whole table
`IS`	on a table: the transaction holds or will take `S` on some of its rows
`IX`	on a table: the transaction holds or will take `X` on some of its rows

Two modes held by different transactions on one resource are compatible when this table says yes:

	`IS`	`IX`	`S`	`X`
`IS`	yes	yes	yes	no
`IX`	yes	yes	no	no
`S`	yes	no	yes	no
`X`	no	no	no	no

Who takes what.

Statement	Locks
SELECT, and `explain analyze`	for each table it reads: `S` on the table when the plan scans it with a `SeqScan`; otherwise `IS` on the table and `S` on each row the scan hands up
INSERT	`IX` on the table and `X` on the new row's key
UPDATE, DELETE	`X` on the table when the plan scans it with a `SeqScan`; otherwise `IX` on the table and `X` on each row the statement changes
a foreign key check (section 75)	`IS` on the parent table and `S` on the parent row found
a search of child rows (section 76)	as a SELECT of them: `S` on the child table with a `SeqScan`, else `IS` and `S` on each child row found
a cascade (section 76)	as the DELETE of those rows: `X` on the child table with a `SeqScan`, else `IX` and `X` on each child row
CREATE TABLE, DROP TABLE, TRUNCATE, ALTER TABLE	`X` on each table it creates, drops, truncates or alters, and with DROP TABLE CASCADE on each table whose foreign key it removes
CREATE INDEX, DROP INDEX	`X` on the index's table
ANALYZE	`S` on the table

Every scan of a table takes locks each time it runs, so a join or a subquery locks what each of its scans reads. explain, which runs nothing, and debug commands take no locks. A transaction never conflicts with itself.

One mode per resource. A transaction holds at most one mode on a resource. Asking for a mode it already covers (X covers everything, S covers IS, IX covers IS) changes nothing. Otherwise the mode it holds becomes the weakest one that covers both: IS and IX give IX, IS and S give S, and S and IX give X.
Released together. COMMIT, ROLLBACK, 01303 and the end of the program release every lock of the transaction at once. A statement that fails keeps the locks it took.
Conflicts. What happens when a transaction asks for a mode that another transaction's mode on the same resource is not compatible with is lock-waits's (section 85). Until then no test makes one.

locks prints one line per resource that some transaction holds or waits for:

[LOCKS] <resource> holders=[<session>:<mode>,...] waiters=[<session>:<mode>,...]

Holders are listed in ascending session order, waiters in the order they started waiting (section 85), each as its session and the mode, and an empty list is []. Lines are sorted by table name in byte order, a table's own line before its rows, rows by key in ascending order. With no lock held it prints [LOCKS] none. locks with anything after it is 00104; lock with no subcommand or any subcommand but graph (section 86) is 00104 too. Neither changes anything.

@1 begin;
@1 update users set name = 'z' where id = 5;
locks
[LOCKS] users holders=[1:IX] waiters=[]
[LOCKS] users:5 holders=[1:X] waiters=[]

Locks on rows of a B+Tree, not on its pages, are what lets two transactions work on one leaf. Locking pages instead looks simpler and is not: a split moves rows between pages while other transactions hold them. Real engines also protect each page for the moment it is read or written with a short latch; in one thread there is nothing to protect it from, so this engine has none.

85. Waiting for a lock (from `lock-waits`)

A request conflicts when its mode is not compatible (section 84) with a mode another transaction holds on the resource, or with the mode of a request another transaction is already waiting with on it. A request that conflicts waits; any other is granted at once.

Parking. The statement that made a waiting request is parked:

what it had changed so far is undone, as for a statement that fails (section 82); the locks it holds stay;
its session prints one line, tagged as the statement's line was: [LOCK] session <n> waits for session <m> on <resource>, where m is the lowest session holding a mode the request conflicts with, or, when none holds one, the first session waiting ahead of it with one;
the program reads the next line.

@1 begin;
@1| Begin statement executed successfully
@1 update users set name = 'a' where id = 5;
@1| Update statement executed successfully (1 rows)
@1| [EXEC] rows_examined=1
@2 update users set name = 'b' where id = 5;
@2| [LOCK] session 2 waits for session 1 on users:5

While it is parked, sessions shows the session WAITING, with waits_for=<m> and the id of the transaction the statement belongs to, which in autocommit is the statement's own; locks lists its request under waiters. A line for a session that is parked, prefixed or, for session 1, not, is 01803, tagged as that line, and nothing else happens.

Resuming. When a transaction ends, its locks are released. Then the parked statements are looked at in the order they parked, and the first whose request can now be granted resumes: its request is granted and the statement runs again from its start, as if its line had just been typed, keeping the locks it already holds and the transaction it already has: an autocommit statement keeps the id it was given when it first ran. Its lines are tagged as its own line was, and come right after the lines of the statement that released the locks. Then the parked statements are looked at again, from the first, until none can resume, and only then is the next line read. A resumed statement may park again, with a new [LOCK] line, and one that ends its transaction, as an autocommit statement does, releases locks in its turn.

@1 commit;
@1| Commit statement executed successfully
@2| Update statement executed successfully (1 rows)
@2| [EXEC] rows_examined=1

Requests are granted in the order they wait: a request that conflicts only with a waiting request waits behind it, and a release grants waiters in their order.
Which mode. A transaction that asks for a mode on a resource where it already holds one is checked with the mode it would hold once granted (section 84: S then IX is checked as X), is listed under waiters with the mode it asked for, and holds the combined mode when granted.
waits_for in sessions is worked out each time it is printed, by the rule of the [LOCK] line, so it follows the holders as they change while the statement waits.
What a resumed statement sees. It runs on the rows as they are when it resumes. An UPDATE that resumes after the holder's COMMIT changes the row that COMMIT left; after a ROLLBACK, the row as it was before. An INSERT takes the X lock on its new key before it looks for that key, so one that waited for the transaction that inserted the same key gets 00701 when that transaction commits and succeeds when it rolls back.
Assignments may read the row. From this stage the value of an UPDATE assignment may be any expression of section 40 over the columns of the row being changed: set n = n + 1. It is evaluated once per row, on the row as the statement finds it, and its type is checked as a literal's would be, with 00403, 01501 and 01502 as section 40 says. A result the column cannot hold is the code a literal would get, met when the row is built and before anything is written: an INT outside 0 to 4294967295 is 00404, a string longer than its VARCHAR(n) is 00405, and NULL for a NOT NULL column is 01503. Every assignment of a row reads the row as it was before the statement changed it: set a = b, b = a swaps them.
The end of the program drops every parked statement, printing nothing, and then rolls back as section 81 says. .crash loses them with everything else.
Cycles. A request whose waiting would close a cycle, a session waiting for a session that waits, in the end, for it, is deadlock's (section 86). Until then no test makes one.

Real engines block the thread and wake it on release. Here the statement's line is kept and run again, which needs no thread and gives the same answers: the statement has changed nothing while parked, and the locks it kept protect what it had already read.

86. Deadlocks (from `deadlock`)

The wait-for graph has an edge n -> m for each waiting session n and each session m that holds a mode its request conflicts with, or waits ahead of it with such a mode (section 85). lock graph prints one line per edge, sorted by n and then by m, both ascending:

[LOCKS] 2 -> 1
[LOCKS] 3 -> 2

With no edge it prints [LOCKS] no waits. lock graph with anything after it is 00104.

Detection. Each time a request conflicts, before it parks, the program looks for a cycle the request would close: a path of edges from a session the requester would wait for back to the requester. With none, it parks as section 85 says. With one:

The victim is the youngest transaction, the one with the largest id (section 80), among the requester and every session on a cycle through it. A session waiting with an autocommit SELECT, which has no transaction id, counts as 0; between equal ids, the larger session number is the victim.
The victim's session prints [ERROR:01804] ..., tagged as the victim's statement was: the requester's line, or the line the victim is parked with. The victim's whole transaction is rolled back, as ROLLBACK does, its locks are released, its parked statement, if any, is dropped, and its session is IDLE. An autocommit victim's transaction is its statement.
When the victim is not the requester, the requester asks again, as if new: it is granted, or it conflicts and is checked again from step 1. Its statement may continue from the request or start again from the beginning, as a resumed one does (section 85): it keeps its locks and its id, and prints the same lines either way.
Then the parked statements are looked at as section 85 says, since the victim released locks.

No timeout ever ends a wait: the only way out of a cycle is a victim.

@1 update accounts set balance = 0 where id = 2;
@1| [LOCK] session 1 waits for session 2 on accounts:2
@2 update accounts set balance = 0 where id = 1;
@2| [ERROR:01804] deadlock: transaction 3 was rolled back
@1| Update statement executed successfully (1 rows)
@1| [EXEC] rows_examined=1

Choosing the youngest is one fair rule among several; what matters for a test is that it is deterministic. InnoDB picks the transaction that changed the fewest rows; PostgreSQL ends the session whose check found the cycle.

87. Read views (from `read-views`)

From this stage a plain read takes no locks and never waits. It reads the rows as they were when its read view was taken, rebuilding older versions from undo records where they have changed since.

Plain reads are SELECT, the subqueries inside it, and explain analyze. They take no locks (section 84 no longer applies to them) and read through the view. Everything else reads the newest committed rows and locks as section 84 says, waiting as section 85 says: UPDATE and DELETE find the rows they change, and check their WHERE, on the newest rows, subqueries inside them included, and INSERT, foreign key checks and UNIQUE checks look at the newest rows too. Section 88 changes plain reads under SERIALIZABLE.
Versions. The row in the tree is the newest version of a row. Each undo record of the row (section 82) holds the version before a change, made by the record's transaction, so following a row's records from the newest gives its older versions in turn. A DELETE's version is the row's absence.
Taking a view. A transaction's view is taken by its first plain read, not by BEGIN, and kept until the transaction ends. An autocommit SELECT takes a view for itself. A view holds two things: the id the next transaction would get at that moment, and the ids of the transactions open at that moment, other than the one taking it.
What a view sees. A change made by transaction t is visible to the view of transaction r when t is r, or when t is smaller than the view's next id and was not open when the view was taken: it had committed. For each row, a read sees the newest version whose change is visible, or, when the row's own insertion is not visible, nothing. A row whose visible version is a deletion is not seen either.
Counting. rows_examined counts the rows a scan hands up, as before: a row the view does not see is not handed up and not counted.
Deleting marks. A DELETE no longer takes the row out of its leaf. It marks it: bit 15 of the length in the row's slot (section 16) is set, the row keeps its bytes and its slot, and free_space does not change, since the cell still uses its bytes. btree dump prints marked at the end of a marked cell's line: [BTREE] Cell 2: key=7 (21 bytes) marked. A marked row is the deletion version of its row: reads that see the delete do not see it, and an INSERT of its key, once the deleting transaction has committed, replaces it. Only table rows that DELETE and its cascades remove are marked; the catalog's rows (DROP TABLE, DROP INDEX, the statistics ANALYZE replaces) are still taken out at once. Undoing a DELETE clears the mark. Until mvcc-indexes (section 89) a DELETE still takes the row's index entries out at once, and tests read old versions through the table's key only: what an index-only scan (section 58) shows a view for rows changed since it was taken is not defined until then.
Keeping old versions. Undo records are no longer dropped when their transaction commits, and its undo pages (section 83) are no longer freed: a view may still need them. Purge drops and frees them. Those of a ROLLBACK are dropped when it ends, as before. A commit marks its own undo pages as committed, a change logged with it, and recovery's undo pass (section 83) rolls back only the transactions whose undo pages are not marked so.
Purge. When a transaction ends and no read view is open in any session, every undo record of a committed transaction is dropped, and every row a committed transaction marked is taken out of its leaf, in the order they were marked, as a DELETE took it out before this stage, merges and freed pages included (section 28). So with one session every transaction ends with nothing kept, as before. Purge at a commit runs before the commit writes its log records, so what it changes goes to the log with that commit, and one session's log is the same as before this stage. Section 90 adds a purge command for when views are open. A clean end of the program purges this way after its rollbacks, and so does recovery after its undo pass (section 83): it frees the committed undo pages, and reads every table and index tree to take out the rows and entries committed transactions marked. A page that fails its checksum there is passed over and left for the statement that uses it, and these reads and writes are not counted (section 36).
undo status: oldest_view is the id of the transaction that holds the oldest open view, taken first, 0 when none is open; purgeable counts the undo records of committed transactions that every open view sees the change of, which no view can need.

@1 begin;
@1 select name from users where id = 5;
@1| name
@1| ann
@1| (1 rows)
@1| [EXEC] rows_examined=1
@2 update users set name = 'bea' where id = 5;
@2| Update statement executed successfully (1 rows)
@2| [EXEC] rows_examined=1
@1 select name from users where id = 5;
@1| name
@1| ann
@1| (1 rows)
@1| [EXEC] rows_examined=1

InnoDB keeps the newest row in the tree and the older ones in its undo log, as here, with each row's last writer and a pointer to its undo record stored in two hidden columns. This engine keeps that pointer in memory beside the undo records instead, so the row format does not change; after a restart no view can be open, so nothing needs it. PostgreSQL does the opposite: every version is a row in the table, and VACUUM sweeps the dead ones out (section 90).

88. Isolation levels (from `isolation-levels`)

SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

Each prints Set transaction statement executed successfully and sets the level of every transaction its session starts from then on, until another SET changes it. A session starts at REPEATABLE READ. The words after SET are matched as written here, in any case, and are not keywords: tokenize prints transaction, isolation, level, read, committed, repeatable and serializable as identifiers. Any other words after SET are 00302, READ UNCOMMITTED included. SET while the session's transaction is open is 01805, and the level does not change. ast prints Statement: SET TRANSACTION ISOLATION LEVEL <level> with the level in capitals and one space between its words, and explain prints its node as SetTransaction, running nothing.

Level	A plain read (section 87)
`READ COMMITTED`	takes a new view for each statement, kept until the statement ends
`REPEATABLE READ`	uses one view for the whole transaction, taken by its first plain read (section 87)
`SERIALIZABLE`	reads the newest committed rows, taking the locks of section 84 and waiting as section 85 says, as plain reads did before `read-views`

At every level, UPDATE and DELETE act on the newest committed rows and lock them (section 87), so a REPEATABLE READ transaction may change a row to something its own view never showed. sessions shows the level in iso, with an underscore between its words (section 81). undo status counts a READ COMMITTED session's view only while its statement runs.

What each level lets happen, each row a case of the stage's suite:

Anomaly	READ COMMITTED	REPEATABLE READ	SERIALIZABLE
dirty read: seeing another transaction's uncommitted change	never	never	never
non-repeatable read: one row reads differently twice in a transaction	happens	never	never
phantom: a second read of the same condition finds a new row	happens	never, for plain reads	never: the scan holds a lock
lost update: two `set n = n + 1` lose one	never: the row lock	never	never
write skew: two transactions each read what the other changes	happens	happens	never: one waits, and one is a deadlock victim

InnoDB's REPEATABLE READ also takes gap locks, between index entries, so that a locking read finds no phantoms either. This engine locks rows and tables only: a locking read is phantom-free under SERIALIZABLE, by its table lock, and only there.

89. Indexes under versions (from `mvcc-indexes`)

An index entry carries no version: it is a value and a key (section 54), whichever transaction wrote it. From this stage index entries are marked like rows (section 87), and every row found through an index is checked against the version the reader sees.

Statement	Each index of the table
INSERT	gains the new row's entry, or, when an entry with that value and key is marked, unmarks it
UPDATE that changes the indexed value	marks the row's old entry, and gains the new one as an INSERT does
DELETE	marks the row's entry
undoing any of these	takes the change back: afterwards the row's entries are what its versions still kept say, the newest version's entry unmarked, the entry of a deleted newest version or of a kept older version marked, and any other entry the change made taken out
purge (section 87)	takes out the marked entries of every row change it drops, as it takes out marked rows

A marked entry is marked with bit 15 of its slot's length, as a row is.

Reading through an index. Every entry whose value the scan's bounds take, marked or not, leads to its row. The reader rebuilds the version of that row it sees (section 87), and hands the row up only when that version exists, is not a deletion, and has the entry's value in the indexed columns. So a row whose value changed from a to b after a view was taken is found by = 'a' through the old entry and not found by = 'b', for that view, and a row is never handed up twice. Locking reads check the newest committed version the same way.
Index-only scans (section 58) answer an entry from the index alone only when the entry is not marked and no undo record of its row is kept; otherwise they read the row as above, which is not counted in index_lookups.
UNIQUE (section 57): a value is taken when an entry that is not marked has it, or a marked one whose marking transaction is another transaction that has not committed. A transaction's own deletion frees the value for its own INSERT. So deleting a row and inserting its unique value again is accepted once the delete has committed, though its marked entry is still there.
index check counts every entry in entries=<n>, marked ones included. It is OK when each row that is not marked has exactly one unmarked entry, with its newest value and its key, every unmarked entry has such a row, and the entries are in order. So after a purge, or in one session after each transaction, entries equals the number of rows, as before.
Counting: index_lookups counts as before; an index-only scan that reads a row from the table does not count it again in rows_examined, which counts rows handed up.

90. Purge (from `purge`)

Section 87 purges only when no read view is open. One long-running reader then holds back every change made since, and so does any other view while one is open, even when no view needs most of those changes. From this stage purge drops everything older than the oldest open view.

What purge may drop. The undo record of a committed transaction t is purgeable when every open view sees t's change (section 87): no view can need the version it holds. A row or index entry marked by such a transaction can go with it. With no view open, every committed transaction's records are purgeable, as in section 87.
purge drops every purgeable record, takes out every marked row and index entry whose deletion it dropped, in the order they were marked, as section 87 says, frees every undo page left holding no record, and prints:

[PURGE] records=<r> rows=<m>

r is the number of undo records dropped and m the number of marked rows taken out of tables, index entries not counted. With nothing to do it prints records=0 rows=0. purge with anything after it is 00104.

purge is logged like a commit (sections 35 and 83): before purging it writes the undo records of open transactions that are in no undo page yet, and after purging it logs every page changed since it was last logged, then a commit record, so nothing it changed reaches the database file unlogged. With nothing changed it logs nothing.
One mark at a time. A row or entry is taken out only when the mark it carries now is one purge drops: a row deleted and committed, inserted again and marked again by a transaction still open, stays.
When it runs by itself is unchanged: when a transaction ends and no view is open (section 87). While any view is open, only purge drops what that view does not need. So after a long reader commits, the backlog it held stays until the last view closes or purge runs.
undo status shows what is held back: oldest_view is the transaction holding the oldest open view, and purgeable the records purge would drop now (section 82). Right after a purge, purgeable=0.
Undo pages (section 83) go back on the free list when purge leaves them holding no record, so undo status counts fewer pages and db freelist shows them.

PostgreSQL keeps every version as a row in the table, so something must sweep the table: VACUUM finds the dead rows and frees their space. InnoDB keeps old versions in undo and trims a log, which is what purge does here. The villain is the same in both: one transaction that stays open holds back every cleanup after it. VACUUM in section 30 is a third thing, moving pages to make the file shorter, with nothing to do with versions.

91. What Sessions and Concurrency changes

As in section 21, each change is made by one stage, which retires the earlier cases that checked the old contract, by name, in the manifest.

Earlier contract	Section	Changed by	Now
a line is a statement, a debug command or a meta command	2	`sessions`	a line may start with `@<n>` and run as session `n`, its output tagged (section 81)
CHECKPOINT and VACUUM need no transaction open in their own session	33, 37	`sessions`	and none in any other session, else `01802` (section 81)
ROLLBACK puts back every page the transaction changed as it was at BEGIN	34	`undo-log`	applies one undo record per row change, newest first; pages allocated stay (section 82)
DROP TABLE, TRUNCATE and DROP INDEX free their pages at once	27, 54	`undo-log`	when their transaction commits (section 82)
ROLLBACK writes nothing and logs nothing	34, 35	`undo-log`	logs the pages applying undo changed, as a commit logs its pages (section 82)
TRUNCATE keeps its root as an empty leaf	27	`undo-log`	inside a transaction it gives the table a new root, freeing the old tree at commit (section 82)
a commit logs the pages its transaction changed	35	`undo-recovery`	every page changed since it was last logged, other transactions' and undo pages included (section 83)
no page an open transaction changed reaches the database file	33	`undo-recovery`	none it changed since the page was last logged (section 83)
header bytes 28 to 31 are zero	18	`undo-recovery`	the first undo page (section 83)
recovery replays committed pages, and its line ends with `discarded=<d>`	36	`undo-recovery`	then rolls back every transaction left in undo pages, and the line ends with `rolled_back=<u>` (section 83)
an UPDATE assigns literals	10, 40	`lock-waits`	any expression over the row's columns (section 85)
a DELETE takes the row out of its leaf	17, 28	`read-views`	marks it; purge takes it out (section 87)
undo records are dropped when their transaction ends	82	`read-views`	a committed transaction's are kept until purge (section 87)
a commit frees its own undo pages	83	`read-views`	marks them committed; purge frees them (section 87)
recovery ends after its undo pass	83	`read-views`	then purges, with no view open (section 87)
SELECT takes locks and waits	84, 85	`read-views`	reads through a read view, with no locks (section 87)
a statement starting with SET is `00301`	5	`isolation-levels`	SET TRANSACTION ISOLATION LEVEL sets the session's level (section 88)
an index loses a deleted row's entry, and an updated row's old one	55	`mvcc-indexes`	marks it; purge takes it out (section 89)
`index check` counts one entry per row	54	`mvcc-indexes`	counts marked entries too (section 89)
purge runs only when a transaction ends with no view open	87	`purge`	and `purge` drops what the oldest open view does not need (section 90)

92. How the Server track is tested (the test kit)

The Server track is optional, and the platform does not run it: its tests need a network, and the sandbox has none. They come in a test kit, droid-server-kit.zip, linked from every page of the track. The kit needs Python 3 and nothing else, and holds only the tests: the learner builds their own program and points the kit at it.

python3 run.py --list
python3 run.py --stage <stage slug> --bin <your program> [--pool <your pooler>]

--stage runs every stage of the track up to and including the one named, without the cases those stages retire, as passing a stage means everywhere else (section 1). --only runs that stage alone, --case <name> one case. A passing case prints one line; a failing case prints what was sent, what was expected, what came back, the server's stdout and the reason.

Starting the server. For each case the kit starts the program as

<program> --server --port 0 --db <a directory of the case's own>/test.db [flags the case adds]

with nothing on stdin. Port 0 asks the system for a free port. When the program is ready to accept connections it prints, on stdout, on a line of its own:

[SERVER] listening on 127.0.0.1:<port>

<port> is the port it was given. The kit waits for this line (3 seconds, like every other test deadline) and then connects to that port. It never sleeps and never guesses a port. A program that exits first, or prints no such line, fails the case. Stdout is the server's log: the stages that log something there (a statement waiting for a lock, the shutdown) say which line, and a case waits for that line as its signal instead of waiting for time to pass. Lines must reach stdout as they are printed, not when the program ends. Every other line is ignored.

Ending. After each case the kit stops the program, whatever state it is in, and deletes the case's directory. The stage that adds SHUTDOWN (server-listen) pins how the server stops by itself.

One thread. Every connection is a session of the multiplexer (section 81), numbered in the order the server accepted it. The tests do not depend on how the server waits for its sockets, but they were written for one thread and one poll loop, so a test never needs two statements to run at the same instant.

Checking the tests against PostgreSQL. python3 run.py --stage all --target postgres://... runs the cases against a real PostgreSQL instead of the program: a case PostgreSQL fails is a wrong test. CI does this on every change. There:

cases about what only droid has (its log lines, SHUTDOWN, --max-connections, the plan cache, the pooler) are skipped;
the fields only droid pins match anything: the process id in BackendKeyData (droid's session number) and the text of an error message, where a case checks one; the SQLSTATE and the severity are always compared;
the kit logs in with trust authentication, the only kind it speaks, so the PostgreSQL it is pointed at must be a throwaway one.

What the kit compares. Every message the server sends is decoded, and a message that cannot be decoded (a wrong length, a string with no zero byte, bytes left over after its fields) fails the case. Message sequences are compared in order, message by message. A greeting is compared by its required parts only: AuthenticationOk first, a ParameterStatus for each parameter the track requires, in any order and among any others, one BackendKeyData, and ReadyForQuery last. A few cases compare exact bytes, and say so.

93. A listener and the line protocol (from `server-listen`)

The command line. --server makes the program a server instead of a REPL. It never reads stdin.

Flag	Meaning
`--server`	serve connections instead of reading stdin
`--port <n>`	the TCP port to listen on, on `127.0.0.1` only; `0` asks the system for a free one. Required with `--server`
`--db <path>`	the database file, as in section 2
`--wire text`	each connection speaks the line protocol below. In this stage it is the only protocol, so its absence may mean it too; from `pg-startup` on, no `--wire` means the PostgreSQL protocol (section 94)

A server flag that cannot be understood is 01901: --server without --port, a port that is not a number from 0 to 65535, a --wire the program does not speak, or --port or --wire without --server. --port or --wire with nothing after it is 00102, as for any option missing its argument. -c with --server is not defined. A port that cannot be listened on, because another program has it, is 01902. Either prints its one line and exits with status 1, like a command line error (section 3); there is no listening line.

The database file is opened before the listening line (section 92); a file that cannot be used prints its error line and the program exits with status 1, as in section 2.

Sessions. Every connection the server accepts is a session of section 81. Sessions are numbered 1, 2, 3, ... in the order the server accepted their connections; a number is never given twice in one run, so the connection accepted after session 1 closes is still the next number. A session exists from its connection's accept until its connection closes. There is no session 1 standing in for stdin: with no connection open there are no sessions, and sessions lists only connections that are open.

The server's log. Besides the lines of section 92, the server prints on stdout:

[SERVER] session <n> connected
[SERVER] session <n> closed

the first when it accepts a connection, the second when that connection is gone, after its session's open transaction, if any, has been rolled back.

The line protocol. With --wire text, a connection is the REPL of section 2, over the socket:

When the server accepts the connection, it sends the welcome line (a line starting with Welcome to droid) and the prompt >.
Bytes from the client are cut into lines at \n; a \r right before the \n is dropped. A line may arrive in many reads, and many lines in one read: the server keeps what it has received of a line until the rest arrives, and handles complete lines one at a time, in order.
Each line runs as a line of that session (section 81, with no @ prefix: a connection's lines never carry one, and a line that does is not defined), and the server sends exactly the lines the REPL would print for it, untagged, each ending with \n, then the prompt >. An empty line sends just the prompt.
.exit sends exiting.. good bye!, rolls back the session's open transaction and closes that connection only. The server goes on serving the others.
A client that closes its connection, at any point and even mid-line, ends its session the same way; the part of a line it had sent is dropped.

So a client reads a reply up to the next > that starts a line. No line the tests make the server print starts with >.

<- Welcome to droid ...
<- >
-> create table t (id int primary key, v varchar(20));
<- Create table statement executed successfully
<- >

(-> is what the client sends, <- what it receives; the prompt has no newline after it.)

Waiting is not blocking. A statement that parks waiting for a lock (section 85) sends its [LOCK] session <n> waits for session <m> on <resource> line to its own connection, and no prompt. The server goes on serving every other connection. The lines that connection sends while its statement is parked wait, unread, until the statement has resumed and finished, so 01803 never happens in server mode. When the statement resumes, its lines and then the prompt go to its own connection, whichever connection's statement released the lock.

A connection's reply is also never held up by another connection that is slow to read: the server keeps what it has not yet been able to send to a connection and sends it as that connection can take it, while it serves the others.

shutdown. A line shutdown or shutdown; (any case) stops the server: it rolls back the open transaction of every session in ascending session order, saves the database as .exit does (section 33), closes every connection without sending anything more, prints [SERVER] shutdown and exits with status 0. It prints [SERVER] session <n> closed for each connection it closes, in ascending session order, before [SERVER] shutdown; whatever a connection had not yet been sent is dropped. shutdown with anything else after it is 00104; spaces before the ; are allowed.

A connection that closes while its statement is parked drops the statement: its session's transaction is rolled back and its locks released, and the parked statements of other sessions are looked at as after any release (section 85). A deadlock victim (section 86) gets its 01804 line on its own connection, then the prompt, and its waiting lines run after it.

94. The startup handshake (from `pg-startup`)

From this stage, a server started without --wire, or with --wire pg, speaks the PostgreSQL frontend/backend protocol, version 3.0, on every connection. --wire text still gives the line protocol of section 93, unchanged. Everything in section 93 that is not about lines holds for both: sessions numbered in accept order, the [SERVER] log lines, a connection that goes away rolled back, shutdown (on a text connection), the output buffers.

Messages. After the first message of a connection, every message, both ways, is one type byte, then a 4-byte big-endian length that counts itself and the body but not the type byte, then the body. The first message a client sends has no type byte: just the length and the body. Integers are big-endian; a string is its UTF-8 bytes and a zero byte.

Bytes	Field	Value
4	length	the whole message, these 4 bytes included
4	protocol	`196608` for 3.0: the major version in the high 16 bits, the minor in the low
n	parameters	name and value strings, one after the other: `user`, `database`, `application_name`, ...
1	end	`0`

The first message. It is one of:

First 8 bytes	What it is	The server's answer
length 8, code `80877103`	SSLRequest	the single byte `N` (no TLS here); once it has read the `N`, the client sends its next first message on the same connection
length 8, code `80877104`	GSSENCRequest	the single byte `N`, the same way
length ≥ 8, protocol `196608`	StartupMessage, protocol 3.0	the greeting below
protocol with a major version other than 3	an older or unknown protocol	ErrorResponse, severity `FATAL`, SQLSTATE `0A000`, then the server closes the connection

A length below 8 or above 10000 makes the server close the connection without a reply; it checks the length as soon as its 4 bytes have arrived, before waiting for anything more. A StartupMessage whose parameters are not complete name and value pairs followed by one final zero byte, ending exactly at the message's length (user\0 alone, user\0droid, user\0droid\0 with no final zero), gets an ErrorResponse, severity FATAL, SQLSTATE 08P01, and then the server closes the connection. Either way the server goes on serving everyone else. Not tested: a request for a minor version above 0, and a client that sends its StartupMessage before reading the answer to its SSLRequest (PostgreSQL closes such a connection, since those bytes could have been planted before encryption began).

The parameters are read but change nothing: the server has one database, its --db, and trusts whoever connects. user and database may be anything.

The greeting. The answer to a StartupMessage for protocol 3.0 is, in this order:

AuthenticationOk: R, length 8, the 32-bit integer 0. In bytes: 52 00 00 00 08 00 00 00 00.
One ParameterStatus (S, then the name and the value as strings) for each of:

Name Value
server_version 16.0 (droid)
server_encoding UTF8
client_encoding UTF8
DateStyle ISO, MDY
integer_datetimes on
standard_conforming_strings on

in any order. Drivers read these; server_version must start with a version number, and standard_conforming_strings on tells them a backslash in a string is just a backslash.
BackendKeyData: K, length 12, the process id, then the secret key, each a 32-bit integer. The process id is the connection's session number. The secret key is any number the server chooses for that connection; a later stage uses the pair to cancel a statement.
ReadyForQuery: Z, length 5, the status byte I (idle). In bytes: 5A 00 00 00 05 49.

Errors. An ErrorResponse is E, its length, then fields, each a one-byte code and a string, then a zero byte. Every ErrorResponse carries at least S (severity, localized), V (severity, not localized), C (SQLSTATE) and M (the message), and S and V are equal. The tests read S, V and C, and against droid also M; they ignore any other field.

Terminate. X with length 4 ends the connection: the server closes it, and the session ends as in section 93. In this stage it is the only message a client sends after the greeting; the next stage adds queries, and other messages are not defined until a stage defines them. After the greeting, a message whose length is below 4 makes the server close the connection without a reply. A CancelRequest (code 80877102) is not defined before pg-connection-lifecycle.

Sessions. A connection is a session from its accept, as in section 93, whatever it then sends: one that never finishes its startup still takes a session number and is logged connected and closed.

Message texts. The text in M is the server's own words; a test compares it only where this page gives it, and none of this section's errors has a pinned text.

One read is not one message. As with lines in section 93, a message may arrive in many reads and many messages in one read. The server keeps what it has of a message until the whole length has arrived.

95. Simple query: results as messages (from `pg-simple-query`)

After the greeting, a client sends Query: Q, its length, then the SQL as one string. The server runs it as the session of that connection and answers with messages that end with ReadyForQuery. The client sends nothing more until ReadyForQuery arrives.

What a query holds. In this stage a Query holds one statement. Its final ; may be left out: the end of the string ends the statement, as the ; does on a REPL line. A line break (\n or \r) anywhere in the query is whitespace to the lexer, like a space; spaces and line breaks around the statement are ignored. Several statements in one Query are pg-errors-txn-status's.

Four kinds of result. Whatever a line prints in the REPL is one of four kinds, and each kind becomes messages:

What the REPL prints	Kind	Messages
the header, the rows and `(n rows)` of a SELECT	rows	RowDescription, one DataRow per row, CommandComplete `SELECT n`
a success line: `Insert statement executed successfully (1 rows)`, `Begin statement executed successfully`, ...	status	CommandComplete with the statement's tag
an error line, and its `HINT:` line	error	ErrorResponse (section 96)
nothing, for an empty line	empty	EmptyQueryResponse: `I`, length 4

Then ReadyForQuery. The [EXEC] line and any other line the REPL adds after a result for the person at the keyboard are not sent. A query that is only spaces, line breaks or a ; is empty.

RowDescription is T, its length, the number of columns (16 bits), then for each column: its name (a string), the table's id and the column's number (32 and 16 bits, both 0 in droid), the type id (32 bits), the type's size (16 bits), a type modifier (32 bits, -1 in droid) and the format code (16 bits, 0 for text). The name is the column's header as the REPL prints it: the column name, or the alias after AS. The types:

droid type	Type id (OID)	Name in PostgreSQL	Size
`INT`	`23`	`int4`	`4`
`VARCHAR(n)`	`1043`	`varchar`	`-1`
`DECIMAL`, from `AVG`	`1700`	`numeric`	`-1`
truth value	`16`	`bool`	`1`

A column whose every value is NULL and whose type the statement does not fix (select null) is a VARCHAR. droid's INT holds 0 to 4294967295 in a column and 64 bits in an expression, more than int4 does; the text of the value is sent all the same, and a driver that reads it into a 32-bit integer may refuse the larger ones.

DataRow is D, its length, the number of values (16 bits), then for each value its length (32 bits) and its bytes: the text the REPL prints for it, without padding. NULL is the length -1 with no bytes; an empty string is the length 0. A truth value is t or f, as PostgreSQL sends it (the REPL prints true and false).

CommandComplete is C, its length and the tag, a string:

Statement	Tag
SELECT	`SELECT <rows sent>`
INSERT	`INSERT 0 <rows inserted>` (the `0` is a leftover PostgreSQL keeps for old clients)
UPDATE, DELETE	`UPDATE <rows>`, `DELETE <rows>`: the count of the success line
CREATE TABLE, DROP TABLE, ALTER TABLE, TRUNCATE	`CREATE TABLE`, `DROP TABLE`, `ALTER TABLE`, `TRUNCATE TABLE`
CREATE INDEX, DROP INDEX	`CREATE INDEX`, `DROP INDEX`
BEGIN, COMMIT, ROLLBACK	`BEGIN`, `COMMIT`, `ROLLBACK`
ANALYZE, CHECKPOINT, VACUUM	`ANALYZE`, `CHECKPOINT`, `VACUUM`
SET TRANSACTION	`SET`

Debug commands (tx status, sessions, btree dump, ...) and explain are droid's own, not SQL, but they answer over the wire too, as rows: one column of type text (25, size -1), named QUERY PLAN for explain and droid for the others, one DataRow per line the REPL prints for them, and the tag EXPLAIN or SHOW. Meta commands (a line starting with .) are a REPL's, not a server's: over the wire they are not defined.

A debug command is run as typed: it takes no ;. One that prints no line answers with its RowDescription, no DataRow and the tag SHOW. explain analyze answers as explain does.

Waiting. A statement that parks waiting for a lock (section 85) sends nothing until it resumes; then its result and ReadyForQuery. Its [LOCK] line is not sent over the protocol. Messages that arrive meanwhile wait, unread, as lines do in section 93. A deadlock victim (section 86) answers with an ErrorResponse, then ReadyForQuery.

Errors in this stage are an ErrorResponse with severity ERROR and some SQLSTATE; section 96 says which, and what happens to the HINT: line. shutdown over this protocol is pg-connection-lifecycle's.

Terminate still ends the connection, as in section 94.

ReadyForQuery's status byte is I after every query in this stage's tests: none of them opens a transaction. Section 96 says what it is inside one.

96. Errors, SQLSTATE and the status byte (from `pg-errors-txn-status`)

ErrorResponse fields. An error over the PostgreSQL protocol is an ErrorResponse (section 94) with these fields, in this order, then the zero byte:

Field	Value
`S` and `V`	`ERROR`; `FATAL` for an error that ends the connection
`C`	the SQLSTATE of the droid code, from the table below
`M`	the error line's message: what the REPL prints after `[ERROR:SSCCC]`
`D`	`droid error SSCCC`: the droid code itself
`H`	the text of the error's `HINT:` line after `HINT:` , when it has one; no `H` field when it has none

SQLSTATEs. Every droid code an error can carry over the wire has one SQLSTATE, the code PostgreSQL gives the same condition. Codes that only a command line, the REPL or the file can raise (00101, 00102, 00103, 00105, 00106, 00107, 00603, 00604, 00608, 01001, 01801, 01803, 01901, 01902) never reach a client and have none.

SQLSTATE	PostgreSQL's name	droid codes
`42601`	syntax_error	`00201`, `00202`, `00301`, `00302`, `00303`, `00901`, `01505`, `01710`
`42P01`	undefined_table	`00401`, `01607`, `01701`
`42703`	undefined_column	`00402`
`42804`	datatype_mismatch	`00403`, `01706`
`22003`	numeric_value_out_of_range	`00404`, `01502`
`22001`	string_data_right_truncation	`00405`
`23502`	not_null_violation	`00406`, `01104`, `01503`
`23503`	foreign_key_violation	`01704`, `01707`
`23505`	unique_violation	`00701`, `01605`, `01606`
`22012`	division_by_zero	`01501`
`21000`	cardinality_violation	`01709`
`42701`	duplicate_column	`00408`
`42702`	ambiguous_column	`01702`
`42712`	duplicate_alias	`01703`
`42P07`	duplicate_table	`01101`, `01602`
`42704`	undefined_object	`01102`, `01603`
`42611`	invalid_column_definition	`01103`
`42P16`	invalid_table_definition	`01601`
`42830`	invalid_foreign_key	`01705`
`2BP01`	dependent_objects_still_exist	`01708`
`42803`	grouping_error	`01507`, `01508`
`42P10`	invalid_column_reference	`01509`
`42883`	undefined_function	`01506`
`25001`	active_sql_transaction	`01301`, `01304`, `01805`
`25P01`	no_active_sql_transaction	`01302`
`55000`	object_not_in_prerequisite_state	`01802`
`40P01`	deadlock_detected	`01804`
`54000`	program_limit_exceeded	`00407`, `01604`
`53100`	disk_full	`00602`
`53200`	out_of_memory	`01201`, `01303`
`58030`	io_error	`01504`, `00609`
`0A000`	feature_not_supported	`00702`, `00801`, `01608`, `01905`
`22023`	invalid_parameter_value	`00104`, `00501`, `00502`, `00503`, `00601`, `00605`, `00606`, `00607`, `00703`, `01202`, `01203`, `01204`
`25P02`	in_failed_sql_transaction	`01903`
`08P01`	protocol_violation	`01904`
`53300`	too_many_connections	`01906`
`57P05`	idle_session_timeout	`01907`
`57014`	query_canceled	`01908`
`57P01`	admin_shutdown	`01909`

A code a later part adds names its SQLSTATE where it is defined. Three codes the wire itself raises:

Code	Condition	SQLSTATE
`01903`	a statement other than COMMIT or ROLLBACK in a failed transaction (below)	`25P02`
`01904`	a message the server does not expect: a type it does not know, or one sent where the protocol does not allow it	`08P01`
`01905`	a protocol version the server does not speak	`0A000`

The FATAL errors of section 94 carry 01904 and 01905. A message of a type the server does not know is 01904 too, severity FATAL: the server closes the connection after it, and the session ends as in section 93.

The status byte. ReadyForQuery's last byte is the session's state when the answer ends:

Byte	State
`I`	idle: no transaction open
`T`	a transaction is open, BEGIN to COMMIT or ROLLBACK
`E`	a failed transaction: one in which a statement failed

Failed transactions. Over the PostgreSQL protocol, a statement that fails inside an open transaction makes that transaction failed, as PostgreSQL does, though the engine kept the transaction as it was (section 3: a failed statement changes nothing). Until the transaction ends:

every statement other than COMMIT and ROLLBACK runs nothing and gets 01903, 25P02;
ROLLBACK rolls the transaction back, with the tag ROLLBACK;
COMMIT also rolls it back, and its tag is ROLLBACK, not COMMIT: nothing of a failed transaction is kept.

A deadlock victim (01804) is failed in the same way: its transaction was already rolled back (section 86), and its next COMMIT or ROLLBACK ends the failed state with the tag ROLLBACK. This rule belongs to the protocol layer: the REPL and the line protocol keep section 3's, unchanged.

Several statements in one Query. A Query may hold several statements, each ended by ; (the last ; may be left out). They run in order, and each answers as section 95 says, with one ReadyForQuery after the last:

when no transaction is open and none of the statements is BEGIN, COMMIT or ROLLBACK, they run as one implicit transaction: begun before the first, committed after the last; if one fails, its ErrorResponse is the last result, the statements after it do not run, and what the ones before it changed is rolled back;
otherwise each runs as if it were its own Query, in turn, and the first error ends the Query: the statements after it do not run.

A statement that cannot run inside a transaction (01304) gets that error inside an implicit transaction too.

Splitting. A ; inside a string literal does not end a statement. Empty pieces (a;;b) are skipped; a Query made only of empty pieces is the empty query of section 95.
In a failed transaction each statement's 01903 is an error like any other: it ends the Query, and the status stays E.
A deadlock victim inside an implicit transaction gets 40P01 and the Query ends with I: the implicit transaction is gone, and there is nothing left to mark failed.
A statement that parks partway through a Query holds the rest of the Query: the statements after it run once it has resumed and finished, and the one ReadyForQuery comes after the last.

97. Waiting, cancelling, disconnecting (from `pg-connection-lifecycle`)

The [LOCK] line on the server's log. A statement that parks (section 85) also prints its line on the server's stdout, whatever its connection speaks:

[LOCK] session <n> waits for session <m> on <resource>

It is the same line a text connection receives (section 93); a PostgreSQL connection still receives nothing while it waits (section 95). It is printed when the statement parks, each time it parks.

Limits. Two flags, each with --server only, a bad value being 01901:

Flag	Meaning
`--max-connections <n>`	at most `n` connections, 1 to 1000, are sessions at once; no limit when absent
`--idle-timeout-ms <n>`	a connection idle for `n` milliseconds, 1 to 3600000, is closed; no timeout when absent

Too many connections. A connection accepted while n sessions exist becomes no session: the server knows it is over the limit when it accepts it, so it gives it no number and logs no line. Over the PostgreSQL protocol the server reads its first message, answers an SSLRequest or GSSENCRequest with N as usual, and answers its StartupMessage with an ErrorResponse, severity FATAL, 01906 (53300), then closes it. Over the line protocol it sends the error line and closes it.
Idle. A session is idle while it has no transaction open, no statement parked, no part of a message or line received, and nothing waiting to be sent. Once it has been idle for the timeout, the server sends it 01907 (57P05), severity FATAL over the PostgreSQL protocol, and closes the connection, which ends the session as in section 93. A session with a transaction open is never closed for being idle. Its idle time starts again whenever it receives a byte or the server finishes sending it what it had to send.
Over the limit, a first message for a protocol the server does not speak still gets 01905.

CancelRequest. A client cancels a running statement from a second connection. That connection's first message is a CancelRequest: length 16, the code 80877102, then the process id and the secret key of the session to cancel, as its BackendKeyData gave them (section 94). The server closes that second connection without a reply, whatever happens. Like every connection accepted under the limit, it took a session number when it was accepted and is logged connected and closed (section 94), but it runs nothing. A CancelRequest is honoured even when the server is at --max-connections. Then:

if the process id names a session, the key is that session's, and the session has a statement parked, the statement stops: it is dropped as section 93 drops the statement of a connection that closes, except that its transaction is not rolled back when the client opened it with BEGIN; the session's connection gets an ErrorResponse 01908 (57014), and then ReadyForQuery, E inside a transaction (now failed, section 96) and I outside one;
otherwise nothing happens: a wrong key, an unknown session or a session with nothing parked is ignored, silently.

A statement that is not parked runs to its end before the server reads anything else, so in droid only a parked statement can be cancelled. A cancelled statement inside an implicit transaction (section 96) rolls the implicit transaction back, and its ReadyForQuery says I.

shutdown over the PostgreSQL protocol. A Query shutdown (or shutdown;) stops the server as in section 93; before closing each PostgreSQL connection, the one that sent it included, it sends that connection an ErrorResponse, severity FATAL, 01909 (57P01). Text connections are closed as before. Only a Query that is shutdown alone stops the server; inside a Query of several statements it is not defined.

Codes.

Code	Condition	SQLSTATE
`01906`	a connection over `--max-connections`	`53300`
`01907`	a session idle for `--idle-timeout-ms`	`57P05`
`01908`	a parked statement cancelled by a CancelRequest	`57014`
`01909`	the server is shutting down	`57P01`

98. Prepared statements in SQL (from `sql-prepare`)

Three statements, which work wherever SQL does: in the REPL, over the line protocol and in a Query.

PREPARE <name> AS <statement>;
EXECUTE <name> [(<value>, ...)];
DEALLOCATE [PREPARE] <name>;
DEALLOCATE [PREPARE] ALL;

prepare, execute, deallocate and all are keywords. A name is an identifier.

Parameters. Inside the statement of a PREPARE, $1, $2, ... stand for values given later; the lexer reads $ and digits as one token, [PARAMETER - $1]. A parameter may stand wherever a literal value may (sections 40 and 41): in a WHERE, in the VALUES of an INSERT, in a SET of an UPDATE. The statement is a SELECT, INSERT, UPDATE or DELETE; any other after AS is 00302. A $ anywhere else than in a PREPARE's statement is 00302 as well.

Parameter types. Each parameter takes its type from where it stands: compared with something whose type is known (a column, a literal, an expression: $1 = 1 is an INT), or assigned to a column, it has that type; an operand of an arithmetic operator is an INT; nothing else fixes it, and then it is a VARCHAR. When a parameter appears in several places, the first that fixes a type gives it, and a later place that needs another type is 00403. Parameter numbers run from $1 to $65535 ($0, and a number past $65535, are 00302). The parameters are $1 up to the highest number used, and every one of them must appear: where id = $2 with no $1 is 01914.

PREPARE checks the statement as if it were run: an unknown table, an unknown column, a type mismatch are reported now, with their own codes, and nothing is prepared. Then it keeps the statement under its name in the session, and prints Prepare statement executed successfully (tag PREPARE). A name the session already uses is 01910.

EXECUTE runs the statement with each $k replaced by the k-th value, and prints exactly what the statement prints (its tag over the wire is the statement's). The values are literals: a number, a string or NULL. A different number of values than parameters is 01912. A value that is not of its parameter's type is 01913: a string for an INT parameter whose text is not a number, a number for a VARCHAR one; a string whose text is a number is that number, as PostgreSQL reads '5' for an int. A value that does not fit (00404, 00405) keeps its code. A name the session does not use is 01911.

PREPARE checks in this order: the syntax (00302), the name (01910), the parameter numbers (01914), then the statement as if run. That last check is what a statement's checks are before it touches a row: names, types, values; what depends on the rows, a duplicate key for one, waits for EXECUTE. A number given for an INT parameter may be negative, as a literal may (section 41); NULL fits any parameter. An error from the statement EXECUTE runs reports its columns against that statement, with the values in place. In the REPL and over the line protocol each statement still ends with ;; over the PostgreSQL protocol the final ; is optional, as in section 95. A parked EXECUTE that resumes runs its statement again from the start with the same values.

DEALLOCATE forgets the named statement and prints Deallocate statement executed successfully (tag DEALLOCATE); DEALLOCATE ALL forgets every statement of the session, prints the same line (tag DEALLOCATE ALL), and is never an error. An unknown name is 01911.

Sessions. Prepared statements belong to the session that prepared them. Another session does not see them and may use the same names. A session's statements go when the session ends.

Codes.

Code	Condition	SQLSTATE
`01910`	PREPARE of a name the session already uses	`42P05`
`01911`	EXECUTE or DEALLOCATE of a name the session does not use	`26000`
`01912`	EXECUTE with a different number of values than the statement has parameters	`42601`
`01913`	an EXECUTE value that is not of its parameter's type	`22P02`
`01914`	a parameter number that does not appear, below the highest one used	`42P18`

99. The extended query protocol (from `pg-extended`)

Besides Query, a client may run a statement in steps, each its own message. Text format only.

Message	Body	The server
Parse `P`	a statement name, the SQL, the number of parameter types and each type (32 bits; 0 for "infer")	prepares the statement as PREPARE does (section 98), under that name; answers ParseComplete `1`. Unlike PREPARE, it takes any one statement a Query may hold (BEGIN, COMMIT, CREATE TABLE, an empty string ...); parameters may still stand only where section 98 allows
Bind `B`	a portal name, a statement name, parameter format codes, the values (each a length and its text, `-1` for NULL), result format codes	makes a portal: the statement with these values; answers BindComplete `2`
Describe `D`	`S` and a statement name, or `P` and a portal name	for a statement: ParameterDescription `t` (the number of parameters, each one's type id), then RowDescription, or NoData `n` for a statement with no rows; for a portal: RowDescription or NoData
Execute `E`	a portal name, a row limit (0 for none)	runs the portal: its DataRows and CommandComplete, as section 95 says, but no RowDescription; EmptyQueryResponse for an empty statement
Close `C`	`S` or `P`, and a name	forgets that statement or portal; answers CloseComplete `3`, also for a name that does not exist
Sync `S`	nothing	ends the batch: answers ReadyForQuery, with the status byte of section 96
Flush `H`	nothing	asks the server to send what it has answered so far

Names. The empty name is the unnamed statement or portal: a Parse or a Bind to it replaces the one there, silently. A named statement is created once: Parse to a name the session already uses is 01910 (42P05). Statements made by Parse and by PREPARE share the session's names, so a Query EXECUTE p (...) runs a statement Parse made, and Close S forgets one PREPARE made. A portal lives until its transaction ends (at the Sync that ends an implicit one), or until Close.

Parameters. A type in Parse that is not 0 must be the type section 98 infers for that parameter, written as its type id (23, 1043); its count may be less than the statement's parameters, the rest inferred. The values of Bind are read as text, as section 98 reads EXECUTE's literals, NULL included, but they are never SQL: a value is the value, whatever characters it holds.

Execute with a row limit. n above 0 sends at most n DataRows. When an Execute has sent n rows, it stops there and sends PortalSuspended s instead of CommandComplete, without looking for a next row; the next Execute of that portal goes on from there. An Execute that runs out of rows before its limit sends CommandComplete, counting the rows of that Execute alone: SELECT 0 when none were left. A portal that has sent its CommandComplete is done; executing it again sends the same CommandComplete and runs nothing (SELECT 0 for a SELECT).

Errors. When a message of the batch fails, the server sends one ErrorResponse and then reads and ignores every message up to the next Sync, which answers ReadyForQuery. Between two Syncs, with no transaction open, the messages run in one implicit transaction (section 96): committed at the Sync, or rolled back if one failed. Inside a transaction the BEGIN opened, an error makes it failed, as a Query's would.

More rules. A failed Parse to the unnamed statement leaves the previous one in place. More types in Parse than parameters, a type past the last parameter not being 0, is 01918. Bind checks, in order: the statement (01911), the format codes (01917), the number of values (01916), the values (01913). In a failed transaction (section 96), Parse, Bind, Describe and Execute get 01903, except for a COMMIT or a ROLLBACK, which go through and end the transaction as section 96 says (tag ROLLBACK both); Close, Flush and Sync still work. A Query between an error and the next Sync is skipped like any other message. Every portal is dropped at a Sync that leaves no transaction open. A BEGIN in the middle of a batch's implicit transaction makes it the explicit transaction it opens. Debug commands and explain go through Parse too, and answer as section 95 says; SQL that is neither gets the parser's error at Parse.

What a batch gets, in order. Each message's answer, in the order the messages came. The server may send answers as soon as they are ready, before Sync or Flush; a client that waits for them sends Flush or Sync.

Codes.

Code	Condition	SQLSTATE
`01915`	Execute or Describe `P` of a portal the session does not have (a statement the session does not have is `01911`)	`34000`
`01916`	Bind with a different number of values than the statement has parameters	`08P01`
`01917`	a format code that is not 0 (text): binary parameters or results	`0A000`
`01918`	a Parse type that is neither 0 nor the type the parameter is given	`42804`

100. Cached plans (from `plan-cache`)

A statement keeps its plan. PREPARE and Parse plan the statement once it is checked, and keep the plan with it. The plan is generic: made without the values, so it holds $k where a value will go, and the planner's choices (sections 52 to 63) are those it makes for a value it does not know: id = $1 on a key is an IndexScan, and an estimate for col = $1 is the one for an unknown value of col. EXECUTE, and Bind and Execute, run the kept plan with the values in place.

What a plan depends on. The tables it reads or changes, their indexes and their statistics. A statement that changes one of them, in any session, invalidates every kept plan that reads or changes that table, when the statement runs (a ROLLBACK does not bring the plan back):

Statement	Invalidates plans over
CREATE INDEX, DROP INDEX	the index's table
ALTER TABLE, TRUNCATE, DROP TABLE	that table
ANALYZE	that table (every table, with no name)

The next EXECUTE of an invalidated statement plans it again first, silently, and runs the new plan. If planning fails, the EXECUTE fails with the error planning gives (00401 for a table that no longer exists) and the statement stays prepared: a later EXECUTE plans again, and works once the table is back. A new plan whose result has other columns than the statement had when it was prepared (other names, types or number: select * after ADD COLUMN) is 01919 (0A000), every time, until the statement is prepared again.

plan cache prints one line per prepared statement of its session, ascending by name:

[PLANCACHE] <name> plans=<p> hits=<h> invalidations=<i>

Field	Counts
`plans`	the times the statement was planned: 1 at PREPARE or Parse, and 1 more for each new plan
`hits`	the executions that ran a kept plan without planning: each EXECUTE or Execute after the first planning
`invalidations`	the times its plan was dropped by a statement of the table above

An EXECUTE that has to plan again counts in plans, not in hits; one that fails to plan counts in neither. A session with no prepared statement prints nothing. plan cache with anything after it is 00104. Over the PostgreSQL protocol it answers as a debug command (section 95).

More counting rules: a statement whose plan is already dropped counts no second invalidation; an EXECUTE whose new plan ends in 01919 counts in neither plans nor hits; a parked EXECUTE that resumes counts a second hit; a portal counts one execution, at its first Execute, however many Executes it takes. plan cache does not list the unnamed statement of the extended protocol; a statement that reads no table (Parse of BEGIN) is listed with plans=1 and is never invalidated. In a generic plan, a range on a parameter (col < $1) is estimated as a third of the rows, and an equality as one value in col's distinct count.

explain execute <name> (<values>) prints the plan the next EXECUTE with those values would run, planning it first if it was invalidated (which then counts in plans); it runs nothing and is not a hit. Its first line is [PLAN] execute <name> (<values>) as typed, as section 12 says for any statement, and the node lines show $k where the plan holds a parameter.

Codes.

Code	Condition	SQLSTATE
`01919`	a new plan whose result has other columns than the prepared statement had	`0A000`

101. A pooling proxy (from `pool-session`)

The pooling stages add a second program, droid-pool, written by the learner like the server. It speaks the PostgreSQL protocol on both sides: clients connect to it as if it were the server, and it keeps a few connections of its own to the server and lends them to its clients.

The command line.

droid-pool --port <n> --server-port <m> --pool-size <k> [--mode session|transaction] [flags of later stages]

Flag	Meaning
`--port <n>`	the port it listens on, on `127.0.0.1`; `0` asks the system for one
`--server-port <m>`	the droid server it lends connections to, on `127.0.0.1`
`--pool-size <k>`	at most `k` server connections, 1 to 100
`--mode`	`session` (the default) or `transaction` (section 102)

A flag that cannot be understood is 01920: it prints the error line and exits with status 1. When it is ready it prints, on stdout, [POOL] listening on 127.0.0.1:<port>, and the kit starts it after the server (section 92), with --port 0, and connects to that port. It runs until it is stopped; it never reads stdin.

Clients. The pool numbers its clients 1, 2, 3, ... in the order it accepts them, never twice. It answers a client's first messages itself, as section 94 says a server does: N to SSLRequest and GSSENCRequest, then the greeting, with the six ParameterStatus messages, a BackendKeyData whose process id is the client's number, and ReadyForQuery I. It opens no server connection to greet a client.

Server connections. The pool numbers its server connections 1, 2, 3, ... in the order it opens them, never twice. It opens one when a client needs one, none is free and fewer than --pool-size are open, connecting to --server-port with a StartupMessage for user droid and database droid and reading the server's greeting. A server connection is held by one client, or idle.

Session mode. A client is given a server connection when it sends its first message after the greeting, and holds it until it leaves. While it holds one, every message it sends goes to that server connection unchanged, and every message the server sends back goes to the client unchanged. A client that needs a connection when none is free and --pool-size are open waits, in the order clients began waiting, and is given the first connection released.

Releasing. When a client leaves (Terminate, or its socket closes), its server connection is reset and then idle: if the last ReadyForQuery the server sent on it said T or E, the pool sends it the Query ROLLBACK and reads to ReadyForQuery; then the Query DEALLOCATE ALL, then the Query SET TRANSACTION ISOLATION LEVEL REPEATABLE READ, each read to ReadyForQuery, so the next client finds no prepared statement and the default level. They are two Queries because one Query holding both would run them in an implicit transaction (section 96), where SET TRANSACTION is 01805. The client sees none of this. Then the first waiting client, if any, is given the connection.

The log. On stdout, each when it happens:

[POOL] client <c> connected
[POOL] client <c> waits
[POOL] client <c> uses server <s>
[POOL] client <c> released server <s>
[POOL] client <c> closed
[POOL] server <s> connected
[POOL] server <s> closed

waits when a client begins waiting for a server connection; uses when it is given one; released once the connection has been reset; server <s> connected once the pool has read the server's greeting on it.

The admin connection. A client whose StartupMessage names the database pool is the admin connection: it is numbered and greeted like any client, never given a server connection, and not counted below. It answers the Query SHOW POOLS (any case, ; optional) with one row:

Column	Type	Counts
`cl_active`	`int4`	clients holding a server connection
`cl_waiting`	`int4`	clients waiting for one
`sv_active`	`int4`	server connections held by a client
`sv_idle`	`int4`	server connections open and idle

then CommandComplete SHOW and ReadyForQuery I. Any other Query on it is 01921 (0A000).

When the server is gone. If a server connection fails or closes, the pool logs server <s> closed; a client holding it gets an ErrorResponse, severity FATAL, 01922 (08006), and is closed. A client that needs a connection when the pool cannot open one gets the same and is closed. The pool goes on running, and opens connections again once the server is back.

More rules. --port, --server-port and --pool-size are all required. A client is logged closed when it leaves, and its released line follows once the reset is done. In SHOW POOLS, a connection being reset is neither active nor idle, and a client whose connection is being opened is neither active nor waiting. A CancelRequest sent to the pool closes that connection and is not forwarded. When a server connection is lost while clients wait, the pool opens a new one for the first of them. The secret keys the pool gives its clients are its own.

Codes.

Code	Condition	SQLSTATE
`01920`	a `droid-pool` flag that cannot be understood	—
`01921`	a Query on the admin connection other than `SHOW POOLS`	`0A000`
`01922`	the server connection was lost, or cannot be opened	`08006`

102. Transaction pooling (from `pool-transaction`)

--mode transaction. A client holds a server connection only while it needs one:

it is given one when it sends a message and holds none (waiting, as in section 101, when none is free);
it gives it back as soon as the server answers with a ReadyForQuery whose status byte is I: the pool passes that ReadyForQuery on, logs released, and the connection is idle at once, with no reset;
a ReadyForQuery T or E keeps it held: a transaction, even a failed one, stays on its connection until its COMMIT or ROLLBACK brings the status back to I.

So an autocommit statement holds a connection for its own answer only, and many clients can share a few server connections. A client that leaves while it holds one releases it with the reset of section 101.

Pipelined messages. A client may send several Queries or Syncs before the first answer comes back. The pool counts the Queries and Syncs it has forwarded on a connection, and releases it only when the status is I and every one of them has had its ReadyForQuery.
Answers still owed when a client leaves. Before the reset of section 101, in either mode, the pool reads and drops the answers the server still owes for what the client sent, so that none is taken for an answer to the reset.
A client closed for waiting too long is logged client <c> closed; a client that leaves while waiting leaves the queue. Before this stage, --query-wait-timeout-ms is not a flag the pool knows (01920).

--query-wait-timeout-ms <n>, 1 to 3600000: a client that has waited n milliseconds for a server connection gets an ErrorResponse, severity FATAL, 01923 (08P01), and is closed; it leaves the queue. With no flag, a client waits as long as it must. In session mode the flag works the same way.

SHOW POOLS counts as before: in transaction mode cl_active counts the clients that hold a connection at that moment.

Codes.

Code	Condition	SQLSTATE
`01923`	a client waited `--query-wait-timeout-ms` for a server connection	`08P01`

103. What transaction pooling breaks (from `pool-breakage`)

A server connection carries session state: prepared statements (section 98), the isolation level (section 88). In transaction mode a client's next transaction may run on another connection, which does not have that state, while the next client to use the first connection inherits it. Without the flag below, the pool forwards every message unchanged and resets nothing when a transaction ends (section 102), so both happen:

a statement a client prepared, by Parse or by PREPARE, is unknown (26000) on the other connection;
a level a client set with SET TRANSACTION stays on the connection for whoever uses it next.

Session mode is not affected: a client keeps its connection, and the reset of section 101 clears both when it leaves.

--track-prepared (transaction mode) fixes the first for the statements made by Parse:

The pool keeps every named Parse a client sends, by the client's name for it, and gives each such statement a name of its own on the server: p<c>_<name>, c the client's number, so that two clients may both have a p on one connection. It rewrites the statement name in the client's Parse, Bind, Describe S and Close S to that name.
Before it forwards a Bind or a Describe S for a statement the connection has not prepared for that client, it first sends the connection the kept Parse, under the server's name, and reads its ParseComplete itself: the client never sees it. Each time it sends a server a Parse for a named statement, the client's own first Parse and every replay alike, it logs [POOL] client <c> prepares <name> on server <s>.
A Bind or Describe S of a name the client has not parsed, or has closed, gets an ErrorResponse 01911 (26000) from the pool, and the pool skips the client's messages up to Sync as a server would (section 99). If nothing of that batch reached a server, the pool answers the Sync's ReadyForQuery itself, with the status of the client's connection (I when it holds none); otherwise the server's answers it, and the pool forwards it.
Close S of a kept statement: the pool forgets it, answers CloseComplete itself, and forwards nothing. When a client leaves, the pool forgets every statement it kept for it; the copies on server connections stay, unused.
Order. An answer the pool gives itself (the 01911 error, CloseComplete, a ReadyForQuery when it skips) takes the place of the message it answers: it goes to the client after every answer the server still owes for the messages before it, never ahead of them.
What is kept. A Parse is kept from the moment the pool forwards it, so a Bind in the same batch finds it; if the server rejects it with an ErrorResponse, the pool drops it, and the client sees the server's error. A Parse of a name the client already has kept is 01910 (42P05) from the pool, and is not forwarded. Close S of a name the client never kept is answered CloseComplete by the pool, too. A Close S alone before its Sync may still borrow a connection for that Sync. --track-prepared in session mode is accepted and changes nothing.
The unnamed statement and SQL PREPARE are not tracked: the pool does not read SQL. A statement made with PREPARE is still lost on another connection, as is the isolation level.

Name	Value
`server_version`	`16.0 (droid)`
`server_encoding`	`UTF8`
`client_encoding`	`UTF8`
`DateStyle`	`ISO, MDY`
`integer_datetimes`	`on`
`standard_conforming_strings`	`on`

Output contract

1. General rules

2. Command line and REPL

3. Errors

Component ranges

Codes in this part

Codes added in Flexible Storage

Codes added in Memory and Space

Codes added in Transactions and Recovery

Codes added in Querying

Codes added in Indexes and the Optimizer

Codes added in Joins and Relations

Codes added in Sessions and Concurrency

Codes added in the Server track

What changes in c-droid today

4. Lexer — tokenize <sql>

5. Parser — ast <sql>

6. Row format — serialize <insert> and deserialize <hex>

7. Pager

8. Persistence

9. B+Tree

Node pages

Debug commands

Splitting a leaf (from btree-leaf-split)

Splitting an internal node (from btree-internal-split)

10. SQL results

WHERE (from the where-filter stage)

UPDATE and DELETE (from the delete-update stage)

11. Output modes (from the result-set stage) (new)

12. Plans — explain <sql> (from the volcano-executor stage)

13. Execution counter (from the index-scan stage) (new)

14. Flexible Storage: general rules

15. Variable-length rows (from varlen-rows)

16. Slotted pages (from slotted-page)

17. B+Tree leaves on slotted pages (from varlen-btree-leaf)

18. The file header (from file-header)

19. Tables and the catalog (from create-table)

20. Page checksums (from page-checksums)

21. What Flexible Storage changes

22. Memory and Space: general rules

23. Counting I/O (from io-counters)

24. Pinning (from pin-unpin)

25. Clock replacement (from clock-eviction)

26. The free list (from free-list)

27. DROP TABLE and TRUNCATE (from drop-table)

28. Borrow and merge (from btree-merge)

29. Overflow pages (from overflow-pages)

30. VACUUM (from vacuum)

31. What Memory and Space changes

32. Transactions and Recovery: general rules

33. BEGIN and COMMIT (from begin-commit)

34. ROLLBACK (from rollback)

35. The write-ahead log (from wal-write)

36. Crash recovery (from crash-recovery)

37. Checkpoints (from checkpoint)

38. What Transactions and Recovery changes

39. Querying: general rules

40. Expressions (from expressions)

41. NULL (from nulls)

42. IN and BETWEEN (from in-between)

43. Projection (from projection)

44. ORDER BY (from order-by)

45. Sorting on disk (from external-sort)

46. LIMIT and OFFSET (from limit-offset)

47. Aggregates (from aggregates)

48. GROUP BY and HAVING (from group-by-having)

49. DISTINCT (from distinct)

50. ALTER TABLE ADD COLUMN (from alter-table)

51. What Querying changes

52. Indexes and the Optimizer: general rules

53. PRIMARY KEY and the hidden rowid (from primary-key-rowid)

54. Secondary indexes (from create-index)

55. Keeping indexes true (from index-maintenance)

56. Duplicates, ranges and order in an index (from index-duplicates-ranges)

57. UNIQUE (from unique-constraint)

58. Composite keys and index-only scans (from composite-covering)

59. ANALYZE and statistics (from analyze-stats)

60. Estimates, cost and choosing a scan (from cost-model)

61. EXPLAIN ANALYZE (from explain-analyze)

62. Logical plans and three rewrites (from rewrite-rules)

What changes in `c-droid` today

4. Lexer — `tokenize <sql>`

5. Parser — `ast <sql>`

6. Row format — `serialize <insert>` and `deserialize <hex>`

Splitting a leaf (from `btree-leaf-split`)

Splitting an internal node (from `btree-internal-split`)

WHERE (from the `where-filter` stage)

UPDATE and DELETE (from the `delete-update` stage)

11. Output modes (from the `result-set` stage) (new)

12. Plans — `explain <sql>` (from the `volcano-executor` stage)

13. Execution counter (from the `index-scan` stage) (new)

15. Variable-length rows (from `varlen-rows`)

16. Slotted pages (from `slotted-page`)

17. B+Tree leaves on slotted pages (from `varlen-btree-leaf`)

18. The file header (from `file-header`)

19. Tables and the catalog (from `create-table`)

20. Page checksums (from `page-checksums`)

23. Counting I/O (from `io-counters`)

24. Pinning (from `pin-unpin`)

25. Clock replacement (from `clock-eviction`)

26. The free list (from `free-list`)

27. DROP TABLE and TRUNCATE (from `drop-table`)

28. Borrow and merge (from `btree-merge`)

29. Overflow pages (from `overflow-pages`)

30. VACUUM (from `vacuum`)

33. BEGIN and COMMIT (from `begin-commit`)

34. ROLLBACK (from `rollback`)

35. The write-ahead log (from `wal-write`)

36. Crash recovery (from `crash-recovery`)

37. Checkpoints (from `checkpoint`)

40. Expressions (from `expressions`)

41. NULL (from `nulls`)

42. IN and BETWEEN (from `in-between`)

43. Projection (from `projection`)

44. ORDER BY (from `order-by`)

45. Sorting on disk (from `external-sort`)

46. LIMIT and OFFSET (from `limit-offset`)

47. Aggregates (from `aggregates`)

48. GROUP BY and HAVING (from `group-by-having`)

49. DISTINCT (from `distinct`)

50. ALTER TABLE ADD COLUMN (from `alter-table`)

53. PRIMARY KEY and the hidden rowid (from `primary-key-rowid`)

54. Secondary indexes (from `create-index`)

55. Keeping indexes true (from `index-maintenance`)

56. Duplicates, ranges and order in an index (from `index-duplicates-ranges`)

57. UNIQUE (from `unique-constraint`)

58. Composite keys and index-only scans (from `composite-covering`)

59. ANALYZE and statistics (from `analyze-stats`)

60. Estimates, cost and choosing a scan (from `cost-model`)

61. EXPLAIN ANALYZE (from `explain-analyze`)

62. Logical plans and three rewrites (from `rewrite-rules`)

63. Top-N and ordered index scans (from `topn-index-order`)

66. Names, aliases and the binder (from `qualified-names`)

67. Joining tables: the nested loop (from `nested-loop-join`)

68. LEFT JOIN (from `left-outer-join`)

69. Index nested loop join (from `index-nested-loop-join`)

70. Hash join (from `hash-join`)

71. When the build side does not fit (from `hash-join-spill`)

72. Sort-merge join (from `sort-merge-join`)

73. Choosing a join algorithm (from `join-algorithm-choice`)

74. Join order (from `join-order`)

75. Foreign keys (from `foreign-keys`)

76. RESTRICT, CASCADE and DROP TABLE CASCADE (from `fk-delete-actions`)

77. Subqueries that run once (from `subqueries-uncorrelated`)

78. Subqueries that run per row (from `subqueries-correlated`)

81. Sessions (from `sessions`)

82. Row-level undo (from `undo-log`)

83. Undo after a crash (from `undo-recovery`)

84. Locks (from `row-locks`)

85. Waiting for a lock (from `lock-waits`)

86. Deadlocks (from `deadlock`)

87. Read views (from `read-views`)

88. Isolation levels (from `isolation-levels`)

89. Indexes under versions (from `mvcc-indexes`)

90. Purge (from `purge`)

93. A listener and the line protocol (from `server-listen`)

94. The startup handshake (from `pg-startup`)

95. Simple query: results as messages (from `pg-simple-query`)

96. Errors, SQLSTATE and the status byte (from `pg-errors-txn-status`)

97. Waiting, cancelling, disconnecting (from `pg-connection-lifecycle`)