Is this DELETE ... WHERE EXISTS query plan O(n*2) or O(n^2)?

Question

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 (
    pk       BIGSERIAL PRIMARY KEY,
    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
  WHERE EXISTS
    (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
WHERE pk IN (SELECT pk FROM (
        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)?

Answer 1

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.

Answer 2

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.