CMU-数据库导论-2

Query Execution

处理模型

当关系型数据库接收到SQL查询时，会将其转化为执行计划。理想情况下，你希望查询计划是一个有向无环图，directed acyclic graph，也就是DAG。大多数系统是将其实现为树。理论上DAG是更优的结构，因为树不能重用一些输出，除非使用特殊的技巧。

管道是操作符的合计，数据库在这些操作符之间连续传递，无需阻塞或等待更多数据。

管道中断器（pipeline breaker）本质上是管道的边界，除非在查询中执行另一个操作（另一个管道），否则无法继续处理当前管道中的任何元组。

管道的核心思想是，定义了一个边界，在这个边界内，我们可以执行一系列操作符，而无需将结果物化到中间存储。

处理模型定义了数据库将如何执行查询计划，以及如何将数据从一个操作符移动到另一个操作符。这里有些操作方式适合OLAP有些适合OLTP。

控制流（control flow）是只是数据库系统用来下一步要运行哪个操作符的机制。它可以是一个管道或者一系列运算符。数据流则决定了操作符发送的位置和方式。

在迭代器模型中控制流和数据流的界限实际上会变的模糊。

在迭代器模型中，表示数据已足够，停止运行的方式，和指示其完全停止的方式是相同的。一个操作符的输出会取决于我们想要使用的处理模型。

常见的三种方法是

• iterator model：最常见，pg，mysql，oracle，db2都是用这个。
• materialization model：少见
• vectorized/batch model：常见，OLAP系统中用的多。

迭代模型

这是最常见的实现方式，尤其在行存储系统中。

查询计划中的每个算子都要实现系统提供的API，这个API包含三个基本的函数。

其中next函数会发出指令，算子会生成下一个元组，这个元组成为正在处理数据的输出结果。

父算子会不断在其子算子上重复调用next函数，直到子算子没有更多元组能够返回。它会返回空指针和一个文件结束标记。

因此，如果一个算子有一个子算子，其并不关心子算子实际上是如何生成数据的。只需要调用子算子的next函数，不需要关心是来自网络，还是来自索引。

我们可以维护一些关于算子状态的元数据。所以我们必须要open和close函数。当调用索引扫描算子的open函数式，就像为B+树创建迭代器一样，实例化迭代器，移动它生成一个元组。先open，调用next直到eof，最后调用close清理迭代器。

当顶层的算子调用child.next时，会发生阻塞，然后执行流程会跳转到下层算子。（不设置的情况下，数据库默认使用的是inner join）

管道之间存在依赖关系，R没有执行完毕之前，S是不能执行的。

父级不在乎子级真正调用next时干了什么，可以是实际去查询一条数据，也可以时将查询好的数据直接返回。

这种方式几乎被用了所有的DBMS中。这种方法的另一个优点是容易控制输出，如果有一个limit语句只要10条数据，那么只需要在获取10个元组后停止调用getNext即可。这就是之前说的，控制流和数据流在某种程度上是混合在一起的。

物化模型

物化模型中仍然有一种next函数，它实际上就像，给我一切。因此不再是每次调用操作符时生成一个元组，而是直接获取该操作符产生的所有元组。

这项技术，20世纪90年代名为monadb的项目，Duckdb实际上是mongnadb的嵌入式版本。

获取S中的所有元组，添加到输出缓冲区，然后现在传递给这个运算符，它会扫描数据并应用谓词。

但是如果有一百万条记录，谓词只会匹配其中俩条，显然是不合理的。因此这个领域里一个非常常见的优化方式是算子融合。基本思想是，将同意流水线的不同算子内联，或者组合起来，从而避免不必要的复杂操作。

在上述例子中，扫描R表，应用谓词，如果满足条件就将其放入输出缓冲区。

物化模型更适合OLTP，因为查询只访问小部分的元组。更少的执行和协调开销，更少的函数掉用。对于OLAP，调用next会很昂贵，因为必须要扫描10亿个元组的场景存在。而且我们不想一次性物化所有的数据，因为我们希望分解处理流程并将其并行化，而不必担心耗尽所有内存，只需要生成运算符的之间结果即可。

一个显而易见的方式是在俩者之间做一些事情

向量化模型

向量化模型类似迭代器模型，当调用next时，得到的不是一个元组，而是一批元组。

现在获得该批元组的运算符将处理这批元组，在整个批上面处理。

• 操作符的一次内部循环处理多一个元组
• 批的大小可以基于精简和查询资源

如果知道某个列中的属性和元组返回相同的值，可以使用类似游程编码的方式来进行。Duckdb底层就会进行类似的操作。

和之前的例子类似，但是这次不再是传递单个元组，而是传递一个向量。

该模型在Clickhouse，oracle，sql server，duckdb中均有使用。

这是2006,2007年才提出的概念，最初的论文是基于monadb的项目。该项目发现，迭代模型在现代CPU上非常慢。

很适合OLAP数据库系统，近15年来出现的大多数，OLAP系统，即使是较早的系统，也经过改造使用这种方法。

CPU喜欢进行的操作方式是，一段连续的内存数据，连续执行1000次操作。

基于推送的迭代模型

这种方式相对少见。但是可以更精确的控制数据在缓存和寄存器中的位置。

上述的都是让父节点往子节点执行，另一种方式是将叶子节点的数据推到父节点。如果

我们现在不再使用getNext方法来触发操作符，通知他们开始运行并生成输出。需要一个位于这些之上的协调器或者调度器。它会显示的调用这些操作符，告诉它们该开始运行了。

duckdb和snowflake用了这种方式。

访问方式

最暴力的搜索方式是读取每个页面，直到找到目标，或扫描完整的表。

有三种不同的方式

• 顺序扫描
• 索引扫描 有不同变体
• 多索引扫描，选择多个然后合并查询结果

顺苏扫描根据数据是聚集型还是非聚集型可以做不同的优化。

顺序扫描

如果没有可用的索引，顺序扫描是最基本的方法。在构建新的数据系统时，通常先实现顺序扫描，已验证数据存储的正确性。

可以使用页面目录或其他机制来获取数据。

虽然很慢，但是之前已经讨论过一堆方法进行优化。比如数据压缩，预取。

• 数据跳过（oracl术语）*

对于要扫描的表，其中一部分数据可能是查询不需要的。它分为有损压缩和无损

• approximate queries（有损）如果查询不需要精确的结果，就不需要扫描每个页面了。这样就可以用统计置信度衡量请求的准确性。比如提供最小值最大值平均值的近似函数。比如统计9.99亿和9.998之间的差距可能是不重要的。但是数据库默认不进行该操作。必须明确告诉系统需要近似计算。
• zone map（无损）：区域图是预先计算好的元数据，描述了特定页面或者一组页面中数据的概要信息。根据这些信息决定是否需要读取这些页面。区域图的粒度可以很细，针对单个页面，也可以很粗，针对多个页面。显然，范围越大，选择性就越差。OLAP领域的几乎所有数据库系统都支持某种区域图。

有区域图的情况下我们还可以跳过一些查询。

parquet和ORC都原生支持这种特性。在最初的论文中，它被称为小型物化聚合信息。物化这里指的是预计算。

index扫描

另一种选择是使用索引扫描。

应用程序在需要扫描的表上创建索引，然后收到一个查询请求，运行时数据库必须确定，对于特定的查询使用的最佳索引是什么。

当执行查询

select * from students where age<30 and dept='CS' and contry='US'

我们必须决定要使用哪个索引。因为我有俩个索引。有可能在这里使用部门更好，有可能使用年龄更好。

实际上我们想把它们都用在我的查询中。这被叫做多索引扫描（multi-index scan 这是oracle的叫法）。pgsql中称为位图扫描。然后将他们进行并集操作，得到交集。mysql中称之为索引合并。

它们将对索引进行多次扫描，取回匹配的记录ID。根据是and还是or确定哪些是匹配的记录。

在这里我们可以先试用索引获取年龄小于30岁记录的ID。然后对第二个索引进行查找，部门为CS。取这俩个结果的交集去获取那些元素。然后检查这些元素是否满足最后一个谓词，即国家为美国。

pgsql就是通过bitmap来进行实现的。oracle中实际上使用的是集合，计算集合的交集。

修改操作

UPDATE / DELETE
子算子（Child Operator）传递目标记录的 Record ID（RID），父算子根据 RID 直接定位要修改或删除的记录。
需要记录已经处理过的元组（tuple），避免同一条记录因为查询计划（如 Join）产生多个结果而被重复更新或删除。
INSERT

有两种实现方式：

1. 物化（Materialize）后再插入
   先把所有待插入的元组缓存（Materialize）到算子内部。

等输入结束后，再统一执行插入。

1. 流式（Pipeline）插入子算子每产生一个元组，INSERT 算子就立即插入。
   不需要额外缓存，能够保持流水线执行（Pipeline）。

假设我们要对每个少于1100薪资的人涨薪100。

这里存在一个万圣节问题。

在update或者delete语句中，由于更新后数据再次满足扫描条件，导致同一行数据被重复更新。这个这个问题最早于 1976 年在 IBM 的 System R 项目中发现，因为是在万圣节（Halloween）那天发现的，所以得名 Halloween Problem。

如果扫描索引，找到记录，立即修改之后，这条数据可能到了原本索引的后面。这是因为索引需要保持有序。

解决方案是，跟踪之前处理过的逻辑记录，这样就不会尝试重复更新同一条记录了。因为当你更新查询是，从集合语义角度或者回滚语义角度来看，应该只更新一次操作。

执行

Expression Tree（表达式树）是现代数据库执行器（Execution Engine）中最核心的数据结构之一。几乎所有关系型数据库（MySQL、PostgreSQL、SQL Server、DuckDB、Snowflake 等）都会在执行 SQL 时构建各种形式的 Expression Tree。

他负责需要计算的所有表达式。Sql parser在解析sql时就会把表达式解析为一棵树。

salary * 1.1 + bonus

会变成

        +
       / \
      *   bonus
     / \
salary 1.1

每一个节点都是一种 Expression。

最终形成查询计划。

但是CPU更倾向于顺序执行。沿着树中的指针向下查找并不是一个好的选择。当然这里需要先表示为树，才能进行额外的优化。

更好的方式是直接评估表达式。我们希望一个比较运算不进行树节点的遍历，因为对cpu不友好。希望只是通过一个函数来比较。

有些系统甚至会生成整个查询计划，包括所有这些谓词。但实际上这非常少见。

pgsql具有一种叫做即时编译（JIT just in time）的技术专门优化这些where子句。

这样就不必为查看的每个元组都遍历那颗树了，我只是编译了一个完全按照我想要方式执行的函数。这里需要做一些成本效益分析，判断是否值得。PGsql会尝试评估需要扫描多少元素。编译谓词（where子句）预计花费多少时间？这么做是否划算。在数据量大的情况下，先编译再执行，比直接通过树要好。

但是不是每个数据库都会有类似的方案。大部分系统都没有采用pgsql的做法，因为这在实现上非常复杂。

另一种替代方案是snowflake采用的，先预编译函数，而不是jit，然后根据谓词内容，将这些函数拼接起来。sql中有的数据类型只有那么多。所以可以预先准备一系列宏。预先生成这些函数。在运行时，调用函数指针来执行相同的操作。它们运行的是向量模型，而不是迭代器模型，因此可以分摊函数调用的开销。

此外，还可以进行常量折叠。

另一种常见的字表达消除方法时，如果我看到子表达式。被重复调用，我们可以只计算一次病重复使用它。

同一个逻辑查询，或者同一个查询可以用很多不同的方式来进行。

并行查询执行

我们想要利用cpu的多核能力。如果它能在单节点上运行，理论上应该能在多节点和多个woker上运行。

但是并行查询和分布式数据库是不应用的。大家都在用更多的资源来执行查询，但是并行查询无论是存储资源还是计算资源，在物理位置上都会比较临近。我们可以假设通信是可靠的，不需要付出很高的成本。

我们使用woker的组件来调度和执行任务。woker是系统中负责执行任务的计算单元，可以处理客户度请求，以及内部后台或维护任务。当讨论垃圾回收和MVCC时，可能会看到一个后台进程需要定期这些垃圾回收。当讨论大型结构化合并树，需要在后台进行压缩，这时候可以给该任务分配一个worker。

一个woker可以对应一个线程，也可以对应一个进程，还有一种是嵌入式数据库的woker。最常见的是每个worker对应一个线程。

这是因为现在编写多线程程序不像80,90年代那么困难了。

进程worker

如果要支持并行，最古老的进程模型就是每个工作进程使用一个线程，这意味着每一个woker都有其自身完整的操作系统进程。就像调用fork来创建一个独立的进程，这个进程有自己的地址空间并且与其他进程隔离。

pgsql有一个pgmatser负责调度，这个调度进程实际上是数据库系统的一部分。调度线程会选择一个工作进程来处理这个链接，如果当前没有工作进程，就fork一个进程。在这里可以把调度器看作是一个协调器，查询发送到调度器程序，然后调度器程序将它们分发给其他工作进程。这种情况下如果进程之间要进行通信，就要使用共享内存之类的技术。因此需要做更多的工作，依赖操作系统来提供很多功能。

这些老系统采用单进程woroker的模式的原因是，早期unix系统，多线程实现方式各不相同。db2，oracle，pgsql用的都是多进程实现。

开发者需要针对每个平台重新实现基础设施。但是如果使用posix标准，fork和join操作是许多功能的基础。而所有操作系统都原生支持这些操作。

线程worker

现代的实现和方向法则更倾向于单线程worker的方式，开发者可以使用posix thread，或其他操作系统提供的线程库系统方面可以更方便协调和调度这些线程。

mysql，sqlserver都用的是这种方式。

这样系统就能更号管理线程调度，因为它能控制每个线程的运行时间和方式。所有线程都在同一地址空间内，因此worker之间的通信成本会更低。与单进程worker模式不同，在单进程worker模式下，如果一个进程崩溃，只会影响该进程本身。但是一个线程在单线程worker模式下崩溃，则会导致整个系统崩溃。

近20年来开发的数据库都支持这种模式，即便是DB2和Oracle这样的老牌系统也增加了对单线程模式的支持，尽管它们最早出采用的是单进程worker模式。只有那些从pgsql派生或基于pgsql开发的系统才会基于沿用pgsql的单进程worker模式

嵌入式数据库系统

嵌入式数据库通常没有自己的线程，也不负责线程的管理，因为它们被嵌入在应用程序的内部。

比如sqlite，rocksdb，duckdb，leveldb。

应用程序会对这个数据库发起调用，无论哪个线程进行调用，系统库都会用该线程来调用他们所需执行的任何查询。对于duckdb，你可以告诉它启动额外的线程，以便它可以用来并行执行查询。在经典的系统模型中，sqlite和rocksdb，都由调用线程来执行。

第一个支持这种模式的嵌入式数据库是berkeleydb。

调度

当一个查询出现时，数据集必须决定如何执行，在哪执行，以及何时执行。大多数数据库执行一个简单的先进先出优先级队列。无论出现什么查询，都会首先查询。

虽然操作系统有自己的调度器，但它也不知道实际查询想要做什么。因为它只看到一些盲目的进程或者线程。数据库系统更能比操作系统更知道该做什么。更高端的系统，比如Oracle，DB2，sql server会基本上重写所有事情，不依赖操作系统做任何事情。

但是，出现一个查询，并不意味着可以将该查询分配到多个worker上。

mysql就是最好的例子，出现一个查询时，只有一个线程可以完整的执行这个查询，没有类似pgsql那样的并行查询。它们无法跨多个核心进行拆分。

那么如何构建系统支持多个运算符的并行。有俩个主流的方式，查询间并行和查询内并行。

内部查询并行

可以让不同连接或不同应用程序发起多个查询。在系统中同时运行。大多数数据库都是采用先到先得的方式。

在一些系统中，比如db2，可以根据用户名来设置事务或者排序优先级。比如CEO的查询速度可以比普通销售人员更快。

如果所有查询都是只读的，也就是说不修改数据库，那就好办了，不需要协调数据，反正不会存在数据更新。

内部查询并行的基本思路是把一个查询分解成多个任务，然后分配给多个worker同时运行。这样就有可能缩短查询的执行时间。

实现内查询并行主要有俩种方式。

一种是水平平行（intra operator），也就是横向扩展同一操作符的多个实例，同时运行。（用的最多）

另一种是垂直并行（inter operator），也就是同时运行不同的pipeline操作符。它们直接存在明确的依赖关系。（很少用）

这些技术不是互斥的，可以结合使用，之前讨论的各种算法，在具体实现的时候做一些小改动就可以了。而且我们之前讨论过的所有算法几乎都有并行版本。比如hash join，grace hash join。

此外，还有第三种类型，即树形并行本质上是前俩种方式的结合。（高端系统能实现的功能）

intra operator

在intra operator中，我们的想法是采用查询计划，不拧将操作符调用复制到工作线程中，以便它们可以同时并行运行。关键在我们将为每个操作符实例分配不同的任务，以便处理输入数据不同的子集。

具体来说，假设有1000个元组的表，并且有四个工作线程，可以将前25%的数据分配给第一个工作线程，接下来25%分配给下一个工作线程以此类推。现在它们可以并行进行扫描，以及过滤等任何其他需要执行的操作。而且它们直接不需要相互通信，其实我们只是在对数据进行分区，然后分发给不同的worker。但现在，某些情况下还需要吧数据整合起来。为了查询计划中执行的后续操作，我们需要引入一种新机制，叫做交换算子（exchange operator）。交换算子在关系代数中没有对应的概念，但我们需要它来进行数据合并。我们可以把它看做是管道的中断器，它的作用是，必须等到所有子运算符都产生了所需的结果，才能继续执行后续的查询计划。无论使用推送模型，还是拉取模型，这一点都一样。在pgsql中，这个操作叫做gather，类似Mapreduce的原理，是开始下一阶段之前的一个屏障。

这是最常见的收集方法，将多个输入流合并成一个输出流。

inter operator

现在讨论操作符间的并行，即不同的操作符可以同时运行，即使它们之间存在依赖关系。有的时候这被称为pipelined parallelism。

还是以这个sql举例子，假设hash计算非常昂贵，我们想让这些操作并行执行，那么可以一个线程负责扫描，一个线程负责进行哈希投影。

这在流逝系统中更为常见，比如spark slq，kafka等。在这些系统中查询操作是连续的输入数据流没有终点。

bushy parallelism

这是水平并行和垂直并行的混合组合，将所有这些并行方式结合起来使用。

比如对于笛卡尔集操作。

同时对A,B，C，D进行连接，

将所有这些元组混合生成所有可能的组合，使用缓冲区来跟踪之前处理过的数据，当新的元组进来时可以匹配它们。

但是很多情况下，磁盘和锁是性能瓶颈，因此即使有一堆worker，能够并行查询实际意义也不大。所有的worker都必须访问磁盘，并且因此阻塞，那么并行化就起不了什么作用。

IO并行

思路是，如果我们可以将数据库的数据分散到多个存储设备上，那么就能升级磁盘带宽。有很多方式可以做到这一点。

最简单的方式是给单个数据库防一个单独的磁盘。也可以将单个表或者单个关系放到一个磁盘上。你可以跨越多个磁盘拆分关系表。

pgsql和mysql的innodb都支持表跨磁盘。在一些系统中可以将WAL放到一个磁盘上，然后将常规表的数据放到另一个磁盘上（Oracle）。这样高速写入WAL，读取数据时，就不会受到写入操作干扰。高端的系统可以对IO并行机制进行显式控制。

对于mysql等着用的系统，在实际数据目录本身中，你只需要将符号链接放到不同的驱动器，数据系统不知道你做了这些，但是你获得了并行性，因为多个磁盘可以同时运行并且互不干扰。

在pgsql中有tablespace，你可以指定这些表属于此表空间。

如果让数据库之间控制磁盘可以实现更细粒度的控制。下面的方式思路类似raid0

理论上可以让数据库来管理这些在不同磁盘上的页面，也可以让操作系统来管理，表现为一个透明的逻辑磁盘。如果数据库系统拥有控制权，它就可以决定如何进行拆分。

条带化的另一个方式是raid1，也就是说对于数据库系统的每个页面，我们都会将其写入，并把多副本写入到每个不同的磁盘驱动器。

因此，第一页会被写入磁盘1,2,3，这样做的好处是，如果要进行大量的读取操作，速度会更快，因为可以访问任何一个驱动器。但这样也增加了写入成本，因为对一个页面的任何操作，都必须在三个驱动器上写入三份。

实际上有一些硬件设备可以自动完成这些操作。raid0，raid1，raid有不同的级别，可以组合使用。软件方案是让数据系统自行管理这些操作，那么就可以使用更多的技巧，无需条带化或者镜像，可以使用纠删码来结合俩者的优点。这通常比硬件支持更快和更灵活。

理解IO并行的一种方式是，在性能耐用性和容量之间进行权衡。更快的速度，更大的容量，可靠性之间做权衡。

我们更希望数据库系统内部实现显示分区，由数据库负责数据划分方式，存储位置，以及如何将数据加载到内存中并行处理。这是sql的优势，无论数据库是否经过分区或者分片，相同的sql理论上都应该能运行，因为它只是在处理逻辑表。不关心数据的物理布局。

查询计划

问题

我们会基于元数据的信息，使用近似估计，来判断一个计划是否优于另一个计划。

比如在join操作的时候有个where子句，那么我们就可以先过滤然后再进行join。

一个笑话是，如果你尝试在优化查询方面有所成就，但最终失败了，那么plan B应该是当一个火箭科学家。每个数据库都会面临这个问题，并且没有AI和LLM能神奇的解决这个问题。

整体的执行姐狗味，解析器获取sql转化为抽象语法树，比如rust的sqlparser，c++中的libpgquery。现代数据库系统都倾向于兼容pgsql的语法。因此你可以获得pgsql解析器模块的优化版本。然后将抽象语法书作为绑定器传递到数据库中，绑定器的作用是将数据库对象的字符串标识，比如表名，映射到目录的对象ID或者内部ID。在pg中有一个pg类表，其中存储了所有这些信息。绑定器用来检查表是否存在，解析器主要负责检查sql查询的语法是否正确。接下来绑定器会生成逻辑计划，逻辑计划会说明需要执行哪些连接操作，需要引用哪些表，进行哪些投影和筛选操作。

但是逻辑计划只描述了怎么做，没描述做什么。然后绑定器会将操作传递给优化器，并且取决于是否采用基于成本的优化方法，目录中会包含一个成本模型组件，通常目录里本来就会有一些统计信息。然后最后输出一个可以最终执行的物理计划。

所以在pgsql，duckdb，sqlite中调用explain时，看到的输出结果，那个树状结构就是物理计划。

逻辑计划会从高层次告诉我们要做什么，物理计划会说明，我希望在查询计划中执行的逻辑步骤，实际上应该以何种物理的方式执行。

在某些情况下，也可以将一个逻辑计划，分解为多个物理计划。逻辑计划转化成物理计划这个过程是不可逆的。查询优化已经被证明是np-hard问题，连接操作可能出现各种排列组合。

现在的思路是我们需要找到一批不同的逻辑计划备选项。然后对于每一个方案，尝试评估其成本，我们正在基于成本的优化，最终要么时间耗尽要么搜索完毕，要么确定这是目前能找到的最佳物理计划。

之所以困难是因为可以把所有可能的查询计划看做是一个巨大的搜索空间，一个包含各种复杂查询解决方案的空间，然后我们无法探索一切。因此我们需要更聪明的做出决策，如何在这个有限的时间内，快速找到这个庞大空间中的某个区域，进行探索，找到一个相对好的方法。因为实际上不可能进行详尽的搜索。对于简单查询来说很简单，比如ID=1的表中选择所有字段，并且ID列上存在索引，那么就能快速找到最优计划。但当进行连接是，上千张表的连接非常复杂。

我们将要做的俩种通用方法是应用规则和启发法，，我想在执行连接之前进行筛选过滤。在进行查询优化的时候，

启发式/规则

我们可以重写查询，以删除我们认为可能是坏主意的操作。谓词下推就是最好的例子，或者让投影提前进行，我们通常只查看元数据而不是实际数据，因为查询甚至还没有开始运行，但是mysql在查询计划时会尝试通过采样收集数据，但是大部分系统不会这样做。

pgsql会执行基于规则的方法几次，然后执行基于成本的方法，然后再返回到基于规则的方法。

基于成本的查询

• 使用模型估计执行计划的成本。
• 为查询枚举多个等效计划，并选择成本最低的计划

优化方法

基于规则的方法

基于规则的方法实际上是关于逻辑计划优化，这里思路是我们会有一些规则，基本上是我们想要在查询计划中匹配的模式，如果某个模式匹配成功，我们就知道它存在某种低效之处，需要我们去消除。然后我们应用第一个转换规则，通过重写规则来进行改变。核心思路是去除那些已知是无用的操作。将其查询计划引导至一个方向，即基于成本的搜索。这是一种更为详细的搜索，确保我们只少从一个好的起点开始。在这种情况下，我们无法进行任何比较来决定，未执行这种转换是否更优。比如作为数据库开发人员，我们知道谓词下推通常是一个好的选择，所以通常会采用这种做法。在这种情况下我们无法保证找到最优执行方案，但是能帮我们朝向正确的方向前进。比如进行投影的时候丢弃掉了大部分数据，我们可能希望复制投影操作符，放到连接操作符的下方。成本模型在这里可以起作用，如果表只有三列，那么不需要花费时间进行投影操作，将数据从扫描操作复制到连接操作中可能是一种浪费。

通常来说在这些规则中，会看到一些硬编码的数值。比如设置阈值10，如果列的数量超过10就执行投影下推。查询优化器的目标就是在合理的成本计算下，尽可能丢掉更多没用的东西。几乎所有数据库都会采用某种形式的这些规则。因为它们速度快，实现起来也相对容易。

基于成本的搜索（CBO）

如果有很多物理计划备选的情况下，选择哪个计划呢？比如排序归并连接，循环嵌套连接，索引嵌套循环连接。我需要一种方法来说明，在所有这些连接算子的选择中，哪一个是最好的？这种估算是数据库系统内部的成本，基于特定系统实现，与其他系统不具备可比性。如果数据发生变化，硬件，系统参数调优发生变换，这些成本在系统内部也可能发生变化。

IBM在20世纪70年代构建了第一个基于成本的优化器。基本上要做的是列举出一些列不同的查询计划估计它们的成本，他们会使用不同的方法来处理单表查询的情况，以及多表连接查询的情况。最棘手的情况可能是子查询或者嵌套查询了。

优化器可能会运行枚举所有这些不同的计划，逐一尝试，直到发现已经找到了所有可能的方案，因此能够确定哪个方案是最优的。但是对于三个以上表的查询，这样做就变得非常困难了，情况会变的非常复杂。就像在pgsql和mysql以及所有其他系统中一样，可以设置查询优化器运行时间上限。因为优化器运行时间可能超过sql运行时间。

如果是单表查询的化，优化更为简单，关键在于找到最佳访问方式。是否需要进行全表扫描，数据是否按照索引排列。如果命中了主键索引，那么就很容易选择。

但是如果where同时用了A和B字段进行查找，A和B拥有各自的独立索引，该如何处理？我们可以将俩个结果合并在一起求交集等。查询算法根据这些成本来估算重新排序这些谓词。

多表查询计划

bottom-Up

代表：System R / Volcano / PostgreSQL

自下而上，动态编程风格，我们从一个没有任何内容的查询计划开始。起点是列出所有需要连接的表，通过迭代的方式逐步构建，并尝试找出最佳的连接顺序和算法。然后选择哪个具有最佳下降路径回到起点的方案。

IBM构建的第一个查询优化器使用这种方法，首先应用我们在开始看到的一系列静态规则，目的是丢弃那些明显不合理的方案。然后他们会使用动态规划来确定表的最佳连接顺序，本质上是分而治之的策略。大多数开源数据库都会使用这种变体。umbra系统采用了一种更加激进的方式，结合超图来实现。

System R是1974年启动的项目，是第一个实现sql的数据库。是一个研究原型，后来IBM将其发展为DB2数据库

System R的工作方式是，首先将查询分解为块，可以简单理解为俩个表之间进行连接操作，计算出这个块的逻辑运算符，实际上更复杂的树形计划可能才是最优解。

不考虑矮胖树（平衡）是因为构建过于困难。放弃构建矮胖树，可以大大减少搜索空间。并且可以做流水线化。

top-Down

代表：Cascades / SQL Server / Oracle

自顶向下的方法，类似与分支定界搜索。从最顶层开始，目标是，这就是我希望查询产生的结果。然后向下逐步分解开始添加操作符，最终达到想要的效果。但是他们在构建查询的时候只会考虑left deep join tree。也就是说A和B连接的结果和C连接的结果和D连接。

这里的想法是如果我们认识到在某个分支的某个点上，我目前为止在这个分支上看到的最佳成本，或者说分支下降到当前为止的成本，已经比我搜索中见过的最佳成本还要糟糕，我们就知道不必追踪分支的其他部分，因为成本空间不可能降低。这就是sqlserver做的。

微软在20世纪90年代基于cascades中的方法，构建了sql server中的新查询优化器。sql server现在有可能夺取最佳优化器的宝座（之前是德国的umbra）。

应用一系列规则，将逻辑计划转化成其他逻辑计划，AB连接可以转换为BA，也有一些规则将逻辑计划转化为物理运算符。AB连接可以转化为A和B的哈希连接。用了这些规则，就不能从物理运算符回到逻辑运算符了。

enforcer rules是专门用来处理物理属性的规则。

在top-down优化过程中，优化器从根节点向下探索，父节点会对子节点提出物理属性要求，最常见的偶俩种。

• 排序顺序（Ordering）：例如 ORDER BY 要求，或者 Merge Join 要求两侧数据按连接键有序。
• 数据分布（Distribution）：例如并行执行时，数据需要按某个Key进行Hash重分布（Repartition），才能做并行聚合。

问题来了：子节点原本生成的计划可能不满足这个属性要求（例如子节点扫描的是无序的堆表）。此时，优化器不能直接丢弃这个子计划，而是需要给它“加装一个功能”来满足父节点的要求。

这个“加装功能”的动作，就是由 Enforcer Rules 触发的。它会在现有的逻辑/物理算子之上，强制插入一个能改变物理属性的物理算子（Physical Operator）。

嵌套子查询

嵌查询实际上比较麻烦，因为必须考虑子查询，所以可以重写它们消除相关性，并将它们展平尾join查询。也可以提取出嵌套查询运行一次，就像对该查询使用CTE一样，将结果注入到外部查询中。

我们可以把嵌套查询重写为join查询。

如果不是这样，需要对sailors表中的每个元组运行内部查询，现在可以直接进行连接操作，速度会快很多。

数据库的CTE是什么
CTE 的全称是 Common Table Expression（公用表表达式），可以简单理解为一个临时的、只存在于当前查询执行期间的“虚拟结果集”。

它的核心作用就是让复杂的 SQL 查询变得更易读、更易写，通常用来替代子查询或递归查询。

也可以直接分解执行。

处理表达式

与查询计划类似，我们也可以建立一个基于规则的系统，对表达式进行模式匹配和重写。

这里的关键在于对于where或on子句中的一些列谓词，我们要尽可能减少计算量，同时保证查询结果的准确性。

与查询计划类似，我们也可以建立一个基于规则的系统，对表达式进行模式匹配和重写。对于表达式树的优化，除非需要重新排序，否则通常不需要成本模型。

有些优化是显而易见的，比如处理不可能成立的谓词比如

select * from A where 1=0;

可以对这种情况进行模式匹配，判断是否存在一个包含等值比较的俩个常量子句。检查结果是否为真，如果结果为假，则将它们重写为真或假。

在某些系统中，如果计算结果为假，pgsql和洽系统可以识别出这是一个不可能的谓词，甚至都不会去扫描表。

此外

select * from A where val between 1 and 100 or val between 50 and 150;

可以直接重写为

select * from A where val between 1 and 150;

成本估算

如何确定一个查询比另一个查询更好？比如对于连接查询，不仅需要知道俩个表的数据量，还需要知道这些谓词的选择率，才能确定要过滤掉多少元组。对于连接操作，有多少数据会被过滤掉，通过连接运算符之后，又被传递到投影运算符。计算预估这些非常困难，因为我们实际上无法运行真实的查询，那样做会太慢，这是一个np-hard问题。

我们仍然需要用到成本模型，帮助我们预测在特定数据库状态下的行为。

成本模型将由俩部分组成，物理成本和逻辑成本

• 物理成本指的是，cpu时间消耗，IO使用量。包括不同运算符的缓存命中次数。
• 逻辑成本指的是运算符输出的元组数量。以及这些元组的大小，列入包含的列数。这些信息可以帮助我们判断是否应该提前进行投影操作。然后将这些信息传递给下一个运算符，用于预测该运算符的预期输出。

大多数系统会结合俩者。高端的企业系统更侧重使用第一种方式。pgsql主要使用IO成本。DB2会在启动时运行一些列基准测试，测量CPI，磁盘和网络的速度，并将这些结果用作物理成本计算中的常量。

以pgsql为例，他们只是有这样的概念，有CPU，IO成本，它们的成本是彼此相关的。顺序IO和随机IO也是如此，它们的成本是相对的。因此可以设置一些参数来调整这些成本，例如顺序页面读取的默认成本为1。随机页面读取的成本是该值的若干倍。

在pgsql的文档中有一段这样的警告：这些值是no well-defined，如果想让系统正常工作，必须正确设置这些参数。

固态，机械可能会让这些值不准确。比如SSD的性能会随着存储容量增加而降低。比如磁盘空间在100时这些参数可能是最佳的，但是磁盘空间到90%时，最佳参数可能就需要调整了。

我们如何估算这些不同操作符的输入和输出，以便我们能以物理成本估算等方法老评估工作量呢？每个数据系统都会维护一个目录，查询优化器会利用这个目录来维护关于数据特征的统计信息。系统使用统计信息来评估不同操作符中各种谓词的选择性。从而预估需要完成的工作量。大多数系统会在后台自动维护这些统计信息，你也可以通过sql命令手动触发更新。这实际上是在后台调用一个查询。对标进行顺序扫描，并计算出数据信息的内部表示，如直方图或者草图等。

比如oracle数据库会在每天晚上9-11点运行。重新计算所有数据。在pgsql中，如果一个表的数据更新超过20%，就会触发统计信息更新。

简单来说，对于给定的表，选择性是满足谓词条件的元组所占的比例，这些元组将会作为操作符的输出。

假设查询年龄为9的数据，在45条中查询出来4条，那么该谓词的选择性就是4/45。现在我可以用这个信息来确定连接的先后顺序，我们可以用它来判断哪个表在谓词下推之后的数据量更大。

在很多情况下通常假设数据是均匀分布的，我们不可能为每个值维护直方图，假设有10亿条记录，10亿个唯一的值，我们不想重复存储只出现一次的值。因此需要对数据进行合并或聚合，以简化处理。系统还需要假设各个谓词之间是相互独立的，但是情况不是总是如此。

此外在进行连接查询的时候，我们通常假设被连接的表中存在一个匹配的key。但是情况总是并非如此。

对于直方图，我们可以用等宽直方图或者等频直方图来进行数据压缩优化。

还有一个场景的方式是采样。并不是所有系统都这样做，方法的核心思想是从原始表中抽样一部分数据，组成一个样本集，它会被存储在目录里，或者想其他表一样存储在数据库里。如果现在要对谓词成本进行评估，不运行完整的查询，只是在样本的数据上进行一个线性扫描，这样就能更好的估计世纪的选择性了。比如采样中有三分之一的数据符合谓词查询的结果，就可以作为评估的依据。

并发控制

有些数据库比如sqlite，允许有很多读取者，但是只允许有一个写入者。但是mysql和pgsql中，它们都允许多个事务同时运行，因为这样性能更好。

我们需要解决操作的任意交错执行。意味着并行的结果需要和串行执行是一样的。

数据库的事务只能控制内部发生的事情，如果发消息队列和数据库一起，我们则并不能保证俩者的原子性。因此我们需要定义正确的含义，并判断事务在交错执行中，这些操作是否有效。

ACID中的C其实有点勉强，因为这个C是要开发者编写sql的正确性才能保证的。

原子性

有俩个方式保证原子性，最常见的日志记录。这里的日志记录是跟踪数据库在运行时所做的所有操作的机制，将这些操作写入log，就像一个分类账。实际上日志可以独立于数据库本身进行维护。今天几乎每个数据库都在使用某种形式记录日志。在某些情况下可以获得更好的性能，对于可审计和可恢复性也很有帮助。

另一种方法叫做影子分页，每当更新页面时，都会在影子空间创建该页面的副本，然后应用更新。在提交时，只需确保以原子性的方式将所有这些页面安装到数据库系统当中。这是IBM在1970年代首次实施的。但是出于性能考虑，这不是一个好主意。需要在页面上进行碎片整理，因为现在所有的更新最终会在空间中产生碎片，必须重新使用这些空间。这会严重影响顺序扫描性能。实际上很少有数据库使用这种方法（couchdb和lmdb）。不过相比于日志记录，影子分页的优点是，崩溃后恢复速度非常快，几乎是瞬间完成的。因为要做的就是回到之前数据库的这种一致性或者正确状态。系统崩溃时，未完成事务残生的修改都保存在一些脏页中，重启后这些脏页会被直接忽略。WAL恢复需要一定时间

一致性

其实如果事务本身没有问题，数据库的状态也是正确和一直的，那么事务运行后，数据库的状态应该也是正确的。应用程序必须告诉数据库怎么样才算正确，你可以通过完整性约束来定义正确性。

总的来说数据库系统会保证，在事务运行前后，所有完整性约束都会成立。一般来说这是在每个查询基础上完成的，但也可以先让事务做任何操作，只有在最后提交的时候做检查，因为有些操作可以批量处理。但是大部分系统在执行更新操作的查询之后会立即检查完整性约束。

在分布式数据库，和nosql中存在最终一致性的概念。一致性在分布式上下文中更有意义。

隔离性

我们希望数据库提供的这种抽象，事务可以运行，并且应用程序不必担心它是否会看到来自同事运行的其他事务或者其他不符合预期的数据。我们希望提供一种假象，我在独占数据库的运行。

为了实现这种并发性，我们可以并行对不同对象的读写。

数据库中实现了并发控制协议。比如二阶段锁定（2PL），乐观并发控制（OCC）。

它将成为我们系统中的一种算法或实现。通常分为悲观锁定和乐观锁定。大多数系统通常只实现一种协议。

可序列化调度将是一种任意交错操作的事务调度，它使数据库达到的状态和按串行执行时顺序一样。

如果调度的事务在同一对象上执行操作，我们将次定义为事务间的冲突。

因此根据调度中可能发生的冲突类型，会出现不同的异常。

可以有

• 读写冲突
• 写入冲突
• 写写冲突，丢失更新

• 脏读：事务允许读取尚未提交事务写入的数据。
• 不可重复读（unrepeatable read）：一个事务在多次读取同一对象时获取不同的值。

当对oracle设置为SERIALIZABLE的时候底层其实也不是串行执行。

冲突可串行化

俩个调度表当且仅当它们对相同对象进行多个操作时，才被认为是冲突等效的。冲突操作的排序，比如在同一对象上的读写，写写，他们的顺序必须一致。

我们可以通过构建依赖图。可串行化是在问：一个并发执行的结果，能不能找到一种串行执行顺序，使两者的最终效果完全一致。

一个并发执行，如果最终效果等价于某一种串行执行顺序，那么它就是可串行化的。

一个节点等于一个事务，一条边表示一个事务必须先于另一个事务。只要图中没有环，就说明不会发生任何冲突。

因此这个调度不是串行化的，它不等同于串行排序。直观上看t1的输出取决于t2做某事。t2的输出取决于t1做某事。

上图中的依赖没有成环，因此，这里是可串行化的。

即使这些事务可能在不同的时间启动。我也会保证数据可串行化的顺序提交。

视图可串行化

即便t3的begin命令在t2的begin命令之前启动，t3也会在t2之后执行。

如果事务执行后的最终结果等同于某种串行排序执行的结果，即使由于冲突实际上不应该发生这些操作，那也没关系（结果可串行化）

这里写入了不应该允许写入的数据

但是这里唯一关心的是A的最终值，这里最终重要的是t3的写入值。没有人关心T1读了什么，t2又读了什么呢？数据库的最终状态就是最后写入者的内容。以上执行顺序，相当于t1，t2，t3一次执行调度。

视图等价性不仅允许所有冲突可串行化的调度，还允许其他视图可串行化调度，尤其是那些执行忙写的速度。

支持视图可串行化，意味着能更好理解应用程序的需求和事务本身的含义，从而获得更好的并行性，但这通常需要静态分析，甚至人工判断是否可行，这就是为什么没有什么实际系统能够支持。

我们想象调度的所有可能是一个空间，最里面是序列化调度，外面是冲突可序列化调度，它是串行的超集。再往外是视图可序列化调度。

• Serial：事务一个一个执行，没有任何交错。
• Conflict Serializable（CSR）：虽然交错执行，但可以通过交换不冲突操作变成某个串行顺序。
• View Serializable（VSR）：不能通过交换操作变成串行，但最终每个事务看到的数据以及最终数据库状态，与某个串行执行一致。

由于判断 View Serializable 是 NP-Complete 问题，因此几乎没有数据库直接去判断它。

大部分实际上使用2pl等实现。

持久性

如果一个事务提交了，并告知了外部系统，那么无论发生什么，恢复后，它们仍然应该能够看到他们的更改。

基本思路就是日志记录和影子分页（shadow paging）。

这些都是静态调度的内容，意味着数据库提前知道事务的所有操作。也就是说，所有的渡河写操作都会提前声明，因此我们可以决定如何交错它们，已确定是否可以产生冲突串行化。但是真实的系统中，大部分系统都不是这样工作的。除非使用存储过程。

大概nosql运动盛行时，许多人认为事务是个坏主意。但是后期大部分nosql都增加了事务。

从程序员的角度来看，假定事务以串行顺序运行，处理起来就容易多了。

spanner论文：We believe it is better to have application programmers deal with performance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions.

实际上，大部分 OLAP 数据库都支持一定程度的事务，只是它们更关注批量数据导入的一致性，而不是高并发事务处理。

Lock

我们可以通过锁来解决不同事物的隔离性。

• latch保护数据结构的物理完整性（内存）
• lock保护数据内容的逻辑一致性（事务）

对于latch来说只有读写锁。

对于lock来说我们有共享和独占俩种模式。共享锁意味着读取，独占锁意味着写入。在使用latch时，我们必须以正确的编码方式编写代码以避免死锁。

对于lock，我们使用额外协议的处理系统内部的死锁。因为查询是程序员发送的，可能会导致死锁。因此数据库系统必须保护开发者，防止它们因自身的原因导致系统故障。我们将采用流量协调器（traffic coordinator）或者事务协调器（transaction coordinator）它可以检测到死锁。或者在某些情况下，可以通过对锁请求排序，避免死锁的发生。

lock不再像b+树中的latch那样保存在数据结构内部，而是位于节点本身中。我们现在在数据库系统中设置一个集中管理器，称为事务管理器或锁管理器。它本质上是一个哈希表，跟踪现有锁的信息。谁以何种模式持有锁，以及使用优先级队列活队列来跟踪哪些事务正在等待获取该锁。

与latch相比，维护lock信息的机制更加昂贵复杂，latch则更为轻量。我们之所以要这种重量级的管理器，是因为考虑到事务持有锁的时间，我们认为值得付出这样的代价，在一个中心化的位置跟踪所有锁。

此外，事务通常不会显示地请求锁定和解锁。这种事情通常是自动发生的。比如运行一个select查询，系统会自动获取共享锁。当进行提交操作的时候，系统会自动解锁。

Two phase locking

我们有共享锁和排他锁。

这是俩种最基本的类型，实际上可以参考数据库手册，会发现它们的兼容性矩阵要复杂许多。锁的的类型有很多种，对于不同类型的对象，用于更新表的目录，用于目录更新与索引更新。

事务在对任何对象进行读写操作之前，都必须像锁管理器申请该对象的锁。可以进行锁升级操作，页技术说，如果持有一个对象的共享锁，下一步要进行写操作，我们可以将已经持有的共享锁升级为排他锁。锁管理器的职责是记录哪些事务持有哪些锁。以何种模式持有，以何种模式等待。事务完成操作后会释放对应的锁。

锁管理器通常以哈希表的形式出现。在某些系统比如pgsql中，可以像查询普通数据库一样查询锁管理器。在记录日志信息时，我们不需要将锁表的内容保存到磁盘，因为系统崩溃重启之后，这些信息已经没有意义。

俩阶段锁是一种协议，它规定了如何释放获取锁。这是20世纪70年代首个被证明正确的并发协议，无需预先知晓所有查询，即可实现事务的可序列化。IBM在开发System R系统时发明了该方法，并在20世纪90年代荣获图灵奖。

增长（growing）阶段：事务可以持续请求锁，锁管理器照常授予或者拒绝，一旦事务释放锁，就会进入自动收缩阶段。进入收缩（shrinking）阶段后，事务便无法再获取新的锁，只能释放锁。这就避免了之前的问题，即解锁A之后又尝试获取另一个锁（当释放锁，导致被其他事务修改时，自己看到的数据就不一致了）。

俩阶段锁可以保证事务或调度冲突是可序列化的，因为任何先例图，或者事务序列总是无环的，也就是说不会导致它们之间产生循环的边。

但是会产生性能问题，被叫做cascading aborts 级联终止。

在这里如果t1发生回滚，但是t2正常执行，就会产生问题。

这样的调度安排在俩阶段锁定下是允许的，但当t2尝试提交，或任何事务读取了来自一个未提交事务的数据时，就必须等待，确认其他事务是否成功提交，之后才能提交。其实你不希望任何人读取到你已经写入，但尚未提交的内容。

我们将对俩阶段锁进行微调以规避这一特定的问题。这被称为string strict 2PL。其中不存在任何收缩阶段的切换，实际上在收缩阶段不会释放任何锁。只有当事务提交时，才会释放你拥有的锁。

有一个略微宽松的版本，称为strict 2pl，允许在收缩阶段释放共享锁。但是会将独占锁保留到最后，但是强严格模式下，共享锁和独占锁会被一只保持到事务结束。

因此如果有一个方案不允许其他任何事务读取或写入来自另一个事务的数据，直到该事务完成提交，那么该调度方案就被称为严格调度，即操作的严格顺序。确保我们不会修改或读取正在进行中的数据。这样的好处是可以避免上述的级联回滚问题。

而且这实际上简化了实现过程，因为现在当一个事务回滚时，由于我们知道没有其他事务可能读取过我们写入的数据，因此回滚操作会变得非常简单。

当然，实际上没有显示的解锁命令，没有一个sql命令是用来执行解锁操作的。大多数系统会之间提供，序列号隔离级别，默认情况下，你会得到严格的俩阶段锁定。

处理死锁

有俩种方式处理死锁

• 死锁检测是用一个后台线程，来检测死锁何时可能发生，并尝试解除它。
• 预防指的是我们用某种方式对事务获取锁的顺序进行排序，确保不可能发生死锁。

死锁检测

这本质上是一个事务循环，这些事务都在等待另一个线程释放锁。除非我们采取措施，否则这些锁永远无法释放。

对于oracle这些数据库，会同时使用俩种方式，并且根据工作负载的不同，采用不同的方式来切换使用这俩种机制。它还会维护许多统计数据。如果要进行死锁检测，应该终止哪个事务，并获取其锁，以便将其提供给其他事务。从而最大限度减少资源浪费并提高性能。

这里需做权衡，我们需要考虑死锁检测工作线程的积极程度。如果每60秒运行一次，那么检查循环的开销会很低，最坏的情况下可能需要60秒才能解决死锁。但是如果让死锁检测器每微妙运行一次，那么基本上就是在浪费cpu的资源，一遍又一遍的检查死锁。

当一个事务正在等待另一个事务的缩时，该事务等待图就引入一条边。

通常找到这些循环是np-hard问题，因此数据系统将运行一个简单的形式，有限寻找设计俩个事务的循环。但是如果没有通过简单的检测找到换，那么就要运行更耗时，更复杂的检测。

但是如何选择受害者是一个复杂的问题。这体现了企业系统和开源系统的区别。因为我们在决策中会考虑很多不同的因素，这些因素可能会因应用程序的需求变化。在企业系统中，你可以调整参数来制定如何选择死锁受害者。

最可能的情况是，我想运行这个事务，然后杀死最老的事务，或者选择最年轻的事务。也可以基于已经执行的查询数量，优先保留已经进行了更多查询的事务。

也可以根据锁定的项目数量，杀死锁较少的事务，因为获取锁是昂贵的。

也可以是回滚事务的次数，如果这个事务被反复一直回滚，就可以让这个事务优先执行。

另一个问题是，想回滚多远。

最简单的做法是完全回滚该事务的所有操作，然后将错误告诉应用程序，让应用程序决定是否重新启动。某些情况下可以使用savepoint进行部分回滚。可以将其理解为事务生命周期中的一个书签。如果发生死锁，将事务回滚到这个保存点，然后重新执行后续操作，通常只在存储过程的情况下才这样做。因为存储过程可能包含应用程序逻辑，根据查询结果不同，会执行不同分支和查询。在某些情况下，即使部分回滚，最终仍能实现可序列化的排序。

死锁预防

当一个事务请求锁时，系统会立即判断是否允许该事务获取此锁，如果该锁已经被其他事务持有，系统会判断当前事务是否可以等待，还是直接强行终止持有锁的事务，夺取其资源，还是选择放弃自身，因为无法等待。这种方法不需要额外的后台工作线程。我们不需要图，无需寻找循环依赖，因为这种请求排序和事务处理方式能够确保不会发生死锁。因此我们假设时间戳较旧的事务具有更高的优先级，

这种死锁预防算法的俩个变种是wait-die和wound-wait

关键在于，如果存在俩个事务，它们时间戳永远不会相同，因为否则它们就是同一个事务。

• 等待-死亡算法的核心思想是，年老的事务可以等待年轻的事务释放锁，那么请求锁的事务可以等待持有锁的事务释放锁，然后获取该锁并运行。如果请求锁的事务比持有锁的事务年轻，则必须终止自身，因为不允许等待。
• 创伤-等待核心思想是，年轻事务可以等待老年的事务。因此请求事务的优先级高于持有事务，那么持有事务必须终止。你可以射杀另一个事务，然后获取它们的锁并且释放。

一个是射杀，一个是自杀。

锁粒度

到目前为止讨论的内容都是一个锁对应一个对象，我们只是大致假设它们是元组，实际上不一定是。

但是问题是，如果我们必须获取大量的锁，那将非常昂贵。访问锁管理器不像latch那么简单，因为需要先获取锁管理表，如果每次更新十亿个元组会非常昂贵。

这就是为什么我们现在要拖过不同的锁粒度引入分层锁定的原因。当一个事务想要获取锁时，我们可以决定它想要获取的该锁的范围，即粒度。我们加更粗粒度的锁，这样只需要少量访问锁管理器。

mongodb刚推出时，整个数据库只有一个全局锁，这意味着，即使只更新一个元组，也会导致其他人无法读取和写入数据库。

理解这一点的关键在于，将数据库视为一种层级结构，在顶部有一个数据库，数据库由数据表组成。

现在有一个T1，如果T1获取了表锁，那么该表在层级结构中的下级节点，即该树节点的所有后代，都会被隐式锁定。因此获取表锁会隐式锁定其下所有内容。

在锁的层级结构中，最常见的是表锁和元组锁。页面上的锁可能是另一个最常见的内容，但是并非所有系统都实现它们。

某些系统在进行DML和DDL时会锁定数据库，但不表锁和元组锁常见。非常罕见的是单个属性或者单个列上具有非常细粒度的锁（yougabyte）。

这就是意向（intention）锁的用武之地，这个想法是在此层级结构中的较高级别节点上的提示，用于告知事务，你在树的较低层级，以共享或独占模式获取对象。

意向锁会告诉你，底层持有一个显式的锁模式，在上层，持有模糊的意向锁。

意向锁主要分为三种

• 意向共享锁（IS）：提示其他事务在层级结构中的某个较低层级，正在使用显式共享锁获取某些对象。
• 意向独占锁（IX）：提示其他事务在底层有事务正在使用显式锁独占获取对象。
• 共享意向独占锁（SIX）：实际上是俩中种锁的结合，是意向共享锁和意向独占锁的结合，以共享模式读取下方一部分数据，也会以独占模式更新下方的一些对象。

俩个事务可以在同一对象上持有不同的锁，只要这些锁是兼容的。

因此现在我们需要跟踪给定对象上持有锁的模式，可以是一个或多个。

在进行six锁的时候数据库并不知道你需要改哪些行，所以SIX锁和IX锁是不兼容的。

我们可以支持锁升级，如果系统意识到底层正在获取大量的锁，那么最好返回上层结构，升级已持有的锁，将其至于显式模式。这样就能获取所有需要的锁，无需在锁表中为每个所都添加条目。因此可以减少所管理器的次数。

实践中不需要显式制定获取或释放锁，在某些系统中可以获取对特定资源的独占锁，但大多数应用程序并非这样设计。

for update

当执行select 查询是，数据存储会自动将读取的对象锁定为共享模式。一个常见的模式是读取，修改写入。我们可以在执行查询的时候，直接使用独占模式，因为稍后将会更新这些数据。这会强制系统在尝试获取锁并读取数据时，立即进入独占模式获取锁。也可以设置共享锁，比如select for share，如果采用较低隔离级别，会强制事务持有锁的时间比更低隔离级别下更长。select for share能防止其他事务更新该记录。

对比维度	普通的 SELECT	SELECT ... FOR SHARE
锁的类型	表级共享锁 (ACCESS SHARE)	表级行共享锁 (ROW SHARE) + 行级共享锁 (FOR SHARE)
锁定对象	整个表	查询返回的特定数据行
目的	保证在查询表时，表不会被删除或修改表结构的操作（如 DROP TABLE, ALTER TABLE）破坏。	告诉数据库：“我可能要修改这些行，请在我检查（读取）期间阻止其他事务修改它们。”
对其他写操作的影响	不阻止其他事务修改数据行。主要保护表结构不被删除或大改。	会阻止其他事务对这些行执行 UPDATE、DELETE 或 SELECT FOR UPDATE/FOR NO KEY UPDATE 等操作。它会等待直到锁释放。
对并发读取的影响	通常不阻塞其他普通的 SELECT 查询。	不阻塞其他 SELECT FOR SHARE 或 SELECT FOR KEY SHARE，即多个事务可以同时持有共享行锁。

skip locked

另一个功能叫做select skip locked。这里可以执行select查询，但是不必等待获取sleect语句中任何数据的锁，我可以指示数据库系统，忽略已经被锁定且无法获取的数据，直接跳过。

这会将数据库的抽象概念或者事务处理机制暴露给应用，有缺点和优点。

OCC

时间

俩阶段锁定可以理解为一种悲观的协议，它要求你必须获得想要操作的锁才能进行并发。然而在某些工作负载环境和数据库中冲突可能很少。大部分事务周期都很少。大多数事务都是，开始事务，读取和写入少量数据，然后提交，一气呵成。

假设冲突少周期短，那么总是要在事务开始前获取锁不是什么好办法。更号的协议可能针对无冲突场景的优化系统即，事务不会尝试访问或修改相同数据。

并发协议分为俩类，一类是悲观，一类是乐观，乐观依赖于时间戳。

数据库会为每个事务分配一个时间戳，系统根据时间戳来决定事务提交的熟悉。

所以接下来时间戳会渗透到整个系统，也就是说，我们会为每个事务分配时间戳。我们也会为数据库中的每个对象分配时间戳。

这些时间戳不一定是实际的物理时间，但它会是一个整数，代表我们希望发生事务的某种顺序。通常来说，最好的情况是使用64位时间戳。一些如pgsql之类的系统使用32位的时间戳。

对于给定的事务Ti我们会分配一个唯一固定的时间戳，这个时间戳的值是单调递增的，时间戳只能随着时间推移而增加，不能跳回到过去。

因此系统中需要某个模块来负责给事务分配时间戳，先假设一个事务只能分配到一个时间戳。

我们可以用系统的时钟来实现时间戳分配。可以从本地CPU获取当前时间，用本地时钟可能出现时钟漂移。而且如果时钟精度不够，只能到毫秒级，就可能出现俩个事务在同一毫秒发生的情况。我就必须等到下一个毫秒才能分配新的时间戳。

另一个方法是使用逻辑计数器，用atomicinteger，使用CAS保证线程安全。但是这在分布式数据库情况下会存在问题。任何获取这个时间不重要，重要的是它必须随着时间单调递增。

存在一类乐观并发控制协议，其中optimistic concurrency control是最主要的协议。

OCC

如果现在没有冲突，我们就可以把事务在私有工作区里的更改，应用到全局数据库中。二阶段锁定是1976年发明的，OCC是1981年发明的。

OCC被分为三个阶段

1. 读取：事务可以读取和写入数据库，无论何时从数据库读取和写入内容，都是从全局数据库复制到你的私有区，任何读取都是那份副本。这里复制的仅仅是需要更新的数据，表里可能有上千个字段，但是只想更新其中一条。
2. 验证：一旦事务想要提交，自动进入到验证阶段，数据库系统会为你分配事务时间戳。系统会检查它与其他事务是否冲突，这些事务可能是过去已经完成的，也可能是当前正在运行的。
3. 写入：当通过了验证，就可以进行写入阶段，在这个阶段你可以应用对于全局数据库所做的所有更改。然后我们将为每个元组设置一个写入时间戳，以跟踪上次写入元组的该事物。我们将更新全局数据库中的写入时间戳，

在write操作时，我们来看T2的写集，它是空的，因为我们只读了一个数据，并没有进行写入。因此在该阶段什么也不做。然后T1对A进行写入操作。此时T1还没有时间戳，因为它还没有开始提交，我们直接把T1的时间戳设置为无穷大，这样就足以进行跟踪了。当读取A是不会访问全局数据库，而是直接读取之前修改过的同一个条目。然后进入验证阶段，数据系统会分配一个时间戳，为2，我们进行验证检查是否与其他事务存在冲突。这里发现没有冲突，则允许进行写入，我们将用分配的时间戳覆盖原有的无穷大时间戳。然后我们继续在上面安装更改。这个例子在二阶段锁定中也是行得通的。

我们要做的是跟踪每个事务的读写集，并将更改存储在私有工作区中。如果要保证可重复读，必须复制读取的所有内容将其放入私有工作区中。

简单期间，我们采用串行验证，这意味着只有单个事务可以检查是否被允许通过验证阶段提交。如果允许并行验证则需要更多的工作。

• 前向（forward）验证指的是检查正在提交的事务，其读写集是否与仍在运行但是尚未运行的任何活动事务的读写集相交。这意味着这些活动事务尚未进入验证阶段。
• 后向验证（backward）则是回顾过去，查看是否有事务进了我本来应该看到但没有看到的更改。

• 前向验证 (Forward Validation)：检查的是当前要提交的事务T，它的写集合（Writeset）与所有还在运行中的事务的读集合（Readset）是否有冲突。它的逻辑是：“我要写的数据，有没有别人正在读？”如果发现冲突，为了维护一致性，通常会终止还在运行的那个事务，保证当前事务能提交。
• 反向验证 (Backward Validation)：检查的是当前要提交的事务T，它的读集合（Readset）与所有已经提交的事务的写集合（Writeset）是否有冲突。它的逻辑是：“我读的数据，有没有在我执行期间被别人改过并提交了？”如果发现冲突，就必须终止当前正要提交的这个事务，因为它读到了过时的数据。

前向验证

对于前向验证，我们将在每个事务进入验证阶段时分配一个时间戳。然后如果我们的事务要提交，则必须满足以下三个条件之一。当你的事务正在提交时，系统知道哪些事务处于活动状态。并且你会查看它们的写集合，私有空间和所做的修改。满足三种情况就可以进行提交。

如果事务T2想要提交，T1已经提交，T1在T2启动前就完整了写入阶段，那么相当于串行执行。

T1在T2开始写入阶段之前就完成了写入阶段，即使T2仍在运行，T2仍然可以对数据库进行读取和写入操作。如果T1没有修改T2读取的任何对象，那么就不存在冲突。T1可以安全提交。简单来说T1是第一个事务，拥有写入集，如果我的写入集与另一个事务的读取集的交集为空集，那么说明男娘没有读取我写入的任何数据。

上图中T1不允许提交。数据库状态在t1提交时为1，但在T2尝试提交时，它会被分配时间戳2，这意味着它本应看到时间戳2时数据库状态。但他实际看到的是时间戳0时的状态。因此它看到了不应该看到的数据。正向验证是为了保证其他人不会错过你的更改。

在上图的情况中，T1和T2都是允许提交的。其实还需要用锁来保证验证线程的读写安全。

第三种允许的情况是需要确保当前事务的写集合补语其他事务的读集合相交。

因此上图的情况，俩个事务都可以正确提交。

假设当前要提交的是中间这个事务，正向验证的思路是，在事务提交的实际节点，我们要检查的范围和内容包括

从当前事务开始，所有其他事务的读写集合，这些事务在我们提交时，或者说在处于验证阶段时仍然在运行。因此你不需要关心过去运行的事务。如果它们已经提交，就无需考虑了。（其他事务能提交，说明其他事务已经通过了检查）

反向验证

反向验证表示，假设T1在此处需要提交，不需要考虑任何活动的事务，

T2只需要回顾最近提交的事务，检查它们是否写入了我本应该看到但实际上没有看到的内容。因为这些更改最初是在私有工作空间进行的。

如果T1修改了对象A，然后T2读取了对象A，T1提交时这些更改才会被应用到全局数据库，因此T2就丢失了这次写入。

总结

在实践中，冲突较少时，OCC效果很好。比如数据库规模庞大，事务访问模式也很均匀，那么OCC的效果会非常好。如果所有事务是只读事务，因为不需要获取共享锁。

俩阶段锁定中获取锁和维护锁表有巨大开销，将数据复制到私有工作区也会产生很大开销。虽然可以通过增量复制解决这个问题，但是复制内存始终是非常耗费资源的。验证和写入阶段会成为瓶颈，因为在应用更改时，需要获取latch来保护数据结构。此外终止事务的成本在OCC中也比2PL昂贵的多。因为在一个2PL锁定中，如果要访问十亿个对象，但无法获取第一个对象的锁，事务就会终止，这样实际上没有造成任何的资源浪费。但在OCC中会先更新所有10亿个对象，然后尝试提交，最终发现第一个对象仍然无法获取锁，因此不得不回滚所有操作（必须完整执行整个事务，才能确定它是否成功）。

幻读：插入和删除

上面2PL和OCC都只讨论了更新操作，事实上数据库还存在插入和删除操作。

第一个事务想要统计人员表状态为lit的记录数量。

这就像发生了不可重复读。执行了相同的查询返回了不同的结果。这在串行排序或可串行化执行下是不应该发生的。2PL无法防止这种情况。因为导致第二次查询不正确的记录，在第一次查询时并不存在。

因此我们无法锁定不存在的数据，因为我们不知道该锁什么。因此基础版本的2PL和OCC只有当对象是固定不变的情况下才能正常工作。这个问题被称为幻读（phantom read）。

幻读的定义是：两次执行同一个谓词（predicate）查询，返回的结果集发生了变化，因为其他事务插入、删除或更新了满足该谓词的记录。

但是数据库底层锁实现是按索引区间来做的。因此在事务中多次扫描一个表的某个范围，并且在俩次扫描之间有另一个事务插入或删除对象，那么就会产生不一致的结果。

有几种方法来解决这个问题

1. 锁定索引资源，最简单的方法，但是对性能不利。（不常见）
2. 提交时重新执行每次扫描已确认结果是否一致。（少见）
3. 谓词锁：检查不同操作或查询之间的逻辑冲突那，以确定是否存在可能导致幻读的冲突。（非常少）
4. 索引锁：一来索引本身保护数据的范围（最常用）

重新执行扫描：这在内存数据库中最为常见，追踪每次要查询时用到的where子句，当事务需要提交时，除了执行验证阶段（无论采用的是2PL还是occ）都需要重新执行查询中的扫描部分，检查是否有新的结果单身。如果有一个带有where子句的更新查询，希望确保更新所有符合条件的记录。有些数据库比如dynamodb和faunadb会采用类似的做法。它们称之为reconnaissance transactions（侦查事务）。简单来说，限制性所有的查询，但仅仅是为了观察它们的读写行为，并不实际修改任何数据，提交阶段再执行这些查询，检查结果是否一致，一致就apply不然就回滚。

谓词锁：（predicate lock）是一种逻辑锁定方案，用于检查事务尝试持有的锁在多维空间中是否冲突。hyper，duckdb，cedardb，umbra使用了这种方案。实际上这是SystemR在20世纪70年代首次推出的。但是实现过于困难。除了20年代名为精确锁定的近似计数外，几乎没有真正实现它的只有上面四个。

假设对于事务T1的扫描查询，在多维空间中村在一个由where子句指定的有界区域，该区域对应于可能存在的元组。因此该区域拥有一个作用于多维空间的逻辑锁。现在我们要检查的是任何其他查询的多维空空间是否与该区域存在交集。这是只是一个二维投影，如果它们重叠或者相交，则表明它们在逻辑上访问的是相同元组。

但是考虑到有成千上万的事务和各种复杂的查询这会变得非常昂贵。要完全实现这点，复杂读是np-complete的

索引锁

人们实际上做的是，利用索引来管理特定取值范围的锁，从而检查这些取值范围是否存在并发冲突。

这些锁本质上和元组锁类似，实际上它们可以是B+树中的节点。最简单的锁类型是键值锁。在某个属性取值范围内我们对特定的键值进行加锁。锁管理器会记录，对于B+树特定范围内的键值存在一个锁，例如可以包含键值14的锁。你还可以使用gap lock（间隙锁）用于跟踪索引中相邻键值之间的间隙。然后就可以对这些间隙进行加锁。现在可以将这些锁组合成键范围锁，对于给定的键，键范围锁既包含该键上的锁，也包含紧邻其后的间隙锁。

比如查询了一条不存在的记录的时候，我们仍然可以进行锁定。

当然也可以锁定(12,14]。但通常只沿一个方向加锁，以避免不必要的锁重叠。现在可以将上次讨论的分层锁机制应用。在更大范围采用更粗粒度的锁。比如我可以获取[10,16)之间的间隙锁，并设置为意向排它模式。因此依赖数据结构本身可以帮助我们识别或划分希望维护锁定的对象范围。

然而实际上大部分数据库不会以可串行化的方式运行。关闭其中的一些特性，可以获得更好的性能。

• 串行读：强严格的2PL和幻读保护（index lock）
• 重复读：和串行读一样，但是没有幻读保护
• 提交读：和重复读一样，但是S锁被立即释放
• 未提交读：类似重复读，但允许脏读（没有S锁）

理论上可以指定每个事务的隔离级别。每个事务以不同的隔离级别运行。

oracle最高隔离级别是快照隔离。如果你要使用serializable隔离级别，它会说没问题，但实际上提供的是更弱的隔离级别，叫做快照隔离。

google的spanner可以保证事务到达系统的顺序就是它们提交的顺序。没有一个系统同时使用OCC和2PL协议，因为实现其中一个就非常的困难。

MVCC

快照隔离

从概念上来说，在OCC里面发生的事情，就会发现元组存在多个版本，也就是说在数据库中，一个逻辑元组对应多个物理版本。一个逻辑元组可以理解为由主键标识的对象。在使用OCC时，如果我们要修改某个元组，我会先把它复制到私有工作区。这样就有了另一个物理版本，也就是那个逻辑元组的另一个物理副本。

MVCC也是同样类似的思路，只不过这次更加彻底，数据库系统拍给你可以为每个逻辑元组货逻辑对象维护多个物理版本。因此任何时候想更新数据库，都会创建一个新的逻辑版本。在OCC中这个新版本只是把整个元组复制到了私有工作区，但其实还有更好的做法，比如只复制修改的部分。

然后现在任何事务要读取这个对象时，都会看到一个视图，我们称之为快照隔离，也就是事务启动时数据库的状态快照。这意味着，如果另一个事务与你同时执行，但它在你之后启动，而且没有任何更改，那么你是看不到它的。因为你看到的是数据库在启动的逻辑时间点的一致性快照。MVCC可以和OCC与2PL以及其他协议结合使用。我们任然要应用之前讨论过的所有并发控制方法，来确定谁在什么时候可以更新什么内容。这种架构和系统工作方式基于一个理念，即创建事务的多个版本。

MVCC的首次描可以追溯到1978年的一篇MIT博士论文。但这篇论文属于系统领域，直到几年后人们才意识到这实际上可以应用于数据库中我们关注的并发控制问题。MVCC的第一次实现是在一个RDB-VMS的系统中。然后另一个是名为InterBase的系统。现代几乎所有数据库系统都会使用mvcc。

MVCC有俩个核心思想，写入者不会阻塞读取，读取也不会阻塞写入。当一个事务出现的时候，它们将被赋予一个时间戳，该时间戳会说，这是允许你查看该时间戳的数据库的一致性快照的时间戳。因此你不会看到任何未提交的更改。

现在因为读取者可以在某个时间戳读取内容，当事务想要写入对象或元组时，它们会创建一个新的版本。这不会干扰其他人读取旧版本。因此我们将允许事务获得一致的快照，而无需获取显式的锁。因此，自然的我们会得到一种隐式的隔离级别，叫做快照隔离。这意味着我看到的数据库，就像它在某个时间点的样子。因此当20世纪80年代，人们大力宣扬MVCC的一大优点就是可以支持所谓的时间旅行查询。理论上，你可以说，帮我运行这个查询，但是要基于三个星期前的数据库来运行。如果你有所有的数据版本，而且你也没有做任何的垃圾回收清理，那么这件事情就变得简单了。因为你只需要搞清楚，三个星期之前的时间戳是多少。然后就去查看那个时间点的数据。pgsql最初就带有这个功能，这是pgsql在1984年推出的时候，经常被拿来说的功能。但是后期这个功能被砍掉了，因为如果不进行垃圾收集，存储空间很快就会耗尽。

在事务开始时，我们必须分配它的开始时间戳（begin time），因为它需要有一个一致性快照。用哪个时间来查看版本。（OCC只有在准备提交的时候才会给时间戳）因为得直到你能看到啥。现在要读取A最终会定位到元组的A0版本。然后就能读取它。T2把开始时间戳设置成T2的启动时间戳。然后回到之前的版本，把结束时间戳，设置为T2的时间戳。

为了让其他事务知道哪些版本已经提交，因此维护一个Txn事务状态表。在这个表里跟踪所有在系统中活跃或正在运行的事务ID。这里记录者它们的市场价，也就是事务启动时，被分配的时间戳。然后提交状态，或者说这些事务的当前状态。中止，提交还是已清理。

在下图中T2为停滞，直到T1完成提交。

每次执行写入时，创建一个新版本，结束时间是无穷大，索引，我像链表一样跟踪版本链，我会看到A0，其实时间0，结束时间是无穷大。

很明显这种方式不同于串行执行。这是因为快照隔离容易受到我们尚未讨论的成为write skew anomaly的影响。

快照隔离的基本思想是，你可以获得事务开始时存在哎的数据库的一致性视图。因此你不会看到来自事务的任何脏写。如果它们更新了五个数据线，你将不会看到三个错过其他俩个。但是当应用更改时，这并不等同以串行执行的结果。

假设我们有俩个事务，一个想把白球涂成黑色的，一个想把黑球涂成白色的。在快照隔离的情况下。就会变成这个样子。

这是允许发生的。俩个事务都更新了自己需要更新的部分。

但如果真正的串行执行，结果应该是这样的。

要么全白，要么全黑。在pgsql中我们还有一些额外的东西要做。在其他系统中，会对快照隔离进行改造，来支持可序列化。

1992年事务隔离级别的原始返回没有体积这个定义。它根据俩阶段锁定义了隔离级别。

它不仅仅是像我们之前看到的2PL或OCC这样的并发协议，版本控制的概念渗透到了整个数据库中。目前来说，mvcc最不理想的实现是pgsql。mysql和oracle做的更好。如今大部分系统采用mysql和oracle的实现方案。

这是最常见的做法，因为SQL标准没有定义快照隔离，这些数据库就将自己高效的快照实现，安上了标准里“可重复读”这个名字。

• PostgreSQL：它的可重复读级别就是标准的快照隔离。需要真正的串行化，要用它的“可串行化”级别。
• MySQL (InnoDB)：它的可重复读读数据时就是基于快照的，但它额外用间隙锁防止了部分幻读，所以不完全等同于纯快照隔离。想关闭间隙锁用纯快照，可以用 READ COMMITTED + binlog_format=ROW。
• Oracle：它的可串行化就是快照隔离。

数据存储

可以将逻辑元组维护的不同版本，想象成一个链表。版本链中会包含指针，指向元祖的下一个版本。因此会存在一个包含记录ID的字段，大致沿着版本链遍历下一个版本的位置。访问的入口通常是版本链的头部。

有三种方式可以存储版本。

1. 仅追加：每次创建新版本时，复制旧版本，将其作为新的元组插入到表中，同时在头部信息中维护版本链。（最差但是pgsql用了）
2. 时间履行存储：类似仅追加存储，但是新版本不会存储在同一个表中，而是存储在指定的时间旅行表中。可以把所有的版本都放在那里。因此会有一张主表包含最新或者最旧的版本，在主表中会有指针指向这些辅助表，所有版本数据都会存储在这些辅助表中。
3. delta存储：这种方法其实是最好的，不用存储完整元祖，而只是存储增量信息。如果表里有上千列，前俩种方法要保存全部的数据。增量存储只需要保存被修改过的列。然后把这些数据放在独立的增量存储区域。

append only

所有数据都放在一个表中。数据库里的没标都会分配一个表空间来存储数据。每次进行更新操作，都会把整个记录复制到表里的一个新位置，写入新的值。

然后更新版本链，指向新创建的版本。在这里A0是最旧的，如果要找到最新的，需要沿着版本链直到找到想要的那个。版本链排序实际上也对性能有很大的影响。

如果从旧到新排序，意味着每次进行查找时，比如跟随一个索引，查找索引，得到记录ID，这将到版本链的链头，然后沿着版本链进行扫描，直到找到我需要的版本。同样需要查看开始时间和结束时间，来判断此版本是否符合你的需求。

从新到最旧的版本链头将是最新的版本，因此当查找索引，并且只需要最新版本时，查找操作首先定位到为止，就是我需要的版本。但是每次更新元组的时候，都需要维护大量的索引。现在必须更新所有条目确保它们都指向链头（如果采用原地更新的存储方式这实际上不是问题，因为如果只是覆盖链表头，那么总是会有新的版本）。

time-travel Storage

和追加存储基本相同。区别在物理版本不是存储在主表中。而是存储在一个完全独立的表中，这个表本质上是另一个数据表。这个表用于存储所有历史版本。

每次更新A2，会将A2复制到时间旅行表中，然后用最新版本更新主表中的主版本记录。

最后如图中一样更新指针，让它指向这里的下一个版本。在最初设计为不是多版本的数据库中，会使用这个方法。在这里会创建大量重复的元组副本。比如有1000列，但它只更新其中一列，你仍然需要付出一样的代价。sql server就是这样工作的。

delta storage

基本思想是每次更新，值复制已经修改的列以及其修改之前的值，把它存储到增量存储段中。mysql将其称之为回滚段（rollback segment）。这就像是一个undo lock。

那么我将存储之前的值以及在主表中的版本信息，现在再设置一个指针指向它，并在主表中覆盖，就是该元组最新的版本了。

这有点类似于LSMtree。在LSM树种，我们是将新的条目，也就是新的更改附加到树上，而在这里，新的更改是直接应用到主表上的，然后把之前的值放到版本存储里。

垃圾收集

现在我们必须用垃圾收集来清理无效的数据，否则存储空间迟早会被耗尽。回收哪些不再被任何事务需要的旧版本所占用的空间。意味着没有任何活跃的事务需要访问这些元组的版本。除非我们需要时间旅行功能，否则我们就没有理由保留这些旧版本。

那么如何查找过期的版本，如何确定合适可以安全回收这些记录所占用的空间存储？

backroom vacuuming：查找过期版本的方法是执行元组级别的垃圾回收。我们查看版本本身，然后说当前正在运行的事务是否还能看到这个版本。我们可以使用专用的工作线程来执行，这被称为backroom vacuuming，或者在是扫描数据的同时进行清理。

为了防止每次查找都遍历整个表，可以维护一个bitmap作为一个脏图。用于跟踪哪些页面被修改过。每次页面被修改时，就将对应位置设置为1。

所以当清理程序启动时，会查看脏位图，值获取那些被标记为脏页的数据。检查是否可以删除任何条目。清理程序不知道页面是被如何修改的，因为只记录了一个位。这基本上就是pgsql执行的方式。也可以在终端命令行调用vacuum命令，它同样会启动清理。

cooperative cleaning协同清理的核心思想是，工作线程会知道哪些内容对它来说是可见的。现在当他们沿着版本链扫描是，如果识别出任何对其他事务不可见的版本。就可以对其进行修剪。

即使扫描速度便慢，但是不需要单独的后台线程。这种方法有效，但是仍然需要定期启动清理过程。因为如果更新了一条记录，创建了新版本，使之前版本失效，并且之后再也没有人读取，那么就永远无法回收该空间。sql server会因此产生一些脏数据，需要定期启动后台线程进行清理。

transaction-level GC：同样需要跟踪事务，以及它们修改过的内容。例如更新A1、A2，创建A3，然后保留这些旧版本。可以是记录ID，或者指针，用于指示哪些内容已失效。事务提交时，获得一个提交时间戳，将次信息传递给vacuum进程，让其进行清理。这个方法很罕见，大部分系统都采用后台清理机制。

不过如果你正在进行差量存储就容易了，因为不用扫描整张表了。只需要扫描差量记录即可。

索引管理

逐渐容易管理，无论使用什么方案，主键总是指向版本头，如果更新了主键本身，就把这个操作当做删除后插入来处理。因为从理论上，它就是一个新的元组。

但是二级索引比较麻烦，因为二级索引的指向会影响处理方式。还需要考虑版本排序，比如从新到旧，或者从旧到新。这样一来更新记录，创建新版本是，可能需要更新所有的索引，让它们指向新版本。

那么如果有二级索引，二级索引指向什么呢？一种方法是逻辑指针，它本质上是一个逻辑标识符，帮助你找到版本链头部的实际物理地址。最简单的事情就是存储主键，mysql就是这样干的，通过二级索引会先找到主键，然后通过主键查询位置。另一种方法是使用元组标识符，可以把它看做是一个合成ID。Pgsql存储的是物理版本，也就是指向版本链同步的物理指针。

当查找主键索引，拿到对象A的时候，会得到一个记录ID。这是页码和槽号，就能准确找到想要的地方，也就是版本链的头部。如果进行二级查找，会得到这个版本链的头部，或者类似这样的记录ID。

而且在OLTP数据库中，通常会有大量索引，尤其是二级索引。这些所有索引都会指向版本链的头部。因此如果我现在更新元组，即使没有更新二级索引依赖的属性，由于版本链的头部会苏子和新的物理地址二改变，我们仍然需要更新所有这些二级索引。pgsql的做法是，实际上在每个版本中都会在索引中拥有另一个条目。如果新版本和旧版本位于一个页面，由于是仅追加的，创建一个新版本，那么就不需要更新索引。因此如果新版本在同一个页面中，pgsql实际上不会更新二级索引。

这是最常见的例外情况，能显著减少索引维护开销。

如果同时满足这两个条件，就会触发 HOT（堆内元组）更新：

• 更新的列不是任何索引的组成部分。
• 索引所在页上有足够空间存放新版本的行。

此时，PostgreSQL 会完全跳过对索引的维护。它只在数据页内操作，并依赖一种指针链，让查询能通过旧索引条目找到新行。

索引中，多版本信息总是保存在元数据本身中。大多数系统不会讲这些信息作为索引键的一部分存储。PGsql是例外，会存储一些版本信息，这样就不需要实际遍历版本链。

如果版本链分布在多个页面上，原本只需要单页查找就能找到一个元组，现在却可能变成一个全表扫描。这将会影响性能。