[DB] Chapter 13-3. Organization of Records in Files

지금까지 record가 어떻게 파일 구조로 표현되는지 공부했다. relation = set of records다.
그렇다면, 레코드의 모음에서 레코드들을 어떻게 구성할지에 대한 질문이 따라온다. 이에 대한 방법이 여러 가지가 있는데 각각에 대해서 하나씩 살펴볼 것이다.

- Heap file organization : 모든 record들이 공간이 있는 파일의 모든 곳에 저장될 수 있어서 record의 순서가 보장되지 않는다. 

- Sequential file organziation : 각 record가 "search key"를 통해 순서대로 저장된다. 

- Multitable clustering file organization : 몇몇 다른 relation들의 record를 같은 파일에 저장해서 join 연산을 하는데 있어 비용을 줄인다. 

- B+ tree file organization : 수많은 연산을 하다보면 ordered access의 효율성은 굉장히 낮아진다. 그래서 record를 구성하는 다른 방법으로 B+ tree 구성 방식이 고안되었다. 이는 B+ 인덱스 구조와 연관되어 있으며 많은 연산이 있더라도 효율적인 ordered access를 제공한다. 

- Hashing file organization : 해시 함수의 계산 결과값을 통해 record가 위치해야 하는 파일의 블록을 지정한다. 

1. Heap file organization

Heap file organization에서는 레코드가 relation에 대응되는 파일 어느 곳에서나 저장될 수 있다. 특정 위치에 저장되고 나면 record는 잘 이동하지 않는다.

레코드가 삽입되면 항상 파일의 맨 마지막에 위치해야 한다.
레코드가 삭제되면 삭제된 공간을 새로운 레코드가 저장되도록 사용하는 것이 타당하다. 때문에 데이터베이스 시스템이 순차 탐색이 아닌 효율적으로 빈 공간(block)을 찾는 것이 중요하다.

대부분의 데이터베이스는 효율적으로 공간을 사용하기 위해 free-space map이라는 자료구조를 사용한다.
free-space map은 relation의 각각의 블록에 대해 하나의 항목들로 이뤄진 배열로 표현된다.
각각의 항목은 f 비율을 표현한다. 최소한 하나의 공간의 f 비율만큼 비어있다.

ex) PostgreSQL

• entry의 크기 1 Byte
• entry에 저장된 값은 비어있는 비율(fraction)을 계산하기 위해 반드시 256으로 나뉘어져야 한다.
• 배열(array)은 파일에 저장되고 파일의 블록은 메모리에서 가져왔다.

record가 삽입/삭제/변경될 때 마다 free-space map의 항목값은 갱신된다.

ex) free-space map의 예시 : 아래 그림은 16개의 블록으로 파일이 구성되어 있다

여기서 3개의 비트는 저장 공간의 비율(occupancy fraction)을 위해서 사용했다고 하자.
i번째에 위치한 값은 i 블록에 대한 빈 공간 비율(free-space fraction)을 알기 위해서 8로 나뉘어야 한다.

예를 들어, 7이라는 값은 블록에 있는 space의 최소 7/8은 비어있다는 것을 의미한다.

주어진 사이즈에서 새로운 record를 저장할 block을 찾기 위해서
database는 free-space map을 스캔해서 해당 record를 저장할 수 있는 충분한 여유 공간을 가진 block을 찾을 수 있다.
만약 블록이 없다면, 새로운 블록이 relation에 할당된다.

위와 같은 scan은 용량이 큰 파일에서는 굉장히 느려질 수 있다.
충분한 여유 공간을 갖고 있는 블록의 위치를 찾는 작업의 속도를 높이기 위해서 2단계 free-space map을 만들 수 있다.
이 맵은 main free-space map의 각 100개 entry당 1개의 entry를 갖도록 구성된다.
2단계 free-space map의 하나의 entry에는 100개의 etnry들 중 최댓값을 저장한다.

ex) 아래 그림 : 위 예시의 2단계 free-space map. 1개의 entry가 main free-space map의 각각 4개의 entry를 표현하도록 함

이렇게 개수가 줄어든 2단계 free-space map을 스캔하는게 훨씬 시간이 단축된다.
즉, 충분한 여유 공간을 나타내는 적합한 entry가 2단계 free-space map에서 발견된다면
여유 공간을 찾기 위해서 이에 대응되는 main free-space map에 있는 100개의 entry들을 조사할 수 있다.
더 큰 relation을 다룬다면, 2단계 이상의 더 많은 단계를 만들어 내면 된다.

매번 entry가 갱신될 때 마다 free-space map을 disk에 작성하는 건 굉장히 비용이 많이 들어간다.
그래서, 정기적으로 free-space map을 disk에 작성하는데
그러다보니 디스크에 있는 free-space map의 정보가 옛날 정보가 될 수도 있고 데이터베이스를 시작할 때 DB는 사용가능한 여유 공간에 대한 옛날 정보를 얻을 수 있다.

이런 문제를 해결하기 위해서 relation을 정기적으로 scan해서 free-space map을 재검토해서 새로운 정보를 디스크에 저장해야 한다.

2. Sequential File Organization

Sequential file은 탐색 키를 기반으로 정렬된 레코드의 효율적인 처리를 위해 디자인되었다.
탐색 키의 순서에 따라 레코드들을 빠르게 검색하기 위해서 레코드들을 pointer로 묶어놔야 한다. 각 레코드에 있는 포인터들은 탐색 키의 순서에 따라 다음 레코드를 가리킨다.

게다가, block access의 횟수를 줄이기 위해서 물리적으로 레코드들을 탐색키 순서로 또는 그 순서와 유사하게 저장한다.

ex) instructor라는 이름의 sequential file / 각 레코드들은 탐색 키 순서로 저장되었다. (여기서 탐색 키는 ID값)

Sequential File Organization에서는 record들이 정렬된 순서로 읽혀지도록 했다.

하지만, 레코드를 삽입 또는 삭제할 때 마다 물리적으로 정렬된 순서를 유지하는 건 굉장히 어렵다. 왜냐하면, 삽입 / 삭제를 한 번 할 때 마다 많은 레코드들이 움직여야 하는 비용이 들기 때문이다. 이전에 pointer chain을 가지고 삭제 작업을 관리했었다.
삽입 작업은 아래의 2가지 규칙을 따른다.

1. 탐색 키 순서로 삽입된 레코드의 바로 앞에 있는 레코드를 파일에서 찾는다.
2. 만약 빈 레코드가 있다면 새로운 레코드를 삽입하고 그렇지 않으면 overflow block에 새로운 레코드를 삽입한다. 각각의 상황에 대해 탐색 키 순서로 레코드들을 연결하기 위해서 포인터를 조정해주면 된다.

아래 그림(13.8)은 위 그림(13.7)에서 record (32222, Verdi, Music, 48000)를 삽입하고 난 이후의 그림이다.
아래 그림과 같은 구조는 새로운 레코드를 빠르게 삽입할 수 있도록 하지만 레코드들이 물리적으로는 정렬되지 않은 상태가 되도록한다는 단점이 있다.

이런 구조를 갖게 되면 시간이 지나면서 탐색 키 순서와 실제 물리적인 저장 순서가 완전히 맞지 않게 되버릴 수 있다.

이 시점에서 파일을 반드시 재구성해줘야 한다. 그러면 물리적으로 sequential order로 정렬된다. 이러한 재정렬(reorganization)은 비용이 많이 들고 system load가 낮을 때 실행해줘야 한다.

재정렬이 필요한 빈도수는 결국 새로운 레코드를 얼마나 많이 삽입하냐에 따라 달라진다. 삽입이 많이 없다면 재졍렬을 많이 할 필요가 없게 된다.

B+ 트리 파일 구성(B+ tree file organization)은 삽입, 삭제, 갱신이 많이 있어도 정렬된 접근을 효율적으로 제공한다.
이에 대해서는 14.4.1에서 다룰 것이다.

3. Multitable Clustering File Organization

대부분의 관계형 데이터베이스 시스템은 각각의 relation을 분리된 파일 또는 파일의 집합으로 저장한다.
따라서, 각각의 파일, 블록은 하나의 relation에 record들을 저장한다.

하지만, 하나의 block 안에 있는 1개 이상의 relation에 record들을 저장하는 것이 유용할 수 있다.
이에 대한 장점을 확인하기 위해서 university라는 DB에 대해 아래와 같은 SQL 문을 작성했다.

SELECT dept name, building, budget, ID, name, salary FROM department NATURAL JOIN instructor;

위 쿼리는 department라는 relation과 instructor라는 relation을 join하는 연산을 수행한다.
따라서, department에 있는 각각의 tuple에 대해 똑같은 dept_name을 가진 instructor의 튜플들을 위치시켜야 한다.

ex)

• department relation

• instructor relation

아래 그림에서 department와 instructor의 natural join을 포함한 쿼리의 효율적인 수행을 위해 디자인된 파일 구조를 볼 수 있다.
instrutor relation의 각 튜플과 department relation의 각 튜플들이 dept_name을 기준으로 뭉쳐서 저장되어 있는 걸 확인할 수 있다.

그리고 아래 그림에는 안나왔지만 각각의 레코드들이 relation의 id값을 갖고 있다고 추정할 수 있다.
또한, storage의 overhead를 줄이기 위해서 dept_name 속성의 값을 저장하는 것도 가능하다.

이러한 구조는 join 연산을 할 때 효율적인 처리가 가능하도록 한다.

department relation의 튜플을 읽어올 때, 튜플을 포함한 전체 블록을 디스크에서 main memory로 복사한다.
instructor 튜플과 이에 상응하는 department 튜플들이 서로 근처에 저장되어 있기 때문에
department 튜플을 포함한 블록은 쿼리를 처리하기 위해 필요한 instructor relation의 튜플을 포함한다.
즉, 하나의 블록을 복사할 때 관련되어 있는 튜플들이 근처에 위치해있는 구조인 것이다.

Multitable Clustering File Organization은 13.11이 표현한 파일 구성방식이다. 이 방식은 각각의 블록에 서로 연관된 2개 이상의 relation 들의 record들을 저장하는 방식이다.

cluster key는 어떤 record들을 함께 저장할 지 정의한 속성이다. 위 예시에서는 dept_name이 되겠다.

이 방식은 특정 join 연산의 속도를 빠르게 높일 수 있지만 다른 형태의 쿼리문에 대한 속도는 느려질 수 있다.
ex) SELECT * FROM department;

앞선 방식처럼 하나의 relation에 있던 튜플들을 각각 분리해놓았다면 위 연산을 수행할 때 더 많은 block access가 필요하다. 왜냐하면, 하나의 블록 뿐만 아니라 여러 블록에 department 테이블의 튜플이 저장되어 있기 때문이다.

이렇듯 Multitable Clustering 방식을 사용할 때 사용하는 쿼리의 종류에 따라 효율성이 달라진다.
Multitable Clustering 방식은 Oracle DB System에서 지원하고 있다.

4. Partitioning

많은 DB들은 relation에 있는 record들이 각각 저장된 더 작은 relation으로 분할(partition)되도록 했다.
이러한 table partitioning은 기본적으로 속성 값에 의해서 실행된다.

ex) transaction relation에 있는 레코드들이 각각 년도 별로 나뉘었다고 하자.(ex. transacation_2018, transaction_2019)

쿼리문은 transaction relation을 가지고 작성이 되지만 연도 별 relation에 적용되는 쿼리로 변환된다.
Query optimizer는 쿼리가 요청받은 연도 정보를 가진 더 작은 relation으로 접근하도록 쿼리를 재작성할 수 있고
다른 년도에 해당하는 record들에 대한 읽기 작업을 피할 수 있다.

ex) SELECT * FROM transaction WHERE year=2019

이러면 오직 transaction_2019라는 relation에만 접근하고 다른 relation에는 접근하지 않는다.

record의 빈 공간을 찾는 것과 같은 몇몇 연산들의 비용은 relation의 크기에 따라 증가한다.
그래서 각 relatoin의 크기를 줄임으로써 partitioning의 overhead를 줄일 수 있다.

또한, partitioning은 relation의 각각 다른 부분을 다른 저장 장치에 저장하기 위해서도 사용된다.
ex. 2019년 시점으로 transaction_2018을 포함한 그 이전 transaction 데이터들을 빈번하게 접근하지 않는 HDD에 저장하고
transaction_2019 데이터는 좀 더 빠른 접근을 위해 SSD에 저장하는 방식을 채택할 수 있다.