导读

本文基于ByteBrain团队实际生产场景，提出一项新的研究问题，即如何在无数据访问条件下，从不完美的查询工作负载中学习一个具备泛化能力与鲁棒性的基数估计模型；同时提出创新技术方案 GRASP（Generalizable and Robust, data-AgnoStic cardinality Prediction） ，借助组合式设计（Compositional Design）解决这一颇具挑战性的问题。论文目前已经被VLDB25接收。

论文标题：Data-Agnostic Cardinality Learning from Imperfect Workloads

论文作者：Peizhi Wu, Rong Kang, Tieying Zhang*, Jianjun Chen, Ryan Marcus, Zachary G. Ives，其中，第一作者Peizhi Wu为宾夕法尼亚大学在读博士，其论文工作是在ByteBrain团队实习期间完成的。通讯作者Tieying Zhang为ByteBrain团队负责人

论文地址：https://arxiv.org/abs/2506.16007

项目地址：https://github.com/shoupzwu/GRASP

背景

在数据库管理和数据库系统领域，基数估计（Cardinality Estimation, 也就是预测查询的返回行数）是个重要的研究课题。因为准确的基数估计是关系型数据库查询优化的必要条件，也是索引推荐的关键因素。随着大数据技术发展，处理海量数据时，快速又准确的基数估计方法非常重要。

在现有的基数估计研究里，已经提出并广泛应用了多种技术。这些技术主要有：

1. 基于数据驱动的方法：这类方法要对数据库的所有数据进行扫描，通过构建不同的数据模型（像直方图、sketches）来对查询做基数估计。
2. 基于查询工作负载 (Query Workload) 驱动的方法：这类算法要利用历史查询工作负载（就是历史执行过的查询和对应的真实基数）来构建机器学习模型，从而对未来的查询进行基数估计。

现有的基于数据驱动的方法需要直接访问数据库实例的数据。但在实际生产环境中，常常由于数据隐私、组织权限隔离或法规限制，无法直接访问底层数据。这使得传统依赖数据统计（如直方图、样本）的估计方法难以适用。另一方面，基于查询工作负载的方法能避免用户数据隐私问题，但现有的技术方案都要求有完美的工作负载。完美的工作负载指的是历史查询工作负载里包含所有可能的连接模版，而且分布均匀。但在实际查询工作负载中，连接模版往往不完整，分布也不均衡，并且查询谓词的分布可能会随时间变化。

目标

本文目标是在无数据访问的约束下，从从实际工作负载上构建准确的基数估计模型。

同时，从实际工作负载上构建基数估计模型往往具有三大挑战：

1. Join 模板不完备（仅覆盖部分表连接形式）；
2. Join 模板严重不平衡（某些模板出现频率极低）；
3. 谓词值分布随时间发生漂移。

因此，我们定义了一个新问题：在无数据访问约束下，如何从不完美的查询工作负载中学习一个具有泛化能力和鲁棒性的基数估计模型。

训练数据

构建阶段以以下输入为基础：

• 数据库模式（Schema）；
• 历史工作负载，即历史查询及其真实基数标签；
• 各基表的行数（表级基数信息，非敏感）。

组合式设计

如图二所示，不同于现有方法对每个join模板训练一个独立的模型或者用一个模型处理所有的join模版，本发明提出了利用join的结构关系来训练不同但是相互关联的模型。该设计显著增强了模型对未见 join 模板（Unseen Join Templates）的泛化能力，大大提升了实用性和扩展性。此外，由于各join模板复用相同的基础模型，GRASP天然支持从高频 join 模板中获得泛化能力，并迁移至低频模板，解决训练样本不均问题。

具体地，在此阶段，本发明通过深度神经网络为每个单表（base table）训练两类关键基础模块：

• 表级基数预测模型（CardEst） ：用于估计每个子查询（如 select + predicate）的表级基数。

• Learned Count Sketch 模型（LCS） ：用于建模各表 join key 分布的低维分布向量。

对于任意输入查询，其中包括多表联合查询 (join query)：

1. 按联合查询所对应的join 模板解析其组成表 (base tables)。

   例如：联合查询“SELECT * FROM A, B WHERE A.key = B.key AND A.a > 5 AND B.b < 10”包含两个组成表，即表A和表B。

2. 将联合查询拆分成各个组成表上的子查询 (subquery)，例如上述联合查询可被拆分成两个分表在表A和表B上的子查询:

   a. SELECT * FROM A WHERE A.a > 5;
   b. SELECT * FROM B WHERE B.b > 10;

3. 调用对应的 CardEst 模型预测每个子表的基数。

     CardEst 模型输入是一个在单一关系表上 (base table) 的包含多维谓词的查询，输出是基数 (cardinality)，也即这张表上的满足给定谓词的数据行数。

4. 调用组成表对应的 LCS 模型生成子查询中连接键（join key）分布对应的低维计数草图（count sketch），后文将会介绍 LCS 模型的模型架构。

5. 利用不同子表的低维计数草图（Count Sketch）向量内积（dot product）结果，并结合每个子表上CardEst模型的预测结果，对最终连接查询的基数进行估计。具体示例可参考图一。

图一： GRASP估计联合查询基数的例子

图二：GRASP的组合式设计 vs 现有工作

训练目标为最小化基数估计误差（如对数平方误差 SLE）。所有模块均为可微结构，支持端到端优化。

ArCDF: Autoregressive CDF Modeling

图三:  ArCDF模型利用deep autoregressive model来自回归地预测段单调样条 (monotonic rational-quadratic splines)的参数

对于针对数值型属性的范围查询（范围谓词），GRASP的CardEst板块采用了创新的ArCDF（如图三所示）来预测基数。ArCDF首先将范围查询转换为其上界和下界的线性组合，然后运用ArCDF模型来预测所有上下界的累积分布函数（CDF）。具体而言，将谓词转换为上界和下界，输入ArCDF，获取所有上界和下界的CDF估计值，通过作差得到基数：card = rows * [CDF(up) - CDF(down)]。这保证了预测基数的单调性和非负性，即使在谓词值分布变化（如滑动窗口、区间变更）时，仍能保持鲁棒的估计性能。

ArCDF沿用了本专利之外的前人工作NeuroCDF [1]，但进行了关键改进，引入了自回归建模，模型结构如图三。其输入是对应单表上每个属性的值，ArCDF利用深度自回归模型来对所有属性的CDF的联合分布进行建模，其计算公式如下图所示：

并且ArCDF在每个属性上使用 monotonic rational-quadratic splines 函数来建模CDF，以确保CDF在每个维度上具有局部单调递增的特性，降低负基数估计出现的可能性。

[1]. Peizhi Wu, Haoshu Xu, Ryan Marcus, Zachary G. Ives. A Practical Theory of Generalization in Selectivity Learning. VLDB 2025.

Learned Count Sketch模型

图四：Learned Count Sketch (LCS) 模型架构

因此，连接的关联性（join correlations, 通常通过其组成表上子查询的连接键分布进行向量内积运算获得）可通过低维计数草图进行向量内积（dot product）近似计算。

传统方法需要在数据预处理阶段通过扫描全量表数据生成静态计数草图，而本文提出了查询驱动的LCS模型（模型结构如图四所示） ，利用神经网络直接依据输入查询动态预测查询结果中连接键分布对应的计数草图向量。 如果其包含多个连接键，LCS模型则对每个连接键输出其对应的低维计数草图（count sketch）。通过神经网络直接根据查询结构动态生成 count sketch 向量，支持端到端训练并与 CardEst 协同优化。

实验与结果

1.显著提升基数估计准确度（更准的预测结果）

通过组合式的建模设计与更强的模型表达能力（包括表级估计模块和基于学习的 Count Sketch 模块），GRASP能对从未见过的 join 模板、长尾查询结构以及谓词值偏移情况做出更准确的估计。预测准确度实验结果如下图所示，在不访问底层数据的前提下，GRASP在多个实际和标准基准上（如CEB-IMDb、DSB等）实现了与传统基于数据统计方法相当甚至更优的预测准确度，尤其在查询模板覆盖率低至10%的情况下依然保持稳定性能。

2.有效提升查询优化质量（更优的执行计划）

由于查询优化器高度依赖基数估计值来选择执行计划，准确的基数预测直接影响最终查询性能。GRASP提供更鲁棒的基数估计后，能有效避免常见的执行计划错误（如错误的连接顺序、索引误选等），从而提升整个查询执行效率。如下图所示，在实验中，GRASP在无数据访问条件下，仍能在多个 benchmark 上显著减少查询延迟，体现出实际系统部署中的优化能力和商业价值。

ByteBrain团队介绍

ByteBrain是字节跳动 AI for Infra / AI for System服务平台，旨在利用 AI技术（机器学习、大模型、运筹优化等），对基础架构和系统的全生命周期进行自动优化。优化对象包括：数据库、存储、大数据系统、虚机、容器、网络、运维和稳定性等。ByteBrain 的主要方向为AIOPS、AI4DB、运筹优化、LLM4Infra，功能模块包括容量规划、资源调度、系统调参、异常检测、根因分析、慢SQL优化、Text2SQL、LLM-AGENT 等。ByteBrain团队正在招聘相关方向的研究员和实习生，联系方式：[email protected]

原文始发于微信公众号（字节跳动技术团队）：ByteBrain团队VLDB25 | 面向不完美工作负载的无数据访问基数估计方法