The Beeston projectA sort-merge join on NG9: 535 records against 1,671 postcodes
Two open tables, one shared key, two ways to match them, and a count of the work each way takes.
The first table comes from the Food Standards Agency's open ratings service. For Broxtowe it returned 812 records on the day we read it, and 535 of them carry a postcode beginning NG9. The learner keeps only the postcode from each record; no business is named or rated in this project. The second table is Ordnance Survey's Code-Point Open, which lists 1,671 postcodes in NG9, each with a map position. Joining the two would give every record a location. The task is to find, for each of the 535 records, its row in the postcode list.
Joining 535 NG9 records to 1,671 NG9 postcodes, comparisons counted in our Python run| Method | Comparisons | Records matched |
|---|
| Nested loop, never stopping early | 893,985 | 442 |
| Nested loop, stopping at the first match | 482,587 | 442 |
| Sort-merge: sort the 535 keys | 4,011 | |
| Sort-merge: sort the 1,671 keys | 1,701 | |
| Sort-merge: two-pointer merge | 3,858 | 442 |
| Sort-merge, all three steps | 9,570 | 442 |
The nested loop compares every record with every postcode until it finds a partner: 482,587 comparisons even when it stops at the first match. The sort-merge join sorts both lists, then places one pointer at the top of each. If the two keys are equal, that is a match. If not, the pointer on the smaller key moves down one row, because a sorted list guarantees nothing earlier can match it. Neither pointer ever moves backwards, so the merge needs only 3,858 comparisons. Adding the cost of both sorts gives 9,570, roughly 50 times fewer than the nested loop. Sorting the postcode list was cheap, 1,701 comparisons for 1,671 keys, because the file arrives almost in order and Python's built-in sort takes advantage of that.
Both methods agree on the result: 442 records matched and 93 did not. The 93 are the interesting part. In 91 of them the postcode field holds only "NG9", because the agency publishes a partial address for some records, and a partial key can never equal a full one. The other 2 have a full postcode that the current Code-Point Open release does not list. A learner who reports "535 records joined" without checking has silently lost one row in six. Counting the unmatched rows, and finding out why, is part of the join.
Ages 8 to 11
Match two piles of numbered cards unsorted, then sorted, and count how many looks each takes.
Ages 11 to 15
Write the nested loop in Python with a comparison counter and watch it grow as the lists lengthen.
Ages 15 and up
Code the two-pointer merge, confirm it matches the nested loop, and explain every unmatched row.
Open data, used carefully
Ratings records are Food Standards Agency open data and postcodes are from OS Code-Point Open, both under the Open Government Licence (Code-Point Open contains OS data © Crown copyright and database right 2026, and Royal Mail data © Royal Mail copyright and database right 2026). We used postcodes only. The comparison counts are ours and will change as either table is updated.
