Indexes: How They Work and When They Help

On the small shop tables every query is instant, because SQLite can read all 14 orders faster than you can blink. Real tables are not small: a log of every LLM call your app makes, a clickstream that feeds a recommender, a table of RAG chunks — these reach millions of rows quickly. Without help, the database answers "find the events of customer 42" by reading every row. An index is that help: a separate, sorted structure that lets the database jump straight to the rows it needs.

This page builds a 200,000-row table, then measures what an index changes — not with a stopwatch (timings vary from machine to machine) but with the query plan and a count of the work SQLite really does.

What you will learn

• What an index is, and the B-tree idea behind almost every index you will meet
• Primary vs secondary indexes, and unique indexes
• Composite indexes, why column order matters (the leftmost-prefix rule), and covering indexes
• Selectivity and cardinality: when an index helps, when it does nothing, and what it costs
• How to read EXPLAIN QUERY PLAN before and after adding an index

A table big enough to notice

Imagine the shop records every product view, add-to-cart and purchase — the raw material for a recommender or a churn model. This block generates 200,000 such events with a recursive CTE (see CTEs and Recursive Queries). Arithmetic on the row number i spreads the values out, so the data is the same every time you run it:

CREATE TABLE events (
    event_id    INTEGER PRIMARY KEY,
    customer_id INTEGER NOT NULL,
    event_type  TEXT    NOT NULL,
    product_id  INTEGER NOT NULL,
    event_day   TEXT    NOT NULL,
    amount      INTEGER NOT NULL
);

INSERT INTO events (event_id, customer_id, event_type, product_id, event_day, amount)
WITH RECURSIVE n(i) AS (
    SELECT 1
    UNION ALL
    SELECT i + 1 FROM n WHERE i < 200000
)
SELECT i,
       (i * 7919) % 5000 + 1,                       -- 5,000 customers
       CASE WHEN i % 20 = 0 THEN 'purchase'         -- 5% purchases
            WHEN i % 5 = 0 THEN 'cart'              -- 15% add-to-cart
            ELSE 'view' END,                        -- 80% views
       (i * 31) % 11 + 1,                           -- products 1 to 11
       date('2026-01-01', '+' || (i % 181) || ' days'),
       (i * 37) % 5000 + 100
FROM n;

SELECT COUNT(*) AS events,
       COUNT(DISTINCT customer_id) AS customers,
       MIN(event_day) AS first_day,
       MAX(event_day) AS last_day
FROM events;

+--------+-----------+------------+------------+
| events | customers | first_day  | last_day   |
+--------+-----------+------------+------------+
| 200000 |      5000 | 2026-01-01 | 2026-06-30 |
+--------+-----------+------------+------------+

Before: a full table scan

EXPLAIN QUERY PLAN in front of a query asks SQLite how it would run it, without running it:

EXPLAIN QUERY PLAN
SELECT * FROM events WHERE customer_id = 42;

+----+--------+---------+-------------+
| id | parent | notused | detail      |
+----+--------+---------+-------------+
|  2 |      0 |       0 | SCAN events |
+----+--------+---------+-------------+

SCAN events means: read the whole table, row by row, and test each one. The detail column is the part to read; the other three describe how plan steps nest. To see what a scan costs, some small helpers. plan() prints just the detail lines. count_steps() runs a statement and counts SQLite's bytecode steps: SQLite compiles every statement into a little program, and a progress handler lets Python count its instructions. work() prints the result. Unlike a timing, the count is the same on every run, so it is a fair way to compare. (It measures CPU work, not disk reads — keep that in mind below.)

import sqlite3

from sqlhelp import con


def plan(sql, params=()):
    """Print the detail lines of SQLite's plan for a query."""
    fresh = sqlite3.connect("shop.db")      # a new connection always sees the latest indexes
    for row in fresh.execute("EXPLAIN QUERY PLAN " + sql, params):
        print(row[3])
    fresh.close()


def count_steps(sql, params=()):
    """Run a statement; return (rows returned, bytecode steps SQLite executed)."""
    steps = 0

    def tick():
        nonlocal steps
        steps += 1
        return 0                      # 0 means "keep going"

    con.set_progress_handler(tick, 1)  # call tick() after every instruction
    rows = con.execute(sql, params).fetchall()
    con.set_progress_handler(None, 1)
    return len(rows), steps


def work(sql, params=()):
    rows, steps = count_steps(sql, params)
    print(f"{rows} rows, {steps:,} steps")


query = "SELECT * FROM events WHERE customer_id = ?"
plan(query, (42,))
work(query, (42,))

SCAN events
40 rows, 600,372 steps

Why a fresh connection in plan()? Python's sqlite3 caches prepared statements, and a cached EXPLAIN is never re-planned — after you add an index in another tool (or another connection) it would keep showing the old plan. Real queries are re-planned automatically; only the plan display goes stale.

About 600,000 steps — roughly three for every row in the table — to return 40 rows. Double the table and the cost doubles: a scan is O(n).

What an index is: the B-tree idea

Think of the index at the back of a textbook. Its entries are sorted, so you find "normalization" in seconds, and each entry gives page numbers instead of the text itself. A database index is the same: a sorted copy of one or more columns, where every entry points back to its row. Almost all of them are B-trees — balanced trees with many keys per node, so even a huge table needs only a few levels:

                     index on customer_id (sorted)
                  ┌──────────────────────────────┐
                  │  root:   1250 | 2500 | 3750  │
                  └──────┬────────┬───────┬──────┘
             ┌───────────┘        │       └────────────┐
     ┌───────▼────────┐   ┌───────▼────────┐   ┌───────▼────────┐
     │ 1 .. 1249      │   │ 1250 .. 2499   │   │ ...            │  inner nodes
     └───────┬────────┘   └────────────────┘   └────────────────┘
     ┌───────▼─────────────────────────────┐
     │ leaf: (42, row 4839) (42, row 9839) │  key + pointer to the row
     │       (42, row 14839) ...           │
     └─────────────────────────────────────┘

Finding a key means walking from the root to one leaf: about log₂(200,000) ≈ 18 comparisons instead of 200,000. Because the leaves are in order, ranges (BETWEEN, >=) and ORDER BY on the indexed column come cheap too. Now create one:

CREATE INDEX idx_events_customer ON events (customer_id);

plan(query, (42,))
work(query, (42,))

SEARCH events USING INDEX idx_events_customer (customer_id=?)
40 rows, 504 steps

Same 40 rows, about 1,200 times less work. The plan changed from SCAN to SEARCH … USING INDEX: SQLite looked up 42 in the index, then fetched only those 40 rows from the table. You did not change the query; the planner chose the index on its own. That is the point of indexes — they make queries faster without changing their results.

Primary, secondary and unique indexes

The table itself is stored as a B-tree ordered by its key. In SQLite an INTEGER PRIMARY KEY is that key (the rowid), so looking up by primary key needs no extra index at all:

plan("SELECT * FROM events WHERE event_id = ?", (4242,))
work("SELECT * FROM events WHERE event_id = ?", (4242,))

SEARCH events USING INTEGER PRIMARY KEY (rowid=?)
1 rows, 14 steps

Every other index is a secondary index: a separate B-tree whose entries point back to the table. The databases differ in what "point back" means:

A unique index also enforces a rule: no two entries may be equal. Every UNIQUE constraint, and every PRIMARY KEY except SQLite's INTEGER PRIMARY KEY (which is the rowid itself), is implemented by one — that is how SQLite checks customers.email so quickly:

PRAGMA index_list('customers');

+-----+------------------------------+--------+--------+---------+
| seq | name                         | unique | origin | partial |
+-----+------------------------------+--------+--------+---------+
|   0 | sqlite_autoindex_customers_1 |      1 | u      |       0 |
+-----+------------------------------+--------+--------+---------+

origin = u means it came from a UNIQUE constraint. You can create one yourself, and it then rejects duplicates like a constraint:

CREATE UNIQUE INDEX idx_products_name ON products (name);
INSERT INTO products (product_id, name, category_id, price, stock)
VALUES (12, 'Wireless Mouse', 2, 950, 10);

Error: UNIQUE constraint failed: products.name

Composite indexes and the leftmost-prefix rule

A composite index covers several columns, sorted by the first, then by the second within each first value — exactly like a phone book sorted by surname, then first name. Replace the single-column index with one on (customer_id, event_day):

DROP INDEX idx_events_customer;
CREATE INDEX idx_events_customer_day ON events (customer_id, event_day);

checks = [
    ("SELECT * FROM events WHERE customer_id = ? AND event_day >= ?", (42, "2026-06-01")),
    ("SELECT * FROM events WHERE customer_id = ? ORDER BY event_day DESC LIMIT 3", (42,)),
    ("SELECT * FROM events WHERE customer_id = ? ORDER BY amount DESC LIMIT 3", (42,)),
    ("SELECT * FROM events WHERE event_day = ?", ("2026-06-01",)),
]
for sql, params in checks:
    print(sql)
    plan(sql, params)
    print()

SELECT * FROM events WHERE customer_id = ? AND event_day >= ?
SEARCH events USING INDEX idx_events_customer_day (customer_id=? AND event_day>?)

SELECT * FROM events WHERE customer_id = ? ORDER BY event_day DESC LIMIT 3
SEARCH events USING INDEX idx_events_customer_day (customer_id=?)

SELECT * FROM events WHERE customer_id = ? ORDER BY amount DESC LIMIT 3
SEARCH events USING INDEX idx_events_customer_day (customer_id=?)
USE TEMP B-TREE FOR ORDER BY

SELECT * FROM events WHERE event_day = ?
SCAN events

• Filtering on both columns uses both: an equality on customer_id, then a range on event_day inside it.
• ORDER BY event_day for one customer needs no sorting: the index already holds that customer's days in order. Sorting by amount does: USE TEMP B-TREE FOR ORDER BY is SQLite building a temporary sort.
• Filtering on event_day alone cannot use the index — like finding everyone called "Rahim" in a phone book sorted by surname. The index helps only for a leftmost prefix of its columns.

The rule of thumb for column order: columns compared with = first, the range or sort column last. (SQLite (once it has statistics), MySQL 8.0.13+ and PostgreSQL 18+ can sometimes "skip-scan" a leading column with few distinct values, but never design an index around that.)

Covering indexes

An index entry already contains its columns. If a query needs only columns that are in the index, the database never has to visit the table — the index covers the query:

plan("SELECT event_day FROM events WHERE customer_id = ?", (42,))
plan("SELECT event_day, amount FROM events WHERE customer_id = ?", (42,))

SEARCH events USING COVERING INDEX idx_events_customer_day (customer_id=?)
SEARCH events USING INDEX idx_events_customer_day (customer_id=?)

Asking for amount as well forces 40 trips back to the table. The step counter cannot show this cost (the table is already in memory), but on a large table that does not fit in memory each trip can be a random disk read. If "a customer's spending by day" is a query your feature pipeline runs millions of times, put amount in the index. The old index is then a leftmost prefix of the new one, so it is redundant — drop it:

CREATE INDEX idx_events_customer_day_amount ON events (customer_id, event_day, amount);
DROP INDEX idx_events_customer_day;

plan("SELECT event_day, amount FROM events WHERE customer_id = ?", (42,))

SEARCH events USING COVERING INDEX idx_events_customer_day_amount (customer_id=?)

The other databases do the same. MySQL's EXPLAIN shows Using index for a covered query. PostgreSQL calls it an Index Only Scan, and can add non-key columns to an index just for covering: CREATE INDEX … ON events (customer_id, event_day) INCLUDE (amount). One PostgreSQL catch: its index entries carry no row visibility information, so an index-only scan skips the table only for pages that the visibility map marks as all-visible. On a table with many recent changes it still visits the table until VACUUM (or autovacuum) catches up.

Selectivity and cardinality: when an index helps

The cardinality of a column is how many distinct values it has. Selectivity is the fraction of rows one value picks out: the smaller, the more an index helps.

SELECT event_type,
       COUNT(*) AS rows_matched,
       ROUND(100.0 * COUNT(*) / (SELECT COUNT(*) FROM events), 1) AS pct_of_table
FROM events
GROUP BY event_type
ORDER BY rows_matched;

+------------+--------------+--------------+
| event_type | rows_matched | pct_of_table |
+------------+--------------+--------------+
| purchase   |        10000 |          5.0 |
| cart       |        30000 |         15.0 |
| view       |       160000 |         80.0 |
+------------+--------------+--------------+

customer_id has 5,000 distinct values (one customer is 0.02% of the table); event_type has only 3. Index it anyway and compare each type with and without the index (NOT INDEXED forbids SQLite from using one):

CREATE INDEX idx_events_type ON events (event_type);

for event_type in ("purchase", "view"):
    rows, with_index = count_steps(
        "SELECT SUM(amount) FROM events WHERE event_type = ?", (event_type,))
    rows, full_scan = count_steps(
        "SELECT SUM(amount) FROM events NOT INDEXED WHERE event_type = ?", (event_type,))
    print(f"{event_type:9} index: {with_index:>9,} steps   scan: {full_scan:>9,} steps")

purchase  index:    50,123 steps   scan:   620,012 steps
view      index:   800,013 steps   scan:   920,011 steps

For purchases (5% of rows) the index saves over 90% of the work. For views (80%) it saves almost nothing — and on a real disk it is often slower, because 160,000 index entries mean 160,000 jumps to scattered table pages, while a scan reads the pages in order. That is why planners with statistics (next page) often ignore an index on a low-selectivity value. If you only ever query the rare value, a partial index (SQLite and PostgreSQL) indexes just those rows:

DROP INDEX idx_events_type;
CREATE INDEX idx_purchases_customer ON events (customer_id) WHERE event_type = 'purchase';

plan("SELECT * FROM events WHERE event_type = 'purchase' AND customer_id = ?", (40,))

SEARCH events USING INDEX idx_purchases_customer (customer_id=?)

What indexes cost

An index is not free. It takes disk space, and every INSERT, UPDATE of an indexed column and DELETE must update every index too. The dbstat virtual table shows the space (it exists only when SQLite was compiled with it, as most Linux builds are; if you get no such table: dbstat, your build lacks it):

from sqlhelp import show

show("""
SELECT name, COUNT(*) AS pages, SUM(pgsize) / 1024 AS kib
FROM dbstat
WHERE name LIKE '%events%' OR name LIKE 'idx_purchases%'
GROUP BY name
ORDER BY kib DESC
""")

+--------------------------------+-------+------+
| name                           | pages | kib  |
+--------------------------------+-------+------+
| events                         |  1576 | 6304 |
| idx_events_customer_day_amount |  1221 | 4884 |
| idx_purchases_customer         |    28 |  112 |
+--------------------------------+-------+------+

The three-column covering index is over three quarters the size of the table itself; the partial index is tiny because it holds only 5% of the rows. Now the write cost: load the same 50,000 rows into a table with no secondary indexes and into one with three:

con.execute("CREATE TABLE events_plain AS SELECT * FROM events WHERE 0")      # same columns, no rows
con.execute("CREATE TABLE events_indexed AS SELECT * FROM events WHERE 0")
con.execute("CREATE INDEX idx_ei_customer ON events_indexed (customer_id, event_day, amount)")
con.execute("CREATE INDEX idx_ei_type ON events_indexed (event_type)")
con.execute("CREATE INDEX idx_ei_product ON events_indexed (product_id)")

for table in ("events_plain", "events_indexed"):
    _, steps = count_steps(f"INSERT INTO {table} SELECT * FROM events WHERE event_id <= 50000")
    con.commit()
    print(f"{table:15} {steps:>9,} steps")

events_plain      750,017 steps
events_indexed  1,500,020 steps

Three indexes doubled the cost of the same load. For a table that is written far more often than it is read — a raw event or log stream — every index needs a good reason. For a table that is read all day — products, a feature table, RAG chunk metadata — indexes on the columns you filter and join by are usually the best performance work you can do.

Indexes in real systems

• Feature lookups, APIs and LLM logs. "All events of this user", "this user's calls last week": index the column you filter by, or a composite like (user_id, created_at). SQLite and PostgreSQL do not index foreign keys for you — the shop's orders.customer_id has no index.
• RAG and vector search. A chunk table needs B-tree indexes on document_id and its metadata filters, plus a vector index such as pgvector's HNSW (see SQL for AI Apps: Embeddings, pgvector and RAG Metadata) — a different structure built for "nearest" instead of "equal", with the same trade-off: faster reads, slower writes, extra space.
• Uniqueness as a guard. A unique index on (source, external_id) makes a pipeline's re-run fail or upsert instead of silently doubling the data.

Common mistakes

• Indexing every column "just in case". Each index slows every write and uses space, and most go unused. Index for the queries you actually run; in PostgreSQL, pg_stat_user_indexes.idx_scan = 0 finds indexes nobody uses.
• Wrong column order. An index on (event_day, customer_id) does not help WHERE customer_id = 42. Put the equality columns your queries always have first: CREATE INDEX … ON events (customer_id, event_day).
• Keeping redundant indexes. (customer_id) is useless next to (customer_id, event_day); drop the shorter one.
• Hiding the column inside a function. The index stores event_day, not substr(event_day, 1, 7), so this scans. Write a range on the bare column instead:
  PythonCopy

  plan("SELECT COUNT(*) FROM events WHERE customer_id = 42 AND substr(event_day, 1, 7) = '2026-06'")
  plan("SELECT COUNT(*) FROM events WHERE customer_id = 42 AND event_day >= '2026-06-01' AND event_day < '2026-07-01'")

  OutputCopy

  SEARCH events USING COVERING INDEX idx_events_customer_day_amount (customer_id=?)
  SEARCH events USING COVERING INDEX idx_events_customer_day_amount (customer_id=? AND event_day>? AND event_day<?)

  The first plan searches only on customer_id and then tests every day of that customer; the second searches on both columns. The next page covers such sargable filters in detail.
• Expecting an index to fix a low-selectivity filter. An index on a yes/no column or a three-value status rarely helps. Use a partial index for the rare value, or a composite index that starts with a selective column.

Try it yourself

1. Easy: Show the plan for SELECT COUNT(*) FROM events WHERE product_id = 7, add an index that turns the scan into a search, and show the plan again.
2. Medium: The marketing team runs SELECT customer_id, amount FROM events WHERE event_type = 'cart' AND event_day BETWEEN '2026-03-01' AND '2026-03-07' every hour. Design one index that lets SQLite search on both conditions and never touch the table, and prove it with the plan.
3. Hard: A churn model needs total purchase spend per customer. Create a partial covering index so that SELECT customer_id, SUM(amount) FROM events WHERE event_type = 'purchase' GROUP BY customer_id reads only the index, and compare the steps with and without it (use NOT INDEXED).

Answers

# 1. Easy
plan("SELECT COUNT(*) FROM events WHERE product_id = 7")
con.execute("CREATE INDEX idx_events_product ON events (product_id)")
plan("SELECT COUNT(*) FROM events WHERE product_id = 7")

# 2. Medium: equality column first, range column second, the selected column last
con.execute("CREATE INDEX idx_events_type_day ON events (event_type, event_day, customer_id, amount)")
plan("""SELECT customer_id, amount FROM events
        WHERE event_type = 'cart' AND event_day BETWEEN '2026-03-01' AND '2026-03-07'""")
# SEARCH events USING COVERING INDEX idx_events_type_day (event_type=? AND event_day>? AND event_day<?)

# 3. Hard (first drop the Medium index, which would also cover this query)
con.execute("DROP INDEX IF EXISTS idx_events_type_day")
sql = "SELECT customer_id, SUM(amount) FROM events {} WHERE event_type = 'purchase' GROUP BY customer_id"
con.execute("""CREATE INDEX idx_purchase_spend ON events (customer_id, amount)
               WHERE event_type = 'purchase'""")
plan(sql.format(""))
print(count_steps(sql.format("")))
print(count_steps(sql.format("NOT INDEXED")))

Summary

• An index is a sorted copy of some columns pointing back to the rows; a B-tree finds a key in a handful of steps instead of scanning the table.
• EXPLAIN QUERY PLAN shows SCAN (read everything) or SEARCH … USING INDEX; COVERING INDEX means the table was never touched.
• Composite indexes serve only a leftmost prefix of their columns: equality columns first, range or sort column last.
• Indexes pay off for selective filters; for values that match a large share of rows they do little. Partial indexes target the rare values.
• Every index costs space and slows every write — index for the queries you run, and drop redundant ones.

Next: EXPLAIN and Query Optimization reads full query plans in SQLite, PostgreSQL and MySQL, and turns this page's ideas into a routine for fixing slow queries: sargable filters, better joins, keyset pagination, N+1 queries from Python and statistics.