hash join构建位图的示例分析

121次阅读

共计 1612 个字符，预计需要花费 5 分钟才能阅读完成。

这篇文章主要介绍了 hash join 构建位图的示例分析，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让丸趣 TV 小编带着大家一起了解一下。

hash join 的逻辑
— 全表扫描小表，并把关联字段的值取出，在 pga 里构建 hash table。
— 遍历大表，根据扫描的结果按照关联字段执行相同的 hash 函数，得到 hash value，去 pga 的 hash table 里找匹配记录。

较小的 row source 被用来构建 hash table 与 bitmap，第 2 个 row source 被用来被 hansed，并与第一个 row source 生成的 hash table 进行匹配，以便进行进一步的连接。Bitmap 被用来作为一种比较快的查找方法，来检查在 hash table 中是否有匹配的行。特别的，当 hash table 比较大而不能全部容纳在内存中时，这种查找方法更为有用。这种连接方法也有 NL 连接中所谓的驱动表的概念，被构建为 hash table 与 bitmap 的表为驱动表，当被构建的 hash table 与 bitmap 能被容纳在内存中时，这种连接方式的效率极高。

位图索引的理解
位图索引：表有多少行则索引就有多少比特位，比如表的 id 字段建立位图索引（只有 5（第一行）、10（第二行）、15（剩下所有行）三个值），表有 100 行，则索引就有 100 比特位，则表第一行是 5，则第一行对应第一个索引值，索引块中第一个索引值是 5 后面对应的不是传统的 B 树索引性质的 rowid 而是位图标识如 1000000000000（99 个 0），表第二行是 10，则第二行对应第二个索引值，索引块中第二个索引值是 10 后面对应 01000000000000（98 个 0），第三行之后的所有行对应第三个索引值 001111111（98 个 1）
索引块如下
5 1000000000000
10 0100000000000
15 0011111111111
通过上面的 1 可以看出 5 只有 1 行是第一行，10 只有 1 行是第二行，15 对应后面的 98 行，如果如下每隔四行就是 5，则说明 5 总计有 20 个值，发现每列只有一个 1, 其实就是每行只有一个值得原因
5 1000010000100
10 0100000000000
15 0011101111011

以下为个人对 hash 位图的一些理解
位图就类似下面 a[1][0]、a[1][1]、a[1][2]、..a[1][9]、..a[10][0]
1、2、3、4、..、100
1、2、3、4、..、1000
1、2、3、4、..、10000
如何快速找出 28
a[10][10]
a[100][10]
a[1000][10]

mod(10,10)
a[1][0]=1
a[1][1]=11
..
a[1][9]=91
a[2][0]=2
a[2][1]=12
..
a[2][9]=92
…
a[8][?]
[8][2]- 28
以上 a[10][0]=10、a[10][1]=20（因为十位为 1，就是 10. 加上前面个位的 10，就是 20）..a[10][9]=100
1、11、21、31、…91
2、12、22、32、…92
3、13、23、33、…93
…
8、18、28、38、…98
..
10、20、30、40、…100