DATOR


오라클 옵티마이져의 최적화 수행원리 RDBMS 개론


오라클 옵티마이져의 최적화 수행원리에 대해 알아 보겠습니다.

 

먼저 오라클 옵티마이져의 기본 아키텍쳐를 살펴 보겠습니다. SQL Trace 결과에 나타나는 수행단계를 보면 Parse à Execute à Fetch 3단계로 이루어져 있는데, Parse 단계를 좀더 자세히 들여다 보면 아래와 같은 일들이 수행되고 있습니다.

 

1.      Statement matching, syntactic and semantic checks : 해당 SQL이 Library Cache에 이미 캐싱되어 있는지 확인하고, 구문(syntax) 검사와 의미(semantic) 검사를 수행합니다.
※ select * form dual
à
syntax error
※ select x from dual
à
semantic error

여기서 중요한 것은 Library Cache에서 캐싱여부를 확인할 때, 실행계획 생성에 영향을 미칠 수 있는 세션레벨 파라미터들의 설정값이 같은지에 대해서도 확인을 한다는 사실입니다. (
à
Environment Match Check)
예를 들어, WORKAREA_SIZE_POLICY를 AUTO로 설정한 경우와 MANUAL로 설정한 경우에 대해서 각각 다른 공유커서를 사용하게 되고 따라서 각 커서는 같은 SQL문일지라도 다른 실행계획을 생성할 수 있습니다.

<리스트1> Environment Match Check

 

SQL> alter system flush shared_pool;

 

시스템이 변경되었습니다.

 

SQL> alter session set workarea_size_policy = manual;

 

세션이 변경되었습니다.

 

SQL> select count(*) from emp;

 

  COUNT(*)

----------

        15

 

SQL> alter session set workarea_size_policy = auto;

 

세션이 변경되었습니다.

 

SQL> select count(*) from emp;

 

  COUNT(*)

----------

        15

 

SQL> select sql_text, child_number, hash_value, address

  2  from v$sql

  3  where sql_text like 'select count(*) from emp%'

  4  /

 

SQL_TEXT                   CHILD_NUMBER HASH_VALUE ADDRESS

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

select count(*) from emp              0 2744835752 C0000000169DE890

select count(*) from emp              1 2744835752 C0000000169DE890


위 테스트 결과를 보면, 현재 SHARED_POOL에는 같은 SQL에 대해 두 개의 공유커서가 캐싱되어 있는 것을 확인할 수 있습니다.

2.      Query Transformation : 앞 단계의 수행결과인 Parse Tree를 분석해서 의미적으로 동일(à 같은 결과집합을 리턴)하면서도 더 나은 성능을 제공하는 형태로 재작성하는 단계입니다.
이러한 질의변환은 크게 두 개의 카테고리로 나눌 수 있습니다.

ü        Heuristic query transformation : view merging, subquery flattening (=unnesting), transitive predicate generation, common subexpression elimination, predicate pushdown and pullup, group pruining for CUBE queries, outer-join to inner join conversion 등이 여기에 속합니다.

이러한 변환은 (최소한 동일하거나) 항상 더 나은 성능을 보장하기 때문에 오라클은 가능한 한 이들 변환을 수행합니다. 이해를 돕기 위해 View Merging에 대한 예를 보도록 하겠습니다.

 

[ 사용자에 의해 작성된 SQL ]

select d.name, avg_sal_dept
from   dept d
     ,(select deptno

            , avg(sal) avg_sal_dept

       from emp group by deptno) e
where  d.deptno = e.deptno
and    d.loc = 'OAKLAND';


 

[ 옵티마이져에 의해 재작성된 SQL ]

select d.name, avg(sal)
from   dept d, emp e
where  d.deptno = e.deptno
and    d.loc = 'OAKLAND'
group by d.rowid, d.name;

 

ü        Cost-based query transformation : materialized view rewrite, OR-expansion, Star transformation, Predicate pushdown for outer-joined views 등이 여기에 속합니다.

3.      Determine object costs and cardinalities : 각 오브젝트에 대한 액세스 방법(Access Method)과 비용을 계산하고 각 단계에서 리턴되는 로우 수를 예측합니다.

4.      Cost different join orders : 조인순서(Join Ordering)와 조인방법(Join Method)을 평가하고, 총 비용(overall cost)이 가장 낮은 실행계획을 선택합니다.

5.      Build structures for runtime : 런타임시 SQL 실행엔진이 사용할 수 있는 데이터 구조체로 포맷팅하고 Library Cache에 캐싱합니다.

 

1번 파싱과정은 Query Parser에 의해 수행되고, 2~4까지의 옵티마이징 단계는 Query Optimizer에 의해 수행되며, 마지막 5번 단계는 Row-Source Generator에 의해 수행됩니다.

이렇게 생성된 Row Source는 SQL Execution Engine에 의해 수행되고 Array Fetch 명령을 통해 그 결과를 최종 사용자에게 전달하게 됩니다.

 

456.gif  

여기서 가장 핵심적인 단계는 2~4까지의 옵티마이징 단계인데, 이를 수행하는 옵티마이저는 <그림1>에서 보는 것처럼 3개의 구성요소(components)로 이루어져 있습니다.

l        Query Transformer : 앞에서 설명드린 Query Transformation을 담당합니다.

l        Estimator : 데이터 딕셔너리에 저장된 다양한 통계정보를 이용해서 선택도(Selectivity), 카디널러티(Cardinality), 비용(Cost) 등의 예상치 값(measure)들을 산정하는 역할을 수행하는데, 뒤에서 언급되는 비용 산정 방식에서 좀 더 자세히 설명드리겠습니다.

l        Plan Generator : 주어진 쿼리를 위해 가능한 실행계획들을 생성해 낸 후에 Estimator의 도움을 받아서 가장 낮은 비용을 갖는 하나를 선택하는 과정을 총괄합니다.

 

지금까지 살펴 본 것처럼, SQL 최적화 단계에서는 순식간이긴 하지만 굉장히 많은 일들이 내부적으로 수행되고 있으며 따라서 가급적 이 단계를 반복적으로 수행하지 않도록 하기 위해 모든 DBMS는 나름대로의 캐싱기술을 사용하고 있습니다. 한번 최적화를 거친 SQL과 그 실행계획은 공유 메모리 영역에 재사용 가능한 상태로 저장 되었다가 다음에 같은 형태의 요청이 들어오면 재사용 될 수 있습니다. 앞에서 설명할 때 오라클의 경우 SQL의 캐싱여부를 파싱단계에서 확인한다고 했는데, 만약 캐싱되어 있지 않다면(à Library Cache Miss) 눈물을 머금고 최적화 단계를 수행해야 하지만 Library Cache에서 캐싱되어 있는 실행계획을 발견(à Library Cache Hit)하면 최적화 단계를 생략하고 곧바로 실행엔진에 의한 실행단계로 건너 뛰게 됩니다.

최적화 단계를 생략하는 경우를 소프트 파싱(Soft Parsing)이라고 하고, 최적화 단계를 수행해야만 하는 경우를 하드 파싱(Hard Parsing)이라고 하는데, SQL의 하드 파싱 횟수를 줄이기 위해서는 바인딩 변수를 적극적으로 사용해야 하겠고 경우에 따라서는 소프트 파싱까지도 생략하기 위한 커서공유기법들을 사용해야 합니다. 참고로 오라클 Pro*C에서 사용하고 있는 HOLD_CURSOR, RELEASE_CURSOR 옵션이 여기에 해당합니다.

 

옵티마이징 단계에서 비용기준 옵티마이져(CBO)는 데이터 딕셔너리에 저장된 테이블과 인덱스에 대한 통계정보를 광범위하게 사용합니다. 따라서 CBO가 작동하기 위해서는 통계정보가 반드시 필요하며, Analyze 명령 또는 DBMS_STATS 패키지의 다양한 프로시져 호출을 통해 수집됩니다.

 

n        테이블에 대한 통계정보(USER/ALL/DBA_TABLES)

ü         NUM_ROWS : 행 수

ü         BLOCKS : 블록 수

ü         EMPTY_BLOCKS : 사용되지 않은 블록 수

ü         AVG_ROW_LEN : 평균 행 길이

ü         AVG_SPACE : 블록 당 이용할 수 있는 평균 여유 공간

ü         CHAIN_CNT : 연결된(chained) 행 또는 이전된(migrated) 행의 수

ü         LAST_ANALYZED : 마지막 ANALYZE 날짜

ü         SAMPLE_SIZE : 샘플 크기

 

n        인덱스에 대한 통계정보(USER/ALL/DBA_INDEXES)

ü         NUM_ROWS : 인덱스 엔트리 수

ü         BLEVEL : 인덱스 B-Tree 레벨. 루트블럭부터 리프블럭까지의 깊이

ü         LEAF_BLOCKS : 리프 블록 수

ü         DISTINCT_KEYS : Unique하게 구별되는 키 값의 수. Unique 속성을 갖는 인덱스인 경우 테이블 행 수와 동일

ü         AVG_LEAF_BLOCKS_PER_KEY : 키 당 평균 리프 블록 수

ü         AVG_DATA_BLOCKS_PER_KEY : 키 당 평균 데이터 블록 수

ü         CLUSTERING_FACTOR : 클러스터링 팩터

ü         LAST_ANALYZED : 마지막 ANALYZE 날짜

ü         SAMPLE_SIZE : 샘플 크기

 

또한 인덱스 컬럼값의 데이터 분포가 균일하지 않은 상황에서는 컬럼값에 대한 히스토그램 정보를 생성해 주는 것이 매우 유용합니다. 히스토그램을 생성하면 옵티마이져는 아래와 같은 통계정보들을 추가적으로 활용할 수 있습니다.

n        컬럼 히스토그램 정보(USER/ALL/DBA_TAB_COLUMNS, DBA_TAB_HISTOGRAMS)

ü         HISTOGRAM

ü         DENSITY

ü         LOW_VALUE : 최저 값

ü         HIGH_VALUE : 최고 값

ü         NUM_DISTINCT : Unique하게 구별되는 값의 수

ü         NUM_NULLS : NULL 개수

ü         AVG_COL_LEN : 컬럼값의 평균 길이

ü         LAST_ANALYZED : 마지막 ANALYZE 날짜

ü         SAMPLE_SIZE : 샘플 크기

 

 

<그림2>에서 알 수 있듯이, 이들 통계정보는 옵티마이져가 각각의 실행계획에 대한 예상비용(estimated cost)을 산출하고 Decision Tree를 생성하기 위해 사용됩니다.

 

DecisionTree.GIF

 

 지금까지의 설명을 요약하면, 옵티마이져는 먼저 질의수행을 위해 가능하다고 생각되는 실행계획들을 찾아내고 각 실행계획들의 비용을 계산합니다. 이렇게 계산된 비용들을 평가한 후에 가장 최소비용이라고 판단되는 실행계획을 최종적으로 선택하는 과정입니다. 그런데 여기서 옵티마이저가 실행계획들을 비교할 때 사용하는 기준으로서의 비용(cost)의 개념이 어디까지나 '예상비용(estimated cost)'임을 이해하는 것이 중요합니다.

 

이제 이러한 기본적인 메커니즘을 바탕으로 Plan Generator가 실행계획을 생성하는 원리와 Estimator가 비용을 산정하는 방식에 대해 좀더 자세히 살펴보겠습니다.

먼저, 가능한 실행계획들을 탐색하는 과정에 대해서 설명할텐데, 여러 개의 테이블을 가지고 조인을 수행하고자 할 때, 가능한 실행계획의 개수는 몇 가지나 될까요? 예를 들어, 조인순서(Join ordering)만을 고려하더라도 5개의 테이블을 조인하는 쿼리는 5!=120 개의 가능한 실행계획을 갖습니다.

 

2 * 1 = 2

3 * 2 * 1 = 6

4 * 3 * 2 * 1 = 24

5 * 4 * 3 * 2 * 1 = 120

 

120개 수행순서에 포함되어 있는 각각의 테이블 조인에 대해 Nested Loop, Sort Merge, Hash Join 등의 다양한 조인방법(Join Method)들을 고려해야 합니다.

그리고 테이블을 액세스 하는 방식에는 크게 2가지가 있는데, 인덱스를 경유하는 방식과 Full Table Scan 방식이 있습니다. 그리고 인덱스를 액세스하는 방식에도 Index Range Scan, Index Unique Scan, Index Full Scan, Index Fast Full Scan, Index Skip Scan 등이 있고 계속해서 새로운 방식들이 도입되고 있습니다. 이런 모든 액세스 방법(Access Method)들까지 모두 고려한다면 모두 얼마나 될까요? 그리고 그러한 모든 실행계획의 예상 비용을 구하고자 한다면 시간은 얼마나 걸릴까요? 5개의 테이블를 조인하기 위해서는 아마 수천 개의 실행계획을 비교평가해야 할텐데 현재 이 정도까지는 옵티마이져가 아주 빠른 속도로 수행해 내고 있습니다. 옵티마이져의 발전과 함께 하드웨어의 발전도 크게 한몫을 했기 때문이겠지요. 그런데 흔한 경우는 아니겠지만 조인에 참여하는 테이블의 개수가 10개 이상이 된다면 그 개수는 기하급수적으로 증가해 수십, 수백만 개의 실행계획들을 비교해야만 하는 상황에 이를 것이며, 이쯤되면 배보다 배꼽이 더 커져서 실제 SQL 수행시간보다 파싱에 소요되는 시간이 더 커질 수 있습니다.

따라서 옵티마이저가 가능한 실행계획을 모두 고려할 수는 없는 노릇이므로 오라클은 SQL 최적화에 걸리는 시간을 단축시키기 위해 비용을 계산해야 할 실행계획들의 수를 줄일 수 있는 지능적인 테크닉들을 사용하고 있습니다.

가장 중요한 테크닉은 적응적 탐색 전략(Adaptive search strategy)입니다. 1초 만에 수행될 수 있는 쿼리를 최적화하기 위해 10초를 소비하는 것은 낭비입니다. 하지만 수십분 내지는 한시간 동안 수행되어야 하는 쿼리를 위해서라면 수초 이상 수분이 걸리더라도 더 나은 실행계획을 찾기 위해 계속적으로 최적화 단계를 수행하는 것이 결코 낭비가 아닐 수 있습니다. 그래서 오라클은 쿼리수행시 예상되는 총 수행시간에 비해 쿼리 최적화에 걸리는 시간이 일정비율을 넘지 않도록 적응적인 탐색 전략을 사용합니다.

 

또다른 중요한 테크닉으로는 Multiple Initial orderings heuristic 이 있습니다. 앞에서 설명한 방식에 의해 옵티마이져는 탐색도중이더라도 최적이라고 판단되는 실행계획을 발견하면 더 이상 진행하지 않고 멈추게 되는데 그럴 경우 미처 고려하지 않은 실행계획들 중에서 실제로 더 나은 실행계획이 있었을지도 모를 일입니다. 그래서 처음 탐색을 시작할 때 임의의 순서로 시작하는 것보다는 heuristic한 방법을 동원해서 거의 최적이거나 최소한 아주 좋은 실행계획일 것이라고 판단되는 실행계획들 순으로 정렬한 후에 그 순서에 따라 일을 진행하는 방식을 사용합니다.

 

이제, 비용 산정 방식에 대해 간단히 살펴 보겠습니다.

앞에서 잠시 언급했듯이 비용산정모듈은 옵티마이져 내부에서 Estimator에 의해 수행되는데, 데이터 딕셔너리에서 관리하는 다양한 통계정보를 기반으로 3개의 다른 "예상치" 값(measure)을 계산해 냅니다.

 

l        선택도(Selectivity)

l        카디널러티(Cardinality, Rows)

l        비용(Cost)

 

선택도(Selectivity)는 특정 행 집합에서 해당 조건을 만족하는 레코드가 차지하는 비율을 가리키는 개념입니다. 행 집합은 테이블 또는 뷰의 전체집합이 될 수도 있고, 조인 또는 Group By 연산에 의한 중간집합일 수도 있습니다.

히스토그램 통계가 없다면 컬럼값이 골고루 분포되어 있다는 가정을 세우고 테이블과 인덱스의 통계정보만을 이용해서 선택도를 계산하게 됩니다. 예를 들어, '=' 조건으로 검색된 특정컬럼의 distinct value가 20으로 분석되어 있다면 선택도는 0.2(=1/20)가 되고, 이는 데이터를 읽는 동안 20개 중 하나씩 조건을 만족하는 레코드를 찾게 될 것이라고 가정하는 것입니다.

만약 히스토그램 정보가 생성되어 있다면 distinct value 값을 이용하지 않고 조건에 사용된 컬럼의 미리 계산된 분포값을 직접 활용하게 되므로 훨씬 정확한 근거를 가지고 비용을 평가할 수 있게 됩니다.

 

Execution Plan

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

   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=2 Card=1 Bytes=32)

   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (Cost=2 Card=1 Bytes=32)

   2    1     INDEX (FULL SCAN) OF 'PK_EMP' (UNIQUE) (Cost=1 Card=15)

 

카디널러티(Cardinality)는 위 실행계획에서 Card로써 표시되는 부분인데, 최종결과건수 혹은 다음 단계로 흘러들어가는 중간결과건수를 의미합니다. 앞에서 계산된 선택도(selectivity)와 전체 레코드 수(num_rows)를 곱해서 계산하게 되는데, 정확한 카디널러티는 좋은 실행계획을 만들기 위한 가장 중요한 정보입니다.

 

비용(Cost)은 위 실행계획에서 Cost로 표시되는 부분으로서, 실행계획 상의 각 연산들을 수행할 때 소요되는 시간비용을 상대적으로 계산한 것입니다. 내부적으로 사용되는 공식에 의해 계산되고, 주로 CPU Cost와 Disk I/O Cost를 고려하게 됩니다.

참고로, 각 연산의 액세스 비용을 평가하는 과정에서 2개의 액세스 비용이 같게 평가된다면 어떤 우선 순위에 따라 결정을 할까요? 예를 들어, 쿼리 최적화를 수행하는 과정에서 2개의 인덱스가 같은 랭킹 또는 같은 액세스 비용을 갖는 경우가 생길 수 있습니다. 이 경우에 옵티아미져는 어떤 인덱스를 사용할지에 대한 결정을 해야 하는데, RBO에서는 rowcache에 나타나는 순서대로 첫번째 것을 선택하고, CBO에서는 인덱스명의 ASCII 값에 근거해서 결정을 내립니다. 예컨대 인덱스 'AAA'와 'ZZZ'가 있을 때 'AAA'를 선택합니다.

 

사실 비용산정 과정에서 옵티마이져는 수많은 가정들을 세우고 계산식을 적용하게 되는데, 그러한 가정들이 항상 성립할 수 없는 불완전한 가정이므로 때로는 잘못된 비용을 산정할 수 밖는 한계를 지니게 됩니다. 그리고 이러한 말 못할 무수히 많은 가정들을 어떻게 풀어 나갈 것인가가 DBMS 벤더들의 고민입니다.

컬럼의 히스토그램 정보를 얼마나 정확히 유지할 것인가? 조건식에 사용된 컬럼들간의 결합형태에 따른 정확한 분포도를 얻을 수 있는가? 서로 밀접한 상관관계를 갖는 컬럼들간의 결합분포도는 어떤 계산식을 사용해야 정확히 산정할 수 있을까? 그렇다고 컬럼들간의 가능한 결합형태에 따라 별도의 히스토그램 정보들을 모두 수집해서 관리할 수도 없는 노릇입니다.

SQL 수행 당시의 시스템 환경, 예를 들면 CPU 상황, Memory 상황, Disk I/O 속도 등에 대한 고려가 중요한 변수인데, 사실 옵티마이져는 이런 실행환경에 대해서 많은 가정들을 세워 최적화를 수행하고 있습니다. 옵티마이져 자체가 특정 상황에 맞추어서 최적화되어 있다는 이야기인데, 각 시스템의 가변적인 환경요인에 의해 생기는 오차를 보정해 주기 위해 옵티마이져에게 도움을 줄 수 있는 몇 개의 초기화 파라미터와 기능들이 있습니다. 이에 대해서는 다음 칼럼을 통해 설명드리겠습니다.

 

 

Leave Comments