SQL查询复杂性对性能有什么一般规律吗？

Question

1)如果不使用索引,SQL查询执行时间O(n)是否与连接数相比较？如果没有,我们可能会期待什么样的关系？并且索引可以改善实际的大O时间复杂度,还是仅仅通过一些常数因子减少整个查询时间？

稍微含糊的问题,我确信它变化很大,但我在这里谈论的是一般意义.

2)如果您有如下查询:

SELECT  T1.name, T2.date
FROM    T1, T2
WHERE   T1.id=T2.id
        AND T1.color='red'
        AND T2.type='CAR'

我是否正确地假设DB在评估多表条件之前首先在T1.color和T2.type上进行单表过滤？在这种情况下,使查询更复杂可以使它更快,因为更少的行受到连接级别测试？

Answer 1

这取决于使用的查询计划.

即使没有索引,现代服务器也可以使用HASH JOIN,MERGE JOIN而且速度更快O(N * M)

更具体地说,a的复杂性HASH JOIN是O(N + M),N散列表和M查找表在哪里.散列和散列查找具有不变的复杂性.

a的复杂性MERGE JOIN是O(N*Log(N) + M*Log(M)):它是对两个表进行排序以及扫描它们的时间的总和.

SELECT  T1.name, T2.date
FROM    T1, T2
WHERE   T1.id=T2.id
        AND T1.color='red'
        AND T2.type='CAR'

如果没有定义索引,引擎将选择a HASH JOIN或a MERGE JOIN.

该HASH JOIN如下工作:

1. 选择散列表(通常是具有较少记录的表).说出来t1

2. t1扫描所有记录.如果记录成立color='red',则此记录将id作为键和name值进入哈希表.

3. t2扫描所有记录.如果记录成立type='CAR',id则在哈希表中搜索它,并name返回所有哈希命中的值以及当前值data.

该MERGE JOIN如下工作:

1. t1 (id, name)创建副本,排序id

2. t2 (id, data)创建副本,排序id

3. 指针在两个表中都设置为最小值:

   >1  2<
    2  3
    2  4
    3  5
   

4. 指针在循环中进行比较,如果匹配,则返回记录.如果它们不匹配,则具有最小值的指针会提前:

   >1  2<  - no match, left pointer is less. Advance left pointer
    2  3
    2  4
    3  5
   
    1  2<  - match, return records and advance both pointers
   >2  3
    2  4
    3  5
   
    1  2  - match, return records and advance both pointers
    2  3< 
    2  4
   >3  5
   
    1  2 - the left pointer is out of range, the query is over.
    2  3
    2  4<
    3  5
   >
   

在这种情况下,使查询更复杂可以使它更快,因为更少的行受到连接级别测试？

当然.

您的查询没有WHERE条款:

SELECT  T1.name, T2.date
FROM    T1, T2

更简单但返回更多结果并运行更长时间.

Answer 2

小心混淆太多不同的东西.根据要检查的行数,您具有查询的逻辑成本,基于实际返回的行数(可能)较小的逻辑成本以及基于必须检查的页数的不相关的物理成本.

这三者是相关的,但并不强烈.

检查的行数是这些成本中最大的,并且最不容易控制.必须通过连接算法匹配行.这也是最不相关的.

返回的行数更加昂贵,因为它是客户端应用程序和数据库之间的I/O带宽.

读取的页数是最昂贵的,因为这是更多的物理I/O. 这是最昂贵的,因为数据库中的负载会影响所有客户端.

一个表的SQL查询是O(n).那是行数.它也是基于页数的O(p).

对于多个表,检查的行是O(n m ...).这是嵌套循环算法.但是,根据关系的基数,结果集可能与O(n)一样小,因为关系都是1:1.但必须检查每个表的匹配行.

散列连接用O(n)直接散列查找替换O(n*log(n))索引+表读取.您仍然必须处理O(n)行,但是您绕过了一些索引读取.

合并连接替换ø(正嵌套米)环Ô(日志(N + M)(N + M))的排序操作.

对于索引,如果仅检查表是否存在,则物理成本可以减少到O(log(n)m).如果需要行,则索引会加快对行的访问,但必须处理所有匹配的行. O(n m)因为这是结果集的大小,与索引无关.

根据索引的选择性,检查此工作的页面可能更小.

索引的要点不是减少检查的行数.这是为了减少获取行的物理I/O成本.