데이터베이스 시스템 - Organization of Records in Files

시작하며

지난 글에서는 한 블록 안에 레코드의 바이트를 어떻게 배치할지 살펴봤습니다. 고정 길이 레코드, 가변 길이 레코드, 블록보다 큰 객체까지 모두 블록 내부에 관한 이야기였습니다.

이번 글에서는 시야를 한 단계 넓혀 봅니다. 한 릴레이션에는 수만, 수억 개의 레코드가 있고, 그것들이 수많은 블록에 흩어져 저장됩니다. 그렇다면 이 많은 레코드를 어떤 순서로, 어느 블록에 묶어 두면 좋을까요. 이 방법들을 파일 구성file organization이라고 부릅니다.

파일 구성의 종류

릴레이션을 파일에 매핑하는 방식은 크게 다음과 같이 나뉩니다.

• 힙 파일 구성heap file organization — 빈 공간이 있는 곳이면 어디든 레코드를 둡니다. 정렬 순서가 없습니다.
• 순차 파일 구성sequential file organization — 각 레코드의 search key 값에 따라 정렬된 순서로 저장합니다.
• 다중 테이블 군집 파일 구성multitable clustering file organization — 보통은 한 블록 안에 한 릴레이션의 레코드만 두지만, 이 방식에서는 함께 조회되는 여러 릴레이션의 레코드를 같은 블록에 묶어 둡니다.
• B+ 트리 파일 구성B+-tree file organization — 순차 파일 구성이 갱신이 잦은 환경에서 발생하는 오버헤드를 해결한 방식입니다.
• 해싱 파일 구성hashing file organization — 레코드의 어떤 속성에 해시 함수를 적용해 저장될 블록을 결정합니다.

이 글에서는 앞 세 가지(힙, 순차, 다중 테이블 클러스터링)에 더해, 큰 릴레이션을 다룰 때 자주 등장하는 파티셔닝partitioning까지 살펴봅니다. B+ 트리와 해싱은 인덱스 챕터로 미루겠습니다.

힙 파일 구성 (Heap File Organization)

힙 파일에서는 레코드가 파일 안의 어느 위치에든 들어갈 수 있습니다. 일단 자리를 잡은 레코드는 정렬이나 재배치 없이 그 자리에 그대로 머뭅니다.

새 레코드를 삽입할 때 가장 단순한 선택은 파일의 끝에 덧붙이는 것입니다. 다만 그동안 다른 레코드가 삭제되어 빈 자리가 생겼다면 그 자리를 재사용하는 편이 공간을 아낄 수 있습니다. 이 과정에서 빈 공간이 있는 블록을 빠르게 찾는 것이 중요합니다. 모든 블록을 한 번씩 훑어보며 빈 블록을 찾는다면 릴레이션을 구성하는 블록 개수만큼의 I/O가 발생하기 때문입니다.

여유 공간 맵 (Free-Space Map)

이 문제를 풀기 위해 대부분의 데이터베이스는 여유 공간 맵free-space map이라는 작은 자료구조를 둡니다. 여유 공간 맵은 보통 릴레이션의 각 블록마다 한 칸씩을 두는 배열입니다. 각 칸에는 그 블록의 여유 공간 비율 하한이 저장됩니다.

다음은 16개 블록을 갖는 파일에 대해 3비트로 점유율을 표현한 여유 공간 맵의 예시입니다. 저장된 값을 8(2^3)로 나누면 여유 공간 비율이 됩니다.

4 2 1 4 7 3 6 5 1 2 0 1 1 0 5 6

값이 7이라면 그 블록의 적어도 7/8 이상이 비어 있다는 뜻입니다. 새 레코드를 삽입할 블록을 고를 때는 이 맵을 훑어 충분한 여유 공간을 가진 블록을 찾으면 됩니다. 그런 블록이 없다면 그때 새 블록을 할당합니다. PostgreSQL는 파일 저장 구성으로 힙 파일 구성을 사용하며, 여유 공간 맵의 한 칸을 1바이트로 관리합니다. 따라서 저장된 값을 256으로 나누면 여유 공간 비율이 됩니다.

여유 공간 맵을 훑는 것은 실제 블록을 디스크에서 가져와 검사하는 것보다 훨씬 빠릅니다. 그러나 릴레이션이 매우 커지면 여유 공간 맵 자체도 커집니다. 이때는 2단계 여유 공간 맵second-level free-space map을 한 층 더 둡니다. 메인 여유 공간 맵의 여러개를 묶어 한 칸으로 만들고, 그 한 칸은 해당하는 배열의 최댓값을 저장합니다. 위의 예시에 4칸당 1칸의 2단계 맵을 만들면 다음과 같습니다.

4 7 2 6

2단계 맵을 먼저 훑으면 충분한 공간이 있는 그룹을 1/4의 시간으로 찾을 수 있고, 그 그룹의 4칸만 다시 보면 됩니다. 거기서는 반드시 빈 블록을 찾을 수 있는데, 2단계 맵은 요소들의 최대값이므로 적어도 하나는 그 값에 해당하는 공간이 남아있을 것이기 때문입니다. 릴레이션이 더 커지면 같은 방식으로 3단계, 4단계로 확장할 수 있습니다.

여유 공간 맵의 일관성

여유 공간 맵을 갱신할 때마다 디스크에 곧바로 쓰는 것은 비용이 매우 큽니다. 그래서 여유 공간 맵은 주기적으로만 디스크에 기록됩니다. 그 결과 디스크 위의 여유 공간 맵은 잠시동안은 현황을 반영하지 못하는 상태일 수 있고, 데이터베이스가 재시작되면 정확하지 않은 정보로 출발하기도 합니다.

이 부정확함으로부터 두 가지 문제가 발생할 수 있습니다. 맵이 "이 블록에 여유 공간이 있다"고 주장했는데 실제로는 없을 수도 있고, 반대로 "공간이 없다"고 했는데 실제로는 비어 있을 수도 있습니다. 전자는 블록을 가져온 시점에 바로 발견되며, 다른 블록을 다시 찾으면 그만입니다. 후자는 그 블록이 잠시 사용되지 않을 뿐 큰 문제를 일으키지는 않습니다. 이런 누적 오차는 가끔씩 릴레이션을 처음부터 끝까지 훑으며 여유 공간 맵을 다시 계산해 디스크에 써주는 것으로 해결합니다.

힙 파일 구성의 매력은 단순함에 있습니다. 어떤 정렬도 사용하지 않는 대신 삽입과 삭제가 빠르고 구현이 가볍습니다. 정렬된 접근이 필요하다면 그 위에 따로 인덱스를 얹어서 해결할 수 있습니다.

순차 파일 구성 (Sequential File Organization)

순차 파일sequential file은 검색키에 따라 정렬된 순서로 레코드를 처리하는 데 최적화된 구성 방식입니다. 어떤 속성 혹은 속성의 집합이 검색키가 될 수 있으며, 검색키는 주키일 필요도 수퍼키일 필요도 없습니다.

정렬된 순서로 레코드를 빠르게 읽을 수 있도록 각 레코드는 다음 검색키 순서의 레코드를 가리키는 포인터를 갖습니다. 또 블록 입출력 횟수를 최소화하기 위해 레코드 자체도 디스크 위에 검색키 순서대로, 혹은 가능한 한 그 순서에 가깝게 배치됩니다.

다음은 instructor 릴레이션을 ID 기준으로 정렬한 순차 파일의 예시입니다.

순차 파일 구성은 정렬된 순서로 레코드를 읽을 수 있게 해줍니다. 결과를 정렬해 보여줘야 하는 경우는 물론이고, 일부 질의 처리 알고리즘이 정렬 순서를 가정하기 때문에 이 구성은 그것만으로도 쓸모가 있습니다.

삽입과 삭제

문제는 갱신입니다. 삽입이나 삭제 한 번에 수많은 레코드를 옮겨야 한다면 물리적 정렬 순서를 유지하는데에는 많은 비용이 들 것입니다. 삭제는 앞서 살펴본 포인터 체인으로 처리할 수 있습니다. 삭제된 레코드를 건너뛰도록 이전 레코드의 포인터를 다음 레코드로 이어주면 됩니다. 삽입은 다음 두 단계로 처리합니다.

1. 새 레코드보다 검색키 순서상 바로 앞에 와야 할 레코드를 파일에서 찾습니다.

2. 그 레코드와 같은 블록 안에 여유 공간이 있다면 거기에 새 레코드를 넣습니다. 그렇지 않다면 새 레코드는 오버플로 블록에 넣고, 어느 쪽이든 포인터를 검색키 순서로 다시 이어줍니다.

이 방식은 삽입은 빠르게 끝낼 수 있지만, 시간이 지날수록 레코드의 물리적 순서와 논리적 순서(포인터 체인 순서)가 어긋나기 시작합니다. 순차 처리 자체는 여전히 가능하지만, 매번 다음 레코드가 어디 있는지 포인터를 따라가야 하므로 디스크 접근의 지역성이 점점 깨집니다.

재구성과 그 한계

오버플로 블록으로 빠진 레코드가 몇 개 없는 동안은 이 방식이 잘 동작합니다. 그러나 시간이 충분히 지나면 검색키 순서와 물리적 순서의 대응이 거의 사라지고, 순차 처리의 효율도 그만큼 나빠집니다. 이때는 파일을 처음부터 끝까지 다시 정렬하는 재구성reorganization이 필요합니다. 재구성은 비용이 큰 작업이라 보통 시스템 부하가 낮은 시간대에 수행됩니다. 얼마나 자주 재구성해야 하는지는 삽입의 빈도에 달려 있습니다. 삽입이 거의 일어나지 않는 극단적인 경우라면 파일은 항상 정렬된 채로 유지되며, 이때는 포인터 자체도 필요하지 않습니다.

이 한계 때문에 갱신이 잦은 환경에서 정렬된 접근을 효율적으로 유지하려면 보통 B+ 트리 파일 구성B+-tree file organization을 씁니다. B+ 트리는 비싼 재구성 없이도 많은 삽입·삭제·갱신 속에서 정렬된 접근을 유지해 주기 때문입니다. B+ 트리 구조에 대해서는 다음 글에서 자세히 알아보겠습니다.

다중 테이블 클러스터링 파일 구성 (Multitable Clustering File Organization)

대부분의 관계형 데이터베이스는 각 릴레이션을 별도의 파일(또는 파일들의 집합)에 저장합니다. 그래서 보통 한 블록에는 한 릴레이션의 레코드만 들어갑니다. 그러나 어떤 경우에는 의도적으로 여러 릴레이션의 레코드를 한 블록에 함께 두는 편이 유리할 수 있습니다.

다음 SQL 질의를 봅시다.

select dept_name, building, budget, ID, name, salary
from   department natural join instructor;

이 질의는 department의 각 튜플마다 같은 dept_name을 갖는 instructor 튜플을 찾아내야 합니다. 만약 dept_name에 해당하는 instructor가 N개의 블록에 나뉘어 저장되어 있다면, N개의 블록 읽기가 추가로 발생합니다.

다중 테이블 클러스터링 파일 구성은 이 문제를 서로 다른 릴레이션을 같은 블록에 배치함으로써 해결합니다.

이렇게 두 릴레이션을 dept_name을 기준으로 함께 묶었을 때 두 릴레이션이 dept_name 위에 클러스터링되었다clustered고 말하며, 이 구성 자체를 다중 테이블 클러스터링 파일 구성multitable clustering file organization이라 합니다. 묶음의 기준이 되는 속성은 클러스터 키cluster key라고 부릅니다. 그림에는 표시되지 않았지만 각 레코드는 자신이 어떤 릴레이션에 속하는지 식별할 수 있는 정보를 함께 가지고 있다고 가정합니다. 또 같은 클러스터 키를 공유하는 묶음 안에서는 dept_name 같은 클러스터 키 값을 한 번만 저장해 공간을 더 아낄 수도 있습니다.

이 구성의 장점은 분명합니다. department 튜플을 한 블록 읽어 들이면 그 블록에는 이미 해당 dept_name의 instructor 튜플이 함께 들어 있습니다. 한 부서의 instructor가 너무 많아 한 블록에 다 못 들어가도 인접한 블록에 이어서 저장되어 있으니 추가 비용이 크지 않습니다.

다른 질의에서의 손해

대신 다중 테이블 클러스터링은 다른 형태의 질의를 느리게 만들 수 있습니다. 가령 다음 질의는

select *
from   department;

각 블록에 department 레코드가 더 적게 들어 있는 만큼, 릴레이션을 따로 저장한 경우보다 더 많은 블록을 읽어야 합니다. 같은 릴레이션의 레코드끼리 포인터 체인으로 묶어 한 블록 안에서 빨리 찾도록 만들 수는 있지만, 어차피 읽어야 하는 블록의 수 자체는 줄어들지 않습니다.

그래서 다중 테이블 클러스터링은 자주 나타나는 질의의 패턴에 따라 신중하게 선택해야 합니다. 자주 함께 조인되는 두 릴레이션이라면 클러스터링이 큰 이득이지만, 한쪽 릴레이션을 단독으로 자주 스캔하는 워크로드라면 오히려 손해입니다.

다중 테이블 클러스터링은 Oracle 등의 데이터베이스에서 지원합니다. create cluster 명령으로 클러스터를 만든 뒤, create table의 확장 문법으로 어떤 릴레이션을 어느 클러스터에 두고 어떤 속성을 클러스터 키로 삼아 저장할지 지정할 수 있습니다.

파티셔닝 (Partitioning)

많은 데이터베이스는 한 릴레이션을 더 작은 릴레이션 여러 개로 나누어 따로 저장하는 테이블 파티셔닝table partitioning을 지원합니다. 보통 어떤 속성 값을 기준으로 나누는데, 회계 데이터베이스의 transaction 릴레이션을 연도 기준으로 transaction_2018, transaction_2019처럼 쪼개는 것이 흔한 예입니다.

질의는 여전히 transaction이라는 큰 릴레이션 위에서 작성되지만, 옵티마이저가 이를 연도별 작은 릴레이션 위의 질의로 다시 써줍니다. 다음과 같은 질의는

select *
from   transaction
where  year = 2019;

옵티마이저에 의해 transaction_2019만 읽도록 변형되며, 다른 연도의 레코드는 아예 건드리지 않습니다. 반면 selection 조건이 없는 질의는 모든 파티션을 함께 읽어야 합니다.

파티셔닝의 이점은 두 가지입니다. 첫 번째는 연산 비용의 절감입니다. 여유 공간 검색처럼 릴레이션의 크기에 비례하는 비용이 드는 작업은, 릴레이션을 작게 쪼개면 그만큼 가벼워집니다. 두 번째는 저장 매체의 분리입니다. 자주 접근되지 않는 과거 연도의 파티션은 자기 디스크처럼 느린 매체에 두고, 자주 접근되는 최신 연도의 파티션만 SSD에 두는 식의 전략이 가능합니다. 같은 릴레이션 안의 데이터라도 접근 빈도에 따라 다른 비용 곡선을 그릴 수 있다는 뜻입니다.

마무리

이번 글에서는 한 릴레이션의 수많은 레코드를 어떤 순서로, 어느 블록에 묶어 둘지를 살펴봤습니다. 정렬을 약속하지 않는 대신 단순한 힙 파일 구성, search key에 따른 정렬을 보장하는 순차 파일 구성, 자주 조인되는 릴레이션을 한 블록에 묶어 두는 다중 테이블 클러스터링, 그리고 큰 릴레이션을 작은 단위로 쪼개는 파티셔닝까지였습니다.

각 구성의 선택은 결국 워크로드가 어떤 모양이냐에 달려 있습니다. 정렬된 순회가 자주 필요한가, 특정 조인이 자주 일어나는가, 데이터의 일부만 자주 접근되는가. 이런 질문에 따라 같은 릴레이션이라도 전혀 다른 물리 구성 위에 놓입니다.

다음 글에서는 데이터 자체가 아니라 그 데이터에 대한 데이터, 즉 릴레이션의 스키마, 인덱스 정보, 사용자 정보처럼 시스템이 자기 자신을 알아보기 위해 보관하는 메타데이터인 데이터 사전data dictionary을 다뤄보겠습니다.