CiviCRM Community Forums (archive)

While dedupe is better than it was in 2.1, it's still mostly unusable on large datasets.  Running a rule manually with just one field (and no length) works ok, but for anything with more than one field or using a length will take hours or days (and likely timeout before it completes).  Even more dangerous is that this tends to lock up the tables in question preventing INSERTs and UPDATEs to the table while the dedupe is in process.  But with some small changes we can reduce the SQL time from a few days to a few minutes.  

Currently the main query looks like this:

CREATE TEMPORARY TABLE dedupe
SELECT t1.contact_id id1, t2.contact_id id2, 5 weight
FROM civicrm_email t1
JOIN civicrm_email t2
   ON (SUBSTR(t1.email, 1, 6) = SUBSTR(t2.email, 1, 6))
WHERE t1.contact_id < t2.contact_id
  AND (t1.contact_id IN (12,88,121,156,164,169,170) OR t2.contact_id IN (12,88,121,156,164,169,170))
UNION ALL SELECT t1.id id1, t2.id id2, 5 weight
FROM civicrm_contact t1
JOIN civicrm_contact t2
  USING (first_name)
WHERE t1.id < t2.id
  AND (t1.id IN (12,88,121,156,164,169,170) OR t2.id IN (12,88,121,156,164,169,170));
Those IN() clauses will only exist if you are deduping a group rather than the entire set of contacts.  Unfortunately even deduping a group of 30k contacts against a total of 600k contacts still takes several hours.  An additional UNION will be made for each additional field that you add to the dedupe rule.  The crazy JOIN with the SUBSTRING functions is caused by using a length on the given field.  

Lets run EXPLAIN on this:
*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: t1
         type: ALL
possible_keys: FK_civicrm_email_contact_id
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 597673
        Extra:
*************************** 2. row ***************************
           id: 1
  select_type: PRIMARY
        table: t2
         type: ALL
possible_keys: PRIMARY,FK_civicrm_email_contact_id
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 597673
        Extra: Using where
*************************** 3. row ***************************
           id: 2
  select_type: UNION
        table: t1
         type: index
possible_keys: PRIMARY,index_first_name
          key: index_first_name
      key_len: 195
          ref: NULL
         rows: 565324
        Extra: Using index
*************************** 4. row ***************************
           id: 2
  select_type: UNION
        table: t2
         type: ref
possible_keys: PRIMARY,index_first_name
          key: index_first_name
      key_len: 195
          ref: democrats_civicrm_staging.t1.first_name
         rows: 4
        Extra: Using where; Using index
*************************** 5. row ***************************
           id: NULL
  select_type: UNION RESULT
        table: <union1,2>
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: NULL
        Extra:

Ouch, there's a full table scan on both tables in the first query. The total number of rows analyzed in this query is 357,215,276,225 to dedupe 15 contacts.  I've never seen it finish running even for just 15 contacts (and I've waited hours).  I'm not even going to calculate the rows analyzed to dedupe all 600k contacts.  

There's a number of ways that we can improve this:
1) The JOIN with no index is the big killer, create a new temporary table before inserting into dedupe. MySQL can't use an index on this JOIN because of the string functions.  So instead we can take all values, truncate them and put them into another temporary table before inserting into dedupe.  The challenge being that our dedupe query joins the table to itself which TEMPORARY tables can't do.  Instead we can use a MEMORY table.  

2) Use MEMORY tables instead of TEMPORARY TABLES.  Which has the added benefit of being much faster than a temporary MyISAM table (which is what this likely is since we don't specify an engine).  This will however require checking the max_heap_table_size session value and increasing if necessary to avoid running out of space and checking the available RAM.  Which we should probably be doing anyway - if a dedupe table gets sent to disk it will never finish and take down the server.  In the example below deduping a group with 30k records civicrm_temp_dedupe is 184MB.  Also since MEMORY TABLES are available to all sessions we'd need to use a random string suffix on tables names to avoid collisions.  See
http://dev.mysql.com/doc/refman/5.1/en/memory-storage-engine.html
This also means that we should Create the temporary table before we insert into.  

3) Split the IN() OR IN() into 2 queries.  MySQL doesn't seem to be able to utilize indexes well in this situation.  

4) Create the temporary table before we insert into it and don't use a UNION.    This means that MySQL doesn't need to try to combine all the results before inserting it in the table.  Just let MySQL be smart about it.  This also means that we can add indexes to the temporary tables to improve our subsequent actions.

Here's my modified example.  

SET SESSION max_heap_table_size = 1024 * 1024 * 1024;

DROP TABLE IF EXISTS civicrm_temp_email_truncated;

CREATE TABLE civicrm_temp_email_truncated (
  contact_id INT(8) UNSIGNED NULL DEFAULT NULL,
  email VARCHAR(6) NULL DEFAULT NULL,
  INDEX (contact_id),
  INDEX (email)
) ENGINE MEMORY;

INSERT INTO civicrm_temp_email_truncated (contact_id, email)
SELECT contact_id, LEFT(email, 6)
FROM civicrm_email;

DROP TABLE IF EXISTS civicrm_temp_dedupe;

CREATE TABLE civicrm_temp_dedupe (
  contact_id_1 INT(8) UNSIGNED NULL DEFAULT NULL,
  contact_id_2 INT(8) UNSIGNED NULL DEFAULT NULL,
  weight INT(2) UNSIGNED NULL DEFAULT 0
--  ,INDEX (contact_id_1, contact_id_2)
) ENGINE MEMORY;

INSERT INTO civicrm_temp_dedupe (contact_id_1, contact_id_2, weight)
SELECT t1.contact_id AS contact_id_1, t2.contact_id AS contact_id_2, 3 AS weight
FROM civicrm_temp_email_truncated t1
INNER JOIN civicrm_temp_email_truncated t2
  ON t1.email = t2.email
WHERE
  t1.contact_id < t2.contact_id
  AND t1.contact_id IN (12,88,121,156,164,169,170,217,220,267,293,350,361,418,496,519,532,555,565,574,578,595,705,711,725,756,774,781,782,793,837,838,843,846,914,932,949,950,955);

INSERT INTO civicrm_temp_dedupe (contact_id_1, contact_id_2, weight)
SELECT t1.contact_id AS contact_id_1, t2.contact_id AS contact_id_2, 3 AS weight
FROM civicrm_temp_email_truncated t1
INNER JOIN civicrm_temp_email_truncated t2
  ON t1.email = t2.email
WHERE
  t1.contact_id < t2.contact_id
  AND t2.contact_id IN (12,88,121,156,164,169,170,217,220,267,293,350,361,418,496,519,532,555,565,574,578,595,705,711,725,756,774,781,782,793,837,838,843,846,914,932,949,950,955);

INSERT INTO civicrm_temp_dedupe (contact_id_1, contact_id_2, weight)
SELECT t1.id AS contact_id_1, t2.id AS contact_id_2, 5 weight
FROM civicrm_contact t1
JOIN civicrm_contact t2
  USING (first_name)
WHERE t1.id < t2.id
  AND t1.id IN (12,88,121,156,164,169,170,217,220,267,293,350,361,418,496,519,532,555,565,574,578,595,705,711,725,756,774,781,782,793,837,838,843,846,914,932,949,950,955);

INSERT INTO civicrm_temp_dedupe (contact_id_1, contact_id_2, weight)
SELECT t1.id AS contact_id_1, t2.id AS contact_id_2, 5 weight
FROM civicrm_contact t1
JOIN civicrm_contact t2
  USING (first_name)
WHERE t1.id < t2.id
  AND t2.id IN (12,88,121,156,164,169,170,217,220,267,293,350,361,418,496,519,532,555,565,574,578,595,705,711,725,756,774,781,782,793,837,838,843,846,914,932,949,950,955);

SELECT contact_id_1, contact_id_2, SUM(weight) AS threshold
FROM civicrm_temp_dedupe
GROUP BY contact_id_1, contact_id_2
HAVING threshold >= 7;

The SQL above executes in a mere few seconds.  For deduping a group of 30k contacts takes 300 seconds.  

The biggest offender is the final query.  I would've thought that a multi-key index on contact_id_1,contact_id_2 would be good but EXPLAIN tells me that it isn't utilized.  It's a full table scan with no indexes being used.  One technique would be to send only those rows that exist more than once to a third temp table.  But that might be difficult.   There's a dichotomy of temp table size vs. performance that needs to be balanced.  

Unfortunately this won't work on the entire 600k contacts because civicrm_temp_dedupe takes too much memory (with max_heap_table_size set to 2GB it still runs out of space (and gets sent to disk)).  Deduping that many contacts may not be feasible with any technique short of moving the data to a separate beefy server, deduping, and then moving it back.  

I'm proposing to the client that we make these modifications and submit a patch.  I'll let you know if they agree, but I thought I should start this dialogue either way.  

Doesn't doing the merge in a new tab avoid the list having to rebuild - though of course you have to remember who you have merged.

As for the memory table, isn't it a high risk than the server will be dead slow to other users because it is running low on memory ?

Have you tried solving the 1 that looks like the biggest problem and instead of doing 2 in memory do it on the disk with myisam and the index ?

X+

Not sure myisam (or archive) isn't more appropriate as you don't need any transaction integrity. What you'd need is a  an enhanced flat file where you can add an index, ie. myISAM.

X+

@torenware Thanks for the ideas.  I implemented most of them (or something similar) into my original proposal.  

The last hurdle is the final query which takes about 90% of the time:

SELECT contact_id_1, contact_id_2, SUM(weight) AS threshold
FROM civicrm_temp_dedupe
GROUP BY contact_id_1, contact_id_2
HAVING threshold >= 7;

Which does a full scan and temp table.  Which makes sense, MySQL needs to create sums for every combination of contact_id_1 and contact_id_2 so it needs to use a temp table.  It has no indexes on this temp table which is possibly why it takes so much time.  I think this can be avoided by creating a third MEMORY table and manually.  Something like (my stored procedure knowledge is pretty slim) (and I haven't compared, or even executed this one):


DROP TABLE IF EXISTS civicrm_temp_dedupe_results;

CREATE TABLE civicrm_temp_dedupe_results (
  contact_id_1 INT(8) UNSIGNED NULL DEFAULT NULL,
  contact_id_2 INT(8) UNSIGNED NULL DEFAULT NULL,
  score INT(2) UNSIGNED NULL DEFAULT 0,
  PRIMARY (contact_id_1, contact_id_2)
) ENGINE MEMORY;

CREATE PROCEDURE calculateDedupeResults()
BEGIN
  DECLARE done BOOLEAN DEFAULT FALSE;
  DECLARE c1, c2 INT(8);
  DECLARE weight INT(2);
  DECLARE cur1 CURSOR FOR SELECT contact_id_1, contact_id_2 FROM civicrm_temp_dedupe d;
  DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = TRUE;

  OPEN cur1;

  REPEAT
    FETCH cur1 INTO c1, c2, weight;
    IF NOT done THEN
        INSERT INTO civicrm_temp_dedupe_results (contact_id_1, contact_id_2, score) VALUES (c1,c2, weight) ON DUPLICATE KEY UPDATE score = score + weight;
    END IF;
  UNTIL done END REPEAT;

  CLOSE cur1;
END

calculateDedupeResults();



Sean how many contacts do you run this against?  I think the last few queries will run into the same problem I had: full table scans and more temp tables sent to disk. 

Hi guys,

I'm really interested in what you guys are trying here,

We currently have CiviCRM deployment from 50k contacts to 250k contacts. We are planning to use it for 500k to 1 million contacts.

I just wanted to throw in my 2 cents here because I think that regardless of query optimization and database tuning, MySQL just has its limits. Physically speaking I don't know how we can optimize the query enough to not perform a full table scan at some point. Also there is the performance vs complexity issue with creating multiple temporary tables.

Coming from another CRM system, I liked one of the things that they did for the de-duping process:

Instead of utilizing the hardware stack and DB server to process the entire database for De-duping, I'm thinking about the preventative approach of stopping duplicate contacts to be created in the first place.

Although I have not dealt with the every aspect of the system, I believe de-dedupe should be a 2 prong approach.

***********************************************************
1. Prevent duplicate contacts to be created in the first place.

Contacts are created in the following senario:

1. Importing process (dupe check here)
2. API call for creating contacts (dupe check here)
3. Activities (making contribution, register for event, using a profile form, etc etc)

Activities here is the culprit because when a user completes the activity, if he or she does not log into the CMS, CiviCRM does not make a connection of that visitor to the contact record, therefore creating a duplicate contact.

This has happened to me many times when I was testing contribution pages.

I believe the solution would be to apply the same de-duping rules on the activities so that the person completing the activities will be merged with an existing contact if rules are matched.

So for example, if I fill in a contribution form and in the form the First Name, Last Name and Email matches an existing contact in the system and first name, last name and email match is the de-dupe rule currently being used then contribution activity should be recorded to the existing contact rather than creating a new contact.


I believe this kind of auto merge can help prevent duplicate contacts to be created in the first place and therefore minimize the need for a resource intensive process.

/***********************************
 2. Thinking about duplicates contextually


For us, we don't like dupe contacts mainly because we do a lot of email marketing and we really DO NOT want to send the same email twice or more times to the same person, so I believe the ability to contextually filter the contacts you want to perform dedupe on is important as well.

So for example, I can filter my contacts like (only people who have made a contribution before) or contacts who have received mailing from us and is not on hold or removed DO NOT EMAIL.

This way we can subset and only perform de-duping on the contacts that we care about.



Let me know what you guys think,



Cheers!


Chang

And if I understand your question, deduping a subset is possible.  Create a group of the contacts in your set and just dedupe that group.