Composite and Covering Indexes: Why Column Order Matters

An index on two or three columns is where people get surprised: the same index makes one query instant and does nothing for another that filters on the same columns. The reason is column order, and the rule behind it, the leftmost prefix rule, is one of the most asked database questions in backend interviews. Add the covering index, one that answers a query without touching the table, and you have most of practical indexing.

The problem it solves

A table of bike docks has a city, a day and a bike count. The hot query asks for one city's rows, ordered by day. Without an index, the database reads every row, tests each, then sorts the survivors: a full scan and a sort on every request.

A single-column index on city removes the scan but not the sort, and each match still points back into the table for the returned columns. A well-chosen composite index removes all three costs: the scan, the sort and the table reads.

The intuition

A composite index on (city, day, bikes) is a sorted list of entries: by city, then by day within each city, then by bikes. Think of a phone book sorted by surname, then first name. That ordering decides everything.

• A filter on the leading column is a jump. All the Leeds entries sit together, so the engine binary-searches to the first one and reads until the city changes.
• A leading prefix works too. city = 'Leeds' AND day = 'Mon' narrows further inside the Leeds block.
• Skipping the leading column does not. Entries for Monday are scattered across every city, the way first names are scattered across a phone book. There is nowhere to jump.
• Equality before range. With city = ? and day > ?, both columns are used. With city > ? and day = ?, only the range on city is used, because inside a range of cities the days are no longer sorted.
• Order for free. Inside one city the entries are already in day order, so ORDER BY day needs no sort.

Covering is a separate idea. If every column the query needs is inside the index, the engine never opens the table. That is why the third column, bikes, is there: it does nothing for the filter and everything for the read.

The price is paid on writes. Every insert, update or delete also has to update every index, and a wide index is a second copy of much of the table.

Watch it run

The animation takes the lesson's three-row dock table and the query for Leeds, ordered by day. Nothing is indexed yet, so every row is read and tested, including the Hull row that was never going to match, plus a temporary b-tree for the ORDER BY. Then the composite index appears, sorted by its first column and then by the next. Leeds becomes a jump, not a search: its rows sit together, already in day order, so no sort is needed. The third column earns its place next: bikes is in the index, so the table is never opened. Then the filter changes to day alone. The entries are sorted by city first, so there is nowhere to jump, and the table is scanned. A prefix works, (city) or (city, day), but never the middle of the list. The last frame shows the bill: every write now updates the table and the index.

The code

Every plan below was printed by Python's sqlite3 module against SQLite 3.37; other engines and versions word their plans differently, but the shapes match. First the lesson's table, through each stage of the animation:

import sqlite3

db = sqlite3.connect(":memory:")
db.executescript("""
CREATE TABLE dock (city TEXT, day TEXT, bikes INT);
INSERT INTO dock VALUES ('Leeds','Mon',12), ('Leeds','Tue',9), ('Hull','Mon',4);
""")

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

q = "SELECT day, bikes FROM dock WHERE city = 'Leeds' ORDER BY day"
print(plan(q))            # ['SCAN dock', 'USE TEMP B-TREE FOR ORDER BY']

db.execute("CREATE INDEX i_city_day ON dock(city, day)")
print(plan(q))            # ['SEARCH dock USING INDEX i_city_day (city=?)']

db.execute("DROP INDEX i_city_day")
db.execute("CREATE INDEX i_cov ON dock(city, day, bikes)")
print(plan(q))            # ['SEARCH dock USING COVERING INDEX i_cov (city=?)']
print(db.execute(q).fetchall())                           # [('Mon', 12), ('Tue', 9)]
print(plan("SELECT bikes FROM dock WHERE day = 'Mon'"))   # ['SCAN dock']

Equality before range, and the sort that comes back when the ORDER BY skips a column:

print(plan("SELECT * FROM dock WHERE city = 'Leeds' AND day > 'Mon'"))
# ['SEARCH dock USING COVERING INDEX i_cov (city=? AND day>?)']
print(plan("SELECT * FROM dock WHERE city > 'H' AND day = 'Mon'"))
# ['SEARCH dock USING COVERING INDEX i_cov (city>?)']
print(plan("SELECT * FROM dock WHERE city = 'Leeds' ORDER BY bikes"))
# ['SEARCH dock USING COVERING INDEX i_cov (city=?)', 'USE TEMP B-TREE FOR ORDER BY']
print(plan("SELECT * FROM dock WHERE city = 'Leeds' AND day = 'Mon' ORDER BY bikes"))
# ['SEARCH dock USING COVERING INDEX i_cov (city=? AND day=?)']

The one exception to "the leading column is required". When the leading column has very few distinct values and the optimizer has statistics, SQLite can skip-scan: it runs one search per city. Without ANALYZE it does not know the column is that small:

big = sqlite3.connect(":memory:")
big.executescript("""
CREATE TABLE dock (city TEXT, day TEXT, bikes INT);
CREATE INDEX i_cov ON dock(city, day, bikes);
""")
big.executemany("INSERT INTO dock VALUES (?, ?, ?)",
                [(c, f"d{d:03}", d % 17) for c in ("Hull", "Leeds") for d in range(500)])
print(plan("SELECT bikes FROM dock WHERE day = 'd042'", big))   # ['SCAN dock']
big.execute("ANALYZE")
print(plan("SELECT bikes FROM dock WHERE day = 'd042'", big))
# ['SEARCH dock USING COVERING INDEX i_cov (ANY(city) AND day=?)']

What the index costs on disk: the same 20,000 rows with and without it, in pages:

def pages(with_index):
    c = sqlite3.connect(":memory:")
    c.execute("CREATE TABLE t (a INT, b INT, c TEXT)")
    if with_index:
        c.execute("CREATE INDEX t_abc ON t(a, b, c)")
    c.executemany("INSERT INTO t VALUES (?, ?, ?)", [(i % 97, i, "x" * 20) for i in range(20_000)])
    return c.execute("PRAGMA page_count").fetchone()[0]

print(pages(False), pages(True))          # 161 352

The rule, checked by brute force: for all six column orders and 40 seeded random filters each, the plan must use exactly the longest prefix the filter pins, and the rows must match a plain Python filter:

import random, re
from itertools import permutations

def leftmost_prefix(index_cols, filtered):
    used = []
    for col in index_cols:
        if col not in filtered:
            break
        used.append(col)
    return used

def used_columns(detail):
    m = re.search(r"USING (?:COVERING )?INDEX \w+ \((.*)\)", detail)
    return [part.split("=")[0] for part in m.group(1).split(" AND ")] if m else []

random.seed(25)
ok, cases = True, 0
for order in permutations("abc"):
    conn = sqlite3.connect(":memory:")
    conn.execute("CREATE TABLE t (a INT, b INT, c INT, v INT)")
    rows = [tuple(random.randint(0, 3) for _ in range(4)) for _ in range(60)]
    conn.executemany("INSERT INTO t VALUES (?, ?, ?, ?)", rows)
    conn.execute(f"CREATE INDEX ix ON t({', '.join(order)})")
    for _ in range(40):
        filtered = random.sample("abc", random.randint(1, 3))
        want = {col: random.randint(0, 3) for col in filtered}
        sql = "SELECT v FROM t WHERE " + " AND ".join(f"{c} = {v}" for c, v in want.items())
        ok &= used_columns(plan(sql, conn)[0]) == leftmost_prefix(order, filtered)
        brute = sorted(r[3] for r in rows if all(r["abc".index(c)] == v for c, v in want.items()))
        ok &= sorted(r[0] for r in conn.execute(sql)) == brute
        cases += 1
print(cases, ok)                           # 240 True

The complexity

• Search on a usable prefix: O(log n) to find the first entry, then one step per matching entry.
• Filter that skips the leading column: a full scan, O(n), unless the engine can skip-scan a tiny leading column.
• Covering read: no table lookup per row, which is often the largest saving on big result sets.
• Writes: every index adds its own O(log n) update to each insert, update and delete, plus its storage.

Where it goes wrong

• Putting the range column first. (day, city) for city = ? AND day > ? uses only the range. Equality columns go first.
• One index per column instead of one composite. Most engines use one index per table access; two single-column indexes rarely add up to one good composite.
• Covering everything. An index with every column is a second copy of the table that every write maintains. Cover the hot queries only.
• Functions on the column. WHERE lower(city) = 'leeds' cannot use an index on city; the SQL cheat sheet has the plan.
• Trusting a tiny test table. Plans change with row counts and statistics.

When it shows up in interviews

It usually arrives as a slow query: "this endpoint filters by user, sorts by time; what index would you add?" The answer is a composite with the equality column first, the sort or range column next, and the returned columns last if the read is hot. Follow-ups ask why it does not help a query on the second column alone, and what it costs writes. The groundwork is in SQL indexes explained. As of September 2026, PostgreSQL (11 and later) and SQL Server can also add non-key columns with INCLUDE, covering without widening the sort key.

How to say it in an interview

"A composite index is sorted by its first column, then the next. So it serves a filter on a leading prefix, and not one that skips the first column, apart from a skip-scan when that column has very few values. I put equality columns first, then the range or sort column, because after a range the later columns are no longer in order. If the query is hot, I add the returned columns so the index covers it. Every index slows writes, so I index the few queries that matter and check the plan."