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

Abierto
#11,076 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 2 días

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
8/100
Tipo de issue
Nueva funcionalidad
Claridad
Bastante claro
Estado de actividad
Activo
Stack tecnológico
rust
Área
data

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.

Lenguaje dominante
Rust
Estrellas
7.3k
Forks
929
Merge medio
2 d 22 h
PR fusionados (30 d)
572

Preparar el entorno

Abrir en Codespaces

Inicia el contenedor de desarrollo del proyecto en tu navegador, con tu propia cuenta de GitHub.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de lance-format/lance

Todos los issues de lance-format/lance

Issues similares

Más issues de Rust

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.