Same match having different match_key values

[lucazav]

Hi all,

after appling the predict() function to a linker and then exporting all to a Pandas dataframe using the as_pandas_dataframe() function, I can see that the same matching pair appears multiple times with a different matching_key value. Is this correct? I expect a matching pair to be associated with the first blocking rule it matches.

Thank you!

[RobinL]

You're right, if the data is identical they should have the same match key. Could it be something like whitespace or other unusual characters meaning they look identical but are in fact different? Don't suppose you're able to share a reproducible example? Appreciate that may be hard.

By 'the same matching pair ' do you mean identical records with different unique IDs? The results should not have duplicate pairs (by unique id) if things are working correctly

[lucazav]

Here the repro using the file as attachment:

import os
import re
import pandas as pd

from splink.duckdb.linker import DuckDBLinker
from splink.duckdb.comparison_template_library import name_comparison
import splink.duckdb.comparison_library as cl

# %%
def clean_string(input_string):
    # Convert to lower case
    cleaned_string = input_string.lower()
    
    # Remove trailing spaces
    cleaned_string = cleaned_string.strip()
    
    # Remove special characters
    cleaned_string = re.sub(r'[^a-zA-Z0-9\s]', '', cleaned_string)
    
    return cleaned_string


# %%
# https://www.cs.utexas.edu/users/ml/riddle/data.html

main_path = r'C:\<your-path>'

restaurants_df = pd.read_csv(os.path.join(main_path, 'restaurants.csv'),
                             skipinitialspace=True)

restaurants_df["name"] = restaurants_df["name"].apply(lambda x: clean_string(x))
restaurants_df["addr"] = restaurants_df["addr"].apply(lambda x: clean_string(x))
restaurants_df["city"] = restaurants_df["city"].apply(lambda x: clean_string(x))

restaurants_df


# %%
settings = {
    "link_type": "dedupe_only",
    "blocking_rules_to_generate_predictions": [
       "l.name = r.name and l.addr = r.addr",
       "l.name = r.name and l.city = r.city",
       "l.name LIKE CONCAT('%',r.name,'%') or r.name LIKE CONCAT('%',l.name,'%')",
    ],
    "comparisons": [
        name_comparison("name", jaro_winkler_thresholds=[0.9, 0.8]),
        name_comparison("addr", jaro_winkler_thresholds=[0.9, 0.8]),
        cl.exact_match("city"),
    ],
    "unique_id_column_name": "id",
    "retain_matching_columns": True,
    "retain_intermediate_calculation_columns": True,
    "max_iterations": 10,
    "em_convergence": 0.0001     
}

linker = DuckDBLinker(restaurants_df, settings)


# %%
linker.estimate_u_using_random_sampling(max_pairs=1e6)

# %%
training_blocking_rule = "l.name = r.name and l.addr = r.addr"
training_session_names = linker.estimate_parameters_using_expectation_maximisation(training_blocking_rule)

# %%
training_blocking_rule = "l.name = r.name and l.city = r.city"
training_session_names = linker.estimate_parameters_using_expectation_maximisation(training_blocking_rule)

# %%
training_blocking_rule = "l.city = r.city and l.addr = r.addr"
training_session_names = linker.estimate_parameters_using_expectation_maximisation(training_blocking_rule)

# %%
df_predict = linker.predict()

matches_df = df_predict.as_pandas_dataframe()
matches_df

I'm using the Splink version 3.9.3 on Windows with the following input file:
restaurants.zip

[RobinL]

Thanks. Will try to take a look later - on my phone right now. In the results of predict(), are the duplicate rows showing the same or different values in the comparison vector columns (the columns that begin gamma_ and contain integer values).

(If they're showing the same gamma values but a different match key, then that would suggest quite strongly this is a bug)

[RobinL]

@lucazav OK, I agree - this looks like a bug. Thanks very much for spotting it and reporting, and especially the reprex which made it very easy to track down the source

The following query shows a problematic record:

sql = f"""
select *
from {df_predict.physical_name}
where 
name_l = 'cafe bizou' and 
name_r = 'cafe bizou' and 
addr_l = '14016 ventura blvd' and 
addr_r = '14016 ventura blvd' 
"""
linker.query_sql(sql)

and the problematic sql seems to be:

from __splink__df_concat_with_tf as l
            inner join __splink__df_concat_with_tf as r
            on
            l.name LIKE CONCAT('%',r.name,'%') or r.name LIKE CONCAT('%',l.name,'%')
            AND NOT (coalesce((l.name = r.name and l.addr = r.addr), false) OR coalesce((l.name = r.name and l.city = r.city), false))
            where l."id" < r."id"

[RobinL]

aha - so that reveals the source of the bug (and how you can temporarily fix that before we do a proper fix):
Your blocking rule:
l.name LIKE CONCAT('%',r.name,'%') or r.name LIKE CONCAT('%',l.name,'%')
contains an OR,
but that OR then is 'evaluated too broadly' when it's interpolated into the SQL.

You want:

from __splink__df_concat_with_tf as l
            inner join __splink__df_concat_with_tf as r
            on
            (l.name LIKE CONCAT('%',r.name,'%') or r.name LIKE CONCAT('%',l.name,'%'))
            AND NOT (coalesce((l.name = r.name and l.addr = r.addr), false) OR coalesce((l.name = r.name and l.city = r.city), false))
            where l."id" < r."id"

Note the additional parenthesis.

So, the short term fix is:

"blocking_rules_to_generate_predictions": [
        "l.name = r.name and l.addr = r.addr",
        "l.name = r.name and l.city = r.city",
        "(l.name LIKE CONCAT('%',r.name,'%') or r.name LIKE CONCAT('%',l.name,'%'))",
    ],

I have logged this as an issue here. The fix should be simple - we just need to wrap all blocking rules in parentheses just in case, here. I.e. literally just add open and close parenthesis in that line. If you fancy being a Splink contributor feel free to do a PR! Otherwise we will do it sometime soon.

I should note that the presence of an OR condition in a blocking rule results in all possible comparisons (the cartesian product) having to be created and then the blocking conditions evaluated, so for large datasets its typically inadvisable. Of course, in this case, since the data is small, it doesn't matter.

[lucazav]

Great!! 🙂

[NickCrews]

I should note that the presence of an OR condition in a blocking rule results in all possible comparisons (the cartesian product) having to be created and then the blocking conditions evaluated

@RobinL can you explain more what you mean here? I think that the LIKE operator is the thing that would cause a cartesian product, not the OR (because it is not hash-joinable). Because of course, we OR together all the blocking rules, and that had better not cause a cartesian product.

[RobinL]

@NickCrews
You're right - the like condition results in a cartesian join. But the OR condition within a single blocking rule does as well.

You're also correct that the list of blocking_rules_for_prediction has an implicit OR condition between each blocking rule in the list, but that isn't how it's actually implemented in the SQL.

Instead it is implemented as a UNION ALL to ensure:

• the equi-join conditions are executed efficiently
• and also so the different blocking rules can be executed in parallel in e.g. Spark

To give an example, consider:

blocking_rules_for_prediction = 
  [
    "l.first_name = r.first_name",
    "l.surname = r.surname"
  ]

When blocking occurs, this results in sql like:

select ..
from input_dfs as l
inner join input_dfs as r
on l.first_name = r.first_name

UNION ALL

 select ..
from input_dfs as l
inner join input_dfs as r
on l.surname = r.surname AND NOT (l.first_name = r.first_name)

Note the second blocking rule has the AND NOT (any of the preceding blocking rules) to prevent duplication of record comparisons.

The bug here is that if a blocking rule itself has an OR condition, then this logic is broken.

Consider if the first blocking rule was l.first_name = r.first_name OR l.dob = r.dob

Then the

on l.surname = r.surname AND NOT (l.first_name = r.first_name)

becomes

on l.surname = r.surname OR l.dob = r.dob AND NOT (l.first_name = r.first_name)

But it should be

on (l.surname = r.surname OR l.dob = r.dob) AND NOT (l.first_name = r.first_name)

Equi-joins and efficiency

Note that if you put ORs beween the blocking rules like this:

select ..
from input_dfs as l
inner join input_dfs as r
on l.first_name = r.first_name OR l.surname = r.surname

Then that would result in the cartesian product being produced, because l.first_name = r.first_name OR l.surname = r.surname is not an equi-join condition and so usually SQL engines can't run it efficiently.

We have recently started work to highlight this to the user better.

Specifically, we're using SQLGlot to detect equi join conditions vs non equi join conditions. See this

In particular, in Splink on master you can now see BlockingRules are 'aware' of their _join_conditions and _filter_conditions (here)

So you can now run e.g.:

from splink.blocking import BlockingRule


brs = [
"l.first_name = r.first_name AND l.surname = r.surname",
"l.first_name = r.first_name OR l.surname = r.surname",
"l.name LIKE CONCAT('%',r.name,'%')",
"l.first_name = r.surname",
"l.name LIKE CONCAT('%',r.name,'%') or r.name LIKE CONCAT('%',l.name,'%')"
]

for br in brs:
  br = BlockingRule(br)
  print("---")
  print(f"{br._join_conditions=}")
  print(f"{br._filter_conditions=}")

output:

---
br._join_conditions=[('first_name', 'first_name'), ('surname', 'surname')]
br._filter_conditions=''
---
br._join_conditions=[]
br._filter_conditions='l.first_name = r.first_name OR l.surname = r.surname'
---
br._join_conditions=[]
br._filter_conditions="l.name LIKE CONCAT('%', r.name, '%')"
---
br._join_conditions=[('first_name', 'surname')]
br._filter_conditions=''

Note the last one actually fails because it can't be parsed by sqlglot - seems like a bug.

As you can see this is currently not part of the public API anywhere. That's because we're still deciding what these things should be called and how we can use them.

[NickCrews]

Then that would result in the cartesian product being produced, because l.first_name = r.first_name OR l.surname = r.surname is not an equi-join condition and so usually SQL engines can't run it efficiently.

Oh interesting, that is not what I would have expected, I would have thought than an engine would treat an AND just like an OR, but you are right, at least with duckdb at https://shell.duckdb.org/:

CREATE OR REPLACE TABLE t as SELECT * FROM 'https://shell.duckdb.org/data/tpch/0_01/parquet/orders.parquet' LIMIT 100;
EXPLAIN ANALYZE SELECT * FROM t as t1 JOIN t as t2 on t1.o_custkey = t2.o_custkey and t1.o_orderkey=t2.o_orderkey;
EXPLAIN ANALYZE SELECT * FROM t as t1 JOIN t as t2 on t1.o_custkey = t2.o_custkey or t1.o_orderkey=t2.o_orderkey;

Being able to analyze these conditions is super important and I bet a common pitfall, I'm excited to see where that goes! I'll take a look at how you did that.