FA-44946 / Data systems / Open access
Hash-join probe omits its non-equality residual · case 01
Hash-join probe omits its non-equality residual.
ROOT CAUSE
hash-join-residual: Hash-join probe omits its non-equality residual.
VERIFIED REPAIR
Preserve the stated physical representation and operation order: Probe a toy hash join whose hash bucket is integer key modulo bucket-count. Return left/right IDs for ordinary equal non-null keys AND right score>=left floor. Preserve all matching build rows and probe order. Hash equality alone never establishes row equality.
Unsuccessful approach: A constant lower bound ignores each probe row floor.
Case contract
Probe a toy hash join whose hash bucket is integer key modulo bucket-count. Return left/right IDs for ordinary equal non-null keys AND right score>=left floor. Preserve all matching build rows and probe order. Hash equality alone never establishes row equality.
Why this case matters
A bounded deterministic data engine model makes representation and changelog faults reproducible.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
try:
left,right,buckets=d
table={}
for ident,key,score in right:
if key is None: continue
table.setdefault(key%buckets,[]).append([ident,key,score])
out=[]
for ident,key,floor in left:
if key is None: continue
for other,k,score in table.get(key%buckets,[]):
if k==key: out.append([ident,other])
return out
except (IndexError, KeyError, ValueError, StopIteration) as exc:
return {"representation_error": type(exc).__name__}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
if N == 1:
check('colliding keys', solve([[[10, 1, 1]], [[20, 1, 1], [21, 4, 1]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 2]], [[20, 1, 1]], 3]), [])
check('build multiplicity', solve([[[10, 1, 1]], [[20, 1, 1], [21, 1, 2]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 6]], [[20, 4, 7]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 1]], [[20, None, 1]], 3]), [])
check('empty build', solve([[[10, 1, 1]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 1]], 3]), [])
elif N == 2:
check('colliding keys', solve([[[10, 1, 2]], [[20, 1, 2], [21, 4, 2]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 3]], [[20, 1, 2]], 3]), [])
check('build multiplicity', solve([[[10, 1, 2]], [[20, 1, 2], [21, 1, 3]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 7]], [[20, 4, 8]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 2]], [[20, None, 2]], 3]), [])
check('empty build', solve([[[10, 1, 2]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 2]], 3]), [])
elif N == 3:
check('colliding keys', solve([[[10, 1, 3]], [[20, 1, 3], [21, 4, 3]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 4]], [[20, 1, 3]], 3]), [])
check('build multiplicity', solve([[[10, 1, 3]], [[20, 1, 3], [21, 1, 4]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 8]], [[20, 4, 9]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 3]], [[20, None, 3]], 3]), [])
check('empty build', solve([[[10, 1, 3]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 3]], 3]), [])
elif N == 4:
check('colliding keys', solve([[[10, 1, 4]], [[20, 1, 4], [21, 4, 4]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 5]], [[20, 1, 4]], 3]), [])
check('build multiplicity', solve([[[10, 1, 4]], [[20, 1, 4], [21, 1, 5]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 9]], [[20, 4, 10]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 4]], [[20, None, 4]], 3]), [])
check('empty build', solve([[[10, 1, 4]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 4]], 3]), [])
elif N == 5:
check('colliding keys', solve([[[10, 1, 5]], [[20, 1, 5], [21, 4, 5]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 6]], [[20, 1, 5]], 3]), [])
check('build multiplicity', solve([[[10, 1, 5]], [[20, 1, 5], [21, 1, 6]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 10]], [[20, 4, 11]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 5]], [[20, None, 5]], 3]), [])
check('empty build', solve([[[10, 1, 5]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 5]], 3]), [])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| colliding keys | [[10, 20]] | [[10, 20]] | Passed |
| residual rejects | [[10, 20]] | [] | Failed |
| build multiplicity | [[10, 20], [10, 21]] | [[10, 20], [10, 21]] | Passed |
| probe bucket | [[11, 20]] | [[11, 20]] | Passed |
| null keys | [] | [] | Passed |
| empty build | [] | [] | Passed |
| empty probe | [] | [] | Passed |
SHA-256 / bd6eef2adab3d49910ef8043f0af294eed519caa12fcdd53c79ddbf383d71124
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
try:
left,right,buckets=d
table={}
for ident,key,score in right:
if key is None: continue
table.setdefault(key%buckets,[]).append([ident,key,score])
out=[]
for ident,key,floor in left:
if key is None: continue
for other,k,score in table.get(key%buckets,[]):
if k==key and score>=0: out.append([ident,other])
return out
except (IndexError, KeyError, ValueError, StopIteration) as exc:
return {"representation_error": type(exc).__name__}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
if N == 1:
check('colliding keys', solve([[[10, 1, 1]], [[20, 1, 1], [21, 4, 1]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 2]], [[20, 1, 1]], 3]), [])
check('build multiplicity', solve([[[10, 1, 1]], [[20, 1, 1], [21, 1, 2]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 6]], [[20, 4, 7]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 1]], [[20, None, 1]], 3]), [])
check('empty build', solve([[[10, 1, 1]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 1]], 3]), [])
elif N == 2:
check('colliding keys', solve([[[10, 1, 2]], [[20, 1, 2], [21, 4, 2]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 3]], [[20, 1, 2]], 3]), [])
check('build multiplicity', solve([[[10, 1, 2]], [[20, 1, 2], [21, 1, 3]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 7]], [[20, 4, 8]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 2]], [[20, None, 2]], 3]), [])
check('empty build', solve([[[10, 1, 2]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 2]], 3]), [])
elif N == 3:
check('colliding keys', solve([[[10, 1, 3]], [[20, 1, 3], [21, 4, 3]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 4]], [[20, 1, 3]], 3]), [])
check('build multiplicity', solve([[[10, 1, 3]], [[20, 1, 3], [21, 1, 4]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 8]], [[20, 4, 9]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 3]], [[20, None, 3]], 3]), [])
check('empty build', solve([[[10, 1, 3]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 3]], 3]), [])
elif N == 4:
check('colliding keys', solve([[[10, 1, 4]], [[20, 1, 4], [21, 4, 4]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 5]], [[20, 1, 4]], 3]), [])
check('build multiplicity', solve([[[10, 1, 4]], [[20, 1, 4], [21, 1, 5]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 9]], [[20, 4, 10]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 4]], [[20, None, 4]], 3]), [])
check('empty build', solve([[[10, 1, 4]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 4]], 3]), [])
elif N == 5:
check('colliding keys', solve([[[10, 1, 5]], [[20, 1, 5], [21, 4, 5]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 6]], [[20, 1, 5]], 3]), [])
check('build multiplicity', solve([[[10, 1, 5]], [[20, 1, 5], [21, 1, 6]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 10]], [[20, 4, 11]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 5]], [[20, None, 5]], 3]), [])
check('empty build', solve([[[10, 1, 5]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 5]], 3]), [])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| colliding keys | [[10, 20]] | [[10, 20]] | Passed |
| residual rejects | [[10, 20]] | [] | Failed |
| build multiplicity | [[10, 20], [10, 21]] | [[10, 20], [10, 21]] | Passed |
| probe bucket | [[11, 20]] | [[11, 20]] | Passed |
| null keys | [] | [] | Passed |
| empty build | [] | [] | Passed |
| empty probe | [] | [] | Passed |
SHA-256 / f74e83dbd1b21e1c4cbe29099255bfff0f4ea2753cc3d42585b478a438ff5ded
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
try:
left,right,buckets=d
table={}
for ident,key,score in right:
if key is None: continue
table.setdefault(key%buckets,[]).append([ident,key,score])
out=[]
for ident,key,floor in left:
if key is None: continue
for other,k,score in table.get(key%buckets,[]):
if k==key and score>=floor: out.append([ident,other])
return out
except (IndexError, KeyError, ValueError, StopIteration) as exc:
return {"representation_error": type(exc).__name__}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
if N == 1:
check('colliding keys', solve([[[10, 1, 1]], [[20, 1, 1], [21, 4, 1]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 2]], [[20, 1, 1]], 3]), [])
check('build multiplicity', solve([[[10, 1, 1]], [[20, 1, 1], [21, 1, 2]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 6]], [[20, 4, 7]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 1]], [[20, None, 1]], 3]), [])
check('empty build', solve([[[10, 1, 1]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 1]], 3]), [])
elif N == 2:
check('colliding keys', solve([[[10, 1, 2]], [[20, 1, 2], [21, 4, 2]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 3]], [[20, 1, 2]], 3]), [])
check('build multiplicity', solve([[[10, 1, 2]], [[20, 1, 2], [21, 1, 3]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 7]], [[20, 4, 8]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 2]], [[20, None, 2]], 3]), [])
check('empty build', solve([[[10, 1, 2]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 2]], 3]), [])
elif N == 3:
check('colliding keys', solve([[[10, 1, 3]], [[20, 1, 3], [21, 4, 3]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 4]], [[20, 1, 3]], 3]), [])
check('build multiplicity', solve([[[10, 1, 3]], [[20, 1, 3], [21, 1, 4]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 8]], [[20, 4, 9]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 3]], [[20, None, 3]], 3]), [])
check('empty build', solve([[[10, 1, 3]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 3]], 3]), [])
elif N == 4:
check('colliding keys', solve([[[10, 1, 4]], [[20, 1, 4], [21, 4, 4]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 5]], [[20, 1, 4]], 3]), [])
check('build multiplicity', solve([[[10, 1, 4]], [[20, 1, 4], [21, 1, 5]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 9]], [[20, 4, 10]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 4]], [[20, None, 4]], 3]), [])
check('empty build', solve([[[10, 1, 4]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 4]], 3]), [])
elif N == 5:
check('colliding keys', solve([[[10, 1, 5]], [[20, 1, 5], [21, 4, 5]], 3]), [[10, 20]])
check('residual rejects', solve([[[10, 1, 6]], [[20, 1, 5]], 3]), [])
check('build multiplicity', solve([[[10, 1, 5]], [[20, 1, 5], [21, 1, 6]], 3]), [[10, 20], [10, 21]])
check('probe bucket', solve([[[11, 4, 10]], [[20, 4, 11]], 3]), [[11, 20]])
check('null keys', solve([[[10, None, 5]], [[20, None, 5]], 3]), [])
check('empty build', solve([[[10, 1, 5]], [], 3]), [])
check('empty probe', solve([[], [[20, 1, 5]], 3]), [])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| colliding keys | [[10, 20]] | [[10, 20]] | Passed |
| residual rejects | [] | [] | Passed |
| build multiplicity | [[10, 20], [10, 21]] | [[10, 20], [10, 21]] | Passed |
| probe bucket | [[11, 20]] | [[11, 20]] | Passed |
| null keys | [] | [] | Passed |
| empty build | [] | [] | Passed |
| empty probe | [] | [] | Passed |
SHA-256 / 508738571753ebae91fc3f3393289d3951c8f3fb58c6830546ffb74e51fcf9d6
Verification & scope
Offline stipulated semantics over valid small inputs; no performance, concurrency, or production-engine conformance claim. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:44:17.237726+00:00.
Case digest / b4ee969b7c621d1a6a8c836e1a7c891c258c8b534ea347fbbe4e9ffcfcae0149