目录一、从代数优化到物理计划代价估算的必要性二、统计信息代价估算的数据地基三、选择率估计从等值到范围的逐步推广四、直方图对抗数据分布的偏斜五、代价模型将行数转化为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₂ SS₁ ∩ S₂ ∅计算将S₁的最优方案与S₂的最优方案连接的代价选择总代价最低的连接方式和连接次序。这一代价包括S₁的生成代价、S₂的生成代价、以及两者连接的代价。连接方式的搜索包括嵌套循环、哈希连接和归并连接优化器对每种方式估算代价选择最低者。最终算法输出包含全部表的最优连接方案。动态规划保证了在搜索空间完备的前提下找到最优解其时间复杂度为O(3^n)空间复杂度为O(2^n)。对于10到15个表的连接这个复杂度在可接受范围内。当涉及数十个表的复杂查询时优化器会引入启发式剪枝或转向遗传算法等随机搜索策略。动态规划在理论上保证了最优性但其最优性只针对代价模型的最优。如果代价模型本身因统计信息偏差而给出错误的代价排序动态规划将忠实地选择那个在错误模型下最优、在现实中次优甚至糟糕的物理计划。代价估算的错误在连接次序优化中被逐层放大——底层选择率估计的微小偏差经过多表连接代价的连锁计算可能使最终选出的计划与实际最优计划相差悬殊。七、结语优化器的有限理性代价估算模型与执行计划选择机制构成了查询优化器的理性决策层。优化器不是凭借经验规则做选择而是基于统计信息、直方图和代价模型进行量化计算以动态规划算法系统性地搜索最优方案。从System R时代至今这套框架的基本结构保持了四十余年的稳定——这充分证明了其设计的深刻与有效。但优化器的理性是有限的。统计信息可能过时均匀分布假设可能被违背独立性假设可能不成立IO代价的权重可能不匹配实际硬件。当这些前提条件失效时优化器的精心计算可能产出偏离现实的最优方案。对于数据库使用者和管理员而言理解代价估算模型的内部机制不是为了替代优化器做决策而是为了在优化器做出次优选择时——这偶尔会发生——能够通过查看执行计划、更新统计信息、调整查询书写方式或添加优化器提示来引导它重回正轨。下一篇我们将从查询执行转向数据库系统最核心的可靠性机制之一——事务管理。ACID属性中的原子性、一致性、隔离性与持久性如何通过日志、锁与快照在充满故障与并发的真实世界中得到保证。