Factorized intermediate results for native multi-hop traversal

Abierto
#163 3 comentarios 0 reacciones 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

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

Línea de trabajo

Comienza con crates/lance-graph/src/lance_native_planner/csr_expand.rs y lee el trabajo de recorrido nativo de la Fase 3 en #159 para entender la ruta actual de flattening. Divide la propuesta en salida de expand anidada, un límite de unfold, consumidores factorizados y encadenamiento multi-hop; la finalización requiere esas etapas además de los benchmarks indicados, pero el issue no especifica ninguna prueba concreta.

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

Descripción

The problem

Our native multi-hop traversal materializes intermediate results in flat (fully enumerated) form. expand_batch flattens the CSR adjacency immediately — for each input row it emits one output row per neighbor and take()s every carried column once per neighbor:

// crates/lance-graph/src/lance_native_planner/csr_expand.rs
for &n in csr.neighbors(src.value(row)) {
    parent_idx.push(row_u32);   // repeat the parent row
    neighbors.push(n);          // once per neighbor
}
// ...then take() duplicates every carried column once per neighbor

For a chain like (a)-[:KNOWS]->(b)-[:LIKES]->(c), the a columns get duplicated once per (b, c) path, so intermediate size grows as O(N^k) for k hops. This is the classic many-to-many blowup.

Background

KuzuDB (and the factorized-database line of work it builds on) avoids this with factorized intermediate results: keep intermediates in a compressed, Cartesian-product form so projections and aggregations push through without materializing the explosion. See What is KuzuDB.

Why this fits lance-graph well

CSR already produces the factorized group for free: csr.neighbors(src) returns a contiguous slice, which is exactly the shape of an Arrow ListArray (offset array + values), i.e. a nested child group. Today we take that naturally-nested output and flatten it. A factorized expand simply keeps the nesting — emit (parent values once) + (list of neighbors) instead of (parent values × neighbors).

It also belongs entirely in LanceNativePlanner. DataFusion's RecordBatch model is flat-relational, so factorization lives in the native operator tree, not the DataFusion fallback. This reinforces the native-planner direction in #159.

Scope and caveats

  • Survives only inside a native-operator chain. Handing a batch back to a DataFusion operator (cross-table join, sort, filter on a cross-hop expression) requires unfolding to flat. Value is proportional to how long a native chain we can keep.
  • Payoff needs consumers that push through nested form — aggregations (count, EXISTS, collect), LIMIT, degree-style queries, heavily-filtered deep traversals. For RETURN a, b, c with no aggregation the final output is the flat product anyway; factorization still saves intermediate memory/CPU but the last step enumerates.
  • Multi-hop only. Single-hop expand gets nothing (its output is just the neighbor set). This is gated on Phase 3 (multi-hop / VariableLengthExpand) in #159.

Proposed approach

  • Step 1 — nested expand output (correctness-preserving)
    • Have native expand emit a nested neighbor column (Arrow ListArray) instead of flattening
    • Add a Flatten/Unfold operator at the native → DataFusion boundary
    • Wire it so any plan can always unfold to flat (no behavior change, just a new option)
  • Step 2 — factorized consumers
    • Factorized count / EXISTS that consume the nested form without unfolding
    • Push projections through the factorized representation
    • LIMIT short-circuit over nested groups
  • Step 3 — multi-hop chains
    • Keep factorization across a chain of native expands (Phase 3 VariableLengthExpand)
    • Unfold only at the final boundary or when an operator can't consume nested input
  • Step 4 — benchmarks
    • Many-to-many multi-hop workload (flat vs. factorized) on intermediate size, memory, latency

Related

  • #159 (CSR native traversal) — this is a Phase 3 sub-track of that effort
  • Possible follow-up: worst-case optimal joins (WCOJ) for cyclic patterns (triangles), complementary to factorization
Lenguaje dominante
Rust
Estrellas
189
Forks
40
Merge medio
16 min
PR fusionados (30 d)
1

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

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-graph

Todos los issues de lance-format/lance-graph

Issues similares

Más issues de Rust

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.