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

iklwldmw 于 2023-02-28 发布在 Mysql

关注(0)|答案(2)|浏览(144)

我想知道下面的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做二进制搜索？

mysql

来源：https://stackoverflow.com/questions/75538639/what-is-the-time-complexity-of-mysql-select-to-find-an-interval-that-contains-a

2条答案

按热度按时间

jhdbpxl91#

这是O（n），如果你在startNum和endNum上都有索引，那么查询计划器会选择一个索引，然后根据表的统计信息，选择一个更具选择性的索引。
然后它将随机访问该索引到第一个符合条件的行，并继续扫描表的其余部分以满足另一个不等式 predicate 。这是BTREE索引的本质。这种情况在使用BTREE索引的每个表服务器中都是相同的，而不仅仅是MySql / Mariadb。
如果索引是复合索引，如下所示

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

查询计划器可能会选择扫描索引而不是整个表，这通常更快，但仍然是O（n）。
请记住，在性能关键型查询中使用SELECT *是一种反模式，除非您确定需要表中的每一列。

赞(0）回复(0）举报 2023-02-28

swvgeqrz2#

将查询转换为O（1）是可能的，但是它要求开始和结束的范围不重叠，并且，如果您愿意为间隙增加额外的行，您可以（并且应该）删除其中的一列。
查询将变为

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

如果你可能什么也得不到，那么这是解决这些方式之一：

如果保留endnum，则验证返回的endnum是否为< 19。
检查LIMIT的 after（如果没有像这样混乱的语法，就无法在之前完成）：

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

删除列endnum。在这种情况下，您得到的是有效行还是“间隙”行应该是显而易见的。（这里假设您保留startnum;类似的查询可以写成：you prefer to keep only endnum。）注意，所有可能的startnum值都在 some 行中表示为〉=当前startnum和

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

赞(0）回复(0）举报 2023-02-28

我来回答

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

2条答案

相关问题

热门标签

最新问答