花月的Blog

Appearance

CS186 笔记02 ​

Buffer Management ​

是什么 (What it is) ​

缓冲区管理器（Buffer Manager） 是数据库管理系统（DBMS）的核心组件之一，它是一个位于内存中的缓冲区，负责在内存（缓冲池，Buffer Pool）和磁盘之间高效地移动和管理数据页面（Page）。它为上层组件提供了一个抽象，让它们感觉数据“总是在内存中”。

为什么 (Why it's needed) ​

磁盘 I/O 相比内存访问要慢几个数量级。缓冲区管理器的主要目的就是为了最小化磁盘 I/O 的次数，通过将最常访问的数据页保留在内存中来显著提升系统性能。它高效地管理有限的内存资源，通过智能的页面替换策略决定哪些页面应该留在内存中，哪些应该被写回磁盘，以优化整体吞吐量和响应时间。

怎么做 (How it works) ​

1. 核心 API 交互 ​

缓冲区管理器主要通过以下两个 API 与上层模块（如文件与索引管理器、关系操作符）进行交互：

  • ReadPage(PageId):

    • 当上层模块需要某个特定的数据页面时，它会调用此 API。
    • 缓存命中（Cache Hit）： 缓冲区管理器首先检查请求的 PageId 是否已存在于缓冲池中。如果命中，它直接返回该页面在内存中的地址，无需进行磁盘 I/O。
    • 缓存未命中（Cache Miss）： 如果页面不在缓冲池中，缓冲区管理器会根据其页面替换策略（下文详述）选择一个可用的内存帧（Frame）。
    • 脏页回写： 如果选定的内存帧当前存储的页面是“脏的”（Dirty Bit 为真，表示在内存中被修改过），则必须先将其内容异步或同步地写回磁盘，以确保数据持久性。
    • 页面加载： 最后，将请求的新页面从磁盘读取到这个选定的内存帧中，并返回其内存地址。

  • WritePage(PageId):

    • 当上层模块修改了内存中的某个页面后，会调用此 API 通知缓冲区管理器。
    • 缓冲区管理器会简单地将该页面的**脏位（Dirty Bit）**设置为真。这表示该页面已被修改，需要在适当的时候（例如，被替换出内存时，或在系统检查点时）被写回磁盘，以保证数据持久性。

2. 状态管理：元数据 📊 ​

为了有效管理缓冲池，缓冲区管理器维护了一组元数据（Metadata）。这些元数据通常以哈希表或数组的形式存储，记录了缓冲池中每个内存帧的状态：

  • FrameId: 内存帧的唯一标识符。
  • PageId: 当前加载到该内存帧中的磁盘页面的标识符。
  • Dirty Bit (脏位): 一个布尔标志，指示该页面在内存中是否被修改过。如果为真，则在写回磁盘前必须先将其内容持久化。
  • Pin Count (引用计数): 一个整数，表示当前有多少个上层模块正在“使用”或“引用”这个页面。
    • 目的： Pin Count 的存在是为了确保正在被活跃使用的页面不会被意外地从内存中替换出去，从而避免数据不一致或系统崩溃。
    • 管理： 当页面被加载到内存并被上层模块使用时，其 Pin Count 会增加（++）。当上层模块使用完毕，会调用相应 API 减少 Pin Count（--）。只有当 Pin Count 为 0 时，该页面才被认为是未固定（Unpinned），成为可以被替换的候选页面。

3. 页面替换策略 (Page Replacement Policies) ​

页面替换策略是缓冲区管理器的核心算法，它决定了当缓冲池满时，哪些页面应该被驱逐（Evict）出内存，为新页面腾出空间。一个好的替换策略能显著提高缓存命中率。

  • 最近最少使用 (Least Recently Used, LRU):

    • 原理： 淘汰最近最少使用的页面。它通常通过维护一个链表或时间戳来实现，将最近访问过的页面移到列表头部，淘汰尾部的页面。
    • 优点： 在大多数工作负载下，LRU 表现良好，因为程序访问具有时间局部性。
    • 缺点：
      • 维护开销： 维护精确的 LRU 顺序（例如通过链表操作）可能带来较高的 CPU 开销。
      • 顺序泛洪（Sequential Flooding）： 这是 LRU 的一个著名“弱点”。想象一个数据库缓存只能容纳 M 个页面，但你正在对一个包含 N 页（N >> M）的文件进行重复的顺序扫描。
        • 在第一次扫描中，页面 P1, P2, ..., PN 依次被加载。当 P(M+1) 需要加载时，LRU 会淘汰 P1（因为它最早被加载且之后没有再次被访问）。接着 P2 被淘汰，以此类推。到第一次扫描结束时，缓存里装的是最后 M 页（P(N-M+1) 到 PN）。
        • 问题出现在第二次扫描开始时。当你再次访问 P1 时，它已经不在缓存里了，LRU 又会把它加载进来，并淘汰当前缓存里“最近最少使用”的页面（即上次扫描最后加载进来的 P(N-M+1)）。这个模式会持续下去：每次访问都是缓存未命中，因为 LRU 总是淘汰掉下次扫描很快就会用到的页面，而保留了当前扫描完就用不着的页面。结果是，缓存命中率为 0%，性能极差。

  • 近似 LRU / CLOCK 策略:

    • 原理： CLOCK 策略是 LRU 的一个实用近似。它维护一个循环链表（或数组）以及一个“时钟指针”。每个页面帧有一个引用位（Reference Bit）。
    • 工作流程： 当需要替换页面时，时钟指针顺时针扫描帧：
      • 如果当前帧的 Pin Count > 0（正在被使用），跳过。
      • 如果 Pin Count == 0：
        • 检查其 Reference Bit。如果 Reference Bit == 1（表示最近被访问过），将其清零（Reference Bit = 0），并给它第二次机会，然后跳过。
        • 如果 Reference Bit == 0（表示最近没有被访问），则选择该帧进行替换。
    • 优点： 避免了 LRU 精确维护顺序的高开销，且能有效防止顺序泛洪，提供良好的通用性能。

  • 最近最常使用 (Most Recently Used, MRU):

    • 原理： 与 LRU 相反，淘汰最近最常使用的页面。
    • 适用场景： 在某些特定场景下（例如对同一个热点数据块进行重复的高频访问），MRU 可能表现更好，但这不是一个通用策略。

4. 为什么 DBMS 需要自己管理缓冲区？ 🤔 ​

为什么不完全依赖操作系统（OS）的内存管理？主要有以下几个原因：

  • 精确的持久化控制： DBMS 需要精确控制何时强制将脏数据写回磁盘，这对于事务的持久性（Durability）和系统崩溃恢复至关重要。操作系统提供的文件缓存通常粒度不够细，且无法保证数据及时落盘。
  • 优化替换策略： DBMS 了解其自身数据结构（例如索引、表）的访问模式。它可以针对这些模式设计并实现更优的页面替换策略（如 LRU、CLOCK，甚至更复杂的策略），以最大化缓存命中率，而操作系统是通用目的的，无法做到这种细粒度优化。
  • 避免双重缓存： 如果完全依赖 OS 文件缓存，可能会导致**双重缓存（Double Caching）**问题——数据同时存在于 OS 缓存和 DBMS 内部缓存中，造成内存浪费和性能下降。DBMS 通过直接管理其缓冲区，可以避免这种情况。
  • 事务语义： 数据库需要支持复杂的事务语义，包括并发控制和崩溃恢复。这些功能要求对数据页面在内存和磁盘之间的生命周期有细致的控制和协调，这是 OS 无法提供的。

排序和哈希 ​

为什么需要排序？ ​

在数据库系统中，排序操作是至关重要的，它支持多种核心功能和性能优化：

  • 去重（Deduplication）： 在有序数据流中，重复项很容易被发现和消除。
  • 分组（Grouping）： 将具有相同值的记录聚集在一起，是聚合操作（如 GROUP BY）的基础。
  • 连接算法的支持（Join Algorithms）： 许多高效的连接算法（如排序归并连接 Sorted-Merge Join）都依赖于预排序的输入流来查找匹配项。
  • 输出排列（Output Ordering）： 用户查询经常要求结果集按照特定顺序返回（例如 ORDER BY 子句）。
  • 批量加载索引（Bulk Loading Indexes）： 如果数据是预排序的，可以以 O(N) 的线性时间复杂度和最小的 I/O 代价高效地构建 B+ 树等索引，远快于逐条插入。

主要问题：外存排序的挑战 ​

当要排序的**数据量远大于可用内存（N >> B）时，传统的内存排序算法（如快速排序、归并排序）就无法直接使用了。将所有数据一次性加载到内存不仅不现实，即便分批加载，也会带来沉重的 I/O 负担。这正是外存算法（External Algorithms）**登场的原因。

外存算法 (External Algorithms) ​

是什么 (What it is) ​

外存算法是专门为处理那些数据量远超可用内存的计算问题而设计的算法。它们的核心设计目标是最小化磁盘 I/O 次数，因为磁盘 I/O 通常是这类操作的性能瓶颈。

两种主要思想： ​

  1. 单趟流式处理（One-Pass Stream Processing）：

    • 原理： 数据只从磁盘读取一次，经过内存处理后直接写入磁盘。
    • 示例： 简单的 SELECT 查询或 Map 操作。
    • 工作流程： 从输入文件读取一个数据块到缓冲区，对其进行处理，然后读取下一个。
    • 优化： 可以采用双重缓冲（Double Buffering）：主线程在一对输入/输出缓冲区上进行处理，同时一个独立的 I/O 线程并行清空已满的输出缓冲区到磁盘，并填充空的输入缓冲区。主线程处理完后与 I/O 线程交换缓冲区，继续处理，从而隐藏 I/O 延迟。

  2. 分而治之（Divide and Conquer）：

    • 原理： 将大问题拆分成若干可以装入内存的小块，分别在内存中处理，最后再将结果合并。这是外存排序和哈希的基础。

外存排序 (External Sorting) ​

怎么做 (How it works - 两阶段/多阶段归并排序) ​

规格（Formal Specs）： 假设文件 F 包含 N 个数据块，我们有 B 个内存缓冲区。我们还有两个临时的“暂存”磁盘，每个都有远超 N 的空闲存储空间。

Pass 0 (Conquer / 分而治之) ​

这个阶段的目标是将整个文件分解成多个独立、已排序的小段。

  1. 分批读取： 利用 B 个内存缓冲区，从输入文件 F 中分批读取 B 页数据到内存中。
  2. 内存排序： 在内存中对这 B 页数据进行内部排序（例如使用快速排序、堆排序等高效算法）。
  3. 写入已排序段： 将排序好的 B 页数据作为一个“已排序的段”（Sorted Run）写入磁盘。
  4. 重复： 重复这个过程，直到所有输入数据都变成了大小为 B 的已排序段。
  • 产生的段数量： $\lceil N/B \rceil$ 个已排序段。
  • I/O 成本： 读取 N 页，写入 N 页，共 $2N$ 次 I/O。

Pass 1, 2, ... (Merge / 合并) ​

这个阶段的目标是将小段逐渐合并成更大的已排序段，直到最终只有一个完全排序的文件。

  1. 缓冲区分配： 利用 B 个内存缓冲区。其中 B-1 个缓冲区用于输入（从不同的已排序段读取），1 个缓冲区用于输出（写入合并后的新段）。
  2. 多路归并： 每次从 B-1 个已排序段的当前最小记录进行比较，将最小的记录写入输出缓冲区。
  3. 输入/输出管理： 当某个输入缓冲区被读完，就从对应的段中读取下一页。当输出缓冲区填满时，就将其内容写入磁盘。
  4. 重复合并： 重复此过程，将 B-1 个较短的已排序段合并成一个更长的已排序段（长度为旧段长度的 B-1 倍）。这个合并过程会重复进行多趟，直到所有段都合并成一个最终的排序文件。
  • 总 I/O 成本： 每次归并过程都会读取并写入所有页面一次，所以每趟的 I/O 成本是 $2N$。
  • 总趟数： 考虑到 Pass 0 和后续的归并 Pass，总趟数为 $1 + \lceil \log_{B-1}(\lceil N/B \rceil) \rceil$。
  • 总成本： $2N \times (\text{总趟数})$。
  • 内存需求： 在两趟内排序 N 页数据，所需的内存 B 大约是 $\sqrt{N}$。即，如果文件大小为 N，内存大小为 B，那么在两趟内可以排序的最大文件大小是 $B(B-1)$ 页。

外存哈希 (External Hashing) ​

是什么 (What it is) ​

外存哈希是另一种处理大数据集的“分而治之”策略，它不要求最终结果有序，但要求具有相同哈希值的记录在磁盘上存储在一起。它常用于高效地消除重复项或执行**分组（Grouping）**操作。

怎么做 (How it works - 两阶段) ​

阶段一：分区（Partition / Divide） ​

这个阶段的目标是根据哈希函数将所有记录分配到不同的磁盘分区中，确保具有相同哈希值的记录最终进入同一个分区。

  1. 缓冲区分配： 利用 B 个内存缓冲区。
  2. 哈希函数选择： 选择一个分区哈希函数 hp (Partitioning Hash function)。
  3. 流式读取与分发： 从原始关系（Original Relation）流式读取记录。对每个记录计算其哈希值 hp(record)，并根据哈希值将其分发到 B-1 个输出缓冲区中的一个（这 B-1 个缓冲区对应 B-1 个不同的目标分区）。
  4. 分区写入： 当某个输出缓冲区填满时，将其内容作为一个“分区”（Partition）写入磁盘。
  • 结果： 产生 B-1 个磁盘分区。所有哈希值相同的记录都被分发到同一个分区中。注意，每个分区可能包含多种不同的哈希值。
  • I/O 成本： 读取 N 页，写入 N 页，共 $2N$ 次 I/O。

阶段二：重哈希（ReHash / Conquer） ​

这个阶段的目标是处理每个分区，进一步利用哈希将相同键的记录聚集在一起，并（可选）消除重复项。

  1. 缓冲区利用： 再次利用 B 个内存缓冲区。
  2. 哈希函数选择： 选择另一个重哈希函数 hr (Rehashing Hash function)。
  3. 分区处理： 一次读取一个磁盘分区到内存中（假设每个分区的大小都足够小，可以装入 B 个内存缓冲区）。
  4. 内存哈希表构建： 在内存中构建一个哈希表，使用 hr 对该分区内的记录进行哈希。
  5. 写入最终结果： 将内存哈希表中的所有桶内容写入输出文件。
  • I/O 成本： 读取 N 页（每个分区读一次），写入 N 页（每个分区写一次），共 $2N$ 次 I/O。
  • 总 I/O 成本： $2N (\text{分区}) + 2N (\text{重哈希}) = \textbf{4N 次 I/O}$。
  • 内存需求： 在两趟内哈希 N 页数据，所需的内存 B 大约是 $\sqrt{N}$。即，如果文件大小为 N，内存大小为 B，那么在两趟内可以哈希的最大文件大小是 $B(B-1)$ 页。
  • 关键假设： 成功的关键在于哈希函数能够均匀地分布记录，避免某个分区数据量过大。
  • 递归分区（Recursive Partitioning）： 如果某个分区仍然太大（超过 B 页）无法装入内存，则可以对该分区递归地应用阶段一的分区操作。
  • 缺点： 存在**“重复项问题”（Duplicates）**。如果某个键的重复项非常多，导致其哈希到一个分区的数据量仍然超过 B，那么即使递归分区也可能无法解决问题，因为它不能有效地将具有相同键的大量重复项进一步分散。

比较排序和哈希的优缺点 ​

选择最适合特定场景的算法是关键：

  • 简单分析：

    • 内存需求： 它们在两趟处理时，对内存的需求量大致相同，都约为 $\sqrt{N}$。
    • I/O 成本： 两阶段的 I/O 成本也相同，都约为 $4N$。

  • 排序的优点 ️：

    • 有序输出： 如果最终输出本身就需要排序（例如 ORDER BY，或者用于排序归并连接），那么排序就是最佳选择，因为哈希无法提供有序性。
    • 对重复项和不良哈希不敏感： 排序算法不依赖于数据的分布或哈希函数的均匀性。它能稳定地处理大量重复项或数据分布极端的情况。

  • 哈希的优点 ：

    • 高效去重和分组： 在消除重复项时，哈希的效率取决于不重复值的数量，而不是项目的总数量（排序则取决于项目的数量）。在第一趟分区时就可以很早地删除重复项。
    • 易于并行化： 通过哈希函数将数据分发到不同机器上，更容易实现均匀分发，非常适合大规模并行处理。
    • 不需要全局排序： 对于只需分组或去重的场景，哈希比排序更轻量，因为它不需要维护全局的有序性。

关系操作符与连接算法 ​

是什么 (What it is) ​

关系操作符是数据库执行 SQL 查询的基本构建块。当用户提交一个 SQL 查询时，查询优化器会将其转换成一个由关系操作符组成的查询计划（Query Plan），这本质上是一个数据流图。每个操作符接收一个或多个数据流（表或中间结果），对其进行处理，然后产生一个输出流。

连接（Join）操作是其中最核心、最复杂的操作符之一，它负责根据指定的连接条件将两个或多个表中的记录组合起来。

为什么 (Why it's needed) ​

  • 模块化与可扩展性： 将复杂的查询分解为一系列标准化的操作符，使得查询处理逻辑清晰、易于管理和优化。可以为同一个逻辑操作（如 Join）提供多种物理实现算法，由优化器根据成本模型选择最优的一种。
  • 数据处理的“流水线”： 操作符通常以**迭代器模式（Iterator Pattern）**实现，上层操作符通过调用下层操作符的 next() 方法来“拉取”数据。这种“拉取”模型形成了高效的数据处理流水线，避免了在每一步都将中间结果物化到磁盘上。

怎么做 (How it works - The Iterator Model) ​

每个关系操作符都实现一个统一的迭代器接口，通常包含以下方法：

  • init(): 初始化操作符，分配资源，设置内部状态。
  • next(): 获取并返回处理后的下一条记录（Tuple）。如果数据流结束，则返回一个结束标记。
  • close(): 释放所有资源。

这种模型分为两种主要类型：

  • 流式（Streaming）操作符： 每次调用 next() 都能立即处理并返回一条记录，如 SELECT（筛选）和 PROJECT（投影）。
  • 阻塞（Blocking）操作符： 必须先消费其全部或大部分输入数据，然后才能产生第一条输出记录，如 SORT（排序）和 GROUP BY（分组聚合）。

连接算法详解 (Join Algorithms)： ​

在数据库中，连接操作就是把两个大表格里的数据按照某种规则“拼”成一个新表格。为了高效地完成这个任务，数据库系统内部有多种“拼装”策略。 咱们会用一些简单的约定来比较它们的效率（主要是磁盘 I/O，也就是“读写硬盘”的次数）。

核心约定：

  • 表X的页数：一个表占用的硬盘页面（数据块）数量。页面是硬盘读写的最小单位，可以理解为一个“数据包裹”。
  • 表X的总记录数：一个表里有多少条数据记录。
  • 内存缓冲区大小（页数）B：你当前能使用的内存空间有多大，用能装多少个“数据包裹”来衡量。

示例表格：

  • Reserves (预订表): 1000页，100,000 条记录。
  • Sailors (水手表): 500页，40,000 条记录。

1. 块嵌套循环连接 (Block Nested Loop Join, BNL)： “分批搬运、集中比对” ​

  • 是什么： 这是对最简单的“挨条比对”方式的巨大升级。它不是一条记录一条记录地比，而是将外层循环的表数据“分大块”读到内存，然后用内存里的这一大块数据，去和另一个表的全部数据进行比对。
  • 核心思想： 一次多读点，减少重复读。
  • 怎么做：
    1. 把外层循环的表（比如 Reserves 预订表）的数据，每次读取**内存缓冲区大小（页数）B 减去 2 页** 的大小，作为一个“大块”数据，加载到内存里。
    2. 对于内存里的这个**“大块”数据**，完整地扫描一遍内层循环的表（Sailors 水手表）的所有页面。
    3. 在内存中，把这个“大块”里的所有预订记录，和当前扫描到的 Sailors 页里的所有水手记录，逐一进行比对，找出匹配项。
    4. 重复此过程，直到 Reserves 表的所有“大块”数据都被处理完毕。
  • 读写硬盘成本： Reserves表页数 + (Reserves表总页数 / (内存缓冲区大小 - 2)) 向上取整 * Sailors表页数。
  • 示例计算 (内存缓冲区B=102页):1000 (读 Reserves) + (1000 / (102 - 2)) 向上取整 * 500 (读 Sailors) = 1000 + (10 * 500) = 6,000 次读写硬盘。
  • 优点： 通过最大化利用内存，显著减少了对内层表的重复扫描次数，是简单连接算法中非常有效且性能稳定的一个。

2. 索引嵌套循环连接 (Index Nested Loops Join, INL)： “查字典式”精确查找 📚🔍 ​

  • 是什么： 当内层循环的表的连接键上有索引时，这是一种极其高效的连接算法。它将对内层表的暴力扫描，转变为高效的索引查找。
  • 核心思想： 哪里有索引，就走哪里。
  • 怎么做：
    1. 逐一遍历外层循环表（比如 Reserves 预订表）的每一条记录。
    2. 对于 Reserves 表的每一条记录，取出它用来连接的那个值（比如 sid 水手ID）。
    3. 使用内层表（Sailors 水手表）在连接键上的索引，直接去**“查字典”**，快速定位并取出所有匹配该值（r.sid）的 Sailors 记录。
  • 读写硬盘成本： Reserves表页数 + (Reserves表总记录数 * 单次索引查找成本)。
    • 单次索引查找成本：取决于索引类型（B+ 树索引通常需要访问树的高度，外加读取实际匹配记录的页面）。
  • 示例计算 (非聚簇索引，假设每次匹配1条记录):1000 (读 Reserves) + 100,000 ( Reserves 记录数) * (3 (查索引树的高度) + 1 (读匹配记录页)) = 401,000 次读写硬盘。
  • 优点： 在有合适索引且匹配记录不多（“一对一”或“一对少”）的情况下，效率非常高。
  • 缺点： 性能高度依赖索引质量。如果没有合适的索引，或者一条外层记录能匹配内层表很多记录（导致多次随机读），效率会急剧下降。

3. 排序归并连接 (Sort-Merge Join, SMJ)： “排好队，再一起走” ​

  • 是什么： 一种分为“排序”和“归并（合并）”两个阶段的连接算法，只适用于等值连接。
  • 核心思想： 先让两边数据都有序，然后像拉链一样同步匹配。
  • 怎么做：
    1. 排序阶段： 分别使用外存排序算法（处理大数据的排序），根据连接键（比如 sid）对 Reserves 和 Sailors 两个表的所有数据进行排序。排序完成后，所有 sid 相同的记录都会紧挨着排列。
      • 注意：如果表上已经有基于连接键的聚簇索引（数据本身就是按 sid 排序的），那这一步就可以跳过，省下大量成本。
    2. 归并阶段（合并扫描）： 设置两个“扫描指针”，分别指向已排序的两个表的开头。然后，两个指针同步地向前移动，并进行比对：
      • 如果 Reserves 的 sid 小于 Sailors 的 sid，就推进 Reserves 的指针。
      • 如果 Reserves 的 sid 大于 Sailors 的 sid，就推进 Sailors 的指针。
      • 如果 Reserves 的 sid 等于 Sailors 的 sid，那么就找到了匹配！将 Reserves 的当前记录，与 Sailors 中所有有相同 sid 的记录进行匹配（可能需要“回溯” Sailors 的指针，处理多个匹配），然后同时推进两个指针。
  • 读写硬盘成本 (含排序):
    • 排序成本(Reserves) + 排序成本(Sailors) + 扫描合并成本(Reserves + Sailors)。
    • 两趟外存排序的成本大约是 4 * 表的页数。
    • 总成本约为 4 * Reserves表页数 + 4 * Sailors表页数 + Reserves表页数 + Sailors表页数 = 5 * (Reserves表页数 + Sailors表页数)。
  • 重要优化 (合并最后一趟归并与连接): 如果内存足够大，可以将排序的最后一步合并和连接操作结合起来做。
    • 优化后成本： 3 * (Reserves表页数 + Sailors表页数)。
    • 示例计算： 3 * (1000 + 500) = 4,500 次读写硬盘。
  • 优点：
    • 性能稳定，不受数据倾斜（某些 sid 值数据特别多）影响。
    • 输出结果自然有序，这对于后续需要数据倾斜：** 如果数据存在严重倾斜，排序归并连接 (SMJ) 比哈希连接更稳定。

关系查询优化I：计划空间 (Relational Query Optimization I: The Plan Space) ​

怎么做 (How it works) ​

数据库系统处理用户提交的 SQL 查询，并将其转化为实际执行的步骤。这个过程就像一个复杂的生产线，每一步都有专门的“工人”负责：

  1. SQL 客户端 (SQL Client): (用户界面)
    • 用户在这里输入他们的 SQL 查询。
  2. 查询解析与优化 (Query Parsing & Optimization): (大脑中枢)
    • 查询解析器 (Query Parser): 就像一个语法检查员，它会检查你写的 SQL 语句有没有语法错误，以及你是否有权限执行这个查询。如果没问题，它会把查询语句变成一个“解析树”，这是查询的初步结构表示。
    • 查询重写器 (Query Rewriter): 这是一个“整理专家”，它会把查询整理得更规范、更高效。比如，如果你的查询里有复杂的“视图”或者“子查询”，它会尝试把它们“扁平化”或者合并起来，让查询结构更简单。
    • 基于成本的查询优化器 (Cost-based Query Optimizer): 这是整个过程的“核心决策者”。
      • 它会把查询分解成一个个小的“查询块”（比如 SELECT、JOIN、GROUP BY 等）。
      • 然后，它会利用数据库里存储的目录统计信息 (catalog stats)（比如表有多少行、索引有多高等等），来估算执行每个查询块的各种可能方法的“成本”。
      • 最终目标是找到总成本最低的执行计划。不过，这就像找迷宫里的最短路径，有时它可能找不到真正的“最优”计划，但会找到一个足够好的。
  3. 计划成本估算器 (Plan Cost Estimator): (预算员)
    • 负责计算不同执行计划可能需要多少资源（比如读写磁盘的次数、CPU 消耗等）。
  4. 计划生成器 (Plan Generator): (方案设计师)
    • 根据查询的结构和数据库的现有条件（比如有没有索引），生成所有可能的执行方案。
  5. 查询执行器 (Query Executor): (实际执行者)
    • 一旦优化器选定了最佳计划，查询执行器就负责按照这个计划一步步地执行操作。
  6. 关系操作符 (Relational Operators): (具体操作工人)
    • 这些是执行关系代数操作（比如连接两个表、筛选数据、对数据分组等）的具体算法。
  7. 文件和索引管理 (Files and Index Management): (仓库管理员)
    • 负责管理数据文件在磁盘上的存放，以及各种索引的结构，确保数据能够被高效地读取和写入。

查询优化是魔法 (Query Optimization is Magic) ​

是什么 (What it is) ​

查询优化就像一座桥梁，连接了你用 SQL 告诉数据库“你想要什么”（声明性语言），以及数据库内部“如何计算才能得到你想要的东西”（命令式程序）。它把你的“愿望”变成了具体的“行动计划”。

一些历史 (A little history) ​

这个“魔法”是由 Pat Selinger 等人在 1979 年发明的。我们主要会关注“System R”优化器 (System R Optimizer)，这是最早也是影响深远的一种优化器。还有另一种常见的优化器叫做“Cascades”优化器 (Cascades Optimizer)。

查询优化概述 (Query Optimization Overview) ​

是什么 (What it is) ​

查询优化的目标很简单：找到执行给定查询的最有效率（也就是成本最低）的执行计划。

组成部分 (The Components) ​

查询优化主要有三个相互独立但又紧密相关的部分：

  1. 计划空间 (Plan space): (所有可能的路径)
    • 对于一个特定的查询，有哪些不同的执行方案可以考虑？这就像一个地图，上面标记了所有可能的路线。
  2. 成本估算 (Cost estimation): (计算每条路径的开销)
    • 如何准确地估算每条执行方案需要消耗多少资源（比如读写磁盘的次数、CPU 时间）？
  3. 搜索策略 (Search strategy): (找到最佳路径的方法)
    • 如何在所有可能的执行方案中，高效地找到那个成本最低的“最优”方案？

目标 (The Goal) ​

  • 理想情况: 找到实际执行时成本最低的那个计划。
  • 现实情况: 找到估算成本最低的计划，并尽量避免那些在实际执行中表现非常糟糕的计划。

关系代数等价性 (Relational Algebra Equivalences) ​

关系代数等价性是查询优化的基础，它们允许优化器在不改变查询结果的情况下，改变查询的执行顺序或结构。

选择 (Selections) ​

选择操作（WHERE 子句）用于从表中筛选出符合特定条件的记录。

  1. 级联 (Cascade):
    • 是什么: 多个选择条件可以合并成一个，也可以分解成多个连续的选择操作。
    • 例子: 筛选出年龄大于 20 并且 部门是“销售”的员工，等价于先筛选年龄大于 20 的员工，再从这些员工中筛选部门是“销售”的员工。
  2. 交换 (Commute):
    • 是什么: 多个选择条件的执行顺序可以互换，结果不变。
    • 例子: 先筛选年龄大于 20 的员工，再筛选部门是“销售”的员工，和先筛选部门是“销售”的员工，再筛选年龄大于 20 的员工，结果是一样的。

投影 (Projections) ​

投影操作（SELECT 子句）用于选择表中的特定列。

  1. 级联 (Cascade):
    • 是什么: 多个投影操作可以合并成一个，只保留最终需要的列。
    • 例子: 如果你先选择员工的姓名和年龄，然后又从这些结果中只选择姓名，那么实际上你只需要一步就选择姓名。

笛卡尔积 (Cartesian Product) ​

笛卡尔积是两个表中所有记录的组合，会产生非常大的结果集。

  1. 结合性 (Associative):
    • 是什么: 多个笛卡尔积的计算顺序可以改变，结果不变。
    • 例子: 表A × (表B × 表C) 等价于 (表A × 表B) × 表C。
  2. 交换性 (Commutative):
    • 是什么: 两个表的笛卡尔积顺序可以互换，结果不变。
    • 例子: 表A × 表B 等价于 表B × 表A。

连接是否具有结合性和交换性？ (Are Joins Associative and Commutative?) ​

  • 是什么: 连接操作可以看作是带有特定筛选条件（连接条件）的笛卡尔积。因此，从理论上讲，它们也具有结合性和交换性。
  • 注意: 要警惕连接退化为笛卡尔积的情况。
    • 例子: 假设有 表S、表T、表R。如果 (表S 连接条件b=b 表T) 连接条件a=a 表R，但第二个连接条件 a=a 实际上只适用于 表T 和 表R，那么它可能会变成 表T × 表R，这和预期可能不同。优化器需要识别并避免这种情况。

一些常见的启发式规则 (Some Common Heuristics) ​

启发式规则是优化器在面对复杂查询时，用来快速做出“好”决策的经验法则。

选择级联和下推 (Selection cascade and pushdown) ​

  • 是什么: 尽可能早地应用筛选条件。只要筛选条件涉及的列在当前阶段可用，就立即进行筛选。
  • 为什么需要: 这可以显著减少中间结果的大小。想象一下，如果你要从一个包含 100 万条记录的表中找出年龄大于 30 岁的员工，并且只关心他们的部门信息。如果你先筛选出年龄大于 30 岁的员工（可能只剩下 10 万条），然后再进行后续操作，比你先进行其他操作再筛选要高效得多。这就像在流水线的最前端就剔除不合格的零件，避免后续的无用加工。
  • 例子: 查询 SELECT S.姓名 FROM 预订表 R, 水手表 S WHERE R.水手ID=S.水手ID AND R.船ID=100 AND S.评级>5。
    • 优化器会倾向于在连接 预订表 和 水手表 之前，先从 预订表 中筛选出 船ID=100 的记录，并从 水手表 中筛选出 评级>5 的记录。这样，参与连接的数据量就大大减少了。

投影级联和下推 (Projection cascade and pushdown) ​

  • 是什么: 只保留下游操作符需要的列。
  • 为什么需要: 减少每条记录的宽度，从而减少数据传输和处理的成本。如果你只需要员工的姓名，那么在处理过程中就没必要一直带着他们的地址、电话等其他信息。
  • 例子: 在连接 预订表 和 水手表 之前，如果最终只需要 水手姓名，那么优化器会只保留 预订表 的 水手ID 列（用于连接），以及 水手表 的 姓名 和 水手ID 列。这样，处理的数据量就变小了。

避免笛卡尔积 (Avoid Cartesian products) ​

  • 是什么: 在可能的情况下，优先使用带有连接条件的连接（比如 INNER JOIN）而不是笛卡尔积（CROSS JOIN）。
  • 为什么需要: 笛卡尔积会产生非常大的中间结果，效率极低。如果 表A 有 100 条记录，表B 有 100 条记录，它们的笛卡尔积将有 100 * 100 = 10,000 条记录。如果再和 表C 进行笛卡尔积，结果会呈指数级增长。
  • 例子: 对于 表R(a,b), 表S(b,c), 表T(c,d)，优化器会倾向于选择 (表R 连接 表S) 连接 表T 这样的连接顺序，而不是 (表R × 表T) 连接 表S。

物理等价性 (Physical Equivalences) ​

物理等价性指的是不同的底层实现算法，它们可以实现相同的逻辑操作。优化器会根据成本模型选择最适合的物理实现。

基本表访问 (Base table access) ​

  • 堆扫描 (Heap scan):
    • 是什么: 简单地从头到尾扫描整个表，读取所有数据。
  • 索引扫描 (Index scan):
    • 是什么: 如果表上有索引，可以使用索引来快速定位和读取需要的数据，而不是扫描整个表。这通常效率更高。

等值连接 (Equijoins) ​

等值连接是连接条件为 = 的连接操作。

  • 块嵌套循环连接 (Block Nested Loop):
    • 是什么: 简单但有效的连接方法，它一次读取外层表的一大块数据到内存，然后用这块数据与内层表的全部数据进行比较。
  • 索引嵌套循环连接 (Index Nested Loop):
    • 是什么: 当内层表的连接键上有索引时，它会对外层表的每一条记录，利用索引直接在内层表中查找匹配的记录。效率很高，但依赖索引。
  • 排序归并连接 (Sort-Merge Join):
    • 是什么: 适用于等值连接。它会先将两个表都按照连接键进行排序，然后像拉链一样同步扫描和合并已排序的两个表，找出匹配项。
  • Grace 哈希连接 (Grace Hash Join):
    • 是什么: 一种基于哈希的分区和连接方法。它将两个表的数据都通过哈希函数分成多个小分区，然后对每个分区在内存中进行哈希连接。
  • 混合连接 (Hybrid Join):
    • 是什么: 结合了其他连接方法的优点，例如将哈希连接和嵌套循环连接结合起来。

非等值连接 (Non-Equijoins) ​

非等值连接是连接条件不是 = 的连接操作（例如 >、<、BETWEEN 等）。

  • 块嵌套循环连接 (Block Nested Loop):
    • 是什么: 通常用于非等值连接，因为其他更高效的连接算法（如排序归并连接、哈希连接）通常只适用于等值连接。

激励性例子 (Motivating Example) ​

让我们通过一个具体的查询例子，看看优化器是如何选择不同计划的。

查询: SELECT S.sname FROM Reserves R, Sailors S WHERE R.sid=S.sid AND R.bid=100 AND S.rating>5。 这个查询的目标是找出那些预订了船号为 100 的船，并且评级高于 5 的水手的姓名。

表结构和假设:

  • 水手表 (Sailors): 包含 水手ID (sid)、姓名 (sname)、评级 (rating)、年龄 (age)。
    • 每条记录 50 字节，每页可以存 80 条记录，总共有 500 页。
    • 假设有 10 种不同的 评级 值。
  • 预订表 (Reserves): 包含 水手ID (sid)、船ID (bid)、日期 (day)、预订名称 (rname)。
    • 每条记录 40 字节，每页可以存 100 条记录，总共有 1000 页。
    • 假设有 100 艘船。
  • 可用内存: 5 页用于连接操作。

计划 1: 朴素的页嵌套循环连接 (Naive Page Nested Loop Join) ​

  • 是什么: 这是最简单、最直接的连接方式。它会逐页地扫描外层表，然后对于外层表的每一页，都完整地扫描一遍内层表。
  • 成本:
    • 扫描 水手表 (500 次 I/O)
    • 对于 水手表 的每页，扫描 预订表 (500 页 * 1000 页 = 500,000 次 I/O)
    • 总成本: 500 + 500,000 = 500,500 次 I/O。
  • 分析: 这个计划非常低效，因为它没有利用任何优化机会，比如提前筛选数据或者利用索引。

计划 2: 选择下推 (Selection Pushdown) ​

  • 是什么: 将筛选条件 S.rating > 5 尽可能早地应用到 水手表 的扫描之后。
  • 成本:
    • 扫描 水手表 (500 次 I/O)
    • 假设 S.rating > 5 筛选掉了 水手表 一半的记录，剩下 250 页。
    • 对于符合条件的 水手表 页面（250 页），扫描 预订表 (250 页 * 1000 页 = 250,000 次 I/O)。
    • 总成本: 500 + 250,000 = 250,500 次 I/O。
  • 比较: 比计划 1 有所改进，因为减少了内层循环的次数。

计划 3: 更多选择下推 (More Selection Pushdown) ​

  • 是什么: 除了 S.rating > 5，也将 R.bid = 100 的筛选条件推到 预订表 的扫描之后。
  • 成本: 即使将 R.bid = 100 推到内部循环，预订表 的每次扫描仍然是全表扫描，所以 I/O 成本并没有改变。
  • 总成本: 250,500 次 I/O。
  • 分析: 逻辑上更合理，但在这个朴素连接算法下，对 I/O 成本没有进一步的节省。

计划 4: 连接顺序优化 (Join Ordering) ​

  • 是什么: 改变连接的顺序，先连接 预订表 和 水手表。并且先扫描 预订表，再扫描 水手表。
  • 成本:
    • 扫描 预订表 (1000 次 I/O)
    • 假设 R.bid = 100 筛选后，预订表 只剩下 10 页数据。
    • 对于筛选后的 预订表 的每页（10 页），扫描 水手表 (10 页 * 500 页 = 5,000 次 I/O)。
    • 总成本: 1000 + 5,000 = 6,000 次 I/O。
  • 比较: 相较于计划 3，这是一个巨大的进步！通过改变连接顺序和提前筛选，I/O 成本大幅下降。

计划 5: 物化内循环 (Materializing Inner Loops) ​

  • 是什么: 在执行连接之前，先将满足条件的 预订表 (bid=100) 和 水手表 (rating>5) 的结果分别保存到临时表（物化）。
  • 成本:
    • 扫描 预订表 (1000 次 I/O)
    • 扫描 水手表 (500 次 I/O)
    • 物化满足 预订表 条件的临时表 T2 (假设 10 页) (10 次 I/O)
    • 物化满足 水手表 条件的临时表 T1 (假设 250 页) (250 次 I/O)
    • 对 T2 的每个块扫描 T1 (10 页 * 250 页 = 2,500 次 I/O)
    • 总成本: 1000 + 500 + 10 + 250 + 2,500 = 4,250 次 I/O。
  • 比较: 比计划 4 略有改进。

计划 6: 连接顺序与物化 (Join Ordering with Materialization) ​

  • 是什么: 类似于计划 5，但改变了物化表的扫描顺序，先扫描 T1（水手）再扫描 T2（预订）。
  • 成本:
    • 扫描 水手表 (500 次 I/O)
    • 扫描 预订表 (1000 次 I/O)
    • 物化 T1 (250 次 I/O)
    • 物化 T2 (10 次 I/O)
    • 对 T1 的每个块扫描 T2 (250 页 * 10 页 = 2,500 次 I/O)
    • 总成本: 500 + 1000 + 250 + 10 + 2,500 = 4,010 次 I/O。
  • 比较: 比计划 5 略优，因为 T1 更大，作为外层表时可以减少内层表的扫描次数。

计划 7: 排序归并连接 (Sort-Merge Join) ​

  • 是什么: 使用排序归并连接算法，利用 5 个内存缓冲区。
  • 成本:
    • 扫描 预订表 (1000 次 I/O)
    • 扫描 水手表 (500 次 I/O)
    • 排序 预订表 (假设 30 次 I/O)
    • 排序 水手表 (假设 1500 次 I/O)
    • 合并阶段 (260 次 I/O)
    • 总成本: 1000 + 500 + 30 + 1500 + 260 = 3,540 次 I/O。
  • 比较: 比计划 6 更好。

计划 8: 排序归并连接与物化 (Sort-Merge Join with Materialization) ​

  • 是什么: 在排序归并连接之前，先物化中间结果。
  • 成本:
    • 扫描 预订表 (1000 次 I/O)
    • 写 T2 (10 次 I/O)
    • 扫描 水手表 (500 次 I/O)
    • 写 T1 (250 次 I/O)
    • 排序 T2 (40 次 I/O)
    • 排序 T1 (4000 次 I/O)
    • 合并阶段 (260 次 I/O)
    • 总成本: 1000 + 10 + 500 + 250 + 40 + 4000 + 260 = 4,060 次 I/O。
  • 比较: 劣于计划 7，因为物化增加了额外的 I/O 成本。

计划 9: 块嵌套循环连接与物化 (Block Nested Loop Join with Materialization) ​

  • 是什么: 使用块嵌套循环连接，并物化中间结果。
  • 成本:
    • 扫描 水手表 (500 次 I/O)
    • 扫描 预订表 (1000 次 I/O)
    • 写 T1 (10 次 I/O)
    • 对于高评分 sailor 的每个块循环 T1 (假设 T1 有 250 页，每块 3 页，则 250/3 向上取整是 84 块。每块扫描 T1 10 页) (84 * 10 = 840 次 I/O)
    • 总成本: 500 + 1000 + 10 + 840 = 2,350 次 I/O。
  • 比较: 优于计划 7。

计划 11: 无物化的块嵌套循环连接，重新排序 (Block Nested Loop Join without Materialization, Reordered) ​

  • 是什么: 先扫描 预订表，对 bid=100 进行筛选，然后将筛选后的结果作为外循环，与 水手表 进行连接。
  • 成本:
    • 扫描 预订表 (1000 次 I/O)
    • 对于 bid=100 的 预订表 中的每个块（假设筛选后剩下 10 页，每块 1 页），扫描 水手表 (10 页 * 500 页 = 5,000 次 I/O)。
    • 总成本: 1000 + 5,000 = 1,500 次 I/O。
  • 比较: 这是目前最优的计划，比之前的 2,350 次 I/O 又少了很多。

索引如何？ (How About Indexes?) ​

  • 假设: 预订表.船ID 上有聚簇索引 (clustered index)（这意味着数据在磁盘上是按照 船ID 的顺序存储的），水手表.水手ID 上有非聚簇索引 (non-clustered index)（索引和数据分开存储），并且这些索引都足够小，可以放入内存。
  • 成本分析:
    • 对 预订表 进行 船ID=100 的索引扫描（因为是聚簇索引，数据是连续的）：只需要读取 10 页。
    • 对于每条 预订表 元组（假设有 1000 条），通过 水手表.水手ID 的非聚簇索引查找匹配的 水手表 元组：每条记录需要 1 次 I/O（查找索引并读取数据页）。所以是 1000 * 1 = 1000 次 I/O。
    • 总成本: 10 + 1000 = 1,010 次 I/O。
  • 比较: 这是目前所有计划中成本最低的，比之前的 1,500 次 I/O 又少了很多。这充分说明了索引在查询优化中的巨大作用。

关系查询优化II：成本计算与搜索 (Relational Query Optimization II: Costing and Searching) ​

查询优化需要什么？ (What is needed for query optimization?) ​

要实现高效的查询优化，数据库系统需要以下几个核心要素：

  1. 一组封闭的操作符 (A closed set of operators):
    • 是什么: 数据库中的所有操作（比如读取数据、连接表、筛选、排序等）都应该被定义为标准化的“操作符”。这些操作符的输入是表，输出也是表（或者可以被看作是表的数据流）。
    • 为什么需要: 这使得优化器可以灵活地组合和替换不同的操作符，形成各种执行计划。每个操作符通常还有多种“物理实现”（比如连接操作可以有嵌套循环、排序归并等多种算法）。
  2. 计划空间 (Plan space):
    • 是什么: 这是所有可能的查询执行计划的集合。这些计划是基于关系代数等价性规则（比如连接顺序可以改变）和不同的物理实现方式（比如选择不同的连接算法）组合而成的。
    • 为什么需要: 优化器需要知道它有多少种“路径”可以选择。
  3. 成本估算 (Cost Estimation):
    • 是什么: 评估每个执行计划需要消耗多少资源。
    • 怎么做:
      • 基于成本公式 (cost formula)：每个操作符都有一个公式来计算其成本（比如扫描 100 页需要多少 I/O）。
      • 基于大小估算 (size estimation)：这又依赖于数据库目录信息 (catalog information)（比如表有多少行、多少页）和选择性 (selectivity)（筛选条件能减少多少数据）的估算。
    • 为什么需要: 优化器需要一个“预算员”来告诉它哪条路径更“便宜”。
  4. 搜索算法 (A search algorithm):
    • 是什么: 在庞大的“计划空间”中，高效地找到成本最低的那个计划的方法。
    • 为什么需要: 计划空间可能非常大，需要智能的算法来避免盲目搜索。

我们主要关注“System R”优化器 (System R Optimizer)，它是一个非常全面的框架，即使在今天，其思想仍在不断研究和改进。

System R优化器概览 (Big Picture of System R Optimizer) ​

是什么 (What it is) ​

System R 优化器是一个经典的、基于成本的查询优化框架。

怎么做 (How it works) ​

  • 适用范围: 对于包含 10-15 个连接的查询，System R 优化器通常能表现良好。
  • 计划空间 (Plan Space):
    • 问题: 完整的计划空间可能非常庞大，优化器必须进行“剪枝”(Pruning) 来缩小搜索范围。
    • 算法洞察 (Algorithmic insight): 许多不同的计划可能包含相同的、高成本的子查询部分。优化器可以识别并避免重复计算这些子树的成本。
    • 常见启发式 (Common heuristic):
      • 只考虑左深计划 (left-deep plans): 这是一种特殊的连接树结构，其中右侧的分支总是连接一个基本表。这有助于限制搜索空间，并且通常可以实现完全的“流水线化”执行，即中间结果不需要写入临时文件。
      • 避免笛卡尔积 (Cartesian products): 优化器会尽量避免生成笛卡尔积，因为它们通常效率很低。
  • 成本估算 (Cost estimation):
    • 特点: System R 的成本估算最初可能不是很精确，但在实践中运行良好。
    • 怎么做: 它使用系统目录中存储的统计信息来估算每个操作的结果大小和成本。它同时考虑 CPU 和 I/O 成本。
    • 发展: System R 的成本估算方案后来得到了改进。
  • 搜索算法 (Search Algorithm):
    • 是什么: System R 优化器使用**动态规划 (Dynamic Programming)**来搜索最优计划。这是一种通过分解子问题并存储子问题解来解决复杂问题的方法。

查询块：优化单元 (Query Blocks: Units of Optimization) ​

是什么 (What it is) ​

为了管理查询优化的复杂性，优化器会将一个大的查询分解成更小的、独立的“查询块”(Query Blocks)，然后一次优化一个块。

怎么做 (How it works) ​

  • 分解:
    • 不相关的嵌套查询块（比如子查询的结果不依赖于外部查询的任何值）会只计算一次。
    • 相关的嵌套查询块（比如子查询的结果依赖于外部查询的值）则像函数调用一样处理（有时可以进行“去关联化”优化 (de-correlation)，但这超出了本课程的范围）。
    • 例子: 在查询 SELECT S.姓名 FROM 水手表 S WHERE S.年龄 IN (SELECT MAX(S2.年龄) FROM 水手表 S2 GROUP BY S2.评级) 中，SELECT MAX(S2.年龄) ... 就是一个独立的嵌套查询块，它会先被优化和执行，然后其结果再用于外部的查询块。
  • 每个块的计划: 对于每个查询块，优化器会考虑以下类型的计划：
    • FROM 子句中涉及的每个表的所有相关访问方法 (access methods)（比如是全表扫描还是走索引）。
    • 所有左深连接树 (left-deep join trees)：这意味着连接操作的右侧分支总是连接一个基本表。优化器会考虑所有可能的连接顺序和连接方法。

回顾代数等价性 (Recall Algebra Equivalences) ​

我们再次回顾一下之前学过的关系代数等价性，它们是优化器重写查询的基础：

选择 (Selections) ​

  • 级联 (Cascade):
    • 是什么: 多个选择条件可以合并或分解。
    • 例子: 筛选出 年龄大于20 并且 部门是“销售” 的员工，等价于先筛选 年龄大于20 的员工，然后从这些结果中再筛选 部门是“销售” 的员工。
  • 交换 (Commute):
    • 是什么: 选择条件的顺序可以改变。
    • 例子: 先筛选年龄大于20，再筛选部门是“销售” 的员工，等价于 先筛选部门是“销售”，再筛选年龄大于20 的员工。

投影 (Projections) ​

  • 级联 (Cascade):
    • 是什么: 多个投影可以合并。
    • 例子: 先选择姓名和年龄，再从这些中选择姓名，等价于 直接选择姓名。

笛卡尔积 (Cartesian Product) ​

  • 结合性 (Associative):
    • 是什么: 表R × (表S × 表T) 等价于 (表R × 表S) × 表T。
  • 交换性 (Commutative):
    • 是什么: 表R × 表S 等价于 表S × 表R。

更多关系代数等价性 (More R. A. Equivalences) ​

除了基础的等价性，还有一些更高级的规则：

  • 预先投影 (Eager projection):
    • 是什么: 可以在操作流中尽早地将那些后续不再需要的列从数据中移除。
    • 例子: 如果你最终只关心员工的姓名和部门，那么在进行连接操作之前，就可以只保留这两个列，而丢弃员工的薪水、电话等其他列。
  • 笛卡尔积上的选择等价于连接 (Selection on a cross-product is equivalent to a join):
    • 是什么: 如果一个笛卡尔积后面紧跟着一个筛选条件，并且这个筛选条件比较的是来自不同关系的属性，那么这个组合实际上就等价于一个连接操作。
    • 例子: 对 (表R × 表S) 进行筛选条件为 R.a=S.b 的操作，等价于 表R 连接条件R.a=S.b 表S。
  • 选择下推 (Selection pushdown):
    • 是什么: 如果一个筛选条件只作用于某个关系（比如 表R 的属性），那么这个筛选条件可以和 表R 连接 表S 交换位置，即可以先对 表R 进行筛选，然后再进行连接。
    • 例子: 对 (表R 连接 表S) 进行筛选条件为 R.年龄>30 的操作，等价于 对表R进行筛选条件为 R.年龄>30 的操作，然后再连接表S。前提是这个筛选条件不涉及 表S 的任何属性。

“物理”属性 (“Physical” Properties) ​

是什么 (What it is) ​

某些操作符的输出可能具有特定的“物理”属性，这些属性可能被后续的操作符利用，从而提高整个查询计划的效率。

常见属性 (Common properties) ​

  1. 排序顺序 (Sort order):
    • 是什么: 数据是按照某个或某些列的值有序排列的。
    • 例子: 索引扫描（特别是聚簇索引 (clustered index)）和排序操作会产生有序的输出。
  2. 哈希分组 (Hash Grouping):
    • 是什么: 数据是根据某个哈希函数的值被分组的，具有相同哈希值的记录被放在一起。
    • 例子: 哈希操作会产生分组的输出，例如哈希连接 (hash join) 或哈希聚合 (hash aggregation)。

重要性 (Importance) ​

  • 某些操作符需要有序输入: 比如，排序归并连接 (Sort-Merge Join) 就需要它的输入表是已经排序好的。如果输入无序，那么在连接之前就必须先进行一次排序操作，这会增加成本。
  • 某些操作符可以保留排序顺序: 比如，合并连接 (Merge Join) 和嵌套循环连接 (Nested Loop Join) 在执行时，如果输入是排序的，它们的输出也可能保持排序顺序。这对于后续需要排序的操作（比如 ORDER BY 或 GROUP BY）来说，可以避免额外的排序成本。

物理等价计划 (Physically Equivalent Plans) ​

是什么 (What it is) ​

物理等价计划指的是那些执行后产生相同内容并且具有相同物理属性的计划。虽然它们最终的结果一样，但实现方式可能完全不同。

例子 (Example) ​

假设我们要连接 水手表 和 预订表，连接条件是 水手ID 相等。

  • 你可以通过排序归并连接 (Sort-Merge Join) 来实现：先对两个表按 水手ID 排序，然后合并。这个计划的输出是按 水手ID 排序的。
  • 你也可以通过 Grace 哈希连接 (Grace Hash Join) 来实现：对两个表按 水手ID 进行哈希分区，然后对每个分区在内存中进行哈希连接。这个计划的输出是无序的，但相同 水手ID 的记录会被分到一起。

虽然它们都完成了连接操作，但一个产生了有序结果，另一个没有。如果后续操作需要有序结果，那么排序归并连接的计划就更“物理等价”于那个需求。

多关系查询 (Queries Over Multiple Relations) ​

System R 启发式 (System R heuristic) ​

当查询涉及多个表（关系）的连接时，System R 优化器会采用一些启发式规则来限制搜索空间，提高效率：

  • 只考虑左深连接树 (left-deep join trees):
    • 是什么: 这种连接树的结构是，每次连接操作的右侧输入总是一个基本表（而不是另一个连接的结果）。
    • 为什么需要: 这大大限制了可能的连接顺序组合，从而缩小了搜索空间。同时，这种结构通常允许优化器生成所有可以完全“流水线化”执行 (fully pipelined execution) 的计划，这意味着中间结果不需要写入临时文件，可以直接从一个操作符流向下一个操作符，减少了磁盘 I/O。
    • 注意: 并非所有左深树都是完全流水线化的（例如，排序归并连接可能需要阻塞，等待排序完成）。

计划空间回顾 (Plan Space Review) ​

完整计划空间 (Full plan space) ​

  • 是什么: 对于一个 SQL 查询，完整的计划空间包含了所有可能的执行计划。这包括了基于我们之前学习的代数等价规则（比如连接顺序可以变）所能得到的所有等价关系代数表达式，以及这些代数表达式的所有可能的物理实现组合（比如选择不同的连接算法）。

剪枝 (Pruning) ​

  • 是什么: 由于完整的计划空间非常巨大，优化器必须进行“剪枝”(Pruning)，即排除那些明显低效或不必要的计划，从而缩小搜索范围。
  • 怎么做: 可以通过以下方式进行剪枝：
    • 选择/投影下推 (Selection/Projection Pushdown): 尽可能早地应用筛选和选择列的操作，减少中间数据量。
    • 只考虑左深树 (Left-Deep Trees): 限制连接树的结构，减少连接顺序的组合。
    • 避免笛卡尔积 (Avoid Cartesian Products): 除非万不得已，否则不生成笛卡尔积。
  • 关注物理属性: 在优化过程中，我们可能还会特别关注像“排序”这样的物理属性，因为下游操作可能依赖它们。如果一个操作符能够产生有序的结果，那么后续操作就不需要再额外排序，这可以节省大量成本。

查询优化：成本估算 (Query Optimization: Cost Estimation) ​

是什么 (What it is) ​

成本估算就是为每个可能的执行计划计算一个总的“开销”数字。这需要估算计划树中每个操作的成本，以及每个操作产生的结果集的大小。

怎么做 (How it works) ​

  • 每个操作的成本 (Cost of each operation):
    • 每个操作（比如顺序扫描 (sequential scan)、索引扫描 (index scan)、各种连接算法等）都有一个计算其成本的公式。这个成本通常取决于其输入数据的大小（基数 (cardinality)）。
  • 每个操作的结果大小 (Size of result for each operation):
    • 每个操作的输出结果大小会成为其下游操作的输入大小。因此，准确估算中间结果的大小至关重要。这依赖于输入关系的统计信息 (statistics)。
  • 假设 (Assumptions):
    • 对于筛选条件和连接条件，优化器通常会假设谓词之间是独立的 (independent)。这意味着一个筛选条件的效果不会影响另一个筛选条件的效果。
  • System R 成本模型 (System R cost):
    • System R 简化了成本计算，将其表示为一个单一的数字：I/O 次数 + CPU 因子 × 元组数量。其中 CPU 因子 是一个权重，用来衡量 CPU 消耗相对于 I/O 的重要性。

统计信息和目录 (Statistics and Catalogs) ​

  • 是什么: 数据库系统需要关于其内部存储的数据和索引的详细信息，这些信息通常存储在系统目录 (system catalog) 中。
  • 常见统计信息 (Common statistics):
    • NTuples: 表中的总记录数（基数）。
    • NPages: 表在磁盘上占用的总页数。
    • Low/High: 列中的最小值/最大值，用于估算范围查询的选择性。
    • Nkeys: 列中不同值的数量，用于估算等值查询的选择性。
    • IHeight: 索引的高度 (index height)（对于 B+ 树索引，这决定了查找一条记录需要访问多少层）。
    • INPages: 索引在磁盘上占用的总页数。
  • 更新 (Update): 这些目录统计信息通常是定期更新的，而不是实时更新，因为持续更新的成本太高。现代数据库系统会维护更详细的数据值统计信息，例如直方图 (histograms)。

大小估算和选择性 (Size Estimation and Selectivity) ​

  • 最大输出基数 (Max output cardinality):
    • 对于没有筛选条件的笛卡尔积，最大输出记录数就是输入关系记录数的乘积。
  • 选择性 (sel) (Selectivity):
    • 是什么: 与每个筛选条件相关联的一个值，它反映了这个条件能将结果集缩小多少。选择性通常定义为 |输出记录数| / |输入记录数|。
    • 注意: 在日常英语中，“高选择性”可能意味着筛选效果好，但在这里，高选择性值（接近 1）意味着筛选效果差，结果集几乎没变；低选择性值（接近 0）意味着筛选效果好，结果集大大缩小。
  • 结果大小估算 (Result Size Estimation):
    • 公式: 最终结果记录数 = 原始最大记录数 × 所有筛选条件选择性的乘积。
  • 常见筛选条件的选择性估算:
    • 条件 列 = 值 (如果 列 上有 Nkeys(I) 个不同值): 选择性 = 1 / 不同值的数量。
      • 例子: 如果 部门 列有 10 个不同的部门，筛选 部门 = '销售' 的选择性就是 1/10 = 0.1。
    • 条件 列1 = 列2 (对连接也很有用): 选择性 = 1 / MAX(列1的不同值数量, 列2的不同值数量)。
      • 例子: 连接 员工表 和 部门表 的条件是 员工.部门ID = 部门.部门ID。如果 员工.部门ID 有 100 个不同值，部门.部门ID 有 10 个不同值，那么选择性是 1 / MAX(100, 10) = 1/100 = 0.01。
    • 条件 列 > 值: 选择性 = (列的最大值 - 值) / (列的最大值 - 列的最小值 + 1)。
      • 例子: 如果 年龄 列的范围是 18 到 60，筛选 年龄 > 40 的选择性就是 (60 - 40) / (60 - 18 + 1) = 20 / 43 ≈ 0.465。
  • 缺失统计信息 (Missing stats): 如果缺少所需的统计信息，优化器通常会采用一个默认的猜测值，比如假定选择性为 1/10。
  • Postgres 默认选择性估算 (Postgres default selectivity estimation):
    • 相等条件：0.005。
    • 不等条件：0.3333333333333333。
    • 范围不等条件：0.005。
    • 匹配模式操作符（如 LIKE）：0.005。
    • 默认不同值数量：200。

缩减因子与直方图 (Reduction Factors & Histograms) ​

  • 是什么: 为了更精确地估算选择性，数据库系统会使用直方图 (histograms)。一个 10 桶的等深直方图会将数据分成 10 个大致相等的“十分位数”。
  • 常见技巧 (Common trick): “端点偏置”直方图 (end-biased histogram)，它会把那些出现频率非常高的值单独放到一个桶里，以避免这些“热点”数据对整体估算造成偏差。

使用直方图计算选择性 (Computing selectivity with histograms) ​

  • 例子: 假设有 100 行数据。
    • 如果筛选条件 销售额 > 99 的选择性是 50% (即有 50 行符合)。
    • 如果筛选条件 年龄 < 26 的选择性是 46% (即有 46 行符合)。

合取（AND）的选择性 (Selectivity of Conjunction) ​

  • 假设 (Assumption): 优化器通常假设多个谓词是独立的。
  • 公式 (Formula): 总选择性 = 各个谓词选择性的乘积。
  • 例子: 销售额 > 99 AND 年龄 < 26 的选择性为 50% × 46% = 23%。

析取（OR）的选择性 (Selectivity of Disjunction) ​

  • 公式 (Formula): 总选择性 = 谓词1选择性 + 谓词2选择性 - (谓词1选择性 × 谓词2选择性)。
  • 例子:
    • 销售额 > 99 OR 利润 < 60 的选择性为 50% + 3% = 53%。
    • 销售额 > 99 OR 年龄 < 26 的选择性为 50% + 46% - (50% × 46%) = 96% - 23% = 73%。

要点 (Upshot) ​

  • 理解如何计算基本筛选条件的选择性（无论是 Selinger 的原始版本还是使用直方图的版本）非常重要。
  • 假设 1 (Assumption 1): 直方图桶内的值是均匀分布的。
  • 假设 2 (Assumption 2): 所有的筛选条件都是相互独立的。
  • 连接操作的选择性计算也类似，只需计算所有谓词的选择性，并乘以表大小的乘积。

替代计划的枚举 (Enumeration of Alternative Plans) ​

优化器会系统地探索各种可能的执行计划。

两种主要情况 (Two main cases) ​

  1. 单表计划 (Single-table plans): (基本情况)
    • 是什么: 只涉及一个表的查询计划。
    • 怎么做: 优化器会考虑所有可用的访问路径 (access paths)（全文件扫描 (file scan) 或索引 (index)）。它会选择估算成本最低的那个。筛选（SELECT）和投影（PROJECT）操作通常会立即完成，结果会直接“流水线化” (pipelined) 到后续的分组或聚合操作中。
  2. 多表计划 (Multiple-table plans): (归纳)。

单关系计划的成本估算 (Cost Estimates for Single-Relation Plans) ​

  • 主键索引匹配选择 (Index I on primary key matches selection):
    • 成本: 对于 B+ 树索引，成本大约是 (索引高度 (Height(I)) + 1) + 1 (查找索引并读取数据页)。
  • 聚簇索引匹配选择 (Clustered index I matching selection):
    • 成本: (索引页数 (NPages(I)) + 表页数 (NPages(R))) × 选择性 (selectivity)。因为聚簇索引的数据是按顺序存储的，所以读取匹配的数据页通常是连续的。
  • 非聚簇索引匹配选择 (Non-clustered index I matching selection):
    • 成本: (索引页数 (NPages(I)) + 表记录数 (NTuples(R))) × 选择性 (selectivity)。因为非聚簇索引的数据可能分散在磁盘上，所以每找到一条匹配记录，可能都需要一次随机 I/O 来读取其数据页。
  • 文件顺序扫描 (Sequential scan of file):
    • 成本: 表页数 (NPages(R))。这是最简单的全表扫描。
  • 去重成本: 如果查询需要去重，还必须额外计算去重操作的成本。

左深计划的枚举 (Enumeration of Left-Deep Plans) ​

  • 左深计划的不同之处在于 (Left-deep plans differ in):
    • 连接关系的顺序。
    • 每个叶子操作符的访问方法 (access method)。
    • 每个连接操作符的具体连接方法 (join method)。
  • 枚举过程 (使用 N 个阶段 (N passes)):
    • 阶段 1 (Pass 1): 为每个单独的关系（表）找到最佳的“1 关系计划”(1-relation plan)。
    • 阶段 i (Pass i): 对于 i 从 2 到 N，找到将 (i-1) 个关系连接的结果（作为外部关系）与第 i 个关系连接的最佳方法。
    • 保留最佳计划: 对于每个关系子集，优化器只会保留：
      • 总成本最低的计划。
      • 对于每种感兴趣的排序 (interesting order)，成本最低的计划。

最优性原理 (The Principle of Optimality) ​

是什么 (What it is) ​

这是动态规划的基础，由 Bellman 在 1957 年提出。它指出：一个最优的整体计划是由其子计划的最佳决策组成的。

最优子结构 (Optimal substructure) ​

  • 是什么: 如果一个问题的最优解包含其子问题的最优解，那么这个问题就具有最优子结构。
  • 例子: 假设要连接 表A、表B、表C。如果 (连接A、B的最佳计划) 连接 C 是连接 A、B、C 的最佳左深计划，那么 连接A、B的最佳计划 本身也必须是连接 A、B 的最佳计划。你不能通过一个次优的 A、B 连接来得到最优的 A、B、C 连接。

优点 (Benefit) ​

  • 优化子计划 (Optimize subplans): 当优化一个子计划时，你不需要考虑它将来会被更高层的计划如何使用。你只需要找到这个子计划自身的最佳方案。
  • 重用结果 (Reuse results): 当优化更高层的计划时，你可以直接重用之前已经计算好的子计划的最佳结果，而不需要重新计算。这大大提高了效率。

System R的动态规划算法 (Dynamic Programming Algorithm for System R) ​

是什么 (What it is) ​

System R 优化器使用动态规划算法来“自底向上”地构建最佳查询计划。

怎么做 (How it works) ​

这个算法通过多个阶段（Pass）来逐步构建和优化计划：

  • 阶段 1 (Pass 1):

    • 目标: 找到所有单个关系（基本表）的最佳访问计划。
    • 过程: 检查每个表的所有可能访问方法（全表扫描、各种索引扫描），并计算它们的成本。同时，记录这些计划是否提供了任何“感兴趣的排序”（比如，如果通过 姓名 上的索引访问员工表，那么结果就是按姓名排序的）。
    • 记录: 将这些最佳的 1 关系计划及其成本记录在一个表格中。

  • 阶段 2 (Pass 2):

    • 目标: 找到所有两个关系连接的最佳计划。
    • 过程: 遍历所有在阶段 1 找到的 1 关系计划。对于每个 1 关系计划 P1，尝试将其作为外部关系，与另一个尚未连接的基本表 R2 进行连接。考虑所有可能的连接方法（比如块嵌套循环 (Block Nested Loop)、排序归并 (Sort-Merge)、索引嵌套循环 (Index Nested Loop) 等），并计算它们的成本。
    • 记录: 将这些最佳的 2 关系计划及其成本记录在表格中。

  • 阶段 i (Pass i):

    • 目标: 找到所有 i 个关系连接的最佳计划。
    • 过程: 遍历所有在阶段 i-1 找到的 (i-1) 关系计划。对于每个 (i-1) 关系计划 P_i-1，尝试将其作为外部关系，与一个尚未连接的基本表 R_i 进行连接。考虑所有可能的连接方法，并计算成本。
    • 记录: 将这些最佳的 i 关系计划及其成本记录在表格中。

  • 阶段 n (Pass n):

    • 目标: 找到整个查询（所有 N 个关系连接）的最佳计划。
    • 过程: 按照上述方式，最终在阶段 N 找到包含所有关系的最佳连接计划。

  • 基本动态规划表 (The Basic Dynamic Programming Table):

    • 这个表格的“键”是 FROM 子句中表的子集，表格中存储了对应这个子集的最佳计划及其估算成本。

一个细节：感兴趣的排序 (A Wrinkle: Interesting Orders) ​

是什么 (What it is) ​

“感兴趣的排序” (Interesting Order) 是一种特殊的物理属性 (physical property)。它指的是中间结果的排序顺序，这种顺序可能对查询的后续部分（“下游”操作）非常有用。

何时关心 (When to care) ​

当以下情况发生时，这种排序顺序就变得“感兴趣”：

  • ORDER BY 属性: 如果最终查询结果需要按照某个列进行排序（比如 ORDER BY 姓名），那么如果中间结果已经有序，就可以避免额外的排序操作。
  • GROUP BY 属性: 如果查询需要按照某个列进行分组聚合（比如 GROUP BY 部门），那么如果数据已经按照部门排序，分组操作会更高效。
  • 尚未添加的连接的连接属性: 如果后续的连接操作是排序归并连接 (Sort-Merge Join)，那么如果当前中间结果已经按照连接键排序，就可以直接进行合并，而不需要额外排序。

包含感兴趣排序的动态规划表 (The Dynamic Programming Table with Interesting Orders) ​

  • 为了利用“感兴趣的排序”，优化器会修改其动态规划表格。
  • 表格的“键”不再仅仅是表的子集，而是表的子集和感兴趣的排序列的组合。
  • 对于每个这样的组合，表格会存储对应的最佳计划及其成本。这意味着，对于同一个表的子集，优化器可能会存储多个“最佳”计划：一个可能是总成本最低但无序的，另一个可能是总成本略高但提供了特定排序的。

计划枚举（续） (Enumeration of Plans (Contd.)) ​

  • 动态规划的初步阶段: 优化器首先使用动态规划确定扫描和连接操作（即 SELECT-PROJECT-JOIN 部分）。
  • 避免笛卡尔积 (Avoid Cartesian Products): 在将一个 (i-1) 路子计划 (i-1-way subplan)（已经连接了 i-1 个表）与另一个表匹配时，优化器会尽量避免生成笛卡尔积。它只有在以下两种情况下才会考虑连接：
    1. 这两个表之间存在明确的连接条件。
    2. WHERE 子句中的所有谓词 (predicates) 已在 (i-1) 路子计划中“用尽” (used up)。
  • 后处理步骤 (Post-processing steps): ORDER BY、GROUP BY 和聚合 (aggregate) 操作通常作为查询计划的最后步骤进行处理。
    • 如果之前选择的“感兴趣的排序”计划 (interesting order plan) 已经提供了所需的排序，那么这些操作的成本就是“免费”的。
    • 否则，优化器会额外增加一个排序或哈希操作符 (hash operator) 来实现这些功能。
  • 指数级复杂度 (Exponential complexity): 尽管有各种剪枝策略 (pruning strategies)，System R 的动态规划算法在处理大量表连接时，其复杂度仍然是指数级的。

例子 (Example) ​

让我们再次看一个具体的查询，了解优化器如何逐步构建计划：

查询: SELECT S.sid, COUNT(*) AS number FROM Sailors S, Reserves R, Boats B WHERE S.sid = R.sid AND R.bid = B.bid AND B.color = “red” GROUP BY S.sid。 这个查询的目标是找出预订了红色船只的水手，并统计每个水手预订了多少次。

  • 阶段 1 (Pass 1): 为每个关系找到最佳计划（例如，水手表 (Sailors)、预订表 (Reserves) 的文件扫描 (File Scan)，预订表.船ID (Reserves.bid) 和 水手表.水手ID (Sailors.sid) 的 B+ 树索引作为感兴趣的排序，船只表 (Boats) 的 颜色 (color) 上的 B+ 树索引）。
  • 阶段 2 (Pass 2): 以外部关系使用阶段 1 的计划，内部关系使用未加入的表，生成连接计划。例如，文件扫描预订表 (File Scan Reserves) (outer) 与 船只表 (Boats) (inner)，预订表上 Btree 索引的船ID (Reserves Btree on bid) (outer) 与 水手表 (Sailors) (inner) 等。保留每个（关系对，顺序）的最便宜计划。
  • 阶段 3 及后续阶段 (Pass 3 and subsequent passes): 以外部关系使用阶段 2 的计划，内部关系使用未加入的表，生成后续连接的计划。
  • 最后: 添加 GROUP BY/AGGREGATE 的成本（如果结果未被前一个操作符排序，则需要对 水手ID (sid) 进行排序），然后选择最便宜的计划。

物理数据库设计 (Physical DB Design) ​

是什么 (What it is) ​

物理数据库设计是关于如何在磁盘上实际存储数据和索引，以最大化查询性能。查询优化器会尽力利用索引 (index)、聚簇 (clustering) 等物理设计特性。数据库管理员 (DBA) 的职责就是设置好这些物理设计，优秀的 DBA 对查询优化器的工作原理非常了解。

一个关键决策：索引 (One Key Decision: Indexes) ​

  • 哪些表需要索引？。
  • 哪些字段应该作为搜索键 (search key)？。
  • 是否需要多个索引？。
  • 是否需要聚簇索引 (clustered index)？。

索引选择 (Index Selection) ​

贪婪方法 (A greedy approach) ​

选择索引通常采用一种“贪婪”的方法：

  1. 依次考虑最重要的查询: 从对系统性能影响最大的那些查询开始。
  2. 评估当前最佳计划: 考虑在现有索引的情况下，这个查询的最佳执行计划是什么。
  3. 考虑添加索引: 看看是否可以通过添加一个新的索引来获得一个更好的执行计划。
  4. 创建索引: 如果添加新索引能显著提升性能，就创建它。

考虑对更新的影响！ (Consider impact on updates!) ​

  • 双刃剑: 索引可以显著加速查询，但它们会减慢数据更新（插入、删除、修改）的速度，因为每次更新数据时，相关的索引也需要同步更新。
  • 存储空间: 索引也需要额外的磁盘空间来存储。

索引选择中要考虑的问题 (Issues to Consider in Index Selection) ​

  • WHERE 子句中提到的属性是索引搜索键 (index search key) 的候选。
  • 范围条件 (Range conditions):
    • 例如 年龄 BETWEEN 20 AND 30。
    • 对聚簇 (clustering) 非常敏感。如果数据是按照范围条件涉及的列进行物理存储的（聚簇），那么读取这些范围的数据将非常高效。
  • 精确匹配条件 (Exact match conditions):
    • 例如 部门 = '销售'。
    • 不一定需要聚簇索引。但如果某个值有大量重复项（比如 性别 = '男'），那么即使是精确匹配，也可能像范围搜索一样需要读取大量数据页，此时聚簇索引会很有帮助。
  • 选择对多个查询都有益的索引。
  • 注意 (NOTE): 每个关系（表）只能有一个聚簇索引 (clustered index)！所以要明智选择。

例子 1 (Example 1) ​

  • 查询: SELECT E.ename, D.mgr FROM Emp E, Dept D WHERE E.dno=D.dno AND D.dname=‘Toy’。
  • 分析:
    • 如果在 部门表.部门名称 (D.dname) 上有 B+ 树索引 (B+ tree index)，可以高效地筛选出 部门名称='Toy' 的部门。
    • 一旦 部门表 (Dept D) 被大量过滤，部门表.部门ID (D.dno) 上的索引就不那么重要了，因为参与连接的部门记录已经很少。
    • 在 员工表.部门ID (E.dno) 上有 B+ 树索引可以帮助快速获取每个选定部门的匹配 员工 (Emp) 元组。
    • 如果 WHERE 子句中还包含 E.age=25，可以考虑在 员工表.年龄 (Emp.age) 上使用索引，然后将筛选后的员工与满足 dname 选择的 部门 (Dept) 元组连接。如果 Emp.age 索引已经存在，那么再添加 Emp.dno 索引的动机就小得多。

例子 2 (Example 2) ​

  • 查询: SELECT E.ename, D.mgr FROM Emp E, Dept D WHERE E.sal BETWEEN 10000 AND 20000 AND E.hobby=‘Stamps’ AND E.dno=D.dno。
  • 分析:
    • 所有选择都在 员工表 (Emp) 上，因此在任何索引嵌套循环连接 (Index Nested Loop Join) 中，员工表 (Emp) 都应该是外部关系 (outer relation)。
    • 建议在 部门表.部门ID (D.dno) 上建立 B+ 树索引。
    • 在 员工表 (Emp) 上建立什么索引？可以在 员工表.薪水 (E.sal) 或 员工表.爱好 (E.hobby) 上建立 B+ 树索引。通常只需要其中一个，哪个更好取决于条件的选择性 (selectivity)。通常，等值选择 (equality selection) 比范围选择 (range selection) 更具选择性。

聚簇的例子 (Examples of Clustering) ​

  • 查询: SELECT E.dno FROM Emp E WHERE E.age>40：B+ 树索引在 员工表.年龄 (E.age) 上可以用于获取符合条件的元组。如果很多元组的 员工表.年龄 (E.age) > 10，使用 E.age 索引并排序检索到的元组可能代价很高。聚簇的 员工表.部门ID (E.dno) 索引可能更好。
  • 查询: SELECT E.dno FROM Emp E WHERE E.hobby=Stamps：对于等值查询和重复值，员工表.爱好 (E.hobby) 上的聚簇会有帮助。

仅索引计划 (Index-Only Plans) ​

  • 是什么: 无需访问堆文件 (heap file) 即可回答查询。
  • 例子:
    • SELECT D.mgr FROM Dept D, Emp E WHERE D.dno=E.dno
      • 如果在 员工表 (Emp) 上有 <E.dno> 索引，并且该索引包含了查询所需的所有列，那么可能不需要访问实际数据表。
    • SELECT E.dno, COUNT(*) FROM Emp E GROUP BY E.dno
      • 如果在 员工表 (Emp) 上有 <E.dno> 索引，优化器可以直接扫描这个索引来计算每个 dno 的数量，而无需访问实际的员工数据。
    • SELECT E.dno, MIN(E.sal) FROM Emp E GROUP BY E.dno
      • 如果在 员工表 (Emp) 上有 <E.dno,E.sal> 复合索引，优化器可以直接扫描这个索引，找到每个 dno 对应的最小 sal 值。
    • SELECT AVG(E.sal) FROM Emp E WHERE E.age=25 AND E.sal BETWEEN 3000 AND 5000
      • 如果在 员工表 (Emp) 上有 <E.age,E.sal> 或 <E.sal, E.age> 复合索引，优化器可以直接在索引中进行筛选和聚合，而无需访问实际的员工数据。

索引调优“向导” (Index Tuning “Wizards”) ​

是什么 (What it is) ​

许多关系型数据库管理系统 (RDBMS) 现在都有自动索引顾问 (automatic index advisors)。

基本思想 (Basic idea) ​

  • 训练: 根据查询工作负载 (query workload)（可能基于日志记录 (log recording)）进行训练。
  • 成本估算: 使用优化器成本指标来估算不同索引集选择下工作负载的成本。
  • 启发式方法: 由于索引集选择数量巨大，需要使用启发式方法 (heuristics) 来加速。

调优查询和视图 (Tuning Queries and Views) ​

如果查询运行速度低于预期：

  • 检查索引是否需要重新聚簇，或统计信息是否过旧:
  • 有时数据库管理系统 (DBMS) 可能没有执行你设想的计划:
  • 优化器表现不佳的常见领域 (Common areas where optimizers are sub-par):
    • 涉及空值的选择（选择性估算不佳）。
    • 涉及算术或字符串表达式的选择。
    • 涉及 OR 条件的选择。
    • 复杂的子查询（缺乏扁平化 (flattening)）。
    • 成本估算失败（大型查询中的常见问题）。
    • 缺乏评估功能，如仅索引策略 (index-only strategy) 或某些连接方法。
  • 解决方案 (Solution):
    • 检查正在使用的计划 (Check the plan being used)（例如通过 SQL EXPLAIN 命令）。
    • 调整索引选择或重写查询/视图。
    • 一些系统（例如 DB2）会为你重写查询，这可能令人困惑但也很有帮助。
  • 强制优化器 (Forcing the optimizer): 许多数据库管理系统允许你覆盖或“提示” (hint) 优化器（例如 MS SQL Server 允许在查询的特定部分使用提示，或指定整个计划）。PostgreSQL 则提供其他控制，例如限制 FROM 子句中表的重新排序数量，或禁用某些物理操作符 (physical operators)。

更多查询调优指南 (More Guidelines for Query Tuning) ​

  • 尽量少用 DISTINCT (Minimize the use of DISTINCT): 如果允许重复或答案包含键，则不需要它。
  • 尽量少用 GROUP BY 和 HAVING (Minimize the use of GROUP BY and HAVING):
    • SELECT MIN (E.age) FROM Employee E GROUP BY E.dno HAVING E.dno=102 可以写成 SELECT MIN (E.age) FROM Employee E WHERE E.dno=102。
  • 编写数学表达式时考虑数据库管理系统 (DBMS) 如何使用索引 (Consider DBMS use of index when writing math): 例如，E.age = 2*D.age 可能只匹配 员工表.年龄 (E.age) 上的索引。
  • 避免使用中间关系 (Avoid using intermediate relations): 避免将中间结果物化 (materialize) 到临时表。例如，直接在连接结果上进行分组聚合，而不是先 SELECT INTO Temp 再对 Temp 进行聚合。
    • 如果 员工表 (Emp) 上有密集的 B+ 树索引 <dno, sal>，可以使用仅索引计划 (index-only plan) 来避免检索 员工 (Emp) 元组。

要点 (Points to Remember) ​

  • 要理解数据库设计（表、索引），必须理解查询优化。
  • 查询优化分为三部分 (Three parts to optimizing a query):
    1. 计划空间 (Plan space): 只考虑左深计划 (left-deep plans)，避免笛卡尔积 (Cartesian products)。将包含“感兴趣的排序” (interesting orders) 的计划与无序计划分开。
    2. 成本估算 (Cost Estimation): 估算每个计划节点 (plan node) 的输出基数 (output cardinality) 和成本。关键问题是统计信息 (statistics)、索引 (indexes) 和操作符实现 (operator implementation)。
    3. 搜索策略 (Search Strategy): 学习了“自底向上” (bottom-up) 的动态规划 (Dynamic Programming)。
  • 单关系查询 (Single-relation queries): 考虑所有访问路径 (access paths)，选择最便宜的。
    • 问题 (Issues): 匹配索引的选择，索引键是否包含所有所需字段，索引是否提供感兴趣的排序元组。
  • 多关系查询 (Multiple-relation queries):
    • 首先枚举所有单关系计划。
    • 尽早考虑选择/投影 (selection/projection)。
    • 使用最佳的 1 路计划 (1-way plan) 形成 2 路计划 (2-way plan)，并剪枝 (prune) 失败的计划。
    • 使用最佳的 (i-1) 路计划和最佳的 1 路计划形成 i 路计划 (i-way plan)。
    • 在每个级别，对于每个关系子集 (relation subset)，保留：每个感兴趣排序（包括无序）的最佳计划。