[DB] Query Optimization

query optimization

SQL 쿼리가 주어질 때 최단 시간내에 출력될 수 있는 최적의 query plan을 선택하는 작업, 특히 쿼리가 복잡한 경우 일반적으로 주어진 쿼리를 처리하기 위해 많은 전략에서 가장 효율적인 쿼리 평가 계획을 선택하는 프로세스

평가 계획은 각 작업에 사용되는 알고리즘과 작업 실행이 조정되는 방법을 정확하게 정의한다. 

query optimize를 하는 이유 : temporary result의 사이즈를 줄이기 위해

 

*cost-based query optimization

1) 동등성 규칙을 사용하여 논리적으로 동등한 식을 생성

 

2) 결과 식에 주석을 달아 대체 쿼리 계획을 가져온다.

 

3) 예상 비용을 기준으로 가장 저렴한 요금제 선택

 

평가 계획을 세울때는 관계에 대한 통계적 정보와 중간결과에 대한 통계적 추정 , 통계를 사용하여 계산된 알고리즘에

대한 비용공식이 사용된다.

 

 

Equivalence Rule(동등 규칙) 

동등성 규칙 집합은 다른 규칙의 어떤 조합에서도 파생될 수 없는 경우 최소라고 한다.

1. 연결 선택 작업은 일련의 개별 선택으로 분해될 수 있다.

 

2. selection 명령은 교환 법칙이 성립한다.

 

3. 마지막 순서의 projection만 필요하다면 나머지 projection 명령은 생략해도 된다.

 

4. selection 연산은 cartesian product와 Theta join으로 결합될 수 있다.

 

 

5. Theta join은 교환 법칙이 성립한다.

 

6-(1). natural join은 동일하다.

 

6-(2). Theta join 상황에 따라 동일하다. (’세타 2’가 ‘E2’와 ‘E3’ 속성만을 포함할 때)

 

7. selection 연산에서 Theta join과 (a), (b) 상황에서 구별된다.

 

(a) ‘세타 0’의 모든 속성이 ‘E1’ 가 결합되는 식중 하나의 속성만 포함 하는 경우

 

-> 테이블 E1과 E2는 각각 1000개의 튜플을 가지고 있다고 하자. (조건은 ‘세타 0’ 조건을 만족하는 것은 10개밖에 없다고 가정하자)

 

왼쪽 식에서는 먼저 조인을 시도 한다. 각각 1000개니까 조인하면 100만개이다. 그리고 나서 ‘세타 0’ 조건을 만족하는 튜플을 빼내고 있다.

 

이에 반해 오른쪽 식에는 먼저 ‘세타 0’ 조건을 만족하는 튜플을 select한 후 조인을 하고 있다. 그렇다면 10 * 1000개 뿐이다.

 

그러므로 select연산은 대체적으로 먼저 진행 한 후 조인을 하는 것이 빠르다.

 

(b) ‘세타 1’가 ‘E1’의 속성만을 포함하고 ‘세타 2’가 ‘E2’의 속성만을 포함할 때

 

8. projection 연산은 Theta join에서 다음과 같은 상황에서 구별된다.

 

(a) ‘세타’가 ‘L1’과 ‘L2’의 합집합의 속성만을 포함할 때

 

(b) ‘E1’과 ‘E2’의 join 하는 상황을 고려

 

 

 

 

 

Statistical Information for Cost Estimation

만약 우리가 정확한 통계를 유지하기를 원한다면 매 순간 relation을 수정할 때마다, 우리는 통계를 업데이트 해야한다.

-> 상당한 오버헤드 유발!

 

많은 시스템들은 매번 수정 할때마다 통계를 업데이트 하지 않는다. 그대신 system load가 낮을 때만 통계를 업데이트 한다.

 

결과에 따르면 query-processing을 선택하는데 사용되는 통계는 엄청 정확하지는 않다. 하지만 통계에서 업데이트들 사이 간격에 너무 많은 업데이트가 일어나지 않는다는 가정하에 통계는 충분히 정확하다.

ex)