Database indexes explained: why a lookup stops scanning the whole table

Imagine looking for one customer in a printed list of 200,000 orders. With no help you read from the first line until you find every match. If the list were sorted by customer you could jump near the right place and read a handful of lines. An index is that sorted help: a second structure the database keeps in step with the table.

What an index is

Most relational databases build indexes as B-trees: sorted, balanced trees where each step narrows the search by a large factor. Finding one value in a million takes a few steps rather than a million reads, and the cost grows very slowly as the table grows.

An index stores the indexed column's values in order, each paired with a pointer to the row. Looking up customer_id = 4242 walks the tree to the first matching entry and reads along it while the value stays 4242.

See it work

This script builds a table of 200,000 orders in SQLite and asks for one customer's orders before and after adding an index. EXPLAIN QUERY PLAN shows what the database decides to do.

import random
import sqlite3
import time

conn = sqlite3.connect(":memory:")
conn.execute(
    "CREATE TABLE orders (id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT, total REAL, created_at TEXT)"
)
random.seed(1)
rows = [
    (i, random.randint(1, 5000), random.choice(["new", "paid", "shipped", "cancelled"]),
     round(random.uniform(5, 500), 2), f"2025-{random.randint(1, 12):02d}-{random.randint(1, 28):02d}")
    for i in range(1, 200_001)
]
conn.executemany("INSERT INTO orders VALUES (?, ?, ?, ?, ?)", rows)
conn.commit()


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


def timed(sql):
    start = time.perf_counter()
    count = len(conn.execute(sql).fetchall())
    print(f"    {count} rows in {(time.perf_counter() - start) * 1000:.2f} ms")


query = "SELECT id, total FROM orders WHERE customer_id = 4242"
print("1. no index")
plan(query)
timed(query)

conn.execute("CREATE INDEX idx_orders_customer ON orders (customer_id)")
print("2. index on customer_id")
plan(query)
timed(query)

On one run on a laptop this printed:

1. no index
    SCAN orders
    32 rows in 4.55 ms
2. index on customer_id
    SEARCH orders USING INDEX idx_orders_customer (customer_id=?)
    32 rows in 0.05 ms

Your timings will differ, but the words matter more than the numbers. SCAN means every row was read. SEARCH ... USING INDEX means the database jumped to the matching entries. The same words (or Seq Scan and Index Scan) appear in the plans of other databases.

Composite indexes: order matters

An index on (customer_id, status, created_at) is sorted by customer_id, then by status within each customer, then by created_at within each status. That makes it useful for queries that filter on the leftmost columns in order, and it can even return rows already sorted.

query2 = "SELECT id FROM orders WHERE customer_id = 4242 AND status = 'paid' ORDER BY created_at"
print("3. filter on two columns and sort, single-column index only")
plan(query2)
conn.execute("CREATE INDEX idx_orders_cust_status_date ON orders (customer_id, status, created_at)")
print("4. composite index (customer_id, status, created_at)")
plan(query2)

3. filter on two columns and sort, single-column index only
    SEARCH orders USING INDEX idx_orders_customer (customer_id=?)
    USE TEMP B-TREE FOR ORDER BY
4. composite index (customer_id, status, created_at)
    SEARCH orders USING COVERING INDEX idx_orders_cust_status_date (customer_id=? AND status=?)

Before, the database found the customer's rows and then had to sort them (USE TEMP B-TREE FOR ORDER BY). With the composite index the rows come out already in order and the sort disappears. The index is also covering: it holds every column the query asks for, so the table is never touched.

A useful rule: put the columns you compare with = first, then the column you range over or sort by.

When the database ignores your index

An index is only useful when the query can use the sorted order. The usual reasons it cannot:

1. A function wraps the column. WHERE lower(status) = 'paid' cannot use an index on status, because the index is sorted by the stored value, not the lowercased one. Compare the plans:

conn.execute("DROP INDEX idx_orders_cust_status_date")
conn.execute("DROP INDEX idx_orders_customer")
conn.execute("CREATE INDEX idx_orders_status ON orders (status)")
print("5. index on status")
plan("SELECT id FROM orders WHERE status = 'paid'")
print("6. the same column wrapped in a function")
plan("SELECT id FROM orders WHERE lower(status) = 'paid'")

5. index on status
    SEARCH orders USING COVERING INDEX idx_orders_status (status=?)
6. the same column wrapped in a function
    SCAN orders USING COVERING INDEX idx_orders_status

In the second query the database reads every entry of the index instead of jumping to the matches. Some databases let you index the expression itself (CREATE INDEX ... ON orders (lower(status))), which fixes this case.

1. A leading wildcard. LIKE '%smith' cannot use an ordinary index, but LIKE 'smith%' can.
2. The leftmost column is missing. The composite index above does not help a query that filters only on status.
3. The index would not help. If a value matches most of the table, reading the table directly is cheaper than jumping back and forth. The planner may rightly choose a scan.

What indexes cost

• Writes get slower. Every insert, update or delete that touches an indexed column must also update each index on it.
• Space. Each index is a copy of the indexed columns plus pointers. Wide composite indexes can rival the table in size.
• Maintenance. More indexes mean more to review, rebuild and keep in step with how the application really queries.

Add an index when a query you actually run is slow, confirm with the plan that the database uses it, and drop indexes that nothing uses.