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