The Conditions No Index Can Rescue
Last timeA Sorted Copy With a Pointer Back
An index is useful only when the thing being compared is the thing that was stored in order. A surprising number of ordinary-looking conditions quietly break that, and one does not break it at all.
An index exists and applies to the column being filtered, and the query still
reads the whole table. This is the most common confusing moment in the subject,
and it has two completely different explanations that need to be told apart
before anything useful can be done.
Either the condition has been written in a way that makes the index unusable, in
which case there is a rewrite that fixes it. Or the index is perfectly usable and
the database has decided not to use it, in which case the database is probably
right and the rewrite will make things worse.
When the condition stops referring to the column
The index holds the column's values, sorted. It can therefore answer questions
about those values. It cannot answer questions about anything computed from them,
because it has no idea what that computation would produce or in what order.
So a condition that compares the column directly is fine, and a condition that
wraps it in a function is not. Taking the lower case of a name, extracting the
year from a timestamp, adding a number to a column before comparing it,
concatenating two columns, or rounding a value all have the same effect: the
sorted copy becomes irrelevant and every row must be computed and tested.
The remedy has two forms. Move the computation to the other side of the
comparison, which is usually possible for arithmetic and for date ranges, so that
the column stands alone. Or build the index on the expression itself, so that the
sorted copy holds exactly the values being compared.
| rows examined | can the index be used, o | milliseconds | how obvious is the probl | |
|---|---|---|---|---|
| the column compared dire | 1 | 4 | 1 | 4 |
| a function applied to th | 9000000 | 1 | 4000 | 1 |
| a pattern anchored at th | 20 | 4 | 2 | 3 |
| a pattern beginning with | 9000000 | 1 | 4000 | 2 |
| the column compared agai | 9000000 | 1 | 4000 | 1 |
Patterns and the left-hand edge
Sorted order groups things by their beginnings. Everything starting with the same
few characters sits together, which is why a prefix search is a range and costs
one descent plus a walk.
A pattern beginning with a wildcard has no fixed beginning, so the matching
entries are scattered through the whole index with nothing contiguous about them.
There is no range to descend to, and the only honest way to answer is to look at
everything. This is not a defect in any particular database; it follows from
sortedness itself, and no amount of index tuning will change it.
What changes it is a different kind of index. Structures built for text search
hold the pieces of each value rather than the whole value, so they can answer
questions about the middle of a string, at the cost of being larger and more
expensive to maintain.
The lesson stops here
3 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 planThe contentsThis 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