[데이터베이스] Chapter 16. Query Optimization

Reference
1. Database System Concepts-Abraham Silberschatz, Henry Korth, S. Sudarshan
2. Database System class by Professor Yon Dohn Chung, Department of Computer Science and Engineering, Korea University

중요한 내용 위주로 요약 & 정리하였습니다.

이번 글만 특별히 수식이 많아 이미지로 대체했습니다

목차

1. Introduction
2. Transformation of Relational Expressions
3. Catalog Information for Cost Estimation
4. Statistical Information for Cost Estimation
5. Cost-based optimization
6. Dynamic Programming for Choosing Evaluation Plans
7. Additional Optimization Techniques

16.1 Introduction

• evaulation plan: 각 operation의 알고리즘과 실행이 어떻게 연결되었는지를 표현

• equivalence rules: logical equivalent plan을 만들기 위해 사용

---

16.2 Transformation of Relational Expressions

두 relational algebra expression이 모든 legal database instance에서 동일한 tuple의 set을 생성한다면, 둘은 equivalent 하다고 표현한다.

16.2.1 Equivalence Rules

16.2.2 Examples of Transformations

Equivalence Rule을 활용하여 동일한 tuple set을 생성하는 logical plan들을 만들 수 있다.

Pushing Selections: join할 tuple 수를 미리 줄이는 것

⇒ 먼저 select한 이후에 join을 실시하여 비용을 줄였다.

Multiple Transformations

Pushing Projections: join할 relation의 size를 줄이기 위한 projection

16.2.3 Join Ordering

join의 순서를 잘 정하면 temporary result의 size를 줄일 수 있다. 따라서 query optimizer는 많은 비용을 들여 join order를 최적화시킨다.

16.2.4 Enumeration of Equivalent Expressions

query optimizer는 주어진 expression에 대해서 가능한 모든 equivalent expression을 생성하고 모두 cost를 계산해야 할까? 이는 매우 비효율적일 것이다. 따라서 Space/Time optimization 를 실시하고 heuristics 를 사용한다.

Choice of Evaluation Plans

또한, evaluation plan을 선택할 때는 globally하게 알고리즘을 분석해야 한다. 예를 들어 merge-join 은 hash join 보다 비용은 비싸지만, 다음 단계에서 이득을 보기 때문에 merge-join을 선택해야 하는 경우도 있다.

Cost-Based Optimization

r1 부터 rn 까지의 join에 대해서 최적의 join-order을 구하기 위해서는 매우 많은 경우의 수를 검토해야 한다. 이를 최적화하기 위해서 Dynamic Programming 을 사용한다. sub problem들로 n relation의 Set을 나누어서 풀이한다.

Heuristic Optimization

cost-based 최적화는 d.p를 사용하더라도 비싸다. 따라서 휴리스틱을 이용하여 비용을 줄여보자.

Structure of Query Optimizers

• Heuristics + Cost-based optimization
• left-deep join orders 만 고려
• plan caching
• 비용이 싼 쿼리는 간단한 휴리스틱을, 비싼 쿼리는 복잡한 휴리스틱을 사용한다.
• 최적화가 어려운 경우 단순 무식하게 수행한다.
• DBMS 구현에 따라 다르다.

---

16.3 Statistical Information for Cost Estimation

• cost estimation을 위해서 미리 만드는 정보들이다.

16.3.1 Catalog Information

Histogram

• 일부를 샘플링하여 만드는 통계정보
• data 변경 시 통계정보를 주기적으로 갱신한다.

16.3.2 Selection Size Estimation

16.3.3 Join Size Estimation

16.3.4 Size Estimation for Other Operations

---

+) Materialized Views

• 미리 계산되어 저장된 값을 사용한 view → 매번 계산 x
• event 발생 시 특정 작업을 수행하여 유지한다.
• Incremental view maintenance : 바뀐 부분만 수정

+) Multiquery Optimization

• 많은 사용자들이 동시에 사용 or 비슷한 쿼리는 같이 실행시킨다.