查询引擎在选择高效的查询计划方面非常出色。用户无需担心如何编写查询语句，因为优化器会综合考虑数据的各种因素（如数据量、存储设备的特性、数据分布模式、索引的可用性等），自动做出正确的执行决策。无论查询多么复杂或编写得多么刻意，查询优化器总能做出最佳选择。至少这是我们对现代查询优化器的期望。然而，现实情况并不总是如此理想。
问题在于查询优化器存在一个致命弱点：基数估计。为了选择最优的查询执行计划，它们需要遍历多种备选方案并评估其成本；而要评估成本，优化器必须估算查询中每个子表达式返回的元组数量。如果估算错误，成本估算就会不准确，从而导致选择了一个效率低下的查询计划。当查询优化器未能选出最佳执行计划时，几乎总是由于基数估计器的信息有误。
基数估计的问题可以简单表述为：给定一个查询，无需实际执行该查询就能估算出其结果集的基数。通常，查询操作仅限于选择和连接操作，因为其他关系操作（如分组、去重、合并等）会被放在查询计划的较高级别。为了进行基数估计，系统会先对每个基表计算一些统计信息，然后在优化时利用这些信息来估算各种查询表达式的基数。这里存在两个主要挑战：首先，我们可以预先计算和存储的统计信息量非常有限，因为所有统计信息都必须在查询优化期间保留在主内存中。生产环境中通常有数百张表，每张表可能包含数百个字段，因此我们只能存储关于每张表和每个字段的少量信息；其次，基数估计必须非常快速，因为它在查询优化的核心循环中会被调用数千次。因此，无法使用磁盘访问或复杂的优化算法，基数估计必须简单高效。
陈等人发表的论文《基数估计图》（“Cardinality Estimation Graphs”）提出了一个统一的框架，涵盖了最常见的基数估计方法：基于汇总统计信息的估计方法（与基于样本的方法相对），以及基于平均度或最大度的估计方法（包括我所知道的所有估算方式）。基数估计通常包含两个独立的部分：对基表上谓词的选择性估计，以及多连接查询的基数估计。本文专门研究了后者。
多连接查询的基数估计依赖于各字段的平均度。以估算一个连接操作的规模为例：。一个合理的估计值是 乘以字段 S 的平均度；例如，如果 中的每个值在 中出现了五次，那么估计值就是 的五倍。不过我们也可以交换 和 S 的角色，用 |S 乘以 R 的平均度来作为估计值。这就引出了一个问题：应该使用哪种估计方法？数据库系统会选择两者中的较小值，从而得出我们在本科课程中常用的经典公式：。
对于一个 n 路连接查询来说，可选的基数估计方法数量非常多，很难确定哪种方法更合适。论文引入了一个称为“基数估计图”（Cardinality Estimation Graph, CEG）的抽象模型，每个路径代表基数估计器的一种可能选择。通过 CEG，论文能够解释和比较文献中描述的各种基数估计方法，并为设计新的估算方法提供了可能性。
最近提出的一种替代方法是计算基数估计的上限。这种方法被称为悲观基数估计（虽然有点误导，因为它实际上是一个保证的上限而非精确估计）。虽然已知多连接查询的上限的数学公式，但实际应用并不现实，现有的悲观估计实现大多对该公式进行了简化。论文表明，同样的 CEG 抽象模型也可以用来解释这些悲观基数估计，只需将平均度替换为最大度即可。
对于不了解基数估计的读者来说，CEG 可以作为了解各种基数估计方法的便捷快速入门工具；专家们可以利用 CEG 来比较不同的估算方法；系统开发人员则可以从实验部分中获得选择适合自己的基数估计器的参考。
这篇技术文章最初发表于 2023 年 6 月的《ACM SIGMOD Record》。
