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.

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

Done so far (0.5.1)

Two 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 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 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 Fetch a node's properties after grouping by it, not before #99.

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.
• Counts over three or more hops, and over variable-length hops.
• Counts grouped by a variable (RETURN a, count(*)), count(DISTINCT ...), and predicates across hops (a.age < c.age).
• Same-type hops that share an end, such as (a)-->(b)<--(c), which perf(planner): count two-hop paths from per-node degrees #97 leaves on the join plan (see the shortcut: comment in count_ops.rs).
• Undirected hops and OPTIONAL MATCH in counting patterns.
• Late materialization of node properties in lazy (Lance) mode: Fetch a node's properties after grouping by it, not before #99.

Each of these can land as its own PR against this issue. Close this issue once hops pass factorized intermediates to each other in general, not when another special case lands.