关系型数据库是怎么工作的？

英文原文链接：How does a relational database work

谈到关系型数据库，总感觉缺了些什么。它们应用广泛，种类繁多，有小而精的SQLite，也有强大的Reradata（天睿公司，又是一家起源于车库的巨头）。但是解释数据库工作的文章却比较少，而且大都比较短。

image-20211025111347330

如果你对数据库感兴趣，但是又不想花费时间深入广泛地挖掘这个领域的话，那么你应该会喜欢这篇文章。

虽然这篇文章的标题很明显，并不是要讲数据库的用法，但是你应该会一些基础的增删改查和join查询，否则你就应该收藏本篇文章，然后去简单学习一下SQL的使用。

我们首先从基础谈起，如复杂度，这部分比较枯燥，可对理解数据库的精妙之所在十分有帮助。在这里我们以SQL的查询为例。我只会展示数据库背后的基础概念，所以看完这篇文章后你能对数据库全局有直观的认识。

文章分为三个部分：

  • 底层和上层数据库组件
  • 查询优化过程
  • 事务和缓冲池管理

从基础谈起

很久很久以前，程序员很明确的知道他们代码的计算量，因为以前CPU和内存都比较金贵，一丝一毫都不能浪费。时至今日，我们也应该大致知道我们代码的复杂度，毕竟，复杂度指数上升的话再多CPU也不够。

O(1) vs O(N^2)

时间复杂度是用来查看：对于给定数目的数据，程序会计算多长时间。为了描述这个复杂程度，科学家们给出了大O的概念。对于大O，我们不关注给定数据的数目，也不关心精确的计算量，而是关注复杂度上升的方式。

image-20211025114448147

在这张图中，我们可以看到不同类型的复杂度。为了方便对比时间复杂度，这里x轴使用对数尺度。可以看到：

  • O(1)是常数复杂度，不随输入数据量改变。
  • O(log(n))即使对于上亿的数据也保持低计算量
  • 最差的是O(n^2)，计算次数上升非常迅速。

为了更直观地理解，举几个例子：

  • 在一个好的哈希表中查找元素，复杂度为O(1)
  • 在一个好的平衡树中查找元素，复杂度为O(log(n))
  • 在数组中查找元素，复杂度O(n)
  • 最好的排序算法，复杂度O(n * log(n))
  • 差的排序算法，如冒泡排序，复杂度为O(n^2)

在衡量时间复杂度时，一般选用最差情况来分析。除了时间复杂度，还有空间复杂度，磁盘IO复杂度。同样，除了上面列举的大O，还要其他的如O(n^4)，O(2^n)等

归并排序

当你需要用到排序的时候，你会怎么做？调用sort()函数。。。好吧，通常情况确实可以。但是对于数据库来说，你需要知道sort()函数到底是怎么工作的。

有很多种不错的排序算法，这里关注归并排序。这里你可能还不太理解为啥需要排序，在查询优化一节后你就明白了。而且，归并排序能帮助我们理解数据库的merge join操作。

归并

将两个N/2的数组合并成一个N元素的数组。

image-20211025124045002

在上图中可以看到，为了构建排序好的8元素数组，你需要在两个4元素数组中迭代，又因为两个4元素数组都是排好序的，所以只需在两个4元素数组的头部各放一个指针，比较得到小的元素放到8元素数组，然后指针后移，继续比较。

Java代码如下：

public static <T extends Comparable<T>> T[] mergeSort(T[] array) {
    if (array.length <= 1) {
        return array;
    }
    int half = array.length / 2;
    T[] left = Arrays.copyOfRange(array, 0, half);
    T[] right = Arrays.copyOfRange(array, half, array.length);
    return merge(mergeSort(left), mergeSort(right));
}

private static <T extends Comparable<T>> T[] merge(T[] left, T[] right) {
    int lindex = 0;
    int rindex = 0;
    int index = 0;
    // 实际不应频繁创建临时数组
    // 这里是为了和上图对应
    T[] ret = (T[]) new Comparable[left.length + right.length];
    while (lindex < left.length && rindex < right.length) {
        if (left[lindex].compareTo(right[rindex]) < 0) {
            ret[index++] = left[lindex++];
        } else {
            ret[index++] = right[rindex++];
        }
    }
    while (lindex < left.length) {
        ret[index++] = left[lindex++];
    }
    while (rindex < right.length) {
        ret[index++] = right[rindex++];
    }
    return ret;
}

测试如下：

public static void main(String[] args) {
    Integer[] arr = {3, 6, 8, 7, 6, 9, 1, 8, 2, 4, 10, 0, 3};
    System.out.println(Arrays.toString(MergeSort.mergeSort(arr)));
    // output: [0, 1, 2, 3, 3, 4, 6, 6, 7, 8, 8, 9, 10]
}

归并排序将问题分割成了更小的问题，解决完小问题之后再组合会原来的问题。

分割阶段

image-20211025150512152

在分割阶段，一个8元素的数组通过3步分割成了最小单元，分割次数为log(N), N=8。

排序阶段

image-20211025150647608

排序阶段会从单元素数组开始，通过多次合并，得到了一个排好序的数组。不管是4*2，还是2*4或者1*8，每一步都需要比较N次，又需要log(N)步，所以一共需要N*log(N)步操作。

归并排序的威力

为什么归并排序如此牛逼？因为它可以在基础版本上进行优化：

  • 为了缩减内存占用，可以使用原地排序
  • 可以在没有巨大IO惩罚的情况下缩减使用的内存（内存里只放正在处理的部分），这样就可以在2G内存上排序10G的数据。
  • 可以改造成多线程或者多服务器版本

数组、树、哈希表

现在我们理解了时间复杂度和排序的概念，接下来会列举三种数据结构，它们是现代数据库的基石，我同样也会介绍数据库index的概念。

数组

二维数组是最简单的数据结构，一张表可以视为一个数组，如：

image-20211025155132051

这个二维数组是一张包含了行和列的表，每一行是一个对象，每一列是描述对象的一个特征，同时，每一列存储特定的数据类型，如integer或者string、date...

用它存储或者可视化数据还不错，当你用它来查找数据时就拉倒了。

例如上表中，你想查找所有在UK工作的人，你必须一行一行遍历，时间复杂度为N(N为行)，倒也不是过于垃圾，但是有更快的方法为何不用呢？这就轮到树出场了。

树和数据库index

树的知识可以看我以前的这篇文章：数据结构-树

这里用到的树为排序树，如二叉搜索树：右子树的结点比当前结点大，左子树的结点比当前结点小。如：

image-20211025160314339

这棵树有 N=15 个元素，我要找208应该怎么找？

先从根结点136找，208比136大，找136的右子树398，208比398小，找398的左子树250，208比250小，找250的左子树200，不等，也没子树，所以208不存在。

image-20211025160550185

其他同理，找到为止，找不到就是不存在。

查找的代价呢？O(log(N))。

image-20211025162902630

现在回到我们的问题，我们用字符串来指代某人所属的国家。假定有一个树，结点为国家（string类型，可比较）。如果想查找UK的人，只需查找结点，找到UK结点，在UK结点中，就可以在UK结点中找到UK的人。

在这里，时间复杂度为O(log(N))，同时，以上就是数据库index的思想。

只要你能比较这些列，你可以为列的任意组合创建index。

尽管二叉搜索树在查找上性能不错，但是当你想要得到两个值之间的元素时存在一个大问题。它的时间复杂度为O(N)，因为你需要查看所有结点去检查结点所属的区间，如用中序遍历。并且，它磁盘IO开销较大，因为需要读取整个树。我们需要一个更高效率的办法去进行区间查询，现代数据库用搜索树的改进版B+树来解决这个问题。在B+树中：

只有叶子结点存储信息（数据行在表中的位置），其他索引只是用来在查询时导航找到正确的结点。

image-20211025170616142

可以看到，结点数多了一倍，决策结点会帮助你找到需要的结点。但是时间复杂度依旧是O(log(N))。区别在于，叶子结点是连起来的。用这个B+树，如要查找区间40到100的结点，只需要找到40，找到100,，就可以了，不需要查找整个树。

image-20211025171051278

但是这里面又有新的问题，如果要在数据库中增加或者删除数据（B+树里也要变动）：必须要维护B+树中结点的顺序，同时需要保证B+树的层数最小。换句话说，B+树需要是自排序、自平衡的。幸运的是可以做到，不幸的是插入和删除都伴随着O(log(N))的代价。这也就是为什么会出现不要有太多索引这个说法的原因，插入数据库不只是插入数据库，所有的索引都需要更新。更有甚者，增加索引会增加事务管理的负担（后文会谈到）。

哈希表

哈希表可以利用键值快速查找元素，建立一个哈希表需要定义：元素的键、哈希函数、键的比较函数（用于在一个桶中快速查找需要的元素）。

一个简单的例子如下：

image-20211025172134020

这个哈希表含有10个桶，哈希函数是对10取模，也就是元素按个位数放入桶中。桶中的元素暂时按列表排序。

如要找209，就找9的桶，依次遍历，比较。

为了使不同的桶里放入的元素个数不要差异太大，就需要寻找合适的哈希函数。尤其是对一些复杂的键，如字符串，字符串和时间...在哈希函数足够理想情况下，查找复杂度为O(1)。

为什么用哈希表不用数组？

  • 哈希表可以加载需要的桶到内存中，其他的待在硬盘上。
  • 数组需要连续内存，大数组的情况下不好找大的连续内存。
  • 哈希表可以选择想要的键。

全局视角

我们已经看过了数据库内部的基础组件，现在我们需要从全局角度看一看。

image-20211025181557757

数据库是信息的集合，这些信息可以被访问，也可以被修改。如果仅仅这样的话，使用一些文件同样能达到这个目的。像SQLite就是一堆文件的集合，但是是一堆十分巧妙的文件的集合，从而能够：

  • 使用事务保证数据的安全性和一致性
  • 面对大量数据也能快速处理

更通俗的讲，数据库可以视为：

image-20211025182428759

核心组件：

  • Process manager：进程管理器，许多数据库都有进程池或者线程池需要管理。有一些数据库还会为了更高的效率使用自己的线程而不是系统的线程
  • Network manager: 网络管理器，网络IO是一个大问题，尤其是对分布式数据库
  • File system manager: 文件系统管理器，磁盘IO是操作系统的第一个瓶颈
  • Memory manager: 内存管理器，为了防止磁盘惩罚，需要大量内存，为此需要一个内存管理器，尤其是同一时间有很多查询的情况
  • Security manager：安全管理器，验证用户权限
  • Client manager：管理用户连接

工具：

  • Backup manager：备份管理器，用于保存和恢复数据库
  • Recovery manager：恢复管理器，用于数据库崩溃后重启的一致性状态检查
  • Monitor manager：监视管理器，记录数据库活动，提供监视数据库的工具
  • Administration manager：存储元数据（如表名，表结构）和提供数据库管理的工具

查询管理器：

  • Query parser: 检查查询是否有效
  • Query rewriter: 预优化查询，垃圾代码 -> 还可以的代码
  • Query optimizer: 优化查询，还可以代码 -> 高效代码
  • Query executor: 编译和执行查询语句

数据管理器：

事务管理器用于管理事务，缓存管理器用于数据在内存和硬盘之间的读取存放，数据获取管理器用于从磁盘获取数据。

接下来，我们重点关注数据库如何管理SQL查询。

用户管理器

image-20211025183952993

用户管理器用于管理用户连接，这个用户可以是web服务器，也可以是终端的用户或者应用。用户管理器通过一系列API提供了不同的方法去连接数据库，如：JDBC, ODBC... 同时也提供了专用连接API。

当你连接数据库时：

  • 管理器首先检查用户信息（用户名和密码），再检查是否有权限用这个数据库。
  • 然后，检查是否有可用进程或线程去管理你的查询。
  • 同时也会检查数据库是否在高负载。
  • 为了获取需要的资源，等待片刻，如果超时了，就关闭连接，返回错误信息。
  • 之后它将你的查询发送给查询管理器，你的查询就会被处理了。
  • 因为查询的过程会逐渐获得数据，所以它会放入缓存中，并且开始发送给你。
  • 有问题情况下，会停止连接，发送给你原因并且释放资源。

查询管理器

image-20211025185337086

这一部分是数据库的强大所在。在这个环节，一个写的不咋滴的查询语句会被转化成一个高效的查询语句，然后执行，将结果返回给用户管理器。过程如下：

  • 解析查询语句看是否有效
  • 优化查询语句
  • 进一步优化为高性能代码
  • 编译
  • 执行

回顾下查询管理器：

  • Query parser: 检查查询是否有效
  • Query rewriter: 预优化查询，垃圾代码 -> 还可以的代码
  • Query optimizer: 优化查询，还可以代码 -> 高效代码
  • Query executor: 编译和执行查询语句

解析

任意一个SQL语句在经过格式验证之后，都会发送给解析器。如果你写错了代码，如将SELECT写成了SEELECT，就拉倒了。之后，会进一步检查关键词的顺序，如WHERE之前没有SELECT。然后会分析查询中的表和字段，解析器用数据库的元数据来检查：表是否存在、表的字段是否存在、操作对于这个字段来说是不是离谱（如比较整数和字符串）。

元数据检查无误后，会验证用户权限，是否可以读或写这张表。

在解析过程中，SQL查询会被转化成内部形式，通常是树的形式，如果一切ok，就发送给Query rewriter。

重写器

三个目的：预优化语句、防止不必要的操作、帮助下一步的优化器找到更好的解决方案。

重写器对查询执行一系列规则，如果匹配就按规则重写，例如：

  • 去除不必要的操作，如果一个UNIQUE约束用DISTINCT

  • 重复join删除

  • 常数转化，如10+2会被转化为12

  • view merging: 如果你在查询语句中使用了view，这个view就会被转化为对应的SQL代码。

  • subquery flattening：子查询难以优化，所以重写器会试着修改查询。

  • 等等

举例：

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%';

统计学特征

在说数据库优化查询语句之前，需要谈一下统计学特征。如果你不告诉数据库需要分析它自己的数据，它就不会分析，然后可能做出一些十分不明智的假设。

但是数据库需要什么样的信息呢？

数据库和操作系统都以页或者块来作为存储的最小单元。当你让数据库收集统计学信息时，它会计算：表的行数、每一列不同的数据值、每一列的数据长度（最大、最小、平均），每一列数据分布信息、表的索引信息。

这些统计学特征会帮助优化器估计查询过程中的磁盘IO，CPU和内存使用。

如对一个表PERSON，它需要根据LAST_NAME和FIRST_NAME执行join操作，根据统计学特征，FIRST_NAME有1000个不同的值，而LAST_NAME有1000000个不同的值。那么数据库执行join就应该基于LAST_NAME, FIRST_NAME 而不是FIRST_NAME, LAST_NAME。因为FIRST_NAME很有可能会再次进行比较。

这些是基础的统计学特征，你还可以让数据库计算高级统计学特征，如直方图可以看出数据的分布情况。这样数据库在查询的时候就进行更加有效的优化。

统计学特征必须要最新。 不然数据库以为有十条数据，实际上有十万条，这就乱套了。这就又带来了额外的计算量，这也是大多数数据库不自动开启它的原因。对于上百万的数据，计算也需要一段时间，这种情况可以选择计算基本的统计学特征。

优化器

所有的数据库都在用Cost Based Optimization，基于代价的优化去优化查询，简称CBO。它的思想就是给每个操作赋予一个代价值，然后去寻找最好的方法取降低查询的代价。

为了更好的理解CBO的工作，这里以join为例，我们接下来关注时间复杂度，但是数据库优化器会计算CPU 代价、磁盘IO和需要的内存。大多数时候，磁盘IO才是性能瓶颈。

索引：

在前面B+树已经谈过索引了，它是有序的。有些时候，现代数据库会动态地为当前的查询创建临时索引，去优化执行查询的代价。

数据获取：

在join之前，首先需要获取数据。

  • full scan：扫描整张表

  • range scan：如index range scan。在语句WHERE AGE > 20 AND AGE <40中，如果对AGE已经建立了索引，就可以以得到时间复杂度O(log(N)+M)，其中，N是索引的数目，M是这个范围内的行数，二者都可以通过统计学特征得到。

  • unique scan：从一个索引中获取一个值

  • access by row id：很过时候，数据库用索引，之后还需要查找对应的行号，如：

    SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28

    如果PERSON表中有索引age，优化器会用索引找到所有28岁的人，然后从表中查找对应的行，得到需要的信息。

    但是如果你用下面的语句：

    SELECT TYPE_PERSON.CATEGORY from PERSON, TYPE_PERSON
WHERE PERSON.AGE = TYPE_PERSON.AGE

    PERSION表中的索引就会用来和TYPE_PERSON做join，后续也不会查找PERSON表的行号，因为你没要PERSON表的数据。

    access by row id的问题还是在磁盘IO，如果你需要太多行的数据，数据库可能宁愿做一个full scan。

  • 其它

join操作

join之前，需要介绍两个术语：inner relation和outer relation。关联可以是表、索引，也可以是操作的中间量。

当你join这两种关联的时候，join算法会区别对待。接下来假设：outer relation是左边的数据集，inner relation是右边的数据集。

如：A JOIN B 是A和B的join，B是inner relation，A是outer relation。

大多数时候，A JOIN B 和 B JOIN A的代价是不一样的。

我们假设outer relaion有N个元素，inner relation有M个元素。

  • 循环嵌套join

    image-20211025212111788

    全连接，左边所有和右边所有都有连接，时间复杂度O(N*M)。

    在磁盘IO的角度，outer relation的N行中的每一行，都需要读M行inner relation数据，也就是需要从磁盘读取N+N*M行数据。但是如果inner realtion很小，你就可以把它们都放入内存，只需读N+M次。

    如果inner relation太大不能放入内存的话，有另一个版本：分块读，而不是一行行读，这样也能减小磁盘IO。

  • 哈希join

    image-20211025213306312

    将inner realtion中的元素存入哈希表，遍历outer relation，计算哈希来找到对应inner relation的桶，在桶中查找是否有对应的元素。

    为了计算时间复杂度需要作出一些假设：inner realtion被分为X个桶，哈希函数将哈希值均匀分布，桶里面元素个数一样。

    时间复杂度就是：（M/X)*N+建立哈希表时间+N*哈希函数时间。如果桶里面元素足够小，那么时间复杂度就是O(M+N)。

  • merge join

    先将关联表的关联列格子做排序，然后从各自的排序表中抽取数据，到另一个排序表中做匹配。

    image-20211025220944318

    思想就是找到排序后相等的元素。由于牵扯到排序，所以时间复杂度为O(Nlog(N)+Mlog(M))，如果已经排好序，O(N+M)。

哪个最好？正如没有最好的编程语言，也没有最好的join方法，否则别的存在都没有了意义应针对具体情况分析，如关系已经排好序，就选merge join。

示例：

假设为了得到一个人的信息，需要join五张表，一个人可以拥有多个手机、多个邮件、地址、银行账户。

也就是如下的查询：

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

查询优化器需要找到最好的join方式，选哪个？用什么顺序连接？如：

image-20211025221825792

动态规划、贪心算法：

很多时候，优化器不需要找到最好的，只需要找到足够好的。因为要找到最好的方案可能时间代价更大。前提：根据统计学特征我们能大致推算复杂度。

动态规划：

许多执行过程都是相似的，如：

image-20211025222456967

这几种方案都有相同的A JOIN B子树，所以这种可以只计算一次，然后重复利用。效率好了些，但还是指数级别。

贪心算法：

如5张表（ABCDE），4个join的查询。从任一一个表开始，如A，计算每个表和Ajoin的代价，选择最小的，如B，之后再选择（A join B）join ? 的最小代价。。。这样的复杂度就可以接受了，这个解决方案的假设是：两个表join之后继续join另一个表仍是这三个表的最佳join方式。

执行器

现在我们已经有了一个plan，可以被编译为代码。如果CPU和内存够的情况下，它就会被执行，里面的操作可以被序列化执行或者并行执行，这取决于执行器。为了获取和写入数据，执行器需要和数据管理器交互。

数据管理器

image-20211025224203424

在这一步，查询管理器正在执行查询，并需要来自表和索引的数据。它请求数据管理器获取数据，但这里存在2个问题：

  • 关系数据库使用事务模型。因此你可能无法获取想要的数据，因为其他人可能在使用甚至修改数据。
  • 数据检索是数据库中最慢的操作，因此数据管理器需要巧妙的策略在内存缓冲区中获取和保存数据。

缓存管理器

数据库的主要瓶颈是磁盘 IO。为了提高性能，现代数据库使用缓存管理器，来减少和磁盘的交互。

image-20211025224611719

查询执行器并不是直接从文件系统获取数据，而是向缓存管理器请求数据。缓存管理器有一个名为buffer pool的内存缓存。从内存中获取数据大大加快了数据库的运行速度。

同样有一个问题，缓存管理器需要在查询执行器需要数据之前读取到内存中，否则查询管理器就必须等待磁盘。

预取：

查询执行器知道它需要的数据，因为它知道查询的完整流程并且知道磁盘上的数据和统计信息。可以采取的一个思路就是：

  • 当查询执行器正在处理它的第一组数据时
  • 它要求缓存管理器预加载第二组数据
  • 当它开始处理第二组数据时
  • 要求缓存管理器加载第三组数据，并且清除第一组数组

如果查询执行器不知道下面要处理什么数据，可以使用猜的方式，例如查询执行器要数据1, 3, 5，那下面很有可能要7, 9, 11, 或者简单地从磁盘加载下一个连续数据。

缓存的一些东西可以看这篇文章帮助理解：操作系统交换空间机制和策略

事务管理器

在一个事务中，你可以运行多个SQL进行各种操作。

ACID

事务的四个属性：ACID。

  • 原子性Atomicity：事务中的操作要么一点没干，要么全干完了。

  • 一致性Consistency：只有有效数据能进入数据库。

  • 隔离性Isolation：事务同时运行，必须互不影响。

  • 持久性Durability：事务执行完之后，数据应该稳妥妥的进入数据库。

当两个事务使用相同的数据时，局面就有些混乱了。如：

  • 事务1：从A账户拿100块给B
  • 事务2：从A账户拿50块给B

就需要并发控制了。

并发控制

为了解决上面的问题，需要并发控制，可以看锁的实现和并发数据结构、条件变量、信号量和事件并发。

日志管理器

为了提高性能，数据库将数据存储在内存缓冲区中。但是如果在提交事务时服务器崩溃，那么在崩溃期间你将丢失仍在内存中的数据，这会破坏事务的持久性。

你可以将所有内容写入磁盘，但是如果服务器崩溃，你最终会将一半的数据写入磁盘，这会破坏事务的原子性。

可以看这篇文章：文件系统和崩溃一致性

总结

翻译翻译着就发现好多东西都是看过的，只是对数据库运行机制没了解，知识点没串起来。后面的东西像是并发控制和崩溃一致性中的日志系统，本来也就是要增加对数据库运行机制的直观认识，就直接贴博客了。