20. 13장 : EXTERNAL SORTING (3) - hashing

정렬의 대안 중 하나로 설명한다.

=> 단순히 같은 값들이 연속된 공간에 모이도록 정리할 필요만 있으면,, sort보다 hashing이 더 나은 선택일 수 있다.

중복제거를 예로 들어보면, 단지 중복된 값들이 배치로 모이기만하면 된다. (굳이 순서대로 정렬될 필요가 없음)

Agrregation또한 그룹을 생성할 때 각 그룹의 요소들이 모이기만하면 된다.

=> 즉 이렇게 배치간의 순서는 중요하지 않을때 hashing이 사용된다.

hash table을 이용하는 방법은 RAM에 데이터를 다 올려야 한다.

Out-Of-Core 해싱을 위한 방법을 설명한다.

Divide And Qonquer

분할정복 방식을 이용한다.

Divide

스트리밍 알고리즘을 이용해 데이터를 spill partitoin으로 나눈다.

=> 해시함수 hp를 사용해 동일한 값은 같은 파티션에모아준다.

이 때, 동일한값이 연속으로 들어간다는 보장은 없음 주의!!

B개의 버퍼중 1개를 입력버퍼, B-1개를 출력버퍼로 사용한다.

B-1개의 버퍼가 곧, B-1개의 파티션이 된다.

_파티션 후 생기는 페이지 (즉 파티션의 개수)는 기존 파일의 페이지보다 많아질 수 있다. (B개수에 영향)

하나의 파티션이 하나의 페이지로 감당이 안되면, 더 많은 페이지가 필요할 수 있다

divide가 끝나면 partition disk에는 똑같은 값은, 똑같은 파티션에 들어가도록 바뀌게 된다.

하지만, 똑같은 값이 연속으로저장되어 있지는 않는다!!

이걸 해결하기 위해 hashing을 한번 더 한다.

Conquer

같은 값들은 특정 파티션 안에 모여있다는건 보장되었으므로,

특정 파티션에 또 다른 해시함수(hr)를 적용해준다.

-> hr를 이용한 해시테이블을 RAM안에 만들어준다!!

이 때 hr로 만드는 해시테이블의 각 버킷에는 고유값만 포함된다.

=> 각 버킷에는 하나의 교유값만 들어가므로, 버킷끼리 묶어서 하나의 파티션을 디스트에 다시 저장할때는 같은 레코드끼리 연속된다는 순서가 보장된다.

해시테이블은 B개의 버퍼를 가지는 메모리에 생성된다. 즉 지금 단계에서는 해시테이블의 크기가 B를 초과하지 않는다고 가정한다

Cost

첫번째 해시에서는, 전체 파일을 읽고, 해싱해서 저장한다 => 2N번의 I/O

이 때, 출력되는 파티션의 개수가, N페이지를 넘길 수 있지만 대략 N이라고 생각한다.

두번째 재해시에서는, 각 파티션을 메모리로 읽고, 해시테이블을 만들어서 다시 디스크에 기록한다 => 2N I/O

이때도, 정확히는 파티션 개수를 사용해야 하지만 위에서 대략 N이라고 했으니까 N을 유지한다

결론 : 4N I/O

memory 요구사항

이번에도 단 두번의 pass로만 해싱을 마무리 하려고 해보자!

첫번째 pass == 첫번째 해시에서 B-1개의 파티션이 생긴다.

두번째 pass == 두번째 해시에서는... 하나의 파티션을 가져와서 B 페이지 공간속에 해시테이블을 만든다.

즉 하나의 파티션이 최대 B페이지 이하면 된다!!

최대 B페이지의 크기를 가지는 파티션이 B-1개가 생기므로 최종 파일의 크기는 B(B-1)이 된다.

즉 대충 N = $B^2$ 이라고 생각하면, sort때랑 비슷하게 생각할 수 있다.

만약 하나의 파티션의 크기가 B페이지를 넘어가면 어떻게될까?

Recursive Partitioning

하나의 파티션의 크기가 B페이지를 넘어가면 재귀로 처리한다.

첫번째 hash를 끝냈을 때 (이 후 phase1이라고함) 파티션 하나의 크기가 B 페이지를 넘어가면

=> 두번째 hash를 한번으로 끝내는게 아니라 재귀적으로 여러번 반복한다!! (즉 파티션을 서브파티션으로 나누는것)

이런식으로, hp를 적용해서 파티션했는데 B보다 크기가 큰 파티션이 있으면 hp1, hp2, hp3....를 적용해서 파티션의 hr함수를 적용할 파티션의 크기가 B보다 작도록 재귀적으로 반복한다.

이 때 재귀적으로 사용하는 hpn는, 기존의 해시함수 hp와는 다른 해시함수를 사용해야한다

그렇지 않으면 파티션 내의 모든 튜플이 다시 똑같은 파티션으로 들어간다

중복데이터 처리

중복 데이터가 너무너무 많아서 하나의 파티션에 다 못들어갈 수 밖에 없는 상황이면 어떻게 해야할까?

예를들어, 내가 분류하려는 Key가 성별이라고 가정한다.

해봤자 겨우 여자, 남자, other 3가지 밖에 없기떄문에, 재귀를 아무리 반복해도 파티션 하나에 모든 튜플을 넣을 수 없을 수 있다.

(여자 인원이 아주아주 많아서 B페이지를 넘게 차지해야 하는 상황이 생길 수 있음)

이 상황에서,하나의 파티션이 B페이지를 넘겼다구 아무리 아무리 재귀를 반복해도,,,, 하나의 파티션만 계속 생긴다 (어짜피 같은값이니까)

고유값의 개수를 파악해서, 재귀를 중간에 끊어줘야한다!