Semi Join

Semi Join 은 Subquery Unnesting 의 대표적인 결과이다.
Semi Join 은 우리말로는 반조인
선행 table의 Row가 후행 Table의 Row와 Match되기만 하면 Join조건이 만족된 것으로 간주하고
- 해당 Row에 대해서는 더 이상의 탐색을 진행하지 않는다. 따라서 효율적이다.
Semi Join 은 Exists 와 In Operation 의 효율적 처리를 위해 고안된 방식
Semi Join 은 주로 Hash Join 이나 Nested Loops Join 의 형태로 구현된다.

{section}
{column:width=50}

Subquery Unnesting 에 의한 Hash Semi Join


SQL> -- Subquery Unnesting 에 의한 Hash Semi Join --
SQL> SELECT COUNT(*)
  2    FROM (SELECT /*+ gather_plan_statistics */
  3                 t1.c1, t1.c2
  4            FROM t1
  5           WHERE t1.c1 IN (SELECT t2.c1 FROM t2)
  6          )
  7  ;
      1000

SQL> SELECT * FROM TABLE(dbms_xplan.display_cursor(null,null,'allstats cost last'));
SQL_ID  9g821jv5f7kgv, child number 0
-------------------------------------
SELECT COUNT(*)   FROM (SELECT /*+ gather_plan_statistics */                t1.c1, t1.c2           FROM t1          WHERE
t1.c1 IN (SELECT t2.c1 FROM t2)         )

Plan hash value: 911817144

----------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation              | Name  | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------------------------
|   1 |  SORT AGGREGATE        |       |      1 |      1 |            |      1 |00:00:00.01 |      31 |       |       |          |
|*  2 |   HASH JOIN RIGHT SEMI |       |      1 |    999 |    10  (10)|   1000 |00:00:00.01 |      31 |  1066K|  1066K| 1178K (0)|
|   3 |    INDEX FAST FULL SCAN| T2_N1 |      1 |   1000 |     2   (0)|   1000 |00:00:00.01 |       7 |       |       |          |
|   4 |    INDEX FAST FULL SCAN| T1_N1 |      1 |  10000 |     7   (0)|  10000 |00:00:00.01 |      24 |       |       |          |
----------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("T1"."C1"="T2"."C1")


21 개의 행이 선택되었습니다.

{column}
{column:width=50}
{column}
{section}

Subquery 가 Unnesting 되어 Hash Join Right Semi 로 풀렸으며 일량은 31 Block 이다.
Subquery Unnesting 이 안되도록 No_Unnest 힌트를 주고 일량을 비교해 보자.

{section}
{column:width=50}

No_Unnest 로 인한 Filter Operation


SQL> -- No_Unnest 로 인한 Filter Operation --
SQL> SELECT COUNT(*)
  2    FROM (SELECT /*+ gather_plan_statistics */
  3                 t1.c1, t1.c2
  4            FROM t1
  5           WHERE t1.c1 IN (SELECT /*+ No_Unnest */ t2.c1 FROM t2)
  6          )
  7  ;
      1000

SQL> SELECT * FROM TABLE(dbms_xplan.display_cursor(null,null,'allstats cost last'));
SQL_ID  7hx47wqmyqn07, child number 0
-------------------------------------
SELECT COUNT(*)   FROM (SELECT /*+ gather_plan_statistics */                t1.c1, t1.c2
       FROM t1          WHERE t1.c1 IN (SELECT /*+ No_Unnest */ t2.c1 FROM t2)         )

Plan hash value: 645528743

----------------------------------------------------------------------------------------------------
| Id  | Operation           | Name  | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------------
|   1 |  SORT AGGREGATE     |       |      1 |      1 |            |      1 |00:00:00.05 |   20038 |
|*  2 |   FILTER            |       |      1 |        |            |   1000 |00:00:00.01 |   20038 |
|   3 |    TABLE ACCESS FULL| T1    |      1 |  10000 |    11   (0)|  10000 |00:00:00.01 |      38 |
|*  4 |    INDEX RANGE SCAN | T2_N1 |  10000 |      1 |     1   (0)|   1000 |00:00:00.03 |   20000 |
----------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter( IS NOT NULL)
   4 - access("T2"."C1"=:B1)


22 개의 행이 선택되었습니다.

{column}
{column:width=50}
{column}
{section}

No_Unnest 힌트로 Filter Operation 이 발생했으며 일량은 31에서 20038로 크게 증가하였다.
- 앞에서 살펴보았던 Filter Optimization(Filter Operation 에서의 Cache 효과)이 아무런 힘을 쓰지 못했다.
- Why? c1 컬럼은 중복값이 없으므로 캐시된 값을 재사용하지 못한다.
그런데 Cost 는 10 에서 11 로 증가하여 그닥 큰 차이가 나지 않는다.
- 여기서 알 수 있는 것은 Oracle이 Filter Operation 에 대한 Cost 를 제대로 계산하지 못한다는 것을 알 수 있다.
- 아마도 Filter Optimization 을 감안하여 낙관적인 계산을 하는것이 아닐런지???
- CBO 입장에서 Filter Operation 은 대단히 위험한 샘이다.
- Oracle이 Subquery를 매우 공격적으로 Unnesting 해야 하는 이유 중 하나이다.

{section}
{column:width=50}

Top-N Query 로 인한 Nested Loops Semi Join


SQL> -- Top-N Query 로 인한 Nested Loops Semi Join --
SQL> SELECT *
  2    FROM (SELECT /*+ gather_plan_statistics */
  3                 t1.c1, t1.c2
  4            FROM t1
  5           WHERE t1.c1 IN (SELECT t2.c1 FROM t2)
  6          )
  7   WHERE ROWNUM <= 1
  8  ;
       636 dummy

SQL> SELECT * FROM TABLE(dbms_xplan.display_cursor(null,null,'allstats cost last'));
SQL_ID  dqgpjf25wnphs, child number 0
-------------------------------------
SELECT *   FROM (SELECT /*+ gather_plan_statistics */                t1.c1, t1.c2           FROM t1       WHERE t1.c1
IN (SELECT t2.c1 FROM t2)         )  WHERE ROWNUM <= 1

Plan hash value: 3833757213

----------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation              | Name  | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------------------------
|*  1 |  COUNT STOPKEY         |       |      1 |        |            |      1 |00:00:00.01 |      11 |       |       |          |
|*  2 |   HASH JOIN RIGHT SEMI |       |      1 |    999 |     5  (20)|      1 |00:00:00.01 |      11 |  1066K|  1066K| 1135K (0)|
|   3 |    INDEX FAST FULL SCAN| T2_N1 |      1 |   1000 |     2   (0)|   1000 |00:00:00.01 |       7 |       |       |          |
|   4 |    TABLE ACCESS FULL   | T1    |      1 |  10000 |     2   (0)|      1 |00:00:00.01 |       4 |       |       |          |
----------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter(ROWNUM<=1)
   2 - access("T1"."C1"="T2"."C1")


22 개의 행이 선택되었습니다.

SQL> SELECT *
  2    FROM (SELECT /*+ gather_plan_statistics */
  3                 t1.c1, t1.c2
  4            FROM t1
  5           WHERE t1.c1 IN (SELECT t3.c1 FROM t3)
  6          )
  7   WHERE ROWNUM <= 1
  8  ;
         1 dummy

SQL> SELECT * FROM TABLE(dbms_xplan.display_cursor(null,null,'allstats cost last'));

SQL_ID  912xytkf43uu6, child number 0
-------------------------------------
SELECT *   FROM (SELECT /*+ gather_plan_statistics */
t1.c1, t1.c2           FROM t1          WHERE t1.c1 IN (SELECT t3.c1
FROM t3)         )  WHERE ROWNUM <= 1

Plan hash value: 1263059105

-------------------------------------------------------------------------------------------------------------
| Id  | Operation           | Name  | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers | Reads  |
-------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |       |      1 |        |     2 (100)|      1 |00:00:00.03 |      10 |      1 |
|*  1 |  COUNT STOPKEY      |       |      1 |        |            |      1 |00:00:00.03 |      10 |      1 |
|   2 |   NESTED LOOPS SEMI |       |      1 |      2 |     2   (0)|      1 |00:00:00.03 |      10 |      1 |
|   3 |    TABLE ACCESS FULL| T1    |      1 |  10000 |     2   (0)|    946 |00:00:00.01 |       7 |      0 |
|*  4 |    INDEX RANGE SCAN | T3_N1 |    946 |      1 |     0   (0)|      1 |00:00:00.03 |       3 |      1 |
-------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter(ROWNUM<=1)
   4 - access("T1"."C1"="T3"."C1")


24 개의 행이 선택되었습니다.

{column}
{column:width=50}
{column}
{section}

TOP-N Query 에서의 Semi Join
- 대량의 Data 처리엔 Hash Join 이 유리하지만 위와 같이 Rownum 조건으로 소량의 Data 처리시엔 Hash Join 이 불리하다.
- Nested Loops Semi Join 으로 풀렸으면 좋았는데... 책과는 다른 결과(Hash Join)가 나와 버렸다.
- t2 로는 책의 실행계획을 얻지 못하고 t3로 바꿔서 책의 결과를 얻어냄.

{section}
{column:width=50}

Top-N Query 가 Filter Operation 으로 풀린다면?


SQL> -- No_Unnest 로 인한 Filter Operation Top-N Query --
SQL> SELECT *
  2    FROM (SELECT /*+ gather_plan_statistics */
  3                 t1.c1, t1.c2
  4            FROM t1
  5           WHERE t1.c1 IN (SELECT /*+ No_Unnest */ t2.c1 FROM t2)
  6          )
  7   WHERE ROWNUM <= 1
  8  ;
       636 dummy

SQL> SELECT * FROM TABLE(dbms_xplan.display_cursor(null,null,'allstats cost last'));
SQL_ID  czy3b9qqwk0uh, child number 0
-------------------------------------
SELECT *   FROM (SELECT /*+ gather_plan_statistics */                t1.c1, t1.c2
FROM t1          WHERE t1.c1 IN (SELECT /*+ No_Unnest */ t2.c1 FROM t2)         )  WHERE
ROWNUM <= 1

Plan hash value: 2386917197

----------------------------------------------------------------------------------------------------
| Id  | Operation           | Name  | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------------
|*  1 |  COUNT STOPKEY      |       |      1 |        |            |      1 |00:00:00.01 |       6 |
|*  2 |   FILTER            |       |      1 |        |            |      1 |00:00:00.01 |       6 |
|   3 |    TABLE ACCESS FULL| T1    |      1 |  10000 |    11   (0)|      1 |00:00:00.01 |       4 |
|*  4 |    INDEX RANGE SCAN | T2_N1 |      1 |      1 |     1   (0)|      1 |00:00:00.01 |       2 |
----------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter(ROWNUM<=1)
   2 - filter( IS NOT NULL)
   4 - access("T2"."C1"=:B1)


24 개의 행이 선택되었습니다.

{column}
{column:width=50}
{column}
{section}

Top-n 쿼리가 Filter 로 풀렸을때 결과
- Logical Reads 가 6 으로 Filter Operation 임에도 불구하고 적은 일량이 나왔다.
- Filter Operation 이 반복적으로 수행되지 않고 Rownum 조건으로 인해 단 한번만 수행했기 때문.
- 부분범위 처리에 있어서는 Nestd Loops Join 이나 Filter Operation 이 유리함을 알 수 있다.
다음과 같이 인덱스 컬럼 조건을 주는 경우에도 Nestd Loops Join 으로 동작한다.

{section}
{column:width=50}

인덱스 조건으로 인한 Nested Loops Semi Join


SQL> -- 인덱스 조건으로 인한 Nested Loops Semi Join --
SQL> SELECT /*+ gather_plan_statistics */
  2         t1.c1, t1.c2
  3    FROM t1
  4   WHERE t1.c1 IN (SELECT t2.c1 FROM t2)
  5     AND t1.c1 = 1
  6  ;
         1 dummy

SQL> SELECT * FROM TABLE(dbms_xplan.display_cursor(null,null,'allstats cost last'));
SQL_ID  7za75sb3zfp6r, child number 0
-------------------------------------
SELECT /*+ gather_plan_statistics */        t1.c1, t1.c2   FROM t1  WHERE t1.c1 IN (SELECT t2.c1
FROM t2)    AND t1.c1 = 1

Plan hash value: 2914088042

-------------------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name  | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |
-------------------------------------------------------------------------------------------------------------
|   1 |  NESTED LOOPS SEMI           |       |      1 |      1 |     3   (0)|      1 |00:00:00.01 |    6 |
|   2 |   TABLE ACCESS BY INDEX ROWID| T1    |      1 |      1 |     2   (0)|      1 |00:00:00.01 |    4 |
|*  3 |    INDEX RANGE SCAN          | T1_N1 |      1 |      1 |     1   (0)|      1 |00:00:00.01 |    3 |
|*  4 |   INDEX RANGE SCAN           | T2_N1 |      1 |      1 |     1   (0)|      1 |00:00:00.01 |    2 |
-------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   3 - access("T1"."C1"=1)
   4 - access("T2"."C1"=1)
       filter("T1"."C1"="T2"."C1")


23 개의 행이 선택되었습니다.

SQL>

{column}
{column:width=50}
{column}
{section}

Subquery Unnesting 에 의한 Semi Join 이 이루어지는 것은 매우 긍정적인 효과가 있음을 알 수있다.
따라서 Subquery 가 사용된 Query 에서 Subquery Unnesting 이 성공적으로 이루어졌는지 실행계획을 통해 확인하자.

Semi Join (by manon94) [2011.04.13]

Semi Join