数据库的原理，一篇文章搞定（三）

合并联接

合并联接是唯一产生排序的联接算法。

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

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

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

排序

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

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

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

合并联接

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

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

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

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

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

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

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）
换句话说，我们需要用下面的查询快速得到答案：

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 种可能性。确定联接的顺序是个二叉树的排列问题，会有 (2*4)!/(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），所以，不必在每个计划中计算这个子树的成本，计算一次，保存结果，当再遇到这个子树时重用。用更正规的说法，我们面对的是个重叠问题。为了避免对部分结果的重复计算，我们使用记忆法。

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

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。最后保留成本最低的执行计划。

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

抛开细节不谈，只需一个良好的模型和一个 N*log(N) 复杂度的排序，问题就轻松解决了。这个算法的复杂度是 O(N*log(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 BY, DISTINCT…) 由简单规则处理。

查询计划缓存

由于创建查询计划是耗时的，大多数据库把计划保存在查询计划缓存，来避免重复计算。这个话题比较大，因为数据库需要知道什么时候更新过时的计划。办法是设置一个上限，如果一个表的统计变化超过了上限，关于该表的查询计划就从缓存中清除。

查询执行器

在这个阶段，我们有了一个优化的执行计划，再编译为可执行代码。然后，如果有足够资源（内存，CPU），查询执行器就会执行它。计划中的操作符 (JOIN, SORT BY …) 可以顺序或并行执行，这取决于执行器。为了获得和写入数据，查询执行器与数据管理器交互，本文下一部分来讨论数据管理器。

数据管理器

在这一步，查询管理器执行了查询，需要从表和索引获取数据，于是向数据管理器提出请求。但是有 2 个问题：

关系型数据库使用事务模型，所以，当其他人在同一时刻使用或修改数据时，你无法得到这部分数据。
数据提取是数据库中速度最慢的操作，所以数据管理器需要足够聪明地获得数据并保存在内存缓冲区内。
在这一部分，我没看看关系型数据库是如何处理这两个问题的。我不会讲数据管理器是怎么获得数据的，因为这不是最重要的（而且本文已经够长的了！）。

缓存管理器

我已经说过，数据库的主要瓶颈是磁盘 I/O。为了提高性能，现代数据库使用缓存管理器。

查询执行器不会直接从文件系统拿数据，而是向缓存管理器要。缓存管理器有一个内存缓存区，叫做缓冲池，从内存读取数据显著地提升数据库性能。对此很难给出一个数量级，因为这取决于你需要的是哪种操作：

• 顺序访问（比如：全扫描） vs 随机访问（比如：按照row id访问）
• 读还是写

以及数据库使用的磁盘类型：

• 7.2k/10k/15k rpm的硬盘
• SSD
• RAID 1/5/…

要我说，内存比磁盘要快100到10万倍。

然而，这导致了另一个问题（数据库总是这样…)，缓存管理器需要在查询执行器使用数据之前得到数据，否则查询管理器不得不等待数据从缓慢的磁盘中读出来。

预读

这个问题叫预读。查询执行器知道它将需要什么数据，因为它了解整个查询流，而且通过统计也了解磁盘上的数据。道理是这样的：

当查询执行器处理它的第一批数据时
会告诉缓存管理器预先装载第二批数据
当开始处理第二批数据时
告诉缓存管理器预先装载第三批数据，并且告诉缓存管理器第一批可以从缓存里清掉了。
……
缓存管理器在缓冲池里保存所有的这些数据。为了确定一条数据是否有用，缓存管理器给缓存的数据添加了额外的信息（叫闩锁）。

有时查询执行器不知道它需要什么数据，有的数据库也不提供这个功能。相反，它们使用一种推测预读法（比如：如果查询执行器想要数据1、3、5，它不久后很可能会要 7、9、11），或者顺序预读法（这时候缓存管理器只是读取一批数据后简单地从磁盘加载下一批连续数据）。

为了监控预读的工作状况，现代数据库引入了一个度量叫缓冲/缓存命中率，用来显示请求的数据在缓存中找到而不是从磁盘读取的频率。

注：糟糕的缓存命中率不总是意味着缓存工作状态不佳。更多信息请阅读Oracle文档。

缓冲只是容量有限的内存空间，因此，为了加载新的数据，它需要移除一些数据。加载和清除缓存需要一些磁盘和网络I/O的成本。如果你有个经常执行的查询，那么每次都把查询结果加载然后清除，效率就太低了。现代数据库用缓冲区置换策略来解决这个问题。

缓冲区置换策略

多数现代数据库(至少 SQL Server, MySQL, Oracle 和 DB2)使用 LRU 算法。

LRU

LRU代表最近最少使用（Least Recently Used）算法，背后的原理是：在缓存里保留的数据是最近使用的，所以更有可能再次使用。

图解：

为了更好的理解，我假设缓冲区里的数据没有被闩锁锁住（就是说是可以被移除的）。在这个简单的例子里，缓冲区可以保存 3 个元素：

1：缓存管理器（简称CM）使用数据1，把它放入空的缓冲区
2：CM使用数据4，把它放入半载的缓冲区
3：CM使用数据3，把它放入半载的缓冲区
4：CM使用数据9，缓冲区满了，所以数据1被清除，因为它是最后一个最近使用的，数据9加入到缓冲区
5：CM使用数据4，数据4已经在缓冲区了，所以它再次成为第一个最近使用的。
6：CM使用数据1，缓冲区满了，所以数据9被清除，因为它是最后一个最近使用的，数据1加入到缓冲区
……
这个算法效果很好，但是有些限制。如果对一个大表执行全表扫描怎么办？换句话说，当表/索引的大小超出缓冲区会发生什么？使用这个算法会清除之前缓存内所有的数据，而且全扫描的数据很可能只使用一次。

改进

为了防止这个现象，有些数据库增加了特殊的规则，比如Oracle文档中的描述：

『对非常大的表来说，数据库通常使用直接路径来读取，即直接加载区块[……]，来避免填满缓冲区。对于中等大小的表，数据库可以使用直接读取或缓存读取。如果选择缓存读取，数据库把区块置于LRU的尾部，防止清空当前缓冲区。』
还有一些可能，比如使用高级版本的LRU，叫做 LRU-K。例如，SQL Server 使用 LRU-2。

这个算法的原理是把更多的历史记录考虑进来。简单LRU（也就是 LRU-1），只考虑最后一次使用的数据。LRU-K呢：

考虑数据最后第K次使用的情况
数据使用的次数加进了权重
一批新数据加载进入缓存，旧的但是经常使用的数据不会被清除（因为权重更高）
但是这个算法不会保留缓存中不再使用的数据
所以数据如果不再使用，权重值随着时间推移而降低
计算权重是需要成本的，所以SQL Server只是使用 K=2，这个值性能不错而且额外开销可以接受。

关于LRU-K更深入的知识，可以阅读早期的研究论文（1993）：数据库磁盘缓冲的LRU-K页面置换算法

其他算法

当然还有其他管理缓存的算法，比如：

2Q（类LRU-K算法）
CLOCK（类LRU-K算法）
MRU（最新使用的算法，用LRU同样的逻辑但不同的规则）
LRFU（Least Recently and Frequently Used，最近最少使用最近最不常用）
……

写缓冲区

我只探讨了读缓存 —— 在使用之前预先加载数据。用来保存数据、成批刷入磁盘，而不是逐条写入数据从而造成很多单次磁盘访问。

要记住，缓冲区保存的是页（最小的数据单位）而不是行（逻辑上/人类习惯的观察数据的方式）。缓冲池内的页如果被修改了但还没有写入磁盘，就是脏页。有很多算法来决定写入脏页的最佳时机，但这个问题与事务的概念高度关联，下面我们就谈谈事务。

事务管理器

最后但同样重要的，是事务管理器，我们将看到这个进程是如何保证每个查询在自己的事务内执行的。但开始之前，我们需要理解ACID事务的概念。

“I’m on acid”

一个ACID事务是一个工作单元，它要保证4个属性：

• 原子性（Atomicity）: 事务『要么全部完成，要么全部取消』，即使它持续运行10个小时。如果事务崩溃，状态回到事务之前（事务回滚）。
• 隔离性（Isolation）: 如果2个事务 A 和 B 同时运行，事务 A 和 B 最终的结果是相同的，不管 A 是结束于 B 之前/之后/运行期间。
• 持久性（Durability）: 一旦事务提交（也就是成功执行）,不管发生什么（崩溃或者出错），数据要保存在数据库中。
• 一致性（Consistency）: 只有合法的数据（依照关系约束和函数约束）能写入数据库，一致性与原子性和隔离性有关。

在同一个事务内，你可以运行多个SQL查询来读取、创建、更新和删除数据。当两个事务使用相同的数据，麻烦就来了。经典的例子是从账户A到账户B的汇款。假设有2个事务：

• 事务1（T1）从账户A取出100美元给账户B
• 事务2（T2）从账户A取出50美元给账户B

我们回来看看ACID属性：

原子性确保不管 T1 期间发生什么（服务器崩溃、网络中断…），你不能出现账户A 取走了100美元但没有给账户B 的现象（这就是数据不一致状态）。
隔离性确保如果 T1 和 T2 同时发生，最终A将减少150美元，B将得到150美元，而不是其他结果，比如因为 T2 部分抹除了 T1 的行为，A减少150美元而B只得到50美元（这也是不一致状态）。
持久性确保如果 T1 刚刚提交，数据库就发生崩溃，T1 不会消失得无影无踪。
一致性确保钱不会在系统内生成或灭失。

[以下部分不重要，可以跳过]
现代数据库不会使用纯粹的隔离作为默认模式，因为它会带来巨大的性能消耗。SQL一般定义4个隔离级别：

• 串行化(Serializable，SQLite默认模式）：最高级别的隔离。两个同时发生的事务100%隔离，每个事务有自己的『世界』。 -可重复读（Repeatable read，MySQL默认模式）：每个事务有自己的『世界』，除了一种情况。如果一个事务成功执行并且添加了新数据，这些数据对其他正在执行的事务是可见的。但是如果事务成功修改了一条数据，修改结果对正在运行的事务不可见。所以，事务之间只是在新数据方面突破了隔离，对已存在的数据仍旧隔离。 举个例子，如果事务A运行”SELECT count(1) from TABLE_X” ，然后事务B在 TABLE_X 加入一条新数据并提交，当事务A再运行一次 count(1)结果不会是一样的。 这叫幻读（phantom read）。
• 读取已提交（Read committed，Oracle、PostgreSQL、SQL Server默认模式）：可重复读+新的隔离突破。如果事务A读取了数据D，然后数据D被事务B修改（或删除）并提交，事务A再次读取数据D时数据的变化（或删除）是可见的。 这叫不可重复读（non-repeatable read）。
• 读取未提交（Read uncommitted）：最低级别的隔离，是读取已提交+新的隔离突破。如果事务A读取了数据D，然后数据D被事务B修改（但并未提交，事务B仍在运行中），事务A再次读取数据D时，数据修改是可见的。如果事务B回滚，那么事务A第二次读取的数据D是无意义的，因为那是事务B所做的从未发生的修改（已经回滚了嘛）。 这叫脏读（dirty read）。

多数数据库添加了自定义的隔离级别（比如 PostgreSQL、Oracle、SQL Server的快照隔离），而且并没有实现SQL规范里的所有级别（尤其是读取未提交级别）。

默认的隔离级别可以由用户/开发者在建立连接时覆盖（只需要增加很简单的一行代码）。

并发控制

确保隔离性、一致性和原子性的真正问题是对相同数据的写操作（增、更、删）：

如果所有事务只是读取数据，它们可以同时工作，不会更改另一个事务的行为。
如果（至少）有一个事务在修改其他事务读取的数据，数据库需要找个办法对其它事务隐藏这种修改。而且，它还需要确保这个修改操作不会被另一个看不到这些数据修改的事务擦除。
这个问题叫并发控制。

最简单的解决办法是依次执行每个事务（即顺序执行），但这样就完全没有伸缩性了，在一个多处理器/多核服务器上只有一个核心在工作，效率很低。

理想的办法是，每次一个事务创建或取消时：

监控所有事务的所有操作
检查是否2个（或更多）事务的部分操作因为读取/修改相同的数据而存在冲突
重新编排冲突事务中的操作来减少冲突的部分
按照一定的顺序执行冲突的部分（同时非冲突事务仍然在并发运行）
考虑事务有可能被取消
用更正规的说法，这是对冲突的调度问题。更具体点儿说，这是个非常困难而且CPU开销很大的优化问题。企业级数据库无法承担等待几个小时，来寻找每个新事务活动最好的调度，因此就使用不那么理想的方式以避免更多的时间浪费在解决冲突上。

锁管理器

为了解决这个问题，多数数据库使用锁和/或数据版本控制。这是个很大的话题，我会集中探讨锁，和一点点数据版本控制。

悲观锁

原理是：

如果一个事务需要一条数据
它就把数据锁住
如果另一个事务也需要这条数据
它就必须要等第一个事务释放这条数据
这个锁叫排他锁。
但是对一个仅仅读取数据的事务使用排他锁非常昂贵，因为这会迫使其它只需要读取相同数据的事务等待。因此就有了另一种锁，共享锁。

共享锁是这样的：

如果一个事务只需要读取数据A
它会给数据A加上『共享锁』并读取
如果第二个事务也需要仅仅读取数据A
它会给数据A加上『共享锁』并读取
如果第三个事务需要修改数据A
它会给数据A加上『排他锁』，但是必须等待另外两个事务释放它们的共享锁。
同样的，如果一块数据被加上排他锁，一个只需要读取该数据的事务必须等待排他锁释放才能给该数据加上共享锁。

锁管理器是添加和释放锁的进程，在内部用一个哈希表保存锁信息（关键字是被锁的数据），并且了解每一块数据是：

被哪个事务加的锁
哪个事务在等待数据解锁

死锁

但是使用锁会导致一种情况，2个事务永远在等待一块数据：

在本图中：

• 事务A 给 数据1 加上排他锁并且等待获取数据2
• 事务B 给 数据2 加上排他锁并且等待获取数据1

这叫死锁。