mysql - 为什么 IN() 被认为是 O(logN) 操作？

Question

进一步研究 this question我在 High Peformance MySQL(p.219) 一书中找到了以下内容:

... MySQL sorts the values in the IN list and uses a fast binary search to see whether a value is in the list.

它认为这种方法是最优的，在列表大小中测量为 O(logN) 并且它是一个非常好的方法(而不是例如转换为一系列 OR语句)。
但它似乎忽略了列表的排序是 O(NlogN) 所以结果比做一系列 OR 更糟糕 O(N) 。
我在这里误解了什么？
需要明确的是，这针对的是列表是来自另一个 SELECT

的巨大结果集的情况

Answer 1

首先，对于带有子查询的in，这个声明是不正确的。为此，要么为数据中的每一行运行子查询(MySQL 5.6 之前的版本)，要么使用连接优化。

其次，在使用列表计算 in 的顺序时，会发生两件事。在你的两个陈述中都隐含着“对于正在处理的每一行”。因此，如果正在处理 R 行，则实际语句是 O(R * logN) 与 O(R*N) 其中 N是列表的大小。

排序列表的创建发生在编译时，并且发生一次。所以，顺序语句是 O((R * logN) + N * logN))。我相信假设是 R >> N，所以它支配表达式。换句话说，因为排序只发生一次，算法会针对每一行进行查看，所以编译工作就省去了。