PRIMARY KEY Syntax and the Hidden Rowid

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:

1. A column marked PRIMARY KEY, in any position. It must be INT, there is only one, and it takes no DEFAULT.
2. 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.
3. 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.

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.

$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

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.

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

What you should see when done

$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.