ITPub博客

首页 > Linux操作系统 > Linux操作系统 > join方法介绍

join方法介绍

原创 Linux操作系统 作者:wengjie_0627 时间:2011-09-21 11:04:03 0 删除 编辑

NESTED LOOP

nested loop:先从驱动表中i/o一条记录,根据这条记录去扫描被驱动表,查找满足join条件的记录,以此循环(所以nested loop对驱动表的每一条记录执行一次I\O,对被驱动表执行最大I\O,数据库的最大I\O由参数db_file_multiblock_read_count决定)

如:

SQL>  select * from employees e join departments d on e.department_id=d.department_id;

  

  分析如上执行计划可知:该join执行nested loops,由employees表作为驱动表,departments表作为被驱动表        

nested loop中哪张表作为驱动表,哪张表作为被驱动表是由优化器来决定的,而不是由select * from employees e join departments d on e.department_id=d.department_id中是employees e join departments d还是departments d join employees e来决定的

如何决定哪张表作为驱动表:一般来说,尽量用小表作为驱动表,但是,当其中一张表有索引时,则用有索引的哪张表作为被驱动表(上面的例子就是因为departments表有索引,所以用其作为被驱动表)

nested loop一般适用于小表连接,并且有索引的情况
嵌套循环原理

 

嵌套循环Nest Loop Join是一种古老的连接方式。SQL中的连接,本质上就是将两个数据集合依据连接条件进行匹配操作。Nest Loop Join就是通过两层循环手段进行依次的匹配操作,最后返回结果集合。SQL语句只是描述出希望连接的对象和规则,而执行计划和执行操作要切实将一行行的记录进行匹配。

 

 

Nest Loop Join的操作过程很简单,很像我们最简单的排序检索算法,两层循环结构。进行连接的两个数据集合(数据表)分别称为驱动表和被驱动表。首先处理驱动表中每一行符合条件的数据,之后每一行数据和被驱动表进行连接匹配操作。最后可以获取到结果集合。

 

 

具体来说,Nest Loop Join的执行过程如下:

 

ü       Oracle CBO首先将一系列的连接关系,拆分为若干层的Nest Loop Join,确定连接顺序。如a.field1=b.field1 and b.field2=c.field2,就可以组织成表A和表B先进行nest loop join操作,之后操作的结果集合再与数据表C进行nest loop join操作。所以,我们查看到的连接操作,通常都是分层次的;

ü       在确定每次Nest Loop Join的两端对象之后,确定驱动表和被驱动表。根据SQL中对驱动表的连接条件,进行筛选。最后获取到驱动表数据集合;

ü       从驱动表每条记录入手,检索被驱动表记录,获取符合连接条件的记录。形成连接行;

 

 

注意:此处有两个需要注意的问题。其一是驱动表的确定。另一个就是检索被驱动表的方法。这两个问题在CBO时代的回答都是成本问题,Oracle通过成本试算获取到。对Nest Loop Join而言,条件列、连接列上的索引是会很大程度上影响执行计划的。

 

下面是一个SQL语句的执行计划,由于CBO操作的复杂性,本SQL使用hint来进行强制的Nest Loop路径。

 

 

SQL> create table tabs as select * from dba_tables;

Table created

 

SQL> create table cols as select owner,table_name, column_name, data_type from dba_tab_cols;

Table created

 

SQL> create index idx_tabs_owner on tabs(owner);

Index created

 

SQL> create index idx_cols_name on cols(table_name);

Index created

 

SQL> set linesize 10000;

SQL> set pagesize 1000;

SQL> explain plan for select /*+use_nl(tabs,cols) */* from tabs, cols where tabs.table_name=cols.tab

le_name and tabs.owner='SCOTT';

 

已解释。

 

SQL> select * from table(dbms_xplan.display);

PLAN_TABLE_OUTPUT

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

Plan hash value: 2834620917

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

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

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

|  0 | SELECT STATEMENT             |               | 1355 |  381K|  360  (0)| 00:00:05 |

|  1 | NESTED LOOPS                |               |      |      |           |         |

|  2 |  NESTED LOOPS               |               | 1355 |  381K|  360  (0)| 00:00:05 |

|  3 |   TABLE ACCESS BY INDEX ROWID| TABS          |  117 | 28314 |    9  (0)| 00:00:01 |

|* 4 |    INDEX RANGE SCAN         | IDX_TABS_OWNER |  117 |      |    1  (0)| 00:00:01 |

|* 5 |   INDEX RANGE SCAN          | IDX_COLS_NAME |   12 |      |    2  (0)| 00:00:01 |

|  6 |  TABLE ACCESS BY INDEX ROWID | COLS          |   12 |  552 |    3  (0)| 00:00:01 |

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

 

Predicate Information (identified by operation id):

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

 

  4 - access("TABS"."OWNER"='SCOTT')

  5 - access("TABS"."TABLE_NAME"="COLS"."TABLE_NAME")

 

已选择19行。

 

 

在执行计划中,伴随着两个Nest Loop Join。首先,通过条件owner=’SCOTT’,检索索引idx_tabs_owner,获取符合条件的rowid列表。之后利用rowidtabs表中取出结果集合。这个集合就成为第一层Nest Loop Join的驱动表

 

被驱动表则是COLS数据表对应的索引IDX_COLS_NAME,进行匹配的条件是table_name相等。第一层Nest Loop Join的结果集合是TABS所有符合条件行字段,外加上对应COLS数据表的rowid

 

第二层Nest Loop Join就是通过获取到的COLS rowid找到COLS记录的全部内容。

 

 

2Nest Loop Join检索图示

 

下面通过一张示意,表达在没有连接列索引的情况下,Nest Loop Join的工作方式。

 

 

在没有索引的情况下,首先Oracle会检索驱动表(全表扫描),获取到符合外侧表单独条件的记录行集合(Row1Row2)。

 

之后针对row1row2,分别对inner表进行全表匹配查询,就是对每个outer的结果行,要进行inner表的所有块查询。最后发现符合条件的row3row4,将结果返回。

 

 

通过图示,我们也可以发现Nest Loop Join的一个致命缺陷:存在大量的随机读。为每一个驱动表的记录,就需要进行被驱动表的全表扫描。如果被驱动表很庞大,那么这个执行计划效率可想而知。

 

 

3、索引优化与Nest Loop Join

 

在目前的Oracle执行计划中,如果驱动表被驱动表均没有索引等优化方式,而且不包含那些很复杂的连接对应条件,出现Nest Loop Join的机会还是很低的。因为Oracle CBO会选择其他替代执行计划(如Hash Join)来参与执行计划。

 

在条件列,特别是连接条件列上添加索引,可以大幅度的减少Nest Loop Join的随机读。见下图示意:

 

 

如果在被驱动的连接条件列上添加索引,在进行Nest Loop Join的时候,Row1/Row2可以直接确定符合连接条件的被驱动表数据行对应的rowid。不需要直接对被驱动表进行检索,就可以获取到rowid了。由于索引对应的体积要远远小于被驱动表,所以进行的块读取要少很多。

 

 

结论:如果确定需要使用嵌套循环Nest Loop Join,那么最好考虑保证连接列上能存在索引对象。这样可以很大程度上提高Nest Loop Join的连接效率。

 

可以使用USE_NL(table_name1 table_name2)可是强制CBO 执行嵌套循环连接。


 

HASH JOIN

hash join是优化器做大数据集连接时的常用方式。优化器扫描小表(或数据源),利用连接键(也就是根据连接字段计算hash 值)在内存中建立hash表,然后扫描大表,每读到一条记录就来探测hash表一次,找出与hash表匹配的行。

Hash Join(哈希连接)原理

 

只有CBO才能使用Hash Join操作。本质上说,Hash Join连接是借助Hash算法,连带小规模的Nest Loop Join,同时利用内存空间进行高速数据缓存检索的一种算法。

 

下面我们分步骤介绍Hash Join算法步骤:

 

  i.       Hash Join连接对象依然是两个数据表,首先选择出其中一个“小表”。这里的小表,就是参与连接操作的数据集合数据量小。对连接列字段的所有数据值,进行Hash函数操作。Hash函数是计算机科学中经常使用到的一种处理函数,利用Hash值的快速搜索算法已经被认为是成熟的检索手段。Hash函数处理过的数据特征是“相同数据值的Hash函数值一定相同,不同数据值的Hash函数值可能相同”;

 ii.       经过Hash处理过的小表连接列,连同数据一起存放到Oracle PGA空间中。PGA中存在一块空间为hash_area,专门存放此类数据。并且,依据不同的Hash函数值,进行划分Bucket操作。每个Bucket中包括所有相同hash函数值的小表数据。同时建立Hash键值对应位图。

iii.       之后对进行Hash连接大表数据连接列依次读取,并且将每个Hash值进行Bucket匹配,定位到适当的Bucket上(应用Hash检索算法);

iv.       在定位到的Bucket中,进行小规模的精确匹配。因为此时的范围已经缩小,进行匹配的成功率精确度高。同时,匹配操作是在内存中进行,速度较Merge Sort Join时要快很多;

 

下面是一个Hash Join的执行计划。

 

 

PLAN_TABLE_OUTPUT

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

Plan hash value: 779051904

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

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

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

|  0 | SELECT STATEMENT  |      | 2617 |  572K|  142  (1)| 00:00:02 |

|* 1 | HASH JOIN        |      | 2617 |  572K|  142  (1)| 00:00:02 |

|  2 |  TABLE ACCESS FULL| SEGS | 2503 |  312K|   16  (0)| 00:00:01 |

|  3 |  TABLE ACCESS FULL| OBJTS | 31083 | 2914K|  126  (1)| 00:00:02 |

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

Predicate Information (identified by operation id):

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

  1 - access("SEGS"."SEGMENT_NAME"="OBJTS"."OBJECT_NAME")

 

 

从原理过程来看,Hash JoinNest Loop Join/Merge Sort Join存在一定相似度。

 

首先,Hash JoinNest Loop Join一样,进行一定的嵌套循环匹配操作,不过差异在于匹配进行随机读的范围是受限范围。不会像Nest Loop Join一样直接频繁进行全表规模的随机读。

 

其次,Hash Join同之前介绍过的Merge Sort Join有相似点,都是利用PGA的空间进行独立操作。Hash Join中的Bucket就是保存在内存的PGA中,有一块专门Hash_Area进行该项操作。选择小表作为驱动连接表,就是尽量争取PGA内存中可以完全装下小表数据,尽量不要使用Temp表空间(当小表可以全部放入内存中,其成本接近全表扫描两个表的成本之和。如果表很大不能完全放入内存,这时优化器会将它分割成若干不同的分区,不能放入内存的部分就把该分区写入磁盘的临时段,此时要有较大的临时段从而尽量提高I/O 的性能。临时段中的分区都需要换进内存做hash join。这时候成本接近于全表扫描小表+分区数*全表扫描大表的代价和。)。这样,进行Hash匹配和精确匹配的速度就是有保证的。

 

 

最后,Hash Join使用的场景是有限制的。其中最大的一个就是连接操作仅能使用=连接。因为Hash匹配的过程只能支持相等操作。还有就是连接列的数据分布要尽量做到数据分布均匀,这样产生的Bucket也会尽可能均匀。这样限制匹配的速度才有保证。如果数据列分布偏移严重,Hash Join算法效率会有退化趋势。

使用hash join时,HASH_AREA_SIZE初始化参数必须足够的大,如果是9i及以上版本,Oracle建议使用SQL工作区自动管理,设置WORKAREA_SIZE_POLICY 为AUTO,然后调整PGA_AGGREGATE_TARGET即可

以下条件下hash join可能有优势:

两个巨大的表之间的连接。

在一个巨大的表和一个小表之间的连接。

SORT MERGE JOIN

sort merge join的操作通常分三步:对连接的每个表做table access full;对table access full的结果进行排序;进行merge join对排序结果进行合并。sort merge join性能开销几乎都在前两步。一般是在没有索引的情况下,9i开始已经很少出现了,因为其排序成本高,大多为hash join替代了

通常情况下hash join的效果都比sort merge join要好,然而如果行源已经被排过序,在执行sort merge join时不需要再排序了,这时sort merge join的性能会优于hash join。

在全表扫描比索引范围扫描再通过rowid进行表访问更可取的情况下,sort merge join会比nested loops性能更佳。

 

可以用USE_HASH(table_name1 table_name2)提示来强制使用散列连接。

Merge Sort Join原理机制

 

Nest Loop Join嵌套循环是一种比较古老的连接匹配方式,特点是通过两层的循环结构,将符合条件的数据行整理出来。嵌套循环的最大缺陷之一,就是伴随着驱动表被驱动表之间的选择,以及大量随机读现象。

 

 

Merge Sort Join连接的优势就是可以一定程度上减少随机读的情况。合并排序连接的最大特征是在一次扫描的同时,就判断连接。不会像Nest Loop Join那样频繁的进行数据读取。使用这种方式的前提,就是连接的两个数据集合必须按照连接列的顺序进行排序。具体操作流程如下:

 

ü       Merge Sort Join连接而言,不存在驱动表和被驱动表的问题。两边的数据集合没有顺序区别,都要进行排序操作;

ü       根据Oracle排序规则和方法,按照连接列的顺序对两个数据集合进行排序;

ü       依次对两边的数据集合进行扫描,由于已经是排序过得结果,可以直接确定连接条件是否匹配;

ü       确定进行连接的两端数据行,再依据筛选列的要求获取数据;

 

下面是一个进行Merge Sort Join的执行计划:

 

//使用Merge Sort Join方法

SQL>select /*+use_merge(segs,tabs)*/* from segs, tabs where segs.segment_name=tabs.table_name;

已选择865行。

 

执行计划

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

Plan hash value: 3475644097

 

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

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

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

|  0 | SELECT STATEMENT   |     |  990 |  354K|      |  144  (2)| 00:00:02 |

|  1 | MERGE JOIN        |     |  990 |  354K|      |  144  (2)| 00:00:02 |

|  2 |  SORT JOIN        |     |  968 |  229K|  712K|   65  (2)| 00:00:01 |

|  3 |   TABLE ACCESS FULL| TABS |  968 |  229K|      |   11  (0)| 00:00:01 |

|* 4 |  SORT JOIN        |     | 2267 |  274K|  824K|   79  (2)| 00:00:01 |

|  5 |   TABLE ACCESS FULL| SEGS | 2267 |  274K|      |   13  (0)| 00:00:01 |

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

Predicate Information (identified by operation id):

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

  4 - access("SEGS"."SEGMENT_NAME"="TABS"."TABLE_NAME")

      filter("SEGS"."SEGMENT_NAME"="TABS"."TABLE_NAME")

统计信息

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

      2010 recursive calls

         0 db block gets

       378 consistent gets

         0 physical reads

         0 redo size

     72346 bytes sent via SQL*Net to client

      1003 bytes received via SQL*Net from client

        59 SQL*Net roundtrips to/from client

        10 sorts (memory)

         0 sorts (disk)

       865 rows processed

 

//使用嵌套循环;

SQL>select /*+use_nl(segs,tabs)*/* from segs, tabs where segs.segment_name=tabs.table_name;

已选择865行。

执行计划

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

Plan hash value: 840690564

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

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

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

|  0 | SELECT STATEMENT  |     |  990 |  354K| 11075  (1)| 00:02:13 |

|  1 | NESTED LOOPS     |     |  990 |  354K| 11075  (1)| 00:02:13 |

|  2 |  TABLE ACCESS FULL| TABS |  968 |  229K|   11  (0)| 00:00:01 |

|* 3 |  TABLE ACCESS FULL| SEGS |    1 |  124 |   11  (0)| 00:00:01 |

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

Predicate Information (identified by operation id):

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

  3 - filter("SEGS"."SEGMENT_NAME"="TABS"."TABLE_NAME")

统计信息

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

      1930 recursive calls

         0 db block gets

     43978 consistent gets

         0 physical reads

         0 redo size

     70556 bytes sent via SQL*Net to client

      1003 bytes received via SQL*Net from client

        59 SQL*Net roundtrips to/from client

         6 sorts (memory)

         0 sorts (disk)

       865 rows processed

 

 

上面代码示例中给出了两个执行计划,给我们如下的信息。

 

首先,我们观察使用use_merge提示的SQL,在Hint的作用下,CBO生成的执行计划中使用Merge Sort Join连接方式。在执行计划中Oracle对两个数据表进行Sort操作,之后对排序过的结果进行Merge连接。其中Oracle对两个数据表进行的都是全表扫描操作。

 

 

另一个执行计划是使用use_nl控制的Nest Loop Join连接方式。中间同样也是没有使用索引等方式。其中,产生了大量逻辑读。见下表对比:

 

对比项目

Merge Sort Join

NestLoopJoin

逻辑读consistent gets

378

43978

排序空间sort

10

6

 

通过数据信息的对比,我们可以明显的看出两个相同结果集合的SQL,由于不同的连接方式而带来的差异。Merge Sort Join可以大大消除由于Nest Loop Join带来的随机读过多的情况。而由于进行的排序操作,Merge Sort Join也要付出相应的排序空间损耗。

 

2Merge Sort Join与排序空间

 

Oracle熟悉的朋友们通常对SortGroup操作是比较敏感的。SortGroup by都是需要单独对数据集进行的操作,要消耗额外的CPU和内存资源。CPU资源主要消耗在算法排序和结果集合整合上。而内存资源的消耗更加需要关注,排序操作要在专门的PGA排序区内完成。如果PGA中特定的排序大小(pga_aggregat_target:sort_area_size)不足以进行排序操作,也就是说需要排序分组的数据集合特别大的时候,Oracle需要调用Temp表空间的容量来进行操作。

 

 

这也就是问题的所在。Temp表空间数据存储位于磁盘中,速度与内存相差很多。所以,当进行排序操作的数据集合很大,会出现性能急剧的下降可能。在实际业务场景中,对海量数据集合的处理、Data Warehouse应用的操作,都可能出现这种情况。

 

回到Merge Sort Join来,就可以理解这种连接方式的缺陷之处了。要进行Merge Sort Join,其中的Sort过程不可避免。而使用Sort操作带来的优势就是不需要进行过多的随机读。在数据集合量很大的时候,Merge Sort Join的效率可能会很差。

 

 

3、对索引路径的借用

 

Nest Loop Join中,对连接列进行索引处理,可以很大程度上提升执行计划效率,减少随机读的数量。道理就是借用了索引排序这个现实。而Merge Sort Join对索引的应用效果远不如Nest Loop Join

 

索引环境构建:

 

//索引构建

SQL> create index idx_tabs_name on tabs(table_name);

Index created

 

SQL> create index idx_segs_name on segs(segment_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,'TABS',cascade => true);

PL/SQL procedure successfully completed

 

 

执行计划如下:

 

 

SQL> explain plan for select/*+use_merge(tabs,segs)*/* from segs,tabs where segs.segment_name=tabs.table_name;

Explained

 

SQL> select * from table(dbms_xplan.display);

PLAN_TABLE_OUTPUT

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

Plan hash value: 3475644097

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

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

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

|  0 | SELECT STATEMENT   |     |  990 |  354K|      |  144  (2)| 00:00:

|  1 | MERGE JOIN        |     |  990 |  354K|      |  144  (2)| 00:00:

|  2 |  SORT JOIN        |     |  968 |  229K|  712K|   65  (2)| 00:00:

|  3 |   TABLE ACCESS FULL| TABS |  968 |  229K|      |   11  (0)| 00:00:

|* 4 |  SORT JOIN        |     | 2267 |  274K|  824K|   79  (2)| 00:00:

|  5 |   TABLE ACCESS FULL| SEGS | 2267 |  274K|      |   13  (0)| 00:00:

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

Predicate Information (identified by operation id):

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

  4 - access("SEGS"."SEGMENT_NAME"="TABS"."TABLE_NAME")

      filter("SEGS"."SEGMENT_NAME"="TABS"."TABLE_NAME")

18 rows selected

 

 

由于Merge Sort Join本身就带有排序的特性,而且返回的结果集合中包括所有字段。所以通常的执行计划中,即使连接列存在索引,也不会进入到执行计划中。除非进行一些特定列处理。

 

 

SQL> explain plan for select/*+use_merge(tabs,segs)*/segs.segment_name,tabs.table_namefrom segs,tabs where segs.segment_name=tabs.table_name;

Explained

 

SQL> select * from table(dbms_xplan.display);

PLAN_TABLE_OUTPUT

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

Plan hash value: 712326860

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

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

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

|  0 | SELECT STATEMENT      |              |  990 | 37620 |    9 (23)| 00

|  1 | MERGE JOIN           |              |  990 | 37620 |    9 (23)| 00

|  2 |  SORT JOIN           |              |  968 | 17424 |    4 (25)| 00

|  3 |   INDEX FAST FULL SCAN| IDX_TABS_NAME |  968 | 17424 |    3  (0)| 00

|* 4 |  SORT JOIN           |              | 2267 | 45340 |    5 (20)| 00

|  5 |   INDEX FAST FULL SCAN| IDX_SEGS_NAME | 2267 | 45340 |    4  (0)| 00

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

Predicate Information (identified by operation id):

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

  4 - access("SEGS"."SEGMENT_NAME"="TABS"."TABLE_NAME")

      filter("SEGS"."SEGMENT_NAME"="TABS"."TABLE_NAME")

18 rows selected

 

 

在对返回结果进行处理的情况下,索引路径会出现的。

 

 

可以使用USE_MERGE(table_name1 table_name2)来强制使用排序合并连接.

 

 

因为要对两个表进行排序,而排序操作是一个非常耗CPU的操作,所以一般不常看到MERGE SORT JOIN,只有在如下情况下才会用到MERGE SORT JOIN:

  1.不等值连接

  2.该语句中本身就有order by等需要执行排序的语句

 

 

4、结论

 

Merge Sort Join是一种古老经典的排序模型,类似于数据结构时代的合并排序算法。Merge Sort Join引入的最大优势是避免同Nest Loop Join类似的大量随机读现象,但是同时也引入了Sort空间变化的问题。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/24984814/viewspace-708008/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 两表连接语法
下一篇: hash join详解
请登录后发表评论 登录
全部评论

注册时间:2011-05-19

  • 博文量
    50
  • 访问量
    27749