Query Processing & Cost Measuring

Query Processing이란?

데이터베이스에서 데이터를 가져오거나 데이터를 삽입할 때 사용하는 언어를 Query라고 한다.

Query Processing이란 우리가 보낸 Query를 데이터베이스가 처리하는 과정을 말한다.

 

 

Basic Step

기본적으로 query를 처리하는 과정은 다음과 같다.

 

1. 입력받은 query를 parser와 translator가 relational-algebra 형태로 변환한다.

2. optimizer가 데이터의 통계 정보를 바탕으로 query 실행 계획을 세운다.

3. evaluation engine이 세워진 계획을 바탕으로 query를 실행하여 결과를 반환한다.

 

 

Query Cost Measuring

query optimization이란 query를 실행 가능한 계획 중 가장 cost가 낮은 계획을 선택하는 작업이다.

이를 위해서는 각각의 계획의 cost를 추정해야 하는데 이는 database catalog의 통계 정보를 이용하여 추정한다.

 

cost는 일반적으로 query를 보내고 응답을 받기까지 총 경과 시간을 측정한다.

이 때, cost는 disk access, CPU, 네트워크 통신 등의 다양한 요인들에 의해 달라질 수 있다.

이 요인들 중 cost에 가장 많은 영향을 주는 요인은 disk access time이다.

 

disk access time은 다음과 같이 상대적으로 쉽게 추정할 수 있다.

 

1. (read 할 block 수) × (평균 block 당 read cost)

2. (write 할 block 수) × (평균 block 당 write cost)

 

평균적으로 write cost가 read cost보다 크며,

write 후에는 성공적으로 write 되었는지 확인하기 위해 read를 1번 수행하므로 이를 합산해야 한다.

 

이 disk access time을 줄이기 위해 여분의 buffer 공간을 활용해 I/O 횟수를 줄이는 algorithm들이 있다.

사용할 수 있는 buffer 공간은 매번 다르지만, 주로 최소한의 buffer 공간을 사용하는 경우를 worst case로 사용한다.

 

그렇다면 다음과 같은 지표들을 통해 query를 실행할 때 사용할 algorithm들의 cost를 계산해보자.

 

M : memory size, memory에 들어갈 수 있는 tuple의 갯수

B : block size, block 하나에 들어갈 수 있는 tuple의 갯수

N : relation에 속한 tuple의 갯수

 

Selection

Algorithm 1. Linear Search

- block 내부를 모두 스캔하며, selection 조건을 만족할 때까지 모든 record를 살펴본다.

- 모든 tuple들을 block 단위로 읽어와 살펴보므로 I/O cost는 O(N/B)이다.

 

Algorithm 2. Primary B⁺ Tree Index (equality on key)

- relation의 key를 기준으로 생성한 index기 때문에 index entry 수와 tuple 수가 같다.

- B⁺ Tree 역시 tree기 때문에 leaf node까지 도달하는 시간은 logN이다.

- I/O 작업은 한번에 block 단위로 불러오기 때문에 I/O cost는 O(log_BN)이다.

 

Algorithm 3. Primary B⁺ Tree Index (equality on non-key)

- relation의 key가 아닌 속성을 기준으로 생성한 index기 때문에 같은 속성 값을 가진 tuple을 모두 봐야 한다.

- 따라서 T(key 값을 가진 record 수)값이 클 경우 T 만큼의 tuple들을 linear search로 탐색해야 한다.

- I/O cost는 T 값이 크지 않을 경우 O(log_BN), T가 클 경우 O(T/B)이다. 따라서 O(log_BN+T/B)이다.

 

Algorithm 4. Secondary Index (equality on non-key)

- secondary index는 기본적으로 index와 tuple의 정렬 순서가 다르기 때문에 block 단위로 I/O 수행이 불가능하다.

- index의 search-key가 candidate key일 경우 모든 tuple이 index에 존재하므로 I/O cost는 O(log_BN)이다.

- 하지만 search-key가 candidate key가 아닐 경우 각 tuple을 1개의 block으로 불러와야 되므로 O(T)의 cost가 발생한다.

- 따라서 search-key가 candidate key일 경우 + candidate key가 아닐 경우 = O(log_BN+T)로 매우 비효율적이다.

 

 

이와 같이 query를 수행할 때 사용되는 algorithm들의 I/O cost를 계산할 수 있다.