数据库：Join算法

Join操作是一种常见的数据库操作，通过Join可以将多个表关联起来，根据用户的条件共同提供数据。一般情况，在数据库中都会内置多种Join算法，优化器在优化的时候会根据SQL语句和表的统计信息选择合适的算法。

Hash Join

在执行Hash Join时，1. 会根据Join条件将一张表进行Hash运算加载到内存中的一张Hash表中。Hash表类似与Java中的HashTable；2.遍历另外一张表，进行Hash运算后在内存中查找满足条件的记录。

select * from t1 join t2 on t1.a = t2.b；在执行这个SQL的时候，先加载表t1的数据，然后根据表t1的a字段作为key构造Hash表。之后，从表t2中逐条取出记录，计算字段b的Hash值，去Hash表中查找是否存在满足条件的记录。

Hash Join的性能很高，但是前提条件是内存中能够存放下其中一张表的Hash表。所以一般适用于大小表Join。在一些大数据分析的数据查询引擎中，当内存放不下这种Hash表的时候，会将小表进行分区保存到磁盘上，之后再执行Join。

嵌套循环Join

嵌套循环Join中，至少一张表存在索引，且Join的条件是对索引列的比对。带有索引的表作为被检索表，对不带有索引或者两张都带有索引的表中较小的那张表进行遍历。这个算法充分利用了索引的优势，让Join的时间复杂度从O(m*n)变成了O(n)，其中m为被检索表的行数，n为遍历表的行数。

Merge Hash

相对于上述两个算法，这个算法的性能差些，但是使用范围更广些。在这个算法中，相对两张表中的数据进行排序，之后再分别取一段进行Join。

Semi Join

半连接，对于左边的表输出满足条件的记录，而对于右边的表则不管是否满足条件都不会被输出，也就是，最终的结果是左边表数据记录的一个子集，类似于in、exists。Semi Join本身就是Join的一种。在大数据跨数据源的查询中，Semi Join是对inner join、left join、right join的一种优化。查询跨数据源时，尽量减少从每个数据源出来的数据量是一种很有效的优化方式，毕竟网络传输是要花费时间的。将Join转化成Semi Join是一种有效减小数据量的方式。

对于：select * from t1 join t2 where t1.a = t2.b，Semi Join的过程如下：

1.将表t1的数据加载到内存；

2.根据t1的数据，改写加载表t2的条件，即将SQL语句改写成in、exists等。假设表t1中，全部记录的a字段只有两个值：aa和bb，那么SQL将被改写为select * from t2 in ('aa','bb');

3.对从表t1和t2加载的数据做Join；

第2步中对加载t2数据的SQL的改写，使原本需要加载整个t2表改为仅加载t2中满足条件的数据。

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

关注下方微信公众号：java圈子，获取价值999元全套java入门到进阶的学习资料以及教程，还有java技术交流群一起交流学习哦。

发表于 2021-11-06 09:23
阅读 ( 420 )
分类：Java开发

数据库：Join算法

你可能感兴趣的文章

相关问题

0 条评论

作家榜 »