Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

The flavour in question is PostgreSQL, but it is a generic enough query pattern that your techniques for optimising against other RDBMs should help as well.

The purpose of the query is to show all records from a table that are duplicated along several columns (user selectable).

  SELECT usr_id,
         team_name, team_streetno, team_city,
         usr_firstname, usr_lastname, usr_jobtitle, usr_department, usr_email
    FROM team c
    JOIN usr p on p.team_id=c.team_id
    JOIN
    (
        select match_firstname, match_lastname, match_jobtitle, match_department, match_email ,
               match_team_name, match_team_streetno, match_team_city 
          FROM usr
          JOIN team on usr.team_id=team.team_id
      GROUP BY match_firstname, match_lastname, match_jobtitle, match_department, match_email,
               match_team_name, match_team_streetno, match_team_city
        HAVING count(usr_id)>1
    ) AS sub
      ON sub.match_team_name = c.match_team_name
     AND sub.match_team_streetno = c.match_team_streetno
     AND sub.match_team_city = c.match_team_city
     AND sub.match_firstname = p.match_firstname
     AND sub.match_lastname = p.match_lastname
     AND sub.match_jobtitle = p.match_jobtitle
     AND sub.match_department = p.match_department
     AND sub.match_email = p.match_email
ORDER BY usr_firstname, usr_lastname, usr_jobtitle, usr_department, usr_email,
         team_name, team_streetno, team_city

The EXPLAIN output looks like this:

explain image

I tried this variation to make arrays out of the duplicated usr_id's and JOIN back to the usr table using = ANY; that increased the duration by about 15%.

 SELECT u.usr_id
     , t.team_name, t.team_streetno, t.team_city 
     , u.usr_firstname, u.usr_lastname, u.usr_jobtitle, u.usr_department, u.usr_email
  FROM (
      SELECT array_agg(u1.usr_id) dups
        FROM usr u1
        JOIN team t1 ON u1.team_id = t1.team_id
    GROUP BY match_firstname, match_lastname, match_jobtitle, match_department, match_email
           , match_team_name, match_team_streetno, match_team_city
      HAVING count(usr_id)>1
       ) AS dup
  JOIN usr u on u.usr_id = ANY (dup.dups)
  JOIN team t on t.team_id = u.team_id
ORDER BY u.usr_firstname, u.usr_lastname, u.usr_jobtitle, u.usr_department, u.usr_email
       , t.team_name, t.team_streetno, t.team_city

Look forward to your suggestions.


Consolidating comments

Tried WITH TMP AS (... ,count(*) over (partition by...) c FROM ..) WHERE c>1, which fared worse than the arrag_agg/ANY approach. Seems like windowing functions in PostgreSQL is not that great, or it needs to be rewritten in another form.

For context, consider census data. If someone else filled it for you, he may fill in Tom one year, Thomas or Tomas the next. The "match" columns are derived from the base columns.

EXISTS has been tried, but didn't perform as well as the code shown above.

share|improve this question
    
Using a derived table with COUNT(*) OVER (PARTITION BY ...) would be a test candidate. –  ypercube Feb 7 '13 at 21:07
    
And did you try the EXISTS way? –  ypercube Feb 7 '13 at 21:29
    
Also: I suppose you are talking about generic queries (no indexes on the several columns). Perhaps you should also be be comparing efficiency in regard with distribution (low or high percent of rows that match the HAVING COUNT(*)>1 condition). –  ypercube Feb 7 '13 at 21:32
    
PKs of tables may be relevant to simplify GROUP BY, depending on your version of Postgres ... –  Erwin Brandstetter Feb 7 '13 at 23:15
    
@Erwin PKs are usr_id and team_id, does that help? –  孔夫子 Feb 7 '13 at 23:22
show 6 more comments

1 Answer

Updated after OP supplied test case voiding much of this answer.

Postgres version

There is a good chance Postgres 9.2 will perform better. A lot of improvements for big data have gone into it.

Simplified query

First off, you can simplify your query quite a bit:

SELECT u.usr_id
      ,t.team_name, t.team_streetno, t.team_city
      ,u.usr_firstname, u.usr_lastname, u.usr_jobtitle, u.usr_department, u.usr_email
FROM   usr  u
JOIN   team t USING (team_id)
JOIN (
   SELECT u.match_firstname, u.match_lastname, u.match_jobtitle, u.match_department
         ,u.match_email, t.match_team_name, t.match_team_streetno, t.match_team_city
   FROM   usr  u
   JOIN   team t USING (team_id)
   GROUP  BY u.match_firstname, u.match_lastname, u.match_jobtitle, u.match_department
            ,u.match_email, t.match_team_name, t.match_team_streetno, t.match_team_city
   HAVING count(usr_id) > 1
   ) AS sub USING (match_firstname, match_lastname, match_jobtitle, match_department
                  ,match_email, match_team_name, match_team_streetno, match_team_city)
ORDER  BY u.usr_firstname, u.usr_lastname, u.usr_jobtitle, u.usr_department, u.usr_email
         ,t.team_name, t.team_streetno, t.team_city;
  • I removed the JOIN to the table team from the subquery, guessing that all the columns stem from table usr (my request for table definitions went unanswered ...) That should help a bit.
    Turns out, some of the columns belong to table team.

  • I replace the verbose equijoin conditions with the much shorter USING syntax. That's also probably slightly faster.

  • Replace count(usr_id) > 1 with count(*) > 1. Does the same here (since usr_id is the PK, ergo NOT NULL), slightly faster.

I took the test case @RichardTheKiwi posted in the comments and created an sqlfiddle from it.

I also ran a local test with temporary tables on PostgreSQL 9.1.6.
Only slightly faster than the query in the question:
1338 ms for 15137 rows (out of 70k).

EXISTS semi-joins might be a hot contender if you have many duplicates. With only a few, not so much. You already tried and ruled that out. Are you positive you tried optimal syntax?

Window function count()

You could also try if count() as window function is faster - without CTE and without additional joins. But I doubt it. I sure does make the query shorter, though:

SELECT *
FROM  (
   SELECT u.usr_id
         ,t.team_name, t.team_streetno, t.team_city
         ,u.usr_firstname, u.usr_lastname, u.usr_jobtitle, u.usr_department, u.usr_email
         ,count(*) OVER (PARTITION BY
            u.match_firstname, u.match_lastname, u.match_jobtitle, u.match_department
           ,u.match_email, t.match_team_name, t.match_team_streetno, t.match_team_city) AS ct
   FROM  usr  u
   JOIN  team t USING (team_id)
   ) x
WHERE  ct > 1
ORDER  BY usr_firstname, usr_lastname, usr_jobtitle, usr_department
         ,usr_email, team_name, team_streetno, team_city;

50% slower in my local test.

Multi-column index?

This is largely obsolete after I have seen the test case.
Indexes are obviously hard to use here, since the columns to check for dupes vary. You might be able to profile user behavior and identify the most common combinations to support those with an index. There is a more radical possibility here, though:

Postgres can use multi-column indexes, even if not all index columns are used. Performance is much better if one or more leading columns of the index are used in the condition, but it still works if not. Compare:
Working of indexes in PostgreSQL

If we can assume that most use cases will check on, for instance, (match_firstname, match_lastname), a multi-column index like the following might help. Not sure, you'll have to test:

CREATE INDEX usr_match_multi_idx
ON usr (match_firstname, match_lastname, match_jobtitle, match_department, match_email);

Columns of the index in order of decreasing usefulness. Order of columns in your GROUP BY / PARTITION BY clause is not relevant.

Index did not help in my local test - was used, but made the query ~ 20 % slower.

Partial indexes?

If the table is read-only or at least rarely written and many of your columns often have unique values, you could take this a step further. Rows with a unique value in one of the used match_* columns can be excluded right away. For columns with many unique values it would pay to either add a column match_email_mult boolean which you set TRUE if match_email is not unique for this row. Or, if you have many columns, you could use a bit(n) column or use an integer columns for an even small footprint on disk. More under this related question on SO.
Don't bother with columns with only few unique values.

CREATE INDEX usr_match_email_mult_idx ON usr (usr_id)
WHERE match_email_mult;

Repeat for all qualifying columns. Then add conditions to your query:

WHERE match_firstname_mult
AND   match_lastname_mult
AND   ...

Postgres can combine a number of bitmap index scans rather quickly. If that can weed out a large portion of the table to begin with, the query planner might switch from a sequential scan to bitmap-index scans ...

Not tested.

share|improve this answer
    
You're right, some sample data would help. So I've created a sample script that produces the distribution that I'm happy with here: pastebin.com/23grgHJp Interestingly, the array_agg/ANY approach now finishes in 1 second, whereas the code in the question takes over a minute and still won't finish! –  孔夫子 Feb 8 '13 at 2:20
    
Took 2.5 minutes to complete, the EXPLAIN output shows it taking a scenic route –  孔夫子 Feb 8 '13 at 2:35
    
@RichardTheKiwi: Your test case reveals a lot that's not in your question and voids much of my answer. I updated to refit it. –  Erwin Brandstetter Feb 8 '13 at 3:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.