AdvancedLesson 21 of 306 min read

How Databases Choose a Path: Composite Indexes

See which queries can use a two-column index, learn the leftmost prefix rule and selectivity, and choose column order from your real queries.

In this lesson you will

  • Explain how a composite index is sorted
  • Apply the leftmost prefix rule
  • Understand selectivity
  • Choose index column order from real queries

About 28 minutes

“I added an index and nothing changed”

Dev adds an index to Maya’s events table and proudly runs a query. It is no faster. He looks at the plan and the database is still reading every row. The index exists, but the query cannot use it. This happens to nearly everyone, and the cause is nearly always the same: a composite index, one built over several columns, only helps queries that fit its shape. At the Advanced level, understanding why is the difference between guessing and designing.

How a composite index is sorted

An index on two columns, user first and kind second, is a sorted list. It is sorted by user. Within each user, it is sorted by kind. Think of a phone book sorted by surname, then first name. It is easy to find everyone called Patel, and easy to find Dev Patel. It is useless for finding everyone called Dev, because the Devs are scattered through the whole book. This picture gives the famous leftmost prefix rule: a query can search the index efficiently when it constrains the leading columns, in order from the left, with no gaps, and the useful part of the index usually ends at the first range condition. Equality tests go first, then ranges.

Four queries, four plans

The program builds a table of 20,000 events, with 400 different users and three kinds of event, and creates one index on user and kind. Then it asks the database for its plan for four queries. The plan wording is SQLite’s, and other databases word theirs differently, but the lesson holds. After that it adds a second index in the opposite order and asks again.

import sqlite3

db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE events (id INTEGER PRIMARY KEY, user_id INTEGER, kind TEXT, created INTEGER)")
kinds = ["view", "buy", "refund"]
db.executemany("INSERT INTO events VALUES (?, ?, ?, ?)",
               [(i, i % 400, kinds[i % 3], 1000 + i) for i in range(1, 20001)])
db.execute("CREATE INDEX idx_user_kind ON events (user_id, kind)")

def plan(where):
    return db.execute("EXPLAIN QUERY PLAN SELECT created FROM events WHERE " + where).fetchone()[3]

tests = [
    ("both columns", "user_id = 7 AND kind = 'buy'"),
    ("first column only", "user_id = 7"),
    ("second column only", "kind = 'buy'"),
    ("first, then a range", "user_id > 390 AND kind = 'buy'"),
]
rows = {}
for label, where in tests:
    rows[label] = db.execute("SELECT COUNT(*) FROM events WHERE " + where).fetchone()[0]
    print(f"{label}: {plan(where)}")
print("rows found:", rows)
db.execute("CREATE INDEX idx_kind_user ON events (kind, user_id)")
print("after a second index, second column only:", plan("kind = 'buy'"))
same = all(db.execute("SELECT COUNT(*) FROM events WHERE " + w).fetchone()[0] == rows[l] for l, w in tests)
print("answers unchanged by the new index:", "yes" if same else "no")
both columns: SEARCH events USING INDEX idx_user_kind (user_id=? AND kind=?)
first column only: SEARCH events USING INDEX idx_user_kind (user_id=?)
second column only: SCAN events
first, then a range: SEARCH events USING INDEX idx_user_kind (user_id>?)
rows found: {'both columns': 17, 'first column only': 50, 'second column only': 6667, 'first, then a range': 150}
after a second index, second column only: SEARCH events USING INDEX idx_kind_user (kind=?)
answers unchanged by the new index: yes

Look at the four plans. A query on both columns gets ‘SEARCH events USING INDEX idx_user_kind (user_id=? AND kind=?)’, so both columns are used. A query on the first column alone gets ‘SEARCH events USING INDEX idx_user_kind (user_id=?)’, the leading column only. A query on the second column alone gets ‘SCAN events’: the database reads the whole table, because the index starts with the user, and the kind values are scattered across all users. The query with a range on the first column and an equality on the second gets ‘SEARCH events USING INDEX idx_user_kind (user_id>?)’, which uses only the first column, since the range ends the useful prefix. Rows found, as a cross-check: 17 for both columns, 50 for one user, 6667 for the kind alone and 150 for the range query.

Adding a second index with the columns in the other order changes the plan for the kind-only query to ‘SEARCH events USING INDEX idx_kind_user (kind=?)’. The answers stayed the same, as they must, because an index changes how the work is done, never the result. But look at the numbers: the kind alone matches 6667 rows out of 20,000, about a third of the table. An index is far less useful when a condition matches such a large share of rows, and a database may rightly decide to scan anyway. This idea is called selectivity: a column with many different values, such as the user, narrows the search a lot, and a column with few different values, such as the kind, does not.

Choosing the order

  • Look at the real queries first, and list the columns used in WHERE, JOIN and ORDER BY.
  • Put columns tested with equality first, and a range column after them.
  • Among equality columns, columns that narrow the search most often make the best leading column, but the shape of your queries matters more than a rule.
  • One composite index can replace several single-column indexes, and every index costs write speed and space.
  • Check the plan after the change, as lesson 19 taught, and drop an index that is not used.

Be aware that databases vary. Some can use an index even when a leading column is missing, with a technique often called a skip scan, and some planners combine single-column indexes. The leftmost prefix rule is the safe mental model, and your own EXPLAIN output is the final word.

Common mistake: index columns in the wrong order

Creating an index in the order that feels natural, and never checking the plan. If the first column is not in the query, the index may be ignored completely.

Made-up sample data, SQLite plans

The events table is made up and the plans came from SQLite. Plan wording, skip scans and index choices differ between databases and versions, so run your own EXPLAIN. Index advice is general, and the right design depends on your workload.

Take one table you use. Write the three most common filters on it, and decide the one composite index that would serve the most of them. Then check which of the three would still scan.

Practice for this lesson

Check what you learned

Five quick questions. Pick an answer and you will see straight away whether it is right and why.

What is the leftmost prefix rule?

  1. An index can only have two columns
  2. A query uses a composite index well when it constrains the leading columns in order
  3. The last column always matters most
  4. Indexes work from right to left

The user-first index served user queries but not kind alone.

Why did the kind-only query scan the table?

  1. The kind column had no values
  2. The table was too small
  3. SQLite cannot index text
  4. The index starts with the user column, which that query did not use

Kinds are scattered across all users in that index.

What does a range condition do to the usable index prefix?

  1. It ends the useful prefix at that column
  2. It extends it
  3. It removes the index
  4. Nothing

The range query used only the user column.

What is selectivity?

  1. How fast a disk is
  2. How big an index is
  3. How much a condition narrows the rows
  4. How many users exist

The kind alone matched about a third of the table.

What stays the same when you add an index?

  1. The plan
  2. The write speed
  3. The storage used
  4. The answer to the query

An index changes how the work is done, not the result.

Summary

  • A composite index is sorted by its first column, then its second.
  • Queries must constrain leading columns in order.
  • A range ends the useful prefix.
  • Low-selectivity columns help little; check the plan.

Next lesson

Lesson 22 covers transactions: ACID, isolation and locks.

Questions

Which column should go first?

Start with the columns your real queries test with equality, and think about how much each narrows the search. Always check with EXPLAIN on real data.

Can a database use an index when the first column is missing?

Some can, with techniques such as skip scans, but you cannot count on it. Treat the leftmost prefix rule as the safe model.

Are these plans what my database will show?

The idea will match, but the wording and details differ. Run EXPLAIN in your own system.

Progress is saved in this browser.