11. NL(Nested Loops) 조인

조회 수 9499 추천 수 0 2010.03.10 21:00:12
휘휘 *.168.123.1

CHAPTER 11. NL(Nested Loops) 조인



기본 메커니즘 381 /이태경


 
NL Join

 
작동원리
 

for r1 in (select rows from table_1 where colx = {value}) loop
for r2 in (select rows from table_2 that match current row from table_1) loop
output values from current row of table_1 and current row of table_2
end loop
end loop
 

 
슈도코드를 보면 NL조인에는 outer(driving)테이블과 inner(target)테이블이 존재한다.
outer테이블에 대해 한 로우를 찾으면 inner테이블에서 해당 로우와 매칭 되는 로우를 loop를 돌며 찾는다.
 
 참고
NL: outer,inner
해시조인: build,probe
merge조 인: first table,second table

but 10053 trace 파일에서는 항상 outer, inner


NL의 두가지 형태

Execution Plan (9.2.0.6 autotrace - unique access on inner table (traditional))
-------------------------------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=324 Card=320 Bytes=11840)
1 0     NESTED LOOPS (Cost=324 Card=320 Bytes=11840)
2 1         TABLE ACCESS (FULL) OF 'DRIVER' (Cost=3 Card=320 Bytes=2560)
3 1         TABLE ACCESS (BY INDEX ROWID) OF 'TARGET' (Cost=2 Card=1 Bytes=29)
4 3             INDEX (UNIQUE SCAN) OF 'T_PK' (UNIQUE) (Cost=1 Card=1)

단일 로우를 리턴 한다는 보장이 있는경우 UNIQUE SCAN


실 행계획 
 
  •  prefetch_test 스크립트 결과
STATEMENT_ID                   OPTIONS
------------------------------ --------------------------------
316                            RANGE SCAN
317                            RANGE SCAN
318                            RANGE SCAN
319                            RANGE SCAN
320                            UNIQUE SCAN

321                            UNIQUE SCAN
322                            UNIQUE SCAN
323                            UNIQUE SCAN
324                            UNIQUE SCAN
325                            UNIQUE SCAN
326                            UNIQUE SCAN
327                            UNIQUE SCAN
328                            UNIQUE SCAN
329                            UNIQUE SCAN
330                            UNIQUE SCAN
331                            UNIQUE SCAN
332                            UNIQUE SCAN
333                            UNIQUE SCAN
334                            UNIQUE SCAN
335                            UNIQUE SCAN
336                            UNIQUE SCAN

 


  • 선 행 테이블의 로우가 319개 일 때(9.2.7.0) prefetch_test_02.txt 실행결과
     

SQL> select
  2     /*+ ordered use_nl(t) index(t) full(d) */
  3     d.id, t.small_vc
  4  from
  5     driver  d,
  6     target  t
  7  where
  8     t.id = d.xref
  9  and        t.padding is not null
 10  ;

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=ALL_ROWS (Cost=322 Card=319 Bytes=11803)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'TARGET' (Cost=2 Card=1 Bytes=29)
   2    1     NESTED LOOPS (Cost=322 Card=319 Bytes=11803)
   3    2       TABLE ACCESS (FULL) OF 'DRIVER' (Cost=3 Card=319 Bytes=2552)
   4    2       INDEX (RANGE SCAN) OF 'T_PK' (UNIQUE) (Cost=1 Card=1)



Execution Plan (9.2.0.6 autotrace - range scan on inner table (new option))
---------------------------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=322 Card=319 Bytes=11803)
1 0     TABLE ACCESS (BY INDEX ROWID) OF 'TARGET' (Cost=2 Card=1 Bytes=29)
2 1         NESTED LOOPS (Cost=322 Card=319 Bytes=11803)
3 2             TABLE ACCESS (FULL) OF 'DRIVER' (Cost=3 Card=319 Bytes=2552)
4 2             INDEX (RANGE SCAN) OF 'T_PK' (UNIQUE) (Cost=1 Card=1)



두번째 실행계획은 table prefetching 메커니즘사용
: 처리량이 많은 NL 조인시 논리적인 I/O 횟수를 줄일수 있음

but 9i의 경우  두번째 테이블 엑세스가 prmary key일경우에
선행 테이블에서 처리되는 로우수에 따라 다른메커니즘을 사용
예의 경우는 로우가 320 일때는 unique scan 319일때는 range scan을 사용함을 보여줌
10g에서는 모두 unique사용
 
 
 

 
 
10053 트레이스 파일
NL Join
  Outer table: cost: 3  cdn: 319  rcz: 8  resp:  2
  Access path: index (unique)
      Index: T_PK
  TABLE: TARGET
      RSC_CPU: 21694   RSC_IO: 1
  IX_SEL:  3.3333e-004  TB_SEL:  3.3333e-004
    Join:  resc: 322  resp: 322

 
  Access path: index (eq-unique) --eq-unique는 뭘 의미하는 건지요.
      Index: T_PK
  TABLE: TARGET
      RSC_CPU: 15423   RSC_IO: 1
  IX_SEL:  0.0000e+000  TB_SEL:  0.0000e+000
    Join:  resc: 322  resp: 322
 

 
  Best NL cost: 322  resp: 322
Join cardinality:  319 = outer (319) * inner (3000) * sel (3.3333e-004)  flag=0
Join result: cost: 322  cdn: 319  rcz: 37
Best so far: TABLE#: 0  CST:          3  CDN:        319  BYTES:       2552
Best so far: TABLE#: 1  CST:        322  CDN:        319  BYTES:      11803
 
NL 조인 비용 계산식
: 첫 번째 테이블로부터 데이터를 가져오는 비용 + 첫 번째 테이블로부터 리턴되는 레코드 개수*두 번째 테이블을 한번 방문하기 위해 소요되는 비용
= 3 + 319 * 3000 * sel(3.3333e-004) = 322
  
 
  • 선행 테이블의 로우가 320개 일 때 (9.2.7.0) prefetch_test_02.txt 실행결과
 

SQL> select
  2     /*+ ordered use_nl(t) index(t) full(d) */
  3     d.id, t.small_vc
  4  from
  5     driver  d,
  6     target  t
  7  where
  8     t.id = d.xref
  9  and        t.padding is not null
 10  ;

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=ALL_ROWS (Cost=324 Card=320 Bytes=11840)
   1    0   NESTED LOOPS (Cost=324 Card=320 Bytes=11840)
   2    1     TABLE ACCESS (FULL) OF 'DRIVER' (Cost=3 Card=320 Bytes=2560)
   3    1     TABLE ACCESS (BY INDEX ROWID) OF 'TARGET' (Cost=2 Card=1 Bytes=29)
   4    3       INDEX (UNIQUE SCAN) OF 'T_PK' (UNIQUE) (Cost=1 Card=1)
 
 
10053 트레이스 파일
NL Join
  Outer table: cost: 3  cdn: 320  rcz: 8  resp:  2
  Access path: index (unique)
      Index: T_PK
  TABLE: TARGET
      RSC_CPU: 21694   RSC_IO: 1
  IX_SEL:  3.3333e-004  TB_SEL:  3.3333e-004
    Join:  resc: 323  resp: 323
  Access path: index (eq-unique)
      Index: T_PK
  TABLE: TARGET
      RSC_CPU: 15423   RSC_IO: 1
  IX_SEL:  0.0000e+000  TB_SEL:  0.0000e+000
    Join:  resc: 323  resp: 323
  Best NL cost: 324  resp: 323
Join cardinality:  320 = outer (320) * inner (3000) * sel (3.3333e-004)  flag=0
Join result: cost: 324  cdn: 320  rcz: 37
Best so far: TABLE#: 0  CST:          3  CDN:        320  BYTES:       2560
Best so far: TABLE#: 1  CST:        324  CDN:        320  BYTES:      11840
 
NL 조인 비용 계산식
: 첫 번째 테이블로부터 데이터를 가져오는 비용 + 첫 번째 테이블로부터 리턴되는 레코드 개수*두 번째 테이블을 한번 방문하기 위해 소요되는 비용
= 3+320*3000*sel(3.3333e-004) = 323
 
 
  • table prefetching의 작동원리 
 장점
 아우터테이블로부터 첫번째 로우를 찾고 인덱스를 탐침해서 리프블록에 도달하면 이너 테이블을 엑세스하기 위해 필요한
 rowid 정보만을 읽고 거기서 멈춘다. 이렇게 driving테이블에 대한 rowid를 모두 찾고 나면 그 뒤에 target테이블에 대한 접근이 이뤄진다.
 따라서 테이블 길이를 따라 블록들을 단 한번씩만 방문하면 되고 논리적 I/O를 최소화시킬 수 있다.
 단점
 rowid순으로 읽게 되면 order by 절에 대한 소트를 발생시킬 수 있다.








 
  •  OPTIMIZER_INDEX_CACHING
 인덱스 블록들이 메모리에 캐싱돼 있을 확률에 대한 퍼센트를 옵티마이저에게 알려주는 용도로 사용.
질 문)optimizer_index_caching 파라미터 값에 의한 작용은? 예를 들어, 파라미터를 낮게 줬을 경우, 엑세스할 때 마다 옵티마이저가 물리 I/O를 발생을 유도하는건가요? 



실사례


prefetch_test_02.sql

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=ALL_ROWS (Cost=324 Card=320 Bytes=11840)
   1    0   NESTED LOOPS (Cost=324 Card=320 Bytes=11840)
   2    1     TABLE ACCESS (FULL) OF 'DRIVER' (Cost=3 Card=320 Bytes=2560)
   3    1     TABLE ACCESS (BY INDEX ROWID) OF 'TARGET' (Cost=2 Card=1 Bytes=29)
   4    3       INDEX (UNIQUE SCAN) OF 'T_PK' (UNIQUE) (Cost=1 Card=1)


2 번째 라인 driver 테이블을 스캔해서 320로우 리턴하는 비용 3
3번째 라인 target 테이블을 한번 방문하는 비용이 2

공식대입 = 3+ (320 *2)=643 
이여서 공식과 다름


반 올림과 중간 결과 출력방식의 문제

실계산


plan table 조회 내용 9.2.0.4


        ID  PARENT_ID OPERATION                            COST CARDINALITY   CPU_COST    IO_COST
---------- ---------- ------------------------------ ---------- ----------- ---------- ----------
         0            SELECT STATEMENT                      324         320    7010826        322
         1          0 NESTED LOOPS                          324         320    7010826        322
         2          1 TABLE ACCESS                            3         320      68643          2
         3          1 TABLE ACCESS                            2           1      21695          1
         4          3 INDEX                                   1           1      14443



i/o 비용
    322 = 2 (2번째줄) + 320 * 1 (세번째)

cpu 비용
    7010826 ≒ 68643 (두번째라인) + 320 * 21,695 (세번째)
            = 7011043

이며 

begin
dbms_stats.set_system_stats('MBRC',8);
dbms_stats.set_system_stats('MREADTIM',20);
dbms_stats.set_system_stats('SREADTIM',10);
dbms_stats.set_system_stats('CPUSPEED',500);
end;


에 의해 cpu클럭 500Mhz , 블록읽기 1/100초 소요되는것으로 간주
500만개의 오퍼레이션 수행이 한블록 읽기와 동일함을 의미하도록 하였으므로

I/O 비용  +(cpu 비용/5,000,000) 을 이용하여야함

COST = IO COST + Adjusted CPU cost
 324 =     322 + ceiling (7,010,826 / 5,000,000)
   2 =       1 + ceiling (68643/5,000,000)
   1 =       0 + ceiling (21,695/5,000,000)

9i 의 autotrace 결과 리포트 간결화로 인한 반올림 문제



실사례 388 /남송휘



prefetch_test_02.sql

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=ALL_ROWS (Cost=324 Card=320 Bytes=11840)
   1    0   NESTED LOOPS (Cost=324 Card=320 Bytes=11840)
   2    1     TABLE ACCESS (FULL) OF 'DRIVER' (Cost=3 Card=320 Bytes=2560)
   3    1     TABLE ACCESS (BY INDEX ROWID) OF 'TARGET' (Cost=2 Card=1 Bytes=29)
   4    3       INDEX (UNIQUE SCAN) OF 'T_PK' (UNIQUE) (Cost=1 Card=1)


2번째 라인 driver 테이블을 스캔해서 320 로우 리턴하는 비용 3
3번째 라인 target 테이블을 한번 방문하는 비용이 2

공식대입 = 3+ (320 * 2)=643 
이여서 공식과 다름


반올림과 중간 결과 출력방식의 문제로 판단






실계산


plan table 조회 내용 

9.2.0.4


        ID  PARENT_ID OPERATION                            COST CARDINALITY   CPU_COST    IO_COST
---------- ---------- ------------------------------ ---------- ----------- ---------- ----------
         0            SELECT STATEMENT                      324         320    7010826        322
         1          0 NESTED LOOPS                          324         320    7010826        322
         2          1 TABLE ACCESS                            3         320      68643          2
         3          1 TABLE ACCESS                            2           1      21695          1
         4          3 INDEX                                   1           1      14443



i/o 비용
    322 = 2 (2번째줄) + 320 * 1 (세번째)

cpu 비용
    7010826 ≒ 68643 (두번째라인) + 320 * 21,695 (세번째)
            = 7011043

이며 

begin
dbms_stats.set_system_stats('MBRC',8);
dbms_stats.set_system_stats('MREADTIM',20);
dbms_stats.set_system_stats('SREADTIM',10);
dbms_stats.set_system_stats('CPUSPEED',500);
end;


에 의해 cpu클럭 500Mhz , 블록읽기 1/100초 소요되는것으로 간주
500만개의 오퍼레이션 수행이 한블록 읽기와 동일함을 의미하도록 하였으므로

I/O 비용  +(cpu 비용/5,000,000) 을 이용하여야함

COST = IO COST + Adjusted CPU cost
 324 =     322 + ceiling (7,010,826 / 5,000,000)
   2 =       1 + ceiling (68,643/5,000,000)
   1 =       0 + ceiling (21,695/5,000,000)


9i 의 autotrace 결과 리포트 간결화로 인한 반올림 문제





Sanity Checks 390 /이창헌

 

인덱스를 이용해 테이블을 액세스하는 비용을 산정할 때 기본공식(Wolfgang Breitling formula)을 이용하지 않고 미리 저장해 둔 값들을 사용하는 특별한 케이스

 

join_cost_03a.sql

 

기본 NL조인 공식에 따라 계산한다면 쿼리를 두 테이블 간 조인으로 전환했을 때 T1테이블에 대한 액세스 비용은 선행 테이블로부터 리턴되는 결과건수의 배수가 됨..

 

select /*+ ordered use_nl( t1 ) index( t1 t1_i1 ) */

      t1.small_vc

        

  from driver d

      ,t1

 where d.n3 = 5

   and t1.ind_pad = d.ind_pad

   and t1.n1 = d.n1

   and t1.n2 = d.n2 

 

driver테이블에서 건만 리턴된다는 사실을 안다. 따라서 최종 결고집합의 카디널리티도 t1테이블을 단독으로 쿼리할 때와 같아야 한다.

 

*선행 테이블로부터 로우를 읽는 비용 + 1(선행 테이블에서 리턴되는 결과건수) * 14(테이블만을 단독으로 쿼리할 때의 비용)

 

예상과 다르게 비용이 이상함.

 

---------------------------------------------------------------------------------------

| Id  | Operation                      | Name   | Rows  | Bytes | Cost (%CPU)| Time     |

---------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT               |        |    16 |  1728 |   292   (0)| 00:00:03 |

|   1 |  NESTED LOOPS                  |        |    16 |  1728 |   292   (0)| 00:00:03 |

|   2 |   TABLE ACCESS BY INDEX ROWID  | DRIVER |     1 |    50 |     1   (0)| 00:00:01 |

|*  3 |    INDEX UNIQUE SCAN           | D_PK2  |     1 |       |     0   (0)| 00:00:01 |

|   4 |   TABLE ACCESS BY INDEX ROWID  | T1     |    16 |   928 |   291   (0)| 00:00:03 |

|*  5 |    INDEX RANGE SCAN            | T1_I1  |    16 |       |    45   (0)| 00:00:01 |

 

Predicate Information (identified by operation id):

---------------------------------------------------

 

   3 - access("D"."N3"=5)

   5 - access("T1"."IND_PAD"="D"."IND_PAD" AND "T1"."N1"="D"."N1" AND

              "T1"."N2"="D"."N2")

 

실행계획을 보면, 카디널리티는 전혀 변하지 않아 16그대로이다. 하지만, 비용에 어떤 일이 발생했는지 보라. 인덱스 라인을 보면 비용이 4에서 45 증가했고, 테이블을 방문하는 비용은 10에서 246으로 매우 증가 했다.

 

select blevel, avg_leaf_blocks_per_key, avg_data_blocks_per_key

  from user_indexes

 where table_name = 'T1'

   and index_name = 'T1_I1'

 

   BLEVEL

              AVG_LEAF_BLOCKS_PER_KEY

          AVG_DATA_BLOCKS_PER_KEY

2

44

246

 

 

인덱스 라인의 비용은 (blevel + avg_leaf_blocks_per_key-1)

테이블 라인의 비용은 (avg_data_blocks_per_key)이다.

 

 

결론 : 인덱스 전체 컬럼을 등로(=)로써 비교하는 특별한 케이스의 조인문을 처리할 옵티마이저는 user_indexes뷰에 미리 계산해서 저장해 값을 이용하는 방식으로 비용계산식을 변경 한다.


 


요약 396 /이태경


테스트 스크립트 396 /이태경