这是 DELETE ... WHERE EXISTS 查询计划 O(n*2) 还是 O(n^2) ？

Question

我正在尝试执行一项常见任务，从表中删除重复项，目的是添加唯一约束。

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);

我想使用常见查询删除重复项，该查询可以在本网站的许多答案中找到。我认为重复率大约为 1%，因此没有太多需要删除的内容。

提供索引纯粹是为了帮助重复数据删除，稍后将被删除。不过，如您所见，PostgreSQL 甚至没有使用它！

有 2,759,559,168 行。索引temp_prefix_suffix_idx本身约为 100 GB。花CREATE INDEX了 12 个小时所以我不指望DELETE会很快。但根据 10% 的样本集，我推断需要 20 小时，而实际上已经花了 40 小时。对于我的示例方法来说，它可能仍在误差范围内，但我担心由于它不使用索引，这将花费指数时间。

这EXPLAIN有Seq Scan on item_identifier a和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)

我可以假设 PostgreSQL 不使用索引做出了正确的选择吗？

作为另一个参考点，另一种常见建议的方法给出了类似的结果：

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)

该EXISTS方法的成本为 1,168,440,103 .. 1,233,224,771。该PARTITION方法的成本为 833,000,000 .. 955,000,000（并使用索引，尽管我认为这不是对此目的有用的索引！）。它们足够接近，我认为 PostgreSQL 在分析EXISTS.

这是进行大约 O(n*2) 的一次性双表扫描，还是嵌套它们，导致更像 O(n^2) 的结果？

Answer 1

在这两种情况下，成本主要由排序决定，如果内存允许的话，成本是 O(n*log n)。可能有帮助的索引是 on 上的一个，并在开始进行仅索引扫描之前(prefix, suffix, id)确保该表。VACUUM

这总是会很慢，提高速度的最佳方法可能是大量work_mem.

另一个想法是创建仅包含您需要的行的表副本：

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

然后改用那个新表。