CMU Databse Fall 2022 를 듣고 정리한 글입니다.
Database Workloads
데이터베이스의 Workload에는 다음과 같은 종류가 있다.
- OLTP (On-Line Transaction Processing): 한 번에 적은 양의 데이터를 읽거나 업로드하는 쿼리. 일반적으로는 read보다 write의 양이 많으며, 예시로는 Amazon storefront가 있다. 유저들이 장바구니에 물건을 추가하고 구매하고.. 하지만, 이러한 동작들은 유저의 정보에만 영향을 주기 때문에 OLTP
- OLAP (On-Line Analytical Processing): 많은 데이터를 읽어서 집계하는 복잡한 쿼리로 write보다는 read가 중심이며 상대적으로 느리다. 예시로는, '비오는 날에 서울에서 가장 많이 구매된 물건'을 계산하는 쿼리가 있을 수 있다.
- Hybrid Transaction + Analytical Processing: 둘 다
Storage Models
여기서 흥미로운 점은, DBMS는 각 page가 어떻게 구성되고 저장되는지를 기술하지 않기 때문에 각 workload에 따라 더 효율적이거나 그렇지 않은 방식의 구조가 있다는 것이다. 즉, 우리의 workload의 유형에 따라 storage 방법을 결정하면 더 효율적일 것이다.
NSM (N-ary Storage Model)
하나의 tuple에 대한 모든 attribute 들을 페이지의 연속된 바이트에 저장하는 방법이다. OLTP workload에 대해서는, 주로 sequential write가 되고 한 개의 tuple을 가져오는 것도 효율적이므로 좋다. 하지만, 여러 tuple의 일부 column을 가져오는 경우 비효율적이다.
DSM (Decomposition Storage Model)
tuple이 아니라, attribute 기준으로 모든 tuple의 한 attribute를 연속된 페이지에 저장한다. column store이라도고도 알려져 있다.
이 경우, OLAP workload에서는 많은 양의 tuple의 일부 attribute만 가져오는 경우가 많으므로 효율적이다. 특히 이는 Disk I/O이기 때문에 성능 상 이점이 크다. 하지만, 하나의 tuple에 대한 정보가 분산되기 때문에, insert/update/delete가 느리다.
DSM 에서는 특정 tuple을 구분하는 방법에 대해 고려해야 한다. 이 때 가능한 방법은 두 가지다.
- Fixed-length Offsets: 많이 사용되는 방법으로, 고정 길이의 오프셋을 이용해서 계산한다.
- Embedded Tuple Ids: value를 저장할 때 tuple id를 같이 저장한다.
Compression
Disk I/O가 병목이기 때문에, 약간의 CPU time을 희생해서 page를 압축한다면 효율적일 수 있다. 이는 특히 read 작업이 많은 데이터베이스에서 더 효율적이다.
한편 In-memory DBMS에서도 page가 압축되어 있다면 DRAM을 더 효율적으로 사용할 수 있고 cache의 hit rate도 높아져서 효율적이다. 하지만 compression ratio와 cpu overhead가 있기 때문에, 밸런스를 찾아야 한다.
만약에 데이터가 완전히 랜덤한 비트 시퀀스로 구성되어 있다면, 이를 효율적으로 압축할 수 있는 방법은 딱히 없다. 하지만 현실적으로는 attribute 안에서, 혹은 서로 다른 attribute 간에 높은 연관관계가 존재하기 때문에 압축은 흔히 효율적이다.
DB를 압축할 때에는 다음 세 가지를 고려해야 한다.
- fixed-length value: DBMS는 데이터를 offset을 통해 효율적으로 가져올 수 있어야 하고, 또한 CPU의 연산 부담을 줄이기 위해 Word-alignment (Word size, 64bit에서 흔히 8btye의 배수 단위로 메모리가 정렬되어 있는 것)을 지켜야 한다.
- late materialization: 최대한 lazy하게 압축을 풀어야 한다. 실제로 필요한 데이터가 식별된 이후에 압축을 풀어야 효율적이기 때문
- lossless: (당연히) 비손실 이어야 한다.
Compression Granularity
DB를 압축하기 전에, 어떤 단위의 데이터를 압축하는지를 결정해야 한다. 이는 tuple이 어떻게 저장되는지 (NMS? DMS?)에 따라 선택의 여지가 달라진다.
- Block Level: 한 taple의 tupe을 압축
- Tuple Level: 각 tuple의 전체 content를 압축 (NMS에서만 가능)
- Attribute Level: 한 tuple의 몇 attribute를 압축
- Columnar Level: 여러 tuple의 몇 attribute를 압축 (DMS에서만 가능)
Naive Compression
만약에 DBMS가 gzip, LZ4 등의 general purpose compression algorithm을 사용한다면 데이터에 접근할 때마다 압축을 풀어야 하므로, 큰 규모의 데이터를 한번에 압축하기 어려워진다.
MySQL의 InnoDB가 이런 식으로 작동하는데, disk page를 조각내서 압축한 다음, 1/2/4/8KB에 맞춰 padding을 추가해 저장한다. 그 다음 읽을 때 마다 압축을 푼다.
압축한 결과가 기존 데이터의 구조나 접근 방식을 전혀 반영하지 않기 때문에, late materialization에 대한 여지도 적다. 즉 우리가 원하는 것은 위 사진과 같이, 압축을 풀지 않은 상태에서 처리를 한 다음 마지막에 압축을 푸는 것인데, 이것이 불가능하다는 의미이다.
Columnar Compression
그러면 Columnar Compression은 이 문제를 어떻게 해결할까?
- Run-length Encoding: 각 column의 같은 값들을
(value, start_position, num_elements)triplet으로 압축한다. 이 때 효율적인 압축을 위해 먼저 sorting을 해야 한다.
- Bit-packing Encoding: 각 attribute의 max value에 따라 더 작은 data type을 사용한다.
- Mostly Encoding: Bit-packing과 비슷하게, 값이 largest size보다 큰 경우 별도의 lookup table을 만든다.
- Bitmap Encoding: 별도의 bitmap을 만들어 attribute의 가능한 unique value마다 해당 값이 있는지 없는지를 나타낸다. 이 때, attribute가 가질 수 있는 값의 개수 (cardinality)가 작아야 쓸모가 있다.
zip code의 cardinality가 43000이고, 이 정보를 포함하는 tuple이 1000만 개 있다고 가정하면, Bitmap Encoding을 사용하면 1000만 row 43000 bit ~== 53.75GB 가 드는 데 비해, plain 4Byte integer를 사용하면 1000만 row 4 Byte = 40MB가 든다.
- Delta Encoding: 값 자체를 저장하는 대신, 값의 차이만 저장하는 방식을 사용할 수 있다. RLE를 같이 사용하면 더 압축할 수 있음. 이 때 base value는 별도의 lookup table을 사용할 수도 있고, inline으로 저장할 수도 있다.
- Incremental Encoding: Delta Encoding의 한 종류로, 연속된 tuple 간의 common prefix/suffix를 중복하여 적지 않기 위해 prefix length를 같이 기입하는 방법이다. 특성상 sorted data에서 효율적이다.
- Dictionary Compression: DBMS에서 가장 널리 쓰이는 방식의 압축으로, variable length value를 integer identifier로 mapping하는 별도의 자료구조를 만든다. 약간 복잡한데, 빠른 encoding/decoding 연산과 함께 ragne query를 지원해야 한다. 이 때 모든 인풋에 대해 unique output을 보장하는 hash function이 없으므로 간단히 hash를 쓰는 것은 불가능하다. 또한, encoding 이전의 sorting과 이후의 sorting 방식이 같아야 압축된 상태의 쿼리 결과와 압축을 푼 상태의 쿼리 결과의 동일성을 보장할 수 있다.
