精华内容
下载资源
问答
  • 哈希原理

    千次阅读 2019-07-08 18:05:07
    哈希表是最常用的数据结构之一,对于其用法,大家都非常熟悉,这里详细探讨一下其原理哈希表的底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后...

    哈希表是最常用的数据结构之一,对于其用法,大家都非常熟悉,这里详细探讨一下其原理。哈希表的底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后和数组容量取模,得到在数组中的位置后再插入。取值时,先对指定的键求Hash值,再和容量取模得到底层数组中对应的位置,如果指定的键值与存贮的键相匹配,则返回该键值对,如果不匹配,则表示哈希表中没有对应的键值对。这样做的好处是在查找、插入、删除等操作可以做到O(1)O(1),最坏的情况是O(n)O(n),当然这种是最极端的情况,极少遇到。
    image
    不管哪门语言,实现一个HashMap的过程均可分为三大步骤:

    • 实现一个Hash函数
    • 合理解决Hash冲突
    • 实现HashMap的操作方法

    Hash函数

    Hash函数非常重要,一个好的Hash函数不仅性能优越,而且还会让存储于底层数组中的值分配的更加均匀,减少冲突发生。之所以是减少冲突,是因为取Hash的过程,实际上是将输入键(定义域)映射到一个非常小的空间中,所以冲突是无法避免的,能做的只是减少Hash碰撞发生的概率。具体实现时,哈希函数算法可能不同,在Rust及很多语言的实现中,默认选择SipHash哈希算法。

    默认情况下,Rust的HashMap使用SipHash哈希算法,其旨在防止哈希表碰撞攻击,同时在各种工作负载上提供合理的性能。虽然 SipHash 在许多情况下表现出竞争优势,但其中一个比其它哈希算法要慢的情况是使用短键,例如整数。这就是为什么 Rust 程序员经常观察到 HashMap 表现不佳的原因。在这些情况下,经常推荐 FNV 哈希,但请注意,
    它不具备与 SipHash 相同的防碰撞性。

    影响Hash碰撞(冲突)发生的除了Hash函数本身意外,底层数组容量也是一个重要原因。很明显,极端情况下如果数组容量为1,哪必然发生碰撞,如果数组容量无限大,哪碰撞的概率非常之低。所以,哈希碰撞还取决于负载因子。负载因子是存储的键值对数目与数组容量的比值,比如数组容量100,当前存贮了90个键值对,负载因子为0.9。负载因子决定了哈希表什么时候扩容,如果负载因子的值太大,说明存储的键值对接近容量,增加碰撞的风险,如果值太小,则浪费空间。

    所以,既然冲突无法避免,就必须要有解决Hash冲突的机制方法。

    处理冲突的几种方法

    主要有四类处理冲突的方法:

    • 外部拉链法(常用)
    • 开放定址法(常用)
    • 公共溢出区(不常用)
    • 再Hash法(不常用)

    外部拉链法

    主要思想是基于数组和链表的组合来解决冲突,桶(Bucket)中不直接存储键值对,每个Bucket都链接一个链表,当发生冲突时,将冲突的键值对插入链表中。外部拉链法的有点在于方法简单,非同义词之间也不会产生聚集现象(相比于开放定址法),并且其空间结构是动态申请的,所以比较适合无法确定表长的情况:缺点是链表指针需要额外的空间,遇到碰撞拒绝服务时会退化为单链表。

    同义词:两个元素通过Hash函数得到了相同的索引地址,这两个元素就叫做同义词。

    下面是外部拉链法的两种实现方法,主要区别在于桶(Bucket)中是否存储数据。
    image

    image

    开放定址法

    主要思想是发生冲突时,直接去寻找下一个空的地址,只要底层的表足够大,就总能找到空的地址。这个寻找下一个地址的行为,叫做探测。 hashi=(hash(key)+di)  mod  mi=1,2...k (km1){hash_{i}=(hash(key)+d_{i})\,{\bmod {\,}}m}, i=1,2...k\,(k\leq m-1)`,其中hash(key)hash(key)为哈希函数,mm为哈希表长,did_{i}为增量序列,ii为已发生冲突的次数。根据增量序列取法的不同有多种探测方法:

    • di=1,2,3...(m1)d_{i}=1,2,3...(m-1)称为线性探测(Linear Probing);即 di=id_{i}=i,或者为其他线性函数。相当于逐个探测存放地址的表,直到查找到一个空单元,把散列地址存放在该空单元。
    • di=±12,±22,±32...±k2(km/2)d_{i}=\pm 1^{2},\pm 2^{2},\pm 3^{2}...\pm k^{2} (k\leq m/2)称为平方探测(Quadratic Probing)。相对线性探测,相当于发生冲突时探测间隔$ d_{i}=i^{2}$个单元的位置是否为空,如果为空,将地址存放进去。
    • di=d_{i}=伪随机数序列,称为伪随机探测。

    下图为线性探测:

    image

    公共溢出区

    主要思想是建立一个独立的公共区,把冲突的键值对都放在其中。不常用,这里不再细述。

    再Hash法

    主要思想是有冲突时,换另外一个Hash函数来算Hash值。不常用,这里不再细述。

    实现哈希表的操作方法

    主要是:

    • insert
    • remove
    • get
    • contains_key
    • …等等…

    其中最重要的是插入、查找、删除这三个操作。

    参考文档Hash table

    关注微信公众号,推送常用数据结构、TCP/IP、分布式、后端开发等技术分享,共同学习进步!

    展开全文
  • Oracle 哈希连接原理

    2015-09-26 02:21:00
    哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。 在Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接...

    《基于Oracle的sql优化》里关于哈希连接的原理介绍如下:

    哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。

    Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接方法都有其明显缺陷。对于排序合并连接,如果两个表在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集很大且需要排序的话,则这种情况下的排序合并连接的执行效率一定是很差的;而对于嵌套循环连接,如果驱动表所对应的驱动结果集的记录数很大,即便在被驱动表的连接列上存在索引,此时使用嵌套循环连接的执行效率也同样会很差。

    为了解决排序合并连接和嵌套循环连接在上述情形下执行效率不高的问题,同时也为了给优化器提供一种新的选择,OracleOracle 7.3中引入了哈希连接。从理论上来说,哈希连接的执行效率会比排序合并连接和嵌套循环连接的执行效率要高,当然,实际情况并不总是这样。

    Oracle 10g及其以后的Oracle数据库版本中,优化器(实际上是CBO,因为哈希连接仅适用于CBO)在解析目标SQL时是否考虑哈希连接是受限于隐含参数_HASH_JOIN_ENABLED,而在Oracle10g以前的Oracle数据库版本中,CBO在解析目标SQL时是否考虑哈希连接是受限于参数HASH_JOIN_ENABLED

    _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_SIZEDB_BLOCK_SIZE_HASH_MULTIBLOCK_IO_COUNT的值来决定Hash Partition的数量(Hash Partition是一个逻辑上的概念,所有Hash Partition的集合就被称之为Hash Table,即一个Hash Table是由多个Hash Partition所组成,而一个Hash Partition又是由多个Hash Bucket所组成);

    2  T1T2在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集中数据量较小的那个结果集会被Oracle选为哈希连接的驱动结果集,这里我们假设T1所对应的结果集的数据量相对较小,我们记为ST2所对应的结果集的数据量相对较大,我们记为B;显然这里S是驱动结果集,B是被驱动结果集;

    3  接着Oracle会遍历S,读取S中的每一条记录,并对S中的每一条记录按照该记录在表T1中的连接列做哈希运算,这个哈希运算会使用两个内置哈希函数,这两个哈希函数会同时对该连接列计算哈希值,我们把这两个内置哈希函数分别记为hash_func_1hash_func_2,它们所计算出来的哈希值分别记为hash_value_1hash_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_1hash_func_2,并且也会计算出两个哈希值hash_value_1hash_value_2;接着Oracle会按照该记录所对应的哈希值hash_value_1Si里找匹配的Hash Bucket;如果能找到匹配的Hash Bucket,则Oracle还会遍历该Hash Bucket中的每一条记录,并会校验存储于该Hash Bucket中的每一条记录的连接列,看是否是真的匹配(即这里要校验SB中的匹配记录所对应的连接列是否真的相等,因为对于Hash运算而言,不同的值经过哈希运算后的结果可能是一样的),如果是真的匹配,则上述hash_value_1所对应B中的记录的位于目标SQL中的查询列和该Hash Bucket中的匹配记录便会组合起来,一起作为满足目标SQL连接条件的记录返回;如果找不到匹配的Hash Bucket,则Oracle就会去访问步骤5中构建的位图,如果位图显示该Hash BucketSi中对应的记录数大于0,则说明该Hash Bucket虽然不在内存中,但它已经被写回到了磁盘上,则此时Oracle就会按照上述hash_value_1的值把相应B中的对应记录也以Hash Partition的方式写回到磁盘上,同时和该记录存储在一起的还有该记录用hash_func_2计算出来的hash_value_2的值;如果位图显示该Hash BucketSi中对应的记录数等于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,现在只剩下位于磁盘上的SiBj还未处理;

    13 因为在构建SiBj时用的是同样的哈希函数hash_func_1hash_func_2,所以Oracle在处理位于磁盘上的SiBj的时候可以放心的配对处理,即只有对应Hash Partition Number值相同的SiBj才可能会产生满足连接条件的记录;这里我们用SnBn来表示位于磁盘上且对应Hash Partition Number值相同的SiBj

    14 对于每一对儿SnBn,它们之中记录数较少的会被当作驱动结果集,然后Oracle会用这个驱动结果集的Hash Bucket里记录的hash_value_2来构建新的Hash Table,另外一个记录数较大的会被当作被驱动结果集,然后Oracle会用这个被驱动结果集的Hash Bucket里记录的hash_value_2去上述构建的新Hash Table中找匹配记录;注意,对每一对儿SnBn而言,Oracle始终会选择它们中记录数较少的来作为驱动结果集,所以每一对儿SnBn的驱动结果集都可能会发生变化,这就是所谓的"动态角色互换"

    15 步骤14中如果存在匹配记录,则该匹配记录也会作为满足目标SQL连接条件的记录返回;

    16 上述处理SnBn的过程会一直持续下去,直到遍历完所有的SnBn为止。

       

    对于哈希连接的优缺点及适用场景,我们有如下总结:

         哈希连接不一定会排序,或者说大多数情况下都不需要排序;

         哈希连接的驱动表所对应的连接列的可选择性应尽可能的好,因为这个可选择性会影响对应Hash Bucket中的记录数,而Hash Bucket中的记录数又会直接影响从该Hash Bucket中查找匹配记录的效率;如果一个Hash Bucket里所包含的记录数过多,则可能会严重降低所对应哈希连接的执行效率,此时典型的表现就是该哈希连接执行了很长时间都没有结束,数据库所在database server上的CPU占用率很高,但目标SQL所消耗的逻辑读却很低,因为此时大部分时间都耗费在了遍历上述Hash Bucket里的所有记录上,而遍历Hash Bucket里记录这个动作是发生在PGA的工作区里,所以不耗费逻辑读

         哈希连接只适用于CBO、它也只能用于等值连接条件(即使是哈希反连接,Oracle实际上也是将其转换成了等价的等值连接)

         哈希连接很适合于一个小表和大表之间的表连接,特别是在小表的连接列的可选择性非常好的情况下,这时候哈希连接的执行时间就可以近似看作是和全表扫描那个大表所耗费的时间相当

         当两个表做哈希连接时,如果这两个表在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集中数据量较小的那个结果集所对应的Hash Table能够完全被容纳在内存中时(PGA的工作区),则此时的哈希连接的执行效率会非常高。

     

    对于以上的说明有两点不明:

    1. 对于第四步,计算的hash value存储在不同Hash Partition的不同Hash Bucket里,如果计算的值和以前重复,是不是会覆盖掉以前Hash Bucket里的记录呢 ?如果是这样,是不是也解释了hash连接非常适合小表连接列可选择性好的情况呢?如果不是,怎么理解可选择性好这句话呢?
    2. 位图向量里面记录的到底是什么呢?如果仅仅"用来标记Si所包含的每一个Hash Bucket是否有记录(即记录数是否大于0)",怎么"显示该Hash Bucket在Si中对应的记录数等于0"呢?
    3. Hash计算的两个函数作用是什么呢?

    第一个疑问已在作者博客里询问,第三个问题作者在他博客下面回答了读者的疑问,"之所以用两个hash函数是为了使各个hash bucket里的值分布的更加均匀",另一个函数就是计算hash值了。

    对于第二个问题,在另外一个作者的一篇博客中找到,"在将S表读入内存分区时,oracle即记录连接键的唯一值,构建成所谓的位图向量",可见位图向量记录的是小表S的唯一键值:

    引自:http://blog.163.com/chunlei_cl/blog/static/81843020146253596868/

    原文:

    深入理解Oracle表:三大表连接方式详解之Hash Join的定义,原理,算法,成本,模式和位图

    Hash Join只能用于相等连接,且只能在CBO优化器模式下。相对于nested loop join,hash join更适合处理大型结果集
     Hash Join的执行计划第1个是hash表(build table),第2个探查表(probe table),一般不叫内外表,nested loop才有内外表
     Hash表也就是所谓的内表,探查表所谓的外表
     两者的执行计划形如:
     nested loop
     outer table   --驱动表
     inner table
     
     hash join
      build table  (inner table) --驱动表
      probe table   (outer  table) 
     先看一张图片,大致了解Hash Join的过程:
       

       

      下面详细了解一下Hash Join
     ㈠ Hash join概念
     
     Hash join算法的一个基本思想就是根据小的row sources(称作build input 也就是前文提到的build table,我们记较小的表为S,较大的表为B)
      建立一个可以存在于hash area内存中的hash table
      然后用大的row sources(称作probe input,也就是前文提到的probe table) 来探测前面所建的hash table
      如果hash area内存不够大,hash table就无法完全存放在hash area内存中
      针对这种情况,Oracle在连接键利用一个hash函数将build input和probe input分割成多个不相连的分区
      分别记作Si和Bi,这个阶段叫做分区阶段;然后各自相应的分区,即Si和Bi再做Hash join,这个阶段叫做join阶段 
      如果HASH表太大,无法一次构造在内存中,则分成若干个partition,写入磁盘的temporary segment,则会多一个写的代价,会降低效率
      至于小表的概念,对于 hash join 来说,能容纳在 pga 中的 hash table 都可以叫小表,通常比如:
      pga_aggregate_target   big integer  1073741824
      hash  area size 大体能使用到40多 M ,这样的话通常可能容纳 几十万的记录
      hash area size缺省是2*sort_area_size,我们可以直接修改SORT_AREA_SIZE 的大小,HASH_AREA_SIZE也会跟着改变的
      如果你的workarea_size_policy=auto,那么我们只需设定pga_aggregate_target
      但请记住,这是一个session级别的参数,有时,我们更倾向于把hash_area_size的大小设成驱动表的1.6倍左右
      驱动表仅仅用于nested loop join 和 hash join,但Hash join不需要在驱动表上存在索引,而nested loop join则迫切需求
      一两百万记录的表 join上  千万记录的表,hash join的通常表现非常好
      不过,多与少,大与小,很多时候很难量化,具体情况还得具体分析
      如果在分区后,针对某个分区所建的hash table还是太大的话,oracle就采用nested loop hash join
      所谓的nested-loops hash join就是对部分Si建立hash table,然后读取所有的Bi与所建的hash table做连接
      然后再对剩余的Si建立hash table,再将所有的Bi与所建的hash table做连接,直至所有的Si都连接完了
     
     ㈡ 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是个隐藏参数,在9.0.1以后就不再使用了

    [sql] 

    sys@ORCL> ed 
    Wrote file afiedt.buf 
     
     1 select a.ksppinm name,b.ksppstvl value,a.ksppdesc description 
     2 from x$ksppi a,x$ksppcv b 
     3 where a.indx = b.indx 
     4* and a.ksppinm like '%hash_multiblock_io_count%' 
    sys@ORCL> / 
     
    NAME VALUE DESCRIPTION 
    ------------------------------ ----- ------------------------------------------------------------ 
    _hash_multiblock_io_count 0 number of blocks hash join will read/write at once 


      Oracle采用内部一个hash函数作用于连接键上,将S和B分割成多个分区
      在这里我们假设这个hash函数为求余函数,即Mod(join_column_value,10)
      这样产生十个分区,如下表:
     

       经过这样的分区之后,只需要相应的分区之间做join即可(也就是所谓的partition pairs) 
      如果有一个分区为NULL的话,则相应的分区join即可忽略
      在将S表读入内存分区时,oracle即记录连接键的唯一值,构建成所谓的位图向量
      它需要占hash area内存的5%左右。在这里即为{1,3,4,5,8,10}
      当对B表进行分区时,将每一个连接键上的值与位图向量相比较,如果不在其中,则将其记录丢弃
      在我们这个例子中,B表中以下数据将被丢弃{0,0,2,2,2,2,2,2,9,9,9,9,9}
      这个过程就是位图向量过滤
      当S1,B1做完连接后,接着对Si,Bi进行连接
      这里oracle将比较两个分区,选取小的那个做build input,就是动态角色互换
      这个动态角色互换发生在除第一对分区以外的分区上面

     ㈢ Hash Join算法
     
     第1步:判定小表是否能够全部存放在hash area内存中,如果可以,则做内存hash join。如果不行,转第二步
      第2步:决定fan-out数
     (Number of Partitions) * C<= Favm *M
      其中C为Cluster size,其值为DB_BLOCK_SIZE*HASH_MULTIBLOCK_IO_COUNT
      Favm为hash area内存可以使用的百分比,一般为0.8左右
      M为Hash_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_2的hash值
      第11步:如果所落的分区在内存中,则将前面通过hash_fun_2函数计算所得的hash值与内存中已存在的hash table做连接
     将结果写致磁盘上。如果所落的分区不在内存中,则将相应的值与表S相应的分区放在一起
      第12步:继续读取表B,重复第9步,直至表B读取完毕  
      第13步:读取相应的(Si,Bi)做hash连接。在这里会发生动态角色互换
      第14步:如果分区过后,最小的分区也比内存大,则发生nested-loop hash join  
     
     ㈣ Hash Join的成本
     
      ⑴ In-Memory 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)
     
      ⑵ On-Disk Hash Join
      根据上述的步骤描述,我们可以看出:
      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 Join的过程
     
     一次完整的hash join如下:
     1  计算小表的分区(bucket)数--Hash分桶
      决定hash join的一个重要因素是小表的分区(bucket)数
      这个数字由hash_area_size、hash_multiblock_io_count和db_block_size参数共同决定
      Oracle会保留hash area的20%来存储分区的头信息、hash位图信息和hash表
      因此,这个数字的计算公式是:
      Bucket数=0.8*hash_area_size/(hash_multiblock_io_count*db_block_size)
     
     2  Hash计算
      读取小表数据(简称为R),并对每一条数据根据hash算法进行计算
      Oracle采用两种hash算法进行计算,计算出能达到最快速度的hash值(第一hash值和第二hash值)
      而关于这些分区的全部hash值(第一hash值)就成为hash表
     
     3  存放数据到hash内存中
      将经过hash算法计算的数据,根据各个bucket的hash值(第一hash值)分别放入相应的bucket中
      第二hash值就存放在各条记录中
     
     4  创建hash位图
      与此同时,也创建了一个关于这两个hash值映射关系的hash位图
     
     5  超出内存大小部分被移到磁盘
      如果hash area被占满,那最大一个分区就会被写到磁盘(临时表空间)上去
      任何需要写入到磁盘分区上的记录都会导致磁盘分区被更新
      这样的话,就会严重影响性能,因此一定要尽量避免这种情况
      2-5一直持续到整个表的数据读取完毕
     
     6  对分区排序
     为了能充分利用内存,尽量存储更多的分区,Oracle会按照各个分区的大小将他们在内存中排序
     
     7  读取大表数据,进行hash匹配
      接下来就开始读取大表(简称S)中的数据
      按顺序每读取一条记录,计算它的hash值,并检查是否与内存中的分区的hash值一致
      如果是,返回join数据
      如果内存中的分区没有符合的,就将S中的数据写入到一个新的分区中,这个分区也采用与计算R一样的算法计算出hash值
      也就是说这些S中的数据产生的新的分区数应该和R的分区集的分区数一样。这些新的分区被存储在磁盘(临时表空间)上
     
     8  完全大表全部数据的读取
      一直按照7进行,直到大表中的所有数据的读取完毕
     
     9  处理没有join的数据
      这个时候就产生了一大堆join好的数据和从R和S中计算存储在磁盘上的分区
     
     10  二次hash计算
      从R和S的分区集中抽取出最小的一个分区,使用第二种hash函数计算出并在内存中创建hash表
      采用第二种hash函数的原因是为了使数据分布性更好
     
     11  二次hash匹配
      在从另一个数据源(与hash在内存的那个分区所属数据源不同的)中读取分区数据,与内存中的新hash表进行匹配。返回join数据
     
     12  完成全部hash join
      继续按照9-11处理剩余分区,直到全部处理完毕

     ㈥ Hash Join的模式
     Oracle中,Hash Join也有三种模式:optimal,one-pass,multi-pass
     ⑴ optimal
     当驱动结果集生成的hash表全部可以放入PGA的hash area时,称为optimal,大致过程如下:
     ① 先根据驱动表,得到驱动结果集
     ② 在hash area生成hash bulket,并将若干bulket分成一组,成为一个partition,还会生成一个bitmap的列表,每个bulket在上面占一位
     ③ 对结果集的join键做hash运算,将数据分散到相应partition的bulket中
      当运算完成后,如果键值唯一性较高的话,bulket里的数据会比较均匀,也有可能有的桶里面数据会是空的
      这样bitmap上对应的标志位就是0,有数据的桶,标志位会是1  
     ④ 开始扫描第二张表,对jion键做hash运算,确定应该到某个partition的某个bulket去探测
      探测之前,会看这个bulket的bitmap是否会1,如果为0,表示没数据,这行就直接丢弃掉
     ⑤ 如果bitmap为1,则在桶内做精确匹配,判断OK后,返回数据
      这个是最优的hash join,他的成本基本是两张表的full table scan,在加微量的hash运算
      博客开篇的那幅图描述的也就是这种情况

     ⑵ one-pass
      如果进程的pga很小,或者驱动表结果集很大,超过了hash area的大小,会怎么办?
      当然会用到临时表空间,此时oracle的处理方式稍微复杂点需奥注意上面提到的有个partition的概念
      可以这么理解,数据是经过两次hash运算的,先确定你的partition,再确定你的bulket
      假设hash area小于整个hash table,但至少大于一个partition的size,这个时候走的就是one-pass
      当我们生成好hash表后,状况是部分partition留在内存中,其他的partition留在磁盘临时表空间中
      当然也有可能某个partition一半在内存,一半在磁盘,剩下的步骤大致如下:
     ① 扫描第二张表,对join键做hash运算,确定好对应的partition和bulket
     ② 查看bitmap,确定bulket是否有数据,没有则直接丢弃
     ③ 如果有数据,并且这个partition是在内存中的,就进入对应的桶去精确匹配,能匹配上,就返回这行数据,否则丢弃
     ④ 如果partition是在磁盘上的,则将这行数据放入磁盘中暂存起来,保存的形式也是partition,bulket的方式
     ⑤ 当第二张表被扫描完后,剩下的是驱动表和探测表生成的一大堆partition,保留在磁盘上
     ⑥ 由于两边的数据都按照相同的hash算法做了partition和bulket,现在只要成对的比较两边partition数据即可
     并且在比较的时候,oracle也做了优化处理,没有严格的驱动与被驱动关系
     他会在partition对中选较小的一个作为驱动来进行,直到磁盘上所有的partition对都join完
     可以发现,相比optimal,他多出的成本是对于无法放入内存的partition,重新读取了一次,所以称为one-pass
     只要你的内存保证能装下一个partition,oracle都会腾挪空间,每个磁盘partition做到one-pass
     
     ⑶ multi-pass
      这是最复杂,最糟糕的hash join
      此时hash area小到连一个partition也容纳不下,当扫描好驱动表后
      可能只有半个partition留在hash area中,另半个加其他的partition全在磁盘上
      剩下的步骤和one-pass比价类似,不同的是针对partition的处理
      由于驱动表只有半个partition在内存中,探测表对应的partition数据做探测时
      如果匹配不上,这行还不能直接丢弃,需要继续保留到磁盘,和驱动表剩下的半个partition再做join
      这里举例的是内存可以装下半个partition,如果装的更少的话,反复join的次数将更多
      当发生multi-pass时,partition物理读的次数会显著增加

     ㈦ Hash Join的位图
     这个位图包含了每个hash分区是否有有值的信息。它记录了有数据的分区的hash值
     这个位图的最大作用就是,如果probe input中的数据没有与内存中的hash表匹配上
     先查看这个位图,以决定是否将没有匹配的数据写入磁盘
     那些不可能匹配到的数据(即位图上对应的分区没有数据)就不再写入磁盘
     
     ㈧ 小结
      ① 确认小表是驱动表
      ② 确认涉及到的表和连接键分析过了
      ③ 如果在连接键上数据不均匀的话,建议做柱状图
      ④ 如果可以,调大hash_area_size的大小或pga_aggregate_target的值
      ⑤ Hash Join适合于小表与大表连接、返回大型结果集的连接

    转载于:https://www.cnblogs.com/mellowsmile/p/4839902.html

    展开全文
  • hash join (Oracle里的哈希连接原理)2015年09月25日 17:00:28阅读数:2188哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。在Oracle 7.3之前,Oracle数据库中的常用表...
    hash join (Oracle里的哈希连接原理)

    哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。

    在Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接方法都有其明显缺陷。对于排序合并连接,如果两个表在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集很大且需要排序的话,则这种情况下的排序合并连接的执行效率一定是很差的;而对于嵌套循环连接,如果驱动表所对应的驱动结果集的记录数很大,即便在被驱动表的连接列上存在索引,此时使用嵌套循环连接的执行效率也同样会很差。

    为了解决排序合并连接和嵌套循环连接在上述情形下执行效率不高的问题,同时也为了给优化器提供一种新的选择,Oracle在Oracle 7.3中引入了哈希连接。从理论上来说,哈希连接的执行效率会比排序合并连接和嵌套循环连接的执行效率要高,当然,实际情况并不总是这样。

    在Oracle 10g及其以后的Oracle数据库版本中,优化器(实际上是CBO,因为哈希连接仅适用于CBO)在解析目标SQL时是否考虑哈希连接是受限于隐含参数_HASH_JOIN_ENABLED,而在Oracle 10g以前的Oracle数据库版本中,CBO在解析目标SQL时是否考虑哈希连接是受限于参数HASH_JOIN_ENABLED。

    _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的工作区),则此时的哈希连接的执行效率会非常高。

    展开全文
  • 哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。 在Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接...

    哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。

    在Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接方法都有其明显缺陷。对于排序合并连接,如果两个表在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集很大且需要排序的话,则这种情况下的排序合并连接的执行效率一定是很差的;而对于嵌套循环连接,如果驱动表所对应的驱动结果集的记录数很大,即便在被驱动表的连接列上存在索引,此时使用嵌套循环连接的执行效率也同样会很差。

    为了解决排序合并连接和嵌套循环连接在上述情形下执行效率不高的问题,同时也为了给优化器提供一种新的选择,Oracle在Oracle 7.3中引入了哈希连接。从理论上来说,哈希连接的执行效率会比排序合并连接和嵌套循环连接的执行效率要高,当然,实际情况并不总是这样。

    在Oracle 10g及其以后的Oracle数据库版本中,优化器(实际上是CBO,因为哈希连接仅适用于CBO)在解析目标SQL时是否考虑哈希连接是受限于隐含参数_HASH_JOIN_ENABLED,而在Oracle 10g以前的Oracle数据库版本中,CBO在解析目标SQL时是否考虑哈希连接是受限于参数HASH_JOIN_ENABLED。

    _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): 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 JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。 在Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接方法...
  • 哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。 在Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接方法...
  • 讲解哈希函数,哈希表的原理以及常用运算。 是常用的数据结构
  • 哈希表实现原理

    千次阅读 2016-07-14 16:22:37
    1.hash 哈希表作为一种高效的存储结构,可以大大降低查询和存储的时间,其核心...哈希表的底层为一个长度较长的数组,通过将存放的各个元素进行一系列运算而转化为一串hash值,再通过相同的规则与数组的下标进行对应。
  • 什么是 哈希表的原理

    2017-03-22 10:16:37
    1,对对象元素中的关键字(对象中的特有数据),进行哈希算法的运算,并得出一个具体的算法值,这个值 称为哈希值。 2,哈希值就是这个元素的位置。 3,如果哈希值出现冲突,再次判断这个关键字对应的对象是否相同。...
  • 将原hash值的低16位与右移16位的高16位值做异或 ^ 运算,(异或运算可以使二进制0,1分散,而不是像使用 &amp; | 集中全1,全0)3.使得计算后的hash值与原hash值的两部分特征值相关(高低16位)4.再将新hash值...
  • 哈希(hash)计算是常见的数据分布技术,其通过求模运算来计算哈希值,然后据此将数据映射到存储空间中。由于只是采用了简单的求模运算.使得简单哈希计算存在很多不足: 1)增删节点时,更新效率低。当系统中存储节点...
  • 哈希(hash)表原理及作用

    千次阅读 2016-05-27 14:20:21
    哈希表的作用: 优点:(查找速度快) 哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得...哈希运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常
  • 哈希

    2021-01-30 00:27:44
    哈希加快查找的原理 将字符串的key,转成整数,使用整数找到对应的value Hash算法将字符串转成整数,同样的Hash值得 key:value会放到一个集合里面,由于Hash能使得不同的字符串尽量有不同的整数值 将海量的数据,按照...
  • HMAC算法原理 HMAC算法是一种基于密钥的报文完整性的验证方法,其安全性是建立在Hash加密算法基础上的。它要求通信双方共享密钥、约定算法...一句话总结:HMAC是密钥相关的哈希运算消息认证码(Hash-based Message...
  • 哈希算法

    2020-02-03 01:46:28
    我们在利用哈希算法的时候,一般选用unsigned long long 的数据类型,因为该数据类型会在溢出的情况下进行求模运算哈希算法求出来的数字可能会很大),哈希算法为了减小相同的哈希值但是字符串不同的概...
  • 哈希函数和哈希

    2021-01-16 11:00:42
    哈希函数的算法的原理是超纲的内容(底层的实现是位运算),常见的哈希算法有扩展MD5(返回2^ 64)、SHA1(返回2^128)(哈希函数的实现有数千种实现方法) 经典实现中,桶后跟的是链表,Java中的实现,实际上不是O(1...
  • 今天上完离散课,老师上课讲解了线性分组...本文主要目的是通过哈希+位运算成功实现[7:4]线性分组码的纠错功能 首先我们来介绍一下[7:4]线性分组码,前4位是有效数字位,后三位是校验位 首先定义7维向量群 G={x1x2x
  • 哈希

    2019-12-08 12:29:37
    哈希表的底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后和数组容量取模,得到在数组中的位置后再插入。取值时,先对指定的键求Hash值,再和容量...
  • 哈希碰撞

    2020-09-14 16:35:44
    二、哈希碰撞产生原理 假设要将某些元素存放在长度length,则其中某一个元素的key值为k,则其哈希值hash的计算公式为: hash = (k)%length 假设length = 16,那么两个不同元素的key值分别为12和28,那么他们所取得...
  • 3. 哈希表的原理 通过对大数取余运算把一个大数映射到一个较小的范围,若取余结果有冲突则进行处理 4. 两种储存结构 根据对出现冲突时的不同处理方式,把哈希表分为两类:开放寻址法、拉链法 5. 两种模板 (1) 拉链法...
  • 哈希函数

    2019-02-16 23:55:40
    所有的字符串哈希算法都是基于对字符编码的迭代运算,只是运算规则不同而已。 1)BKDRHash算法 // BKDR Hash Function unsigned int BKDRHash(char *str) {  unsigned int seed = 131; // 31 131 1313 13131 131313...
  • 1.1 原理 假设有三台服务器,图片是怎么均匀的存储到三台缓存服务器上呢? 简单做法是将缓存的 key 做 hash 运算运算后的值是一个整数,再用缓存服务器的数量做取模运算, 用取模产生的余数来决定数据应该缓存在...
  • 数据结构哈希

    2019-07-26 10:11:53
    开发工具与关键技术:MyEclipse 10;Java基础语法 撰写时间:2019-07-26 ...对对象元素中的关键字 (对象中的特有数据) ,进行哈希算法的运算,并得出一个具体的算法值,这个值称为哈希值。而哈...
  • Python之哈希

    2020-02-26 17:19:50
    哈希哈希表是种数据结构,它可以提供快速的插入操作和查找操作。 不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0(1)的时间级。...取模运算使得 h(key) 的结果不会超过...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 339
精华内容 135
关键字:

哈希运算原理