查询优化的必要性：为何要估算成本？

数据库系统中的查询优化是一个复杂而关键的环节。当用户提交一个查询时，数据库管理系统（DBMS）并非直接执行它，而是会生成大量可能的执行方案，即查询计划。每一种查询计划都对应着不同的执行路径和资源消耗。例如，对于一个涉及多表连接的查询，表连接的顺序、使用的连接算法（如哈希连接、排序合并连接、嵌套循环连接）以及访问数据的方式（如全表扫描、索引扫描）都会影响查询的效率。

由于直接运行每一个可能的查询计划来评估其成本是极其昂贵且耗时的 （尤其当可能方案达到成千上万个时）， DBMS 必须有一种方法来近似估算每个查询计划的执行成本 。这个估算模型允许优化器在实际执行之前评估计划的“质量”或所需的工作量，并从中选择成本最低的那个，以确保查询以最高效的方式运行。

估算信息来源：数据库内部统计信息

为了准确估算查询计划的成本，DBMS 依赖于其内部的 统计信息目录 (internal catalog) 。这些统计信息详细描述了数据库中表、属性和索引的特性。

核心的统计信息包括：

• 每张表的元组数量 (NR) ：表示表中包含的记录总数。
• 每个属性的唯一值数量 (V(A,R)) ：表示特定列中不同值的数量。

基于这些基本信息，可以派生出 选择基数 (Selection Cardinality, SC(A,R)) ，它代表了给定属性中具有相同值的记录的平均数量，计算方式是 NR / V(A,R)。

统计信息的更新频率因系统而异。通常，它们可以通过手动命令（如 Postgres/SQLite 的 ANALYZE，Oracle/MySQL 的 ANALYZE TABLE，SQL Server 的 UPDATE STATISTICS，DB2 的 RUNSTATS）进行刷新。一些系统也支持通过后台任务（如 cron jobs）、在查询执行时顺便更新，或通过触发器（如表数据变化达到一定百分比时）来自动更新。需要注意的是， 收集这些统计信息本身是昂贵的 ，因为它通常涉及对整个表的顺序扫描。

核心概念：选择率 (Selectivity)

选择率 (Selectivity) 是优化器估算成本的关键指标，它定义为 满足给定谓词的元组在总元组中所占的比例 。本质上，选择率可以被视为一个元组满足某个条件的概率。

根据谓词类型，选择率的计算方式不同：

• 等值谓词 (Equality Predicate) ：sel(A=constant) = SC(P) / NR。例如，age=2 的选择率在均匀分布假设下可能是 1/5。
• 范围谓词 (Range Predicate) ：sel(A>=a) = (Amax – a) / (Amax – Amin)。例如，age>=2 的选择率可能被估算为 (4-2)/(4-0) = 1/2。
• 否定谓词 (Negation Predicate) ：sel(not P) = 1 – sel(P)。
• 合取谓词 (Conjunction, AND) ：sel(P1 ⋀ P2) = sel(P1) ∙ sel(P2)。
• 析取谓词 (Disjunction, OR) ：sel(P1 ⋁ P2) = sel(P1) + sel(P2) – sel(P1) ∙ sel(P2)。

优化器的估算假设与挑战

为了简化数学模型，查询优化器通常会做出一些关键假设，但这些假设在现实世界中往往不成立，从而导致估算误差。

假设1：数据均匀分布 (Uniform Data)

• 含义 ：假设一个属性的所有唯一值出现的频率都是相同的。
• 问题 ：实际数据往往是 倾斜的 (skewed) 。例如，在有10000名学生和10个学院的大学中，如果数据均匀分布，每个学院将有1000名学生。但实际上，计算机科学学院的学生数量可能远多于美术学院。这种不准确的假设会导致对结果集大小的低估或高估。

假设2：谓词独立 (Independent Predicates)

• 含义 ：假设查询中不同谓词（如 WHERE 子句中的多个条件）之间没有关联，它们的满足概率可以简单相乘或相加。
• 问题 ：在现实中，谓词之间往往存在 关联性 (correlated) 。例如，查询汽车数据库中 make="Honda" AND model="Accord" 的车辆。如果假设独立性，计算结果是 1/10 * 1/100 = 0.001 (假设有10个品牌和100个型号)。但我们知道只有本田生产 Accord 车型，因此实际上，只要知道 model="Accord"，make 就必然是 Honda，正确选择率应是 1/100 = 0.01。这种情况下，优化器会 低估 查询将要处理的数据量，导致对中间数据结构（如哈希连接的哈希表、排序的缓冲区）的大小估算错误，进而影响查询的实际运行时性能。

假设3：包含原则 (Inclusion Principle)

• 含义 ：在连接操作中，假设内部表中的每一个连接键值都能在外部表中找到匹配的键值。
• 问题 ：实际中可能存在 悬空引用 (dangling references) ，即内部表中的值在外部表中没有对应的记录。

这些假设使得优化器的数学模型更易于处理，但同时也引入了误差。研究表明，许多数据库系统在估算操作符的选择率时普遍存在低估的问题。

数据库如何弥补估算误差？

为了应对数据分布不均匀和谓词关联性等问题，现代数据库系统采用更复杂的技术来维护和利用统计信息：

直方图 (Histograms)

最简单的直方图会为每个唯一值存储其出现次数，但这在唯一值数量巨大时会占用过多存储空间。

• 重度打击器 (Heavy Hitters) ：对于出现频率特别高的值（即倾斜数据中的“热点”），数据库会单独存储它们的精确计数，而对于其余数据则可能继续使用均匀分布的假设。
• 等宽直方图 (Equi-width Histograms) ：将数据值范围分成等宽的桶，每个桶存储其内值的总计数。这节省了空间，但如果桶内数据分布仍不均匀，估算精度会下降。
• 等深直方图/分位数直方图 (Equi-depth/Quantile Histograms) ：通过调整桶的宽度，使每个桶包含大致相同数量的元组（即每个桶的“深度”或总计数大致相同）。这种方法通常能提供更准确的估算，因为它能更好地捕捉数据分布的特征。
• 更新机制 ：直方图通常是定期 重新计算 的，而不是在每次插入、更新或删除时实时维护的，因为实时维护的成本太高，会影响事务性能。

采样 (Sampling)

一些现代 DBMS 会从表中随机选择并维护一个较小的 数据样本 (sample) 。

当需要估算谓词的选择率时，优化器将谓词应用到这个样本上，然后根据样本中符合条件的元组比例来推断整个表的选择率。

• 优点 ：样本可以比直方图更准确地反映实际数据分布，尤其在处理复杂谓词时。
• 挑战 ：如何生成一个对所有查询都具有代表性的样本是一个难题。同时，对样本进行扫描以计算选择率可能比简单查询直方图要慢，因此通常只在预计查询本身会运行很长时间时才值得使用。
• 高级系统 ：像 SQL Server 这样的高端商业数据库通常会 结合使用直方图和采样 来获得最佳的估算精度。

数据库如何找到最优计划？

查询优化器在进行完基于规则的查询重写（例如消除冗余操作、推拉谓词等）之后，会进入 基于成本的搜索 (Cost-based Search) 阶段，以将逻辑查询计划转换为物理查询计划。

单表查询优化

对于只涉及单个表的查询，优化器主要关注选择最佳的 访问方法 (access method) ，例如是进行全表扫描（最慢但总是正确）、使用聚簇索引的二分查找，还是使用一个或多个索引进行索引扫描。

此外，它还会考虑谓词的评估顺序，优先评估选择率更高的谓词，以便更快地过滤掉不符合条件的元组。

对于在线事务处理 (OLTP) 查询，由于它们通常只访问少量数据并主要进行单表查找，优化通常相对简单，主要依赖于 启发式规则 (heuristics) 和识别 可索引查询 (sargable queries) 来选择最佳索引。

多表连接优化

当涉及多表连接时，查询计划的替代方案数量会急剧增长。对于 N 个表的连接，可能的连接顺序和算法组合可以达到 4^N 甚至更多。

动态规划 (Dynamic Programming) ：为了应对这种爆炸式的搜索空间，IBM System R 在1970年代引入了动态规划技术。这种方法将问题分解为更小的子问题，先解决这些子问题并存储其最优解，然后逐步组合这些最优解以找到整个查询的最优计划。在每一步中，它只保留当前已知成本最低的路径，从而剪枝大量不必要的搜索。

左深连接树 (Left-deep Join Trees) ：System R 做出一个关键的简化假设——只考虑 左深连接树 。这意味着连接操作总是从左侧开始，前一个连接的结果作为下一个连接的左输入。

• 优点 ：这种结构有利于实现 流水线操作 (pipelining) ，即前一个操作符的结果可以立即作为下一个操作符的输入，而无需将中间结果写入磁盘上的临时文件。这在内存受限的早期系统上尤为重要，因为它最大限度地减少了磁盘 I/O。
• 现代系统 ：虽然左深连接树在历史上很重要，但现代 DBMS 不再局限于此，它们通常会探索所有类型的连接树，包括左深、右深和 灌木式 (bushy) 连接树 。

混合优化策略（以 Postgres 为例）

Postgres 采用了一种混合策略：

• 对于 少于12个表 的查询，它使用传统的 动态规划方法 。
• 对于 12个或更多表 的复杂查询，它会切换到 遗传查询优化器 (Genetic Query Optimizer, GEQO) 。

遗传算法 是一种随机搜索算法，它模拟生物进化过程：

• 初始种群 ：首先生成一组随机的查询计划（第一代）。
• 评估与选择 ：对每个计划计算成本，选择其中成本最低的计划作为当前“最优”方案，并淘汰掉成本最高的计划。
• 交叉与变异 ：保留下来的计划的“基因”（即计划的组成部分，如连接顺序、算法等）进行随机“混合”和“变异”，生成下一代新的查询计划。
• 迭代 ：这个过程不断重复，直到达到预设的时间限制或连续多代没有发现更好的计划为止。
• 适用场景 ：遗传算法能够处理更大的搜索空间，这对于数据仓库中常见的 星型/雪花型 (snowflake schema) 查询尤其有用，因为这些查询通常涉及大量维度表和事实表之间的连接。

嵌套子查询 (Nested Sub-queries) 的优化

WHERE 子句中的嵌套子查询最初被视为一个函数，对外部查询的每一行进行评估，效率极低。为了优化这类查询，优化器通常采用两种主要方法。

重写/去相关/扁平化 (Rewrite/De-correlate/Flatten)

将相关的子查询（即子查询引用了外部查询中的列）重写为连接操作。

一旦重写为连接，优化器就可以利用其成熟的连接优化技术（如动态规划）来找到最优的执行计划。

SELECT name FROM sailors WHERE EXISTS (SELECT * FROM reserves WHERE S.sid = R.sid AND R.day = '2018-10-15') 可以被重写为 SELECT S.name FROM sailors AS S, reserves AS R WHERE S.sid = R.sid AND R.day = '2018-10-15'。

分解 (Decomposition)

将嵌套的子查询（尤其是不相关的子查询）作为一个独立的查询块先执行，将其结果存储在一个临时表或变量中，然后将这个结果作为参数或数据源传递给外部查询。

避免了对每一行外部查询都重复执行子查询的低效率问题。

在一个复杂查询中，如果有一个子查询是计算所有水手的最高等级 (SELECT MAX(S2.rating) FROM sailors S2)，优化器可以先单独执行这个子查询，得到最高等级的值，然后将这个值插入到外部查询中 S.rating = [最高等级的值]，从而避免重复计算。

总结

查询优化是一个 极其困难但又至关重要 的问题。尽管其中的数学模型和算法非常复杂，但现代数据库系统能够以惊人的速度完成这些优化，这使得用户几乎感知不到其中的开销。通过结合统计信息、多样的估算技术、复杂的搜索算法和智能的查询重写，DBMS 不断努力为每条查询找到最高效的执行路径。

（额外信息：课程中还提到了一个名为 https://dbdb.io/ 的额外加分项目，鼓励学生编写关于不同数据库管理系统的百科文章，以加深对数据库架构和实现方式的理解）