From Global Sorts to Sketches

TL;DR: This article explains how Databend combines KLL, Top-N, and Count-Min Sketch (CMS) to build optimizer statistics with lower

ANALYZE

Why Statistics Affect Both Performance and Cost

Before executing a SQL query, a cost-based optimizer estimates the cardinality and cost of candidate plans. These estimates influence join ordering, scan selection, and operator choice. If the optimizer substantially underestimates or overestimates a filter, even a fast execution engine can end up running an expensive plan.

Histograms are a common way to summarize a column's distribution. Equi-depth histograms usually behave better than equi-width histograms on skewed data because every bucket contains roughly the same number of rows.

Accurate statistics, however, are not free. A conventional histogram builder may need to scan, sort, and aggregate an entire column. In a cloud data warehouse such as Databend,

ANALYZE

The engineering question is therefore:

How can the optimizer obtain useful statistics without paying for a global sort every time?

Databend addresses different parts of this problem with KLL, Top-N, and CMS. They complement one another rather than compete as alternative implementations.

How Histograms Support Cardinality Estimation

Consider a simplified table:

CREATE TABLE employee (
    id INT,
    salary INT
);

Assume the

salary

For this range predicate:

SELECT *
FROM employee
WHERE salary < 5000;

B1 and B2 are fully covered, while B3 is only partially covered. Assuming a uniform distribution within B3:

Estimated Rows
= B1 + B2 + B3 * Coverage
= 250 + 250 + 250 * (5000 - 4000) / (7000 - 4000)
~= 583

The histogram approximates the global distribution through bucket boundaries. Building exact equi-depth boundaries traditionally requires a full scan, a global sort, and aggregation:

Column Values
      |
      v
+--------------------+
|  Full Table Scan   |
+--------------------+
      |
      v
+--------------------+
|    Global Sort     |
+--------------------+
      |
      v
+--------------------+
| Global Aggregation |
| Compute Quantiles  |
+--------------------+
      |
      v
+--------------------+
|  Build Histogram   |
+--------------------+

As the table grows, the global sort becomes a major source of latency and memory pressure. KLL removes that bottleneck by accepting a controlled amount of approximation.

KLL: Approximating Quantiles in One Pass

KLL, short for Karnin-Lang-Liberty Sketch, is a streaming summary algorithm for approximate quantiles. It reads values sequentially and compresses a bounded number of samples into a mergeable sketch.

Mergeability makes KLL a natural fit for Databend's distributed execution model. Compute nodes can build local sketches in parallel, merge them into a global KLL, query the required quantiles, and use those quantiles as equi-depth bucket boundaries.

Input Values
      |
      v
+-------------------+
| One-pass KLL Scan |
+-------------------+
      |
      v
+-------------------+
| Merge KLL Sketch  |  Distributed
+-------------------+
      |
      v
+-------------------+
|  Quantile Query   |
| q0, q1, ..., qN   |
+-------------------+
      |
      v
+-------------------+
|  Build Histogram  |
+-------------------+

This changes histogram construction from "scan, globally sort, and aggregate" to "scan once and merge sketches." On large tables whose statistics need regular refreshes, the difference can significantly reduce memory usage and interference with foreground queries.

KLL Still Needs NDV

KLL provides quantiles and bucket boundaries, but it does not directly provide each bucket's number of distinct values, or NDV. Bucket-level NDV is important for equality predicates.

During the first

ANALYZE

let column_ndv = self
    .ndv_states
    .get(&column_id)
    .map(|hll| hll.count() as f64);

KLL uses rank to derive the number of rows in each equi-depth bucket. A fast implementation can then distribute the column-level NDV proportionally:

bucket_ndv = column_ndv * bucket_values / total_values

The estimate is constrained to:

1 <= bucket_ndv <= bucket_values

For example:

Total rows        = 10,000
Column HLL NDV    = 1,000
Number of buckets = 100
Rows per bucket   ~= 100

This approach is inexpensive, but it assumes that distinct values are distributed across buckets in proportion to row counts. Equality estimates become less reliable as skew increases.

kll_fast and kll_full

Databend provides two KLL-based

ANALYZE

• kll_fast performs one scan and estimates each bucket's NDV from the column-level HLL result.

• kll_full uses KLL to determine bucket boundaries, then performs a second scan to collect row counts and HLL NDV for every bucket.

The two passes in

kll_full

Pass 1:
Values -> KLL Sketch -> Approximate Quantiles -> Fixed Boundaries

Pass 2:
Values -> Route into Buckets -> Count Rows and HLL NDV per Bucket

Each bucket maintains the following state:

struct KllBucketStats {
    routing_upper_bound: Datum,
    observed_lower_bound: Option<Datum>,
    observed_upper_bound: Option<Datum>,
    count: u64,
    ndv: MetaHLL,
}

For each value in the second scan, Databend finds the first bucket satisfying:

value <= bucket.routing_upper_bound

It then updates the row count and NDV state:

self.count += 1;
self.ndv.add_object(original_value);

The implementation also records the minimum and maximum values actually observed in the bucket. Its final NDV is:

bucket.ndv.count()

The second scan gives

kll_full

kll_full

Why Bucket NDV Matters for Equality Predicates

Add NDV to the earlier

salary

For:

SELECT *
FROM employee
WHERE salary = 4500;

The value belongs to B3. Assuming a uniform distribution inside the bucket:

Estimated Rows = Bucket Rows / Bucket NDV
               = 250 / 150
               ~= 1.67

For:

SELECT *
FROM employee
WHERE salary = 1500;

The value belongs to B1:

Estimated Rows = 250 / 50
               = 5

The buckets contain the same number of rows but have different average frequencies:

Range predicates mainly depend on boundaries and coverage. Equality predicates depend more heavily on NDV. KLL describes quantiles and value ranges well, but KLL plus bucket NDV still cannot identify hot values hidden inside a bucket.

Benchmark: KLL's Trade-offs

The following benchmark compares a sort-based

window

kll_fast

kll_full

Three trade-offs stand out:

1. kll_fast
   

   greatly reduces

   ANALYZE
   

   time. On the 1M- and 5M-row data sets, it takes 20.5% and 16.8% of the

   window
   

   runtime, respectively, while also reducing RSS growth.

2. kll_fast
   

   remains effective for range predicates but is insufficient for equality estimates on its own. Range q-error geomeans are 1.111 and 1.135, while equality q-error geomeans rise to 5.236 and 6.833.

3. kll_full
   

   improves overall and equality accuracy, but it does not provide a runtime advantage. Its RSS delta is lower than

   window
   

   , and its range estimates are nearly exact. The second scan, however, makes it slightly slower than

   window
   

   , while some equality predicates still show large outliers.

KLL solves the resource problem of histogram construction. It does not, by itself, solve skew. Databend uses Top-N and CMS for that.

Top-N: Exact Statistics for the Hottest Values

Top-N records the most frequent values in a column and their row counts. Databend collects and merges these statistics hierarchically:

Block-local Top-N
        |
        v Merge
Segment / Source-local Top-N
        |
        v Merge
Analyze Sink
        |
        v
Table-snapshot Top-N per Column

Block-level Top-N statistics are stored in segment statistics. Incremental

ANALYZE

When an equality predicate hits Top-N, the optimizer can use its recorded frequency directly rather than assuming a uniform distribution within a histogram bucket. This works well when a small, stable set of values dominates the column.

The limitation is capacity. If a column has many moderately hot values, some of them will inevitably fall outside the retained Top-N set.

CMS: Fixed-Space Estimates for a Wider Hot Set

Count-Min Sketch estimates value frequencies with a two-dimensional counter array and multiple hash functions:

hash(value, row0) -> counter++
hash(value, row1) -> counter++
...
hash(value, row4) -> counter++

To estimate a value's frequency, CMS takes the minimum matching counter:

estimate(value) = min(counter[hash_i(value)])

Hash collisions can only increase counters, so CMS produces an approximate upper-biased estimate. It uses fixed space and supports distributed merging:

Block CMS
    |
    v Counter-wise Add
Segment / Source CMS
    |
    v Counter-wise Add
Table Snapshot CMS

CMS covers a much wider set of values than Top-N, which makes it useful when the number of hot values exceeds the Top-N capacity. The trade-off is approximation and collision noise.

Combining KLL, Top-N, CMS, and NDV in Databend

Databend evaluates equality predicates through a hierarchy of statistics:

Exact Top-N Match
        |
        v No Match
CMS Frequency Estimate
        |
        v Not Applicable
Error-aware Top-N Estimate
        |
        v
Regular NDV / Histogram Estimate

CMS does not automatically override the regular estimator. The optimizer computes:

lower_count   = cms_estimate - cms_error_bound
average_count = non_null_rows / NDV

It uses the CMS estimate only when:

lower_count > average_count

This condition provides evidence that a value is genuinely hotter than the average. Low-frequency values continue to use the regular NDV or histogram estimate, preventing CMS collision noise from unnecessarily degrading their estimates.

The responsibilities are therefore clear:

• KLL summarizes the global value range and quantiles.

• Top-N records the most prominent hot values exactly.

• CMS covers a wider set of hot values that do not fit in Top-N.

• NDV and histograms continue to estimate ordinary values.

Benchmark: Recovering Hot Values Missed by Top-N

This benchmark uses 1 million rows, an NDV of 100,000, a Top-N capacity of 50, and a CMS error rate of 0.001. Half of the rows in

wide_hot_key

Each result reports the median and range of three runs.

ANALYZE

Overhead

Top-N and CMS add both runtime and memory overhead, but all four variants remain below one second in this test. Whether that overhead is worthwhile depends on how important equality predicates are to the workload.

Equality q-error

Without hotspot statistics, the equality q-error geomean is 25.354. CMS reduces it to 1.355 and cuts P90 from 2006.822 to 2.5. Top-N helps with the most prominent values, but CMS provides much broader coverage when the hot set is wide.

wide_hot_key

q-error

For a representative predicate,

wide_hot_key = 0

With 200 hot values competing for 50 Top-N slots, this particular value is missed and falls back to a 10-row estimate. CMS corrects the estimate to 2,716, close to the actual cardinality.

Choosing a Statistics Strategy

No single strategy offers both minimum overhead and maximum accuracy. The right choice depends on the data distribution and query workload.

kll_fast

kll_full

In Databend, these probabilistic structures do more than make

ANALYZE

Conclusion

KLL, Top-N, and CMS solve different parts of the cardinality estimation problem:

• KLL approximates quantiles with a one-pass, mergeable sketch, reducing the sorting and memory cost of equi-depth histogram construction.

• Top-N records the most frequent values exactly and corrects histogram estimates for prominent hotspots.

• CMS covers a broader hot set in fixed space, including values that fall outside the Top-N capacity.

The benchmarks also make their boundaries visible.

kll_fast

kll_full

For an S3-native, cloud-native analytical database such as Databend, optimizer statistics are not an isolated engine feature. Lower

ANALYZE