近日，华东师范大学与 OceanBase 团队合作完成的论文《Metis: Workload-Aware Multi-Dimensional Histograms for Cardinality Estimation》被 VLDB 2027 接收。

VLDB 是国际数据库领域最具影响力的顶级学术会议之一，与 SIGMOD、ICDE 并称为数据库领域三大国际顶级会议。VLDB 2027 将于 2027 年 8 月 23 日至 27 日在希腊雅典举行。

此次被接收的论文聚焦数据库基数估计中的多维统计信息问题。

基数估计是查询优化器选择执行计划的重要基础，但传统一维直方图依赖属性独立假设，难以准确刻画多属性相关性，而直接构建高维直方图又会带来指数级的空间开销。

针对这一问题，Metis 提出面向工作负载的多维直方图方法，从历史查询反馈中识别真正影响估计准确性的属性相关性，并围绕“选对属性、建好统计、灵活使用”三个关键环节进行系统设计。

图 1. Metis 流程图

核心技术一：基于查询误差的属性组合选择

传统方法通常根据数据本身的相关性选择需要联合建模的属性，但“数据相关”并不意味着“对当前查询负载有价值”。

Metis 引入 workload-imperative correlation，即优先关注那些“缺少联合建模时，会持续导致较大基数估计误差”的属性相关性。

设计核心：Error-Based Correlation Graph + ILP

图 2. 从查询误差中构建误差关联图 CoG

Metis 根据历史查询的 Q-error 构建误差关联图 CoG。图中的节点表示属性，边表示两个属性在历史查询里共同出现，边权则累积这些查询产生的估计误差。

在此基础上，Metis 将属性子集选择建模为一个带存储预算约束的 0-1 整数规划问题，在有限空间内优先覆盖高价值属性相关性。

此外，每构建一张新的多维直方图后，Metis 会重新估计历史查询并更新 CoG，使后续统计信息继续聚焦于尚未解决的主要误差来源。

核心技术二：基于查询反馈的多维直方图构建

传统方法要么需要反复扫描原始数据，构建开销较高；要么只能有效利用被直方图完整覆盖的查询，大量部分覆盖查询中的反馈被浪费。

Metis 的核心思想是：将完整覆盖和部分覆盖查询中的反馈都转化为概率约束，并联合求解这些约束来恢复多属性联合分布。

设计核心：Projection-Aware Constraint Derivation

图 3. 等式、下界和边际约束构建

Metis 将不同来源的信息转化为三类概率约束，用于恢复多维直方图中的联合分布：

• Equality Constraint：对于被当前直方图完整覆盖的查询，其真实选择率可以直接约束对应查询区域的概率。

• Lower-Bound Constraint：对于只被部分覆盖的查询，Metis 将它们投影到当前属性空间。投影会放宽查询条件，因此这些查询的真实选择率可以为投影区域 (g) 提供概率下界。

• Marginal Constraint：数据库已有的一维统计信息提供各属性区间的边际概率，用于约束多维直方图在对应区间上的概率总和。

最终，Metis 联合求解三类约束，得到各个直方图桶的概率，从而恢复所选属性的联合分布。

核心技术三：基于共享属性的多直方图联合推理

当一条查询涉及的属性无法被单个多维直方图完整覆盖时，就需要组合多个直方图进行估计。

传统方法通常要求所有多维直方图预先组织成固定的全局结构，这会限制高价值属性组合的构建，并可能拉长推理路径。

Metis 的核心思想是：不预先固定全局结构，而是在查询到来时，根据当前查询动态选择最合适的多维直方图，并通过共享属性将它们连接起来。

设计核心：Shared-Attribute-Driven Selection + Query-Specific Factor Graph

Metis 优先选择与已选直方图共享更多属性的候选，使这些共享属性充当条件变量，从而提供更充分的条件信息、减少额外的条件独立假设。随后，所选直方图被组织成当前查询专属的因子图，并通过概率推理得到最终基数估计。

总结

Metis 围绕多维直方图的选择、构建和应用三个关键环节，形成了一套完整的 workload-aware 基数估计框架：

利用历史估计误差识别真正值得建模的属性相关性，充分挖掘查询反馈恢复联合分布，并在查询到来时灵活组合多张多维直方图，从而在准确性、效率与可部署性之间取得良好平衡。

立即试用 OceanBase 企业版，体验国产数据库能力 180 天免费试用，零门槛开通