ORACLE_011. OPTIMIZER - Understanding the Cost-Based Optimizer

OPTIMIZER - Understanding the Cost-Based Optimizer                        

 CBO는 어떤 접근경로가 가장 효율적인지 결정합니다. 이 경로는 SQL문에 의해 선택되어지는 스키마 오브젝트의 통계에 기반하여 정보를 만들어 냅니다. 또한 CBO는 SQL구문에서 제안하는 HINT 절 역시 접근경로를 결정하는데 있어 하나의 고려대상입니다.

 

 CBO는 다음과 같은 순서로 진행합니다.

  1. 옵티마이저는 유효한 접근경로와 힌트절에 기반하여 SQL 구문을 수행할 수 있는 실행 가능한 계획을 생성합니다.
  2. 옵티마이저는 구문에 의해 접근되어질 테이블, 인덱스, 파티션의 통계에 기반하여 각각의 계획에 따른 비용을 계산합니다.

   비용이란 특정한 계획으로 구문을 수행할때 필요한 예상되어지는 리스소 사용량과 비례합니다.
   옵티마이저는 접근경로의 비용값과 I/O, CPU, Memory 사용값을 합쳐 계산하게 됩니다.

   높은 비용을 소요하는 시리얼 계획은 작은 비용을 소요하는 계획들에 비해 많은 시간이 소요됩
   니다. 하지만 어떤 특정한 계획을 수행할시 자원소모량과 수행시간은 직접적으로 연관되진 않습
   이다. 

  3. 옵티마이저는 이러한 계획들이 소모할 비용을 비교하고 가장 비용이 적게 들어가는 계획을 수행합니다.

COMPONENT OF THE CBO
 CBO는 다음 세가지의 주요 요소로 구성되어 있습니다.
 
  - Query Transformer
  - Estimator
  - Plan Generator

                 그림) CBO Components (www.oracle.com)

QUERY TRANSFORMER

 Query Transformer (이하 QT)로 들어오는 입력값들은 쿼리블럭셋으로 표현된 파싱된 쿼리 입니다.  쿼리블럭들은 독립적이거나 내부적으로 연관지어져 있습니다. 쿼리의 형식은 쿼리블럭들이 어떻게 내부적으로 연관되어 있는지 정의합니다. QT의 주 역할은 쿼리의 폼을 변형시켜 좀더 나은 실행계획을 세울 수 있는지 결정하는 것 입니다. 4개의 방법으로 이를 수행합니다.

 

View Merging  && Predicate Pushing && Subquery Unnesting && Query Rewrite with Materialized  View

 

Detail (English)

View Merging

  Each view referenced in a query is expanded by the parser into a separate query block. The query block essentially represents the view definition, and therefore the result of a view. One option for the optimizer is to analyze the view query block separately and generate a view subplan. The optimizer then processes the rest of the query by using the view subplan in the generation of an overall query plan. This technique usually leads to a suboptimal query plan, because the view is optimized separately from rest of the query.

  The query transformer then removes the potentially suboptimal plan by merging the view query block into the query block that contains the view. Most types of views are merged. When a view is merged, the query block representing the view is merged into the containing query block. Generating a subplan is no longer necessary, because the view query block is eliminated.

Predicate Pushing

  For those views that are not merged, the query transformer can push the relevant predicates from the containing query block into the view query block. This technique improves the subplan of the nonmerged view, because the pushed-in predicates can be used either to access indexes or to act as filters.

Subquery Unnesting

  Like a view, a subquery is represented by a separate query block. Because a subquery is nested within the main query or another subquery, the plan generator is constrained in trying out different possible plans before it finds a plan with the lowest cost. For this reason, the query plan produced might not be the optimal one. The restrictions due to the nesting of subqueries can be removed by unnesting the subqueries and converting them into joins. Most subqueries are unnested by the query transformer. For those subqueries that are not unnested, separate subplans are generated. To improve execution speed of the overall query plan, the subplans are ordered in an efficient manner.

Query Rewrite with Materialized Views

  A materialized view is like a query with a result that is materialized and stored in a table. When a user query is found compatible with the query associated with a materialized view, the user query can be rewritten in terms of the materialized view. This technique improves the execution of the user query, because most of the query result has been precomputed. The query transformer looks for any materialized views that are compatible with the user query and selects one or more materialized views to rewrite the user query. The use of materialized views to rewrite a query is cost-based. That is, the query is not rewritten if the plan generated without the materialized views has a lower cost than the plan generated with the materialized views.
 

 

ESTIMATOR
 ESTIMATOR는 Selectivity, Cardinality, Cost 세가지 방법으로 견적을 뽑아내는데 이 방법들은 서로간 정보를 전달하는 방식으로 연관되어 있습니다.

 

 Selectivity

 첫번째 측정자인 Selectivity는 Row set 에서 단편화된 행을 나타냅니다. Row set은 기본 테이블, 뷰 혹은 Group By 단서를 이용한 JOIN 구문의 결과들을 말합니다. Selectivity 는 last_name='Smith' 혹은 last_name='Smith' AND job_type='Clerk' 과 같은 쿼리의 술부로 엮여 있습니다. 술부는 Row set에서 수개의 행을 솎아내는 역할을 합니다. 따라서 술부의 Selectivity 는 술부 테스트에서 얼마나 많은 행이 Row set에서 통과가 되는지를 나타냅니다. Selectivity는 0.0 부터 1.0까지의 값을 가지는데 0.0은 Row set에서 선택되어지는 행이 하나도 없음을 뜻하고 1.0은 모든 행이 선택되어진다는 의미 입니다.

  Estimator 는 사용 가능한 통계정보가 없다면 Selectivity 의 내부 기본값을 사용합니다. 술부의 형식에 따라서 이 기본값은 다른 값을 이용합니다. 술부 등가식의 기본 내부값은 (ex. last_name='Smith')이 범위식(ex. last_name > 'Smith') 의 값보다 작습니다.  이는 Estimator가 등가식은 범위식보다 다 적은 수의 행을 반환한다고 생각하기 때문입니다.

  통계정보가 유효하다면 Selectivity를 계산하기 위해 이를 이용합니다. 예를들어 등가식의 경우 (last_name='Smith') last_name의 중복되는 n개의 행을 역수로 설정하는데,  이는 중복값 n의 범위 바깥에 있는 하나의 값만 가지고 있는 모든 행을 선택하기 때문입니다. last_name에 히스토그램이 유효하다면 중복값 대신 히스토그램을 사용합니다. 이 히스토그램은 컬럼의 중복되지 않은 값들에 대한 분산정도를 가지고 있어서 Selectivity를 계산하는데 더 좋은 이익을 가져다 줍니다. 넓은 범위의 중복된 많은 n개의 값(Skew data)을 가지고 있는 컬럼에 대한 히스토그램은 CBO를 생성하는데 좋은 selectivity 값을 계산해 냅니다.

 

 Cardinality
  Cardinality는 Row set에 몇개의 행이 있는지 나타냅니다. 여기에서 Row set이란 Table, View, Join, 혹은 Group by 구문을 이용한 질의 결과들의 모음을 말합니다.

 

  Base Cardinality

   기반 테이블의 행 갯수 입니다. Cardinality 의 기본값은 테이블의 통계 정보를 수집함으로써 얻을 수 있습니다. 테이블 통계정보가 존재하지 않으면 (혹은 유효하지 않다면) Estimator는 테이블이 사용하고 있는 Extent 의 갯수를 이용하여 Cardinality 의 기본값을 설정합니다.

  Effective Cardinality
   기반 테이블에서 선택된 행의 갯수 입니다. Effective Cardinality는 기반 테이블에서 각각의 술부가 성공적으로 필터링을 수행한 것과 더불어 기반 테이블의 각각의 컬럼에 정의되어 있는 술부에 따라 변합니다. Effective Cardinality는 기반 Cardinality를 생성하는 것 처럼 산출되어지고 테이블에 정의된 모든 술부의 Selectivity 를 섞습니다. 테이블에 술부가 존재하지 않을경우 Effective Cardinality 는 Base Cardinality 와 같습니다.

  Join Cardinality
   두개의 Row set이 서로 Join 하여 생긴 테이블의 행의 갯수 입니다. JOIN 은 두 Row set의 카르테시안 프로덕트(Cartesian product)와  함께 술부가 필터로서 결과를 생성하는 join 입니다. 따라서 Join Cardinality 는 join 구문의 Selectivity 에 의해 복합적으로 생성된 두 Row set의 Cardinalities 입니다.

  Distinct Cardinality
   Row set 에 존재하는 중복되는 행의 갯수 입니다. Row set 의 Distinct Cardinality 는 컬럼이 가지고 있는 데이터에 기반하고 있습니다. 예를들오 100개의 Row set중에 중복되는 값이 20개이면 Distinct Cardinality 는 20 입니다.

  Group Cardinality
   GROUP BY 명령이 수행된 후 생성된 Row set의 행 갯수 입니다.  GROUP BY 구문은 Row set의 행의 갯수를 줄이는데 효과적입니다. Group Cardinality는 각 그룹핑된 컬럼의 중복된 cardinality 와 Row set의 행 갯수에 따라 변합니다.

   Example of Group Cardinality
    중복되는 Cardinality 값이 20이고 colX를 Group by 로 묶은 100개의 행을 가진 Row set 이라면

    Group Cardinality 값은 30입니다.

    하지만 똑같이 colX와 colY로 그룹된 100개의 행을 가지고 있는 Row set에서 각각의 Distinct
    Cardinality 가 30 과 60이라고 가정해 봅시다. 이 경우 Group Cardinality 는 colX와 colY의 Distinct
    Cardinality 값의 최대값, 그리고 colX와 colY중 작은 Distinct Cardinality 값과 Row set 의 행 갯수
    를 곱한 값의 사이값이 됩니다.

  예문에 있는 Group Cardinality 는 다음과 같은 표현식으로 나타낼 수 있습니다.
     group cardinality lies beetween max ( dist.card.colX , dist.card.colY)
                                                             min ( (dist.card.colX * dist.card.colY), num rows in row set)

 Cost
  Cost는 작업의 단위(Unit of Work) 혹은 자원 사용량을 나타냅니다. CBO는 단위 작업당 Disk I/O, CPU, Memory 사용량을 이용합니다. 따라서 CBO에 의해 사용된 Cost는 명령을 수행하는 동안의 Disk I/O 횟수, CPU와 Memory 사용 횟수를 나타냅니다. 작업은 테이블 스캐닝, 인덱스를 이용한 행으로의 접근, 두 테이블의 Join, 혹은 Row set의 정렬이 될 수 있습니다. 쿼리 계획의 Cost 는 쿼리가 수행되고 결과를 생성할때 야기되는 예상되어지는 작업 단위의 갯수입니다.

  접근 경로(Access Path)는 기반 테이블에서 데이터를 가져올때 요구되는 작업 단위를 결정합니다. 접근 경로는 테이블 스켄, Fast Full Index scan, 혹은 Index Scan 이 될 수 있습니다. 테이블스켄이나 Fast Full Index scan 을 수행하는 동안 많은 블럭들이 싱글 I/O 로 데이터를 읽어드립니다. 그러므로 테이블 스켄과, Fast Full Index scan은 읽혀지는 블럭의 갯수와 multiblock_read_count 의 값에 의해 좌우 됩니다. Index scan의 Cost는 B-tree의 레벨과 스캔된 index leaf 블럭수, 그리고 인덱스 키에 있는 row id를 이용해 추출되는 행의 갯수에 의해 좌우 됩니다. Rowid를 이용하여 행을 뽑아내는 일은 Index clustering Factor 값에 의해 결정됩니다.

  Clustering Factor가 index의 등록된 값 일지라도 Clustering Factor는 테이블의 데이터 블럭에 있는 비슷한 인덱스 컬럼값에 대한 분포도에 영향을 받습니다. 낮은 Clustering factor값은 테이블의 적은 데이터 블럭에 집중적으로 각각의 행이 모여있음을 나타냅니다. 반대로 높은 값은 각각의 행들이 여러 블럭들에 무작위로 퍼져 있음을 나타냅니다. 그러므로 높은 Clustering Factor는 rowid를 이용하여 행을 추출하는 범위 스캔(Range scan)에서 좀더 많은 Cost가 소요되게 됩니다.

 

 

FIN
REF) Oracle Documents (Server .920)/a96533 "Introduction to the Optimizer"