ITPub博客

首页 > 数据库 > Oracle > HASH JOIN

HASH JOIN

原创 Oracle 作者:eworm 时间:2007-08-23 16:00:51 0 删除 编辑

HASH JOINS ALGORITHM

In this section, we present a simplified step-by-step outline of the Oracle hash join algorithm.

[@more@]

HASH JOINS ALGORITHM

In this section, we present a simplified step-by-step outline of the Oracle hash join algorithm.

Step 1 – Determine fan-out Such that:

(Number of Partitions) * C<= Favm *M

where Favm is the usable fraction of hash area and C is the cluster size. Fan-out Calculation takes into account overhead required for partition, hash tables, bitmap vector filter,some extra buffers

required for asynchronous I/O and parallel query.

WHILE ( ROWS IN S ) LOOP

Step 2 – Read the join column value and select-list items from S.

Use an internal hash function, say HASH_FUN_1, and map the join column value to a partition.

Also generate a hash value for the next level using another hash function, say HASH_FUN_2, and store it with the join key. The second hash function value will be used to build a hash table in the later part of the algorithm

Step 3 – Build bitmap vector for all unique keys in build input.

Step 4 – If no space in the partition, write the partition to disk.

END LOOP

Step 5 – Try to fit the maximum number of possible partitions in memory from which a Hash table can be built and flush the rest to disk

Step 5.1 – Sort partitions by size.

Step 5.2 – Choose smallest number of partitions that fit in memory.

Step 5.3 – Schedule disk writes on other (Fan-out - X) number of partitions.

Step 6 – Build hash table from X partitions of S, using hash value already calculated for next level using HASH_FUN_2.

WHILE ( ROWS TO BE READ FROM B ) LOOP

Step 7

Step 7.1 – Filter rows using bit-vector.

Step 7.2 – Hash the rows that pass the bit-vector filter into the appropriate partition using join key and internal HASH_FUN_1.

Step 7.3 –IF hashed row falls into partitions in memory

Perform join by applying internal HASH_FUN_2 value and traversing the appropriate hash bucket

ELSE

Write to disk to the appropriate partition of S (we do keep track of Ri and Si pairs on disk through the partition table) the HASH FN2 value, the join keys, and select list items

END LOOP

Step 8 – Read (S,B) unprocessed partition pairs from disk.

Use smaller input to build hash table and larger one for probe. In building the hash table we use internal HASH_FUN_2 value. This results in dynamic role reversal leading to zigzag execution trees. On the first iteration, the optimizer should select the smaller table to be the build input and the larger table to be the probe. Role reversal only takes place after the first iteration.

Step 9 – If the smaller of the two inputs is too large and does not fit in memory then read the smaller build input into memory in chunks and iterate over the probe. This is called the nested hash loops join.

END OF HASH JOIN ALGORITHM

-----------------------------------------------------------------------------------------------------------------------

Hash Join算法

1步:判定小表是否能够全部存放在hash area内存中,如果可以,则做内存hash join。如果不行,转第二步。

2步:决定fan-out数。(Number of Partitions) * C<= Favm *M

其中CCluster size

其值为DB_BLOCK_SIZE*HASH_MULTIBLOCK_IO_COUNTFavmhash area内存可以使用的百分比,一般为0.8左右;MHash_area_size的大小。

3步:读取部分小表S,采用内部hash函数(这里称为hash_fun_1),将连接键值映射至某个分区,同时采用hash_fun_2函数对连接键值产生另外一个hash值,这个hash值用于创建hash table用,并且与连接键值存放在一起。

4步:对build input建立位图向量。

5步:如果内存中没有空间了,则将分区写至磁盘上。

6步:读取小表S的剩余部分,重复第三步,直至小表S全部读完。

7步:将分区按大小排序,选取几个分区建立hash table(这里选取分区的原则是使选取的数量最多)

8步:根据前面用hash_fun_2函数计算好的hash值,建立hash table

9步:读取表B,采用位图向量进行位图向量过滤。

10步:对通过过滤的数据采用hash_fun_1函数将数据映射到相应的分区中去,并计算hash_fun_2hash值。

11步:如果所落的分区在内存中,则将前面通过hash_fun_2函数计算所得的hash值与内存中已存在的hash table做连接, 将结果写致磁盘上。如果所落的分区不在内存中,则将相应的值与表S相应的分区(依据分区表实现)放在一起。

12步:继续读取表B,重复第9步,直至表B读取完毕。

13步:读取相应的(Si,Bi)hash连接。在这里会发生动态角色互换。

14步:如果分区过后,最小的分区也比内存大,则发生nested- loop hash join

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7988176/viewspace-965292/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    29
  • 访问量
    336106