精华内容
下载资源
问答
  • 本文翻译自Coding-Geek文章:《 How does a relational database work》。原文链接:... 本文翻译了如下章节, 介绍数据库查询优化器的循环嵌套连接的实现原理: 连接操作-Join operators 通过...

    本文翻译自Coding-Geek文章:《 How does a relational database work》。原文链接:http://coding-geek.com/how-databases-work/#Buffer-Replacement_strategies

    本文翻译了如下章节, 介绍数据库查询优化器的循环嵌套连接的实现原理:

    这里写图片描述

    连接操作-Join operators

    通过上一章的学习,我们已知如何获取数据,现在我们来做数据的连接。

    下面我将介绍3中常用的数据库表连接操作:归并连接、哈希连接和循环嵌套连接

    在此之前我需要介绍两个新名词内连接对象(inner relation)和外连接对象(outer relation)。连接的对象可以是:
    1. 一张表
    2. 一个索引
    3. 前一次操作产生的中间结果(例如:前一个连接产生的结果)。

    当你连接两个对象时,不同的算法管理这两个连接对象的方式有很大差异。后面的章节,我们假设:
    1. 外连接对象是参与连接的左数据集(译者注:表、视图等)。
    2. 内连接对象是右数据集。

    例如:A连接B,A是左数据集,B是右数据集。大多数情况,A连接B与B连接A的代价是一样的。

    在这一章节,我假定A集合中有N个元素,B集合有M个元素。数据库在数据统计阶段已经计算出了A和B包含的数据条数。Notes:N和M是连接操作的基数。

    循环嵌套连接-Nested loop join

    循环嵌套连接是最简单的一种连接操作(译者注:笛卡尔积)。

    这里写图片描述

    其基本思想是:
    1. 循环遍历外连接对象的每一条记录。
    2. 查找内连接对象的所有记录,看是否存在匹配的记录(做连接操作)。

    它的伪码是这样的:

    nested_loop_join(array outer, array inner)
      for each row a in outer
        for each row b in inner
          if (match_join_condition(a,b))
            write_result_in_output(a,b)
          end if
        end for
       end for

    因为它是两层for循环,时间复杂度是O(N*M)。

    考虑磁盘I/O的开销, 对外连接对象的N条记录的每一条,内层循环都需要读取内连接对象的M条记录。这个算法总共需要从磁盘读取N+N*M条记录。但是,如果内连接对象的数据量很小,可以把它的数据一次性读到内存,这样就仅需要读取M+N条记录。

    基于这种方式,内连接对象必须是最小的一个数据集合,这样它就有更大可能性一次加载到内存中。

    考虑时间开销,哪个做内连接对象都没有差异;但考虑磁盘I/O的话,两个连接对象最好都只读取一次。当然,内连接对象可以用索引代替,这样可以从磁盘读取更少的数据(性能自然更好)。

    这个算法非常简单,这里提供算法的另外一种实现方式;它在内连接对象集太大而不能全部加载到内存的情况下,尽可能的减少磁盘I/O开销。其基本思路是这样的:
    1. 不使用从两个连接集合中逐条读取数据的方式。
    2. 你可以从两个对象集中批量读取两捆数据到内存(译者注:比如说一次读取一万条)。
    3. 比较两捆数据中数据,并保存匹配的数据结果。
    4. 然后加载新的两捆数据到内存做比较。
    5. 继续做这样的操作直到所有的数据比较完。

    下面是算法伪码:

    // improved version to reduce the disk I/O.
    nested_loop_join_v2(file outer, file inner)
      for each bunch ba in outer
      // ba is now in memory
        for each bunch bb in inner
            // bb is now in memory
            for each row a in ba
              for each row b in bb
                if (match_join_condition(a,b))
                  write_result_in_output(a,b)
                end if
              end for
           end for
        end for
       end for
    

    这种算法实现,时间复杂度不会变,但是磁盘I/O降下来了。
    1. 前一种算法种需要访问N+N*M次磁盘,因为每读取一条记录就要访问一次磁盘。
    2. 后一种算法,磁盘的访问次数变成了number_of_bunches_for(outer)+ number_of_ bunches_for(outer)* number_of_ bunches_for(inner)。
    3. 如果你增加每捆数据的条数(译者注:增加每一次读取的数据条数),访问磁盘的次数还会降低(译者注:视内存大小而定。超过一定阈值后性能反而降低,实际开发经验是一次拿2000条数据)。

    展开全文
  • nested loop 连接(循环嵌套连接)指的是两个表连接时, 通过两层嵌套循环来进行依次的匹配, 最后得到返回结果集的表连接方法.  假如下面的 sql 语句中表 T1 和 T2 的连接方式是循环嵌套连接, T1 是驱动表 select ...
    一. nested loop 原理
    

    nested loop 连接(循环嵌套连接)指的是两个表连接时, 通过两层嵌套循环来进行依次的匹配, 最后得到返回结果集的表连接方法. 

    假如下面的 sql 语句中表 T1 和 T2 的连接方式是循环嵌套连接, T1 是驱动表
    select *
    from T1, T2
    where T1.id = T2.id and T1.name = 'David';
    那么将上述 sql 语句翻译为伪码应该如下所示:.
    for each row in (select * from T1 where name = 'David') loop
    for (select * from T2 where T2.id = outer.id) loop
    If match then pass the row on to the next step
    If no match then discard the row
    end loop
    end loop

    具体来说, 如果上述 sql 语句执行循环嵌套连接的话, 那么实际的执行过程应该如下所示:
    (1) 首先 oracle 会根据一定的规则(根据统计信息的成本计算或者 hint 强制)决定哪个表是驱动表, 哪个表是被驱动表 (假设 T1 是驱动表)
    (2) 查询驱动表 "select * from T1 where name = 'David'" 然后得到驱动结果集 Q1
    (3) 遍历驱动结果集 Q1 以及被驱动表 T2, 从驱动结果集 Q1 中取出一条记录, 接着遍历 T2 并按照连接条件 T2.id = T1.id 去判断 T2 中是否存在匹配的记录, 如果能够匹配则保留, 不能匹配则忽略此行, 然后再从 Q1 中取出下一条记录, 接着遍历 T2 进行匹配, 如此下去直到取完 Q1 中的所有记录


    二. nested loop 特性


    嵌套循环连接有以下特性:

    (1) 通常 sql 语句中驱动表只访问一次, 被驱动表访问多次
    (2) 不必等待处理完成所有行前可以先返回部分已经处理完成的数据
    (3) 在限制条件以及连接条件列上建立索引, 能够提高执行效率
    (4) 支持所有类型的连接 (等值连接, 非等值连接, like 等)


    构造试验数据
    SQL> CREATE TABLE t1 (
      2    id NUMBER NOT NULL,
      3    n NUMBER,
      4    pad VARCHAR2(4000),
      5    CONSTRAINT t1_pk PRIMARY KEY(id)
      6  );
    
    Table created.
    
    SQL> CREATE TABLE t2 (
      2    id NUMBER NOT NULL,
      3    t1_id NUMBER NOT NULL,
      4    n NUMBER,
      5    pad VARCHAR2(4000),
      6    CONSTRAINT t2_pk PRIMARY KEY(id),
      7    CONSTRAINT t2_t1_fk FOREIGN KEY (t1_id) REFERENCES t1
      8  );
    
    Table created.
    
    SQL> CREATE TABLE t3 (
      2    id NUMBER NOT NULL,
      3    t2_id NUMBER NOT NULL,
      4    n NUMBER,
      5    pad VARCHAR2(4000),
      6    CONSTRAINT t3_pk PRIMARY KEY(id),
      7    CONSTRAINT t3_t2_fk FOREIGN KEY (t2_id) REFERENCES t2
      8  );
    
    Table created.
    SQL> CREATE TABLE t4 (
      2    id NUMBER NOT NULL,
      3    t3_id NUMBER NOT NULL,
      4    n NUMBER,
      5    pad VARCHAR2(4000),
      6    CONSTRAINT t4_pk PRIMARY KEY(id),
      7    CONSTRAINT t4_t3_fk FOREIGN KEY (t3_id) REFERENCES t3
      8  );
    
    
    Table created.
    
    SQL> execute dbms_random.seed(0)
    
    PL/SQL procedure successfully completed.
    
    
    SQL> INSERT INTO t1 SELECT rownum, rownum, dbms_random.string('a',50) FROM dual CONNECT BY level <= 10 ORDER BY dbms_random.random;
    
    10 rows created.
    
    SQL> INSERT INTO t2 SELECT 100+rownum, t1.id, 100+rownum, t1.pad FROM t1, t1 dummy ORDER BY dbms_random.random;
    
    100 rows created.
    
    SQL> INSERT INTO t3 SELECT 1000+rownum, t2.id, 1000+rownum, t2.pad FROM t2, t1 dummy ORDER BY dbms_random.random;
    
    1000 rows created.
    
    SQL> INSERT INTO t4 SELECT 10000+rownum, t3.id, 10000+rownum, t3.pad FROM t3, t1 dummy ORDER BY dbms_random.random;
    
    10000 rows created.
    
    SQL> COMMIT;
    
    Commit complete.

    使用 hint 让 sql 语句通过 nested loop 连接, 并且指定 t3 为驱动表
    SQL> select /*+ leading(t3) use_nl(t4) */ * from t3, t4
      2  where t3.id = t4.t3_id and t3.n = 1100;
    
    10 rows selected.
    
    SQL> select * from table(dbms_xplan.display_cursor(null,null,'allstats last'));
    
    PLAN_TABLE_OUTPUT
    ---------------------------------------------------------------------------------------------
    ---------------------------------------------------------------------------------------------
    
    SQL_ID  89hnfwqakjghg, child number 0
    -------------------------------------
    select /*+ leading(t3) use_nl(t4) */ * from t3, t4 where t3.id =
    t4.t3_id and t3.n = 1100
    
    Plan hash value: 1907878852
    
    -------------------------------------------------------------------------------------
    | Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
    -------------------------------------------------------------------------------------
    |   0 | SELECT STATEMENT   |      |      1 |        |     10 |00:00:00.01 |     121 |
    |   1 |  NESTED LOOPS      |      |      1 |     10 |     10 |00:00:00.01 |     121 |
    |*  2 |   TABLE ACCESS FULL| T3   |      1 |      1 |      1 |00:00:00.01 |      16 |
    |*  3 |   TABLE ACCESS FULL| T4   |      1 |     10 |     10 |00:00:00.01 |     105 |
    -------------------------------------------------------------------------------------
    
    Predicate Information (identified by operation id):
    ---------------------------------------------------
    
       2 - filter("T3"."N"=1100)
       3 - filter("T3"."ID"="T4"."T3_ID")

    在执行计划中我们可以看到驱动表 T3 访问一次, 因为驱动表上有谓词条件 t3.n = 1100, 通过执行谓词条件后驱动结果集的记录数为 1, 所以 T4 也只访问一次(starts 列)

    使用 hint 让 sql 语句通过 nested loop 连接, 并且指定 t4 为驱动表

    SQL> select /*+ leading(t4) use_nl(t3) full(t4) full(t3) */ * from t3, t4
      2  where t3.id = t4.t3_id and t3.n = 1100;
    
    SQL> select * from table(dbms_xplan.display_cursor(null,null,'allstats last'));
    
    PLAN_TABLE_OUTPUT
    ----------------------------------------------------------------------------------------------------------
    ----------------------------------------------------------------------------------------------------------
    SQL_ID  0yxm1muqwrfq2, child number 0
    -------------------------------------
    select /*+ leading(t4) use_nl(t3) full(t4) full(t3) */ * from t3, t4
    where t3.id = t4.t3_id and t3.n = 1100
    
    Plan hash value: 3886808168
    
    -------------------------------------------------------------------------------------
    | Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
    -------------------------------------------------------------------------------------
    |   0 | SELECT STATEMENT   |      |      1 |        |     10 |00:00:00.25 |     150K|
    |   1 |  NESTED LOOPS      |      |      1 |     10 |     10 |00:00:00.25 |     150K|
    |   2 |   TABLE ACCESS FULL| T4   |      1 |  10000 |  10000 |00:00:00.01 |     105 |
    |*  3 |   TABLE ACCESS FULL| T3   |  10000 |      1 |     10 |00:00:00.21 |     150K|
    -------------------------------------------------------------------------------------
    
    Predicate Information (identified by operation id):
    ---------------------------------------------------
    
       3 - filter(("T3"."N"=1100 AND "T3"."ID"="T4"."T3_ID"))
    在执行计划中我们可以看到驱动表 T4 访问一次, 因为驱动表上 T4 结果集的记录数为 10000, 所以 T4 访问了 10000 次, buffers 和 A-time(实际执行时间) 都比较高.


    三. nested loop 优化

    在 nested loop 被驱动表上的连接列上 (T4 表的 t3_id 列) 建立索引 
    SQL> CREATE INDEX t4_t3_id ON t4(t3_id);
    
    Index created.
    
    SQL> select /*+ leading(t3) use_nl(t4) */ * from t3, t4
      2  where t3.id = t4.t3_id and t3.n = 1100;
    
    10 rows selected.
    
    SQL> select * from table(dbms_xplan.display_cursor(null,null,'allstats last'));
    
    PLAN_TABLE_OUTPUT
    ------------------------------------------------------------------------------------------------------------------------------------
    ------------------------------------------------------------------------------------------------------------------------------------
    
    SQL_ID  89hnfwqakjghg, child number 0
    -------------------------------------
    select /*+ leading(t3) use_nl(t4) */ * from t3, t4 where t3.id =
    t4.t3_id and t3.n = 1100
    
    Plan hash value: 2039660043
    
    ------------------------------------------------------------------------------------------------------------
    | Id  | Operation                    | Name     | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  |
    ------------------------------------------------------------------------------------------------------------
    |   0 | SELECT STATEMENT             |          |      1 |        |     10 |00:00:00.01 |      29 |   1 |
    |   1 |  NESTED LOOPS                |          |      1 |        |     10 |00:00:00.01 |      29 |   1 |
    |   2 |   NESTED LOOPS               |          |      1 |     10 |     10 |00:00:00.01 |      19 |   1 |
    |*  3 |    TABLE ACCESS FULL         | T3       |      1 |      1 |      1 |00:00:00.01 |      16 |   0 |
    |*  4 |    INDEX RANGE SCAN          | T4_T3_ID |      1 |     10 |     10 |00:00:00.01 |       3 |   1 |
    |   5 |   TABLE ACCESS BY INDEX ROWID| T4       |     10 |     10 |     10 |00:00:00.01 |      10 |   0 |
    ------------------------------------------------------------------------------------------------------------
    
    Predicate Information (identified by operation id):
    ---------------------------------------------------
    
       3 - filter("T3"."N"=1100)
       4 - access("T3"."ID"="T4"."T3_ID")
    在执行计划中可以看到在被驱动表上的连接列上加上索引后, buffer 从 121 下降到了 29

    在驱动表的谓词条件列上 (T3 表的 n 列) 加上索引
    SQL> create index t3_n on t3(n);
    
    Index created.
    
    SQL> select /*+ leading(t3) use_nl(t4) */ * from t3, t4
      2  where t3.id = t4.t3_id and t3.n = 1100;
    
    10 rows selected.
    
    SQL> select * from table(dbms_xplan.display_cursor(null,null,'allstats last'));
    
    PLAN_TABLE_OUTPUT
    -------------------------------------------------------------------------------------------------------------------------------------
    -------------------------------------------------------------------------------------------------------------------------------------
    
    SQL_ID  89hnfwqakjghg, child number 0
    -------------------------------------
    select /*+ leading(t3) use_nl(t4) */ * from t3, t4 where t3.id =
    t4.t3_id and t3.n = 1100
    
    Plan hash value: 2304842513
    
    -------------------------------------------------------------------------------------------------------------
    | Id  | Operation                     | Name     | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  |
    -------------------------------------------------------------------------------------------------------------
    |   0 | SELECT STATEMENT              |          |      1 |        |     10 |00:00:00.01 |      17 |   1 |
    |   1 |  NESTED LOOPS                 |          |      1 |        |     10 |00:00:00.01 |      17 |   1 |
    |   2 |   NESTED LOOPS                |          |      1 |     10 |     10 |00:00:00.01 |       7 |   1 |
    |   3 |    TABLE ACCESS BY INDEX ROWID| T3       |      1 |      1 |      1 |00:00:00.01 |       4 |   1 |
    |*  4 |     INDEX RANGE SCAN          | T3_N     |      1 |      1 |      1 |00:00:00.01 |       3 |   1 |
    |*  5 |    INDEX RANGE SCAN           | T4_T3_ID |      1 |     10 |     10 |00:00:00.01 |       3 |   0 |
    |   6 |   TABLE ACCESS BY INDEX ROWID | T4       |     10 |     10 |     10 |00:00:00.01 |      10 |   0 |
    -------------------------------------------------------------------------------------------------------------
    
    Predicate Information (identified by operation id):
    ---------------------------------------------------
    
       4 - access("T3"."N"=1100)
       5 - access("T3"."ID"="T4"."T3_ID")
    在执行计划中可以看到在驱动表上的谓词条件列上加上索引后, buffer 从 29 继续下降到了 17

    四. 小结

    由此可见, 在 sql 调优时如果遇到表的连接方式是 nested loop:

    首先,要确保结果集小的表为驱动表,结果集多的表为被驱动表。这不意味着记录多的表不能作为驱动表, 只要通过谓词条件过滤后得到的结果集比较小,也可以作为驱动表。

    其次,在驱动表的谓词条件列以及被驱动表的连接列上加上索引,能够显著的提高执行性能

    最后,如果要查询的列都在索引中,避免回表查询列信息时,又将进一步提高执行性能。



    展开全文
  • 【mysql优化 3】嵌套循环连接算法

    千次阅读 2017-08-02 21:10:53
    循环嵌套连接算法: 一个简单的嵌套循环连接(NLJ:nested-loop jon)算法,每一次运用一个循环从第一个表里读取行,通过每一行去嵌套循环连接第二个表。这个过程被重复了多次,因为还有剩余的待连接的表。 假设使用...

    原文地址:Nested-Loop Join Algorithms

    mysql在表之间执行连接操作,包括了使用循环嵌套算法或者其他在此基础上的变形。

     

    循环嵌套连接算法:

    一个简单的嵌套循环连接(NLJ:nested-loop jon)算法,每一次运用一个循环从第一个表里读取行,通过每一行去嵌套循环连接第二个表。这个过程被重复了多次,因为还有剩余的待连接的表。

    假设使用以下连接类型来执行三个表t1,t2和t3之间的连接:

    Table Join Type

    t1 range

    t2 ref

    t3 ALL

     

    如果使用一个简单的NL算法,那么连接过程如下:

    for each row in t1 matching range {
      for each row in t2 matching reference key {
        for each row in t3 {
          if row satisfies join conditions, send to client
        }
      }
    }

    因为NLJ算法一次将一行从外部循环传递到内部循环,所以通常会在内部循环中多次读取处理的表。

     

    块循环嵌套连接算法:

    块嵌套循环(BNL)连接算法使用在外部循环中读取行的缓冲来减少内部循环中的表必须被读取的次数。例如:如果有10行被读取到了缓冲区,并将缓冲区传递到下一个内循环,则可以将内循环中读取的每行与缓冲区中的所有10行进行比较。这将减少内表必须读取的次数

    Mysql的连接缓冲区有以下特点:

    1,连接缓存可以被使用,当join的类型为:All、index、range。在外连接中使用缓冲区,也被描述在:Block Nested-Loop and Batched Key Access Joins

    2,绝不会为第一个非常数表分配一个缓冲区,尽管它是All或者index类型

    3,仅会把连接中必要的列存入它的连接缓存,而不是整行数据

    4,连接缓存的大小的系统变量定义了每一个被用于查询的连接缓存的大小

    5,每一个可以被缓存的连接都会被分配一个缓冲区,所以,一个查询可以会需要使用几个连接缓存

    6,一个缓存区在它执行连接之前建立,而在查询结束后释放

     

    例如:之前的NLJ算法(没有缓存),通过缓存,这个连接会像下面所描述的一样被执行:

    for each row in t1 matching range {
      for each row in t2 matching reference key {
        store used columns from t1, t2 in join buffer
        if buffer is full {
          for each row in t3 {
            for each t1, t2 combination in join buffer {
              if row satisfies join conditions, send to client
            }
          }
          empty join buffer
        }
      }
    }


    if buffer is not empty {
      for each row in t3 {
        for each t1, t2 combination in join buffer {
          if row satisfies join conditions, send to client
        }
      }

    }

     

    如果,S是每一个t1的存储大小,t2是连接缓存的组合,C是在缓存中组合的数量,t3扫描的次数是:

    (S * C)/join_buffer_size + 1

     

    随着join_buffer_size的值增加,t3扫描的数量减少,直到join_buffer_size足够大以容纳所有以前的行组合。但是,尽管join_buffer_size足够大,但是它并没有变得更快!

    展开全文
  •  今天我将介绍在SQLServer 中的三种连接操作符类型,分别是:循环嵌套、哈希匹配和合并连接。主要对这三种连接的不同、复杂度用范例的形式一一介绍。  本文中使用了示例数据库AdventureWorks ,下面是下载地址:...

     

      今天我将介绍在SQLServer 中的三种连接操作符类型,分别是:循环嵌套、哈希匹配和合并连接。主要对这三种连接的不同、复杂度用范例的形式一一介绍。

      本文中使用了示例数据库AdventureWorks ,下面是下载地址:http://msftdbprodsamples.codeplex.com/releases/view/4004

    简介:什么是连接操作符

      连接操作符是一种算法类型,它是SQLServer优化器为了实现两个数据集合之间的逻辑连接选择的操作符。优化器可以基于请求查询、可用索引、统计信息和估计行数等不同的场景为每一套数据选择不同的算法

      通过查看执行计划可以发现操作符如何被使用。接下来我们看一下如何具体使用。

    NESTED LOOPS(循环嵌套)

      我们通过下面的例子来展示一下(查询2001年7月份的数据):

    SELECT
    OH.OrderDate, OD.OrderQty, OD.ProductID, OD.UnitPrice
    FROM
    Sales.SalesOrderHeader AS OH
    JOIN
    Sales.SalesOrderDetail AS OD
    ON
    OH.SalesOrderID = OD.SalesOrderID
    WHERE
    OH.OrderDate BETWEEN '2001-07-01' AND '2001-07-31'

     

    执行计划的结果如下:

    join types 1 exec plan

    图右上方的叫“outer input”,在其下面的叫做“inner input” 

    本质上讲,“Nested Loops”操作符就是:为每一个记录的外部输入找到内部输入的匹配行。

    技术上讲,这意味着外表聚集索引被扫描获取外部输入相关的记录,然后内表聚集索引查找每一个匹配外表索引的记录。

    我们可以通过把鼠标放在聚集索引扫描操作符上面来验证这个信息,请看这个tooltip:

    join types 2 details

    看这个执行的估计行数是1,索引查找tooltip如下:

    join types 3 details

    这次发现执行的估计行数是179,这是很接近返回的外部输入行的。

    按照复杂度计算(假设N是外部输出的行数,M是总行数在SalesOrderDetai表的):查询复杂度是O(NlogM),这里logM是在内部输入表的每次查找的复杂度。

    当外部输入比较小并且内部输入有索引在连接的字段上的时候SQLServer 优化器更喜欢选择这种操作符类型(Nested Loop)。外部和内部输入的数据行差距越大,这个操作符提供的性能越高。

    MERGE Join(合并连接)

    “Merge”算法是连接两个较大且按序存储的在连接键上最有效的方式。请看一下下面这个查询例子(查询返回用户和销售表的ID):

     

    SELECT
    OC.CustomerID, OH.SalesOrderID
    FROM
    Sales.SalesOrderHeader AS OH
    JOIN
    Sales.Customer AS OC
    ON
    OH.CustomerID = OC.CustomerID

     

    查询执行计划如下:

    join types 4 exec plan

    • 首先我们注意到两套数据是在CustomerID上是有序的:因为聚集索引是有序的且在SalesorderHeader表上该字段是非聚集索引。
    • 根据在操作符的箭头(鼠标放在上面),我们能看到每个返回结果行数都是很大的。
    • 除此之外,在On 的子句后面要用=操作符。

    就是这三个因素会导致优化器选择Merge Join查询操作符。 

     

    使用这种连接操作符的最大的性能就是两个输入操作符执行一次。我们能把鼠标放在两个数据的上面看一下执行的次数都是1,也就是说算法是很有效率的。

    合并连接同时读取两个输入然后比较他们。如果匹配就返回,否则,行数较小的被放弃,因为两边输入是有序的。放弃的行不再匹配任何行。

    知道其中一个表完毕一直重复匹配,即使另一个表还有数据,那么最大的时间复杂的消耗就是两个表完全不同键值,那么最大的复杂度就是: O(N+M)。

    HASH Match(哈希匹配)

    “Hash”连接是我们称为 “the go-to guy” 的操作符。当其他连接操作符都不支持的场景时,就会选择这种操作符。比如当表恰好不排序,或者没有索引时。当优化器选择这种操作符,一般来说可能是我们没有做好一些基础工作(例如,加索引)。但是有些情况(复杂查询)没有别的方式,只能选择它。

    请看下面这个查询(获取contacts 表中姓和名中以“John”开始的包含销售的ID字段的数据集):

     

    SELECT
    OC.FirstName, OC.LastName, OH.SalesOrderID
    FROM
    Sales.SalesOrderHeader AS OH
    JOIN
    Person.Contact AS OC
    ON
    OH.ContactID = OC.ContactID
    WHERE
    OC.FirstName LIKE 'John%'

     

    The execution plan looks like this:

    join types 5 exec plan

    由于ContactID列没有索引,所以选择哈希操作符。

    在深入理解这个例子之前,介绍两个重要的概念:一个是“Hashing”函数,一个是“Hash Table”。

    函数是一个程序性函数,它接收1或者多个值然后转换他们为一个符号值(通常是数字)。这个函数通常是单向的,意味着不能反转回来原始值,但是确定性保证如果你提供了相同的值,符号值是完全一样的。也就是说,几个不同的输入值,可以有相同的Hash值。

    “Hash Table”是一个数据结构,把所有行都放到一个相同尺寸的桶里面。每一个桶代表一个哈希值。这意味着当你激活函数的行,使用结果你就会知道它属于哪个桶。

    利用统计信息,SQLServer 会选择较小的两个数据输入来提供构造输入,并且输入被用来在内存中创建哈希表。如果没有足够的内存,在tempdb中会使用物理磁盘。在哈希表建立后,SQLServer将从较大的表中得到数据,叫做探测输入。利用哈希匹配函数与哈希表比较,然后返回匹配行。在图形执行计划中,构造输入的查询在上面,探测输入的查询在下面。

    只要较小的表非常小,这个算法就是非常有效的。但是如果两个表都非常大,这可能是非常低效的执行计划。

    查询Hints

    利用Hints,破事SQLServer使用指定的连接类型。但是强烈不推荐这么做,尤其在生产环境,因为没有永恒的最佳选择(因为数据在变化),并且优化器通常是正确的。

    添加OPTION 子句作为查询的结尾,使用关键字LOOP JOINMERGE JOIN 或者 HASH JOIN可以强制执行连接。

    看看如何实现:

     

    SELECT OC.CustomerID, OH.SalesOrderID
    FROM Sales.SalesOrderHeader AS OH
    JOIN Sales.Customer AS OC
    ON OH.CustomerID = OC.CustomerID
    OPTION (HASH JOIN)
    
    SELECT OC.FirstName, OC.LastName, OH.SalesOrderID
    FROM Sales.SalesOrderHeader AS OH
    JOIN Person.Contact AS OC
    ON OH.ContactID = OC.ContactID
    WHERE OC.FirstName LIKE 'John%'
    OPTION (LOOP JOIN)
    
    SELECT OC.FirstName, OC.LastName, OH.SalesOrderID
    FROM Sales.SalesOrderHeader AS OH
    JOIN Person.Contact AS OC
    ON OH.ContactID = OC.ContactID
    WHERE OC.FirstName LIKE 'John%'
    OPTION (MERGE JOIN)

     

    总结

    Nested Loops

    • 复杂度: O(NlogM)。
    • 其中一个表很小的时候。
    • 较大的表允许使用索引查找连接字段。

    Merge Join

    • 复杂度: O(N+M)。
    • 两个输入的连接字段是有序的。
    • 使用=操作符
    • 适合非常大的表

    Hash Match

    • 复杂度: O(N*hc+M*hm+J)
    • 最后默认的操作符
    • 使用哈希表和动态哈希匹配函数匹配行

         本篇随笔详细介绍了三种链接操作符和它们的触发机制,当然这些也都是动态的,就像前面说的没有最佳的操作符,只有最合适的,要根据实际请款选择不同的操作符。

    展开全文
  • 嵌套循环连接

    千次阅读 2013-11-09 10:52:57
    这里介绍一下嵌套循环 (Nested Loops 简称NL) 的连接方式。   嵌套循环,顾名思义就是将一个表为出发点,将该表全部记录逐条去遍历另外一张表的记录,符合条件的就是写入结果集。  www.2cto.com   例如: ...
  • Mysql算法内部算法 - 嵌套循环连接算法1.循环连接算法// 循环连接算法分为两种 1.嵌套循环连接算法 2.块嵌套循环连接算法2.嵌套循环连接算法一个简单的嵌套循环连接(NLJ)算法从一个循环中的第一个表中读取一行中的...
  • 一个简单的循环嵌套连接(NLJ)算法一次循环读取一行数据在第一张表中,通过每一行都嵌套循环处理与下一张表连接。这个过程被重复多次直到其他的多有表都被连接。 假设一个涉及到三张表t1,t2,t3的连接被执行通过如下的...
  • 连接三剑客(嵌套循环连接,哈希连接,排序合并连接) 1.表连接的定义: 例子1:有一个特别的舞会,男孩子集中在一个房间,女孩子集中在另外一个房间,舞池设置在两个房间中间. 开始跳舞时,从男孩子中选出一个à然后进入...
  • oracle 嵌套循环连接

    千次阅读 2014-12-30 16:06:12
    我这里收集了oracle 嵌套循环连接几篇文章,仅供学习参考!! 梅森上校博客: http://blog.csdn.net/seagal890/article/details/33419949 realkid4博客: http://blog.itpub.net/17203031/viewspace-696917/ ...
  • 嵌套循环连接(Nested Loops Join)是一种两个表在做表连接时依靠两层嵌套循环(分别为外层循环和内存循环)来得到连接结果集的表连接方法。即外层循环对应的驱动结果集有多少条记录,遍历被驱动表的内层循环就要做...
  • Oracle表连接方法有四种: ● 排序合并连接(Sort Merge Join) ● 嵌套循环连接(Nested Loops Join) ● 哈希连接(Hash Join) ● 笛卡尔积(Cart...
  • SQL server 内部实现了三种类型的内连接运算,大多数人从来没有听说过这些连接类型,因为它们不是逻辑连接也很少被用于代码中。那么它们什么时候会被用到呢?答案是要依情况而定。这就意味着要依赖于记录集和索引。...
  • 目录第八章 优化(八)—— 嵌套循环连接算法8.2 优化SQL语句8.2.1 优化 SELECT 语句8.2.1.7 嵌套循环连接算法嵌套循环连接算法块嵌套循环连接算法 第八章 优化(八)—— 嵌套循环连接算法 8.2 优化SQL语句 8.2.1 ...
  • 一、前言:对于一名有志于成为SQL调优的开发人员或SQL的DBA,就很有必要了解下ORACLE数据库在对两个表进行连接时的运行机制,因为再复杂的执行计划也是每次分解成两个表的连接去执行的。ORACLE数据库有常见的三种...
  • 作为众多菜鸟中的一员,虽然无数次的写SQL语句,但是从来只知道有哈希链接,但是从来没有使用过,链接只是使用无数老师和教科书教的: select a.id from a,b where a...一嵌套循环连接: SQL:select a.ac_id from tes
  • 嵌套循环连接,哈希连接,排序合并连接 -->>嵌套循环连接 select * from /*+leading(t1) use_nl(t2)*/ from t1,t2 where t1.id=t2.t1_id and t1.n=19; 这个HINT的含义:leading(t1)表示强制先访问表t1,...
  • 多核处理器中基于Radix-Join的嵌套循环连接优化.pdf
  • jsp foreach 循环 嵌套外层函数

    千次阅读 2016-12-29 16:57:25
    ${report[colKey.key]} 既是 ${report....1. ${“report.”concat(colKey.key)}--------表示${'report.name'}='report.name字符串---------------------字符串连接 2.${report[colKey.key]} []运算级优先 rep
  • 1)外连接消除 ①外连接简介 1)LEFT JOIN / LEFT OUTER JOIN:左外连接 左向外连接的结果集包括:LEFT OUTER子句中指定的左表的所有行,而不仅仅是连接列所匹配的行。如果左表的某行在右表中没有匹配行,则...
  • 标签关联集合循环嵌套问题

    千次阅读 2016-11-25 15:15:40
    最近,在项目中用到标签在jsp页面做信息展示,关于各种属性意义这里就不多说了,这里介绍一下我遇到的循环嵌套问题。
  • 循环嵌套使用案例 案例1.打印五行小星星 row = 1 while row # 每一行要打印的小星星数量和当前行数是一样的 # 增加一个小循环,专门负责当前行中,每一列的小星星输出 col = 1 while col print("*", end=...
  • 嵌套循环(Nestloop Join)是在两个表连接时一种连接方式。在嵌套循环中,内表被外表驱动,外表返回的每一行都要在内表中检索找到与它匹配的行,因此整个查询返回的结果集不能太大,要把返回子集较小的表作为外表,...
  • MySQL查询优化之五-嵌套循环连接算法(Nested-Loop Join Algorithms) 如需转载请标明出处:http://blog.csdn.net/itas109 QQ技术交流群:12951803 环境: MySQL版本:5.5.15 操作系统:windows 本文讨论嵌套...
  • 连接涉及到两个表A和B,通俗的讲嵌套循环链接相当于遍历A中的每一条记录(满足A表条件),然后再在B表中遍历记录直至找到匹配的记录,等同于两层循环。而哈希链接和排序合并,可以看作是先各自处理自身的记录(排序...
  • 当一条SQL语句引用多张表连接时,Oracle的查询优化器(Optimizer)不仅
  • oracle嵌套循环连接外部表和内部表的识别SQL> create table a1 as select * from all_objects ;Table createdSQL> select count(*) from a1; COUNT(*)---------- 49708SQL> create table a2 as select * from a1 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 93,365
精华内容 37,346
关键字:

循环嵌套连接