Skip to main content
ProgrammersOS
Sign In
Databases•Last Updated : 23 Oct 2026
~45 min read

Database Indexes and Query Plans

Why an index turns a table scan into a handful of page reads, how to read a query plan, how composite and covering indexes work, and the common ways a query accidentally ignores its index.

The query that was fast in development

A new feature ships. The page that lists a customer's orders loads instantly on your laptop, where the table holds a few hundred rows. Six months later it holds forty million rows and the page times out. Nothing in the code changed. What changed is that the database now answers WHERE customer_id = 42 by reading every row and checking each one, because nothing tells it where customer 42's rows live.

An index is that missing "where": a separate, sorted structure that maps a column's values to the rows that contain them. It is the same idea as the index at the back of a textbook. You do not read 800 pages to find "recursion"; you look it up alphabetically and jump to page 312.

Indexing is the single highest-leverage performance skill in everyday database work, and it has a price: every index must be updated on every write and takes disk space. The goal of this lesson is to let you decide which indexes earn their keep, and to verify the decision by reading the database's own account of what it did, the query plan.

How an index works: sorted keys and a shallow tree

Start with the intuition. If the values are kept sorted, you can find one by binary search: look at the middle, discard half, repeat. A million sorted values need about 20 comparisons; an unsorted list needs up to a million.

Databases refine this into a B-tree (strictly a B+ tree in most engines). Disk is read in pages of several kilobytes, so instead of a binary tree with two children per node, each node is one page holding hundreds of sorted keys and pointers. The tree stays balanced and very shallow: with a few hundred keys per page, three or four levels address hundreds of millions of rows, which means a lookup costs a handful of page reads. The leaf level is linked in order, so a range query (created BETWEEN a AND b) finds the start and then walks sideways without going back up.

Each leaf entry stores the indexed value and a pointer to the full row (its row id or primary key). Looking up a row through a secondary index is therefore two steps: find the key in the index, then fetch the row from the table.

A B-tree index on customer_id (three levels shown in miniature)
                  [ 200 | 400 ]                  <- root page
                 /      |       \
    [ 50|100|150 ]  [ 250|300|350 ]  [ 450|500 ...]   <- internal pages
     /   |   |  \
[1..49][50..99][100..149][150..199]  ---->  chained leaf pages
   |      |
key -> row pointer (customer 42 -> rows 42, 542, 1042, ...)
A lookup descends one page per level; leaves are chained so ranges are cheap.

Seeing the difference: comparisons, not guesses

Wall-clock timings depend on your machine, so first measure something deterministic: the number of comparisons. The program below searches 100,000 sorted ids for a value, once the way a table scan does (check one by one) and once the way an index does (binary search). Count the steps rather than trusting a stopwatch.

PythonScan versus binary search, counted
1from bisect import bisect_left
2 
3data = list(range(0, 200000, 2))   # 100,000 sorted even numbers
4target = 150000
5 
6def scan(values, x):
7    steps = 0
8    for v in values:
9        steps += 1
10        if v == x:
11            return steps
12    return steps
13 
14def binary(values, x):
15    lo, hi, steps = 0, len(values), 0
16    while lo < hi:
17        steps += 1
18        mid = (lo + hi) // 2
19        if values[mid] < x:
20            lo = mid + 1
21        else:
22            hi = mid
23    return steps
24 
25print("rows:", len(data))
26print("table-scan steps:", scan(data, target))
27print("index-style steps:", binary(data, target))
28assert data[bisect_left(data, target)] == target
Output
rows: 100000
table-scan steps: 75001
index-style steps: 16

Reading a query plan

You never need to guess whether the database used your index. Every engine can describe its strategy: EXPLAIN in PostgreSQL and MySQL, EXPLAIN QUERY PLAN in SQLite. The plan lists the steps in order; the words to look for are SCAN (read the whole table) and SEARCH ... USING INDEX (descend an index).

Below, the same query is planned before and after creating an index on customer_id. Run it yourself on a table with 5,000 rows. The exact wording of the plan text differs between SQLite versions and between engines, but SCAN versus SEARCH is universal.

Note

A plan is a prediction made from statistics. For the actual numbers use EXPLAIN ANALYZE (PostgreSQL) or the slow-query log, and test with realistic data volume: a plan on 100 rows can differ from the plan on 100 million.

PythonPlan before and after CREATE INDEX
1import sqlite3
2db = sqlite3.connect(":memory:")
3db.execute("CREATE TABLE orders (id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT, created INTEGER, email TEXT)")
4rows = []
5for i in range(1, 5001):
6    rows.append((i, i % 500, "shipped" if i % 3 else "pending", 20260000 + i % 365, "user%d@mail.test" % (i % 700)))
7db.executemany("INSERT INTO orders VALUES (?,?,?,?,?)", rows)
8def plan(sql):
9    for r in db.execute("EXPLAIN QUERY PLAN " + sql):
10        print("  ", r[3])
11 
12q = "SELECT * FROM orders WHERE customer_id = 42"
13print("before the index:")
14plan(q)
15db.execute("CREATE INDEX idx_orders_customer ON orders(customer_id)")
16print("after the index:")
17plan(q)
18print("rows returned:", len(db.execute(q).fetchall()))
Output
before the index:
   SCAN orders
after the index:
   SEARCH orders USING INDEX idx_orders_customer (customer_id=?)
rows returned: 10

Composite indexes and the leftmost-prefix rule

Real queries usually filter on more than one column: "this customer's pending orders, newest first". A composite index on (customer_id, status, created) stores entries sorted by customer first, then by status within each customer, then by date within that. Think of a phone book sorted by last name, then first name.

That ordering explains the leftmost-prefix rule. The index can serve a query that constrains customer_id, or customer_id and status, or all three, because in each case the matching entries sit together. It cannot efficiently serve a query on status alone, just as a phone book cannot help you find everyone named "Ana" without reading every page.

Column order is therefore a design decision. A good default: put equality columns first, then the column used for a range or ordering last. The index below supports the filter and the ORDER BY with no separate sort step.

PythonWhich queries can use (customer_id, status, created)?
1import sqlite3
2db = sqlite3.connect(":memory:")
3db.execute("CREATE TABLE orders (id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT, created INTEGER, email TEXT)")
4rows = []
5for i in range(1, 5001):
6    rows.append((i, i % 500, "shipped" if i % 3 else "pending", 20260000 + i % 365, "user%d@mail.test" % (i % 700)))
7db.executemany("INSERT INTO orders VALUES (?,?,?,?,?)", rows)
8def plan(sql):
9    for r in db.execute("EXPLAIN QUERY PLAN " + sql):
10        print("  ", r[3])
11 
12db.execute("CREATE INDEX idx_cust_status_created ON orders(customer_id, status, created)")
13tests = [
14    "SELECT * FROM orders WHERE customer_id = 7",
15    "SELECT * FROM orders WHERE customer_id = 7 AND status = 'pending' ORDER BY created",
16    "SELECT * FROM orders WHERE status = 'pending'",
17    "SELECT * FROM orders WHERE customer_id = 7 AND created > 20260200",
18]
19for q in tests:
20    print(q)
21    plan(q)
Output
SELECT * FROM orders WHERE customer_id = 7
   SEARCH orders USING INDEX idx_cust_status_created (customer_id=?)
SELECT * FROM orders WHERE customer_id = 7 AND status = 'pending' ORDER BY created
   SEARCH orders USING INDEX idx_cust_status_created (customer_id=? AND status=?)
SELECT * FROM orders WHERE status = 'pending'
   SCAN orders
SELECT * FROM orders WHERE customer_id = 7 AND created > 20260200
   SEARCH orders USING INDEX idx_cust_status_created (customer_id=?)

Covering indexes: never touching the table

Normally an index lookup costs a second hop to fetch the row. If the index already contains every column the query needs, the engine can answer from the index alone and skip the table entirely. That is a covering index, and the plan says so ("USING COVERING INDEX").

The query below only needs customer_id and status, both in the composite index, so it is covered. Add a column the index does not hold (email) and the engine must go back to the table for each match. Covering is a tuning technique for your hottest read queries: you widen the index slightly to save a page read per row returned.

PythonCovered and not covered
1import sqlite3
2db = sqlite3.connect(":memory:")
3db.execute("CREATE TABLE orders (id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT, created INTEGER, email TEXT)")
4rows = []
5for i in range(1, 5001):
6    rows.append((i, i % 500, "shipped" if i % 3 else "pending", 20260000 + i % 365, "user%d@mail.test" % (i % 700)))
7db.executemany("INSERT INTO orders VALUES (?,?,?,?,?)", rows)
8def plan(sql):
9    for r in db.execute("EXPLAIN QUERY PLAN " + sql):
10        print("  ", r[3])
11 
12db.execute("CREATE INDEX idx_cust_status ON orders(customer_id, status)")
13print("needs customer_id, status only:")
14plan("SELECT customer_id, status FROM orders WHERE customer_id = 7")
15print("also needs email (not in the index):")
16plan("SELECT customer_id, status, email FROM orders WHERE customer_id = 7")
Output
needs customer_id, status only:
   SEARCH orders USING COVERING INDEX idx_cust_status (customer_id=?)
also needs email (not in the index):
   SEARCH orders USING INDEX idx_cust_status (customer_id=?)

Five ways a query ignores its index

An index existing and an index being used are different things. These are the usual reasons a perfectly good index sits idle:

  1. A function wrapped around the column. WHERE lower(email) = 'x' must compute lower() for every row, so the sorted order of raw email values is useless. Fix: compare the raw column, store a normalised copy, or create an expression index on lower(email) if your engine supports it.
  2. A leading wildcard. LIKE '%mail.test' cannot use the sort order, whereas a pure prefix match can, because matching strings sit next to each other in the index. Details vary by engine: SQLite's LIKE is case-insensitive and ignores a plain index (use GLOB 'user7@*', as below, or a NOCASE index), and PostgreSQL needs a suitable operator class or C collation for prefix searches.
  3. Low selectivity. An index on a column where half the rows share one value (status) saves little; the optimiser may rightly prefer a scan because jumping around the index plus the table is slower than reading straight through.
  4. Type mismatch. Comparing a text column to a number can force a conversion on every row.
  5. Skipping the leftmost column of a composite index, as seen above.

Run the experiment: exact match, function wrapped, prefix match, suffix match.

PythonA function on the column defeats the index
1import sqlite3
2db = sqlite3.connect(":memory:")
3db.execute("CREATE TABLE orders (id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT, created INTEGER, email TEXT)")
4rows = []
5for i in range(1, 5001):
6    rows.append((i, i % 500, "shipped" if i % 3 else "pending", 20260000 + i % 365, "user%d@mail.test" % (i % 700)))
7db.executemany("INSERT INTO orders VALUES (?,?,?,?,?)", rows)
8def plan(sql):
9    for r in db.execute("EXPLAIN QUERY PLAN " + sql):
10        print("  ", r[3])
11 
12db.execute("CREATE INDEX idx_email ON orders(email)")
13for q in [
14    "SELECT * FROM orders WHERE email = 'user7@mail.test'",
15    "SELECT * FROM orders WHERE lower(email) = 'user7@mail.test'",
16    "SELECT * FROM orders WHERE email GLOB 'user7@*'",
17    "SELECT * FROM orders WHERE email GLOB '*@mail.test'",
18]:
19    print(q)
20    plan(q)
Output
SELECT * FROM orders WHERE email = 'user7@mail.test'
   SEARCH orders USING INDEX idx_email (email=?)
SELECT * FROM orders WHERE lower(email) = 'user7@mail.test'
   SCAN orders
SELECT * FROM orders WHERE email GLOB 'user7@*'
   SEARCH orders USING INDEX idx_email (email>? AND email<?)
SELECT * FROM orders WHERE email GLOB '*@mail.test'
   SCAN orders

The cost side of the ledger

Every index is a second copy of part of your data that must stay sorted. An INSERT into a table with five indexes writes to six structures; an UPDATE of an indexed column moves entries; a bulk load into heavily indexed tables is often faster if you drop the indexes first and rebuild afterwards. Indexes also consume memory in the buffer cache that other data could use.

So index for the queries you actually run. Start from slow queries (the slow-query log or pg_stat_statements), read the plan, add the smallest index that turns a SCAN into a SEARCH, then re-check. Drop indexes nothing uses, and remember that a composite (a, b) makes a separate index on (a) redundant. A primary key and a UNIQUE constraint already create an index for you, so do not duplicate them.

Best Practices (Do)
  • ✓Index foreign keys and the columns you filter, join or sort on in frequent queries.
  • ✓Verify with the query plan before and after, on realistic data volume.
  • ✓Order composite columns: equality first, range or sort last.
Common Pitfalls (Don't)
  • ✕Do not index every column 'just in case': writes slow down and the optimiser has more bad choices.
  • ✕Do not wrap an indexed column in a function inside WHERE.
  • ✕Do not trust a plan produced on a tiny development table.

Check your understanding

Four questions on the ideas behind the syntax.

Suggested Quiz
Question 1 of 4

Why is a B-tree node large (hundreds of keys) rather than binary (two children)?

Quick Syntax & Reference Sheet

Concept / RuleSyntax / Usage
Create an indexCREATE INDEX idx_orders_customer ON orders(customer_id);
Composite indexCREATE INDEX idx ON orders(customer_id, status, created);
Read the plan (SQLite)EXPLAIN QUERY PLAN SELECT ...;
Read the plan (PostgreSQL)EXPLAIN ANALYZE SELECT ...;
Plan wordsSCAN = whole table; SEARCH USING INDEX = index lookup

Common Pitfalls & Developer Mistakes

✕ Mistake 1:

Adding an index without checking the plan

Why it happens: The optimiser may not use it, and you still pay for every write.

Correction: Run EXPLAIN before and after, on data of realistic size.
✕ Mistake 2:

Putting the range column first in a composite index

Why it happens: Everything after a range condition cannot be used for seeking.

Correction: Equality columns first, then the range or ORDER BY column.
✕ Mistake 3:

Applying functions or arithmetic to the indexed column

Why it happens: The stored order is of the raw value, not the computed one.

Correction: Rewrite as column OP constant, or create an expression index.

Frequently Asked Questions

How many indexes is too many?

There is no magic number. Count the cost: each index slows every write and uses memory. Keep an index only if a real query's plan depends on it, and review unused ones periodically.

Does a primary key need a separate index?

No. Primary key and UNIQUE constraints create their own index, so adding another on the same column is pure overhead.

Why did the optimiser ignore my index?

Common causes are a function on the column, a leading wildcard, low selectivity, a type mismatch, or an unused leftmost column. Read the plan, then test the same query with the filter simplified to see which change brings the index back.
Next: Database Systems & Storage Engines →
Article Tags:#Indexes#B-Tree#Query Plan#EXPLAIN#Performance#SQLite
Previous TopicUnion-Find (Disjoint Sets)
Next TopicDatabase Systems & Storage Engines
Was this lesson clear and helpful?

Discussion (0)

Sign in to ask questions and reply.
Loading discussion

Related discussions

Discuss in community