RFDB Datalog hash-join shared-var bug
Problem
RFDB's Datalog engine has a fast path that kicks in once current
bindings exceed HASH_JOIN_THRESHOLD: it pulls all edges of a given
type and builds HashMap<src, Vec<dst>> (or the inverse for
incoming) for O(1) lookups per binding.
The bug: when the other end of the edge is a Term::Var whose name
is already bound in the current row (i.e. a shared variable
across two atoms), the fast path rebinds it unconditionally. Any
value that satisfies the second edge pattern in isolation gets
emitted as a "match," even when it contradicts the first atom's
bindings.
Repro
edge(M, C, "CONTAINS"), edge(C, M, "SENDS_MESSAGE")
When you want: M contains C AND C sends back to M (self-loop).
What you get with the bug: M contains C AND C sends to *any* M',
bleeding ~N false positives.
Constraining M to a concrete id returns 0 rows; free M returns many.
That delta is the symptom.
Trigger conditions
- Two
edge/3 or incoming/3 atoms share a variable, each on
opposite sides of the edge direction.
- Current bindings for the first atom exceed
HASH_JOIN_THRESHOLD
(default 256). Below that, nested-loop runs via unify which
handles bound vars correctly.
- Edge types are constants (hash-join requires const type).
Fix
In packages/rfdb-server/src/datalog/eval.rs, both
eval_edge_hash_join and eval_incoming_hash_join must check the
non-key Term::Var against bindings.get(var) before accepting a
row:
if let Term::Var(var) = dst_term {
if let Some(existing) = bindings.get(var).and_then(|v| v.as_id()) {
if existing != dst_id { continue; }
}
}
(Mirror in eval_incoming_hash_join with src_term / src_id.)
Put the check before bindings.clone() so mismatched rows are
skipped without allocation.
Verification
Regression tests in packages/rfdb-server/src/datalog/tests.rs:
test_hash_join_shared_var_across_two_edges — edge/3 self-join.test_incoming_hash_join_shared_var — incoming/3 self-join.
Both build a graph with n = HASH_JOIN_THRESHOLD + 10 triples where
exactly one pair forms a true round-trip. Without the fix, the
rule returns n rows; with the fix, 1.
How we found it
Adding MESSAGE_TYPE → CONTAINS → CALL edges to the BEAM graph and
writing a Datalog guarantee for handler self-loops surfaced 13 hits
on Ichi. Drilling into each "hit" M by binding it to a literal id
showed zero incoming CONTAINS-that-sends-back edges. Reducing to the
minimal repro edge(A, B, "CONTAINS"), edge(B, A, "CONTAINS") on a
tree-shaped graph produced 15 spurious symmetric pairs — a tree has
zero symmetric CONTAINS by construction. Cypher showed the same
rows, ruling out the Datalog reorder/parser layer and pointing at
the shared join engine.
Notes
- Nested-loop path (via
unify) is correct — the bug is isolated to
the hash-join fast path.
eval_negation_hash_join (for \+ edge(X, _, "T")) does not have
the same bug because it only projects one variable by design; the
other side is always _ / Wildcard.- If you ever add a third variant of hash-join (e.g. for path/2
transitive closure), port the same check.