feature: preserve matched element identity in vector search over list<struct>

Aperta
#11,076 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 2 giorni

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
8/100
Tipo di issue
Funzionalità
Chiarezza
Abbastanza chiara
Stato di attività
Attiva
Stack tecnologico
rust
Ambito
data

Direzione di ricerca

This is design work spanning lance-index scalar and vector code (rust/lance-index/src/scalar/list_element.rs and rust/lance-index/src/vector/transform.rs), with FTS _doc_index traversal as precedent. Start by reading how multivector flattening repeats parent IDs in transform.rs and how list_element.rs returns parent row-address sets. Done means the example returns B/0 for top-1 with coordinates carried through exact search, per the acceptance criteria.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

feature

Summary

Support element-level vector search over a list<struct<..., embedding: fixed_size_list<float>>> column, retaining the matched element's physical position and applying scalar predicates to that same element before ranking.

This enables retrieving a particular chunk, detection or clip together with its parent, vector distance and matching metadata. Milvus documents this as StructArray element-level vector search with element filtering.

Existing building blocks and remaining gap

  • #10901 / #10950 implement any_element and its experimental scalar index. The tuple keys preserve same-element scalar correlation, but the postings and search results identify parent rows.
  • #11010 / #11062 add fragment-reuse remapping of those parent row addresses and declarations of nested schema-field dependencies. A schema field ID identifies a field such as label; it does not identify one element within a particular row's list.
  • Existing multivector flattening repeats the parent row ID for each vector. It does not emit an element ordinal. Parent-level late-interaction retrieval is already supported, including WARP (#10927).
  • FTS already has list-element document granularity and _doc_index coordinates (#7788), providing a useful traversal and result-identity precedent.

Checked against main e602c45026ecace05081c880906615e6341ab713 and #11062 head dd4f15c576ef50ce55ca1d95bcc44b2a13d4271b:

Correctness example

For cosine query [1, 0], search detections satisfying label = 'car' AND confidence > 0.9:

Parent Element ordinal Label Confidence Embedding
A 0 car 0.95 [0, 1]
A 1 person 0.99 [1, 0]
B 0 car 0.96 [0.8, 0.6]

The best eligible hit is B, element 0, with cosine distance 0.2. A parent-level any_element prefilter admits A, but searching all its vectors lets its person vector win with distance 0. Child eligibility must reach vector scoring and candidate selection.

This is a desired feature contract; the table is a semantic example, not a claim that the nested vector API already accepts this query.

Proposed initial scope

  1. Resolve a vector leaf across one list-of-struct boundary, reusing/extracting the schema-derived traversal and physical-coordinate conventions already used by FTS.
  2. Carry (parent identity, element coordinate) through exact search and an initial ANN path such as IVF_FLAT. Retain coordinates through flattening, shuffle/partition storage, filtering, candidate selection, refinement and result materialization.
  3. Apply parent eligibility and same-element scalar predicates before selecting top-k. The current listelement index can supply coarse parent pruning; scalar-leaf scans and exact element rechecks can provide the initial child mask.
  4. Return the parent identifier, matched coordinate, distance and metadata from the scored child. Preserve multiple hits from one parent unless grouping is explicitly requested.
  5. Define index metadata/routing so element search selects a coordinate-bearing representation or a correct exact fallback. Preserve existing parent-search defaults.

Coordinates are physical list positions in a pinned dataset snapshot. Filtering or skipping null/invalid elements must preserve those positions. An application-supplied child ID can provide durable identity across list edits.

Acceptance criteria

  • The example above returns B/0 for top-1; scalar predicates and vector scoring always refer to the same child.
  • Duplicate vectors/keys in different list positions remain distinguishable. Returned child metadata matches the scored coordinate.
  • Exact, indexed, mixed indexed/unindexed and refined execution use the same coordinate and eligibility semantics; exhaustive unquantized IVF search agrees with the exact reference, and ANN recall is measured against it.
  • Cover empty/null lists, null structs/vectors, sliced offsets, multiple fragments, deletes, list rewrites/overlays, compaction/remapping and historical snapshots, including stable-row-ID/FRI paths where supported.
  • Field renames follow schema identity; dropping/casting indexed leaves invalidates the affected representation appropriately.

Related: #10900, #10950, #11010, #11062, #10927, #7788.

Lingua principale
Rust
Stelle
7.3k
Fork
929
Merge medio
2g 22h
PR unite (30g)
572

Preparare l'ambiente

Apri in Codespaces

Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di lance-format/lance

Tutte le issue di lance-format/lance

Issue simili

Altre issue su Rust

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.