Project4

Project4 Design

Index

1. Project4의 요구사항
2. JOIN operation 구현
3. 그 외 변경사항
4. TODO

---

1. Project4의 요구사항

최대의 메모리 사용을 유지하며 (추가적인 메모리 할당/사용을 하지 않으며) JOIN operation을 구현

1. int join_table(int table_id_1, int table_id_2, char* pathname) 함수를 API service로 제공
2. 2개 table을 natural join
3. 주어진 pathname의 파일로 결과를 출력
4. 결과는 key에 따라 오름차순 정렬되어있을 것
5. 구현한 함수가 성공 반환 시 결과가 write 완료되어 있을 것

---

2. JOIN operation 구현

개요

• JOIN operation이 존재할 relational set operator layer를 추가하였으며, API layer의 join_table 함수(wrapper function)가 호출할 rso_join_table 함수를 relational set operator layer에 구현하였다. 하위 layer에서 구현된 API들의 wrapper function을 해당 layer에 추가하였으며, 해당 layer에서 buffer를 사용하기 위해 index manager에 buffer manager 함수 일부의 wrapper function을 추가하였다. 자세한 내용은 Layer 구조 변경 참고
• 해당 layer의 rso_join_table 함수가 사용하기 위한 find_leftmost_leaf 함수를 index manager에 추가 구현하였다.
• 해당 layer의 rso_join_table 함수가 사용하기 위한 advance 함수를 해당 layer에 구현하였다.
• JOIN operation을 구현하기 위해서는, Block Nested Loops Join, Index Nested Loops Join, Sort-Merge Join, Hash Join 등을 고려해볼 수 있다. 현재 DB는 B+Tree로 모든 record가 key에 따라 정렬된 상태이고, 출력할 결과가 key에 따라 오름차순 정렬되어야 하므로, 정렬된 입력 시 정렬 작업을 pass할 수 있고 정렬된 결과를 출력하는 Sort-Merge Join을 선택하였다.
• 이에 따라, 강의자료(lecture11 16slide)에서 제시된 pseudo code를 참고하였으나, 현재 DB는 key의 중복을 허용하지 않으므로 보다 단순하게 구현이 가능하다.

rso_join_table 함수

int rso_join_table(int table_id_1, int table_id_2, char* pathname);

• relational set operator layer에 구현
• 2개 table의 id를 입력받아서 natural join을 수행하고, 그 결과를 입력받은 pathname의 파일에 저장한 후, 성공 여부를 반환한다. (성공 : 0, 실패 : non-zero value)
• key의 중복을 가정한 기존 Sort-Merge Join과 달리, 중복 key block의 start point를 저장해가며 돌아갈 필요가 없고, 각 table에서 page를 1개씩 read해가며 수행이 가능하다.
• 구체적인 구현과 그 순서는 아래와 같다.
  1. 인자로 받은 pathname을 가지는 file을 (덮어)쓰기 전용으로 open한다. 실패 시 -1을 반환한다.
  2. 각 table의 header page를 request하고, find_leftmost_leaf 함수를 call하여 각 table의 leftmost leaf page를 찾는다. request 실패 시 -2를 반환, find_leftmost_leaf 실패 시(table이 비었을 시) -3을 반환한다.
  3. 각 table의 첫 record부터 key를 서로 비교하며 한 쪽이 작으면 작은 쪽을 advance, 같으면 출력 후 둘 다 advance하는 것을 둘 중 1개 이상 table에서 advance가 불가능할 때 마지막 record를 처리할 때까지 반복한다.
  4. 구현한 함수가 성공을 반환하기 이전에 파일 write가 완료되어야 하므로, fsync 함수를 call하여 실제 disk write이 수행되도록 한다.
  5. 요청하여 현재 사용 중이던 page를 모두 release하고 file을 닫는다.
  6. 0(성공)을 반환한다.

find_leftmost_leaf 함수

buffer_block_t* find_leftmost_leaf(buffer_block_t *header_buffer);

• index manager layer에 구현
• 특정 table의 header page (buffer block 포인터)를 입력받고 해당 table의 leftmost leaf page를 탐색하여 반환한다.
• 현재 record의 key는 자료형으로 int64_t를 사용하므로 index_find_leaf 함수에 해당 자료형의 최솟값을 key로 입력하여 동일한 기능을 수행할 수 있다. 하지만 key에 따른 탐색 작업 없이 수행하도록 추가적인 함수를 구현하였다.
• 구체적인 구현과 그 순서는 아래와 같다.
  1. 현재 table이 empty이면 NULL을 반환한다.
  2. root page에서 시작하여 leaf page에 이를 때까지 각 internal page에서 leftmost child page, 즉 one more page의 탐색을 반복한다.
  3. 해당 page의 buffer block 포인터를 반환한다.

advance 함수

int advance(int *idx, buffer_block_t **cur_buf, page_t **cur_page);

• relational set operator layer에 구현
• 특정 page에서 현재 확인한 record의 다음 record로 advance하고 성공 여부를 반환한다. 이를 위해 해당 page buffer와 그 안의 frame 포인터의 주소(caller에서 해당 포인터들을 저장한 포인터 변수들의 주소), 해당 page에서 현재 확인한 record의 index값의 주소(caller에서 해당 값을 저장한 변수의 주소)를 인자로 받는다.
• 구체적인 구현과 그 순서는 아래와 같다.
  1. 현재 확인한 record의 index가 해당 page의 key 갯수 - 1, 즉 해당 page의 마지막 record의 index보다 작으면 index 값을 1 증가시킨다.
  • 그렇지 않다면, 현재 buffer를 release하고 right sibling page buffer를 request한 후 index을 0으로 초기화한다. 즉 다음 page로 넘어간다. right sibling page number가 0, 즉 현재 page가 마지막 page일 경우 -1(advance 실패)을 반환한다.
  2. 0(성공)을 반환한다.

---

3. 그 외 변경사항

• JOIN operation 추가를 위한 layer 구조 변경과 몇 가지 최적화 시도 등이 존재한다.

• Index

  1. Layer 구조 변경
  2. buffer에서 shutdown_db 및 close_table 수정 (debugging)
  3. buffer에서 pin의 기능 수정
  4. buffer에 hash table 추가
  5. find 함수의 search 방식 변경 시도
  6. merge와 redistribution의 우선순위 변경 시도
  7. index_get_index 함수로 3개 함수 통합

1. Layer 구조 변경

• 과제에서 요구된 JOIN operation을 구현하기 위하여 API layer와 index manager layer 사이에 relational set operator layer를 추가하였다.
• 이에 따라, API layer의 각 함수가 index manager 소속 함수가 아닌 relational set operator 소속 함수의 wrapper function으로 수정되었다. 또한 join_table 함수가 추가되었다.
• API layer의 join_table 함수(wrapper function)가 호출할 rso_join_table 함수를 relational set operator layer에 구현하였으며, 하위 layer에서 구현된 API들의 wrapper function을 해당 layer에 추가하였다.
• relational set operator layer에서 buffer를 사용하기 위해 buffer_request_page와 buffer_release_page 함수의 wrapper function을 index manager layer에 추가하였다.

2. buffer에서 shutdown_db 및 close_table 수정 (debugging)

project3에서는 제출일까지 미처 발견하지 못한, 여러 table을 close할 때 비정상적으로 작동하는 문제가 있었다.
buffer_close_table 함수의 끝에서, 해당 table 구조체를 buf_tables 배열에서 제거할 때, 한 칸씩 당기기 위해

for(i = table_index;  i < table_num - 1; i++) {
    buf_tables[i] = buf_tables[i - 1];
}

위와 같이 구현하였는데, +로 적어야 할 부분을 -로 적은 오타가 있어서 정상적으로 수행되지 않았다.

for(i = table_index;  i < table_num - 1; i++) {
    buf_tables[i] = buf_tables[i + 1];
}

위와 같이 구현해야 했다.
또한, buffer_shutdown_db 함수에서

for(i = 0; i < table_num; i++) {
    result += buffer_close_table(buf_tables[i].table_id);
}

위와 같이 모든 table의 close를 수행하도록 구현했는데,
buffer_close_table은 buf_tables 배열을 앞으로 밀착시키며 수행되기에 buf_tables[i]가 아닌 buf_tables[0]을 연속적으로 제거해야 하고,
buffer_close_table은 table_num을 감소시키므로 이를 미리 복사해둔 후 해당 값으로 반복문을 수행하여,

repeat = table_num;
for(i = 0; i < repeat; i++) {
    result += buffer_close_table(buf_tables[0].table_id);
}

위와 같이 구현해야 했다.
해당 부분을 수정하였다.

3. buffer에서 pin의 기능 수정

• project 3에서는 buffer block의 pin이 evict 방지 외에도 lock 기능도 수행하는 것으로 오해하여, pin이 꽂힌 page를 중복으로 read/write할 수 없도록 구현하였다.
• lock에 관해 수업을 들으며 오해했음을 깨달았고, 현재 구현을 유지할 경우 중복 read가 불가능해서 동일한 table을 join할 수 없음을 확인했다. 따라서 lock 기능을 수행하도록 구현한 부분을 제거하였다.
  • request 시 pin이 꽂혀 있으면 실패를 반환하고, pin이 없으면 in_pinned 값을 1로 변경하던 것을, pinned 여부 확인 없이 해당 값을 1 증가시키도록 변경하였다.
  • release 시 is_pinned 값을 0으로 설정하던 것을 해당 값을 1 감소시키도록 변경하였다.

4. buffer에 hash table 추가

• project3에서는 buffer manager가 buffer block을 각 table별로 linked list로 연결하여 관리하고, buffer가 특정 table 특정 page의 request를 받으면 해당 linked list를 선형적으로 탐색하였다.
• 이런 구현은 buffer block의 수에 비례하게 매 request마다 탐색 시간을 증가시킨다. 실제로 10만 / 100만 개의 중복 없는 random insert / find / delete를 수행하였을 때 buffer pool의 크기(최대 buffer block 수)가 400 > 1000 > 4000개인 순서로 실행 속도가 빠름을, 즉 buffer pool이 클수록 속도가 느려지는 비정상적인 구조임을 알 수 있었다.
• 이를 개선하기 위해 buffer에 hash table을 추가하였다.
  • hash를 적용하지만 table별로 가지는 linked list는 유지한다. 이는 close_table에서 사용된다. (제거하기 위한 수단 고려 중)
  • collision을 해결하기 위해 separate chaining(open hashing)을 사용하였다.
  • hash bucket 구조체를 구현하고 이의 배열인 전역 변수로 hash table을 구성하였다. (init_db 함수에서 입력받은 buffer pool의 크기에 따라 동적할당해야 하므로 실제로 배열로 선언한 것은 아니고 구조체 포인터 전역 변수를 선언하였다.)
  • disk에서 읽은 페이지를 buffer에 올리는 create_buffer_block 함수에서 해당 buffer block을 hash table에 삽입하기 위해 insert_to_hash_table 함수를 선언/정의하였다.
  • buffer block을 evict하는 evict_buffer_block 함수에서 해당 buffer block을 hash table에서도 제거하기 위해 delete_from_hash_table 함수를 선언/정의하였다.
  • 상위 layer(index manager)의 요청에 따라 buffer 위의 특정 table의 특정 page를 반환하는 buffer_request_page 함수에서 해당 table id와 page number에 해당하는 buffer block을 hash table에서 빠르게 탐색하기 위해 find_from_hash_table 함수를 선언/정의하였다. (hash table을 추가한 목적)
• buffer_init_db 함수에서 buffer pool(buffer_block의 배열)을 동적할당한 이후, 같은 개수의 hash_bucket 배열을 동적할당하여 hash table을 생성한다.
• 동일하게 buffer_shutdown_db 함수에서 buffer pool을 free한 이후 hash_table을 free한다. separate chaining으로 추가 할당된 영역은, buffer_shutdown_db 함수 초반에 모든 table을 close할 때, 각 table에 속하는 모든 buffer block을 evict하면서 해제되기 때문에 고려하지 않아도 된다.
• 현재 구현에서 특정 buffer block을 탐색하기 위해서는 table id와 page number 총 2개가 사용되므로, 이를 1개의 key로 만들기 위해 차세현 학생이 제안한 Cantor pairing function을 사용하였다.
• 이는 2개의 입력 값에 따라 unique한 1개 값을 구해준다. int형의 table id와, uint64_t형의 page number로 해당 식을 계산하면, 현재 uint64_t형으로 둔 key에서 overflow가 발생하고 중복 key가 생길 수 있다. 그러나 중복된 key가 hash function을 거쳐 hash table의 중복 index에 삽입될 때 separate chaining으로 collision은 해결되며, 중복 index에서의 탐색은 해당 key가 아닌 table id와 page number를 가지고 수행하도록 하였으므로 문제가 되지 않는다.
• hash function을 따로 함수로 만들지는 않았으며 위의 3개 hash table 관련 함수에서 각각 cantor pairing function으로 구한 key를 hash size로 modular 연산을 하여 hash 값(해당 data가 hash table에 저장될 index)을 구한다.
• 현재 구현에서는 64bit 컴퓨터에서 1개 buffer block이 4145bytes, 1개 hash_bucket이 28byte의 크기를 가진다. 따라서 n개의 buffer block으로 이루어진 buffer pool이 있을 때 이의 크기는 4145n bytes가 된다.
• hash table은 매우 uniform하여 chaining이 없을 때 28n bytes, 한 위치에 모든 data가 chaining 된 worst case에 28(2n-1) bytes = (56n-28)bytes의 크기를 가진다. 이는 buffer pool의 약 0.68~1.35% 크기의 메모리 영역을 추가적으로 사용하게 되지만, 아래와 같이 탐색 속도를 비약적으로 향상시키므로 그만한 가치를 가진다고 판단하였다.
• 두 가지 방법의 탐색 속도 차이를 비교해보았다. intel i5-6600 CPU(4코어)를 가지는 데스크탑 PC에서 VM에 설치된 ubuntu 18.04.3에 CPU 2코어, 8GB RAM을 주고 수행하였다. host OS에서 다른 프로그램이 동작하는 등 완전히 통제되지 못한 환경이었으나, 수행 시간의 차이가 커서 충분히 우열을 가릴 수 있었다. 중복되지 않은 10만 개 record의 random order insert / find / delete를 test해보았다. 각 시간은 반복 test로 구한 시간들의 평균값. (find와 delete는 찾거나 삭제하는 10만 개 record가 모두 insert된 상태에서 수행. insert와 delete 함수는 성공 여부와 성공한 count를 log로 출력하고, find 함수는 성공 여부와 성공한 count, 찾은 key/value를 log로 출력해가며 test하였다.)
  

Linear	Insert	Find	Delete
buffer 1만	57.0s	56.9s	397.8s
buffer 1천	42.3s	6.8s	121.7s
buffer 1백	47.0s	3.7s	63.9s
buffer 1십	50.0s	3.4s	58.3s

Hash	Insert	Find	Delete
buffer 1만	6.9s	3.2s	3.9s
buffer 1천	24.1s	3.3s	47.1s
buffer 1백	40.8s	3.3s	53.8s
buffer 1십	47.3s	3.7s	56.5s

• Linear search는 buffer가 늘어날수록 느려지지만 hash를 사용했을 때는 buffer가 늘어날수록 빨라지는 정상적인 수행시간을 보이며, 전체적으로 hash의 수행시간이 빠름을, 특히 buffer가 클수록 월등히 빠름을 볼 수 있다.
• buffer의 수가 매우 적을 때는 linear 탐색이 별로 오래 걸리지 않는 것에 비해 hash table을 관리하는 데에 드는 resource가 있어서 (위 표에서 buffer 10개일 때 find 수행시간과 같이) hash 사용이 다소 느린 경우도 존재할 수 있으나 그 차이가 buffer가 클 때 linear search가 hash보다 느린 것에 비해서는 크지 않고, 수행에도 문제가 없다.
• 100만 개 record를 10만/1천 개 buffer에서 수행해본 결과 더욱 큰 차이를 확인할 수 있었다. 수행 시간이 오래 걸려서 여러 번 test하여 평균값을 내보기가 어려워 표를 첨부하지는 않았으나, data의 양과 buffer의 크기가 커질수록 hash 사용이 linear search보다 훨씬 우수한 성능을 보임을 알 수 있었다.

5. find 함수의 search 방식 변경 시도

• 기존 index manager의 index_find, index_find_leaf 함수는 주어진 key를 가지는 record를 탐색하기 위해 linear search를 사용하였다.
• 즉 각각의 internal page / leaf page에서 child page / record를 탐색할 때 제일 앞부터 끝까지 key 값을 비교해보며 탐색하였다.
• 이를 개선하기 위해 binary search의 적용을 시도하였다.
• 제일 마지막에 1번만 일어나며 최대 31개의 key를 가지는 leaf page에서의 탐색보다, 최대 248개의 key를 가지는 internal page에서의 탐색에 먼저 적용해보기 위해 index_find_leaf 함수를 수정하여 binary search를 적용해 보았다.
• 하지만 test 결과, 두 가지 search 방식을 사용했을 때 프로그램 수행 시간에서 유의미한 차이를 볼 수 없었다.
• 단순하게 생각했을 때 linear search는 O(n), binary search는 O(log n)의 시간복잡도를 가지지만, 현재 n이 최대 248개로 한정된 상태에서 이에 곱해지는 상수의 차이가 크다면 둘이 비슷한 수행 시간을 가질 수도 있고,
• 전체 수행 시간에서 find 함수의 비중이 작다면 프로그램 수행 시간의 비교로 그 차이를 찾기 어려울 수도 있다고 판단했다.
• 일단은 linear search를 유지. 추후 과제를 수행하면서 더욱 다양한 test를 해보고, find 함수나 해당 search 수행부분에 관해서만 수행 시간을 측정해보며, 보다 구체적으로 분석해볼 예정.

6. merge와 redistribution의 우선순위 변경 시도

• 기존 index manager에서는, merge를 최대한 줄이기 위해 redistribution을 우선적으로 수행하고 있다.
• redistribution은 옮긴 child page들의 parent page number를 수정해주기 위해 모두 request/release를 반복하므로 overhead가 커서 merge를 우선적으로 수행하는 것이 더 빠를 수도 있다고 판단하였다.
• 이에 따라, redistribution 우선만을 고려한 merge 함수를 일반적인 경우에도 사용할 수 있도록 수정한 후, merge를 우선적으로 수행하도록 시도하였다.
• 하지만 test 결과, 작은 비율이지만 평균적으로 merge를 우선적으로 수행한 쪽이 오히려 더 느림을 확인하였다. 또한, redistribution을 우선적으로 수행할 때에, 일반적인 경우를 고려한 merge 함수 사용보다 redistribution 우선만을 고려한 merge 함수 사용이 조금 더 빠름도 확인하였다.
• 일단은 기존의, redistribution 우선 수행과 그것만을 고려한 merge 함수를 사용. 추후 과제를 수행하면서 더욱 다양한 test를 포함하여 구제적으로 분석해볼 예정.

7. index_get_index 함수로 3개 함수 통합

• 기존 index manager에는, index_remove_entry_from_internal 함수에서 사용되는, 현재 page buffer 포인터와 parent page buffer 포인터를 입력받아 현재 page의 index를 반환하는 index_get_index 함수가 존재한다.
• index_insert_into_parent 함수에서 사용되던, parent page buffer 포인터와 left page의 page number를 입력받아 left page의 index를 반환하는 index_get_left_index 함수는 이와 실질적으로 동일한 기능을 수행하기에 삭제하고 index_get_index 함수로 통합하여 사용하도록 수정하였다. 이 과정에서, index_get_page 함수가 현재 page buffer 포인터가 아닌 현재 page number만 인자로 받고도 동작할 수 있음을 확인하고 그렇게 수정하였다.
• index_delete_entry 함수에서 사용되던, 현재 page buffer 포인터와 parent page buffer 포인터를 입력받아 현재 page의 left neighbor page의 index를 반환하는 index_get_neighbor_index 함수는 index_get_index 함수의 반환값에 1을 뺀 값과 동일한 반환값을 가지므로, 이 또한 삭제하고 index_get_index 함수로 통합하여 사용하도록 수정하였다.

---

4. TODO

1. page 삭제 시 right sibling page number 연결 방식 변경

• 현재 특정 leaf page 삭제 후 right sibling page number를 재연결해 줄 때, 삭제되는 page의 left page를 찾기 위해 table의 leftmost leaf page부터 탐색한다.
• 이는 leaf page가 증가(record가 증가)할수록 그에 비례해 탐색시간이 증가하는 문제점을 가지고 있다. 따라서 개선방안이 필요하다.

2. LRU list와 empty buffer 관리 방법 변경

• 현재 새로운 disk page를 buffer에 올리기 위해 empty buffer가 필요할 때, buffer pool을 선형적으로 탐색한다. 이는 buffer가 커질수록, empty page가 적을수록 탐색 시간이 증가하는 문제점을 가진다.
• LRU list에 empty page도 넣어서 evict될 쪽 (least recently use된 쪽)에 몰려있도록 하거나, 따로 list로 관리하는 등 개선방안이 필요하다.

3. 에러 체크

• 현재 각각의 함수에서 에러 발생 시 그에 대한 적절한 조치 없이 단순히 음수값을 반환하는 등 에러 체크가 미흡한 상태이다.
• 추후 recovery를 적용할 것을 고려하며 함수들의 각 위치에서 에러가 발생했을 때 해당 transaction의 수행을 취소하고 그 전 상태로 온전히 복구하는 등의 조치가 필요하다.