{"abstract":"Merge join advances the left cursor when the right key is smaller.","category":"Data systems","checks":7,"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.","evaluation_group":"s3-data-systems-merge-join-runs","failed_approach":"Advancing both cursors skips left rows that may match later right keys.","family":"s3-data-systems-merge-join-runs-right-advance","id":"FA-44986","implementations":{"attempt":{"sha256":"fd1023a4f7b12c39836a359f2bb9b04d74e5e68200dd9e27fc069120c4d5dd7f","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(d):\n    try:\n        left,right=d\n        i=j=0; out=[]\n        while i<len(left) and j<len(right):\n            a=left[i][0]; b=right[j][0]\n            if a<b: i+=1; continue\n            if a>b: i+=1; j+=1; continue\n            ie=i+1\n            while ie<len(left) and left[ie][0]==a: ie+=1\n            je=j+1\n            while je<len(right) and right[je][0]==b: je+=1\n            for x in left[i:ie]:\n                for y in right[j:je]: out.append([x[1],y[1]])\n            i,j=ie,je\n        return out\n    except (IndexError, KeyError, ValueError, StopIteration) as exc:\n        return {\"representation_error\": type(exc).__name__}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nif N == 1:\n    check('duplicate runs', solve([[[1, 10], [1, 11]], [[1, 20], [1, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[1, 10], [2, 11]], [[2, 20]]]), [[11, 20]])\n    check('right gap', solve([[[2, 10]], [[1, 20], [2, 21]]]), [[10, 21]])\n    check('single match', solve([[[1, 10]], [[1, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[1, 10]], [[3, 20]]]), [])\n    check('empty left', solve([[], [[1, 20]]]), [])\n    check('empty right', solve([[[1, 10]], []]), [])\nelif N == 2:\n    check('duplicate runs', solve([[[2, 10], [2, 11]], [[2, 20], [2, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[2, 10], [3, 11]], [[3, 20]]]), [[11, 20]])\n    check('right gap', solve([[[3, 10]], [[2, 20], [3, 21]]]), [[10, 21]])\n    check('single match', solve([[[2, 10]], [[2, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[2, 10]], [[4, 20]]]), [])\n    check('empty left', solve([[], [[2, 20]]]), [])\n    check('empty right', solve([[[2, 10]], []]), [])\nelif N == 3:\n    check('duplicate runs', solve([[[3, 10], [3, 11]], [[3, 20], [3, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[3, 10], [4, 11]], [[4, 20]]]), [[11, 20]])\n    check('right gap', solve([[[4, 10]], [[3, 20], [4, 21]]]), [[10, 21]])\n    check('single match', solve([[[3, 10]], [[3, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[3, 10]], [[5, 20]]]), [])\n    check('empty left', solve([[], [[3, 20]]]), [])\n    check('empty right', solve([[[3, 10]], []]), [])\nelif N == 4:\n    check('duplicate runs', solve([[[4, 10], [4, 11]], [[4, 20], [4, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[4, 10], [5, 11]], [[5, 20]]]), [[11, 20]])\n    check('right gap', solve([[[5, 10]], [[4, 20], [5, 21]]]), [[10, 21]])\n    check('single match', solve([[[4, 10]], [[4, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[4, 10]], [[6, 20]]]), [])\n    check('empty left', solve([[], [[4, 20]]]), [])\n    check('empty right', solve([[[4, 10]], []]), [])\nelif N == 5:\n    check('duplicate runs', solve([[[5, 10], [5, 11]], [[5, 20], [5, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[5, 10], [6, 11]], [[6, 20]]]), [[11, 20]])\n    check('right gap', solve([[[6, 10]], [[5, 20], [6, 21]]]), [[10, 21]])\n    check('single match', solve([[[5, 10]], [[5, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[5, 10]], [[7, 20]]]), [])\n    check('empty left', solve([[], [[5, 20]]]), [])\n    check('empty right', solve([[[5, 10]], []]), [])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"37c246198cce4a6fdc28b518c9ea30594af24c22dbfb3a9c7a3b0322350eee88","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(d):\n    try:\n        left,right=d\n        i=j=0; out=[]\n        while i<len(left) and j<len(right):\n            a=left[i][0]; b=right[j][0]\n            if a<b: i+=1; continue\n            if a>b: i+=1; continue\n            ie=i+1\n            while ie<len(left) and left[ie][0]==a: ie+=1\n            je=j+1\n            while je<len(right) and right[je][0]==b: je+=1\n            for x in left[i:ie]:\n                for y in right[j:je]: out.append([x[1],y[1]])\n            i,j=ie,je\n        return out\n    except (IndexError, KeyError, ValueError, StopIteration) as exc:\n        return {\"representation_error\": type(exc).__name__}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nif N == 1:\n    check('duplicate runs', solve([[[1, 10], [1, 11]], [[1, 20], [1, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[1, 10], [2, 11]], [[2, 20]]]), [[11, 20]])\n    check('right gap', solve([[[2, 10]], [[1, 20], [2, 21]]]), [[10, 21]])\n    check('single match', solve([[[1, 10]], [[1, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[1, 10]], [[3, 20]]]), [])\n    check('empty left', solve([[], [[1, 20]]]), [])\n    check('empty right', solve([[[1, 10]], []]), [])\nelif N == 2:\n    check('duplicate runs', solve([[[2, 10], [2, 11]], [[2, 20], [2, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[2, 10], [3, 11]], [[3, 20]]]), [[11, 20]])\n    check('right gap', solve([[[3, 10]], [[2, 20], [3, 21]]]), [[10, 21]])\n    check('single match', solve([[[2, 10]], [[2, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[2, 10]], [[4, 20]]]), [])\n    check('empty left', solve([[], [[2, 20]]]), [])\n    check('empty right', solve([[[2, 10]], []]), [])\nelif N == 3:\n    check('duplicate runs', solve([[[3, 10], [3, 11]], [[3, 20], [3, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[3, 10], [4, 11]], [[4, 20]]]), [[11, 20]])\n    check('right gap', solve([[[4, 10]], [[3, 20], [4, 21]]]), [[10, 21]])\n    check('single match', solve([[[3, 10]], [[3, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[3, 10]], [[5, 20]]]), [])\n    check('empty left', solve([[], [[3, 20]]]), [])\n    check('empty right', solve([[[3, 10]], []]), [])\nelif N == 4:\n    check('duplicate runs', solve([[[4, 10], [4, 11]], [[4, 20], [4, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[4, 10], [5, 11]], [[5, 20]]]), [[11, 20]])\n    check('right gap', solve([[[5, 10]], [[4, 20], [5, 21]]]), [[10, 21]])\n    check('single match', solve([[[4, 10]], [[4, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[4, 10]], [[6, 20]]]), [])\n    check('empty left', solve([[], [[4, 20]]]), [])\n    check('empty right', solve([[[4, 10]], []]), [])\nelif N == 5:\n    check('duplicate runs', solve([[[5, 10], [5, 11]], [[5, 20], [5, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[5, 10], [6, 11]], [[6, 20]]]), [[11, 20]])\n    check('right gap', solve([[[6, 10]], [[5, 20], [6, 21]]]), [[10, 21]])\n    check('single match', solve([[[5, 10]], [[5, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[5, 10]], [[7, 20]]]), [])\n    check('empty left', solve([[], [[5, 20]]]), [])\n    check('empty right', solve([[[5, 10]], []]), [])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"90863919ff6501a2f7ac5bae94997e43d6b6e9331863760adffe6ee264bf6546","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(d):\n    try:\n        left,right=d\n        i=j=0; out=[]\n        while i<len(left) and j<len(right):\n            a=left[i][0]; b=right[j][0]\n            if a<b: i+=1; continue\n            if a>b: j+=1; continue\n            ie=i+1\n            while ie<len(left) and left[ie][0]==a: ie+=1\n            je=j+1\n            while je<len(right) and right[je][0]==b: je+=1\n            for x in left[i:ie]:\n                for y in right[j:je]: out.append([x[1],y[1]])\n            i,j=ie,je\n        return out\n    except (IndexError, KeyError, ValueError, StopIteration) as exc:\n        return {\"representation_error\": type(exc).__name__}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nif N == 1:\n    check('duplicate runs', solve([[[1, 10], [1, 11]], [[1, 20], [1, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[1, 10], [2, 11]], [[2, 20]]]), [[11, 20]])\n    check('right gap', solve([[[2, 10]], [[1, 20], [2, 21]]]), [[10, 21]])\n    check('single match', solve([[[1, 10]], [[1, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[1, 10]], [[3, 20]]]), [])\n    check('empty left', solve([[], [[1, 20]]]), [])\n    check('empty right', solve([[[1, 10]], []]), [])\nelif N == 2:\n    check('duplicate runs', solve([[[2, 10], [2, 11]], [[2, 20], [2, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[2, 10], [3, 11]], [[3, 20]]]), [[11, 20]])\n    check('right gap', solve([[[3, 10]], [[2, 20], [3, 21]]]), [[10, 21]])\n    check('single match', solve([[[2, 10]], [[2, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[2, 10]], [[4, 20]]]), [])\n    check('empty left', solve([[], [[2, 20]]]), [])\n    check('empty right', solve([[[2, 10]], []]), [])\nelif N == 3:\n    check('duplicate runs', solve([[[3, 10], [3, 11]], [[3, 20], [3, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[3, 10], [4, 11]], [[4, 20]]]), [[11, 20]])\n    check('right gap', solve([[[4, 10]], [[3, 20], [4, 21]]]), [[10, 21]])\n    check('single match', solve([[[3, 10]], [[3, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[3, 10]], [[5, 20]]]), [])\n    check('empty left', solve([[], [[3, 20]]]), [])\n    check('empty right', solve([[[3, 10]], []]), [])\nelif N == 4:\n    check('duplicate runs', solve([[[4, 10], [4, 11]], [[4, 20], [4, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[4, 10], [5, 11]], [[5, 20]]]), [[11, 20]])\n    check('right gap', solve([[[5, 10]], [[4, 20], [5, 21]]]), [[10, 21]])\n    check('single match', solve([[[4, 10]], [[4, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[4, 10]], [[6, 20]]]), [])\n    check('empty left', solve([[], [[4, 20]]]), [])\n    check('empty right', solve([[[4, 10]], []]), [])\nelif N == 5:\n    check('duplicate runs', solve([[[5, 10], [5, 11]], [[5, 20], [5, 21]]]), [[10, 20], [10, 21], [11, 20], [11, 21]])\n    check('left gap', solve([[[5, 10], [6, 11]], [[6, 20]]]), [[11, 20]])\n    check('right gap', solve([[[6, 10]], [[5, 20], [6, 21]]]), [[10, 21]])\n    check('single match', solve([[[5, 10]], [[5, 20]]]), [[10, 20]])\n    check('no overlap', solve([[[5, 10]], [[7, 20]]]), [])\n    check('empty left', solve([[], [[5, 20]]]), [])\n    check('empty right', solve([[[5, 10]], []]), [])\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"s3-data-systems-merge-join-runs-right-advance","generated_at":"2026-09-29T14:44:17.604599+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"A bounded deterministic data engine model makes representation and changelog faults reproducible.","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.","root_cause":"merge-join-runs: Merge join advances the left cursor when the right key is smaller.","sha256":"68d37dd1911c20157b8fa6b00f05b78c333e0a20d47b58acea7c0ca0fc5cb74a","title":"Merge join advances the left cursor when the right key is smaller · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":41.89,"exit_code":1,"observations":[{"actual":[[10,20],[10,21],[11,20],[11,21]],"check":"duplicate runs","expected":[[10,20],[10,21],[11,20],[11,21]],"passed":true},{"actual":[[11,20]],"check":"left gap","expected":[[11,20]],"passed":true},{"actual":[],"check":"right gap","expected":[[10,21]],"passed":false},{"actual":[[10,20]],"check":"single match","expected":[[10,20]],"passed":true},{"actual":[],"check":"no overlap","expected":[],"passed":true},{"actual":[],"check":"empty left","expected":[],"passed":true},{"actual":[],"check":"empty right","expected":[],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"duplicate runs\", \"actual\": [[10, 20], [10, 21], [11, 20], [11, 21]], \"expected\": [[10, 20], [10, 21], [11, 20], [11, 21]], \"passed\": true}, {\"check\": \"left gap\", \"actual\": [[11, 20]], \"expected\": [[11, 20]], \"passed\": true}, {\"check\": \"right gap\", \"actual\": [], \"expected\": [[10, 21]], \"passed\": false}, {\"check\": \"single match\", \"actual\": [[10, 20]], \"expected\": [[10, 20]], \"passed\": true}, {\"check\": \"no overlap\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty left\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty right\", \"actual\": [], \"expected\": [], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":43.655,"exit_code":1,"observations":[{"actual":[[10,20],[10,21],[11,20],[11,21]],"check":"duplicate runs","expected":[[10,20],[10,21],[11,20],[11,21]],"passed":true},{"actual":[[11,20]],"check":"left gap","expected":[[11,20]],"passed":true},{"actual":[],"check":"right gap","expected":[[10,21]],"passed":false},{"actual":[[10,20]],"check":"single match","expected":[[10,20]],"passed":true},{"actual":[],"check":"no overlap","expected":[],"passed":true},{"actual":[],"check":"empty left","expected":[],"passed":true},{"actual":[],"check":"empty right","expected":[],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"duplicate runs\", \"actual\": [[10, 20], [10, 21], [11, 20], [11, 21]], \"expected\": [[10, 20], [10, 21], [11, 20], [11, 21]], \"passed\": true}, {\"check\": \"left gap\", \"actual\": [[11, 20]], \"expected\": [[11, 20]], \"passed\": true}, {\"check\": \"right gap\", \"actual\": [], \"expected\": [[10, 21]], \"passed\": false}, {\"check\": \"single match\", \"actual\": [[10, 20]], \"expected\": [[10, 20]], \"passed\": true}, {\"check\": \"no overlap\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty left\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty right\", \"actual\": [], \"expected\": [], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":43.257,"exit_code":0,"observations":[{"actual":[[10,20],[10,21],[11,20],[11,21]],"check":"duplicate runs","expected":[[10,20],[10,21],[11,20],[11,21]],"passed":true},{"actual":[[11,20]],"check":"left gap","expected":[[11,20]],"passed":true},{"actual":[[10,21]],"check":"right gap","expected":[[10,21]],"passed":true},{"actual":[[10,20]],"check":"single match","expected":[[10,20]],"passed":true},{"actual":[],"check":"no overlap","expected":[],"passed":true},{"actual":[],"check":"empty left","expected":[],"passed":true},{"actual":[],"check":"empty right","expected":[],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"duplicate runs\", \"actual\": [[10, 20], [10, 21], [11, 20], [11, 21]], \"expected\": [[10, 20], [10, 21], [11, 20], [11, 21]], \"passed\": true}, {\"check\": \"left gap\", \"actual\": [[11, 20]], \"expected\": [[11, 20]], \"passed\": true}, {\"check\": \"right gap\", \"actual\": [[10, 21]], \"expected\": [[10, 21]], \"passed\": true}, {\"check\": \"single match\", \"actual\": [[10, 20]], \"expected\": [[10, 20]], \"passed\": true}, {\"check\": \"no overlap\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty left\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"empty right\", \"actual\": [], \"expected\": [], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}