564. 컬럼 기반 스토리지 런 렝스 인코딩(RLE) 압축

⚠️ 이 문서는 데이터 웨어하우스(OLAP)에서 압도적인 디스크 I/O 감소를 위해 사용되는 컬럼 지향 저장소(Columnar Storage) 포맷이 어떻게 '런 렝스 인코딩(Run-Length Encoding, RLE)' 등의 압축 알고리즘과 찰떡궁합을 이루어 디스크 공간을 기하급수적으로 절약하고 쿼리 속도를 가속하는지 다룹니다.

핵심 인사이트 (3줄 요약)

  1. 본질: 데이터를 로우(행) 단위로 저장하는 RDBMS와 달리, 컬럼 단위로 저장하면 '동일한 데이터 타입과 값이 연속해서 나타날 확률'이 극도로 높아진다.
  2. 가치: "M, M, M, F, F, M" 처럼 반복되는 성별 데이터를 "M 3개, F 2개, M 1개" 식으로 숫자로 압축해 버려 스토리지 비용을 수십 분의 일로 줄이고, 디스크에서 메모리로 퍼 올리는 I/O 병목을 제거한다.
  3. 기술 체계: 정렬(Sorting)이 선행될 때 RLE의 파괴력이 극대화되며, 딕셔너리 인코딩(Dictionary Encoding), 델타 인코딩(Delta Encoding) 등 데이터의 성격(문자열, 숫자 증감 등)에 따라 최적의 압축 기법을 섞어 쓴다.

Ⅰ. 행(Row) 저장의 압축 불가와 컬럼(Column) 저장의 기적

데이터의 생김새(패턴)가 달라지면 압축률이 천양지차로 달라진다.

  1. Row 저장소의 혼돈 (압축의 어려움):
    • 일반적인 RDBMS 블록에는 [홍길동, 30세, 서울, 남성, 5만원] 다음에 [김영희, 25세, 부산, 여성, 8만원]이 이어진다.
    • 글자, 숫자, 다른 글자, 기호가 무작위로 섞여 있어(Entropy가 높음), 아무리 훌륭한 압축 알고리즘(Zip 등)을 돌려도 패턴을 찾기 어려워 압축이 거의 되지 않는다.
  2. Column 저장소의 질서 (패턴의 등장):
    • 성별 컬럼만 따로 떼어서 디스크 블록에 저장하면 [남성, 여성, 여성, 남성, 남성, 남성, 여성] 처럼 똑같은 도메인의 값들만 연속으로 저장된다.
    • 나이 컬럼은 숫자만, 주소 컬럼은 문자열만 깔끔하게 모이게 되며, 이는 압축 알고리즘이 환호성을 지를 만큼 완벽하게 '예측 가능하고 반복적인' 패턴 덩어리가 된다.

📢 섹션 요약 비유: 과일 바구니에 사과, 배, 포도를 마구 섞어 담아놓으면(Row 저장) 과일 상자에 이름을 붙여 분류하기가 애매합니다. 하지만 사과는 사과 상자에, 포도는 포도 상자에 따로 분리해 두면(Column 저장), 상자 겉면에 그냥 "사과 100개"라고 짧게 적어버리는 것(압축)만으로도 재고 정리가 완벽하게 끝나는 마법입니다.

Ⅱ. 런 렝스 인코딩 (RLE, Run-Length Encoding)

가장 단순하지만, 컬럼 스토리지에서는 가히 폭발적인 성능을 내는 핵심 알고리즘이다.

  1. RLE의 원리:
    • 연속해서 나타나는 똑같은 값(Run)을, '그 값'과 '연속된 횟수(Length)'의 쌍으로 치환하는 방식이다.
    • 원본 데이터: [서울, 서울, 서울, 서울, 부산, 대구, 대구, 대구] (8건)
    • RLE 압축: [(서울, 4), (부산, 1), (대구, 3)] (3건으로 압축)
  2. 정렬(Sorting)과의 시너지:
    • 만약 데이터가 [서울, 부산, 서울, 대구, 서울, 대구]처럼 뒤죽박죽이면 RLE를 해봐야 [(서울,1), (부산,1)...] 식으로 압축 효과가 전혀 없다.
    • 따라서 데이터 웨어하우스(Redshift, Vertica 등)에서는 데이터를 디스크에 쓰기 전에 카디널리티(Cardinality, 중복도가 높은)가 낮은 컬럼을 기준으로 먼저 **정렬(Sort)**을 수행한다. 정렬된 데이터에 RLE를 먹이면 10GB짜리 로그 파일이 100MB로 줄어드는 기적이 일어난다.
  3. 압축된 상태에서의 연산 (Late Materialization):
    • RLE의 진정한 무서움은 압축을 풀지 않고도 연산이 가능하다는 점이다. "서울 사람 몇 명이야?"라는 COUNT 쿼리가 들어왔을 때, 데이터를 메모리에서 굳이 압축 해제(Decompression)할 필요 없이 (서울, 4)라는 압축 메타데이터의 '4'만 가져와 더해버리면 CPU 연산 속도가 수백 배 빨라진다.

📢 섹션 요약 비유: 공책에 "아아아아아아아아"라고 100글자를 쓰는 대신, "아 $\times$ 100"이라고 짧게 적는 것이 RLE입니다. 나중에 글자가 몇 개인지 셀 때도, 100개의 글자를 일일이 손가락으로 세는 게 아니라 겉에 적힌 "100"이라는 숫자만 딱 보고 즉시 정답을 외치는(압축 상태 연산) 천재적인 계산법입니다.

Ⅲ. 다른 컬럼 압축 기법들의 조합 (Dictionary & Delta)

데이터의 성격에 따라 RLE가 통하지 않을 땐 다른 무기를 꺼낸다.

  1. 딕셔너리 인코딩 (Dictionary Encoding):
    • 과일 이름처럼 문자열이 길 때 사용한다.
    • [사과, 바나나, 사과, 오렌지]를 저장할 때, 맨 앞에 사전(0=사과, 1=바나나, 2=오렌지)을 하나 만들어두고, 실제 데이터 블록에는 [0, 1, 0, 2]라는 아주 작은 정수(Integer) 번호표만 저장한다. 길고 무거운 텍스트(String) 디스크 I/O를 정수형 I/O로 탈바꿈시킨다.
  2. 델타 인코딩 (Delta Encoding):
    • 타임스탬프(시간)나 로그의 ID처럼 1씩 계속 증가하는 데이터에 쓴다.
    • [10001, 10002, 10003, 10005]를 저장할 때, 첫 번째 기준값 10001만 저장하고 그다음부터는 이전 값과의 차이(Delta)인 [+1, +1, +2]처럼 아주 작은 1바이트 숫자만 저장하여 용량을 극한으로 아낀다.

📢 섹션 요약 비유: 긴 단어를 통째로 쓰는 게 팔 아파서, 책 맨 앞장에 '해리포터=1, 헤르미온느=2'라고 암호표를 만들어두고 본문에는 숫자만 적는 것이 '딕셔너리 인코딩'입니다. 그리고 연도를 적을 때 "1998년, 1999년, 2000년"이라 안 적고 기준점 '1998년'을 적은 뒤 "+1년, +2년"이라고 짧게 차이만 적어내는 꼼수가 '델타 인코딩'입니다.