百度360必应搜狗淘宝本站头条
当前位置:网站首页 > IT技术 > 正文

「分布式技术专题」数据库常见的JOIN算法

wptr33 2025-03-08 01:03 26 浏览

mysql支持的join算法

  • Nested Loop Join
  • Index Nested-Loop Join
  • Block Nested-Loop Join

Index Nested-Loop Join 和 Block Nested-Loop Join是在Nested-Loop Join基础上做了优化。

Nested Loop Join

Nested-Loop Join的思想就是通过双层循环比较数据来获得结果; 其中左表为外循环,右表为内循环,左表为驱动表。其实现逻辑简单粗暴,可以理解为两层for循环,小表在外环,大表在内环,数据比较的次数 = 小表记录数 * 大表记录数。

//select * from t1 inner join t2 on t1.a= t2.a;

List<结果> lists = new ArrayList<>();
for(t2 t2 : t2){  //外层循环
    for(t1 t1 : t1){  //内循环
        if(t2.a().equals(t1.a())){  //条件匹配
            //存放结果到结果集
            结果 = t1的字段 + t2的字段
            lists.add(结果集);
        }
    }
}

索引嵌套循环连接 Index Nested-Loop Join

优化思路:内表为大表,可在join字段上建立索引,减少内表数据的扫描次数。

执行流程
0.前置条件:外表 t2 已在连接用的 a 字段以建立索引;
1.从外表 t1 中读取一行数据 R;
2.使用 R 中的a 字段和内表 t2 的 a 字段进行索引关联查找;
3.根据索引到的记录取出表 t2 中满足条件的行,跟 R 组成一行,作为结果集的一部分;
4.重复执行步骤 1 到 3,直到表 t1 循环结束。

可见,通过索引的建立,避免了对大表进行全表扫描,加快了查询速度。

缓存块嵌套循环连接 Block Nested-Loop Join

优化思路:通过一次性缓存多条数据,减少外层表的循环次数。

t1为小表时的执行流程
1.把t1 表查询的字段数据整个读入线程内存 join_buffer 中;
2.扫描表 t2,把表 t2 中的每一行取出来,跟 join_buffer 中的 数据做对比,满足 join 条件的,作为结果集的一部分返回。

t1为大表时的执行流程: 1.扫描表 t1,顺序读取一定长度的数据行放入 join_buffer 中;
2.扫描表 t2,把 t2 中的每一行取出来,跟 join_buffer 中的数据做对比,满足 join 条件的,作为结果集的一部分返回;
3.清空 join_buffer;
4.顺序读取 t1表下一批次数据放入 join_buffer 中,重复步骤2

Oracle的join算法

  • Nested Loop Join,嵌套循环
  • Hash Join,将两个表中较小的一个在内存中构造一个 Hash 表(对JoinKey),扫描另一个表
  • Sort Merge Join,将两个表排序,然后再进行join

DB2和SQL Server也使用这三种方式join算法。

Hash Join

Hash Join的使用场景

  • 适合于小表与大表连接、返回大型结果集的连接
  • 只能用于等值连接,且只能在CBO优化器模式下

在inner/left/right join,以及union/group by等 都会使用hash join进行操作。

实现原理:


Hash Join中的小表称之为hash表,大表称为探查表,以小表作为驱动表。

  • 两个输入:

– build input(也叫做outer input),小表

– probe input(也叫做inner input),大表

  • 两个阶段:

– Build(构造)阶段,处理build input

– Probe(探测)阶段,探测probe input

build 阶段,主要是构造哈希表(hash table):

  • 在inner/left/right join等操作中,表关联字段作为hash key
  • 在group by操作中,group by的字段作为hash key;
  • 在union或其它去重操作中,hash key包括所有的select字段。

一个hash值对应到hash table中的hash buckets。多个hash buckets可以使用链表数据结构连接起来。

Probe 阶段,从probe input中取出每一行记录,根据key值生成hash值,从build阶段构造的hash table中搜索对应的hash bucket。

  • Grace Hash join


以上为数据库常见的JOIN算法,「分布式技术专题」是国产数据库hubble团队精心整编,专题会持续更新,欢迎大家保持关注。

相关推荐

redis的八种使用场景

前言:redis是我们工作开发中,经常要打交道的,下面对redis的使用场景做总结介绍也是对redis举报的功能做梳理。缓存Redis最常见的用途是作为缓存,用于加速应用程序的响应速度。...

基于Redis的3种分布式ID生成策略

在分布式系统设计中,全局唯一ID是一个基础而关键的组件。随着业务规模扩大和系统架构向微服务演进,传统的单机自增ID已无法满足需求。高并发、高可用的分布式ID生成方案成为构建可靠分布式系统的必要条件。R...

基于OpenWrt系统路由器的模式切换与网页设计

摘要:目前商用WiFi路由器已应用到多个领域,商家通过给用户提供一个稳定免费WiFi热点达到吸引客户、提升服务的目标。传统路由器自带的Luci界面提供了工厂模式的Web界面,用户可通过该界面配置路...

这篇文章教你看明白 nginx-ingress 控制器

主机nginx一般nginx做主机反向代理(网关)有以下配置...

如何用redis实现注册中心

一句话总结使用Redis实现注册中心:服务注册...

爱可可老师24小时热门分享(2020.5.10)

No1.看自己以前写的代码是种什么体验?No2.DooM-chip!国外网友SylvainLefebvre自制的无CPU、无操作码、无指令计数器...No3.我认为CS学位可以更好,如...

Apportable:拯救程序员,IOS一秒变安卓

摘要:还在为了跨平台使用cocos2d-x吗,拯救objc程序员的奇葩来了,ApportableSDK:FreeAndroidsupportforcocos2d-iPhone。App...

JAVA实现超买超卖方案汇总,那个最适合你,一篇文章彻底讲透

以下是几种Java实现超买超卖问题的核心解决方案及代码示例,针对高并发场景下的库存扣减问题:方案一:Redis原子操作+Lua脚本(推荐)//使用Redis+Lua保证原子性publicbo...

3月26日更新 快速施法自动施法可独立设置

2016年3月26日DOTA2有一个79.6MB的更新主要是针对自动施法和快速施法的调整本来内容不多不少朋友都有自动施法和快速施法的困扰英文更新日志一些视觉BUG修复就不翻译了主要翻译自动施...

Redis 是如何提供服务的

在刚刚接触Redis的时候,最想要知道的是一个’setnameJhon’命令到达Redis服务器的时候,它是如何返回’OK’的?里面命令处理的流程如何,具体细节怎么样?你一定有问过自己...

lua _G、_VERSION使用

到这里我们已经把lua基础库中的函数介绍完了,除了函数外基础库中还有两个常量,一个是_G,另一个是_VERSION。_G是基础库本身,指向自己,这个变量很有意思,可以无限引用自己,最后得到的还是自己,...

China&#39;s top diplomat to chair third China-Pacific Island countries foreign ministers&#39; meeting

BEIJING,May21(Xinhua)--ChineseForeignMinisterWangYi,alsoamemberofthePoliticalBureau...

移动工作交流工具Lua推出Insights数据分析产品

Lua是一个适用于各种职业人士的移动交流平台,它在今天推出了一项叫做Insights的全新功能。Insights是一个数据平台,客户可以在上面实时看到员工之间的交流情况,并分析这些情况对公司发展的影响...

Redis 7新武器:用Redis Stack实现向量搜索的极限压测

当传统关系型数据库还在为向量相似度搜索的性能挣扎时,Redis7的RedisStack...

Nginx/OpenResty详解,Nginx Lua编程,重定向与内部子请求

重定向与内部子请求Nginx的rewrite指令不仅可以在Nginx内部的server、location之间进行跳转,还可以进行外部链接的重定向。通过ngx_lua模块的Lua函数除了能实现Nginx...