欢迎光临散文网 会员登陆 & 注册

CMU 15-445/645-笔记-11-Join 算法

2022-11-28 12:30 作者:dengluzhanghao  | 我要投稿

## 课程目标


### 为什么需要 Join?


Join 实际上是关系型数据库系统和范式化(normalize)表(table)时的副产物,通过拆分到不同的表中,减少重复冗余的信息(比如外键)


在没有任何信息丢失的情况下,使用 Join operator 可以对原来的 tuple 进行重组


### Join 算法


在这节课中,会关注一次只 Join 2 个表的情况,会谈到 inner equijoin 算法,这个算法是目前数据库系统中最常见的算法实现


当然也有 Multi-way Join 算法,它可以在同一时间内对 3 张以上的表进行 Join 操作(这几乎只存在理论中,仅有部分高端系统已经支持了这个,15-721 课会讲到这个算法)


equijoin 指的是,从一个表中拿到一个 tuple,检查它是否和另一个表中的 tuple 相等,能不能匹配的上(这里不考虑大于小于,也不考虑 anti-join)


那么 Join 操作大致是怎么的呢? —— 始终把更小的表作为 Join 操作中的左表(left table)


想象一下之前提到过的查询计划树(Query Plan Tree),在这个树上的 operator 节点处,它下面有左右 2 个子节点,这 2 个子节点作为该 operator 节点的输入(递归遍历)。在这 2 个子节点中,左边那个节点就是这个 更小的表,即 左表


> 注意这里说的 outer table,指的也是左表


### Join Operator


Join Operator 是如何工作的? 


这个就需要涉及到查询计划树了,基本上原理就是,拿到一个 SQL 查询中的关系代数,然后将它转变成一个有向图/树


比如上图中,在叶子节点处要对表进行访问,将表中的 tuple 作为输入,传给父节点处的 operator,而这里,就是一个 Join Operator,这个 Join Operator 的左边就是 outer table 即左表,右边的就是 inner table


那么 Join Operator 的输出是什么?


### Join Output


对于所有属于 R 表中的 tuple,用 r 表示,对于所有属于 S 表中的 tuple,用 s 表示


在输出结果时,如果满足 Join 条件,那么就将符合条件的 tuple 向上传给树中的下一个 operator


从更高层面来说,Join 其实就是对 2 个表中的 tuple 进行级联


比如上图中,拿到 R 表和 S 表中的所有属性,将它们杂糅到一起,然后输出结果


虽然这个操作在理论上可行(取所有属性),但是在实际工程中,需要考虑到磁盘读取、使用多少内存,所以并不会去把所有属性都拿到


整个流程就是,将当前 operator 的输出结果发送给下一个 operator,如何发送会取决于实现的查询模型。在这个流程中,输出的结果的发送并不会是 一直只发送一个 tuple,而是也会发送多个 tuple,发多发少也取决于存储模型,比如是基于行数据库还是基于列数据库


对于发送 tuple 的属性来讲,发送对应的 tuple 的属性的多少取决于查询计划树,在输出结果的发送过程中,可能不需要将这 2 个表中所有属性都发送出去,而是只需要发送部分属性就可以了


#### Join Operator Output: Data


第一个方案就是发送数据,即复制 Join 条件中 tuple 的属性值,生成一个新的输出 tuple,然后传给下一个 operator


如图所示,上图中有 R 表和 S 表,当对这 2 个表进行 Join 操作时


其实就是将 S 表中的属性追加到 R 表属性的后面,这就是 Join operator 所生成的新的结果


对应于查询计划树,就是上图中出现的结果(Join operator 对应的地方)


这样做有优势也有劣势


1. 优势

    在上述查询计划树中,就不需要回过头去从基础表里面去读取更多数据了,因为从 R 表和 S 表中 Join 出来的数据会被用来生成 inner join 的输出

2. 劣势

    因为 Join operator 生成的这个新的结果,导致这个结果即 tuple 巨大无比(如果 R 表和 S 表中的属性非常多,这个 tuple 所具备的属性就变得超级多),将这样的结果进行复制并沿着查询计划树向上传递,那代价就会变得昂贵


因为这个劣势存在,所以在执行 Join 操作之时,可以内嵌执行 Projection 操作,过滤掉 R 表和 S 表中那些不需要的属性和字段,这样最终生成的 tuple 才是合理的


#### Join Operator Output: Record Ids


第二个方案就是,只发送所需要的最小限度的信息,即 Join keys。这个最小限度的信息同时也包括 匹配 Join 条件的 tuple 的 record id,通过这个 record id 可以找到表中其他剩余的数据


如图所示,上图中只在 R.id 和 S.id 上进行 Join 操作,所以在 Join operator 的输出结果中,其 R.id 要和 R.rid 匹配上,S.id 要和 S.rid 匹配上(rid 即 record id)


有什么用呢? 如果此时需要将 R 表或 S 表中其他属性的值找到,只需要利用这个对应的 record id,或者 tuple id 中的 page number 以及 offset 值,就可以找到该 tuple 其他剩余的属性的值


然后经过 Join operator 生成一个新的结果


此时如果想要拿到 S.cdate,只需要通过 S.rid 即可找到对应属性的值


但是,对于列存储来说,它实际上需要将这些所有不同列的的 tuple 粘接在一起,从列形式变成行形式,然后把生成的这个结果传给查询计划树,这中间的代价依然非常昂贵(因为要传递的属性依然非常多)


那么怎么解决呢? 就是尽可能的延迟它这种从 列形式 变成 行形式 的操作,那么就不用在查询计划树中向上传递一大堆数据了


其基本思想有些类似于懒加载,即只有当 query 需要时,在执行 Join 操作之后,再去执行到磁盘中获取其他字段数据并做粘接的操作(从列形式变成行形式),比如上图中需要的 S.cdata,如果没有它,则不需要再去经历从列形式变成行形式的过程,也就提升了性能


> 但是这里有个问题,一开始就需要把数据取出来,经历从列形式变成行形式的过程,代价不是依然很高吗?这也许是第一个列存储数据库 Vertica 在 2000 年推出时一直在推崇这个技术,但到后来放弃掉它的原因吧


### I/O 成本分析


如何判断一个 Join 算法的好坏? 可以见上图


基本思路就是,**用在计算 Join 操作时所必须使用的 I/O 次数** 来做判断


> 注意,这个 *计算 Join 操作* 的过程不包括实际生成最终结果所付出的成本,因为这期间可能要考虑到其他因素


### Join VS. Cross-Product


本节主要关注的是 inner equijoin,因为这最常见


本节不会去讨论 cross product/cross join 以及 Cartesian products,因为这些东西几乎很难遇到


> cross join 也没办法让他变得更快,因为这个需要 2 个 for 循环去遍历处理这堆匹配上的数据,就像是一个不需要条件判断的 nested-loop join


但是尽管有关于 Join 算法的优化,对每种可能的场景、数据集、查询来说,不可能始终有效


## Join 算法


### Nested-Loop Join


顾名思义,它就是在一个 for 里面又嵌了一个 for


上图就是遍历 R 表和 S 表,然后看下 SQL 中的 Join 子句和 Where 子句中的条件部分,看看这些 tuple 是否满足上图中的条件,如果满足,则生成输出,它会作为下一个 tuple 的输出结果而缓存起来


> Outer 就是在外层的循环,Inner 就是在里层的循环


在实际的查询计划中,它长啥样呢?


如上图所示,左边 R 代表 Outer Table,右边 S 代表 Inner Table


这种 Join 算法肯定是最蠢的,因为对于每个在 R 表中的 tuple,每次循环都得将 S 表中的数据放入内存进行处理(显然从磁盘到内存的 I/O 变多了,所以付出的代价也变的奇高)


那么成本是多少呢?


M + (m x N)


一个鲜明的例子如下


所以这个朴素的 Join 算法需要优化,那么怎么优化呢? 将更小的表作为 Outer Table 使用对吧?


那么我们再来计算一下成本


可以看到至少要花 1.1 小时才能完成整个 Join 操作,是进步了一点,但还不太够


假设 page 是 4KB 大小,通过计算可得出这些 page 的总体积为 6MB 左右,而这完全可以放在 L3 Cache 中,这些数据放在 CPU Cache / 内存中操作当然会很快,但是如果一定要从磁盘上读取,那就会慢的离谱


### Block Nested-Loop Join


其中一种优化方式就是,使用 block 和 page,将多个 tuple 打包进 page 中


基本原理是这样的


对于 Outer Table 所用的每个 block 而言,每次从 Inner Table 中拿到一个 block 时,会让 Outer Table block 中的每个 tuple 和 Inner Table block 中的所有 tuple 进行 Join,直到这个 Outer Table block 中所有的 tuple 完成了 Join 操作,才会继续和 Inner Table 中下一个 block 的所有 tuple 进行 Join


为什么这种会好点? 因为成本降低了


M + (M x N)


这里的关键在于,**现在是让 Outer Table 中的每个 page 和 Inner Table 中的每个 page 进行 Join**


那么这里哪个是 Outer Table 呢?很显然是 page 数最小的那个


一个鲜明的例子如下


虽然优化到了 50s 左右,但这依然是一个糟糕的数字,因为要对 6MB 大小的数据进行 Join 处理不应该花上 50s 左右的时间


那么还能怎么继续优化呢?


上面的算法,对于 Outer Table 和 Inner Table 来说,它们都是使用 1 个 block 来承载数据


那么很自然就想到,如果使用 多个 block 来承载数据呢?


这个优化的基本原理是


对于 Outer Table,尽可能使用内存中的 buffer 来保存它,即使用 B-2 个 block。然后用 1 个 block 来负责 Inner Table,再用 1 个 block 用来负责输出结果


算法如上图所示


由于此时不需要再进行 m x N 次读取,所以成本计算如下


对于 Outer Table 处 page 的读取成本来说,是 M/(B-2)


所以最终为


M + (M/(B-2) x N)


那么如果 Outer Table 能完全放入内存中,会发生什么呢?


这意味着 允许 buffer 的数量 > M+2


> M+2 中的 2 ,1 个代表的是 Inner Table,另 1 个代表的是输出结果


如果能把数据放入这 B-2 个 buffer 中(这 B-2 个 buffer 包含了 Outer Table 中所有的数据),那么现在要做的就只是从 Outer Table 中获取一次数据,然后将该数据放入内存中,然后再去扫描下 Inner Table,那么成本就会变成


M + N


如下图所示


其实这里本质上就是把原来在磁盘的数据丢内存处理了,相当于少了很多 I/O,所以速度就变快了


所以如果内存足够,将 Outer Table 相关数据放入到这里,可以极大的提升性能(相比于之前的方法而言)


当然如果数据库的数据过大(TB/PB),这个还是不可行的


### 为什么 Nested-Loop Join 系列 sucks?


当然因为这是暴力查询啊


所以没有索引存在时,暴力查询就是一个备选项


那么假如能对进行 Join 操作的 key 建立索引,那么对于 Inner Table,可以将它作为内循环的一部分使用,就没必要每次都要循序扫描了


某些系统可以在运行时构建索引,比如 Hash Join。在其他系统中,比如 SQL Server,它在运行时可以构建一个名叫 Spooling Index 的 B+ Tree。在系统查询并进行 Join 操作时,就会去使用这个索引。而当查询结束,这个索引就会被丢弃掉


### Index Nested-Loop Join


首先对 Outer Table 进行扫描,这个时候可以使用额外的 buffer block,这样就不用每次都对单个 tuple 进行 I/O (从磁盘到内存)获取了


对于内部循环来说,可以使用索引探针(index probe),如果条件匹配上了,就可以检查能否生成一个输出


那么此时成本是多少呢?


这就取决于使用的索引了


M + (m x C)


> 常量 C 表示索引带来的成本消耗。如果是 Hash Table,那么时间复杂度最好情况就是 O(1)。如果是 B+ Tree,那么情况就是 log(n)


因为索引是 **有序** 的,知道了这些 tuple 的所在位置,就只需要 N 次 I/O 就能拿到对应的数据。所以对于上图中单个 page,成本是 nxC,对于 N 个 page,成本就是 N + (nxC)。要理解的话,nxC 在这里就相当于一个 offset,因为这里移动的是游标(指针),用过 C 语言的话这里理解应该不难


现在通过成本的分析可以看到,性能更佳了


### 小结


- Nested-Loop Join 方式就是一种暴力查询,虽然粗暴但是实现起来简单

- 始终需要将更小的表作为 Outer Table

- 尽可能将 Outer Table 放入内存中,减少冗余 I/O

- 有索引就用索引,加快扫描速度


### Sort-Merge Join 算法


这个所谓的 Sort-Merge Join 算法很想上节课说过的 external merge sort 算法,这个算法可以在 sort 阶段使用。(如果数据全在内存中可以使用快排)


但是到 merge 阶段,就有些不同了


merge 阶段,通过游标对这 2 个排好序的的表中的 tuple 逐个对比,如果匹配,就输出匹配的 tuple


在某些情况下,只需要对 Inner Table 中的 tuple 访问 1 次就够了(也就是说可以不需要进行回溯并多次访问,因为已经提前排好序了)


上图是这个 Join 算法的一种近似实现


以图举例


首先,先对数据做排序


然后通过游标去遍历这 2 个表


R 表中的游标指向的是 id=100 的位置,S 表中的游标指向的是 id=100 的位置,此时根据条件,它俩匹配上了,将这 2 个对应的 tuple 结合在一起,生成一个输出结果


然后移动 S 表的游标,继续匹配下一个,并生成一个结果


然后继续移动


此时 S 表中的游标指向的位置的 id 的值是 200,比 R 表中游标指向的 100 要大,所以此时移动 R 表中的游标,直到匹配上对应的条件


此时 2 个表中的游标就没必要往回走了,因为数据已经预先排好序了


这就是为什么 Sort-Merge Join 要比 Nested-Loop Join 好的原因


当然有没有可能存在回溯的情况呢? 有的,比如下图


R 表中的游标往下移动了,对应的 id = 200,此时如果 S 表依然往下移动,那么它就会错过此次的匹配机会


那么怎么解决呢?


这个就需要在 Inner Table 中维护一些元数据。操作是这样,如果在 Inner Table 中,上次遇到的这个值是 200,那么在下次 Outer Table 移动游标时,如果此时 Outer Table 游标对应的值是 200,那么如果它能匹配上在 Inner Table 中刚访问过的最后一个 tuple 的 id 值,就回到第一次在 Inner Table 中看到这个值所在的位置,比如下面


然后再执行 Join 操作,生成一个匹配输出


接下来就是按照上述算法来做匹配输出了,直到 2 个游标都到达 2 张表的最底部,整个 Join 操作宣告完成


所以这里实际上的优势就在于


**虽然 Inner Table 可回溯,但 Outer Table 不可回溯**


那么这个算法的成本是多少呢?


Inner Table 和 Outer Table 中排序所用的成本跟之前讨论过的 external merge sort 所用的成本是一样的


粗略计算,merge 的成本就是 M+N


一个例子


那么 sort-merge 会有最糟糕的情况吗?


有的


一个极端情况是,Outer Table 中每个值都和 Inner Table 中的每个值相同(比如 Table 中每个值都是 1),那这样排序就失去了意义,同时也是在浪费时间,这种情况下,其实就跟 Nested-Loop Join 算法差不多了


当然,如果发现都是这一类型的数据,直接做笛卡尔积就好了(即直接生成输出结果,不需要任何经过任何排序算法)


### 为什么 Sort-Merge Join 算法有用?


如果 id 已经排好序,那就不需要再经历一次排序


如果查询语句中包含 ORDER BY 子句,那么它就会基于要进行的 Join 操作的 key 来对表或者结果进行排序。排序之后就是做合并操作(因为在做 Sort-Merge Join 操作),最终输出结果的排序顺序和 ORDER BY 子句的排序顺序是一样的


## Hash Join


重点算法来了


Hash Join 跟 Hash Aggregation 类似,众所周知,hash 函数是确定的,如果将同一个输入传给该 hash 函数,那么它生成的值始终都是相同的


所以,如果将 Outer Table 以及 Inner Table 中的 value 进行 hash 处理,让它 mapping 到某个值上,这样的话就能对对应的数据进行分区(partition),然后在查数据时只需要在同一个 hash bucket 中查就好了


所以基本原理就是,基于 hash key 将 Outer Table 以及 Inner Table 拆分为多个分区


- 如果这些数据都能放在内存中,就可以使用之前讲过的 linear hash table(linear probing hash table、static hash table)

- 如果必须将数据溢出到磁盘,那么就可以使用之前讲过的 bucket chain hash table 进行递归分区


分区的好处在于,在查数据时,只需要关心同一个分区中的数据就行了,就不用去看整张表了


### Hash Join 算法


基本的 Hash Join 算法有 2 个阶段


1. build

    拿到 Outer Table,并对其进行循序扫描,然后对要 Join 的那个属性进行 hash 处理,将数据填入 hash table

2. probe

    对 Inner Table 进行循序扫描,用 build 阶段相同的 hash 函数对 Inner Table 中每个 tuple 进行 hash 处理,然后检查是否有匹配的 tuple


最终,如果匹配成功,就生成输出结果


例子如下


首当其冲的就是,通过 Outer Table,用一个 hash 函数构建一个 hash table


然后就是上面提到的 build 阶段,将数据填入 hash table


然后就是 probe 阶段


### Hash Table 的内容


主要就分 2 个,key 和 value


1. key

    要进行 Join 操作的那些属性

2. value

    取决于要往查询计划上传递的信息结构


### Hash Table 的 Value


这个 Value 的结构可以是怎么样的呢?


1. 存整个 tuple

    这意味着所有的 tuple 属性都能拿到,无须做回表 I/O,但同时 hash table 会变得很大,这意味着可能需要将数据溢出到磁盘,虽然查找数据是变快了

2. 只存 tuple 的标识符

    这个 tuple 的标识符就是 tuple 的 record ID,这种方式适用于列存储,不要数据时可以不用到磁盘去取。但对于行存储,即便是通过 record ID 去找,还是需要先拿到包含这个 tuple 的那个 page(这中间需要从磁盘加载到内存),然后再能对这个 tuple 做操作


### Probe 阶段优化


在 build 阶段,把一个 hash table 构建好后,可以去构建一个辅助数据结构/filter,通过它,在没有查看 这个 hash table 的情况下,可以判断要查找的 tuple 是否在这个 hash table 中


那么怎么做呢?


答案是弄一个 **布隆过滤器(Bloom Filter)**


那么什么是布隆过滤器呢? 见下图


> 又是一个在 1970 年代发明的算法,发明人就叫 Bloom


它是一种概率数据结构,一个 bitmap,可以用来响应 set membership 查询


set membership 查询可以做什么事情? 它可以判断某个 key 是否存在于要查找的集合中,来回应你 yes or no


但因为它是这种概率数据结构,所以可能会出现 假阳性 的情况


> 即它会对传入的 key 进行 2 次 hash,hash 后结果为真,但实际上 2 次 hash 可能都属于 **碰撞为真**,而那个要查找的 key 实际上并不存在


基本的布隆过滤器只做 2 件事情


1. 插入 key

2. 查找 key


不能去 删除 key


那么它是怎么运作的呢?


一个典型的 8 bit 布隆过滤器如下


比如这里要 insert 一个 'RZA' 这个 key,那么就会对 'RZA' 这个 key 进行多次 hash


hash 结果出来之后,就会去修改过滤器中所拥有的 bit 数量,如下所示(4 对应的位置和 6 对应的位置,将对应的 bit 翻转)


接着 insert 一个 'GZA' 这个 key,相似的操作


修改过滤器对应 bit 中的值


接着,查找 'Raekwon' 这个 key


经过 hash 后的结果为


3 对应的位置是 1,5 对应的位置是 0,因为 1&0 === false,所以 'Raekwon' 这个 key 就不存在


接着,查找 'ODB' 这个 key,并对其做 hash 处理


这里可以看到过滤器中 3 和 6 的位置都是 1,但是这俩位置之前已经用 'RZA' 和 'GZA' 填充过了,虽然这里面之前并没有插入过 'ODB',但显示的结果依然为真。这就是所谓的 假阳性 的情况


所以使用布隆过滤器的 插入 操作的次数越多,hash 函数越多,那么最终结果中获得假阳性的概率就会越大。所以在数据量比较小的场景是合适的,因为这样 hash 碰撞的概率会小些


那么回到 probe 优化这里来,布隆过滤器在这里的作用是什么?


在 probe 阶段,构建 hash table 时,这个 hash table 会变得很大,并且可能会溢出到磁盘。这个时候可以为这个 hash table 的 key 构建一个布隆过滤器,因为它的体积非常小,所以可以放到内存中


如下图


这个布隆过滤器会传到 Join 里,并且在对 hash table 进行检测(key)前,要通过过滤器来做一次检测(key)(因为是在内存中,所以速度会非常快)


如果 key 匹配不上 hash table 中的任何东西,那么过滤器中也没有相应能匹配的 key


过滤器提前知道了这个 key 是否在 hash table 里存在,也就避免了在 hash table 中的查找操作,同时也能避免接下来要跳到想要找的数据对应的位置时,发生的磁盘 I/O


否则,如果过滤器知道这个 key 在 hash table 中存在,那么就需要去在 hash table 中进行查找操作


因为过滤器提供的结果可能是假的(假阳性)


当然,可以通过调整布隆过滤器的大小,来避免所有位置上的数字都被设置成 1


### 无法在内存中处理的 Hash Join


如果所有数据都能放在内存中,那可以使用 linear probing hash table,基于数据大小来预估所需要的 hash table 的大小,速度会很快


但是如果现在开始要往磁盘上溢出数据,那么 hash table 处理起来就有些麻烦了(因为这样就要进行随机 I/O 了,需要对获取到的 key 进行 hash 处理到 hash table 上某个 slot 处,对于那些 miss cache 的 key 来说,就得到一个个 page 上去找)


怎么优化呢?


转变为 随机访问模式(random access pattern),即使用 hash 索引


### Grace Hash Join


> Grace 这个词来源于东京大学在 1980 年代开发的一个学术项目,一个叫 Grace 的数据库机器。虽然项目不在了,但是其相关的 paper 有。作为项目的一部分,该 paper 讨论了当数据无法放在内存中时,该如何进行 hash join


那么上图中提到的 数据库机器 是什么?


数据库机器/设备是一种专门为数据库定制的一套硬件,这套硬件由那些供应商提供,该硬件能针对数据库系统进行调整


> IBM: Netezza(现在无了)、AOL(已被 Percona 收购): Clustrix、Oracle: Oracle Exadata、Yellowbrick(2018 年初创公司)


它也有 2 个阶段


> 在普通 Hash Join 中,只对 Outer Table 进行 hash,并为其构建一个 hash table,然后检测 Inner Table 是否有符合 Join 条件的 tuple,如果有则进行 Join


1. build 阶段

    基于 hash key 来对 2 个表拆分成不同的分区,也就是 Outer Table 和 Inner Table 各自都有构建对应的 hash table,然后对匹配的分区进行 Nested-Loop Join 操作

2. probe 阶段


例子


对 Outer Table 中的值进行 hash 处理,构建它的 hash table(一个 bucket chain hash table)


> linear probe hash table 中已经存在的数据,可能会提前占据新数据 hash 过后的位置,这个已经存在的数据现在的位置,也不一定是当初它经过 hash 后所在的位置(可能有过移动),新数据经过 hash 过后也可能会出现在 hash table 中很底层的位置,会触发循序扫描


对 Inner Table 中的值进行 hash 处理,构建它的 hash table(一个 bucket chain hash table)


然后对每个分区(这里的分区就是在 hash table 里面的位置)进行编号


当构建完 hash table 后,取出同一分区中所有的 bucket,并使用一个内嵌 for 循环对它们进行遍历


因为已经提前做好了 hash 分片,那么 Outer Table 就能知道它匹配的 tuple 的边界在哪儿了


那么这里可能会出现 hash 碰撞吗?


可能的,因为使用的是同一个 hash 函数,2 个不同的值是有可能会 hash 到同一个 bucket 中


这个时候怎么解决呢? 可以在内存中对这个 bucket 使用暴力查找(避开这些存在冲突的 bucket)


但是如果所有的值都 hash 到同一位置,就会产生溢出,这个时候又如何去解决呢?


可以通过递归分区(recursive partitioning)来解决


例子


首先,对 Outer Table 进行 hash,创建一堆 bucket,并对其进行分区


如果数据已经溢出到很多 page/bucket 中时,就可以对这个 page/bucket 中的数据再进行一次 hash 处理(图中的 h1 和 h2 相同,但是 hash seed 不同),然后拆分出更多子 page/bucket


而对于 Inner Table,同样的,要对其进行 hash(这里跟 Outer Table 用同样的 h1 hash 函数)


对于类似的值,会落在相应的分区中(比如分区 0 和分区 n),但是如果此时如果 hash 到分区 1


由于在 build 阶段已经将 Outer Table 的分区 1 拆分了,所以此时需要使用 h2 hash 函数再对分区 1 做一个 hash 处理,就可以找到需要找的那个分区


所以整体的效果如下


### Grace Hash Join 成本


3x(M + N)


> 注意这里计算的是 I/O 成本


3 是来自于 build 阶段,分区时,要对 Outer Table 中 M 个 page 以及 Inner Table 中 N 个 page 进行 1 轮处理。1 轮读取(Inner Table 的相关 page),1 轮写入(根据 Outer Table 将结果写入到另一个 page 上)。


然后就是进行 join,在同一分区内对里面的 bucket 进行 Nested-Loop Join,这里要对所有的 page 进行 1 轮处理


所以加起来就是 3


对应于下图


数字举例


可以看到比 Sort-Merge Join 还要快一点


### 小结


算法快慢比较


## 结论


除非所操作的数据已经提前排好序,不然 hash join 永远比其他 join 算法要好

CMU 15-445/645-笔记-11-Join 算法的评论 (共 条)

分享到微博请遵守国家法律