SD4.2 · LESSON 2 OF 6

Composite indexes

Explain how indexes change work and how transactions protect application invariants under concurrency.

THE IDEA

Composite indexes

A composite index on (country, city, age) is sorted by country, then city, then age. A lookup can use the leading columns that the query constrains: country and city equalities use two; city alone uses none because the first column is free; a range ends the usable prefix. Column order is therefore a design decision, and the real behaviour of your database's optimizer should be confirmed with its execution plan.

Index on (country, city, age). Click a column to cycle its predicate: none → equals → range.

leading columns the index can use: 1 (country) the walk stopped at a gap or a range; the remaining predicates are filtered afterwards an index is judged by column order and the predicates you run, not by how many columns it has

Click the columns to change the predicates.

Predict first. Should a composite index's utility be judged only by its column count?

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

Find usable prefixes by hand, then write the prefix rule, an ORDER BY check and an index chooser.

Index on (country, city, age). Click a column to cycle its predicate: none → equals → range.

country = FR AND age = 30 city = Paris only country = FR AND city = Paris country =, city range, age = judge by column count? (yes/no)

To do: Composite index on (country, city, age). Query: country = FR AND age = 30. How many leading index columns can the lookup use? (city is missing, so the prefix stops after country)
To do: Query: city = Paris only. Usable leading columns?
To do: Query: country = FR AND city = Paris. Usable columns?
To do: Query: country = FR AND city is a RANGE AND age = 30. Usable columns (a range ends the usable prefix)?
To do: Should a composite index's utility be judged only by its column count? Type yes or no

Part 2. Do it in code

usable_prefix(cols, preds): cols is the composite index's column list; preds maps a column to "=" or "range". Walk the index columns from the left: a column with "=" is used and the walk continues; a column with "range" is used and the walk STOPS; a column without a predicate stops the walk. Return how many leading columns were used.
can_serve(cols, preds): True if at least one leading column is usable.
sort_served(cols, eq_cols, order_by): True if an ORDER BY on order_by (a list of columns) can be read straight from the index: after skipping the leading columns that are fixed by equality predicates (eq_cols), the next index columns must equal order_by in order.
best_index(indexes, preds): indexes is a dict name → column list; return the name with the most usable leading columns (ties: sorted name order), or None if none is usable.

def usable_prefix(cols, preds):
    pass

def can_serve(cols, preds):
    pass

def sort_served(cols, eq_cols, order_by):
    pass

def best_index(indexes, preds):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Should a composite index's utility be judged only by its column count?

ANoBYes

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.