Choosing Between Scan Strategies

Table Scan vs Index Scan

Every query has to decide, row by row, "does this qualify?" — but how the engine finds candidate rows in the first place is the query planner's first and most important decision. This lesson introduces the two fundamental access paths: the table scan and the index scan.

Table scan — the default

A table scan (a.k.a. sequential scan / full scan) reads every row in the table, in storage order, and tests each one against the WHERE clause:

for row in table:
    if matches(row, predicate):
        emit(row)

Cost: O(n) where n is the row count — you touch every row no matter what you're looking for. This is the only option when there's no index on the filtered column, or when there's no filter at all (SELECT * FROM users).

Index scan — using the B-tree

If you've already built a B-tree for the table's primary key (or, after this lesson's sibling, a secondary index), an equality lookup can walk the tree directly instead of scanning every row:

node = root
while node is not leaf:
    node = node.child_for(key)
# node now holds (or is close to) the matching entry

Cost: O(log n) — each level of the tree eliminates a large fraction of the remaining rows, the same way a binary search halves a sorted array. For a million-row table that's the difference between reading a million rows and reading roughly 20.

Choosing between them: .explain

Your planner should look at the WHERE clause and decide:

• Is the referenced column indexed? → index scan, seeking directly to matching rows. Every table has the implicit rowid index for free; any other column becomes indexed only after a CREATE INDEX <name> ON <table> (<col>), and the plan then names the index it used.
• Otherwise (or no WHERE at all)? → table scan, reading everything.

.explain SELECT * FROM users WHERE rowid = 5
→ SEARCH TABLE users USING INDEX (rowid=5)

.explain SELECT * FROM users WHERE name = 'Alice'
→ SCAN TABLE users

.explain doesn't execute the query — it's a diagnostic that reveals the plan the engine would use, which is exactly how EXPLAIN works in Postgres/MySQL/SQLite. Implementing it forces you to separate "decide how to access the data" (planning) from "actually read it" (execution) — a separation every real query engine makes.

Why this decision matters

This is the single biggest lever for query performance. An unindexed equality lookup on a huge table can be thousands of times slower than the same lookup once an index exists — which is exactly the motivation for the next lesson, where you'll let users declare secondary indices on arbitrary columns so more queries qualify for the fast path.

When the scan wins anyway

"Indexed → index scan" is the rule you are implementing, but it is not the rule a mature planner uses, and the reason matters more than the rule. An index scan does two things per matching row: it walks the B-tree, then it follows the rowid back to that row's page — a random read. A table scan reads pages in storage order, sequentially, and sequential reads are far cheaper per page than random ones. So the index only pays off when it eliminates most of the work.

That gives a crossover point. A predicate matching a handful of rows out of a million is exactly what an index is for. A predicate matching a large fraction of the table — the usual rule of thumb puts the crossover somewhere above roughly a third — makes the index the slower choice: you touch nearly every page anyway, in random order, with the tree traversal added on top. The fraction of rows a predicate keeps is its selectivity, and real planners maintain table statistics precisely so they can estimate it before choosing. You will build that estimate explicitly in the query-planner lesson later in this chapter.

Edge cases to watch

• A WHERE clause on a column that isn't your primary key and has no secondary index yet must fall back to a table scan — don't assume every column is indexed.
• Distinguish "the column is indexed" from "the predicate is an equality test the index can use" — a range predicate (age > 20) can't be serviced by a plain equality index lookup the same way (more on this in the multi-column lesson).
• Keep the plan output format exact — .explain is typically matched against precise expected strings in tests, so mirror the format shown above exactly.