CMU Database Fall 2022 를 듣고 정리한 글입니다.
Slotted Page Design Revisited
이전 강의에서 Slotted Page Table Design을 알아보았다. 이 구조에서 새 tuple을 삽입하기 위해서는 아래와 같은 절차를 따른다.
- Page directory를 확인해서 free slot이 남아 있는 Page를 찾는다.
- Page를 디스크로부터 혹은 메모리에서 가져온다.
- 해당 Page의 slot array에 접근하여 충분한 크기의 공간을 찾는다.
한편, 한 번 삽입한 tuple을 수정할 때에는 다음 절차를 따른다.
- Page directory를 확인해서 수정할 tuple이 있는 Page를 찾는다.
- Page를 디스크 혹은 메모리에서부터 가져온다.
- Slot Array로부터 수정 대상 tuple의 offset을 찾는다.
- 수정할 내용을 반영한다.
이 구조의 잠재적 위험은 다음과 같다.
- Fragmentation: tuple을 삭제하면 page가 파편화 될 수 있다.
- Useless Disk I/O: 특정 tuple을 읽을 수 없고, 대신 관심의 대상인 tuple이 포함된 어떤 disk block 전체를 읽어야 한다.
- Random Disk I/O: 만약 여러 개의 tuple을 동시에 읽거나 업데이트해야 할 경우, 한 block 안에 tuple들이 위치하지 않으면 결국 random I/O가 될 수 있다.
- Not overwritable system: 만약 underlying system이 기존 데이터를 덮어씌우는 것을 지원하지 않는다면? (ex: S3)
Log-Structured Storage
DBMS가 raw tuple data를 저장하는 대신, log record의 형태로 tuple의 changelog을 기록하는 방식이 있다.
각 log는 tuple의 unique identifier와 함께 변경 사항을 PUT 혹은 DELETE 와 함께 남긴다. 이 때 DBMS는 이전 record를 확인하지 않고 파일의 끝에 append 할 뿐이다.
페이지가 가득 차면 DBMS는 disk에 page를 쓰기 시작한다. 여기서 알 수 있는 것은, 모든 write는 sequential하고 disk의 page는 변경되지 않는다는 점이다.
이때 어떤 tuple을 읽는다고 생각해 보자. 그러면 DBMS는 log를 가장 최신의 것부터 검색하기 시작한다. 그러다가 tuple id가 같은 log을 발견하면 그것을 읽는다. 이때 log record는 메모리에 있을 수도 있고, 디스크에 있을 수 있다.
이 작업을 빠르게 하기 위해, tuple id를 마지막 log와 mapping 하는 인덱스 또한 가지고 있다.
Compaction
그런데 이 구조에서는 log가 계속해서 커지기만 한다. 따라서 DBMS는 주기적으로 page에서 필요 없는 부분을 삭제해 낭비되는 공간을 없애야 한다.
DBMS는 한 page에서 각 tuple id가 최대 한 번만 등장하도록 중복을 제거하고, tuple id를 가지고 page의 log를 정렬한다. 이를 통해 lookup performance가 증가할 수 있으며 이러한 테이블을 SSTables (Sorted String Tables)라고 한다.
Downsides
이러한 storage manager는 요즘 더 흔하게 볼 수 있지만, 단점 또한 존재한다. 우선 Compaction 연산이 비싸고, 값을 쓸 때 in-place로 값을 수정하는 것이 아니라, 매 번 새 log을 추가하고 compaction을 진행하고 그 결과를 다시 쓰는, 1개의 logical write가 여러 개의 physical write를 유발하는 write amplication을 발생시킨다.
Data Representation
tuple은 byte array일 뿐, 이것을 해석하고 attribute에 연관시키는 것은 DBMS의 일이다. data representation은 DBMS가 byte를 value로 해석하는 방법이다.
Integers
INTEGER/BIGINT/SMALLINT/TINYINT: C/C++에서 사용하는 Fixed length의 IEEE-754 standard를 사용한다.
Floats
FLOAT/REAL,NUMERIC/DECIMAL: 둘 다 소숫점을 표현하는데 사용되지만, 전자는 IEEE-754의 부동소숫점 표현이고, 후자는 Fixed-point decimal로 마치 string처럼 작동하며 오차는 없지만 성능에서 손해를 본다.
MySQL의 Numeric 정의는 대략 아래와 같다.
typedef int32 decimal_digit_t;
struct decimal_t {
int intg, frac, len;
bool sign;
decimal_digit_t *buf;
}즉 실제로 숫자를 담고 있는 것은 buf 가 가리키고 있는 메모리 공간이며 intg, frac, len, sign 은 이 자료의 메타데이터를 나타낸다.
Large Objects
VARCHAR/VARBINARY/TEXT/BLOB: length, checksum을 포함한 header 뒤에 data byte 를 담고 있다.
대부분의 DBMS는 page의 크기보다 큰 tuple을 허용하지 않는다. 그러한 tuple을 담으려면, 별도의 overflow storage page를 사용한다.
이러면 tuple은 overflow page의 tuple의 reference를 가지게 된다. overflow page가 또 다른 overflow page로의 reference를 가질 수도 있다.
그러나 몇 DBMS에서는 이러한 overflow page로도 감당이 안되는 큰 데이터를 external file로 저장하고 tuple은 그 file로의 reference만 갖게 할 수 있다. 이 때 DBMS는 file을 in-place로 수정하거나 durability / transaction protection을 보장할 수 없게 된다.
Date and Times
TIME, DATE, TIMESTAMP 는 Date/Time을 나타내는 용도로 사용된다. unix epoch부터 얼마 만큼의 unit time (ms)가 지났는지를 나타낸다.
System Catalogs
DBMS는 내부 catalog에다가 database에 대한 metadata를 기록한다.
- Tables, Columns, Indexes, Views
- Users, Permissions
- Internal Statistics
예를 들면 현재 database의 모든 table은 다음과 같이 알 수 있다.
SELECT *
FROM INFORMATION_SHCEMA.TABLES
WHERE table_catalog = '<db name>';하지만 DBMS들은 이것에 대한 (비표준) 숏컷을 지원한다.
SHOW TABLES;