Skip to content
Français

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.

Plays from YouTube. Nothing loads from YouTube until you press play. Privacy

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 notebookColab · Kaggle · GitHub

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 readyAbout 30 minutes

What you need to know

What you need on your computer

  • The project larkfield-match at 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.

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.

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.

Six records on the left: 1 G-001688 samuel green M7K4L8, 2 L-011126 samuel green M7K4L8, 3 S-007770 samuel green M7K4L8, 4 G-008438 samuel green L0H6T9, 5 G-002894 nathan green M7K4L8, 6 G-009906 jacques beaulieu J8Y1L3. Records 1 to 4 are Samuel, record 5 is his brother Nathan, record 6 is Jacques. A triangle grid has one cell for each of the 15 pairs. Six cells say same person: 1-2, 1-3 and 2-3 have a thick border, because the two records share a postcode; 1-4, 2-4 and 3-4 are dashed, because record 4 has another postcode. Cells 1-5, 2-5 and 3-5 are light blue: two people with the same postcode. The other six cells are white. Below: 6 records give 15 pairs, 6 true pairs; the same postcode gives 6 candidate pairs and keeps 3 of the 6 true pairs.
Six records make 15 pairs. Comparing only the records with the same postcode leaves 6 pairs, and keeps 3 of the 6 true pairs. Values are the clean values of Module 2 (synthetic 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.

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.

The number of pairs is n × (n − 1) / 2: it grows with the square of the number of records. This curve is computed from the formula, not measured.
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.

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.

  1. Make sure that you have the newest course files. In the folder that holds nextia-learning-labs and larkfield-match, run:

    Terminal window
    git -C nextia-learning-labs pull

    If you used the ZIP file, download it again.

  2. 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-match
    cp ../nextia-learning-labs/C39/snapshots/end-of-m03/larkfield_match/commands/allpairs.py larkfield_match/commands/

    The match command finds its subcommands by their files, so the new command works at once.

  3. Run it:

    Terminal window
    match allpairs
    60,108 records -> 1,806,455,778 pairs
    Timed 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 names
    Only 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.

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.

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.

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.

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.

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.

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.

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.

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.

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”.

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.

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 allpairs estimates 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.

Next: Blocking keys and sorted neighbourhood