Index Scan on the Primary Key

Why this stage exists

The tree has been sorted by id since btree-search, and btree find has used that since, reading one path from the root to a leaf. SELECT never did. where id = 20 has been a Filter over a SeqScan: read every row, keep one. On 24 rows nobody notices. On a million rows it is the difference between reading three pages and reading all of them.

This stage gives the planner a second way to read the table, the IndexScan, and makes it the plan for every WHERE on id. The rows printed do not change, not one. What changes is how many rows are read to find them, and a new line makes that visible: [EXEC] rows_examined=<n>.

What changes: the scan starts where the answer starts

The tree is sorted by id, and its leaves are chained in that order. So the rows with id > 14 are all together: they start at one position in one leaf and run to the end of the chain. An IndexScan goes down the tree to that position, the way btree find does, then reads along the leaves:

The three conditions differ only in where they start and when they stop:

id < k starts at the beginning, like a SeqScan, but it stops as soon as the keys pass k instead of reading on to the end. Because the rows come in key order, nothing after that key can match.

The IndexScan hands up only rows that satisfy its condition, so there is no Filter above it. For name and email nothing changes: the tree is not sorted by them, and a Filter over a SeqScan is still the only way to answer.

The plan

explain shows the new node. For a key it names the key; for a range, the condition:

>explain select * from users where id = 20;
[PLAN] select * from users where id = 20
[PLAN]   └── IndexScan (table=users, key=20)
>explain select id from users where id > 14;
[PLAN] select id from users where id > 14
[PLAN]   └── IndexScan (table=users, range: id > 14)

The volcano model makes this a small change. An IndexScan has the same open, next and close as any other node. The executor, the Filter and both printers do not change at all. Only the planner learns to choose it.

Counting the work

After every SELECT's result, the program now prints how many rows the scan at the bottom of the plan read and handed up: [EXEC] rows_examined=<n>. In table mode it follows the (n rows) footer; in CSV mode, the last row, or the header line when no row matched.

• A SeqScan hands up every row, so it examines the whole table. A Filter above it may keep one row, and 24 were still examined.
• An IndexScan examines only the rows it hands up: 1 for a key that is there, 0 for one that is not, and the rows of the range for > and <.
• To know that id < 3 is over, the scan must look at key 3. It does not hand that row up, so it does not count it: id < 3 over rows 1 to 24 examines 2.

The counter is what the tests use to tell the two plans apart. The rows printed are the same either way; only the count shows which plan ran.

Output contract for this stage

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

What you should see when done

The file already holds rows 1 to 24, inserted in order in an earlier session.

$droid --db users.db
Welcome to droid!
>explain select * from users where id = 20;
[PLAN] select * from users where id = 20
[PLAN]   └── IndexScan (table=users, key=20)
>select * from users where id = 20;
id | name | email
20 | user20 | user20@example.com
(1 rows)
[EXEC] rows_examined=1
>explain select id from users where id > 14;
[PLAN] select id from users where id > 14
[PLAN]   └── IndexScan (table=users, range: id > 14)
>select id from users where id > 14;
id
15
16
17
18
19
20
21
22
23
24
(10 rows)
[EXEC] rows_examined=10
>select id from users where name = 'user20';
id
20
(1 rows)
[EXEC] rows_examined=24
>select id from users where id < 3;
id
1
2
(2 rows)
[EXEC] rows_examined=2
>.exit
exiting.. good bye!

Row 20 found by its id examined 1 row. Found by its name, 24: same row, same output, and the counter is the only line that shows the difference.

Common bugs in this stage

• Still filtering. The plan says IndexScan, but the node reads every row and checks each one. The rows are right and the counter says 24. An IndexScan starts at its first row and stops after its last.
• Stopping one leaf early. A range reads to the end of the leaf where it started and stops, instead of following the link. id > 14 returns 15 and 16. Follow the leaf chain.
• Counting the row that ends the range. id < 3 examines 3 instead of 2. Look at the key to decide, and count only the rows handed up.
• Starting id > k at k. The search for k lands on k when it is there, and > must not include it. Start at the first key greater than k.
• Equal keys going left. The descent must use the same rule as btree find: a key equal to a separator is on its right. Otherwise id = 13 searches the wrong leaf and finds nothing.
• A Filter left above the IndexScan. It does no harm to the rows and fails explain, which shows one node.
• An IndexScan for name. The tree is sorted by id only. A WHERE on name through the tree finds some rows and misses others.
• The counter in the wrong place. Before the footer, missing in CSV mode, or printed after an error or after explain.

Language notes

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

• All languages: the search that finds the position of a key, or of the first key greater than it, is the one btree find and INSERT already use. An IndexScan is that search plus the cursor you wrote for SELECT, started at the position the search returns.
• C: the IndexScan node's state is a cursor, the operator, the key, and a flag for "done". Its next is a few lines, because the cursor already knows how to cross leaves.
• C++: a second subclass of the node base class, beside SeqScan, with the same three virtual methods. The planner returns one or the other through the same std::unique_ptr to the base.
• Rust: an IndexScan struct implementing the same trait as SeqScan, holding a cursor. If your cursor borrows the pager, the scan needs the same lifetime.
• Zig: one more arm in the tagged union of nodes, or one more struct behind the same function table; the switch in next gains a case and nothing else changes.