컬럼 인코딩

「바이너리 형식」으로 돌아가기

---

위까지가 값 하나를 어떻게 적느냐이고, 여기부터는 한 컬럼의 값들을 어떻게 적느냐입니다.

값마다 조밀하게 적어도 값 사이의 중복은 그대로 남습니다. 정적 기획 데이터에서는 그 중복이 파일의 대부분입니다.

같은 문자열이 수만 번 나오고, id는 1씩 증가하고, enum 컬럼은 유니크 값이 셋뿐입니다.

컬럼 지향 배치가 이미 같은 성질의 값을 한 블록에 모아 두었으므로, 인코딩은 그 블록 안에서만 닫히면 됩니다. 디스크립터의 encoding 바이트가 어느 배치인지 나타냅니다.

번호	이름	블록 배치	어느 원소에
0	RAW	위 「값 인코딩」 그대로	전부
1	VARINT	행마다 counter32 값	i32
2	DELTA	첫 값, 그다음 counter32 차이들	i32
3	RLE	counter32 런 길이 + counter32 값의 반복	i32, varint(enum), bool
4	DELTA_RLE	첫 값, 그다음 차이 스트림의 RLE	i32
5	DICT	counter32 사전 크기 + 사전 + 행마다 counter32 인덱스	string, i64, f32, f64
6	DICT_RLE	사전 + 인덱스 스트림의 RLE	string, i64, f32, f64
7	DICT_FRONT	정렬된 사전을 접두사 공유로 접음 + 인덱스	string
8	DICT_FRONT_RLE	접힌 사전 + 인덱스 스트림의 RLE	string
9	ARRAY	원소용 인코딩 + (가변이면) 길이용 인코딩 + 두 스트림	배열 (uuid 원소 제외)
10	WHOLE	정수 인코딩 하나 + 그 인코딩으로 담은 정수 스트림	f32, f64
11	DICT_SEG	조각 표 + 조각 참조로 조립하는 사전 + 인덱스	string
12	DICT_SEG_RLE	같은 사전 + 인덱스 스트림의 RLE	string
13	BITPACK	폭 + base + 내부 인코딩 + 그 폭으로 묶은 비트 스트림	bool, varint, i32, i64

사전은 원소로 매개변수화됩니다. 항목은 그 컬럼 원소의 RAW 형식 그대로입니다 — string은 길이

• UTF-8, f32는 fixed32, i64·f64는 fixed64. 그래서 인코딩 번호를 늘리지 않고 사전이 문자열 밖으로 나갑니다. 「실수는 압축이 안 된다」는 것은 값 하나를 볼 때의 이야기이고, 컬럼으로 보면 기획 데이터의 실수는 몇 개의 값이 반복됩니다 — 측정한 데이터셋의 f32 18,718개 중 유니크는 1,065개(5.7%)였고 0.0 하나가 2,450번이었습니다.

7·8번이 있는 이유는 기획 데이터의 문자열이 중복이 아니라 접두사를 공유하기 때문입니다. 02_CRI_DAMAGE_FLOAT 옆에 02_CRI_INT, N등급 근거리 0성급 옆에 N등급 근거리 10성급 — 서로 다른 값이라 사전은 전부 보관해야 하지만 앞부분이 계속 겹칩니다. 사전을 바이트 오름차순으로 정렬한 뒤 항목마다 「앞 항목과 공유하는 바이트 수 + 나머지」만 적으면, 실측에서 문자열 바이트의 62%가 사라집니다.

• 배열도 인코딩합니다. 예전에는 스칼라만 인코딩하고 배열은 항상 RAW였는데, 그 판단의 근거는 「배열이 실측에서 바이트의 1.8%」였습니다. 그 숫자는 형식의 성질이 아니라 시트의 성질이라서, 다른 데이터셋에서는 배열이 바이트의 60.3%입니다. 9번이 그 자리를 엽니다.
• uuid는 RAW입니다. 16바이트 항목은 아주 심하게 반복되지 않으면 사전이 손해이고, 그래서 uuid 배열도 9번의 후보가 되지 않습니다 — 원소에 적용될 인코딩이 없으면 얻는 것이 행 길이의 압축뿐입니다.
• 델타의 뺄셈과 복원의 덧셈은 32비트에서 순환합니다. int32 두 값의 차는 int32를 넘칠 수 있지만, 2의 보수에서 순환 연산은 모든 쌍을 정확히 왕복시킵니다. 64비트 정수가 기본인 언어는 더한 뒤 하위 32비트로 자르고 부호를 확장합니다.
• 사전 순서는 인코딩이 정합니다 — 5·6번은 첫 등장 순서(정렬 없이 한 번의 순회로 만들 수 있음), 7·8번은 바이트 오름차순(그래야 접두사가 겹침). 어느 쪽이든 런 구조는 같습니다: 어느 행끼리 값이 같은지는 사전의 번호 매김과 무관합니다.
• 리더는 표에 없는 (원소, 인코딩) 조합을 만나면 — string 컬럼에 DELTA, uuid 컬럼에 DICT 같은 — 필드 이름과 함께 멈춥니다. 모르는 번호도 같습니다. 모르는 컬럼은 여전히 advance(byteLength) 하나입니다: 인코딩을 몰라도 건너뛰기는 성립합니다.

9~12번 — 새로 더해진 넷

새 배치는 11번 하나이고, 나머지 셋은 조합입니다. 9·10번은 블록 헤더에 인코딩 바이트를 하나 더 적고 그 뒤의 스트림을 이미 있는 커서로 풀며, 12번은 11번의 사전에 RLE 인덱스를 붙인 것입니다. 그래서 디코드 단계가 어디에도 늘지 않고, 그 인코딩 바이트도 길이 스트림도 전부 컬럼 블록 안이라 건너뛰기는 여전히 advance(byteLength) 한 번입니다.

9 — ARRAY. 배열 블록이 원소용 인코딩 하나와, 행마다 길이가 다르면 길이용 인코딩 하나를 지목합니다.

fixed8    elementEncoding
fixed8    lengthEncoding          가변 배열일 때만
[길이 스트림]                      가변 배열일 때만. rowCount개
[원소 스트림]                      totalElements개

• elementEncoding으로 올 수 있는 것은 그 원소 타입의 스칼라 컬럼에 올 수 있는 것과 같습니다. 문자열 배열은 사전까지, 실수 배열은 10번까지 닿습니다.
• 길이는 varint 값들이므로 lengthEncoding은 varint 컬럼에 허용되는 것 — RAW 또는 RLE — 입니다. 행마다 길이가 같은 컬럼이 대다수이고, 그것은 런 하나가 됩니다.
• 리더는 길이를 전부 먼저 풀고 그 자리에서 원소 커서를 만듭니다. 그래서 원소 스트림의 시작 위치가 저절로 맞습니다.

10 — WHOLE. f32·f64 컬럼의 값이 전부 정수이면 int32로 싣고, 그 정수 스트림에 정수 인코딩(VARINT·DELTA·RLE·DELTA_RLE 중 하나)을 겁니다. 스프레드시트에는 수 종류가 하나뿐이라 개수·등급·식별자가 부동소수점으로 도착해 값마다 8바이트를 쓰는데, 정수로 적으면 1씩 증가하는 컬럼이 런이 됩니다.

판정은 「소수부가 없다」가 아닙니다. 정수로 바꿔 다시 쓴 바이트가 RAW 블록이 담았을 바이트와 같아야 합니다 — 음의 0(비트 패턴이 다릅니다), f32가 정확히 담지 못하는 큰 정수, NaN·무한대가 이 검사에서 걸립니다. 가정하지 않고 재는 이유는 그 실패가 드러나지 않기 때문입니다.

11·12 — DICT_SEG · DICT_SEG_RLE. 사전 항목을, 항목들이 공유하는 조각 표에 대한 참조 목록으로 싣습니다.

counter32 segmentCount
segmentCount ×:                   바이트 오름차순, front coding
  counter32 shared
  counter32 restLength
  restLength 바이트
counter32 dictCount
dictCount ×:
  counter32 pieceCount
  pieceCount ×: counter32 segmentIndex
[인덱스 스트림]                     rowCount개. 11은 평문, 12는 RLE

7번과 8번의 front coding이 접을 수 있는 것은 이웃한 두 항목이 앞에서 공유하는 부분뿐입니다.

조각으로 조립된 값은 가운데와 끝에서도 같은 조각을 반복합니다. 경로, 단어로 만든 이름, 구획이 있는 식별자가 그렇습니다.

front coding은 그 부분을 항목마다 다시 적습니다.

조각은 탐색으로 찾지 않고 값의 성격이 바뀌는 자리에서 자릅니다.

구분자(_ - / . \ : (공백) |) 다음, 그리고 숫자와 글자가 만나는 자리입니다. 결정적이고 한 번의 순회로 끝납니다.

자를 자리를 ASCII에서만 보므로 멀티바이트 문자가 조각 경계에서 쪼개지는 일은 없습니다.

11·12번이 7·8번을 대체하지 않습니다. 계층적인 값에서는 front coding이 여전히 더 작습니다. 둘 다 후보로 내고 재는 것이 처음부터 이 형식의 선택 방식입니다.

고르는 방법: 전부 해보고 가장 작은 것

변환기는 통계로 추측하지 않습니다. 적용 가능한 인코딩을 전부 인코딩해 보고 가장 작은 것을 고릅니다. 크기가 같으면 낮은 번호를 고릅니다.

인코딩 시간은 이 형식이 신경 쓰지 않는 유일한 자원이고(읽는 쪽만 빠르면 됩니다), 실제로 측정한 바이트 수는 틀리는 법이 없는 유일한 선택 기준입니다. 선택이 결정적이므로 같은 입력은 같은 바이트를 내고, 골든 트리와 형식 고정 테스트가 그 성질에 기댑니다.

읽는 쪽: 컬럼 커서

생성된 테이블 리더의 행 루프는 그대로 행 루프이고, 값을 꺼내는 자리만 커서를 거칩니다. 델타가 어떻게 누적되는지, 런이 얼마나 남았는지, 사전 인덱스가 무엇을 가리키는지 아는 곳은 언어마다 그 커서 하나입니다.

사전 인코딩은 파일 크기와 별개의 이득을 하나 더 줍니다. 문자열 객체가 유니크 개수만큼만 생깁니다.

유니크 값 3개짜리 컬럼이 103,395행이면 문자열 셋을 만들고 행마다 그 참조를 나눠 줍니다. 그래서 줄어드는 것이 로드 비용만이 아니라 상주 메모리입니다.

접두사로 접힌 사전도 커서가 열릴 때 온전한 문자열로 펴집니다. 접은 것은 디스크의 바이트였지 행이 받는 값이 아닙니다.

고정폭 원소의 사전은 항목을 바이트 그대로 들고 있다가 행이 요청할 때 값으로 만듭니다. 실수의 비트 패턴이 RAW로 읽었을 때와 정확히 같아야 하기 때문이고, 그래서 NaN도 음의 0도 왕복합니다.