Query Optimization 개요

SQL과 Query Optimization의 필요성

• SQL은 결과를 명시할 뿐 절차를 지시하지 않는 선언적 언어(Declarative language)임
• 따라서 DBMS는 SQL 문을 실행 가능한 Query Plan으로 변환해야 하며, 이 과정에서 성능 최적화가 필수적으로 요구됨
• 동일한 쿼리라도 데이터를 결합하고 탐색하는 알고리즘에 따라 성능 차이가 매우 크므로, 가장 비용이 적게 드는(Cheapest) 계획을 찾는 것이 최적화의 핵심 목표임
  • 쿼리 최적화는 NP-hard 문제이기에 이를 잘 해결하는 것이 중요함

최적화 전략의 2가지 접근법

Heuristics / Rules (휴리스틱 및 규칙 기반)

• 쿼리의 비효율적인 구조를 정적인 규칙에 따라 재작성(Rewriting)하여 최적화함. 데이터의 실제 내용을 보지 않고 카탈로그 정보만으로 논리적 구조를 개선함

Cost-based Search (비용 기반 탐색)

• 동등한 여러 실행 계획들에 대해 예상 비용을 추정(Estimate)하는 모델을 사용하여, 가장 낮은 비용의 계획을 선택함

Logical vs Physical Plans

• Logical operators: 무엇을 수행할지 정의함 (예: Union, Selection, Projection, Join 등)

• Physical operators: 실제 어떻게 구동할지 정의함 (예: Nested loop join, Hash join, Index join 등)

• 논리적 계획과 물리적 계획이 항상 1:1로 매핑되는 것은 아니며, 물리적 포맷(압축, 정렬 상태 등)에 따라 다양한 알고리즘이 적용될 수 있음

• 질의 처리 파이프라인

  

  1. Parse: SQL Query를 입력받아 파싱하여 Parse Tree 생성
  2. Convert: Parse Tree를 변환하여 초기 Logical Query Plan 생성
     • Equivalence rules를 통해서 여러 Logical Plan 생성
  3. Apply rules: 관계대수 법칙을 적용하여 구조를 개선한 "Improved" Logical Query Plan 도출
  4. Estimate result sizes: 데이터 통계를 기반으로 중간 산출물의 크기(Size)를 추정
  5. Consider physical plans: 크기 정보가 결합된 논리 계획을 바탕으로 다수의 Physical Plan 후보군 생성
  6. Estimate costs: 여러 후보 계획들의 실행 비용을 산출
  7. Pick best & Execute: 가장 비용이 낮은 최적의 계획을 선택하여 런타임에 실행하고 최종 결과를 반환함