Experimental listelement scalar index: indexing fields inside list<struct> elements

[sarwarbhuiyan]

This is the design discussion for the experimental listelement scalar index. The voting rules ask for one before an experimental format feature merges. The full design, with prototype measurements, is in #10900.

What it is

The index lets a filter on fields inside a list<struct> column be answered from an index, with every condition on the same element. For detections: list<struct<label, confidence, ...>>:

any_element(detections, 'label = ''car'' AND confidence > 0.9')

any_element merged in #10901 and works without an index, as a scan.

The format addition

• No new file layout. The index's files are a standard BTREE over Binary keys, one row per list element. Each key is the element's chosen sub-fields, for example (label, confidence), encoded with Arrow's row format. That is the same encoding as the composite keys in docs(format): specify composite B-tree keys #10358. The posting is the row address.
• A new details message, ListElementIndexDetails: the key fields, their types, the key encoding, and the inner BTREE's details and version. It wraps the BTREE the way JsonIndexDetails does.
• Row addresses. The index stores row addresses, so it joins the row-address and eager-remap lists in lance-table. On tables with stable row IDs, the writer fence from fix(index): fence older writers from row-address indices #10352 applies.

Why experimental

It meets the prerequisites for an experimental merge:

• Forward compatible: a reader that doesn't know the index type ignores it and scans.
• Backward compatible: no existing message or behavior changes.
• Droppable: the index is index files only, so removing the feature never rewrites data.

Planned PRs

1. feat: add any_element filter for per-element predicates on list<struct> columns #10901, any_element: merged.
2. Spec PR feat(format): add the listelement scalar index specification (experimental) #10949: docs/src/format/index/scalar/list_element.md and the details message, marked experimental.
3. Code PR feat: add the experimental listelement scalar index over list<struct> elements #10950: the index, its tests and user docs.
4. Later, a stabilization PR that removes the experimental markers and carries the vote.

Open questions

1. Composite keys (docs(format): specify composite B-tree keys #10358). If composite keys gain a per-element (multi-valued) key source, listelement could become a thin "explode the list" wrapper over the composite BTREE. Is a separate wrapper acceptable while experimental, with a merge into composite keys considered before stabilization?
2. Key types. The details record each key's type, so a reader can decline the index if a key field's type changes. docs(format): specify composite B-tree keys #10358 takes key types from the dataset schema instead. Which should this follow?