FA-44941 / Data systems / Open access
Hash-join probe treats bucket equality as key equality · case 01
Hash-join probe treats bucket equality as key equality.
ROOT CAUSE
hash-join-residual: Hash-join probe treats bucket equality as key equality.
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: Comparing hashes again still does not reject colliding unequal keys.
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 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, 21]] | [[10, 20]] | Failed |
| 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 / dc565abc8fb2c9bf4be4c4db5cb8dabddf0e2e879406d3e015f6f39774e2d0a1
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%buckets==key%buckets 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, 21]] | [[10, 20]] | Failed |
| 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 / 8fea72086ab1142eba010595ef943a0a2f1674205a9a86e81dfaa8a9cc2cd062
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.196231+00:00.
Case digest / 29f507d03715188be4518cb878ebb6addb9d33f8aa9a6b8cf99b53f4e1885d16