CMU15-445笔记(九)
Join
Operator Output
Data
Early Materialization
将需要join的数据复制到新的tuple中，这样做的好处就是接下来的子操作不会再回到原来的tuple进行更多的操作。
Record Ids
Later Materialization
只复制join匹配上的主键，以及join key，当需要数据的时候，直接去相应的table中获取
I/O Cost Analysis Criteria
衡量join algorithm好坏的标准在于I/O的数量
接下来的讨论会基于以下假设：
表R，有M个pages和m个tuples
表S，有N个pages和n个tuples
Join Algorithm
Nested Loop Join
就是for循环，这种方法是最暴力的方式
Cost是M + (m * N)
Block Nested Loop Join
将outer table用block来读取（也可以是一个page），inner table用另外一个block读取，这样可以减少io次数
如果有多个buffer page 的话，假设为B个，其中一个用于inner table，另一个用于output， 那么outer table就可以一次缓存 B-2个page
这样cost也会减少
Index Nested Loop Join
给inner table使用index（可以是B+树），来加快查找的速度
Sort Merge Join
有两个步骤
- Sort
- 将inner和outer table通过join key进行排序
- 这里排序可以使用上一个笔记当中说到的各种排序方式
- Merge
- 通过扫描（双指针）两个表的key，来达到join的目的
Hash Join
大概思路就是先将outer table的key通过hash进行分区，然后将inner table的key也通过相同的hash分区到和outer hash值一样的区域，然后根据这些分区来逐个进行join，主要步骤有两个：
- Build
- 扫描outer table 然后用假设叫h1的hash function 来hash join属性到hash table中
- Probe(探测)
- 扫描inner table，用h1来hash join属性，然后取定位到outer table的hash tabel中，这样就能找到匹配到的tuple
这里hash table的key就是需要join的字段，value取决于具体实现
Hash Table Values
有两个方法
- Full Tuple
- 将整个tuple放入hash table中
- 这样可以避免来回的查找，因为hash table中已经有全部的需要的字段，但是也会占用大量的空间
- Tuple Identifier
- 直接用tuple record id，需要数据的时候去disk里面取
- 减少大小
Probe Phase Optimization
可以使用布隆过滤器，来判断key是否存在于hash table中（可能会误判不存在为存在，但是无关紧要），由于布隆过滤器很小，所以可以直接放入内存中，这样就可以让inner table查找outer key是否存在的时候，先看布隆过滤器，然后再去找hash table(因为hash table 会很大，所以内存放不下，读取需要多次IO)，这样就减少了IO次数
Bloom Filters
使用了bitmap来回答是否数据存在，有误差，可能将不存在判断为存在
Grace Hash Join
与常规的Hash Join 不同，Grace Hash Join两个table都需要进行hash，然后通过遍历相同hash值的bucket来进行join
如果bukckets太大了，放不进内存中就有
Recursive Partitioning(递归分区)
如果其中一个bucket太大了， 就可以使用另一个hash将这个bucket继续拆分
hash join的cost
Summary
结论
hash总是一个比sort更好的方法，例外是
- 当数据分布为及其不均匀的
- 当结果需要sort
CMU15-445笔记(九)