我想知道下面的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
如果运算符是>;、<;、>;=、<;=、!=、<;>;、介于或类似于 优化器使用它,但不考虑更多的关键部件.
我不认为MySQL正在进行"智能"的二进制搜索.
我说的对吗? 有什么配置可以让MySQL执行二进制搜索吗?