Epic: A First-Class Index Layout (`vortex.indexed`)

[brancz]

This Epic is for tracking the addition of locating indexes as a first-class feature to Vortex.

We can define a locating index as an auxiliary structure keyed by value that locates the rows (or blocks of rows) where a value occurs.

This is in contrast to a skipping index (#8900), which is a conservative summary proving that a given data region cannot match a predicate. A locating index instead answers which positions might (or exactly do) match a value, at a probe cost proportional to the query rather than to the file.

Status

Proposed.

The intended shape is a new wrapper layout (vortex.indexed) with pluggable indexes. The concrete design is worked out in the #9024 tracking issue.

Goal

Our goals are:

• Build a stable, documented interface for defining, building, and probing a locating index.
• Scans should automatically probe any index they understand to answer or prune filter predicates, and fall back to a plain scan of the data whenever an index is missing, unknown, or inapplicable, with identical logical results to a full scan.
• Following the ethos of Vortex being extensible, users should be able to define and register custom locating indexes without changes to core Vortex.

As with skipping indexes, locating indexes are strictly optional accelerators: they are not required for the correctness of a query, and a reader that does not understand an index can ignore it and perform a normal scan.

Non-goals: this Epic does not implement any specific index, and each should be tracked in its own sub-issue. It also does not cover multi-column or table-level indexes, index maintenance or incremental update (Vortex files are immutable; an index is built at write time, full stop), or clustering/primary indexes that own the data. And cross-file indexes are beyond the scope of Vortex.

Motivation

Vortex today has exactly one pruning structure: the zoned layout (vortex.zoned), which stores per-zone aggregate summaries (min/max/null-count/etc.) and prunes fixed, contiguous zone_len-row ranges via stats-domain falsification (Expression::falsify). This works well for range-correlated data but is fundamentally unable to express locating indexes, for three reasons:

1. Alignment. The zoned layout's economy comes from a positional bijection: the i-th summary row corresponds to rows [i * zone_len, (i+1) * zone_len), so range keys are implicit (stored nowhere), addressing is arithmetic (row_range to zone_range by division), and each summary finalizes the moment its chunk streams past. A locating index is keyed by value, which inherently forfeits these positional exploits: index entries ordered by value must store positions explicitly, the value-to-position mapping is many-to-many, and it can only finalize after all data has been seen.
2. Semantics. Zone columns are serialized AggregateFn states. A summary can prove "no row in this range matches" but can never say which rows match. The pruning rewrite machinery (StatsRewriteRule, StatFn) is explicitly falsification-only.
3. Access pattern. PruningState::zone_map() materializes the entire zones child and evaluates the predicate against every zone, so it is O(zones). An index requires sub-linear, value-keyed lookup.

To enable locating indexes as a first-class citizen in Vortex, we want a sibling layout that shares the zoned layout's structural pattern (transparent data child + auxiliary children, written after the data) but inverts the orientation: value-keyed postings instead of range-keyed summaries.

The boundary with skipping indexes (#8900)

Per-zone approximate membership structures, such as bloom filters or sketches, are not locating indexes. They are zone-aligned summaries and belong to the skipping-index machinery tracked in #8900 (an aggregate whose state is a bloom filter, plus a falsification rewrite rule).

The distinction here is orientation, not payload:

• Range-keyed (one summary per zone; a probe reads O(zones) summaries) -> zoned layout / aggregate function (Epic: Skipping Indexes #8900).
• Value-keyed (postings keyed by value; a probe reads O(query-terms) posting lists, sub-linear in zones) -> index layout (this Epic).

Both can express "this range might match", but the value-keyed orientation wins when the query touches few keys, because the probe cost is proportional to the query, not to the file.

For example, a per-zone bloom filter would be decoded for every zone on every query, while an inverted index or sorted value index reads only the handful of posting lists the query requires.

Locating Indexes

Here is a list of locating indexes that we potentially want to add:

• Inverted term/n-gram indexes: Positional information in zone layout aggregations #8682
• Sorted value ("b-tree") indexes
• Hash indexes

Prior Art

• Generalized Search Trees for Database Systems (GiST)
• PostgreSQL index access method interface
• Inverted files for text search engines

Unresolved questions

• Which index kinds do we ship first, and what does each demand from the common plumbing?
• How does a user declare that a column should carry a given index at write time? (Shared with Epic: Skipping Indexes #8900; there is no per-column index-declaration surface today.)
• Old readers cannot read even the data beneath an unknown wrapper layout, so emitting index layouts is a writer opt-in. Should a general "read through unknown layouts" mechanism be proposed separately before this becomes a default?

[connortsui20]

Related: #8900