10. 查询处理

1. Motivation (动机)

声明式语言特性：SQL 仅描述“想要什么结果 (What)”，而不指定“如何执行 (How)”。
多样性 (Equivalence)：同一个 SQL 查询可以被翻译成多种等价的关系代数表达式。
灵活性：每种关系代数操作（如 Select, Join）都有多种具体算法（全表扫？用索引？）。
核心目标：查询处理的任务是将高级查询转换为执行计划 (Execution Plan)，并在所有可能的计划中选择估算代价最低 (Lowest Estimated Cost) 的那个。

2. Concepts & Steps (核心概念与步骤)

2.1 处理流程 (Basic Steps)

Parsing and Translation (解析与翻译)：
- 检查语法 (Syntax) 和关系名/属性名。
- 将查询翻译成关系代数表达式。
Optimization (查询优化)：
- 这是最关键的一步。优化器利用统计信息（Statistics），估算各种策略的 Cost，输出最优的执行计划。
Evaluation (执行)：
- 执行引擎运行计划，返回结果。

2.2 代价衡量 (Measures of Query Cost)

主要指标：磁盘访问 (Disk Access) 是主要瓶颈。为简化计算，通常忽略 CPU 时间和结果写入时间。
核心公式：
- ：需要传输的磁盘块数 (Number of block transfers)。
- ：传输一个块的时间 (Transfer time)。
- ：寻道次数 (Number of seeks)。
- ：一次寻道的时间 (Seek time)。
假设：通常基于最坏情况 (Worst Case) 估算，假设内存缓冲很小。

3. Methods (具体算法)

3.1 简单选择：无索引 (File Scan)

算法	名称	原理	代价 (Cost)	特点
A1	Linear Search (线性扫描)	逐块扫描整个文件		万能算法。若在主键查找，平均代价减半。
A2	Binary Search (二分查找)	在有序文件中二分		前提：文件必须按属性有序且连续存储。

3.2 简单选择：有索引 (Index Scan)

算法	名称	场景	关键点
A3	主索引 + 候选键	找唯一记录 (Unique)	为树高。点查询效率极高。
A4	主索引 + 非键	找多条记录 (Range)	因为物理连续，找到起点后只需顺序读。
A5	辅助索引	找多条记录 (Range)	极昂贵！是匹配记录数。每读一条数据都可能产生一次新的 Seek。

★ 重点 Trade-off：A1 vs. A5

这是考试常考点：什么时候该放弃索引，改用全表扫描？
* 少量数据：使用 A5 (辅助索引) 更好。
* 大量数据：使用 A1 (全表扫描) 更好。因为 A5 会产生大量的随机 I/O (Seeks)，而 A1 是顺序 I/O。

3.3 复杂条件处理 (Complex Selections)

针对 WHERE 子句中包含逻辑运算的情况。

(1) 合取条件 (Conjunction: AND)

即 WHERE cond1 AND cond2 ...

A8: 单索引 + 内存过滤 (Single Index)
- 策略：只使用一个代价最低（过滤性最强，即返回记录最少）的索引。
- 流程：通过该索引从磁盘取出记录 -> 放入内存 -> 在内存中检查是否满足其他条件。
A9: 复合索引 (Composite Index)
- 策略：如果存在覆盖多个字段的复合索引（如 (age, dept)），直接使用。
- 评价：通常是最高效的方法。
A10: 索引交集 (Intersection of Identifiers)
- 策略：利用多个索引分别查找。
- 流程：扫描每个条件的索引 -> 获取指针集合 -> 在内存取交集 (Intersection) -> 根据交集指针去磁盘读数据。

(2) 析取条件 (Disjunction: OR)

即 WHERE cond1 OR cond2 ...

A11: 索引并集 (Union of Identifiers)
- 策略：利用多个索引分别查找。
- 流程：扫描每个条件的索引 -> 获取指针集合 -> 在内存取并集 (Union) -> 根据并集指针去磁盘读数据。
强制前提 (Crucial)：所有参与 OR 的条件必须都有索引。
- 否则：只要有一个条件没索引，必须使用 A1 线性扫描 (Linear Scan)。

(3) 否定条件 (Negation: NOT)

即 WHERE NOT condition
* 策略：通常使用 A1 线性扫描。
* 原因：“不等于”通常意味着绝大多数数据都满足条件，索引扫描会导致全表随机读取，性能不如顺序扫描。

4. Examples (典型考题模型)

场景：表有 10,000 个块 ()。辅助索引树高忽略不计。
假设 , 。

对比 A1 (全表) vs A5 (辅助索引)：

Case 1: 匹配 10 条记录 ()
- A1 (Linear): (约 10秒)
- A5 (Index): (0.1秒)
- 结论：索引完胜。
Case 2: 匹配 2000 条记录 ()
- A1 (Linear): 依然 (约 10秒)
- A5 (Index): (22秒)
- 结论：全表扫描更快！因为辅助索引的随机 I/O 代价太高。

5. Summary (复习要点)

公式记忆：背熟。
权衡 (Trade-off)：
- 主索引：对于范围查询和多记录查找非常快（物理连续）。
- 辅助索引：只适合查找少量记录（随机访问成本高）。一旦匹配记录多，不如全表扫。
复杂逻辑判断：
- AND：优先找复合索引 (A9) -> 其次找交集 (A10) -> 最后单索引过滤 (A8)。
- OR：检查是否所有列都有索引。缺一个就得全表扫。