Zero-Cost NDV Estimation from Columnar File Metadata

Each language version is independently generated for its own context, not a direct translation.

이 논문은 **"데이터 파일을 열지 않고도, 파일의 '라벨'만 보고 그 안에 들어있는 고유한 값의 개수를 정확히 추측하는 방법"**을 소개합니다.

마치 택배 상자를 열지 않고도, 상자 겉에 적힌 무게와 크기만으로 안에 들어있는 사과 개수를 맞추는 마법과 같습니다.

이 기술의 핵심을 일상적인 비유로 설명해 드리겠습니다.

📦 1. 문제 상황: "상자 안을 열지 마세요!"

대용량 데이터 파일 (예: Parquet 파일) 은 거대한 창고에 쌓인 수많은 상자 (Row Groups) 들로 이루어져 있습니다.

기존 방식: "이 상자에 사과가 몇 개나 들어있을까?"를 알기 위해 상자를 하나하나 열어 사과를 세거나, 미리 계산해 둔 목록을 만들어야 했습니다. 하지만 이 과정은 시간이 너무 오래 걸리고, 상자를 여는 비용 (데이터 접근) 이 너무 비쌉니다.
이 논문의 목표: 상자를 절대 열지 않고, 상자 겉에 적힌 **무게 (저장 크기)**와 **최소/최대 크기 (통계 정보)**만 보고 정답을 맞추는 것입니다.

🔍 2. 두 가지 추리 도구 (마법의 눈)

이 논문은 상자를 열지 않고도 추측할 수 있게 해주는 두 가지 서로 다른 '추리 도구'를 개발했습니다.

🛠️ 도구 A: "무게로 개수 맞추기" (사전 인코딩 역산)

비유: 상자에 들어있는 사과들이 모두 '사전 (Dictionary)'에 등재되어 있고, 각 사과에는 번호만 붙여져 있다고 상상해 보세요.
- 상자 겉에 **"총 무게: 50kg"**이라고 적혀 있습니다.
- 사과 한 개의 평균 무게 (길이) 를 알고 있다면, **"50kg ÷ 사과 한 개 무게 = 사과 개수"**를 계산할 수 있습니다.
원리: 데이터 파일에는 '고유한 값들의 사전'과 '각 행이 가리키는 번호'만 저장되어 있습니다. 파일의 총 저장 크기를 보고, 수학 공식을 뒤집어 (역산) 고유한 값이 몇 개인지 계산합니다.
장점: 사과들이 상자 전체에 골고루 섞여 있을 때 (Well-spread) 매우 정확합니다.
단점: 사과들이 상자마다 특정 크기만 담겨 있다면 (예: 1 번 상자엔 작은 사과만, 2 번 상자엔 큰 사과만), 이 방법은 개수를 과소평가할 수 있습니다.

🛠️ 도구 B: "최소/최대값으로 개수 맞추기" (쿠폰 수집 게임)

비유: 100 개의 상자가 줄지어 있습니다. 각 상자에는 **"가장 작은 사과"**와 **"가장 큰 사과"**의 크기가 적혀 있습니다.
- 만약 1 번 상자에 '1cm 사과', 2 번 상자에 '2cm 사과'처럼 상자마다 최소/최대 크기가 계속 변한다면, 이 상자들은 서로 다른 사과들로 가득 차 있다는 뜻입니다.
- 반대로 모든 상자의 최소/최대 크기가 비슷하다면, 같은 사과들이 반복해서 들어있을 가능성이 높습니다.
원리: 이는 **'쿠폰 수집 게임'**과 같습니다. (예: 100 가지 쿠폰이 있는데, 몇 번이나 뽑아야 모든 쿠폰을 모을 수 있을까?) 상자들의 최소/최대값이 얼마나 다양하게 나타나는지 세어보면, 전체 사과 (고유 값) 가 얼마나 많은지 통계적으로 역추적할 수 있습니다.
장점: 사과들이 크기순으로 정렬되어 있거나 (Sorted), 지역별로 나뉘어 있을 때 (Partitioned) 이 방법이 훨씬 정확합니다.

⚖️ 3. 지능적인 중재자: "어떤 도구를 쓸까?"

이 두 도구는 서로 다른 상황에서 작동합니다. 그래서 이 논문은 **"데이터가 어떤 모양인지 먼저 파악하는 지능형 중재자"**를 만들었습니다.

상황 1: 상자들의 최소/최대 크기가 많이 겹친다? → **도구 A(무게 계산)**를 사용합니다.
상황 2: 상자들의 최소/최대 크기가 순서대로 변한다? → **도구 B(최소/최대 다양성)**를 사용합니다.
최종 결정: 두 가지 방법으로 계산한 결과 중 더 큰 숫자를 선택합니다. (왜냐하면 두 방법 모두 실제 값보다 작게 잡는 경향이 있기 때문에, 큰 쪽이 더 정확할 확률이 높기 때문입니다.)

🚀 4. 왜 이것이 중요할까요? (실생활 예시)

이 기술은 **데이터를 분석하는 AI 나 컴퓨터의 '뇌' (쿼리 최적화 엔진)**에게 큰 도움을 줍니다.

예시: "이 데이터에서 '고객 ID'가 몇 개인지 알면, 컴퓨터는 메모리를 얼마나 할당해야 할지, 어떤 순서로 데이터를 처리해야 가장 빠를지 미리 결정할 수 있습니다."
기존: "일단 데이터를 다 읽어보자." → 시간 낭비, 비용 폭탄.
이 기술: "파일 라벨만 보고 계산했으니, 바로 실행하자!" → 초고속, 비용 제로 (Zero-Cost).

💡 요약

이 논문은 **"데이터 파일을 열어보지 않고도, 파일의 '지문' (메타데이터) 만으로 그 안에 숨겨진 고유한 값의 개수를 90% 이상의 정확도로 맞추는 방법"**을 제시합니다.

이는 마치 상자 겉의 무게와 겉면의 패턴만 보고, 상자 안의 보물 개수를 정확히 예측하는 탐정과 같습니다. 덕분에 데이터 처리 속도가 빨라지고, 불필요한 계산 비용이 사라지게 됩니다.

Each language version is independently generated for its own context, not a direct translation.

1. 문제 정의 (Problem)

열형 데이터 파일 (예: Apache Parquet) 을 처리하는 분산 쿼리 엔진 (VoltronData 의 GPU 가속 엔진 'Theseus' 등) 에서 컬럼의 고유 값 개수 (NDV, Number of Distinct Values) 는 쿼리 최적화 (조인 순서 결정, 집계 푸시다운, GPU 메모리 할당 등) 를 위해 필수적입니다.

그러나 다음과 같은 이유로 정확한 NDV 를 얻는 것이 어렵습니다:

메타데이터 부재: Parquet 파일의 distinct_count 필드는 계산 비용이 너무 비싸기 때문에 대부분의 작성자 (Writer) 가 채우지 않습니다.
데이터 접근 불가: 메타데이터만 기반으로 한 비용 기반 최적화 (Cost-Based Optimization) 를 수행하려면 실제 데이터 페이지에 접근하여 샘플링하거나 HyperLogLog 와 같은 스케치를 유지해야 하는데, 이는 추가적인 I/O 오버헤드나 작성자 측 인프라 변경을 필요로 하므로 '메타데이터 전용' 계획의 목적을 훼손합니다.

따라서 추가 저장 공간이나 데이터 접근 없이, 기존 파일 메타데이터만으로 NDV 를 추정할 수 있는 방법이 필요했습니다.

2. 방법론 (Methodology)

이 논문은 Parquet 파일 메타데이터에 내재된 두 가지 상보적인 신호를 활용하여 NDV 를 추정하는 새로운 기법을 제안합니다.

A. 사전 인코딩 크기 역산 (Dictionary Size Inversion)

원리: Parquet 은 저/중도 카디널리티 컬럼에 대해 사전 인코딩 (Dictionary Encoding) 을 사용합니다. 메타데이터에는 압축되지 않은 전체 크기 ( $S$ ), 행 수 ( $N$ ), NULL 개수, 그리고 값의 평균 길이 ( $len$ ) 가 포함되어 있습니다.
방정식: 저장 크기 방정식 $S = ndv \times len + (N - nulls) \times \lceil \log_2(ndv) \rceil / 8$ 을 $ndv$ 에 대해 풉니다.
해법: 뉴턴 - 라프슨 (Newton-Raphson) 반복법을 사용하여 $ndv$ 를 수치적으로 구합니다.
적용 조건: 고유 값들이 행 그룹 (Row Group) 간에 고르게 분포되어 있을 때 (Well-spread) 정확도가 높습니다.

B. 최소/최대 값 다양성 추정 (Min/Max Diversity Estimation)

원리: 각 행 그룹은 해당 컬럼의 최소값 (min) 과 최대값 (max) 을 메타데이터에 저장합니다. $n$ 개의 행 그룹에서 관찰된 서로 다른 min 값과 max 값의 개수를 분석합니다.
모델: 이를 쿠폰 수집 문제 (Coupon Collector Problem) 모델로 간주합니다. $n$ 개의 행 그룹이 전체 고유 값 집합에서 샘플을 추출했다고 가정하고, 관찰된 고유 min/max 개수를 통해 전체 NDV 를 역산합니다.
적용 조건: 데이터가 정렬 (Sorted) 이나 파티셔닝된 경우, 행 그룹별로 값 범위가 명확히 구분되어 min/max 가 다양하게 분포하므로 이 방법이 더 정확합니다. (사전 인코딩 역산은 이 경우 과소평가하는 경향이 있음)

C. 분포 감지 및 하이브리드 전략 (Distribution Detection & Hybrid Strategy)

분류기: 행 그룹 간의 범위 중첩 (Overlap) 과 단조성 (Monotonicity) 을 분석하여 데이터가 '잘 분포된 (Well-spread)' 상태인지, '정렬/파티션된 (Sorted/Partitioned)' 상태인지 감지합니다.
최종 추정: 두 방법 (사전 인코딩 역산, min/max 다양성) 의 추정치 중 더 큰 값 (Max) 을 선택합니다. 이는 각 방법이 서로 다른 시나리오에서 과소평가하는 경향이 있기 때문에, 더 보수적이고 안전한 값을 선택하는 전략입니다.
제약 조건: 데이터 타입 (정수, 날짜 등) 의 이론적 상한선이나 스키마 제약 조건 (외래 키 등) 을 적용하여 추정치를 보정합니다.

3. 주요 기여 (Key Contributions)

폐쇄형 방정식 유도: 사전 인코딩 저장 크기와 NDV 사이의 관계를 수학적으로 모델링하고, 뉴턴 - 라프슨 법으로 해를 구하는 방법을 제시했습니다.
통계적 스케치로서의 min/max 인식: 행 그룹별 min/max 통계가 암시적인 카디널리티 스케치 역할을 하며, 이를 쿠폰 수집 모델의 역산을 통해 NDV 를 복원할 수 있음을 증명했습니다.
가벼운 분포 감지기: 데이터 분포 특성에 따라 두 추정기 중 적절한 것을 선택하거나 하이브리드 방식으로 결합하는 경량 로직을 개발했습니다.
배치 메모리 예측: 추정된 글로벌 NDV 를 기반으로 GPU 배치 처리 시 필요한 사전 (Dictionary) 메모리 양을 데이터 읽기 없이 예측하는 방법을 제시했습니다.

4. 결과 및 평가 (Results & Evaluation)

배포 환경: VoltronData 의 GPU 가속 분산 쿼리 엔진 'Theseus'에서 실제 프로덕션 워크로드에 적용되었습니다.
정확도:
- 잘 분포된 (Well-spread) 컬럼의 경우 오차가 10% 미만으로 매우 높았습니다.
- 정렬된 데이터의 경우 사전 인코딩 역산만으로는 과소평가되었으나, min/max 다양성 추정기가 이를 효과적으로 보정하여 하이브리드 접근법의 견고성을 입증했습니다.
성능: 모든 연산은 메타데이터를 한 번만 스캔 (Single-pass) 하며 수행되므로 시간 복잡도 $O(n)$ , 공간 복잡도 $O(1)$ 로 매우 효율적입니다.
한계: VoltronData 의 자산 매각으로 인해 구현체와 상세 실험 데이터가 분실되었으며, 현재는 공개 벤치마크에서의 재현이 계획 중입니다.

5. 의의 및 중요성 (Significance)

제로 비용 (Zero-Cost) 추정: 추가적인 데이터 스캔이나 스케치 유지 없이 기존 메타데이터만으로 NDV 를 추정함으로써, 쿼리 최적화 오버헤드를 극도로 줄였습니다.
범용성: 이 기법은 Parquet 에 국한되지 않으며, 사전 인코딩과 파티션 수준의 min/max 통계를 지원하는 ORC, F3 등 다른 열형 파일 포맷에도 적용 가능합니다.
실용적 가치: GPU 메모리 할당, 집계 푸시다운, 조인 순서 최적화 등 현대적인 분산 쿼리 엔진의 핵심 성능 요소들을 개선하는 데 직접적으로 기여했습니다.

결론적으로, 이 논문은 데이터 파일의 메타데이터에 숨겨진 정보를 수학적으로 역산하여, 데이터 접근 없이도 높은 정확도의 카디널리티 추정을 가능하게 하는 혁신적인 접근법을 제시했습니다.