Hash join算法
hash join的基本思想是根据晓得row sources（称作build input）建立一个可以存在于hash area内存中的hash table，然后用大的row sources（称作probe input）来探测前面所建的hash table。
如果hash area内存不够大，hash table就无法完全存放在hash area内存中。针对这种情况，oracle在连接键利用一个hash函数build input和probe input分割成许多个不相连的分区（分别记作Si和Bi）；这个阶段就做分区阶段；然后各自相应的分区再做hash join，这个阶段叫做join阶段。
如果在分区后，针对某个分区所建的hash table还是太大的话，oracle就采用nested-loops hash join。nested-loops hash join就是对部分Si建立hash table，然后读取所有的bi与所建立hash table做连接，然后再对剩余的si建立hash table，再将所有bi与所建立的hash table做连接，直至所有的si都连接完了。
hash join算分有一个限制，它是在假设两张标在连接键上是均匀的，也就是每个分区拥有差不多的数据。但是实际当中数据都是不均匀的，为了很好的解决这个问题，oracle引进了几种技术： 位图向量过滤、角色互换、柱状图
14.如果分区活 后，最小的分区也比内存大，则发生nested- loop hash join
Cost(HJ)=Read(S)+ build hash table in memory(CPU)+Read(B) +
Perform In memory Join(CPU)
忽略cpu的时间，则
Cost(HJ)=Read(S)+Read(B)
Cost(HJ)=Cost(HJ1)+Cost(HJ2)
Cost(HJ1)的成本就是扫描S,B表，并将无法放在内存上的部分写回磁盘，对应前面第2步至第12步。
Cost(HJ2)即为做nested-loop hash join的成本，对应前面的第13步至第14步。
其中Cost(HJ1)近似等于Read(S)+Read(B)+Write((S-M)+(B-B*M/S))。
因为在做nested-loop hash join时，对每一chunk的build input，都需要读取整个probe input，因此
Cost(HJ2)近似等于Read((S-M)+n (B-B M/S))
其中n是nested-loop hash join需要循环的次数。
n=(S/F)/M
一般情况下，如果n大于10的话，hash join的性能将大大下降。从n的计算公式可以看出，n与Fan-out成反比例，提高fan-out，可以降低n。当hash_area_size是固定时，可以降低cluster size来提高fan-out。
从这里我们可以看出，提高hash_multiblock_io_count参数的值并不一定提高hash join的性能。
当驱动结果集生成的hash表全部可以放入PGA的hash area时，称为optimal，过程如下
这个是最优的hash join，它的成本就是两张标的full table scan，再加上微量的hash运算
如果进程的pga很小，或者驱动表结果集很大，超过了hash_area的大小，会用到临时表空间。
数据是经过两次hash运算的，先确定你的partition，再确定你的bulket，假设hash area小于整个hash table，但至少大于一个partition的size，这个时候走的就是onepass。
当我们生成好hash表后，状况是部分partition留在内存中，其他的partition留在磁盘临时表空间中，当然也有可能某个partition一半在内存，一半在磁盘，剩下的步骤大致如下：
相比optimal，他多出的成本是对于无法放入内存的partition，重新读取了一次，所以称为onepass，只要你的内存保证能装下一个partition，oracle都会腾挪空间，每个磁盘partition做到onepass
这是最复杂，最糟糕的hash join，此时hash area小到连一个partition也容纳不下，当扫描好驱动表后，可能只有半个partition留在hash area中，另半个加其他的partition全在磁盘上,剩下的步骤和onepass比价类似，不同的是针对partition的处理
由于驱动表只有半个partition在内存中，探测表对应的partition数据做探测时，如果匹配不上，这行还不能直接丢弃，需要继续保留到磁盘，和驱动表剩下的半个partition再做join，这里举例的是内存可以装下半个partition，如果装的更少的话，反复join的次数将更多，当发生multipass时，partition物理读的次数会显著增加
ZESTRON
2024-09-04 广告
