mysql - 优化 : WHERE x IN (1, 2 .., 100.000) 与 INNER JOIN tmp_table USING(x)？

Question

我最近参加了一次有趣的工作面试。在那里我被问到一个关于使用包含长标量列表(即数千个值)的 WHERE..IN 子句优化查询的问题。这个问题不是关于 IN 子句中的子查询，而是关于简单的标量列表。

我马上回答说，这可以使用 INNER JOIN 与另一个表(可能是临时表)进行优化，该表将仅包含那些标量。我的回答被接受了，并且有评论者的注释，“目前没有数据库引擎可以优化长 WHERE..IN 条件以获得足够的性能”。我点了头。

但是当我走出去的时候，我开始有些疑惑了。该条件似乎相当微不足道，并且广泛用于现代 RDBMS 无法对其进行优化。因此，我开始进行一些挖掘。

PostgreSQL:

看来，PostgreSQL parse scalar IN() constructions into ScalarArrayOpExpr structure ，即 sorted .此结构稍后在索引扫描期间用于定位匹配行。此类查询的 EXPLAIN ANALYZE 仅显示一个循环。没有连接完成。所以，我希望这样的查询比 INNER JOIN 更快。我在我现有的数据库上尝试了一些查询，我的测试证明了这一点。但我不关心测试的纯度，而且 Postgres 在 Vagrant 之下，所以我可能是错的。

MSSQL 服务器:

MSSQL 服务器 builds a hash structure from the list of constant expressions and then does a hash join with the source table .尽管似乎没有进行排序，但我认为这是一场性能比赛。我没有做任何测试，因为我没有任何使用此 RDBMS 的经验。

MySQL 服务器:

The 13th of these slides说，在 5.0 之前，这个问题确实在某些情况下发生在 MySQL 中。但除此之外，我没有发现任何其他与错误的 IN () 处理相关的问题。不幸的是，我没有找到任何逆向证明。如果你这样做了，请踢我。

SQLite:

Documentation page暗示了一些问题，但我倾向于相信那里描述的事情确实处于概念层面。没有找到其他信息。

所以，我开始认为我误解了我的面试官或误用了谷歌 ;) 或者，可能是因为我们没有设置任何条件，我们的谈话变得有点含糊(我们没有指定任何具体的 RDBMS或其他条件。那只是抽象的谈话)。

看起来像那些日子，数据库将 IN() 重写为一组 OR 语句(这有时会导致 NULL 出现问题列表中的值，顺便说一句)是很久以前的事了。还是不行？

当然，在标量列表比允许的数据库协议(protocol)数据包长的情况下，INNER JOIN 可能是唯一可用的解决方案。

我认为在某些情况下，查询解析时间(如果没有准备好)本身就会降低性能。

此外，数据库可能无法准备 IN(?) 查询，这将导致一次又一次地重新解析它(这可能会降低性能)。实际上，我从未尝试过，但我认为即使在这种情况下，查询解析和规划与查询执行相比也不是很大。

但除此之外我没有看到其他问题。好吧，除了遇到这个问题之外。如果您有包含数千个 ID 的查询，则说明您的架构有问题。

你呢？

Answer 1

只有在列表上建立索引(最好是主键索引)时，你的答案才是正确的，除非列表真的很小。

任何关于优化的描述都是特定于数据库的。然而，MySQL非常具体地说明了它如何优化 in:

Returns 1 if expr is equal to any of the values in the IN list, else returns 0. If all values are constants, they are evaluated according to the type of expr and sorted. The search for the item then is done using a binary search. This means IN is very quick if the IN value list consists entirely of constants.

在这种情况下，使用 IN 肯定会比使用另一个表更快 -- 并且可能比使用主键索引的另一个表更快。

我认为 SQL Server 将 IN 替换为 OR 的列表。然后这些将作为顺序比较来实现。请注意，如果某些元素比其他元素更常见并且出现在列表的最前面，则顺序比较可能比二进制搜索更快。