Database indexes: how they work, when they help

Asked for one customer’s 20 latest orders, a table of 100,000 orders made SQLite read every row and sort the matches; with one index it read only that customer’s 14 orders, already in order. A database index is a separate, sorted copy of one or more columns in which every entry points to its row, usually kept in a B-treeB-tree: A balanced tree of fixed-size pages, each holding many sorted keys, in which every lookup walks from the root page down to a leaf. Most databases keep their indexes, and many their tables, in one., so the database can jump to the matching rows in a few page reads instead of reading the whole table, and hand them back already sorted.

An index helps the queries that filter, join or sort on its leading columns. It costs disk space and extra work on every insert, update and delete, which is why you add indexes for the queries you run, not for the ones you might.

Searching instead of scanning

Take that table of 100,000 orders and the query behind a customer’s order history: their 20 latest orders. Without an index, the database must read every row, a full table scanfull table scan: A query plan that reads every row of a table to find the ones it wants, because no index leads to them. Its cost grows in step with the number of rows. More in “Latency numbers, measured on real hardware”, keep the matches and sort them. With an index on (user_id, created_at), it walks down the B-tree to the first entry for that user and reads only that user’s entries, already in time order. The script counts the rows each plan reads:

# One query, before and after an index: a user's 20 latest orders in a table of 100,000. The function touch() is
# called once for every row SQLite reads, so the count shows how much work each plan does.
import random
import sqlite3

rng = random.Random(1)
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE orders (id INTEGER PRIMARY KEY, user_id INTEGER, created_at INTEGER, status TEXT, total INTEGER)")
db.executemany(
    "INSERT INTO orders VALUES (?, ?, ?, ?, ?)",
    ((i, rng.randrange(1, 10_001), 1_750_000_000 + 30 * i, rng.choice(("delivered",) * 8 + ("cancelled", "pending")),
      rng.randrange(100, 2_000)) for i in range(1, 100_001)),
)
rows_read = 0


def touch(_):
    global rows_read
    rows_read += 1
    return 1


db.create_function("touch", 1, touch)
QUERY = ("SELECT id, created_at, total FROM orders WHERE touch(id) AND user_id = ? "
         "ORDER BY created_at DESC LIMIT 20")


def run(title):
    global rows_read
    print(title)
    for row in db.execute("EXPLAIN QUERY PLAN " + QUERY, (42,)):
        print(f"  plan: {row[3]}")
    rows_read = 0
    found = db.execute(QUERY, (42,)).fetchall()
    print(f"  rows read: {rows_read:,}; orders returned: {len(found)}")


print("The 20 latest orders of user 42, in a table of 100,000 orders\n")
run("Without an index")
db.execute("CREATE INDEX orders_user_time ON orders (user_id, created_at)")
run("\nWith CREATE INDEX orders_user_time ON orders (user_id, created_at)")

The 20 latest orders of user 42, in a table of 100,000 orders

Without an index
  plan: SCAN orders
  plan: USE TEMP B-TREE FOR ORDER BY
  rows read: 100,000; orders returned: 14

With CREATE INDEX orders_user_time ON orders (user_id, created_at)
  plan: SEARCH orders USING INDEX orders_user_time (user_id=?)
  rows read: 14; orders returned: 14

SQLite’s EXPLAIN QUERY PLAN says SCAN for a full pass over a table and SEARCH when only some rows are visited, and USE TEMP B-TREE marks a separate sort (SQLite). The index turned 100,000 rows read plus a sort into 14 rows read in order. The diagram shows the pages such a lookup reads:

Step through the same lookup, one page at a time:

The tree stays shallow because each page holds hundreds of entries. If a page holds about 300, three levels reach 300 × 300 × 300 = 27 million entries and four levels reach 8.1 billion, so a lookup reads a handful of pages whatever the table’s size, and the top levels are almost always already in memory. That is the logarithmic cost SQLite’s documentation describes for a search, against a cost that grows with every row for a scan (query planning).

Whether an index helps a given query follows from a few rules, each in one line here:

• The leftmost-prefix rule: a composite indexcomposite index: An index on several columns, sorted by the first column and, within each value of it, by the next. It can narrow a search only when the query constrains its leading columns. helps only queries that constrain its first columns.
• Equality first, range last: put the columns compared with = before the column compared as a range.
• Covering indexescovering index: An index that holds every column a query needs, so the database answers the query from the index alone, without reading the table. hold every column a query needs, so the table is never read.
• Partial indexes hold only the rows a WHERE clause selects, so they stay small; a query whose own condition implies that clause can use one.
• Write cost: every index adds work to every insert, update and delete.
• Query plans in SQLite and PostgreSQL show which index, if any, a query really uses.

The leftmost-prefix rule, and the scan hiding behind an index Pro: opens with a Pro, Premium or Ultimate pass