Count two-hop paths from per-node degrees instead of enumerating them #96

Problem

Queries that only count multi-hop paths spend almost all their time building paths they then throw away. In the graph-benchmark suite (100K Person nodes, 2.4M FOLLOWS edges), q8 and q9 are:

// q8
MATCH (a:Person)-[r1:FOLLOWS]->(b:Person)-[r2:FOLLOWS]->(c:Person)
RETURN count(*) AS numpaths

// q9
MATCH (a:Person)-[r1:FOLLOWS]->(b:Person)-[r2:FOLLOWS]->(c:Person)
WHERE b.age < $age_1 AND c.age > $age_2
RETURN count(*) AS numpaths

lance-csr 0.5.0 builds every one of the 58M (q8) or 45M (q9) paths before counting them. That's why it's 10 to 20 times slower than Kuzu and LadybugDB on q8, while being the fastest Cypher engine in the suite on q3 to q7 (results table).

#78 tracks the full fix: factorized expansion that passes neighbour lists between hops. This issue is a much smaller step for the common case where a query only counts paths.

Idea

When the only thing returned is a count, the number of two-hop paths through each middle node b is in(b) × out(b). So the count can be computed from per-node degrees, and filters on a, b or c just decide which edges or nodes go into those degrees:

count = Σ over b where pred(b):  #{a → b : pred(a)}  ×  #{b → c : pred(c)}

This is "eager aggregation" (Yan and Larson): the aggregate is pushed below the join on the shared node, so each side is grouped down to one row per node before the join. The work is proportional to the number of edges, not the number of paths, and it's all ordinary DataFusion: two group-bys, two joins and a sum.

I checked it on the same data using lance-csr's own SqlEngine, with the same in-memory tables, on an Apple M5 (10 cores, 24 GB):

The counts are identical: 58,431,994 for q8 and 45,362,926 for q9.

-- q8
WITH i AS (SELECT dst AS b, count(*) AS n FROM follows GROUP BY dst),
     o AS (SELECT src AS b, count(*) AS n FROM follows GROUP BY src)
SELECT sum(i.n * o.n) AS numpaths FROM i JOIN o ON i.b = o.b;

-- q9
WITH i AS (SELECT dst AS b, count(*) AS n FROM follows GROUP BY dst),
     o AS (SELECT f.src AS b, count(*) AS n
           FROM follows f JOIN person c ON c.id = f.dst
           WHERE c.age > 25 GROUP BY f.src)
SELECT sum(i.n * o.n) AS numpaths
FROM i JOIN o ON i.b = o.b JOIN person p ON p.id = i.b
WHERE p.age < 50;

A first version

Add a logical rewrite next to PushCsrTargetFilters and PruneCsrTargetColumns. It applies only when all of these hold:

• The pattern is a linear two-hop chain (a)-[r1]->(b)-[r2]->(c), in any direction.
• RETURN has only count(*), or count(x) on a node key that can't be null, with no grouping keys. Grouping by b, or by properties of b, could come later.
• Each WHERE predicate refers to only one of a, b, c, r1 or r2. Any predicate that compares two of them, like a.age < c.age, keeps the current plan.
• There's no DISTINCT, no OPTIONAL MATCH, no named path, and r1 and r2 aren't used anywhere else.

Anything else keeps the current plan.

Relationship uniqueness needs care (see #59). When r1 and r2 have the same type, a self-loop b → b is counted once in in(b) × out(b) as its own pair (r1, r2), and Cypher doesn't allow that. The rewrite has to subtract the number of self-loops at each b that pass both sides' filters. Parallel edges need no special handling: the formula counts them exactly as path expansion does.

Later steps

• Using the CSR: with use_csr=True and no filters on a, in(b) and out(b) are just differences between neighbouring CSR offsets. q8 then becomes one pass over the nodes, with no group-by at all.
• Longer chains: the same idea works hop by hop. Carry a count of paths per node and join it to the next hop's edges. Relationship uniqueness gets harder past two hops (r1 can't equal r3 either), so that needs its own design.
• Other aggregates: sum or count over properties of c, and grouping by b, follow the same pattern.

Before the rule is merged, check that it returns exactly the same counts as the current plan, using random graphs that include self-loops, parallel edges and nulls in the filtered columns, and measure both benchmark suites as CONTRIBUTING.md describes.

Related: use_csr=True is slower on this suite

On the same run, use_csr=True was slower than the default on q2 (89 vs 30 ms), q8 (166 vs 114 ms) and q9 (128 vs 91 ms), using in-memory tables. q8 and q9 name their relationships (r1, r2), so this may be the same trade-off as #92. That run is kept here.