Indexes and query plans

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.

Python

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())

Read the full lesson