droidPart 6 · Indexes and the Optimizer

Indexes and the Optimizer · Stage 1

PRIMARY KEY Syntax and the Hidden Rowid

Accept PRIMARY KEY on any INT column and key the table's B+Tree by it; keep an INT first column as the key when nothing is marked; and give every other table a hidden, ever-increasing rowid that the catalog remembers.

Not run yet · 11 tests

Why this stage exists

Since the B+Tree stages, a table's rows have lived in one tree, ordered by the first column, which had to be an INT. That rule was a shortcut: the engine needed a key, and the first column was the easy one to find. It is also wrong in two ways that the next stages would trip over.

First, the key is a property of the data, not of the column order. create table orders (customer varchar(20), id int primary key) is a perfectly good table whose key is its second column. Second, many tables have no natural key at all: a log of events, a list of names. Forcing the user to invent an INT column for them is what this stage removes.

The indexes of this part make the choice matter more. A secondary index stores, for each row, the indexed value and the row's key, and finds the row by looking that key up in the table's tree. So the key has to be settled, stable and known for every table before the first index exists. That is this stage.

Three ways a table gets its key

Every table has exactly one key, decided by CREATE TABLE and never changed:

A column marked PRIMARY KEY, in any position. It must be INT, there is only one, and it takes no DEFAULT.
No column marked, and the first column is INT. The first column is the key, exactly as before. Every table created in earlier stages, and every test of those stages, is in this case, so none of them changes.
Anything else: a hidden rowid, an INT the engine assigns, 1 for the first row and one more for each row after it.

Whatever the case, the key does the same jobs it always did: the tree is ordered by it, an INSERT must have one that the tree does not hold yet, an UPDATE cannot change it, and a WHERE bound on it is an IndexScan. Only where it comes from differs.

t (name varchar(20), id int primary key): ids 3, 1, 2 inserted

header

cells = 3

cell 0

key = 1

cell 1

key = 2

cell 2

key = 3

free space

h (name varchar(20), city varchar(10)): ada, bob, cy inserted

header

cells = 3

cell 0

key = 1

new

cell 1

key = 2

new

cell 2

key = 3

new

free space

Each cell is 64 bytes. A cell that moves one position moves by 64 bytes.

Both leaves look the same: cells in key order. In t the key is copied from the id column of each row. In h it was handed out by the table, and no column of the row holds it.

The rowid is a key, not a column

The rowid lives where every key lives: in the cell, in front of the row. The row itself holds only the declared columns. That is why select * does not show it, and why the catalog's column list does not mention it.

It can still be read. On a rowid table the name rowid means the row's key, wherever a column could be read: select rowid, name from h, where rowid = 2, order by rowid. It cannot be written: an INSERT or UPDATE that names it is 00402, because it is not a column. On a table keyed by a column, rowid is not a name at all.

A counter that never repeats

The obvious way to pick the next rowid is to look at the largest key in the tree and add one. It is also wrong for this stage: delete the last row, insert a new one, and the new row gets the deleted row's rowid. Anything outside the table that remembered the old rowid now points at a different row. droid promises that a rowid is never given twice.

So the next rowid is stored, as a fifth column of the table's catalog row, next_rowid. Every INSERT into a rowid table reads it, uses it, and writes it back one higher. That puts the counter on a page like any other, and everything you built for pages already handles it:

It survives reopening, because the catalog is in the file.
It survives a crash, because the catalog page is logged and recovered like the table's pages.
It goes back on ROLLBACK, because the catalog page is one of the transaction's pages. The rows that were rolled back never existed, so their rowids are free again. That is the one way a rowid is reused, and it is safe: nothing outside the transaction ever saw them.

shell

$droid --db log.db
Welcome to droid!
>create table h (name varchar(20), city varchar(10));
Create table statement executed successfully
>insert into h (name, city) values ('ada', 'x');
Insert statement executed successfully (1 rows)
>insert into h (name, city) values ('bob', 'x');
Insert statement executed successfully (1 rows)
>delete from h where rowid = 2;
Delete statement executed successfully (1 rows)
[EXEC] rows_examined=1
>insert into h (name, city) values ('cy', 'x');
Insert statement executed successfully (1 rows)
>select rowid, name from h;
rowid | name
1 | ada
3 | cy
(2 rows)
[EXEC] rows_examined=2

The algorithm in words

Decide the key when the table is created

The choice is made once, from the column list, and never changes.

1.Read each column's options after its type: NOT NULL, DEFAULT and PRIMARY KEY may come in any order. A second PRIMARY KEY in the same column is 00302.
2.Before any check, find the key in the column list: the first column marked PRIMARY KEY; with none marked, the first column if it is INT; otherwise the table gets a hidden rowid.
3.Run the checks of a CREATE TABLE column by column, in the order written. For a column marked PRIMARY KEY, add two: it is INT (01103), and no earlier column was marked (01601). Then, for the key column, a DEFAULT is 01104, even DEFAULT NULL.
4.A first column that is not INT is no longer an error. ADD COLUMN with PRIMARY KEY is 01601: the table already has a key.
5.Record the choice in the catalog: the marked column carries PRIMARY KEY in the column list, and a rowid table's catalog row carries its next rowid, starting at 1.

Insert into a table

Every place that took the first column as the key now takes the key column.

1.Keyed by a column: the INSERT must give it (00406), not as NULL (01503), and the tree must not have it yet (00701).
2.Keyed by a rowid: read next_rowid from the catalog row, use it as the row's key, and write next_rowid plus one back, in the same statement.
3.Encode the row from its declared columns only. The rowid is the cell's key, never one of the row's values.

Read the rowid by name

rowid is resolved like a column name, but only for reading.

1.On a rowid table, a name that is no column and is rowid means the row's key, an INT, with header rowid.
2.* expands to the declared columns only.
3.An INSERT column list or an UPDATE assignment that names rowid is 00402, and so is any rowid on a table keyed by a column.
4.A bound on rowid, or on a PRIMARY KEY column in any position, is a key bound: the planner already turns it into an IndexScan.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, sections 52 and 53.

Input	Output
`tokenize id int primary key`	`[IDENTIFIER - id]`, `[IDENTIFIER - int]`, `[KEYWORD_PRIMARY - primary]`, `[KEYWORD_KEY - key]`
`ast create table t (name varchar(20), id int primary key not null);`	`Columns: [name varchar(20), id int NOT NULL PRIMARY KEY]`
`catalog list`	`[CATALOG] t root=2 (name VARCHAR(20), id INT PRIMARY KEY, n INT)`; a rowid table prints its columns with no marker
`select * from h;` on a rowid table	the declared columns only
`select rowid, name from h;`	`rowid \| name`, then `1 \| ada`, `2 \| bob`, ...
`explain select * from t where id = 2;`	`[PLAN] └── IndexScan (table=t, key=2)`, for a key column in any position
`explain select name from h where rowid = 2;`	`Project (cols=[name])` over `IndexScan (table=h, key=2)`
a PRIMARY KEY on a VARCHAR column	`[ERROR:01103] <message>`
two columns marked PRIMARY KEY; ADD COLUMN with PRIMARY KEY	`[ERROR:01601] <message>`
a DEFAULT on the key column	`[ERROR:01104] <message>`
INSERT without the key column; NULL in it; a repeated key; UPDATE of it	`00406`, `01503`, `00701`, `00801`, as for the first column before
`rowid` in an INSERT column list or an UPDATE assignment, or on a table keyed by a column	`[ERROR:00402] <message>`

primary and key are keywords. rowid is not: it is an identifier that a rowid table resolves.

What you should see when done

shell

$droid --db shop.db
Welcome to droid!
>create table orders (customer varchar(20), id int primary key);
Create table statement executed successfully
>insert into orders (customer, id) values ('cy', 30);
Insert statement executed successfully (1 rows)
>insert into orders (customer, id) values ('ada', 10);
Insert statement executed successfully (1 rows)
>insert into orders (customer, id) values ('bob', 10);
[ERROR:00701] key 10 already exists
>select * from orders;
customer | id
ada | 10
cy | 30
(2 rows)
[EXEC] rows_examined=2
>create table notes (body varchar(40));
Create table statement executed successfully
>insert into notes (body) values ('first');
Insert statement executed successfully (1 rows)
>insert into notes (body) values ('second');
Insert statement executed successfully (1 rows)
>select rowid, body from notes;
rowid | body
1 | first
2 | second
(2 rows)
[EXEC] rows_examined=2
>catalog list
[CATALOG] Tables: 2
[CATALOG]   orders root=2 (customer VARCHAR(20), id INT PRIMARY KEY)
[CATALOG]   notes root=3 (body VARCHAR(40))
>.exit
exiting.. good bye!

The messages are yours to word; the tests check only the codes.

Common bugs in this stage

Still keying on the first column. Rows come back in name order, and a repeated id is accepted. Every place that read "column 0" as the key (INSERT, UPDATE, the planner's key bounds, btree find) has to ask the table which column is its key.
Breaking old tables. A table with an INT first column and no PRIMARY KEY must stay keyed by that column, or every earlier suite fails.
The rowid stored in the row. Then select * shows it, and every row is four bytes larger than its columns. It is the cell's key, not a value.
The next rowid computed from the tree. It passes until a test deletes the last row and inserts again. Store the counter.
The counter kept in memory. It passes until the program restarts, or a ROLLBACK leaves the counter ahead of the rows. Write it to the catalog row, inside the statement.
Taking a rowid for a statement that fails. Check the INSERT completely before you touch the counter.
Resetting the counter on TRUNCATE. TRUNCATE empties the table, but rowids already given stay given: the next row does not get 1.

Language notes

The page above is the same for every language. These are the only language-specific hints.

C: give your table descriptor a key-column index with a sentinel for "rowid", and route every key access through one function that takes a row and returns its key.
C++: a std::optional<std::size_t> for the key column says "rowid" by being empty.
Rust: an enum Key { Column(usize), RowId } makes the compiler find every place that still assumes column 0.
Zig: a tagged union for the key choice gets the same help from switch exhaustiveness.

Loading starter code…

No run yet

11 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.