FA-44991 / Data systems / Open access
Merge join reuses only one build row per equal-key run · case 01
Merge join reuses only one build row per equal-key run.
ROOT CAUSE
merge-join-runs: Merge join reuses only one build row per equal-key run.
VERIFIED REPAIR
Preserve the stated physical representation and operation order: Join two key-sorted non-null relations [key,id] by matching equal-key runs. Emit the full left-major Cartesian product for each matching run. Advance the lower unmatched run and preserve physical order within equal-key runs.
Unsuccessful approach: Choosing the final build row still omits the run Cartesian product.
Case contract
Join two key-sorted non-null relations [key,id] by matching equal-key runs. Emit the full left-major Cartesian product for each matching run. Advance the lower unmatched run and preserve physical order within equal-key runs.
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=d
i=j=0; out=[]
while i<len(left) and j<len(right):
a=left[i][0]; b=right[j][0]
if a<b: i+=1; continue
if a>b: j+=1; continue
ie=i+1
while ie<len(left) and left[ie][0]==a: ie+=1
je=j+1
while je<len(right) and right[je][0]==b: je+=1
for x in left[i:ie]:
for y in right[j:j+1]: out.append([x[1],y[1]])
i,j=ie,je
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('duplicate runs', solve([[[1, 10], [1, 11]], [[1, 20], [1, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[1, 10], [2, 11]], [[2, 20]]]), [[11, 20]])
check('right gap', solve([[[2, 10]], [[1, 20], [2, 21]]]), [[10, 21]])
check('single match', solve([[[1, 10]], [[1, 20]]]), [[10, 20]])
check('no overlap', solve([[[1, 10]], [[3, 20]]]), [])
check('empty left', solve([[], [[1, 20]]]), [])
check('empty right', solve([[[1, 10]], []]), [])
elif N == 2:
check('duplicate runs', solve([[[2, 10], [2, 11]], [[2, 20], [2, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[2, 10], [3, 11]], [[3, 20]]]), [[11, 20]])
check('right gap', solve([[[3, 10]], [[2, 20], [3, 21]]]), [[10, 21]])
check('single match', solve([[[2, 10]], [[2, 20]]]), [[10, 20]])
check('no overlap', solve([[[2, 10]], [[4, 20]]]), [])
check('empty left', solve([[], [[2, 20]]]), [])
check('empty right', solve([[[2, 10]], []]), [])
elif N == 3:
check('duplicate runs', solve([[[3, 10], [3, 11]], [[3, 20], [3, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[3, 10], [4, 11]], [[4, 20]]]), [[11, 20]])
check('right gap', solve([[[4, 10]], [[3, 20], [4, 21]]]), [[10, 21]])
check('single match', solve([[[3, 10]], [[3, 20]]]), [[10, 20]])
check('no overlap', solve([[[3, 10]], [[5, 20]]]), [])
check('empty left', solve([[], [[3, 20]]]), [])
check('empty right', solve([[[3, 10]], []]), [])
elif N == 4:
check('duplicate runs', solve([[[4, 10], [4, 11]], [[4, 20], [4, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[4, 10], [5, 11]], [[5, 20]]]), [[11, 20]])
check('right gap', solve([[[5, 10]], [[4, 20], [5, 21]]]), [[10, 21]])
check('single match', solve([[[4, 10]], [[4, 20]]]), [[10, 20]])
check('no overlap', solve([[[4, 10]], [[6, 20]]]), [])
check('empty left', solve([[], [[4, 20]]]), [])
check('empty right', solve([[[4, 10]], []]), [])
elif N == 5:
check('duplicate runs', solve([[[5, 10], [5, 11]], [[5, 20], [5, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[5, 10], [6, 11]], [[6, 20]]]), [[11, 20]])
check('right gap', solve([[[6, 10]], [[5, 20], [6, 21]]]), [[10, 21]])
check('single match', solve([[[5, 10]], [[5, 20]]]), [[10, 20]])
check('no overlap', solve([[[5, 10]], [[7, 20]]]), [])
check('empty left', solve([[], [[5, 20]]]), [])
check('empty right', solve([[[5, 10]], []]), [])
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 |
|---|---|---|---|
| duplicate runs | [[10, 20], [11, 20]] | [[10, 20], [10, 21], [11, 20], [11, 21]] | Failed |
| left gap | [[11, 20]] | [[11, 20]] | Passed |
| right gap | [[10, 21]] | [[10, 21]] | Passed |
| single match | [[10, 20]] | [[10, 20]] | Passed |
| no overlap | [] | [] | Passed |
| empty left | [] | [] | Passed |
| empty right | [] | [] | Passed |
SHA-256 / 21f76ef38fa5eceb6d4fa91226ff9d37d5b89b7d173853501f952dd6725246c6
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=d
i=j=0; out=[]
while i<len(left) and j<len(right):
a=left[i][0]; b=right[j][0]
if a<b: i+=1; continue
if a>b: j+=1; continue
ie=i+1
while ie<len(left) and left[ie][0]==a: ie+=1
je=j+1
while je<len(right) and right[je][0]==b: je+=1
for x in left[i:ie]:
for y in right[je-1:je]: out.append([x[1],y[1]])
i,j=ie,je
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('duplicate runs', solve([[[1, 10], [1, 11]], [[1, 20], [1, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[1, 10], [2, 11]], [[2, 20]]]), [[11, 20]])
check('right gap', solve([[[2, 10]], [[1, 20], [2, 21]]]), [[10, 21]])
check('single match', solve([[[1, 10]], [[1, 20]]]), [[10, 20]])
check('no overlap', solve([[[1, 10]], [[3, 20]]]), [])
check('empty left', solve([[], [[1, 20]]]), [])
check('empty right', solve([[[1, 10]], []]), [])
elif N == 2:
check('duplicate runs', solve([[[2, 10], [2, 11]], [[2, 20], [2, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[2, 10], [3, 11]], [[3, 20]]]), [[11, 20]])
check('right gap', solve([[[3, 10]], [[2, 20], [3, 21]]]), [[10, 21]])
check('single match', solve([[[2, 10]], [[2, 20]]]), [[10, 20]])
check('no overlap', solve([[[2, 10]], [[4, 20]]]), [])
check('empty left', solve([[], [[2, 20]]]), [])
check('empty right', solve([[[2, 10]], []]), [])
elif N == 3:
check('duplicate runs', solve([[[3, 10], [3, 11]], [[3, 20], [3, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[3, 10], [4, 11]], [[4, 20]]]), [[11, 20]])
check('right gap', solve([[[4, 10]], [[3, 20], [4, 21]]]), [[10, 21]])
check('single match', solve([[[3, 10]], [[3, 20]]]), [[10, 20]])
check('no overlap', solve([[[3, 10]], [[5, 20]]]), [])
check('empty left', solve([[], [[3, 20]]]), [])
check('empty right', solve([[[3, 10]], []]), [])
elif N == 4:
check('duplicate runs', solve([[[4, 10], [4, 11]], [[4, 20], [4, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[4, 10], [5, 11]], [[5, 20]]]), [[11, 20]])
check('right gap', solve([[[5, 10]], [[4, 20], [5, 21]]]), [[10, 21]])
check('single match', solve([[[4, 10]], [[4, 20]]]), [[10, 20]])
check('no overlap', solve([[[4, 10]], [[6, 20]]]), [])
check('empty left', solve([[], [[4, 20]]]), [])
check('empty right', solve([[[4, 10]], []]), [])
elif N == 5:
check('duplicate runs', solve([[[5, 10], [5, 11]], [[5, 20], [5, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[5, 10], [6, 11]], [[6, 20]]]), [[11, 20]])
check('right gap', solve([[[6, 10]], [[5, 20], [6, 21]]]), [[10, 21]])
check('single match', solve([[[5, 10]], [[5, 20]]]), [[10, 20]])
check('no overlap', solve([[[5, 10]], [[7, 20]]]), [])
check('empty left', solve([[], [[5, 20]]]), [])
check('empty right', solve([[[5, 10]], []]), [])
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 |
|---|---|---|---|
| duplicate runs | [[10, 21], [11, 21]] | [[10, 20], [10, 21], [11, 20], [11, 21]] | Failed |
| left gap | [[11, 20]] | [[11, 20]] | Passed |
| right gap | [[10, 21]] | [[10, 21]] | Passed |
| single match | [[10, 20]] | [[10, 20]] | Passed |
| no overlap | [] | [] | Passed |
| empty left | [] | [] | Passed |
| empty right | [] | [] | Passed |
SHA-256 / f31ed2ff25efd2bc10cd5959fe405e2d4335868dcd2774ffe5aae25ce2ce1254
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=d
i=j=0; out=[]
while i<len(left) and j<len(right):
a=left[i][0]; b=right[j][0]
if a<b: i+=1; continue
if a>b: j+=1; continue
ie=i+1
while ie<len(left) and left[ie][0]==a: ie+=1
je=j+1
while je<len(right) and right[je][0]==b: je+=1
for x in left[i:ie]:
for y in right[j:je]: out.append([x[1],y[1]])
i,j=ie,je
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('duplicate runs', solve([[[1, 10], [1, 11]], [[1, 20], [1, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[1, 10], [2, 11]], [[2, 20]]]), [[11, 20]])
check('right gap', solve([[[2, 10]], [[1, 20], [2, 21]]]), [[10, 21]])
check('single match', solve([[[1, 10]], [[1, 20]]]), [[10, 20]])
check('no overlap', solve([[[1, 10]], [[3, 20]]]), [])
check('empty left', solve([[], [[1, 20]]]), [])
check('empty right', solve([[[1, 10]], []]), [])
elif N == 2:
check('duplicate runs', solve([[[2, 10], [2, 11]], [[2, 20], [2, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[2, 10], [3, 11]], [[3, 20]]]), [[11, 20]])
check('right gap', solve([[[3, 10]], [[2, 20], [3, 21]]]), [[10, 21]])
check('single match', solve([[[2, 10]], [[2, 20]]]), [[10, 20]])
check('no overlap', solve([[[2, 10]], [[4, 20]]]), [])
check('empty left', solve([[], [[2, 20]]]), [])
check('empty right', solve([[[2, 10]], []]), [])
elif N == 3:
check('duplicate runs', solve([[[3, 10], [3, 11]], [[3, 20], [3, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[3, 10], [4, 11]], [[4, 20]]]), [[11, 20]])
check('right gap', solve([[[4, 10]], [[3, 20], [4, 21]]]), [[10, 21]])
check('single match', solve([[[3, 10]], [[3, 20]]]), [[10, 20]])
check('no overlap', solve([[[3, 10]], [[5, 20]]]), [])
check('empty left', solve([[], [[3, 20]]]), [])
check('empty right', solve([[[3, 10]], []]), [])
elif N == 4:
check('duplicate runs', solve([[[4, 10], [4, 11]], [[4, 20], [4, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[4, 10], [5, 11]], [[5, 20]]]), [[11, 20]])
check('right gap', solve([[[5, 10]], [[4, 20], [5, 21]]]), [[10, 21]])
check('single match', solve([[[4, 10]], [[4, 20]]]), [[10, 20]])
check('no overlap', solve([[[4, 10]], [[6, 20]]]), [])
check('empty left', solve([[], [[4, 20]]]), [])
check('empty right', solve([[[4, 10]], []]), [])
elif N == 5:
check('duplicate runs', solve([[[5, 10], [5, 11]], [[5, 20], [5, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])
check('left gap', solve([[[5, 10], [6, 11]], [[6, 20]]]), [[11, 20]])
check('right gap', solve([[[6, 10]], [[5, 20], [6, 21]]]), [[10, 21]])
check('single match', solve([[[5, 10]], [[5, 20]]]), [[10, 20]])
check('no overlap', solve([[[5, 10]], [[7, 20]]]), [])
check('empty left', solve([[], [[5, 20]]]), [])
check('empty right', solve([[[5, 10]], []]), [])
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 |
|---|---|---|---|
| duplicate runs | [[10, 20], [10, 21], [11, 20], [11, 21]] | [[10, 20], [10, 21], [11, 20], [11, 21]] | Passed |
| left gap | [[11, 20]] | [[11, 20]] | Passed |
| right gap | [[10, 21]] | [[10, 21]] | Passed |
| single match | [[10, 20]] | [[10, 20]] | Passed |
| no overlap | [] | [] | Passed |
| empty left | [] | [] | Passed |
| empty right | [] | [] | Passed |
SHA-256 / 90863919ff6501a2f7ac5bae94997e43d6b6e9331863760adffe6ee264bf6546
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.649468+00:00.
Case digest / dd5f7aa2b92be8dc4d78c0ce045e535482bf66a51ee6870676ad34246b758280