Repository navigation
query_graph: multi-pattern MATCH/OPTIONAL MATCH produces a cross join when the bound variable is the pattern's target node #1404
Description
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 30Returns _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, 3390197 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: 645645 = 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:
cross_join_with_relsmultiplies every existing binding by every scannedt.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 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 in short: 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.
Activity
AmirF194 commentedon Aug 2, 2026
Update (2026-08-03): answering @tom-dyar directly, yes, this is separate from #1385 (aggregation-time, not pattern-expansion) and not filed on its own yet. Leaving it noted here for now rather than opening a fourth thread on this issue; will flag it for a follow-up filing.
Tried to reproduce this on current
main(d6be58ef, 2026-07-31), in a clean container, and the headline symptom (the 3390/645-style cross join) doesn't fire anymore.expand_additional_patterns()'snodes[0]-onlystart_boundcheck is still there, but a bound-terminal special case added for #627 (expand_from_bound_terminal, commit3f754cf44, 2026-06-27, about five weeks before this issue) now intercepts exactly the!start_bound && rel_count == 1 && term_boundshape (cypher.c:4658-4670) and drives the expansion from the boundf, instead of falling intoscan_pattern_nodes+ cross join.Minimal repro (8 functions:
helpercalled bycaller1/2/3, the rest uncalled):gives
helper: 3, everyone else:1(not a cross join, but still wrong: should be0for the uncalled ones). The remaining bug is one level further down, in aggregation rather than pattern matching:ret_agg_accumulate()(cypher.c:4224) doesentry->counts[ci]++unconditionally for every binding in the group, with no check for whether the aggregated variable is actually bound.binding_get_virtual()(cypher.c:2854) returns""for an unbound var, indistinguishable from a real value to the counter, so the rowexpand_from_bound_terminaldeliberately leaves withtunbound (to supportWHERE t IS NULL) still gets counted as a match.Plain (non-OPTIONAL)
MATCH (f:Function) MATCH (t)-[:CALLS]->(f) RETURN count(f)is unaffected and correctly gives3.For a fast re-check:
This is a different bug than the one reported here (aggregation, not pattern-expansion), so let me know if a separate issue is preferred rather than repurposing this thread.
DeusData commentedon Aug 3, 2026
Thank you for the detailed row-count analysis. Current main includes the #1385 fix (
27d9831) for the headline case where an OPTIONAL fallback row was fabricated after the execution budget filled. Your remaining observation about aggregation being capped beforeDISTINCTis a narrower correctness problem and is not discharged by that change. I have kept the issue open at high priority in0.9.1-rcwith that residual scope.tom-dyar commentedon Aug 3, 2026
That explains it — the binary I reproduced against was built from a Jun 16 checkout, 11 days before 3f754cf landed. I should have rebuilt before filing. Apologies for the noise.
One thing worth separating out: Amir's finding (ret_agg_accumulate counting unbound vars as matches via binding_get_virtual returning "") is a different code path from 27d9831. The #1385 fix addresses fabricated OPTIONAL fallback rows when the expansion budget fills; the aggregation counter bug fires after expand_from_bound_terminal correctly leaves t unbound and that unbound row reaches ret_agg_accumulate. The two fixes don't overlap. @AmirF194, if that's not already tracked separately it's probably worth a new issue.
The direction-symmetry test (queries #2 and #3 returning identical results) is still worth adding since nodes[0]-only start_bound is still there and expand_from_bound_terminal won't cover every pattern shape. But that's a suggestion, not a blocker.
AmirF194 commentedon Aug 4, 2026
Not tracked separately yet, thanks for isolating the two paths so clearly. I'd rather not open an issue on your diagnosis without reproducing it myself first, so I'll look at building a repro for the ret_agg_accumulate/binding_get_virtual path and file a dedicated issue if it holds up.
DeusData commentedon Sep 19, 2026
Thank you for correcting the build chronology. The bound-terminal change is in 3f754cf. The later null-counting observation is a separate correctness question, not evidence that #1385's budget behavior explains it. Our earlier response conflated those mechanisms. I have not verified all the reported cases on the current release, so no full-resolution claim is warranted.