ACCESSPostgreSQL EXPLAIN执行计划上–多表连接几乎种Join方式较

更改了同一组成部分。稍后又修改。

 

老三种多表Join的算法:

一. NESTED LOOP:

对于给连续的数码子集较小之景象,嵌套循环连接是单比好的选料。在嵌套循环中,内表被标让,外表返回的各个一行还如于内表中找寻找到与她相当的实行,因此所有查询返回的结果集不克顶死(大于1 万不适合),要把返回子集较小表的当作外表(CBO 默认外表是驱动表),而且每当内表的连字段上一定要是来目录。当然为可以据此ORDERED 提示来改CBO默认的驱动表,使用USE_NL(table_name1
table_name2)可是强制CBO 执行嵌套循环连接。

         

Nested loop一般用当连年的表明中生出目录,并且索引选择性较好之时候.

 

手续:确定一个驱动表(outer table),另一个表为inner
table,驱动表中之各一行同inner表中的照应记录JOIN。类似一个嵌套的巡回。适用于驱动表的记录集比较小(<10000)而且inner表需要有立竿见影之访方法(Index)。需要小心的凡:JOIN的各个很关键,驱动表的记录集一定要稍微,返回结果集的应时间是极度抢之。

cost = outer access cost + (inner access cost * outer cardinality)

 

| 2 | NESTED LOOPS | | 3 | 141 | 7 (15)|
| 3 | TABLE ACCESS FULL | EMPLOYEES | 3 | 60 | 4 (25)|
| 4 | TABLE ACCESS BY INDEX ROWID| JOBS | 19 | 513 | 2 (50)|
| 5 | INDEX UNIQUE SCAN | JOB_ID_PK | 1 | | |

EMPLOYEES为outer table, JOBS为inner table.

 

 

二. HASH JOIN :

散列连接是CBO 做大数据集结连接时之常用方式,优化器使用有限独说明中于小之表明(或数据源)利用连接键在内存中确立散列表,然后扫描较生之表并探测散列表,找有和散列表匹配的实行。

这种措施适用于较小的发明了可以放于内存中的气象,这样总成本就是看片个说明底资本之和。但是以说明很死之情事下连无克全放入内存,这时优化器会将她分成几不比的分区,不能够放入内存的有就拿该分区写副磁盘的临时段,此时使来比较生之临时段从而尽量提高I/O 的性能。

否可就此USE_HASH(table_name1
table_name2)提示来强制行使散列连接。如果应用散列连接HASH_AREA_SIZE 初始化参数必须足够的可怜,如果是9i,Oracle建议利用SQL工作区自动管理,设置WORKAREA_SIZE_POLICY 为AUTO,然后调整PGA_AGGREGATE_TARGET 即可。

         

Hash join在片个说明底数据量差别十分可怜的时候.

 

步骤:将少只说明中比较小之一个当内存中布局一个HASH表(对JOIN
KEY),扫描另一个表明,同样对JOIN
KEY进行HASH后探测是否可以JOIN。适用于记录集比较深之场面。需要小心的凡:如果HASH表太怪,无法等同浅组织在内存中,则分为多单partition,写副磁盘的temporary
segment,则会多一个形容的代价,会下滑效率。

cost = (outer access cost * # of hash partitions) + inner access cost

 


| Id | Operation | Name | Rows | Bytes | Cost (%CPU)|

| 0 | SELECT STATEMENT | | 665 | 13300 | 8 (25)|
| 1 | HASH JOIN | | 665 | 13300 | 8 (25)|
| 2 | TABLE ACCESS FULL | ORDERS | 105 | 840 | 4 (25)|

| 3 | TABLE ACCESS FULL | ORDER_ITEMS | 665 | 7980 | 4 (25)|

ORDERS为HASH TABLE,ORDER_ITEMS扫描

 

 

三.SORT MERGE JOIN

一般而言状态下散列连接的功能还较排序合并连接要好,然而如果行源已经于消除了序,在实行排序合并连接时无需重新排序了,这时排序合并连接的性质会优于散列连接。足用USE_MERGE(table_name1
table_name2)来强制行使排序合并连接.

         

Sort Merge join 用在无索引,并且数据都排序的情况.

 

cost = (outer access cost * # of hash partitions) + inner access cost

 

手续:将点滴只表排序,然后拿鲜独说明合并。通常状态下,只有当以下情形发生时,才会采取这种JOIN方式:

1.RBO模式

2.免对等关联(>,<,>=,<=,<>)

3.HASH_JOIN_ENABLED=false

4.数据源已排序

 

 

四.  三种植连接工作法较:

      

       Hash
join的工作方法是用一个发明(通常是小一些底慌表)做hash运算,将列数据存储到hash列表中,从其他一个表中抽取记录,做hash运算,到hash 列表中找到相应的值,做配合。

         

Nested
loops 工作章程是起同摆放表中读取数据,访问另一样张表(通常是索引)来开配合,nested
loops适用的场合是当一个关联表比较小的下,效率会重胜似。

 

         Merge
Join 是事先以关联表的关联列各自做排序,然后起各自的排序表中抽取数据,到任何一个排序表中做配合,因为merge
join需要开还多的排序,所以吃的资源还多。 通常来讲,能够用merge
join的地方,hash join都好发表更好之性。

 

 

数据库多表连接方式介绍-HASH-JOIN

 

1.概述

  hash
join是平种植数据库在展开多表连接时的拍卖算法,对于多表连接还有点儿栽于常用之法门:sort
merge-join 和 nested loop。 为了比较清楚的介绍hash
join的采取状况以及为何设引入这样同样栽连接算法,这里呢会见顺便简单介绍一下点提到的有限种join方式。

  连接方式是一个安的概念,或者说俺们为什么要发生同时有几许种,对于未极端了解数据库的人数来讲或许这些是起的迷惑。简单来讲,我们拿数据有不同之表中,而各异之表有着它自己的发明结构,不同表之间可是出涉及的,大部分实在运用中,不见面只是只有待同张表的信息,比如用由一个班级表中搜索有杭州地区底学习者,再就此者信息去寻觅成绩表中他们之数学成绩,如果无多表连接,那只好手动将首先个表的信息查询出来作为第二独说明的追寻信息去询问最终之结果,可想而知这将见面是多么繁琐。

  对于几单大的数据库,像oracle,postgresql它们都是永葆hash-join的,mysql并无支持。在即时上面,oracle和pg都曾经做的比较完善了,hash-join本身的实现并无是格外复杂,但是她要优化器的贯彻配合才能够尽老之表述本身的优势,我当就才是太麻烦之地方。

  多表连接的查询方式以分为以下几种植:内连接,外接连和穿插连接。外接连而分为:左外连接,右外连接和全外连接。对于不同的查询办法,使用同样之join算法也会发两样之代价来,这个是与该实现方式紧密有关的,需要考虑不同的查询艺术怎么样实现,对于具体应用啊一样种植连接方式是由于优化器通过代价的衡量来决定的,后面会简单介绍一下几乎栽连接方式代价的盘算。
hashjoin其实还有为数不少要考虑同实现的地方,比如数据倾斜严重如何处理、内存放不下怎么木办,hash如何处理冲突等,这些并无是本文介绍的重中之重,不再详述,每个拿出去都得更张嘴同样首了。

  nested loop join

  嵌套循环连接,是较通用的连方式,分为前后表,每扫描外表的一行数都要于内表中查找和的相配合的履行,没有索引的复杂度是O(N*M),这样的复杂度对于特别数目集是非常劣势的,一般来讲会经过搜寻引来提升性能。 

   sort merge-join

  merge
join需要首先针对少个说明按照关联的字段进行排序,分别于少单说明中取出一行数开展匹配,如果适度放入结果集;不配合将较小之那行丢掉继续配合另一个阐明的下一行,依次拍卖直到将两表的多少获得完。merge
join的酷十分一些开花在排序上,也是同等条件下差于hash
join的一个重要原因。

2.原理同兑现

  简单的对于个别只说明来讲,hash-join就到底说点儿申明中的小表(称S)作为hash表,然后去扫描另一个阐明(称M)的各个一行数,用得出去的行数据依据连续条件去炫耀建立的hash表,hash表是置身内存中之,这样好便捷的收获相应的S表与M表相兼容的执行。

  对于结果集非常死的景象,merge-join需要针对其排序效率并无会见坏高,而nested
loop
join是相同种植嵌套循环的查询办法确实更非合乎生数据集的连日,而hash-join正是为拍卖这种困难的询问办法而格外,尤其是对于一个大表和一个小表的状,基本上只有待用大小表扫描一全体就是足以得出最终的结果集。

  不过hash-join只适用于等值连接,对于>, <, <=,
>=这样的查询连接要用nested
loop这种通用的连接算法来处理。如果老是key本来就是有序的要么用排序,那么可能就此merge-join的代价会比hash-join更粗,此时merge-join会重复发出优势。

  好了,废话说了累累了,来讲说实现,拿同样久简单的多表sql查询语句来推举个栗子:select
* from t1 join t2 on t1.c1 = t2.c1 where t1.c2 > t2.c2 and t1.c1
>
1。这样同样漫漫sql进入数据库系统中,它是怎吃拍卖及解剖的吗?sql:鬼知道我都更了若干什么。。。

  1.背景知识

  1.首先步呢,它需经验词法以及语法的辨析,这片之输出是一致粒带有token结点的语法树。

  ACCESS 1  

  语法分析,顾名思义这有的仅是语法层面的剖析,将一个string的sql语句处理成同粒有着雏形结构的node
tree,每个结点有她本身之非正规标识,但是连无分析及拍卖此结点的现实意思和价值。

  2. 次之步是语义分析与重写处理。

  重写的经过不同之数据库可能发生差的拍卖,有些可能是暨逻辑执行进程在一块儿,有的尽管分别。

  ACCESS 2

  这同步做完树的样大体上是和语法分析树保持一致的,但是这底结点都携了有些具体的信息,以where后面的表达式为条例,这粒被缀表达式每一个结点都发矣本人的门类和特定的音讯,并无关心值是啊,这步做完后跻身改写过程,改写是同等种植逻辑优化措施,使得有些扑朔迷离的sql语句变得重简便易行或者又切合数据库的拍卖流程。

  3.优化器处理

  优化器的处理是比较复杂的,也是sql模块最难以的地方,优化无止境,所以优化器没有最好优异特来还优秀。优化器需要考虑全的要素既设召开的通用型很强以使包充分强之优化能力和不利。

  优化器最紧要的打算莫过于路径选择了,对于多表连接如何规定表连接的各个及连方式,不同之数据库有不同的处理方式,pg支持动态规划算法,表数据过多之时光利用遗传算法。路径的规定以乘让代价模型的落实,代价模型会保护有统计信息,像列的最好深价值、最小价、NDV和DISTINCT值等,通过这些消息可算选择率从而越计算代价。

  ACCESS 3

  回归到正文,使用啊一样栽连接方式就是在这里决定的,hash join
对大小表是产生求的,所以这边形成的计划是t1-t2还是t2-t1凡是匪均等的,每种连接方式有自身的代价计算办法。

  hash join的代价估算:

  COST = BUILD_COST + M_SCAN_COST + JOIN_CONDITION_COST +
FILTER_COST

  简单来拘禁,hash
join的代价主要在建立hash表、扫描M表、join条件连接和filter过滤,对于S表和M表都是就需要扫描一坏即可,filter过滤是指t1.c2>t2.c2这么的规范过滤,对于t1.c1>1如此光涉及单表的原则会为下压,在举行连接之前就是受滤了。

  优化器处理过后,会怪成一粒执行计划树,真正的实现过程根据实施计划之流程操作数据,由低向上地递归处理并赶回数据。

  ACCESS 4  

  2.hash join的实现

  hash join的兑现分为build table也便是为用来建立hash map的小表和probe
table,首先依次读取小表的数码,对于各级一行数因连续条件十分成一个hash
map中之一个元組,(最终一个key对诺了千篇一律组数据,key可以装也10或其它)数据缓存在内存中,如果内存放不生用dump到外存。依次扫描探测表拿到各级一行数根据join
condition生成hash key映射hash
map中对应之元組,元組对应的行和探测表的立即一行有着一样的hash key,
这时并无可知确定就简单尽就是是满足条件的数据(因为一个key可能对应之凡相同组数,hash值为10时,1,11,21,31…还于余为1中里面),需要更过一样尽join
condition和filter,满足条件的数码集返回需要的投影列。

  ACCESS 5    

  hash join实现之几只细节

  1.hash
join自的实现不要错过看清哪个是小表,优化器生成执行计划时即便已规定了说明底连各个,以左表为小表建立hash
table,那对应的代价模型就见面以左表作为小表来得出代价,这样因代价变的门路就是是顺应实现要求的。

  2.hash
table的轻重、需要分配多少个桶这个是要在同等始就是办好的,那分配多少是一个题材,分配最大会造成内存浪费,分配最小会促成桶数过多少开链过长性能变差,一旦过此的内存限制,会考虑dump到外存,不同数据库有其本身之落实方式。

  3.什么样对数据hash,不同数据库有自己的法门,不同的哈希方法呢会针对性造成一定的熏陶。

3.pg和oracle实测

1.oracle

表结构

ACCESS 6

SQL> select * from or1;

     A        B
---------- ----------
     1        1
     2        2
     3        3

SQL> select * from or2;

     A        B C
---------- ---------- --------------------
     1        2 a
     2        3 b
     4        5 d

ACCESS 7

内连接

ACCESS 8

SQL> select * from or1 join or2 on or1.a = or2.a;

     A        B           A      B C
---------- ---------- ---------- ---------- --------------------
     1        1           1      2 a
     2        2           2      3 b
SQL> explain plan for select * from or1 join or2 on or1.a = or2.a;

Explained.

SQL> SELECT plan_table_output FROM TABLE(DBMS_XPLAN.DISPLAY('PLAN_TABLE'));

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 738363828

---------------------------------------------------------------------------
| Id  | Operation       | Name | Rows  | Bytes | Cost (%CPU)| Time      |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |    3 |   192 |    4   (0)| 00:00:01 |
|*  1 |  HASH JOIN       |      |    3 |   192 |    4   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| OR1  |    3 |    78 |    2   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| OR2  |    3 |   114 |    2   (0)| 00:00:01 |
---------------------------------------------------------------------------


PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("OR1"."A"="OR2"."A")

Note
-----
   - dynamic statistics used: dynamic sampling (level=2)

19 rows selected.

ACCESS 9

左外连接,右外连接

ACCESS 10

SQL> select * from or1 left join or2 on or1.a = or2.a;

     A        B           A      B C
---------- ---------- ---------- ---------- --------------------
     1        1           1      2 a
     2        2           2      3 b
     3        3

SQL> explain plan for select * from or1 left join or2 on or1.a = or2.a;

Explained.

SQL> SELECT plan_table_output FROM TABLE(DBMS_XPLAN.DISPLAY('PLAN_TABLE'));

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 1456425992

---------------------------------------------------------------------------
| Id  | Operation       | Name | Rows  | Bytes | Cost (%CPU)| Time      |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |    3 |   192 |    4   (0)| 00:00:01 |
|*  1 |  HASH JOIN OUTER   |      |    3 |   192 |    4   (0)| 00:00:01 |
|   2 |   TABLE ACCESS FULL| OR1  |    3 |    78 |    2   (0)| 00:00:01 |
|   3 |   TABLE ACCESS FULL| OR2  |    3 |   114 |    2   (0)| 00:00:01 |
---------------------------------------------------------------------------


PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("OR1"."A"="OR2"."A"(+))

Note
-----
   - dynamic statistics used: dynamic sampling (level=2)

19 rows selected.

ACCESS 11

全外连接

ACCESS 12

SQL> select * from or1 full join or2 on or1.a = or2.a;

     A        B           A      B C
---------- ---------- ---------- ---------- --------------------
     1        1           1      2 a
     2        2           2      3 b
                   4      5 d
     3        3

SQL> SELECT plan_table_output FROM TABLE(DBMS_XPLAN.DISPLAY('PLAN_TABLE'));

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 2943417606

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

| Id  | Operation          | Name     | Rows  | Bytes | Cost (%CPU)| Time
 |

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


PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     3 |   192 |     4   (0)| 00:00:01
 |

|   1 |  VIEW              | VW_FOJ_0 |     3 |   192 |     4   (0)| 00:00:01
 |

|*  2 |   HASH JOIN FULL OUTER|      |     3 |   192 |     4   (0)| 00:00:01
 |

|   3 |    TABLE ACCESS FULL  | OR1     |     3 |    78 |     2   (0)| 00:00:01
 |

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------

|   4 |    TABLE ACCESS FULL  | OR2     |     3 |   114 |     2   (0)| 00:00:01
 |

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


Predicate Information (identified by operation id):
---------------------------------------------------


PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
   2 - access("OR1"."A"="OR2"."A")

Note
-----
   - dynamic statistics used: dynamic sampling (level=2)

20 rows selected.

ACCESS 13

 

2.postgresql

申数据量

ACCESS 14

hudson=# select count(*) from hj1;

count

200022
(1 row)

hudson=# select count(*) from hj2;

count

200000
(1 row)

ACCESS 15

内连接

ACCESS 16

hudson=# explain select * from hj1 join hj2 on hj1.a=hj2.a;
                               QUERY PLAN
------------------------------------------------------------------------
 Hash Join  (cost=7338.00..26467.34 rows=430732 width=51)
   Hash Cond: (hj1.a = hj2.a)
   ->  Seq Scan on hj1  (cost=0.00..3467.22 rows=200022 width=25)
   ->  Hash  (cost=3470.00..3470.00 rows=200000 width=26)
         ->  Seq Scan on hj2  (cost=0.00..3470.00 rows=200000 width=26)
(5 rows)

ACCESS 17

外连接 

外接连使用大小表数据量差别比较老的有限单说明,可以清楚的张hash
join是以小表作为hash table的。

ACCESS 18

hudson=# explain select * from hj1 full join hj3 on hj1.a=hj3.a;

QUERY PLAN

Hash Full Join (cost=7335.50..8905.67 rows=200022 width=33)
Hash Cond: (hj3.a = hj1.a)
->  Seq Scan on hj3 (cost=0.00..32.60 rows=2260 width=8)
-> Hash (cost=3467.22..3467.22 rows=200022 width=25)
-> Seq Scan on hj1 (cost=0.00..3467.22 rows=200022 width=25)
(5 rows)

hudson=# explain select * from hj1 left join hj3 on hj1.a=hj3.a;

QUERY PLAN

Hash Right Join (cost=7335.50..8905.67 rows=200022 width=33)
Hash Cond: (hj3.a = hj1.a)
->  Seq Scan on hj3 (cost=0.00..32.60 rows=2260 width=8)
-> Hash (cost=3467.22..3467.22 rows=200022 width=25)
-> Seq Scan on hj1 (cost=0.00..3467.22 rows=200022 width=25)
(5 rows)

hudson=# explain select * from hj1 right join hj3 on hj1.a=hj3.a;

QUERY PLAN

Hash Left Join (cost=7335.50..8905.67 rows=5270 width=33)
Hash Cond: (hj3.a = hj1.a)
->  Seq Scan on hj3 (cost=0.00..32.60 rows=2260 width=8)
-> Hash (cost=3467.22..3467.22 rows=200022 width=25)
-> Seq Scan on hj1 (cost=0.00..3467.22 rows=200022 width=25)
(5 rows)

ACCESS 19

足见见,left join为了能为小表建立hash table被更换为right join,
同样right join也吃移写成left join。

 

重来精心阐述一下Hash join的历程:

一.        Hash Join概述
Hash join算法的一个主干考虑便是冲小之row sources(称作build
input,我们记较小的表为S,较充分之表为B) 建立一个得是于hash
area内存中的hash table,然后用老的row sources(称作probe input)
来探测前面所构筑的hash table。如果hash area内存不敷好,hash
table就无法完全存放于hash
area内存中。针对这种情况,Oracle在连接键利用一个hash函数将build
input和probe
input分割成多独无随地的分区(分别记作Si和Bi),这个路叫作分区阶段;然后分别对应的分区,即Si和Bi再举行Hash
join,这个等级叫作join阶段。
一经当分区后,针对有分区所构筑的hash
table还是最为可怜之说话,oracle就动用nested-loops hash
join。所谓的nested-loops hash join就是针对性一些Si建立hash
table,然后读取所有的Bi与所建造的hash
table做连接,然后又对余下的Si建立hash table,再将有所的Bi与所建之hash
table做连接,直至所有的Si都连了了。
Hash
Join算法有一个限,就是其是以借而两摆放表在连接键上是都匀的,也就是说每个分区拥有多的数。但是实际上中数据还是休净匀的,为了好好地解决这个问题,oracle引进了几乎栽技术,位图向量过滤、角色互换、柱状图。
二.        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的特性。
Oracle采用其中一个hash函数作用被连接键上,将S和B分割成多只分区,在这里我们如果是hash函数为请余函数,即Mod(join_column_value,10)。这样发生十只分区,如下表。

分区                B0        B1        B2        B3        B4       
B5        B6        B7        B8        B9
        值        0,0,10,10        1,1,1,1,11        2,2,2,2,2,2       
3        NULL        NULL        NULL        NULL        8       
9,9,9
S0        10       
√                                                                        
S1        1,1,1               
√                                                                
S2       
Null                                                                                
S3        3,3                               
√                                                
S4       
4,4,4,4                                                                                
S5       
5                                                                                
S6       
NULL                                                                                
S7       
NULL                                                                                
S8       
8,8,8,8                                                                       
√        
S9       
NULL                                                                                
透过如此的分区之后,只需要相应的分区之间做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的成本
1.        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)
2.        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算法介绍(转):

版权声明:本文也博主原创文章,转载请指明
http://blog.csdn.net/tanggao1314

 

 

一.概念

 

哈希表就是一致种植为 键-值(key-indexed)
存储数据的构造,我们若输入待搜的值就是key,即可寻找到该对应之价值。

哈希的思路特别简短,如果拥有的键都是整数,那么就算得以一个简练的无序数组来落实:将键作为目录,值即为夫相应的值,这样虽可以快速访问任意键的值。这是对于简易的键的景,我们用那扩张至好拍卖越扑朔迷离的品种的键。

运哈希查找有些许单步骤:

1. 采取哈希函数将于摸的键转换为数组的目录。在好之气象下,不同之键会被移为不同的索引值,但是以多少情况下我们得处理多单键被哈希到和一个索引值的情形。所以哈希查找的亚独步骤就是是拍卖闯

2. 甩卖哈希碰撞冲突。有那么些甩卖哈希碰撞冲突之法,本文后面会介绍拉链法和线性探测法。

哈希表是一个以时以及空间及做出权衡的藏例子。如果没内存限制,那么得一直将键作为数组的目。那么具有的查找时间复杂度为O(1);如果没工夫限制,那么我们可运用无序数组并进行逐项查找,这样只是待很少之内存。哈希表使用了适龄的时光跟空间来当即时简单单极之间找到了平衡。只待调动哈希函数算法即可在岁月和空中上做出取舍。

 

 

在Hash表中,记录在表中的职和该要字之内在在一样栽确定的关系。这样我们即便能够先了解所查看重点字当表中的职,从而一直通过下标找到记录。使ASL趋近与0.

 

            
 1)   哈希(Hash)函数是一个画面,即: 将重要字的集合映射到某某地点集合上,它的安老利索,只要这个地
      址集合的分寸非浮允许范围即可;

            
2)  由于哈希函数是一个削减映象,因此,在一般景象下,很易发生“冲突”现象,即: key1!=key2,而  f
 (key1) = f(key2)。

            
 3).  只能尽量减少冲突要休克完全避免冲突,这是因一般而言要字集合比较老,其元素包括所有可能的机要字, 而地址集合的元素就为哈希表中之地点值

 

     
 在结构这种异常的“查找表” 时,除了用选择一个“好”(尽可能少产生冲突)的哈希函数之外;还得找到同样
“处理闯” 的方法。

 

二.Hash构造函数的方法

 

   1.一直定址法:

                         

 直白定址法是坐数量元素关键字k本身还是其的线性函数作为它们的哈希地址,即:H(k)=k
 或 H(k)=a×k+b ; (其中a,b为常数)

  例1,有一个人口统计表,记录了从1载至100岁之总人口数据,其中年纪作为根本字,哈希函数取关键字我,如图(1):

地址

A1

A2

……

A99

A100

年龄

1

2

……

99

100

人数

980

800

……

495

107

足见见,当得找某平岁的口时,直接搜索相应的宗即可。如搜寻99寒暑的老人数,则直读来第99宗即可。

 

地址

A0

A1

……

A99

A100

年龄

1980

1981

……

1999

2000

人数

980

800

……

495

107

 

要我们只要统计的是80晚诞生的人口数,如上表所示,那么我们班出生年是要字可以用年减去1980来作地方,此时f(key)=key-1980

这种哈希函数简单,并且对不同之第一字勿会见发生冲突,但得见到这是一样种植较为突出之哈希函数,实际在着,关键字的因素很少是接二连三的。用该法发生的哈希表会促成空间大量之荒废,因此这种方式适应性并无赛。\[2\]

  此法才符合给:地址集合的深浅 =
= 关键字集合的轻重,其中a和b为常数。

 

 

2.数字分析法:

           
 假设重点字集合中的每个重要字都是由于 s 位数字组成 (u1,
u2, …,
us),分析重点字集中之全部,并从中提取分布均匀的多少各还是其的结缘作为地方。

数字分析法是得多少元素关键字被一些取值较咸匀的数字位作为哈希地址的法。即当重点字之位数很多时时,可以由此对重要字的诸位进行分析,丢掉分布不咸匀的个,作为哈希值。它才可为具有重点字值已掌握之动静。通过分析分布情况将重要字取值区间转化为一个比较小之重要字取值区间。

   例2,要结构一个数码元素个数n=80,哈希长度m=100之哈希表。不失一般性,我们这里仅给闹其中8个主要字展开分析,8单第一字如下所示:

K1=61317602      K2=61326875      K3=62739628      K4=61343634

K5=62706815      K6=62774638      K7=61381262      K8=61394220

分析上述8单举足轻重字可知,关键字从左到右的第1、2、3、6各项取值比较集中,不宜作哈希地址,剩余的第4、5、7、8各取值较咸匀,可挑选其中的星星员作为哈希地址。设选取最后两位作为哈希地址,则随即8个重大字之哈希地址分别吗:2,75,28,34,15,38,62,20。 
         

 

 本法适于:能事先估计有全方位关键字之诸一样员上各种数字出现的频度。

             

3.折叠法:

           
将着重字分割成多少片,然后抱其的叠加和为哈希地址。两栽叠加拍卖的方法:移位叠加:将分 割后的几乎部分不如对齐相加;边界叠加:从平端挨分割界来回折叠,然后针对齐相加。

所谓折叠法是拿第一字分割成各类数一模一样之几组成部分(最后一部分的位数可以不同),然后抱这几有些之增大和(舍去进位),这措施称为折叠法。这种措施适用于重点字位数比多,而且要字中各一样员上数字分布大致均匀的状态。

  折叠法中一再各项折叠而分为移位叠加和边际叠加点儿栽方式,移位叠加是以分开后是各一样局部的最低位对伙同,然后相加;边界叠加是起一头向任何一样端挨分割界来回折叠,然后针对齐相加。

例4,当哈希表长为1000常常,关键字key=110108331119891,允许的地址空间也老三位十向前制数,则随即半种植叠加情况而图:

       移位叠加                                 边界叠加

       8 9 1                                     8 9 1

       1 1 9                                     9 1 1

       3 3 1                                     3 3 1

       1 0 8                                     8 0 1

    +  1 1 0
                                  + 1 1 0              

   (1) 5 5 9                                  (3)0 4 4

                 图(2)由折叠法求哈希地址

     用移位叠加得的哈希地址是559,而之所以边界叠加所得到的哈希地址是44。如果要字勿是数值而是字符串,则只是先转化为数。转化的艺术可以据此ASCⅡ字符或字符的次序值。

            此法适于:一言九鼎字之数字位数特别多。

 

4.平方取中模仿

  顿时是相同种植常用之哈希函数构造方法。这个点子是事先获得关键字的平方,然后因可应用空间的尺寸,选取平方数是中等几乎号为哈希地址。

哈希函数
H(key)=“key2的中档几乎个”因为这种办法的原理是经取得平方扩大差别,平方值的中游几乎号与是数之各一样各类还息息相关,则指向两样之关键字落的哈希函数值是有冲突,由此发生的哈希地址也较均匀。

例5,若设哈希表长为1000尽管可得到关键字平方值的中三号,如图所示:

关键字

关键字的平方

哈希函数值

1234

1522756

227

2143

4592449

924

4132

17073424

734

3214

10329796

297 

  

下让闹平方取中效仿之哈希函数

     //平方取中法哈希函数,结设关键字值32各之平头

     //哈希函数将回到key * key的中间10位

       Int  Hash (int key)

         {

     //计算key的平方

      Key * = key ;

     //去掉低11位

     Key>>=11;

     // 返回低10位(即key * key的中间10位)

       Return key %1024;

          }

   本法适于:重点字被的诸一样号都发生好几数字又出现频度很高的状况

 

 

5.减去法

 

减去法是数据的键值减去一个特定的数值为求得数据存储的职。

例7,公司出一百单职工,而职工的号子在1001到1100,减去学即是职工编号减去1000晚就是为数据的职务。编号1001职工的数额在多少中的第一画。编号1002员工的多寡在数量被的亚笔…依次类推。从而赢得有关员工的兼具消息,因为号码1000原先并没有多少,所有员工编号都于1001开头编号。

 

 

6.基数转换法

  将十进制数X看作其他进制,比如十三进制,再按十三上制数转换成十上制数,提取其中几乎作为X的哈希值。一般拿走过原来基数的数作为转换的基数,并且两只基数应该是互素的。

 

例Hash(80127429)=(80127429)13=8*137+0*136+1*135+2*134+7*133+4*132+2*131+9=(502432641)10要是博中间三个作为哈希值,得Hash(80127429)=432

 为了拿走良好的哈希函数,可以将几种方法并起来用,比如先变基,再折或平方取中等等,只要散列均匀,就得随便拼凑。

 

 

 

  7.除留余数法:

             

苟哈希表长为m,p为小于等于m的极深素数,则哈希函数为

h(k)=k  %  p ,其中%为模p取余运算。

像,已知待散列元素呢(18,75,60,43,54,90,46),表长m=10,p=7,则生

    h(18)=18 % 7=4    h(75)=75 % 7=5    h(60)=60 %
7=4   

    h(43)=43 % 7=1    h(54)=54 % 7=5    h(90)=90 %
7=6   

    h(46)=46 % 7=4

这儿冲突较多。为压缩冲,可取较生之m值和p值,如m=p=13,结果如下:

    h(18)=18 % 13=5    h(75)=75 % 13=10    h(60)=60 %
13=8    

    h(43)=43 % 13=4    h(54)=54 % 13=2    h(90)=90 %
13=12   

    h(46)=46 % 13=7

这不曾撞,如图8.25所著。

 

0      1      2     3     4     5      6     7     8     9     10     11    12

 

 

 

54

 

43

18

 

46

60

 

75

 

90

                      

 

除留余数法求哈希地址

 

 

辩研讨表明,除留余数法的模p取不超过表长且最好相近表长m素数时效力太好,且p最好得1.1n~1.7n期间的一个素数(n为存在的多寡元素个数)

 

 

8.随机数法:

           设定哈希函数为:H(key) = Random(key)其中,Random 为伪随机函数

           此法适于:本着长不等的基本点字构造哈希函数。

 

        
实际造表时,采用何种构造哈希函数的计在建表的显要字集合的状(包括要字的限定及形态),以及哈希表
 
 长度(哈希地址范围),总的条件是使有冲突的可能性降低到尽可能地聊。

 

9.随机乘数法

  亦曰“乘余取整法”。随机乘数法使用一个随意实数f,0≤f<1,乘积f*k的分数有在0~1之内,用这分有的价和n(哈希表的长度)相乘,乘积的平头部分就是是相应之哈希值,显然这哈希值落于0~n-1之间。其发挥公式为:Hash(k)=「n*(f*k%1)」其中“f*k%1”表示f*k
的小数部分,即f*k%1=f*k-「f*k」

  例10,对下列关键字值集合采用擅自乘数仿计算哈希值,随机数f=0.103149002
哈希表长度n=100得图:

 

k

f*k

n*((f*k)的小数部分)

Hash(k)

319426

32948.47311

47.78411

47

718309

74092.85648

86.50448

86

629443

64926.41727

42.14427

42

919697

84865.82769

83.59669

83

  此道的独到之处是对n的挑无坏重要。通常要地址空间吧p位就是选n=2p.Knuth对经常反复f的拟做了密切的钻,他觉得f取任何价值都得,但某些价值功能更好。如f=(-1)/2=0.6180329…比较理想。

 

10.字符串数值哈希法

在好都状况下主要字是字符串,因此这样对字符串设计Hash函数是一个需讨论的问题。下列函数是取字符串前10单字符来设计的哈希函数

Int Hash _ char (char *X)

{

  int I ,sum 

  i=0;

  while (i 10 && X[i])

  Sum +=X[i++];

  sum%=N;      //N是记录的条数

  }

这种函数把字符串的面前10单字符的ASCⅡ值之与对N取摸作为Hash地址,只要N较小,Hash地址将于咸匀分布[0,N]距离内,因此这函数还是可用的。对于N很酷之事态,可采取下列函数

int ELFhash (char *key )

{

 Unsigned long h=0,g;

whie (*key)

h=(h<<4)+ *key;

key++;

g=h & 0 xF0000000L;

if (g) h^=g>>24;

h & =~g;

}

h=h % N

return (h);

}

  这个函数称为ELFHash(Exextable and Linking Format
,ELF,可实行链接格式)函数。它把一个字符串的断然长作为输入,并经过一样种植艺术把字符的十上前制值结合起来,对长字符串和短字符串都灵验,这种方式来的职位不可能不统匀分布。

 

11.旋转法

  旋转法是以数据的键值中开展盘。旋转法通常并无直接下以哈希函数上,而是搭配任何哈希函数使用。

  例11,某学校以及一个相关的初杀(小于100人)的学号前5各数是同等之,只有最终2个数不同,我们将最终一员数,旋转放置到第一位,其余的朝右侧变。

新生学号

旋转过程

旋转后的新键值

5062101

5062101

1506210

5062102

5062102

2506210

5062103

5062103

3506210

5062104

5062104

4506210

5062105

5062105

5506210

                    如图

 下这种艺术可以但输入一个数值从而快速地翻及关于学生的音。

 

 

当实际采用被,应根据具体情况,灵活采用不同之道,并就此实际数据测试它的性能,以便做出科学判断。通常应考虑以下五单因素 :

l 计算哈希函数所欲时 (简单)。

l 关键字之长短。

l 哈希表大小。

l 关键字分布状况。

l 记录查找频率

 

 

 

三.Hash处理闯方法

 

   通过结构性能优异的哈希函数,可以减掉冲,但貌似不容许完全避免冲突,因此解决冲突是哈希法的外一个关键问题。创建哈希表和摸索哈希表都见面遇见冲突,两种状态下解决冲突之方式应该亦然。下面坐创造哈希表为条例,说明解决冲突之法子。常用之化解冲突方法来以下四种植:

 通过结构性能优良的哈希函数,可以减掉冲,但貌似不容许完全避免冲突,因此解决冲突是哈希法的其他一个关键问题。创建哈希表和摸索哈希表都见面赶上冲突,两种植状况下解决冲突之不二法门应该同。下面坐创建哈希表为条例,说明解决冲突之方法。常用之化解冲突方法有以下四栽:

1.         开放定址法

这种艺术为称又散列法,那个核心考虑是:当重要字key的哈希地址p=H(key)出现冲常常,以p为根基,产生任何一个哈希地址p1,如果p1仍然冲突,再坐p为根基,产生其它一个哈希地址p2,…,直到找来一个勿闯的哈希地址pi ,将相应元素存入其中。这种办法来一个通用的重新散列函数形式:

          Hi=(H(key)+di)% m   i=1,2,…,n

    其中H(key)为哈希函数,m 也表长,di称为增量列。增量列的取值方式各异,相应的更散列方式吧不比。主要发生以下三种:

l         线性探测再散列

    dii=1,2,3,…,m-1

这种措施的性状是:冲突有常,顺序查看表中生一致单元,直到找来一个空单元或查遍全表。

l         二潮探测再散列

    di=12,-12,22,-22,…,k2,-k2    (
k<=m/2 )

    这种方式的表征是:冲突发生时,在表底左右进展跳跃式探测,比较灵活。

l         伪随机探测再散列

    di=伪随机数序列。

实际贯彻时,应成立一个伪随机数发生器,(如i=(i+p) %
m),并被一定一个即兴数开起点。

譬如说,已知道哈希表长度m=11,哈希函数为:H(key)=
key  %  11,则H(47)=3,H(26)=4,H(60)=5,假设下一个第一字呢69,则H(69)=3,与47冲。如果就此线性探测再散列处理闯,下一个哈希地址为H1=(3 + 1)% 11 =
4,仍然冲突,再寻找下一个哈希地址为H2=(3 + 2)% 11 =
5,还是冲,继续找下一个哈希地址为H3=(3 + 3)% 11 = 6,此时不再冲突,将69填写入5号单元,参图8.26
(a)。如果就此二软探测再散列处理冲突,下一个哈希地址也H1=(3 + 12)% 11 = 4,仍然冲突,再找下一个哈希地址也H2=(3 – 12)% 11 = 2,此时不再冲突,将69填写入2号单元,参图8.26
(b)。如果就此伪随机探测再散列处理闯,且伪随机数序列为:2,5,9,……..,则生一个哈希地址为H1=(3 + 2)% 11 =
5,仍然冲突,再找下一个哈希地址为H2=(3 + 5)% 11 = 8,此时不再冲突,将69填写入8号单元,参图8.26
(c)。

 

 

0        1       2      3      4      5       6      7      8       9      10    

 

 

 

 

47

26

60

69

 

 

 

 

         (a) 用线性探测再散列处理冲突

 

 

0        1       2      3      4      5       6      7      8       9      10    

 

 

 

69

47

26

60

 

 

 

 

 

         (b) 用二糟探测再散列处理冲突

 

 

0        1       2      3      4      5       6      7      8       9      10    

 

 

 

 

47

26

60

 

 

69

 

 

         (c) 用伪随机探测再散列处理冲突

 

                      图8.26盛开地方法处理冲突

自打上述例子可以观看,线性探测再散列容易出“二次于聚集”,即于处理同义词的冲常常以导致非同义词的闯。例如,当表中i, i+1 ,i+2三个单元已满时,下一个哈希地址也i, 或i+1 ,或i+2,或i+3的元素,都拿填入i+3这跟一个单元,而当时四单元素并非与义词。线性探测再散列的独到之处是:只要哈希表不洋溢,就决然能够找到一个未冲突之哈希地址,而二不行探测再散列和伪随机探测再散列则无自然。

 

2. 复哈希法

    这种方式是还要组织多单不等的哈希函数:

    Hi=RH1(key)  i=1,2,…,k

当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到撞不再有。这种方式对有聚集,但多了匡时。

3. 链地址法

    这种方式的着力思想是用所有哈希地址为i的素结合一个叫同义词链的单链表,并拿单链表的头指针存在哈希表的第i只单元中,因而查找、插入和去主要在平词链中开展。链地址法适用于时开展扦插和去的状。

诸如,已了解一组第一字(32,40,36,53,16,46,71,27,42,24,49,64),哈希表长度为13,哈希函数为:H(key)= key %
13,则就此链地址法处理闯的结果使图

 

 
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

希冀链地址法处理冲突时常的哈希表

本例的平均查找长度 ASL=(1*7+2*4+3*1)=1.5

4.白手起家国有溢出区

这种方式的中心思维是:将哈希表分为基本表溢出表区区组成部分,凡是跟基本表发生冲突的因素,一律填入溢起表

 

 hash算法就上总结到这里了,今天度过了22寒暑生日,晚上还是坚持做到了写就首博客,今天少不写了,明天来总Java中的hashcode和equals方法,

转载请指明出处http://blog.csdn.net/tanggao1314/article/details/51457585

参考资料

大话数据结

算法导论

 

相关文章