首页 > 代码库 > Sort merge join、Nested loops、Hash join（三种连接类型）
Sort merge join、Nested loops、Hash join（三种连接类型）
目前为止，典型的连接类型有3种：
Sort merge join（SMJ排序－合并连接）：
首先生产driving table需要的数据，然后对这些数据按照连接操作关联列进行排序；然后生产probed table需要的数据，然后对这些数据按照与driving table对应的连接操作列进行排序；最后两边已经排序的行被放在一起执行合并操作。排序是一个费时、费资源的操作，特别对于大表。所以smj通常不是一个特别有效的连接方法，但是如果driving table和probed table都已经预先排序，则这种连接方法的效率也比较高。
Nested loops（NL嵌套循环）：
连接过程就是将driving table和probed table进行一次嵌套循环的过程。就是用driving table的每一行去匹配probed table 的所有行。Nested loops可以先返回已经连接的行，而不必等待所有的连接操作处理完成才返回数据，这可以实现快速的响应时间。
Hash join（哈希连接）：
较小的row source被用来构建hash table与bitmap，第二个row source用来被hashed，并与第一个row source生产的hash table进行匹配。以便进行进一步的连接。当被构建的hash table与bitmap能被容纳在内存中时，这种连接方式的效率极高。但需要设置合适的hash_area_size参数且只能用于等值连接中。
Cartesian product（笛卡尔积）：表的每一行依次与另外一表的所有行匹配。
_______________________________________________________
实验：
SQL> create table segs as select * from dba_segments where owner=‘SYS‘;
Table created.
SQL> create table objts as select * from dba_objects where owner=‘SYS‘;
Table created.
SQL> select count(*) from segs;
COUNT(*)
----------
2355
SQL> select count(*) from objts;
COUNT(*)
----------
30967
SQL> create index idx_segs_name on segs(segment_name);
Index created.
SQL> create index idx_objts_name on objts(object_name);
Index created.
SQL> exec dbms_stats.gather_table_stats(user,‘SEGS‘,cascade => true);
PL/SQL procedure successfully completed.
SQL> exec dbms_stats.gather_table_stats(user,‘OBJTS‘,cascade => true);
PL/SQL procedure successfully completed.
作用:DBMS_STATS.GATHER_TABLE_STATS统计表,列,索引的统计信息.
DBMS_STATS.GATHER_TABLE_STATS的语法如下:
DBMS_STATS.GATHER_TABLE_STATS ( ownname VARCHAR2, tabname VARCHAR2, partname VARCHAR2, estimate_percent NUMBER, block_sample BOOLEAN, method_opt VARCHAR2, degree NUMBER, granularity VARCHAR2, cascade BOOLEAN, stattab VARCHAR2, statid VARCHAR2, statown VARCHAR2, no_invalidate BOOLEAN, force BOOLEAN);
参数说明:
ownname:要分析表的拥有者
tabname:要分析的表名.
partname:分区的名字,只对分区表或分区索引有用.
estimate_percent:采样行的百分比,取值范围[0.000001,100],null为全部分析,不采样. 常量:DBMS_STATS.AUTO_SAMPLE_SIZE是默认值,由oracle决定最佳取采样值.
block_sapmple:是否用块采样代替行采样.
method_opt:决定histograms信息是怎样被统计的.method_opt的取值如下:
for all columns:统计所有列的histograms.
for all indexed columns:统计所有indexed列的histograms.
for all hidden columns:统计你看不到列的histograms
for columns <list> SIZE <N> | REPEAT | AUTO | SKEWONLY:统计指定列的histograms.N的取值范围[1,254]; REPEAT上次统计过的histograms;AUTO由oracle决定N的大小;SKEWONLY multiple end-points with the same value which is what we define by "there is skew in the data
degree:决定并行度.默认值为null.
granularity:Granularity of statistics to collect ,only pertinent if the table is partitioned.
cascace:是收集索引的信息.默认为falase.
stattab指定要存储统计信息的表,statid如果多个表的统计信息存储在同一个stattab中用于进行区分.statown存储统计信息表的拥有者.以上三个参数若不指定,统计信息会直接更新到数据字典.
no_invalidate: Does not invalidate the dependent cursors if set to TRUE. The procedure invalidates the dependent cursors immediately if set to FALSE.
force:即使表锁住了也收集统计信息.
例子:
execute dbms_stats.gather_table_stats(ownname => ‘owner‘,tabname => ‘table_name‘ ,estimate_percent => null ,method_opt => ‘for all indexed columns‘ ,cascade => true);
------------------------------------------------------------------------------------------------------------------------
自从Oracle8.1.5引入dbms_stats包，Experts们便推荐使用dbms_stats取代analyze。 理由如下
dbms_stats可以并行分析
dbms_stats有自动分析的功能(alter table monitor )
analyze 分析统计信息的不准确some times
1,2好理解，且第2点实际上在VLDB中是最吸引人的；3以前比较模糊，看了metalink236935.1 解释，analyze在分析Partition表的时候，有时候会计算出不准确的Global statistics .
原因是，dbms_stats会实在的去分析表全局统计信息（当指定参数）；而analyze是将表分区（局部）的statistics 汇总计算成表全局statistics ,可能导致误差。
SQL> select * from segs, objts where segs.segment_name=objts.object_name;
2851 rows selected.
Execution Plan
----------------------------------------------------------
Plan hash value: 779051904
----------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
----------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 2450 | 528K| 139 (1)| 00:00:02 |
|* 1 | HASH JOIN | | 2450 | 528K| 139 (1)| 00:00:02 |
| 2 | TABLE ACCESS FULL| SEGS | 2355 | 287K| 14 (0)| 00:00:01 |
| 3 | TABLE ACCESS FULL| OBJTS | 30967 | 2903K| 125 (1)| 00:00:02 |
----------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("SEGS"."SEGMENT_NAME"="OBJTS"."OBJECT_NAME")
Statistics
----------------------------------------------------------
1 recursive calls
0 db block gets
674 consistent gets
0 physical reads
0 redo size
228361 bytes sent via SQL*Net to client
2561 bytes received via SQL*Net from client
192 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
2851 rows processed
SQL> select/*+use_merge(segs,objts)*/*from segs, objts where segs.segment_name=objts.object_name;
2851 rows selected.
Execution Plan
----------------------------------------------------------
Plan hash value: 2272228973
-------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes |TempSpc| Cost (%CPU)| Time |
-------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 2450 | 528K| | 822 (1)| 00:00:10 |
| 1 | MERGE JOIN | | 2450 | 528K| | 822 (1)| 00:00:10 |
| 2 | SORT JOIN | | 2355 | 287K| | 15 (7)| 00:00:01 |
| 3 | TABLE ACCESS FULL| SEGS | 2355 | 287K| | 14 (0)| 00:00:01 |
|* 4 | SORT JOIN | | 30967 | 2903K| 8136K| 807 (1)| 00:00:10 |
| 5 | TABLE ACCESS FULL| OBJTS | 30967 | 2903K| | 125 (1)| 00:00:02 |
-------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - access("SEGS"."SEGMENT_NAME"="OBJTS"."OBJECT_NAME")
filter("SEGS"."SEGMENT_NAME"="OBJTS"."OBJECT_NAME")
Statistics
----------------------------------------------------------
1 recursive calls
0 db block gets
487 consistent gets
0 physical reads
0 redo size
248233 bytes sent via SQL*Net to client
2561 bytes received via SQL*Net from client
192 SQL*Net roundtrips to/from client
2 sorts (memory)
0 sorts (disk)
2851 rows processed
SQL> select/*+use_nl(segs,objts)*/*from segs, objts where segs.segment_name=objts.object_name;
2851 rows selected.
Execution Plan
----------------------------------------------------------
Plan hash value: 2045044449
-----------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 2450 | 528K| 4725 (1)| 00:00:57 |
| 1 | NESTED LOOPS | | | | | |
| 2 | NESTED LOOPS | | 2450 | 528K| 4725 (1)| 00:00:57 |
| 3 | TABLE ACCESS FULL | SEGS | 2355 | 287K| 14 (0)| 00:00:01 |
|* 4 | INDEX RANGE SCAN | IDX_OBJTS_NAME | 1 | | 1 (0)| 00:00:01 |
| 5 | TABLE ACCESS BY INDEX ROWID| OBJTS | 1 | 96 | 2 (0)| 00:00:01 |
-----------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - access("SEGS"."SEGMENT_NAME"="OBJTS"."OBJECT_NAME")
Statistics
----------------------------------------------------------
1 recursive calls
0 db block gets
3473 consistent gets
0 physical reads
0 redo size
227906 bytes sent via SQL*Net to client
2561 bytes received via SQL*Net from client
192 SQL*Net roundtrips to/from client
0 sorts (memory)
0 sorts (disk)
2851 rows processed
三种连接方式，SQL数据量、语句相同，最后获取不同的成本消耗。可以看出，当数据量达到万级之后，Nest Loop Join的随机读会急剧增加，带来的CPU成本和总执行时间成本也会大大增加。
而使用Merge Sort Join带来的块读是相对较少，但是付出的CPU成本和执行时间也是不可忽视的。将数据集合排序映射到内存中（可能要利用Temp Tablespace），需要消耗很大的CPU和内存资源（排序段）。
总体来说，Hash Join在这个SQL中还是能带来很好的综合性能的。只有块读稍大，其他指标都是可以接受的最好值。
下面我们介绍与Hash Join相关的一些系统参数，和Hash Join进行的三种操作模式。不同的系统参数，可能会给CBO成本运算带来影响。不同的操作模式，帮助我们理解PGA中的hash_area大小是如何影响到Hash Join操作的性能。
3、Hash Join相关参数
Hash Join是CBO优化器才能生成的执行计划操作，如果是选择了RBO就不能生成包括Hash Join的执行计划。此外，与Hash Join相关的Oracle参数还包括下面几个：
ü Hash_Join_Enable
该参数是控制CBO启用Hash Join的开关。如果设置为True，则表示CBO可以使用Hash Join连接方式，否则就不可以使用。在目前的版本中，该参数已经演化为一个隐含参数，名称为“_hash_join_enable”。
SQL> col name for a20;
SQL> col value for a10;
SQL> col DESCRIB for a30;
SQL> SELECT x.ksppinm NAME, y.ksppstvl VALUE, x.ksppdesc describ
2 FROM SYS.x$ksppi x, SYS.x$ksppcv y
3 WHERE x.inst_id = USERENV (‘Instance‘)
4 AND y.inst_id = USERENV (‘Instance‘)
5 AND x.indx = y.indx
6 AND x.ksppinm LIKE ‘%hash_join_enable%‘;
NAME VALUE DESCRIB
-------------------- ---------- ------------------------------
_hash_join_enabled TRUE enable/disable hash join
ü Hash_Area_Size
Hash Join操作是依赖独立的私有空间，我们称之为Hash_Area。Hash Area在Join过程中的作用就是将连接小表尽可能的缓存在Hash Area中，供进行Hash匹配和Bucket内部精确匹配。Hash Area是贮存在PGA中，属于会话session独立的一块空间。如果Hash Area较小，不足以存放小表全部数据，就会引起Temp表空间的使用，进而影响Hash Join性能。
4、连接三模式
Hash Join比较Merge Sort Join一个比较优势的地方，就是对PGA空间的有限使用上。但是，使用PGA毕竟是一种风险操作。因为Hash Area同Sort Area一样，在小表不能完全装入系统时，会调用Temp表空间的硬盘空间。这样，就会引起一些问题。
下面关于三种模式的阐述，借鉴八神前辈的《Oracle Hash Join》（http://www.alidba.net/index.php/archives/440）。特此表示感谢。
针对不同的状态，Oracle分别有不同的模式对应。
Optimal模式
这是我们进行Hash Join的最理想情况。驱动表（小表）生成的Hash数据集合可以完全存放在Hash Area的时候，我们称之为Optimal模式。
ü 首先找到驱动表，获取到驱动表。存放在Hash_Area中；
ü 在Hash Area中，对驱动表进行Hash操作，形成Hash Bulket，形成对应的分区信息。针对多个Bulket，同时形成一个Bitmap列表，做到Bulket与Bitmap位的联系；
ü 在各个Bulket中，分布着不同的数据行。如果连接列分布比较均匀，Bulket中数据也就比较均匀。如果Bulket中包括数据，对应该Bulket的Bitmap位上为1，否则为0；
ü 找被驱动表的每一列，将连接列值进行Hash处理。匹配Bitmap位，如果Bitmap为0，表示该列值没有存在，直接抛弃。否则进入Bulket进行精确匹配；
Onepass模式
如果我们设置的PGA空间小，或者连接的小表体积就已经很大了，那么就会利用到临时表空间。具体处理，就是进行两次的Hash处理，在Bulket层面的上面建立Partition分区。
当进行Hash操作的时候，出现的情形是一部分的Partition在内存中，另一部分Partition被存放在Temp表空间上。
在进行连接匹配的时候，如果能够在Bitmap中确定到Partition在内存中，那么直接在内存中进行检索和精确匹配过程。否则从Temp表空间中将对应的Partition调取到内存中，进行匹配操作。
Multipass模式
这是一种很极端的情况，如果Hash Area小到一个Partition都装不下。当进行Hash操作后，只有半个Partition能装入到Hash Area。
这种情况下，如果一个Partition匹配没有做到，还不能够放弃操作，要将剩下一半的Partition获取到进行Hash Join匹配。也就是一个Partition要经过两次的Bitmap匹配过程。
5、结论
Hash Join是一种效率很高，CBO时代很常见的连接方式。但是，相对于其他古典算法，Hash Join的综合效率很高，特别在海量数据时代。
Sort merge join、Nested loops、Hash join（三种连接类型）