[Database] DBA급 개발자로 - #13 Rule based 쿼리 최적화

이전 포스팅에서는 쿼리 요청을 어떻게 병렬 처리하는지 살펴봤습니다. 이번 포스팅에서는 쿼리를 최적화할 수 있는 방법에 대해 살펴보겠습니다. 

Query Optimization 

쿼리는 다양한 방법으로 최적화할 수 있습니다. 첫 번째 방법은 잘못됐거나 비효율적인 쿼리 문장을 제거하는 heuristic / rule 방식의 최적화 방법이 있습니다. 두 번째 방법은 쿼리 수행에 필요한 예상 비용을 비교해서 비용이 가장 작은 쿼리 플랜을 선택하는 cost based 방법이 있습니다. 이번 포스팅에서는 heuristic / rule 기반의 최적화 방식에 대해 살펴보겠습니다. 

Relational Algebra Equivalance

Relational algebra 표현식이 서로 다르더라도 결괏값이 동일하면 해당 relational algebra 표현식은 동일하다고 할 수 있습니다. DBMS는 이 원리를 통해 쿼리 최적화를 수행합니다. 

Predicate Pushdown 

조건절을 더 아래 단계의 쿼리에서 처리하도록 pushdown 해서 최적화하는 방법입니다. 다음과 같은 쿼리를 predicate pushdown을 통해 어떻게 처리하는지 살펴보겠습니다. 

SELECT student.name, class.id
FROM student, class  
WHERE student.cid = class.id 
AND class.grade = 10

Predicate Pushdown

"where class.grade=10"이라는 predicate operator를 더 아래 단계에서 수행함으로써 미리 데이터를 필터링해 더 적은 수의 데이터만 가져오도록 최적화할 수 있습니다. 위 사진의 쿼리 플랜을 각각 relational algebra 표현식을 통해 나타내면 다음과 같습니다. 

$$ \boldsymbol{project}_{student.name, class.id}(\boldsymbol{where}_{class.grade=10}(\boldsymbol{join}_{student, class})) $$

$$  \boldsymbol{project}_{student.name, class.id}(\boldsymbol{join}_{student, class(\boldsymbol{where}_{class.grade=10})}) $$

위의 표현식은 동일한 결과값을 반환하기 때문에 relational algebra 관점에서 동일한 것으로 간주할 수 있습니다. 따라서 DBMS는 relational algebra의 관점에서 동일한 표현식 중 가장 최적의 표현식을 선택해서 쿼리 요청을 처리합니다. 

 

Logical Query Optimization 

논리적인 방법으로 쿼리를 최적화할 수 있습니다. 

Split Conjunctive Predicate 

큰 predicate operator을 작은 단위로 분리함으로써 optimizer가 분리된 predicate operators를 쉽게 옮겨서 최적화할 수 있도록 하는 방식입니다. 다음 쿼리를 어떻게 최적화하는지 살펴보겠습니다. 

SELECT student.name
FROM student, class, school
WHERE student.cid = class.id 
AND class.sid = school.id 
AND school.location = 'SEOUL'

Split Conjunctive Predicate

위의 쿼리는 큰 덩어리인 predicate operator(where 절)을 잘게 분해해서(split conjunctive predicate) 쿼리 실행의 아래 단계로 이동시킴으로써(predicate pushdown) 최적화를 수행합니다. 

Replace Cartesian Products 

Cartesian 곱의 형태로 실행될 수 있는 쿼리를 inner join이 가능하다면 inner join으로 변형해서 최적화하는 방식입니다. 

Replacing Cartesian Products

Projection Pushdown 

Projection operator을 쿼리 실행의 아래 단계로 옮겨 미리 materialization을 수행합니다. 불필요한 데이터를 미리 제거함으로써 최적화하는 방식입니다. 

Projection Pushdown

Nested Sub-queries

Where 절에 사용되는 nested sub-query를 최적하는 대표적 방식은 다음과 같습니다. 

Rewrite Nested Sub-queries 

Nested sub-query를 변형시키는 방법입니다. 

SELECT name 
FROM student AS s 
WHERE EXISTS (
    SELECT * 
    FROM class AS c 
    WHERE s.cid = c.id 
    AND c.grade = 5 
)

위와 같은 쿼리는 다음과 같이 최적화될 수 있습니다. 

SELECT name 
FROM student AS s, class AS c 
WHERE s.cid = c.id 
AND c.grade = 5

Decompose Nested Sub-queries 

두 번째 방법으로는 nested sub-query를 실행시켜 결괏값을 임시 테이블에 저장해서 사용하는 방식입니다. 

SELECT s.name, c.name 
FROM student AS s, class AS c 
WHERE s.cid = c.id 
AND s.score = (SELECT max(s.score) FROM student s2 GROUP BY s.cid)

DBMS는 위 쿼리를 처리할 때 "(SELECT max(s.score) FROM student s2 GROUP BY s.cid)"의 결과를 임시 테이블에 저장해서 사용하고 처리가 끝나면 임시 테이블을 삭제합니다. 

Expression Rewriting 

DBMS는 쿼리 표현식에서 불필요한 부분을 제거하거나 최적화할 수 있습니다. 

SELECT * FROM A WHERE 1 = 0

위의 쿼리에서 1 = 0은 항상 불가능하기 때문에 데이터를 가져오지 않고도 결과를 반환할 수 있습니다. 

SELECT * FROM A WHERE 1 = 1

위의 쿼리는 항상 1 = 1 조건을 만족하기 때문에 해당 조건은 삭제하는 방향으로 최적화할 수 있습니다. 

 

마무리 

이번 포스팅에서는 쿼리 최적화 방법 중 rule based 최적화에 대해 살펴봤습니다. 다음 포스팅에서는 cost based 쿼리 최적화에 대해 살펴보겠습니다.