Semi Join 의 재조명

예전에 Hash Join Right (Semi/Anti/Outer) 의 용도 라는 글에서 서브쿼리가 Semi Join 으로 적용될때 조인의 순서를 바꿀수 있는 방법에 대하여 설명한바 있다. 이어서 오늘도 예전글과 유사한 Semi Join 의 튜닝에 대해서 이야기 하려 한다.

환경 : Oracle 11.1.0.6
먼저 테이블을 단순한 구조로 만들기 위해서 테이블을 2개 생성한다.
ORACLE 의 Sample 스키마인 SH 를 이용한다.

CREATE TABLE SALES_T AS SELECT * FROM sh.sales;

CREATE TABLE PRODUCTS_T AS SELECT * FROM sh.products ;

ALTER TABLE PRODUCTS_T ADD CONSTRAINT PK_PRODUCTS_T         --> PK 및 인덱스 생성
PRIMARY KEY (PROD_ID) USING INDEX;

CREATE BITMAP INDEX SALES_T_PROD_BIX ON SALES_T (PROD_ID);  --> BIT MAP 인덱스 생성

dbms_stats.gather_table_stats(user,'SALES_T',cascade=>true);
dbms_stats.gather_table_stats(user,'PRODUCTS_T',cascade=>true);

이제 SQL 을 실행할 준비가 다 되었다.
아래는 상품의 Category 가 Software/Other 인 제품의 상품코드별, 채널별 판매량을 나타낸 SQL 이다.
이러한 SQL 은 주로 DW 에서 나타난다.

SELECT /*+ GATHER_PLAN_STATISTICS QB_NAME(MAIN) */
            s.prod_id, s.channel_id, SUM (quantity_sold) AS qs, SUM (amount_sold) AS amt
   FROM sales_t s
 WHERE s.prod_id IN (SELECT /*+ QB_NAME(SUB) */
                                             p.prod_id
                                   FROM products_t p
                                 WHERE p.prod_category_desc = 'Software/Other')
GROUP BY s.prod_id, s.channel_id ;

--------------------------------------------------------------------------
| Id  | Operation           | Name       | Starts |   A-Time   | Buffers |
--------------------------------------------------------------------------
|   1 |  HASH GROUP BY      |            |      1 |00:00:08.12 |    4445 |
|*  2 |   HASH JOIN         |            |      1 |00:00:06.94 |    4445 |
|*  3 |    TABLE ACCESS FULL| PRODUCTS_T |      1 |00:00:00.01 |       4 |
|   4 |    TABLE ACCESS FULL| SALES_T    |      1 |00:00:01.84 |    4441 |
--------------------------------------------------------------------------

헉 8초 이상 걸렸다!
Subquery Unnesting 이 발생하여 작은쪽 테이블인 Products_t 가 Driving 테이블로 선정되었고 Salse_t 테이블과 Hash Join 을 하게된다. Scan 한 블럭수는 4445블럭 이며 8초 이상 수행되었다. 조인건수(Starts 항목 참조)는 1회에 불과하다. 이것은 최적으로 튜닝된 SQL 인가?  이것을 알아보기 위해 Hash Join 대신 Nested Loop 조인으로 바꿔보자.

  SELECT /*+ GATHER_PLAN_STATISTICS */
               prod_id, channel_id, SUM (qs) AS qs, SUM (amt) amt
    FROM (SELECT /*+ NO_MERGE USE_NL(PR S) */
                            s.prod_id, s.channel_id,
                            quantity_sold AS qs, amount_sold AS amt
                  FROM sales_t s, products_t pr
                 WHERE s.prod_id = pr.prod_id
                     AND pr.prod_category_desc = 'Photo')
GROUP BY prod_id, channel_id ;

원본 SQL 의 경우 왠만해서는 Nested Loop Join 으로 바뀌지 않으므로 강제로 서브쿼리를 From 절로 끌어 올려서 Nested Loop Join 으로 유도 하였다.

------------------------------------------------------------------------------------
| Id |Operation                       |Name            |Starts|   A-Time   |Buffers|
------------------------------------------------------------------------------------
|  1 | HASH GROUP BY                  |                |    1 |00:00:10.07 |   3099|
|  2 |  VIEW                          |                |    1 |00:00:08.92 |   3099|
|  3 |   NESTED LOOPS                 |                |    1 |00:00:07.70 |   3099|
|  4 |    NESTED LOOPS                |                |    1 |00:00:02.03 |     41|
|* 5 |     TABLE ACCESS FULL          |PRODUCTS_T      |    1 |00:00:00.01 |      4|
|  6 |     BITMAP CONVERSION TO ROWIDS|                |   26 |00:00:00.41 |     37|
|* 7 |      BITMAP INDEX SINGLE VALUE |SALES_T_PROD_BIX|   26 |00:00:00.01 |     37|
|  8 |    TABLE ACCESS BY INDEX ROWID |SALES_T         |  405K|00:00:02.45 |   3058|
------------------------------------------------------------------------------------ 

Hash Join 보다 더 느려졌다
Nested Loop Join 으로 유도 하자 인덱스는 제대로 사용하였지만 비효율이 극심하게 드러난다. 먼저 Nested Loop Join 이 40만번 이상 수행된다.(Starts항목 참조) 그결과로 View 를 만드는데 8초 이상 수행되었다. Buffer 가 30% 이상 줄어들었지만 조인건수 때문에 시간이 많이 걸리므로 이것은 견딜수 없는 결과이다.

그럼 Hash Join 에 만족해야 하나?
지금까지의 상식으로는 그렇다. 하지만 Driving Semi Join 기법을 사용한다면 생각이 달라질것이다.

Driving Semi Join 이란?
Driving Semi Join 이란 Semi Join 의 변형된 형태로서 Hash Join 의 장점(조인건수의 최소화)과 Nested Loop Join 의 장점(선행테이블이 상수화 되어 후행 테이블에서 인덱스를 효율적으로 사용) 을 합친 개념이다. 물론 Driving Semi Join 이라는 Title 자체의 의미대로 Semi Join 이 Driving 집합이 되는것은 당연하다. 다음의 SQL 을 보자  

SELECT /*+ GATHER_PLAN_STATISTICS QB_NAME(MAIN) SEMIJOIN_DRIVER(@SUB) */
             s.prod_id, s.channel_id, SUM (quantity_sold) AS qs, SUM (amount_sold) AS amt
   FROM sales_t s
WHERE s.prod_id IN (SELECT /*+ QB_NAME(SUB) */
                                          p.prod_id
                                FROM products_t p
                               WHERE p.prod_category_desc = 'Photo')
GROUP BY s.prod_id, s.channel_id ;

----------------------------------------------------------------------------------
| Id | Operation                     |Name            |Starts|   A-Time  |Buffers|
----------------------------------------------------------------------------------
|   1|  HASH GROUP BY                |                |     1|00:00:03.40|   2231|
|   2|   TABLE ACCESS BY INDEX ROWID |SALES_T         |     1|00:00:02.04|   2231|
|   3|    BITMAP CONVERSION TO ROWIDS|                |     1|00:00:00.42|     63|
|   4|     BITMAP MERGE              |                |     1|00:00:00.02|     63|
|   5|      BITMAP KEY ITERATION  |                |     1|00:00:00.02|     63|
|*  6|       TABLE ACCESS FULL       |PRODUCTS_T      |     1|00:00:00.01|      4|
|*  7|       BITMAP INDEX RANGE SCAN |SALES_T_PROD_BIX|    26|00:00:00.02|     59|
----------------------------------------------------------------------------------

환상적이다
Hash Join (8초 이상), Nested Loop Join (10초 이상) 인데 반하여 Driving Semi Join 은 3.4초 만에 끝이 났다. 또한 조인횟수도 26 번에 불과하며 I/O Block 수도 2231 로 Hash Join 의 절반에 해당한다.

환상적인 이유는?
그 이유는 Join 대신에 BITMAP KEY ITERATION 이 수행된 까닭이다.
BITMAP KEY ITERATION 의 원리는 INLIST ITERATOR Operation 과 같다고 볼수 있다. 
INLIST ITERATOR 의 개념은 InList / Concatnation / Range Scan Control 하기 을 참조하라.

Driving Semi Join은 B-Tree 인덱스에서도 사용이 가능해
이기능은 Bit Map 인덱스 뿐만 아니라 B-Tree 인덱스 에서도 사용가능하다.
하지만 _b_tree_bitmap_plans 파라미터가 True 로 되어 있어야 한다.
아래의 SQL 을 보자.

DROP INDEX SALES_T_PROD_BIX;  --> Bit Map 인덱스 Drop

CREATE INDEX SALES_T_PROD_IX ON HR.SALES_T (PROD_ID); --> B-Tree 인덱스 생성

ALTER SESSION SET  "_b_tree_bitmap_plans" = TRUE;

SELECT /*+ GATHER_PLAN_STATISTICS QB_NAME(MAIN) SEMIJOIN_DRIVER(@SUB) */
     s.prod_id, s.channel_id, SUM (quantity_sold) AS qs,
     SUM (amount_sold) AS amt
FROM sales_t s
WHERE s.prod_id IN (SELECT /*+ QB_NAME(SUB) */
                          p.prod_id
                     FROM products_t p
                    WHERE p.prod_category_desc = 'Photo')
GROUP BY s.prod_id, s.channel_id;

-------------------------------------------------------------------------------------
| Id |Operation                          |Name           |Starts|   A-Time  |Buffers|
-------------------------------------------------------------------------------------
|   1| HASH GROUP BY                     |               |     1|00:00:04.94|   3045|
|   2|  TABLE ACCESS BY INDEX ROWID      |SALES_T        |     1|00:00:03.76|   3045|
|   3|   BITMAP CONVERSION TO ROWIDS     |               |     1|00:00:02.14|    877|
|   4|    BITMAP MERGE                   |               |     1|00:00:01.73|    877|
|   5|     BITMAP KEY ITERATION          |               |     1|00:00:01.73|    877|
|*  6|      TABLE ACCESS FULL            |PRODUCTS_T     |     1|00:00:00.01|      4|
|   7|      BITMAP CONVERSION FROM ROWIDS|               |    26|00:00:01.73|    873|
|*  8|       INDEX RANGE SCAN            |SALES_T_PROD_IX|    26|00:00:00.86|    873|
-------------------------------------------------------------------------------------

Bit Map 인덱스에 비하여 약간의 비효율이 있다. 그것은 BITMAP CONVERSION FROM ROWIDS Operation 이 추가되었기 때문이다. 하지만 기존의 Hash Join 이나 Nested Loop Join 보다는 수행시간, I/O Block 수, 조인건수등이 우월함을 알수 있다.

당신은 이미 Driving Semi Join을 사용했다
여러분의 SQL 이 Star Transformation 을 수행하는 경우는 싫든 좋든 Driving Semi Join 기능을 이용하고 있는 것이다. 아래는 Star Transformation 을 수행하는 SQL 의 Plan 과 Outline Data 를 출력한 것이다.

  SELECT /*+ gather_plan_statistics */
         p.prod_id,
         c.CHANNEL_ID,
         SUM (quantity_sold) AS qs,
         SUM (amount_sold) AS amt
    FROM sh.sales s, sh.CHANNELS c, sh.products p
   WHERE s.CHANNEL_ID = c.CHANNEL_ID
     AND c.CHANNEL_DESC = 'Internet'
     AND s.prod_id = p.prod_id
     AND p.prod_category_desc = 'Photo'
GROUP BY p.prod_id, c.CHANNEL_ID;

------------------------------------------------------------------+
| Id  | Operation                              | Name             |
------------------------------------------------------------------+
| 0   | SELECT STATEMENT                       |                  |
| 1   |  HASH GROUP BY                         |                  |
| 2   |   HASH JOIN                            |                  |
| 3   |    TABLE ACCESS FULL                   | CHANNELS         |
| 4   |    HASH JOIN                           |                  |
| 5   |     TABLE ACCESS FULL                  | PRODUCTS         |
| 6   |     PARTITION RANGE ALL                |                  |
| 7   |      TABLE ACCESS BY LOCAL INDEX ROWID | SALES            |
| 8   |       BITMAP CONVERSION TO ROWIDS      |                  |
| 9   |        BITMAP AND                      |                  |
| 10  |         BITMAP MERGE                   |                  |
| 11  |          BITMAP KEY ITERATION          |                  |
| 12  |           BUFFER SORT                  |                  |
| 13  |            TABLE ACCESS FULL           | CHANNELS         |
| 14  |           BITMAP INDEX RANGE SCAN      | SALES_CHANNEL_BIX|
| 15  |         BITMAP MERGE                   |                  |
| 16  |          BITMAP KEY ITERATION          |                  |
| 17  |           BUFFER SORT                  |                  |
| 18  |            TABLE ACCESS FULL           | PRODUCTS         |
| 19  |           BITMAP INDEX RANGE SCAN      | SALES_PROD_BIX   |
------------------------------------------------------------------+

  Outline Data:
  /*+
    BEGIN_OUTLINE_DATA
      IGNORE_OPTIM_EMBEDDED_HINTS
      OPTIMIZER_FEATURES_ENABLE('11.1.0.6')
      ... 중간생략    
      STAR_TRANSFORMATION(@"SEL$1" "S"@"SEL$1" SUBQUERIES(("C"@"SEL$1") ("P"@"SEL$1")))
      BITMAP_TREE(@"SEL$1" "S"@"SEL$1" AND(("SALES"."CHANNEL_ID") ("SALES"."PROD_ID")))
      SEMIJOIN_DRIVER(@"SEL$1898F719")
      SEMIJOIN_DRIVER(@"SEL$D750A531")
    END_OUTLINE_DATA
  */

Driving Semi Join의 장점은 또 있다
Driving Semi Join Nested Loop Join 시의 조인횟수에 의한 부하나 Hash 조인시의 Full Table Scan + Hashing 작업의 부하를 획기적으로 감소켜준다. 더 좋은것은 Star Transformation 사용시에 바인드 변수를 사용할수 없었지만 Driving Semi Join은 이러한 제약이 없다. 하지만 이 기능은 오라클사의 정식힌트가 아니므로 필자의 경우 데이터 분석 용도로만 사용하고 있다. 이기능이 11.2 버젼에는 정식으로 메뉴얼에 나오길 기대하며 이글을 마칠까 한다.