읽지 않는 것이 가장 빠르다 (Pruning in Snowflake, SIGMOD 2025)

출처

참고 이 페이지는 원문 번역이 아니라 한국어 해설이에요. 정확한 표현과 수치는 원문을 확인하세요.

한눈에

• 저장과 컴퓨트가 분리된 구조에서는 파티션 하나를 읽지 않으면 계산뿐 아니라 네트워크 I/O 까지 아낍니다. 그래서 프루닝은 Snowflake 성능의 핵심입니다.
• 필터 프루닝 외에 LIMIT 프루닝, top-k 프루닝, 조인 프루닝 세 가지를 설명하고, 이 가운데 LIMIT 프루닝 방법과 검색 엔진식 top-k 프루닝의 SQL 엔진 적용을 새로 제안합니다.
• 운영 데이터에서 Snowflake 는 전체 쿼리에 걸쳐 마이크로 파티션의 99.4% 를 걸러 냈습니다.
• 반면 TPC-H 에서는 평균 프루닝 비율이 28.7% 에 그쳐, 합성 벤치마크가 실제 업무의 프루닝 효과를 크게 놓친다고 지적합니다.

왜 나왔나

프루닝은 존 맵이나 작은 머티리얼라이즈드 집계(SMA) 같은 이름으로 오래 쓰였지만, 실제 고객 작업 부하에서 얼마나 효과가 있는지 정량적으로 보고한 연구는 드물었습니다. 저자들은 스캔과 필터가 처리 시간의 절반 넘게 차지한다는 선행 연구를 인용하면서, 그 비용을 줄이는 가장 확실한 방법은 애초에 읽지 않는 것이라고 봅니다. 또 기존 연구는 대부분 WHERE 조건에만 집중했기 때문에, LIMIT, ORDER BY 와 LIMIT, 조인처럼 흔한 쿼리 모양에서 얼마나 더 거를 수 있는지를 보여 주고자 합니다.

핵심 아이디어

Snowflake 구조와 프루닝의 위치 (2절)

일반 테이블은 압축 전 50MB 에서 500MB 정도의 마이크로 파티션으로 나뉘고, 클라우드 서비스의 메타데이터 서비스가 파티션마다 열별 최솟값과 최댓값 같은 통계를 보관합니다. 프루닝은 두 번 일어납니다. 컴파일 시점에는 읽을 파티션 목록(스캔 세트)을 미리 줄여 카디널리티 추정과 계획 선택에 반영하고, 실행 시점에는 데이터를 보고 나서야 알 수 있는 top-k 와 조인 프루닝을 적용합니다. 어떤 기법이든 필요한 파티션을 빠뜨리는 일은 없고, 필요 없는 파티션을 남기는 일만 있을 수 있습니다.

필터 프루닝 (3절)

조건을 각 파티션의 최솟값, 최댓값 범위에 대입해 결과가 없음이 증명되는 파티션을 뺍니다. 복잡한 식도 범위로 계산합니다. 예를 들어 단위를 바꾸는 IF 식은 두 갈래 범위를 모두 덮는 넓은 범위로, LIKE 'Marked-%-Ridge' 는 STARTSWITH('Marked-') 같은 더 느슨한 조건으로 바꿔 프루닝에만 씁니다. 필터마다 걸러 낸 비율과 평가 시간을 지켜보다가, 효과 없이 느린 필터는 프루닝 대상에서 빼고 실행 시점으로 미룹니다.

LIMIT 프루닝 (4절)

LIMIT k 쿼리는 아무 행이나 k 개만 주면 되므로, 모든 행이 조건을 만족하는 완전 일치 파티션을 찾아 그 행 수 합이 k 이상이면 그 파티션들만 읽으면 됩니다. 완전 일치 여부는 조건을 뒤집어 한 번 더 메타데이터에 대입해 판단합니다. 표 1에 따르면 LIMIT 쿼리는 SELECT 의 2.60%, top-k 쿼리는 5.55% 입니다. 그림 6에서 LIMIT 쿼리의 97% 는 k 가 10,000 이하였습니다.

top-k 프루닝 (5절)

ORDER BY x DESC LIMIT k 를 처리하는 힙의 가장 작은 값, 즉 경계 값을 테이블 스캔에 넘겨, 최댓값이 경계 값보다 작은 파티션을 건너뜁니다. 경계 값이 빨리 올라갈수록 많이 거르므로, 파티션을 최댓값 내림차순으로 처리하는 것이 유리합니다(그림 8). 컴파일 시점에도 완전 일치 파티션과 행 수 정보로 초기 경계 값을 정할 수 있습니다. 필터, 조인의 프로브 쪽, 정렬 키가 그룹 키에 포함된 집계에도 적용됩니다(그림 7).

조인 프루닝 (6절)

해시 조인의 빌드 쪽을 만들면서 키 값 요약을 만들고, 이를 프로브 쪽 파티션의 최솟값, 최댓값과 비교해 겹치지 않는 파티션을 통째로 뺍니다. 행마다 해시 탐색을 줄이는 Bloom 조인과 달리 파티션 단위로 I/O 자체를 없앤다는 점이 다릅니다. 요약은 빌드 쪽 크기의 작은 일부만 차지하며, 정확한 구조는 공개하지 않았습니다.

이어지는 흐름과 데이터 레이크 (7절, 8절)

그림 11은 기법들이 정해진 순서로 이어 적용될 때 각 기법이 몇 퍼센트의 쿼리에 영향을 주는지 흐름도로 보여 주며, 가장 먼저이자 가장 널리 적용되는 것은 필터 프루닝입니다. 모든 기법은 Iceberg 테이블에도 적용되며, Parquet 페이지 인덱스와 Iceberg 매니페스트 메타데이터를 쓸 수 있습니다. 같은 쿼리가 반복될 때 쓰는 술어 캐싱과도 비교하는데, top-k 계획 모양의 85% 가 3일 동안 한 번만 나타나(그림 12) 캐싱만으로는 부족하다고 봅니다.

실험과 결과

운영 측정은 2024년 11월 18일부터 24일까지(전체 비율), 그림 11은 2025년 3월 25일부터 28일까지의 쿼리 표본입니다.

• 전체: 모든 쿼리에 걸쳐 마이크로 파티션의 99.4% 를 걸렀습니다. 비교를 위해 Google PowerDrill 의 92.41% 를 들지만, 측정 방식이 달라 직접 비교할 수는 없다고 밝힙니다.
• 필터 (그림 4): 쿼리의 36% 에서 파티션의 약 90% 이상을 걸렀고, 약 27% 는 걸러질 수 있는 조건이 있었지만 스캔 세트가 줄지 않았습니다.
• LIMIT (표 2): LIMIT 쿼리의 64.22% 는 이미 최소 스캔 세트였고, 3.85% 는 파티션 하나로 줄었습니다. 조건 없는 LIMIT 쿼리만 보면 16.58% 가 파티션 하나로 줄었습니다.
• top-k (그림 9): top-k 프루닝이 적용된 쿼리의 평균 프루닝 비율은 약 77% 였고, 프루닝 비율과 실행 시간 단축이 강하게 연관되었습니다.
• 조인 (그림 10): 프로브 쪽 마이크로 파티션의 79% 를 걸렀고, 쿼리 절반은 스캔 세트가 72% 이상 줄었습니다. 약 13% 는 100% 를 걸렀는데, 빌드 쪽이 비어 있는 경우로 추정합니다.
• TPC-H 비교 (그림 13): 규모 100, X-Small 웨어하우스에서 평균 프루닝 비율 28.7%, 쿼리별 중앙값 8.3% 로 운영보다 훨씬 낮았습니다.
• 결론 (9절): 적용 가능한 쿼리 기준 프루닝 비율을 필터 99%, LIMIT 70%, top-k 77%, 조인 79% 로 정리합니다.

지금 Snowflake 에서는

• 논문이 다루는 마이크로 파티션과 최솟값, 최댓값 메타데이터는 Snowflake 모든 일반 테이블의 저장 방식입니다. 처음 설명은 SIGMOD 2016 논문의 3.3.3절에 있습니다.
• 사용자가 프루닝 효과를 높이는 수단은 클러스터링 키와 자동 클러스터링입니다. 쿼리 프로필의 "Partitions scanned" 와 "Partitions total" 로 얼마나 걸렀는지 확인할 수 있습니다.
• 이 논문의 기법은 내부 최적화라서 사용자가 켜고 끄는 기능 이름으로 노출되지 않습니다. 어느 버전부터 어떤 기법이 적용되었는지는 논문에 없어 연결하지 않습니다.

함께 읽기

• 마이크로 파티션과 클러스터링: 이 사이트의 기능 문서
• 쿼리 튜닝: 이 사이트의 기능 문서
• 저장과 컴퓨트를 나눈 클라우드 웨어하우스 (SIGMOD 2016)
• 7000만 쿼리로 본 저장 분리 엔진 (NSDI 2020): 거르지 못한 파티션을 캐시로 받아 내는 구조
• Snowflake 공식 문서: Micro-partitions & Data Clustering