Basis Lab

Answers · Where the data lives

What does it mean for an index to cover a query?

In shortA covering index holds every column a query needs, so the database can answer from the index without reading the table row.

An index covers a query when every column the query mentions is present in the index, so the database can answer from the index alone and never fetch the row. The index must not only find the matching entries; it must also carry every value the query returns, filters on, orders by or groups by.

FIG 1The cost of a lookup split into descent and fetch
reads from storage for the whole query
reads to walk down the index, two or three in practice
number of rows the filter matches
share of row fetches already in the cache, usually small for a large table
For a handful of rows the fetch is invisible. For a thousand matched rows it is the query: m row fetches, each a scattered read into a table too large to cache, against d reads down a tree whose upper levels are usually cached.

Put numbers on it. A query matches m=1000m = 1000 rows, the descent takes d=3d = 3 reads, and 5 per cent of row fetches hit cache, so h=0.05h = 0.05. Then r=3+1000×0.95=3+950=953r = 3 + 1000 \times 0.95 = 3 + 950 = 953 reads. The tree walk is three reads. The fetch is 950, so 950 of the 953 reads are the part that a covering index removes. If every column is in the index, the same query descends in three reads and then reads the matching leaf entries. At 100 entries per leaf page, 1000 entries occupy 10 pages, so the total is 3+10=133 + 10 = 13 reads. That is 953/13≈73953 / 13 \approx 73 times fewer reads. The exact ratio depends on cache hit rate and entry size, but the structure is fixed: the descent is small and the fetch is proportional to the rows.

r=3+1000×(1−0.05)=953 readsrcovered=3+1000100=13 readsr = 3 + 1000 \times (1 - 0.05) = 953 \text{ reads} \qquad r_{\text{covered}} = 3 + \frac{1000}{100} = 13 \text{ reads}

The natural guess and why it fails

The natural guess is that an index is only a pointer to the row, so a lookup always ends with a row fetch. That is true for an index that holds only the key columns. It is false for an index that carries extra columns in its leaf entries. The carried values are stored beside the key, in the order the key imposes, so they can be returned without being searchable. The test is all or nothing. If a query selects two indexed columns and sorts by a third that is not in the index, it is not covered: the sort needs the missing column, so the database fetches every matching row. The same happens if the select list names one column the index does not hold, even when every filter column is indexed. A single missing output column brings back the full fetch for every matching row. An index on customer, then date, carrying amount answers a sum of amounts for a customer over a date range. It does not answer a list of delivery addresses for that customer, because delivery address is not in the index.

Key columns and carried columns

An index on customer, then date, carrying amount shows the distinction. Customer and date are key columns: they are sorted, so the index can be sought on customer and ranged on date. Amount is carried: it is present in the leaf entry but not part of the ordering. Put a column in the key if you will filter, order or group by it. Carry a column if you only need it in the answer. A key column widens every level of the tree and can lower the branching factor, which can add a level to the descent. A carried column widens only the bottom level, where the entries live anyway, so the descent is unaffected and only the leaf count grows.

It is not free. Suppose the index is 100 bytes per entry: 22 bytes for key columns, 48 bytes for carried columns, 18 bytes for row pointers and 12 bytes for page overhead and free space. The carried columns are 48 of those 100 bytes, so nearly half the index is data that exists only to avoid a fetch. Remove them and the same entry is 52 bytes, so the index is a little over half its size. Every write pays for the larger version: more pages to cache, more bytes written when a page splits, and a new index write whenever a carried column changes. That is worth doing for a query run constantly over columns that rarely change. It is not worth doing for a monthly report, or for a table whose carried columns are updated all day.

Two cases are easy to miss. Counting rows for a filtered set needs no output columns at all, so it is covered by any index that serves the filter. Summing or averaging a column is covered if that column is in the index, which is the single most valuable use of the idea, because aggregate queries are the ones that touch the most rows.

One caveat belongs to real systems rather than to the arithmetic. An index entry does not by itself prove that the row is visible to the current transaction. Databases keep a separate structure to answer that question cheaply. When that structure cannot answer, the database reads the row after all, so an index-only answer is usually conditional rather than guaranteed. It works well on tables that are mostly read and degrades on tables under heavy write load until maintenance catches up. The trade also reverses when the carried columns change often or the query is rare: then the write cost on every change outweighs the fetch saved on the occasional read.

Worth keeping

  • An index covers a query only when every column the query mentions is in the index, including selected, filtered, ordered and grouped columns.
  • If one needed column is missing, the database must fetch each matching row, so most of the saving is lost.
  • Carried columns make the index larger on every write, so covering is a trade for frequent queries, not a default.

Where this goes next

This question is one step of How an Index Actually Works, a course that works through its subject from the beginning. The page that teaches this part of it is Answering Without Touching the Table, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that pageThe whole course

Other questions people ask about this

  1. Why can't a hash index handle a range query like created_at > '2024-01-01'?A hash index finds only exact keys: it scrambles key order to pick a bucket, so there is no way to seek to the start of a range and walk forward.
  2. How does a B-tree find one row among millions in just a few reads?A B-tree finds a row by reading only a few pages: each page holds hundreds of pointers, so the tree stays three or four levels deep.
  3. Why is a log-structured store faster for writes than a B-tree?Because a B-tree finds a page and then rewrites it in place for every insert, while a log-structured store only appends, and appending in order is far cheaper than jumping about the disk.
  4. Why does inserting a single row sometimes cost many page writes?A row insert usually writes one page, but when the target page is full it splits in half and the split can climb to the root, so rare inserts write several pages for each index.
  5. Why is the date off by one day after I save it and read it back?You saved a calendar date as if it were a precise moment, so showing it in another time zone can move it to the day before or after.
  6. Is UTF-8 the same thing as Unicode, or what's the difference?No: Unicode assigns a number to each character, while UTF-8 is a way of writing those numbers as bytes, using one to four bytes per character.

Read alongside