Composite and Partial Indexes

The previous lesson told index types apart, and every one of them was single-column and covered the whole table. Both restrictions are design decisions, not requirements.

An index can carry more than one column. This raises a new question: in which order are the columns written? The Reading Query Plans lesson measured this question’s answer for a single query, and one order won by a factor of forty-four thousand. That measurement leaves an incomplete impression, as if one order were correct and the other wrong. In reality each order serves one query set and leaves another one out in the cold. This lesson shows that balance with three queries, then relaxes the second restriction: an index that covers only part of the table.

Three Queries, Two Orders

Measurements run on library loan records. The setup below builds the two tables this lesson needs.

rm -f library.db
cat > setup.sql <<'SQL'
CREATE TABLE member (
  member_id         INTEGER PRIMARY KEY,
  name              TEXT NOT NULL,
  city              TEXT NOT NULL,
  registration_date TEXT NOT NULL
);
CREATE TABLE loan (
  loan_id      INTEGER PRIMARY KEY,
  book_id      INTEGER NOT NULL,
  member_id    INTEGER NOT NULL,
  pickup_date  TEXT NOT NULL,
  return_date  TEXT
);
INSERT INTO member (member_id, name, city, registration_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000)
SELECT n, 'Member ' || n,
       CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir'
                  WHEN 3 THEN 'Bursa' ELSE 'Konya' END,
       date('2015-01-01', '+' || (n % 3200) || ' days')
FROM counter;
INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000)
SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000),
       date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'),
       CASE WHEN n % 9 = 0 THEN NULL
            ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END
FROM counter;
SQL
sqlite3 library.db < setup.sql

Three queries are the three questions the loan desk actually asks. The first wants a member’s loan history in date order. The second counts every book picked up on a given day. The third wants a member’s records after a given date. The same two columns are indexed in two different orders, and all three queries are run against both indexes.

for cols in "member_id, pickup_date" "pickup_date, member_id"; do
  rm -f order.db
  sqlite3 order.db < setup.sql
  sqlite3 order.db "CREATE INDEX loan_composite ON loan($cols);"
  printf '=== index: (%s) ===\n' "$cols"
  sqlite3 order.db <<SQL
.print '-- Q1: member equality, ordered by date'
EXPLAIN QUERY PLAN SELECT loan_id FROM loan WHERE member_id = 4 ORDER BY pickup_date;
.stats vmstep
SELECT count(*) FROM (SELECT loan_id FROM loan WHERE member_id = 4 ORDER BY pickup_date);
.stats off
.print '-- Q2: date equality only'
EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE pickup_date = '2021-03-15';
.stats vmstep
SELECT count(*) FROM loan WHERE pickup_date = '2021-03-15';
.stats off
.print '-- Q3: member equality + date range'
EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE member_id = 4 AND pickup_date >= '2022-01-01';
.stats vmstep
SELECT count(*) FROM loan WHERE member_id = 4 AND pickup_date >= '2022-01-01';
SQL
done

=== index: (member_id, pickup_date) ===
-- Q1: member equality, ordered by date
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_composite (member_id=?)
17
VM-steps: 135
-- Q2: date equality only
QUERY PLAN
`--SCAN loan USING COVERING INDEX loan_composite
820
VM-steps: 6000831
-- Q3: member equality + date range
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_composite (member_id=? AND pickup_date>?)
8
VM-steps: 37
=== index: (pickup_date, member_id) ===
-- Q1: member equality, ordered by date
QUERY PLAN
`--SCAN loan USING COVERING INDEX loan_composite
17
VM-steps: 6000101
-- Q2: date equality only
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_composite (pickup_date=?)
820
VM-steps: 2471
-- Q3: member equality + date range
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_composite (pickup_date>?)
8
VM-steps: 2402957

Six measurements fit into one table. With column order (member_id, pickup_date), Q1 spent 135 steps, Q2 spent 6,000,831 steps, and Q3 spent 37 steps. With the reversed order, Q1 became 6,000,101, Q2 became 2,471, and Q3 became 2,402,957. No single order wins all three queries at once.

The reason is a single structural fact. A composite index sorts its entries first by the first column, and only for equal first-column values by the second. Such an order only helps if it provides an entry point, and the entry point always starts from the beginning.

The Leftmost Prefix Rule

The rule’s name is the leftmost prefix rule (leftmost prefix rule): a composite index provides an entry point only for the part of the column list starting from the left. An (a, b, c) index answers a condition on a, a condition on a and b, and a condition on a, b, and c; it does not answer a condition on b alone, or on b and c alone.

The measurements confirm this three times over. Q2 filters on the date alone: in the (member_id, pickup_date) index the date is the second column, so there is no entry point, and the plan says SCAN. The same query finishes in 2,471 steps in the (pickup_date, member_id) index, because it filters on the first column.

Q3 shows the rule’s second face. In the (member_id, pickup_date) index both conditions reach into the key — the plan states this by writing (member_id=? AND pickup_date>?) — and the work finishes in 37 steps. In the reversed order, only the date range becomes the key; the engine reads every record from 2022 onward out of the index and tests the member condition on each one individually. The result is the same eight rows, at a cost of 2.4 million steps.

From this the rule for choosing column order follows: columns filtered by equality go first, range and sort columns go last. Equality pins the position in the index to a single point and preserves the order of the following column; a range, once entered, scatters the order of the columns that follow it. In the (member_id, pickup_date) index, the date order is preserved separately for each member, which is why Q1 never needed a sort node.

Nothing forbids the same column from appearing in two indexes at once. The way to speed up all three queries above together is to build two composite indexes; the cost is that both trees are updated on every write. That cost is measured in the Index Maintenance lesson.

The Partial Index

The second relaxation concerns coverage. A partial index (partial index) is an index that holds only the rows of the table satisfying one condition. In the library this maps directly: most loan records are closed, and what the day-to-day work asks about is the open loans.

rm -f base.db full.db partial.db
sqlite3 base.db < setup.sql
cp base.db full.db
cp base.db partial.db
sqlite3 full.db    'CREATE INDEX loan_member ON loan(member_id);'
sqlite3 partial.db 'CREATE INDEX loan_open   ON loan(member_id) WHERE return_date IS NULL;'

echo "-- covered row count --"
sqlite3 base.db "SELECT count(*) AS all_rows FROM loan;
                  SELECT count(*) AS open_rows FROM loan WHERE return_date IS NULL;"
echo "-- page count --"
for db in base.db full.db partial.db; do
  printf '%-10s %s\n' "$db" "$(sqlite3 "$db" 'PRAGMA page_count;')"
done
for db in full.db partial.db; do
  printf '\n=== %s ===\n' "$db"
  sqlite3 "$db" <<'SQL'
.print '-- a members open loans'
EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE member_id = 4 AND return_date IS NULL;
.stats vmstep
SELECT count(*) FROM loan WHERE member_id = 4 AND return_date IS NULL;
.stats off
.print '-- the same members all loans'
EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE member_id = 4;
.stats vmstep
SELECT count(*) FROM loan WHERE member_id = 4;
SQL
done

-- covered row count --
2000000
222222
-- page count --
base.db    19161
full.db    24915
partial.db 19802

=== full.db ===
-- a members open loans
QUERY PLAN
`--SEARCH loan USING INDEX loan_member (member_id=?)
6
VM-steps: 103
-- the same members all loans
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_member (member_id=?)
17
VM-steps: 62

=== partial.db ===
-- a members open loans
QUERY PLAN
`--SEARCH loan USING INDEX loan_open (member_id=?)
6
VM-steps: 36
-- the same members all loans
QUERY PLAN
`--SCAN loan
17
VM-steps: 6000028

The size difference tracks the row ratio the index covers, exactly. The full index added 5,754 pages to the database (24,915 − 19,161), the partial index added 641 pages (19,802 − 19,161). The ratio 5,754 / 641 ≈ 9.0; the covered-row ratio is 2,000,000 / 222,222 = 9.0 as well. The partial index is small because it holds fewer rows — there is no other trick to it.

It wins on the plan side too. On the open-loan query the full index spent 103 steps, the partial index spent 36. The gain comes from two sources: the partial index’s tree is shorter, and because every entry coming out of the index already satisfies the condition, there is no need to return to the table and check return_date.

The Partial Index’s Boundary

The second measurement shows the cost. When the same member’s entire set of loans was asked for, the partial index could not be used and the query fell to a full table scan: 6,000,028 steps. This should be seen not as a shortcoming but as a consequence of the definition — the partial index has no entry at all for closed loans; using it would have produced a wrong answer.

The planner uses a partial index only when the query’s condition implies the index’s condition. In application terms this means a concrete writing discipline: a query that is meant to benefit from a partial index must carry that index’s condition in its own WHERE clause. If the query fetching open loans does not write return_date IS NULL, the index stays out of use.

The gain also exists on the write side, and it comes from the same ratio: inserting a row that falls outside the covered condition never touches the index at all.

rm -f write_full.db write_partial.db
sqlite3 write_full.db < setup.sql
cp write_full.db write_partial.db
sqlite3 write_full.db    'CREATE INDEX loan_member ON loan(member_id);'
sqlite3 write_partial.db 'CREATE INDEX loan_open   ON loan(member_id) WHERE return_date IS NULL;'
for db in write_full.db write_partial.db; do
  printf '%-14s ' "$db"
  sqlite3 "$db" <<'SQL'
.timer on
INSERT INTO loan (book_id, member_id, pickup_date, return_date)
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 200000)
SELECT 1 + ((n*7) % 200000), 1 + ((n*13) % 120000),
       date('2024-01-01','+'||(n%300)||' days'),
       date('2024-01-15','+'||(n%300)||' days')
FROM s;
SQL
done

write_full.db    Run Time: real 0.209 user 0.144466 sys 0.057085
write_partial.db Run Time: real 0.093 user 0.078058 sys 0.013362

Since every one of the two hundred thousand inserted rows is a returned record, not a single entry was written to the partial index; in this environment the insert ran a little over twice as fast. Run-time values depend on the environment and change on another machine; what is stable is the ratio between two runs on the same environment.

The partial index’s natural use case follows from this: columns with a strongly uneven distribution, where only the small side is queried. Open loans, records not yet cancelled, unprocessed queue rows, non-null fields. The reverse also holds: if queries ask about both sides of the coverage, a partial index is a misleading saving, because a second, full index will still be needed.

Summary

• A composite index sorts its entries first by the first column; it therefore provides an entry point only for column groups starting from the left — the leftmost prefix rule.
• The same two columns in two orders gave three different outcomes across three queries: no order won all three at once, since order is a choice of query set.
• When choosing column order, columns filtered by equality go first, range and sort columns go last; a range condition scatters the order of every column that follows it.
• A partial index holds only the rows satisfying its condition; in the measurement a full index added 5,754 pages while a partial index added 641 pages, and the ratio tracked the covered-row ratio exactly.
• A partial index is used only when the query’s condition implies the index’s condition; a query outside its coverage falls to a full table scan, and writing rows outside its coverage never touches the index at all.

Next Step

In this lesson one plan line came out with the word COVERING twice, and once without it. The difference looked silent but showed up in the numbers: the same index, the same member, 62 steps in one case and 103 in the other. The work in between is returning to the table for every entry found in the index. The next lesson measures that return and builds a way to remove it: putting every column the query asks for into the index. How the gain grows with the number of matching rows, which columns are worth adding to an index, and where this approach stops paying for itself will all be seen through measurement.