Add an IndexScan node that answers WHERE id = k, id > k and id < k by searching the tree instead of reading every row, have the planner choose it for any WHERE on id, and print how many rows each SELECT examined.
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>.
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:
| Condition | Starts at | Stops |
|---|---|---|
id = k | the position of k, found by searching the tree | after one row, or at once if k is not there |
id > k | the first key greater than k, found by searching the tree | at the end of the table |
id < k | the first row of the table | at the first key that is not less than k |
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.
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.
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.
> and <.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.
The planner now has two ways to read the table.
Every IndexScan finds a starting point in the tree, then reads forward along the leaves until its condition stops holding.
Every scan counts the rows it hands up, and SELECT prints the count at the end.
These are the exact lines the tests check. The full definition is on the output contract page, sections 12 and 13.
| Input | Output |
|---|---|
explain select ... where id = <k>; | [PLAN] <statement>, then [PLAN] └── IndexScan (table=users, key=<k>) |
explain select ... where id > <k>; or id < <k> | [PLAN] <statement>, then [PLAN] └── IndexScan (table=users, range: id > <k>) or range: id < <k> |
explain select ... where name ... or email ... | a Filter over a SeqScan, as before |
| any SELECT that runs | its result, then [EXEC] rows_examined=<n> |
an INSERT, explain, a statement that fails | no [EXEC] line |
The file already holds rows 1 to 24, inserted in order in an earlier session.
$droid --db users.dbWelcome 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 | email20 | 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;id15161718192021222324(10 rows)[EXEC] rows_examined=10>select id from users where name = 'user20';id20(1 rows)[EXEC] rows_examined=24>select id from users where id < 3;id12(2 rows)[EXEC] rows_examined=2>.exitexiting.. 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.
id > 14 returns 15 and 16. Follow the leaf chain.id < 3 examines 3 instead of 2. Look at the key to decide, and count only the rows handed up.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.btree find: a key equal to a separator is on its right. Otherwise id = 13 searches the wrong leaf and finds nothing.explain, which shows one node.explain.The page above is the same for every language. These are the only language-specific hints.
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.next is a few lines, because the cursor already knows how to cross leaves.SeqScan, with the same three virtual methods. The planner returns one or the other through the same std::unique_ptr to the base.IndexScan struct implementing the same trait as SeqScan, holding a cursor. If your cursor borrows the pager, the scan needs the same lifetime.switch in next gains a case and nothing else changes.