如果有人问你数据库的原理，叫他看这篇文章（转载）

摘要：如果你对了解一个数据库感兴趣，但是从未有时间或意愿来刻苦钻研这个内容广泛的课题，你应该喜欢这篇文章。优秀的排序算法有好几个，我侧重于最重要的一种合并排序。再者，合并排序有助于我们以后理解数据库常见的联接操作，即合并联接。

一提到关系型数据库，我禁不住想：有些东西被忽视了。关系型数据库无处不在，而且种类繁多，从小巧实用的 SQLite 到强大的 Teradata 。但很少有文章讲解数据库是如何工作的。你可以自己谷歌/百度一下『关系型数据库原理』，看看结果多么的稀少【译者注：百度为您找到相关结果约1,850,000个…】 ，而且找到的那些文章都很短。现在如果你查找最近时髦的技术（大数据、NoSQL或JavaScript），你能找到更多深入探讨它们如何工作的文章。

难道关系型数据库已经太古老太无趣，除了大学教材、研究文献和书籍以外，没人愿意讲了吗？

作为一个开发人员，我不喜欢用我不明白的东西。而且，数据库已经使用了40年之久，一定有理由的。多年以来，我花了成百上千个小时来真正领会这些我每天都在用的、古怪的黑盒子。关系型数据库非常有趣，因为它们是基于实用而且可复用的概念。如果你对了解一个数据库感兴趣，但是从未有时间或意愿来刻苦钻研这个内容广泛的课题，你应该喜欢这篇文章。

虽然本文标题很明确，但我的目的并不是讲如何使用数据库。因此，你应该已经掌握怎么写一个简单的 join query（联接查询）和CRUD操作（创建读取更新删除），否则你可能无法理解本文。这是唯一需要你了解的，其他的由我来讲解。

我会从一些计算机科学方面的知识谈起，比如时间复杂度。我知道有些人讨厌这个概念，但是没有它你就不能理解数据库内部的巧妙之处。由于这是个很大的话题，我将集中探讨我认为必要的内容：数据库处理SQL查询的方式。我仅仅介绍数据库背后的基本概念，以便在读完本文后你会对底层到底发生了什么有个很好的了解。

【译者注：关于时间复杂度。计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。如果不了解这个概念建议先看看维基或百度百科，对于理解文章下面的内容很有帮助】

由于本文是个长篇技术文章，涉及到很多算法和数据结构知识，你尽可以慢慢读。有些概念比较难懂，你可以跳过，不影响理解整体内容。

这篇文章大约分为3个部分：

底层和上层数据库组件概况
查询优化过程概况
事务和缓冲池管理概况
回到基础
很久很久以前（在一个遥远而又遥远的星系……)，开发者必须确切地知道他们的代码需要多少次运算。他们把算法和数据结构牢记于心，因为他们的计算机运行缓慢，无法承受对CPU和内存的浪费。

在这一部分，我将提醒大家一些这类的概念，因为它们对理解数据库至关重要。我还会介绍数据库索引的概念。

O(1) vs O(n^2)
现今很多开发者不关心时间复杂度……他们是对的。

但是当你应对大量的数据（我说的可不只是成千上万哈）或者你要争取毫秒级操作，那么理解这个概念就很关键了。而且你猜怎么着，数据库要同时处理这两种情景！我不会占用你太长时间，只要你能明白这一点就够了。这个概念在下文会帮助我们理解什么是基于成本的优化。

概念
时间复杂度用来检验某个算法处理一定量的数据要花多长时间。为了描述这个复杂度，计算机科学家使用数学上的『简明解释算法中的大O符号』。这个表示法用一个函数来描述算法处理给定的数据需要多少次运算。

比如，当我说『这个算法是适用 O(某函数())』，我的意思是对于某些数据，这个算法需要 某函数(数据量) 次运算来完成。

重要的不是数据量，而是当数据量增加时运算如何增加。时间复杂度不会给出确切的运算次数，但是给出的是一种理念。

图中可以看到不同类型的复杂度的演变过程，我用了对数尺来建这个图。具体点儿说，数据量以很快的速度从1条增长到10亿条。我们可得到如下结论：

绿：O(1)或者叫常数阶复杂度，保持为常数（要不人家就不会叫常数阶复杂度了）。
红：O(log(n))对数阶复杂度，即使在十亿级数据量时也很低。
粉：最糟糕的复杂度是 O(n^2)，平方阶复杂度，运算数快速膨胀。
黑和蓝：另外两种复杂度（的运算数也是）快速增长。
例子
数据量低时，O(1) 和 O(n^2)的区别可以忽略不计。比如，你有个算法要处理2000条元素。

O(1) 算法会消耗 1 次运算
O(log(n)) 算法会消耗 7 次运算
O(n) 算法会消耗 2000 次运算
O(n*log(n)) 算法会消耗 14,000 次运算
O(n^2) 算法会消耗 4,000,000 次运算
O(1) 和 O(n^2) 的区别似乎很大（4百万）,但你最多损失 2 毫秒，只是一眨眼的功夫。确实，当今处理器每秒可处理上亿次的运算。这就是为什么性能和优化在很多IT项目中不是问题。

我说过，面临海量数据的时候，了解这个概念依然很重要。如果这一次算法需要处理 1,000,000 条元素（这对数据库来说也不算大）。

O(1) 算法会消耗 1 次运算
O(log(n)) 算法会消耗 14 次运算
O(n) 算法会消耗 1,000,000 次运算
O(n*log(n)) 算法会消耗 14,000,000 次运算
O(n^2) 算法会消耗 1,000,000,000,000 次运算
我没有具体算过，但我要说，用O(n^2) 算法的话你有时间喝杯咖啡（甚至再续一杯！）。如果在数据量后面加个0，那你就可以去睡大觉了。

继续深入
为了让你能明白

搜索一个好的哈希表会得到 O(1) 复杂度
搜索一个均衡的树会得到 O(log(n)) 复杂度
搜索一个阵列会得到 O(n) 复杂度
最好的排序算法具有 O(n*log(n)) 复杂度
糟糕的排序算法具有 O(n^2) 复杂度
注：在接下来的部分，我们将会研究这些算法和数据结构。

有多种类型的时间复杂度

一般情况场景
最佳情况场景
最差情况场景
时间复杂度经常处于最差情况场景。

这里我只探讨时间复杂度，但复杂度还包括：

算法的内存消耗
算法的磁盘 I/O 消耗
当然还有比 n^2 更糟糕的复杂度，比如：

n^4：差劲！我将要提到的一些算法具备这种复杂度。
3^n：更差劲！本文中间部分研究的一些算法中有一个具备这种复杂度（而且在很多数据库中还真的使用了）。
阶乘 n：你永远得不到结果，即便在少量数据的情况下。
n^n：如果你发展到这种复杂度了，那你应该问问自己IT是不是你的菜。
注：我并没有给出『大O表示法』的真正定义，只是利用这个概念。可以看看维基百科上的这篇文章。

合并排序
当你要对一个集合排序时你怎么做？什么？调用 sort() 函数……好吧，算你对了……但是对于数据库，你需要理解这个 sort() 函数的工作原理。

优秀的排序算法有好几个，我侧重于最重要的一种：合并排序。你现在可能还不了解数据排序有什么用，但看完查询优化部分后你就会知道了。再者，合并排序有助于我们以后理解数据库常见的联接操作，即合并联接 。

合并
与很多有用的算法类似，合并排序基于这样一个技巧：将 2 个大小为 N/2 的已排序序列合并为一个 N 元素已排序序列仅需要 N 次操作。这个方法叫做合并。

我们用个简单的例子来看看这是什么意思：

通过此图你可以看到，在 2 个 4元素序列里你只需要迭代一次，就能构建最终的8元素已排序序列，因为两个4元素序列已经排好序了：

1) 在两个序列中，比较当前元素（当前=头一次出现的第一个）
2) 然后取出最小的元素放进8元素序列中
3) 找到（两个）序列的下一个元素，(比较后)取出最小的
重复1、2、3步骤，直到其中一个序列中的最后一个元素
然后取出另一个序列剩余的元素放入8元素序列中。
这个方法之所以有效，是因为两个4元素序列都已经排好序，你不需要再『回到』序列中查找比较。

【译者注：合并排序详细原理，其中一个动图（原图较长，我做了删减）清晰的演示了上述合并排序的过程，而原文的叙述似乎没有这么清晰，不动戳大。】

既然我们明白了这个技巧，下面就是我的合并排序伪代码。

    array mergeSort(array a)
       if(length(a)==1)
          return a[0];
       end if
     
       //recursive calls
       [left_array right_array] := split_into_2_equally_sized_arrays(a);
       array new_left_array := mergeSort(left_array);
       array new_right_array := mergeSort(right_array);
     
       //merging the 2 small ordered arrays into a big one
       array result := merge(new_left_array,new_right_array);
       return result;

合并排序是把问题拆分为小问题，通过解决小问题来解决最初的问题（注：这种算法叫分治法，即『分而治之、各个击破』）。如果你不懂，不用担心，我第一次接触时也不懂。如果能帮助你理解的话，我认为这个算法是个两步算法：

拆分阶段，将序列分为更小的序列
排序阶段，把小的序列合在一起（使用合并算法）来构成更大的序列
拆分阶段

在拆分阶段过程中，使用3个步骤将序列分为一元序列。步骤数量的值是 log(N) （因为 N=8, log(N)=3）。【译者注：底数为2，下文有说明】

我怎么知道这个的？

我是天才！一句话：数学。道理是每一步都把原序列的长度除以2，步骤数就是你能把原序列长度除以2的次数。这正好是对数的定义（在底数为2时）。

排序阶段

在排序阶段，你从一元序列开始。在每一个步骤中，你应用多次合并操作，成本一共是 N=8 次运算。

第一步，4 次合并，每次成本是 2 次运算。
第二步，2 次合并，每次成本是 4 次运算。
第三步，1 次合并，成本是 8 次运算。
因为有 log(N) 个步骤，整体成本是 N*log(N) 次运算。

【译者注：这个完整的动图演示了拆分和排序的全过程，不动戳大。】

合并排序的强大之处
为什么这个算法如此强大？

因为：

你可以更改算法，以便于节省内存空间，方法是不创建新的序列而是直接修改输入序列。
注：这种算法叫『原地算法』(in-place algorithm)

你可以更改算法，以便于同时使用磁盘空间和少量内存而避免巨量磁盘 I/O。方法是只向内存中加载当前处理的部分。在仅仅100MB的内存缓冲区内排序一个几个GB的表时，这是个很重要的技巧。
注：这种算法叫『外部排序』(external sorting)。

你可以更改算法，以便于在 多处理器/多线程/多服务器 上运行。
比如，分布式合并排序是Hadoop（那个著名的大数据框架）的关键组件之一。

这个算法可以点石成金（事实如此！）
这个排序算法在大多数（如果不是全部的话）数据库中使用，但是它并不是唯一算法。如果你想多了解一些，你可以看看 这篇论文，探讨的是数据库中常用排序算法的优势和劣势。

阵列，树和哈希表
既然我们已经了解了时间复杂度和排序背后的理念，我必须要向你介绍3种数据结构了。这个很重要，因为它们是现代数据库的支柱。我还会介绍数据库索引的概念。

阵列
二维阵列是最简单的数据结构。一个表可以看作是个阵列，比如：

这个二维阵列是带有行与列的表：

每个行代表一个主体
列用来描述主体的特征
每个列保存某一种类型对数据（整数、字符串、日期……）
虽然用这个方法保存和视觉化数据很棒，但是当你要查找特定的值它就很糟糕了。 举个例子，如果你要找到所有在 UK 工作的人，你必须查看每一行以判断该行是否属于 UK 。这会造成 N 次运算的成本（N 等于行数），还不赖嘛，但是有没有更快的方法呢？这时候树就可以登场了（或开始起作用了）。

树和数据库索引
二叉查找树是带有特殊属性的二叉树，每个节点的关键字必须：

比保存在左子树的任何键值都要大
比保存在右子树的任何键值都要小
【译者注：binary search tree，二叉查找树/二叉搜索树，或称 Binary Sort Tree 二叉排序树。见百度百科 】

概念

这个树有 N=15 个元素。比方说我要找208：

我从键值为 136 的根开始，因为 136<208，我去找节点136的右子树。
398>208，所以我去找节点398的左子树
250>208，所以我去找节点250的左子树
200<208，所以我去找节点200的右子树。但是 200 没有右子树，值不存在（因为如果存在，它会在 200 的右子树）
现在比方说我要找40

我从键值为136的根开始，因为 136>40，所以我去找节点136的左子树。
80>40，所以我去找节点 80 的左子树
40=40，节点存在。我抽取出节点内部行的ID（图中没有画）再去表中查找对应的 ROW ID。
知道 ROW ID我就知道了数据在表中对精确位置，就可以立即获取数据。
最后，两次查询的成本就是树内部的层数。如果你仔细阅读了合并排序的部分，你就应该明白一共有 log(N)层。所以这个查询的成本是 log(N)，不错啊！

回到我们的问题
上文说的很抽象，我们回来看看我们的问题。这次不用傻傻的数字了，想象一下前表中代表某人的国家的字符串。假设你有个树包含表中的列『country』：

如果你想知道谁在 UK 工作
你在树中查找代表 UK 的节点
在『UK 节点』你会找到 UK 员工那些行的位置
这次搜索只需 log(N) 次运算，而如果你直接使用阵列则需要 N 次运算。你刚刚想象的就是一个数据库索引。

B+树索引
查找一个特定值这个树挺好用，但是当你需要查找两个值之间的多个元素时，就会有大麻烦了。你的成本将是 O(N)，因为你必须查找树的每一个节点，以判断它是否处于那 2 个值之间（例如，对树使用中序遍历）。而且这个操作不是磁盘I/O有利的，因为你必须读取整个树。我们需要找到高效的范围查询方法。为了解决这个问题，现代数据库使用了一种修订版的树，叫做B+树。在一个B+树里：

只有最底层的节点（叶子节点）才保存信息（相关表的行位置）
其它节点只是在搜索中用来指引到正确节点的。
【译者注：参考 B+树 ， 二叉树遍历 维基百科】

你可以看到，节点更多了（多了两倍）。确实，你有了额外的节点，它们就是帮助你找到正确节点的『决策节点』（正确节点保存着相关表中行的位置）。但是搜索复杂度还是在 O(log(N))（只多了一层）。一个重要的不同点是，最底层的节点是跟后续节点相连接的。

用这个 B+树，假设你要找40到100间的值：

你只需要找 40（若40不存在则找40之后最贴近的值），就像你在上一个树中所做的那样。
然后用那些连接来收集40的后续节点，直到找到100。
比方说你找到了 M 个后续节点，树总共有 N 个节点。对指定节点的搜索成本是 log(N)，跟上一个树相同。但是当你找到这个节点，你得通过后续节点的连接得到 M 个后续节点，这需要 M 次运算。那么这次搜索只消耗了 M+log(N) 次运算，区别于上一个树所用的 N 次运算。此外，你不需要读取整个树（仅需要读 M+log(N) 个节点）,这意味着更少的磁盘访问。如果 M 很小（比如 200 行）并且 N 很大（1,000,000），那结果就是天壤之别了。

然而还有新的问题（又来了！）。如果你在数据库中增加或删除一行（从而在相关的 B+树索引里）：

你必须在B+树中的节点之间保持顺序，否则节点会变得一团糟，你无法从中找到想要的节点。
你必须尽可能降低B+树的层数，否则 O(log(N)) 复杂度会变成 O(N)。
换句话说，B+树需要自我整理和自我平衡。谢天谢地，我们有智能删除和插入。但是这样也带来了成本：在B+树中，插入和删除操作是 O(log(N)) 复杂度。所以有些人听到过使用太多索引不是个好主意这类说法。没错，你减慢了快速插入/更新/删除表中的一个行的操作，因为数据库需要以代价高昂的每索引 O(log(N)) 运算来更新表的索引。再者，增加索引意味着给事务管理器带来更多的工作负荷（在本文结尾我们会探讨这个管理器）。

想了解更多细节，你可以看看 Wikipedia 上这篇关于B+树的文章。如果你想要数据库中实现B+树的例子，看看MySQL核心开发人员写的这篇文章 和 这篇文章。两篇文章都致力于探讨 innoDB(MySQL引擎)如何处理索引。

哈希表
我们最后一个重要的数据结构是哈希表。当你想快速查找值时，哈希表是非常有用的。而且，理解哈希表会帮助我们接下来理解一个数据库常见的联接操作，叫做『哈希联接』。这个数据结构也被数据库用来保存一些内部的东西（比如锁表或者缓冲池，我们在下文会研究这两个概念）。

哈希表这种数据结构可以用关键字来快速找到一个元素。为了构建一个哈希表，你需要定义：

元素的关键字
关键字的哈希函数。关键字计算出来的哈希值给出了元素的位置（叫做哈希桶）。
关键字比较函数。一旦你找到正确的哈希桶，你必须用比较函数在桶内找到你要的元素。
一个简单的例子
我们来看一个形象化的例子：

这个哈希表有10个哈希桶。因为我懒，我只给出5个桶，但是我知道你很聪明，所以我让你想象其它的5个桶。我用的哈希函数是关键字对10取模，也就是我只保留元素关键字的最后一位，用来查找它的哈希桶：

如果元素最后一位是 0，则进入哈希桶0，
如果元素最后一位是 1，则进入哈希桶1，
如果元素最后一位是 2，则进入哈希桶2，
…我用的比较函数只是判断两个整数是否相等。
【译者注：取模运算】

比方说你要找元素 78：

哈希表计算 78 的哈希码，等于 8。
查找哈希桶 8，找到的第一个元素是 78。
返回元素 78。
查询仅耗费了 2 次运算（1次计算哈希值，另一次在哈希桶中查找元素）。
现在，比方说你要找元素 59：

哈希表计算 59 的哈希码，等于9。
查找哈希桶 9，第一个找到的元素是 99。因为 99 不等于 59， 那么 99 不是正确的元素。
用同样的逻辑，查找第二个元素(9)，第三个(79)，……，最后一个(29)。
元素不存在。
搜索耗费了 7 次运算。
一个好的哈希函数
你可以看到，根据你查找的值，成本并不相同。

如果我把哈希函数改为关键字对 1,000,000 取模（就是说取后6位数字），第二次搜索只消耗一次运算，因为哈希桶 00059 里面没有元素。真正的挑战是找到好的哈希函数，让哈希桶里包含非常少的元素。

在我的例子里，找到一个好的哈希函数很容易，但这是个简单的例子。当关键字是下列形式时，好的哈希函数就更难找了：

1 个字符串（比如一个人的姓）
2 个字符串（比如一个人的姓和名）
2 个字符串和一个日期（比如一个人的姓、名和出生年月日）
…
如果有了好的哈希函数，在哈希表里搜索的时间复杂度是 O(1)。

阵列 vs 哈希表
为什么不用阵列呢？

嗯，你问得好。

一个哈希表可以只装载一半到内存，剩下的哈希桶可以留在硬盘上。
用阵列的话，你需要一个连续内存空间。如果你加载一个大表，很难分配足够的连续内存空间。
用哈希表的话，你可以选择你要的关键字（比如，一个人的国家和姓氏）。
想要更详细的信息，你可以阅读我在Java HashMap 上的文章，是关于高效哈希表实现的。你不需要了解Java就能理解文章里的概念。

全局概览
我们已经了解了数据库内部的基本组件，现在我们需要回来看看数据库的全貌了。

数据库是一个易于访问和修改的信息集合。不过简单的一堆文件也能达到这个效果。事实上，像SQLite这样最简单的数据库也只是一堆文件而已，但SQLite是精心设计的一堆文件，因为它允许你：

使用事务来确保数据的安全和一致性
快速处理百万条以上的数据
数据库一般可以用如下图形来理解：

撰写这部分之前，我读过很多书/论文，它们都以自己的方式描述数据库。所以，我不会特别关注如何组织数据库或者如何命名各种进程，因为我选择了自己的方式来描述这些概念以适应本文。区别就是不同的组件，总体思路为：数据库是由多种互相交互的组件构成的。

核心组件：

进程管理器（process manager）：很多数据库具备一个需要妥善管理的进程/线程池。再者，为了实现纳秒级操作，一些现代数据库使用自己的线程而不是操作系统线程。
网络管理器（network manager）：网路I/O是个大问题，尤其是对于分布式数据库。所以一些数据库具备自己的网络管理器。
文件系统管理器（File system manager）：磁盘I/O是数据库的首要瓶颈。具备一个文件系统管理器来完美地处理OS文件系统甚至取代OS文件系统，是非常重要的。
内存管理器（memory manager）：为了避免磁盘I/O带来的性能损失，需要大量的内存。但是如果你要处理大容量内存你需要高效的内存管理器，尤其是你有很多查询同时使用内存的时候。
安全管理器（Security Manager）：用于对用户的验证和授权。
客户端管理器（Client manager）：用于管理客户端连接。
……
工具：

备份管理器（Backup manager）：用于保存和恢复数据。
复原管理器（Recovery manager）：用于崩溃后重启数据库到一个一致状态。
监控管理器（Monitor manager）：用于记录数据库活动信息和提供监控数据库的工具。
Administration管理器（Administration manager）：用于保存元数据（比如表的名称和结构），提供管理数据库、模式、表空间的工具。【译者注：好吧，我真的不知道Administration manager该翻译成什么，有知道的麻烦告知，不胜感激……】
……
查询管理器：

查询解析器（Query parser）：用于检查查询是否合法
查询重写器（Query rewriter）：用于预优化查询
查询优化器（Query optimizer）：用于优化查询
查询执行器（Query executor）：用于编译和执行查询
数据管理器：

事务管理器（Transaction manager）：用于处理事务
缓存管理器（Cache manager）：数据被使用之前置于内存，或者数据写入磁盘之前置于内存
数据访问管理器（Data access manager）：访问磁盘中的数据
在本文剩余部分，我会集中探讨数据库如何通过如下进程管理SQL查询的：

客户端管理器
查询管理器
数据管理器（含复原管理器）
客户端管理器

客户端管理器是处理客户端通信的。客户端可以是一个（网站）服务器或者一个最终用户或最终应用。客户端管理器通过一系列知名的API（JDBC, ODBC, OLE-DB …）提供不同的方式来访问数据库。

客户端管理器也提供专有的数据库访问API。

当你连接到数据库时：

管理器首先检查你的验证信息（用户名和密码），然后检查你是否有访问数据库的授权。这些权限由DBA分配。
然后，管理器检查是否有空闲进程（或线程）来处理你对查询。
管理器还会检查数据库是否负载很重。
管理器可能会等待一会儿来获取需要的资源。如果等待时间达到超时时间，它会关闭连接并给出一个可读的错误信息。
然后管理器会把你的查询送给查询管理器来处理。
因为查询处理进程不是『不全则无』的，一旦它从查询管理器得到数据，它会把部分结果保存到一个缓冲区并且开始给你发送。
如果遇到问题，管理器关闭连接，向你发送可读的解释信息，然后释放资源。
查询管理器

这部分是数据库的威力所在，在这部分里，一个写得糟糕的查询可以转换成一个快速执行的代码，代码执行的结果被送到客户端管理器。这个多步骤操作过程如下：

查询首先被解析并判断是否合法
然后被重写，去除了无用的操作并且加入预优化部分
接着被优化以便提升性能，并被转换为可执行代码和数据访问计划。
然后计划被编译
最后，被执行
这里我不会过多探讨最后两步，因为它们不太重要。

看完这部分后，如果你需要更深入的知识，我建议你阅读：

关于成本优化的初步研究论文(1979)：关系型数据库系统存取路径选择。这个篇文章只有12页，而且具备计算机一般水平就能理解。
非常好、非常深入的 DB2 9.X 如何优化查询的介绍
非常好的PostgreSQL如何优化查询的介绍。这是一篇最通俗易懂的文档，因为它讲的是『我们来看看在这种情况下，PostgreSQL给出了什么样的查询计划』，而不是『我们来看看PostgreSQL用的什么算法』。
官方SQLite优化文档。『易于』阅读，因为SQLite用的是简单规则。再者，这是唯一真正解释SQLite如何工作的官方文档。
非常好的SQL Server 2005 如何优化查询的介绍
Oracle 12c 优化白皮书
2篇查询优化的教程，第一篇 第二篇。教程来自《数据库系统概念》的作者，很好的读物，集中讨论磁盘I/O，但是要求具有很好的计算机科学水平。
另一个原理教程，这篇教程我觉得更易懂，不过它仅关注联接运算符（join operators）和磁盘I/O。
查询解析器
每一条SQL语句都要送到解析器来检查语法，如果你的查询有错，解析器将拒绝该查询。比如，如果你写成”SLECT …” 而不是 “SELECT …”，那就没有下文了。

但这还不算完，解析器还会检查关键字是否使用正确的顺序，比如 WHERE 写在 SELECT 之前会被拒绝。

然后，解析器要分析查询中的表和字段，使用数据库元数据来检查：

表是否存在
表的字段是否存在
对某类型字段的 运算 是否 可能（比如，你不能将整数和字符串进行比较，你不能对一个整数使用 substring() 函数）
接着，解析器检查在查询中你是否有权限来读取（或写入）表。再强调一次：这些权限由DBA分配。

在解析过程中，SQL 查询被转换为内部表示（通常是一个树）。

如果一切正常，内部表示被送到查询重写器。

查询重写器
在这一步，我们已经有了查询的内部表示，重写器的目标是：

预优化查询
避免不必要的运算
帮助优化器找到合理的最佳解决方案
重写器按照一系列已知的规则对查询执行检测。如果查询匹配一种模式的规则，查询就会按照这条规则来重写。下面是（可选）规则的非详尽的列表：

视图合并：如果你在查询中使用视图，视图就会转换为它的 SQL 代码。
子查询扁平化：子查询是很难优化的，因此重写器会尝试移除子查询
例如：

SELECT PERSON.*
FROM PERSON
WHERE PERSON.person_key IN
(SELECT MAILS.person_key
FROM MAILS
WHERE MAILS.mail LIKE "christophe%");

会转换为：

SELECT PERSON.*
FROM PERSON, MAILS
WHERE PERSON.person_key = MAILS.person_key
and MAILS.mail LIKE "christophe%";

去除不必要的运算符：比如，如果你用了 DISTINCT，而其实你有 UNIQUE 约束（这本身就防止了数据出现重复），那么 DISTINCT 关键字就被去掉了。
排除冗余的联接：如果相同的 JOIN 条件出现两次，比如隐藏在视图中的 JOIN 条件，或者由于传递性产生的无用 JOIN，都会被消除。
常数计算赋值：如果你的查询需要计算，那么在重写过程中计算会执行一次。比如 WHERE AGE > 10+2 会转换为 WHERE AGE > 12 ， TODATE(“日期字符串”) 会转换为 datetime 格式的日期值。
（高级）分区裁剪（Partition Pruning）：如果你用了分区表，重写器能够找到需要使用的分区。
（高级）物化视图重写（Materialized view rewrite）：如果你有个物化视图匹配查询谓词的一个子集，重写器将检查视图是否最新并修改查询，令查询使用物化视图而不是原始表。
（高级）自定义规则：如果你有自定义规则来修改查询（就像 Oracle policy），重写器就会执行这些规则。
（高级）OLAP转换：分析/加窗 函数，星形联接，ROLLUP 函数……都会发生转换（但我不确定这是由重写器还是优化器来完成，因为两个进程联系很紧，必须看是什么数据库）。
【译者注： 物化视图 。谓词，predicate，条件表达式的求值返回真或假的过程】

重写后的查询接着送到优化器，这时候好玩的就开始了。

统计
研究数据库如何优化查询之前我们需要谈谈统计，因为没有统计的数据库是愚蠢的。除非你明确指示，数据库是不会分析自己的数据的。没有分析会导致数据库做出（非常）糟糕的假设。

但是，数据库需要什么类型的信息呢？

我必须（简要地）谈谈数据库和操作系统如何保存数据。两者使用的最小单位叫做页或块（默认 4 或 8 KB）。这就是说如果你仅需要 1KB，也会占用一个页。要是页的大小为 8KB，你就浪费了 7KB。

回来继续讲统计！ 当你要求数据库收集统计信息，数据库会计算下列值：

表中行和页的数量
表中每个列中的：
唯一值
数据长度（最小，最大，平均）
数据范围（最小，最大，平均）
表的索引信息
这些统计信息会帮助优化器估计查询所需的磁盘 I/O、CPU、和内存使用

对每个列的统计非常重要。
比如，如果一个表 PERSON 需要联接 2 个列： LAST_NAME, FIRST_NAME。
根据统计信息，数据库知道FIRST_NAME只有 1,000 个不同的值，LAST_NAME 有 1,000,000 个不同的值。
因此，数据库就会按照 LAST_NAME, FIRST_NAME 联接。
因为 LAST_NAME 不大可能重复，多数情况下比较 LAST_NAME 的头 2 、 3 个字符就够了，这将大大减少比较的次数。

不过，这些只是基本的统计。你可以让数据库做一种高级统计，叫直方图。直方图是列值分布情况的统计信息。例如：

出现最频繁的值
分位数 【译者注：http://baike.baidu.com/view/1...】
…
这些额外的统计会帮助数据库找到更佳的查询计划，尤其是对于等式谓词（例如： WHERE AGE = 18 ）或范围谓词（例如： WHERE AGE > 10 and AGE < 40），因为数据库可以更好的了解这些谓词相关的数字类型数据行（注：这个概念的技术名称叫选择率）。

统计信息保存在数据库元数据内，例如（非分区）表的统计信息位置：

Oracle： USER / ALL / DBA_TABLES 和 USER / ALL / DBA_TAB_COLUMNS
DB2： SYSCAT.TABLES 和 SYSCAT.COLUMNS
统计信息必须及时更新。如果一个表有 1,000,000 行而数据库认为它只有 500 行，没有比这更糟糕的了。统计唯一的不利之处是需要时间来计算，这就是为什么数据库大多默认情况下不会自动计算统计信息。数据达到百万级时统计会变得困难，这时候，你可以选择仅做基本统计或者在一个数据库样本上执行统计。

举个例子，我参与的一个项目需要处理每表上亿条数据的库，我选择只统计10%，结果造成了巨大的时间消耗。本例证明这是个糟糕的决定，因为有时候 Oracle 10G 从特定表的特定列中选出的 10% 跟全部 100% 有很大不同（对于拥有一亿行数据的表，这种情况极少发生）。这次错误的统计导致了一个本应 30 秒完成的查询最后执行了 8 个小时，查找这个现象根源的过程简直是个噩梦。这个例子显示了统计的重要性。

注：当然了，每个数据库还有其特定的更高级的统计。如果你想了解更多信息，读读数据库的文档。话虽然这么说，我已经尽力理解统计是如何使用的了，而且我找到的最好的官方文档来自PostgreSQL。

查询优化器

所有的现代数据库都在用基于成本的优化（即CBO）来优化查询。道理是针对每个运算设置一个成本，通过应用成本最低廉的一系列运算，来找到最佳的降低查询成本的方法。

为了理解成本优化器的原理，我觉得最好用个例子来『感受』一下这个任务背后的复杂性。这里我将给出联接 2 个表的 3 个方法，我们很快就能看到即便一个简单的联接查询对于优化器来说都是个噩梦。之后，我们会了解真正的优化器是怎么做的。

对于这些联接操作，我会专注于它们的时间复杂度，但是，数据库优化器计算的是它们的 CPU 成本、磁盘 I/O 成本、和内存需求。时间复杂度和 CPU 成本的区别是，时间成本是个近似值（给我这样的懒家伙准备的）。而 CPU 成本，我这里包括了所有的运算，比如：加法、条件判断、乘法、迭代……还有呢：

每一个高级代码运算都要特定数量的低级 CPU 运算。
对于 Intel Core i7、Intel Pentium 4、AMD Opteron…等，（就 CPU 周期而言）CPU 的运算成本是不同的，也就是说它取决于 CPU 的架构。
使用时间复杂度就容易多了（至少对我来说），用它我也能了解到 CBO 的概念。由于磁盘 I/O 是个重要的概念，我偶尔也会提到它。请牢记，大多数时候瓶颈在于磁盘 I/O 而不是 CPU 使用。

索引
在研究 B+树的时候我们谈到了索引，要记住一点，索引都是已经排了序的。

仅供参考：还有其他类型的索引，比如位图索引，在 CPU、磁盘I/O、和内存方面与B+树索引的成本并不相同。

另外，很多现代数据库为了改善执行计划的成本，可以仅为当前查询动态地生成临时索引。

存取路径
在应用联接运算符（join operators）之前，你首先需要获得数据。以下就是获得数据的方法。
注：由于所有存取路径的真正问题是磁盘 I/O，我不会过多探讨时间复杂度。

【译者注：四种类型的Oracle索引扫描介绍 】

全扫描
如果你读过执行计划，一定看到过『全扫描』（或只是『扫描』）一词。简单的说全扫描就是数据库完整的读一个表或索引。就磁盘 I/O 而言，很明显全表扫描的成本比索引全扫描要高昂。

范围扫描
其他类型的扫描有索引范围扫描，比如当你使用谓词 ” WHERE AGE > 20 AND AGE < 40 ” 的时候它就会发生。

当然，你需要在 AGE 字段上有索引才能用到索引范围扫描。

在第一部分我们已经知道，范围查询的时间成本大约是 log(N)+M，这里 N 是索引的数据量，M 是范围内估测的行数。多亏有了统计我们才能知道 N 和 M 的值（注： M 是谓词 “ AGE > 20 AND AGE < 40 ” 的选择率）。另外范围扫描时，你不需要读取整个索引，因此在磁盘 I/O 方面没有全扫描那么昂贵。

唯一扫描
如果你只需要从索引中取一个值你可以用唯一扫描。

根据 ROW ID 存取
多数情况下，如果数据库使用索引，它就必须查找与索引相关的行，这样就会用到根据 ROW ID 存取的方式。

例如，假如你运行：

SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28
如果 person 表的 age 列有索引，优化器会使用索引找到所有年龄为 28 的人，然后它会去表中读取相关的行，这是因为索引中只有 age 的信息而你要的是姓和名。

但是，假如你换个做法：

SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON
WHERE PERSON.AGE = TYPE_PERSON.AGE
PERSON 表的索引会用来联接 TYPE_PERSON 表，但是 PERSON 表不会根据行ID 存取，因为你并没有要求这个表内的信息。

虽然这个方法在少量存取时表现很好，这个运算的真正问题其实是磁盘 I/O。假如需要大量的根据行ID存取，数据库也许会选择全扫描。

其它路径
我没有列举所有的存取路径，如果你感兴趣可以读一读 Oracle文档。其它数据库里也许叫法不同但背后的概念是一样的。

联接运算符
那么，我们知道如何获取数据了，那现在就把它们联接起来！

我要展现的是3个个常用联接运算符：合并联接（Merge join），哈希联接（Hash Join）和嵌套循环联接（Nested Loop Join）。但是在此之前，我需要引入新词汇了：内关系和外关系（ inner relation and outer relation） 【译者注： “内关系和外关系” 这个说法来源不明，跟查询的“内联接（INNER JOIN） 、外联接（OUTER JOIN） ” 不是一个概念 。只查到百度百科词条：关系数据库 里提到“每个表格（有时被称为一个关系）……” 。 其他参考链接 “Merge Join” “Hash Join” “Nested Loop Join” 】 。 一个关系可以是：

一个表
一个索引
上一个运算的中间结果（比如上一个联接运算的结果）
当你联接两个关系时，联接算法对两个关系的处理是不同的。在本文剩余部分，我将假定：

外关系是左侧数据集
内关系是右侧数据集
比如， A JOIN B 是 A 和 B 的联接，这里 A 是外关系，B 是内关系。

多数情况下， A JOIN B 的成本跟 B JOIN A 的成本是不同的。

在这一部分，我还将假定外关系有 N 个元素，内关系有 M 个元素。要记住，真实的优化器通过统计知道 N 和 M 的值。

注：N 和 M 是关系的基数。【译者注： 基数 】

嵌套循环联接
嵌套循环联接是最简单的。

道理如下：

针对外关系的每一行
查看内关系里的所有行来寻找匹配的行
下面是伪代码：

nested_loop_join(array outer, array inner)
for each row a in outer

for each row b in inner
  if (match_join_condition(a,b))
    write_result_in_output(a,b)
  end if
end for

end for
由于这是个双迭代，时间复杂度是 O(N*M)。

在磁盘 I/O 方面， 针对 N 行外关系的每一行，内部循环需要从内关系读取 M 行。这个算法需要从磁盘读取 N+ N*M 行。但是，如果内关系足够小，你可以把它读入内存，那么就只剩下 M + N 次读取。这样修改之后，内关系必须是最小的，因为它有更大机会装入内存。

在CPU成本方面没有什么区别，但是在磁盘 I/O 方面，最好最好的，是每个关系只读取一次。

当然，内关系可以由索引代替，对磁盘 I/O 更有利。

由于这个算法非常简单，下面这个版本在内关系太大无法装入内存时，对磁盘 I/O 更加有利。道理如下：

为了避免逐行读取两个关系，
你可以成簇读取，把（两个关系里读到的）两簇数据行保存在内存里，
比较两簇数据，保留匹配的，
然后从磁盘加载新的数据簇来继续比较
直到加载了所有数据。
可能的算法如下：

// improved version to reduce the disk I/O.
nested_loop_join_v2(file outer, file inner)
for each bunch ba in outer
// ba is now in memory

for each bunch bb in inner
    // bb is now in memory
    for each row a in ba
      for each row b in bb
        if (match_join_condition(a,b))
          write_result_in_output(a,b)
        end if
      end for
   end for
end for

end for
使用这个版本，时间复杂度没有变化，但是磁盘访问降低了：

用前一个版本，算法需要 N + N*M 次访问（每次访问读取一行）。
用新版本，磁盘访问变为 外关系的数据簇数量 + 外关系的数据簇数量 * 内关系的数据簇数量。
增加数据簇的尺寸，可以降低磁盘访问。
哈希联接
哈希联接更复杂，不过在很多场合比嵌套循环联接成本低。

哈希联接的道理是：

1) 读取内关系的所有元素
2) 在内存里建一个哈希表
3) 逐条读取外关系的所有元素
4) （用哈希表的哈希函数）计算每个元素的哈希值，来查找内关系里相关的哈希桶内
5) 是否与外关系的元素匹配。
在时间复杂度方面我需要做些假设来简化问题：

内关系被划分成 X 个哈希桶
哈希函数几乎均匀地分布每个关系内数据的哈希值，就是说哈希桶大小一致。
外关系的元素与哈希桶内的所有元素的匹配，成本是哈希桶内元素的数量。
时间复杂度是 (M/X) N + 创建哈希表的成本(M) + 哈希函数的成本 N 。
如果哈希函数创建了足够小规模的哈希桶，那么复杂度就是 O(M+N)。

还有个哈希联接的版本，对内存有利但是对磁盘 I/O 不够有利。 这回是这样的：

1) 计算内关系和外关系双方的哈希表
2) 保存哈希表到磁盘
3) 然后逐个哈希桶比较（其中一个读入内存，另一个逐行读取）。
合并联接
合并联接是唯一产生排序的联接算法。

注：这个简化的合并联接不区分内表或外表；两个表扮演同样的角色。但是真实的实现方式是不同的，比如当处理重复值时。

1.（可选）排序联接运算：两个输入源都按照联接关键字排序。

2.合并联接运算：排序后的输入源合并到一起。

排序
我们已经谈到过合并排序，在这里合并排序是个很好的算法（但是并非最好的，如果内存足够用的话，还是哈希联接更好）。

然而有时数据集已经排序了，比如：

如果表内部就是有序的，比如联接条件里一个索引组织表 【译者注： index-organized table 】
如果关系是联接条件里的一个索引
如果联接应用在一个查询中已经排序的中间结果
合并联接

这部分与我们研究过的合并排序中的合并运算非常相似。不过这一次呢，我们不是从两个关系里挑选所有元素，而是只挑选相同的元素。道理如下：

1) 在两个关系中，比较当前元素（当前=头一次出现的第一个）
2) 如果相同，就把两个元素都放入结果，再比较两个关系里的下一个元素
3) 如果不同，就去带有最小元素的关系里找下一个元素（因为下一个元素可能会匹配）
4) 重复 1、2、3步骤直到其中一个关系的最后一个元素。
因为两个关系都是已排序的，你不需要『回头去找』，所以这个方法是有效的。

该算法是个简化版，因为它没有处理两个序列中相同数据出现多次的情况（即多重匹配）。真实版本『仅仅』针对本例就更加复杂，所以我才选择简化版。

如果两个关系都已经排序，时间复杂度是 O(N+M)

如果两个关系需要排序，时间复杂度是对两个关系排序的成本：O(NLog(N) + MLog(M))

对于计算机极客，我给出下面这个可能的算法来处理多重匹配（注：对于这个算法我不保证100%正确）：

C
mergeJoin(relation a, relation b)
relation output
integer a_key:=0;
integer b_key:=0;

while (a[a_key]!=null and b[b_key]!=null)

 if (a[a_key] < b[b_key])
  a_key++;
 else if (a[a_key] > b[b_key])
  b_key++;
 else //Join predicate satisfied
  write_result_in_output(a[a_key],b[b_key])
  //We need to be careful when we increase the pointers
  if (a[a_key+1] != b[b_key])
    b_key++;
  end if
  if (b[b_key+1] != a[a_key])
    a_key++;
  end if
  if (b[b_key+1] == a[a_key] && b[b_key] == a[a_key+1])
    b_key++;
    a_key++;
  end if
end if

end while
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
mergeJoin(relation a, relation b)
relation output
integer a_key:=0;
integer b_key:=0;

while (a[a_key]!=null and b[b_key]!=null)

 if (a[a_key] < b[b_key])
  a_key++;
 else if (a[a_key] > b[b_key])
  b_key++;
 else //Join predicate satisfied
  write_result_in_output(a[a_key],b[b_key])
  //We need to be careful when we increase the pointers
  if (a[a_key+1] != b[b_key])
    b_key++;
  end if
  if (b[b_key+1] != a[a_key])
    a_key++;
  end if
  if (b[b_key+1] == a[a_key] && b[b_key] == a[a_key+1])
    b_key++;
    a_key++;
  end if
end if

end while
哪个算法最好？
如果有最好的，就没必要弄那么多种类型了。这个问题很难，因为很多因素都要考虑，比如：

空闲内存：没有足够的内存的话就跟强大的哈希联接拜拜吧（至少是完全内存中哈希联接）。
两个数据集的大小。比如，如果一个大表联接一个很小的表，那么嵌套循环联接就比哈希联接快，因为后者有创建哈希的高昂成本；如果两个表都非常大，那么嵌套循环联接CPU成本就很高昂。
是否有索引：有两个 B+树索引的话，聪明的选择似乎是合并联接。
结果是否需要排序：即使你用到的是未排序的数据集，你也可能想用成本较高的合并联接（带排序的），因为最终得到排序的结果后，你可以把它和另一个合并联接串起来（或者也许因为查询用 ORDER BY/GROUP BY/DISTINCT 等操作符隐式或显式地要求一个排序结果）。
关系是否已经排序：这时候合并联接是最好的候选项。
联接的类型：是等值联接（比如 tableA.col1 = tableB.col2 ）？ 还是内联接？外联接？笛卡尔乘积？或者自联接？有些联接在特定环境下是无法工作的。
数据的分布：如果联接条件的数据是倾斜的（比如根据姓氏来联接人，但是很多人同姓），用哈希联接将是个灾难，原因是哈希函数将产生分布极不均匀的哈希桶。
如果你希望联接操作使用多线程或多进程。
想要更详细的信息，可以阅读DB2, ORACLE 或 SQL Server)的文档。

简化的例子
我们已经研究了 3 种类型的联接操作。

现在，比如说我们要联接 5 个表，来获得一个人的全部信息。一个人可以有：

多个手机号（MOBILES）
多个邮箱（MAILS）
多个地址（ADRESSES）
多个银行账号（BANK_ACCOUNTS）
换句话说，我们需要用下面的查询快速得到答案：

MySQL
SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS
WHERE
PERSON.PERSON_ID = MOBILES.PERSON_ID
AND PERSON.PERSON_ID = MAILS.PERSON_ID
AND PERSON.PERSON_ID = ADRESSES.PERSON_ID
AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID
1
2
3
4
5
6
SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS
WHERE
PERSON.PERSON_ID = MOBILES.PERSON_ID
AND PERSON.PERSON_ID = MAILS.PERSON_ID
AND PERSON.PERSON_ID = ADRESSES.PERSON_ID
AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID
作为一个查询优化器，我必须找到处理数据最好的方法。但有 2 个问题：

每个联接使用那种类型？
我有 3 种可选（哈希、合并、嵌套），同时可能用到 0, 1 或 2 个索引（不必说还有多种类型的索引）。
按什么顺序执行联接？
比如，下图显示了针对 4 个表仅仅 3 次联接，可能采用的执行计划：

那么下面就是我可能采取的方法：

1) 采取粗暴的方式
用数据库统计，计算每种可能的执行计划的成本，保留最佳方案。但是，会有很多可能性。对于一个给定顺序的联接操作，每个联接有三种可能性：哈希、合并、嵌套，那么总共就有 3^4 种可能性。确定联接的顺序是个二叉树的排列问题，会有 (24)!/(4+1)! 种可能的顺序。对本例这个相当简化了的问题，我最后会得到 3^4(2*4)!/(4+1)! 种可能。
抛开专业术语，那相当于 27,216 种可能性。如果给合并联接加上使用 0,1 或 2 个 B+树索引，可能性就变成了 210,000种。我是不是告诉过你这个查询其实非常简单吗？
2) 我大叫一声辞了这份工作
很有诱惑力，但是这样一来，你不会的到查询结果，而我需要钱来付账单。
3) 我只尝试几种执行计划，挑一个成本最低的。
由于不是超人，我不能算出所有计划的成本。相反，我可以武断地从全部可能的计划中选择一个子集，计算它们的成本，把最佳的计划给你。
4) 我用聪明的规则来降低可能性的数量
有两种规则：
我可以用『逻辑』规则，它能去除无用的可能性，但是无法过滤大量的可能性。比如： 『嵌套联接的内关系必须是最小的数据集』。
我接受现实，不去找最佳方案，用更激进的规则来大大降低可能性的数量。比如：『如果一个关系很小，使用嵌套循环联接，绝不使用合并或哈希联接。』
在这个简单的例子中，我最后得到很多可能性。但现实世界的查询还会有其他关系运算符，像 OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT … 这意味着更多的可能性。

那么，数据库是如何处理的呢？

动态规划，贪婪算法和启发式算法

关系型数据库会尝试我刚刚提到的多种方法，优化器真正的工作是在有限时间里找到一个好的解决方案。

多数时候，优化器找到的不是最佳的方案，而是一个『不错』的

对于小规模的查询，采取粗暴的方式是有可能的。但是为了让中等规模的查询也能采取粗暴的方式，我们有办法避免不必要的计算，这就是动态规划。

动态规划
这几个字背后的理念是，很多执行计划是非常相似的。看看下图这几种计划：

它们都有相同的子树（A JOIN B），所以，不必在每个计划中计算这个子树的成本，计算一次，保存结果，当再遇到这个子树时重用。用更正规的说法，我们面对的是个重叠问题。为了避免对部分结果的重复计算，我们使用记忆法。

应用这一技术，我们不再有 (2*N)!/(N+1)! 的复杂度，而是“只有” 3^N。在之前 4 个JOIN 的例子里，这意味着将 336 次排序降为 81 次。如果是大一些的查询，比如 8 个 JOIN （其实也不是很大啦），就是将 57,657,600 次降为 6551 次。【译者注：这一小段漏掉了，感谢 nsos指出来。另外感谢 Clark Li 指出Dynamic Programing 应该翻译为动态规划。 】

对于计算机极客，下面是我在先前给你的教程里找到的一个算法。我不提供解释，所以仅在你已经了解动态规划或者精通算法的情况下阅读（我提醒过你哦）：

C
procedure findbestplan(S)
if (bestplan[S].cost infinite)
return bestplan[S]
// else bestplan[S] has not been computed earlier, compute it now
if (S contains only 1 relation)

     set bestplan[S].plan and bestplan[S].cost based on the best way
     of accessing S  /* Using selections on S and indices on S */
 else for each non-empty subset S1 of S such that S1 != S

P1= findbestplan(S1)
P2= findbestplan(S - S1)
A = best algorithm for joining results of P1 and P2
cost = P1.cost + P2.cost + cost of A
if cost < bestplan[S].cost

   bestplan[S].cost = cost
  bestplan[S].plan = 『execute P1.plan; execute P2.plan;
             join results of P1 and P2 using A』

return bestplan[S]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
procedure findbestplan(S)
if (bestplan[S].cost infinite)
return bestplan[S]
// else bestplan[S] has not been computed earlier, compute it now
if (S contains only 1 relation)

     set bestplan[S].plan and bestplan[S].cost based on the best way
     of accessing S  /* Using selections on S and indices on S */
 else for each non-empty subset S1 of S such that S1 != S

P1= findbestplan(S1)
P2= findbestplan(S - S1)
A = best algorithm for joining results of P1 and P2
cost = P1.cost + P2.cost + cost of A
if cost < bestplan[S].cost

   bestplan[S].cost = cost
  bestplan[S].plan = 『execute P1.plan; execute P2.plan;
             join results of P1 and P2 using A』

return bestplan[S]
针对大规模查询，你也可以用动态规划方法，但是要附加额外的规则（或者称为启发式算法）来减少可能性。

如果我们仅分析一个特定类型的计划（例如左深树 left-deep tree，参考)，我们得到 n*2^n 而不是 3^n。

如果我们加上逻辑规则来避免一些模式的计划（像『如果一个表有针对指定谓词的索引，就不要对表尝试合并联接，要对索引』），就会在不给最佳方案造成过多伤害的前提下，减少可能性的数量。【译者注：原文应该是有两处笔误： as=has, to=too】
如果我们在流程里增加规则（像『联接运算先于其他所有的关系运算』），也能减少大量的可能性。
……
贪婪算法
但是，优化器面对一个非常大的查询，或者为了尽快找到答案（然而查询速度就快不起来了），会应用另一种算法，叫贪婪算法。

原理是按照一个规则（或启发）以渐进的方式制定查询计划。在这个规则下，贪婪算法逐步寻找最佳算法，先处理一条JOIN，接着每一步按照同样规则加一条新的JOIN。

我们来看个简单的例子。比如一个针对5张表（A,B,C,D,E）4次JOIN 的查询，为了简化我们把嵌套JOIN作为可能的联接方式，按照『使用最低成本的联接』规则。

直接从 5 个表里选一个开始（比如 A）
计算每一个与 A 的联接（A 作为内关系或外关系）
发现 “A JOIN B” 成本最低
计算每一个与 “A JOIN B” 的结果联接的成本（“A JOIN B” 作为内关系或外关系）
发现 “(A JOIN B) JOIN C” 成本最低
计算每一个与 “(A JOIN B) JOIN C” 的结果联接的成本 ……
最后确定执行计划 “( ( (A JOIN B) JOIN C) JOIN D ) JOIN E )”
因为我们是武断地从表 A 开始，我们可以把同样的算法用在 B，然后 C，然后 D, 然后 E。最后保留成本最低的执行计划。

顺便说一句，这个算法有个名字，叫『最近邻居算法』。

抛开细节不谈，只需一个良好的模型和一个 Nlog(N) 复杂度的排序，问题就轻松解决了。这个算法的复杂度是 O(Nlog(N)) ，对比一下完全动态规划的 O(3^N)。如果你有个20个联接的大型查询，这意味着 26 vs 3,486,784,401 ，天壤之别！

这个算法的问题是，我们做的假设是：找到 2 个表的最佳联接方法，保留这个联接结果，再联接下一个表，就能得到最低的成本。但是：

即使在 A, B, C 之间，A JOIN B 可得最低成本
(A JOIN C) JOIN B 也许比 (A JOIN B) JOIN C 更好。
为了改善这一状况，你可以多次使用基于不同规则的贪婪算法，并保留最佳的执行计划。

其他算法
[ 如果你已经受够了算法话题，就直接跳到下一部分。这部分对文章余下的内容不重要。] 【译者注：我也很想把这段跳过去 -_- 】

很多计算机科学研究者热衷于寻找最佳的执行计划，他们经常为特定问题或模式探寻更好的解决方案，比如：

如果查询是星型联接（一种多联接查询），某些数据库使用一种特定的算法。
如果查询是并行的，某些数据库使用一种特定的算法。 ……
其他算法也在研究之中，就是为了替换在大型查询中的动态规划算法。贪婪算法属于一个叫做启发式算法的大家族，它根据一条规则（或启发），保存上一步找到的方法，『附加』到当前步骤来进一步搜寻解决方法。有些算法根据特定规则，一步步的应用规则但不总是保留上一步找到的最佳方法。它们统称启发式算法。

比如，基因算法就是一种：

一个方法代表一种可能的完整查询计划
每一步保留了 P 个方法（即计划），而不是一个。
0) P 个计划随机创建
1) 成本最低的计划才会保留
2) 这些最佳计划混合在一起产生 P 个新的计划
3) 一些新的计划被随机改写
4) 1，2，3步重复 T 次
5) 然后在最后一次循环，从 P 个计划里得到最佳计划。
循环次数越多，计划就越好。

这是魔术？不，这是自然法则：适者生存！

PostgreSQL 实现了基因算法，但我并没有发现它是不是默认使用这种算法的。

数据库中还使用了其它启发式算法，像『模拟退火算法（Simulated Annealing）』、『交互式改良算法（Iterative Improvement）』、『双阶段优化算法（Two-Phase Optimization）』…..不过，我不知道这些算法当前是否在企业级数据库应用了，还是仅仅用在研究型数据库。

如果想进一步了解，这篇研究文章介绍两个更多可能的算法《数据库查询优化中联接排序问题的算法综述》，你可以去阅读一下。

真实的优化器
[ 这段不重要，可以跳过 ]

然而，所有上述罗里罗嗦的都非常理论化，我是个开发者而不是研究者，我喜欢具体的例子。

我们来看看 SQLite 优化器 是怎么工作的。这是个轻量化数据库，它使用一种简单优化器，基于带有附加规则的贪婪算法，来限制可能性的数量。

SQLite 在有 CROSS JOIN 操作符时从不给表重新排序
使用嵌套联接
外联接始终按顺序评估
……
3.8.0之前的版本使用『最近邻居』贪婪算法来搜寻最佳查询计划
等等……我们见过这个算法！真是巧哈！
从3.8.0版本（发布于2015年）开始，SQLite使用『N最近邻居』贪婪算法来搜寻最佳查询计划
我们再看看另一个优化器是怎么工作的。IBM DB2 跟所有企业级数据库都类似，我讨论它是因为在切换到大数据之前，它是我最后真正使用的数据库。

看过官方文档后，我们了解到 DB2 优化器可以让你使用 7 种级别的优化：

对联接使用贪婪算法

0 – 最小优化，使用索引扫描和嵌套循环联接，避免一些查询重写
1 – 低级优化
2 – 完全优化

对联接使用动态规划算法

3 – 中等优化和粗略的近似法
5 – 完全优化，使用带有启发式的所有技术
7 – 完全优化，类似级别5，但不用启发式
9 – 最大优化，完全不顾开销，考虑所有可能的联接顺序，包括笛卡尔乘积

可以看到 DB2 使用贪婪算法和动态规划算法。当然，他们不会把自己的启发算法分享出来的，因为查询优化器是数据库的看家本领。

DB2 的默认级别是 5，优化器使用下列特性： 【译者注：以下出现的一些概念我没有做考证，因为[ 这段不重要，可以跳过 ]】

使用所有可用的统计，包括线段树（frequent-value）和分位数统计（quantile statistics）。
使用所有查询重写规则（含物化查询表路由，materialized query table routing），除了在极少情况下适用的计算密集型规则。
使用动态规划模拟联接

有限使用组合内关系（composite inner relation）
对于涉及查找表的星型模式，有限使用笛卡尔乘积

考虑宽泛的访问方式，含列表预取（list prefetch，注：我们将讨论什么是列表预取），index ANDing（注：一种对索引的特殊操作），和物化查询表路由。
默认的，DB2 对联接排列使用受启发式限制的动态规划算法。

其它情况 (GROUP B