Factorized intermediate results for native multi-hop traversal
Nadie ha tomado este issue todavía.
Evaluación
- Dificultad
- 5/5
- Tiempo estimado
- Más de una semana
- Aptitud para principiantes
- 35/100
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. ForRETURN a, b, cwith 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/Unfoldoperator at the native → DataFusion boundary - Wire it so any plan can always unfold to flat (no behavior change, just a new option)
- Have native expand emit a nested neighbor column (Arrow
- Step 2 — factorized consumers
- Factorized
count/EXISTSthat consume the nested form without unfolding - Push projections through the factorized representation
-
LIMITshort-circuit over nested groups
- Factorized
- 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
- Keep factorization across a chain of native expands (Phase 3
- 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
- Lee el issue completo y luego la guía de contribución del proyecto.
- Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
- Haz un fork del repositorio y trabaja en una rama.
- Abre un pull request que haga referencia al número del issue.
Más de lance-format/lance-graph
-
Dificultad 4/5 3-5 días Aptitud para principiantes 25/100
lance-format/lance-graph#171 ·
-
Dificultad 4/5 1-2 días Aptitud para principiantes 55/100
lance-format/lance-graph#170 ·
-
LDBC benchmark: insignificant performance gain from enabling Lance dataset indexes for LanceGraphAbierto
Dificultad 4/5 3-5 días Aptitud para principiantes 35/100
lance-format/lance-graph#166 · 1 comentario ·
-
Dificultad 4/5 3-5 días Aptitud para principiantes 48/100
lance-format/lance-graph#165 ·
-
Dificultad 5/5 Más de una semana Aptitud para principiantes 25/100
lance-format/lance-graph#164 ·
Todos los issues de lance-format/lance-graph
Issues similares
-
area:cli area:security bug priority:medium
Dificultad 2/5 1-3 horas Aptitud para principiantes 82/100
rtk-ai/rtk#5127 · 1 comentario ·
Los mantenedores suelen responder en 1 día
-
status: new topic: ga4gh-sdk type: bug
Dificultad 2/5 1-3 horas Aptitud para principiantes 75/100
Los mantenedores suelen responder en 1 día
-
comp-rbac
Dificultad 2/5 1-3 horas Aptitud para principiantes 68/100
ClickHouse/ClickHouse#131875 ·
Los mantenedores suelen responder en 1 día
-
Dificultad 2/5 1-3 horas Aptitud para principiantes 70/100
Los mantenedores suelen responder en 1 día
-
`gws auth login` keeps the old token cache, so API calls use a token from the previous grantAbierto
Dificultad 2/5 1-3 horas Aptitud para principiantes 80/100
googleworkspace/cli#984 ·
Los mantenedores suelen responder en 1 día