SD4.1 · LESSON 1 OF 6

Index access

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

THE IDEA

Index access

An index is an ordered structure that lets the database find rows without reading the whole table. A B-tree with effective fanout f over N rows has depth about log_f N: with a fanout of 100, a million rows need roughly 3 levels, at fanout 10 about 6. But an index only helps a query whose predicate and ordering match it: an index on email does nothing for a filter on name or for a contains-search.

rows1,000,000effective fanout100

There is an index on email. Choose the query:

filter on: operator:

depth ≈ log_100(1,000,000) → 3 level(s) WHERE email =: the index matches: read about 3 pages + the matching row

B-tree indexes support equality, ranges and ordered access on their columns. A predicate on another column, or one that cannot use ordering (a contains-search, a function on the column), gets no help.

Choose the filter column and operator.

Predict first. Does an index on one column guarantee every query becomes faster?

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

Estimate index depth by hand, then write a tiny planner that chooses index or scan.

rows1,000,000effective fanout100

There is an index on email. Choose the query:

filter on: operator:

depth ≈ log_100(1,000,000) → 3 level(s) WHERE email =: the index matches: read about 3 pages + the matching row

depth, 1M rows, fanout 100 fanout 10 rows scanned filtering by name one index speeds every query? (yes/no)

To do: A B-tree over 1,000,000 rows has effective fanout 100. Rough depth (levels to read), from log₁₀₀ N?
To do: With fanout 10?
To do: The same 1,000,000-row table has an index on email only. A query filters on name. Rows examined in the worst case?
To do: Does an index on one column guarantee every query becomes faster? Type yes or no

Part 2. Do it in code

tree_depth(n, fanout): the number of levels needed so that fanout ** levels >= n (at least 1). Use integer arithmetic. ValueError if fanout < 2 or n < 1.
index_usable(index_col, pred): pred is {"col", "op"}; an index on index_col helps only if pred['col'] == index_col and op is "=" or "range". Operators such as "contains" (LIKE '%x%') or "func" (a function applied to the column) cannot use a plain B-tree.
choose_plan(n_rows, fanout, index_col, pred, matches): returns {"method": "index" or "scan", "cost"}. Index: cost = tree_depth + matches. Scan: cost = n_rows. Use the index only when it is usable AND cheaper than a scan.
rows_examined(plan): plan['cost'].

def tree_depth(n, fanout):
    pass

def index_usable(index_col, pred):
    pass

def choose_plan(n_rows, fanout, index_col, pred, matches):
    pass

def rows_examined(plan):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Does an index on one column guarantee every query becomes faster?

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.