Query Processing

2023. 10. 28. 15:00ㆍCS/데이터베이스

 데이터베이스를 실행하면 DBMS 는 쿼리문을 Linear Algebra (관계대수) 형식으로 변경하여 처리하게 됩니다. 

관계 대수는 순차적인 (Procedural) 한 언어이고, SQL 은 Non-Procedural 하기 때문입니다. 

알고리즘 문제를 풀거나, 쿼리문을 작성 하는 경우, 같은 문제에 대하여 여러가지 해답이 나올 수 있다는 사실은 자명합니다. 

당장 백준에 들어가 누군가의 코드를 보더라도 누구는 O(N) 만에 해결하는 반면, 제 코드는 O(N^2) 만에 해결된 경우가 이에 해당 될 것 같습니다. 그럼 DBMS 는 어떨까요? 분명 컴퓨터니까 사람처럼 직관과 추론을 사용하지는 못할 것입니다. 

이번 챕터는 어떻게 쿼리 프로세스가 진행되는지에 대하여 알아보겠습니다. 

 

1. Basic Steps in Query Processing 

 

우리가 작성한 쿼리문들은 DBMS 안에서 해당 단계들을 거쳐서 결과물로 도출됩니다.

  1. 쿼리문 입력 (SQL)
  2. 관계 대수 표현식으로 변환 (parsing -> 문법 체크 and translation -> 관계대수로 번역)
  3. 최적화 ( 통계 데이터를 이용)
  4. 실행 계획 수립
  5. 평가 엔진을 이용해 데이터 처리
  6. 결과물 도출

여기서 가장 중요한 단계가 무슨 단계일까요 ? 최적화 단계입니다. 위에서 말했듯 같은 문제를 풀어도 효율적으로 풀 수도, 비효율적으로 풀 수도 있습니다. 컴퓨터는 비용을 저장되어 있는 통계적 데이터를 이용하여 분석하고, 수많은 해들 중 가장 최적의 비용(시간)을 가지는 실행 계획을 수립합니다. 

 

다양한 풀이

그 다음, 평가 계획이라 불리는 자세한 평가 전략을 도출합니다. 예를 들어 

다음과 같이 인덱스가 존재하는 경우에, 가능한 접근 방안은 

1. 전체 테이블 스캔후 값 탐색

2. 인덱스를 이용한 스캔 및 값 탐색 

정도가 있을 것이고, 이들 중 Optimize 한 방식을 채택합니다. 만약 인덱스를 사용한다면 

75000보다 작은 튜플들을 찾고, salary 만 Projection 하는 방식으로 진행됩니다.

 

이러한 정보들이 담겨있는 통계 데이터는 database catalog 이라는 이름으로 DBMS 내부에 존재합니다. 

 

2. Measures of Query Cost 

비용을 계산하는 방식에는 여러가지 방법들이 있을 수 있습니다. 

하지만 응답 시간은 실행 이전에는 알 수 없으므로 방식에서 제외하고, 간단하게 Disk Access 를 지배적인 비용 산출 기준으로 선정합니다. 디스크 접근은

  • Number of seeks (탐색 횟수)
  • Number of blocks read (읽기 횟수)
  • Number of blocks written (쓰기 횟수) 

로 분류됩니다. 책에서는 해당 요인들을 일반화 하기 위해 

Tt : 1 블록을 전송하는데 걸리는 시간 (transfer) 

Ts : 1 번 탐색하는데 걸리는 시간 (seek) 으로 선정하였습니다. 

 

(보통 write 작업은 값을 쓰고 값이 올바르게 작성 되었는지 검사까지 하기 때문에 read 작업보다 오래 걸린다고 합니다.

하지만 책에서는 Tt 로 통합하여 고려합니다.)

 

각 블록은 보통 4Kb 로 가정합니다.

또한 High-end magnetic disk 의 경우 Ts = 4msec, Tt = 0.1 msec 정도로, seek time 이 40배 이상 소요됩니다.

SSD는 Ts = 20-90 microsec, Tt = 2~10 microsec 이라고 합니다.

 

3. Selection Operation

Select 연산을 진행하는 경우는 두가지 방법이 있습니다. 

첫 번째는 파일 스캔을 이용하는 방법, 두 번째는 인덱스들을 이용하는 방법입니다. DBMS는 A1 ~ A6 까지의 알고리즘들을 통해 

Selection 연산의 비용을 게산합니다. 

 

 File scan 

데이터에 접근하는 연산 중 가장 낮은 레벨의 연산입니다. 

말 그대로, 파일에 접근해서 일일히 스캔하는 방식입니다. 

 

Algorithm A1 (Linear search) 

각 파일 블록들을 스캔하고, 각 레코드가 selection 조건에 맞는지 검사하는 방식입니다. 한번의 seek 후, 블록 개수만큼 transfer 합니다.

Cost = Br block transfers + 1 seek

(Br 테이블 r이 가지고 있는 레코드 블록들입니다. )

 

 

  • 만약 selection 연산이 key attribute 에 대하여 일어난다면, 평균적으로 (Br/2) block transfer + 1 seek 만에 탐색이 가능합니다.

block transfer 가 절반으로 줄었습니다! 어떤 방식을 이용해서 줄인 걸까요?

절반이니까 이진 탐색을 이용했다고 생각하기 쉽지만, 데이터베이스에서 이진 탐색은 그다지 효율적인 작업이 아닙니다. 

보통 데이터는 순차적으로 메모리에 저장되지 않기 때문에, 이진 탐색을 이용해 인덱스를 이리저리 움직인다면 데이터에

랜덤 액세스를 하는 꼴이 됩니다. 하지만 위에서 보았듯, seek time 은 transfer time 보다 절대적으로 느리기 때문에 효율적인 작업이 아닙니다. 

즉, key attribute 에 대해 일어나는 비용은 평균적인 결과값입니다. 정리하자면 

A1 Linear Search Ts + Br * Tt
A1 Linear Search, 키 동등성  (Br/2) * Tt + Ts 

가 됩니다. 

 

A2 (Primary index, equality on key) 

해당 알고리즘은 primary 인덱스가 존재하는 경우, key 요소의 동일성을 판별할 때 적용할 수 있는 방식입니다. 

Cost = (Hi + 1 ) * (Tt + Ts) 입니다. 어떻게 이런 식이 나온 것일까요 ? 

 

인덱스는 B+ tree로 이루어져 있습니다. B+ tree에서 leaf node에 접근하기 위해서는 B+tree 높이만큼 Tt + Ts 가 필요합니다. 

1. Root node 탐색 ( 1 seek + 1 transfer ) 

2. Internal Node 찾기 ( 1 seek + 1 transfer)

3. Leaf node 찾기( 1 seek + 1 transfer) 

또한, leaf node는 테이블을 가리키는 포인터를 가지고 있을 뿐입니다. 따라서 테이블에 직접 접근하기 위해서는 추가적인 

(1 seek + 1 transfer ) 가 필요합니다.  총 4 seek + 4 transfer 입니다.

 

위의 비용 식을 풀어보자면, Hi * (Tt + Ts) + 1 * (Tt + Ts) 가 됩니다. 즉, leaf node 까지 도달하는데 드는 비용 + 직접 접근에 드는 비용 으로 해당 식이 도출됩니다. 

 

A3 (Primary index, equality on nonkey) 

드문 경우입니다. primary index 인데, 키가 아닌 요소의 동일성을 판별하는 경우입니다. 이 경우, 

cost = Hi * (Tt + Ts) + Ts + Tt * b       (b 는 일치 레코드를 가지는 블록의 개수) 입니다.

위와 동일하게 인덱스 전체를 순회하기 위해 높이만큼 디스크 액세스를 하지만, 이번엔 Ts + Tt * b 가 다릅니다. 

이 뜻은, 1번 seek 후에, 매칭되는 블록의 개수만큼 transfer 를 작업한다는 뜻이 됩니다. 

seek은 1번만으로도 블록 최상단에 접근이 가능합니다. primary index는 테이블이 기본키를 기준으로 정렬되어 있기 때문에, 

블록의 개수만큼 transfer 를 하며 동일성을 판별하면 됩니다. 

 

primary index 를 이용한 selection은 정리하자면 이렇게 됩니다. 

A2 primary B+tree index, 키에 동일성  (Hi +1) * (Tt + Ts)
A3 primary B+tree index, 키가 아닌 것에 동일성 Hi * (Tt + Ts) + Ts + (B * Tt)

A4 ( secondary index, equality )

 다음은 primary index 가 아닌, secondary index 입니다. A4 알고리즘은 두 가지 상황으로 나눌 수 있습니다. 

1. search key 가 candidate key 인 경우

2. search key 가 candidate key 가 아닌 경우. 

 

첫 번째 상황부터 보겠습니다. secondary index 는 무조건 dense한(밀집된) 인덱스여야 합니다. 그렇다는 가정 하에, 비용은

1. Cost = (Hi + 1) * (Tt + Ts) 입니다. 아까와 동일한 비용을 소모합니다. 이는 생각해본다면 간단합니다. 

그저 키 값을 찾아오면 되기 때문에, 동일하게 인덱스 탐색 + 테이블 접근을 위한 탐색 으로 종료될 수 있습니다. 

하지만 2번의 경우 약간의 차이를 보입니다. 

 

2. Cost = (Hi+n) * (Tt + Ts)  ( n은 전체 레코드의 개수 ) 입니다. 이 역시 아까와 비슷하지만, 블록을 추가적으로 가져오냐, 레코드 전체를 가져오냐의 차이가 있습니다. secondary index는 기본적으로 dense 하지만, 인덱스와 연결되어 있는 테이블이 정렬되어 있다고 보장할 수 없습니다. 심지어 다른 메모리 블록에 위치할 수도 있기 때문에, 전체 레코드를 조회하여 일일히 비교해야 하는 상황이 발생합니다. 

전체 레코드를 탐색하는 작업은 굉장히 큰 비용을 유발합니다. 레코드가 10000개라면 결과값은 1개일 때 보다 만배가 더 들게 됩니다. 

 

secondary index 의 경우도 정리하자면,

A4 secondary index, 후보키에 동일성 ( Hi + 1 ) * (Tt + Ts)
A4 secondary index, 후보키가 아닌 것에 동일성 (Hi + n) * (Tt + Ts) (n은 일치하는 레코드 수)

 

가 되겠습니다. 

 

A5 (primary index, comparison) 

위에서는 그저 키와 키가 아닌 레코드의 동일성을 검사하는 방법에 대하여만 알아보았습니다. 하지만 selection 연산은 어떠한 값이 기준 값 보다 작거나 높은 경우도 알아낼 수 있어야 합니다. 값을 비교하는 방법은 σA<=V 혹은 σA>=V 등이 있겠죠!

여기서는 두가지 방식을 선택할 수 있습니다.

첫 번째는 선형적으로 파일을 스캔하는 방법이고,

두 번째는 인덱스를 이용해서 값을 찾을 수 있습니다. 

 

A5 알고리즘은 primary index를 이용하여 비교하는 방식을 보여줍니다.

1. Cost = Hi *(Tt + Ts) + Ts + b * Tt  어디서 많이 본 수식이지 않나요? 바로 위의 A3 알고리즘, Equality on non-key 경우의 비용과 동일합니다. primary index는 값들이 정렬되어 있기 때문에, 인덱스 탐색(Hi * (Tt + Ts)) + 블록 이동 (seek)  + 블록 탐색( B * Tt) 가 되겠습니다.  사실상 키가 아닌 요소에 대해 검색하는 것과 동일한 케이스입니다. 

 

하지만 , σA<=V (이하) 의 경우는 조금 다릅니다. 블록 이동 후 탐색을 진행하는데, 컴퓨터 입장에서는 어디까지가 V 보다 작은 값인지를 알지 못하기 때문에, 인덱스를 이용한 방식이 의미가 없습니다. 따라서 이 경우는 그냥 테이블을 스캔합니다.

그럼 이상의 경우는 비용이 왜 다른지에 대해 궁금할 수 있습니다. 이상인 경우는 V보다 높은 값인 곳을 스캔하여 그 이후로 블록들을 가져오기만 하면 됩니다. primary index는 정렬되어 있기에 가능한 연산입니다. 

 

A5 primary index, Comparison (A>=V) Hi * (Tt + Ts) + Ts + (B * Tt) 
A5 primary index, Comparison (A<=V) sequentially table scan

 

A6 (secondary index, comparison) 

다음은 secondary index를 이용한 비교 연산의 경우입니다. 이 경우도 위쪽과 동일합니다. secondary index는 모든 레코드를 탐색하며 이 레코드가 조건에 충족하는지에 대한 검사가 필요하기 때문에, 아래와 같이 변경되었습니다. 

A6 secondary index, Comparison (A>=V) (Hi + n)  * (Tt + Ts) (n은 레코드 수)
A6 secondary index, Comparison (A<=V) leaf node 까지 탐색 후 record 수만큼 탐색

 

A7 ( conjunctive selection using one index) 

다음은 Conjunction 한 연산에 관한 비용입니다. AND 연산이라고 생각하면 되겠습니다. 

예시로는 σsalary=40000 ∧ σdept_name='comp_sci'

몇 가지 방법이 있는데, 첫 번째는 하나의 인덱스를 사용하여 and 연산을 진행하는 방법입니다. 아이디어는 굉장히 단순합니다.

A2 부터 A6 까지의 방법을 사용하여 가장 비용이 적게 드는 연산을 우선 시행합니다. 그 후 나타난 결과값을 메모리에 올려, 

그 다음 조건에 대한 연산을 실행하는 방식입니다. 즉 DBMS계의 greedy 기법이라고 할 수 있겠습니다. 

이 방식은 and 연산이 교집합이기 때문에 가능한 방식의 연산입니다. 

 

A8 (conjunctive selection using composite index) 

복합 인덱스를 사용하여 탐색하는 방식입니다. 만약 salary 와 dept_name 으로 이루어진 복합 인덱스가 있다면, 이것을 활용하는 것이 가장 빠른 방식의 탐색이 될 것입니다. 

 

A9 (conjunctive selection by intersection of identifiers) 

A7 과 비슷한 방식입니다만, 이번에는 연산을 진행하고 교집합 시키는 것이 아니라, 각 테이블에 존재하는 B+ tree index 들을 이용해 leaf node 로 이동한 후, pointer 들을 교집합 하여 연산을 진행합니다. 그 후 남은 pointer 들에 대하여 직접 메모리에 fetching하여 결과값을 받아오는 방식입니다. 

 

A10 (disjunctive selection by union of identifiers) 

다음은 합집합에 대한 방식입니다. 합집합의 경우는 오직 모든 조건들이 인덱스를 가지고 있는 경우에만 적용이 가능합니다. 

그 외의 경우에는 선형 테이블 탐색이 더 효율적이라고 합니다. 

A9 방식과 비슷하게, 각 인덱스의 leaf node 에 달린 pointer 들을 합집합 후, 각각 메모리에 fetching 하여 결과값을 받아오는 방식입니다. 

 

Negation (부정) 

not 연산의 경우, 선형 파일 탐색을 진행합니다. 

 

4. Sorting  

다음은 테이블의 값을 정렬하는 경우에 대한 연산입니다. DBMS 에서는 기본적으로 두가지의 정렬을 지원합니다. 

또한 , 정렬이 잘 되어있을 경우, join 연산에 시간적인 이득을 볼 수 있어 중요한 알고리즘입니다. 

1. Ascending (오름차순)

2. Descending (내림차순)

 

보통 테이블을 생성하면, Primary key 에 대한 인덱스는 자동으로 생성됩니다. (primary index) 

즉, 우리가 임의로 생성하는 인덱스의 경우는 거의 대부분 secondary index인 경우라고 할 수 있습니다. 

그렇다면 secondary index의 특징은 뭘까요? 바로 각 테이블의 주소가 메모리에 선형적으로 위치하지 않을 수도 있다는 것.

따라서 Dense 한 인덱스여야 한다는 사실입니다. 

 

위와 같이, 인덱스 자체는 정렬되어 있는 것 처럼 보이나, 테이블과 테이블의 주소는 정렬되어 있지 않을 수 있습니다. 

 

그럼 물리적으로 각기 다른 위치에 있는 인덱스들을 어떻게 정렬할까요? 이 또한 두가지 경우에 따라 나뉠 수 있습니다 .

 

1. 메모리용량 안에 relation 이 포함될 수 있는 경우(fit) 

2. relation 이 메모리 용량을 초과하는 경우(don't fit)

 

첫 번째의 경우는 굉장히 이상적인 경우라고 할 수 있습니다. 그저 단순하게 메모리에 모두 올려서 연산을 실행하고, 내보내면 됩니다.

따라서 quick sort 와 같은 기법들을 사용하여 효율적인 처리가 가능합니다.

두 번째의 경우는 조금 복잡합니다. 메모리가 담을 수 있을 만큼 테이블을 분해하고 (run 이라고 부릅니다.) 분해한 내용물을 각 메모리에 올려 비교 후 내보내는 방식입니다. 방식이 merge sort 와 굉장히 비슷한 것 같습니다. 이름도 external sort-merge 입니다.

 

방식은 그리 복잡하지 않습니다. 메모리에 올라갈 수 있는 만큼의 크기들로 테이블을 분리합니다. 이것들을 run 이라고 부릅니다.

각각 쪼개진 run 들을 정렬합니다. 그 후 1번 run 과 2번 run을 비교 후 작거나 높은 값( 오름차/ 내림차) 내보내기 방식을 이용해 정렬을 진행합니다. 

부끄럽지만 설명에 도움이 될 것 같아 필기 내용 포함하여 올리겠습니다. 

 

우선 메모리에 3개의 요소만 올라갈 수 있다고 가정하겠습니다. 각 요소들을 세개씩 run 들로 분리합니다. 이때, 정렬을 진행합니다. 

그 후 서로의 요소들을 비교하며 합병을 진행하는 방식입니다. 

이렇게, 각 run들을 서로 메모리에 올리고 비교를 진행합니다. 마치 도마 위에 횟감을 올리고, 어떤 생선이 더 큰지를 판단하는 것과 비슷한 느낌입니다. 그 후 비교된 값을 내보내 output buffer 에 저장합니다. 만약 output buffer 가 다 찬다면, disk에 작성하는 방식이 되겠습니다. 

5. Join Operation

다음은 Join 연산입니다. join 에 사용되는 방법은 

  1. Nested loop join
  2. Block nested loop join
  3. Indexed nested loop join
  4. Merge join
  5. Hash join 

방식이 있습니다. 빠른 이해를 위해 드는 예시 테이블의 목록과 정보입니다. 

  student takes
레코드 개수 5000 10000
블록 개수 100 400

 

Nested Loop Join

첫 번째는 Nested Loop join 입니다. 

for each tuple Tr in r do begin
	for each tuple Ts in s do begin
	test pair (Tr, Ts) to see if they satisfy the join condition θ
	if they do, add Tr * Ts to the result.
	end
end

의사 코드만 봐서는 잘 이해가 안 갑니다. 

 

대략적으로 설명하자면, 이중 반복문을 돌며 모든 레코드에 대한 값들을 조회한다고 생각하면 되겠습니다. 

이중 반복문은 바깥 쪽과 안 쪽 반복문이 있습니다. nest loop join 도 바깥쪽을 Outer relation, 안쪽을 Inner relation 이라고 합니다.

여기서는 바깥쪽 relation 을 r, 안쪽 relation을 s 라고 가정하겠습니다. 

 

최악의 경우 각 relation 의 메모리 블록을 1개만 저장 할 수 있다고 할 때, 비용은 

Nr * Bs + Br block transfer + Nr + Br seek 이 됩니다. 

우선, block transfer 는 s의 관점과 r의 관점으로 나눌 수 있습니다. 

s는 내부에서 반복문을 수행하는 릴레이션으로, r의 각각의 레코드를 가져와서 나의 block 들과 검사를 진행합니다. 

근데 메모리는 블록단위로 이루어져 있습니다. 레코드를 조회하기 위해서는 반드시 block을 가져와서 탐색해야 합니다. 

때문에 r의 관점에서는 자신의 전체 block 들을 가져와서 탐색해야 합니다. 

 

seek 도 마찬가지로, s 입장에서는 r의 레코드 별로 seek을 일일히 진행해야 합니다. 게다가 레코드를 조회하기 위해서는 블록이 필요하므로 + r의 blcok 개수만큼 seek 이 필요합니다. 

추가적으로, s relation 에 값에도 접근이 필요하므로, s에도 seek 이 필요하지만, 1번 탐색 후 순차적으로 들여오면 되기 때문에, +1의 탐색 비용이 발생합니다. 

 

하지만 만약 메모리에 모두 들어온다면, 이런 번거로운 행위를 반복할 이유가 없습니다. 그냥 도마 위에 두 테이블을 올려놓고 비교하면 됩니다. 따라서 메모리가 테이블의 크기보다 충분히 커서 모두 포함된다면, Br + Bs transfer and 2 seek 으로 비용은 줄어듭니다.

 

loop join 은 외부 테이블이 어떤것인지에 따라 연산 횟수가 차이나게 됩니다. 

이렇게 어떤 relation 을 외부에 두었냐에 따라 seek 과 transfer 가 차이나게 됩니다. 

takes 를 외부 relation으로 두게 된다면, transfer time 에서는 유리하지만, seek time 이 두배 가량 증가합니다. 

위에서 보았듯, seek time이 보통 transfer time 보다 10배 가량 비싸기에, 어떤 것이 우세한지는 상황에 맞는 선택이 필요할 것 같습니다.

 

위에서 보면, 레코드에 일일히 접근해서 s와 비교하고 있습니다. 추가적으로 레코드에 접근하기 위해 block 도 가져오고 있고요. 무언가 불필요한 연산을 지속하고 있는 느낌입니다. 어차피 block 단위로 값들을 가져오는데, 그냥 block 단위로 비교하면 안될까요? 

 

Block Nested Loop Join 

for each block B r of r do begin
	for each block B s of s do begin
		for each tuple t r in B r do begin
			for each tuple t s in B s do begin
				Check if (t r , t s ) satisfy the join condition
				if they do, add t r • t s to the result.
			end
		end
	end
end

그 아이디어를 현실화 한 것이 바로 Block Nested Loop Join 입니다. 

보기엔 엄청 거부감이 드는 반복문의 연속이지만, 사실 내부를 본다면 블록 단위로 가져와서 tuple 끼리 비교하는 사실을 알 수 있습니다. 

 

따라서 최악의 경우에, 일일히 레코드 조회에서 block 단위 조회로 바뀌었기 때문에, 비용은

Br * Bs + Br block transfers + 2 * Br seek 입니다. 위에 계산 식에서 Nr 이 Br 로 바뀌었습니다.

 

최선의 경우에도 비슷합니다. 

Br + Bs block transfer + 2 seek 입니다. 

 

다음은 block nested loop join 에서 참고할 만한 성능 향상 목록 사례들입니다.

  1. 만약 join 요소들이 inner relation의 key 에 대하여 natural join 이거나 equi-join인 경우. 
    • 이 경우 테이블 전체를 탐색 할 필요 없이, 조건에 맞는 요소를 발견하면 바로 반복을 중지할 수 있습니다.
  2. outer relation 에 메모리에 들어갈 만큼 최대한 큰 블록 유닛을 두기
  3. inner loop을 앞뒤로 돌기 
    • 캐시된 데이터를 활용할 수도 있습니다. 

 

Indexed Nested Loop Join 

이 경우는 인덱스를 이용해서 join 을 실행하는 경우입니다. indexed neste loop join은 조건이 있는데

1. equi join 과 natural join 일 경우

2. 내부 relation 에 대하여 index가 존재하는 경우에 사용가능합니다.

 

nested Loop join 과 비슷하지만, s 튜플과 r의 튜플을 비교할 때, s에 존재하는 인덱스를 이용해 조회하는 경우입니다. 

비용 : Br(Tt+Ts) + Nr * c (c 는 r의 한 튜플에 맞는 짝을 찾을 때 인덱스를 탐색하는 비용) 

요약하자면 블록 개수만큼 가져와서, R의 tuple 개수만큼 인덱스를 탐색해 값을 가져오는 방식입니다.

c의 값은 딱 봐도 굉장히 비싸보입니다. 따라서 outer relation에 tuple 값이 작은 relation 을 두는 것이 효과적입니다. 

 

Block nested loop join 을 사용하면 400 * 100 + 100 = 40100 block transfer + 2 * 100 = 200 seek 이고,

Indexed Nest loop join 은 100 * 5000 * 5 = 25100 block tranfer + 25100 seek 입니다. 

seek 은 transfer 보다 매우 비싼 연산이고, 때문에 원하는 만큼의 성능 향상이 나타나지 않을 수도 있습니다. 

 

Merge Join 

다음은 merge join 입니다. 이름에서 알 수 있듯이, 합병하며 join 하는 방식입니다. 이 경우도

1. equi join과 natural join 에만 적용 가능

2. 정렬이 되어있어야 한다.

라는 조건이 필요합니다. 

 

 

이름에서도 추측이 가능하듯이, 위에서 언급한 external sort merge 와 방식이 유사합니다. 

분리후 merge 하며, join attribute 가 일치하는지 판별합니다. 

이 경우 비용은 Br + Bs block transfer + (Br/Bb) + (Bs/Bb) seek + (만약 정렬 안되어있다면 정렬 비용) 

입니다. Bb 는 각 릴레이션에 할당된 버퍼의 크기가 되겠습니다. 

 

Hash join 

해시 함수를 이용한 join 방법입니다. 이 방법 또한 Equi-join과 natural join 에 사용 가능합니다. 

기본 아이디어는 해시 함수를 이용해서 해싱을 진행합니다. 

그후 같은 해시 값을 가지는 튜플들 끼리 실제로 값이 같은지 비교하는 방식입니다. 

(hash 값이 같다고 해당 값이 반드시 똑같지는 않습니다. 하지만 hash 값이 다르다면 그 값들은 절대 같을 수 없습니다) 

6%3 = 0 , 9 % 3 = 0 으로 해시 값이 같아도 수는 다를 수 있지만, 5 % 3 = 2, 4% 3 = 1 해시 값이 다르면 절대 같을 수 없습니다.

이렇게 각각 해시된 값을 메모리로 가져와서, 검사할 때에 또 한번의 해싱을 이용합니다. (In-memory hash) 이때 이용하는 해시 함수는 첫 번째 partitioning 에서 사용한 해시 함수랑은 다른 함수가 됩니다. 

 

Complex Joins 

다음은 join 조건에 복잡한 조건들이 첨가된 경우입니다. 이 경우도 위와 같이 and 와 or 인 경우로 나눌 수 있습니다. 

 

AND의 경우 (ex. S natural join S.Id = T.Id ∧ S.dept_name = T.dept_name T) 

두 가지의 방식이 있습니다. 

1. block nested join (simple 한 경우) 

2. 처음 조건에 맞는 tuple 들을 구하고, 그 다음 조건에 맞는 tuple들을 찾기. 

 

위에서 언급한 selection 의 경우와 굉장히 유사합니다. 

 

OR의 경우 (ex. S natural join S.Id = T.Id ∨ S.dept_name = T.dept_name T) 

1. block nested loop join 

2. 각각 조건에 대해 join 후 합집합

두가지 방법이 존재합니다. 

 

6. Other Operations

다음은 그 외에 나머지 연산에 관한 내용입니다.

  • Duplicate elimination (중복 제거) 
    • sql 입장에서 중복 제거는 비용이 많이 드는 작업입니다. 따라서 distinct 를 명시하여 중복을 제거합니다.
    • hashing 이나 sorting 을 이용하여 제거합니다.
  • Projection 
    • 각 튜플에 대해 projection 을 사용합니다.
  • Aggregation (집계)
    • 중복 제거와 비슷하게 구현됩니다.
  • Set Operation (집합)
    • sorting 후 merge join, 혹은 여러가지의 hash join 을 사용 가능합니다. 
  • Outer Join 
    • join 알고리즘을 수정하여 이루어집니다. 

 

이렇게 Query Processing 과정에 대하여 알아보고, 비용 계산 방식을 살펴보았습니다. 

틀린 점이나 부족한 점이 있다면 언제든지 댓글 달아주시면 감사하겠습니다. 

'CS > 데이터베이스' 카테고리의 다른 글

Transaction  (1) 2024.01.16
Query Optimization  (1) 2023.12.21
Materialization 과 Pipelining  (0) 2023.10.30

관련글

티스토리툴바