[database] DBMS는 데이터를 어떻게 저장하고 관리할까(Heap File Structure, Slotted Page Structure)

본 게시글은

서울대학교 데이터사이언스대학원 이상원 교수님의

데이터사이언스 응용을 위한 빅데이터 및 지식관리시스템 수업을

학습을 목적으로 재구성하였습니다

---

저번 시간까지가 중간고사 범위였다

저번 시간까지는 사실 단순(?) SQL과

여러 가지 종류의 SQL representation에 대해 배웠다면

중간고사 이후부터는 DB internal에 대해 배운다

 

지금부터 배우는 것들이

정말 중요한 내용이라고 한다

 

 

DBMS의 internal 부분을 살펴보자

오늘 배울 내용은 file and access method이다

 

실제로 우리가 만드는 테이블 데이터들이

디스크 storage에 어떻게 저장되는지에 대한 내용이다

실제로 디스크에 datafile이라는 형태로 테이블은 저장되고

테이블에 대한 정보들은 디스크에 system catalog나

dictonary의 metadata 형태로 관리된다고 한다

 

그리고 우리가 index를 만들면

index도 storage에 저장된다

 

DB에는 Logical level과 physical level이 있다

 

logical level은 우리가 흔히 생각하는

CREATE TABLE을 해주고

column들을 정의하는 구조라고 생각하면 된다

우리가 생각하는 그 테이블 형태이다

 

그런데 disk에 이 table형태가

그대로 저장되는 것은 당연히 아닐 것이다

정말 실제 disk에 어떻게 저장되어있을까

그것이 physical database level이다

가장 보편적인 형태의 구조가

slotted page structure이고

이번 시간에 우리가 배우게 될 내용이다

 

 

DB에 테이블을 만들고 tuple들을 넣으면

storage에 저장된다

위에서 storage의 가장 보편적인 구조는

slotted page structure라고 했다

 

위 DBMS architecture를 보면

Buffer Manager가 있는데

여기서 buffer manager는 DRAM이다

이 DRAM이 disk space manager

즉, disk와 data를 왔다갔다하며

IO를 수행한다

 

시스템 프로그래밍 시간에 배웠듯이

DRAM <-> disk의 IO 단위는

보통 4KB이고

이 단위를 page라고 부른다

 

DBMS의 쿼리 프로세스는

특정한 table에 속하는 record단위로 access한다

logical한 table이 있으면

그에 해당하는 Physical한 객체가 있는 것이다

그래서 각 table 당 튜플들을 담고 있는

container로써 물리적으로 해당하는 file이 있다

이 file은 물리적으로 page들을 담고 있는 집합이다

이를 record interface를 통해 접근한다

 

table에 새로운 tuple이 insert되면

물리적으로도 해당 file에다 insert하고

DBMS는 그런 operation들을 지원해야한다

 

또, 모든 tuple들은 자기의 unique한 id를 가진다

따라서 이 id만 있으면 특정한 tuple을 가져올 수 있고

이러한 Interface도 DBMS는 지원한다

 

마지막으로 DBMS는 튜플 전체를 처음부터 끝까지 읽어오는

interface도 제공해야한다

 

 

unordered heap file은

structure가 record를 담고있는 기본적인 형태로

순서가 없는 레코드 집합이다

여기서 heap은 자료구조에서의 heap과는 아무런 관계가 없다

 

정렬이 되어있지 않기 때문에

record가 insert될 때 레코드를 끌어다가

빈 자리에 append 시킬 수 있다

어떤 경우 정렬이 필요해서

ordering을 지원하는 자료구조도 있지만

일반적으로는 heap 파일을 사용한다

 

DBMS는 record level operation을 지원하기 위해서

몇 가지를 반드시 수행해야하는데

1) 이 file에 해당하는 page가 얼마나 있는지

2) 페이지에 빈 공간이 얼마나 있는지

3) 페이지 안에서 레코드들의 위치

이러한 것들을 계속 tracking하고 있어야한다

 

 

그렇다면 이러한 heap file을 실제로 어떻게 구현할 수 있을까

첫 번째는 list 형태로 관리하는 것이다

실제로 이렇게 되어있다는 것은 아니고

그냥 이런 방식으로도 구현이 가능하다는 것이다

 

이렇게 metadata나 여러 정보를 담고 있는

Header page를 두고

각 page가 2개의 포인터를 갖고있는

양방향 linked list의 형태로 구현할 수도 있다

(실제로는 이렇게 구현 X)

 

 

이런 방식으로도 구현할 수 있다

Header Page가 있고

page directory라는 곳에

각 page마다 저장 위치나 빈 공간을 저장해두면

record 삽입 시 빠르게 찾아가서 삽입을 수행할 수 있다

위의 linked list 구조는 비어있는 page를 찾기 위해

하나하나 쫓아가야하는 구조라 비효율적이었다

하지만 이 구조는 그렇게 쫓아갈 필요는 없는 것이다

그리고 이런 directory 자체도 사실 page의 collection이다

 

 

지금까지 살펴본건 그냥 개념적인 내용이었고

지금부터는 실제 oracle에서 어떻게 구현되어있는지 살펴보자

postgres도 비슷한 형태로 구현되어있다고한다

대부분의 DB는 다 유사하게 구성이 되어있다

 

oracle은 tablespace라는 개념이 있고

그 안에 segment, extents, blocks라는 개념들이 있다

 

tablespace는 물리적인 개념은 아니고

logical한 공간이다

system tablespace가 있고 logical tablespace가 있다

system tablespace는 시스템이 사용하는 논리적 공간으로

메타데이터들이 주로 저장되는 곳이다

user tablespace는 유저가 정의하는

테이블, 인덱스 등이 저장되는 곳이다

 

이 tablespace는 논리적인 공간이고

실제 데이터는

이 공간에 포함된 datafile이다

 

user가 tablespace를 만들고 그 위에

내가 만들 table을 만들었다고 가정하자

그럼 각각의 table에 대해서

하나의 segment가 생성되는데

이게 table segment이다

그리고 이 segement가 바로 physical file이다

logical한 table이나 index는 생성하게 되면

그에 해당하는 physical file로써 하나의 segment를 갖게되고

이 segment가 물리적 저장소가 되는 것이다

 

이런 segment는 extent라는 단위로 구성이 되는데

extent는 연속된 page=block의 집합이며

block들 집합의 단위가 extent이다

용어가 자꾸 바뀌어서 헷갈릴 수 있겠지만

IO최소단위 = page이고 여기선 이걸 block과 동일하게 여긴다

 

한마디로 정리하자면

page(block) < extent < segment

가 되는 것이고

page의 집합 = extent

extent의 집합 = segment

가 되는 것이다

 

 

지금까지 위에서 설명한 내용을

그림으로 도식화한 것이라고 한다

 

우선 table 혹은 index를 생성하면

segment가 한개씩 배정된다

그럼 그 segment는 extent들로 구성이 되어있다

그러고 이 extent들은 다시 page들의 집합으로 구성이 되는데

page는 4KB 혹은 8KB 단위의 연속된 데이터들의 집합인 것이다

 

 

 

tablespace를 정의하는 내용이다

 

 

orcale DB에서 데이터를 담는 폴더들을 보면

DBF라는 확장자가 있는데

이 DBF 파일이 tablespace에 해당하는 파일들이다

 

우선 Oracle을 설치하면 4개의 tablespace가 만들어지는데

user tablespace

system tablespace

temp tablespace

그리고 recovery 용도로 사용하는 tablespace가 있다고 한다

 

oracle에서 sysdba로 접속해서

SHOW PARAMETERS db_block_size

 

쿼리를 입력하면 block size 정보를 볼 수 있다

앞에서 말했듯 block = page이고

DB에서는 보통 8KB 단위를 사용한다

 

수업시간에 교수님께서 위 쿼리를 활용해서

oracle에서 이것저것 정보들을 확인해주셨다

 

교수님께서 설명해준 예시의 경우

한 page에 tuple들이 10개씩 들어가는 것을 확인할 수 있었는데

이는 tuple한개가 658B이기 때문에

658B * 10 하면 약 8KB를 만족시키기 때문이다

 

그럼 만약 tuple을 100만개를 insert하게 되면

1 page에 10 tuple이 들어가므로

10만 page가 생성되게 된다

그럼 page 1개가 8KB이므로

8KB * 10만을 하면 800MB가 나온다

 

ANAYLZE TABLE test COMPUTE STATISTICS;

 

또 위 쿼리를 한 번 실행해봤다

이 쿼리를 실행해서 알 수 있었던 건

AVG_SPACE가 있었는데

이는 각 page에 평균적으로 비어있는 공간을 알려준다

모든 page를 꽉꽉 채우지 않고

보통 10% 정도 되는 공간은 비워둔다고 한다

 

 

지금 위 ppt slide를 보면

각 row가 extent를 나타내는 것을 알 수 있다

각 row마다 extent_id가 있다

위 예시의 경우 총 23개의 extent가 test라는 table에 있는 것이다

그리고 운영체제 파일에서는 4번 file인 것이고

block_id는 각 extent의 시작 page 주소를 나타낸다

 

그러고 blocks column을 보면

각 extent당 block이 총 몇개가 있는지를 볼 수 있는데

처음에는 8개씩 있다가 나중에 개수가 128로 뛰는 것을 볼 수 있다

이게 왜 이렇게 되냐면

처음에는 조금씩 할당하다가 나중에

이 table자체가 좀 큰 파일이라고 판단해서

extent의 size를 점차 늘려나간다고 한다

그래서 뒤로갈수록 block_size가 커지는 것을 확인할 수 있다

 

따라서 extent의 시작 주소인 block_id를 보면

block_size만큼 점진적으로 증가하는 것을 볼 수 있다

이러한 경우는 extent가 연속적으로 쭈루룩 할당되어있기 때문인데

이건 한명의 사용자가 접속해서 생성할 때

이렇게 연속적으로 할당될 수 있다고 한다

실제로 여러 명의 사용자가 동시에 접속해서 데이터를 넣는다면

이렇게 연속적으로는 나오지 않는다고 한다

 

 

 

그렇다면 page는 각 record들의 집합이라고 했다

그렇다면 page 안에서 record들을 어떻게 관리할까?

이 구조를 page format이라고 부른다

 

위 예시는 fixed length record의 경우인데

page 내부에 있는 record들의 길이가

고정되어있을 때의 경우이다

하지만 보통 record 길이는 가변적이기 때문에

fixed length record는 잘 쓰지 않는다

아무튼 그래도 알아보자

 

각 tuple들의 길이가 100바이트라고 가정해보자

여기서 N은 tuple의 개수이다

이게 50이라고 가정해보자

그럼 첫번째부터 50개까지 packing되어서

위 그림처럼 차곡차곡 나란히 50개가 들어가게 된다

그러고 새로운 데이터가 추가되면 빈자리에 51번째가 추가되는 것이다

 

그런데 만약 데이터를 삭제하고싶다면?

이게 packing이 되어있기 때문에

뒤에 있는 것을 copy해서 앞에다가 넣어줘야하는 문제가 있다

 

그래서 packing을 하면 삭제했을 때

데이터 전체가 이동해야하는 문제가 있기 때문에

packing을 하지 않고 bitmap으로 record가 어디에 있는지 표현한다

 

또한 특정한 record를 선택해야할 때

해당 record가 어떤 page에 있으며

해당 page 내의 어디에 있는지를 검색해야하는데

그걸 하도록 도와주는게 record id이다

이 record id는 나중에 index를 할 때도 사용한다

 

 

 

하지만 record들은 보통 고정길이가 아니다

각각의 record들은 길이가 각각 다르다

따라서 가변 길이의 record를 담을 수 있는 page 구조가 필요하다

따라서 대부분의 DBMS는 이런식으로 page 구조를 가진다

 

slot directory의 가장 처음에는 시작 부분의 pointer를 담고있고

각 slot들은 record의 시작 pointer를 갖고있다

만약 100번 page의 5번째 record을 찾으라고 하면

100번 page의 총 N개의 slot에서 5번에 진입한 다음

거기의 시작 pointer에 접근하게 되는 것이다

 

따라서 이런 하나의 record를

slot이라고 표현하기도 하고

physical tuple이라고 부르기도 한다

 

그래서 이걸 slotted page structure라고 부른다

이게 보편적인 형태의 page 구조이다

 

정확한 페이지 구조가 궁금해서 gpt한테 물어봤다

 

하나의 페이지 안에 이렇게 구성이 되어있다고 한다

 

oracle에서 EMP라는 테이블을

block dump를 시켜보자

 

 

이게 EMP table을 binary형태로 dump한 내용이다

page format이 있었다면

record들의 format도 있을 것이다

 

 

 

fixed length record일 때의 record format을 보자

record의 길이가 정해져있기 때문에

record 내부의 데이터들은

offset을 더하는 형식으로 찾아가면 된다

 

 

 

이번에는 record의 길이가 다를 때를 살펴보자

가변길이일때는 위의 예시처럼

주소값으로 계산할 수가 없다

따라서 가변일 때는 각 field의 끝에

$를 통해서 해당 field의 끝임을 나타낸다

 

그래서 만약에 해당 Record의 4번째 column에 접근하고 싶다면

$를 3번을 지나가면 된다

따라서 어떤 column을 찾기 위해서

주소값을 jump할 수 있는 방법은 없고

전체를 scanning을 해야한다

 

따라서 이렇게 전체 scanning을 하지 않고

각 column의 시작 pointer를 앞에 저장해서

포인터를 기준으로 접근을 하게 된다

따라서 4번째 column에 접근하고 싶다면

pointer array에서 세번째 Pointer를 찾아가면

4번째 column이 시작하는 주소를 찾아갈 수 있는 것이다

레이아웃은 위 ppt의 그림처럼 되어있다

 

 

oracle의 row layout이라고 한다

앞부분이 row header

뒷 부분이 column data로 구성되어있다고 한다

 

 

 

row layout 구조를 좀 더 자세히 살펴보자

여기서 column count는 8개이다

가장 앞에는 row flag, lock byte, column count들이 각각 1바이트씩 들어있다

cluster key idx는 optional하게 들어있다

이제 그 다음부터 8개의 column에 대한 정보가 들어가있다

 

위 예시에서 첫번째 column은 EMPNO이다

얘는 column length가 3인데

뒤의 3바이트가 이 column을 표현한다는 뜻이다

따라서 c2 4a 46이

7396을 표현하는 것이 되는 것이다

 

그 다음은 ENAME이다

column length가 5이기 때문에

5바이트가 이 데이터를 표시하고

53 4d 49 54 48이

SMITH를 나타내게 되는 것이다

 

그리고 COMM field는 NULL값이 들어가있다

따라서 길이를 0xFF로 표현하면 이건 Null로 간주하기로 약속했다

 

또한 기존의 column length로는

표현이 안되는 column이 있을 수도 있다

그런 경우는 그 다음에 length field를 둬서

부족한 length를 더 표현한 다음

그 다음에 data를 표현한다

 

이 것이 oracle의 가변 길이의 tuple을 지원하는 방식이다

 

 

전형적인 DBMS의 tuple layout을 살펴보자

우리가 아는 logical table이 있고

column이 있고 tuple들에 그에 맞게 저장되어있다

이게 물리적인 disk에 저장할 때도

slotted pages안에서 그런 구조로 저장되어있다

따라서 위와 같은 방식으로 저장되어 있는 것을

열 중심이라고해서 row-store이라고 부르고

혹은 n-ary, NSM이라고도 부른다

 

그렇다면 보통 DBMS는 왜 이런 방식을 택했을까?

전형적인 OLTP query는

어떤 데이터를 가져올 때 그 모든 row를 가져와서

그 중에서 데이터를 선택하는 방식으로 한다

이런 쿼리 구조에서는 row-store가 유리한 것이다

 

하지만 OLTP가 아니라면?

만약 전체 row가 아니라 나이, 월급과 같은

특정 column만 중요하다면?

row-wise하게 하면 원하는 column이 아닌 나머지 column들의 값도

disk -> 메모리 -> CPU까지 끌고와야하고

여기서 불필요한 IO가 발생한다

 

그렇다면 이걸 해결할 수 있는 다른 방법은 없을까?

 

 

그 다른 방식이 바로

테이블을 쪼개서 column만 가져와서 작성하는

column-store 방식이다

column들만 가져와서 저장하는 것이다

 

그리고 이런 row-wise와 column-wise를

좀 더 hybrid하게 섞는게 PAX방식이다

이 PAX방식은 전체 튜플을 페이지 안에다가 집어넣고

페이지 안에서 record는 column-store 방식으로 저장한다

이러한 방식이 OLAP에서는 대세를 이루고 있고

OLTP에서는 여전히 row-store 방식이다

 

또 어떤 DBMS는 둘다 지원해야하기 때문에

데이터를 copy해서 각각의 store 형태로

dual 하게 지원하는 경우도 있다고 한다

---