Skip to content

Pass neighbour lists between CSR hops instead of one row per match #134

Open
0 of 1 issue completed
Open

Description

@prrao87

Problem

Each CSR hop emits one Arrow row per match, and the DataFusion operators above it work on those flat rows. In a multi-hop pattern the intermediate rows multiply at every hop, even when the query needs only a count or a few columns at the end. Factorized engines such as Kuzu and LadybugDB pass neighbour lists between operators instead, and expand them only when an operator needs individual rows.

The counting rewrites (#97, #113, #131, #132, #133) avoid this for particular count shapes by counting from node degrees. They can't help when the answer depends on which paths exist, not only how many there are:

  • count(DISTINCT c) over a multi-hop pattern;
  • conditions that read more than one hop, such as WHERE a.age < c.age;
  • queries that return rows rather than a count.

Idea

Let CSR operators pass neighbour lists (or counts) from one hop to the next, and expand them into rows at the latest point that needs them, at the latest the RETURN. This is independent of how the CSR is stored.

#105 investigated packed factorized execution based on FFX: Factorized and Vectorized Execution (Yasser, Dorbani and Mhedhbi, SIGMOD 2026). The current benchmark workloads don't show the shape where it helps: the queries where lance-csr trailed were limited by how nested Cypher was flattened, which #108 fixed, not by intermediate size. If this is pursued, the direction is FFX-style packed vectors in a fused operator, not Kuzu-style list-based processing, and it starts with a workload that shows the intermediate blowup.

Split from #78.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions