数据库查询评估与优化全解析

# 数据库查询评估与优化全解析 ## 1. 基本操作评估 ### 1.1 选择操作（Selection） 选择操作是从表中简单检索元组，其实现与访问路径密切相关。对于形如 σR.attr op value(R) 的选择操作，如果 R.attr 上没有索引，就需要扫描整个表 R；若有匹配的索引，则可使用索引检索匹配元组，并应用剩余选择条件进一步限制结果集。 例如，在 Reserves 表上进行 rname < ‘C%’ 的选择操作，假设名字首字母均匀分布，大约 10% 的元组会在结果中，即 10,000 个元组或 100 页。若 Reserves 的 rname 字段有聚簇 B + 树索引，检索符合条件的元组大约需要 100 次 I/O（加上从根节点到合适叶节点开始扫描的几次 I/O）；若索引是非聚簇的，最坏情况下可能需要 10,000 次 I/O。一般来说，如果要检索的元组超过 5%，直接扫描整个表可能更便宜。 ### 1.2 投影操作（Projection） 投影操作需要丢弃输入的某些字段，关键在于确保结果中无重复项。若不需要消除重复项（如 SELECT 子句中未包含 DISTINCT 关键字），投影操作只需从输入表的每个元组中检索所需字段子集，可通过简单迭代表或其键包含所有必要字段的索引来实现。 若需要消除重复项，通常采用分区方法。例如，从 Reserves 表投影获取 sid, bid 时，可先扫描 Reserves 表获取 sid, bid 对，然后以 sid, bid 为排序键对这些对进行排序，最后扫描排序后的对并丢弃相邻的重复项。 投影操作可通过优化减少成本，如将 Reserves 的初始扫描与排序的第一遍扫描结合，将排序对的扫描与排序的最后一遍扫描结合。合适的索引也可降低消除重复项的成本，若索引的搜索键包含投影保留的所有字段，可对索引中的数据条目进行排序；若保留的属性出现在聚簇索引搜索键的前缀中，可直接使用索引检索数据条目，方便检测重复项。 ### 1.3 连接操作（Join） 连接操作成本高且常见，系统通常支持多种连接算法。以 Reserves 和 Sailors 表的连接为例，连接条件为 Reserves.sid = Sailors.sid。 #### 1.3.1 索引嵌套循环连接（Index Nested Loops Join） 若其中一个表（如 Sailors）的 sid 列有索引，可扫描 Reserves 表，对每个元组使用索引在 Sailors 表中查找匹配元组。假设 Sailors 表的 sid 属性有基于哈希的索引，平均每次检索索引页需要 1.2 次 I/O。Reserves 表有 100 * 1000 个元组，扫描 Reserves 表的成本是 1000 次 I/O，每个元组检索匹配的 Sailors 元组需要（1 + 1.2）次 I/O，总共需要 100,000 * (1 + 1.2) 次 I/O 来检索匹配的 Sailors 元组，总成本为 221,000 次 I/O。 #### 1.3.2 排序合并连接（Sort - Merge Join） 若两个表上都没有匹配连接条件的索引，可对两个表按连接列进行排序，然后扫描它们以查找匹配项。假设 Reserves 表和 Sailors 表都可在两遍排序完成，排序 Reserves 表的成本是 2 * 2 * 1000 = 4000 次 I/O，排序 Sailors 表的成本是 2 * 2 * 500 = 2000 次 I/O，排序合并连接的第二阶段还需要额外扫描两个表，总成本为 4000 + 2000 + 1000 + 500 = 7500 次 I/O。 虽然排序合并连接成本低于索引嵌套循环连接，但索引嵌套循环连接具有增量性。若查询中有额外选择条件，只考虑 Reserves 表的一小部分元组，使用索引嵌套循环连接可避免计算整个连接结果。 ### 1.4 其他操作 SQL 查询除基本关系操作外，还包含分组（Group - by）、聚合（Aggregation）以及集合操作（如并集、差集、交集）。集合操作的主要成本在于消除重复项，可采用与投影操作类似的方法。分组操作通常通过排序实现，若输入表有与分组属性匹配的树索引，可直接使用索引按适当顺序检索元组，聚合操作在检索元组时使用主内存中的临时计数器完成。 ## 2. 查询优化基础 ### 2.