Explore FFX-style packed factorized execution for multi-hop CSR #105

Parent: #78

Problem

CsrExpandExec emits one flat Arrow row per match. Its bounded batches control memory per chunk, but each hop still repeats earlier bindings and property columns before the next hop can filter or aggregate them. #97 avoids this for a narrow two-hop count, and #101 delays node-property lookup after grouping in memory. General compact intermediates between hops remain open.

Explore whether FFX's execution methodology can address that remaining gap while preserving regular query performance and DataFusion's planning and execution framework. This is an investigation, not a commitment to adopt the full FFX engine.

Paper

Sunny Yasser, Anas Dorbani and Amine Mhedhbi. Factorized and Vectorized Execution: Optimizing Analytical and Semantic Queries over Relations. Proceedings of the ACM on Management of Data 4(3), Article 178, June 2026 (SIGMOD 2026).

• Paper PDF
• DOI: 10.1145/3802055
• Reference implementation

The relevant parts are packed factorized vectors (§4), join evaluation (§5.1), cascade updates (§5.2), and analytical evaluation (§§7.2–7.3). FFX keeps values in contiguous buffers, with offsets describing parent–child groups and masks tracking active values. This permits branching factorization layouts while batching work across multiple parents. Cascade updates propagate invalidations through dependent groups.

Treat the evaluation as motivation, not a lance-csr speedup estimate. The end-to-end comparisons use in-memory execution with spilling disabled, exclude compilation time, and select factorization-friendly orderings. Outer and anti-joins are unsupported. The largest reported gains use MIN aggregation to avoid output enumeration, and some packed plans are slower than their unpacked counterparts. DataFusion is not an evaluated baseline.

Proposed investigation

Start with a small, compatible multi-hop CSR region implemented as a custom DataFusion ExecutionPlan. Keep intermediates compact inside that region and emit ordinary Arrow batches with the original schema and row semantics at its boundary. Use the existing optimizer and CsrExtensionPlanner hooks; retain DataFusion's default planning and ordinary operators elsewhere.

Questions to resolve:

• Representation: carry node IDs, edge occurrences, parent-binding references, offsets and selection masks without copying every earlier column per match. Query bindings can revisit the same node: grouping must preserve multiplicity and relationship-reuse rules.
• Traversal and grouping order: compare a left-to-right chain with a layout rooted at a middle node, where independent left and right branches remain separate until needed. High fan-out alone does not establish a benefit; account for selective starting nodes, predicates, skew and the eventual output size.
• Filtering: evaluate supported branch-local predicates with DataFusion expressions before combining branches. Propagate empty groups correctly. Predicates comparing independent branches, such as a.age < c.age, require combination-aware evaluation or expansion at that boundary.
• Consumers: test ordinary row-returning queries as well as compatible aggregates. A generic COUNT(*) cannot infer how many paths a compact group represents. Preserve perf(planner): count two-hop paths from per-node degrees #97's simpler rewrite where it applies; grouped or longer-path counts need their own correctness argument.
• Materialization: fetch properties only when a predicate or output needs them. Coordinate with Fetch a node's properties after grouping by it, not before #99 for lazy node lookup and Read relationship columns once on large named hops from Lance #102 for named relationship columns; reducing intermediate computation does not remove scattered Lance I/O costs.

Arrow list arrays could store groups, but ordinary DataFusion operators do not interpret sibling lists as an implicit Cartesian product. Keep that interpretation within the custom region. Choose a physical rewrite or a logical extension based on the information required to recognize and plan the supported pattern, and document that choice.

First experiment and boundaries

Use a three- or four-hop directed pattern with independent branches and a selective downstream predicate. Include an ordinary row-returning version so the experiment addresses work beyond the two-hop count already optimized by #97. Use low-fan-out and selective-start variants as controls.

Initially support fixed-length inner matches with clearly defined predicates and binding semantics. Leave OPTIONAL MATCH, undirected and variable-length traversal, cross-branch predicates, and unsupported aggregates on their existing plans. For initial experiments, distinct relationship types can isolate representation costs; do not extend eligibility to same-type hops without preserving the current relationship-reuse semantics.

Retain bounded chunks, cancellation, backpressure and correct partitioning. Bound and account for retained memory through DataFusion's facilities. A query returning every path still has to produce every result row, even if earlier work is reduced.

Acceptance

• Record the supported shapes, representation, DataFusion extension points, expansion boundaries, and a conservative eligibility/cost rule. Unsupported or unprofitable shapes keep their existing plans.
• Build a focused prototype and compare its results with existing CSR and join execution. Cover repeated bindings, parallel edges, self-loops, empty groups, null predicates, deleted edges, chunk boundaries and supported relationship-reuse rules. Verify fallback for unsupported shapes.
• Report a table of planning time, execution time, peak memory and intermediate work for the target patterns and controls. Distinguish synthetic experiments from suite results.
• Before proposing a performance change, follow CONTRIBUTING.md: release wheels from main and the branch, both benchmark suites, both memory and lazy modes, alternating repeated runs, every query and result check reported. Do not change benchmark queries, expected answers or runner settings. Investigate regressions beyond observed run-to-run noise.
• Conclude whether the measured benefit justifies the implementation and identify the smallest production follow-up, or document why it does not.

Completing this investigation does not close #78. That issue still requires general factorized intermediates between hops. Porting FFX's full engine, general join-order search and its LLM operators are outside this investigation.