SQL调优之五：哈希连接（HashJoins）
哈希连接
数据库⼀般使⽤hash join来连接更⼤的数据集。
优化器会使⽤两个数据集中⽐较⼩的那个，在连接列上创建⼀个摆放在内存⾥的hash表，然后使⽤唯⼀性的hash函数来指定每⼀⾏在hash 表⾥的存放位置。
然后数据库会扫描⼤的那个数据集，探测hash表，到匹配的⾏。
优化器什么时候会考虑使⽤hash join?
⼀般来说，在需要等式连接数据量更⼤的两个数据集的时候，Oracle会考虑使⽤hash join(或者⼀个⼩表但是很⼤⽐例的数据需要被连接的时候)。
在做哈希连接的时候，如果较⼩的数据集能够完全放到内存⾥⾯，这个时候它是最⾼效的（低成本⾼效益）。在这个情况下，它成本主要是在两个数据集之间传递的单次读。
因为hash表是存在PGA中的，数据库可以不需要加闩锁直接访问数据，这样⼦能够避免重复性地加闩锁再从缓存读数据块，从⽽减少逻辑I/O。
如果数据集⽆法整个放到内存⾥⾯，那么数据库就会对数据集进⾏分区，然后⼀个分区⼀个分区进⾏连接。这种情况会使⽤很多内存排序区域，以及temporary表空间的⼤量I/O。
尽管如此，hash join仍然可以是最⾼成本效益⽐的，尤其是当数据库使⽤并⾏查询服务的时候。
哈希连接怎么⼯作的？
⼀个哈希算法会获取输⼊的数据集，然后通过⼀个hash函数来⽣成⼀个在1到n之间的hash值，n是hash表的⼤⼩。在⼀次哈希连接中，输⼊的值是连接列的值，输出的值则是在⼀个数组阵列⾥⾯的索引(插槽)，也就是哈希表。
哈希表
为了描述hash表，让我们假设在⼀次deparments表和employees表的连接中，哈希表是hr.departments，然后连接列是department_id。deparments表的前5⾏是：
数据库会使⽤哈希函数，对每⼀个department_id进⾏哈希运算，⽣成⼀个哈希值。
在这次描述⾥，hash表有5个插槽（可以更多或者少），也就是n=5，hash值得范围是1到5。
所以哈希函数⽣成得哈希值如下：
f(10) = 4
f(20) = 1
f(30) = 4
f(40) = 2
f(50) = 5
你可能会注意到，10跟30的哈希值是⼀样的，这个叫做哈希冲突。在这种情况下，数据库会把10和30的记录给放到同⼀个插槽（4）⾥⾯，⽤⼀个链接列表把他们放在⼀起。
理论上来说，hash表看起来会是：
1 20,Marketing,201,1800
2 40,Human Resources,203,2400
3
4 10,Administration,200,1700 -> 30,Purchasing,114,1700
5 50,Shipping,121,1500
哈希链接：基础步骤
优化器使⽤⽐较⼩的数据集在内存中基于连接列⽣成⼀个哈希表，然后扫描较⼤的表，来到匹配的⾏。
基础步骤如下：
1，数据库对⽐较⼩的数据集进⾏⼀次全扫描，然后在连接列上的每⼀⾏应⽤哈希函数，在PGA⾥⾯创建⼀个哈希表。
伪代码如下：
FOR small_table_row IN (SELECT * FROM small_table)
LOOP
  slot_number := HASH(small_table_row.join_key);
  INSERT_HASH_TABLE(slot_number,small_table_row);
END LOOP;
2，数据库探测第⼆个数据集，也叫做探测表，使⽤的是最低成本访问机制。
通常来说，数据库会对两个数据集进⾏⼀次全扫描，⽆论是⼤的还是⼩的数据集。它的伪代码如下：
FOR large_table_row IN (SELECT * FROM large_table)  --针对⼤表⾥的每⼀⾏，循环
LOOP
  slot_number := HASH(large_table_row.join_key); --对⼤表的⾏进⾏哈希运算，获得slot值
  small_table_row = LOOKUP_HASH_TABLE(slot_number,large_table_row.join_key); -- 根据连接条件，到对应的slot⾥⾯查是否有匹配的⼩表的⾏
  IF small_table_row FOUND --如果到匹配的
  THEN
    output small_table_row + large_table_row; --输出⼩表的⾏
  END IF;
END LOOP;
对于从⼤表返回的每⼀⾏数据，数据库会做以下操作：
a. 在连接列，应⽤相同的哈希函数，然后计算出在哈希表⾥对应的slot值（插槽）。⽐如说，去探索哈希表⾥有没有department ID等于30的，数据库会对30应⽤哈希函数，计算出来的插槽的值为4.
b. 探查哈希表，看看插槽⾥是否有数据，如果插槽⾥没有数据，那么数据库就会循环⼤表⾥的下⼀⾏，如果插槽⾥有数据，数据库就会进⾏下⼀步。
c. 检查连接列，看看是不是有匹配的数据。如果有匹配到的，那么数据库就会返回这些⾏，或者把这些⾏传递到执⾏计划的下⼀步，然后继续处理⼤表的下⼀⾏。
如果插槽⾥⾯有多⾏数据，那么数据库会沿着链接列表往下查，直到到匹配的数据。
看看下⾯这个执⾏计划，order_items表的估算返回⾏数是665，是orders表105的6倍多，所以数据库会⽤orders表来建哈希表。在执⾏计划⾥⾯，先执⾏的那⼀步，在这⾥是第2步，是⽤来构建哈希表的数据集，⽽下⼀个表，则是来探测哈希表的。
当哈希表⽆法整个存到PGA⾥⾯的时候，哈希连接是怎么做的？
当哈希表⽆法整个存到PGA⾥⾯的时候，数据库会使⽤临时表空间来存储哈希表的⼀部分（也就是分区）以及有些时候⼤表⽤来探查哈希表的⼀部分（分区）。
其基本步骤是：
1，数据库会对较⼩的数据集做⼀次全扫描，然后在PGA以及磁盘上创建哈希bucket（桶）的数组。
当PGA哈希区域满了的时候，数据库会到当前哈希表⾥最⼤的部分，把它写到磁盘上的临时空间，相当于把现有最占PGA的那个bucket给写到了磁盘上，然后后续属于这个bucket的数据，都会直接写到磁盘上。如果PGA后来⼜满了，则会重复这个过程。因此，哈希表的⼀部分在PGA⾥⾯，⼀部分在磁盘上。
2，数据库在读取另⼀个数据集的时候会做⼀次重要传递：
针对每⼀⾏：
a，应⽤相同的哈希函数，计算出相关的哈希bucket的数值
b，探查哈希表，确定这⼀⾏在不在内存⾥的hash bucket⾥⾯
如果哈希值指向了内存⾥⾯的⾏，那么数据库就完成了这⼀次连接并返回这⼀⾏。如果哈希值指向的值是在磁盘上的分区⾥，那么，数据库会使⽤同样的分区⽅案，把这⼀⾏存到临时表空间⾥
c，数据库会⼀个⼀个地读取在磁盘上的临时空间
d，数据库会把每⼀个分区⾥的数据，和在磁盘上临时分区⾥⾯的数据进⾏连接
如果对更详细的内容感兴趣，可以看⼀下这个link
稍微总结⼀下这个link的⼏个补充：
1，⼀个Hash Table是由多个Hash Partition所组成，⽽⼀个Hash Partition⼜是由多个Hash Bucket所组成
2，在做哈希计算的时候，会⽣成两个哈希值，第⼆个哈希值在将磁盘上的分区写回内存的时候被⽤来构建哈希表
3，在创建哈希分区的时候，会同时创建⼀个位图，这个位图⽤来标记bucket是否有记录
3，在构建完哈希分区后，Oracle会对这些哈希分区进⾏排序，尽可能保证更多的分区在内存⾥
4，当在探查哈希表的时候没有到需要的bucket，那么数据库会去位图⾥查，如果位图显⽰bucket⾥⾯有数据，那么数据库就会同样⽤哈希函数在磁盘上创建同样的哈希分区，然后把数据和第⼆个哈希值放进去。
如果位图上显⽰这个buket没有数据，那么数据库就不需要再去做接下来的操作，直接过滤掉这部分，这就是位图过滤
5，对于在磁盘上的哈希分区，数据库会将第⼀个数据集和第⼆个数据集的相同分区进⾏连接，选择两者之间较⼩的数据集根据第⼆个哈希值，到内存⾥⾯构建新的哈希表。因为哪个数据集做哈希表不是固定的，所以这也叫“动态⾓⾊互换”
6，哈希连接不⼀定会排序，或者说绝⼤多数情况下不会排序
7，哈希连接⽤来构建哈希表的选择列的选择性要尽可能的好，因为这个选择性会决定哈希bucket⾥⾯的记录数，⽽bucket⾥⾯的记录数数量⼜会影响哈希遍历的效率。如果哈希bucket⾥⾯的数据太多，可能会严重影响哈希连接的效率。此时典型的表现就是，哈希连接执⾏了很长时间没有结束，然后数据库的CPU消耗很⾼，但是逻辑读却很低，因为此时⼤部分时间都消耗在了遍历哈希bucket上，⽽哈希表⼜是在PGA中，所以逻辑读很低
8，哈希连接只适⽤于等式连接，就算是反式连接也会被先转换成等式连接
种子哈希转换链接
9，哈希连接很适合于⼀个⼩表和⼀个⼤表之间的连接，特别是⼩表的可选择性很好的情况下，这个时候哈希连接的可近似看作是和全扫⼤表的时间相当
10，如果基于⼩的数据集构建的哈希表能够整个放⼊到PGA中，执⾏效率会很好
哈希连接的控制
使⽤USE_HASH hint来指定优化器使⽤哈希连接
适⽤10104事件观察哈希连接的过程：
oradebug setmypid
oradebug event 10104 trace name context forever, level 1
set autotrace traceonly
实际执⾏⽬标SQL（必须要实际执⾏该SQL，不能⽤explain plan for）
oradebug tracefile_name
例⼦：
“Number of in-memory partitions (may have changed): 8”、“Final number of hash buckets: 2048”、“Total buckets: 2048 Empty buckets: 1249 Non-empty buckets: 799”、“Total number of rows: 1000”、“Maximum number of rows in a bucket: 4”、“Disabled bitmap filtering: filtered rows=0 minimum required=50 out of=1000”等，这说明上述哈希连接驱动结果集的记录数为1000，共有8个Hash Partition、2048
个Hash Bucket，这2048个Hash Bucket中有1249个是空的（即没有记录）、799个有记录，包含记录数最多的⼀个Hash Bucket所含记录的数量为4以及上述哈希连接并没有启⽤位图过滤
哈希连接⼀些相关的参数：
hash_multiblock_io_count
hash_area_size

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。