4. Records Organization — Sorter
01. Pattern Overview
데이터를 특정 컬럼 기준으로 정렬하여 저장함으로써, 쿼리 시 불필요한 데이터 블록을 건너뛸 수 있게 하는 패턴
- 데이터가 정렬되어 있으면 각 파일/블록의 min/max 메타데이터가 좁은 범위를 가지게 됨
- 쿼리 엔진이 이 메타데이터를 보고 해당 범위에 해당하지 않는 블록을 통째로 스킵
# 정렬되지 않은 경우File A: visit_time 범위 [2022-05-01 ~ 2024-05-01] ← 범위가 넓어 대부분 쿼리에 걸림File B: visit_time 범위 [2023-05-01 ~ 2024-05-01] ← 마찬가지
# 정렬된 경우File A: visit_time 범위 [2022-05-01 ~ 2023-05-01] ← 2024년 쿼리 시 스킵 가능File B: visit_time 범위 [2023-05-01 ~ 2024-05-01] ← 2022년 쿼리 시 스킵 가능02. Lexicographical Sort vs Z-order
Lexicographical Sort (사전순 정렬): 가장 기본적인 정렬. 첫 번째 컬럼으로 완전히 정렬, 같은 값 내에서 두 번째 컬럼으로 정렬
- 복합 정렬 키에서 첫 번째 컬럼을 건너뛰면 최적화가 되지 않음
# sort key = (visit_time, page)
visit_time page id2024-05-01T10:00 home.html 1 ← visit_time + page 둘 다 조건 → 효율적2024-05-01T10:03 about.html 22023-05-01T01:00 home.html 3 ← page만 조건 → visit_time이 먼저라 전체 스캔2023-05-01T04:00 about.html 42022-05-01T04:00 home.html 5WHERE visit_time = '2024-05-01' AND page = 'home.html' → 효율적 (id=1만 읽음)
WHERE page = 'home.html' → 비효율적 (id 1,3,5 모두 흩어져 있어 전체 스캔)
- Z-order: 이 문제를 해결하는 곡선 정렬(curved sort) 방식.
여러 컬럼을 동시에 고려하여 다차원 공간에서 가까운 값들을 같은 데이터 블록에 배치
Lexicographical: X 기준으로 완전 정렬 → X 없이 Y만 조회하면 무용지물Z-order: X와 Y를 동시에 고려 → X만 조회해도, Y만 조회해도 어느 정도 스킵 가능언제 어떤 정렬을 쓰는가
Lexicographical: 쿼리가 항상 첫 번째 정렬 키를 포함할 때. 예를 들어 event_time이 거의 모든 쿼리의 필터 조건일 때 최적.
Z-order: 여러 컬럼이 독립적으로 필터 조건에 사용될 때. 예를 들어 어떤 쿼리는 visit_id로, 다른 쿼리는 page로 필터링할 때.
03. Consequences
Unsorted Segments: 새로 쓰인 데이터는 아직 정렬되지 않은 상태. 정렬 최적화를 누리려면 쓰기 작업에 정렬을 포함하거나, 별도 정렬 작업을 스케줄링해야 한다. 쓰기 시 정렬하면 쓰기 성능이 저하된다. -> 핵심 트레이드오프
Composite Sort Keys: lexicographical 정렬에서 첫 번째 키를 건너뛰는 쿼리는 최적화가 안됨. 쿼리 패턴을 분석하여 가장 자주 쓰는 필터 컬럼을 첫 번째 키로 설정
Mutability: 정렬 키 변경은 가능하지만, 전체 테이블 재정렬이 필요할 수 있어 비용이 크다.
1: Delta Lake Z-order Compaction
from delta.tables import DeltaTablefrom pyspark.sql import SparkSession
spark = SparkSession.builder.getOrCreate()
# 먼저 데이터를 일반적으로 저장input_data = spark.read.schema("visit_id STRING, page STRING, event_time TIMESTAMP") \ .json("/data/visits")input_data.write.format("delta").save("/output/visits_sorted")
# Z-order 정렬 적용 (기존 데이터 파일을 재조직)table = DeltaTable.forPath(spark, "/output/visits_sorted")table.optimize().executeZOrderBy(["visit_id", "page"])executeZOrderBy는 기존 데이터 파일을 읽어서 Z-order 기준으로 재배치한 새 파일을 생성.
이는 사실상 compaction + sorting이 결합된 작업. 기존 파일은 남아있으므로 이후 VACUUM으로 정리
2: Spark orderBy로 Lexicographical Sort
# 쓰기 시 정렬 적용( input_data .orderBy("event_time", "page") # 전역 정렬 .write.format("parquet") .save("/output/visits_lexi_sorted"))
# sortWithinPartitions: 파티션 내에서만 정렬 (전역 shuffle 없음, 더 가벼움)( input_data .sortWithinPartitions("event_time", "page") .write.format("parquet") .save("/output/visits_local_sorted"))orderBy는 전체 데이터에 대한 global sort이므로 shuffle이 발생해 비용이 큰 작업,sortWithinPartitions는 각 Spark 파티션 내에서만 정렬하므로 shuffle 없이 가볍지만, 파티션 간 정렬은 보장되지 않는다. 대부분의 경우sortWithinPartitions로 충분하다. 각 파일 내부만 정렬되어 있어도 메타데이터 min/max 범위가 좁아지기 때문이다.
BigQuery Clustered Table
-- BigQuery에서 clustered table = Sorter 패턴CREATE TABLE `dedp.visits.raw_visits`PARTITION BY DATE(event_time) -- 1차: 수평 파티셔닝CLUSTER BY visit_id, page -- 2차: 정렬 (Sorter)AS SELECT * FROM source_table;BigQuery의 CLUSTER BY는 lexicographical sort다. 파티셔닝과 결합하면 파티션 pruning 후 정렬 기반 블록 스킵까지 적용되어 이중 최적화가 가능
Concept
- Sorter : 데이터를 특정 컬럼 기준으로 정렬 저장하여, 메타데이터(min/max) 기반 데이터 블록 스킵을 가능하게 하는 패턴
- Lexicographical Sort : 사전순 정렬. 첫 번째 키로 완전 정렬 후 같은 값 내에서 두 번째 키 정렬. 첫 번째 키가 쿼리에 포함되어야 효과적
- Z-order : 다차원 곡선 정렬. 여러 컬럼을 동시에 고려하여 어느 컬럼으로 필터링해도 블록 스킵 가능
- Data Skipping : 정렬된 데이터의 min/max 메타데이터를 확인하여 불필요한 블록을 읽지 않는 최적화
- Unsorted Segments : 새로 쓰인 데이터 중 아직 정렬되지 않은 블록. 별도 정렬/compaction 작업 필요
- Composite Sort Key : 여러 컬럼으로 구성된 정렬 키. lexicographical 정렬에서 선행 컬럼 없이 후행 컬럼만 조회하면 최적화 불가
- orderBy vs sortWithinPartitions : 전역 정렬(shuffle 발생) vs 파티션 내 로컬 정렬(shuffle 없음)
- Clustered Table : BigQuery, Snowflake에서 정렬 기반 데이터 조직을 구현하는 테이블 유형