Table Scan vs Index Lookup

So far every query reads the whole table. That is a table scan: look at row 1, row 2, row 3, and so on, keep the ones that match. It always works, and it gets slower in step with the table: ten times the rows, ten times the work. A lookup goes straight to the row it wants. Telling those two apart, and choosing between them for each query, is the first job of a query planner.

The one index every table already has

Every row has a hidden integer rowid, handed out in increasing order and never reused (you built that in the storage lessons). Because rows are appended in rowid order and a delete only leaves a gap, the rows are always sorted by rowid. Sorted data means you can binary search it: halve the range, compare the middle, repeat. Finding one row among a million takes about 20 comparisons instead of a million.

rows (rowid):  1  2  4  5  8  9  12  15      (3, 6, 7, 10, 11... were deleted)
find 9:        middle=5 -> too small -> look right -> middle=9 found
find 6:        ... the range closes without a match -> no such row

Because the search ends either with the row or with an empty range, a lookup of a rowid that does not exist is just as cheap, and it returns no rows.

The plan, and how to read it

.explain SELECT ... prints the plan instead of running the query:

SEARCH TABLE users USING INDEX (rowid=2)     a direct lookup of rowid 2
SCAN TABLE users                              read every row

The planner may use the lookup only when it can prove that the lookup finds every row the query wants. In this lesson that means the entire WHERE is a single test rowid = <integer> (or <integer> = rowid). Everything else scans, even if part of the query could have used the shortcut; a later lesson teaches the planner to split a WHERE into pieces.

The cases that fall back to a scan, and why:

• rowid = 'x' (text) and rowid = NULL: no integer to look up. (= NULL is never true anyway.)
• rowid > 1, rowid = a (another column), 1 = 1: not an equality against a constant.
• rowid = 2 AND b = 'y', rowid = 2 OR rowid = 3, NOT rowid = 2: not a single test (parentheses around one test do not matter).
• A table that declares its own column called rowid: then rowid names that column, not the hidden one, and it has no index.

Seeing the difference: examined

.examined reports how many rows the last SELECT had to look at. A scan examines every row of the table (3 for a three-row table, whatever the answer was). A lookup examines at most one: 1 when the row exists and 0 when it does not. This counter is how you can tell, from the outside, that the planner did what .explain promised.

What you build

The starter already parses and runs SELECT, prints plans and keeps the counter. It asks the planner for an access path and asks that path for its candidate rows; the rest of the WHERE is still evaluated on those candidates, so the answer is right whichever path is chosen. You write:

• find_row: the binary search over the rows by rowid.
• choose_access: decide between the lookup and the scan.

Common mistakes

• A linear search that "works". The output is correct but .examined and the running time show it is a scan.
• Using the shortcut for a WHERE that has more in it. rowid = 2 OR rowid = 3 would then lose a row.
• Forgetting the declared-column case, or letting rowid = NULL or text through.
• Reusing rowids. After a delete the table has gaps; a rowid that was deleted must find nothing.

Your exercise

You implement find_row and choose_access. The mistake to avoid: searching with a loop over all rows.