[데이터베이스] 쿼리 최적화에 대해서 (Query Optimization)

데이터베이스 쿼리 최적화에 대해서

두 개의 relational algebra 표현식이 데이터베이스 인스턴스에서 항상 같은 튜플들을 반환한다면 그것은 동등(equivalent)하다고 한다. (순서는 상관 없음)

참고) 스키마 : 데이터베이스의 논리적 구조, 인스턴스 : 특정시간에 사진을 찍었을 때 그 테이블의 모습. 즉 튜플들의 전체적인 모습

Equivalence Rules

이 중에 대표적인 것들을 보자.

1. 네추럴 조인 (Natural Join)은 associative(동일)하다.

2. select연산의 동등성

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

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

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

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

다른 예를 보자.

처음 것을 보면 3개의 테이블 (course, teaches, instructor)에서 작업이 이루어진다. 그런데 3개의 테이블의 조인연산이 끝난 후 셀렉션이 이루어진다(dept_name="music")

두 번째는 instructor에서 미리 dept_name이 music인 것을 select한다. 결국 이렇게 하는 작업이 속도가 더 빠르다는 것이다.

"Performing the selection as early as possible reduces the size of the relation to be joined" 라는 말이 있다. select연산을 최대한 빨리한다면 조인횟수를 줄일 수가 있다는 말이다.

3. Projection 연산의 동등성

프로젝션또한 위의 것들과 마찬가지로 최대한 빨리 진행한다면 조인되는 횟수를 줄일 수 있다. 

4. 조인은 결과가 작은 쪽으로 조인하자. 

만약에 r1과 r2의 조인 결과가 r2와 r3의 조인 결과보다 작다면, 우리는 왼쪽식을 써야한다. 왜냐하면 temporary relation을 줄이는 쪽으로 가야 연산의 횟수가 적어진다.

이러한 Cost-Based Optimizer는 모든 evaluation plan을 검사하기 때문에 expensive하다. 대부분의 옵티마이저들은 휴리스틱을 써서 계산한다.

예를들어, 

세 가지 테이블이 있다면 조인 연산을 계산하는 가짓수는 12가지가 나온다. 만약에 7개면 665280 개라는 숫자가나온다. 너무 비효율적이라 여기서 Dynamic Programming을 이용하여 풀 수 있다. 

그런데 이마저도 비싸다. 그렇다면 아까 언급한 휴리스틱까지 추가하게 된다.

대부분의 옵티마이저는 left-deep join tree를 사용한다. 이유는 조인 알고리즘과 상호작용을 잘 한다고 한다.

Nested Subqueries에 대해서

Nested Query는 옵티마이져가 최적의 솔루션을 만든다는 보장이 없다. 그래서 nested query는 가능한 피하는 것이 상책이다. 

Query Planning을 하는 이유

한번 expensive query planning을 하게 되면 처음에는 시간이 오래걸리겠지만 시간이 지나면 점차 reuse되기 때문에 이득이다. 

Materialized Views (구체화 뷰)

구체화 뷰란 어떤 결과를 뽑아내는 쿼리가 자주 사용된다면 저장을 해놓고 다음번에 access할 필요가 없게 만드는 것이다. 즉 자주사용되는 View를 저장해서 속도를 향상시키는 기법이다.