Indexes and query plans
See how an index changes a table scan into a search by reading the query plan.
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,)]
Explanation
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.
Explore the dry run
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,)] |
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.