Secondary index service

The idea

A primary store is keyed by its primary key — the row id. Looking up order 7 is instant. But "find all orders with status = shipped" asks about a non-key attribute, and the only honest answer is to read every row and check. That full scan gets slower as the table grows.

A secondary index is a separate mapping from attribute value → list of primary keys. Maintain it on every write, and a query becomes one fast lookup instead of a scan. The two operations that matter: the index is updated on write, and looked up on read. It can even live as its own service kept in sync with the base store — which is where consistency lag sneaks in.

How it works

Every write touches two things: the base row and the index buckets for the attribute. On an update you must remove the id from the old value's bucket and add it to the new one — forgetting the removal leaves a stale entry. A read then skips the scan: look up the bucket, get the ids. A non-covering index stops there and fetches each row from the base table; a covering index also stores the needed columns, so it answers alone.

def write_status(id, new):           # insert / update
    old = base[id].status
    base[id].status = new            # 1. update base row
    if old is not None:
        index[old].remove(id)        # 2a. drop OLD bucket entry
    index[new].add(id)               # 2b. add to NEW bucket
    # covering index also stores the columns the query needs:
    # index[new][id] = {status:new, name:base[id].name}

def read_by_status(value):           # query on a non-key attribute
    ids = index.get(value, [])       # one lookup, no scan
    if COVERING:
        return ids                   # index already has the answer
    return [base[i] for i in ids]    # non-covering: N extra fetches

The index can live in the same store (maintained synchronously on the write path) or in a separate service fed by change events (maintained asynchronously). Async keeps writes fast but lets the index trail the base table for a moment — reads can briefly miss a just-written row.

Trade-offs

Watch out for

• Every extra index taxes every write. Indexes are not free reads — they are slower writes, paid forever.
• Stale reads under async maintenance. If the index trails the base table, a query can miss a row that was just written.
• Low-cardinality buckets get huge. An index on a status with three values means one bucket holds a third of the table — barely better than a scan.
• Forgetting to remove the OLD value's entry on update. The id lingers in its old bucket and the query returns rows that no longer match.
• Non-covering index = N extra fetches. A query matching 500 ids does 500 base-table reads after the lookup; a covering index avoids them.

Worked example

Order 7 ships. The write sets base[7].status = shipped, then maintains the index: remove 7 from index["pending"] (now [9]) and add it to index["shipped"] (now [5, 7, 11]). Later a query asks for status = shipped. With a non-covering index the lookup returns [5, 7, 11] and then fetches all three base rows — one lookup plus three reads. With a covering index those columns are already stored, so the same query answers from the index alone, never touching the base table. Both beat the alternative: a full scan of all five rows.

Check yourself