进一步研究this question我在《High Performance 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
最佳答案
首先，这个语句对于带有子查询的 in 来说是不正确的。为此，要么对数据中的每一行运行子查询(MySQL 5.6 之前的版本)，要么使用连接优化。
其次，在使用列表计算 in 的顺序时会发生两件事。您的两个陈述中隐含的是“对于正在处理的每一行”。因此，如果正在处理 R 行，则实际语句是 O(R * logN) 与 O(R*N) where N是列表的大小。
排序列表的创建在编译时发生，并且发生一次。因此，顺序语句为O((R * logN) + N * logN))。我相信假设是 R >> N，所以它主导了表达式。换句话说，因为排序发生一次并且针对每一行查看算法，所以编译工作就消失了。
关于mysql - 为什么 IN() 被视为 O(logN) 操作？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18173765/