데이터베이스 시스템(DBMS)의 핵심 기능으로, 사용자가 요청한 관계 대수 표현식(Relational-Algebra Expression)을 실행하는 가장 효율적인 방법을 찾는 과정

목표는 요청된 결과를 정확히 계산하면서도 가장 적은 비용(Least-costly)이 드는 쿼리 실행 계획(Query-Evaluation Plan)을 선택하는 것이다.

앞 글들에서 효율적인 비용에 대해서 다루었다.

쿼리 최적화는 크게 두 가지 핵심 단계로 진행한다.

대체 계획 생성 (Generating Alternative Plans)

주어진 관계 대수 표현식(쿼리)을 동일한 결과를 내는 다양한 다른 표현식으로 변환하고, 각 표현식에 해당하는 실행 계획을 생성하는데 이때 주로 관계 대수 법칙(Relational-Algebra Equivalences)을 적용하여 Equivalence Rules 을 지키면서 이루어진다.

• 왼쪽 그림은 데이터를 쌩 조인한다. 그래서 데이터의 크기가 불필요하게 크다.

• 오른쪽 그림은 데이터를 한번 셀렉션으로 줄인 후 조인하여 중간 계산의 크기가 줄었다.

---

Equivalence Rules

이 규칙들은 데이터베이스 쿼리 최적화(Query Optimization)의 핵심 기반이다. 관계 대수 규칙을 사용하여 쿼리 표현식을 변형하면, 논리적으로는 동일한 결과를 내면서도 훨씬 효율적인 실행 계획을 생성할 수 있다. 무려 12가지나 있으니 마음을 단단히 먹어야 한다.

---

1. 선택 연산의 분해 (Deconstruction of Conjunctive Selection)

$\sigma_{\theta_1 \wedge \theta_2}(E) = \sigma_{\theta_1}(\sigma_{\theta_2}(E))$

• 예: $A=5$ AND $B>10$ 같이 두 가지 선택 조건을 가진 하나의 선택 연산은 개별 조건들로 이루어진 순차적인 선택 연산으로 분해될 수 있다

중간 결과가 작게 나오면 계산량이 줄어든다

---

2. 선택 연산의 교환 법칙 (Commutativity of Selection)

$\sigma_{\theta_1}(\sigma_{\theta_2}(E)) = \sigma_{\theta_2}(\sigma_{\theta_1}(E))$

• 순차적인 선택 연산은 그 순서가 바뀌어도 동일한 결과를 산출한다.

중간 결과가 작게 나오면 계산량이 줄어든다

---

3. 투영 연산의 중복 제거 (Omission of Projection)

$\Pi_{L_1}(\Pi_{L_2}(\dots \Pi_{L_n}(E) \dots)) = \Pi_{L_1}(E)$

• 연속된 투영 연산에서는 가장 마지막 투영($\Pi_{L_1}$)만 필요하며, 그 이전의 투영 연산들은 생략될 수 있습니다. (단, $L_1 \subseteq L_2 \subseteq \dots \subseteq L_n$이 성립해야 함)

가장 마지막 계산 한번만 하면 계산량이 줄어든다

---

4. 선택 연산과 조인/카테시안 곱의 결합 (Combination of Selection with Joins/Cartesian Products)

$\sigma_{\theta}(E_1 \times E_2) = E_1 \bowtie_{\theta} E_2$

• 카테시안 곱에 이어서 $\theta$ 조건을 적용하는 것은 $\theta$ 조인과 동일하다 (당연한 말) 실제로 DBMS는 카테시안 곱($\times$)을 수행한 후 필터링하는 대신, $\theta$ 조인 알고리즘(NLJ, Hash Join 등)을 사용하여 훨씬 효율적으로 결과를 계산한다고 한다

---

5. $\theta$-조인/자연 조인의 교환 법칙 (Commutativity of Joins)

$E_1 \bowtie_{\theta} E_2 = E_2 \bowtie_{\theta} E_1$

조인 순서 최적화의 핵심

• 조인 연산($\theta$ 조인 또는 자연 조인)에서 피연산자($E_1$과 $E_2$)의 순서는 바뀌어도 동일한 결과를 산출한다. Nested-Loop Join에서는 더 작은 테이블을 Outer Relation으로 선택하는 것이 유리한데, 이 규칙을 통해 옵티마이저는 가장 비용이 적게 드는 조인 순서를 결정할 수 있다.

---

6. 조인 연산의 결합 법칙 (Associativity of Joins) - 중요

$(E_1 \bowtie E_2) \bowtie E_3 = E_1 \bowtie (E_2 \bowtie E_3)$

• 세 개의 릴레이션을 조인할 때, 어떤 두 릴레이션을 먼저 조인하든 결과는 동일하다.

중간 결과의 크기가 작게 되도록

---

7. 선택 연산의 조인 분배 법칙 (Distribution of Selection over Join) - 중요

$\sigma_{\theta_0}(E_1 \bowtie_{\theta} E_2) = (\sigma_{\theta_0}(E_1)) \bowtie_{\theta} E_2$

• 선택 연산을 조인 연산보다 먼저 수행하여 조인에 참여하는 데이터의 크기를 줄이는 데 사용

선택 연산 - 조인 연산 -> 선택 연산 먼저 !!! (완전히 분배되는 경우에만)

---

8. 투영 연산의 조인 분배 법칙 (Distribution of Projection over Join)

조건: 조인 조건 $\theta$가 $L_1 \cup L_2$에 있는 속성들만 포함할 때.

$\Pi_{L_1 \cup L_2}(E_1 \bowtie_{\theta} E_2) = \Pi_{L_1}(E_1) \bowtie_{\theta} \Pi_{L_2}(E_2)$

• 최종 결과에 필요 없는 속성들을 조인 전에 미리 제거하여 데이터 크기를 줄인다.

---

9. 합집합/교집합의 교환 법칙 (Commutativity of Set Operations)

$E_1 \cup E_2 = E_2 \cup E_1$

$E_1 \cap E_2 = E_2 \cap E_1$

• 합집합($\cup$)과 교집합($\cap$) 연산은 피연산자의 순서와 관계없이 동일한 결과를 산출

• 차집합($-$)은 교환 법칙이 성립하지 않는다

---

10. 합집합/교집합의 결합 법칙 (Associativity of Set Operations)

$(E_1 \cup E_2) \cup E_3 = E_1 \cup (E_2 \cup E_3)$

$(E_1 \cap E_2) \cap E_3 = E_1 \cap (E_2 \cap E_3)$

• 세 개 이상의 집합 연산은 어떤 순서로 묶어 연산하든 결과는 동일

합-합-합 이나 교-교-교 는 어떻게 해도 같다

---

11. 선택 연산의 집합 연산 분배 법칙 (Distribution of Selection over Set Operations)

$\sigma_{\theta}(E_1 \cup E_2) = \sigma_{\theta}(E_1) \cup \sigma_{\theta}(E_2)$

$\sigma_{\theta}(E_1 \cap E_2) = \sigma_{\theta}(E_1) \cap \sigma_{\theta}(E_2)$

$\sigma_{\theta}(E_1 - E_2) = \sigma_{\theta}(E_1) - \sigma_{\theta}(E_2)$

• 집합 연산 전에 필터링을 수행하여 데이터 크기를 줄인다

---

12. 투영 연산의 합집합 분배 법칙 (Distribution of Projection over Union)

$\Pi_{L}(E_1 \cup E_2) = (\Pi_{L}(E_1)) \cup (\Pi_{L}(E_2))$

• 투영 연산은 합집합 연산에 대해 분배될 수 있다

---

최종 정리

엄밀히 분배되는 상황 아래에서는 Selection (σ) > Projection(Π) > Join (⋈)

the selection as early as possible reduces the size of the relation to be joined
("선택 연산을 가능한 한 빨리(조기에) 수행하는 것은 조인되어야 할 릴레이션(테이블)의 크기를 줄여줍니다.")

Performing the projection as early as possible reduces the size of therelation to be joined
("투영 연산을 가능한 한 빨리(조기에) 수행하는 것은 조인되어야 할 릴레이션(테이블)의 크기를 줄여줍니다.")