這是 DELETE … WHERE EXISTS 查詢計劃 O(n*2) 還是 O(n^2)？
我正在嘗試執行一項常見任務，從表中刪除重複項，以添加唯一約束。
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) 的東西？
除非您有超過 100GB 的 RAM，否則該索引不太可能有用。否則，超過 25 億次隨機訪問未記憶體的索引葉頁面將是一個巨大的問題。
這種刪除工作將非常令人沮喪，因為 postgresql 無法自省如果繼續進行，並且中斷將導致迄今為止的所有工作失去。因此，我將從創建一個儲存所有要刪除的 pk 的表 (AS SELECT) 開始。一旦完成，如果下一步失敗，至少有一部分工作可以重用。我還將儲存該行的系統列“item_identifier.ctid”以及 pk。使用在一個語句中收集的 ctid 來在後面的語句中標識行是不安全的，但將其用於排序目的應該足夠安全。
刪除和更新的計劃估計特別糟糕，因為它沒有考慮獲取行以刪除它所需的隨機 IO。例如，頂部合併連接將返回按（前綴，後綴）排序的行，這可能意味著 ctid 上的隨機排序。所以它會在整個表中隨機跳躍以進行實際刪除，但估計沒有考慮到這一點。現在它只需要為每一行刪除，但 27 億中的 1% 仍然不是一個小數字。如果 pk 的順序與表行的物理順序相匹配，那麼第二個計劃在這方面可能會更好。
當然，這有多重要取決於底層儲存的隨機讀取與順序讀取的相對速度。
如果有記憶的話，這兩種情況下的成本都是由排序決定的，即 O(n*log n)。可能有幫助的索引是 one on ，並在開始進行僅索引掃描之前
(prefix, suffix, id)確保您的表。VACUUM這總是會很慢，提高速度的最好方法可能是很多
work_mem.一個不同的想法是創建一個表的副本，其中只包含您需要的行：
SELECT DISTINCT ON (prefix, suffix) * FROM item_identifier ORDER BY prefix DESC, suffix DESC, id DESC;然後改用那個新表。