hash join原理介绍
http://www.itpub.net/315494.html
[B]
二.
Hash Join原理
我们用一个例子来解释Hash Join算法的原理,以及上述所提到的术语。
考虑以下两个数据集。
S={1,1,1,3,3,4,4,4,4,5,8,8,8,8,10}
B={0,0,1,1,1,1,2,2,2,2,2,2,3,8,9,9,9,10,10,11}
Hash Join的第一步就是判定小表(即build input)是否能完全存放在hash area内存中。如果能完全存放在内存中,则在内存中建立hash table,这是最简单的hash join。
如果不能全部存放在内存中,则build input必须分区。分区的个数叫做fan-out。Fan-out是由hash_area_size和cluster size来决定的。其中cluster size等于db_block_size * hash_multiblock_io_count,hash_multiblock_io_count在oracle9i中是隐含参数。这里需要注意的是fan-out并不是build input的大小/hash_ara_size,也就是说oracle决定的分区大小有可能还是不能完全存放在hash area内存中。大的fan-out导致许多小的分区,影响性能,而小的fan-out导致少数的大的分区,以至于每个分区不能全部存放在内存中,这也影响hash join的性能。
..............................
[/B]
但这样的原理介绍是hash join实现的介绍,是而且跟Oracle数据库是绑定的,我现在想要知道的是如果抛开数据库,也就是说不管是oracle也好,sybase也好,hash join总有一个公共的原理的,只不过在不同的rdbms的实现方法不同而已,那么这个原理是什么呢?那位xd可以从纯粹从算法的角度来解析一下?
|