The Index Already Knew the Answer

Last timeIndexes on More Than One Column

A lookup ends by fetching the row, and that fetch is most of the cost. If every column the query mentions is in the index, the fetch never happens.

Every lookup in this course has ended the same way: the index gives you a

pointer, and then you go and get the row. This lesson is about not doing that,

and it is the largest single saving available from index design.

The fetch you are paying for

Separate the two halves of a lookup. Finding the matching entries in the index

costs the depth of the tree, which the third lesson put at two or three reads

with the upper levels cached. Fetching the rows costs one read per row, each one

landing somewhere unpredictable in a table far too large to cache.

FIG 1The two halves of a lookup, with the second one dominating

: 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 one matching row the first term dominates and nothing here matters. For a thousand matching rows the second term is a thousand scattered reads against a handful of cached index reads, and the query is entirely the fetch. The whole of this lesson is about driving the second term to zero rather than making it faster.

FIG 2Query time against rows matched, with and without the fetch

seek, then fetch each rowanswered from the index alone

Both lines start at the same place, because both pay for the descent. They diverge at about twenty to one, which is the ratio between a scattered read into the table and reading the next entry in a page of the index that is already in hand. At a thousand rows the difference is ninety milliseconds against five, and the shape of the lower line is why people call this the biggest free win in index design.

Note what the ratio is made of. The fetches are scattered, so each one is a

separate request the storage device cannot anticipate, which is exactly the

distinction from the first lesson. The index entries are adjacent, so reading

the next one usually costs nothing at all because it is in the page already

read.

The lesson stops here

6 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

The Index Already Knew the Answer

The fetch you are paying for

6 more paragraphs to go

This is the reading half

Read alongside