Write and storage costs
Explain how indexes change work and how transactions protect application invariants under concurrency.
THE IDEA
Write and storage costs
Every index is extra data that must be kept up to date. 10,000,000 rows with a 24-byte entry means 240 MB per index, 960 MB for four. Each insert writes the table row and one entry per index, so 1,000 inserts a second with four indexes is 5,000 writes a second. Reads get cheaper, ingestion gets slower: add an index only when the reads it speeds up outweigh the writes it slows.
An index is a second copy of part of the data that must be kept in step on every write. It makes some reads cheaper and every write dearer.
Predict first. Is an extra index free when the application mostly writes?
Chapter context
Databases execute concurrent requests against shared state. Fast lookup and correct updates are separate concerns: an index can improve a query while the application still loses updates or violates a cross-row rule.
TRY IT YOURSELF
Part 1. Do it hands-on
Cost indexes by hand, then write the cost model and a break-even test.
An index is a second copy of part of the data that must be kept in step on every write. It makes some reads cheaper and every write dearer.
- To do: A 10,000,000-row table gets a secondary index with 24 bytes per entry. Index size in bytes?
- To do: Four such indexes?
- To do: Each insert writes the table row and every index entry. At 1000 inserts/s with 4 indexes, writes per second?
- To do: Is an extra index free when the application mostly writes? Type yes or no
Part 2. Do it in code
- index_bytes(rows, entry_bytes, n_indexes): total bytes for the indexes.
- writes_per_insert(n_indexes): 1 table write + one per index.
- write_rate(inserts_per_s, n_indexes): total writes per second.
- worth_it(reads_per_s, saved_ms_per_read, inserts_per_s, cost_ms_per_index_write): True if the milliseconds saved per second by reads is greater than the milliseconds spent per second maintaining ONE more index.
- ingest_seconds(rows, n_indexes, rows_per_s_no_index): time to load `rows`, assuming throughput falls in proportion to writes per insert: rows / (rows_per_s_no_index / writes_per_insert).
Stuck, or something not working? You can come back to it any time.
CHECK YOUR UNDERSTANDING
Is an extra index free when the application mostly writes?
Chapter reference: math, worked example & code
This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.
Math and notation
For an idealized search tree with effective fanout f and N distinguishable leaves, log base f of N gives a rough depth scale. Actual pages, occupancy and row-pointer costs differ. For an optimistic update, change value and version only when the stored version equals the version read by the caller.
Worked example
Two callers read count=10 at version 1 and each intends to increment. Unconditional writes of 11 lose one increment. With an atomic expected-version check, the first writes 11/version 2; the second stale attempt is rejected. After rereading, it can write 12/version 3. The model below demonstrates the condition, not database transaction implementation.
Reference code
The following example uses the Python standard library and does not call a remote service.
state={'count':10,'version':1}
def update(expected):
if state['version'] != expected: return False
state['count']+=1
state['version']+=1
return True
assert update(1)
assert not update(1)
assert update(2)
assert state == {'count':12,'version':3}
Python examples are provided for study and local execution; this page does not execute Python.
Common mistakes
A transaction's isolation level matters. A unique application-side check is race-prone without a database-enforced invariant. Index depth estimates are not actual query-latency measurements.