CREATE INDEX: A Sorted Structure You Keep Up to Date

The rowid lookup was fast because rows are already sorted by rowid. But you rarely ask for a row by rowid; you ask for name = 'Alice'. For that you need a second ordering: a structure sorted by name that points back to the rows. That is a secondary index, and CREATE INDEX builds one.

What an index is

An index on a column is a sorted list of entries, one per row: (value, rowid). The entries are ordered by value first and by rowid among equal values.

rows:   rowid 1: Alice     index on name:  (NULL, 4) (Alice, 1) (Alice, 3) (Bob, 2) (Cy, 5)
        rowid 2: Bob
        rowid 3: Alice
        rowid 4: NULL
        rowid 5: Cy

Rules for the order: NULL sorts before every value, integers sort before text (the same order the engine already uses), and equal values are tied by rowid, so all the entries for Alice sit next to each other, in rowid order.

To find every row with name = 'Alice', binary search to the first entry that is >= ('Alice', 0) (no rowid is 0, so that lands on the first Alice), then walk forward while the value is still 'Alice', collecting rowids. Each rowid is then fetched from the table by the binary search from the previous lesson. The work is proportional to the number of matches plus a logarithmic search, not to the size of the table.

Keeping the index true

An index is a redundant copy of information in the table, and a redundant copy that goes stale is worse than none: queries would silently return wrong rows. So every change to the table must be mirrored:

• INSERT: add the new row's entry.
• DELETE: remove the deleted rows' entries.
• UPDATE of an indexed column: remove the old entry, add the new one. (Updating a column the index does not cover changes nothing in it.)
• CREATE INDEX on a table that already has rows: build the entries from the existing rows.

This is the price of an index: every write does extra work, and the index takes space. Indexes are for columns you search often.

Using it

CREATE INDEX name ON table (column) prints OK. Errors are checked in this order: syntax, unknown table, unknown column, an index with that name already exists. Indexing rowid is refused (rowid is always indexed). .indexes [table] lists name ON table(column), sorted by index name, for all tables or one.

The planner from the last lesson now has a second kind of lookup. When the whole WHERE is column = <non-NULL value> and the column has an index, the plan is

SEARCH TABLE users USING INDEX idx_name (name='Alice')

and .examined counts only the rows fetched through the index (the number of matches). If a column has several indexes, the one created first is used. rowid = <integer> still beats everything and name = NULL still scans (nothing is ever equal to NULL). Any other WHERE still scans; a later lesson improves on that.

What you build

The starter already creates indexes, keeps them in step with INSERT, UPDATE and DELETE, and runs queries through them. You write the four operations on the sorted list:

• index_find: binary search for the first entry that is >= (value, rowid).
• index_add: insert an entry at its sorted place.
• index_remove: delete one entry.
• index_lookup: all rowids for a given value.

Common mistakes

• Appending the entry and sorting later, or forgetting to keep it sorted, so binary search misses rows.
• Comparing values with plain < on mixed data. Use the engine's ordering, with NULL smallest.
• Stopping the walk too early or too late in index_lookup, e.g. missing the second Alice, or running on into Bob.
• Removing the wrong entry when several rows share a value: the rowid is part of the key.

Your exercise

You implement index_find, index_add, index_remove and index_lookup. The mistake to avoid: leaving stale entries behind after an UPDATE or DELETE.