[데이터베이스] 질의 처리와 최적화 - (1)

 

질의 처리 단계(Query Processing Procedure)

---

 

1. parsing과 translation:

 

parser는 사용자가 작성한 질의의 문법이 맞는지 확인하고, 질의를 parse tree로 변환한다.

 

그 후 parse tree는 관계 대수 표현식으로 변환된다.

 

 

 

2. optimization:

 

먼저, 하나의 관계 대수식에 대해 동등한 관계 대수식을 가지는 많은 수의 질의 평가 계획(query execution plan)을 생성된다.

 

 

그 후, 각 질의 평가 계획을 구성하고 있는 relational operation들이 수행되었을 때 result size를 통계적으로 추정한다.

 

이때, 딕셔너리 데이터베이스에 저장되어 있는 통계적 수치들을 이용해서 result size를 추정하게 된다.

(튜플의 개수, 각 튜플의 크기, 한 속성에서 서로 다른 값들의 개수, 한 릴레이션에서 한 속성의 최솟값/최댓값 등)

 

각 operation들의 비용을 계산해야 하는데, 비용을 계산하기 위해서는 input의 크기를 알아야 하기 때문에 이 과정이 필요하다.

 

 

그 후, 각 질의 평가 계획과 그 계획 내에 포함되는 operation의 추정된 크기 정보를 이용해 각 pyhsical plan을 고려한다.

 

각 operation은 다양한 알고리즘을 사용해서 구현될 수 있으므로, 다양한 physical plan이 생성된다.

(select - linear scan or index 1, join - nested loop join or hash join or merge join 등)

 

 

그 후, 각 physical plan에 대해서 실행 비용을 추정한다.

 

앞에서 계산된 각 operation의 result size와 operation의 종류를 통해서 각 operation의 비용을 추정할 수 있고, physical plan에 포함된 모든 operation 비용의 합이 physical plan의 비용이다.

 

 

마지막으로, 모든 physical plan들 중 비용이 가장 적게 드는 최적의 plan을 선택한다.

 

 

 

3. evaluation:

 

질의 수행 엔진(query-execution engine)이 선택된 질의 평가 계획을 받아들이고 그 계획을 수행한 후, 질의에 대한 결과를 넘겨준다.

 

 

 

 

 

 

관계형 표현식의 변환(Transformation of Relational Expression)

---

 

모든 적법한 데이터베이스 인스턴스에 대해 두 표현식이 동일한 결과 튜플을 만들어 낼 때, 두 개의 관계 대수 표현식은 동등(equivalent)하다고 한다.

 

이때, 동등 규칙은 두 가지 형태의 표현식이 동등하다는 것을 나타낸다.

 

 

 

- 동등 규칙(Equivalence rule)

 

1. 선택 연산의 논리곱은 선택 연산의 순차열로 분해할 수 있다.

 

 

2. 선택 연산은 교환 법칙이 성립한다.

 

 

3. 일련의 추출 연산 중 마지막 연산만 필요하고 나머지는 생략될 수 있다. 

 

 

4. 선택 연산은 카티션 곱이나 세타 조인과 결합한다.

 

 

5. 세타 조인 연산은 교환 법칙이 성립한다.

 

 

6.

a. 자연 조인 연산은 결합 법칙이 성립한다.

 

 

b. 세타 조인 연산은 다음과 같은 방법으로 결합 법칙이 성립한다.

 

 

7. 선택 연산은 다음과 같은 두 가지 조건하에서 세타 조인 연산에 배분될 수 있다.

 

a. 선택 조건 $\theta_{1}$이 조인에 참여하는 두 표현식 중 하나의 표현식에만 관련 있을 경우 다음과 같이 선택 연산이 배분된다.

 

 

b. 선택 조건 $\theta_{1}$이 $E_{1}$의 속성에만 연관이 있고, 선택 조건 $\theta_{2}$이 $E_{2}$의 속성에만 연관이 있으면 다음과 같이 선택 연산이 배분된다.