query_graph: multi-pattern MATCH/OPTIONAL MATCH produces a cross join when the bound variable is the pattern's target node

[tom-dyar]

Summary

Any multi-pattern query whose second pattern's relationship points into a variable bound by the first returns a Cartesian product instead of a constrained expansion. No error is raised. The result looks plausible and is wrong.

MATCH (f:Function)
OPTIONAL MATCH (t)-[:CALLS]->(f)
RETURN f.name, count(t)

f is bound. The second pattern's target is f; its source t is fresh. CBM ignores the binding on f, scans every node for t, and cross-joins. Reversing the arrow so the bound variable is the source is correct. Same graph shape, two syntaxes, different results.

Plain MATCH is affected identically (see below).

Reproduction

Project with 197 nodes, 17 Function nodes, 20 total CALLS-into-Function edges (ground truth established four independent ways).

#	Query	Result	Correct?
1	MATCH (t)-[:CALLS]->(f:Function) RETURN f.name, count(t)	sums to 20	yes
2	MATCH (f:Function) OPTIONAL MATCH (f)<-[:CALLS]-(t) RETURN f.name, count(t)	sums to 20	yes
3	MATCH (f:Function) OPTIONAL MATCH (t)-[:CALLS]->(f) RETURN f.name, count(t)	sums to 3390	NO

#2 and #3 are the same pattern written two ways. #3 is a cross join.

Row-level confirmation:

MATCH (f:Function) OPTIONAL MATCH (t)-[:CALLS]->(f) RETURN f.name, t.name LIMIT 30

Returns _dense paired with ARTICLE.md, Dockerfile, Description, a string literal config value — none of which has a CALLS edge at all.

Count arithmetic:

MATCH (f:Function) OPTIONAL MATCH (t)-[:CALLS]->(f) RETURN count(f), count(t)
-- result: 3390, 3390

197 nodes × 17 functions = 3390. Exactly the Cartesian product. count(t) equalling count(f) means every t was bound — no row was left optional-empty, which correct evaluation would produce for 13 of the 17 functions (zero callers).

Plain MATCH:

MATCH (f:Function) MATCH (t)-[:CALLS]->(f) RETURN count(f)
-- truth: 20, result: 645

645 = 43 × 15 (43 total CALLS edges, 15 outer rows). The inner pattern runs standalone against all edges once per outer row, then f is rebound from the result. Non-matching combinations are dropped, which is why plain MATCH looks less obviously wrong while being equally broken.

Independently reproduced on a second, much larger project. Per-group counts came back as an arithmetic sequence with step equal to that project's group size — the cross-join signature.

Root cause

expand_additional_patterns() in src/cypher/cypher.c:

const char *nvar = patn->nodes[0].variable ? patn->nodes[0].variable : "_n_extra";
bool start_bound = *bind_count > 0 && binding_get(&(*bindings)[0], nvar) != NULL;

if (start_bound && patn->rel_count > 0) {
    expand_pattern_rels(...);   // correct path
} else {
    scan_pattern_nodes(...);    // scans ALL nodes matching nodes[0]
    cross_join_with_rels(...);  // wrong path
}

start_bound checks only nodes[0]. In (t)-[:CALLS]->(f) that is t, which is unbound, so the else-branch runs even though f — nodes[1] — is already bound and should constrain the expansion.

Two things compound it:

1. cross_join_with_rels multiplies every existing binding by every scanned t.
2. binding_set (line 1986) overwrites a variable already present:

for (int i = 0; i < b->var_count; i++) {
    if (strcmp(b->var_names[i], var) == 0) {
        node_fields_free(&b->var_nodes[i]);
        node_deep_copy(&b->var_nodes[i], node);   // clobbers the outer f
        return;
    }
}

f is not merely unconstrained — it is rebound to whatever the expansion reached. That is why f.name in the row dump shows values unrelated to the outer MATCH.

The bug: a bound variable at a non-zero position in a later pattern is treated as fresh, then overwritten.

Suggested fix

start_bound should scan all nodes in the pattern, not just nodes[0]:

int bound_idx = -1;
for (int ni = 0; ni < patn->node_count; ni++) {
    const char *v = patn->nodes[ni].variable;
    if (v && *bind_count > 0 && binding_get(&(*bindings)[0], v) != NULL) {
        bound_idx = ni;
        break;
    }
}

With bound_idx > 0 two approaches are viable:

(a) Walk incoming edges from the bound node — the correct fix, O(edges) not O(nodes).
(b) Keep the forward scan but filter rather than rebind: when binding_set targets a variable already present, require node equality and drop the row on mismatch. Smaller change, fixes the clobbering class generally, but keeps the full-node scan.

The regression test invariant is direction-symmetry: (a)-[:R]->(b) and (b)<-[:R]-(a) must return identical result sets when either node is bound. Queries #2 and #3 above are ready-made for it.

Workarounds (both verified)

Write the bound variable first and reverse the arrow: OPTIONAL MATCH (f)<-[:CALLS]-(t). Exact, no client-side work.

For set difference: skip OPTIONAL MATCH entirely, do a plain MATCH, diff in the client.

Related

#1293 — inbound anti-join with OPTIONAL MATCH silently returns 0 rows. Different symptom, same area of the code.