SQL Indexes Explained: Full Scan vs Index Search, With Query Plans

"Add an index" is the most common answer to a slow query, and the least understood. An index is not a switch that makes a table fast. It is a second, sorted copy of some columns, and it helps exactly the queries that can use that sort order. Every query below was run on SQLite 3.37 with EXPLAIN QUERY PLAN, and the plans shown are the real output.

The problem it solves

Without an index, a query like WHERE shot_by = 'Okonjo' has one strategy: read every row and test it. That is a full table scan, and its cost grows with the table, not with the answer. Finding 2 rows in a million-row table reads a million rows.

An index changes the strategy. Because its entries are sorted, the engine can binary-search to the first matching entry, read forward while entries still match, and follow each entry's pointer back to its row. The cost now grows with the logarithm of the table plus the size of the answer.

The intuition

Think of the lesson's photo library. The prints are filed in boxes by date. A second drawer holds cards sorted by photographer, each naming a box. To find every Weiss print, you flip to the W cards — a quick search in a sorted drawer — and go to the boxes they name.

Three consequences follow from that picture, and they are most of what there is to know about indexes:

• It only helps questions about its sort key. The photographer drawer is useless for "which prints are in box 9?".
• A sorted key helps ranges and ordering too, not only equality: "photographers after M" is a contiguous run of cards, and reading the drawer front to back gives the photographers in order.
• Every new print is filed twice. Writes pay for the reads you speed up.

The database version is usually a B-tree: a balanced tree whose leaves hold the sorted entries. SQLite stores both tables and indexes as B-trees.

Watch it run

The animation runs WHERE shot_by = 'Okonjo' first without an index: three rows read to return two, including a Weiss row that had to be read only to be rejected. Then CREATE INDEX builds the sorted copy, the same query jumps straight into the Okonjo block, and row 2 is never touched. The last frames show the price: a new print is written to the table and the index, and a query on box still scans everything.

The code

A small table, and the plan for the same query before and after the index. SCAN means every row; SEARCH means the engine jumps to the matching range:

import sqlite3

db = sqlite3.connect(":memory:")
db.executescript("""
  CREATE TABLE photo (id INTEGER PRIMARY KEY, shot_by TEXT, box INTEGER, year INTEGER);
  INSERT INTO photo (shot_by, box, year) VALUES
    ('Okonjo', 4, 1998), ('Weiss', 9, 2001), ('Okonjo', 2, 2003),
    ('Weiss', 7, 1998), ('Adler', 1, 2010);
""")

def plan(sql):
    for row in db.execute("EXPLAIN QUERY PLAN " + sql):
        print(row[3])

plan("SELECT box FROM photo WHERE shot_by = 'Okonjo'")
# SCAN photo
db.execute("CREATE INDEX photo_by ON photo(shot_by)")
plan("SELECT box FROM photo WHERE shot_by = 'Okonjo'")
# SEARCH photo USING INDEX photo_by (shot_by=?)

What the same index does and does not help. A range uses it; a different column does not; and wrapping the column in a function hides it, because the index is sorted by shot_by, not by lower(shot_by):

plan("SELECT box FROM photo WHERE shot_by > 'M'")
# SEARCH photo USING INDEX photo_by (shot_by>?)
plan("SELECT box FROM photo WHERE box = 9")
# SCAN photo
plan("SELECT box FROM photo WHERE lower(shot_by) = 'okonjo'")
# SCAN photo
plan("SELECT shot_by FROM photo ORDER BY shot_by")
# SCAN photo USING COVERING INDEX photo_by
plan("SELECT box FROM photo ORDER BY year")
# SCAN photo
# USE TEMP B-TREE FOR ORDER BY

The ORDER BY shot_by plan still says SCAN, but of the index, which is already in order, and covering: the index alone holds every column the query needs, so the table is never read. ORDER BY year has no index to lean on, so SQLite builds a temporary B-tree just to sort.

Composite indexes sort by the first column, then by the second within ties — like a phone book sorted by surname, then first name. That makes them useful for the leftmost columns, and not for the second column alone:

db.execute("CREATE INDEX photo_by_year ON photo(shot_by, year)")
plan("SELECT box FROM photo WHERE shot_by = 'Weiss' AND year = 1998")
# SEARCH photo USING INDEX photo_by_year (shot_by=? AND year=?)
plan("SELECT box FROM photo WHERE year = 1998")
# SCAN photo
plan("SELECT year FROM photo WHERE shot_by = 'Weiss'")
# SEARCH photo USING COVERING INDEX photo_by_year (shot_by=?)

An index must never change an answer, only how it is found. The check below runs the same query on 200 random tables twice — once without the index, once with it — and compares both with a plain Python filter, while confirming that the indexed copy actually used the index:

import random

random.seed(5)
names = ["Adler", "Okonjo", "Weiss", "Zhou"]
ok = True
for trial in range(200):
    rows = [(i, random.choice(names), random.randint(1, 20), random.randint(1990, 2000))
            for i in range(random.randint(0, 60))]
    plain = sqlite3.connect(":memory:")
    indexed = sqlite3.connect(":memory:")
    for con in (plain, indexed):
        con.execute("CREATE TABLE photo (id INTEGER PRIMARY KEY, shot_by TEXT, box INTEGER, year INTEGER)")
        con.executemany("INSERT INTO photo VALUES (?, ?, ?, ?)", rows)
    indexed.execute("CREATE INDEX photo_by_year ON photo(shot_by, year)")
    who, lo = random.choice(names), random.randint(1990, 2000)
    q = "SELECT id FROM photo WHERE shot_by = ? AND year >= ? ORDER BY id"
    want = [r[0] for r in rows if r[1] == who and r[3] >= lo]   # brute force filter
    got_plain = [r[0] for r in plain.execute(q, (who, lo))]
    got_index = [r[0] for r in indexed.execute(q, (who, lo))]
    used = indexed.execute("EXPLAIN QUERY PLAN " + q, (who, lo)).fetchone()[3]
    ok &= want == got_plain == got_index and "photo_by_year" in used
print(ok, used)
# True SEARCH photo USING COVERING INDEX photo_by_year (shot_by=? AND year>?)

SQLite prints year>? for the >= condition in this plan; the results confirm the boundary rows were included.

The complexity

• Scan: O(n) rows read, whatever the answer size.
• B-tree search: O(log n) to find the start of the range, plus O(k) to read k matching entries, plus one lookup per match to fetch the row unless the index is covering.
• Writes: every insert and delete, and every update to an indexed column, also updates each index that contains it — O(log n) more work per index, and more storage.

When a query matches a large fraction of the table, the per-row lookups can cost more than one sequential scan, and query planners may choose the scan on purpose.

Where it goes wrong

• Functions on the indexed column. lower(shot_by), date arithmetic or type conversions on the column hide it from the index. Rewrite the condition, or create an index on the expression if your database supports it.
• Composite column order. An index on (shot_by, year) serves shot_by alone and shot_by with year, but not year alone. Put the column you always filter by first.
• Indexing everything. Each index slows every write and takes space. Index the queries you actually run, and check with the plan.
• Guessing instead of reading the plan. EXPLAIN QUERY PLAN in SQLite, EXPLAIN in PostgreSQL and MySQL. The words differ; SCAN versus SEARCH is the question to ask.

How to say it in an interview

"An index is a separate sorted structure, usually a B-tree, over one or more columns, with each entry pointing to its row. It turns a full scan into a logarithmic search plus the matches, and it also serves range conditions and ORDER BY on those columns. A composite index works for its leftmost columns. The cost is on writes and storage, since every index has to be maintained. I'd confirm it's used with EXPLAIN rather than assume."

Two follow-ups go deeper: composite and covering indexes and reading a query plan.