Global temporal scan¶

Architecture

The global scan answers "everything valid at time T across the tenant," the one query shape entity-scoped point lookups cannot serve. This page covers the two covering indexes that make it possible, the per-candidate winner check that keeps it correct across pages, and the cursor-resumption fix that closed a tombstone-leak bug found during PR-016.

Overview & purpose¶

Every other read in the engine is entity-scoped: given a logicalId, seek its version history and apply the winner rule (see The tritemporal model). That is a cheap prefix scan because the primary CFs (node_versions, edge_versions) key on [scope][logicalId][inv(validStart)][inv(txStart)], per The version record model.

The global scan answers a different question: "show me the whole tenant's world at (validTime, txTime)" without an entity id to seek by. There is no way to enumerate every logicalId cheaply from the primary CFs alone, so the engine maintains two covering secondary indexes, valid_time_index and tx_time_index, that let the scan walk time order directly and validate each candidate with a point lookup rather than a second scan.

GlobalScan (core-engine/src/query/global_scan.rs) is the operator that walks these indexes. It backs the query executor's label/predicate scan path (core-engine/src/query/executor.rs, scan_and_filter) whenever the bitmap accelerator does not have a usable index for the query (see Bitmap predicate index), and it is the only way to serve a query with no entity anchor at all.

Design¶

Why point lookups are not enough¶

A point lookup answers "what is the state of this entity at (vT, tT)." A global scan has to answer "which entities have any state at (vT, tT)," which means walking every entity's history in time order and stopping only when time itself rules out further candidates. Without a covering index that walk degenerates to a full-tenant scan of every version of every entity ever written, most of which are irrelevant to the query.

The dual-axis problem¶

Because every version carries two time intervals, valid time and transaction time (the tritemporal model's first two clocks), "in time order" is ambiguous: order by which axis?

The engine resolves this by maintaining two covering indexes, one keyed by each axis as the leading dimension:

Both indexes carry the same two time values per entry, just in reversed key order, so both scans can validate a candidate's containment on both axes regardless of which one leads the iteration. GlobalScan::scan takes a TimeAxis (Valid or Transaction) and picks the index CF and the "lead" timestamp from it; the validation step below is identical either way.

Why a naive containment-only scan over- or under-counts¶

The obvious algorithm is: walk the index forward from inv(T), and for every row whose interval contains the queried coordinate, emit it. This is wrong in both directions:

• Over-counts if an entity has been corrected. Both the superseded version and its replacement can have valid-time intervals that contain the same validTime; naive containment would emit both, when only one is ever "the truth" at a given (vT, tT).
• Under-counts on a past-transaction-time query if you dedupe on the first row seen per entity without checking containment first: the newest version usually sorts first in the index, but a query asking "what did we know before this entity was corrected" needs the older version, which sorts later.

Both failure modes are why the scan performs a genuine winner check per candidate rather than "first row per entity wins" or "every containing row wins." See Algorithms & invariants for the exact fix.

Data model¶

Index key layout¶

Both temporal indexes share one physical layout (composite-key-layout §5.2), 65 bytes, fixed width:

[scope: 32B][inv(primary_time): 8B][inv(secondary_time): 8B][logical_id: 16B][kind: 1B]

valid_time_index stores primary_time = validTimeStart, secondary_time = txTimeStart; tx_time_index swaps them. Both timestamps are stored inverted (u64::MAX - ts) so that forward byte-order iteration visits entries newest-first on the leading axis, matching every other descending-time scan in the storage layer. kind (IndexKind::Node = 0x00 / IndexKind::Edge = 0x01) disambiguates node versions from edge versions in the same CF.

Crucially, the index value is not a marker, it is the exact primary-CF key bytes for that version (core-engine/src/temporal/indexing.rs, version_index_ops):

/// The two covering-index puts that must accompany a version put.
/// `primary_key` is the version's key in its primary CF.
pub(crate) fn version_index_ops(
    scope: &TenantScope,
    logical_id: Uuid,
    valid_start: Ts,
    tx_start: Ts,
    kind: IndexKind,
    primary_key: &Key,
) -> [WriteOp; 2] {
    let value = primary_key.as_bytes().to_vec();
    [
        WriteOp::Put {
            cf: cf::VALID_TIME_INDEX,
            key: KeyCodec::valid_time_index_key(scope, valid_start, tx_start, logical_id, kind),
            value: value.clone(),
        },
        WriteOp::Put {
            cf: cf::TX_TIME_INDEX,
            key: KeyCodec::tx_time_index_key(scope, tx_start, valid_start, logical_id, kind),
            value,
        },
    ]
}

This makes every scan validation a single point lookup in the primary CF, never a second scan. version_index_ops is called from every version write, create, update-closure, and tombstone, with no exceptions, and its two WriteOps ride in the same WriteBatch as the primary-record put so the index can never observe a version the primary CF does not also have.

Request and page shapes¶

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

The as-built GlobalScan (core-engine/src/query/global_scan.rs) implements this contract as two public methods over one private scan:

The cursor is opaque: it is the last index key visited, hex-encoded (encode_cursor / decode_cursor), and resuming re-derives a ScanRange starting immediately after that key (ScanRange::temporal_index_after), tenant-checked on decode so a cursor from another tenant's scan is rejected as GlobalScanError::BadCursor rather than silently scanning the wrong prefix. The query executor layers its own signed, versioned cursor (sign_cursor, HMAC-tagged) on top of this raw index-key cursor for the public API; GlobalScan's cursor is the inner, unsigned primitive.

Horizon and row ceiling¶

Two configuration values bound the scan, both read from GlobalScanConfig (core-engine/src/config.rs):

The horizon check happens once per row, immediately after decoding the index key and before validation, comparing the entry's leading-axis primary_time against lead_t.saturating_sub(horizon_days * 86_400_000_000) microseconds. Because the leading axis is stored inverted, the walk visits entries in descending time order, so the first entry to drop below the floor proves every subsequent entry will too, and the scan can stop immediately.

Algorithms & invariants¶

The scan, step by step¶

flowchart TD
    A[Start: ScanRange from cursor or inv-T] --> B{Row available?}
    B -- no --> Z1[Terminate: Exhausted]
    B -- yes --> C{rows_scanned >= max_rows_scanned?}
    C -- yes --> Z2[Terminate: ScanCeiling<br/>emit cursor, partial results]
    C -- no --> D[Decode index key<br/>rows_scanned += 1]
    D --> E{primary_time below horizon floor?}
    E -- yes --> Z3[Terminate: Horizon<br/>no cursor]
    E -- no --> F{logical_id already in seen-set?}
    F -- yes --> B
    F -- no --> G[Point-lookup primary record<br/>rows_validated += 1]
    G --> H{valid_time AND tx_time<br/>contain vT, tT?}
    H -- no --> B
    H -- yes --> I[Winner check:<br/>scan full entity history,<br/>find highest txTime.start<br/>among containing versions]
    I --> J[Mark logical_id seen]
    J --> K{This candidate IS the winner<br/>AND winner is not tombstoned?}
    K -- yes --> L[Emit ScanHit<br/>rows_returned += 1]
    K -- no --> B
    L --> M{hits.len == limit?}
    M -- yes --> Z4[Terminate: Limit<br/>emit cursor]
    M -- no --> B

In prose (spec §4, as built):

1. Build a ScanRange starting at [scope][inv(leadT)] (fresh scan) or immediately after the last visited index key (resumed scan).
2. For each index row: check the row ceiling first; if hit, stop with a cursor (partial-with-warning).
3. Decode the index key. If its leading-axis timestamp has fallen below the horizon floor, stop; nothing further in the walk can qualify because the walk is strictly descending on that axis.
4. If this (kind, logicalId) has already been resolved earlier in this scan invocation, skip the row: the entity's fate is already decided.
5. Otherwise, point-lookup the primary record via the key carried in the index value, and check both intervals contain (validTime, txTime). If not, this version says nothing about the query point (it may be too old or not yet known); continue to the next row without marking the entity seen, because an older version of the same entity, appearing later in the walk, might still be the one that matters.
6. If it does contain the coordinate, run the winner check (next section) and mark the entity seen either way.
7. Emit a hit only if this candidate is the winner and the winner is not a tombstone. Stop when the page limit is reached (cursor emitted) or the index is exhausted (no cursor).

Invariant: per-candidate winner check, not first-hit-wins¶

The validate function in global_scan.rs does not stop at "does this version's intervals contain the query point." After confirming containment, it re-scans the entity's full history (ScanRange::node_history / edge_history, a prefix scan of the primary CF) to find the containing version with the highest tx_time.start:

// Winner check over the entity's full history (latest-recorded
// containing version wins — same rule as the read path).
let mut winner: Option<(Ts, bool)> = None; // (tx_start, tombstone)
for row in self.engine.scan_prefix(primary_cf, &history)? {
    let (_, row_value) = row?;
    let (v, t, tomb) = /* decode valid_time, tx_time, tombstone */;
    if v.contains(valid_t) && t.contains(tx_t) && winner.is_none_or(|(wt, _)| t.start > wt)
    {
        winner = Some((t.start, tomb));
    }
}

The candidate is only emitted if it is that winner (winner_tx == tx_time.start) and neither the winner nor the candidate is a tombstone. If some other version of the entity is the true winner, this candidate resolves silently (Validation::Contained(Box::new(None))), on the understanding that the winner will be emitted at its own index entry elsewhere in the walk, or was already emitted earlier.

Why naive containment-only scanning over-counts: the dedupe-on-containment lesson¶

The regression test past_knowledge_query_sees_superseded_version in global_scan.rs exists specifically to pin this: an entity is created, then updated (so v2's index entry sorts before v1's in index order). A query pinning tx_t to a moment between v1's and v2's recording times reaches v2's index entry first. v2 fails tx-containment (it wasn't recorded yet as of the queried tT), so the scan must not mark the entity resolved at that point, it must fall through and keep scanning until it reaches v1's entry, which does contain the coordinate and wins. The seen-set is only populated once containment is confirmed (step 5/6 above), never on raw index order, precisely so this fallthrough is possible.

Why cursor resumption must not leak tombstone-shadowed versions¶

This is why the per-candidate winner check in validate does not merely ask "have I seen this entity in this scan yet"; it re-derives the winner from the primary CF every time a fresh, previously-unseen candidate is encountered, on every page, independent of what any earlier page did. An entity is emitted (or resolved as absent) exactly when the walk reaches the index entry of its own winning version, at which point validate proves that status directly from the entity's full history rather than trusting page-local state. Concretely:

• If the winning version is a tombstone, validate returns Contained(Box::new(None)); the caller sees Validation::Contained (so the entity is marked seen and will not be reconsidered), but no ScanHit is pushed. The entity correctly reads as absent, and it reads as absent regardless of which page its winning tombstone's index entry falls on.
• A superseded, non-winning version that happens to be the first candidate encountered for its entity on a given page resolves silently the same way, on that same page. It is never carried into a later page as "unresolved," and it is never emitted just because it was first through the door.

The doc comment on validate states the invariant directly: "Without this, a cursor resuming past the winner would re-emit older versions or leak tombstone-shadowed ones (the in-page seen-set does not survive pagination)." This is the fix the task's context refers to as "dedupe-on-containment": dedup keys are only committed to the seen-set after the winner check runs, and the winner check is re-derived fresh, per candidate, per page, from the primary CF rather than carried in any cross-page cache.

Dangling index entries fail loud¶

If a point lookup for the primary key carried in an index value returns nothing, that is a maintenance-doctrine violation (spec §5: the index-entry set must exactly equal 2x the version-record set), and validate returns GlobalScanError::DanglingIndexEntry rather than silently skipping the row. The consistency checker (core-engine/src/storage/consistency.rs) exists to catch this class of drift proactively: telha debug index-check <tenant> --org <org> walks one tenant's primary CFs and both index CFs and reports IndexReport { missing, orphaned }, expected to be empty on every run.

Configuration¶

These are the defaults wired in Config::default() (core-engine/src/config.rs) and are also settable via the environment keys global_scan.horizon_days, global_scan.max_rows_scanned, and global_scan.max_page_size (ENV_KEYS in the same file).

Telemetry¶

Every scan returns a ScanTelemetry alongside its page:

Per the spec (§6), selectivity = rows_returned / rows_scanned is the number that feeds planner cost decisions and the PR-022b bitmap-index trigger: a scan with chronically low selectivity is the signal that a label or predicate is a good candidate for bitmap acceleration (see Bitmap predicate index). The scan also emits a tracing::debug! line on completion with all four fields, and a tracing::warn! when it terminates on ScanCeiling, since that termination means the caller received a partial page silently unless it inspects terminated itself.

As-built notes¶

Deviations and clarifications versus the spec's prose, drawn from the module's own doc comments since the spec's §14 changelog itself is still at its initial v0.1 draft entry:

• Winner check is per-candidate, not "first hit wins." The spec's architecture sketch (§4) reads as a single dedupe-by-(kind, logicalId) step, "first hit wins (latest version sorts first)." The as-built code goes further: it defers marking an entity "seen" until containment is confirmed, and then proves winner-ness by re-scanning that entity's full history rather than trusting index order. This is the containment-vs-order distinction covered in detail above.
• OQ-1's long-lived-set mitigation is unbuilt. The spec proposes it as the v1 answer to the horizon/immortal-record tension; the code explicitly defers it pending real measurement of how often it would matter.
• Cursor is a two-layer construct. The spec's API contract (§6) describes a single opaque cursor. As built, GlobalScan produces a raw hex-encoded index-key cursor, tenant-checked on decode, and the query executor wraps that in its own HMAC-signed, versioned cursor for the public API. Both layers reject foreign or tampered input rather than silently misbehaving.
• Index maintenance matches the spec exactly. The "same WriteBatch, every write, no exceptions, never deleted" doctrine (§3/§5) is implemented literally in version_index_ops and is exercised by the consistency checker's round-trip tests; no drift found here.

Related¶

• The version record model
• Temporal write & read paths
• Tombstone cascade
• Traversal semantics
• The tritemporal model