[CS186] Introduction to Database Systems - Week 5

⛅ Sorting ⛅

I/O Review

• 페이지를 메모리에서 디스크로 쓰거나 디스크에서 메모리로 페이지를 읽을 때 I/O가 발생한다
• 알고리즘의 performance를 계산할 때 I/Os가 얼마나 발생하는지를 본다

Two Way External Merge Sort

• 한번에 모든 데이터를 메모리에 적재하지 못하기 때문에 먼저 정렬한 뒤에 머지해야 한다
• 1. conquer: 페이지 별로 정렬 알고리즘을 수행한다
• 2. sorted runs: merge sort 알고리즘을 사용해서 페이지들을 머지 한 결과이다
• 3. 하나의 sorted run이 될 때까지 계속 sorted runs를 머지한다

Analysis of Two Way Merge

• 데이터베이스의 알고리즘을 분석할 때 가장 중요한 것은 알고리즘이 얼마나 많은 I/Os를 발생하는가이다
• 데이터의 각 패스마다 2 * N개의 I/O가 필요하다 (N은 페이지 수) -> 각 패스에서 모든 페이지를 읽고 수정한 후에 모든 페이지를 다시 쓰기 때문에
• 이제 필요한 패스의 수를 계산해야 되는데 우선 초기 conquer 패스를 수행해야 하므로 최소한 하나의 패스는 필요하다
• 병합 패스는 각 패스마다 sorted runs를 반으로 줄이기 때문에 log2(N)이 된다
• 따라서 최종적인 공식은 2N * (1 + [log2(N]) I/Os가 된다
• 이 알고리즘을 실행하는데 필요한 버퍼 페이지의 수(버퍼 페이지 프레임)를 계산해보면 사용가능한 모든 메모리를 쓰진 않기 때문에 더 나은 알고리즘이 존재한다

Full External Sort

• Two Way External Merge Sort를 다음과 같이 최적화 할 수 있다
• 1. 초기 conquer pass에서 가능한 버퍼 페이지 수 만큼 적재해서 한번에 sorted run으로 정렬한다 -> 이렇게 하면 처음 pass 이후에 더 적고 긴 sorted runs을 만들 수 있다
• 2. 한번에 2개 이상의 sorted runs을 머지한다.  예를 들어 B개의 버퍼 페이지(프레임)을 사용할 수 있다면, 출력버퍼를 위한 버퍼 페이지 1을 제외하고 B-1개의 입력 버퍼를 사용할 수 있다. 즉, 한 번에 B-1개의 sorted runs를 머지할 수 있다
• 이렇게 하면 패스의 수(I/Os)를 절반으로 줄 일 수 있다

Analysis of Full External Merge Sort

• 2N ∗ (1 + ⌈logB−1 ⌈N/B⌉⌉) I/Os

 

 

⛅ Hashing ⛅

데이터베이스에서 동일한 값을 그룹핑 하는 것을 해싱이라고 한다

 

General Strategy

• 모든 데이터를 메모리에 한번에 저장할 수 없기 때문에 여러개의 다른 해시 테이블을 구축하고 서로 연결해야 한다
• 하지만 만약 다른 두개의 해시 테이블이 똑같은 값을 가지고 있는 경우 해시 테이블을 concatenate 할 때 문제가 된다
• 그래서 메모리 내의 데이터를 해시 테이블로 구축하기 전에, 특정 값이 메모리에 적어도 한 번이라도 나타나면, 해당 값의 모든 발생은 현재 메모리에 있어야 한다
• 이렇게 하면 값들은 하나의 해시 테이블에만 나타나고 안전하게 해시 테이블을 연결할 수 있다

The Algorithm

• 분할정복 알고리즘을 사용하는데 divide 단계에서 파티셔닝 패스를 수행하고, conquer 단계에서는 해시 테이블을 구성한다

Drawbacks of Hashing

• 해싱은 data skew에 민감하다
• data skew는 해시하는 값들이 균일한 분포를 따르지 않을 때 발생한다
• 해시된 파티션의 경우 같은 값들은 동일한 파티션에 위치하기 때문에, data skew는 크기가 불균형한 파티션을 발생 시킬 수 있다