I'm trying to perform a common task, deleting duplicates from a table with the aim of adding a unique constraint.

CREATE TABLE IF NOT EXISTS item_identifier (
    prefix   INTEGER NOT NULL,
    suffix   VARCHAR(1024) NOT NULL
CREATE INDEX temp_prefix_suffix_idx ON item_identifier (prefix, suffix);

I want to delete duplicates using a common query that can be found in many answers on this site. I think the rate of duplicates runs to about 1%, so there are not many to remove.

Index is provided purely to help this de-duplicate and will be dropped later. Though, as you see, it isn't even used by PostgreSQL!

There are 2,759,559,168 rows. The temp_prefix_suffix_idx index itself is ~ 100 GB. The CREATE INDEX took 12 hours so I don't expect the DELETE to be quick. But from a 10% sample set I extrapolated that it would take 20 hours, and it's already taken 40 hours. It's probably still within the margin of error for my sample method, but I am worried that this will take exponential time due to it not using indexes.

This EXPLAIN has Seq Scan on item_identifier a and Seq Scan on item_identifier b.

EXPLAIN DELETE FROM item_identifier a
    (SELECT FROM item_identifier b
       WHERE a.prefix = b.prefix
       AND a.suffix = b.suffix
       AND a.pk > b.pk);
                                                QUERY PLAN
 Delete on item_identifier a  (cost=1168440103.12..1233224771.45 rows=0 width=0)
   ->  Merge Semi Join  (cost=1168440103.12..1233224771.45 rows=919853056 width=12)
         Merge Cond: ((a.prefix = b.prefix) AND ((a.suffix)::text = (b.suffix)::text))
         Join Filter: (a.pk > b.pk)
         ->  Sort  (cost=584220051.56..591118949.48 rows=2759559168 width=52)
               Sort Key: a.prefix, a.suffix
               ->  Seq Scan on item_identifier a  (cost=0.00..57175596.68 rows=2759559168 width=52)
         ->  Materialize  (cost=584220051.56..598017847.40 rows=2759559168 width=52)
               ->  Sort  (cost=584220051.56..591118949.48 rows=2759559168 width=52)
                     Sort Key: b.prefix, b.suffix
                     ->  Seq Scan on item_identifier b  (cost=0.00..57175596.68 rows=2759559168 width=52)

Can I assume that PostgreSQL is making the right choice with not using an index?

As another point of reference, another commonly suggested method gives similar results:

explain DELETE FROM item_identifier
        SELECT pk, row_number() OVER w as rnum
        FROM item_identifier
        WINDOW w AS (
            PARTITION BY prefix, suffix
            ORDER BY pk)
    ) t
WHERE t.rnum > 1);
                                                              QUERY PLAN
 Delete on item_identifier  (cost=833491464.98..955347491.91 rows=0 width=0)
   ->  Merge Semi Join  (cost=833491464.98..955347491.91 rows=919853056 width=38)
         Merge Cond: (item_identifier.pk = t.pk)
         ->  Index Scan using item_identifier_pkey on item_identifier  (cost=0.58..101192612.10 rows=2759559168 width=14)
         ->  Sort  (cost=833476299.40..835775932.04 rows=919853056 width=40)
               Sort Key: t.pk
               ->  Subquery Scan on t  (cost=574787964.56..671372535.44 rows=919853056 width=40)
                     Filter: (t.rnum > 1)
                     ->  WindowAgg  (cost=574787964.56..636878045.84 rows=2759559168 width=54)
                           ->  Sort  (cost=574787964.56..581686862.48 rows=2759559168 width=46)
                                 Sort Key: item_identifier_1.prefix, item_identifier_1.suffix, item_identifier_1.pk
                                 ->  Seq Scan on item_identifier item_identifier_1  (cost=0.00..57175596.68 rows=2759559168 width=46)

The EXISTS method has a cost of 1,168,440,103 .. 1,233,224,771. The PARTITION method has a cost of 833,000,000 .. 955,000,000 (and uses the index, though not the one I thought would be uesful for the purpose!). They are close enough that I think PostgreSQL isn't making an error in its analysis of EXISTS.

And is this doing a one-off doble table-scan of approx O(n*2) or is it nesting them, resulting in something more like O(n^2)?

2 Answers 2


That index is unlikely to be useful, unless you have well over 100GB of RAM. Otherwise, hitting a random uncached index leaf page over 2.5 billion time will be a massive problem.

This deletion effort will be very frustrating as postgresql offers no way to introspect what if going on, and an interruption will cause all work so far to be lost. So I would start out by creating a table (AS SELECT) that stores all the pks to delete. Once that is done, that is at least one chunk of work that can be reused if the next step fails. I would also store the system column 'item_identifier.ctid' of the row as well as the pk. It is not safe to use a ctid collected in one statement to id rows in a later statement, but it should be safe enough to use it for ordering purposes.

Planning estimates for deletions and updates are particularly bad, as it doesn't take into account of random IO needed to fetch the row to delete it. The top merge join for example is going to return rows ordered by (prefix, suffix), which is likely to mean random ordering on ctid. So it will hop randomly all over the table to do the actual deletion, but the estimate does not account for that. Now it only has to do that for each row to delete, but still 1% of 2.7 billion is not a small number. If the order of the pk matches the physical ording of table rows, the second plan might be better in that regard.

How important this is of course depends on the relative speed of random versus sequential read of your underlying storage.

  • Thanks for those ideas. I will certainly try that intermediate step. A part of me wonders why it can't just walk the B-tree of (prefix, suffix, id). If fully vacuumed, there's surely no more info than that?
    – Joe
    Jul 4, 2022 at 17:17
  • You mean still do the merge join, but replace one of the sorts with an index scan? I think the reason for that is that DELETEs thinks it needs to see the ctid of the rows that are joined to ones about to be deleted, and PostgreSQL thinks index-only-scans can't return ctid. So it would need to be an index scan, not index-only, and that would be bad due to random IO. I don't know why it thinks IOS can't return ctid.
    – jjanes
    Jul 4, 2022 at 20:36
  • These details are stuff I still need to learn, so I can't say! But my intuitive understanding was that if I want to delete all-but-smallest PKs for unique (prefix, suffix) pairs, and there's an index of (prefix, suffix, pk) then the db should just need to walk the tree leaves of the first two index columns (to get unique pairs) and iterate over every pk in the third index, except the first. If I have an index on a vacuumed table, then the table contains no more information than the index. I know I'm wrong or naïve about something there.
    – Joe
    Jul 4, 2022 at 20:57
  • @jjanes: I think ctid from an index is inherently unreliable because we may have to follow a H.O.T. chain in the main relation to arrive at the live tuple. So I don't think we can get ever ctid from an index-only scan. Jul 4, 2022 at 22:35

The cost is dominated by sorting in both cases, which is O(n*log n), if memory serves. An index that might help is one on (prefix, suffix, id), and make sure you VACUUM the table before you start to get an index-only scan.

This is always going to be slow, and the best way to improve speed is probably lots of work_mem.

A different idea is to create a copy of the table with only the rows you need:

SELECT DISTINCT ON (prefix, suffix) *
FROM item_identifier
ORDER BY prefix DESC, suffix DESC, id DESC;

Then use that new table instead.

  • Thank you for the insight, it hadn't occurred to me to compare the sort and scan costs! I have work_mem at 8gb but can spare more. I did think about the copy, but given that the duplicates are rare I didn't think it was worth trying.
    – Joe
    Jul 4, 2022 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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