Estimating NDV from Parquet metadata

Data lakes based on Parquet files are increasingly popular, but data often lacks detailed statistics, so estimating them from metadata alone has become an interesting problem. The diversity of data types, encodings, and compression methods in these files offers a number of possibilities, but here we will focus on min/max values.

Parquet files break their rows into rowgroups and record metadata for each. Minimum and maximum values for each column are included to allow data skipping, but they offer some insight into the NDV.

For a Sorted Column

Short Runs

In a sorted sequence with duplicates $v_1...v_1, v_2,...,v_2,...,v_{NDV},...,v_{NDV}$, the probability $p_{\neq}$ of consecutive values being unequal is $NDV/n$ (or $(NDV-1)/(n-1)$ if the endpoint is removed, but we will ignore this adjustment).

$$ NDV = p_{\neq} n $$

We can estimate $p_{\neq}$ by cutting the sequence at random locations and comparing the values before and after the cut; if it falls in the middle of a run, the values are equal, and if it falls on the boundary, they are unequal.

Rowgroup minimum/maximum values at rowgroup boundaries form such a sample, where the maximum of one rowgroup is compared with the minimum of the next.

Test

Test data was generated and evaluated in duckdb.

In the TPC-DS benchmark, the store_sales ss_ticket_number column is sorted and non-unique, with a multiplicity ranging from 8 to 16.

To generate the schema and data:

 CALL dsdgen(sf = 1);

To generate a parquet file:

 copy store_sales to 'store_sales.parquet' (format parquet, row_group_size 10000);

From this file's metadata we construct an NDV estimate and compare with the exact value:

  with pairs as (
      select
       row_group_id,
       row_group_num_rows,
       (stats_min <> lag(stats_max) over (order by row_group_id))::int as neq
      from parquet_metadata('store_sales.parquet')
      where column_id = 9),
     mr as (
      select
       sum(neq) as mismatches,
       count(*) as num_row_groups,
       sum(row_group_num_rows) as rowcnt,
       sum(neq)/count(neq) as p_neq
      from pairs )
    select
     p_neq * rowcnt as ndv_est,
     (select count(distinct ss_ticket_number) from store_sales) as ndv_exact
     from mr;

The result is about 11% above the true value.

  ┌───────────────────┬───────────┐
  │      ndv_est      │ ndv_exact │
  │      double       │   int64   │
  ├───────────────────┼───────────┤
  │ 266514.2491103203 │    240000 │
  └───────────────────┴───────────┘

Long runs > B

If the run length L = n/NDV is longer than rowgroup length B, the situation is even simpler. This assumption means a rowgroup can have at most one change in value, so

NDV = 1 + [number of rowgroups where min < max] + [number of rowgroups where max < min of next rowgroup]

This value is exact, but it may undercount if some runs are shorter than B.

Unsorted Column

On the assumption that each distinct value repeats exactly $k$ times, we attempt to find $k$ from the observed minima.

We first observe that a random shuffle can be modeled as a process on a sorted sequence:

S is an ascending sequence of integers where each value repeats exactly k times. We randomly shuffle S into m bins, until every bin is nonempty, and record the first or minimum value placed into each bin. What is the number of distinct minimum values recorded as a function of m and k?

This problem is a variant of the coupon collector problem, and an LLM was used to frame the problem as an ODE (https://claude.ai/share/0199cd66-4a76-406b-a3fc-eaf677e8f1e9), yielding a succinct result

$$ E[R] \approx \frac{m}{k}H_k $$

Solving this expression for $k$ is possible, but a simpler approach may be to try $k = 1..m$ for the closest match.

Related Manual Work

Originally, a less accurate estimator

$$ R \approx \frac{m}{k}(H_m - H_{\frac{m}{k}} + 1) $$

was constructed by separating the process into two phases:

Where the expected number of trials to fill the next bin is less than $k$.
Where it is greater.

Intuitively, phase 1 has a small "stride" that does not skip a run of $k$ duplicates, so every value appears in some bin, possibly more than one. Phase 2 always skips ahead by at least $k$, so each subsequent bin gets a distinct value.

The dividing line between the two phases is where $k$ and the expected number of trials are equal, which is where $m/k$ empty bins remain. So phase 2 contributes $\frac{m}{k}$ distinct values to the total, and phase 1 contributes the total number of values consumed, $m(H_m-H_{\frac{m}{k}})$, divided by $k$.

These are weak assumptions, as variance from the expected number ot trials skews these terms in various ways, but the estimate is often within 10-20% of the true value.

Ironically, the expression for phase 1 comes close to the succinct estimator since $H_m-H_{\frac{m}{k}} \approx ln{ m }- ln {\frac{m}{k}} = ln{ k }$. More exploration might yield some intuition as to why $H_k$ appears.

Other Work

Brisson, Claude. Zero-Cost NDV Estimation from Columnar File Metadata https://arxiv.org/abs/2603.24606

Method 2 is fairly close. I havent had a chance to run it on the TPC dataset though

-- Setup
CREATE TABLE t AS SELECT (random() * 10000)::INTEGER AS col FROM range(1000000);
COPY t TO 'test.parquet' (FORMAT PARQUET, ROW_GROUP_SIZE 50000);

-- Ground truth → 10001
SELECT COUNT(DISTINCT col) FROM t;

-- Built-in HLL → 8571 (low default precision; 14% error)
SELECT approx_count_distinct(col) FROM t;

-- Method 2 from the list: min/max bound from parquet footer only, ZERO data reads → 10001
SELECT MAX(stats_max::INTEGER) - MIN(stats_min::INTEGER) + 1 AS upper_bound
FROM parquet_metadata('test.parquet');

-- Method 4: compression-ratio oracle (footer only)
SELECT row_group_id,
(total_compressed_size * 8.0 / num_values) AS bits_per_value,
POW(2.0, total_compressed_size * 8.0 / num_values)::BIGINT AS cardinality_upper_bound
FROM parquet_metadata('test.parquet');

-- Method 5: KMV sketch (k = 1024) → 9888 (1.1% error)
WITH distinct_h AS (SELECT DISTINCT hash(col) AS h FROM t),
k_smallest AS (SELECT h FROM distinct_h ORDER BY h LIMIT 1024)
SELECT (1023.0 / (MAX(h)::DOUBLE / POW(2.0, 64)))::BIGINT FROM k_smallest;

-- Method 6: birthday-paradox sampling → 10046 (0.4% error)
WITH s AS (
SELECT col, row_number() OVER () AS rn FROM t USING SAMPLE 5000 ROWS
),
c AS (
SELECT COUNT(*) AS collisions
FROM s a JOIN s b ON a.col = b.col AND a.rn < b.rn
)
SELECT (5000.0 * 4999.0 / (2.0 * collisions))::BIGINT FROM c;

-- Method 7: coupon collector with Chao1 extrapolation (10% sample) → 10004 (0.03% error)
WITH s AS (SELECT col FROM t USING SAMPLE 10 PERCENT (RESERVOIR)),
f AS (SELECT col, COUNT() AS cnt FROM s GROUP BY col),
stats AS (
SELECT COUNT() AS observed,
SUM(CASE WHEN cnt=1 THEN 1 ELSE 0 END) AS singletons,
SUM(CASE WHEN cnt=2 THEN 1 ELSE 0 END) AS doubletons
FROM f
)
SELECT (observed + singletons*(singletons-1)/(2.0*GREATEST(doubletons,1)))::BIGINT
FROM stats;

-- Method 8: entropy via empirical distribution → 9951 (0.5% error)
WITH freqs AS (SELECT col, COUNT(*)::DOUBLE AS c FROM t GROUP BY col),
probs AS (SELECT c / SUM(c) OVER () AS p FROM freqs)
SELECT POW(2.0, -SUM(p * LOG2(p)))::BIGINT FROM probs;

KWillets/Parquet NDV.md

Select an option

No results found