Indexes and query plans
See how an index changes a table scan into a search by reading the query plan.
On this page
SELECT queries and basic tree ideas.
- See how an index changes a table scan into a search by reading the query plan.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
Without help, a query that filters on a column must examine every row in the table: a full scan, with O(n) cost. An index is a separate sorted structure, usually a B-tree, that maps column values to rows. A lookup in a B-tree touches O(log n) pages, so the same filter becomes a search.
Indexes are not free. Each index uses storage and must be updated on every INSERT, UPDATE, or DELETE that touches its columns, so a table with many indexes writes more slowly. They help most when a query is selective, returning a small fraction of the rows. A composite index on (a, b) can serve queries on a or on a and b, but generally not on b alone, because it is sorted by a first.
The database's query planner chooses how to run a query, and EXPLAIN QUERY PLAN (EXPLAIN in other databases) shows its choice. The exact wording differs between database versions, so the program checks for the words SCAN and SEARCH and for the index name rather than printing the plan text.
Code example
import sqlite3
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE person (id INTEGER PRIMARY KEY, email TEXT, age INTEGER)")
db.executemany(
"INSERT INTO person (email, age) VALUES (?, ?)",
[(f"user{i}@example.com", 20 + i % 40) for i in range(1000)],
)
query = "SELECT id FROM person WHERE email = 'user500@example.com'"
def plan(sql):
return " ".join(row[3] for row in db.execute("EXPLAIN QUERY PLAN " + sql))
before = plan(query)
db.execute("CREATE INDEX idx_person_email ON person(email)")
after = plan(query)
print("SCAN" in before, "SEARCH" in after, "idx_person_email" in after)
print(db.execute(query).fetchall())True True True [(501,)]
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
import sqlite3 db = sqlite3.connect(":memory:")db.execute("CREATE TABLE person (id INTEGER PRIMARY KEY, email TEXT, age INTEGER)")db.executemany( "INSERT INTO person (email, age) VALUES (?, ?)", [(f"user{i}@example.com", 20 + i % 40) for i in range(1000)],)query = "SELECT id FROM person WHERE email = 'user500@example.com'" def plan(sql): return " ".join(row[3] for row in db.execute("EXPLAIN QUERY PLAN " + sql)) before = plan(query)db.execute("CREATE INDEX idx_person_email ON person(email)")after = plan(query)print("SCAN" in before, "SEARCH" in after, "idx_person_email" in after)print(db.execute(query).fetchall())Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| With no index on email, the planner must scan the whole table: SCAN person. | plan: SCAN person | — | |
| Build a B-tree on email. Inserts now also maintain this index. | plan: SCAN person | — | |
| The planner now searches the index instead of scanning every row: SEARCH ... USING INDEX idx_person_email. | plan: SEARCH person USING INDEX idx_person_email | — | |
| All three checks are true. | plan: SEARCH person USING INDEX idx_person_email | True True True | |
| The query returns the same row either way; only the cost changed. | plan: SEARCH person USING INDEX idx_person_email | True True True [(501,)] |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
A full scan is O(n). An indexed equality lookup is O(log n). Building the index costs O(n log n) once.
- Indexing every column slows writes and wastes space. Index columns that queries actually filter, join, or sort on.
- A function on the column, such as WHERE lower(email) = ..., usually prevents the index from being used unless the index is built on that expression.
- Plan text is not a stable interface. Check behavior (SCAN versus SEARCH), not exact strings, when you test it.
Try it yourself
Would the email index help the query WHERE age = 30? Why?
Reveal answer and reasoning
No. The index is sorted by email, so it cannot locate rows by age. An index on age would be needed.