【数据库系统原理】第24篇：代价估算模型与执行计划的选择
目录
一、从代数优化到物理计划：代价估算的必要性
二、统计信息：代价估算的数据地基
三、选择率估计：从等值到范围的逐步推广
四、直方图：对抗数据分布的偏斜
五、代价模型：将行数转化为IO与CPU
六、动态规划与连接次序优化
七、结语：优化器的有限理性
一、从代数优化到物理计划：代价估算的必要性
上一篇我们探讨了查询优化器的代数优化阶段——选择下推、投影下推与连接顺序重排，在不改变查询语义的前提下，将逻辑查询计划树重写为中间结果规模更小的等价形式。然而，代数优化只能提供逻辑层面的“更小中间结果”这一方向性指导，它无法回答一组更具体、更决定性的问题：当过滤条件可以走索引扫描也可以走全表扫描时，哪一种更快？当两张表需要连接时，用嵌套循环、哈希连接还是归并连接？当涉及多表连接时，以什么顺序执行连接操作总代价最低？
回答这些问题的能力，是逻辑查询计划与物理执行计划之间的分水岭。代数优化后的逻辑计划树仍然使用抽象的关系代数运算符——σ、Π、⋈——而不指定每个运算符的具体执行算法。物理计划生成阶段的任务，就是为每个逻辑运算符选择具体的执行算法，为每个基表选择具体的存取路径，并确定连接操作的执行顺序。这个阶段做出的决策，直接决定了查询在物理层面的IO次数和CPU时间。
不同的物理计划在代价上可能相差数个数量级。选择全表扫描意味着读取一个表的全部数据页，选择索引扫描则可能只读取少数几个索引页加几个数据页。选择嵌套循环连接意味着对两张表进行双重遍历，选择哈希连接则只需单次遍历外加构建哈希表。这些选择不能凭直觉做出，必须基于量化的代价估算。
代价估算的输入是统计信息，输出是估计代价。统计信息告诉优化器每个表有多少行、每个列有多少种不同的取值、数据值的分布形态如何。代价模型则将这些信息翻译为IO次数、CPU操作次数，最终汇总为一个可比较的总代价数字。优化器选择总代价最低的物理计划作为最终的执行计划。
二、统计信息：代价估算的数据地基
代价估算的准确性首先取决于统计信息的完整性与新鲜度。数据库管理系统的数据字典中维护着一组用于查询优化的统计信息，它们通常在表发生显著变化后通过ANALYZE命令或自动后台任务更新。
表级统计信息包括：表的行数（基数）、表占用的数据页数、表的平均行长度。行数和页面数是估算全表扫描代价的基础——全表扫描的IO次数约等于表的页面数（在行存模型下）。
列级统计信息包括：列的不同值数量（NDV，即基数）、列中NULL值的比例、列的平均长度。列基数直接决定了等值查询的选择率——如果列上有索引且查询条件为等值，优化器估计选择率为1/NDV。列基数也影响连接结果的估算——连接列的基数决定了连接后的行数。
索引统计信息包括：索引的层级数（B+树高度）、索引占用的叶子页数、索引键值的聚簇因子。聚簇因子衡量索引键值的逻辑顺序与表中行的物理存储顺序的一致程度——聚簇因子越低（越接近表的页面数），通过索引进行范围扫描的效率越高，因为相邻键值的行大概率位于同一个数据页中；聚簇因子越高（越接近表的行数），范围扫描可能引发大量随机IO。
这些统计信息的准确性依赖于及时更新。当一张表经过大量的插入、删除或更新操作后，其实际行数和数据分布可能与最后一次统计信息更新时大相径庭。优化器如果基于过时的统计信息做出代价估算，可能错误地选择全表扫描（当实际行数远小于统计行数时）或错误地选择索引扫描（当实际行数远大于统计行数时）。数据库管理员必须将统计信息维护纳入日常运维计划。
三、选择率估计：从等值到范围的逐步推广
选择率是代价估算中最核心的中间变量。一个选择操作的选择率，定义为满足该选择条件的元组数占输入关系总元组数的比例。选择率决定了选择操作的输出行数，进而影响上游操作的数据量和代价。
对于等值条件——WHERE 列 = 常量——在没有任何额外信息的情况下，优化器假设列的值均匀分布，选择率估算为1/NDV。如果列的NDV为100，则选择率为1%。这个假设极其朴素，但也是最危险的——当数据分布严重不均匀时，1/NDV可能产生数量级的偏差。例如，一个“城市”列有100个不同取值，但50%的记录集中在“北京”，等值查询“北京”的实际选择率是50%，而非1%。
对于范围条件——WHERE 列 > 常量或WHERE 列 BETWEEN A AND B——均匀分布假设下的选择率可以通过常量在值域中的位置来估算。例如，列的取值范围为[1, 1000]，条件列 > 900的选择率约为10%。但同样，如果数据在高端密集分布，实际选择率可能远超10%。
对于多条件组合——WHERE A = a AND B = b——如果A和B在统计上相互独立，组合选择率为各自选择率的乘积。独立性假设是优化器中最常使用也最常被违背的假设——现实数据中列之间往往存在关联（例如“城市”和“邮政编码”、“年龄”和“收入”），独立性假设可能导致选择率估计偏差数十倍。
对于连接选择率——R⋈S——在均匀分布和无相关性假设下，等值连接的结果行数估算为|R|×|S| / max(NDV(R.A), NDV(S.A))。直觉解释是：R中的每一行在S中平均找到|S|/NDV(S.A)个匹配行，或者反过来。
四、直方图：对抗数据分布的偏斜
均匀分布假设在真实数据面前常常脆弱不堪。直方图技术正是为了捕捉数据分布的不均匀性而引入的。直方图将列的值域划分为若干个连续的桶，每个桶记录该区间的行数或不同值数量，使优化器能够根据目标值落入的桶来更精确地估计选择率。
等宽直方图将值域均匀划分为等宽的区间。构造简单，但在数据分布极不均匀时效果不佳——高频值所在的桶可能包含绝大多数的数据行，桶内的分布假设（通常仍是均匀假设）会导致估算偏差。
等高直方图是目前主流数据库系统普遍采用的技术。它将数据按值排序后划分为行数大致相等的桶，每个桶的宽度不必相同。高频值所在的桶宽度窄（因为少量不同值就占据了大量行），低频值所在的桶宽度宽（因为大量稀疏值才凑满一个桶的行数配额）。查询时，优化器根据目标值落入的桶，结合桶内值的分布情况估算选择率。等高直方图能够有效捕捉数据偏斜，对频繁值的选择率估计精度显著优于等宽直方图和朴素均匀假设。
除了直方图，优化器还可能维护最常见值列表——对出现频率最高的若干个值单独记录其精确行数，绕过直方图的近似估算。对于等值查询涉及高频值的场景，最常见值列表提供了接近精确的选择率估计。
五、代价模型：将行数转化为IO与CPU
选择率估算提供了每个操作的输出行数。代价模型则将这些行数转化为量化代价——主要是磁盘IO次数和CPU操作次数，有时还包括网络传输代价（在分布式数据库中）。
IO代价是传统代价模型的核心。一次磁盘IO定义为读取或写入一个数据页（通常为4KB至16KB）。全表扫描的IO代价等于表的页面数。索引扫描的IO代价等于索引树从根到叶的遍历页面数（通常为索引高度，即2到4个页面）加上数据页的访问次数。数据页访问次数取决于需要回表的行数以及这些行在物理存储上的聚集程度——如果行在数据页中紧密聚集，访问少数几个页面即可覆盖；如果行分散在大量页面中，每次回表都可能是独立的随机IO。
CPU代价衡量在内存中对数据行执行比较、运算和复制的开销。单个元组的CPU代价远低于一次磁盘IO——通常相差三到四个数量级。因此，在IO密集型的传统查询中，CPU代价常被简化为IO代价的线性加成。但在纯内存查询或分析型查询（大量表达式计算、聚合函数）中，CPU代价可能成为主导因素，现代代价模型对CPU代价的建模颗粒度日趋细化。
代价模型通过将IO代价和CPU代价加权求和，为每个物理操作赋予一个总代价值。不同数据库系统使用不同的权重参数，这些参数通常由数据库厂商根据基准测试预设，有经验的数据库管理员也可以根据硬件配置进行调整。
代价模型面临的一个深层挑战是：同一个查询的真实代价高度依赖于运行时的系统状态——缓冲池中已有多少所需页面、磁盘当前的并发队列长度、系统是否正在进行检查点操作。代价模型在计划生成时只能基于统计平均值进行估算，无法精确预知运行时的瞬时状态。这也是为什么同一个执行计划在冷启动（缓冲池为空）和热启动（所需页面已在内存）时的实际执行时间可能相差数量级。
六、动态规划与连接次序优化
多表连接的次序选择是代价估算模型最复杂的应用场景。n个表的连接有Catalan(n-1)种可能的连接顺序，枚举全部顺序在n稍大时即不可行。系统需要一种能在有限时间内找到最优或近似最优方案的搜索算法。
动态规划是System R项目在1979年提出的经典解法，至今仍为主流数据库系统所沿用。其核心思想是将多表连接优化分解为具有最优子结构的一系列子问题。
动态规划算法自底向上构建最优方案。初始阶段，为每个基表估算单表扫描的代价，包括全表扫描和各种可用索引扫描的代价，保留代价最低的存取路径和对应的物理计划。
后续阶段逐层构建越来越大的表子集的连接方案。对于子集S，算法遍历S的所有二划分S₁和S₂（S₁ ∪ S₂ = S，S₁ ∩ S₂ = ∅），计算将S₁的最优方案与S₂的最优方案连接的代价，选择总代价最低的连接方式和连接次序。这一代价包括S₁的生成代价、S₂的生成代价、以及两者连接的代价。连接方式的搜索包括嵌套循环、哈希连接和归并连接，优化器对每种方式估算代价，选择最低者。
最终，算法输出包含全部表的最优连接方案。动态规划保证了在搜索空间完备的前提下找到最优解，其时间复杂度为O(3^n)，空间复杂度为O(2^n)。对于10到15个表的连接，这个复杂度在可接受范围内。当涉及数十个表的复杂查询时，优化器会引入启发式剪枝或转向遗传算法等随机搜索策略。
动态规划在理论上保证了最优性，但其最优性只针对代价模型的最优。如果代价模型本身因统计信息偏差而给出错误的代价排序，动态规划将忠实地选择那个在错误模型下最优、在现实中次优甚至糟糕的物理计划。代价估算的错误在连接次序优化中被逐层放大——底层选择率估计的微小偏差，经过多表连接代价的连锁计算，可能使最终选出的计划与实际最优计划相差悬殊。
七、结语：优化器的有限理性
代价估算模型与执行计划选择机制，构成了查询优化器的理性决策层。优化器不是凭借经验规则做选择，而是基于统计信息、直方图和代价模型进行量化计算，以动态规划算法系统性地搜索最优方案。从System R时代至今，这套框架的基本结构保持了四十余年的稳定——这充分证明了其设计的深刻与有效。
但优化器的理性是有限的。统计信息可能过时，均匀分布假设可能被违背，独立性假设可能不成立，IO代价的权重可能不匹配实际硬件。当这些前提条件失效时，优化器的精心计算可能产出偏离现实的最优方案。对于数据库使用者和管理员而言，理解代价估算模型的内部机制，不是为了替代优化器做决策，而是为了在优化器做出次优选择时——这偶尔会发生——能够通过查看执行计划、更新统计信息、调整查询书写方式或添加优化器提示来引导它重回正轨。
下一篇，我们将从查询执行转向数据库系统最核心的可靠性机制之一——事务管理。ACID属性中的原子性、一致性、隔离性与持久性，如何通过日志、锁与快照在充满故障与并发的真实世界中得到保证。