Bloom filter 글 1장의 user_id는 정렬되지 않은 탓에 Row Group마다 min과 max가 전체 범위를 덮었고, 통계가 있어도 하나도 건너뛰지 못했습니다. 그 글에서는 점 조회만 Bloom filter로 막고 범위 조회는 다음으로 미뤘습니다. 이번 글이 그 나머지이고, 정렬 키가 하나일 때와 둘일 때, 그리고 두 컬럼을 같이 다루려고 나온 Z-order와 Hilbert curve를 차례로 봅니다.
1. 정렬과 min/max 통계
1-1. 정렬 전후 비교
행 16개를 파일 4개에 4행씩 나눠 담는다고 가정해 보겠습니다. 컬럼은 a와 b 두 개이고 값은 각각 0~3입니다. 들어온 순서대로 담으면 파일마다 값이 섞입니다.
들어온 순서대로 저장
파일 1: a 0~3 b 0~3
파일 2: a 0~3 b 0~3
파일 3: a 0~3 b 0~3
파일 4: a 0~3 b 0~3
WHERE a = 1 → 네 파일 모두 범위 안 → 4개 다 읽음min/max 통계는 각 파일에 어떤 값의 범위가 들어 있는지만 기록합니다. 파일마다 범위가 0~3이면 어떤 조건이 와도 통계로는 아무것도 걸러지지 않습니다. 통계를 만드는 비용은 냈는데 건너뛰는 파일은 없는 상태입니다.
a로 정렬해서 담으면 결과가 달라집니다.
a로 정렬 후 저장
파일 1: a 0
파일 2: a 1
파일 3: a 2
파일 4: a 3
WHERE a = 1 → 파일 2만 읽음데이터도 통계도 같은데 읽는 파일이 4개에서 1개로 줄었습니다.
1-2. 통계 단위
이 글에서는 "파일"이라고 부르겠지만, 통계가 붙는 단위는 포맷마다 다릅니다. Parquet은 Row Group마다 컬럼별 min/max를 두고, 선택 기능인 page index(ColumnIndex, OffsetIndex)를 쓰면 페이지 단위로도 min/max를 둡니다. Delta Lake는 트랜잭션 로그에 파일마다 통계를 기록하는데, 기본으로 처음 32개 컬럼만 통계를 모읍니다. 단위가 작을수록 더 촘촘하게 건너뛸 수 있지만, 원리는 같습니다. 정렬되지 않은 데이터에서는 어느 단위든 범위가 넓어집니다.
2. 다중 컬럼 정렬
2-1. 사전순 정렬의 한계
이번에는 a, b 순서로 정렬해 보겠습니다. ORDER BY a, b와 같습니다.
(a, b) 순으로 정렬 후 저장
파일 1: a 0 b 0~3
파일 2: a 1 b 0~3
파일 3: a 2 b 0~3
파일 4: a 3 b 0~3
WHERE a = 1 → 파일 2만 읽음
WHERE b = 1 → 네 파일 모두 범위 안 → 4개 다 읽음b는 a 값이 같은 구간 안에서만 정렬됩니다. 파일 경계가 a 값을 따라 잘리니 파일마다 b는 0부터 3까지 다 들어갑니다.
BigQuery 5편에서 클러스터링 컬럼은 왼쪽이 가장 강하게 정렬되고 오른쪽으로 갈수록 약해진다고 썼습니다. 그 이유가 이 구조입니다. 사전순 정렬에서 둘째 컬럼은 첫 컬럼이 같은 행들 사이에서만 의미가 있고, 첫 컬럼의 카디널리티가 높을수록 그 구간은 짧아집니다.
2-2. 컬럼 순서 바꾸기
b, a 순으로 바꾸면 이번에는 b로는 1개, a로는 4개를 읽습니다. 쿼리가 두 컬럼을 번갈아 거른다면 어느 쪽을 앞에 둬도 한쪽은 손해를 봅니다. 필요한 것은 두 컬럼을 같은 무게로 다루는 순서이고, Z-order가 그 순서를 만드는 한 가지 방법입니다.
3. Z-order
3-1. 비트 인터리빙
Z-order는 여러 컬럼 값의 비트를 한 자리씩 번갈아 이어 붙여서 하나의 숫자(Z값)를 만들고, 그 숫자로 정렬합니다. 1966년 IBM의 G. M. Morton이 지리 데이터베이스 파일 순서용으로 제안해서 Morton order라고도 부릅니다.
이 글에서는 각 자리에서 a의 비트를 b보다 앞에 둡니다. 어느 컬럼을 앞에 두느냐는 규약이라 구현마다 다르고, 규약이 바뀌면 Z값도 바뀝니다.
a = 2 → 10
b = 3 → 11
자리별로 a, b 순서로 번갈아:
윗자리: a=1, b=1 → 11
아랫자리: a=0, b=1 → 01
Z값 = 1101 = 130~3 격자 전체의 Z값은 이렇습니다.
a=0 a=1 a=2 a=3
b=0 0 2 8 10
b=1 1 3 9 11
b=2 4 6 12 14
b=3 5 7 13 150, 1, 2, 3을 따라가면 왼쪽 위 2×2 칸을 Z자로 돌고, 4부터 7까지는 그 아래 2×2 칸, 8부터 11까지는 오른쪽 위, 12부터 15까지는 오른쪽 아래를 돕니다. 큰 Z 안에 작은 Z가 들어 있는 모양이라 이 이름이 붙었습니다.
3-2. 파일별 범위 비교
이 Z값 순서대로 4행씩 끊어 파일에 담으면 이렇게 됩니다.
Z-order로 정렬 후 저장
파일 1 (Z 0~3): a 0~1 b 0~1
파일 2 (Z 4~7): a 0~1 b 2~3
파일 3 (Z 8~11): a 2~3 b 0~1
파일 4 (Z 12~15): a 2~3 b 2~3이 예시는 값이 격자에 고르게 한 행씩 들어 있어서 파일이 정확히 사분면으로 떨어집니다. 실제 데이터에서는 값마다 행 수가 다르고 파일 경계도 고르지 않아서, 숫자가 이렇게 깨끗하게 나오지는 않습니다.
Z-order는 a만 거르는 쿼리에서 단순 정렬보다 손해를 봅니다. 그 대가로 b로 걸러도 똑같이 절반을 건너뜁니다. 쿼리가 늘 같은 컬럼 하나로만 거른다면 Z-order를 쓸 이유가 없습니다.
3-3. 점프 구간과 컬럼 수
Z값이 이웃한 두 칸이 격자에서도 늘 이웃한 것은 아닙니다. 위 격자에서 Z값 7은 (a=1, b=3)이고 8은 (a=2, b=0)입니다. 순서로는 바로 옆인데 격자에서는 반대편 끝입니다. 파일 경계가 이런 점프 지점 근처에 걸리면 한 파일 안에 멀리 떨어진 값이 같이 들어가고, 그 파일의 min/max 범위가 넓어집니다.
컬럼을 늘릴수록 이 손해가 커집니다. 컬럼 하나에 돌아가는 비트 자리가 줄고, 각 컬럼이 덜 촘촘하게 정렬됩니다. Delta Lake도 Z-order 컬럼이 하나 늘 때마다 지역성의 효과가 떨어진다고 밝힙니다.
3-4. 치우친 분포 처리
원래 값의 비트를 그대로 섞으면 값 분포가 치우쳤을 때 문제가 생깁니다. a가 0부터 1,000,000까지인데 대부분이 100 이하에 몰려 있다면, 윗자리 비트는 거의 모든 행에서 0이라 정렬에 기여하지 못합니다.
Delta Lake는 이 문제를 피하려고 값을 그대로 쓰지 않습니다. 소스 코드를 보면 각 컬럼을 먼저 range_partition_id로 바꾸는데, 이 함수는 값을 대략적인 순위 구간 번호로 바꿉니다. 소스 주석의 예시대로 (0, 1, 3, 15, 36, 99)를 구간 3개로 나누면 (0, 0, 1, 1, 2, 2)가 됩니다. 값의 크기가 아니라 순위를 섞기 때문에 분포가 치우쳐도 각 컬럼이 비트를 고르게 씁니다.
Iceberg의 Z-order 재작성은 방식이 다릅니다. 정수 같은 고정폭 타입은 순서를 보존하는 8바이트 표현으로 바꿔 그대로 섞습니다. 순위가 아니라 원래 값에 가까운 표현을 쓰기 때문에 Delta보다 분포의 영향을 더 받습니다. 문자열 같은 가변 길이 값은 앞에서부터 잘라 기본 8바이트(var-length-contribution)만 씁니다. https://가 정확히 8바이트라서, URL 컬럼을 Z-order에 넣으면 https로 시작하는 값은 Z값에서 서로 구별되지 않습니다. 접두어가 고정된 문자열 컬럼은 Iceberg Z-order로는 정렬 효과를 거의 내지 못하고, 더 많은 바이트를 쓰려면 var-length-contribution을 늘려야 합니다.
4. Hilbert curve
4-1. Z-order와의 차이
3-3절의 점프를 줄이려고 쓰는 것이 Hilbert curve입니다. Hilbert curve는 격자를 한 붓 그리기로 도는데, 순서상 이웃한 두 칸이 격자에서도 항상 맞닿아 있습니다. Z-order처럼 반대편 끝으로 건너뛰는 구간이 없으니, 파일 경계가 어디에 걸리든 한 파일이 멀리 떨어진 칸들을 같이 묶는 일이 줄어듭니다. 대신 Z값처럼 비트를 섞기만 해서는 계산되지 않고, 회전과 반전을 섞은 계산이 필요합니다.
4-2. Delta와 Iceberg의 Hilbert 지원
Delta Lake 오픈소스 코드에서 OPTIMIZE ... ZORDER BY 경로는 곡선 이름이 zorder이고, liquid clustering 경로는 hilbert입니다. 클러스터링 컬럼이 하나뿐이면 Hilbert 대신 Z-order 경로를 타고, Hilbert 인덱스는 컬럼 9개까지만 계산합니다(MultiDimClusteringFunctions.scala의 hilbert_index 제약). 다만 Delta 오픈소스 문서에는 liquid clustering이 Hilbert curve를 쓴다는 설명이 없고, 이 내용은 소스 코드 기준입니다.
Iceberg도 1.12.0에서 Spark 4.1용 rewrite_data_files에 Hilbert curve 전략을 추가했습니다. hilbert(c1, c2) 형태로 쓰고, 같은 작업에서 zorder와 섞어 쓸 수는 없습니다.
5. 엔진별 구현
5-1. Delta Lake: ZORDER BY에서 liquid clustering으로
오픈소스 Delta Lake는 2.0.0에서 OPTIMIZE ... ZORDER BY를 지원했습니다.
OPTIMIZE events ZORDER BY (user_id, event_type);Delta는 Z-order가 멱등(idempotent)하지 않다고 명시합니다. 실행할 때마다 이미 Z-order를 마친 파일까지 포함해 파티션 전체를 다시 클러스터링하므로, 새 데이터가 조금 들어왔어도 다시 돌리면 비용이 큽니다.
이 비용을 줄이려고 나온 것이 liquid clustering입니다. Delta 3.1.0에서 preview로 들어왔고 3.2에서 GA가 됐습니다.
CREATE TABLE events (user_id STRING, event_type STRING, ...)
USING DELTA
CLUSTER BY (user_id, event_type);liquid clustering은 증분(incremental) 방식이라 필요한 데이터만 다시 씁니다. 제약도 있습니다. 클러스터링 컬럼은 4개까지이고, 파티셔닝이나 ZORDER와 같이 쓸 수 없습니다. 여기까지가 오픈소스 Delta Lake 기준입니다. Databricks는 버전 체계가 따로 있고, Databricks Runtime 15.4 LTS부터 liquid clustering이 GA입니다. Databricks는 스트리밍 테이블과 materialized view를 포함해 모든 새 테이블에 liquid clustering을 권장합니다.
5-2. Iceberg: sort order와 재작성
Iceberg는 테이블에 정렬 순서(sort order)를 선언해 둘 수 있습니다.
ALTER TABLE prod.db.events WRITE ORDERED BY event_type, user_id;이 선언은 Spark의 MERGE INTO처럼 일부 엔진이 쓸 때 데이터를 자동으로 정렬하는 데 쓰입니다. 쓰기 분배 방식(write.distribution-mode)도 여기에 맞물립니다. Iceberg 1.2.0부터 Spark의 기본값은 hash이고, sort order가 있는 테이블은 range가 기본입니다. 1.2.0 이전에는 none이 기본값이었습니다.
이미 쌓인 파일은 rewrite_data_files 프로시저로 다시 씁니다. 0.14.0부터 zorder 전략이 들어갔습니다.
CALL catalog_name.system.rewrite_data_files(
table => 'db.events',
strategy => 'sort',
sort_order => 'zorder(user_id, event_type)'
);5-3. 다른 엔진들
BigQuery는 클러스터링 컬럼을 4개까지 받고, 백그라운드에서 자동으로 재클러스터링합니다. BigQuery 5편에서 다룬 내용이라 여기서는 넘어갑니다.
Snowflake는 micro-partition(압축 전 50~500MB) 단위로 컬럼별 값 범위를 기록하고, micro-partition끼리 범위가 얼마나 겹치는지를 clustering depth로 보여 줍니다. 겹침이 적을수록 depth가 1에 가깝고 건너뛸 수 있는 파티션이 많습니다. Snowflake는 clustering key 컬럼을 3개나 4개까지만 두라고 권합니다.
ClickHouse는 테이블의 ORDER BY가 곧 정렬 순서이고, 기본 8192행(granule)마다 인덱스 항목(mark)을 하나씩 둡니다. ORDER BY (a, b) 테이블에서 b만 거르면, 2-1절과 같은 이유로 a의 카디널리티가 높을수록 건너뛰는 granule이 줄어듭니다.
6. 정렬 유지 비용
6-1. 새 데이터와 재정렬
정렬은 한 번 해 두면 끝나는 작업이 아닙니다. 새로 들어오는 파일은 기존 정렬과 상관없이 쓰이고, 그 파일들의 min/max는 다시 넓은 범위를 덮습니다. Snowflake도 매우 큰 테이블에 DML이 쌓이면 시간이 지나면서 클러스터링이 최적이 아니게 된다고 경고합니다. BigQuery의 자동 재클러스터링, Delta의 OPTIMIZE, Iceberg의 rewrite_data_files가 모두 이 문제를 푸는 작업이고, 셋 다 이미 쓴 파일을 다시 읽고 다시 씁니다. 증분 방식인 liquid clustering도 범위를 필요한 파일로 좁혀서 다시 씁니다.
6-2. 컬럼 수와 카디널리티
Z-order나 클러스터링 컬럼은 자주 거르는 컬럼이어야 하고, 개수는 적을수록 각 컬럼에 돌아가는 효과가 큽니다. Delta liquid clustering과 BigQuery는 4개로 제한하고, Snowflake는 3~4개를 권합니다. Snowflake는 그보다 많으면 성능 이득보다 유지 비용이 커진다는 점을 이유로 들고, Z-order라면 3-3절에서 본 것처럼 컬럼이 늘수록 지역성까지 떨어집니다.
카디널리티는 엔진마다 권고가 다릅니다. Delta는 자주 거르면서 카디널리티가 높은 컬럼에 ZORDER BY를 쓰라고 하고, Snowflake는 카디널리티가 너무 낮은 컬럼과 너무 높은 컬럼을 모두 경계합니다. 카디널리티가 아주 낮은 컬럼은 정렬하지 않으면 1-1절처럼 모든 값이 모든 파일에 퍼지고, 정렬해도 값 하나가 파일 여러 개를 차지해서 건너뛰는 이득이 작습니다. 이런 컬럼은 파티셔닝이 더 맞을 수 있습니다.
마무리
16행 예시로 돌아가면, a 하나로만 거르는 테이블에서는 단순 정렬이 파일 1개로 가장 적게 읽었고, a와 b를 번갈아 거르는 테이블에서는 Z-order가 2개씩으로 손해를 나눴습니다. 그 2개는 컬럼이 늘어도 늘고, 새 데이터가 쌓여도 늘어납니다. 그래서 Z-order나 liquid clustering을 쓰는 테이블은 정렬 컬럼을 고를 때 OPTIMIZE나 rewrite_data_files를 얼마나 자주 돌릴지도 같이 정하게 됩니다.
다음 글에서는 저장 구조에서 잠깐 벗어나 MVCC와 스냅샷 격리를 알아보겠습니다. 읽는 쪽과 쓰는 쪽이 서로를 막지 않으려고 데이터베이스가 행의 여러 버전을 어떻게 들고 있는지, 그리고 Iceberg 스냅샷과는 무엇이 같고 다른지까지 뜯어보겠습니다.