Expand multi-hop patterns without materializing every intermediate row #78

Problem

Each CSR hop emits one fully materialized Arrow row per match, and the DataFusion operators above it work on those flat rows. In multi-hop patterns the number of intermediate rows multiplies at every hop, even when the query only needs counts or a few columns at the end. Factorized engines such as Kuzu and LadybugDB carry neighbour lists between operators instead and expand them only when needed.

Idea

Let CSR operators pass neighbour lists (or counts) between hops, and expand them into rows only when an operator needs individual rows, at the latest the RETURN. This is independent of how the CSR is stored.

FFX exploration

• Explore FFX-style packed factorized execution for multi-hop CSR #105 investigates packed factorized execution based on FFX: Factorized and Vectorized Execution (Yasser, Dorbani and Mhedhbi, SIGMOD 2026). It scopes compact intermediates within compatible multi-hop CSR regions using DataFusion's existing extension points, with ordinary Arrow batches at the boundary and benchmarks to check regular workloads for regressions.
• Status so far (see Explore FFX-style packed factorized execution for multi-hop CSR #105): the current benchmark workloads don't show the shape where factorization helps. The queries where lance-csr trailed were limited by how nested Cypher was flattened, not by intermediate size, and perf(planner): walk pattern predicates on the csr and keep comprehension rows once #108 fixed those relationally. If this is pursued, the direction is FFX-style packed vectors in a fused operator, not Kuzu-style list-based processing.

This is a research direction for the general mechanism below. Completing the investigation alone does not close this issue.

Done so far (post 0.6.1)

Special cases have shipped. The general mechanism has not: hops still emit one row per match.

• perf(planner): count two-hop paths from per-node degrees #97 (0.5.1) counts two-hop paths from per-node degrees (Σ_b in(b)·out(b)) instead of building them. q8 and q9 on graph-benchmark got about 80% faster. It applies only to (a)-[]->(b)-[]->(c) RETURN count(*) (or count(v)) over two directed fixed-length hops, with no grouping or DISTINCT, WHERE conjuncts that each read one hop, and fan-out statistics showing many more paths than edges.
• perf(planner): look up a grouped node's columns after grouping by id #101 (0.5.1) groups by a node's id and looks up its other columns after the aggregate (NodeLookupExec), for in-memory node tables only. Lance tables are tracked in Late-materialize a grouped node's properties from Lance node tables #99.
• perf(csr): match the join path on whole-relationship queries #113 (0.6.1), from Make use_csr=True at least match the join path on full-relationship queries #112:
  • On the CSR, the two-hop count now counts each middle node's neighbours in place (HopDegreesNode, chosen by the CountCsrDegrees optimizer rule), one row per node instead of one per edge.
  • MATCH (x)-[:R]->(m)... RETURN ..., count(x) counts each m's x neighbours in place, plans the rest of the pattern from m, and sums the counts. This works for patterns of any length and for counts grouped by properties or variables other than x and r, but only the first hop is collapsed: later hops still emit one row per match. It needs the CSR and a mean fan-out of at least two.
  • Grouping by a node's id plus its other properties groups by the id and looks the properties up after the aggregate, as WITH b already did.

Still open

• Factorized expansion between hops in general: pass neighbour lists or counts from one CsrExpandExec to the next and expand at the latest point that needs rows. Moved to Pass neighbour lists between CSR hops instead of one row per match #134.
• Counts over three or more hops, and over variable-length hops. perf(csr): match the join path on whole-relationship queries #113 collapses only the root hop of a longer pattern. Moved to Count paths of three or more hops from node degrees #135.
• Counts grouped by a variable (RETURN a, count(*)), count(DISTINCT ...), and predicates across hops (a.age < c.age). perf(csr): match the join path on whole-relationship queries #113 covers grouped counts where the counted variable is the root of a one-hop fan-out; count(DISTINCT ...) and cross-hop predicates still use the usual plan. Grouped counts moved to Count two-hop patterns grouped by a node from degrees #136; count(DISTINCT ...) and cross-hop predicates need the general mechanism, Pass neighbour lists between CSR hops instead of one row per match #134.
• Same-type hops that share an end, such as (a)-->(b)<--(c), which perf(planner): count two-hop paths from per-node degrees #97 left on the join plan. Done in perf(planner): count same-type two-hop paths that share an end #131.
• Undirected hops and OPTIONAL MATCH in counting patterns. Done in perf(planner): count two-hop paths over undirected hops #132 (undirected) and perf(planner): count two-hop paths whose second hop is optional #133 (OPTIONAL MATCH).
• Late materialization of node properties in lazy (Lance) mode: Late-materialize a grouped node's properties from Lance node tables #99. Tracked there.

Closed and split up (November 2026): each open item now has its own issue, #134, #135, #136 and #99, so that each can be scoped and closed on its own. #105, the FFX investigation, moved under #134.