跳到主要内容

CMU 15445

Storage Manager​

DBMS 底层是如何存储数据的？​

BusTub 中有基于内存的存储后端（可以设定读写延时）和基于文件系统的存储后端 DiskManager。DiskManager 支持 Page 粒度的读写，使用链表或字典组织页面（BusTub 中没有 Page 回收的逻辑，使用数组）。

Page Header 包含以下信息：

  1. Page Size
  2. Checksum（校验数据存储的正确性）
  3. DBMS Version
  4. Transaction Visibility（事务可见性）
  5. Compression Information

Page Data 部分的布局，通常采用 Slotted Pages 或 LSM，Slot 从页的 Data 区域的最前面往后存，Tuple 是从 Data 区域的最后面往前存，Tuple 之间可以是乱序的，Slot 的数据可以动态更新，简化了 Tuple 存储的方式。

BusTub 中没有使用 Direct I/O 的原因与影响？​

课上提到，大部分数据库管理系统使用 Direct I/O 绕过内核的 Page Cache，但 BusTub 的 DiskManager 并没有使用 Direct I/O，在维护自身缓冲池的同时，也使用了 Page Cache。

  • 原因：Direct I/O  要求  4K  对齐和文件系统支持，实现较繁琐。BusTub 目前没有考虑 Recovery，所以没有用到 fsync()。
  • 影响：应该不影响  Buffer Pool Manager，也不影响性能，取决于 Page Cache 容量。正确性上没有区别。有一些场景需要  Page Cache + Buffer Pool Manager，有一些场景  Direct I/O  更合适。如读无法  4K  对齐，其实用  Page Cache  也问题不大；还有一些  page compression  的场景，如果能让  Page Cache  缓存压缩后的  page，也可以省一点  I/O。正确性上，如果有  ARIES，正确性由  redo/undo log  保证；redo undo log  做了 fsync() 就没有正确性问题。

如果使用 O_DIRECT 选项，磁盘读写从文件系统层直接访问最底层的存储设备，不走操作系统层的 Page Cache。但除了文件数据本身，文件的元数据（如文件大小）也会影响数据完整性。Direct I/O 只对文件数据本身有效，元数据读写还是会经过内核缓存。因此即使使用了 O_DIRECT 选项，在写入后，还需要调用 fsync() 保证数据真正落到磁盘。

fsync 卡顿怎么处理？​

参考 PostgreSQL 9.6 平滑 fsync, write 原理浅析-阿里云开发者社区 一文，当数据库产生尖锐（堆积）的 I/O 需求时，就可能造成 fsync() 的卡顿。解决方式为：

  1. 定期检测 os dirty page 的占比，超过水位线则异步刷脏
  2. 对属于同一个存储块的脏页排序后再写入，降低离散 I/O

将数据刷入磁盘时宕机了怎么办？​

参考 基于 Redo Log 和 Undo Log 的 MySQL 崩溃恢复流程 - 知乎 一文，可以使用 Redo Log 和 Undo Log 以保证数据的持久化。MySQL 使用 2PC (two-phase commit protocol) 以保证 Redo Log 和 Binlog 在事务提交时的数据一致性。

  1. Redo Log 记录了此次事务「完成后」的数据状态，记录的是更新之「后」的值
  2. Undo Log 记录了此次事务「开始前」的数据状态，记录的是更新之「前」的值

Buffer Pool​

LRU-K 比 LRU 替换算法好在哪里？​

在 LRU-K 算法的论文中，列举了以下情况：

  • 内部事务 (Intra-Transaction)：事务进行更新时，先读取某页，再更新该页
  • 事务重试 (Transaction-Retry)：事务访问页后中止，重试时再次访问该页
  • 内部流程 (Intra-Process): 具有相同流程的事务接连访问某页，如连续更新 100 条记录
  • 巧合流程 (Inter-Process): 两个完全独立的事务刚好访问相同的页

前 3 个例子被称作关联访问 (correlated reference-pair type)，LRU 算法无法处理这些情况，无法避免因为周期性模式而淘汰了需要长时间保存在缓存中的数据；原始的 LRU-K 算法在保留前 K 次的访问情况的同时，会将关联访问缩点，从而提高缓存的命中率和性能表现。

在 BusTub 的测试中，为 Scan 线程和 Get 线程提供了不同的标签，可以用比较方便的方式区分关联访问和非关联访问。

LRU-K 替换算法中 K 的选择依据？​

一般取 K=2。对于稳定不变的访问规律，K 越大，cache 命中率越高；但访问规律变化较大时，K 越大则表明需要更加多的访问去适应新的规律，因此变化响应更差。

在 BusTub 的测试中，包含多个顺序访问的 Scan 线程，和基于 zipfian 分布访问页面的 Get 线程，K 的默认取值为 16，Frame 数量为 64。使用为读写操作上添加 1ms 延迟的内存存储后端，对 K 分别为 1、2、3、4、16 的情况进行 30 秒的测试，命中率结果如下：

Scan\K123416
区分0.0510.1430.1060.0840.050
不区分0.0550.1430.1060.0870.047

其中 K=1 的情况（LRU）和 K=16 的情况，命中率基本一致，约为 5%；K=2 时命中率最高，约为 14%；之后伴随着 K 的增加，逐渐趋近 LRU 的命中率。可能是测试场景问题，区分关联访问似乎并非带来明显受益。结合实验，K=2 确实是 LRU-K 替换算法的最佳选择。

LRU 的时间复杂度为 O(1)，LRU-K 的时间复杂度为 O(logN)，在 K=2 的 LRU-K 替换算法的基础上，后续业界还提出了一些时间复杂度为 O(1) 的 改进算法 ，如 2Q、LIRS 等。

如何实现无锁 Buffer Pool？​

无锁 Buffer Pool 的实现需要无锁数据结构的支持，在 Buffer Pool 中使用到的数据结构，一是提供从 Page ID 到 Frame ID 映射的哈希表，二是维护了替换策略信息的某种数据结构。

参考 A Lock-free Buffer for WattDB - Lume UFRGS 论文中给出的无锁 Buffer Pool 的实现，替换策略基于非阻塞版本的 GCLOCK 算法 (Nb-GCLOCK)，无锁哈希表基于 Libcds (Khizsinsky 2013) 的实现，使用 FIX-USE-UNFIX 协议以保证并发操作的一致性。

数据库为什么要用 Buffer Pool 而非 mmap 管理内存？​

Buffer Pool 可以针对应用程序的访问模式进行调整，如特殊的淘汰策略、预取优化、将脏页按顺序刷盘。参考 Are You Sure You Want to Use MMAP in Your Database Management System? ，mmap 由 OS 将文件的一部分映射到内存中，存在以下问题：

  • OS 可能在任何时候刷脏，从而破坏事务（解决方案：CoW / Shadow Paging）
  • 伴随着不确定的 I/O 开销（解决方案：OS hints）
  • 缺页中断导致的总线错误，增大程序中错误处理的难度
  • 不确定文件是何时读取的，难以校验文件的有效性
  • 难以性能优化

Buffer Pool 的优化方式？​

  1. 在 BusTub 中，我细化了 bpm 读写锁与 frame 的锁，实现并发 I/O，QPS 提升 25 倍。
  2. 优化 LRU-K 算法，借助 Perf 和火焰图工具，发现 LRU-K 中用于存储历史记录的 std:: list 结构开销较大，可以尝试改为 2Q 等更高效的算法。
  3. 关联访问缩点。对于顺序扫描类型的数据，可以不存入 Buffer Pool。
  4. 还有一些优化方式，如预取、共享扫描、Direct I/O 等。

B+Tree Index​

BusTub 中 B+Tree 的用途？​

Project 2 实现了不支持重复键和并发安全 Iterator 的 B+Tree，用于索引，支持创建最多 2 列的 Integer 类型索引。BusTub 中共有 3 种索引：

  • BPlusTreeIndex
  • LinearProbeHashTableIndex（线性探测法）
  • ExtendibleHashTableIndex（可拓展哈希）

在已经建立索引的表上排序、点查询、范围查询时，Query Optimizer 会将 SeqScan 优化为 IndexScan，从而使用到我们实现的 B+Tree。课程组保证了测试数据中不会出现重复键。

B+Tree 相比 B-Tree 的优劣？​

B+树和 B-树都是常用的数据结构，用于在磁盘或其他外部存储设备上实现高效的索引结构。B+树相比 B-树有以下优势：

  1. 更适合外存储：B+树将所有数据都存储在叶子节点中，而非在中间节点中，B+树的每个节点可以存放更多的 Key，相同数据量下，层高比 B-树更低，可减少 I/O 的次数。
  2. 更适合范围查询：B+树叶子节点构成链表，只需要遍历叶子节点即可进行范围查询或排序；B-树则需要用中序遍历的方式。

B-树相比 B+树的优势在于：

  1. 更适合基于频率的搜索：所有关键字在 B-树中出现且只出现一次，非叶子结点可以命中。经常访问的元素可能离根节点更近，访问更加迅速。

B+Tree 增删查的流程？​

  • 查找：每次找到第一个严格大于 key 的节点的前一个节点，直至叶节点。
  • 插入：先按照查找逻辑找到应该插入的位置，如果插入后 LeafPageSize = MaxSize，则将一半的键值对分裂到新产生的右兄弟节点中，并递归向父节点插入。
  • 删除：先按照查找逻辑找到应该删除的位置，如果删除后 PageSize < MinSize，则向兄弟节点借节点，或与兄弟节点合并，合并后需要在父节点中递归删除被合并节点的键值对。

B+Tree 中节点大小的选择依据？​

  • Page 大小：B+树中节点大小通常设为 Page 或 Page 的倍数。如果节点大小不满一页，但读取该节点时依然需要读取完整的一页，就造成了资源的浪费；如果每个节点都刚好一页的话，就可以用 Page ID 作为指向其他节点的指针。MySQL 中 B+ 树节点大小为 16K（1 页），层数为 3 的 B+树，可以存放约两千多万条的数据。
  • 磁盘性能：存储设备越慢，B+树节点需要越大，对单个节点的磁盘 I/O 就可以读取更多的数据；存储设备越快，B+树节点需要越小，减少冗余数据。
  • 负载类型：OLAP 类型负载常会全表扫描，会遍历 B+树的叶子节点，可增加节点大小，单次 I/O 能扫描更多数据；OLTP 类型负载常会进行点查询，可减小节点大小，降低查询过程在节点之间跳跃的开销。

B+Tree 如何处理 Duplicate Keys？​

  1. 为 Key 追加主键 ID：DBMS 可以使用 Partial Key 查找
  2. 叶子节点溢出：在原有的叶子节点后面，外接一个溢出节点

MySQL 在 InnoDB 引擎下，非唯一索引会同时存储对应行的主键 ID，所以非唯一索引相同时，会按记录的主键进行排序。

B+Tree 如何处理 Variable-Length Keys？​

参考网友的总结，主要有下列 4 种方法：

  1. 改为存储 Key 的指针：笔者个人感觉有可能采取 ELF 文件格式里符号表中的表项里的符号名存储的是该符号名在字符串表中的索引这种策略
  2. 让 B+树每个节点也都是变长节点：但这种策略并不推荐，因为节点变长的话就不一定对应一个或多个文件页了，管理的难度会变大
  3. Padding 策略：padding 这个词笔者之前在学习 OS 的引导扇区时见过，OS 启动所需的引导扇区的大小是固定的，xv6 中引导扇区是位于磁盘的第一个 block，但引导扇区中存储的用于启动的代码的长度未必正好有一个 block 的大小，因此就需要在程序文件剩下的位置补 0，直至总长度达到一个 block 那么大，然后存入磁盘里对应的扇区，从而制作好引导扇区，这种方式就叫 padding，在 DBMS 里，如果 Key 是变长的，我们也可以再向 Key 中补入空的字节，直到让 Key 的长度达到我们所设计的 fixed-size
  4. Slot 策略：和存储引擎模块里的 tuple 在 Page 里面的 Layout 通过 slot 来组织的方式）很像，节点里面有数组形式排布的 slot，slot 中存储指向对应 KV 的指针，这使得节点中 KV 的存储有很大灵活性

B+Tree 的优化方式？​

  1. 前缀压缩 (Prefix Compression)：在同一个叶子节点里很多 Key 的前缀是相同的，可以在叶子节点的元数据中存储公共前缀
  2. 去重 (Deduplication)：多个 KV 的 K 相同时，可去掉冗余的 K 减少占用空间
  3. 批量插入 (Bulk Insert)：如果一开始你就知道要插的所有 KEY，可以对他们先排序，然后对这些 KEY 去构建 INDEX BOTTOM UP，这种思想和创建堆时可以选择快速建堆策略而非一个一个地插入建堆的思想有点像
  4. 指针调整：如果一个 PAGE 已经在 BUFFER POOL 里 PINNED 了，我们可以存直接的指针来代替原来存的 PAGE ID。避免去 PAGE TABLE 查 ADDRESS

Latch Crabbing 的基本思想？​

Latch Crabbing 是 B+树常用的并发策略，意思是锁的释放和获取就像螃蟹一样在节点间爬行。线程在遍历时，只有当子节点被认为是安全时，才释放父节点的锁。安全的定义是：节点在进行操作后，不会触发分裂或合并，影响父节点的指针。

  • 插入：叶节点和中间节点的安全性分别考虑，因为它们分裂的时机不同
  • 删除：子节点要比最小的 minsize 大

Latch Crabbing 乐观锁如何实现？​

标准的 Latch Crabbing 是悲观锁，插入删除都要对根节点加写锁，根节点是锁的瓶颈，高并发场景下导致糟糕的多线程扩展性。

乐观锁采用一种乐观思想，假设大部分写操作不会修改树结构。实现比较简单，修改 find_leaf_page 的逻辑，一路加读锁，最后对 leafpage 加写锁即可。如果发现对 leafpage 的操作会影响 b+树结构时，放弃获取的所有锁，回滚到根节点，悲观地获取锁。

如果 B+ 树已经有好几层，每一个叶节点可以容纳大量键值对信息，在写操作下不会那么容易发生合并分裂操作，乐观锁可以显著提升性能。但是如果树只有几个节点，频繁发生分裂合并，性能就比较差了。

在我的 BusTub 实现中，我使用的是「基于螃蟹协议的乐观策略」，然而，B+Tree 本身通常是「矮胖」的，如 MySQL 通常为 3 层。这种情况下，需要持有 2 层读锁的实现方式就未必足够乐观。B-link Tree 就是一种进一步提升并发能力的数据结构，可以避免在树结构调整时全局加锁而带来的性能衰退，主要有两点核心思想：

  1. 在中间节点增加字段 link pointer，指向右兄弟节点，B-link Tree 的名字也由此而来
  2. 在每个节点内增加一个字段 high key，在查询时如果目标值超过该节点的 high key，就需要循着 link pointer 继续往后继节点查找

B-link Tree 的劣势在于需要额外维护 link pointer 和 high key 字段，以及查询时需要额外判断，如果查询超过 high key，需要额外通过 link pointer 查询其后继节点，在数据库应用中可能会产生一次额外的 IO，从而造成单次查找性能的下降。

如何实现无锁 B+Tree？​

在创建这张卡片时，对无锁容器的理解还不够深入，这里先贴几篇链接：

  1. 微软提出的无锁 B 族树 —— Bw-tree - 知乎
  2. 数据库管理系统(二): Lock-free, high-performance Bw Tree - 知乎
  3. 高性能无锁数据结构探索-B+树读写、SMO 及 swap - 知乎

常见的 Hash 算法有哪些？​

  • Static Hashing Schemes
    • Linear Probe Hashing
    • Robin Hood Hashing
    • Cuckoo Hashing
  • Dynamic Hashing Schemes
    • Chained Hashing
    • Extendible Hashing
    • Linear Hashing

什么是跳表？​

跳表（Skip List）是一种数据结构，用于实现有序集合（例如有序的键值对）。它可以在 O(log n) 的时间复杂度内执行搜索、插入和删除等操作，与平衡树相比，它的实现更加简单，而且在许多情况下性能也更好。

跳表通过在每个节点上增加多个指针，从而实现了跳跃式的访问。在一个跳表中，每一层都是一个有序的链表，每个节点上都包含了多个指向下一层节点的指针。这些指针可以让我们在搜索时跳过一些不必要的节点，从而提高搜索的效率。

跳表的实现基于一种简单的随机化算法，该算法可以保证跳表的高度始终保持在 O(log n) 级别，从而保证了跳表操作的时间复杂度。

Query Model​

Processing Models 有哪些？​

在 DBMS 中，SQL 语句会被组织成树状的查询计划，数据从叶节点流向根节点，查询结果在根节点得出。 Processing Model 定义了系统如何执行 Query Plan，主要有三种模型：

  1. Iterator Model（迭代器模型/火山模型/管道模型）：父节点递归调用子节点的 next()
  2. Materialization Model（物化模型）：每个算子一次性返回全部数据
  3. Vectorized/Batch Model（矢量化/批量模型）：每个算子一次返回一批数据

不同模型的区别如下：

模型调用方向提交场景
Iterator / Volcano自顶向下单个 TupleGeneral Purpose
Materialization自底向上全部 TupleOLTP
Vectorized自顶向下Tuple BatchOLAP

详细介绍一下火山模型？​

火山模型中，每个算子都实现了 Init() 和 Next() 方法，每次调用时操作符会返回一个 Tuple 或者 Null，Null 表示已经全部返回完了。操作符本身由一个循环实现，循环内部调用其子操作符的 Next() 方法，并从它们那边获取下一条数据供自己操作。

部分算子会在 Init() 阶段直接获取子操作符的数据并操作，如 Sort、Hash Join、Aggregate 等，这一类算子被称为 pipeline breaker。在 BusTub 中，我们假设这类操作完全适合内存，因此实现比较简单。

火山模型的优劣？​

参考 SQL 优化之火山模型 - 知乎 一文，火山模型的优点在于实现简单，每个 Operator 可以单独抽象实现、不需要关心其他 Operator 的逻辑；缺点在于造成大量的虚函数调用，不利于编译器优化、CPU 分支预测等，进而降低 CPU 的利用率。

在 I/O 速度获得极大提升的今天，对火山模型的优化主要可以从两方面考虑：

  1. 代码生成：将查询计划生成为通过循环推数据的代码，从而避免虚函数调用以提升速度。但可能因查询计划过于复杂而导致代码生成过慢。
  2. 向量化：算子每次返回多条数据，借助 SIMD（Single Instruction Multiple Data，单指令流多数据流）技术提高 CPU 的利用率，通常基于列存储。

火山模型一次吐出多个  Tuple，和向量化模型的区别？​

参考 列式数据库和向量化 | zulu.wang 一文，向量化模型通常是针对列存储而言的，具有如下优势：

  1. 减少 I/O 的读入总量：列存储利于压缩，读取一组数据所需 I/O 次数比行存储少
  2. 可以充分利用 CPU 的缓存：在基于列的处理中，只会读入感兴趣的列数据，可以有效使用 CPU 的内存带宽；行存储还需要进行一些列裁剪的优化才能减少冗余数据。

火山模型一次吐出多个  Tuple，说明仍是基于行的处理，相比基于列存储的向量化模型，两者的区别应该主要在 I/O 成本上。

Query Executor​

External Merge Sort 实现细节？​

外排序 (External Merge Sort) 的思路和归并排序比较像。以 2-Way 外排序为例，待排序数据占 N 页，缓冲池大小为 B 页，缓冲池最少要有 3 页（2 页存储输入数据，1 页缓存中间结果），外排序的步骤如下：

  1. 先将带排序的数据分块（在 DBMS 就是 Page 大小的块）
  2. 将每块放入内存分别排序，得到有序子串
  3. 将排序好的子串合并为更大的有序子串

排序的优化方式：

  1. Double Buffering Optimization：预读下一个要排序的 Page，类似流水线
  2. 使用 n-Way 外排序，n=B−1n=B-1，则有：
    • Number of Passes: 1+⌈log⁡B−1⌈N/B⌉⌉1+⌈\log_{B-1}⌈N/B⌉⌉
    • Total I/O Cost: 2N⋅passes2N·passes
  3. 使用有序的 B+Tree 索引

Aggregation 实现细节？​

Aggregation 算子的执行有三种策略：

  1. PLAIN-AGG：计算不含 group by 的聚集函数
  2. SORT-AGG：输入的元组已经是有序的
  3. HASH-AGG：BusTub 中实现的
    1. Partition：以 Group By 字段构建哈希表，以哈希桶为分区落盘
    2. Rehash：区分哈希碰撞的值，将结果放入最终哈希表中

Join 早物化和晚物化的区别？​

  • 早物化 (Early Materialization)：Join 操作输出完整的一行数据，无需回表。
  • 晚物化 (Late Materialization)：Join 操作输出对应原始表的 Record ID，获取其他字段需要回表，适合列存储的情况，DBMS 在对 Join 后得到的表执行查询时，无需拷贝不需要的数据。

Nested Loop Join  实现细节？​

以 Inner Equal Join 为例，有 3 种 Join 的实现方式：

  • Simple / Stupid Nested-Loop Join：外表占 M 页，内表占 N 页，外表的元组数量为 m，则开销为 M+(m⋅N)M+(m·N)。
  • Block Nested-Loop Join：将外表的数据批量与内表的数据进行匹配。外表占 M 页，内表占 N 页，缓冲池大小为 B 页，缓冲池一个页用于输出，一个页用于缓存右侧（内表），其余表都用于缓存外表。则开销为 M+(⌈M/(B−2)⌉⋅N)M+(⌈M/(B-2)⌉·N)。
  • Index Nested-Loop Join：以内表参与 Join 的那一列字段为 Key 构建索引，假设每次查询索引的开销为 C，则开销为 M+(M⋅C)M+(M·C)。

Sort-Merge Join 实现细节？​

又名 Merge Join，先给参与 Join 的两个表按照连接列的字段进行排序，然后对这两个排好序的表进行 Merge，Merge 的操作类似于双指针（存在回溯右指针的情况）。

开销为 2M(1+⌈log⁡B−1⌈M/B⌉⌉)+2N(1+⌈log⁡B−1⌈N/B⌉⌉)+(M+N)2M(1+⌈\log_{B-1}⌈M/B⌉⌉)+2N(1+⌈\log_{B-1}⌈N/B⌉⌉)+(M+N)，在参与 Join 运算的表已经按照连接列排好序时（如 Sort 算子、索引），或者输出要求为按照连接列排序时，使用 Merge Join 更合适。

Hash Join 实现细节？​

基础的 Hash Join 主要由两阶段组成：

  1. 构建哈希表 (Build)： 扫描 Outer Table，使用哈希函数 H1 构建哈希表，以连接列为 Key
  2. 点查询 (Probe)：Inner Table 以哈希函数 H1 进行查询

在点查询时，一种可行的优化是在构建阶段创建布隆过滤器 (Bloom Filter)，以提前确定不存在的相关表项。而对于假阳性的情况，则通过对哈希表的查询以排除。

Grace Hash Join 实现细节？​

针对内存无法存下整个哈希表的情况，需要将哈希表的部分内容驱逐到硬盘，采用 Grace Hash Join 算法：

  1. 构建哈希表 (Build)： 对 R 表和 S 表都使用相同的哈希函数构建哈希索引，存入硬盘，读取和写入的开销为 2(M+N)2(M+N)
  2. 点查询 (Probe)：把硬盘中两个表相具有相同桶号的哈希桶取出，做 Nested Loop Join，匹配所需开销为 (M+N)(M+N)

对于哈希桶太大的情况，则另一种哈希函数递归地分区，直到拆分为足够小的块。Grace Hash Join 的总开销为 3(M+N)3(M+N)。

不同  Join  算法的使用场景？​

  • Block Nested Loop Join：绝对不会用 Simple Nested Loop Join 的
  • Index Nested Loop Join
  • Sort-Merge Join：
    • 数据倾斜时，为其构建哈希表会导致严重的哈希碰撞
    • 输出要求有序
    • 下层算子已经经过排序
  • Hash Join：OLAP 下多数情况下最好的选择

Query Optimize​

查询优化的方式？​

查询优化是数据库最难的部分。优化通常包含两个阶段：

  1. 基于规则的优化（Rule-Based-Optimization，简称 RBO）：如常量折叠、列裁剪、谓词下推、谓词上推、Max/Min 转 TopN 等
  2. 基于代价的优化（Cost-Based Optimization，简称 CBO）：如 Join Reorder 等

怎么实现基于代价优化？​

使用代价模型来进行索引选择和算子选择，计算每个索引的访问代价和计划中每个物理算子的执行代价（如 HashJoin、IndexJoin 等），选择代价最低的计划。在 2022 的 BusTub 中，提到了 Join Reorder 的代价优化，每个表可以根据后缀得到表的规模，进而计算执行代价。

为什么 Join 交换表的顺序就能达到优化效果？​

在 Join 时，要尽量把所占 Page 较小的表放在左侧（驱动表，外表），可以减少磁盘读写次数。

  • 以 Nested Loop Join 为例，外表占 M 页，内表占 N 页，缓冲池大小为 B 页，则 I/O 次数为 M+(⌈M/(B−2)⌉⋅N)M+(⌈M/(B-2)⌉·N)，缓冲池一个页用于输出，一个页用于缓存右侧（内表），其余表都用于缓存外表，可见将外表大小减小可以有效减小 I/O 次数。

查询优化如何避免 Overhead？​

为了避免优化本身比执行开销大：

  1. 定期监控数据库性能：通过监控数据库的性能指标，可以了解数据库的实时状态，及时发现性能瓶颈，并进行优化。这样可以避免过度优化导致的额外开销。
  2. 执行计划管理： 执行计划管理 (SPM) | PingCAP 文档中心 ，手动禁用一些优化规则。
  3. 定期评估优化效果：定期评估优化效果可以了解优化措施的实际效果，及时发现优化带来的问题，并进行调整和优化。

而以 Join Reorder 为例，存在两种 Join Reorder 算法，贪心算法和动态规划算法。

  1. Join Reorder 贪心算法：在所有参与 Join 的节点中，选择行数最小的表与其他各表分别做一次 Join 的结果估算，然后选择其中结果最小的一对进行 Join，再继续这个过程进入下一轮的选择和 Join，直到所有的节点都完成 Join。
  2. Join Reorder 动态规划算法：在所有参与 Join 的节点中，枚举所有可能的 Join 顺序，然后选择最优的 Join 顺序。

在 PingCAP 中，Join Reorder 算法的选择由变量 tidb_opt_join_reorder_threshold 控制，当参与 Join Reorder 的节点个数大于该阈值时选择贪心算法，反之选择动态规划算法。这也是一种避免 Overhead 的手段。

Concurrency Control​

什么是事务的 ACID？​

ACID 是事务的四个基本属性，分别代表原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability）。

  1. 原子性（Atomicity）：指事务是一个不可分割的操作序列，事务中的所有操作要么全部执行成功，要么全部执行失败。如果事务中的任何一部分操作失败，整个事务都将被回滚到事务开始前的状态，保证了数据的完整性。
  2. 一致性（Consistency）：指事务的执行不会破坏数据库的完整性约束。在事务执行前和执行后，数据库必须处于一致性状态。例如，如果一个银行账户从一个用户转移到另一个用户，那么在此过程中总金额必须保持不变。
  3. 隔离性（Isolation）：指多个事务并发执行时，每个事务都应该与其他事务隔离开来，互不干扰。事务的隔离级别越高，就越能保证数据的一致性和隔离性，但同时也会增加并发处理的开销。
  4. 持久性（Durability）：指事务一旦提交，它对数据库中数据的改变就应该永久保存在数据库中。即使系统崩溃或发生其他故障，也应该能够恢复到提交事务后的状态。

综上所述，ACID 是事务的四个基本属性，用于保证事务的原子性、一致性、隔离性和持久性，确保数据库在并发环境下的数据完整性和可靠性。

什么是事务的隔离级别？​

事务的隔离级别是指多个并发事务之间的隔离程度，即一个事务对于其他事务的可见性和影响程度。在并发环境下，多个事务可能同时访问相同的数据，如果事务之间的隔离级别不够高，就可能会导致一些问题，如脏读、不可重复读和幻读等。

常见的事务隔离级别有以下四种：

  1. 读未提交（Read Uncommitted）：允许一个事务读取其他事务未提交的数据。此级别最低，可能出现脏读、不可重复读和幻读等问题。
  2. 读已提交（Read Committed）：一个事务只能读取其他事务已提交的数据。此级别可以避免脏读问题，但可能出现不可重复读和幻读等问题。
  3. 可重复读（Repeatable Read）：一个事务在执行期间多次读取同一条记录所获取的结果是一致的，不受其他事务的影响。此级别可以避免脏读和不可重复读问题，但可能会出现幻读问题。
  4. 可串行化（Serializable）：最高的隔离级别，强制事务串行执行，避免了所有并发问题，但可能会导致性能问题。

不同的隔离级别提供不同的隔离程度和并发控制，应根据实际需求选择合适的隔离级别，以平衡数据一致性和并发性能。BusTub 实现了前三种隔离级别。

为什么 2PL 可以保证事务的可串行化？​

参考以下资料，可以使用反证法或归纳法证明。

什么是脏读、不可重复读、幻读？​

脏读、不可重复读和幻读是在并发事务中可能会出现的问题，这些问题的产生与事务的隔离级别有关。

  1. 脏读（Dirty Read）：指一个事务读取了另一个事务未提交的数据。如果另一个事务在后续操作中回滚，那么当前事务读取的数据就是无效的或错误的。
  2. 不可重复读（Non-repeatable Read）：指一个事务多次读取同一条记录，但在这个过程中，其他事务对该记录进行了修改或删除，导致多次读取的结果不一致。
  3. 幻读（Phantom Read）：指一个事务执行相同的查询，但在查询期间另一个事务插入了新的记录，导致当前事务多次执行查询时结果不一致。

这些问题的产生是由于事务的隔离级别不同，不同隔离级别下事务的可见性和影响程度不同。例如，在读未提交隔离级别下，一个事务可以读取其他事务未提交的数据，可能导致脏读问题；在读已提交隔离级别下，一个事务只能读取其他事务已提交的数据，可以避免脏读问题，但是还可能出现不可重复读和幻读问题。

锁管理器是怎么加锁解锁？​

事务持久化是通过什么实现的？​

备注
  • 三个隔离级别分别怎么实现，加锁策略是什么
  • 什么是两阶段锁
  • 锁是怎么管理的，一个事务请求锁的具体过程讲讲
  • 什么是一致性哈希算法
  • 数据倾斜怎么解决
  • 星环科技数据库开发实习面经（已 offer）_牛客网
  • Raft 成员变更
  • multi-Raft 架构
  • LSM-tree 结构
  • LSM-tree 优化
  • 火山模型向量化
  • 数据库整体架构
  • 星环数据库内核研发二面 20230329_牛客网
  • 美团问了 lru-k
  • 腾讯问了那几个物化模型
  • 向量模型
  • join
  • hash join
  • 你的项目死锁怎么检测的
  • 数据库的架构
  • 服务层到引擎层，然后细化
  • 不同引擎对索引的支持
  • B 树和 B+树的区别
  • B+树树高怎么算？树高为 4 能支持多少数据量
  • 数据库 ACID 怎么实现
  • binlog 记录的是什么
  • 字节跳动 - 后端实习 - 通过_牛客网
  • DBInterview
  • 一、P0 字典树
  • 什么场景下适合使用字典树？
  • 有限状态自动机 FST 了解吗？跟字典树有什么联系？
  • 怎么理解的倒排索引？
  • 二、P1 缓冲池管理
  • 可扩展哈希表如何扩容，如何缩容的？
  • LRU-K 算法的应用场景？
  • LRU-K 算法相对于 LRU 算法的优势有哪些？
  • 缓冲池的执行流程
  • Page Cache 的执行流程
  • 什么情况下可以用 O_Direct
  • 如果页的大小为 16KB，而磁盘只保证 4KB 的读写是原子的，刷脏页的时候只刷了部分页进程就崩溃了，怎么处理？
  • 三、B+树
  • B+树和 B 树的区别？
  • 为什么 MySQL 使用 B+树而不使用 B 树？
  • B 树的应用场景有哪些？
  • B+树和 LSM-Tree 的使用场景？LSM-Tree 存在的问题有哪些？针对这些问题有什么解决思路？
  • B+树并发处理有哪些优化思路？
  • Blink 树有什么特点？
  • 四、查询执行
  • 什么是火山模型？
  • 为什么要使用火山模型？有什么优点？有什么缺点？缺点从哪些角度进行优化？
  • 解释一下左连接和内连接？
  • 怎么理解的数据库回表？
  • 五、事务管理
  • 2PL 原理是什么？2PL 存在什么问题？如何解决这些问题？
  • 如何基于 2PL 实现的隔离级别？
  • 什么是严格两阶段锁（strict-2PL）？
  • 什么是强两阶段锁（strong-2PL）?
  • 隔离级别有哪些？分别存在什么问题？
  • 什么情况下会导致幻读，举个例子？
  • 快照隔离存在什么问题？什么是写偏序问题，举个例子？
  • 数据库是怎么实现一致性的？
  • 项目中所涉及的几种锁介绍一下，怎么理解隔离级别和锁的关系？
  • 为什么 MySQL 使用 B+树而不使用 B 树？
  • 死锁问题怎么解决？
  • MySQL 怎么保证原子性的？
  • MySQL 的默认隔离级别是什么？可重复读会有什么问题？既然可重复读有幻读问题那 MySQL 满足了隔离性吗？如果满足了幻读问题如何解决的？如果没满足如何保证的数据一致性？