优化器与代价模型

• 选择率（selectivity）与基数（cardinality）的估算
• 物理代价（CPU、IO、网络）的加权与标定
• 代价模型误差的来源与回归校准

CBO 通过估算每个算子的代价并选择总代价最小的执行计划。其核心输入是选择率（selectivity，谓词过滤后保留行数的比例）和基数（cardinality，操作输出行数估计），它们由统计信息（直方图、采样、唯一值数）推导。在此基础上，代价模型把各类物理操作量化：CPU 代价（每行/每算子的处理成本）、IO 代价（读页/读盘次数）、网络代价（MPP 中跨节点传输的字节量），每类乘以对应的标定权重（如磁盘 IO 的权重远高于内存计算）后求和，得到算子与计划的代价。为让模型贴合实际硬件，代价权重需要做硬件标定（用基准测试测出各操作的真实耗时），并可用真实执行结果做回归校准，减少模型与实际的偏差。

CBO 的准确性取决于"基数/选择率估计"与"物理代价标定"两者，前者决定算子输入规模，后者决定单位成本，任一不准则整体代价误导。

• DP 保证最优但指数级、限于中小 join 数
• GA 启发式、可扩展但非最优
• Volcano/Cascades 用 memo 结构 + 动态规划在规则空间内搜索，兼顾最优与可扩展

Join 顺序优化的目标是找到代价最小的连接顺序。动态规划（DP）枚举所有可能的连接顺序并利用最优子结构，能保证全局最优，但状态数随表数指数增长，只适用于中小规模（通常十几个表以内）。遗传算法（GA）用启发式进化逼近最优解，可扩展到大量表，但不保证最优，易陷入局部最优。Volcano/Cascades 框架把逻辑规则与物理实现分离，用 memoization 结构（memo + group）缓存子计划，在保证一定最优性的同时通过剪枝、上界控制缩小搜索空间，能在可接受时间内找到接近最优的计划，是不少查询优化器（如 Calcite 的 VolcanoPlanner）的常用做法。工程取舍即在"最优性、可扩展性、实现复杂度"之间权衡：DP 最优但规模受限，GA 可扩展但非最优，Cascades 在两者间取得平衡。

Join 顺序搜索是"一交换最优性换可扩展性"的权衡，DP 极端最优、GA 极端可扩展、Cascades 用 memo 结构与剪枝折中。

• RBO 基于规则恒真、不依赖代价
• CBO 基于代价估算选择物理算子与连接顺序
• 具体规则分类：恒优的按 RBO，需要代价的按 CBO

RBO（基于规则优化）应用一组恒真（无论数据如何都更优或等价）的规则，不变换语义、不依赖代价，例如：常量折叠、谓词下推、投影下推、连接消除（内外连接消除为需要时才保留）、子查询上拉/展开、去重消除等。这些优化无论数据分布如何都成立，因此直接套用。CBO（基于代价优化）则对需要代价才能决策的部分做估算，例如：Join 顺序选择（多表连接顺序）、Join 算法选择（Nested Loop vs Hash Join vs Sort Merge）、是否使用索引、是否做聚合下推等，这些依赖数据分布与基数，必须用代价估算。实际优化器（如 Postgres、Oracle）把 RBO 作为基础变换层，CBO 在其上做代价驱动的物理计划选择，RBO 先做恒优变换，CBO 再决定物理实现。

分层的判据是"该优化是否恒优、是否依赖数据分布"：恒优且不依赖分布的走 RBO，需要基于底层数据分布与代价对比的走 CBO。

• 等频/等高直方图的分桶与估算原理
• 多列相关性导致独立假设失效
• 采样误差导致的基数偏差及其对 Join 顺序的影响

等频直方图让每个桶包含近似相等的行数，等高直方图让每个桶的取值区间宽度相等，二者都用于近似估算某个谓词命中的行数（基数）。估算误差的主要来源：一是假设列相互独立，实际多列相关时会严重低估/高估（如 c1 与 c2 强相关时，独立假设会把联合命中数估计得过大或过小）；二是采样误差（样本不能完全代表整体，尤其对倾斜数据）；三是桶内分布假设（等频桶内假设均匀）。这些误差导致基数高估或低估，直接影响 Join 顺序选择：若某表基数被低估，优化器可能以为 join 输出小、把它放在容易位置，实际却产生巨大中间结果，甚至选错连接顺序或 Join 算法（如误用 Nested Loop 而非 Hash Join），造成计划退化。

基数估计是 CBO 的基石，直方图质量、相关性假设与采样精度共同决定估计准确性，偏差会传导到 Join 顺序与算法选择，导致性能骤降。

• Hash Join 构建（build）与探测（probe）两阶段代价
• 内存内 vs 溢出（spill）的代价模型差异
• 优化器对 join 内存需求的预估

Hash Join 分两阶段：构建阶段把小表（构建侧）读入并哈希建立 hash 表，探测阶段读大表（探测侧）逐条在 hash 表查找匹配。代价模型需分别估算构建和探测的 CPU 与 IO 成本：构建侧要读入构建表并计算哈希、插入，探测侧要读入探测表并逐条查找。若构建表能全部放入内存（内存内），代价以内存 hash 表操作为主；若超出内存预算，需要按分区把构建表落盘（spill），再分片探测，产生额外 IO 与多次读盘，代价显著上升。优化器预估内存时，根据构建侧估算行数、每行大小、hash 表开销估算所需内存，与可用内存预算比较，决定是否选用 Hash Join、是否需多分区/落盘，从而把"内存 vs 落盘"的成本纳入总代价。预估不准会导致错误的方案选择（如误以为内存内而实际落盘）。

Hash Join 代价的要点是"构建侧是否内存内"决定是否产生落盘 IO，优化器对内存的预估直接决定它把 Hash Join 当作内存内还是溢出方案来计代价。

• Nested Loop 适用于小表/只有少量匹配的驱动情形
• Hash Join 适用于等值连接、大表、内存足够
• Sort-Merge 适用于有序/非等值连接，Sort 代价高

Nested Loop 把外层表每一行与内层表全表匹配，代价 O(N*M)，只适合小表或内层能快速匹配（且匹配行少）的场景、也适合非等值连接。Hash Join 对外层构建 hash 表、内层探测，等值连接下复杂度 O(N+M)，适合大表等值连接，但需内存建立 hash 表（不足则落盘）。Sort-Merge Join 先把两侧按连接键排序再归并匹配，适合两个输入已排序或需非等值连接的场景，但排序本身代价高（O(N log N)）。Index Nested Loop 用内层表的索引加速匹配，等于把内层全表扫描变成索引查找，适合大表通过索引做小结果集连接。优化器按数据量、是否有索引、连接类型、内存可用性选择代价最小的方案。

四种算法在"扫描匹配 vs 排序 vs 哈希 vs 索引"间权衡，优化器根据表大小、连接键、索引与内存情况选择，核心是让每次匹配的成本与匹配次数最小。

• 自动统计收集（ANALYZE、后台采样）
• 采样方法与直方图构建
• 失真检测（采样偏差、过期、数据变化）

统计信息自动收集通常通过后台任务或 ANALYZE 命令触发：对表做随机采样（采样率可配置），用样本构建直方图（等频/等高）、统计唯一值数、空值率、平均行宽等，并存储在系统目录中，供优化器估算基数。失真检测包括：采样质量（样本是否代表整体，是否因采样率过低导致偏差）、数据变化捕获（表发生大量增删改后统计是否过期，可通过统计信息中的 reltuples 与实际行数对比、自动更新阈值判断）、以及直方图重新构建（数据分布变化时需要重采样）。当检测到统计失真或过期时，应触发 ANALYZE 重新收集，避免优化器基于过期统计选错计划。

统计信息是 CBO 的原料，自动收集保证新鲜度，失真检测捕捉"数据变化与统计过期"，二者结合才能让优化器稳定选对计划。

• 通用计划（generic plan）复用一次、稳定但可能非最优
• 定制计划（custom plan）按参数重新优化、最优但每参数都优化
• 计划不稳定的缓解（参数化、限定、计划缓存策略）

Prepared Statement 把查询参数化，第一次执行时优化器可能生成定制计划（custom plan，针对具体参数值优化），也可能选择通用计划（generic plan，忽略参数值、对所有参数通用）。定制计划更贴合实际参数、可能更优，但每次新参数都重新优化、并有缓存膨胀；通用计划复用一个稳定计划、避免重复优化，但参数取值范围大时可能对某些参数非最优。计划不稳定指同一查询因参数或统计变化在不同执行时选择差异很大的计划，导致性能波动。缓解手段包括：限定 prepared statement 的通用/定制计划选择策略（如执行次数达到阈值后改用通用计划）、对计划做参数化（把常量参数化避免因参数值不同而生成不同计划）、以及计划缓存失效控制（统计信息变化时淘汰旧计划并重算）。

通用 vs 定制是"计划稳定性 vs 计划最优性"的权衡，计划不稳定是参数化查询的常见问题，需通过计划策略与缓存失效控制缓解。

• Hint 的作用与使用时机（统计信息不可靠等）
• 验证 hint 必要性（对比计划、回归测试）
• hint 的副作用（统计信息更新后计划退化、无法自适应）

优化器 Hint 是人工指定某条查询的 Join 顺序、访问方式或参数，用于在优化器决策错误时强制纠正。其使用时机应限于：统计信息严重失真、数据分布特殊、优化器反复选错计划且无法通过更新统计/调参解决。使用 hint 前应验证必要性：对比"无 hint 的执行计划与耗时"与"使用 hint 后"，确认确有提升且长时间稳定；同时要评估副作用——hint 是硬编码的，可能忽略后续数据与统计信息的变化，当统计信息更新（表数据量、分布变化）后，原本合理或原最优的 hint 可能反而导致计划退化，且 hint 无法自适应。因此 hint 应作为最后手段，配合回归测试与监控，并及时评估是否可移除。

Hint 用"人工确定性"换"优化器自适应"，其边界是统计/优化器已不可靠时的兜底，但必须验证有效性并警惕统计更新后的退化。

• 自动更新阈值（变更行数触发）、采样比例
• 手动 ANALYZE 的时机与场景
• 统计过期导致计划退化的症状

统计信息新鲜度由自动更新机制维护：数据库（如 Postgres、MySQL）在表发生一定比例的行变更（插入/删除/更新超过阈值，如 10%）或达到时间阈值时自动触发 ANALYZE，也可配置采样比例（默认 100% 或小比例）以平衡开销与精度。手动 ANALYZE 用于数据刚发生大量变化、批量加载后、或发现统计过期时，主动刷新直方图与基数。统计严重过期的症状是优化器基于过时基数估算选错计划：例如表实际有百万行但统计仍显示几百行，导致优化器误选 Nested Loop 或全表扫描、Join 顺序错误，查询出现"有时快有时慢"的性能波动，EXPLAIN 中估算行数与实际行数偏差巨大。这些症状是触发手动 ANALYZE 的信号。

新鲜度靠"自动阈值 + 定时 + 手动"三管齐下，过期症状集中在"估算行数 vs 实际行数偏差大导致计划退化"，是判断何时 ANALYZE 的依据。

• DP 最优但指数级、限于表数
• 启发式（贪心、左深树、随机）可扩展但非最优
• 工程上按表数与查询复杂度选择

Join 顺序优化中，DP 通过枚举所有连接顺序并利用最优子结构（memoization）保证找到全局最优连接顺序，但状态数随表数指数增长，只适用于表数较少（通常十几个以内）的查询。启发式方法（如贪心选择最小代价连接、构造左深树、基于随机的搜索）不枚举全部，能以多项式时间扩展到大量表，但可能陷入局部最优、无法保证全局最优。工程上通常按表数分级：表数少时用 DP/Cascades 保证最优，表数多时用启发式或剪枝的 DP 快速逼近，并可用遗传算法在更大空间搜索。权衡本质是"最优性 vs 可扩展性"：DP 最优但受限，启发式可扩展但非最优。

权衡点是"搜索空间大小 vs 最优性保证"，DP 在受限空间内最优，启发式在更大空间内快速逼近，实际引擎按表数混合使用。

• 常量折叠：编译期计算常量表达式
• 谓词化简：简化/转置谓词
• 外连接消除与子查询上拉：把复杂查询改写为等价但更高效的形式

逻辑优化是在不改变结果语义的前提下，把查询树改写为逻辑上更高效的形式（属于 RBO 类）。常用优化包括：常量折叠（把 1+2 编译期算成 3，把 where col = 3+4 变成 col = 7）、常量表达式求值提前；谓词化简（把复杂谓词化简，如 col > 5 AND col > 10 简化为 col > 10，或把 col IN (1,2,3) 转成等价形式）、谓词下推；外连接消除（当外连接的一侧被后续谓词强制为非空，或不需要保留不匹配行时，把 LEFT/RIGHT OUTER JOIN 改写为 INNER JOIN，从而允许更灵活的连接顺序与优化）；子查询上拉/反嵌套（把子查询改写为 join 或相关子查询提升，使优化器能统一优化）。这些优化恒真、不依赖代价，是 RBO 的基础。

逻辑优化做的是"等价改写"，把查询化简、收紧、消除冗余，为后续代价优化提供更小的、更利于优化的逻辑形态。

• 基数估计偏差是普遍问题
• 反馈优化：用实际执行结果修正估算
• 历史查询重放：用真实查询与结果校准模型

基数估计偏差是业界普遍问题（多列相关性、倾斜、复杂谓词导致估算不准），会误导代价优化。反馈优化（feedback optimization）利用实际执行时收集的真实行数/基数，反馈给优化器，修正后续对同一或相似查询的估算，甚至用实际数据训练/校准代价模型。历史查询重放即是把记录下来的真实查询负载（query log）重新执行或模拟，收集实际基数与执行信息，用于校准估算模型、验证计划质量、检测计划退化。二者都试图用"真实执行数据"替代"静态估算"的不确定性，是兜底和补救大变差的手段。AQE 也属于运行时反馈的一种。

偏差是统计估算法测度的固有局限，补救思路是用真实执行结果（反馈）与真实负载（重放）来校准模型，让估算贴近实际。

• 不同介质 IO 延迟差异巨大，需标定代价权重
• 基准测试标注各操作的相对成本
• 错误标定导致选错访问方式/算法

数据库代价模型把 CPU、IO、内存等操作按权重加权估算，不同存储介质的 IO 成本差异巨大（HDD 随机读毫秒级、SSD 百微秒级、内存纳秒级），权重必须按实际硬件标定。标定方法通常用基准测试测出各操作的真实耗时（如顺序读一页、随机读一页、CPU 处理一行），设定相对权重（如磁盘随机读代价远高于内存计算）。若标定错误（如把 SSD 的随机 IO 代价误标为 HDD 级别或反之），优化器会错误估计：把磁盘 IO 代价估得过大会偏向少读盘但 CPU 重的计划（如全表扫描换成索引）、估得过小会偏向多读盘的计划，导致选择错误的访问方式（索引 vs 扫描）、Join 算法或存储位置，造成性能偏差。因此代价权重需随硬件与部署环境标定。

代价权重是"各物理操作相对成本"的量化，标定错误会让优化器在"读盘 vs 计算"之间做出错误取舍，进而选错计划。

• 过期统计导致基数估算失真、计划退化
• 手动 ANALYZE 强制刷新统计
• 何时需要手动执行

统计信息过期指表的实际数据分布已发生变化，但优化器使用的直方图/基数仍是旧值，导致估算失准、选错执行计划（如误选 Nested Loop、错误 Join 顺序、错误索引），表现为查询性能下降或"时快时慢"。手动 ANALYZE 会重新扫描/采样表，重建直方图与统计信息，让优化器获得最新基数。在批量加载、大量增删改、刚建索引、或发现计划退化时应手动执行 ANALYZE。由于自动收集有阈值与调度延迟，手动 ANALYZE 是保证统计新鲜度、纠正计划退化的直接手段。

过期统计的后果是"估算 → 计划 → 性能"的连锁恶化，手动 ANALYZE 通过刷新统计直接纠正优化器的输入。

• 计划缓存（plan cache）复用已生成计划
• 统计信息变化/表结构变化触发失效
• 失效后重算新计划

数据库通常缓存已生成的执行计划（plan cache），对相同/相似的查询直接复用，避免重复优化。但缓存计划依赖生成时的统计信息与表结构，当统计信息变化（表数据量、分布变化、ANALYZE 后直方图更新）、表结构变化（加列、加索引、重建表）或优化器版本变化时，旧计划可能不再最优甚至不正确，需要失效并重算。计划缓存失效通过记录计划依赖的统计信息版本/表版本，检测到变化时把标记为失效，下次执行时重新优化生成新计划。失效策略要在"复用减少优化开销"与"避免用过时计划"之间权衡（如按版本号、按变更阈值触发）。

计划缓存的关键是"何时复用、何时失效"，依赖统计与结构版本检测，失效后重算以保持计划与当前数据匹配。

• 驱动表（外层表）的选择影响匹配次数
• 选择性（匹配行数比例）影响算法选择
• 数据量、索引、内存的影响

Nested Loop 的代价取决于外层（驱动）表行数乘以内层匹配代价，若外层小、内层有索引、匹配行少，则 Nested Loop 高效；若外层大或内层匹配行多，则代价高。Hash Join 则是先构建 hash 表（用较小一侧）、再探测，代价与两表总行数相关，不依赖匹配行数，适合大表等值连接且构建侧小的情况。选择性（连接键值的唯一性/匹配比例）影响：选择性高（匹配行多）时 Nested Loop 因内层扫描次数多而差，Hash Join 更优；选择性低（匹配行少）时 Nested Loop 可更快终止。驱动表选择在 Nested Loop 中尤其关键（一般选小表/选择性高的一端做外层），Hash Join 则选小表做构建侧。优化器结合数据量、选择性、索引、内存综合选择。

关键在于"匹配次数与总扫描量"：Nested Loop 对"驱动表小 + 匹配少"友好，Hash Join 对"大表等值 + 匹配多"友好，驱动表与选择性是核心判断依据。

• 随机查询生成（fuzz testing）验证结果正确性
• plan diff 比较优化前后计划差异
• 查询重放用真实负载回归

优化器正确性测试既要保证"生成的计划正确返回结果"，又要保证"优化不引入副作用"。方法包括：随机查询生成（fuzz testing），随机生成合法查询（含各类 join、子查询、聚合、谓词），与基准实现（如解释执行或参考数据库）对比结果，验证优化后计划结果一致；plan diff，比较同一查询在优化前后的执行计划（或不同优化器配置下的计划），检查优化是否引入意外变化、计划是否退化；查询重放，把真实生产负载（query log）重放到测试环境，验证优化器在真实查询上的正确性与性能变化，检测回归。三者结合覆盖了"正确性（结果一致）"与"稳定性/无回归（计划与性能不退化）"。

优化器测试的本质是"结果正确性"与"计划质量/无回归"双维度，随机查询验证正确性，plan diff 与重放验证计划稳定性与性能。