P1

ARC Replacement

1. MRU (Most Recently Used) List / 最近使用列表：

   • 作用：追踪那些最近被访问过一次的页面。

   • 代表：体现了访问的“新近度”。一个页面刚被加载进缓存时，通常会先放在这里。

2. MFU (Most Frequently Used) List / 频繁使用列表：

   • 作用：追踪那些被访问过不止一次的页面。

   • 代表：体现了访问的“频率”。当 MRU 列表中的页面被再次访问时，它就会被移动到 MFU 列表。

3. MRU Ghost List / MRU 幽灵列表：

   • 作用：这是一个“历史记录”列表，它追踪那些最近从 MRU 列表中被淘汰出去的页面的 ID。这些页面已经不在缓存（Buffer Pool）中了。

   • 目的：用来判断我们为 MRU 分配的空间是否太小了。如果一个刚被淘汰的 MRU 页面很快又被访问了（即在幽灵列表中被“击中”），说明我们应该给 MRU 列表更多的空间。

4. MFU Ghost List / MFU 幽灵列表：

   • 作用：同样是历史记录，它追踪那些最近从 MFU 列表中被淘汰出去的页面的 ID。

   • 目的：用来判断我们为 MFU 分配的空间是否太小了。如果一个被淘汰的 MFU 页面很快又被访问，说明我们应该给 MFU 列表更多的空间。

简单来说，ARC 算法就像一个聪明的图书管理员，他把书架分成了“新书区 (MRU)”和“热门书区 (MFU)”。他还随身带了两个小本子，一个记录“刚被还回去的新书 (MRU Ghost)”，另一个记录“刚被还回去的热门书 (MFU Ghost)”。

• 当有人来借书，发现这本书刚被还回去了（在“小本子”上找到了记录）：

  • 如果是在“新书”本子上找到的，管理员会认为“新书区”太小了，下次会把新书区扩大一点 (mru_target_size_ 增加)。

  • 如果是在“热门书”本子上找到的，他会认为“热门区”太小了，下次会把热门区扩大一点 (mru_target_size_ 减小)。

1. ARC 把缓存空间动态分成两部分
   T = LRU + LFU
   用 p = |LRU| 表示 LRU 部分的目标大小，剩下 |T|−p 给 LFU。
   ghost 列表（LRU-ghost、LFU-ghost）并不占内存，它们只是“历史记录”，记录哪些页最近被踢出去了。

2. ghost hit 的含义
   当 CPU 再次访问一个已经踢出去的页，却在 ghost 里找到了它，说明：
   “这个页其实很快又被用到了，我上次把它踢掉是错误的。”
   这条信息非常宝贵——它直接告诉算法：
   “踢得太多（或太少）了，要改。”

3. 如何“改”——调整 p

   • 如果在 mru_ghost 里命中 ⇒ 被踢的是“最近”页 ⇒ 说明 LRU 部分给得太小，导致 LRU 页过早被逐出 ⇒ 把 p 增大（多给 LRU 一点空间）。

   • 如果在 mfu_ghost 里命中 ⇒ 被踢的是“频繁”页 ⇒ 说明 LFU 部分给得太小，导致 LFU 页过早被逐出 ⇒ 把 p 减小（多给 LFU 一点空间）。

   这样下一次 Evict 时，就会按新的 p 值去选受害者，同类型的页面就能在缓存里停留更久，减少再次误杀。

好的，我们来详细分析一下 DiskScheduler 的代码，并提供一个清晰的实现思路。

代码解释 (Code Explanation)

这部分代码定义了一个异步磁盘 I/O 调度器。在数据库中，直接在处理查询的线程（工作线程）上执行磁盘读写操作，会因为磁盘 I/O 的高延迟而阻塞该线程，导致系统吞吐量下降。

DiskScheduler 的核心思想是解耦：将 "请求 I/O" 的动作和 "执行 I/O" 的动作分开，放到不同的线程中。

1. DiskRequest 结构体:

   • 这是一个封装了单次磁盘 I/O 操作所有信息的结构体。
   • is_write_: 一个布尔值，用于区分是读操作还是写操作。
   • data_: 一个 char* 指针，指向一块内存。对于读操作，磁盘上的数据会被读到这块内存里；对于写操作，这块内存里的数据会被写到磁盘上。这通常是缓冲池（Buffer Pool）中的一个 Frame。
   • page_id_: 要操作的磁盘页的 ID。
   • callback_: 这是实现异步的关键。它是一个 std::promise<bool>。
     • Promise/Future 模式: 当一个线程（比如 Buffer Pool Manager）需要进行磁盘 I/O 时，它会创建一个 promise 和一个与之关联的 future。它将 promise 放入 DiskRequest 中，自己保留 future 对象。
     • 然后它把这个 Request 交给 DiskScheduler。
     • 之后，该线程可以调用 future.get()，这个调用会阻塞，直到 promise 被 fulfill (即 promise.set_value() 被调用)。
     • 这样，请求线程就可以在需要等待结果时才阻塞，而不是在 I/O 操作一开始就阻塞。

2. DiskScheduler 类:

   • disk_manager_: 一个指向 DiskManager 的指针。DiskManager是真正与物理磁盘交互的底层组件。DiskScheduler 只是一个调度层，最终的读写还是要委托给 DiskManager。
   • request_queue_: 这是一个 Channel，本质上是一个线程安全的阻塞队列。
     • 生产者-消费者模型: Schedule 方法是生产者，它把 DiskRequest 放入队列。后台的工作线程是消费者，它从队列中取出 DiskRequest 并处理。
     • std::optional<DiskRequest>: 使用 optional 是一个巧妙的设计。队列中存放的是 DiskRequest。当调度器要析构（关闭）时，它会往队列里放一个 std::nullopt（空值）。后台线程取到这个空值时，就知道这是个“关闭信号”，于是退出循环，线程结束。
   • background_thread_: 一个 std::thread，在 DiskScheduler 构造时创建。它专门运行 StartWorkerThread 函数，是磁盘 I/O 的实际执行者。
   • 构造函数 DiskScheduler(...): 创建并启动后台线程。
   • 析构函数 ~DiskScheduler(): 发送关闭信号 (std::nullopt) 到队列，并调用 join() 等待后台线程安全退出。这确保了所有排队的请求都被处理完毕（或者至少线程被干净地关闭）后，程序才继续执行。
   • Schedule(...): 公共接口，供其他模块（如 Buffer Pool Manager）提交 I/O 请求。
   • StartWorkerThread(): 后台线程的入口函数，是我们需要实现的核心逻辑。

工作流程 (Workflow)

1. 请求方 (e.g., Buffer Pool Manager):
   a. 需要从磁盘读取 page 5 到内存 data_ptr。
   b. 创建一个 std::promise<bool> p。
   c. 从 p 获取 std::future<bool> f = p.get_future()。
   d. 创建一个 DiskRequest：{is_write_: false, data_: data_ptr, page_id_: 5, callback_: std::move(p)}。
   e. 将这个 DiskRequest 放入一个 vector 中，调用 disk_scheduler->Schedule(requests)。
   f. 请求方现在持有 f，它可以继续做别的工作，或者立即调用 f.get() 等待 I/O 完成。当 f.get() 返回时，它就知道 page 5 的数据已经成功读入 data_ptr 了。

2. DiskScheduler:
   a. Schedule 方法接收到 vector<DiskRequest>，它会遍历这个 vector，把每一个 DiskRequest 都 Put 进 request_queue_。

3. 后台线程 (background_thread_):
   a. 线程一直在一个循环中运行 StartWorkerThread 函数。
   b. 在循环里，它调用 request_queue_.Get()。这个调用会阻塞，直到队列里有新的 DiskRequest 或者关闭信号。
   c. 当它从队列里取出一个 DiskRequest 后：
   i. 检查 is_write_ 字段。
   ii. 如果是写请求，就调用 disk_manager_->WritePage(...)。
   iii. 如果是读请求，就调用 disk_manager_->ReadPage(...)。
   d. 磁盘操作完成后，它通过请求中的 callback_ (即那个 std::promise) 调用 callback_.set_value(true)。
   e. 这个 set_value 操作会唤醒之前在 future.get() 上阻塞的请求方线程。
   f. 后台线程回到循环的开始，继续等待下一个请求。
   g. 如果从队列中取到的是 std::nullopt，则跳出循环，线程结束。

Buffer Pool Manager（P2）

流程一：Cache Hit（页面已在内存）

线程 T1 调用 ReadPage(page_id):

1. 获取 bpm_latch_ 锁

2. 查 page_table_ → 命中，找到 frame_id

3. pin_count++，RecordAccess

4. 释放 bpm_latch_ 锁

5. 获取 frame_header->io_mutex_

6. 检查 io_done_:

   - 如果 io_done_ == true：直接继续

   - 如果 io_done_ == false：在 io_cv_ 上等待

7. 释放 io_mutex_

8. 获取 frame_header->rwlatch_ 的读锁

9. 返回 ReadPageGuard

  

如果此时页面正在 I/O（io_done_ == false）：

- T1 在 io_cv_ 上等待

- 当 I/O 完成后，io_done_ = true，io_cv_.notify_all()

- T1 被唤醒，继续执行

代码位置（buffer_pool_manager.cpp:365-368）：

std::unique_lock io_lock(frame_header->io_mutex_);

while (!frame_header->io_done_.load()) {

  frame_header->io_cv_.wait(io_lock);

}

io_lock.unlock();

流程二：Cache Miss + 需要 I/O

线程 T1 调用 ReadPage(page_id):

1. 获取 bpm_latch_ 锁

2. 查 page_table_ → 未命中

3. 从 free_frames_ 拿一个空闲 frame，或 Evict

4. 如果 Evict 的是脏页，需要写回

5. 更新 page_table_

6. 初始化 frame_header:

   - pin_count = 1

   - io_done_ = false

7. 获取 frame_header->io_mutex_

8. 把 page_id 加入 pages_in_writeback_（加 writeback_latch_）

9. 释放 bpm_latch_ 锁

10. 如果需要写回脏页：

    - 调度写请求

    - 等待写完成

    - 从 pages_in_writeback_ 移除

11. 调度读请求，从磁盘读新页面

12. 等待读完成

13. 设置 io_done_ = true

14. io_cv_.notify_all() （唤醒所有等待的线程）

15. 释放 io_mutex_

16. 返回 ReadPageGuard

  

此时如果有其他线程 T2 也读同一个 page_id:

- T2 获取 bpm_latch_，查 page_table_ → 命中（因为 T1 已经更新了）

- T2 pin_count++，释放 bpm_latch_

- T2 获取 io_mutex_，发现 io_done_ == false

- T2 在 io_cv_ 上等待

- 当 T1 完成 I/O，io_cv_.notify_all()

- T2 被唤醒，继续执行

代码位置（buffer_pool_manager.cpp:398-433）：

std::unique_lock<std::mutex> io_lock(frame_header->io_mutex_);

frame_header->io_done_.store(false);  // io ongoing

// ...

// Read the new page from disk

read_future.get();  // Wait for the read to complete.

frame_header->io_done_.store(true);

frame_header->io_cv_.notify_all();

io_lock.unlock();

流程三：AccessType::Scan（绕过缓冲池）

线程 T1 调用 ReadPage(page_id, AccessType::Scan):

1. 检查 access_type == AccessType::Scan

2. 获取 writeback_latch_ 锁

3. 查 pages_in_writeback_:

   - 如果 page_id 在里面，获取对应的 mutex

4. 释放 writeback_latch_ 锁

5. 如果有对应的 mutex，获取它（等待写回完成）

6. 创建临时 buffer，直接从磁盘读

7. 创建临时 FrameHeader

8. 返回特殊的 ReadPageGuard

  

作用：

- 全表扫描时绕过缓冲池，避免把热页面挤出

- 但仍要确保读到最新数据（等待正在进行的写回）

代码位置（buffer_pool_manager.cpp:454-487）：

if (access_type == AccessType::Scan) {

  // 创建临时缓冲区，直接从磁盘读取

  std::unique_lock<std::mutex> wb_latch(*writeback_latch_);

  // 检查是否正在写回

  // ...

  // 直接从磁盘读取

  read_future.get();

  // ...

}

四、设计亮点

1. 避免重复 I/O

当多个线程同时访问同一个不在内存中的页面时：

• 只有第一个线程真正做 I/O

• 其他线程在 io_cv_ 上等待

• I/O 完成后，所有等待的线程都被唤醒

• 避免了重复读取同一个页面

2. 细粒度锁

• 不是一个全局大锁，而是：

- 每个 shard 有自己的 bpm_latch_

- 每个 frame 有自己的 rwlatch_、io_mutex_

- writeback_latch_ 只保护 pages_in_writeback_

• 减少锁竞争，提高并发度

3. 条件变量的正确使用

// 总是用 while 循环检查条件，不是 if！

while (!frame_header->io_done_.load()) {

  frame_header->io_cv_.wait(io_lock);

}

• 避免虚假唤醒（Spurious Wakeup）

• 多线程安全

4. Sharding（分片）

• 把 Buffer Pool 分成多个 shard

• 每个 shard 有独立的锁

• page_id 用哈希分配到不同 shard

• 进一步减少锁竞争

五、锁的层次结构

BufferPoolManager

  └── Shard 0

        ├── bpm_latch_ (mutex)

        │   ├── 保护 page_table_

        │   ├── 保护 free_frames_

        │   └── 保护 replacer_

        ├── writeback_latch_ (mutex)

        │   └── 保护 pages_in_writeback_

        └── Frame 0

            ├── rwlatch_ (shared_mutex)

            │   ├── 读锁：多个读者

            │   └── 写锁：独占

            ├── io_mutex_ (mutex)

            │   └── 保护 io_done_

            └── io_cv_ (condition_variable)

                └── 等待 I/O 完成

        └── Frame 1

            └── ... (same as Frame 0)

  └── Shard 1

        └── ... (same as Shard 0)

P3 Query Executor

1. SQL 字符串输入: 用户输入 SELECT * FROM my_table WHERE id = 1;

2. 解析 (Parse): BusTub (在这个项目中简化了) 会将 SQL 字符串转换成一个“抽象语法树 (AST)”。

3. 绑定 (Bind): 将 AST 中的表名、列名等标识符与数据库的元信息（Catalog）中的实际对象关联起来。

4. 计划 (Plan): 将 AST 转换成一个逻辑计划树 (Logical Plan Tree)。树的每个节点代表一个操作，比如 SeqScanNode, FilterNode, JoinNode 等。例如，上面的查询可能会变成一个 FilterNode (过滤 id=1)，它的子节点是一个 SeqScanNode (扫描 my_table)。

5. 优化 (Optimize): 优化器会把逻辑计划树转换成一个更高效的物理计划树 (Physical Plan Tree)。比如，如果 id 列有索引，优化器可能会把 SeqScanNode 换成 IndexScanNode。

6. 执行 (Execution): 这是 P3 的核心工作。

   • ExecutorFactory 会遍历物理计划树，为每一个 PlanNode 创建一个对应的 Executor（执行器）。比如，SeqScanPlanNode 对应 SeqScanExecutor，InsertPlanNode 对应 InsertExecutor。

   • 这些执行器也组成一棵树，结构和物理计划树完全一样。

   • 执行引擎从最顶层的执行器节点开始调用它的 Next() 方法。

各个组成部分

1. Catalog (图书馆的“总目录/索引系统”)

   • 它是什么？ Catalog 是数据库的“元数据”管理器。它就像图书馆入口处的电脑查询系统或者老式的卡片目录。

   • 它知道什么？ 你问它：“《数据库系统概念》这本书在哪？” 它不会直接给你书，但它会告诉你：这本书的索引号是 TP311.13-G5，它在 计算机科学 书架区。在数据库里，你问 Catalog：“students 这张表的信息是什么？” 它会告诉你：这张表的 ID (oid) 是 123，它有 id, name, age 这几列，它的物理数据存储在一个叫做 TableHeap 的对象里（相当于告诉你在哪个书架区）。

   • 它不知道什么？ 它不关心书的具体内容（元组数据），也不关心书现在被谁借走了（事务/锁）。它只负责记录“有什么”和“在哪里”。

   • 关系: SeqScanExecutor 开始工作时，第一步就是拿着 plan_ 给的 table_oid 去问 Catalog，从而找到管理这张表物理存储的 TableHeap 对象。Catalog是所有查询的起点。

2. Buffer Pool Manager (BPM) (图书馆的“图书管理员和阅览区”)

   • 它是什么？ BPM 是内存和磁盘之间的桥梁。磁盘就像图书馆的“地下书库”，非常大但访问很慢。内存（RAM）就像图书馆的“阅览桌”，很小但访问超快。BPM 就是那个负责把书从书库搬到阅览桌，并在桌子满了之后决定哪些书可以搬回去的图书管理员。

   • 它的工作单位是什么？ BPM 不关心一本“书”（Tuple）有多大，它只按“箱子”（Page）来搬运。一个 Page 是一个固定大小的数据块（比如 4KB），里面可能放了很多个 Tuple。

   • 它如何工作？ 当 TableHeap (书架) 需要读取某个 Tuple 时，它会先计算出这个 Tuple 在哪个 Page 里。然后它会向 BPM 发出请求：“请把第 N 号箱子（Page ID）给我”。BPM 会：

     1. 检查阅览桌（内存）上是否已经有这个箱子了。

     2. 如果有，直接把这个箱子的位置给 TableHeap。

     3. 如果没有，管理员（BPM）就去地下书库（磁盘），找到这个箱子，把它搬到阅览桌上一个空位。如果没空位，就根据某种规则（比如 LRU，最久没用的）把一个旧箱子搬回书库，再把新箱子放上来。

   • 关系: BPM 是物理数据访问的唯一通道。 任何模块（比如TableHeap）想要读写磁盘上的数据，都必须通过 BPM。它对上层屏蔽了复杂的磁盘 I/O 操作。

3. Transaction Manager (图书馆的“规则和安保系统”)

   • 它是什么？ 事务管理器确保数据库操作的ACID特性，尤其是并发控制（Concurrency Control）和恢复（Recovery）。它就像图书馆的安保和借阅规则系统。

   • 它如何工作？

     • 并发控制 (锁): 假设你和另一个人同时想看同一本孤本。图书馆规定，一个人在看的时候，另一个人必须等待（加锁）。Transaction Manager (通过内部的 LockManager) 就是做这个的。当你（一个事务）要读取一个 Tuple 时，你需要先获取一个“共享锁”（S Lock，允许多人同时读）。当你要修改一个 Tuple 时，你需要获取一个“排他锁”（X Lock，只允许你一个人修改）。

     • 日志: 你在书上做的所有笔记（数据修改），图书管理员都会在一个日志本上记录下来。万一图书馆突然停电（系统崩溃），管理员可以根据这个日志本恢复所有笔记，确保数据不丢失。

   • 关系: 所有对数据的操作都必须在一个事务（Transaction）的监督下进行。 SeqScanExecutor 在 Init 和 Next 中使用的 exec_ctx_->GetTransaction() 就是获取当前操作所属的事务。当 TableHeap 通过 BPM 拿到了一个 Page 准备读取时，它必须先代表当前事务去 LockManager 获取适当的锁。

Schema (模式)：表的“蓝图”或“登记表模板”

Schema 不是数据本身，而是对数据结构的描述。

想象一下，你要在图书馆建立一个学生档案系统。在录入任何学生信息之前，你首先要设计一张空白的登记表。这张表上会规定好有哪些栏目，以及每个栏目要填什么类型的信息：

栏目名称 (Column Name)	数据类型 (Data Type)	备注 (Constraints)
student_id	整数 (Integer)	唯一，4个字节长
student_name	字符串 (Varchar)	最长50个字符
gpa	小数 (Decimal)	2位小数

这张空白的表格模板，就是 Schema。

在 BusTub 的 C++ 代码中，一个 Schema 对象就是：

• 一个 Column 对象的列表（std::vector<Column>)。

• 每个 Column 对象包含了：

  • 列名 (e.g., "student_id")

  • 数据类型 (e.g., TypeId::INTEGER)

  • 长度（如果是变长类型）

  • ... 等其他元信息。

Schema 的作用是什么？

它的作用至关重要，体现在两个方面——写入和读取：

1. 序列化 (Serialization) - 写入时
   当你有一个 Tuple 对象（比如代表学生 Alice 的 (101, "Alice", 3.9))，并想把它存到磁盘的 Page 里时，你不能直接把 C++ 对象存进去。你需要把它转换成一串紧凑的二进制字节流。
   Schema 就是这个转换过程的规则手册：

   • 它告诉你 101 是个 INTEGER，应该转换成 4 个字节。

   • 它告诉你 "Alice" 是个 VARCHAR，应该存下它的长度（5），然后再存下 A-l-i-c-e 这 5 个字节。

   • 它告诉你 3.9 是个 DECIMAL，应该按特定格式转换成 8 个字节。
     最终，Tuple 对象 (101, "Alice", 3.9) 被 Schema 指导，变成了一串类似 [bytes_for_101][bytes_for_Alice][bytes_for_3.9] 的二进制数据，存入 Page。

2. 反序列化 (Deserialization) - 读取时
   反过来，当 TableHeap 从 Page 里读出了一串二进制字节时，它本身是毫无意义的。TableHeap 必须拿着 Schema 这个“模板”去解析它：

   • Schema 说：“前 4 个字节是一个 INTEGER”，于是 TableHeap 就把这 4 个字节翻译回整数 101。

   • Schema 说：“接下来是一个 VARCHAR”，于是 TableHeap 先读取长度，再读取相应数量的字节，翻译回字符串 "Alice"。

   • ...以此类推。
     通过这个过程，一堆无意义的字节就被重新构造成了一个有结构的、你可以在 C++ 代码里操作的 Tuple 对象。

小结：Schema 是连接逻辑 Tuple 对象和物理二进制存储的桥梁。

---

TableHeap：表的“物理书架集合”

TableHeap 是负责物理存储一张表所有元组（Tuples） 的模块。

1. 每个表都有一个 TableHeap 吗？

是的，绝对是。 每个表在逻辑上是独立的，所以在物理上，BusTub 会为每张表创建一个单独的 TableHeap 实例来管理它的数据。

• students 表有一个 TableHeap 实例，管理着所有学生元组。

• courses 表有另一个不同的 TableHeap 实例，管理着所有课程元组。

Catalog 就像是总索引，它维护着一个映射关系：table_oid -> TableInfo。而 TableInfo 对象里面就包含了指向该表唯一的那个 TableHeap 实例的指针。

2. TableHeap 是一个怎样的结构？

它不是一个 B+ 树或任何有序的索引结构。它的名字 "Heap"（堆）暗示了它的特点：数据是无序存放的。新来的数据会被塞到任何有空位的地方。

火山模型

想象一下，数据库的查询执行就像一个汽车装配流水线。

• 每个执行器 (Executor) 就像流水线上的一个工人。

• 每个工人只负责一个非常具体、简单的任务（装轮子、装引擎、喷漆）。

• 元组 (Tuple) 就像流水线上正在组装的汽车底盘。

• 数据从流水线的开端（读取磁盘的工人）流向末端（最终打包的工人），每个工人都对它进行一步加工。

火山模型的关键特点是，这是一个 “拉”模型 (Pull Model)。也就是说，流水线末端的工人（比如，最终要向你展示结果的那个）主动去要一个加工好的产品。这个请求会一直向流水线的前方传递，直到最开始的工人从仓库里拿出一个新的底盘。

这个“请求”的动作，就是调用子节点的 Next() 方法。

例子 SELECT

SELECT name FROM students WHERE gpa > 3.5;

[ProjectionExecutor]  (只保留 name 字段)
                  ^
                  |  (调用 child->Next() 来拉取元组)
                  |
           [FilterExecutor]     (只保留 gpa > 3.5 的元组)
                  ^
                  |
                  |
         [SeqScanExecutor]    (从 "students" 表中一条一条地读元组)

执行流程（当客户端请求第一条结果时）：

1. 你 (客户端) 调用最顶层 ProjectionExecutor 的 Next() 方法，说：“给我一条结果”。

2. ProjectionExecutor 说：“好的，但我手上没有元组。我需要从我的下游（我的 child）那里拿一个。” 于是它调用 FilterExecutor 的 Next()。

3. FilterExecutor 说：“我也没有元组，我得从我的 child 那里拿一个。” 于是它调用 SeqScanExecutor 的 Next()。

4. SeqScanExecutor 是流水线的起点。它去磁盘上读取 students 表的第一行记录。假设是 (id: 1, name: 'Alice', gpa: 4.0)。它把这个元组准备好，然后通过 return true 把它“递给”了 FilterExecutor。

5. FilterExecutor 拿到了 ('Alice', 4.0)。它的工作是检查 gpa > 3.5。4.0 > 3.5 是 true，所以这个元组通过了过滤。FilterExecutor 把它原封不动地“递给”了 ProjectionExecutor。

6. ProjectionExecutor 拿到了 ('Alice', 4.0)。它的工作是“投影”，也就是只保留 name 字段。它会创建一个新的元组 ('Alice')。

7. 最后，ProjectionExecutor 把这个最终结果 ('Alice') 返回给你（客户端）。

当客户端请求第二条结果时，会发生什么？

这个过程会重复。假设 SeqScanExecutor 读取的下一条记录是 (id: 2, name: 'Bob', gpa: 3.0)。

1. 请求一路向下传到 SeqScanExecutor，它返回 ('Bob', 3.0) 给 FilterExecutor。

2. FilterExecutor 拿到后，检查 gpa > 3.5。3.0 > 3.5 是 false！

3. 关键点来了：FilterExecutor 不会就此放弃。它不会把这个元组传上去，也不会返回 false（因为表里可能还有其他符合条件的元组）。它会在内部循环，再次调用 SeqScanExecutor->Next()，说：“这个不行，给我下一个”。

4. SeqScanExecutor 于是去读第三条记录，比如 (id: 3, name: 'Charlie', gpa: 3.8)。它把这个元组返回给 FilterExecutor。

5. FilterExecutor 检查 3.8 > 3.5，true！它终于找到了一个合格的元组，于是把它向上递给 ProjectionExecutor。

6. ProjectionExecutor 把它变成 ('Charlie')，然后返回给客户端。

这个过程一直持续，直到 SeqScanExecutor 读完了整张表，它的 Next() 方法返回 false。这个 false 会被逐层向上传递，最终客户端就知道没有更多结果了。

另一个例子 JOIN

SELECT s.name, c.cname
FROM students s JOIN courses c ON s.id = c.student_id;

				[ProjectionExecutor]
                        ^
                        |
            [NestedLoopJoinExecutor]
                   /           \
                  /             \  (有两个 child)
                 /               \
       [SeqScanExecutor]     [SeqScanExecutor]
       (scans "students")    (scans "courses")

NestedLoopJoinExecutor 的工作方式：

它内部有两个循环（一个外循环，一个内循环）。

1. 当 JoinExecutor::Next() 第一次被调用时，它会：
   a. 从它的左子节点 (students 扫描) 调用 Next()，获取第一名学生，比如 s1 = ('Alice', id: 1)。它会把 s1 存起来。
   b. 从它的右子节点 (courses 扫描) 调用 Next()，获取第一门课程，比如 c1 = ('DB', student_id: 1)。
   c. 检查 JOIN 条件 s1.id == c1.student_id (即 1 == 1)。匹配！
   d. 它将两者合并成一个新元组 ('Alice', 'DB')，然后返回。

2. 当 JoinExecutor::Next() 第二次被调用时，它会：
   a. 保持左边的元组 s1 不变。
   b. 从右子节点再次调用 Next()，获取下一门课程，比如 c2 = ('OS', student_id: 2)。
   c. 检查 JOIN 条件 s1.id == c2.student_id (即 1 == 2)。不匹配！
   d. 它会继续从右子节点获取元组，直到找到一个匹配的，或者右边的课程全部扫描完毕。

3. 当右边的 courses 表扫描完一遍后：
   a. JoinExecutor 会从左子节点调用 Next()，获取第二名学生，比如 s2 = ('Bob', id: 2)。
   b. 关键：它会重置右子节点的扫描，让它从头开始。
   c. 然后重复上面的过程，用 s2 去匹配 courses 表里的每一条记录。

这就是为什么它叫“嵌套循环连接”，火山模型通过 Next() 调用巧妙地实现了这个算法。

Insert executor

对于插入迭代器来说 只需要一个next执行一次即可
所以要设置一个之后再调用他 都直接返回 要想返回插入的数量 根据要求 也是要通过元组返回给父执行器的
所以使用

  std::vector<Value> result_values;
  result_values.emplace_back(Value(INTEGER, inserted_count_));
  *tuple = Tuple(result_values, &GetOutputSchema());
  returned_flag_ = true;
  return true;

RID到底是什么

在bustub中 RID 由 page_id 和 solt_id 构成
被table heap 用来定位具体的数据

auto [old_meta, old_tuple] = table_heap->GetTuple(child_rid);

1. Table Heap 使用 RID 找到具体位置

   • 根据 RID 中的 Page ID 找到对应页面
   • 根据 Slot Number 在页面内找到具体记录

2. 将数据加载到 Tuple 中

   • 从磁盘/内存中的物理存储位置读取数据
   • 将数据组织成 Tuple 格式，便于上层操作

Students 表 | id | name  | age | 
			|----|-------|-----| 
			| 1 | Alice  | 20 | <- RID 可能是 (Page1, Slot0) 
			| 2 | Bob    | 22 | <- RID 可能是 (Page1, Slot1) 
			| 3 | Carol  | 19 | <- RID 可能是 (Page2, Slot0)

Update executor

Delete executor

Index_scan_executor

Seq scan as Index scan

回顾一下查询的过程
parser->binder->planner

直接从语法上得出的查询计划可能不够快

// 优化前：全表扫描 + 过滤
Filter { predicate=(#0.0=1) }
  SeqScan { table=t1 }

// 优化后：直接索引扫描
IndexScan { index_oid=0, filter=(#0.0=1) }

这个优化器的作用就是把顺序查找变成索引查找

优化的种类

• 基于规则的优化 比如这就是一种规则 将顺序扫描转化成索引查找
• 基于成本的优化 可以通过估算不同查询计划产生的成本 来选择计划
• 动态规划

auto Optimizer::Optimize(const AbstractPlanNodeRef &plan) -> AbstractPlanNodeRef {
  if (force_starter_rule_) {
    // Use starter rules when `force_starter_rule_` is set to true.
    auto p = plan;
    p = OptimizeMergeProjection(p);
    p = OptimizeMergeFilterNLJ(p);
    p = OptimizeNLJAsIndexJoin(p);
    p = OptimizeOrderByAsIndexScan(p);
    p = OptimizeMergeFilterScan(p);
    p = OptimizeSeqScanAsIndexScan(p);
    return p;
  }
  // By default, use user-defined rules.
  return OptimizeCustom(plan);
}

从这个优化器的入口可以看出 bustub运用的是一种基于规则的优化 不断尝试这些优化规则 并且应用

常见优化规则包括：

1. 谓词下推(Predicate Pushdown)：将过滤条件下推到数据源，减少中间结果
2. 投影剪枝(Projection Pruning)：只选择需要的列，避免不必要的数据传输
3. 连接重排序(Join Reordering)：调整表连接顺序以减少计算量
4. 连接算法选择：决定使用嵌套循环连接、哈希连接还是排序合并连接

比如这个seqscan到indexscan的优化之前就有一部谓词下推的优化

// 优化前
Filter { predicate=(#0.0=1) }
  SeqScan { table=t1 }

// 经过 MergeFilterScan 优化后
SeqScan { table=t1, filter=(#0.0=1) }

以这个谓词下推代码为例

auto Optimizer::OptimizeMergeFilterScan(const AbstractPlanNodeRef &plan) -> AbstractPlanNodeRef {
  std::vector<AbstractPlanNodeRef> children;
  for (const auto &child : plan->GetChildren()) {
    children.emplace_back(OptimizeMergeFilterScan(child));
  }

  auto optimized_plan = plan->CloneWithChildren(std::move(children));

  if (optimized_plan->GetType() == PlanType::Filter) {
    const auto &filter_plan = dynamic_cast<const FilterPlanNode &>(*optimized_plan);
    BUSTUB_ASSERT(optimized_plan->children_.size() == 1, "must have exactly one children");
    const auto &child_plan = *optimized_plan->children_[0];
    if (child_plan.GetType() == PlanType::SeqScan) {
      const auto &seq_scan_plan = dynamic_cast<const SeqScanPlanNode &>(child_plan);
      if (seq_scan_plan.filter_predicate_ == nullptr) {
        return std::make_shared<SeqScanPlanNode>(filter_plan.output_schema_, seq_scan_plan.table_oid_,
                                                 seq_scan_plan.table_name_, filter_plan.GetPredicate());
      }
    }
  }

  return optimized_plan;
}

首先递归优化所有child 使得整个优化过程是自底向上进行的

如果当前节点是Filter 那么就执行优化：
如果孩子是seqscan 而且没有其他filter谓词的话 那么就返回一个新的节点
相当于丢弃了原来的filter 把谓词转移到新的seqscan里了

Aggregation executor

nested loop executor

SELECT s.name, c.cname
FROM students s JOIN courses c ON s.id = c.student_id;

				[ProjectionExecutor]
                        ^
                        |
            [NestedLoopJoinExecutor]
                   /           \
                  /             \  (有两个 child)
                 /               \
       [SeqScanExecutor]     [SeqScanExecutor]
       (scans "students")    (scans "courses")

NestedLoopJoinExecutor 的工作方式：

它内部有两个循环（一个外循环，一个内循环）。

1. 当 JoinExecutor::Next() 第一次被调用时，它会：
   a. 从它的左子节点 (students 扫描) 调用 Next()，获取第一名学生，比如 s1 = ('Alice', id: 1)。它会把 s1 存起来。
   b. 从它的右子节点 (courses 扫描) 调用 Next()，获取第一门课程，比如 c1 = ('DB', student_id: 1)。
   c. 检查 JOIN 条件 s1.id == c1.student_id (即 1 == 1)。匹配！
   d. 它将两者合并成一个新元组 ('Alice', 'DB')，然后返回。

2. 当 JoinExecutor::Next() 第二次被调用时，它会：
   a. 保持左边的元组 s1 不变。
   b. 从右子节点再次调用 Next()，获取下一门课程，比如 c2 = ('OS', student_id: 2)。
   c. 检查 JOIN 条件 s1.id == c2.student_id (即 1 == 2)。不匹配！
   d. 它会继续从右子节点获取元组，直到找到一个匹配的，或者右边的课程全部扫描完毕。

3. 当右边的 courses 表扫描完一遍后：
   a. JoinExecutor 会从左子节点调用 Next()，获取第二名学生，比如 s2 = ('Bob', id: 2)。
   b. 关键：它会重置右子节点的扫描，让它从头开始。
   c. 然后重复上面的过程，用 s2 去匹配 courses 表里的每一条记录。

External Merge Sort Executor

Phase 1: 生成有序段 (Sorted Runs)
+------------------+     +------------------+     +------------------+
| 读取一批元组      | --> | 内存中排序这些元组 | --> | 写入磁盘作为Run1 |
+------------------+     +------------------+     +------------------+

+------------------+     +------------------+     +------------------+
| 读取下一批元组    | --> | 内存中排序这些元组 | --> | 写入磁盘作为Run2 |
+------------------+     +------------------+     +------------------+

...

Phase 2: 多路归并
+--------+  +--------+       +----------------------+
| Run1   |  | Run2   |  ...  |                     |
+--------+  +--------       +----------------------+
    \         /                    |
     \       /              +--------------+
      多路归并  -----------> | 归并后的Run  |
                           +--------------+

class SortPage {
	public:
		void Init()
		auto AddTuple(Tuple tuple) -> bool;
		auto GetTuple(size_t index) -> Tuple;
		auto GetSize() -> size_t;
		void SetSize();
		static constexpr auto GetMaxSize() -> size_t;
	private:
		static constexpr size_t SORT_PAGE_HEADER_SIZE = sizeof(size_t);
		static constexpr size_t SORT_PAGE_DATA_SIZE = BUSTUB_PAGE_SIZE - SORT_PAGE_HEADER_SIZE;
		char data_[BUSTUB_PAGE_SIZE];
		auto GetSizePtr() -> size_t * {
			return reinterpret_cast<size_t *>(data_);
		}
		.... 
}

sort page类 对于这种page类型的使用char*明确页面大小 然后使用reinterpret cast来序列化与反序列化内容
同时 使用 static constexpr 来规定页面结构

class MergeSortRun {
	public:
		MergeSortRun();
		void AddPage();
		
		class Iterator {
			public:
				auto operator++() -> Iterator&;
				auto operator*() -> Tuple&;
			private:
				page_id_t cur_page_;
				size_t cur_idx_;
				const MergeSortRun *run_;
				std::optional<ReadPageGuard> page_guard_
		}
		auto begin() -> Iterator;
		auto end() -> Iterator;
		
	private:
		std::vector<page_id_t> pages_;
		BufferPoolManager *bpm_;

}

<template size_t k>
class MergeSortExecutor {
	public:
		void MergeSort();
	private:
		std::vector<MergeSortRun> runs_;
		BufferPoolManager* bpm_
}

<template size_t k>
auto MergeSortExecutor::

<template size_t k> // k way merge
void MergeSortExecutor::MergeSort() {
	std::vector<Tuple> InMemTuples;
	size_t tuple_size = child_executor_->GetOutputSchema().GetInlinedStorageSize();
	 
	size_t max_tuples_per_page = (BUSTUB_PAGE_SIZE - sizeof(size_t)) / tuple_size;
	while(GetData()) {
	InMemTuples.push_back(Data);	
	if(InMemTuple.size() == max_tuple_pre_page) {
		std::sort(inMemTuple.begin(), inMemTuple.end());
		auto new_sort_page_id = bpm_->NewPage();
		auto new_sort_page = bpm_->WritePage(new_sort_page_id).AsMut<SortPage>();
		
		for(const auto &tuple : inMemTuple) {
			new_sort_page->AddTuple(tuple);	
		}
		MergeSortRun cur_run;
		cur_run.AddPage(new_sort_page->GetPageId());
		runs_.push_back(std::move(cur_run));
		InMemTuples.clear();
		//call dtor of new sort page
	}	
	}
	if(!InMemTuples.empty()) {
		create last run
	}
	while(run_.size() > 1) {
		std::vector<MergeSortRun> Merged_runs;
		for(size_t i = 0; i < run_.size(); i += 2) {
			if(i + 1 >= runs_.size()) {
				merged_runs.push_back(std::move(run_[i]))；
				break;
			}
			auto new_run = MergeRuns(runs_[i], run_[i + 1]);
			merger_runs.push_back(new_run);
		}
		runs_ = std::move(merged_runs);
	}
	
}

![[Pasted image 20251121131635.png]]

P4 concurrency control

隔离级别 READ TIMESTAMP
事务在开始的时候 拍摄了一个快照 在他的生命周期中 看到的内容永远是食物开始时快照中的世界

补充：可能出现的异常：Anomalies

一、 读异常 (Read Anomalies)

这些问题发生在“读取数据”时，看到的状态不一致或不正确。

1. 脏读 (Dirty Read)

• 现象：T2 读到了 T1 修改但未提交的数据。如果 T1 后来回滚了（Abort），T2 拿到的就是废数据。
• 例子：
  • A 原本有 100 块。
  • T1 把 A 改成 200（未提交）。
  • T2 读 A，看到 200。
  • T1 出错回滚，A 变回 100。
  • T2 拿着 200 去做后续计算，全错了。
• Lab 4 处理：通过检查 Tuple 的时间戳。如果发现是临时时间戳（txn_id），且不是自己写的，绝对不读，要去 Undo Log 找上一个版本。

2. 不可重复读 (Non-repeatable Read) / 模糊读 (Fuzzy Read)

• 现象：在一个事务内，两次读取同一行数据，结果不一样。
• 例子：
  • T1 读取 A = 10。
  • T2 将 A 更新为 20 并提交。
  • T1 再次读取 A，变成了 20。
  • T1 困惑：“我还在同一个事务里，怎么世界变了？”
• Lab 4 处理：Snapshot Isolation (SI) 完美解决。T1 有固定的 Read TS。不管 T2 怎么改，T1 永远通过 Undo Log 重建出 Read TS 那个时刻的数据。

3. 幻读 (Phantom Read)

• 现象：在一个事务内，执行两次范围查询（如 SELECT count(*) FROM user WHERE age > 10），结果集的行数不一样。
• 例子：
  • T1 查 age > 10，返回 5 人。
  • T2 插入一个新用户，age = 15，并提交。
  • T1 再次查 age > 10，返回 6 人。
  • T1 困惑：“刚才明明只有 5 个，哪里冒出来的鬼影？”
• Lab 4 处理：标准的 SI 其实不能完全防止幻读（虽然你看不到新插入的行，但在写操作时可能会有问题）。在 Lab 4 中，通常不强求完全解决幻读，除非要求实现 Serializable。

4. 读偏斜 (Read Skew)

• 现象：这是 MVOCC 最想避免的问题。读取数据库的不一致快照。
• 例子：账户 A=100, B=100。总和应为 200。
  • T1 读取 A=100。
  • T2 将 A 转账 50 给 B（A=50, B=150），提交。
  • T1 读取 B=150。
  • T1 算总账：A(100) + B(150) = 250。多了 50 块！
• Lab 4 处理：有了 Commit TS 和 Read TS，T1 读 B 时会发现 B 的 Commit TS 比自己的 Read TS 新，于是回溯 Undo Log 找到 B=100 的旧版本。T1 最终读到 A=100, B=100。

---

二、 写异常 (Write Anomalies)

这些问题发生在“写入数据”时，导致数据丢失或逻辑破坏。

1. 丢失更新 (Lost Update)

• 现象：两个事务同时读写同一行，后一个写的覆盖了前一个写的。
• 例子：计数器 X=10。
  • T1 读 X=10，计算 X+1。
  • T2 读 X=10，计算 X+1。
  • T1 写回 X=11。
  • T2 写回 X=11。
  • 结果应该是 12，却变成了 11。T1 的工作白做了。
• Lab 4 处理：原子检测。在 Update 时，通过 CAS (Compare-And-Swap) 或者检查版本号。如果 T2 写的时候发现版本已经变了（或者被 T1 锁住了），T2 必须 Abort（重试）。这是“乐观并发控制”的核心。

2. 写偏斜 (Write Skew) —— 最隐蔽的杀手

• 现象：两个事务分别修改不同的对象，但破坏了这些对象之间的联合约束。
• 例子：医院值班系统。约束是“至少要有一个医生值班”。现在 Alice 和 Bob 都在值班。
  • T1 (Alice): 查询当前值班人数 -> 2人。没事，我可以请假。更新 Alice=不值班。
  • T2 (Bob): 查询当前值班人数 -> 2人。没事，我可以请假。更新 Bob=不值班。
  • T1 提交。T2 提交。
  • 结果：没医生值班了！
• 为什么难搞：T1 改的是 Alice 的记录，T2 改的是 Bob 的记录。他们没有修改同一行，所以通常的行锁（Row Lock）或版本检测（Version Check）检测不到冲突。

![[Pasted image 20251122163809.png]]
对于每一个事务 都有一个开始时间戳 比如 T1在时间戳2开始 那么他只能看到 A2 B1 C2状态的元组
对于每一个事务 还有一个提交时间戳 决定了事务的序列化顺序（单调递增）也可以唯一地标识已经提交的事务 比如版本链中ts = 3 就是代表事务3提交的时间
在table heap中 维护一个版本链

几个概念

TS (Timestamp / 时间戳)

• 是什么： 它不仅仅是时间，更像是一个逻辑上的“计数器”或“版本号”。
• 作用： 用来标记数据的版本和事务的先后顺序。
  • 0, 1, 2, 3... 随着事务的提交不断增加。
• 在事务中：
  • read_ts_ (读取时间戳)：事务开始时，系统当前的全局时间。事务只能看到这个时间点之前已经提交的数据（快照）。
  • commit_ts_ (提交时间戳)：事务结束并提交时，获取的一个新的、更大的时间戳。这标志着这个事务产生的新数据版本的“出生时间”。

Txn (Transaction / 事务)

• 是什么： 数据库操作的执行单元（比如 T1, T2）。
• 结构： 每个 Txn 对象（Transaction 类）都包含：
  • txn_id_: 唯一标识符。
  • read_ts_: 它的“视野”范围（我看的是几点钟的数据）。
  • commit_ts_: 它完成的时间（我把数据更新到了几点钟的版本）。
  • Undo Log: 用于回滚操作。

Watermark (水位线)

• 是什么： 它记录了当前所有正在运行的事务中，最小的 read_ts。
• 作用： 它是垃圾回收（Garbage Collection, GC） 的依据。
• 通俗理解： 想象大家都在看一本不断更新的历史书。
  • 事务 A 在看第 100 页（read_ts=100）。
  • 事务 B 在看第 105 页（read_ts=105）。
  • 虽然现在书已经写到第 110 页了，但如果把第 100 页撕掉，事务 A 就没法读了。
  • Watermark 就是 100。意思是：“第 100 页及以后的内容都有人在看，绝对不能删（不能回收旧版本）”。一旦事务 A 结束，Watermark 可能会变成 105，那么 100 到 104 之间的旧版本数据就可以被清理了。

class watermark

只有两个方法 一个是add 一个是 remove
分别代表 某个在read_ts的事务开始了 那个在read_ts的事务结束了
会对应在map里面记录在read_ts工作的事务有几个 如果最低的read_ts事务结束了 就提高watermark 告诉垃圾回收模块 之前的都可以回收了 因为目前所有事物的read_ts都大于等于这个时刻 所以之前的快照是没用的

Task2

BusTub 的存储方式是 "Delta Storage" (增量存储)。

• Table Heap (堆表)：永远只存最新版本的数据（Base Tuple）
• Undo Log (回滚日志)：存储旧版本的数据（Delta）
• Version Chain (版本链)：通过链表将最新数据和旧版本日志连起来。

Task 2 的核心目标是： 实现“时间旅行”。
既然堆表里只有“最新”的数据，如果一个老事务（Read Timestamp 较小）来读数据，它不能读最新的，它必须通过回滚日志，把数据“还原”成它那个时间点应该看到的样子

1. Tuple (In Table Heap)

   • 这是完整的行数据。
   • 包含 TupleMeta：
     • ts_ (Timestamp): 这行数据是何时被提交的？或者被哪个活跃事务锁定的？
     • is_deleted_: 是否被删除了。

2. UndoLink (The Pointer)

   • Table Heap 的每一行都有一个隐藏的指针（VersionUndoLink），指向最新的那条 Undo Log。
   • 结构：{ prev_txn_: txn_id, prev_log_idx_: index }。这就像一个座标，告诉你在哪个事务的 Buffer 里，第几条日志是它的上一个版本。

3. Undo Log (The Delta)

   • 存放在 TransactionManager (也就是事务的私有空间) 里，而不是堆表里。
   • 内容：它不是完整的 Tuple，它只包含被修改的字段 (Partial Update)。
   • 结构：
     • modified_fields_: 一个布尔数组，标记哪些列被修改了。
     • tuple_: 只有被修改列的值。
     • ts_: 这个旧版本原本的时间戳。

Task 2.2

原来我们的顺序扫描执行器直接返回TableHeap中的对应RID位置的数据 但是由于READ TIMESTAMP隔离策略 堆表中的数据是最新的 可对于一个事务来说 他应该只能看到readts这个时刻的快照。 因此要返回task2.1实现的 根据undolog重建以后的tuple

TupleMeta.ts_ 是一个 int64_t（64位整数）。系统把这 64 位划分成了两个范围，通过一个巨大的常量 TXN_START_ID 来分割。
可以把 ts_ 看作一个状态指示灯：

• 情况 A：已提交数据 (Committed)
  • 数值范围：0 到 TXN_START_ID - 1。
  • 含义：这是一个正常的时间戳（Read/Commit Timestamp）。
  • 解读：这行数据已经在时刻 ts_ 提交了，任何人只要读的时间戳 >= ts_ 都能看到它。
• 情况 B：未提交数据 (Uncommitted / In-progress)
  • 数值范围：>= TXN_START_ID。
  • 含义：这是一个事务 ID（加上了标志位）。
  • 解读：这行数据正在被某个活跃的事务修改，还没有提交！它是“脏”的。

TXN_START_ID 是 1 << 62（或者类似的最高位标志）。
当我们说 ts_ = TXN_START_ID + 5 时，意思是：

• 标志位（最高位）是 1 -> 表示“正在被锁定/修改”。
• 低位 是 5 -> 表示“是被 Txn #5 锁定的”。

这个任务中最重要的是重建tuple的逻辑 当我拿到一个table heap中的tuple的时候。发现他的timestamp更新一点 我就需要根据undolog去重现旧版本（read_ts）快照的时候这个tuple的样子 用于这个事务

struct UndoLink {
  /* Previous version can be found in which txn */
  txn_id_t prev_txn_{INVALID_TXN_ID};
  /* The log index of the previous version in [prev_txn_](file:///root/bustub-private/src/include/concurrency/transaction.h#L58-L58) */
  int prev_log_idx_{0};
}

其实这个结构非常简单 undolog是存放在txn自己的结构里的 一个vector 所以只需要记住前一个修改这个元组的事务是什么 并且存放在他的第几个undolog中 就可以还原这一个版本

struct UndoLog {
  /* Whether this log is a deletion marker */
  bool is_deleted_;
  /* The fields modified by this undo log */
  std::vector<bool> modified_fields_;
  /* The modified fields */
  Tuple tuple_;
  /* Timestamp of this undo log */
  timestamp_t ts_{INVALID_TS};
  /* Undo log prev version */
  UndoLink prev_version_{};  // <-- 这就是指向下一级的链接
};

对于一个UndoLog来说 他存放isdelete标记位 用于标记是否删除 这样在重建的时候 可以只修改这个标志位 可以看出 这个log里面包括了一个link结构 所以可以根据这个link 找到上一个修改这个元组的事务和他的undolog 最后直到遍历到isvalid是false 也就是 该undolog中的undolink记录的prev_txn == INVALID_TXN 的 代表我们完成了整个遍历过程

一、数据库总架构

BusTub是一个模块化的关系型数据库管理系统，采用分层设计架构，主要包含以下核心组件：

1. 前端处理层

• Binder：负责SQL语句的解析和绑定，将SQL文本转换为抽象语法树(AST)
• Planner：基于AST生成初始查询执行计划
• Optimizer：对查询计划进行优化，生成最优执行计划

2. 执行引擎层

• Execution：执行优化后的查询计划，协调各组件完成数据操作
• Concurrency：提供并发控制机制，确保事务的ACID特性
• Recovery：实现事务恢复机制，保证系统故障时的数据一致性

3. 存储引擎层

• Storage：负责数据的物理存储和访问
  • Table：表结构的实现，包括TableHeap和Tuple
  • Index：索引结构的实现，如B+树索引、哈希表索引等
• Buffer：缓冲池管理器，减少磁盘I/O，提高系统性能
• Catalog：元数据管理器，负责表和索引的创建、查找和管理

4. 基础组件层

• Common：通用工具和配置
• Type：数据类型系统
• Container：容器类实现
• Page：页面管理，包括表页面、索引页面等

二、SQL执行流程

SQL语句在BusTub中的执行遵循以下步骤：

1. SQL解析与绑定 (Binder)

• 接收用户输入的SQL语句
• 进行词法分析和语法分析，生成抽象语法树(AST)
• 绑定表、列等元数据信息到AST节点
• 进行语义检查，确保SQL语句的合法性

2. 查询计划生成 (Planner)

• 基于绑定后的AST生成初始查询执行计划
• 将SQL操作转换为一系列可执行的操作符，如扫描、连接、聚合等
• 构建操作符树，表示操作的执行顺序和依赖关系

3. 查询优化 (Optimizer)

• 对初始查询计划进行优化，生成最优执行计划
• 考虑多种执行策略，如全表扫描 vs 索引扫描
• 优化连接顺序和连接算法
• 应用谓词下推等优化技术

4. 执行计划执行 (Execution)

• 按照优化后的执行计划执行操作
• 调用存储引擎层的接口访问数据
• 处理并发控制和事务管理
• 收集执行结果并返回给用户

5. 数据访问 (Storage)

• 执行实际的数据读写操作
• 利用缓冲池减少磁盘I/O
• 管理数据的物理存储结构
• 维护索引结构，加速数据查找

三、Catalog、Table、TableHeap的关系

1. Catalog

• 作用：作为元数据管理器，负责表和索引的创建、查找和管理
• 核心数据结构：
  • tables_：映射表OID到TableInfo
  • table_names_：映射表名到表OID
  • indexes_：映射索引OID到IndexInfo
  • index_names_：映射表名和索引名到索引OID
• 核心方法：
  • CreateTable：创建新表并返回表元数据
  • GetTable：根据表名或OID获取表元数据
  • CreateIndex：创建新索引并返回索引元数据
  • GetIndex：获取索引元数据

2. TableInfo

• 作用：维护表的元数据信息
• 核心成员：
  • schema_：表的模式定义
  • name_：表名
  • table_：指向TableHeap的唯一指针
  • oid_：表的唯一标识符

3. TableHeap

• 作用：表示磁盘上的物理表，管理实际的数据存储
• 结构：
  • 是一个双向链表结构的页面集合
  • 每个页面是一个TablePage实例
  • 管理表的所有元组数据
• 核心方法：
  • InsertTuple：插入新元组
  • UpdateTuple：更新元组
  • GetTuple：读取元组
  • MakeIterator：创建表迭代器

4. 关系总结

Catalog → TableInfo → TableHeap → TablePage → Tuple

• Catalog管理多个TableInfo
• 每个TableInfo对应一个TableHeap
• 每个TableHeap包含多个TablePage
• 每个TablePage存储多个Tuple

四、数据在内存中的组织：Slot模型

BusTub采用Slotted Page（槽式页面）模型来组织内存中的数据，具体结构如下：

1. 页面布局

---------------------------------------------------------
| HEADER | ... FREE SPACE ... | ... INSERTED TUPLES ... |
---------------------------------------------------------
                              ^
                              free space pointer

2. 头部结构 (8字节)

----------------------------------------------------------------------------
| NextPageId (4)| NumTuples(2) | NumDeletedTuples(2) |
----------------------------------------------------------------------------
----------------------------------------------------------------
| Tuple_1 offset+size (4) | Tuple_2 offset+size (4) | ... |
----------------------------------------------------------------

3. 元组格式

| meta | data |

• meta：元组的元数据，如可见性、删除标记等
• data：元组的实际数据

4. Slot模型特点

• 动态空间管理：通过free space pointer管理页面中的自由空间
• 高效元组访问：通过元组信息数组快速定位元组位置
• 支持可变长度元组：每个元组的大小可以不同
• 处理元组删除：通过标记删除，而非立即回收空间
• 空间复用：删除的元组空间可以被新元组复用

5. 元组操作

• 插入：从页面尾部向前分配空间，更新元组信息数组
• 读取：根据RID（记录标识符）定位到页面和槽位，读取元组数据
• 更新：可以原地更新（如果空间足够）或删除后插入新位置
• 删除：标记元组为删除状态，更新NumDeletedTuples计数

五、执行流程示例

以一个简单的SQL查询为例，展示其执行流程：

1. SQL语句：SELECT * FROM students WHERE id = 100;

2. 解析与绑定：

   • Binder解析SQL，生成AST
   • 绑定students表和id列的元数据

3. 计划生成：

   • Planner生成初始计划：全表扫描students表，过滤id=100的记录

4. 优化：

   • Optimizer发现id列有索引，将计划优化为：使用索引查找id=100的记录

5. 执行：

   • Execution执行优化后的计划
   • 通过Catalog获取students表的TableInfo
   • 通过TableInfo获取TableHeap
   • 使用索引定位到id=100的元组所在的页面和槽位
   • 从TablePage中读取元组数据
   • 返回查询结果给用户

火山模型执行器

火山模型（Volcano Model），也被称为迭代器模型（Iterator Model） 或管线模型（Pipeline Model），是数据库执行引擎中最经典的模型。

理解火山模型，最核心的一句话是：“自顶向下调用，自底向上返回。”

---

1. 核心概念：树状结构

在一个 SQL 查询中，执行器会被组织成一棵树（Plan Tree）。

• 叶子节点：通常是数据源，比如 SeqScanExecutor（全表扫描）。
• 中间节点：处理逻辑，比如 FilterExecutor（过滤）、JoinExecutor（连接）。
• 根节点：最上层的执行器。

每个执行器都必须实现两个核心接口：Init() 和 Next()。

---

2. 详解 Init()：准备工作

Init() 相当于 “铺设管道”。在正式开始拉取数据前，所有的初始化工作都在这里完成。

在代码中：

void SeqScanExecutor::Init() {
  // 1. 从 Catalog（元数据管理器）获取表的信息
  const auto table_oid = plan_->GetTableOid();
  table_info_ = exec_ctx_->GetCatalog()->GetTable(table_oid);
  
  // 2. 初始化迭代器：把“指针”指向表的开头
  table_iterator_ = std::make_shared<TableIterator>(table_info_->table_->MakeIterator());
}

重点： Init() 只执行一次。它并不读取实际的数据行，只是把扫描器摆在表的起始位置，准备开始。

---

3. 详解 Next()：单行处理

Next() 是火山模型的灵魂。它的规则是：每次被调用，只返回一行数据（Tuple）。

如果父节点需要 100 行数据，它就会调用子节点的 Next() 100 次。

在SeqScanExecutor::Next 代码中，逻辑如下：

1. 循环查找：while (!table_iterator_->IsEnd())。
2. 多版本并发控制 (MVCC) 处理：
   • 数据库不一定直接读原始数据。由于事务的存在，代码里有复杂的 GetTupleAndUndoLink 和 ReconstructTuple。
   • 它在判断：“当前事务是否有权看到这一行数据？”。
   • 如果数据是别人正在修改的（不可见），它会通过 UndoLog 重构出旧版本的数据。
3. 谓词过滤（Filter Predicate）：

   if (plan_->filter_predicate_ == nullptr || 
       plan_->filter_predicate_->Evaluate(...)) {
       *tuple = res_tuple.value();
       return true; // 找到了符合条件的一行，立即返回
   }

4. 移动指针：++(*table_iterator_)。

为什么 Next 里面有个 while 循环？
因为当前行可能被删除、不可见、或者不符合 WHERE 条件。如果当前行不合适，Next 不能直接返回 false，它必须继续往后找，直到找到第一行符合要求的记录并返回 true，或者直到表结束返回 false。

---

4. 整个执行流程是怎么跑起来的？

假设有一个查询：SELECT name FROM users WHERE age > 18 LIMIT 2;

执行器树长这样：
LimitExecutor -> ProjectionExecutor -> FilterExecutor -> SeqScanExecutor

执行顺序：

1. Init 阶段（自顶向下）：

   • Limit 调用 Projection 的 Init。
   • Projection 调用 Filter 的 Init。
   • Filter 调用 SeqScan 的 Init。
   • 此时，所有执行器都准备好了，SeqScan 的迭代器指向了表的第一行。

2. Next 阶段（数据流自底向上）：

   • Limit 向 Projection 要一行数据。
   • Projection 向 Filter 要一行数据。
   • Filter 向 SeqScan 要一行数据。
   • SeqScan 从磁盘/内存读出 Row 1，交给 Filter。
   • Filter 检查 age > 18：
     • 如果不符合，Filter 会再次调用 SeqScan.Next() 获取 Row 2。
     • 如果符合，返回给 Projection。
   • Projection 裁剪掉不需要的列，只留 name，返回给 Limit。
   • Limit 计数 +1。

3. 循环：

   • Limit 发现还没攒够 2 行，于是重复上述过程。
   • 一旦 Limit 拿到了 2 行，它在下一次被调用时会直接返回 false，整棵树停止运行。

---

5. 火山模型的优缺点

优点：

1. 内存占用低：内存里通常只存一行数据。即使表有 100G，也可以一行行处理。
2. 灵活性高：每个执行器只关心自己的逻辑（Filter 只管过滤，Limit 只管计数），互相解耦。
3. 支持流式处理：不需要等所有数据处理完就可以开始产生结果。

缺点（BusTub 中可能会遇到的）：

1. 虚函数调用开销：每一行数据都要触发多次 Next() 虚函数调用。对于简单查询，这种开销占 CPU 的很大比例。
2. CPU 缓存不友好：每次只处理一行，无法利用 CPU 的 SIMD 指令或高速缓存预取。

具体执行器实现

1. 顺序扫描执行器 (SeqScanExecutor)

Init方法

void SeqScanExecutor::Init() {
  const auto table_oid = plan_->GetTableOid();
  table_info_ = exec_ctx_->GetCatalog()->GetTable(table_oid);
  if (table_info_ == nullptr) {
    throw Exception(ExceptionType::INVALID, "table_oid is invalid");
  }
  table_iterator_ = std::make_shared<TableIterator>(table_info_->table_->MakeIterator());
}

功能：

• 获取表的OID
• 从Catalog中获取表信息
• 初始化表迭代器，准备遍历表中的元组

Next方法

auto SeqScanExecutor::Next(Tuple *tuple, RID *rid) -> bool {
  auto *txn = exec_ctx_->GetTransaction();
  auto *txn_mgr = exec_ctx_->GetTransactionManager();
  auto read_ts = txn->GetReadTs();
  while (!table_iterator_->IsEnd()) {
    auto rid_val = table_iterator_->GetRID();
    auto [meta, tpl, undo_link] = GetTupleAndUndoLink(txn_mgr, table_info_->table_.get(), rid_val);
    std::optional<Tuple> res_tuple = std::nullopt;
    bool is_own_modification = (meta.ts_ >= TXN_START_ID && (meta.ts_ ^ TXN_START_ID) == txn->GetTransactionId());
    if (meta.ts_ <= read_ts || is_own_modification) {
      if (!meta.is_deleted_) {
        res_tuple = tpl;
      } else {
        res_tuple = std::nullopt;
      }
    } else {
      auto undo_logs = CollectUndoLogs(table_iterator_->GetRID(), meta, tpl, undo_link, txn, txn_mgr);
      if (undo_logs.has_value()) {
        res_tuple = ReconstructTuple(&table_info_->schema_, tpl, meta, undo_logs.value());
      } else {
        res_tuple = std::nullopt;
      }
    }

    ++(*table_iterator_);
    if (res_tuple.has_value()) {
      if (plan_->filter_predicate_ == nullptr ||
          plan_->filter_predicate_->Evaluate(&(res_tuple.value()), table_info_->schema_).GetAs<bool>()) {
        *tuple = res_tuple.value();
        *rid = rid_val;
        return true;
      }
    }
  }
  return false;
}

功能：

• 获取当前事务和事务管理器
• 遍历表中的元组，直到找到符合条件的元组或遍历结束
• 处理事务可见性，确保只返回符合隔离级别的元组
• 应用过滤条件（如果有）
• 返回符合条件的元组和RID

2. 过滤执行器 (FilterExecutor)

Init方法

void FilterExecutor::Init() {
  // Initialize the child executor
  child_executor_->Init();
}

功能：

• 初始化子执行器

Next方法

auto FilterExecutor::Next(Tuple *tuple, RID *rid) -> bool {
  auto filter_expr = plan_->GetPredicate();

  while (true) {
    // Get the next tuple
    const auto status = child_executor_->Next(tuple, rid);

    if (!status) {
      return false;
    }

    auto value = filter_expr->Evaluate(tuple, child_executor_->GetOutputSchema());
    if (!value.IsNull() && value.GetAs<bool>()) {
      return true;
    }
  }
}

功能：

• 从子执行器获取元组
• 应用过滤条件
• 只返回满足过滤条件的元组

3. 投影执行器 (ProjectionExecutor)

Init方法

void ProjectionExecutor::Init() {
  // Initialize the child executor
  child_executor_->Init();
}

功能：

• 初始化子执行器

Next方法

auto ProjectionExecutor::Next(Tuple *tuple, RID *rid) -> bool {
  Tuple child_tuple{};

  // Get the next tuple
  const auto status = child_executor_->Next(&child_tuple, rid);

  if (!status) {
    return false;
  }

  // Compute expressions
  std::vector<Value> values{};
  values.reserve(GetOutputSchema().GetColumnCount());
  for (const auto &expr : plan_->GetExpressions()) {
    values.push_back(expr->Evaluate(&child_tuple, child_executor_->GetOutputSchema()));
  }

  *tuple = Tuple{values, &GetOutputSchema()};

  return true;
}

功能：

• 从子执行器获取元组
• 计算投影表达式的值
• 构建并返回投影后的新元组

4. 哈希连接执行器 (HashJoinExecutor)

Init方法

void HashJoinExecutor::Init() {
  left_executor_->Init();
  right_executor_->Init();

  // Build phase: read left table and build hash table
  Tuple tuple;
  RID rid;
  while (left_executor_->Next(&tuple, &rid)) {
    // Calculate join key
    std::vector<Value> values;
    for (const auto &expr : plan_->LeftJoinKeyExpressions()) {
      values.push_back(expr->Evaluate(&tuple, left_executor_->GetOutputSchema()));
    }
    AggregateKey join_key{values};

    // Insert into hash table
    if (ht_.find(join_key) == ht_.end()) {
      ht_.insert({join_key, std::vector<Tuple>()});
    }
    ht_[join_key].push_back(tuple);
  }

  // Reset state
  current_right_tuple_ = nullptr;
  right_idx_ = 0;
  left_idx_ = 0;
  left_ht_iterator_ = ht_.begin();
  left_unmatched_idx_ = 0;
}

功能：

• 初始化左右子执行器
• 构建哈希表：遍历左表所有元组，计算连接键，插入哈希表
• 重置状态变量

Next方法

auto HashJoinExecutor::Next(Tuple *tuple, RID *rid) -> bool {
  const Schema *left_schema = &left_executor_->GetOutputSchema();
  const Schema *right_schema = &right_executor_->GetOutputSchema();
  const Schema *output_schema = &GetOutputSchema();

  while (true) {
    // If we're currently processing a right tuple
    if (current_right_tuple_ != nullptr) {
      // Compute right table join key
      std::vector<Value> values;
      for (const auto &expr : plan_->RightJoinKeyExpressions()) {
        values.push_back(expr->Evaluate(current_right_tuple_, *right_schema));
      }
      AggregateKey join_key{values};

      // Look for matching entries in hash table
      auto it = ht_.find(join_key);
      if (it != ht_.end()) {
        const std::vector<Tuple> &left_tuples = it->second;

        // Still have unprocessed left tuples
        if (left_idx_ < left_tuples.size()) {
          const Tuple &left_tuple = left_tuples[left_idx_];

          // Mark left tuple as matched (for LEFT JOIN)
          if (plan_->GetJoinType() == JoinType::LEFT) {
            matched_left_tuples_.insert(&left_tuple);
          }

          // Construct output tuple
          std::vector<Value> output_values;
          for (uint32_t i = 0; i < left_schema->GetColumnCount(); i++) {
            output_values.push_back(left_tuple.GetValue(left_schema, i));
          }
          for (uint32_t i = 0; i < right_schema->GetColumnCount(); i++) {
            output_values.push_back(current_right_tuple_->GetValue(right_schema, i));
          }

          *tuple = Tuple(output_values, output_schema);
          left_idx_++;
          return true;
        }
      } else if (plan_->GetJoinType() == JoinType::LEFT) {
        // For LEFT JOIN, when there's no matching left tuple, we skip this right tuple
        current_right_tuple_ = nullptr;
        left_idx_ = 0;
        continue;
      }

      // Done processing current right tuple
      current_right_tuple_ = nullptr;
      left_idx_ = 0;
    }

    // Get next right table tuple
    Tuple new_tuple;
    RID new_rid;
    if (!right_executor_->Next(&new_tuple, &new_rid)) {
      // Right table fully processed
      // For left join, process unmatched left tuples
      if (plan_->GetJoinType() == JoinType::LEFT) {
        // Iterate through all hash table entries
        while (left_ht_iterator_ != ht_.end()) {
          const std::vector<Tuple> &left_tuples = left_ht_iterator_->second;

          // Iterate through all left tuples for this key
          while (left_unmatched_idx_ < left_tuples.size()) {
            const Tuple &left_tuple = left_tuples[left_unmatched_idx_];

            if (matched_left_tuples_.find(&left_tuple) == matched_left_tuples_.end()) {
              std::vector<Value> output_values;
              for (uint32_t i = 0; i < left_schema->GetColumnCount(); i++) {
                output_values.push_back(left_tuple.GetValue(left_schema, i));
              }
              for (uint32_t i = 0; i < right_schema->GetColumnCount(); i++) {
                output_values.push_back(ValueFactory::GetNullValueByType(right_schema->GetColumn(i).GetType()));
              }

              *tuple = Tuple(output_values, output_schema);
              left_unmatched_idx_++;
              return true;
            }
            left_unmatched_idx_++;
          }

          ++left_ht_iterator_;
          left_unmatched_idx_ = 0;
        }
      }
      return false;
    }

    // Process the new right tuple
    right_tuple_buffer_.push_back(new_tuple);
    current_right_tuple_ = &right_tuple_buffer_.back();
    right_idx_ = right_tuple_buffer_.size() - 1;
    left_idx_ = 0;
  }
}

功能：

• 探测阶段：遍历右表元组，计算连接键，在哈希表中查找匹配项
• 构建连接后的元组
• 处理左外连接的情况，返回未匹配的左表元组

5. 聚合执行器 (AggregationExecutor)

Init方法

void AggregationExecutor::Init() {
  child_executor_->Init();

  // Clear the hash table before re-populating
  aht_.Clear();

  bool has_result = false;

  // Build the aggregation hash table
  Tuple tuple;
  RID rid;
  while (child_executor_->Next(&tuple, &rid)) {
    auto agg_key = MakeAggregateKey(&tuple);
    auto agg_val = MakeAggregateValue(&tuple);
    aht_.InsertCombine(agg_key, agg_val);
    has_result = true;
  }

  // Handle special case for empty input
  // If there is no group by and no data, we need to add a default aggregation result
  if (!has_result && plan_->GetGroupBys().empty()) {
    aht_.InsertDefaultAggregation();
  }

  aht_iterator_ = aht_.Begin();
}

功能：

• 初始化子执行器
• 清空并重新构建聚合哈希表
• 处理空输入的特殊情况
• 初始化聚合结果迭代器

Next方法

auto AggregationExecutor::Next(Tuple *tuple, RID *rid) -> bool {
  // 检查是否还有聚合结果
  if (aht_iterator_ == aht_.End()) {
    return false;
  }

  // 构造结果元组
  std::vector<Value> values;

  // 添加GROUP BY列的值
  const auto &agg_key = aht_iterator_.Key();
  for (const auto &key_val : agg_key.group_bys_) {
    values.push_back(key_val);
  }

  // 添加聚合列的值
  const auto &agg_val = aht_iterator_.Val();
  for (const auto &val : agg_val.aggregates_) {
    values.push_back(val);
  }

  *tuple = Tuple(values, &GetOutputSchema());
  ++aht_iterator_;

  return true;
}

功能：

• 遍历聚合哈希表中的结果
• 构建并返回聚合后的元组

执行优化器

1.投影合并优化 (OptimizeMergeProjection)

• 工作原理 ：合并连续的、执行相同投影操作的投影节点
• 优化条件 ：列类型相同，投影表达式为直接列引用
• 应用场景 ： SELECT * 查询、重命名列的查询

2. 过滤条件合并到嵌套循环连接 (OptimizeMergeFilterNLJ)

• 工作原理 ：将过滤条件合并到嵌套循环连接中
• 优化条件 ：过滤节点的子节点是嵌套循环连接，且连接谓词为恒真
• 应用场景 ：交叉连接后跟随过滤的查询

3. 嵌套循环连接转哈希连接 (OptimizeNLJAsHashJoin)

• 工作原理 ：将嵌套循环连接转换为哈希连接
• 优化条件 ：连接类型为INNER或LEFT，存在等值连接条件
• 应用场景 ：等值连接查询

4. 嵌套循环连接转索引连接 (OptimizeNLJAsIndexJoin)

• 工作原理 ：利用索引加速连接操作
• 优化条件 ：连接条件为等值比较，右表有索引
• 应用场景 ：连接列上有索引的查询

5. 消除恒真过滤条件 (OptimizeEliminateTrueFilter)

• 工作原理 ：移除总是为真的过滤条件
• 优化条件 ：过滤条件为恒真（如 1=1 ）
• 应用场景 ：包含冗余条件的查询

6. 过滤条件合并到扫描操作 (OptimizeMergeFilterScan)

• 工作原理 ：将过滤条件合并到顺序扫描中
• 优化条件 ：过滤节点的子节点是顺序扫描，且无过滤条件
• 应用场景 ：带WHERE子句的查询

7. 排序操作转索引扫描 (OptimizeOrderByAsIndexScan)

• 工作原理 ：利用索引的有序性避免显式排序
• 优化条件 ：排序为升序，排序列上有索引
• 应用场景 ：带ORDER BY子句的查询

8. 顺序扫描转索引扫描 (OptimizeSeqScanAsIndexScan)

• 工作原理 ：利用索引加速等值查询
• 优化条件 ：存在等值过滤条件，对应列有索引
• 应用场景 ：带等值条件的查询

9. 列剪枝优化 (OptimizeColumnPruning)

• 工作原理 ：移除不需要的列，减少数据传输
• 优化条件 ：执行计划中包含投影节点
• 应用场景 ：只需要部分列的查询

10. 排序+限制转TopN优化 (OptimizeSortLimitAsTopN)

• 工作原理 ：将排序+限制转换为TopN操作
• 优化条件 ：限制节点的子节点是排序节点
• 应用场景 ：带ORDER BY和LIMIT的查询

ARIES

---

1. 核心思想与目的 (The Big Picture)

想象一下你在写一篇非常重要的论文，突然电脑断电了。

• 原子性 (Atomicity) 挑战：你可能只写完了一半的句子。重启后，这个半成品句子必须被删掉，恢复到你写它之前的样子。
• 持久性 (Durability) 挑战：在你断电前，你可能已经点击了“保存”并看到了确认提示。重启后，这部分内容必须完好无损地存在。

数据库面临同样的问题。ARIES 的核心目标就是，无论系统何时以何种方式崩溃（断电、软件Bug等），重启后都能快速恢复到一个逻辑一致的状态，即：

• 所有已提交 (Committed) 事务的修改都必须永久生效。
• 所有未提交 (Aborted/Unfinished) 事务的修改都必须被完全撤销，就像从未发生过一样。

ARIES 的核心思想非常优雅，可以总结为三个词：

1. 预写日志 (Write-Ahead Logging - WAL)：在修改磁盘上的数据页之前，必须先将描述这个修改的“日志”写入磁盘。日志是不可篡改的证据。
2. 重复历史 (Repeating History)：恢复时，我们不关心磁盘上的数据页现在是什么鬼样子。我们相信日志，并从一个已知的安全点（检查点）开始，把日志里记录的所有操作原封不动地重做一遍。这会把系统恢复到崩溃前的瞬间状态，但这个状态是“脏”的（包含了未提交事务的修改）。
3. 撤销失败者 (Undoing Losers)：在恢复到崩溃前的瞬间状态后，我们再回头看，哪些事务最终没有提交？把这些“失败者”事务的所有操作，按照日志记录的相反顺序一一撤销。

---

2. 关键组件与概念 (The Cast of Characters)

在进入恢复过程之前，必须先认识这几个关键角色：

• 日志记录 (Log Record)：这是数据库操作的最小单元，记在磁盘的日志文件中。每一条日志都有一个独一无二、单调递增的 LSN (Log Sequence Number)。

  • Update Record: [LSN, TxnID, PageID, BeforeImage, AfterImage] (记录了哪个事务修改了哪个页，改之前和之后是什么样)
  • Commit Record: [LSN, TxnID, 'COMMIT']
  • Abort Record: [LSN, TxnID, 'ABORT']
  • CLR (Compensation Log Record): 这是用于“撤销”操作的特殊日志，我们后面会讲。

• 脏页表 (Dirty Page Table - DPT)：内存中一张表，记录了哪些在缓冲池（Buffer Pool）中的数据页被修改过但尚未刷回磁盘。

  • [PageID, recoveryLSN]：recoveryLSN 是第一次让这个页变“脏”的那条日志的 LSN。

• 活跃事务表 (Active Transaction Table - ATT)：内存中另一张表，记录了当前正在运行（尚未提交或中止）的事务。

  • [TxnID, lastLSN]：lastLSN 是该事务产生的最新一条日志的 LSN。

• 检查点 (Checkpoint)：这是一个“存档点”机制。它会把当前的 ATT 和 DPT 的内容写入日志文件。这极大地缩短了恢复时需要扫描的日志长度，我们不需要从日志的开头开始，只需要从最近的一个检查点开始即可。

---

3. 恢复的三个阶段 (The Three Acts of the Play)

好了，主角登场！假设系统刚刚崩溃重启，ARIES 恢复过程正式开始。

把这个过程想象成一个侦探在调查一起案件（系统崩溃）。

阶段一：分析 (Analysis) - "勘察现场"

目标：确定在崩溃的瞬间，到底哪些事务是活跃的，哪些内存页是脏的。简单说，就是重建崩溃瞬间的 ATT 和 DPT。

动作：

1. 从日志文件中找到最后一个检查点 (Checkpoint)。
2. 从这个检查点开始，从前向后 (Forward) 扫描日志，直到日志文件末尾。
3. 根据扫描到的日志记录，重建 ATT 和 DPT：
   • 如果看到一个事务的 Begin 或 Update 记录，就把它加入 ATT。
   • 如果看到一个事务的 Commit 或 Abort 记录，就把它从 ATT 中移除。
   • 如果看到一条 Update 记录修改了 Page P，检查 P 是否在 DPT 中。如果不在，就把它加入 DPT，并记录当前日志的 LSN 为其 recoveryLSN。

结果：分析阶段结束后，我们得到了一份准确的“失踪人员名单”（ATT，未完成的事务）和一份“待救援财产清单”（DPT，可能未存盘的脏页）。

阶段二：重做 (Redo) - "重演案情"

目标：确保所有记录在日志中的修改（包括已提交和未提交的）都真正在磁盘上生效。实现持久性 (Durability)。

动作：

1. 找到 DPT 中 recoveryLSN 最小的那个 LSN，这是我们需要开始重做的最早点。
2. 从该 LSN 开始，从前向后 (Forward) 扫描日志直到末尾。
3. 对于每一条 Update 日志记录：
   • 检查其修改的 PageID 是否在 DPT 中。
   • 如果是，就从磁盘读取该数据页，并比较页上记录的 LSN（每个数据页都会记录最后一次修改它的 LSN）。
   • 如果 磁盘页的 LSN < 日志记录的 LSN，说明这个修改在崩溃前可能没来得及写入磁盘，必须重新执行这个修改操作（应用 AfterImage），并更新页上的 LSN。
   • 否则，说明这个修改已经写入磁盘了，跳过即可。

为什么叫“重复历史”？ 因为这个阶段不管三七二十一，把日志里的操作重放一遍，让数据库恢复到崩溃前最后一刻的状态。这个过程是幂等的，即使在 Redo 过程中又崩溃了，再次恢复时重复执行 Redo 操作，结果也是一样的。

阶段三：撤销 (Undo) - "清理现场，纠正错误"

目标：将所有在分析阶段确定的“活跃事务”（ATT 里的那些）的修改全部回滚。实现原子性 (Atomicity)。

动作：

1. 拿到分析阶段得到的 ATT，我们称这些事务为 Losers。
2. 从后向前 (Backward) 扫描日志，从 ATT 中所有事务的 lastLSN 的最大值开始。
3. 如果当前日志记录属于 Loser 事务之一：
   • 执行该操作的逆操作（应用 BeforeImage）。
   • 为这个“撤销”动作，生成一条新的特殊日志记录，叫做 CLR (Compensation Log Record)。CLR 指向了它所撤销的那条日志的 LSN (undoNextLSN)。
   • 然后，跳到该事务的上一条日志记录（由日志中的 prevLSN 字段指引），继续撤销。
4. 这个过程一直持续，直到所有 Loser 事务的所有操作都被撤销（即追溯到它们的 Begin 记录）。

为什么需要 CLR？ CLR 保证了 Undo 操作的原子性。如果系统在 Undo 过程中又崩溃了，恢复时，ARIES 在 Redo 阶段会重放 CLR，但不会对 CLR 进行 Undo 操作。这保证了一个操作要么被成功撤销，要么没被撤销，绝不会被“撤销了又撤销”。

---

面试怎么讲

面试官: "你能讲讲数据库是如何做崩溃恢复的吗？比如 ARIES 算法。"

你:
"好的。ARIES 是一个非常经典的崩溃恢复算法，它的核心目标是在系统崩溃后，保证所有已提交事务的修改都持久化，所有未提交事务的修改都被撤销，也就是保证事务的原子性和持久性。它主要基于**预写日志（WAL）**原则。"

"ARIES 的恢复过程主要分为三个阶段："

"第一阶段是分析（Analysis）。这个阶段的目标是搞清楚崩溃时系统的状态。它会从最后一个检查点开始，向后扫描日志，重建两张表：一张是活跃事务表（ATT），记录了哪些事务还没提交；另一张是脏页表（DPT），记录了哪些数据页在内存中被修改但可能没写回磁盘。"

"第二阶段是重做（Redo）。这个阶段的目标是保证持久性。它会从脏页表里记录的最早的修改点开始，向后扫描日志，并把日志里记录的所有修改操作重新应用到磁盘上。这样可以确保所有事务（包括未提交的）的修改都反映在磁盘上，让数据库恢复到崩溃前的瞬间状态。"

"第三阶段是撤销（Undo）。这个阶段的目标是保证原子性。它会处理在分析阶段找到的所有活跃事务，也就是‘失败者’。它会从后向前扫描日志，对这些失败者事务的每一个操作执行逆操作，将它们的影响完全消除。为了保证撤销操作本身也是可以恢复的，每执行一次撤销，它还会写入一条特殊的补偿日志记录（CLR）。"

"总结一下就是：先分析，再重做所有历史，最后撤销未完成的事务。 这个设计非常巧妙，即使在恢复过程中再次崩溃，也能保证最终数据的一致性。"