SQL调优教程 - 理解数据库执行计划（1）

引言

我每天的工作是为移动电信运营商开发后台应用程序。当客户通过 Web 或语音前端订购服务时，我们的应用程序必须提供非常快速的反馈。虽然我们要求在不到一秒钟的时间内做出响应，但我们必须在数十 GB 的数据库上执行复杂的 SQL 语句。

在这种环境中，任何一个低效的查询都可能产生灾难性的后果。糟糕的语句可能会使所有数据库处理器过载，导致它们无法为其他客户的订单提供服务。当然，这类问题通常在新优惠推出后不久就会出现……也就是在营销宣传最激烈的时候。您能想象在这种灾难发生时我们高层管理人员的心情吗？

不幸的是，次优的语句很难避免。应用程序通常使用比生产环境小得多的数据量进行测试，因此性能问题不太可能通过经验来检测。

这就是为什么每个数据库开发人员（以及所有处理数据库的应用程序开发人员）都应该理解数据库性能调优的基本概念。本文的目标是对这个问题进行理论介绍。读完本文，您应该能够回答这个问题：考虑到我所拥有的具体数据量，这个执行计划是否合理？

我必须警告您：这纯粹是理论。我知道每个人都讨厌理论，但这是没有捷径的。因此，请准备好面对大量的对数和概率……不害怕？那么，我们继续。

在本文中，我将尝试涵盖以下主题：

• 我们正在优化什么。
• 在表中查找记录。
• 使用嵌套循环连接表。

在第二部分（待写）中，需要勾勒出以下内容：

• 应用谓词。
• 使用哈希连接表。
• 排序
• 合并 (Merging)
• 使用合并连接表。

场景

我需要一个示例数据库来演示本文中的示例。让我们设定场景。

CUSTOMERS 表包含所有客户的一般信息。假设公司大约有百万客户。该表有一个主键 CUSTOMER_ID，由 PK_CUSTOMERS 索引。LAST_NAME 列由 IX_CUSTOMERS_LAST_NAME 索引。有 100,000 个唯一的姓氏。此表中的记录平均为 100 字节。

CUSTOMERS 表的 REGION_ID 列引用 REGIONS 表，该表包含该country的所有地理区域。大约有 50 个区域。该表有一个主键 REGION_ID，由 PK_REGIONS 索引。

我将使用符号 RECORDS(CUSTOMERS) 和 PAGES(CUSTOMERS) 分别表示 CUSTOMERS 表中的记录数和页数，其他表甚至索引也类似。Prob[CUSTOMERS.LAST_NAME = @LastName] 表示当我们没有关于他/她的其他信息时，客户被命名为 @LastName 的概率。

什么是执行计划

SQL 语句表达的是您想要“什么”，而不是告诉服务器“如何”去做。使用 SQL 语句，您可以要求服务器检索居住在布拉格地区的所有客户。当服务器收到语句时，它首先会解析它。如果语句没有语法错误，服务器就可以继续。它将决定计算结果的最佳方式。服务器会比较所有可能方法的成本，并选择其中一种。语句可以被物理执行的方式称为 **执行计划** 或 **查询计划**。

执行计划由 **基本操作** 组成。基本操作的示例如：完整读取表、使用索引、执行嵌套循环或哈希连接……我们将在本系列文章中详细介绍它们。所有基本操作都有一个输出：结果集。有些操作，如嵌套循环，有一个输入。其他操作，如哈希连接，有两个输入。每个输入应连接到另一个基本操作的输出。这就是为什么执行计划可以被勾勒成一棵树：信息从叶子流向根。本文后面有很多示例。

负责计算最佳执行计划的数据库服务器组件称为 **优化器**。优化器根据其对数据库内容的了解来做出决定。

如何检查执行计划

如果您使用的是 Microsoft SQL Server 2000，您可以使用 **查询分析器** 来查看优化器选择的执行计划。只需在查询窗口中键入 SQL 语句，然后按 Ctrl+L 键。查询将以图形方式显示。

或者，您可以获取 **文本表示**。如果您需要打印执行计划，这将特别有用。使用命令提示符，打开 isql 程序（键入 isql -? 以显示可能的命令行参数）。请按照以下说明操作：

1. 键入 set showplan_text on，然后按 Enter。
2. 键入 go，然后按 Enter。
3. 在命令提示符下粘贴您的 SQL 语句，然后按 Enter。
4. 键入 go，然后按 Enter。

程序将显示执行计划。

此执行计划的顶级操作是 hash join，其输入是 UNC_Dep_DepartmentName 的索引扫描和 PK_USERS 的聚集索引扫描。本系列文章的目的是学习如何理解此类执行计划。

我们正在优化什么？

应用程序开发人员通常需要最小化处理器使用，有时也最小化内存使用。然而，在开发数据库应用程序时，瓶颈在于其他地方。主要关注点是 **最小化磁盘访问**。

数据库引擎的主要磁盘分配单元称为 **页**。页的大小通常为几 KB。一个页通常包含几十到几百条记录。这一点很重要：有时您可能认为一个查询从 *记录* 访问的角度来看是最优的，但如果从 *页* 访问的角度来看，它就不是最优的。

在表中查找记录

• 全表扫描

  假设我们要在一个表中查找几条记录——例如，我们要查找姓氏为 @LastName 的客户。

  sql1 ::= SELECT * FROM CUSTOMERS WHERE LAST_NAME = @LastName

  第一个策略是从客户表中读取记录，并选择满足条件 LAST_NAME = @LastName 的记录。由于记录未排序，我们必须从头到尾读取表中的所有记录。此操作称为 **全表扫描**。它具有 **线性复杂度**，这意味着执行时间是表中行数的倍数。如果在一个 1000 条记录的表中查找一条记录需要 500 毫秒，那么在一个百万条记录的表中可能需要 8 分钟，在一个十亿条记录的表中可能需要 5 天……

  为了计算 sql1 的成本，我们建立一个包含基本操作的表。对于每个操作，我们指定单次出现的成本和出现次数。查询的总成本显然是操作单元成本与重复次数乘积的总和。

  操作 (Operation)	单元成本	数字
  CUSTOMERS 的全表扫描	PAGES(CUSTOMERS)	1

  让我们打个比方：全表扫描就像在一本小说中查找一个词的所有出现。

• 索引查找和索引范围扫描

  现在，如果这本书不是小说，而是一本带有详尽索引的技术手册呢？当然，搜索会快得多。但索引到底是什么？

  • 索引是 **键值和位置对** 的集合。键是我们查找的词。在书本的情况下，位置是页码。在数据库的情况下，它是物理行标识符。通过物理行标识符在表中查找记录具有 **常数复杂度**，也就是说，它不取决于表中的行数。
  • 键是排序的，因此我们不必读取所有键来找到正确的键。事实上，在索引中搜索具有 **对数复杂度**。如果在 1000 条记录的索引中查找一条记录需要 100 毫秒，那么在一百万条记录的索引中可能需要 200 毫秒，在十亿条记录的索引中可能需要 300 毫秒。（我这里指的是 B-Tree 索引。还有其他类型的索引，但它们与应用程序开发关系不大）。

  如果我们按姓名查找客户，我们可以执行以下物理操作：

  • 在 IX_CUSTOMERS_LAST_NAME 中查找第一个 LAST_NAME=@LastName 的条目。此操作称为 **索引查找**。
  • 读取索引，从该条目到 LAST_NAME=@LastName 仍然为 true 的最后一个条目。这将花费磁盘读取 PAGES(IX_CUSTOMERS_LAST_NAME)*Prob[LAST_NAME=@LastName] 页。此操作（始终与索引查找结合）称为 **索引范围扫描**。
  • 通过前面步骤找到的每个索引条目都为我们提供了 CUSTOMERS 表中记录的物理位置。我们仍然需要从表中获取该记录。这将涉及 RECORDS(CUSTOMERS)*Prob[LAST_NAME=@LastName] 次页获取。此操作称为 **表查找**。

  使用索引范围扫描的 sql1 的详细成本分析如下：

  操作 (Operation)	单元成本	数字
  IX_CUSTOMERS_LAST_NAME 的索引查找	Log( PAGES(IX_CUSTOMERS_LAST_NAME) )	1
  IX_CUSTOMERS_LAST_NAME 的索引范围扫描	PAGES(IX_CUSTOMERS_LAST_NAME)* Prob[LAST_NAME = @LastName]	1
  CUSTOMERS 的表查找	1	RECORDS(CUSTOMERS)* Prob[LAST_NAME = @LastName]

  坏消息是查询复杂度仍然是线性的，因此查询时间仍然是表大小的倍数。好消息是，我们真的不能做得更好：查询的复杂度 *不能* 小于其结果集的大小。

  在本篇文章的下一节中，我们将接受一个简化：**我们将假设索引查找的成本是单位成本**。这个估计并不算太粗糙，因为如果一个对数成本被 *加* 到一个线性成本上，它总是可以被忽略。如果它被 *乘以* 另一个成本，这个简化就不成立了。

• 索引选择性

  比较全表扫描方法和索引范围扫描方法的成本，让我们接触到数据库调优中的一个关键概念。上一节的结论是，如果从数量级上看，以下条件成立，则索引范围扫描方法会更快：

  [1] RECORDS(CUSTOMERS)* Prob[LAST_NAME = @LastName]< PAGES(CUSTOMERS)

  客户拥有给定姓名的概率 simply 是拥有该姓名的客户数量除以客户总数。令 KEYS(IX_CUSTOMERS_LAST_NAME) 表示索引 IX_CUSTOMERS_LAST_NAME 中唯一键的数量。@LastName 姓名的客户数量统计上是 RECORDS(CUSTOMERS)/KEYS(IX_CUSTOMERS_LAST_NAME)。

  因此，概率可以写成：

  [2] Prob[LAST_NAME = @LastName] = 
     (RECORDS(CUSTOMERS)/ KEYS(IX_CUSTOMERS_LAST_NAME))/RECORDS(CUSTOMERS) 
     = 1 / KEYS(IX_CUSTOMERS_LAST_NAME)

  将 [2] 代入 [1]：

  [3] RECORDS (CUSTOMERS)/ KEYS(IX_CUSTOMERS_LAST_NAME)< PAGES(CUSTOMERS)

  也就是说，**当每个唯一键的记录数小于表页数时，索引才足够**。

  前面表达式的左成员的倒数称为索引的 **选择性**：

  SELECTIVITY(IX_CUSTOMERS_LAST_NAME) = 
           KEYS(IX_CUSTOMERS_LAST_NAME) / RECORDS(CUSTOMERS)

  唯一索引的选择性始终为 1。索引的选择性越高（其选择性系数越大），效率就越高。推论：选择性差的索引可能适得其反。

使用嵌套循环连接表

当您需要从多个表中检索信息时，事情会变得更加困难。

假设我们想在客户姓名旁边显示区域的名称。

SELECT d.NAME, e.FIRST_NAME, e.LAST_NAME 
 FROM CUSTOMERS e, REGIONS d 
WHERE e.REGION_ID = d.REGION_ID

在可能的策略中，本文将介绍最自然的一种：选择一个表，从头到尾读取它，然后对于每一条记录，在第二个表中搜索相应的记录。第一个表称为 **外表** 或 **领先表**，第二个表称为 **内表**。当然，难题在于决定哪个表应该作为领先表。

因此，让我们首先尝试从区域表中开始。我们之前了解到 CUSTOMERS.REGION_ID 上的索引选择性太低，效率不高，因此我们的第一个候选执行计划是读取区域表，然后对于每个区域，对 CUSTOMERS 执行全表扫描。

操作 (Operation)	单元成本	数字
REGIONS 的全表扫描	PAGES(REGIONS)	1
CUSTOMERS 的全表扫描	PAGES(CUSTOMERS)	RECORDS(REGIONS)

领先成本显然是 PAGES(CUSTOMERS)*RECORDS(REGIONS)。如果我们给出数值，大约是 50*PAGES(CUSTOMERS)。

现在，如果我们反过来呢？由于区域表非常小，只有一页，所以拥有索引没有意义，因此我们再次选择两个嵌套的全表扫描。

操作 (Operation)	单元成本	数字
CUSTOMERS 的全表扫描	PAGES(CUSTOMERS)	1
REGIONS 的全表扫描	PAGES(REGIONS)	RECORDS(CUSTOMERS)

乍一看，领先成本是 PAGES(REGIONS)*RECORDS(CUSTOMERS)。由于区域表非常小，它只占一页，并且每页大约有 80 条客户记录（假设页大小为 8K），我们可以写成领先成本是 80*PAGES(CUSTOMERS)，这似乎比第一种方法差一点。然而，第二次连接顺序应该快得多。要看到这一点，我们必须考虑到一个我们至今为止都忽略的因素：内存缓存。

由于我们只关心最小化磁盘访问，我们可以认为 **从内存中读取页的成本为零**。

REGIONS 表及其主键都可以存储在缓存内存中。因此，成本矩阵可以重写如下：

操作 (Operation)	单元成本	数字
CUSTOMERS 的全表扫描	PAGES(CUSTOMERS)	1
REGIONS 的第一次全表扫描	PAGES(CUSTOMERS)	1
REGIONS 的下一次全表扫描	0	RECORDS(CUSTOMERS)

因此，最终领先成本项是 PAGES(CUSTOMERS)，这比第一种连接顺序好大约 200 倍。

摘要

让我们总结一下我试图在本篇文章中介绍的内容：

1. 我们优化的是磁盘的页访问，而不是记录访问。
2. 执行计划描述了数据如何在基本操作之间流动。要理解执行计划，有必要了解每个基本操作的复杂性及其输入流的记录数。
3. 全表扫描具有线性复杂度，索引查找具有对数复杂度。
4. 注意误区。索引扫描并不总是优于全表扫描。
5. 嵌套循环类似于 foreach 迭代。
6. 缓存可以产生巨大影响。
7. 执行顺序直接影响内存使用效率。

然而，我们还有很多工作要做。我还没有谈论最常见的连接类型：hash join。更糟糕的是：我还没有讨论谓词（WHERE 子句中非连接部分）如何完全误导优化器。如果您想做得比内置优化器更好，您仍然需要阅读第二篇文章。

待续。请继续关注我的 RSS feed。

参考文献

一个有用的信息来源，它在我撰写本文时给了我很多帮助，是 Oracle Performance Tuning Guide and Reference。那里解释的大多数概念也适用于 Microsoft SQL Server。Microsoft 用户还可以阅读在线帮助中的“查询调优”部分。

文档历史

1. 2005-03-14
   • 最初版本发布在 Gael Fraiteur 的博客。
2. 2005-03-31
   • 发布于 The Code Project。
3. 2005-04-07
   • 对查询分析器更友好；）。
4. 2005-04-18
   • 一些更正（由 Peter Molnar 和 Mikael Håkansson 提供）。