Lesson · Storage Engines and Indexes · The write side

The Write Cost of an Index

An index has to contain the column it answers questions about, so inserting a row changes every index on the table. With k of them an insert is k + 1 random writes and throughput is divided by k + 1 — not reduced by a percentage. A device doing ten thousand random writes a second carries two and a half thousand inserts a second once three indexes are on the table.

Open the interactive lesson Practice

writes per insert = k + 1 the row, and one page in every index inserts a second = device / (k + 1) device 10 000 random writes a second k = 0 1 write 10 000/s 100% k = 3 4 writes 2 500/s 25.0% k = 1 2 writes 5 000/s 50% k = 4 5 writes 2 000/s 20.0% ⌊10 000 / 2 500⌋ − 1 = 3 the most indexes a 2 500/s target allows

The exchange rate between a reader's index and a writer's throughput

Core ideas

What this lesson establishes

One addition and one division. The addition is obvious once it is said; the division is where the intuition goes wrong, because people expect a subtraction.

An insert touches every index

The row goes into the table and a key goes into each of the k indexes, so an insert is k + 1 writes. Nothing here depends on the index being clever or badly designed: a structure that answers questions about a column has to contain that column, and inserting a row changes that column.

The writes are random, and that is the expensive word

Each index is ordered on a different key, so where an insert lands in one index says nothing about where it lands in another. An insert that is perfectly sequential in the table is k scattered page writes elsewhere. That is why the cost is k + 1 random writes rather than k + 1 bytes, and it is the seek term of the first lesson arriving on the write side.

Throughput divides, it does not decrease by a percentage

If the device sustains D random writes a second, inserts run at D/(k + 1) and the share left is 1/(k + 1): 1/2 at one index, 1/4 at three, 1/9 at eight. The first index is the expensive one — it halves the write rate on its own — and every index after it costs less than the one before.

The material

k + 1 random writes, and the throughput that leaves

Why the first index is the expensive one, and how to turn a throughput target into a budget of indexes.

Definition · Write cost of an index

For a table carrying k secondary indexes, one insert performs k + 1 random writes: one for the row and one for each index page the new key lands on. On a device sustaining D random writes a second the insert rate is D/(k + 1), and the share of the bare rate is 1/(k + 1).

The same count holds for a delete, and an update counts once for every index whose key it changes.

Nothing in that definition is about how a particular engine is built. It is what it means for an index to be an index. A query planner can choose not to use an index; the writer has no such choice, because an index that skipped an insert would be wrong.

device 10 000 random writes a second indexes k 0 1 2 3 4 5 writes/insert 1 2 3 4 5 6 inserts/s 10 000 5 000 3 333 2 500 2 000 1 667 share 1 1/2 1/3 1/4 1/5 1/6 100% 50.0% 33.3% 25.0% 20.0% 16.7%

Read the last row from left to right. The first index costs fifty percentage points, the second seventeen, the third eight, the fourth five. 1/(k + 1) falls fastest at the start, so the question “can we afford one more index?” has a different answer depending on how many there already are — and the cheapest place to add one is a table that already has several.

Example · Three indexes on a ten-thousand-write device

k = 3 makes an insert 4 random writes, so a device doing 10 000 random writes a second does 2 500 inserts a second: 25% of its bare rate. The device did not get slower and the rows did not get bigger. Three quarters of its write budget is now being spent keeping indexes correct.

Turning a target into a budget of indexes

Run the division the other way. If the workload needs T inserts a second on a device doing D random writes a second, the writes available per insert are D/T and the indexes you can afford are ⌊D/T⌋ − 1. At D = 10 000 and T = 2 500 that is 3. Raise the target by twenty per cent, to 3 000, and it falls to 2: the relation is a floor, so it moves in whole indexes, and every index is free until the division crosses an integer.

This is the arithmetic that makes an index a decision rather than an optimisation. An index that serves a query is worth it; an index that was added years ago for a report nobody runs is still being written on every insert, and the way to see that is to price it in the units above rather than in megabytes.

One honest caveat. An engine that buffers index updates — a change buffer, or an LSM's memtable — converts some of these random writes into sequential ones performed later, which is exactly the trade “Write Amplification in LSM Trees” prices. The k + 1 is the count of index pages that must eventually be written. When they are written, and how many times each, is a different question with a much larger answer.

Interactive

The write cost of an index

k + 1 random writes an insert, and the throughput that leaves

Add indexes and watch the writer pay

Insert throughput is the device's random-write rate divided by k + 1, recomputed as you move k. Start at three indexes, then take k to zero one index at a time and watch which single step costs the most.

Indexes on the table (k)3

Random writes the device does a second10000

Inserts a second the workload needs2500

Random writes per insert—

Inserts a second—

Share of the bare rate—

Most indexes that still meet the target—

The writes are random because the indexes are ordered on different keys: an insert that is sequential in the table lands in a different place in every index. That is why the cost is k + 1 random writes and not k + 1 bytes.

Method

Pricing the write side of an index

Two of these steps are the calculation and two are the decision it is for.

Count the indexes, then add one

k secondary indexes and the table itself: k + 1 random writes an insert. Count every index that exists, not every index the queries use — the writer pays for all of them.

Divide the device's random-write rate

D/(k + 1) is the insert rate. Use the device's random write figure, not its sequential one; the two can differ by two orders of magnitude and only one of them is relevant here.

Hold it against what the workload needs

If the required insert rate is above D/(k + 1) the table is already over budget, and no amount of query tuning changes that: the shortfall is on the write path.

Invert it to get the index budget

⌊D/T⌋ − 1 is the most indexes a target of T inserts a second allows. It is a floor, so it steps: knowing where the next step is tells you how much headroom the table actually has.

Indexes, writes and throughput

Score 0 / 0

Choose the answer you can justify.

Three indexes on a device that does 10 000 random writes a second

One division, run across every plausible index count, and then run backwards from two throughput targets.

device 10 000 random writes a second indexes k 0 1 2 3 4 5 writes/insert 1 2 3 4 5 6 inserts/s 10 000 5 000 3 333 2 500 2 000 1 667 share 1 1/2 1/3 1/4 1/5 1/6 100% 50.0% 33.3% 25.0% 20.0% 16.7% cost of this index −50.0 −16.7 −8.3 −5.0 −3.3 points target 2 500 inserts/s ⌊10 000 / 2 500⌋ − 1 = 4 − 1 = 3 indexes target 3 000 inserts/s ⌊10 000 / 3 000⌋ − 1 = 3 − 1 = 2 indexes

The index that halves throughput is the first one. Not the fifth, not the tenth: going from none to one costs fifty percentage points and going from three to four costs five, because 1/(k + 1) falls fastest at the start. Anyone who has ever said “one more index will not hurt” was right, and was right for a reason that stops applying at k = 0.

Raising the required insert rate by twenty per cent, from 2 500 to 3 000, costs an index. The budget is a floor function, so it changes in whole indexes at the points where the division crosses an integer, and between those points a target can move a long way for free.

For a faded rehearsal, take a device that sustains 6 000 random writes a second and a workload needing 1 000 inserts a second. The supplied first move is that the answer is a floor: ⌊6 000/1 000⌋ − 1. Compute it, then state the insert rate you actually get at that many indexes and how much headroom is left over. Run the lab at your numbers before opening the quiz.

Common mistakes

Counting an index's cost in bytesAn index entry may be sixteen bytes, which sounds free. The cost is not the bytes — it is that those sixteen bytes are somewhere else on the device, and the device is rate-limited on how many separate somewhere-elses it can reach in a second. Price an index in random writes and the number stops looking free.

Believing an unused index is freeThe planner can ignore an index; the writer cannot. An index that no query has touched in a year is still one of the k, still one random write on every insert, and still dividing throughput. Dropping it is the only operation that removes it from the count.

Reading k + 1 as a penalty to subtractIt divides. Three indexes do not cost thirty per cent of the write rate; they cost seventy-five per cent of it, leaving 1/4. Anyone whose estimate of an index's cost is a small percentage has done a subtraction where the arithmetic is a division.

Check your understanding

✓

Finish when “add an index” sounds like a division rather than a favour.

You should be able to state the writes an insert costs from the index count, convert that into an insert rate on a stated device, and invert it to say how many indexes a throughput target allows.

Note: The k + 1 random writes here are exactly what a log-structured engine refuses to pay at insert time. The bill it pays instead is the subject of “Write Amplification in LSM Trees”: twenty-five bytes written for every byte handed over, on ordinary settings, and all of them sequential.