Composite and covering indexes

A composite index covers more than one column, such as (customer_id, status). Its entries are sorted by the first column, then by the second within it. That sort order decides which queries the index can serve. A covering index goes one step further. It also stores extra columns, so the query can be answered from the index alone, with no visit to the table.

Both ideas come down to the same rule: the index is a sorted list, and it helps only when a query's filters and sorts match its order.

The leftmost-prefix rule

Build an index on (customer_id, status). It is sorted by customer_id, and within each customer by status. Then:

• WHERE customer_id = 5 can use it, because the first column is pinned.
• WHERE customer_id = 5 AND status = 'paid' can use it fully.
• WHERE status = 'paid' can't seek, since status is not the first column. Paid orders are spread across every customer's section.

Here is the plan from a real query planner, using SQLite:

import sqlite3
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE orders(id INTEGER PRIMARY KEY, customer_id INT, status TEXT, created_at TEXT, total INT)")
db.execute("CREATE INDEX idx_cs ON orders(customer_id, status)")

for q in ["SELECT total FROM orders WHERE customer_id = 5 AND status = 'paid'",
          "SELECT total FROM orders WHERE status = 'paid'"]:
    print([row[3] for row in db.execute("EXPLAIN QUERY PLAN " + q)])

Output:

['SEARCH orders USING INDEX idx_cs (customer_id=? AND status=?)']
['SCAN orders']

The first query seeks into the index. The second scans the whole table, because the index can't help. SQLite's wording differs from PostgreSQL's, but the idea holds everywhere.

Covering indexes

Now the query asks for total as well. The index has customer_id and status, but it doesn't have total. So the engine finds each matching entry, then goes to the table for every row to read total. That extra lookup is the expensive part. If the matching set is large, most of the work is random reads.

Add total to the index:

db.execute("CREATE INDEX idx_cov ON orders(customer_id, status, total)")
print([row[3] for row in db.execute("EXPLAIN QUERY PLAN SELECT total FROM orders WHERE customer_id = 5 AND status = 'paid'")])

Output:

['SEARCH orders USING COVERING INDEX idx_cov (customer_id=? AND status=?)']

Now the plan says COVERING INDEX. Every column the query needs is in the index, so the table is never touched. In PostgreSQL the same idea is INCLUDE, as in CREATE INDEX ... (customer_id, status) INCLUDE (total). The included columns are stored but not sorted, so they don't affect seeks.

What indexes cost

Every index is another B+tree. Each insert, update and delete must change every index on the row. Covering indexes make this worse, because they're wider. A table with eight indexes writes eight extra trees per row change. Before adding one, check how often the query runs and how selective its filter is.

Common mistakes

• Building (status, customer_id) when most queries filter on customer_id first. The leftmost column decides the seek.
• Adding a covering index to every query. Each one costs writes and space.
• Reading EXPLAIN output without checking the index's column order.

Check yourself

• Why can't WHERE status = 'paid' seek into an index on (customer_id, status)? Answer: entries are sorted by customer_id first, so paid orders are scattered across the whole index.
• Why is a covering index faster than a plain composite index for the same filter? Answer: it returns the needed columns from the index, so the engine skips a random table read for each matching row.

Key takeaways

• A composite index serves queries that match its leftmost columns.
• A covering index includes every column a query needs, so the table isn't read.
• Each index costs write time, cache space and storage.
• Read the plan, and check the column order before you add an index.

Further learning

Next, return to the storage engines overview to see how these indexes sit on the page and buffer design.