广东网站营销seo方案,网页制作平台有什么,查网站备案名称,做一公司网站目录
嵌套循环算法#xff08;NLJ#xff09;
简单嵌套循环#xff08;SNLJ#xff09;
索引嵌套循环#xff08;INLJ#xff09;
块嵌套循环#xff08;BNLJ#xff09;
三种算法比较
哈希连接算法#xff08;Hash Join#xff09;
注意事项#xff1a;
工…目录
嵌套循环算法NLJ
简单嵌套循环SNLJ
索引嵌套循环INLJ
块嵌套循环BNLJ
三种算法比较
哈希连接算法Hash Join
注意事项
工作原理
优点
缺点
排序合并链接SORT MERGE JOIN
工作流程
优点
缺点
总结 我们都知道SQL的join关联表的使用方式但是这次聊的是实现join的算法join有三种算法分别是Nested Loop JoinHash joinSort Merge Join。
嵌套循环算法NLJ
嵌套循环算法Nested-Loop JoinNLJ是通过两层循环用第一张表做Outter Loop第二张表做Inner LoopOutter Loop的每一条记录跟Inner Loop的记录作比较符合条件的就输出。而NLJ又有3种细分的算法嵌套循环算法又可以分为简单嵌套循环、索引嵌套循环、块嵌套循环。
简单嵌套循环SNLJ // 伪代码for (r in R) {for (s in S) {if (r satisfy condition s) {output r, s;}}} SNLJ就是两层循环全量扫描连接的两张表得到符合条件的两条记录则输出这也就是让两张表做笛卡尔积比较次数是R * S是比较暴力的算法会比较耗时。
索引嵌套循环INLJ // 伪代码for (r in R) {for (si in SIndex) {if (r satisfy condition si) {output r, s;}}} INLJ是在SNLJ的基础上做了优化通过连接条件确定可用的索引在Inner Loop中扫描索引而不去扫描数据本身从而提高Inner Loop的效率。 而INLJ也有缺点就是如果扫描的索引是非聚簇索引并且需要访问非索引的数据会产生一个回表读取数据的操作这就多了一次随机的I/O操作。
块嵌套循环BNLJ // 伪代码for (r in R) {for (sbu in SBuffer) {if (r satisfy condition sbu) {output r, s;}}} 扫描一个表的过程其实是先把这个表从磁盘上加载到内存中然后在内存中比较匹配条件是否满足。但内存里可能并不能完全存放的下表中所有的记录。为了减少访问被驱动表的次数我们可以首先将驱动表的数据批量加载到 Join Buffer连接缓冲然后当加载被驱动表的记录到内存时就可以一次性和多条驱动表中的记录做匹配这样可大大减少被驱动表的扫描次数这就是 BNLJ 算法的思想。
三种算法比较
算法比较(外表大小R内表大小S) \algorithm comparison\Simple Nested Loop JoinBlock Nested Loop Join外表扫描次数111内表扫描次数R0读取记录次数 R R * S R RS_Matches 比较次数 R * SR * IndexHeight R * S回表次数0 RS_Matches0
整体效率比较INLJ BNLJ SNLJ
哈希连接算法Hash Join
MySQL 8.0.18支持在optimizer_switch中设置hash_join标志以及优化器提示HASH_JOIN和NO_HASH_JOIN。在MySQL 8.0.19和更高版本中这些都不再有任何效果。
从MySQL 8.0.20开始对块嵌套循环的支持被删除并且服务器在以前使用块嵌套循环的地方使用哈希连接。 hash join的实现分为build table也就是被用来建立hash map的小表和probe table首先依次读取小表的数据对于每一行数据根据连接条件生成一个hash map中的一个元組数据缓存在内存中如果内存放不下需要dump到外存。依次扫描探测表拿到每一行数据根据join condition生成hash key映射hash map中对应的元組元組对应的行和探测表的这一行有着同样的hash key, 这时并不能确定这两行就是满足条件的数据需要再次过一遍join condition和filter满足条件的数据集返回需要的投影列。 // 伪代码
// 算法复杂度O(M N)
// 假设用户表有M条记录 订单表有N条记录
func HashJoin(users []TradeUser, orders []TradeOrder) []*UserOrderView {var userOrderViews []*UserOrderView make([]*UserOrderView, 0)// 将用户表以用户ID为Key用户为Value转换为Hash表// 算法复杂度O(M)userTable : make(map[int]TradeUser)for _, user : range users {userTable[user.Id] user}// 遍历订单表查找用户// 算法复杂度O(N)for _, order : range orders {// 复杂度接近:O(1)if user, exists : userTable[order.UserId]; exists {// 添加视图结果userOrderViews append(userOrderViews, UserOrderView{UserId: user.Id,UserName: user.Name,OrderId: order.Id,OrderAmount: order.Amount,})}}return userOrderViews
} 注意事项
hash join本身的实现不要去判断哪个是小表优化器生成执行计划时就已经确定了表的连接顺序以左表为小表建立hash table,那对应的代价模型就会以左表作为小表来得出代价这样根据代价生成的路径就是符合实现要求的。hash table的大小、需要分配多少个桶这个是需要在一开始就做好的那分配多少是一个问题分配太大会造成内存浪费分配太小会导致桶数过小开链过长性能变差一旦超过这里的内存限制会考虑dump到外存不同数据库有它们自身的实现方式。如何对数据hash,不同数据库有着自己的方式不同的哈希方法也会对性能造成一定的影响。
工作原理
构建阶段Build Phase
选择构建表Build Table算法通常会选择数据量较小的表作为构建表以减少哈希表的构建时间和所需内存。但这不是绝对的实际选择会根据统计信息和成本估算来决定。创建哈希表对构建表中的每一行记录取其连接列即用于JOIN的列的值应用哈希函数计算出一个哈希码hash code。然后根据这个哈希码将记录存储在一个哈希桶hash bucket中。如果有多个记录的连接列值经过哈希后得到相同的哈希码这些记录会被组织成链表或其他数据结构存储在同一哈希桶内。
探测阶段Probe Phase
扫描探测表Probe Table对另一个较大的表探测表进行扫描。哈希计算与匹配对于探测表中的每一行同样对其连接列值应用相同的哈希函数计算哈希码然后在这个预先构建好的哈希表中查找对应的哈希桶。匹配与输出如果找到匹配的哈希桶就进一步检查桶内的链表或数据结构进行精确的等值比较以确保连接列的值确实相等。一旦找到匹配项就结合两个表的相关字段生成结果集的行并输出。
优点
性能优势在数据量大时哈希连接可以显著减少磁盘I/O和CPU时间因为它避免了嵌套循环的多次扫描和排序-合并连接中的排序开销。并行处理友好哈希连接天然适合并行化处理因为哈希表可以在不同的处理器或节点上并行构建和查询。内存依赖哈希连接的效率高度依赖于可用内存因为需要在内存中存储整个哈希表。如果内存不足部分或全部哈希表可能需要溢写到磁盘这会大大降低效率。
缺点
内存消耗如前所述构建哈希表需要足够的内存空间特别是当构建表较大时。非等值连接不适用哈希连接主要用于等值连接对于非等值连接如大于、小于等条件不适用。预读取与优化为了效率数据库系统需要有效管理内存使用并可能实施预读取策略来优化性能。
排序合并链接SORT MERGE JOIN
排序合并连接是嵌套循环连接的变种。如果两个数据集还没有排序那么数据库会先对它们进行排序这就是所谓的sort join操作。对于数据集里的每一行数据库会从上一次匹配到数据的位置开始探查第二个数据集这一步就是Merge join操作。 // 伪代码
// 算法复杂度O(M log M N log N)
// 假设用户表有M条记录 订单表有N条记录
func SortJoin(users []TradeUser, orders []TradeOrder) []*UserOrderView {var userOrderViews []*UserOrderView make([]*UserOrderView, 0)// 排序user表// 算法复杂度O(M log M)sort.Slice(users, func(i, j int) bool {return users[i].Id users[j].Id})// 排序order表// 算法复杂度O(N log N)sort.Slice(orders, func(i, j int) bool {return orders[i].Id orders[j].Id})// 遍历订单表查找用户// 算法复杂度O(M)userIdx : 0for _, order : range orders {// 在user.id为主键的情况下这里还可以执行二分查找for idx len(users) users[userIdx].Id order.UserId {userIdx}// 如果找到用户添加到结果集合if userIdx len(users) users[userIdx].id order.UserId {// Join条件满足添加视图结果userOrderViews append(userOrderViews, UserOrderView{UserId: user.Id,UserName: user.Name,OrderId: order.Id,OrderAmount: order.Amount,})}}return userOrderViews
} 工作流程 排序阶段 数据排序首先算法会对参与连接的两个表根据连接键进行排序。这一步骤是关键因为只有排序后的数据才能有效地进行归并操作。如果表已经按照连接键排序这一步可以省略。索引利用如果表上有适合的索引如聚集索引或覆盖索引数据库引擎可能会直接利用这些索引来避免全表排序。 合并阶段 双指针扫描一旦两个表的数据都按连接键排序好了算法会使用两个指针或游标分别指向两个表的开始。每个指针逐步向后移动比较两个指针所指记录的连接键值。匹配与输出当两个指针指向的记录的连接键相等时说明这两个记录应该被连接起来此时就会输出或累积到结果集中这对匹配的记录。如果一个表的指针达到末尾而另一个表还有剩余记录则剩余的记录被视为不匹配如果有外连接的情况则可能作为NULL扩展输出。推进指针匹配后指针会根据排序顺序向后移动继续寻找下一个匹配的记录。
优点
效率对于大表连接特别是当连接键分布均匀且数据已经排序或可以低成本排序时SMJ比Nested-Loop Join更高效因为它减少了不必要的比较次数。稳定性由于是基于排序的Sort Merge Join保证了输出结果的稳定性即具有相同键值的记录保持原有的相对顺序。可预测性能时间复杂度主要取决于排序操作通常是O(n log n)对于大规模数据集来说性能较为可预测。
缺点
内存和I/O开销排序操作可能需要额外的内存空间并且如果数据不能完全放入内存还需要磁盘I/O操作这可能会成为性能瓶颈。预处理时间排序是预处理步骤可能增加整体处理时间尤其是在数据已经接近有序或只需要执行一次连接操作的情况下。
总结
算法名称时间复杂度描述Nested Loop JoinOM*N适合小数据集大数据集很慢Sort Merge JoinOM log M N log N M N适合于当内存不足以存放整个数据集需要小的分区上进行排序和合并Hash JoinOMN适用于大数据集
