Composite Keys and Index-Only Scans

Why this stage exists

Two ideas share this stage because they are two sides of one fact: an index entry can hold more than one value.

The first is the composite key. Queries often pin more than one column: where city = 'x' and age = 30. An index on city finds every row in the city and filters the ages; an index on (city, age) goes straight to the rows that match both.

The second is the covering index. Every lookup so far paid for two descents: one in the index, one in the table to fetch the row. If the entry already holds every column the query needs, the second descent has nothing to fetch.

A phone book sorted by last name, then first name

Entries of an index on (city, age) sort by city first, and by age only among rows with the same city:

That ordering decides which WHERE clauses the index can serve, exactly as a phone book sorted by last name, then first name, can find "Smith" or "Smith, Anna" but not every "Anna":

The rule: an index helps through a prefix of its columns, = on as many leading columns as the WHERE pins, then at most one range on the next. Everything after a range, and every column the prefix does not reach, goes into the Filter.

The second descent, and when it disappears

Every entry ends with the row's table key. So an index on (city, age) actually holds city, age and id, and a query that reads only those has nothing to fetch from the table:

The [EXEC] line shows it: rows_examined=10 index_lookups=0. And the pager shows it louder: on a table of wide rows, the covered query reads a handful of index pages, while the same WHERE with one more column reads the table page by page.

count(*) is the favourite trick: it reads no column, so any index whose columns cover the WHERE answers it without the table.

Covering decides how to read the chosen index, never which index to choose. That keeps the plan predictable now; weighing a covering index against a better-matching one is a cost question for the cost-model stage.

Output contract for this stage

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

A one-column index prints as before: key='x', range: name > 'b'.

What you should see when done

$droid --db people.db
Welcome to droid!
>create table t (id int, city varchar(10), age int, name varchar(20));
Create table statement executed successfully
>create index ca on t (city, age);
Create index statement executed successfully
>insert into t (id, city, age, name) values (1, 'x', 30, 'ada');
Insert statement executed successfully (1 rows)
>insert into t (id, city, age, name) values (2, 'x', 25, 'bob');
Insert statement executed successfully (1 rows)
>insert into t (id, city, age, name) values (3, 'y', 30, 'cy');
Insert statement executed successfully (1 rows)
>select id, age from t where city = 'x';
id | age
2 | 25
1 | 30
(2 rows)
[EXEC] rows_examined=2 index_lookups=0
>select name from t where city = 'x' and age = 30;
name
ada
(1 rows)
[EXEC] rows_examined=1 index_lookups=1
>.exit
exiting.. good bye!

Common bugs in this stage

• Using the index for its second column alone. The entries are not in that order; the rows come back wrong or missing.
• A range on the first column followed by = on the second used as one seek. After a range, the second column is no longer in order; it belongs in the Filter.
• Printing the prefix in WHERE order. key=(...) follows the index's column order, whatever order the WHERE was written in.
• Forgetting the table key when deciding coverage. select id, city is covered by an index on city.
• An index-only UPDATE. It must read the row to write it.
• A unique composite index refusing ('a', NULL) twice. A NULL in any column means no conflict.

Language notes

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

• C: compare composite entries with a loop over the index's column types, decoding one value at a time; stop at the first difference.
• C++: a std::vector<Value> per entry with a lexicographic compare reads clearly; encode it once for the page.
• Rust: a Vec<Value> with Ord implemented per value compares lexicographically for free.
• Zig: keep the column types in the index handle and walk them in the compare function.