Why all pairs is impossible
- Lesson 8
- 30 min
- Module 3: Blocking: do not compare everything
Where we are
We measured exact rules on all our records. A fuzzy matcher must compare records that are not equal, and there are very many pairs. In this lesson, we count the pairs, time them on a laptop, and meet the idea of candidate pairs.
Lesson 8 of 29 · Entity Resolution and Record Matching: Is This the Same Thing?Why all pairs is impossible
1. The matching problem
2. Clean first, then match exactly
3. Blocking: do not compare everything
4. Compare records: similarity measures
5. Probabilistic linkage
6. Learned matching: classifiers, embeddings and language models
7. From pairs to entities
8. Run matching in production
What you will be able to do
See why a matcher cannot compare every record with every other record. Count the pairs, time them on your laptop, and meet the idea that the rest of this module builds on: candidate pairs.
NotebookCount, time and block in a notebook
The notebook counts the pairs of TermLarkfieldA made-up Canadian online shop for home and garden products. It is not a real company. All Nextia courses use its help desk and data as the example.Learn more Meet Larkfield’s records and times a small comparison. Then you make your first blocking key and measure what it keeps. Its setup cells download the data, so it needs no local setup.
Colab and Kaggle open your own copy. They need a free Google or Kaggle account. Stuck? See the solution notebook.
Before you startWhat to know and to have ready
What you need to know
- True pairs, pair precision and pair recall, from False merges and missed matches and Measure a matcher.
- The clean values of each record (name, email, phone, postcode, date of birth), from Normalise.
What you need on your computer
- The project
larkfield-matchat the end of Module 2, as in Meet the records, with its virtual environment active. Or use the notebook only.
Tested on macOS with Python 3.12.13. The Windows (PowerShell) commands are written the same way, but we did not test them.
The clinic’s filing cabinets
Section titled “The clinic’s filing cabinets”Think of the clinic again. The new clerk must find every patient who has two cards. She has 600 cards. She could take card 1 and compare it with each of the other 599 cards. Then card 2 with the 598 cards after it. And so on, to the end.
That is 179,700 comparisons. At one comparison a second, it takes her about 50 hours.
She does not do that. She sorts the cards into drawers by the first letters of the surname. Then she compares cards only inside one drawer. “Gagnon” is never compared with “Smith”. That takes her an afternoon.
She can miss a patient. If one card says “Gagnon” and the other card has a typing error in the first letter, the two cards land in different drawers. She accepts that risk, because the other way never ends.
A matcher has the same problem, and it uses the same idea.
Every pair, counted
Section titled “Every pair, counted”A matcher decides “same or not” for a pair of records. To find every customer with two records, it must look at every pair that could be one customer.
How many pairs do n records make? Record 1 pairs with the n − 1 others. Record 2 pairs with the n − 2 after it. Add these up and you get:
pairs = n × (n − 1) / 2
Look at a tiny example first. Six records of Larkfield’s synthetic data: four records of Samuel Green, one of his brother Nathan, and one of Jacques Beaulieu. You met Samuel and Nathan in Meet the records.
Text description of the diagram
Six records on the left: four of Samuel Green (records 1 to 4), one of his brother Nathan (record 5), and one of Jacques Beaulieu (record 6). Record 4 is Samuel’s old record, with the postcode L0H6T9; the other Green records have M7K4L8. The triangle grid has one cell for each pair: 15 cells. Six cells are true pairs, the pairs among Samuel’s four records. Three of them have a thick border: both records have the postcode M7K4L8. Three are dashed: they include record 4, with its old postcode. Three light-blue cells pair Nathan with one of Samuel’s records: two people with the same postcode. The other six cells are white: different people and different postcodes.
Six records make 6 × 5 / 2 = 15 pairs. Only 6 of them are true pairs. That is already 40% of the pairs, because we picked the example. In the real data, true pairs are very rare.
Larkfield’s pairs
Section titled “Larkfield’s pairs”Now put in Larkfield’s numbers. There are 60,108 customer records:
60,108 × 60,107 / 2 = 1,806,455,778 pairs, about 1.8 billion.
Only 27,677 of these pairs are true pairs. That is about 1 pair in 65,000. Almost every pair that a matcher compares is two different people.
The number of pairs grows with the square of the number of records. Ten times more records give about a hundred times more pairs. The chart shows the curve.
Text description of the chart
A line chart. The horizontal axis is the number of records, from 0 to 100,000. The vertical axis is the number of pairs, from 0 to 5 billion. The line is flat at first and then bends up steeply. At 10,000 records it is at 0.05 billion pairs; at 60,108 records, Larkfield’s data, at 1.8 billion; at 100,000 records, at 5 billion.
Doubling Larkfield’s records would not double the work. It would make it about four times larger.
How long would it take?
Section titled “How long would it take?”A count does not tell you the time. So measure it. The project has a command for this in Module 3. It times a very small comparison on 200,000 random pairs, and multiplies.
-
Make sure that you have the newest course files. In the folder that holds
nextia-learning-labsandlarkfield-match, run:Terminal window git -C nextia-learning-labs pullIf you used the ZIP file, download it again.
-
Go into your project folder, with the TermVirtual environmentA folder with its own Python and its own packages, for one project. Packages that you install there do not change other projects.Learn more Isolate dependenciesPython for Practical AI Engineering active. Copy the command file of this lesson from the snapshot
end-of-m03:Terminal window cd larkfield-matchcp ../nextia-learning-labs/C39/snapshots/end-of-m03/larkfield_match/commands/allpairs.py larkfield_match/commands/Terminal window cd larkfield-matchCopy-Item ..\nextia-learning-labs\C39\snapshots\end-of-m03\larkfield_match\commands\allpairs.py larkfield_match\commands\The
matchcommand finds its subcommands by their files, so the new command works at once. -
Run it:
Terminal window match allpairs60,108 records -> 1,806,455,778 pairsTimed 200,000 random pairs: 7.06 microseconds per pair (one CPU core)All pairs would take about 3.5 hours for one simple comparison of the namesOnly to store the pairs as two 4-byte numbers each: 14.5 GB of memory
Your time will differ. We ran it on a laptop that was busy with other work. On the same laptop with nothing else running, the same command printed 2.04 microseconds per pair and “about 1.0 hours”. A microsecond is a millionth of a second.
What the numbers mean
Section titled “What the numbers mean”The comparison in match allpairs is tiny. It only asks how many letters two names have in common. A real matcher compares five or more fields, and each comparison is slower. So the real time is many hours, not one.
A fast library helps, but not enough. We timed the Jaro-Winkler similarity of the rapidfuzz library, which you meet in Module 4. It needs 0.34 microseconds a pair. All pairs would still take 0.17 hours, for one field. And the pairs must be compared again after every change to the matcher.
The last line is worse. Only to hold the pairs, as two record numbers each, needs 14.5 GB of memory. The course’s laptop has 16 GB in all. A matcher that builds every pair fills the memory before it compares anything. Then the computer becomes very slow, or the program stops.
And Larkfield is small. A company with 1 million records has about 500 billion pairs.
The idea: candidate pairs
Section titled “The idea: candidate pairs”Most pairs are not worth a look. Take a customer in Montréal and another customer in Ontario who share no name, no email, no phone and no postcode. No sensible matcher would call them one person. So do not compare them.
A candidate pair is a pair that has some chance to be one customer. A matcher compares only the candidate pairs. Every other pair is called “different” without a look.
Blocking is the step that chooses the candidate pairs. The name comes from the drawers of the clinic: records go into blocks, and only records in the same block are compared. In the steps of a matcher, blocking comes after normalising and before comparing.
The simplest way to make blocks is a blocking key: one value that the records of one customer usually share. For example, the postcode. Two records become a candidate pair when they have the same key.
The tiny example, blocked
Section titled “The tiny example, blocked”Look at the six records again. Block them on the postcode:
| Block (postcode) | Records | Candidate pairs |
|---|---|---|
| M7K4L8 | 1, 2, 3, 5 | 6 |
| L0H6T9 | 4 | 0 |
| J8Y1L3 | 6 | 0 |
The blocking leaves 6 candidate pairs out of 15. Three of them are true pairs (the thick cells in the picture). Three are Nathan with his brother: the comparison step must say “different” for them. And three true pairs are lost: record 4 has Samuel’s old postcode, so it never meets his other records.
Blocking always has these two sides. It removes most pairs, and the matcher becomes fast. But a true pair that the blocking removes is lost for good. No later step can find it, because no later step sees it.
Two numbers for a blocking
Section titled “Two numbers for a blocking”So we measure every blocking with two numbers:
- Pair completeness: the share of true pairs that are candidates. It is the recall of the blocking. In the example: 3 of 6 = 0.5.
- Reduction ratio: the share of all pairs that the blocking removes. In the example: 1 − 6/15 = 0.6.
A good blocking has both close to 1: it removes almost every pair, and keeps almost every true pair.
Block Larkfield on the postcode
Section titled “Block Larkfield on the postcode”Now the real data. The project does this in the next lesson, but you can already see the result. On all 60,108 records, the postcode makes 89,630 candidate pairs. It keeps 23,388 of the 27,677 true pairs:
- pair completeness = 23,388 / 27,677 = 0.845
- reduction ratio = 1 − 89,630 / 1,806,455,778 = 0.99995
Read the second number with care. The postcode removes 99.995% of the pairs. The matcher now compares 89,630 pairs, not 1.8 billion. In our runs, making these candidate pairs took between 0.06 and 2.3 seconds.
But the first number says that 15.5% of true pairs are lost. The next lessons find better keys. The project’s default blocking, keys, uses five keys together. It makes 1,108,591 candidate pairs, keeps 0.9937 of the true pairs, and still removes 99.939% of all pairs.
The same idea in search
Section titled “The same idea in search”You may know this idea from search. A search engine does not score every document for a query. It first takes a small set of candidates from an index, and then ranks only those. Search and Ranking: Find the Best Match teaches this in Two-stage ranking. Blocking is the first stage of a matcher.
When to block, and what it costs
Section titled “When to block, and what it costs”Use blocking whenever you have more than a few thousand records. At 1,000 records there are 499,500 pairs: a laptop compares them all in seconds. At 10,000 records there are about 50 million pairs: slow, but possible once. At 60,000 records and more, blocking is not a choice.
You can skip it for a one-time check of a small list, or when you link a few new records to a list. One new record against 60,108 known records makes only 60,108 pairs.
What it costs: blocking loses the true pairs whose records do not share a key. You must measure this loss, with pair completeness, every time you change the keys. The last lesson of this module, What blocking loses, does it in detail.
Common mistake
A key that every record shares
Symptom: in the notebook, you try the source list as a blocking key: "shop", "loyalty" or "garden". The cell stops with an error:
ValueError: This key makes 700,893,447 pairs: too many to hold in memory. Use a narrower key.Without the guard, the laptop becomes very slow, and the notebook stops after some minutes.
Cause: a key with few values makes huge blocks. The shop block has 31,128 records, and 31,128 records make 484 million pairs on their own. The three blocks together make 700,893,447 pairs: 39% of all pairs. A key with one value for every record makes all 1.8 billion pairs. The notebook’s helper counts the pairs from the block sizes first, and refuses a key that makes more than 20 million.
Fix: use a key with many values and small blocks: a postcode, a phone, the start of a surname. Count the pairs of a key before you build them: the pairs of a block of size k are k × (k − 1) / 2. Add them up over the blocks.
Consequence in AI work: a self-join (a table joined to itself on one column) has the same risk in SQL and in pandas. One common value, such as an empty string or “unknown”, can make a block of thousands of records. SQL and Data Preparation for AI shows how a join can multiply rows in Join tables. Always count before you join.
Knowledge check
Section titled “Knowledge check”Check your understanding
Larkfield buys a second garden-centre chain, and its list grows from 60,108 to 120,216 records. About how many pairs does it have now, and about how much longer does a comparison of all pairs take?
Show the answer
120,216 × 120,215 / 2 = 7,225,883,220 pairs: about 7.2 billion. That is four times 1.8 billion, not two times, because the number of pairs grows with the square of the number of records. So the comparison of all pairs takes about four times longer, and storing the pairs needs about four times the memory: about 58 GB.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Check your understanding
In the tiny example, the postcode makes 6 candidate pairs from the 6 records. Which true pairs are lost, and why can no later step find them?
Show the answer
The lost pairs are 1–4, 2–4 and 3–4: record 4 (G-008438) is Samuel Green’s old record, with the postcode L0H6T9. His other records have M7K4L8. Record 4 is alone in its block, so it is never paired with them. Later steps (compare, score, cluster) only see candidate pairs. A pair that is not a candidate is never compared, so it is always called “different”.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Check your understanding
Tomás says: “The postcode blocking has a reduction ratio of 0.99995. That is almost perfect.” What is missing from his judgement?
Show the answer
The reduction ratio only says how many pairs the blocking removes. It says nothing about the true pairs that it removes. The postcode keeps only 23,388 of the 27,677 true pairs: its pair completeness is 0.845. So 15.5% of the true pairs are lost before any comparison. A blocking must be judged on both numbers. A key that removes every pair has a reduction ratio of 1 and is useless.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Recap
- n records make n × (n − 1) / 2 pairs. Larkfield’s 60,108 records make 1,806,455,778 pairs, and only 27,677 of them are true pairs.
- The pairs grow with the square of the records.
match allpairsestimates about one hour for one tiny comparison on a quiet laptop, and 14.5 GB only to hold the pairs. - A matcher compares only candidate pairs. Blocking chooses them, for example with a blocking key such as the postcode.
- Pair completeness is the share of true pairs that blocking keeps. The reduction ratio is the share of all pairs that it removes. The postcode alone: 0.845 and 0.99995.
- A true pair that blocking removes is lost for good.
The postcode loses the customers who moved. Next, you build keys from other fields, use several keys together, and try a sliding window over sorted names.