Hello DBA

我们对hash join的通常的认识：适用于一个小表和一个大表作关联，小表build hash table，扫描大表作为probe table，通过hash函数完成join的动作，这应该是最简单的认识，实际上hash join比这个要复杂一些。

1.Optimal Hash Join

这是最理想的情况，如果hash area足够容纳hash table，那么就和我们之前理解的一致。不过我测试发现，就算hash area足够大，事实上还是要对hash table作分区的，只不过所有的分区都在内存中。我们来看看event 10104 trace的部分内容：

Original memory: 5336064
Memory after all overhead: 5213832
Memory for slots: 2826240（slots的可用空间2760KB)
Calculated overhead for partitions and row/slot managers: 2387592
Hash-join fanout: 8 （hash table 8个partition）
Number of partitions: 8
Number of slots: 23 （共有23个slot/cluster）
Multiblock IO: 15
Block size(KB): 8
Cluster (slot) size(KB): 120 （每个cluster 15*8KB=120KB）
Hash-join fanout (manual): 8
Cluster/slot size(KB) (manual): 192
Minimum number of bytes per block: 8160
Bit vector memory allocation(KB): 256
Per partition bit vector length(KB): 32
Maximum possible row length: 163
Estimated build size (KB): 100 （估算实际需要100KB的空间）
Estimated Row Length (includes overhead): 19

Partition:0    rows:841        clusters:1      slots:1      kept=1
Partition:1    rows:858        clusters:1      slots:1      kept=1
Partition:2    rows:812        clusters:1      slots:1      kept=1
Partition:3    rows:844        clusters:1      slots:1      kept=1
Partition:4    rows:871        clusters:1      slots:1      kept=1
Partition:5    rows:843        clusters:1      slots:1      kept=1
Partition:6    rows:838        clusters:1      slots:1      kept=1
Partition:7    rows:814        clusters:1      slots:1      kept=1

可以看到每个分区大至800条数据，每个分区分配了1个cluster，并且都在内存中(slots:1代表第一个slot在内存中，kept=1整个分区都在内存中)。

2.onepass hash join

当hash area无法容纳所有的分区，但是却足够容纳至少一个分区时，这种情况就是onepass hash join。需要首先对hash table做分区，然后将其写入到磁盘的临时空间，当hash table完成分区后，然后对probe table也用同样的hash函数作分区，然后对应的分区分别做join。需要注意的是，除了第一个分区，从第二个分区开始，Oracle会自动根据分区的大小来交换build table和probe table，以期望达到更好的性能。因为所有的分区只需要从磁盘上读取一次就可以完成，所以叫onepass.

还有一个东西值得关注：Bit vector memory，这是一块位图区域，实际上他保存了hasn table所有分区的hash bucket位图，在hash join时，首先在这里寻找对应的hash bucket，如果发现则置1，否则就丢弃这一行。

Original memory: 9919499
Memory after all overhead: 9919499
Memory for slots: 6094848
Calculated overhead for partitions and row/slot managers: 3824651
Hash-join fanout: 16
Number of partitions: 16
Number of slots: 24
Multiblock IO: 31
Block size(KB): 8
Cluster (slot) size(KB): 248
Hash-join fanout (manual): 8
Cluster/slot size(KB) (manual): 440
Minimum number of bytes per block: 8160
Bit vector memory allocation(KB): 1024
Per partition bit vector length(KB): 64
Maximum possible row length: 67
Estimated build size (KB): 31250
Estimated Row Length (includes overhead): 32

Partition:0    rows:62767      clusters:5       slots:1      kept=0
Partition:1    rows:62479      clusters:5       slots:1      kept=0
Partition:2    rows:62448      clusters:5       slots:1      kept=0
Partition:3    rows:62559      clusters:5       slots:1      kept=0
Partition:4    rows:62780      clusters:5       slots:1      kept=0
Partition:5    rows:62278      clusters:5       slots:1      kept=0
Partition:6    rows:62193      clusters:5       slots:1      kept=0
Partition:7    rows:62168      clusters:5       slots:1      kept=1
Partition:8    rows:62672      clusters:5       slots:1      kept=1
Partition:9    rows:62526      clusters:5       slots:1      kept=1
Partition:10   rows:62196      clusters:5      slots:1      kept=1
Partition:11   rows:62495      clusters:5      slots:1      kept=1
Partition:12   rows:63283      clusters:5      slots:1      kept=1
Partition:13   rows:62185      clusters:5      slots:4      kept=1
Partition:14   rows:62468      clusters:5      slots:1      kept=1
Partition:15   rows:62503      clusters:5      slots:5      kept=1

这里可以看到，每个分区就算不在内存中，也必须至少有一个slot在内存中。我们可以看到只有最后一个分区，所有的slot都在内存中。我没搞明白的是，有些分区只有1个slot在内存中，为什么kept=1。

3.multipass hash join

当hash area甚至都无法容纳其中的一个分区时，这时就有些麻烦了。可能有两种做法：1.将hash table partition再分区（可以容纳在hash area中），然后针对每个小分区，循环扫描整个probe table，来完成hash join。2.将hash table和probe table都用同样的hash函数再分区，直到分区足够小可以放在hash area中。很明显，第一个效率会很差，因为probe table会被循环扫描，但是很不幸，Oracle正是采用了这个方法，我们可以称之为nest loop hash join或者是multipass hash join。为什么Oracle没有采用第二种方法，我觉得是考虑了算法复杂度的原因。

这篇文章参考了《cost based oracle fundamentals》，光辉兄很早以前写的一篇有关hash join的文章以及metalink中的一些内容，并结合了我自己的一些测试。

hash join可以通过event 10104了解到更多细节的内容，这里就不一一赘述。

–EOF–