skaidb v0.234.0

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).
  • Single-node (Session) writes maintain entries directly in the local entry table — the local shard is the whole ring there. 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.

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.

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.