Nested Loop, Sort-Merge, Hash Join 조인연산

    조인연산(Join Operation) 이란?


    - SQL 명령문에 의해서 여러 테이블에 저장된 데이터를 한번에 조회할 수 있게 하는 DBMS의 기능

    - 두 집합(테이블) 간의 곱으로 데이터를 연결하는 가장 대표적인 데이터 연결 방법

    - 대표적인 종류로 Nested-Loop Join, Sort-Merge Join, Hash Join 등이 존재함


    ※ 조인연산은 옵티마이저(Optimizer)의 성능 및 DBMS의 고유의 성능, 그리고 조인연산의 알고리즘에 의해서 속도 등의 차이가 있을 수 있으나, 결과집합은 동일함




    Nested Loop Join


    가. Nested Loop의 개념

    - 2개 이상의 테이블에서 하나의 집합을 기준으로 순차적으로 상대방 Row를 결합하여 원하는 결과를 조합하는 방식

    - 먼저 선행 테이블의 처리 범위를 하나씩 액세스하면서 추출된 값으로 연결할 테이블을 조인한다




    쉽게 생각해서는 아래와 같은 C, JAVA 코드의 원리와 동일하다.


    1
    2
    3
    4
    5
    6
    < C, JAVA >
     for(i=0; i<100; i++) { -- outer loop 
       for(j=0; j<100; j++) { -- inner loop 
       // Do Anything ... 
       } 
    }
    cs



    나. Nested Loop의 특징

    - 좁은 범위에 유리한 성능을 보여줌

    - 순차적으로 처리하며, Random Access 위주

    - 후행 테이블(Driven)에는 조인을 위한 인덱스 생성 필요

    - 실행속도 = 선행 테이블 사이즈 * 후행 테이블 접근횟수



    다. 사용법 예제 및 PLAN

    SQL> explain plan for
      2  SELECT /*+ ordered use_nl(e)*/*
      3  FROM   dept d, emp e
      4  WHERE  d.deptno = e.deptno;
    
    해석되었습니다.
    
    SQL> SELECT * FROM table(dbms_xplan.display);
    
    PLAN_TABLE_OUTPUT
    --------------------------------------------------------------------------------
    Plan hash value: 4192419542
    
    ---------------------------------------------------------------------------
    | Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
    ---------------------------------------------------------------------------
    |   0 | SELECT STATEMENT   |      |    14 |   798 |     9   (0)| 00:00:01 |
    |   1 |  NESTED LOOPS      |      |    14 |   798 |     9   (0)| 00:00:01 |
    |   2 |   TABLE ACCESS FULL| DEPT |     4 |    80 |     3   (0)| 00:00:01 | => Outer/Driving
    |*  3 |   TABLE ACCESS FULL| EMP  |     4 |   148 |     2   (0)| 00:00:01 | => Inner/Driven
    ---------------------------------------------------------------------------


    라. Nested Loop 사용 시 주의사항

    • 데이터를 랜덤으로 액세스하기 때문에 결과 집합이 많으면 느려짐
    • Join index가 없거나, 조인 집합을 구성하는 검색조건이 조인 범위를 줄여주지 못할 경우 비효율적
    • 테이블 중 Row수가 적은 쪽을 Driven 테이블로 설정




    Sort Merge Join


    가. Sort Merge Join의 개념

    - 조인의 대상범위가 넓을 경우 발생하는 Random Access를 줄이기 위한 경우나 연결고리에 마땅한 인덱스가 존재하지 않을 경우 해결하기 위한 조인 방안

    - 양쪽 테이블의 처리범위를 각자 Access하여 정렬한 결과를 차례로 Scan하면서 연결고리의 조건으로 Merge하는 방식




    나. Sort Merge Join의 특징

    - 연결을 위해 랜덤 액세스를 하지 않고 스캔을 하면서 수행

    - Nested Loop Join처럼 선행집합 개념이 없음

    - 정렬을 위한 영역(Sort Area Size)에 따라 효율에 큰 차이 발생

    - 조인 연산자가 '='이 아닌 경우 nested loop 조인보다 유리한 경우가 많음



    다. 사용법 예제 및 PLAN

    SQL> explain plan for
      2  SELECT /*+ ordered full(d) use_merge(e)*/ *
      3  FROM   dept d, emp e
      4  WHERE  d.deptno = e.deptno;
    
    해석되었습니다.
    
    SQL> SELECT * FROM table(dbms_xplan.display);
    
    PLAN_TABLE_OUTPUT
    --------------------------------------------------------------------------------
    Plan hash value: 1407029907
    
    ----------------------------------------------------------------------------
    | Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
    ----------------------------------------------------------------------------
    |   0 | SELECT STATEMENT    |      |    14 |   798 |     8  (25)| 00:00:01 |
    |   1 |  MERGE JOIN         |      |    14 |   798 |     8  (25)| 00:00:01 |
    |   2 |   SORT JOIN         |      |     4 |    80 |     4  (25)| 00:00:01 |
    |   3 |    TABLE ACCESS FULL| DEPT |     4 |    80 |     3   (0)| 00:00:01 | => Outer/First
    |*  4 |   SORT JOIN         |      |    14 |   518 |     4  (25)| 00:00:01 |
    |   5 |    TABLE ACCESS FULL| EMP  |    14 |   518 |     3   (0)| 00:00:01 | => Inner/Second


    라. Sort Merge 사용 시 주의사항

    • 두 결과집합의 크기가 차이가 많이 나는 경우에는 비효율적
    • Sorting 메모리에 위치하는 대상은 join key뿐만 아니라 Select list도 포함되므로 불필요한 select 항목 제거



    Hash Join


    가. Hash Join의 개념

    - 해싱 함수(Hashing Function) 기법을 활용하여 조인을 수행하는 방식(해싱 함수는 직접적인 연결을 담당하는 것이 아니라 연결될 대상을 특정 지역(partition)에 모아두는 역할만을 담당

    - 해시값을 이용하여 테이블을 조인하는 방식

    - Sort-Merge 조인은 소트의 부하가 많이 발생하여, 이를 보완하기 위한 방법으로 Sort 대신 해쉬값을 이용하는 조인



    나. Hash Join의 특징

    - 대용량 처리의 선결조건인 랜덤 액세스와 정렬에 대한 부담을 해결할 수 있는 대안

    - parallel processing을 이용한 hash 조인은 대용량 데이터를 처리하기 위한 최적의 솔루션

    - 2개의 조인 테이블 중 small rowset을 가지고 hash_area_size에 지정된 메모리 내에서 hash table 생성

    - CBO에서만 가능하며, CPU 성능에 의존적

    - Hash table 생성 후 Nested Loop처럼 순차적인 처리 형태로 수행



    다. 사용법 예제 및 PLAN

    SQL> explain plan for
      2  SELECT /*+ ordered use_hash(e)*/*
      3  FROM   dept d, emp e
      4  WHERE  d.deptno = e.deptno;
    
    해석되었습니다.
    
    SQL> SELECT * FROM table(dbms_xplan.display);
    
    PLAN_TABLE_OUTPUT
    --------------------------------------------------------------------------------
    Plan hash value: 615168685
    
    ---------------------------------------------------------------------------
    | Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
    ---------------------------------------------------------------------------
    |   0 | SELECT STATEMENT   |      |    14 |   798 |     7  (15)| 00:00:01 |
    |*  1 |  HASH JOIN         |      |    14 |   798 |     7  (15)| 00:00:01 |
    |   2 |   TABLE ACCESS FULL| DEPT |     4 |    80 |     3   (0)| 00:00:01 | => Outer/Build Input
    |   3 |   TABLE ACCESS FULL| EMP  |    14 |   518 |     3   (0)| 00:00:01 | => Inner/Probe Input
    ---------------------------------------------------------------------------


    라. Hash Join 사용 시 주의사항

    • 대용량 데이터 처리에서는 상당히 큰 hash area를 필요로 함으로, 메모리의 지나친 사용으로 오버헤드 발생 가능성

    • 연결조건 연산자가 ‘=’인 동치조인인 경우에만 가능



    참고자료

    http://wiki.gurubee.net/pages/viewpage.action?pageId=26743004

    DBGuide.net - SQL 가이드


    댓글

    Designed by JB FACTORY