Table Scan vs Index Scan — Cost Estimation

The query planner decides how to execute each query. Its most fundamental choice: should we scan the entire table, or use an index?

Two Strategies

Table Scan (Sequential Scan):

• Read every row in the table
• Check WHERE clause against each row
• O(n) — always reads everything
• Best when: most rows match, table is small, or no useful index exists

Index Scan:

• Look up matching rows via a B-tree index
• Read only the matching rows from the table
• O(log n + k) where k is the number of matching rows
• Best when: few rows match and a relevant index exists

Cost Model

The planner assigns a numeric cost to each strategy and picks the cheapest:

Table Scan cost = num_pages * seq_page_cost + num_rows * cpu_tuple_cost

Index Scan cost = index_depth * random_page_cost
               + matching_rows * (random_page_cost + cpu_tuple_cost)

Key insight: sequential page reads are cheaper than random page reads (about 4x cheaper on spinning disks, less difference on SSDs).

When Index Scan Loses

Index scan isn't always better! If the WHERE matches many rows:

Table: 1,000,000 rows, 10,000 pages
WHERE status = 'active'  (matches 900,000 rows = 90%)

Table Scan: read 10,000 pages sequentially
Index Scan: 900,000 random page reads (each matching row might be on a different page)

Table scan wins by a huge margin!

The rule of thumb: index scan is faster when selectivity is below ~15-30%.

The .explain Command

Our database shows the chosen plan:

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

.explain SELECT * FROM users WHERE name = 'Alice'
→ SCAN TABLE users    (no index on name)

SEARCH = index scan (targeted lookup) SCAN = full table scan (reads everything)

Index-Only Scans

If all requested columns are in the index, the engine can skip the table entirely:

CREATE INDEX idx_age ON users(age)
SELECT age FROM users WHERE age > 25
→ Index contains age values, no need to read the table

PostgreSQL calls this an "Index Only Scan." It's the fastest possible read path.

How SQLite's Query Planner Works

SQLite's planner (where.c) uses a "next generation query planner" (NGQP) that evaluates multiple possible index combinations. It estimates selectivity using the sqlite_stat1 table (populated by ANALYZE) and picks the lowest-cost plan.

Your Task

Implement .explain that shows SCAN TABLE when no index exists and SEARCH TABLE USING INDEX when an indexed column is used in WHERE.