| 失效链接处理 |
|
GBase8s两表连接算法 PDF 下载
本站整理下载：
相关截图：
主要内容：
关系代数的一项重要操作就是连接操作，两表连接的方式对连接效率的提高有着直接的影响，这里我们简单谈一谈。
基本的两表连接算法主要有嵌套循环连接和Hash连接算法。下面针对这两个算法进行介绍：
（1）嵌套循环连接算法
两个表做连接，一般多采用这种连接算法。描述如下：
FOR EACH ROW r1 IN t1 {
FOR EACH ROW r2 IN t2 {
IF r1,r2 SATISFIES JOIN CONDITIONS
JOIN r1,r2
}
}
数据库引擎在实现这个算法的时候，以元组为单位进行连接。元组是从一个内存页获取的，而页是从存储层通过IO操作获得的，每个IO申请以“块”为单位读入多个页。所以考虑获取元组的方式，可以改进这个算法，改进后的算法为基于块的循环连接算法。描述如下：
FOR EACH CHUNK c1 OF t1 {
IF c1 NOT IN MEMORY // 一次读入多个页面
READ CHUNK c1 INTO MEMORY
FOR EACH ROW r1 IN CHUNK c1 { //从页面中分析出元组，消耗CPU
FOR EACH CHUNK c2 OF t2 {
IF c2 NOT IN MEMORY
READ CHUNK c2 INTO MEMORY
FOR EACH ROW r2 IN c2 { //从页面中分析出元组，消耗CPU
IF r1,r2 SATISFIFS JOIN CONDITIONS
JOIN r1,r2
}
}
}
}
无论是嵌套循环连接还是基于块的嵌套循环连接，其本质都是在一个两层的循环中拿出各自的元组，逐一匹配是否满足连接条件。其他一些两表连接算法，多是在此基础上进行的改进，如：基于索引做的改进等。
（2）Hash连接算法
基于Hash的连接算法有如下：
用连接列作为Hash值，对内表进行Hash运算建立hash表，然后对外表的每个元组的连接列用Hash函数求值，值映射到内表建立好的Hash表就可以连接了；否则，探索外表的下一个元组。这样的Hash算法称为简单Hash连接（SHJ）
如果把内表和外表划分成等大小的子表，然后对外表和内表的每个相同下标值的子表进行SHJ算法的操作，可以避免因内存小反复读入内外表的数据问题。这样的改进算法称为优美Hash连接算法（GHJ）
结合以上两个算法，称为混合Hash连接算法（HHJ）。HHJ算法是把第一个子表保存到内存不刷出，如果内存很大，则子表能容纳更大量的数据，效率接近于SHJ。
Hash类的算法都可能存在Hash冲突，如GHJ算法，当内存小或数据倾斜（不能均衡地分布到Hash桶，Hash处理后集中在少量桶中）时，通过把一个表划分为多个子表的方式，仍然不能消除反复读入的内外表数据的问题（称为“分区溢出”）。
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
