Zero-Cost NDV Estimation from Columnar File Metadata
Claude Brisson · 2026
Read Zero-Cost NDV Estimation from Columnar File Metadata by Claude Brisson (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-24606.txt.
Introduction
Brisson presents a zero-cost method to estimate the number of distinct values in a column. The method uses only existing file metadata, with no extra storage. One signal inverts the dictionary-encoded storage size equation, which works well when values spread evenly across row groups. Another counts distinct min and max values across row groups and inverts a coupon collector model, suiting sorted or partitioned data. A light detector picks between the two. Shown on Parquet, the idea extends to ORC and other formats.
Catalog record
| CREATOR | Claude Brisson |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 16337 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.24606
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Zero-Cost NDV Estimation from Columnar File Metadata Claude Brisson Abstract We present a method for estimating the number of distinct values (NDV) of a column in columnar file formats, using only existing file metadata–no extra storage, no data access. Two complementary signals are exploited: (1) inverting the dictionary-encoded storage size equation yields accurate NDV estimates when distinct values are well-spread across row groups; (2) counting distinct min/max values across row groups and inverting a coupon collector model provides robust estimates for sorted or partitioned data. A lightweight distribution detector routes between the two estimators. While demonstrated on Apache Parquet, the technique generalizes to any format with dictionary encoding and partition-level statistics, such as ORC and F3. Applications include cost-based query optimization, GPU memory allocation, and data profiling. 1 Introduction While building Theseus [ 12 ] , a GPU-accelerated distributed query engine at VoltronData, we needed NDV estimates to drive cost-based optimization–aggregate pushdown, join ordering, memory allocation for GPU kernels. Parquet’s distinct_count field is almost never populated: computing exact distinct counts is expensive, and most writers omit it. Sampling or maintaining HyperLogLog sketches would require accessing data or adding writer-side infrastructure, defeating the purpose of metadata-only planning. The question became: what cardinality information is already encoded in existing metadata? Dictionary-encoded columns store their uncompressed size per column chunk. Row groups store per-column min/max statistics. Neither was designed for cardinality estimation, but both encode it implicitly–at least locally, within individual row groups. This paper details techniques for generalizing these local signals into global NDV estimates for the entire column. The technique was implemented and validated on production workloads at VoltronData. When the company’s assets were liquidated, the implementation and experimental results were lost; this paper reconstructs the approach from memory. Contributions. 1. A closed-form equation relating NDV to dictionary-encoded storage size, solved via Newton-Raphson (Section 4 ). 2. Recognition that row group min/max statistics function as implicit cardinality sketches, with NDV recovery via coupon collector inversion (Section 5 ). 3. A lightweight distribution detector that routes between the two estimators (Section 6 ). 4. Batch memory prediction using coupon collector analysis (Section 8 ). 2 Background 2.1 Parquet Dictionary Encoding Apache Parquet organizes data into row groups , each containing one column chunk per column. Within a column chunk, Parquet employs dictionary encoding for low-to-medium cardinality columns [ 3 ] : a dictionary page stores the distinct values, and data pages store bit-packed indices into the dictionary. Dictionary Page Data Pages +-------------+ +---+---+---+---+---+ | "alice" 0 | | 0 | 2 | 1 | 0 | 2 | ... | "bob" 1 | +---+---+---+---+---+ | "charlie" 2 | (indices, bit-packed) +-------------+ Each column chunk exposes a total_uncompressed_size field in its metadata, equal to the sum of dictionary and index pages before compression: S=\text{ndv}\times\text{len}+(N-\text{nulls})\times\lceil\log_{2}(\text{ndv})\rceil\,/\,8 (1) where ndv is the number of distinct values, len the mean byte length of values, N the row count, and nulls the null count. 2.2 Row Group Statistics Parquet stores per-column min/max statistics in each row group [ 4 ] . These are designed for predicate pushdown–skipping row groups whose value ranges exclude a query predicate–but have not traditionally been used for cardinality estimation. Across n row groups, a column yields n pairs (\min_{i},\max_{i}) . We exploit both the diversity of these values and the overlap patterns between consecutive ranges. 3 Approach Overview The two metadata signals have complementary strengths. Dictionary size inversion (Section 4 ) is grounded in a storage equation whose accuracy depends on how distinct values are spread across row groups. It does not require statistical uniformity–values may have arbitrary frequency distributions within each row group. What matters is that most distinct values appear in most row groups, a condition we call well-spread . When row group ranges heavily overlap, this condition holds and dictionary inversion is accurate. Min/max diversity estimation (Section 5 ) instead exploits the spread of extreme values across row groups; it is accurate for sorted or partitioned data, where dictionary inversion underestimates. Well-spread Sorted/Partitioned Low NDV Dictionary inversion accurate underestimates accurate Min/max diversity underestimates accurate underestimates Table 1: Complementary accuracy profiles of the two estimators. A distribution detector (Section 6 ) classifies each column’s data layout by analyzing range overlap and monotonicity across row groups. The final estimate takes the maximum of both methods, bounded by type-specific constraints (Section 7 ). 4 Dictionary Size Inversion 4.1 Core Equation Given the observable metadata tuple (S,N,\text{nulls},\text{len}) , we solve Equation ( 1 ) for ndv : f(\text{ndv})=\text{ndv}\times\text{len}+(N-\text{nulls})\times\lceil\log_{2}(\text{ndv})\rceil\,/\,8-S=0 (2) 4.2 Newton-Raphson Solution We apply Newton-Raphson iteration using the exact f but a continuous approximation for the derivative, since the ceiling function has zero derivative almost everywhere: \text{ndv}_{k+1}=\text{ndv}_{k}-\frac{f(\text{ndv}_{k})}{f^{\prime}(\text{ndv}_{k})},\qquad f^{\prime}(\text{ndv})\approx\text{len}+\frac{N-\text{nulls}}{8\cdot\text{ndv}\cdot\ln 2} (3) The ceiling discontinuities are small relative to the dominant linear term, and convergence is unaffected in practice. The initial guess \text{ndv}_{0}=S/\text{len} assumes index overhead is small. Convergence to a tolerance of 10^{-6} is typically achieved in 5–10 iterations. 4.3 Estimating Mean Value Length The parameter len is not directly stored in metadata. For fixed-width types (integers, dates, timestamps), it is known exactly from the Parquet schema. For variable-length types, we estimate it from all distinct min and max values observed across row groups: \text{len}=\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}|v|,\qquad\mathcal{V}=\{\text{distinct mins}\}\cup\{\text{distinct maxs}\} (4) The sample size |\mathcal{V}| serves as a reliability indicator: more distinct extreme values yield a more representative length distribution. For a single row group, we fall back to \text{len}=(|\min|+|\max|)/2 . 4.4 Plain Encoding Fallback When a column’s cardinality exceeds Parquet’s dictionary threshold (typically {\sim}1 MB), the writer falls back to plain encoding [ 3 ] : no dictionary page is written, and data pages contain raw values instead of indices. The uncompressed size then satisfies S\approx(N-\text{nulls})\times\text{len} , which the solver interprets as very high NDV. We detect this condition by checking two indicators simultaneously: \text{likely\_fallback}=\left(\frac{\text{ndv}}{N-\text{nulls}}\geq 0.9\right)\;\land\;\left(\frac{S}{(N-\text{nulls})\times\text{len}}\in[0.8,\;1.2]\right) (5) When detected, the estimate should be treated as a lower bound rather than a point estimate: the true NDV is at least as high as the dictionary threshold, but the inversion equation no longer constrains it. 5 Min/Max Diversity Estimation 5.1 Row Group Extrema as Implicit Samples Each row group computes and stores the minimum and maximum values for each column. Across n row groups, let m_{\min} denote the number of distinct min values and m_{\max} the number of distinct max values. These counts reflect how many different values appear as row group extrema–a signal that depends on the underlying cardinality and the data distribution. 5.2 Coupon Collector Model The coupon collector problem models sampling with replacement from a finite population [ 5 ] . Drawing k items uniformly from N distinct values, the expected number of distinct values observed is: E[\text{distinct}]=N\times(1-e^{-k/N}) (6) We model the n row group minima as n draws from the population of NDV distinct values: E[m_{\min}]=\text{NDV}\times(1-e^{-n/\text{NDV}}) (7) An analogous equation holds for m_{\max} . 5.3 Inverting for NDV Given an observed count m (either m_{\min} or m_{\max} ), we solve: g(\text{NDV})=\text{NDV}\times(1-e^{-n/\text{NDV}})-m=0 (8) via Newton-Raphson with derivative: g^{\prime}(\text{NDV})=1-e^{-n/\text{NDV}}\cdot\left(1+\frac{n}{\text{NDV}}\right) (9) We compute separate estimates from m_{\min} and m_{\max} and retain the larger of the two. 5.4 Accuracy on Sorted Data For uniformly distributed data, row group minima cluster near the global minimum–we are sampling order statistics, not sampling uniformly from the value space. This causes min/max diversity