CREATE INDEX and Equality Lookup

Why this stage exists

A table's B+Tree answers one question fast: which row has this key? Every other question, where name = 'n250' included, reads every leaf. On a table of fifty leaves that is fifty page reads to find one row.

An index answers the same kind of question for another column. It is a second B+Tree, kept beside the table, ordered by that column. Find the value in it, and it tells you where the row is.

The interesting part is what "where the row is" means.

What an entry holds

The obvious answer is a page and slot: "the row is in page 37, slot 4". It is also wrong, for an engine like this one. Rows live inside the table's B+Tree, and they move: a leaf split sends half of them to a new page, a merge sends them back, VACUUM renumbers pages, a long row spills to overflow pages. An index full of page numbers would be wrong after the next insert.

What does not move is the row's key. So an index entry is the indexed value followed by the row's table key, and nothing else:

Putting the table key inside the entry's key, rather than after it as a payload, solves duplicates before they appear. Two rows with the same name make two entries that differ in their table key, so no two entries are ever equal, an index never needs a list of rows per value, and deleting one row later removes exactly one entry.

Entries compare left to right: by value first (INT as unsigned numbers, VARCHAR as bytes with a prefix before the longer string, NULL before everything), then by table key.

Two descents

A lookup through an index goes down two trees:

That second descent is the price of an index that stores keys, and it is paid once per matching row. For one match it is nothing. For half the table it is far more than a full scan, and the optimizer stages of this part are about knowing which case you are in. For now the rule is simple: an equality on an indexed column uses the index.

The [EXEC] line shows both descents' work. rows_examined counts the rows the scan handed up, as always: 1, not 500. A new field, index_lookups, counts the table lookups made through entries. They are equal in this stage; a later stage makes the second one zero.

Indexes are catalog objects

An index is recorded in the catalog, next to its table: its name, table, column and root page. That one decision makes the rest of the engine handle it for free:

• Reopening finds it in the catalog.
• Transactions: CREATE INDEX writes pages and a catalog record, so a ROLLBACK takes the whole index back, and a crash after COMMIT keeps it.
• DROP TABLE looks up the table's indexes and frees their trees too; DROP INDEX frees one.
• VACUUM already updates every pointer to a page it moves; the index's root in the catalog is one more.

Index names are global, like table names in their own name space: create index idx on a (x) and create index idx on b (y) cannot both exist.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 54.

index and on are keywords. Only = on an indexed column uses the index in this stage: name > 'b' is still a Filter over a SeqScan.

What you should see when done

$droid --db shop.db
Welcome to droid!
>create table s (id int, name varchar(20), n int);
Create table statement executed successfully
>insert into s (id, name, n) values (1, 'ada', 3);
Insert statement executed successfully (1 rows)
>insert into s (id, name, n) values (2, 'bob', 5);
Insert statement executed successfully (1 rows)
>insert into s (id, name, n) values (3, 'cy', 3);
Insert statement executed successfully (1 rows)
>select id from s where name = 'cy';
id
3
(1 rows)
[EXEC] rows_examined=3
>create index idx on s (name);
Create index statement executed successfully
>select id from s where name = 'cy';
id
3
(1 rows)
[EXEC] rows_examined=1 index_lookups=1
>explain select id from s where name = 'cy';
[PLAN] select id from s where name = 'cy'
[PLAN]   └── Project (cols=[id])
[PLAN]       └── IndexScan (table=s, index=idx, key='cy')
>index check idx
[INDEX] Check idx: OK entries=3
>.exit
exiting.. good bye!

Common bugs in this stage

• Storing a page and slot in the entry. It works until the first split moves the row. Store the table key.
• Putting the table key in a payload instead of the entry's key. Then two rows with the same value make two equal keys, and the tree's duplicate check rejects the second. The next stage's tests will find it, but so will any table where a value repeats.
• Comparing VARCHAR values as C strings or with a locale. Compare bytes, the shorter prefix first, so the order is the same in every language.
• Counting the stopping entry. The first entry with a different value ends the scan; it is not a row.
• Forgetting the catalog. An index that lives only in memory vanishes on reopen and survives a ROLLBACK it should not.
• DROP TABLE leaving the index behind. Its pages leak, and its name stays taken.

Language notes

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

• C: your B+Tree code compares keys somewhere; make that comparison a function pointer chosen by the node type, so the same split and search code serves tables and indexes.
• C++: template the tree on a key type with a comparator, or pass a comparator object; avoid copying the tree code.
• Rust: a trait KeyOrder with one implementation for table keys and one for index entries keeps one tree implementation; Ordering::then composes value and key.
• Zig: pass a comparison function as a comptime parameter to the tree, or store one in the tree handle.