Tracking Issue: Index Layouts

[connortsui20]

This is a tracking issue for the plumbing that lets a reader locate rows by value: a new layout encoding, vortex.indexed, that attaches one or more locating indexes (sorted "btree" indexes, inverted indexes, hash indexes, etc.) to a data layout as auxiliary children.

Writers build indexes through a pluggable IndexVTable registry while they stream data, and readers probe those indexes to answer or prune filter predicates. A reader falls back to a plain scan of the data child whenever an index is missing, unknown, or inapplicable.

Motivation

Parent epic: #8948, which covers the motivation for locating indexes in general and where the boundary with skipping indexes (#8900) sits.

This issue is scoped to the plumbing only: the layout, the registry, the write path, and the read path. No specific index kind lands here, since each one gets its own sub-issue under the epic.

Design

Right now LayoutReader::pruning_evaluation returns a mask whose false values are all proven false, with no granularity requirement attached, so an index that produces a row-granular or block-granular superset mask already satisfies the existing contract. The scan loop, the split machinery, and IO coalescing all compose with index-driven masks as they are, and an exact index can additionally answer filter_evaluation outright. So nothing in the LayoutReader trait, the scan loop, or the flatbuffer Layout schema has to change for any of this.

On-disk format

IndexedLayout ("vortex.indexed")
├── child 0: data        LayoutChildType::Transparent("data")
├── child 1: index #0    LayoutChildType::Auxiliary("index:0")
├── child 2: index #1    LayoutChildType::Auxiliary("index:1")
└── metadata (versioned protobuf, ZonedMetadata-style leading version byte):
      IndexedMetadataProto {
          indexes: [ IndexSpecProto {
              id: string         // registry id, e.g. "vortex.idx.sorted"
              options: bytes     // index-kind-defined, self-versioned
              index_dtype: bytes // serialized DType of the index child
          } ]
      }

• Multiple index children per node, so a column can be indexed several ways without stacking wrapper layers. Child i + 1 corresponds to indexes[i].
• The flatbuffer Layout node carries no dtype (dtype flows top-down during deserialization), so each index child's dtype is carried in IndexSpecProto.index_dtype and reconstructed during build.
• Row coordinates stored in an index are local to the data child (0..row_count). LayoutChildType::Transparent guarantees the wrapper shares the data child's row space, so probe results translate into masks with no coordinate mapping.
• Index segments are written after all data segments, using the same eof.split_off() sequencing as ZonedStrategy, so a streaming writer still works in one pass and data locality is preserved for readers that ignore the indexes.

The index child is an ordinary layout tree

An index's content is written through the normal strategy stack, so it inherits compression, zone maps, chunking, and lazy segment IO instead of defining its own binary format. Note that this is the decision most of the rest of the design depends on.

A "btree" is then just a struct child {key: T (sorted, deduped), locator}. For a data child holding [7, 3, 3, 9], a sorted value index is roughly {key: [3, 7, 9], locator: [[1, 2], [0], [3]]}, where the posting representation itself is the index kind's business. The sorted key column gets zone maps for free, so probing the index is a pruned scan over the index child, where min/max stats on a sorted key cut the probe down to a handful of zones. Zones do the job of btree leaf pages and zone maps the job of internal nodes, out of machinery that already exists and is already tested. Posting list encodings (delta, RLE, roaring style) are then pure array-encoding concerns inside the index child, invisible to this design.

Note that fully columnar is not mandatory, since the index child's dtype is whatever the kind declares. There is a spectrum of opacity, and the options are:

1. Fully columnar: zone-map-pruned probes, lazy per-chunk IO, compression. This is the default.
2. Paged opaque: a Binary column with one row per page or node of a custom structure, chunked so that pages land in separate segments. Page contents stay private to the kind while the layout machinery still provides paging, caching, and IO scheduling.
3. Single blob: a one-row Binary child, fetched and decoded whole on the first probe. This form is the least preferred, since a probe pays for the entire structure even when it touches a single key. It stays legitimate for small structures with a read-once-stay-cached profile (a per-file filter, a small FST).

Kinds should reach for opacity only when their structure does not decompose into arrays, and should prefer (2) over (3) whenever a probe touches only a subset of the structure. The wrapper never looks inside the index child, so masks, probe caching, and unknown-kind degradation are identical across all three.

Index kinds: the IndexVTable registry

This mirrors AggregateFnVTable plus AggregateFnSession: an IndexVTable registered in an IndexSession (a vortex-session registry) with the standard allow_unknown policy.

pub trait IndexVTable: 'static + Send + Sync {
    /// Stable string id, e.g. "vortex.idx.sorted", "vortex.idx.inverted".
    fn id(&self) -> IndexId;

    /// Whether this index kind can be built over values of `dtype`.
    fn supports_dtype(&self, dtype: &DType) -> bool;

    // ---- write side ----

    /// `data_block_len` is the data child's repartition block granule, when known. Kinds
    /// that emit block-granular locators should default their `block_len` to it so that
    /// pruned blocks nest inside chunk and segment boundaries.
    fn builder(
        &self,
        dtype: &DType,
        options: &[u8],
        data_block_len: Option<u64>,
        session: &VortexSession,
    ) -> VortexResult<Box<dyn IndexBuilder>>;

    // ---- read side ----

    /// Decide whether this index can serve `expr` (a single conjunct, scoped to the data
    /// child's dtype). `None` means "no claim", which is always safe, and the scan falls
    /// back to the data child.
    fn plan(
        &self,
        expr: &Expression,
        dtype: &DType,
        options: &[u8],
    ) -> VortexResult<Option<IndexQueryPlan>>;
}

pub trait IndexBuilder: Send {
    /// Chunks arrive in stream order with their absolute row offset within this layout.
    fn push(&mut self, chunk: &dyn Array, row_offset: u64, ctx: &mut ExecutionCtx)
        -> VortexResult<()>;

    /// Emit the index content as an array stream, written through a child layout strategy.
    ///
    /// Returns the final serialized options, since builders may record normalization
    /// choices, block sizes, and other decisions made during the build.
    fn finish(self: Box<Self>) -> VortexResult<(SendableArrayStream, Vec<u8>)>;

    /// Reported up through `LayoutStrategy::buffered_bytes` for writer memory accounting.
    fn buffered_bytes(&self) -> u64;
}

A query plan declares what its result mask means and at what granularity it locates:

pub enum IndexExactness {
    /// True bits are exactly the matching rows. May serve `filter_evaluation` directly.
    Exact,
    /// False bits are proven non-matching, and true bits are "maybe". May serve
    /// `pruning_evaluation` only, so the real predicate re-checks the survivors.
    Superset,
}

pub enum RowLocator {
    /// Sorted row positions, local to the data child.
    Rows(Buffer<u64>),
    /// Sorted ids of fixed `block_len`-row blocks. Expanded to a row mask by the same
    /// per-zone broadcast the `ZonedReader` uses.
    Blocks { block_len: u64, ids: Buffer<u64> },
}

IndexExactness	Rows	Blocks
Exact	e.g. sorted value index: serve filter directly	coherent but unusual (exact block hit list)
Superset	e.g. hash index with collisions	e.g. inverted n-gram index

The cells are illustrative and not assignments. Exactness is usually inherent to a kind's semantics (n-gram intersection is Superset at any granularity, since n-grams co-occurring in a row still do not prove a substring match), while granularity is a size/precision trade the kind picks per plan, or even per posting list. Coarse Blocks locators trade recheck volume for much smaller postings, and their IO benefit (a pruned block being a whole chunk or segment that never gets fetched) only shows up when block_len lines up with the data child's actual chunking.

Note that in the default write stack, the data child's blocks are not a fixed number of rows. RepartitionStrategy emits blocks holding a multiple of RepartitionWriterOptions::effective_block_len(dtype) rows and at least block_size_minimum uncompressed bytes, and effective_block_len shrinks below row_block_size for wide fixed-width dtypes, so the actual block length varies per column and per block. That makes the per-column granule, not any average chunk length, the useful target for data_block_len: a block_len that divides the granule always nests inside real chunk boundaries, while one picked to match an average chunk length does not. A misaligned block_len still prunes correctly, it just produces masks that slice through chunks and save less IO.

Write path: IndexedStrategy

IndexedStrategy implements LayoutStrategy, wrapping a data child strategy plus a list of index specs:

1. For each incoming chunk: forward it to the data child's stream, then feed builder.push(chunk, row_offset) for every index builder. Pushes have to be sequential in stream order because index building is globally stateful, but per-chunk key extraction can still run on spawn_cpu with a sequential combine, mirroring the zoned writer's parallel-partials / sequential-serialize split.
2. At stream EOF: data_eof = eof.split_off() so that data segments come first, then builder.finish() streams each index's content through an index child strategy, by default the normal table stack, so index content is zoned and compressed for free.
3. Return IndexedLayout::try_new(data_layout, index_layouts, specs).

v1 buffers builder state in RAM and reports it through buffered_bytes(). External sort and spilling are later builder-internal improvements, as are the index kinds themselves.

Indexes are declared opt-in, per column, via WriteStrategyBuilder::with_field_index(field_path, spec). Nothing prevents inserting the wrapper at table level later for multi-column indexes, since only expression scoping changes.

Read path: IndexedReader

Structured like ZonedReader plus PruningState:

• One probe per expression per file. An IndexState caches a shared probe future per expression (precedent: PruningState::pruning_mask_future), so every split slices its row_range out of the shared RowLocator instead of re-probing. Dynamic expressions (runtime-bound literals) re-probe through the same DynamicExprUpdates versioning the zoned reader already uses.
• The probe is itself a scan over the index child reader. plan() produces a predicate over the index child's schema, and the probe evaluates it using the index child's own pruning, filter, and projection evaluations (its zone maps prune the probe, its segments are fetched lazily), then post-processes the projected postings into a RowLocator.
• pruning_evaluation: if any index child has a plan for expr, return the sliced index mask ANDed with the data child's own pruning, otherwise forward to the data child untouched. Only conjuncts arrive here, which keeps plan() matching simple.
• filter_evaluation: if the plan is Exact, return the index mask intersected with the input mask and skip data child evaluation for that conjunct entirely. If the plan is Superset, or there is no plan, delegate to the data child, where the recheck is the existing prune-then-filter flow.
• projection_evaluation and register_splits: pure pass-through to the data child.

IO composes on its own: blocks pruned by an index are never polled by the data child's readers, so the IO driver never fetches or coalesces their segments.

Compatibility

• vortex.indexed is a new layout id, so existing files are not affected. Layout metadata is self-versioned, and each index kind's options are self-versioned by that kind.
• New reader, unknown index kind: the degradation path drops that index child from consideration and reads the data child directly. The precedent is Zoned::build disabling pruning when stored aggregates are unknown and the session allows unknown ids. plan() returning None gives the same graceful degradation per query, even for known kinds.
• Old reader, unknown layout id: this resolves to ForeignLayout, whose new_reader bails, so an old reader cannot read even the data underneath a wrapper it does not recognize. Emitting index layouts is therefore a writer opt-in. A general fix, some transparent-child hint so that a foreign layout can degrade to reading through, would benefit every wrapper layout and is left as an open question below.

Steps

• IndexVTable and IndexBuilder traits, plus the IndexSession registry.
• The vortex.indexed layout: metadata proto, build and deserialize, and unknown-kind degradation.
• Write path: IndexedStrategy and the WriteStrategyBuilder::with_field_index declaration surface.
• Read path: IndexedReader with the shared per-expression probe cache.
• A reference index kind that exercises the plumbing, with roundtrip and degradation tests.
• Documentation.

Unresolved questions

• What does IndexQueryPlan look like concretely? It is not settled how a plan executes its probe against the index child reader, where IndexExactness gets declared, or how dynamic literals trigger a re-probe. This is the least understood part of the design, and it gates the read path.
• How does a plan turn projected postings into a RowLocator? A sorted value index projects a locator column whose rows are themselves posting lists, so the step from "projected index rows" to "sorted row positions local to the data child" needs a defined shape, including who decides Rows versus Blocks for a given plan.
• When several indexes on the same column can serve the same conjunct, does the reader probe one of them or intersect all of them? Probing one requires a cost model, and no cost model exists in vortex-layout or vortex-scan today, so picking one means introducing the first one. Intersecting all of them avoids that, at the price of paying every probe's IO for a mask that may be no tighter than the cheapest probe alone.
• Should a builder be able to abstain and emit no index when its buffered state grows too large, instead of only reporting that state through buffered_bytes()? Note that data-dependent layout choice is already normal on the write side, since DictStrategy writes through its fallback strategy when the dtype is unsupported or when the first chunk does not compress to Dict, and it cuts a new dictionary run when the dict constraints are hit mid-stream. So the open part is which of those two shapes a builder copies: abstain wholesale and write no index child at all, or emit a partial index the way DictStrategy starts a new run. Abstaining wholesale is much simpler, but it turns a declared index into no index with nothing in the file explaining why.
• How should with_field_index compose with the default stack, and with an existing per-field override? Right now a TableStrategy::with_field_writer override replaces the whole per-column strategy stack: dispatch resolves a leaf field to either its exact-path entry in leaf_writers or the leaf fallback, and validate_path forbids overlapping overrides, so a field has an exact override or deeper ones and never both. The two options are (1) wrap whatever that dispatch resolves for the path, or (2) insert the wrapper into leaf_writers directly, which clobbers an existing override and has to duplicate the dispatch logic to know what it is wrapping.
• What does IndexedStrategy pass as data_block_len, given that the data child's strategy stack is opaque to it? The granule lives in RepartitionWriterOptions, several layers below where the wrapper sits, so either the wrapper derives it from the builder configuration (row_block_size, data_block_target_bytes, and the field's dtype) or LayoutStrategy grows a way to report it. Deriving it in the wrapper duplicates effective_block_len and goes stale as soon as the repartition options change.
• Should the "read through an unknown wrapper layout" mechanism be specified before vortex.indexed ships, rather than after? Also open on the epic as an unresolved question. Without it, every index-carrying file is unreadable by an older reader, which makes index emission a permanent writer opt-in rather than something that can become a default.

Implementation history

cc @brancz

[connortsui20]

(this is LLM generated right now, auto derived from the old version of #8948, ill touch it up later)