关系型数据库是如何工作的

约 7123 字大约 24 分钟

2025-10-02

全局概览

数据库一般可以用如下图形来理解:

核心组件

进程管理器（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 manager）：用于保存元数据（比如表的名称和结构），提供管理数据库、模式、表空间的工具。
...

数据管理器

事务管理器（Transaction manager）：用于处理事务
缓存管理器（Cache manager）：数据被使用之前置于内存，或者数据写入磁盘之前置于内存
数据访问管理器（Data access manager）：访问磁盘中的数据

查询管理器

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

数据查询的流程

本章集中探讨数据库如何通过如下进程管理SQL查询的：

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

客户端管理器

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

当你连接到数据库时：

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

查询管理器

这部分是数据库的威力所在，在这部分里，一个写的糟糕的查询可以转换成一个快速执行的代码，代码执行的结果被送到客户端管理器

操作过程如下：

用户的查询语句首先被解析并判断是否合法
然后用户的查询语句被重写，去除了无用的操作并加入预优化部分
接着被优化以便提升性能，并被转换为可执行代码和数据访问计划
然后计划被编译
最后被执行

这里我不会过多探讨最后两步，因为它们不太重要。

查询解析器

每一条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 函数……都会发生转换（但我不确定这是由重写器还是优化器来完成，因为两个进程联系很紧，必须看是什么数据库）。

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

统计

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

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

我必须（简要地）谈谈数据库和操作系统如何保存数据。两者使用的最小单位叫做页或块（默认 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 个字符就够了，这将大大减少比较的次数。

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

出现最频繁的值
分位数(quantiles)
…

这些额外的统计会帮助数据库找到更佳的查询计划，尤其是对于等式谓词（例如： 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 使用。

存取路径

在应用联接运算符（join operators）之前，你首先需要获得数据。以下就是获得数据的方法。

注：由于所有存取路径的真正问题是磁盘 I/O，我不会过多探讨时间复杂度。

全扫描
简单的说全扫描就是数据库完整的读一个表或索引。就磁盘 I/O 而言，很明显全表扫描的成本比索引全扫描要高昂。
范围扫描
其他类型的扫描有索引范围扫描，比如当你使用谓词 ” WHERE AGE > 20 AND AGE < 40 ” 的时候它就会发生。
当然，你需要在 AGE 字段上有索引才能用到索引范围扫描。
范围扫描时，你不需要读取整个索引，因此在磁盘 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）这里的关系可以是：

一个表
一个索引
上一个运算的中间结果（比如上一个联接运算的结果）

当你联接两个关系时，联接算法对两个关系的处理是不同的。在本文剩余部分，我将假定：

外关系是左侧数据集
内关系是右侧数据集

比如， A JOIN B 是 A 和 B 的联接，这里 A 是外关系，B 是内关系。

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

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

注：N 和 M 是关系的基数。

嵌套循环联接

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

原因如下：

针对外关系的每一行，查看内关系里的所有行来寻找匹配的行

下面是伪代码：

def nested_loop_join(outer, inner):
    for a in outer:
        for b in inner:
            if match_join_condition(a, b):
                write_result_in_output(a, b)

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

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

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

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

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

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

可能的算法如下：

# 改进版本以减少磁盘 I/O
def nested_loop_join_v2(outer_file, inner_file):
    for ba in outer_file:  # ba 现在在内存中
        for bb in inner_file:  # bb 现在在内存中
            for a in ba:
                for b in bb:
                    if match_join_condition(a, b):
                        write_result_in_output(a, b)

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

用前一个版本，算法需要 N + N*M 次访问（每次访问读取一行）。
用新版本，磁盘访问变为外关系的数据簇数量 + 外关系的数据簇数量 * 内关系的数据簇数量。
增加数据簇的尺寸，可以降低磁盘访问

哈希联接

哈希联接更复杂，不过在很多场合比嵌套循环联接成本低。

哈希联接的原理是：

读取内关系的所有元素
在内存里建一个哈希表
逐条读取外关系的所有元素 +（用哈希表的哈希函数）计算每个元素的哈希值，来查找内关系里相关的哈希桶内
是否与外关系的元素匹配。

在时间复杂度方面我需要做些假设来简化问题：

内关系被划分成 X 个哈希桶
哈希函数几乎均匀地分布每个关系内数据的哈希值，就是说哈希桶大小一致。
外关系的元素与哈希桶内的所有元素的匹配，成本是哈希桶内元素的数量。

时间复杂度是 (M/X) * N + 创建哈希表的成本(M) + 哈希函数的成本 * N 。如果哈希函数创建了足够小规模的哈希桶，那么复杂度就是 O(M+N)。

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

计算内关系和外关系双方的哈希表
保存哈希表到磁盘
然后逐个哈希桶比较（其中一个读入内存，另一个逐行读取）。

合并联接

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

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

1.（可选）排序联接运算：两个输入源都按照联接关键字排序。
2.合并联接运算：排序后的输入源合并到一起。
排序

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

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

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

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

在两个关系中，比较当前元素（当前=头一次出现的第一个）
如果相同，就把两个元素都放入结果，再比较两个关系里的下一个元素
如果不同，就去带有最小元素的关系里找下一个元素（因为下一个元素可能会匹配）
重复 1、2、3步骤直到其中一个关系的最后一个元素。

因为两个关系都是已排序的，你不需要『回头去找』，所以这个方法是有效的。

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

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

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

哪个算法最好

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

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