oracle 表连接 - hash join 哈希连接

luyj

一. hash 连接(哈希连接)原理

指的是两个表连接时, 先利用两表中记录较少的表在内存中建立 hash 表, 然后扫描记录较多的表并探测 hash 表, 找出与 hash 表相匹配的行来得到结果集的表连接方法. 哈希连接只能用于等值连接条件(=)。


假设下面的 sql 语句中表 T1 和 T2 的连接方式是哈希连接, T1 是驱动表


    select *  
    from T1, T2  
    where T1.id = T2.id and T1.name = 'David';  

oracle 执行步骤如下:

1  计算 hash partition 的数量 (分区数量)
    这个数字由 hash_area_size, db_block_size, _hash_multiblock_io_count 的值来决定

    hash partition 是一个逻辑上的概念, 它由多个 hash bucket 组成, 而一个 hash table 又由多个 hash partition 组成. hash partition 是 I/O 单位, 当 hash table 过大时, 以 hash partition 为单位写出到磁盘; hash bucket 是 hash 运算映射的单位, 可以把 hash bucket 想象为一个链表.
   

2  构建驱动结果集 S 的 hash table

      2.1 遍历驱动结果集, 计算 hash 值

      根据谓词条件(T1.name = 'David') 过滤驱动表 T1 的数据, 得到驱动结果集 S. 读取 S 中的每一条数据, 并根据连接列(T1.id)做 hash 运算.
      oracle 采用两种 hash 算法进行计算, S 中的每一条记录都会得到两个哈希值记为 hash_value_1, hash_value_2.

      2.2 存储数据到 hash partition

      oracle 按照 hash_value_1 的值把驱动结果集 S 的记录映射存储在不同的 hash partition 中不同 hash bucket 里, 存储在 hash bucket 中的内容包括 sql 中的查询列, 连接列以及 hash_value_2 的值.
      我们把驱动结果集 S 所对应的每一个 hash partition 记为 S.

      2.3 构建位图
      这个位图用来标记 S 所包含的每一个 hash bucket 是否有记录

      2.4 如果驱动结果集 S 数据量很大, 则将数据交换到磁盘上(temp 表空间)

      如果驱动结果集 S 的数据量很大, 构建 S 对应的 hash table 时就会造成 PGA中的 hash_area_szie 被填满, 这时候 oracle 会把 hash area 中记录数最多的 hash partition 写到磁盘上. 重复步骤 2.1 - 2.4 直至读取数据完毕.
      另外, 在构建 S 对应的 hash table 时, 如果记录对应的 hash partition 已经被写到磁盘上, oracle 就会将 sql 中的查询列, 连接列以及hash_value_2 的值写到已经位于磁盘上的 hash partition 中不同 hash bucket 里.

      2.5 排序
      对驱动结果集 S 的 hash partition 根据记录数多少进行排序

3 遍历被驱动结果集 B

      3.1 遍历驱动结果集 B 及位图过滤

      把被驱动结果集 (T2) 记为 B, 读取 B 中的每一条记录, 并按照连接列(T2.id)做 hash 运算, 同步骤 (2) 一样得到两个哈希值 hash_value_1, hash_value_2. oracle 根据这个 hash_value_1 去 S 匹配 hash bucket,

    如果能够找到匹配的 bucket, 则进一步比较连接列是否相等, 如果相等, 则将记录 join 后返回; 如果不相等, 则舍弃;
    如果找不到匹配的 bucket, 就会去访问 2.3 中构建的位图,   

          (1) 如果位图显示该 hash bucket 在 S 中对应的记录数大于 0, 则说明该 hash bucket 虽然不在内存中, 但实际上是被写到了磁盘上, 此时 oracle 会按照 hash_value_1 的值把被驱动结果集 B 的记录映射存储在磁盘上一个新的 hash partition 中的 hash bucket, 存储在 hash bucket 中的内容包括 sql 中的关于 B 的查询列, 连接列以及 hash_value_2 的值;
          (2) 如果位图显示该 hash bucket 在 S 中对应的记录数等于 0, 则说明这条记录不符合连接连接需舍弃.

      【这个位图决定是否将 hash_value_1 所对应 B 中的记录写回到磁盘的动作就是所谓的位图过滤】

      我们将 B 所对应的每一个 hash partition 记为 B[j]。遍历完 B 中的所有记录, 构建 B[j] 完毕.

      3.2  再次构建 hash table
      现在 oracle 已经处理完成内存中的 S 和 B[j], 只剩下磁盘上的 S 和 B[j] 还未处理.

      由于构建 S 和 B[j] 使用的相同的 hash 函数, 只有对应 hash partition number 相同的 S 和 B[j] 才有可能满足连接条件, 所以处理磁盘上的 S 和 B[j] 只需处理 hash partition number 相同的 S 和 B[j].


      对于每一对相同 hash partition number 的 S 和 B[j], oracle 会选择记录数较少的当作驱动结果集, 同时根据 hash bucket 中 hash_value_2 构建新的 hash table, 记录数较多的当作被驱动结果集根据 hash_value_2 去匹配, 如果匹配成功, 则返回记录, 匹配不成功则丢弃.

   

     【对于每一对相同 hash partition number 的 S 和 B[j], oracle 会选择记录数较少的当作驱动结果集, 所以每一对相同 hash partition number 的 S 和 B[j] 的驱动结果集都可能发生变化, 这就是动态角色互换】

   

      处理完每一对相同 hash partition number 的 S 和 B[j] 后, 哈希连接处理完成.

二. hash 连接特性


1. hash 连接只能用在等值连接条件

2. 驱动表的选择对执行效率及性能有影响

3. 驱动表和被驱动表最多被访问一次


构造测试数据



    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.  

比较 hash 连接, nested loops 连接, sort merge join 连接



    SQL> select * from t3, t4 where t3.id = t4.t3_id;  
      
      
    10000 rows selected.  
      
      
    Execution Plan  
    ----------------------------------------------------------  
    Plan hash value: 1396201636  
      
      
    ---------------------------------------------------------------------------  
    | Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |  
    ---------------------------------------------------------------------------  
    |   0 | SELECT STATEMENT   |      | 10000 |  1250K|    35   (3)| 00:00:01 |  
    |*  1 |  HASH JOIN         |      | 10000 |  1250K|    35   (3)| 00:00:01 |  
    |   2 |   TABLE ACCESS FULL| T3   |  1000 | 63000 |     5   (0)| 00:00:01 |  
    |   3 |   TABLE ACCESS FULL| T4   | 10000 |   634K|    29   (0)| 00:00:01 |  
    ---------------------------------------------------------------------------  
      
      
    Predicate Information (identified by operation id):  
    ---------------------------------------------------  
      
      
       1 - access("T3"."ID"="T4"."T3_ID")  
      
      
      
    Statistics  
    ----------------------------------------------------------  
              0  recursive calls  
              0  db block gets  
            779  consistent gets  
              0  physical reads  
              0  redo size  
        1376470  bytes sent via SQL*Net to client  
           7745  bytes received via SQL*Net from client  
            668  SQL*Net roundtrips to/from client  
              0  sorts (memory)  
              0  sorts (disk)  
          10000  rows processed  
      
      
    SQL> select /*+ leading(t3) use_nl(t4) */* from t3, t4 where t3.id = t4.t3_id;  
      
      
    10000 rows selected.  
      
    Execution Plan  
    ----------------------------------------------------------  
    Plan hash value: 2039660043  
      
      
    -----------------------------------------------------------------------------------------  
    | Id  | Operation                    | Name     | Rows  | Bytes | Cost (%CPU)| Time     |  
    -----------------------------------------------------------------------------------------  
    |   0 | SELECT STATEMENT             |          | 10000 |  1250K| 11007   (1)| 00:02:13 |  
    |   1 |  NESTED LOOPS                |          |       |       |            |          |  
    |   2 |   NESTED LOOPS               |          | 10000 |  1250K| 11007   (1)| 00:02:13 |  
    |   3 |    TABLE ACCESS FULL         | T3       |  1000 | 63000 |     5   (0)| 00:00:01 |  
    |*  4 |    INDEX RANGE SCAN          | T4_T3_ID |    10 |       |     1   (0)| 00:00:01 |  
    |   5 |   TABLE ACCESS BY INDEX ROWID| T4       |    10 |   650 |    11   (0)| 00:00:01 |  
    -----------------------------------------------------------------------------------------  
      
      
    Predicate Information (identified by operation id):  
    ---------------------------------------------------  
      
      
       4 - access("T3"."ID"="T4"."T3_ID")  
      
      
    Statistics  
    ----------------------------------------------------------  
              0  recursive calls  
              0  db block gets  
          12605  consistent gets  
              0  physical reads  
              0  redo size  
         342258  bytes sent via SQL*Net to client  
           7745  bytes received via SQL*Net from client  
            668  SQL*Net roundtrips to/from client  
              0  sorts (memory)  
              0  sorts (disk)  
          10000  rows processed  
      
      
    SQL> select /*+ leading(t3) use_merge(t4) */* from t3, t4 where t3.id = t4.t3_id;  
      
      
    10000 rows selected.  
      
    Execution Plan  
    ----------------------------------------------------------  
    Plan hash value: 3831111046  
      
      
    ------------------------------------------------------------------------------------  
    | Id  | Operation           | Name | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |  
    ------------------------------------------------------------------------------------  
    |   0 | SELECT STATEMENT    |      | 10000 |  1250K|       |   193   (2)| 00:00:03 |  
    |   1 |  MERGE JOIN         |      | 10000 |  1250K|       |   193   (2)| 00:00:03 |  
    |   2 |   SORT JOIN         |      |  1000 | 63000 |       |     6  (17)| 00:00:01 |  
    |   3 |    TABLE ACCESS FULL| T3   |  1000 | 63000 |       |     5   (0)| 00:00:01 |  
    |*  4 |   SORT JOIN         |      | 10000 |   634K|  1592K|   187   (1)| 00:00:03 |  
    |   5 |    TABLE ACCESS FULL| T4   | 10000 |   634K|       |    29   (0)| 00:00:01 |  
    ------------------------------------------------------------------------------------  
      
      
    Predicate Information (identified by operation id):  
    ---------------------------------------------------  
      
      
       4 - access("T3"."ID"="T4"."T3_ID")  
           filter("T3"."ID"="T4"."T3_ID")  
      
      
    Statistics  
    ----------------------------------------------------------  
              0  recursive calls  
              0  db block gets  
            119  consistent gets  
              0  physical reads  
              0  redo size  
         344114  bytes sent via SQL*Net to client  
           7745  bytes received via SQL*Net from client  
            668  SQL*Net roundtrips to/from client  
              2  sorts (memory)  
              0  sorts (disk)  
          10000  rows processed  

从上面的执行计划可以看出:

	排序次数	逻辑读	CPU Time
hash join	0	779	00：01
nested loops	0	12605	02：13
merge join	2	119	00：03

可见，oracle 引入的 hash 连接, 能够解决嵌套循环连接中大量随机读的问题, 同时解决了排序合并连接中排序代价过大的问题.

三. hash 连接优化
    SQL> alter session set statistics_level=ALL;  
    SQL> select /*+ leading(t3) use_hash(t4) */* from t3, t4 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  f57pu4khtptsc, child number 0  
    -------------------------------------  
    select /*+ leading(t3) use_hash(t4) */* from t3, t4 where t3.id =  
    t4.t3_id and t3.n = 1100  
      
      
    Plan hash value: 1396201636  
      
      
    ----------------------------------------------------------------------------------------------------------------  
    | Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |  
    ----------------------------------------------------------------------------------------------------------------  
    |   0 | SELECT STATEMENT   |      |      1 |        |     10 |00:00:00.03 |     120 |       |       |          |  
    |*  1 |  HASH JOIN         |      |      1 |     10 |     10 |00:00:00.03 |     120 |   737K|   737K|  389K (0)|  
    |*  2 |   TABLE ACCESS FULL| T3   |      1 |      1 |      1 |00:00:00.01 |      15 |       |       |          |  
    |   3 |   TABLE ACCESS FULL| T4   |      1 |  10000 |  10000 |00:00:00.01 |     105 |       |       |          |  
    ----------------------------------------------------------------------------------------------------------------  
      
      
    Predicate Information (identified by operation id):  
    ---------------------------------------------------  
      
      
       1 - access("T3"."ID"="T4"."T3_ID")  
       2 - filter("T3"."N"=1100)  

在表 T3 的谓词条件(n)上增加索引


    SQL> create index t3_n on t3(n);  
      
      
    Index created.  
      
      
    SQL> select /*+ leading(t3) use_hash(t4) */* from t3, t4 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  f57pu4khtptsc, child number 0  
    -------------------------------------  
    select /*+ leading(t3) use_hash(t4) */* from t3, t4 where t3.id =  
    t4.t3_id and t3.n = 1100  
      
      
    Plan hash value: 2452410886  
      
      
    --------------------------------------------------------------------------------------------------------------------------  
    | Id  | Operation                    | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |  
    --------------------------------------------------------------------------------------------------------------------------  
    |   0 | SELECT STATEMENT             |      |      1 |        |     10 |00:00:00.03 |     108 |       |       |          |  
    |*  1 |  HASH JOIN                   |      |      1 |     10 |     10 |00:00:00.03 |     108 |   737K|   737K|  389K (0)|  
    |   2 |   TABLE ACCESS BY INDEX ROWID| T3   |      1 |      1 |      1 |00:00:00.01 |       3 |       |       |          |  
    |*  3 |    INDEX RANGE SCAN          | T3_N |      1 |      1 |      1 |00:00:00.01 |       2 |       |       |          |  
    |   4 |   TABLE ACCESS FULL          | T4   |      1 |  10000 |  10000 |00:00:00.01 |     105 |       |       |          |  
    --------------------------------------------------------------------------------------------------------------------------  
      
      
    Predicate Information (identified by operation id):  
    ---------------------------------------------------  
      
      
       1 - access("T3"."ID"="T4"."T3_ID")  
       3 - access("T3"."N"=1100)  

从执行计划中可以看出 buffers 从 120 下降为 108， 可见谓词条件上的索引能够减少 hash 连接的逻辑读


接下来，看看在等值连接条件下，小表(小的结果集)为驱动表，hash 连接和 nested loop 嵌套循环连接


    SQL> select * from t3, t4 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  c204pd6srpjfq, child number 0  
    -------------------------------------  
    select * 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 |  
    ---------------------------------------------------------------------------------------------------  
    |   0 | SELECT STATEMENT             |          |      1 |        |     10 |00:00:00.01 |      29 |  
    |   1 |  NESTED LOOPS                |          |      1 |        |     10 |00:00:00.01 |      29 |  
    |   2 |   NESTED LOOPS               |          |      1 |     10 |     10 |00:00:00.01 |      19 |  
    |*  3 |    TABLE ACCESS FULL         | T3       |      1 |      1 |      1 |00:00:00.01 |      16 |  
    |*  4 |    INDEX RANGE SCAN          | T4_T3_ID |      1 |     10 |     10 |00:00:00.01 |       3 |  
    |   5 |   TABLE ACCESS BY INDEX ROWID| T4       |     10 |     10 |     10 |00:00:00.01 |      10 |  
    ---------------------------------------------------------------------------------------------------  
      
      
    Predicate Information (identified by operation id):  
    ---------------------------------------------------  
      
      
       3 - filter("T3"."N"=1100)  
       4 - access("T3"."ID"="T4"."T3_ID")  
      
      
    SQL> select * from t3, t4 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  c204pd6srpjfq, child number 0  
    -------------------------------------  
    select * 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")  

从上面的执行计划中可以看出, 采用 nested loops 嵌套循环连接的 CPU 0.03 降为 0.01, buffers 从 108 降为 17, 因此，在等值连接条件且在连接列条件上有索引, 如果返回的数据量较少, 适合用嵌套循环连接; 如果返回的数据量比较大, 则适合用 hash 连接。

四. 小结

在大多数的情况下, 哈希连接的效率比嵌套循环连接和排序合并连接更高：

1. 哈希连接可能比嵌套循环连接快，因为处理内存中的哈希表比检索B树更加迅速。

2. 哈希连接可能比排序合并连接更快，因为这种情况下，只有一张源表需要排序，而且只是对 hash partition 排序。在排序合并连接中，两张表的数据都需要先做排序，然后做MERGE操作，因此效率相对最差。


hash 连接很适合一大一小的结果集连接返回大数据量的情形, 特别是 hash table 能够全部放在 hash area 的情况下, 这时候哈希连接的执行时间可以近似看做是全表扫描两个结果集的时间之和.


在 sql 调优时, 如果遇到表的连接方式是 hash 连接, 进行优化可以考虑以下几点：

1. 确认小结果集为驱动结果集

2. 如果有谓词条件, 考虑在谓词条件上增加索引

3. 确认涉及到的表和连接列被分析过, 如果连接列上的数据分布不均匀, 考虑在此列上收集直方图
4. 增加 hash_area_size 大小, 使哈希连接只在内存就能完成, 即保证 PGA hash area 能够容纳 hash 运算