Effectively checking for possible duplicate objects
I have a requirement to create a list of possible duplicates before the user saves the object to the database and warns them about possible duplicates.
There are 7 criteria by which we should check for duplicates, and if there are at least 3 matches, we should mark it up to the user. The criteria will match by id, so no fuzzy string pairing is required, but my problem comes from the fact that there are many possible ways (99 ways if I did my sums with a reasonable degree of probability) for at least 3 elements corresponding list of 7 possible.
I don't want to do 99 separate db queries to find search results, and I also don't want to return the whole batch from the db and client side filter. We are probably talking about several tens of thousands of records now, but this will grow into the millions as the system matures.
Has anyone got any good efficient way to do this? I was looking into a simple OR query to get records where at least one field is the same as db and then doing some processing on the client to filter it out a little more, but some of the fields are very low cardinality and don't actually decrease the numbers by a huge amount.
Thanks, John
source to share
OR
and CASE
summation will work, but very inefficient as they don't use indexes.
You need to do UNION
for usability of indexes.
If the user enters name
, phone
, email
and address
in the database, and you want to check all the records that match at least 3
these fields, you issue:
SELECT i.*
FROM (
SELECT id, COUNT(*)
FROM (
SELECT id
FROM t_info t
WHERE name = 'Eve Chianese'
UNION ALL
SELECT id
FROM t_info t
WHERE phone = '+15558000042'
UNION ALL
SELECT id
FROM t_info t
WHERE email = '42@example.com'
UNION ALL
SELECT id
FROM t_info t
WHERE address = '42 North Lane'
) q
GROUP BY
id
HAVING COUNT(*) >= 3
) dq
JOIN t_info i
ON i.id = dq.id
This will use the indexes on those fields and the query will be fast.
Read more in this blog post:
- Match 3 of 4 : How to match a record that matches at least
3
4
possible conditions
Also see this question , which the article is based on.
If you want to have a list of values DISTINCT
in existing data, you simply wrap this query into a subquery:
SELECT i.*
FROM t_info i1
WHERE EXISTS
(
SELECT 1
FROM (
SELECT id
FROM t_info t
WHERE name = i1.name
UNION ALL
SELECT id
FROM t_info t
WHERE phone = i1.phone
UNION ALL
SELECT id
FROM t_info t
WHERE email = i1.email
UNION ALL
SELECT id
FROM t_info t
WHERE address = i1.address
) q
GROUP BY
id
HAVING COUNT(*) >= 3
)
Note that this DISTINCT
one is not transitive: if it A
matches B
and B
matches C
, it doesn't mean it A
matches C
.
source to share
You may need the following:
SELECT id
FROM
(select id, CASE fld1 WHEN input1 THEN 1 ELSE 0 "rule1",
CASE fld2 when input2 THEN 1 ELSE 0 "rule2",
...,
CASE fld7 when input7 THEN 1 ELSE 0 "rule2",
FROM table)
WHERE rule1+rule2+rule3+...+rule4 >= 3
This is untested, but it shows a way to handle this.
source to share
Have you considered using a stored procedure with a cursor? Then you can execute your OR query and then execute the records one at a time to find matches. Using a stored procedure will allow you to perform all checks on the server.
However, I think that scanning a table with millions of records will always be slow. I think you have to decide which of the 7 fields is most likely to match, make sure they are indexed.
source to share
I am assuming your system is trying to match tag IDs of a specific post or something similar. It's a multi-to-multi relationship and you must have three tables to handle it. One for messages, one for tags, and one for communication with messages and tags.
If my assumptions are correct, the best way to handle this is:
SELECT postid, count(tagid) as common_tag_count
FROM posts_to_tags
WHERE tagid IN (tag1, tag2, tag3, ...)
GROUP BY postid
HAVING count(tagid) > 3;
source to share