[CMU 15-445 Intro to DB Sys] Lec10 Sorting and Aggregation

• disk-oriented DBMS에서 buffer pool을 사용하고, i/o를 최소화(즉 sequential i/o를 최대화)하고자 함.

Sorting

• 직접적으로 ORDER BY에 사용하는 경우 이외에도, DISTINCT, GROUP BY, JOIN, bulk loading into B+tree index 등에 사용되기 때문에 sort가 필요함.

  In-Memory Sorting

• memory 내에 데이터가 들어온다면 quicksort 등 통상적인 정렬 알고리즘을 사용 가능함. 대부분의 DBMS에서는 퀵소트를 사용함.
• 만약 memory에 맞지 않는다면 read/write하는 비용을 고려해야 할 것임.

Top-N Heap Sort

• ORDER BY와 LIMIT를 사용한 쿼리에 대해서는 상위 N개만을 찾아내면 됨. 만약 상위 N개가 메모리에 들어온다면, heapsort를 통해 in-memory priority queue를 유지하면 된다.
  • 이미 N개가 sorted heap에 들어온 상황(ascending order 상황)에서, 제일 큰 원소보다 큰 원소는 heap에 포함시키지 않고 skip해도 된다.

External Merge Sort

• 메모리에 들어오지 않는 데이터를 정렬하기 위해 사용한다.
• run: list of key/value pairs
  • 여기서 key는 정렬에 사용되는 attribute, value는 tuple(early materialization한 경우) 또는 record ID(late materialization한 경우) 가능
  • record ID 방식이 space-efficient하기는 하지만, 나중에 random I/O를 야기할 수도 있다. 따라서 row store에서는 주로 tuple 방식을 사용하고, column store에서는 record ID를 사용한다.

Two-way Merge Sort

• 먼저, 각 페이지 내의 sort를 통해 1-page runs를 만든다. 그 다음에는 2개의 페이지를 가지고 정렬하여 2-page runs를 만들고, 이를 가지고 4-page runs를 만드는 식으로 합쳐 나간다.
  • 이 때 페이지를 read해 온 뒤에 sort하여 다시 write해 주어야 하기 때문에, 각 pass마다 페이지를 2번씩 I/O해야 하는 것이다.
  • 0번째 pass에서는 한 페이지를 불러온 뒤에 한 페이지를 쓰면 되지만, 이후 pass에서는 2개의 sorted page를 불러온 뒤에 이를 합쳐서 세번째 buffer page에 쓴 뒤에 disk write해 주어야 하기 때문에 3개의 page가 필요하다.
• 이렇게 하면 $1+\lceil \log_{2}{N}\rceil$번의 pass가 필요하고, total I/O cost는 $2N (\text{# of passes})$가 된다.
• 만약 메모리가 충분하다면 여기서 여러 pass를 한번에 한다든지(chop the tree!) 2개 이상의 merge를 하는 방식(widen the tree!)으로 pass의 횟수를 줄일 수 있다.

General Merge Sort

• 먼저, $B$개의 buffer page를 사용하여, $\lceil N/B \rceil$ sorted runs를 만든다. 그 다음에는 1개의 buffer page를 이용하여 나머지 $B-1$개에 담긴 run을 합쳐나가는 작업을 할 수 있다.
• 이렇게 하면 $1 + \lceil \log_{B-1} \lceil N/B \rceil \rceil$번의 pass가 필요하다.

Double Buffering Optimization

• buffer에서 merge 작업을 CPU가 하는 동안 I/O가 이루어지지 않는 점을 이용하여, buffer를 절반으로 나누어 다음 run을 disk로부터 prefetch해 올 수 있다.
• response time을 줄일 수 있다는 장점이 있으나 throughput에는 별 차이가 없다.

Comparison Optimizations

• key의 자료형에 따라 특화시켜서 comparator를 hard-code할 수 있다.
• string 비교에 있어서 binary prefix만을 먼저 비교한 뒤에 만약 prefix가 같으면 string comparison으로 fallback할 수 있다.

Using B+Trees

• 이미 B+Tree index가 있는 경우 이를 이용할 수도 있다.
  • 만약 clustered B+Tree라면 페이지의 순서가 이미 맞게 저장되어 있기 때문에, 제일 왼쪽의 페이지를 찾은 뒤 leaf node를 따라서 가면 sequential I/O가 가능하다.
  • unclustered B+Tree라면 data를 찾아가는 과정에서 random I/O가 필요해서 일반적으로 좋지 못하다.

Aggregations

• 한 개 이상의 tuple의 값을 하나의 scalar value로 만드는 경우다.

Sorting

• GROUP BY에 해당하는 tuple들을 먼저 정렬한 뒤에, 이에 대해 sequential scan을 통해 aggregation을 계산한다.

Hashing

• 정렬될 필요가 없는 경우라면 hashing을 쓰면 된다. 중복된 것을 제거하기만 하면 되기 때문이다.
  • (phase 1: partition) 먼저, hash function $h_1$을 이용하여 bucket들로 나누어 준다. 이때 $B$개의 buffer를 가지고 있다면 1개를 input, $B-1$개를 output에 사용한다.
  • (phase 2: rehash) hash function $h_2$를 이용하여 위에서 나눈 각 partition에 대해 in-memory hash table을 만들고, 이 새로운 해쉬 테이블의 bucket들을 보면서 tuple들을 골라낸다. 이렇게 중복된 것을 없앨 수 있다.'
  • rehash 과정에서 RunningValue를 저장하여 이후 aggregation 계산에 사용할 수 있다.