MySql SELECT 查找包含数字的区间的时间复杂度是多少？

Question

我想知道下面的 MySql SELECT 查询是否采用 O(N) 或 O(logN)。

让我们有一个表代表 4 个整数区间 [startNum, endNum]。 该表由 startNum 和 endNum 列索引。

startNum, endNum
3, 8
10, 15
16, 21
28, 42

查询：

SELECT * from table
where startNum <= 19 AND endNum >= 19

我认为 MySql 会采用 O(N)，因为它会

 1. find the first 3 rows using the "startNum"; then 
 2. go through each of them and use the "endNum" to identify the 3rd row; then 
 3. return the 3rd row [16, 21] as the result.

MySql 是否“聪明”到可以做到以下几点？

1. binary search on the startNum to find the position of the 3rd row, since "startNum" is sorted; then
2. binary search on the endNum to find the 3rd row again, since "endNum" is also sorted; then
3. return the 3rd row [16, 21] as the result.

来自本文档：https://dev.mysql.com/doc/refman/5.7/en/range-optimization.html

如果运算符是 >、<, >=、<=, !=, <>、BETWEEN 或 LIKE，则 优化器使用它但不再考虑关键部分。

我认为 MySql 没有进行“智能”二进制搜索。

我说得对吗？ 是否有任何配置可以使 MySql 进行二进制搜索？

Answer 1

你是对的。是 O(n)。如果您在 startNum 和 endNum 上都有索引，查询计划器将选择一个索引。根据表统计信息，它将尝试选择更具选择性的索引。

然后它将随机访问该索引到第一个符合条件的行，并继续扫描表的其余部分以满足其他不平等谓词。这是 BTREE 索引的本质。每个使用 BTREE 索引的表服务器的情况都是一样的，而不仅仅是 MySql / Mariadb。

如果你的索引是复合索引，像这样

ALTER TABLE `table`
  ADD INDEX start_end (startNum, endNum),
  ADD INDEX end_start (endNum, startNum);

查询规划器可能会选择扫描索引而不是整个表。这通常更快，但仍然是 O(n)。

请记住，除非您确定需要表中的每一列，否则在性能关键查询中使用

SELECT *

是一种反模式。

Answer 2

可以将查询转化为 O(1)。但它要求开始结束范围不重叠。而且，如果您愿意为间隙增加额外的行，您可以（并且应该）摆脱其中一列。

查询将变为

SELECT *
    FROM table
    WHERE startnum >= 19
    ORDER BY startnum
    LIMIT 1;

如果您可能一无所获，那么可以通过以下方式之一解决：

• 如果保留

  endnum

  ，那么验证返回的

  endnum

  是

  < 19

  .

• 在LIMIT之后

  检查

  （如果没有像这样的混乱语法，之前无法完成）：

    SELECT *
        FROM ( the above query ) AS x
        WHERE endnum <= 19;
  

• 消除列

  endnum

  。在这种情况下，您得到的是有效行还是“间隙”行应该很明显。 （假设您保留

  startnum

  ；可以编写一个类似的查询，您更愿意只保留

  endnum

  。）请注意，所有可能的 startnum 值都在 some 行中表示为 >= 当前 startnum 和 < the next startnum.

我在我的博客中讨论了如何处理 IP 地址范围：http://mysql.rjweb.org/doc.php/ipranges