by-nc-sa     개발자, DBA가 함께 만들어가는 구루비 지식창고!

10. 조인 카디널리티




ch10. 조인 카디널리티

  • 오라클은 FROM절에 얼마나 많은 테이블을 기술할 수 있느냐는 별개로 조인 시 한번에 두개 오브젝트만을 처리한다.
  • 다섯개의 테이블을 조인하기 위해 옵티마이저는 어느 한 테이블을 시작으로 다른 한 테이블과 조인한다.
  • 결과로서 만들어진 중간결과 집합을 다른 테이블과 조인하고, 다시 그 결과집합을 또 다른 테이블과 계속해서 조인하는 방식이다.

조인 카디널리티 기본

- 조인 선택도를 구하는 공식
Sel = 1 / max[(NDV(t1.c1), NDV(t2.c2)] *
        ((card t1 - # t1.c1 NULLS) / card t1) *
        ((card t2 - # t2.c2 NULLS) / card t2)
조인 선택도 =
        ((num_rows(t1) - num_nulls(t1.c1)) / num_rows(t1)) *
        ((num_rows(t2) - num_nulls(t2.c2)) / num_rows(t2)) *
        greater(num_distinct(t1.c1), num_distinct(t2.c2))
-> user_tables.num_rows
-> user_tab_col_statistics.num_nulls
-> user_tab_col_statistics.num_distinct

- 조인 카디널리티(Cardinality)를 구하는 공식
Card(Pj) = card(t1) * card(t2) * sel(Pj)
조인 카디널리티 =
        조인 선택도 *
        필터된 카디널리티(t1) * 필터된 카디널리티(t2)
-> 필터된 카디널리티 : 조인조건외의 다른 조건들을 각 테이블에 적용한 것.
(조인 조건중 일부가 필터 조건처럼 작용할 수 도 있다)
create table t1 AS
SELECT trunc(dbms_random.value(0, 25 )) filter,
       trunc(dbms_random.value(0, 30 )) join1,
       lpad(rownum, 10) v1,
       rpad('x', 100) padding
  FROM all_objects
 WHERE rownum <= 10000 ;
create table t2 AS
SELECT trunc(dbms_random.value(0, 50 )) filter,
       trunc(dbms_random.value(0, 40 )) join1,
       lpad(rownum, 10) v1,
       rpad('x', 100) padding
  FROM all_objects
 WHERE rownum <= 10000 ;
-- Collect statistics using dbms_stats here
SELECT t1.v1,
       t2.v1
  FROM t1,
       t2
 WHERE t1.filter = 1
   AND t2.join1 = t1.join1
   AND t2.filter = 1 ;
  • 생성된 데이터
    t1.filter 25 values
    t2.filter 50 values
    t1.join1 30 values
    t2.join1 40 values.
    - 조인 카디널리티
    Join Selectivity =
    		(10,000 - 0) / 10,000) *
    		(10,000 - 0) / 10,000) /
    		greater(30, 40) = 1/40
    Join Cardinality = 1/40 * (400 * 200) = 2000
    - autotrace 결과
    Execution Plan (9.2.0.6 autotrace)
    ----------------------------------------------------------
    0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=57 Card=2000 Bytes=68000)
    1 0 HASH JOIN (Cost=57 Card=2000 Bytes=68000)
    2 1 TABLE ACCESS (FULL) OF 'T2' (Cost=28 Card=200 Bytes=3400)
    3 2 TABLE ACCESS (FULL) OF 'T1' (Cost=28 Card=400 Bytes=6800)
    
  • NULL 값을 포함할 때도 계산식이 잘 들어 맞는지 확인.
  • t1 테이블은 20번째 로우마다 t2 테이블은 30번째 로우마다 조인컬럼이 NULL 값을 갖도록 데이터 갱신
    update t1 set join1 = null
    where mod(to_number(v1),20) = 0;
    -- 500 rows updated
    update t2 set join1 = null
    where mod(to_number(v1),30) = 0;
    -- 333 rows updated
    
    - 조인 카디널리티
    Join Selectivity =
    		(10,000 - 500) / 10,000) *
    		(10,000 - 333) / 10,000) /
    		greater(30, 40) = 0.022959125
    Join Cardinality = 400 * 200 * 0.022959125 = 1,836.73
    - autotrace 결과
    Execution Plan (9.2.0.6 autotrace)
    ----------------------------------------------------------
    0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=57 Card=1837 Bytes=62458)
    1 0 HASH JOIN (Cost=57 Card=1837 Bytes=62458)
    2 1 TABLE ACCESS (FULL) OF 'T2' (Cost=28 Card=200 Bytes=3400)
    3 1 TABLE ACCESS (FULL) OF 'T1' (Cost=28 Card=400 Bytes=6800)
    
  • 필터 컬럼의 일부 레코드도 NULL 값으로 치환
    update t1 set filter = null
    where mod(to_number(v1),50) = 0;
    -- 200 rows updated
    update t2 set filter = null
    where mod(to_number(v1),100) = 0;
    -- 100 rows updated
    
    - 필터조건(filter = 1) 컬럼에 NULL 값이 존재하므로 테이블별로 필터된 카디널리티만 다시 계산.
    Adjusted (computed) Cardinality = Base Selectivity * (num_rows - num_nulls)
    	. For table t1 we have 1/25 * (10,000 . 200) = 392.
    	. For table t2 we have 1/50 * (10,000 . 100) = 198.
    - 조인 카디널리티
    Join Cardinality = 392 * 198 * 0.022959125 = 1,781.995
    - autotrace 결과
    Execution Plan (9.2.0.6 autotrace)
    ----------------------------------------------------------
    0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=57 Card=1782 Bytes=60588)
    1 0 HASH JOIN (Cost=57 Card=1782 Bytes=60588)
    2 1 TABLE ACCESS (FULL) OF 'T2' (Cost=28 Card=198 Bytes=3366)
    3 1 TABLE ACCESS (FULL) OF 'T1' (Cost=28 Card=392 Bytes=6664)
    
  • 조인 컬럼이 두 개 이상이라면 어떻게 계산해야 할까?
  • 조인절에 범위 검색 조건(range scan)을 포함한다면 어떻게 해야 할까?
  • 3개 이상의 테이블을 조인한다면 어떻게 해야 할까?
  • 공식을 보면, 양쪽 조인 컬럼 값의 범위가 일부만 겹치는, 즉 일부 값들만 조인에 성공하는 경우에
    대해서는 고려하고 있지 않은 것 같은데, 그 이유는 무엇일까?
  • 히스토그램 정보가 있다면 조인 카디널리티 계산에 어떤 영향을 미칠까?

한 쪽에만 필터조건을 적용한 경우

create table t1 AS
SELECT trunc(dbms_random.value(0, 100 )) filter,
       trunc(dbms_random.value(0, 30 )) join1,
       lpad(rownum, 10) v1,
       rpad('x', 100) padding
  FROM all_objects
 WHERE rownum <= 1000 ;
create table t2 AS
SELECT trunc(dbms_random.value(0, 100 )) filter,
       trunc(dbms_random.value(0, 40 )) join1,
       lpad(rownum, 10) v1,
       rpad('x', 100) padding
  FROM all_objects
 WHERE rownum <= 1000 ;
-- Collect statistics using dbms_stats here
SELECT t1.v1,
       t2.v1
  FROM t1,
       t2
 WHERE t2.join1 = t1.join1
-- and t1.filter = 1
   AND t2.filter = 1 ;
  • 테이블 t1의 조인컬럼에는 30개의 distinct 값을, t2의 조인컬럼에는 40개의 distinct 값을 갖는다.
    Join Selectivity =
    		(1000 / 1000) * (1000 / 1000) / greater(30, 40) =
    		1/40 = 0.025
    Join Cardinality =
    		Join Selectivity *
    		filtered cardinality(t1) * filtered cardinality(t2) =
    		0.025 * 10 * 1000 = 250
    - autotrace 결과
    Execution Plan (9.2.0.6 Filter on just T1)
    ----------------------------------------------------------
    0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=11 Card=250 Bytes=7750)
    1 0 HASH JOIN (Cost=11 Card=250 Bytes=7750)
    2 1 TABLE ACCESS (FULL) OF 'T1' (Cost=5 Card=10 Bytes=170)
    3 1 TABLE ACCESS (FULL) OF 'T2' (Cost=5 Card=1000 Bytes=14000)
    Execution Plan (9.2.0.6 Filter on just T2)
    ----------------------------------------------------------
    0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=11 Card=333 Bytes=10323)
    1 0 HASH JOIN (Cost=11 Card=333 Bytes=10323)
    2 1 TABLE ACCESS (FULL) OF 'T2' (Cost=5 Card=10 Bytes=170)
    3 1 TABLE ACCESS (FULL) OF 'T1' (Cost=5 Card=1000 Bytes=14000)
    
  • 필터 테이블을 바꾸었는데, 조인 후 결과집합의 카디널리티가 바뀌었다.
  • 두 개의 num_distinct 중 더 큰쪽을 이용하는게 아니라 필터 조건이 없는 쪽 테이블의 num_distinct 값을 사용한다.
    (옵티마이저가 어느 테이블의 num_distinct값을 사용할지를 결정하는 데에 필터 조건이 영향을 미치는 일반적인
    규칙에서 벗어나는 매우 특별한 케이스에 해당한다(필자생각))
    -> t2에만 필터조건을 사용할 때는 기본 공식에 따라 더 큰 num_distinct 값 40을 사용하지 않고
    t1테이블의 num_distinct 값 30을 사용하게 된 것이다.

실환경에서의 조인 카디널리티

  • 두 테이블 조인 시 둘 이상의 컬럼이 사용될 경우는 어떻게 될까?
  • 단일 테이블에 대한 다중 조건절을 처리할 때 했던 방식과 같은 전략을 사용한다.
  • 선택도 구하는 공식은 각 조건절마다 차례로 한 번씩 적용하고 그 값들을 곱하기만 하면 최종 조인 선택도가 구해진다.
    create table t1 AS
    SELECT trunc(dbms_random.value(0, 30 )) join1,
           trunc(dbms_random.value(0, 50 )) join2,
           lpad(rownum, 10) v1,
           rpad('x', 100) padding
      FROM all_objects
     WHERE rownum <= 10000 ;
    create table t2 AS
    SELECT trunc(dbms_random.value(0, 40 )) join1,
           trunc(dbms_random.value(0, 40 )) join2,
           lpad(rownum, 10) v1,
           rpad('x', 100) padding
      FROM all_objects
     WHERE rownum <= 10000 ;
    
    -- Collect statistics using dbms_stats here
    SELECT t1.v1,
           t2.v1
      FROM t1,
           t2
     WHERE t2.join1 = t1.join1
       AND t2.join2 = t1.join2 ;
    - autotrace 결과
    Execution Plan (9.2.0.6 autotrace)
    ----------------------------------------------------------
    0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=60 Card=50000 Bytes=1700000)
    1 0 HASH JOIN (Cost=60 Card=50000 Bytes=1700000)
    2 1 TABLE ACCESS (FULL) OF 'T1' (Cost=28 Card=10000 Bytes=170000)
    3 1 TABLE ACCESS (FULL) OF 'T2' (Cost=28 Card=10000 Bytes=170000)
    - 조인선택도
    Join Selectivity =
    		{join1 bit} *
    		{join2 bit} =
    		(10,000 - 0) / 10,000) *
    		(10,000 - 0) / 10,000) /
    		greater(30, 40) * -- uses the t2 selectivity (1/40)
    		(10,000 - 0) / 10,000) *
    		(10,000 - 0) / 10,000) /
    		greater(50, 40) = -- uses the t1 selectivity (1/50)
    		1/40 * 1/50 = 1/2000
    
  • 10g autotrace 결과 (다른 결과 출력 - 역으로 조사)
    Execution Plan (10.1.0.4 autotrace)
    ----------------------------------------------------------
    0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=60 Card=62500 Bytes=2125000)
    1 0 HASH JOIN (Cost=60 Card=62500 Bytes=2125000)
    2 1 TABLE ACCESS (FULL) OF 'T1' (TABLE) (Cost=28 Card=10000 Bytes=170000)
    3 1 TABLE ACCESS (FULL) OF 'T2' (TABLE) (Cost=28 Card=10000 Bytes=170000)
    - 조인선택도
    62,500 = 100,000,000 * join selectivity.
    Join selectivity = 62,500 / 100,000,000 = 1/1,600
    
  • 옵티마이저는 두 개의 선택도를 양쪽 테이블에서 하나씩 취한 게 아니라 두 테이블 중 어느 한 쪽을 선택하고
    거기서 두개의 선택도를 취했다.

– 10053 트레이스

Table: T1 Multi-column join key card: 1500.000000 (30 * 50)
Table: T2 Multi-column join key card: 1600.000000 (40 * 40)

Using multi-column join key sanity check for table T2
Revised join selectivity: 6.2500e-004 = 5.0000e-004 * (1/1600) * (1/5.0000e-004)
Join Card: 62500.00 = outer (10000.00) * inner (10000.00) * sel (6.2500e-004)
  • 간단히 두 테이블을 조인하는 경우에는 10g 에서 계산방식이 대체되어 항상 이런 sanity check가 일어난다(11장에서 설명)
    1. 양쪽 조인 컬럼 중 num_distinct가 큰 값을 선택하는 작업을 조인 조건절마다 차례로 수행.
    2. 각테이블 조인 컬럼들의 num_distinct 값을 조회해서 테이블별 선택도를 따로따로 구한 후에 그 중 작은 값을 사용.
  • _optimizer_join_sel_sanity_check 파라미터로 이 행동을 제어할 것이다.
  • 개별 테이블에 대한 다중컬럼 조인키 카디널리티가 그 테이블에 대한 1/num_rows 보다 작다면 계산된 값 대신 1/num_rows를 사용.

확장과 예외

범위조건에 의한 조인

  • 옵티마이저가 범위(t2.join1>t1.join1)기반 조인문을 만났을때는 조인 조건절의 선택도로서 미리 정해 둔 고정된 상수를 이용.(5%)
  • t2.join1 between t1.join1 - 1 and t1.join1 + 1 은 두개의 독립적이 조건절 "join1 >= :bind1 and join1 <= :bind2"로 처리하여
    1/20과 1/20을 곱해서 1/400(0.025%)의 선택도를 계산한다.
  • 조인절 t2.join1=t1.join1일 때의 결과 집합이 t2.join1 between t1.join1 - 1 and t1.join2 + 1 의 부분집합인데, 계산된
    카디널리티를 보면 거꾸로 2전자가 2,000, 후자는 200이라는 점을 주목하라.
    일관성에 문제가 있고, 범위기반 조인의 계산 전략에 진지하게 고민해 볼 필요가 있다.

부등호 조인

  • t1.join1 != t2.join1의 선택도는 1에서 (t1.join1 = t2.join1의 선택도를 빼면 된다.
    SELECT t1.v1,
           t2.v1
      FROM t1,
           t2
     WHERE t2.join1 != t1.join1 -- (30 / 40 values for num_distinct)
       AND t2.join2 != t1.join2 -- (50 / 40 values for num_distinct)
           ;
    
  • 두 조인조건이 등호일 경우 1/40 * 1/50 공식을 사용하므로, 반대로 둘 다 부등호일 때는 39/40 * 49/50 공식을 사용하면 된다.
  • 두 조인조건을 OR연산자로 했을경우에는 잘못된 카디널리티를 보여준다(버그)
  • 이 경우 옵티마이저가 묵시적으로 concatenation 실행계획을 생성하도록 UNION ALL을 이용해 두 개의 조인문으로 분기해라.

조인하는 두 집합이 완전히 겹치지 않는 경우

  • 두 집합이 서로 중복되는 비율이 낮아질수록 조인 카디널리티에 어떤변화가 발생하는지 살펴보자.
  • join1 컬럼의 distinct 값은 양쪽 모두 100개,
  • t1.join1이 갖는 값의 범위를 -100 ~ -1 부터 100 ~ 199 까지 계속 값의 범위를 변경
  • t2.join1 컬럼의 값은 항상 0 ~ 99
  • 9i, 10g에서는 서로 일치하는 값이 전혀 없는 경우를 제외하면 양쪽 집합이 100% 조인한다는 가정하에 카디널리트를 계산.
    (8i에서는 두 집합간에 겹치는 데이터가 전혀 없는 경우에도 카디널리티를 1,000,000으로 계산)

히스토그램

  • 조인 카디널리티 계산 시 조인조건에 포함된 두 컬럼들의 히스토그램 정보를 이용한다.(9i/10g 결과)
  • 첫번째 버킷사이즈 85(height balanced), 두번째 254(frequency)로 히스토그램 생성.
  • 첫번째는 중복된 집합에 대서 만큼은 완벽하지 않지만 어느 정도 정밀하고 합리적인 값으로 계산
  • 두번째는 최저값을 100 또는 -100으로 바꾸었을때만 1,000,000으로 계산되고, 이외에는 실제 로우 개수와 거의 일치하는 값으로 계산.()의 값.
  • 일반적으로 사용되는 히스토그램은 height balanced 형태이다.
  • 첫번째에서 -22와 75 사이일때 실제 로우 수와 거의 가까운 값을 계산해 내고 있다.
    (이 구간에서 양쪽 테이블 중 하나의 히스토그램에 빈번한 값(popular value)이 있는것으로 나타났다)
  • 아래 조건을 모두 만족할때 옵티마이저는 히스토그램을 활용하는 어떤 방법을 동원함으로서 더 나은 조인 실행계획을 만들어 내는 것 같다.
    1. 9i/10g 에서 수행
    2. 등호(=)로 조인되는 양쪽 컬럼 무두에 히스토그램을 생성.
    3. 적어도 둘 중 하나가 두수분포(frequency) 히스토그램이거나 빈번한 값(popluar value)이 있는것으로 나타난다.
  • 8i에서는 히스토그램이 완전한 도수 분포 히스토그램이 아닌 경우에 다소 부정확한 결과가 나온다.
  • 도수분포 히스토그램을 생성할 수 없을 때(빈번한 값(popular value)이 있을때) 그런 값들을 잘 표현하기 위한
    적정한 버킷 개수를 몇 개로 선택할지가 고민거리다.(알아서 찾아내라???)

1. 적정한 버킷 개수 선택하기.

  • 히스토그램 생성 시 요청할 수 있는 가장 큰 버킷 개수는 254.
  • 컬럼에 대한 히스토그램이 유익할 것으로 판단되면 최적의 버킷 개수를 찾기 위한 추정치로서 처음부터 아예 가장 큰 값을 지정해도 좋다.
  • 히스토그램의 정밀도를 높임으로써 얻을 수 있는 잠재적인 이익을 고려하면, 초과버킷(기본값은 75)에 의한 한?비용은 중요하지 않다.

2. 도수분포(FREQUENCY) 히스토그램과 DBMS_STATS

  • dbms_stats 패키지를 통해 도수분포 히스토그램을 생성할 때 문제가 있다.
  • 위의 예에서 100이상의 버킷 개수를 요청해도 높이균형 히스토그램이 생성된다. 134를 넘는 순간부터 도수분포 히스토그램이 생성된다.

이행적 폐쇄

SELECT t1.v1,
       t2.v1
  FROM t1,
       t2
 WHERE t1.join1 = 20 -- 30 distinct values
   AND t2.join1 = t1.join1 -- 40 / 30 distinct values
   AND t2.join2 = t1.join2 -- 40 / 50 distinct values
;

- t1.join1 = 20이 없을 경우
Execution Plan (9.2.0.6 autotrace)
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=60 Card=50000 Bytes=1700000)
1 0 HASH JOIN (Cost=60 Card=50000 Bytes=1700000)
2 1 TABLE ACCESS (FULL) OF 'T1' (Cost=28 Card=10000 Bytes=170000)
3 1 TABLE ACCESS (FULL) OF 'T2' (Cost=28 Card=10000 Bytes=170000)

- 조건 추가했을경우
Execution Plan (9.2.0.6 autotrace)
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=57 Card=1667 Bytes=56678)
1 0 HASH JOIN (Cost=57 Card=1667 Bytes=56678)
2 1 TABLE ACCESS (FULL) OF 'T2' (Cost=28 Card=250 Bytes=4250)
3 1 TABLE ACCESS (FULL) OF 'T1' (Cost=28 Card=333 Bytes=5661)

- dbms_xplan
--------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost |
--------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1667 | 56678 | 57 |
|* 1 | HASH JOIN | | 1667 | 56678 | 57 |
|* 2 | TABLE ACCESS FULL | T2 | 250 | 4250 | 28 |
|* 3 | TABLE ACCESS FULL | T1 | 333 | 5661 | 28 |
--------------------------------------------------------------------
Predicate Information (identified by operation id):
1 - access("T2"."JOIN2"="T1"."JOIN2")
2 - filter("T2"."JOIN1"=20)
3 - filter("T1"."JOIN1"=20)

Join Selectivity =
		((num_rows(t1) - num_nulls(t1.c1)) / num_rows(t1)) *
		((num_rows(t2) - num_nulls(t2.c2)) / num_rows(t2)) /
		greater(num_distinct(t1.c1), num_distinct(t2.c2))
Join Cardinality =
		join selectivity *
		filtered cardinality(t1) * filtered cardinality(t2)
		Join Selectivity =
		((10000 - 0)/ 10000) *
		((10000 - 0)/ 10000) /
		greater(40, 50) = -- t1.join2, t2.join2 (num_distinct)
		1/50
Join Cardinality =
		(1 / 50) *
		10000/30 * 10000/40 = -- t1.join1 has 30 values, t2.join1 has 40
		333 * 250 / 50 =
		1,666.66
  • Predicate Information를 보면 이행적 폐쇄(transitive closure)의 매카니즘에 의해 두개의 필터조건과 단일 조인 컬럼을 갖는 형태로 바뀌었다.
  • 9i, 10g의 결과가 같게 나타난다(이행성 폐쇄과정에서 두 개의 조인 조건중 하나가 제거되었기 때문에 10g에서 snity check가 일어나지 않는다.)
  • 필요 이상의 조건정을 명시적으로 추가할 경우 어떤일이 일어날까?
    SELECT t1.v1,
           t2.v1
      FROM t1,
           t2
     WHERE t1.join1 = 20 -- 30 distinct values
       AND t2.join1 = t1.join1 -- 40 / 30 distinct values
       AND t2.join2 = t1.join2 -- 40 / 50 distinct values
       AND t2.join1 = 20 -- 40 distinct values
    ;
    
    - dbms_xplan
    --------------------------------------------------------------------
    | Id | Operation | Name | Rows | Bytes | Cost |
    --------------------------------------------------------------------
    | 0 | SELECT STATEMENT | | 42 | 1428 | 57 |
    |* 1 | HASH JOIN | | 42 | 1428 | 57 |
    |* 2 | TABLE ACCESS FULL | T2 | 250 | 4250 | 28 |
    |* 3 | TABLE ACCESS FULL | T1 | 333 | 5661 | 28 |
    --------------------------------------------------------------------
    Predicate Information (identified by operation id):
    1 - access("T2"."JOIN1"="T1"."JOIN1" AND "T2"."JOIN2"="T1"."JOIN2")
    2 - filter("T2"."JOIN1"=20)
    3 - filter("T1"."JOIN1"=20)
    
    - 9i
    Join Selectivity =
    		{join1 bit} *
    		{join2 bit} =
    		(10,000 - 0) / 10,000) *
    		(10,000 - 0) / 10,000) /
    		greater(30, 40) *
    		(10,000 - 0) / 10,000) *
    		(10,000 - 0) / 10,000) /
    		greater(50, 40) =
    		1/40 * 1/50 = 1/2000
    Join Cardinality =
    		(1 / 2000) *
    		10000 / 30 * 10000 / 40 =
    		333 * 250 / 2000 =
    		41.625
    
    - 10g
    Join Cardinality =
    		(1 / 1600) *
    		10000 / 30 * 10000 / 40 =
    		333 * 250 / 2000 =
    		52.031
    
  • t2.join1 = t1.join1 조건절이 다시 나타났다. t2.join1 = 20 조건절을 생성하려고 이행적 폐쇄를 사용할 필요가 없었다.
  • 옵티마이저가 t2.join1의 선택도를 중복해서 두번 계산하는 셈이된다(조인 선택도를 위해 한번(1), 필터 카디널리티를 위해 한번(2))
  • 10g에서는 다중컬럼 sanity check 효과 때문에 다르게 나타난다. 1/2,000 대신 더 작은 결과집합을 리턴하는 어느 한쪽
    테이블로부터의 개별적인 선택도들을 가져온다(여기서는 t2 테이블로부터 1/40*1/40=1/1,600)
  • 오래전부터 사람들은 옵티마이저와 관련된 버그들을 발견하고는 이를 이용해 단순 조건절을 반복 사용함으로써 옵티마이저가
    다른 실행계획을 사용하도록 조정하곤 했다.
  • 8i/9i 에서 query_rewrite_enabled 파라미터를 TRUE로 설정하는 것은 이행적 폐쇄가 작동한느 방식에 영향을 미친다.

세 개 이상 테이블을 조인할 경우

  • 세 번째 테이블과 조인 시 연결 컬럼이 첫 번째 또는 두 번째 테이블 중 어느 한 쪽으로부터 오는 것이 아니라 양쪽 모두에서 오는 경우.
    SELECT t1.v1,
           t2.v1,
           t3.v1
      FROM t1,
           t2,
           t3
     WHERE t2.join1 = t1.join1 -- 36 / 40 distinct values
       AND t2.join2 = t1.join2 -- 38 / 40 distinct values
    --
       AND t3.join2 = t2.join2 -- 37 / 38 distinct values
       AND t3.join3 = t2.join3 -- 39 / 42 distinct values
    --
       AND t3.join4 = t1.join4 -- 41 / 40 distinct values
    ;
    
    Execution Plan (9.2.0.6 autotrace)
    ----------------------------------------------------------
    0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=109 Card=9551 Bytes=573060)
    1 0 HASH JOIN (Cost=109 Card=9551 Bytes=573060)
    2 1 TABLE ACCESS (FULL) OF 'T3' (Cost=28 Card=10000 Bytes=200000)
    3 1 HASH JOIN (Cost=62 Card=62500 Bytes=2500000)
    4 3 TABLE ACCESS (FULL) OF 'T1' (Cost=29 Card=10000 Bytes=200000)
    5 3 TABLE ACCESS (FULL) OF 'T2' (Cost=28 Card=10000 Bytes=200000)
    
  • 조인 순서 t1 > t2 > t3
    1. t3을 메모리로 해싱
    2. t1을 메모리로 해싱
    3. t2를 읽기 시작하여 각 로우마다 매칭되는 데이터를 찾기 위해 t1 해시 테이블 탐색
    4. 첫 번째 탐색이 성공한다면 매칭 되는 데이터를 찾기 위해 t3 해시 테이블 탐색
  • 첫 번째 조인은 t1 > t2 (t2 > t1이 맞지 않나??), 두 번째 조인은 (t1 > t2) > t3
    Join Selectivity =
    		{join1 bit} *
    		{join2 bit} =
    		((10000 - 0) / 10000) *
    		(10000 - 0) / 10000)) /
    		greater (36 , 40) *
    		((10000 - 0) / 10000) *
    		(10000 - 0) / 10000)) /
    		greater (38 , 40) =
    		1/1600
    Join Cardinality =
    		1 / 1600 *
    		10000 * 10000 =
    		62,500
    - 62,500개의 로우를 갖는 중간집합을 생성.
    
    Join Selectivity =
    		{join2 bit} *
    		{join3 bit} *
    		{join4 bit} =
    		((10000 - 0) / 10000) *
    		(10000 - 0) / 10000)) /
    		greater( 37, 38) * -- greater( 37, 40)으로 대체해야 하지 않을까?
    		((10000 - 0) / 10000) *
    		(10000 - 0) / 10000)) /
    		greater( 39, 42) *
    		((10000 - 0) / 10000) *
    		(10000 - 0) / 10000)) /
    		greater( 41, 40) =
    		1/65,436
    Join Cardinality =
    		1 / 65436 *
    		62500 * 10000 =
    		9,551 (as required)
    
  • 조인 선택도를 계산하기 위해 join2와 join3의 컬럼이 속한 테이블의 SQL 조인문에 기술된 테이블 별칭을 보고 알 수 있다.
  • 무의식적으로(또는 고의로) 조인 조건절을 다르게 기술했을 때 계산된 카디널리티가 어떻게 바뀔까?
    t2.join1 = t1.join1
    and t2.join2 = t1.join2
    --
    and t3.join3 = t2.join3
    --
    and t3.join2 = t1.join2 -- was t3.join2 = t2.join2
    and t3.join4 = t1.join4
    
    Execution Plan (9.2.0.6 autotrace)
    ----------------------------------------------------------
    0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=109 Card=9074 Bytes=544440)
    1 0 HASH JOIN (Cost=109 Card=9074 Bytes=544440)
    2 1 TABLE ACCESS (FULL) OF 'T3' (Cost=28 Card=10000 Bytes=200000)
    3 1 HASH JOIN (Cost=62 Card=62500 Bytes=2500000)
    4 3 TABLE ACCESS (FULL) OF 'T1' (Cost=29 Card=10000 Bytes=200000)
    5 3 TABLE ACCESS (FULL) OF 'T2' (Cost=28 Card=10000 Bytes=200000)
    
  • 이행성 폐쇄는 열결고리 컬럼 중 어느 하나에 상수조건을 추가적으로 가지고 있을 때에만 일어난다.
  • 계산된 카디널리티가 9,074로 떨어졌다.
  • 공식은 분명히 greater( 37, 38)에서 greater( 37, 40)으로 바뀌었다.
  • 이것은 틀림없이 옵티마이저의 결함이다.
    (첫 번째는 중간집합시 t1테이블 선택도 사용, t3 조인시 t2 테이블의 선택도 사용,
    두 번째는 중간집합시 t1테이블 선택도 사용, t3 조인시 t1 테이블의 선택도 사용)
  • 복잡한 조인에서도 항상 컬럼의 선택도를 정확하고 일관성 있게 처리 해야 한다.
  • 10g에서 실행할 때 고려해야 할 중요한 요소가 있다.(sanity check)
  • 첫 번째는 같은 방식으로 9,551로 계산(join4 컬럼을 위해 t3 선택도 사용)
  • 두 번째는 9,301로 바뀐다(join2를 위해 t1 선택도 사용, join4 컬럼에 대해서도 t1 선택도 사용)
  • 더 나쁜 케이스는 't3.join2 = t2.join2', 't3.join2 = t1.join2'를 모두 사용할 경우 두 조건 모두를
    사용하여 최종 카디널리티를 계산한다.(239로 떨어진다)
  • 이런 이유 때문에 다중테이블 조인문을 작성할 때는 세심한 주의가 필요하다.

조인 컬럼에 NULL값을 갖는 경우

  • 두 테이블만을 다룰 때는 대개 문제가 되지 않지만, 오라클 버전이 8i에서 9i로 올라가면서
    조인 선택도 계산시 NULL을 다루는 전략이 바뀌었다.
    (존인 컬럼에 포함된 NULL값의 개수가 테이블 로우 수의 5%를 초과할 때만 새로운 계산식이 사용)
    create table t1 AS
    SELECT mod(rownum-1, 15) n1,
           lpad(rownum, 10) v1,
           rpad('x', 100) padding
      FROM all_objects
     WHERE rownum <= 150 ;
    
    UPDATE t1
       SET n1 = null
     WHERE n1 = 0;
    
  • 100개의 로우를 가진 t1 테이블 정의.
  • n1 컬럼은 1 ~ 9까지 9개의 값과 NULL 값을 가지도록 가공.(num_rows=100, num_distinct=9, num_nulls=10)
  • t2, t3는 각각 1~11, 1~14까지의 값을 갖도록 정의
  • 세 테이블 모두 n1 컬럼이 어떤 값이든 각각 열 개의 로우를 가진다.
  • 각 테이블마다 n1에는 NULL값을 가진 레코드도 열 개씩 들어 있으므로 5% 제한을 넘는다.
    SELECT /*+ ordered */
      t1.v1,
           t2.v1,
           t3.v1
      FROM t1,
           t2,
           t3
     WHERE t2.n1 = t1.n1
       AND t3.n1 = t2.n1 ;
    
    Execution Plan (9.2.0.6 autotrace)
    ----------------------------------------------------------
    0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=8 Card=9000 Bytes=378000)
    1 0 HASH JOIN (Cost=8 Card=9000 Bytes=378000)
    2 1 TABLE ACCESS (FULL) OF 'T3' (Cost=2 Card=140 Bytes=1960)
    3 1 HASH JOIN (Cost=5 Card=900 Bytes=25200)
    4 3 TABLE ACCESS (FULL) OF 'T1' (Cost=2 Card=90 Bytes=1260)
    5 3 TABLE ACCESS (FULL) OF 'T2' (Cost=2 Card=110 Bytes=1540)
    
    Execution Plan (8.1.7.4 autotrace)
    ----------------------------------------------------------
    0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=5 Card=8250 Bytes=346500)
    1 0 HASH JOIN (Cost=5 Card=8250 Bytes=346500)
    2 1 TABLE ACCESS (FULL) OF 'T3' (Cost=1 Card=150 Bytes=2100)
    3 1 HASH JOIN (Cost=3 Card=900 Bytes=25200)
    4 3 TABLE ACCESS (FULL) OF 'T1' (Cost=1 Card=100 Bytes=1400)
    5 3 TABLE ACCESS (FULL) OF 'T2' (Cost=1 Card=120 Bytes=1680)
    
  • 라인 4, 5의 각 테이블 스켄을 위한 다른 카디널리티로 계산 했는데 두 버전 모두 라인 3에서 같은 카디널리티(900) 값을 보여준다.
  • 로우수 계산 (9i가 정확)
    1. t1의 n1 컬럼에는 9개의 다른값, 총 90개의 로우(NULL 제외)
    2. t2에 매칭되는 로우가 10개씩, 조인결과 900로우
    3. t3에 매칭되는 로우가 10개씩, 조인결과 총 9,000로우
  • 9i에서 dbms_xplan을 이용하면 필터 조건절에 다음을 확인할 수 있다
    t1.n1 is not null
    t2.n1 is not null
    t3.n1 is not null
    
  • t1.n1 = t1.n2 조건으로 조인한 결과집합에는 이들 컬럼에 NULL값을 가진 레코드가 존재할 수 없다.
    - 8i
    T1 to T2: the tables with 100 and 120 rows respectively:
    Join Selectivity =
            (100 - 10) / 100) *
            (120 - 10) / 120) /
            greater(9, 11) = 0.075
    Join Cardinality =
            0.075 * 100 * 120 = 900
    
    Intermediate to T3: the table with 150 rows:
    Join Selectivity =
            (120 - 10) / 120) * -- the CBO uses the t2 figures at one end
            (150 - 10) / 150) / -- of the join, and the t3 at the other.
            greater(11, 14) =
            0.0611111
    Join Cardinality =
            0.061111 * 900 * 150 =
            8,250
    
    - 9i
    T1 to T2: the tables with 100 and 120 rows respectively:
    Join Selectivity =
            1 / greater(9, 11) =
            0.09090909
            Join Cardinality =
            0.09090909 * 90 * 110 =
            900
    
    Intermediate to T3: the table with 150 rows:
    Join Selectivity =
            1 / greater(11, 14) =
            0.0714285
            Join Cardinality =
            0.0714285 * 900 * 140 =
            9,000 (as required)
    
  • 9i에서는 'is not null' 조건에 의한 필터링 효과를 조인 카디널리티를 구하는 단계에서 반영하고 있다.
  • 즉, 조인 선택도 공식에는 NULL효과를 반영하지 않고 조인 카디널리티를 구하는 단계에서만 각 테이블의
    필터된 카디널리티를 인자로 사용.
  • 8i에서 9i로 업그레이드하면 NULL 허용 컬럼들을 이용해 여러 테이블을 조인하는 쿼리들의 카디널리티가
    더 높게 계산되기 때문에 갑자기 실행계획이 바뀔 수 있다(계산된 카디널리티가 앞 단계에서 증가하기 때문에 NL -> 해쉬 나 머지로)

문서에 대하여

  • 최초작성자 : 김종원
  • 최초작성일 : 2009년 9월 5일
  • 이 문서는 오라클클럽 코어 오라클 데이터베이스 스터디 모임에서 작성하였습니다.
  • 이 문서의 내용은 (주)비투엔컬설팅에서 번역한 '비용기반의 오라클 원리'를 참고하였습니다.

문서정보

Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.