PostgreSQL：NOT IN和EXCEPT性能差异（编辑＃2）

Question

我有两个功能相同的查询语句，其中一个运行效率非常高，另一个则非常低。我不知道这些性能差异的原因所在。

查询语句 #1：

SELECT id 
FROM subsource_position
WHERE
  id NOT IN (SELECT position_id FROM subsource)

这将返回以下计划：

                                  QUERY PLAN                                   
-------------------------------------------------------------------------------
 Seq Scan on subsource_position  (cost=0.00..362486535.10 rows=128524 width=4)
   Filter: (NOT (SubPlan 1))
   SubPlan 1
     ->  Materialize  (cost=0.00..2566.50 rows=101500 width=4)
           ->  Seq Scan on subsource  (cost=0.00..1662.00 rows=101500 width=4)

查询2：

SELECT id FROM subsource_position
EXCEPT
SELECT position_id FROM subsource;

计划：

                                           QUERY PLAN                                            
-------------------------------------------------------------------------------------------------
 SetOp Except  (cost=24760.35..25668.66 rows=95997 width=4)
   ->  Sort  (cost=24760.35..25214.50 rows=181663 width=4)
         Sort Key: "*SELECT* 1".id
         ->  Append  (cost=0.00..6406.26 rows=181663 width=4)
               ->  Subquery Scan on "*SELECT* 1"  (cost=0.00..4146.94 rows=95997 width=4)
                     ->  Seq Scan on subsource_position  (cost=0.00..3186.97 rows=95997 width=4)
               ->  Subquery Scan on "*SELECT* 2"  (cost=0.00..2259.32 rows=85666 width=4)
                     ->  Seq Scan on subsource  (cost=0.00..1402.66 rows=85666 width=4)
(8 rows)

我感觉我可能错过了其中一个查询的明显问题，或者我已经错误配置了PostgreSQL服务器。 我本来希望这个 NOT IN 查询能够很好地进行优化; 是否 NOT IN 总是存在性能问题，还是它在这里无法优化有原因呢？

其他数据：

=> select count(*) from subsource;
 count 
-------
 85158
(1 row)

=> select count(*) from subsource_position;
 count 
-------
 93261
(1 row)

编辑：我已经解决了下面提到的A-B != B-A问题。但是，我的问题仍然存在：查询＃1仍然比查询＃2要慢得多。我认为这是由于两个表具有相似数量的行。

编辑2：我正在使用PostgreSQL 9.0.4。我无法使用EXPLAIN ANALYZE，因为查询＃1需要太长时间。所有这些列都是NOT NULL的，因此不应该由此产生任何差异。

编辑3：我在这两列上都有索引。我还没有让查询＃1完成（在约10分钟后放弃）。查询＃2立即返回。

- Daniel Lyons

---

@mu太短了：这正是问题所在。不同的查询语义。你应该把它作为一个答案。 - gbn

NOT IN通常在性能方面不是一个好主意。这可能是PostgreSQL拥有（可能是专有的，因为我从未在其他RDBMS中听说过它）EXCEPT的原因。您没有说查询实际上是否需要不同的执行时间，或者只是估计成本（可能相当偏离）。那么索引呢？ - MarianP

@Marian FYI，MS SQL Server和IBM DB2都有EXCEPT，而Oracle则有MINUS。我猜其他数据库也有它们的等价物... - Branko Dimitrijevic

行估计是否合理？如果是，尝试在查询中增加work_mem，从默认的1mb可能增加到20或更高，只是为了测试。 - Magnus Hagander

如果您尝试使用 LEFT JOIN 版本会发生什么呢？类似这样的 select sp.id from subsource_position sp left join subsource s on sp.id = s.position_id where s.position_id is null。看起来像是它看到了 "没有 where 的选择"，直接转到了顺序扫描并将其材料化，因为中间结果集很大。如果在内部 SELECT 中添加 WHERE，您将看到它从 seq 扫描过渡到索引扫描，并且在不同点上进行了材料化。材料化看起来是您的敌人。 - mu is too short

Answer 1

查询#1不是做这件事的优雅方式......在选择中(NOT) IN对于一些条目来说还可以，但它无法使用索引(Seq Scan)。

如果没有EXCEPT，替代方法是使用JOIN(HASH JOIN):

    SELECT sp.id
    FROM subsource_position AS sp
        LEFT JOIN subsource AS s ON (s.position_id = sp.id)
    WHERE
        s.position_id IS NULL

EXCEPT 很久以前就出现在 Postgres 中... 但是我相信在使用 MySQL 时，这仍然是唯一的方法，使用索引来实现。

- Antony Gibbs

---

多么杰出的想法！ - Zoltán

Answer 2

您的查询在功能上并不相等，因此对它们的查询计划进行比较是没有意义的。

您的第一个查询可以用集合论的术语来表示：

{subsource.position_id} - {subsource_position.id}
          ^        ^                ^        ^

但是你的第二个问题是这样的：

{subsource_position.id} - {subsource.position_id}
          ^        ^                ^        ^

A - B并不等于任意集合A和B的B - A。

请更改查询以使其语义上等效，然后再试一次。

- mu is too short

---

我已经纠正了SQL和查询计划。如果您能再看一下，我会很感激。 - Daniel Lyons

哇，我不得不读那些大约5次才看到“.”和“_”字符位置的差异。 - Ross Bradbury

@RossBradbury，那个小修改让它更清楚了吗？ - mu is too short

Answer 3

由于您正在使用默认配置，尝试增加work_mem。很可能，子查询最终会因为您只允许使用1Mb的工作内存而被溢写到磁盘上。尝试使用10或20MB。

- Magnus Hagander

---

在我的测试中，2 MB 甚至可以解决这个问题。我可能会使用介于其中的某个值。感谢您的帮助！ - Daniel Lyons

性能差异与服务器配置无关。这两个查询具有不同的使用索引的能力（或限制）。#1 =>需要逐个扫描子源中的所有条目，而#2可以获取两个索引以“交叉匹配”（HASH JOIN）。但是，添加更多的“工作内存”用于“在RAM中扫描表”可以帮助运行非常糟糕的SQL而不使用连接... - Antony Gibbs

Answer 4

如果id和position_id都被索引（单独或作为多列索引的第一列），那么只需要两个索引扫描，就可以使用一个简单的基于排序合并的集合算法。个人认为PostgreSQL没有理解这一点的优化智能。

（我在诊断一个运行了超过24小时的查询后来到了这个问题，我可以在几秒钟内使用命令行上的sort x y y | uniq -u执行它。导出时数据库小于50MB）。

PS：更有趣的评论在这里：here：

已经投入了更多的工作来优化 EXCEPT 和 NOT EXISTS，因为后者由于其与 NULL 处理相关的不直观但规范强制性处理而显著不实用。 我们不会为此道歉，也不会将其视为错误。

归根结底，问题在于except与not in在空值处理方面不同。我还没有查看详细信息，但这意味着PostgreSQL（积极地）不对其进行优化。

- Barry Kelly

Answer 5

第二个查询利用了PostgreSQL的HASH JOIN特性。这比第一个查询的Seq Scan要快得多。

- Thomas Berger

---

这是否意味着“not in”不能使用索引？ - Jonathan Hartley