Data Storage Structures

상위 문서: 데이터베이스 시스템

개요

해당 문서에서는 기본 저장 장치인 하드 디스크나 SSD에 저장된 데이터의 구성 방식과, 데이터에 접근하는 방법에 초점을 맞춘다.

File Organization

데이터베이스는 OS에 의해 관리되는 디스크에 영구적으로 저장되는 여러 개의 파일에 매핑된다. 파일은 논리적으로(logically) 구성된 레코드들의 시퀸스로 구성되며, 이들 레코드들은 디스크 블록에 매핑된다. 각 파일은 논리적으로 블록(block)이라고 불리는 고정된 길이의 저장 단위로 구성된다. 이때 블록은 일반적으로 4~8 킬로바이트의 블록 크기를 사용하는 저장 공간 할당과 데이터 전송의 단위이다. 하나의 블록에는 여러 개의 레코드가 포함될 수 있으며, 어떤 레코드들이 블록에 포함되는지는 사용되는 물리적인(physical) 데이터의 조직(organization) 방식에 따라 결정된다. 이때 사용되는 기본적인 접근 방식은 다음과 같다:

• 레코드 크기가 고정되어 있다.
• 각 파일은 동일한 타입의 레코드만 가진다.
• 다른 릴레이션(relation)들은 서로 다른 파일에 저장된다.

Fixed-Length Records

예를 들어, 대학교 데이터베이스의 instructor 레코드들로 이루어지고, figure 1과 같이 레코드들을 저장한 파일을 고려하자. 이 파일의 각 레코드는 아래와 같이 정의된다.

파일:File containing instructor records.png

Figure 1. File containing instructor records

type instructor = record  
    ID varchar(5);  
    name varchar(20);  
    dept_name varchar(20);  
    salary numeric(8,2);  
end

각 문자가 1바이트를 차지하고, numeric(8, 2) 타입이 8바이트를 차지한다고 가정하자. 또한 속성인 ID, name, dept_name에 대해 가변적인 크기의 바이트를 할당하는 대신, 각 속성이 가질 수 있는 최대 바이트 수를 고정적으로 할당한다고 가정하자. 그러면 instructor 레코드는 총 53바이트의 크기를 가지게 된다. 이때 instructor 레코드를 파일에 저장하는 가장 간단한 방식은 파일의 첫 53바이트를 첫 레코트에, 그 다음 53바이트를 두 번째 레코드에 저장하는 것이다. 그러나 이 방식에는 두 가지 문제가 존재한다.

1. 블록 크기가 53의 배수가 아닐 경우, 일부 레코드가 블록 경계에 알맞게 정의되지 않는다. 즉, 레코드의 일부는 한 블록에, 나머지는 다른 블록에 저장된다.
   • 이 경우, 해당 레코드를 읽거나 쓰기 위해 두 번의 블록 접근이 필요하게 된다.
2. 레코드를 삭제하는 것이 어렵다.
   • 삭제된 레코드가 차지하던 공간은 파일의 다른 레코드로 채워야 하거나, 삭제된 레코드를 무시할 수 있도록 표시할 방법이 필요하다.

첫 번째 문제를 피하기 위해서, 사용되는 방식은 블록이 넘치지 않도록 레코드를 저장하는 것이다. 즉 블록의 크기를 레코드 크기로 나누고, 그 몫의 크기 만큼만 레코드를 계산한다. 각 블록에서 남는 바이트는 사용하지 않고 남겨둔다.

파일:File of Figure 1, with record 3 deleted and all records moved..png

Figure 2. File of Figure 1, with record 3 deleted and all records moved.

파일:File of Figure 1, with free list after deletion of records 1, 4, and 6.png

Figure 3. File of Figure 1, with free list after deletion of records 1, 4, and 6

또한 레코드를 삭제할 때 발생하는 문제를 해결하기 위해 생각할 수 있는 간단한 방식은 레코드가 삭제될 때, 삭제된 레코드 자리에 그 다음 레코드를 옮기고, 그 다음 레코드를 또 옮기고, 이런 식으로 모든 레코드를 앞으로 당기는 것이다. 이는 figure 2에 잘 나타나있다. 하지만 이런 접근은 매우 많은 레코드를 이동시켜야 하기 때문에 비효율적이다. 혹은 파일의 마지막 레코드를 삭제된 자리로 옮기는 것이 더 쉬울 수 있다. 그러나, 삭제된 레코드의 자리를 채우기 위해 레코드를 이동시키는 방식은 권장되지 않는다. 이는 이동 과정에서 추가적인 블록 접근이 필요하기 때문이다.
따라서, 파일에서 레코드를 삭제하고, 삭제된 자리를 표시하는 방식을 생각할 수 있다. 또한 일반적으로 삽입이 삭제보다 더 자주 발생하므로, 삭제된 레코드가 차지하던 공간은 비워 두었다가 이후 삽입 시 재사용하는 방식으로 활용하는 것을 가능케 한다는 점에서 좋아보인다. 하지만, 나중에 삽입 시 빈 레코드 공간을 찾는 것이 어렵기 때문에 역시 권장되지 않는다. 따라서 이 방식을 더 잘 활용하기 위해서, 추가적인 구조를 도입해야 한다.
이는 파일의 시작 부분에 일정 바이트를 파일 헤더로 할당하고, 삭제된 첫 번째 레코드의 주소 정보를 저장하는 것이다. 또한 첫 번째 삭제된 레코드 자리에는 두 번째 삭제된 레코드의 주소를 저장하고, 이런 식으로 연결된 구조를 형성한다. 이렇게 삭제된 레코드들은 연결 리스트(linked list)를 형성하며, 이를 보통 프리 리스트(free list)라고 한다. figure 3는 figure 1의 파일에서 레코드 1, 4, 6이 삭제된 후의 프리 리스트를 보여준다. 새로운 레코드를 삽입할 때는, 헤더가 가리키는 삭제된 레코드 위치를 사용한다. 그리고 헤터 포인터는 다음으로 사용가능한 레코드 자리를 가리키도록 변경된다. 만약 사용 가능한 공간이 없다면 새 레코드를 파일의 끝에 추가한다. 고정 길이(fixed-length) 레코드를 사용하는 파일에서는 삽입과 삭제가 단순하게 구현될 수 있다. 이는 삭제된 레코드가 차지하던 공간의 크기가 정확히 새로운 레코드가 필요한 공간의 크기와 일치하기 때문이다. 하지만 가변 길이(variable-length) 레코드를 사용하는 경우, 이러한 일치가 더 이상 성립하지 않는다.

Variable-Length Records

데이터베이스 시스템에서는 여러 이유로 인해 가변 길이 레코드(variable-length records)가 발생한다. 가장 일반적인 이유는 문자열과 같은 가변 길이 필드의 존재 때문이다. 그 밖의 이유로는 배열이나 다중 집합(multisets)과 같은 iterative 필드를 포함하는 레코드 타입이나, 하나의 파일 안에 여러 종류의 레코드 타입이 존재하는 경우가 있다.

가변 길이 레코드를 구현하기 위한 여러 기법이 존재하며, 이러한 기법은 아래의 두가지 문제를 해결해야 한다:

1. 개별 속성(attribute)이 가변 길이라 하더라도, 주어진 레코드 내에서 가변 길이 속성을 쉽게 추출할 수 있도록 표현해야 한다.
2. 블록 내에서 레코드를 쉽게 추출할 수 있도록 저장해야 한다.

파일:Representation of a variable-length record of the instructor relation.png

Figure 4. Representation of a variable-length record of the instructor relation

이를 구현하기 위해서, 가변 길이 속성을 가진 레코드를 표현할 때는 일반적으로 두 부분으로 구성된다:

1. 고정된 길이를 가지는 초기 부분: 고정 길이 필드와, 가변 길이 필드에 대한 (offset, length)쌍들
2. 가변 길이를 가지는 속성들의 실제 값

예를 들어, 정수나 날짜, 고정 길이 문자열과 같은 고정 길이 속성은 해당 값을 저장하는 데 필요한 바이트 수 만큼을 할당한다. 반면, varchar 타입과 같은 가변 길이 속성은 (offset, length) 쌍으로 표현된다. 이때 offset은 해당 속성의 실제 값이 레코드 내에서 어디서 시작되는지를 나타내고, length는 그 속성의 바이트 수를 의미한다. 이렇게 초기 부분이 고정된 길이로 작성된 채로, 가변 길이 속성들의 실제 값은 레코드의 초기 고정 부분 다음에 연속적으로 저장된다. Figure 4는 이러한 표현 방식의 예시를 보여준다. 해당 그림은 instructor 레코드를 보여주며, 이 레코드는 처음 세 개의 속성 ID, name, dept_name이 가변 길이 문자열이고, 네 번째 속성 salary는 고정 크기의 숫자이다. 이때 offset과 length는 각각 2바이트로 저장된다고 가정하면, 각 가변 길이 속성 당 4바이트가 필요하다. 또한 salary는 8바이트로 저장되며, 문자열은 각 문자의 개수만큼 바이트를 사용한다고 가정한다. 이 경우, 레코드의 초기 부분은 20바이트의 고정된 길이로 저장된다. 해당 figure는 또한 null bitmap의 사용도 보여준다. 이 비트맵은 레코드의 어떤 속성이 null 값인지를 나타낸다. 예를 들어, salary 속성이 null이라면, null 비트맵의 네 번째 비트가 1로 설정되고, 12~19 바이트에 저장된 salary 값은 무시된다. 이 레코드는 4개의 속성을 가지므로, null 비트맵은 1바이트면 충분하다.

파일:Slotted-page structure.png

Figure 5. Slotted-page structure

다음으로, 가변 길이 레코드를 블록 내에 저장하는 방식은 슬롯 페이지 구조(slossted-page structure)이며, 이는 figure 5에 잘 나타나 있다. 각 블록의 시작 부분에는 헤더(header)가 있으며, 다음 정보를 담고 있다:

• 블록 내에 존재하는 레코드 항목 수
• 블록 내 남은 여유 공간의 끝을 가리키는 포인터
• 각 레코드의 위치와 크기 정보를 담은 배열

실제 레코드들은 블록의 끝 부분부터 연속적으로 할당되므로, 헤더 배열의 마지막 항목과 첫 번째 레코드 사이가 여유 공간 영역이다. 레코드를 삽입하면, 여유 공간 끝에서 공간을 할당하고, 헤더에 해당 레코드의 크기와 위치를 추가한다. 레코드를 삭제하면 해당 공간은 비워지고, 헤더에서 해당 항목은 삭제된 것으로 처리된다. 그리고 삭제된 레코드 앞의 레코드들을 앞으로 이동시켜 여유 공간이 한 곳에 연속적으로 유지되도록 한다. 그리고 이에 따라 헤더의 항목들과, 여유 공간을 가리키는 포인터를 갱신한다.

슬롯 페이지 구조에서는, 레코드를 가리키는 포인터가 직접 레코드를 가리키지 않고 헤더 배열의 항목(슬롯)을 가리킨다. 이런 간접화(indirection)를 통해, 블록 내에서 레코드를 이동시켜도 해당 포인터를 통해 접근이 가능하게 한다.

Storing Large Objects

데이터베이스는 종종 디스크 블록보다 훨씬 더 큰 데이터를 저장해야 할 수 있다. 예를 들어 이미지나 오비오, 비디오 객체들이 이에 해당한다. SQL은 이와 같은 대형 데이터를 위해 blob (binary large object), clob (character large object)와 같은 대형 객체 타입을 지원한다. 많은 데이터베이스는 내부적으로 하나의 레코드 크기가 블록 크기를 초과하지 않도록 제한한다. 이러한 시스템에서는, 레코드가 논리적으로 대형 객체를 포함할 수는 있지만 대형 객체의 실제 값은 별도로 저장되고, 레코드 안에는 해당 객체를 가리키는 포인터만 저장된다. 이때 대형 객체는 다음 방식 중 하나로 저장될 수 있다:

• 데이터베이스에 의해 관리되는 외부의 파일 시스템 영역에 저장
• 데이터베이스 내부에서 파일처럼 관리하도록 저장
• 데이터를 여러 조각으로 나눠서 별도의 릴레이션에 분산 저장(PostgreSQL TOAST)

Organization of Records in Files

하나의 릴레이션(relation)은 레코드들의 집합이며, 레코드 집합이 주어졌을 때 해결해야 할 문제 중 하나는 이 레코드들을 파일 내에서 어떻게 조직할 것인가이다. 이때 파일 내에서 레코드를 조직할 수 있는 여러 방식들이 아래와 같이 존재한다.

• Heap file organization: 어떤 레코드든, 공간만 있다면 파일 내 어디에나 저장될 수 있으며, 레코드를 정렬하는 순서가 존재하지 않는다.
• Sequential file organization: 레코드는 각 레코드의 “검색 키(search key)” 값에 따라 순차적인 순서로 저장된다.
• Multitable clustering file organization: 서로 다른 여러 릴레이션의 레코드를 하나의 파일 혹은 파일 내의 동일한 블록 내에 저장하여 어떤 조인 연산의 비용을 줄인다.
• B+-tree file organization: B+-트리 인덱스 구조를 통해서 삽입, 삭제, 갱신 작업이 많더라도 레코드에 대한 효율적인 정렬 접근을 제공한다.
• Hashing file organization: 각 레코드의 어떤 속성에 대해 해시 함수를 계산하고, 이를 통해 해당 레코드를 파일의 어떤 블록에 저장할 것인지를 지정한다.

Heap File Organization

힙 파일 조직에서는, 하나의 레코드가 해당 릴레이션에 해당하는 파일 내 아무 위치에나 저장될 수 있으며, 레코드가 일단 특정 위치에 저장되면, 그 레코드는 보통 이동되지 않는다. 파일에 레코드를 삽입할 때, 한 가지 방법은 항상 파일 끝에 추가하는 것이다. 그리고 레코드가 삭제되면, 해당 공간을 새 레코드 저장에 재사용하는 것이 합리적이다. 하지만 이를 위해서는 데이터베이스 시스템은 파일의 모든 블록을 순차적으로 탐색하지 않고도, 여유 공간이 있는 블록을 효율적으로 찾을 수 있어야 한다.

파일:Free-space-map for a file having 16 blocks.png

Figure 6. Free-space-map for a file having 16 blocks

대부분의 데이터베이스는 free-space map이라는 공간 효율적인 자료 구조를 사용하여 어떤 블록에 레코드를 저장할 수 있는 여유 공간이 있는지 추적한다. 이 free-space map은 보통 각 블록마다 하나의 항목(entry)을 갖는 배열로 표현된다. 배열의 항목은 해당 블록의 공간 중 적어도 f 비율이 비어 있다는 것을 나타낸다. 레코드가 삽입, 삭제되거나 크기가 변경될 때, 해당 블록의 점유율(fraction)이 변화하여 저장된 값에 영향을 줄 정도라면, 그 항목은 free-space map에서 업데이트된다. Figure 6는 16개의 블록을 가진 파일에 대한 free-space map이다:

위에서 점유율을 표현하기 위해서 3비트를 사용한다고 가정한다면, 각 항목에 저장된 값을 8로 나누어서 각 블록에 해당하는 여유 공간의 비율을 구할 수 있다. 예를 들어, 값이 7이라면, 해당 블록 공간의 최소 7/8이 비어 있음을 의미한다. 주어진 크기의 새로운 레코드를 저장할 블록을 찾기 위해, 데이터베이스는 free-space map을 스캔하여 충분한 공간을 가진 블록을 찾을 수 있다. 만약 그런 블록이 없다면, 새로운 블록이 릴레이션에 할당된다.

파일:Second-level free-space map example.png

Figure 7. Second-level free-space map

이러한 스캔은 실제로 블록을 직접 읽는 것보다는 훨씬 빠르지만, 파일이 매우 큰 경우에도 여전히 느릴 수 있다. 이 문제를 해결하기 위해, 2단계 free-space map을 도입할 수 있다. 예를 들어, 주 free-space map의 100개 항목마다 하나의 항목을 가지는 2단계 free-space map을 생성할 수 있다. 이 항목은 해당하는 100개 항목 중 최댓값을 저장한다. 아래에 제시된 free-space map은 앞서 예시로 든 주 map에 대해 4개 항목마다 하나씩 대응되는 2단계 free-space map이다:

100개마다 하나의 항목을 가진 2단계 맵이 있다면 2단계 맵을 스캔하는 시간은 1/100로 줄어든다. 이때 충분한 여유 공간이 있는 항목을 찾으면 그에 대응되는 free-space map의 100개 항목을 스캔하여 실제로 충분한 공간을 가진 블록을 찾을 수 있다. 하지만 free-space map의 항목이 갱신될 때마다 디스크에 즉시 기록하는 것은 매우 비용이 크므로 free-space map은 주기적으로 디스크에 기록된다. 따라서 디스크에 있는 free-space map은 최신 상태가 아닐 수 있으며, 데이터베이스가 시작될 때, 오래된 여유 공간 정보를 얻을 수 있다. 그 결과, free-space map이 실제로는 공간이 없는 블록을 공간이 있다고 잘못 표시할 수 있다. 이런 오류는 해당 블록을 실제로 읽어들이면 발견되며 다시 map을 검색하여 다른 블록을 찾는 방식으로 처리된다. 반면에, map이 실제로는 공간이 있는 블록을 공간이 없다고 잘못 판단할 수도 있다. 이 경우는 단지 공간이 사용되지 않은 채 남겨지는 문제일 뿐이다.

Sequential File Organization

파일:Sequential file for instructor records.png

Figure 8. Sequential file for instructor records

Sequential file은 어떤 검색 키(search key)를 기준으로 정렬된 순서를 통해서 레코드를 효율적으로 처리할 수 있도록 설계된다. 어떤 릴레이션의 어떤 속성이나 여러 속성들의 집합은 모두 검색 키가 될 수 있으며, 반드시 기본키(primary key)이거나 슈퍼키(superkey)일 필요는 없다. 이때 검색 키 순서대로 레코드를 빠르게 검색할 수 있도록, 레코드들을 포인터로 연결(chain)하고, 각 레코드에 있는 포인터는 검색 키 순서상 다음 레코드를 가리키도록 한다. 또한 sequential file 처리에서 블록에 대한 접근 횟수를 최소화하기 위해, 레코드들을 물리적으로(physically) 검색 키 순서에 가깝게 또는 가능한 한 그 순서대로 저장한다. Figure 8은 instructor 레코드들의 sequential file을 보여주며, ID를 검색 키로 사용하여 검색 키 순서로 레코드를 저장하고 있다. sequential file 조직은 레코드를 정렬된 순서대로 읽을 수 있게 해주며, 이는 출력(display)이나, 특정 질의 처리 알고리즘들에 대해서 유용하다.

하지만, 레코드가 삽입되거나 삭제될 때, 물리적 정렬 순서를 유지하는 것은 어렵다. 이는 삽입이나 삭제 하나 때문에 여러 레코드를 이동해야 하는 높은 비용이 들기 때문이다. 먼저 삭제는 이전 절에서 본 것처럼 포인터 체인을 이용해 처리할 수 있다. 그리고 삽입 작업을 위해서는 다음 두 가지 규칙을 따른다.

1. 검색 키 순서상 삽입될 레코드 앞에 오는 레코드를 파일 내에서 찾는다.
2. 이 레코드와 같은 블록 안에 삭제된 레코드로 인해 남은 여유 공간이 있다면, 새 레코드를 그곳에 삽입한다. 그렇지 않다면, 오버플로우 블록(overflow block)에 새 레코드를 삽입한다. 어느 경우든, 포인터를 조정하여 검색 키 순서대로 레코드들을 연결한다.

파일:Figure 9. Sequential file after an insertion.png

Figure 9. Sequential file after an insertion

Figure 9은 (32222, Verdi, Music, 48000) 레코드를 figure 8의 파일에 삽입한 후의 구조를 보여준다. 이 구조는 새 레코드를 빠르게 삽입할 수 있게 하지만, 레코드들의 물리적 순서와 일치하지 않는 순서로 sequential file 응용 프로그램이 레코드를 처리하게 만든다. 오버플로우 블록에 저장되어야 하는 레코드 수가 적을 경우, 이 방식은 잘 작동한다. 그러나 시간이 지남에 따라 검색 키 순서와 물리적 순서 간의 대응 관계가 완전히 깨질 수도 있으며, 이 경우 seqential file의 효율성이 크게 저하된다. 이 시점에서 파일을 다시 정렬된 순서대로 물리적으로 재구성(reorganize) 해야 하는데, 이는 비용이 크므로 시스템 부하가 적은 시간에 수행해야 한다.

Multitable Clustering File Organization

대부분의 관계형 데이터베이스 시스템은 각 릴레이션을 하나의 파일 또는 별도의 파일 집합에 저장하므로, 대부분은 각 파일과 그 파일의 블록이 오직 하나의 릴레이션에 속한 레코드만 저장한다. 하지만 어떤 경우에는 하나의 블록에 여러 릴레이션의 레코드를 저장하는 것이 유용할 수 있다. 여러 릴레이션의 레코드를 하나의 블록에 저장하는 장점을 이해하기 위해, 다음과 같은 대학 데이터베이스에 대한 SQL 쿼리를 생각해보자:

select dept.name, dept.building, dept.budget, instr.ID, instr.name, instr.salary
from department natural join instructor;

이 쿼리는 department와 instructor 릴레이션의 내츄럴 조인 연산을 수행한다. 따라서 각 department 튜플에 대해, dept_name이 같은 instructor 튜플들을 찾아야 한다. 이때 레코드의 실제 데이터는 디스크에서 메인 메모리로 읽어들여야 하므로, 릴레이션의 레코드를 저장하는 각 블록을 읽을 때마다 디스크에 대한 접근이 필요하다. 예를 들어 10명의 instructor 레코드가 있고 각각 다른 블록에 저장되어 있다면 10번의 디스크 접근이 발생한다.

파일:The department relation.png

Figure 10. The department relation

파일:The instructor relation.png

Figure 11. The instructor relation

구체적인 예로, figure 10의 department 릴레이션과 figure 11의 instructor 릴레이션을 바탕으로 figure 12를 살펴보자. Figure 12는 department와 instructor의 내츄럴 조인 연산을 포함하는 쿼리의 효율적인 실행을 위해 설계된 파일 구조를 보여준다. 특정 dept_name에 해당하는 모든 instructor 튜플은, 해당 department 튜플 근처에 저장되어 있다. 이러한 두 릴레이션은 dept_name 키를 기준으로 클러스터링(clustering) 되어 있다고 불린다. 또한 클러스터 키(cluster key)는 어떤 레코드들이 함께 저장될지를 결정하는 속성이며, 해당 예시에서는 dept_name이다.

이때 각 레코드는 자신이 속한 릴레이션의 식별자(identifier)를 포함한다고 가정하지만, figure 12에는 이것이 생략되어 있다. 또한 figure 12에는 나타나 있지 않지만, 클러스터링을 정의하는 dept_name 속성의 값은 두 릴레이션의 튜플 그룹마다 한 번만 저장할 수도 있으며, 이를 통해 저장 공간의 오버헤드를 줄일 수 있다.

파일:Multitable clustering file structure.png

Figure 12. Multitable clustering file structure

이러한 구조는 조인을 효율적으로 처리할 수 있게 해준다. department 릴레이션의 하나의 튜플이 읽힐 때, 해당 튜플이 포함된 전체 블록이 디스크에서 메인 메모리로 복사된다. 이때 해당 department 튜플과 가까운 디스크 위치에 연관된 instructor 튜플들도 저장되어 있으므로, 그 블록에는 쿼리를 처리하는 데 필요한 instructor 튜플들이 포함되어 있게 된다.
만약 어떤 department가 너무 많은 instructor를 가지고 있어서 레코드가 한 블록에 모두 들어가지 못할 경우, 나머지 레코드들은 인접한 블록들에 저장된다.

다중 테이블 클러스터링 파일 조직은 특정 조인 쿼리를 빠르게 처리할 수 있게 하지만, 다른 종류의 쿼리 처리 성능은 느려질 수 있다. 예를 들어 앞의 예에서,

select * from department;

을 수행할 경우, 각 블록이 더 적은 수의 department 레코드만 포함하므로, 이전의 독립적으로 파일에 각 릴레이션의 레코드를 저장하는 방식보다 더 많은 블록 접근이 필요하다. 이때

특정 블록 내의 모든 department 튜플을 효율적으로 찾기 위해 포인터를 이용하여 해당 릴레이션의 모든 레코드를 연결(chain)할 수 있지만, 이것이 읽어야 할 블록의 수를 줄여주는 것은 아니다. 따라서 다중 테이블 클러스터링을 사용할지의 여부는 데이터베이스 설계자가 가장 자주 수행될 쿼리 유형이 무엇일지 판단하는 것에 달려 있다. 이때 다중 테이블 클러스터링은 Oracle 데이터베이스 시스템에서 지원된다.

Partitioning

많은 데이터베이스는 하나의 릴레이션에 있는 레코드들을 더 작은 릴레이션들로 분할하여 따로 저장하는 것을 허용한다. 이러한 테이블 파티셔닝(table partitioning)은 일반적으로 속성 값을 기준으로 수행된다. 예를 들어, 회계 데이터베이스의 transaction 릴레이션은 연도(year)를 기준으로 분할되어, 각 연도에 해당하는 더 작은 릴레이션들로 나뉘어 저장될 수 있다.
쿼리는 여전히 원래의 transaction 릴레이션을 기준으로 작성되지만, 실제로는 연도별 릴레이션들에 대한 쿼리로 변환된다. 이를 위해 쿼리 최적화기(query optimizer)가 사용되어 쿼리를 실제로 요청된 것보다 작은 릴레이션에만 접근하도록 재작성할 수 있으며, 다른 연도에 해당하는 레코드들은 읽지 않아도 되게 한다. 예를 들어, 아래의 쿼리는:

select * from transaction where year = 2019

는 쿼리 최적화기에 의해서 아래와 같은 쿼리로 변형된다:

SELECT * FROM transaction_2019;

즉, transaction_2019 릴레이션에만 접근하며, 다른 릴레이션들은 무시한다. 하지만 연도에 대한 조건이 없는 쿼리는 모든 릴레이션을 읽는다. 레코드를 위한 여유 공간을 찾는 작업과 같은 일부 연산의 비용은 릴레이션의 크기가 커질수록 증가하는데, 파티셔닝은 릴레이션 크기를 줄이기 때문에 이러한 오버헤드를 줄이는 데 도움이 된다. 또한 파티셔닝은 릴레이션의 서로 다른 부분을 서로 다른 저장 장치에 저장하는 데도 사용될 수 있다. 예를 들어, 2019년에는 transaction_2018와 같이 자주 접근되지 않는 데이터는 하드 디스크에, transaction_2019처럼 빠른 접근이 필요한 데이터는 SSD에 저장할 수 있다.

Data-Dictionary Storage

릴레이션 데이터베이스 시스템은 릴레이션 인스턴스 뿐만 아니라 릴레이션의 스키마와 같은 릴레이션에 대한 데이터도 유지해야 한다. 일반적으로 이러한 “데이터에 대한 데이터”는 메타데이터(metadata)라고 한다. 관계 스키마 및 릴레이션에 대한 기타 메타데이터는 데이터 사전(data dictionary)이라고 불리는 자료 구조에 저장된다. 이때 시스템이 저장해야 하는 정보의 유형을 아래와 같다:

파일:Relational schema representing part of the system metadata.png

Figure 13. Relational schema representing part of the system metadata

• 릴레이션에 대한 정보
  • 릴레이션의 이슴들
  • 릴레이션에 속한 속성들의 이름, 데이터 타입, 길이
  • 데이터베이스에 정의된 뷰(view)들의 이름 및 정의
  • 무결성 제약 조건
• 사용자 및 계정 정보
  • 사용자 이름, 기본 스키마(default schema), 사용자 인증용 비밀번호나 기타 정보
  • 각 사용자에 대한 권한 정보
• 통계 및 설명 데이터
  • 각 릴레이션에 들어 있는 튜플 수 (→ 옵티마이저가 사용)
• 물리적 파일 구성 정보
  • 릴레이션이 어떻게 저장되는지
  • 릴레이션이 어디에 저장되는지
• 인덱스 정보

이러한 모든 메타데이터 정보는 사실상 하나의 미니 데이터베이스를 구성한다. 일반적으로 이 미니 데이터 베이스는 데이터베이스 자체 안에 있는 릴레이션들로 저장한다. 이를 통해서 전체 시스템 구조를 가능하게 하고, 시스템 데이터에 빠르게 접근할 수 있도록 데이터베이스의 기능을 활용할 수 있다. 시스템 메타데이터를 릴레이션으로 어떻게 표현할지는 시스템 설계자가 결정하며, 다양한 방식으로 작성될 수 있다. Figure 13은 위에서 언급한 정보의 일부를 저장하는 간단한 데이터 사전의 스키마 다이어그램을 보여준다. 아래는 각 릴레이션에 대한 설명들이다:

• Relation_metadata: 릴레이션의 이름, 속성 개수, 저장 방식, 물리적 위치
• Attribute_metadata: 릴레이션의 각 속성에 대한 정보: 이름, 타입, 순서, 길이
• Index_metadata: 인덱스 이름, 어떤 릴레이션과 속성에 대한 인덱스인지, 인덱스 타입 등
• View_metadata: 뷰 이름과 정의
• User_metadata: 사용자 이름, 암호화된 비밀번호, 그룹 정보

해당 메타데이터 표현 방식에서, relation_metadata 릴레이션의 index_attributes 속성이 하나 이상의 속성들로 구성된 목록을 포함한다고 가정하자. 이는 "dept_name, building"과 같은 문자열로 표현될 수 있다. 이러한 이유로 index_metadata 릴레이션은 제1정규형(1NF)을 만족하지 않는다. 물론 이를 정규화할 수도 있지만, 위와 같은 표현 방식이 접근 효율성 측면에서 더 나을 수 있다. 사실 빠른 접근을 위해 데이터 사전은 종종 정규화되지 않은 형식으로 저장된다.

데이터베이스 시스템이 릴레이션으로부터 레코드를 검색하기 위해서는 먼저 relation_metadata 릴레이션을 참조하여 그 릴레이션의 위치와 저장 조직 방식을 찾고, 그 정보를 이용하여 실제 레코드를 가져와야 한다. 하지만 relation_metadata 릴레이션 자체의 저장 방식과 위치는 다른 곳에 기록되어 있어야 한다. 왜냐하면, relation_metadata의 내용을 찾기 위해서는 그 위치 정보를 먼저 알아야 하기 때문이다.

Database Buffer

오늘날의 대부분의 데이터베이스에서 데이터는 주로 디스크에 저장되어 있으며, 이를 읽거나 갱신하기 위해 메모리로 가져와야 한다. 또한 갱신된 데이터 블록은 이후 다시 디스크에 기록되어야 한다. 하지만 디스크에서의 데이터 접근은 메모리 내 접근보다 훨씬 느리기 때문에, 데이터베이스 시스템은 디스크와 메모리 간의 블록 전송 수를 최소화하고자 한다. 디스크 접근 횟수를 줄이는 한 가지 방법은 가능한 많은 블록을 메인 메모리에 유지하는 것이다. 이는 어떤 블록에 접근할 때 그 블록이 이미 메모리에 있을 확률을 높이는 것이고, 이 경우에는 디스크에 대한 접근이 필요 없기 때문이다. 그러나 모든 블록을 메모리에 유지하는 것은 불가능하므로 메모리에 할당된 블록 저장 공간의 관리가 필요하다. 이러한 상황에서 버퍼(buffer) 개념이 등장한다. 데이터베이스 시스템에서 버퍼(buffer)는 디스크 블록의 복사본을 저장하기 위해 메인 메모리에서 사용 가능한 부분을 의미한다. 이때 버퍼에 저장된 디스크 블록의 복사본에 어떤 갱신이나 삭제 작업이 가해진다면, 실제로 디스크에 저장된 블록은 업데이트되지 않고, out-of-date 상태가 될 수 있다.

Buffer Manager

자세한 내용은 Buffer Manager 문서를 참조해 주십시오.

Column-Oriented Storage

파일:Columnar representation of the instructor relation.png

Figure 14. Columnar representation of the instructor relation

데이터베이스는 기본적으로 하나의 튜플에 있는 모든 속성을 하나의 레코드에 함께 저장하며, 이러한 저장 방식을 row-oriented storage 방식이라고 한다. 반면 column-oriented storage 방식은 릴레이션의 각 속성을 따로 저장하고, 연속된 튜플들로부터의 속성값들을 파일 안에 연속적으로 저장한다. Figure 14는 instructor 릴레이션이 column-oriented storage 방식으로 어떻게 저장되는지를 보여준다. 가장 단순한 형태의 열 지향 저장에서는 각 속성이 별도의 파일에 저장된다. 아래는 column-oriented storage 방식의 장점이다:

1. I/O 감소: 많은 속성을 가진 릴레이션에서 일부 속성만 접근할 경우, 나머지 속성은 디스크에서 메모리로 가져올 필요가 없다.
2. CPU 캐시 성능 향상: 쿼리 프로세서가 특정 속성값을 가져올 때, CPU는 연속된 바이트가 메모리에서 CPU 캐시에 함께 로드된다. 이후 해당 바이트들이 다시 접근될 경우, 캐시에 있으면(캐시 히트!) 매우 빠르게 접근할 수 있다. 이때 이 바이트들이 쿼리에서 필요하지 않은 속성 값이라면, 캐시 공간과 메모리 대역폭이 낭비된다.
3. 압축 효율 향상: 동일한 타입의 값들을 함께 저장하면, 서로 다른 타입들이 섞여 있는 행 저장보다 압축 효율이 훨씬 높아진다.
4. 벡터 처리 지원: CPU는 배열 내 여러 값에 대해 병렬로 연산을 수행할 수 있는 벡터 처리(vector processing)를 지원한다. 이때 column-oriented storage 방식은 여러 연산을 벡터화할 수 있어 이에 유리하다.

아래는 해당 방식의 단점이다:

1. 튜플 재구성 비용: 각 열로부터 튜플을 재조립하는 것은 비용이 크다.
2. 튜플 삭제 및 갱신 비용: 튜플을 삭제/갱신/삽입할 때에는 튜플이 여러 열에 분산되어 있어 비효율적이다.
3. 압축 해제 비용: 데이터를 사용할 때 압축을 풀어야 하므로 오버헤드가 발생한다.

이러한 장단점을 고려할 때, column-oriented storage 방식은 대규모 데이터에 대해 집계/통계/분석을 할 때 유리하다. 반면, row-oriented storage 방식은 삽입/삭제/갱신 등의 트랜잭션 작업을 할 때 유리하다. 따라서, 일부 DBMS는 두 방식을 모두 사용하는 hybrid row/column stores 방식을 사용하여 두 장점을 모두 취한다.

Columnar File Representation

파일:Columnar data representation in the ORC file format.png

Figure 15. Columnar data representation in the ORC file format

ORC와 Parquet는 빅데이터 처리에서 널리 사용되는 column-oriented storage 방식을 기반으로 하는 파일 형식이다. Figure 15는 ORC 파일 형식의 세부사항을 보여준다. 각 stripe는 인덱스 데이터(index data)와 행 데이터(row data)로 구성된다. 인덱스 영역은 각 속성마다 10,000개 값 단위로 압축 시작 위치를 저장하며, 이를 통해 원하는 튜플이나 튜플 시퀀스에 빠르게 접근할 수 있다.

파일:In-memory columnar data representation.png

Figure 16. In-memory columnar data representation

Storage Organization in Main-Memory Databases

오늘날에는 메인 메모리의 용량이 충분히 크고 가격도 저렴해져서, 데이터베이스 전체를 메모리 내에 저장할 수 있다. 이는 사실상 데이터베이스 전체를 버퍼에 적재하여 데이터를 읽기 위한 디스크 I/O 작업을 피할 수 있다.

이때 데이터베이스 전체가 메모리에 들어가는 경우, 저장 구조와 데이터베이스 자료구조를 메모리 내에 존재하는 데이터의 특성을 활용해 최적화하여 성능을 크게 향상시킬 수 있다. 메인 메모리 데이터베이스(main-memory database)란 모든 데이터가 메모리에 존재하는 데이터베이스를 의미한다. 이러한 메인 메모리 데이터베이스 시스템은 이러한 특성을 활용하여 성능을 최적화하도록 설계되어, 버퍼 매니저(buffer manager)를 필요로 하지 않는다.

만약 column-oriented storage 방식이 메인 메모리 데이터베이스 시스템에서 사용된다면, 하나의 열에 있는 모든 값들을 연속된 메모리 위치에 저장할 수 있다. 이는 대규모 데이터에 대해 집계/통계/분석을 할 때 매우 큰 성능 향상을 보여줄 수 있다. 또한 압축(conpression)을 통해 메모리 사용량을 감소시킬 수 있으며, 특히 column-oriented storage 방식은 유사한 데이터가 인접해 있어 그 효율이 높다.