从全表排序到概率统计：Databend 如何用 KLL、Top-N 与 CMS 改进基数估计

为什么统计信息同时关乎性能与成本

SQL 查询进入数据库后，优化器需要估算不同执行计划的成本，再决定 JOIN 顺序、扫描方式和算子组合。基数估计是这一过程的基础：如果优化器错误判断某个过滤条件会返回多少行，即使执行引擎本身足够快，也可能选出代价很高的计划。

直方图（Histogram）是描述列值分布的常用统计结构。相比等宽直方图（Equi-width Histogram），等深直方图（Equi-depth Histogram）让每个桶包含大致相同数量的行，因此在存在数据热点和倾斜时，通常能提供更稳定的估计。

但准确的统计信息并不是免费的。传统方式通常需要扫描、排序并聚合整列数据。在 Databend 这类面向大规模分析、采用存算分离架构的云数据仓库中，

ANALYZE

如何在不承担全局排序成本的前提下，获得足以支撑优化器决策的统计信息？

Databend 使用 KLL、Top-N 和 CMS 处理这个问题。三者并非互相替代，而是分别描述数据分布的不同部分。

直方图如何支持基数估计

先看一个简化的范围查询。

CREATE TABLE employee (
    id INT,
    salary INT
);

假设

salary

对于查询：

SELECT *
FROM employee
WHERE salary < 5000;

B1 和 B2 被完全覆盖，B3 只覆盖了部分范围。若假设桶内数据均匀分布，则估算结果为：

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

直方图通过桶边界近似描述全局分布。但要得到完全准确的等深桶边界，传统实现往往需要完成一次全表扫描、全局排序和聚合：

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

随着数据量增长，全局排序会成为

ANALYZE

KLL：用一次扫描近似数据分位点

KLL（Karnin-Lang-Liberty Sketch）是一种近似计算分位数（Quantile）的流式摘要算法。它只需要顺序读取数据，并将有限数量的样本压缩为可合并的 Sketch。

KLL 的可合并性非常适合 Databend 的分布式执行模型：不同计算节点可以并行构建局部 KLL，再将结果合并为全局 Sketch，最后查询各个分位点并生成等深桶。

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

这条路径将“全表扫描 + 全局排序 + 聚合”简化为“一次扫描 + Sketch 合并”。对于需要频繁刷新统计信息的大表，它可以显著降低内存占用，并减少统计收集对业务查询的资源干扰。

KLL 还需要 NDV

KLL 能计算分位点和桶边界，但不能直接给出每个桶的 NDV（Number of Distinct Values，不同值数量）。而 NDV 又直接影响等值谓词的估计精度。

Databend 在第一次

ANALYZE

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

KLL 根据 rank 推算每个等深桶的行数

bucket_values

bucket_ndv = column_ndv × bucket_values / total_values

结果被限制在以下范围：

1 ≤ bucket_ndv ≤ bucket_values

例如：

总行数       = 10,000
全列 HLL NDV = 1,000
桶数         = 100
每桶行数     ≈ 100

这种估算开销低，但隐含了“不同值在各个桶中按行数比例分布”的假设。数据倾斜越明显，等值查询的估计误差就越可能增大。

kll_fast

与

kll_full

：在速度和精度之间选择

Databend 提供两种基于 KLL 的

ANALYZE

• kll_fast
  

  ：执行一次扫描，使用整列 HLL NDV 按比例估算各桶 NDV。

• kll_full
  

  ：先用 KLL 确定桶边界，再执行第二次扫描，统计每个桶的实际行数与 HLL NDV。

kll_full

第一遍扫描：

数据 → KLL Sketch → 近似分位点 → 固定桶边界

第二遍扫描：

数据 → 根据桶边界分桶 → 每桶单独统计 Count 和 HLL NDV

每个桶维护以下状态：

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

第二遍扫描每读到一个值，就寻找第一个满足以下条件的桶：

value <= bucket.routing_upper_bound

然后更新桶的行数和 NDV：

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

与此同时，Databend 还会更新该桶实际观察到的最小值和最大值。最终桶 NDV 来自：

bucket.ndv.count()

kll_full

window

为什么桶级 NDV 会影响等值查询

继续使用

salary

对于等值谓词：

SELECT *
FROM employee
WHERE salary = 4500;

4500 位于 B3。B3 包含 250 行和 150 个不同值。假设桶内数据均匀分布：

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

再看另一个查询：

SELECT *
FROM employee
WHERE salary = 1500;

1500 位于 B1：

Estimated Rows = 250 / 50
               = 5

虽然 B1 和 B3 的行数相同，但不同的 NDV 会产生不同的平均频率：

因此，范围谓词主要依靠桶边界和覆盖比例；等值谓词则更依赖桶内 NDV。KLL 很适合描述整体值域和分位点，但仅靠 KLL 与 NDV 仍无法识别桶内的热点值。

Benchmark：KLL 节省了什么，又牺牲了什么

下面比较传统

window

kll_fast

kll_full

结果体现出三个清晰的取舍：

1. kll_fast
   

   显著缩短了

   ANALYZE
   

   时间。 在 1M 和 5M 数据集上，它分别约为

   window
   

   耗时的 20.5% 和 16.8%，同时明显降低内存增量。

2. kll_fast
   

   对范围谓词较稳定，但不适合单独承担等值估计。 两组测试中的 Range q-error geomean 分别为 1.111 和 1.135，而 Eq q-error geomean 上升到 5.236 和 6.833。

3. kll_full
   

   改善了整体和等值估计精度，但时间优势并不成立。 它的内存增量低于

   window
   

   ，范围估计几乎保持准确；不过第二次扫描使其耗时略高于

   window
   

   ，极端等值谓词仍可能存在明显误差。

这说明 KLL 解决的是直方图构建的资源问题，而不是所有数据倾斜问题。要准确处理高频值，还需要 Top-N 和 CMS。

Top-N：精确记录最重要的热点值

Top-N 用于保存单列中出现频率最高的一组值及其对应行数。与在全表层面一次性计算不同，Databend 采用分层采集和合并：

Block 局部 Top-N
        │
        ▼ Merge
Segment / Source 局部 Top-N
        │
        ▼ Merge
Analyze Sink
        │
        ▼
表快照级、按列全局 Top-N

Block 级 Top-N 会保存在 Segment Statistics 中，可在增量

ANALYZE

当等值谓词命中 Top-N 时，优化器可以直接使用记录的频率，避开“桶内均匀分布”这一假设。它对少量、稳定且非常突出的热点尤其有效。

Top-N 的边界也很明确：可保存的值数量有限。如果热点值很多、频率分布较宽，一些实际高频值可能被截断在 Top-N 之外。

CMS：以固定空间覆盖更宽的热点集合

Count-Min Sketch（CMS）是一种估计元素频率的概率数据结构。它使用多个 Hash 函数将输入值映射到二维计数器数组：

hash(value, row0) → counter++
hash(value, row1) → counter++
...
hash(value, row4) → counter++

查询某个值的频率时，CMS 取多个计数器中的最小值：

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

因为 Hash 冲突只会让计数增大，所以 CMS 给出的是带上界偏差的近似频率。它使用固定空间，且和 KLL 一样支持分布式合并：

Block CMS
    │
    ▼ Counter-wise Add
Segment / Source CMS
    │
    ▼ Counter-wise Add
Table Snapshot CMS

相比 Top-N，CMS 能覆盖更广的值集合，尤其适合“热点数量超过 Top-N 容量”的场景；代价是结果不再完全精确，并且需要控制 Hash 冲突产生的噪声。

Databend 如何组合 Top-N、CMS 与普通估计

Databend 对等值谓词采用分层的估计策略：

Top-N 精确命中
        │ 未命中
        ▼
CMS 频率估算
        │ 不适用
        ▼
Top-N 带误差估算
        │
        ▼
普通 NDV / 直方图估算

CMS 不会无条件覆盖普通估计。优化器首先计算：

lower_count  = cms_estimate - cms_error_bound
average_count = non_null_rows / NDV

只有满足以下条件时：

lower_count > average_count

优化器才认为该值确实比平均频率高，并采用 CMS 结果。对于普通低频值，仍然使用常规 NDV 或直方图估算，从而避免 CMS 的碰撞噪声放大误差。

这一组合背后的思路是：

• KLL 描述整体值域与分位点；

• Top-N 精确保存最突出的热点；

• CMS 覆盖 Top-N 容量之外的宽热点；

• NDV 和直方图继续处理普通值。

Benchmark：CMS 如何修正 Top-N 漏掉的热点

测试数据包含 100 万行、10 万 NDV，Top-N 大小为 50，CMS 错误率为 0.001。

wide_hot_key

以下结果为三次重复实验的中位数和范围。

ANALYZE

开销

启用 Top-N 或 CMS 会增加统计收集时间与内存，但整体开销仍处于亚秒级。是否值得承担这部分成本，需要结合等值过滤在真实工作负载中的重要程度判断。

全部等值谓词的 q-error

仅使用普通统计信息时，等值谓词 q-error 的几何平均值为 25.354；启用 CMS 后下降到 1.355，P90 从 2006.822 降至 2.5。Top-N 能明显改善最突出的热点，但面对更宽的热点集合，CMS 的覆盖更完整。

wide_hot_key

的 q-error

以代表性的

wide_hot_key = 0

这个结果揭示了 Top-N 的容量限制：当 200 个热点竞争 50 个位置时，某些热点会被漏掉；CMS 虽然是近似估计，却能把结果从 10 行修正到接近真实值的 2716 行。

如何为不同工作负载选择统计策略

没有一种统计方式能同时取得最低开销和最高精度。更合理的选择取决于查询模式与数据分布。

kll_fast

kll_full

在 Databend 中，这些概率数据结构的价值不只是让

ANALYZE

总结

KLL、Top-N 和 CMS 分别解决了基数估计中的三个不同问题：

• KLL 以一次扫描和可合并 Sketch 近似分位点，降低等深直方图构建的排序与内存开销。

• Top-N 精确记录最常见值，修正直方图对突出热点的估计。

• CMS 用固定空间覆盖更宽的热点集合，弥补 Top-N 容量有限的问题。

Benchmark 也说明了它们的边界：

kll_fast

kll_full

对 Databend 这样的云原生分析数据库而言，优化器统计不是一个孤立的内核功能。更低的

ANALYZE