---
title: 'From Global Sorts to Sketches'
date: 2026-07-28
slug: category-engineering/optimizer-sketches
cover_url: 'https://static.databend.cn/img/202607/20260728-FromGlobalbanner-EN1.png'
description: 'This article explains how Databend combines KLL, Top-N, and Count-Min Sketch (CMS) to build optimizer statistics with lower `ANALYZE` overhead. Together, they balance histogram efficiency with accurate estimates for skewed and high-frequency values.'
tags: [databend]
category: Engineering
authors:
  - KKould
---

**TL;DR:** This article explains how Databend combines KLL, Top-N, and Count-Min Sketch (CMS) to build optimizer statistics with lower `ANALYZE` overhead. Together, they balance histogram efficiency with accurate estimates for skewed and high-frequency values.

{/* truncate */}

## 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` consumes compute and memory and may also trigger significant reads from object storage.

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:

```SQL
CREATE TABLE employee (
    id INT,
    salary INT
);
```

Assume the `salary` column has the following equi-depth histogram:

|Bucket|Salary Range|Rows|
|---|---|---|
|B1|[1000, 2000)|250|
|B2|[2000, 4000)|250|
|B3|[4000, 7000)|250|
|B4|[7000, 10000]|250|

For this range predicate:

```SQL
SELECT *
FROM employee
WHERE salary < 5000;
```

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

```Plaintext
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:

```Plaintext
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.

```Plaintext
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` scan, Databend uses HyperLogLog (HLL) to estimate the NDV of the entire column:

```Rust
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:

```Plaintext
bucket_ndv = column_ndv * bucket_values / total_values
```

The estimate is constrained to:

```Plaintext
1 <= bucket_ndv <= bucket_values
```

For example:

```Plaintext
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` modes:

- **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` are:

```Plaintext
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:

```Rust
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:

```Plaintext
value <= bucket.routing_upper_bound
```

It then updates the row count and NDV state:

```Rust
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:

```Rust
bucket.ndv.count()
```

The second scan gives `kll_full` more accurate bucket-level statistics, but scanning and routing all values still has a cost. As the benchmark below shows, `kll_full` is not necessarily faster than a sort-based baseline.

## Why Bucket NDV Matters for Equality Predicates

Add NDV to the earlier `salary` histogram:

|Bucket|Salary Range|Rows|NDV|
|---|---|---|---|
|B1|[1000, 2000)|250|50|
|B2|[2000, 4000)|250|100|
|B3|[4000, 7000)|250|150|
|B4|[7000, 10000]|250|80|

For:

```SQL
SELECT *
FROM employee
WHERE salary = 4500;
```

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

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

For:

```SQL
SELECT *
FROM employee
WHERE salary = 1500;
```

The value belongs to B1:

```Plaintext
Estimated Rows = 250 / 50
               = 5
```

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

|Bucket|Rows|NDV|Average Frequency|
|---|---|---|---|
|B1|250|50|5.00|
|B3|250|150|1.67|

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` baseline with `kll_fast` and `kll_full`. A q-error of 1 means that the estimate matches the actual cardinality; larger values indicate greater error.

|Rows|Algorithm|Analyze Elapsed|RSS Delta|Peak RSS|Overall q-error|Equality q-error|Range q-error|
|---|---|---|---|---|---|---|---|
|1M|window|3.203s|333,016 KB (~325 MB)|2,059,548 KB|geo 1.000, p90 1.000, max 1.000|geo 1.000, max 1.000|geo 1.000, max 1.000|
|1M|kll_fast|0.657s|130,300 KB (~127 MB)|1,826,592 KB|geo 2.412, p90 39.713, max 227.380|geo 5.236, max 227.380|geo 1.111, max 1.318|
|1M|kll_full|4.266s|113,688 KB (~111 MB)|1,862,936 KB|geo 1.251, p90 1.166, max 9.532|geo 1.564, max 9.532|geo 1.000, max 1.003|
|5M|window|20.103s|1,093,400 KB (~1068 MB)|2,818,556 KB|geo 1.000, p90 1.000, max 1.000|geo 1.000, max 1.000|geo 1.000, max 1.000|
|5M|kll_fast|3.373s|442,104 KB (~432 MB)|2,167,888 KB|geo 2.785, p90 198.086, max 224.573|geo 6.833, max 224.573|geo 1.135, max 1.799|
|5M|kll_full|22.210s|466,308 KB (~455 MB)|2,191,748 KB|geo 1.401, p90 1.157, max 46.612|geo 1.962, max 46.612|geo 1.000, max 1.002|

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:

```Plaintext
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` can reuse them instead of rescanning all historical data.

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:

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

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

```Plaintext
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:

```Plaintext
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:

```Plaintext
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:

```Plaintext
lower_count   = cms_estimate - cms_error_bound
average_count = non_null_rows / NDV
```

It uses the CMS estimate only when:

```Plaintext
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` are distributed across 200 hot values. Top-N cannot retain all 200 values, while CMS can still estimate their frequencies.

Each result reports the median and range of three runs.

### `ANALYZE` Overhead

|Variant|Elapsed|RSS Delta|
|---|---|---|
|none|0.201s (0.193-0.279)|29.7 MiB (21.2-29.8)|
|topn|0.548s (0.517-0.931)|89.4 MiB (76.8-92.6)|
|cms|0.486s (0.429-0.502)|74.2 MiB (59.2-87.5)|
|topn_cms|0.642s (0.613-0.857)|79.0 MiB (75.5-92.6)|

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

|Variant|Geomean|P50|P90|Max|
|---|---|---|---|---|
|none|25.354|24.189|2006.822|18190.086|
|topn|4.921|1.333|250.000|250.000|
|cms|1.355|1.036|2.500|10.000|
|topn_cms|1.355|1.036|2.500|10.000|

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

|Variant|Geomean|P50|P90|Max|
|---|---|---|---|---|
|none|65.266|208.681|208.681|208.681|
|topn|30.214|129.000|250.000|250.000|
|cms|1.202|1.080|1.667|1.667|
|topn_cms|1.202|1.080|1.667|1.667|

For a representative predicate, `wide_hot_key = 0`, the actual result is 2,500 rows:

|Statistics|Estimated Rows|
|---|---|
|Top-N|10|
|CMS|2,716|
|Top-N + CMS|2,716|

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.

|Workload Characteristic|Recommended Strategy|Rationale|
|---|---|---|
|Range-heavy queries with frequent statistics refreshes|`kll_fast`|One scan, lower memory use, and stable range estimates|
|Bucket NDV and general equality accuracy matter more|`kll_full`|A second scan produces more accurate bucket statistics|
|A small number of values dominate|KLL + Top-N|Top-N records the hottest values exactly|
|The hot set exceeds Top-N capacity|KLL + CMS, or KLL + Top-N + CMS|CMS covers a wider frequency distribution|
|Distribution is close to uniform and equality filters are not critical|KLL + regular NDV|Avoid unnecessary collection overhead|

In Databend, these probabilistic structures do more than make `ANALYZE` faster. They help the optimizer build a sufficiently accurate model of large data sets while keeping background maintenance bounded. For data stored in object storage, reducing scans, sorts, and memory pressure also makes compute usage more predictable and limits interference with interactive workloads.

## 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` is effective for fast, low-memory range statistics but can produce large equality errors by itself. `kll_full` improves bucket-level accuracy without guaranteeing a shorter runtime. CMS adds limited collection overhead while substantially improving equality estimates for wide, skewed hot sets.

For an S3-native, cloud-native analytical database such as Databend, optimizer statistics are not an isolated engine feature. Lower `ANALYZE` overhead, more reliable cardinality estimates, and more stable execution plans translate directly into better query efficiency, more predictable resource usage, and clearer cost-performance trade-offs at scale.