分类:
2008-10-28 09:45:12
在开发过程中,很多人经常会使用到Hash Map或者Hash Set这种数据结构,这种数据结构的特点就是插入和访问速度快。当向集合中加入一个对象时,会调用hash算法来获得hash code,然后根据hash code分配存放位置。访问的时,根据hashcode直接找到存放位置。
Hash join 是一种非常高效的join 算法,主要以CPU(hash计算)和内存空间(创建hash table)为代价获得最大的效率。Hash join一般用于大表和小表之间的连接,我们将小表构建到内存中,称为Hash cluster,大表称为probe表。
效率
Hash join具有较高效率的两个原因:
1.Hash 查询,根据映射关系来查询值,不需要遍历整个数据结构。
2.Mem 访问速度是Disk的万倍以上。
理想化的Hash join的效率是接近对大表的单表选择扫描的。
首先我们来比较一下,几种join之间的效率,首先 optimizer会自动选择使用hash join。
注意到Cost= 221
SQL> select * from vendition t,customer b WHERE t.customerid = b.customerid;
100000 rows selected.
Execution Plan
Plan hash value: 3402771356
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
| 0 | SELECT STATEMENT | | 106K| 22M| 221 (3)| 00:00:03 |
|* 1 | HASH JOIN | | 106K| 22M| 221 (3)| 00:00:03 |
| 2 | TABLE ACCESS FULL| CUSTOMER | 5000 | 424K| 9 (0)| 00:00:01 |
| 3 | TABLE ACCESS FULL| VENDITION | 106K| 14M| 210 (2)| 00:00:03 |
不使用hash,这时optimizer自动选择了merge join。。
注意到Cost=3507大大的增加了。
SQL> select /*+ USE_MERGE (t b) */* from vendition t,customer b WHERE t.customerid = b.customerid;
100000 rows selected.
Execution Plan
Plan hash value: 1076153206
| Id | Operation | Name | Rows | Bytes |TempSpc| Cost (%CPU)| Time
| 0 | SELECT STATEMENT | | 106K| 22M| | 3507 (1)| 00:00:43 |
| 1 | MERGE JOIN | | 106K| 22M| | 3507 (1)| 00:00:43 |
| 2 | SORT JOIN | | 5000 | 424K| | 10 (10)| 00:00:01 |
| 3 | TABLE ACCESS FULL| CUSTOMER | 5000 | 424K| | 9 (0)| 00:00:01 |
|* 4 | SORT JOIN | | 106K| 14M| 31M| 3496 (1)| 00:00:42 |
| 5 | TABLE ACCESS FULL| VENDITION | 106K| 14M| | 210 (2)| 00:00:03 |
那么Nest loop呢,经过漫长的等待后,发现Cost达到了惊人的828K,同时伴随3814337 consistent gets(由于没有建索引),可见在这个中,Nest loop是最低效的。在给customerid建立唯一索引后,减低到106K,但仍然是内存join的上千倍。
SQL> select /*+ USE_NL(t b) */* from vendition t,customer b WHERE t.customerid = b.customerid;
100000 rows selected.
Execution Plan
Plan hash value: 2015764663
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
| 0 | SELECT STATEMENT | | 106K| 22M| 828K (2)| 02:45:41 |
| 1 | NESTED LOOPS | | 106K| 22M| 828K (2)| 02:45:41 |
| 2 | TABLE ACCESS FULL| VENDITION | 106K| 14M| 210 (2)| 00:00:03 |
|* 3 | TABLE ACCESS FULL| CUSTOMER | 1 | 87 | 8 (0)| 00:00:01 |
HASH的内部
HASH_AREA_SIZE在 9i 和以前,都是影响hash join性能的一个重要的参数。但是在10g发生了一些变化。Oracle不建议使用这个参数,除非你是在MTS模式下。Oracle建议采用自动PGA管理(设置PGA_AGGREGATE_TARGET和WORKAREA_SIZE_POLICY)来,替代使用这个参数。由于我的环境是mts环境,自动内存管理,所以我在这里只讨论mts下的hash join。
Mts的PGA中,只包含了一些栈空间信息,UGA则包含在large pool中,那么实际类似hash,sort,merge等操作都是有large pool来分配空间,large pool同时也是auto管理的,它和SGA_TARGET有关。所以在这种条件下,内存的分配是很灵活。
Hash连接根据内存分配的大小,可以有三种不同的效果:
1.optimal 内存完全足够
2.onepass 内存不能装载完小表
3.multipass workarea executions 内存严重不足
下面,分别测试小表为50行,500行和5000行,内存的分配情况(内存都能完全转载)。
Vendition表 10W条记录
Customer表 5000
Customer_small 500,去Customer表前500行建立
Customer_pity 50,取Customer表前50行建立
表的统计信息如下:
SQL> SELECT s.table_name,S.BLOCKS,S.AVG_SPACE,S.NUM_ROWS,S.AVG_ROW_LEN,S.EMPTY_BLOCKS FROM user_tables S WHERE table_name IN ('CUSTOMER','VENDITION','CUSTOMER_SMALL','CUSTOMER_PITY') ;
TABLE_NAME BLOCKS AVG_SPACE NUM_ROWS AVG_ROW_LEN EMPTY_BLOCKS
CUSTOMER 35 1167 5000 38 5
CUSTOMER_PITY 4 6096 50 37 4
CUSTOMER_SMALL 6 1719 500 36 2
VENDITION 936 1021 100000 64 88打开10104事件追踪:(hash 连接追踪)
ALTER SYSTEM SET EVENTS ‘ 10104 TRACE NAME CONTEXT,LEVEL 2’;
[1]