Oracle里的哈希连接原理
Posted: January 30, 2013 | Author: Cui Hua | Filed under: Oracle | 21 Comments »哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。
在Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接方法都有其明显缺陷。对于排序合并连接,如果两个表在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集很大且需要排序的话,则这种情况下的排序合并连接的执行效率一定是很差的;而对于嵌套循环连接,如果驱动表所对应的驱动结果集的记录数很大,即便在被驱动表的连接列上存在索引,此时使用嵌套循环连接的执行效率也同样会很差。
为了解决排序合并连接和嵌套循环连接在上述情形下执行效率不高的问题,同时也为了给优化器提供一种新的选择,Oracle在Oracle 7.3中引入了哈希连接。从理论上来说,哈希连接的执行效率会比排序合并连接和嵌套循环连接的执行效率要高,当然,实际情况并不总是这样。
在Oracle
_HASH_JOIN_ENABLED的默认值是TRUE,表示允许CBO在解析目标SQL时考虑哈希连接。当然,即使你将该参数的值改成了FALSE,我们使用USE_HASH Hint依然可以让CBO在解析目标SQL时考虑哈希连接,这说明USE_HASH Hint的优先级高于参数_HASH_JOIN_ENABLED。
如果两个表(这里将它们分别命名为表T1和表T2)在做表连接时使用的是哈希连接,则Oracle在做哈希连接时会依次顺序执行如下步骤:
1、 首先Oracle会根据参数HASH_AREA_SIZE、DB_BLOCK_SIZE和_HASH_MULTIBLOCK_IO_COUNT的值来决定Hash Partition的数量(Hash Partition是一个逻辑上的概念,所有Hash Partition的集合就被称之为Hash Table,即一个Hash Table是由多个Hash Partition所组成,而一个Hash Partition又是由多个Hash Bucket所组成);
2、 表T1和T2在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集中数据量较小的那个结果集会被Oracle选为哈希连接的驱动结果集,这里我们假设T1所对应的结果集的数据量相对较小,我们记为S;T2所对应的结果集的数据量相对较大,我们记为B;显然这里S是驱动结果集,B是被驱动结果集;
3、 接着Oracle会遍历S,读取S中的每一条记录,并对S中的每一条记录按照该记录在表T1中的连接列做哈希运算,这个哈希运算会使用两个内置哈希函数,这两个哈希函数会同时对该连接列计算哈希值,我们把这两个内置哈希函数分别记为hash_func_1和hash_func_2,它们所计算出来的哈希值分别记为hash_value_1和hash_value_2;
4、 然后Oracle会按照hash_value_1的值把相应的S中的对应记录存储在不同Hash Partition的不同Hash Bucket里,同时和该记录存储在一起的还有该记录用hash_func_2计算出来的hash_value_2的值。注意,存储在Hash Bucket里的记录并不是目标表的完整行记录,而是只需要存储位于目标SQL中的跟目标表相关的查询列和连接列就足够了;我们把S所对应的每一个Hash Partition记为Si;
5、 在构建Si的同时,Oracle会构建一个位图(BITMAP),这个位图用来标记Si所包含的每一个Hash Bucket是否有记录(即记录数是否大于0);
6、 如果S的数据量很大,那么在构建S所对应的Hash Table时,就可能会出现PGA的工作区(WORK AREA)被填满的情况,这时候Oracle会把工作区中现有的Hash Partition中包含记录数最多的Hash Partition写到磁盘上(TEMP表空间);接着Oracle会继续构建S所对应的Hash Table,在继续构建的过程中,如果工作区又满了,则Oracle会继续重复上述挑选包含记录数最多的Hash Partition并写回到磁盘上的动作;如果要构建的记录所对应的Hash Partition已经事先被Oracle写回到了磁盘上,则此时Oracle就会去磁盘上更新该Hash Partition,即会把该条记录和hash_value_2直接加到这个已经位于磁盘上的Hash Partition的相应Hash Bucket中;注意,极端情况下可能会出现只有某个Hash Partition的部分记录还在内存中,该Hash Partition的剩余部分和余下的所有Hash Partition都已经被写回到磁盘上;
7、 上述构建S所对应的Hash Table的过程会一直持续下去,直到遍历完S中的所有记录为止;
8、 接着,Oracle会对所有的Si按照它们所包含的记录数来排序,然后Oracle会把这些已经排好序的Hash Partition按顺序依次、并且尽可能的全部放到内存中(PGA的工作区),当然,如果实在放不下的话,放不下的那部分Hash Partition还是会位于磁盘上。我认为这个按照Si的记录数来排序的动作不是必须要做的,因为这个排序动作的根本目的就是为了尽可能多的把那些记录数较小的Hash Partition保留在内存中,而将那些已经被写回到磁盘上、记录数较大且现有内存已经放不下的Hash Partition保留在磁盘上,显然,如果所有的Si本来就都在内存中,也没发生过将Si写回到磁盘的操作,那这里根本就不需要排序了。
9、 至此Oracle已经处理完S,现在可以来开始处理B了;
10、 Oracle会遍历B,读取B中的每一条记录,并对B中的每一条记录按照该记录在表T2中的连接列做哈希运算,这个哈希运算和步骤3中的哈希运算是一模一样的,即这个哈希运算还是会用步骤3中的hash_func_1和hash_func_2,并且也会计算出两个哈希值hash_value_1和hash_value_2;接着Oracle会按照该记录所对应的哈希值hash_value_1去Si里找匹配的Hash Bucket;如果能找到匹配的Hash Bucket,则Oracle还会遍历该Hash Bucket中的每一条记录,并会校验存储于该Hash Bucket中的每一条记录的连接列,看是否是真的匹配(即这里要校验S和B中的匹配记录所对应的连接列是否真的相等,因为对于Hash运算而言,不同的值经过哈希运算后的结果可能是一样的),如果是真的匹配,则上述hash_value_1所对应B中的记录的位于目标SQL中的查询列和该Hash Bucket中的匹配记录便会组合起来,一起作为满足目标SQL连接条件的记录返回;如果找不到匹配的Hash Bucket,则Oracle就会去访问步骤5中构建的位图,如果位图显示该Hash Bucket在Si中对应的记录数大于0,则说明该Hash Bucket虽然不在内存中,但它已经被写回到了磁盘上,则此时Oracle就会按照上述hash_value_1的值把相应B中的对应记录也以Hash Partition的方式写回到磁盘上,同时和该记录存储在一起的还有该记录用hash_func_2计算出来的hash_value_2的值;如果位图显示该Hash Bucket在Si中对应的记录数等于0,则Oracle就不用把上述hash_value_1所对应B中的记录写回到磁盘上了,因为这条记录必然不满足目标SQL的连接条件;这个根据位图来决定是否将上述hash_value_1所对应B中的记录写回到磁盘的动作就是所谓的“位图过滤”;我们把B所对应的每一个Hash Partition记为Bj;
11、 上述去Si中查找匹配Hash Bucket和构建Bj的过程会一直持续下去,直到遍历完B中的所有记录为止;
12、 至此Oracle已经处理完所有位于内存中的Si和对应的Bj,现在只剩下位于磁盘上的Si和Bj还未处理;
13、 因为在构建Si和Bj时用的是同样的哈希函数hash_func_1和hash_func_2,所以Oracle在处理位于磁盘上的Si和Bj的时候可以放心的配对处理,即只有对应Hash Partition Number值相同的Si和Bj才可能会产生满足连接条件的记录;这里我们用Sn和Bn来表示位于磁盘上且对应Hash Partition Number值相同的Si和Bj;
14、 对于每一对儿Sn和Bn,它们之中记录数较少的会被当作驱动结果集,然后Oracle会用这个驱动结果集的Hash Bucket里记录的hash_value_2来构建新的Hash Table,另外一个记录数较大的会被当作被驱动结果集,然后Oracle会用这个被驱动结果集的Hash Bucket里记录的hash_value_2去上述构建的新Hash Table中找匹配记录;注意,对每一对儿Sn和Bn而言,Oracle始终会选择它们中记录数较少的来作为驱动结果集,所以每一对儿Sn和Bn的驱动结果集都可能会发生变化,这就是所谓的“动态角色互换”;
15、 步骤14中如果存在匹配记录,则该匹配记录也会作为满足目标SQL连接条件的记录返回;
16、 上述处理Sn和Bn的过程会一直持续下去,直到遍历完所有的Sn和Bn为止。
对于哈希连接的优缺点及适用场景,我们有如下总结:
Ÿ 哈希连接不一定会排序,或者说大多数情况下都不需要排序;
Ÿ 哈希连接的驱动表所对应的连接列的可选择性应尽可能的好,因为这个可选择性会影响对应Hash Bucket中的记录数,而Hash Bucket中的记录数又会直接影响从该Hash Bucket中查找匹配记录的效率;如果一个Hash Bucket里所包含的记录数过多,则可能会严重降低所对应哈希连接的执行效率,此时典型的表现就是该哈希连接执行了很长时间都没有结束,数据库所在database server上的CPU占用率很高,但目标SQL所消耗的逻辑读却很低,因为此时大部分时间都耗费在了遍历上述Hash Bucket里的所有记录上,而遍历Hash Bucket里记录这个动作是发生在PGA的工作区里,所以不耗费逻辑读;
Ÿ 哈希连接只适用于CBO、它也只能用于等值连接条件(即使是哈希反连接,Oracle实际上也是将其转换成了等价的等值连接);
Ÿ 哈希连接很适合于一个小表和大表之间的表连接,特别是在小表的连接列的可选择性非常好的情况下,这时候哈希连接的执行时间就可以近似看作是和全表扫描那个大表所耗费的时间相当;
Ÿ 当两个表做哈希连接时,如果这两个表在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集中数据量较小的那个结果集所对应的Hash Table能够完全被容纳在内存中时(PGA的工作区),则此时的哈希连接的执行效率会非常高。
我们可以借助于10104事件所产生的trace文件来观察目标SQL在做哈希连接时的大致过程和一些统计信息(比如用了多少个Hash Partition、多个少Hash Bucket以及各个Hash Bucket都分别有多少条记录等),10104事件在我们实际诊断哈希连接的性能问题时非常有用。
使用10104事件观察目标SQL做哈希连接的具体过程为:
oradebug setmypid
oradebug event 10104 trace name context forever, level 1
set autotrace traceonly
实际执行目标SQL(必须要实际执行该SQL,不能用explain plan for)
oradebug tracefile_name
一个典型的10104事件所产生的trace文件内容为如下所示:
kxhfInit(): enter
kxhfInit(): exit
*** RowSrcId: 1 HASH JOIN STATISTICS (INITIALIZATION) ***
Join Type: INNER join
Original hash-area size: 3642760
Memory for slot table: 2826240
Calculated overhead for partitions and row/slot managers: 816520
Hash-join fanout: 8
Number of partitions: 8
Number of slots: 23
Multiblock IO: 15
Block size(KB): 8
Cluster (slot) size(KB): 120
Minimum number of bytes per block: 8160
Bit vector memory allocation(KB): 128
Per partition bit vector length(KB): 16
……省略显示部分内容
Slot table resized: old=23 wanted=12 got=12 unload=0
*** RowSrcId: 1 HASH JOIN RESIZE BUILD (PHASE 1) ***
Total number of partitions: 8
Number of partitions which could fit in memory: 8
Number of partitions left in memory: 8
Total number of slots in in-memory partitions: 8
kxhfResize(enter): resize to 14 slots (numAlloc=8, max=12)
kxhfResize(exit): resized to 14 slots (numAlloc=8, max=14)
set work area size to: 2215K (14 slots)
*** RowSrcId: 1 HASH JOIN BUILD HASH TABLE (PHASE 1) ***
Total number of partitions: 8
Number of partitions left in memory: 8
Total number of rows in in-memory partitions: 1000
(used as preliminary number of buckets in hash table)
Estimated max # of build rows that can fit in avail memory: 79800
### Partition Distribution ###
Partition:0 rows:120 clusters:1 slots:1 kept=1
Partition:1 rows:122 clusters:1 slots:1 kept=1
……省略显示部分内容
Partition:6 rows:118 clusters:1 slots:1 kept=1
Partition:7 rows:137 clusters:1 slots:1 kept=1
*** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***
Revised number of hash buckets (after flushing): 1000
Allocating new hash table.
*** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***
Requested size of hash table: 256
Actual size of hash table: 256
Number of buckets: 2048
Match bit vector allocated: FALSE
*** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***
Total number of rows (may have changed): 1000
Number of in-memory partitions (may have changed): 8
Final number of hash buckets: 2048
Size (in bytes) of hash table: 8192
qerhjBuildHashTable(): done hash-table on partition=7, index=0 last_slot#=3 rows=137 total_rows=137
qerhjBuildHashTable(): done hash-table on partition=6, index=1 last_slot#=4 rows=118 total_rows=255
……省略显示部分内容
qerhjBuildHashTable(): done hash-table on partition=1, index=6 last_slot#=2 rows=122 total_rows=880
qerhjBuildHashTable(): done hash-table on partition=0, index=7 last_slot#=5 rows=120 total_rows=1000
kxhfIterate(end_iterate): numAlloc=8, maxSlots=14
*** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***
### Hash table ###
# NOTE: The calculated number of rows in non-empty buckets may be smaller
# than the true number.
Number of buckets with 0 rows: 1249
Number of buckets with 1 rows: 626
Number of buckets with 2 rows: 149
Number of buckets with 3 rows: 21
Number of buckets with 4 rows: 3
Number of buckets with 5 rows: 0
……省略显示部分内容
Number of buckets with between 90 and 99 rows: 0
Number of buckets with 100 or more rows: 0
### Hash table overall statistics ###
Total buckets: 2048 Empty buckets: 1249 Non-empty buckets: 799
Total number of rows: 1000
Maximum number of rows in a bucket: 4
Average number of rows in non-empty buckets: 1.251564
Disabled bitmap filtering: filtered rows=0 minimum required=50 out of=1000
qerhjFetch: max probe row length (mpl=0)
*** RowSrcId: 1, qerhjFreeSpace(): free hash-join memory
kxhfRemoveChunk: remove chunk 0 from slot table
注意到上述显示内容中我粗体标出的部分,如“Number of in-memory partitions (may have changed):
“Oracle会遍历S,读取S中的每一条记录,并对S中的每一条记录按照该记录在表T1中的连接列做哈希运算”
不明白S和T1的关系是什么? 我理解S是T1的一个子集.
他们之间的连接列是什么?如果S 和 T1 都有,S.a 和T1.a 那么他们的连接列就是a? 针对a字段做哈希运算?f1(a) f2(a) ?
不知道我理解是否准确。
当目标SQL中有额外的对表T1的限制条件时,S就是T1的一个子集,当没有额外的限制条件时,S就是T1本身。比如表T1和T2的连接条件是where T1.a = T2.b,这里在T1中的连接列就是a。这里的哈希运算就是针对列a来做的,也就是你评论里提到的f1(a)和f2(a)
多谢解惑
“哈希连接很适合于一个小表和大表之间的表连接,特别是在小表的连接列的可选择性非常好的情况下,这时候哈希连接的执行时间就可以近似看作是和全表扫描那个大表所耗费的时间相当”
这种情况,是不是Nest Loop效率更高呢,小表做驱动,大表关联字段上有索引。
即使大表关联字段上有索引,那是否比哈希连接的效率高也是不一定的,这个取决于大表关联字段的可选择性,如果这个可选择性非常好,那此时走嵌套循环连接的执行效率是会比走哈希连接要好,但你提到的这种情况根本就不是哈希连接的适用场景。
“这个取决于大表关联字段的可选择性”,这个确实非常重要
兄弟你的书时候出版呀 呵呵 等着看呢 呵呵
我已经写了811页了,只剩下了不到一章的内容。抱歉一拖再拖,主要是因为难度太大再加上我对自己要求又很高
相信这一定会成为经典之作,期待中,感谢你的辛苦 呵呵
两个疑问
1 构造hash table时不需要对候选结果集做distinct处理么?
2 为b构造hash table时会不会出现hash_area_size不够大导致部分partition存入temp的情况?如果是,那么位于temp的partition在第10步时会被读取与si匹配么,还是说留到第12步以后进行
谢谢
1、不需要
2、不会
崔老师,为什么要进行两次函数运算得到hash_value_1 hash_value_2呢,他们分别是用来做什么的呢;
bucket里面的记录为什么会出现空啊,hash table不是已经在内存里了么,那他里面的记录也都在内存里了呀?
之所以用两个hash函数是为了使各个hash bucket里的值分布的更加均匀。hash bucket的数量一开始就定好了,里面的记录数当然有可能会为空。
正在拜读您的大作,有个疑问。
对于第四步,计算的hash value存储在不同Hash Partition的不同Hash Bucket里,如果计算的值和以前重复,是不是会覆盖掉以前Hash Bucket里的记录呢 ?如果是这样,是不是也解释了hash连接非常适合小表连接列可选择性好的情况呢?如果不是,怎么理解可选择性好这句话呢?
不会覆盖。
崔老师,您好,对于你上文第3点提到的“接着Oracle会遍历S,读取S中的每一条记录,并对S中的每一条记录按照该记录在表T1中的连接列做哈希运算”不明白,不明白为什么S还要去和T1根据连接列做hash运算?我们最后要得的结果集肯定不包括T1结果集S之外的记录了啊,如果这样假设T1有1000万条记录,S结果集只有10万记录,那这样hash会高效吗?
你是啥意思啊?我没明白。我这里的意思是说——假设要执行的SQL是select t1.col4,t2.col5 from t1,t2 where t1.col1=t2.col2 and t1.col3=1 and t2.col4=2;那么这里的S就是对t1施加了条件t1.col3=1后的结果集,然后Oracle会对这个结果集按照连接列t1.col1来做哈希运算。
崔老师,您好,对于hash有些疑问,麻烦有空帮解答下,谢谢。
1.use_hash会有use_nl那种传值的概念吗?
2.你文中第10点的“接着Oracle会按照该记录所对应的哈希值hash_value_1去Si里找匹配的Hash Bucket;”以及第11点“上述去Si中查找匹配Hash Bucket和构建Bj的过程会一直持续下去,直到遍历完B中的所有记录为止”都说的是B去S里找匹配的,S是驱动表,不应该是S去B里找匹配的吗?
1、没有
2、hash连接里的驱动表的概念和通常意义上(如嵌套循环连接)的驱动表的概念不完全相同,你可以把hash连接里的驱动表理解为Oracle先处理哪个表的数据那么这个表就是hash连接里的驱动表
谢谢崔老师的回复。 :)
对于1点中,use_hash没有传值概念(即驱动表传值给被驱动表)
,那么谓词推入,子查询push这些转换只能用于use_nl?
还是说我对谓词推入,子查询push理解不对?
是这样的,我认为use_hash没有传值的概念,因为hash连接一般走的都是全表扫描。对于全表扫描,谓词推入没啥意义——你推入也好,不推入也好,反正我走的是全表扫描,你就算谓词推入了,对全表扫描而言也不能提高效率,还是要扫所有数据的