Skip to content

Spec: Covering Temporal Indexes & Global Scan Semantics

File: .ai/specs/core-engine/2026-07-02-global-temporal-scan.md Status: Draft Owners: Storage lane Related: PR-016; composite-key-layout spec §5.2 (valid_time_index / tx_time_index layouts); tombstone-cascade spec

1. Overview

Defines how the two covering secondary indexes are maintained, the exact algorithm for global cross-cutting temporal queries ("everything valid at T within tenant"), horizon-boundary termination, and the consistency doctrine between primary and index CFs.

2. Problem Statement

Entity-scoped reads are cheap prefix scans, but "show me the whole tenant's world at time T" cannot enumerate every logicalId. Without covering indexes it degenerates to a full-tenant scan; without defined maintenance rules the indexes silently drift from the primary CFs; without a termination rule the scan is unbounded; and without a validation step, index rows for versions whose validity has since been capped produce false positives.

3. Proposed Solution

Every version write (create, update-closure, tombstone — no exceptions) emits its valid_time_index and tx_time_index entries in the same WriteBatch as the primary record; index values carry the full primary key (covering). The global scan iterates the index forward from [scope][inv(T)], and for each candidate performs a primary-CF point lookup to validate the record's current end boundaries at the query's bitemporal coordinate. Index rows are never deleted (append-only doctrine); staleness is impossible because validation always consults the primary record.

4. Architecture

query "valid at (vT, tT)"
  → ScanRange from [scope][inv(vT)]           (valid_time_index)
  → forward iterate: candidates have validTimeStart <= vT (by inversion)
  → per candidate: point-lookup primary key (carried in index value)
      keep iff validTime.start <= vT < validTime.end
           AND txTime.start   <= tT < txTime.end
           AND !tombstone
  → dedupe by (kind, logicalId): first hit wins (latest version sorts first)
  → stop at: result limit | horizon boundary | scan ceiling

5. Data Models

Key layouts per composite-key-layout spec §5.2 (65B, kind byte disambiguating node/edge). Index value = the exact primary-CF key bytes (64B), making every validation a point lookup. Maintenance rule (normative): the set of index entries is exactly the set of version records × 2 — verified by the consistency checker (§12). Horizon boundary: iteration stops when validTimeStart drops below vT − horizon (config, default 10 years): any record starting earlier that is still valid at vT is a long-lived record and horizon must be sized so none are missed — see OQ-1 for the pathological case and its mitigation.

6. API Contracts

fn scan_valid_at(scope, valid_t, tx_t, filter: Option<LabelFilter>, limit, cursor) -> Page<VersionRef>;
fn scan_tx_at(...)  // mirror on tx_time_index

Cursor = last index key (opaque, tenant-checked on resume). Telemetry per scan: rows_scanned, rows_validated, rows_returned — exported as metrics; selectivity = returned/scanned drives planner cost decisions and the PR-022b bitmap trigger.

7. UI/UX

Internal. Forensics: telha debug index-check <tenant> runs the consistency checker over one tenant and reports orphan/missing entries (should always be zero).

8. Configuration

global_scan.horizon (default 10y), global_scan.max_rows_scanned (default 1,000,000 — exceeding returns partial-with-warning), page size caps.

9. Alternatives Considered

Deleting index entries when versions close (rejected: violates append-only; breaks backward snapshots; F3 doctrine). Interval trees / segment indexes (rejected for v1: powerful but complex; the covering-index + validation pattern is simple, correct, and measurable — revisit only if selectivity telemetry shows chronic waste). Storing end-times in index keys (rejected: end-times change when versions close, and keys must be immutable; validation-via-primary keeps keys write-once).

10. Implementation Approach

PR-016 commits: this spec → index maintenance in write paths → scan operator → telemetry → consistency checker (tool + test) → brute-force-reference correctness tests on randomized datasets.

11. Migration Path

Greenfield. If maintenance rules ever change, indexes are rebuildable from primary CFs by full scan (derived-data doctrine, same as F4) — a telha index rebuild-temporal subcommand accompanies any such change.

12. Success Metrics

Consistency checker: zero orphans/missing across randomized write/tombstone workloads. Correctness: results byte-equal to a brute-force full-scan reference on 10k randomized histories. Performance (F6 gate, PR-029): global valid-at-T scan p50 within budget on the 10M-node dataset at realistic selectivity.

13. Open Questions

  • OQ-1: Horizon vs immortal records — a record created 30 years ago and still valid would be missed by a 10y horizon. Stance: v1 mitigates by exempting open-ended (end==MAX) records via a small per-tenant "long-lived set" side list consulted at scan start; measure its size in practice and revisit if it grows past ~10k entries per tenant.

14. Changelog

  • 2026-07-02 — v0.1: initial draft for peer review.