--- title: 'Composite and Partial Indexes' source: 'https://academia.sh/en/courses/database-administration/composite-and-partial-indexes' course: 'Relational Database Administration' language: en updated: '2026-08-23T07:00:41+00:00' license: 'CC BY-SA 4.0' --- # Composite and Partial Indexes The effect of column order in a composite index across three separate queries, the leftmost prefix rule, the page-count size gain of a partial index, and what happens on a query it does not cover. 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. ```sh 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. ```sh 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 <= '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. ```sh 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. ```sh 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.