时间:2020-08-31来源:www.pcxitongcheng.com作者:电脑系统城
我们在做SQL查询的时候,经常会用到各各种关联查询,对于不同的联接,效率还是有差别的,具体该用哪种呢?虽说数据库会做一些查询的优化,但了解原理,能有助我们直指核心。
开始join吧。
我们分析三种常见的join: Merge join,Hash join 和 NestedLoop Join。在此之前,我们先介绍一些关键词:
Inner ralation 和 outer relation。
一个 relation 可以是:
当你在对两个 relation 进行 Join 的时候,join 算法对inner 和 outer relation 的方式是有区别的。outer relation 是左数据集, inner relation 是右数据集。
比如说 A JOIN B,此时 A 是 outer relation,B 是 inner relation。而且一般 A JOIN B 和 B JOIN A 用时是不一样的。
后面我们假设 outer relation 有 N 个元素, inner relation 有 M个元素。不过实际的优化器里,可以从统计信息中拿到确切的值。
Nested loop join
嵌套关联是最容易的一个。过程大概是:
遍历 outer relation 的每一行
然后去查找inner relation 的每一行是否匹配
写成伪代码是这样:
因为两重遍历,所以复杂度是 O(N*M)。对应到磁盘的I/O,在outer relation中,N 行中的每一行,都需要从inner relation 中循环读取M行数据。
所以这个算法需要从磁盘读 N + N*M行数据。但是,如果 inner relation 足够小,可以放到内存里的话,就只需要读 M + N 次了。虽然说在时间复杂度上没什么变化,但在磁盘I/O上这个方式还不错,因此, inner relation 可以被索引替代,磁盘I/O也更有利。
Hash join
哈希连接更复杂,不过很多时候也比循环嵌套连接成本要低
哈希连接的原理是:
在时间复杂度方面我们需要做点假设简化问题:
时间复杂度是 (M/X) * N + cost_to_create_hash_table(M) + cost_of_hash_function*N。如果哈希函数创建了足够小规模的哈希桶,那么复杂度就是 O(M+N)。
还有个哈希联接的版本,对内存更友好,但是对磁盘 I/O 不够有利。情况是这样的:
Merge join
合并联接是唯一产生排序的联接算法。
注:这个简化的合并联接不区分内表或外表;两个表扮演同样的角色。但实际实现方式是不同的,比如当处理重复值时。
(1) 排序
我们已经说过合并排序,在这里合并排序是个很好的算法。
有些时候数据集已经排序了,比如:
(2) 合并联接
这部分与我们说过的合并排序中的合并运算非常相似。区别只在于我们不从两个关系里挑选所有元素,只选相同的元素。
大致原理如下:
因为两个关系都是已排序的,你不再需要「回过头找」,所以这个方法很有效。
这个算法是个简化版本,它没有处理两组数据中相同数据出现多次的情况。
哪个连接算法最好?
如果有最好的,就没必要弄那么多种类型了。由于很多因素要考虑,所以不会有一个简单的答案,需要考虑的因素例如这些:
2023-03-19
Centos 7.9安装MySQL8.0.32的详细教程2023-03-19
一步步教你利用Mysql存储过程造百万级数据2023-03-19
利用Mysql定时+存储过程创建临时表统计数据的过程问题描述:MYSQL version 5.6.8command 表结构 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 CREATE TABLE command ( ID INT NOT NULL, NAME VARCHAR(16), D...
2023-03-19
一、Galera Cluster 二、基础环境搭建 三、加入配置参数启动集群 四、 测试 五、ProxySql...
2023-03-17