skaidb v0.320.9

Global (value-sharded) secondary indexes — internals

A regular secondary index is local per node: each node indexes only its own shard, so a non-PK indexed read scatters IndexScan to every member, unions candidate keys, and quorum re-reads them. A global index instead places its entries on the ring by indexed value, so an equality probe routes to the one replica set owning that value — a single replica-set round-trip, like a PK point read, regardless of cluster size.

For the user-facing guide (syntax, when to choose global over local, query shapes) see INDEXING.md. This document covers the mechanism.

Measured on a 3-member RF<members cluster (2,000 probe pairs, exact correctness parity with the scatter path): routed probes win reads ~16% median / ~12% p95 over the local-index scatter; writes pay ~20–27% batch latency for the companion entry writes. At 2 members the two are at parity (the candidate re-read dominates); the routing win grows with member count, since scatter cost scales with members and the probe does not. On a full-copy cluster (RF ≥ members) a local index already answers without fan-out and a global index buys nothing.

Data model: the index is a table

A global index is an internal row table whose rows are the index entries:

key   = u16 BE prefix_len ‖ values_prefix ‖ row_key
value = (empty)

The PK tail makes entries unique per row and lets a probe enumerate candidate PKs by scanning the [values...] prefix range. Because it is a table, it inherits every existing mechanism unchanged: ring placement + replication + hints (replicas_for on the entry key), LWW via HLC, anti-entropy repair (including the digest gate), backup, resharding. No separate storage or repair machinery exists for it.

  • Entry keys are self-describing for placement: every ring lookup with table context (writes, repair ownership, reshard/joiner motion, reads) places __gidx__ keys by the embedded VALUES prefix, so one value's entries live on one replica set — the routed-probe contract.
  • The entry table is named <db>␟__gidx__<bare-index-name>. It is hidden from SHOW TABLES and from schema replay (the index DDL implies it; replay emits the WITH (global = true) clause).
  • Catalog: IndexDef.global (serde-default false, so old catalogs deserialize). SHOW INDEXES reports kind global with local health ok — entries are replicated rows, so there is no per-node index state to be missing.
  • Readiness is part of the index's schema: schema replay emits WITH (global = true, ready = true) once backfill completes. ready is an internal DDL option.

Write path

On a row put/delete the coordinator computes old→new entry deltas and issues companion writes to the entry table, routed by the entry keys — potentially to different nodes than the row:

  • Companion writes ship at the row write's consistency, after the row write, before the ack — read-your-writes parity with local indexes.
  • The old row version is fetched with one quorum point read (only on tables that declare a global index); multi-row INSERTs on such tables take the per-row path. DELETE reuses the already-matched row — no extra read.
  • Unchanged entries produce no writes (old/new entry-key set difference, global_entry_delta).
  • Every entry write carries the row version's stamp, so an entry key's last-writer-wins order is its rows': a retraction sent late by a write that lost to another coordinator's later write of the same value can no longer land over that write's put (stamped by the coordinator's clock when sent, it could, and hid the row until the next verify pass).
  • Single-node (Session) writes maintain entries directly in the local entry table — the local shard is the whole ring there. The replaced version is read as stored, TTL-expired or not (expiry removes no entry). New entries go in before the row, the replaced version's come out only after the row append succeeded; a refused append (WAL error, full disk) takes the new entries back out, so the entries stay exactly as they were. A DELETE removes the row's entries after its tombstone is appended. The replica APPLY path never touches entries.

There is no cross-key atomicity (no distributed transaction). A crash between row ack and entry write leaves a missing or orphan entry; both are self-healing:

  • orphan entry → the probe's candidate re-read finds the row absent or non-matching and drops it (the standard residual re-check);
  • missing entry → invisible to index reads until the repair pass regenerates it from the row (the row table is the source of truth); bounded by the anti-entropy interval.

Read path

Full-tuple equality only (plan_global_probe), consulted by the coordinator after PK and local-index plans decline:

  1. start/end = prefix range of encode_key([values...]) in the entry table.
  2. Route to replicas_for(prefix) — the one replica set owning that value.
  3. Read the entry range from that set at the statement's consistency (Request::EntryRange), LWW-merge per entry key, extract candidate row keys.
  4. Resolve candidates through the standard quorum point-read + residual filter (orphan entries drop out there).
  • IN-list probes: every index column pinned by =/literal IN expands to one probe range per value tuple (cross product, capped at 100 ranges — past that the scatter paths win), each routed to its own value's replica set, candidates unioned into one resolve. A pin to an empty set answers empty without touching the ring.
  • Fallbacks to the scatter paths (still correct, just wider): an entry-set quorum miss, a peer lacking the probe verb (mixed-version rolling upgrade), a hot value past GIDX_PROBE_MAX (10 000 candidates), or the index still building.
  • Value ranges and partial prefixes of a composite never route (hash placement) and keep the scatter paths.
  • Multikey ([]) columns produce one entry per array element (the same expansion as the local multikey index), equality-pinned probes only.
  • EXPLAIN: access global-index probe via '<name>' (routed …); cluster.fan_out global-index probe routed to the value's replica set.

Backfill and readiness

The DDL-coordinating node drives backfill in the background: it pages every member's shard (ScanPage), writes entries for rows the member primarily owns (exactly-once across members) through the normal routed write path at QUORUM, then broadcasts GidxReady; every node flips building off and starts routing probes. Single-node databases backfill inline before the DDL returns.

  • Convergence: readiness advances the index's schema stamp, so a node that missed the GidxReady broadcast (down at the time, or freshly bootstrapped) converges on its next schema sync instead of never routing probes. Until then it keeps building — routes no probes; safe, just slower.
  • Resumability: a repair pass that finds a global index still building re-queues the backfill drive on that node; duplicate drives are idempotent LWW upserts and readiness is stamped, so whichever drive finishes first wins.

Repair

gidx_repair, part of every repair pass, is a paged two-direction verification of entries against rows:

  • heals missing entries — a missing entry silently hides its row from probes (the correctness direction);
  • GCs orphans — harmless, pure waste.

Both directions, and CHECK INDEX, judge a row as stored: a row the table's TTL has expired but storage still holds keeps its entries until it is reclaimed (a probe's candidate re-read drops it meanwhile).

On full-copy clusters everything is local point reads. At RF < members it is a batched cross-node exchange driven by each shard's PRIMARY owner: row-primaries derive their rows' entries and ask entry owners which exist (KeysPresent; absentees are re-put to the entry's replica set), and entry-primaries ask row-owners which entries are still produced (GidxProduced — recomputed on the node that has the row) and tombstone the rest. An unreachable owner skips the batch: silence is never treated as absence.

CHECK INDEX <name> audits a global index on demand, on a node that holds every row of its table and every entry (a single node, a full-copy cluster): both directions from that node's copy, with counts and sample keys, and REPAIR fixes its copy of the entry table (anti-entropy carries the fix to the other replicas). Entries arrive as their own replicated writes, so on a cluster member a difference whose row or entry is under 30 seconds old counts as in_flight, not drift. Where no node holds the whole table (RF < members) it is listed skipped: sharded; the repair pass's exchange above is the verification there.

Limits

  • Equality/IN probes on the full value tuple only; composite indexes require every column pinned (leftmost prefixes do not route under hash placement). Ranges and partial prefixes stay on the scatter paths.
  • No index-only answers: entries carry no row data, and counts go through the candidate-resolve path (an entry-only count would double-count unrepaired divergence).
  • IN cross products cap at 100 probe ranges; values hotter than 10 000 candidate rows fall back to scatter.