Covering Indexes

The previous lesson’s final measurement gave the same index, the same member, and the same query shape two different numbers: 62 steps and 103 steps. The only difference between them was that one plan carried the word COVERING and the other did not.

That word describes exactly one thing. If the index carries every column the query asks for, the database produces the answer directly from the index. If it does not, the engine must return to the table for every entry found in the index and read the missing column. This lesson measures how expensive that return is — and the measurement itself produces a finding about which tool should be used to make it.

The Trace of the Return

Measurements run on library loan records. A monthly report question has been chosen: how many distinct books were picked up within a given month? The query touches two columns — pickup_date for filtering, book_id for counting.

rm -f base.db narrow.db covering.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 base.db < setup.sql
cp base.db narrow.db
cp base.db covering.db
sqlite3 narrow.db   'CREATE INDEX loan_pickup       ON loan(pickup_date);'
sqlite3 covering.db 'CREATE INDEX loan_pickup_book ON loan(pickup_date, book_id);'

echo "-- page count --"
for db in base.db narrow.db covering.db; do
  printf '%-13s %s\n' "$db" "$(sqlite3 "$db" 'PRAGMA page_count;')"
done
for db in narrow.db covering.db; do
  printf '\n=== %s ===\n' "$db"
  sqlite3 "$db" <<'SQL'
EXPLAIN QUERY PLAN SELECT count(DISTINCT book_id) FROM loan
  WHERE pickup_date BETWEEN '2021-03-01' AND '2021-03-31';
.stats vmstep
SELECT count(DISTINCT book_id) FROM loan
  WHERE pickup_date BETWEEN '2021-03-01' AND '2021-03-31';
SQL
done

-- page count --
base.db       19161
narrow.db     28507
covering.db   30394

=== narrow.db ===
QUERY PLAN
|--USE TEMP B-TREE FOR count(DISTINCT)
`--SEARCH loan USING INDEX loan_pickup (pickup_date>? AND pickup_date<?)
25441
VM-steps: 203543

=== covering.db ===
QUERY PLAN
|--USE TEMP B-TREE FOR count(DISTINCT)
`--SEARCH loan USING COVERING INDEX loan_pickup_book (pickup_date>? AND pickup_date<?)
25441
VM-steps: 178101

The plan difference is as expected: because the second index also carries the book_id column, the plan says COVERING INDEX. The size difference is also as expected: the covering index carries one extra column, so it added more pages to the database.

The step count defeats the expectation. From 203,543 to 178,101 is only twelve percent. Is this the true cost of twenty-five thousand table returns for twenty-five thousand rows?

The Right Measure

The step count tallies the virtual machine instructions the query executes. Reading one row from the table is a single instruction — behind that instruction sits a disk page being located and read, but the counter does not see that. Put differently: the step count counts operations performed, not pages touched.

The distinction drawn in the Processor Cache lesson returns here. The same instruction count can take a hundred times longer depending on where the data sits. The measure needs to change: page miss count. The run below executes the same query at three different widths and, for each run, records both the page miss count and the elapsed time. Each query runs in a separate process, so the counters start from a cold cache.

echo "-- matching row counts --"
sqlite3 base.db "SELECT '1 day', count(*) FROM loan WHERE pickup_date BETWEEN '2021-03-15' AND '2021-03-15'
UNION ALL SELECT '1 month', count(*) FROM loan WHERE pickup_date BETWEEN '2021-03-01' AND '2021-03-31'
UNION ALL SELECT '1 year', count(*) FROM loan WHERE pickup_date BETWEEN '2021-01-01' AND '2021-12-31';"

for range in "2021-03-15 2021-03-15" "2021-03-01 2021-03-31" "2021-01-01 2021-12-31"; do
  start=${range% *}; end=${range#* }
  printf '\n### %s .. %s\n' "$start" "$end"
  for db in narrow.db covering.db; do
    printf '%-13s ' "$db"
    sqlite3 "$db" <<SQL 2>&1 | grep -E 'Page cache misses|Run Time' | tr '\n' ' '
.stats on
.timer on
SELECT count(DISTINCT book_id) FROM loan WHERE pickup_date BETWEEN '$start' AND '$end';
SQL
    echo
  done
done

-- matching row counts --
1 day|820
1 month|25441
1 year|299547

### 2021-03-15 .. 2021-03-15
narrow.db     Page cache misses:                   874 Run Time: real 0.002 user 0.000648 sys 0.000831
covering.db   Page cache misses:                   8 Run Time: real 0.000 user 0.000125 sys 0.000042

### 2021-03-01 .. 2021-03-31
narrow.db     Page cache misses:                   26241 Run Time: real 0.032 user 0.017051 sys 0.014478
covering.db   Page cache misses:                   147 Run Time: real 0.005 user 0.004910 sys 0.000164

### 2021-01-01 .. 2021-12-31
narrow.db     Page cache misses:                   309414 Run Time: real 0.371 user 0.207453 sys 0.163681
covering.db   Page cache misses:                   1686 Run Time: real 0.061 user 0.058585 sys 0.001783

The numbers show a single pattern. In the narrow index, page miss count tracks the number of matching rows almost one to one: 874 pages for 820 rows, 26,241 pages for 25,441 rows, 309,414 pages for 299,547 rows. In the covering index the same three counts are 8, 147, and 1,686.

The source of the ratio is the physical storage layout. Because the index is sorted by date, matching entries sit next to each other, and one page read brings back hundreds of entries. The return to the table, on the other hand, means landing at random points in a structure laid out by loan_id order; two loan entries that sit side by side in the index are far apart in the table. Every row costs a separate page read, the same page gets read more than once, and the buffer pool cannot hold onto this access pattern.

Time confirms it: in this environment, the yearly query ran at 0.371 seconds against 0.061 seconds, roughly a sixfold difference. Run times depend on the environment and change on another machine; what is stable is the page-miss ratio — in the yearly query, 309,414 / 1,686 ≈ 184.

From here a rule of measurement discipline follows: when evaluating the effect of a plan change, the measure being used has to see the work that is actually changing. Step count measures a query’s logic well; it does not measure disk access.

The Limit of Covering

A covering index is not free. Every column placed in it is repeated in each of the two million entries. The measurement below builds the same index at four different widths and compares the page count of each against the table itself.

rm -f width.db
sqlite3 width.db < setup.sql
sqlite3 width.db <<'SQL'
.mode column
.headers on
CREATE INDEX d1 ON loan(pickup_date);
CREATE INDEX d2 ON loan(pickup_date, book_id);
CREATE INDEX d3 ON loan(pickup_date, book_id, member_id);
CREATE INDEX d4 ON loan(pickup_date, book_id, member_id, return_date);
SELECT name AS object, count(*) AS pages FROM dbstat
WHERE name IN ('loan','d1','d2','d3','d4') GROUP BY name ORDER BY pages;
SQL

object  pages
------  -----
d1      9346
d2      11233
d3      13089
d4      17968
loan    18013

The four-column index reaches 17,968 pages; the table itself is 18,013 pages. As every column a query needs gets added to the index, the index approaches becoming a sorted copy of the table. At that point covering is no longer an optimization but a second copy of the data: space doubles, every write goes to two structures at once, and the backup grows in size.

The selection criterion follows from this. Columns worth covering are the ones that appear in the query’s result but are narrow relative to the rest of the table. Adding the single identifier column needed for a count paid 1,887 pages and returned a 184-fold gain in page misses; adding a long text column reverses that arithmetic.

The second criterion is the query’s width. On a query filtering a single day, the gain went from 874 pages to 8 pages — a small saving in absolute terms. The same index prevented reading three hundred thousand pages on the yearly report. A covering index is worth building for queries that match many rows and ask for few columns; there is no need to build one for single-row lookups, because the return there is already a single page.

Covering and Order Together

A covering index’s column list does two jobs at once, and the two can conflict. The leftmost prefix rule established in the previous lesson decides column order for filtering and sorting; covering asks only that the column exist, not where it sits.

The two requirements are combined in one list: filtering and sorting columns go first, where their order matters, and columns added only because they appear in the result go last. The (pickup_date, book_id) index is exactly this — the date gives the entry point, the book identifier is only carried along. The reverse order, (book_id, pickup_date), carries the same columns and occupies the same space, but gives no entry point for the date range.

Some engines carry this distinction into their syntax and offer a notation that keeps carried-only columns outside the index key; such a column does not participate in the uniqueness check and takes no place in the ordering. The name and existence of this notation is engine-specific; the concept is the same — separating columns that are the key from columns that are only carried.

Summary

• A covering index is one that carries every column the query asks for; it shows up in plan output with the word COVERING and reports that the table was never returned to.
• The cost of returning to the table does not show up in step count: on the monthly query, step count dropped by twelve percent while page misses fell from 26,241 to 147.
• Page misses in a narrow index track the number of matching rows almost one to one, because the return to the table is random access; in a covering index the read proceeds in order within the index.
• The gain grows with the number of matching rows: 874 pages against 8 on a single-day query, 309,414 pages against 1,686 on a yearly query.
• As columns are added, the index approaches a copy of the table; the four-column index reached 17,968 pages against the table’s own 18,013 pages.

Next Step

The three lessons so far treated the index as a pure gain and measured its cost only by the space it occupied at the moment it was built. An index does not stay where it was built: rows get deleted and updated, gaps accumulate in the index tree, the file grows, and every new index stretches the write path a notch further. The next lesson measures that side — how much an index bloats after deletion, what a rebuild recovers, and how much each index added to a table lengthens insert time.