数据库Join算法原理与优化
连表算法详解 连表算法是数据库管理系统(DBMS)中的一种重要操作,它将割开的关系重组起来,组成一个新的关系。连表算法的本质是将两个表的关系组合起来,得到一个新的关系。例如,xxx在班,班在3楼,把这两条关系组合起来,就可以得到“xxx在3楼”这个关系。 连表算法的原则是尽量把小表(所占页数较少的表)放在左侧(此时这个小表也叫驱动表),后面会讲到,这会减少硬盘IO次数。 join算法的输出R表的 一条数据和S表的一条数据,它们的连接列match上了(也就是相等),之后这两条数据就可以组合成一条新的数据,输出给join算法的父算法。 join算法输出的内容由以下三个因素决定: 1. SQL处理模型 2. 存储模型 3. 整个SQL语句所需要的数据 join算法输出的内容有如下几种: 1. 直接输出数据 这种情况属于早物化,被join的都是完整的tuple,因此join操作结束后输出的就是完整的一行数据。这样处理的好处在于,join操作输出的结果是完整的,如果join的父算法(project),那么就可以直接将感兴趣的字段输出,无需再回到原始的表中找数据(这个操作简称回表)。 2. 输出recordid 这种属于晚物化,join后得到的一条数据里只含有在相对应的原始表中的record id,而不是全部的字段。上级的父算法如果需要原始的表中的其他字段,就需要回表。 这种输出方式符合列存储的思想,DBMS在对join后得到的表执行查询时无需拷贝不需要的数据。 join操作的开销假设R表有M个页大,含有m条数据,S表有N个页大,含有n条数据,我们首先通过分析硬盘I/O次数来分析join操作的开销。 此外,还要注意一个和笛卡尔积相关的问题,join算法在SQL语句中最为常见,也最耗时,最容易出问题,因此对其进行的优化必须格外小心,join操作有时可以通过笛卡尔积来完成,先对两个表进行笛卡尔积,然后用谓词来筛选,但这非常低效,因为笛卡尔积导致的中间结果非常巨大,所以说除了笛卡尔积以外,DBMS的设计者更倾向于采用以下几种join算法。 join算法的类型有很多,常见的有: 1. NestedLoopjoin嵌套循环join 伪代码如下,外层循环是遍历R表的所有行,对于R表的每一行,再开一个内层循环,遍历S表的所有行,看r和s能不能连上其中,因为R表是小表,所以被放在外层循环中,也同时被放在了join算法的左侧,被称为outertable(对于基于硬盘的DBMS来说,所谓的“小表”一般是指所占的文件页少的,R表虽然行数多,但它比较窄,所占用)。 2. Sort-Merge Join 排序合并join 这种算法首先对R表和S表进行排序,然后对两个表进行合并,得到最终的结果。 3. Hash Join 哈希join 这种算法使用哈希函数将R表和S表分配到不同的桶中,然后对每个桶进行join操作,最后将结果合并。 4. Index Join 索引join 这种算法使用索引来加速join操作,首先对R表和S表创建索引,然后对两个表进行join操作。 join算法的优化是DBMS中非常重要的一步,对于join操作的优化可以减少硬盘IO次数,提高查询效率。
![](https://csdnimg.cn/release/download_crawler_static/86324081/bg4.jpg)
剩余15页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/904c451ab56d4fa6b710a15c5a7cc68d_weixin_35745051.jpg!1)
- 粉丝: 26
- 资源: 298
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 中国微型数字传声器:技术革新与市场前景
- 智能安防:基于Hi3515的嵌入式云台控制系统设计
- 手机电量低时辐射真增千倍?解析手机使用谣言
- 56F803型DSP驱动的高精度大功率超声波电源控制策略研究
- ARM与GPRS结合的远程监测系统设计
- GPS与RFID技术结合的智能巡检系统设计
- CPLD驱动的低功耗爆炸场温度测试系统设计
- 基于FPGA的智能驱动控制系统:可扩展设计与工业网络协议
- 基于ATmega128和CH374的嵌入式USB接口设计
- 基于AT89C52的温度补偿超声波测距仪:高精度设计与应用
- MSP430F448单片机在交流数字电压表中的应用
- 提升变频器应用效率的12项实用技巧
- STM32F103在数字电镀电源并联均流系统中的应用
- PSpice仿真下的升压开关电源设计:拓扑分析与CCM稳定性提升
- 轻巧高效:MSP430主导的低成本无线传感器网络节点设计
- FPGA在EDA/PLD中实现LVDS接口的应用解析
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)