[database] Physical Query Algorithm & Query Optimization

본 게시글은

서울대학교 데이터사이언스대학원 이상원 교수님의

데이터사이언스 응용을 위한 빅데이터 및 지식관리시스템 수업을

학습을 목적으로 재구성하였습니다

---

이번 시간에 배울 내용이다

 

우리는 이 수업 아주 초반에

모든 쿼리는 사실 관계대수라고 하는 연산자로부터 나왔다는 것을 배웠는데

사실 관계대수는 같아도

실제로 어떻게 구현되는지인 physical algorithm은 달라질 수 있다

 

따라서 현재 어떤 상황인지에 따라 best algorithm을 구현해야하는데

오늘 배울 내용은 이것에 관한 내용이다

 

 

수업의 초반부에 배웠던 내용이다

이런 논리적 연산자들을

물리적으로 어떻게 구현할 것인가에 대한 내용이다

 

 

이러한 내용을 쿼리를 어떻게 처리할 것인가를 다루는 내용이라

query processing 혹은 query evaluation이라고 부른다

 

physical algorithm을 구하는 과정은 세가지가 있는데

첫 번째는 index가 있다면 index를 활용하는 것

2번째는 full table scanning을 하는 것

그 다음 마지막은 divide and conquer, sorting, hashing으로

데이터를 쪼개는 방식이다

 

 

access path는 테이블로부터 원하는 튜플을 얻기위한 방법이다

full table scanning 혹은 index를 통해서

selection을 수행할 수 있다

 

DBMS는 cost model을 사용해서

index를 사용해서 selection을 할 때와

full table scan을 했을 때를 비교해서

어떤 것이 더 효율적인지를 계산해서 선택한다

 

 

 

selection을 어떻게 구체적으로 수행할 수 있는지

방법들에 대해서 간단하게 알아보자

 

간단하게 위 쿼리와 같이 selection 연산을 수행하는 쿼리가 있다

 

첫 번째로 인덱스도 없고 정렬도 안되어있다면

full table scan을 해야할 것이다

그 다음 인덱스가 없는데 정렬이 되어있다면

이진탐색을 한 뒤 scan을 해야할 것이다

세 번째는 B+ Tree index를 사용해서 index를 활용하는 경우와

마지막으로는 hash index를 활용하는 것인데

hash index의 경우 range query는 힘들고

point query는 구현이 간단하기 때문에

이 경우 hash index도 충분히 사용할 수 있다고한다

 

하지만 보통은 B+Tree를 가장 많이 사용한다고한다

 

 

 

selection에서 index를 활용할 경우

cost model을 이해해야한다고 한다

 

RID sorting이라는게 있는데 이건 별로 중요하지는 않다고..하시고

cost model을 통해서 index를 활용하는게 좋은지

아니면 그냥 full table scan을 하는게 좋은지 계산을 해야한다

왜냐하면 clustering이 안되어있는 경우

index를 사용하는게 오히려 좋지 않을 수도 있기 때문이다

 

 

그렇다면 general selection 예시를 한 번 살펴보자

위 예시에서 a, b, c 모두 다 index가 있다고하자

 

가장 무식하게 처리하는 방법은

full table scanning을 해서 찾는 방법이지만

일반적이지는 않다

그렇다면 위 쿼리는 어떻게 처리하는게 좋을까?

 

3개 다 index가 있다면

가장 디스크 IO가 적게드는 한 index만 사용하는 방법이 있다

이때 사용되는 개념이 most selective access path이다

 

그렇다면 예를 들어서 

day<8/9/94 AND bid = 5 AND sid = 3

이런 selection 조건이 있다고해보자

앞 day 조건은 범위 조건이기 때문에 B+Tree가 있는 것이 적절하다

하지만 뒤의 bid와 sid 조건은 point라서

hash index도 충분히 수행할 수 있다

 

 

그렇다면 이제 projection 연산을 살펴보자

 

projection에서 expensive한 부분은

중복제거를 하는 부분이다

DISTINCT가 나왔을 때 중복을 어떻게 제거하는지

크게 2가지 방법을 알아보자

 

첫번째는 정렬을 하면서 중복을 제거하는 방식이다

우리가 앞에서 배웠던 external sorting등의 방식으로 정렬한 다음

중복되는 것을 제거하면 된다

 

두번째는 hashing apporach이다

hash 함수를 통해서 데이터들을 파티셔닝을 한 다음

각 파티션을 메모리에 로드해서 중복을 제거하는 방식이다

 

 

그렇다면 이제 equality join을 하는 경우를 살펴보자

관계대수는 간단하지만 join같은 경우는

최적화가 정말 중요한 연산이다

join연산의 cost는 IO 횟수로 계산한다

 

 

join을 해결하는 첫 번째 방법이다

nested loops를 활용해서 

nested loops는 우리가 잘 알고있듯이 중첩 loop인데

쉽게 말해서 R에 대해서 S의 조건을 모두 비교하여

만족하는 튜플을 찾는 방식이다

 

이 nested loops join에는

tuple을 기반으로 찾는 방식과

page를 기반으로 찾는 방식이 있다

 

 

세번째로는 block nested loops join이 있는데

이 방식은 buffer memory를 활용해서

nested loops join의 성능을 늘린 방식이다

 

R의 여러 페이지를 buffer에 올려놓고

S의 페이지를 읽어서 스캔하며 비교하는 방식이다

 

이전의 두 방식에 비해서는 효율적이지만

여전히 S 전체를 다 읽어야하므로

S 전체가 클 경우 부담이 생길 수 있다

 

 

block nested loops의 예시를 한 번 살펴보자

 

cost는 outer table 스캔 비용 + (outer block 수 * 내부 테이블 전체 스캔 비용)

이다

 

outer table로 Reserves라는 table R이 있고

page의 개수는 1000개라고 하자

전체 R의 scanning 비용은 1000 I/Os가 되고

block은 총 10개가 있다

그다음 inner table은 Sailors table인 S는

페이지가 500개가 있으므로

R의 각 block 당 S를 스캔하는 비용은

10 * 500이 된다

만약 이 경우 buffer에 R의 page가 90개만 올릴 수 있도록 할당이 된다면

scan time은 12초가 된다고 한다

 

그런데 여기서 먄악 S를 outer table로 삼는다면

S의 block당 R을 scan하는 비용은 5 * 1000이 된다

 

따라서 DBMS는 순차 접근 시 IO 비용이 낮아지기 때문에

한 테이블에 버퍼를 모두 할당하는 것보다

R과 S에 균등하게 할당하는 것도 좋은 방법이 될 수 있다

 

 

다음으로 index nested loops join을 살펴보자

외부 테이블의 튜플에 대해서 내부 테이블이

join column에 index를 갖고있다면

그 인덱스를 활용해서 매칭 튜플을 빠르게 찾는 것이다

 

cost는 위 ppt slide에 나와있는 것과 같고

hash index로 접근하냐 B+Tree index로 접근하냐에따라

IO는 조금씩 차이가 난다

또한 당연히 클러스터링 여부도 크게 차이가 난다

 

 

이제 데이터베이스에서 nested loop을 할 때

partitioning을 하는 것과 하지 않는 것의 차이를 알아보자

 

왼쪽의 경우 partitioning을 하지 않고

R의 모든 튜플에 대해 S의 모든 튜플을

brute-force 방식으로 비교하는 구조이다

이는 당연히 비교횟수도 많고 성능도 떨어진다

 

하지만 오른쪽의 경우 partitioning을 한 구조이다

R과 S를 어떤 공통된 기준으로 나누어

동일 파티션끼리만 비교한다

이렇게 하면 비교해야할 튜플의 수가 훨씬 줄어들고

성능이 훨씬 향상된다

 

이렇게 파티셔닝을 할 수 있는 방법으로는

hash 혹은 sorting이 있다

 

 

nested loop join에서는 모든 데이터 블록은

buffer cache에 존재한다

outer relation에서 각 튜플을 가져오고

inner relation에서 튜플들을 일일이 비교하는 과정을 거칠 때

이 모든 작업은 buffer cache 안에서 수행된다

추가적인 메모리 공간이나 임시 테이블 스페이스를 사용하지 않는다

 

그러나 sort merge join을 하거나 hash join을 할 경우

메모리가 부족하면 디스크의 temporary tablespace이라는 영역에서

데이터를 관리한다

 

 

그렇다면 sort-merge가 무엇인지 구체적으로 알아보자

sort-merge join은 두 릴레이션을 join column을 기준으로 정렬한 뒤

merge하는 방식으로 매칭되는 튜플을 찾아

조인 결과를 생성하는 방식이다

 

우선 join column을 기준으로 두 relation을 sorting한다

그 다음 merge 단계로 넘어가는데

해당 단계에서 R의 tuple 값 >= 현재 S tuple 값이 되고

S tuple 값 >= 현재 R tuple 값이 될 때까지 이동한다

그러다가 두 값이 같아지면 멈춘다

 

그런 뒤, 같은 값을 가진 그룹끼리 join을 수행한다

현재 R의 그룹과 S의 그룹이 같으면

해당 그룹의 모든 튜플 쌍을 매칭하여 결과를 출력한다

 

이 과정을 R과 S가 끝날 때까지 반복한다

 

 

sort merge join의 수도코드이다

 

시간복잡도는 M log M + N log N + (M+N)이다

여기서 M+N은 merge page에서의 비용이다

 

 

이제 Hash join에 대해서 알아보자

 

hash join에서는 Hash 함수를 사용하는데

이는 보통 모듈러 함수를 많이 사용한다

따라서 이걸로 7개정도의 튜플들을 배분한다고 한다

N만큼 읽고 N만큼 쓰기때문에 2의 N제곱만큼의 disk IO가 발생한다

 

R과 S 모두 같은 hash function h를 사용해서

우선 Ri와 Si로 파티셔닝을 한 다음

Ri와 Si끼리만 매칭을 해준다

매칭을 해줄 때 Ri에 대해서

다시 새로운 해시함수 h2를 이용해서 파티셔닝을 해주는데

Si에서도 한 튜플씩 읽어서 h2로 같은 해시 버킷을 찾고

해당 버킷에서 실제로 키가 일치하는지 비교하는 방식으로 매칭한다

 

저 위 사진의 교수님이 만드신 인덱스이고

일반적으로는 sort-merge join에 비해서

hash join이 더 빠르지만

join column에 index가 있는 경우는

sort-merge join이 더 빠르다고 한다

 

따라서 메모리 여유 공간, 인덱스 유무 등을 보고

쿼리 옵티마이저가 어떤 방식의 조인을 활용할지 결정하는 것이다

 

 

지금까지는 그냥 equal join에 대해서만 알아보았다

하지만 만약에 equality만 검사하는 쿼리가 아니라면?

R.name < S.name과 같은 부등호가 포함된 쿼리라면?

 

equality query의 경우 우리가 지금까지 배운

nested loops join, sort-merge join, hash join 등

모든 Join 연산을 활용할 수 있다

 

하지만 inequality condition의 경우

index nested loop이 가능하고

B+Tree로 indexing이 되어있어야 유리하다

그러나 부등호 join에서는 일치하는 튜플 수가 폭발적으로 많을 수가 있어

성능이 저하될 수도 있다

이 경우에는 hash join과 sort-merge join은 사용될 수 없으며

block nested loops join이 나름 최선의 해결책으로 사용될 수 있다

 

 

또한 지금까지의 설명은

반드시 disk IO를 한다는 것을 기반으로 한다

 

여러 연산이 동시에 수행되면

실제로 buffer page가 어디에 얼마나 사용되는지

정확하게 예측하기가 어렵다

 

join 연산 수행시 특히 inner table에 반복적으로 접근하게되고

이 반복적 접근이 성능에 큰 영향을 준다

하지만 만약에 inner table이 너무 커서

buffer에 다 올리지 못하게 된다면?

buffer replacement policy가 굉장히 중요해지게 된다

ppt slide에 따르면 LRU는 최악이고 MRU가 최선이라고 한다

왜냐하면 R의 튜플이 계속해서 바뀌기 때문에

가장 최근에 사용한 페이지를 먼저 교체하는게 유리해진다

 

 

지금까지 배운 내용들에 대한 요약이다

쿼리는 논리 연산자로 구성되어있지만

이를 실제 알고리즘으로 구현하는 것은 이보다 훨씬 복잡한 일이다

따라서 같은 연산자일지라도

그걸 어떻게 구현하는지는 기술적으로 다양하다

 

따라서 쿼리 옵티마이저는 현재 상황 등을 보고

가장 사용하기에 적합한 알고리즘을 선택해서 사용한다

그리고 우리는 위에서 실제로 selection, projection, join에서

각각 어떤 알고리즘으로 연산을 구현하는지를 살펴봤다

 

 

이제 이어서 쿼리 옵티마이저에 대해서 알아보자

 

 

RDBMS 구조에서 query optimizer는

위 부분에 해당한다

 

 

query optimizer가 수행되는 전체적인 과정이다

 

user에 의해서 쿼리가 입력되면

query를 parsing 한 다음

어떤식으로 수행할 것인지 계획을 세운다

그런다음 옵티마이저는 각 플랜에 대해서

비용이 얼마나 드는지를 계산한다

따라서 비용을 계산했을 때 더 적게 드는 것을

선택해서 해당 방식으로 쿼리를 수행하게된다

 

 

동일한 쿼리에 대해서

관계 대수로 표현한 것과

실제 execution에 대해서 표현한 것이다

 

관계 대수에 비해서 실제 연산은

조금 더 복잡해진다

 

 

실제로 위 쿼리를

oracle에서 어떻게 수행하는지를 나타내는 슬라이드이다

 

 

따라서 쿼리 옵티마이저는 쿼리 수행에 대해서

어떤 플랜을 할 것인가를 결정하고

그 플랜에 대해서 cost를 계산하는데

쿼리가 복잡해지면 이 cost를 계산하는 것 자체만해도

시간이 굉장히 오래걸린다

plan estimation 자체가 비용이 비싸기 때문이다

 

따라서 query optimizer의 수행법에는 2가지가 있는데

첫번째는 cost-based optimizer라고해서

모든 plan에 대해서 비용을 산정해서 사용하는 방식이고

대부분의 DBMS가 채택하고 있는 방식이다

나머지 한 개는 rule-based optimizer라고해서

규칙을 기반으로 쿼리를 실행하는 방식이다

예를 들면 join column에 하나라도 index가 있으면

index를 활용하는 것과 같은 방식이다

 

 

쿼리 옵티마이저는 SystemR의 개발에 참여하신

오른쪽 위의 여성분이 큰 기여를 하셨다고한다

 

하지만 query optimization의 기반이 되고있는

cost-based optimization 기술은 40년이 넘었지만

여전히 5% 정도는 그렇게 좋은 결과를 내지 못하고 있다

이 분야의 특성상 완벽해지기가 힘들기 때문이다

 

 

query 수행에 대한 plan을 계산하는 것만해도

큰 비용이 든다는 것을 알려주는 slide이다

(수업 내용을 잘 못들어서 정확하게 뭔지는 기억이 잘..)

 

 

 

아무튼 옵티마이저는 정말 어마어마하게 많은 양에 대한

비용을 계산하는 경우도 있다

이때 사용하는 것들이 data dictionary인데

이 data dictionary에 table, column 별 tuple 개수 등

이러한 정보들이 모두 들어가 있다

따라서 정확하게 비용을 계산하기 보다는

통계치를 기반으로 휴리스틱하게 추정하는 기법을 많이 사용한다