【DB SQL】 工作原理

Metadata

title: 【DB SQL】 工作原理
date: 2022-12-20 15:06
tags:
  - 行动阶段/完成
  - 主题场景/数据存储
  - 笔记空间/KnowladgeSpace/ProgramSpace/BasicsSpace
  - 细化主题/数据存储/DB_SQL
categories:
  - 数据存储
keywords:
  - 数据存储
description: 【DB SQL】 工作原理

知识点

数据结构及算法

归并排序

归并排序是把问题拆分为小问题，通过解决小问题来解决最初的问题（注：这种算法叫分治法，即『分而治之、各个击破』）。

为什么是归并排序？

  • 你可以更改算法，以便于节省内存空间，方法是不创建新的序列而是直接修改输入序列。注：这种算法叫『原地算法』(in-place algorithm)
  • 你可以更改算法，以便于同时使用磁盘空间和少量内存而避免巨量磁盘 I/O。方法是只向内存中加载当前处理的部分。在仅仅100MB的内存缓冲区内排序一个几个GB的表时，这是个很重要的技巧。注：这种算法叫『外部排序』(external sorting)。
  • 你可以更改算法，以便于在 多处理器/多线程/多服务器 上运行。比如，分布式合并排序是Hadoop（那个著名的大数据框架）的关键组件之一。

二叉搜索树

数据库中查询的时间复杂度，是我们无法使用矩阵，转而使用二叉搜索树(BST)，具体请参考： 树 - 二叉搜索树(BST)

  • 二叉搜索树只需 log(N) 次运算，而如果你直接使用阵列则需要 N 次运算

B+树索引

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

如果你在数据库中增加或删除一行

  • 你必须在B+树中的节点之间保持顺序，否则节点会变得一团糟，你无法从中找到想要的节点。
  • 你必须尽可能降低B+树的层数，否则 O(log(N)) 复杂度会变成 O(N)。

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

哈希表

为什么不用阵列呢？

  • 如果有了好的哈希函数，在哈希表里搜索的时间复杂度是 O(1)。
  • 一个哈希表可以只装载一半到内存，剩下的哈希桶可以留在硬盘上。
  • 用阵列的话，你需要一个连续内存空间。如果你加载一个大表，很难分配足够的连续内存空间。

全局概览

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

核心组件

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

查询管理器

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

数据管理器

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

数据查询的流程

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

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

客户端管理器

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

当你连接到数据库时：

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

查询管理器

这个多步骤操作过程如下：

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

查询解析器

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

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

  • 表是否存在
  • 表的字段是否存在
  • 对某类型字段的 运算 是否 可能（比如，你不能将整数和字符串进行比较，你不能对一个整数使用 substring() 函数）
    接着，解析器检查在查询中你是否有权限来读取（或写入）表。再强调一次：这些权限由DBA分配。
    在解析过程中，SQL 查询被转换为内部表示（通常是一个树）。
    如果一切正常，内部表示被送到查询重写器。

查询重写器

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

  • 预优化查询
  • 避免不必要的运算
  • 帮助优化器找到合理的最佳解决方案
    重写器按照一系列已知的规则对查询执行检测。如果查询匹配一种模式的规则，查询就会按照这条规则来重写。下面是（可选）规则的非详尽的列表：
  • 视图合并：如果你在查询中使用视图，视图就会转换为它的 SQL 代码。
  • 子查询扁平化：子查询是很难优化的，因此重写器会尝试移除子查询
  • 去除不必要的运算符：比如，如果你用了 DISTINCT，而其实你有 UNIQUE 约束（这本身就防止了数据出现重复），那么 DISTINCT 关键字就被去掉了。
  • 排除冗余的联接：如果相同的 JOIN 条件出现两次，比如隐藏在视图中的 JOIN 条件，或者由于传递性产生的无用 JOIN，都会被消除。
  • 常数计算赋值：如果你的查询需要计算，那么在重写过程中计算会执行一次。比如 WHERE AGE > 10+2 会转换为 WHERE AGE > 12 ， TODATE(“日期字符串”) 会转换为 datetime 格式的日期值。
  • （高级）分区裁剪（Partition Pruning）：如果你用了分区表，重写器能够找到需要使用的分区。
  • （高级）物化视图重写（Materialized view rewrite）：如果你有个物化视图匹配查询谓词的一个子集，重写器将检查视图是否最新并修改查询，令查询使用物化视图而不是原始表。
  • （高级）自定义规则：如果你有自定义规则来修改查询（就像 Oracle policy），重写器就会执行这些规则。
  • （高级）OLAP转换：分析/加窗 函数，星形联接，ROLLUP 函数……都会发生转换（但我不确定这是由重写器还是优化器来完成，因为两个进程联系很紧，必须看是什么数据库）。

统计

  • 这些统计信息会帮助优化器估计查询所需的磁盘 I/O、CPU、和内存使用
  • 统计信息必须及时更新。

查询优化器

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

对于这些联接操作，我会专注于它们的时间复杂度，但是，数据库优化器计算的是它们的 CPU 成本、磁盘 I/O 成本、和内存需求。

大多数时候瓶颈在于磁盘 I/O 而不是 CPU 使用。

索引

存取路径

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

  • 全扫描
  • 范围扫描
  • 唯一扫描
  • 根据 ROW ID 存取
  • 其它路径

联接运算符

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 的成本是不同的。

嵌套循环联接

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

算法实现

  • 针对外关系的每一行，查看内关系里的所有行来寻找匹配的行
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 更加有利。原因如下：

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

哈希联接

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

哈希联接的原理是：

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

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

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

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

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

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

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

  1. （可选）排序联接运算：两个输入源都按照联接关键字排序。
  2. 合并联接运算：排序后的输入源合并到一起。
  • 排序
    • 如果表内部就是有序的，比如联接条件里一个索引组织表(index-organized table)
    • 如果关系是联接条件里的一个索引
    • 如果联接应用在一个查询中已经排序的中间结果
  • 合并联接

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

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

哪个算法最好

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

查询计划缓存

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

查询执行器

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

数据管理器

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

  • 关系型数据库使用事务模型，所以，当其他人在同一时刻使用或修改数据时，你无法得到这部分数据。
  • 数据提取是数据库中速度最慢的操作，所以数据管理器需要足够聪明地获得数据并保存在内存缓冲区内。

缓存管理器

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

查询执行器不会直接从文件系统拿数据，而是向缓存管理器要。缓存管理器有一个内存缓存区，叫做缓冲池，从内存读取数据显著地提升数据库性能。

预读

缓存管理器在缓冲池里保存所有的这些数据。为了确定一条数据是否有用，缓存管理器给缓存的数据添加了额外的信息（叫闩锁）。

缓冲区置换策略

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

写缓冲区

缓冲区保存的是页（最小的数据单位）而不是行（逻辑上/人类习惯的观察数据的方式）。

事务管理器

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

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

并发控制

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

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

这个问题叫并发控制。

锁管理器

多数数据库使用锁和/或数据版本控制。

日志管理器

数据库把数据保存在内存缓冲区内。但如果当事务提交时服务器崩溃，崩溃时还在内存里的数据会丢失，这破坏了事务的持久性。你可以把所有数据都写在磁盘上，但是如果服务器崩溃，最终数据可能只有部分写入磁盘，这破坏了事务的原子性。

事务作出的任何修改必须是或者撤销，或者完成。

  • 影子副本/页（Shadow copies/pages）
  • 事务日志（Transaction log）

WAL（预写式日志）

影子副本/页在运行较多事务的大型数据库时制造了大量磁盘开销，所以现代数据库使用事务日志。事务日志必须保存在稳定的存储上

多数数据库（至少是Oracle,SQL Server,DB2,PostgreSQL, MySQL 和SQLite) 使用预写日志协议（Write-Ahead Logging protocol ，WAL）来处理事务日志。WAL协议有 3 个规则：

  • 每个对数据库的修改都产生一条日志记录，在数据写入磁盘之前日志记录必须写入事务日志。
  • 日志记录必须按顺序写入；记录 A 发生在记录 B 之前，则 A 必须写在 B 之前。
  • 当一个事务提交时，在事务成功之前，提交顺序必须写入到事务日志。

ARIES

IBM 研究人员『发明』了WAL的增强版，叫 ARIES。ARIES 或多或少地在现代数据库中使用，逻辑未必相同，但AIRES背后的概念无处不在。ARIES 代表『数据库恢复原型算法』（Algorithms forRecovery andIsolationExploitingSemantics）。

这个技术要达到一个双重目标：

  • 写日志的同时保持良好性能
  • 快速和可靠的数据恢复

有多个原因让数据库不得不回滚事务：

  • 因为用户取消
  • 因为服务器或网络故障
  • 因为事务破坏了数据库完整性（比如一个列有唯一性约束而事务添加了重复值）
  • 因为死锁

日志

事务的每一个操作（增/删/改）产生一条日志，由如下内容组成：

  • LSN：一个唯一的日志序列号（Log Sequence Number）。LSN是按时间顺序分配的，这意味着如果操作 A 先于操作 B，log A 的 LSN 要比 log B 的 LSN 小。
  • TransID：产生操作的事务ID。
  • PageID：被修改的数据在磁盘上的位置。磁盘数据的最小单位是页，所以数据的位置就是它所处页的位置。
  • PrevLSN：同一个事务产生的上一条日志记录的链接。
  • UNDO：取消本次操作的方法。比如，如果操作是一次更新，UNDO将或者保存元素更新前的值/状态（物理UNDO），或者回到原来状态的反向操作（逻辑UNDO, 只使用逻辑UNDO，因为处理物理UNDO太过混乱了)。
  • REDO：重复本次操作的方法。 同样的，有 2 种方法：或者保存操作后的元素值/状态，或者保存操作本身以便重复。
  • …：（供您参考，一个 ARIES 日志还有 2 个字段：UndoNxtLSN 和 Type）。

日志缓冲区

为了防止写日志成为主要的瓶颈，数据库使用了日志缓冲区。

当查询执行器要求做一次修改：

  • 缓存管理器将修改存入自己的缓冲区；
  • 日志管理器将相关的日志存入自己的缓冲区；
  • 到了这一步，查询执行器认为操作完成了（因此可以请求做另一次修改）；
  • 接着（不久以后）日志管理器把日志写入事务日志，什么时候写日志由某算法来决定。
  • 接着（不久以后）缓存管理器把修改写入磁盘，什么时候写盘由某算法来决定。

当事务提交，意味着事务每一个操作的5个步骤都完成了。

STEAL 和 FORCE 策略

下面是这些策略对恢复的影响：

  • STEAL/NO-FORCE 需要 UNDO 和 REDO: 性能高，但是日志和恢复过程更复杂 (比如 ARIES)。多数数据库选择这个策略。 注：这是我从多个学术论文和教程里看到的，但并没有看到官方文档里显式说明这一点。
  • STEAL/ FORCE 只需要 UNDO.
  • NO-STEAL/NO-FORCE 只需要 REDO.
  • NO-STEAL/FORCE 什么也不需要: 性能最差，而且需要巨大的内存。

关于恢复

ARIES从崩溃中恢复有三个阶段：

  1. 分析阶段：恢复进程读取全部事务日志，来重建崩溃过程中所发生事情的时间线，决定哪个事务要回滚（所有未提交的事务都要回滚）、崩溃时哪些数据需要写盘。
  2. Redo阶段：这一关从分析中选中的一条日志记录开始，使用 REDO 来将数据库恢复到崩溃之前的状态。
    • 在REDO阶段，REDO日志按照时间顺序处理（使用LSN）。
    • 对每一条日志，恢复进程需要读取包含数据的磁盘页LSN。
    • 如果LSN（磁盘页）>= LSN（日志记录），说明数据已经在崩溃前写到磁盘（但是值已经被日志之后、崩溃之前的某个操作覆盖），所以不需要做什么。
    • 如果LSN（磁盘页）< LSN（日志记录），那么磁盘上的页将被更新。
    • 即使将被回滚的事务，REDO也是要做的，因为这样简化了恢复过程（但是我相信现代数据库不会这么做的）。
  3. Undo阶段：这一阶段回滚所有崩溃时未完成的事务。回滚从每个事务的最后一条日志开始，并且按照时间倒序处理UNDO日志（使用日志记录的PrevLSN）。

恢复过程中，事务日志必须留意恢复过程的操作，以便写入磁盘的数据与事务日志相一致。一个解决办法是移除被取消的事务产生的日志记录，但是这个太困难了。相反，ARIES在事务日志中记录补偿日志，来逻辑上删除被取消的事务的日志记录。

当事务被『手工』取消，或者被锁管理器取消（为了消除死锁），或仅仅因为网络故障而取消，那么分析阶段就不需要了。对于哪些需要 REDO 哪些需要 UNDO 的信息在 2 个内存表中：

  • 事务表（保存当前所有事务的状态）
  • 脏页表（保存哪些数据需要写入磁盘）

当新的事务产生时，这两个表由缓存管理器和事务管理器更新。因为是在内存中，当数据库崩溃时它们也被破坏掉了。

分析阶段的任务就是在崩溃之后，用事务日志中的信息重建上述的两个表。为了加快分析阶段，ARIES提出了一个概念：检查点（check point），就是不时地把事务表和脏页表的内容，还有此时最后一条LSN写入磁盘。那么在分析阶段当中，只需要分析这个LSN之后的日志即可。