项目准备

项目地址：Project #1 - Buffer Pool

准备工作：阅读 Chapter 12.1-12.4 13.2-13.3 24.2，学习 Lecture #03 #04，以及阅读课堂笔记。

项目结构

buffer_pool_manager

pages_ 数组相当于缓冲池，frame_id 是该数组的下标，也就唯一标识一个 Page，即标识一个缓冲页面。一个 Page 可以存储不同的物理页面，Page 的数据成员 page_id_ 唯一标识一个物理页面。因为不管是 FetchPage，还是 DeletePage 等函数，我们都是针对实际的物理页面做操作，所以 buffer_pool_manager 中的函数的形参都是提供 page_id。

lru_k_replacer

该类提供缓冲页面的淘汰策略，即淘汰某个 fram_id 对应的缓冲页面。一个缓冲页面会有一个对应的 LRUKNode，它负责记录该缓冲页面的访问历史。

page_guard

主要有三个类：BasicPageGuard，ReadPageGuard 和 WritePageGuard。BasicPageGuard 的作用是保证缓冲页面在使用完后会进行 UnpinPage 操作。而 ReadPageGuard 和 WritePageGuard，它们和 BasicPageGuard 是组合关系，它们的作用在 BasicPageGuard 的基础上保证页面在使用完后会解除读写锁。

Task #1 - LRU-K Replacement Policy

实现

① 一开始以为 current_timestamp_ 自动就是当前时间戳，调试时发现一直是 \(0\)，我真笨。可以直接从 \(0\) 开始手动模拟时间戳，调用 RecordAccess 时，让当前时间戳加 \(1\) 即可。

② 在 Evict 的注释中有：If multiple frames have inf backward k-distance, then evict frame with earliest timestamp* based on LRU。我以为淘汰的是最后一次访问时间最早的 frame，结果淘汰的是第一次访问时间最早的 frame。

③ 在 ListNode 中使 history_ 的长度不超过 k_，如果超过就调用 pop_front()，这样每次获取之前第 k_ 个访问记录只需要调用 front() 函数。

④ 在 RecordAccess 的注释中有：If frame id is invalid (ie. larger than replacer_size_), throw an exception。但其实应该是大于等于吧，因为 BufferPoolManager 构造函数的实现如下：

1
2
3
4
5
6
7
8

// we allocate a consecutive memory space for the buffer pool
pages_ = new Page[pool_size_];
replacer_ = std::make_unique<LRUKReplacer>(pool_size, replacer_k);

// Initially, every page is in the free list.
for (size_t i = 0; i < pool_size_; ++i) {
    free_list_.emplace_back(static_cast<int>(i));
}

上述代码说明 frame_id 是小于 pool_size 的，所以大于等于 pool_size 的 fram_id 都应该抛出异常。（或许小于零的也应该抛出异常）

补充

① 测试时将 DISABLED_SampleTest 改为 SampleTest。

② 忘记 C++ 的 = 是拷贝，传引用加上 &：

1

auto node = node_store_.at(frame_id); // 错误：拷贝

③ LRU 的中文翻译是“最近最少使用”，实在让人很无语，我以后就将其称为“最久未被使用”吧。

Task #2 - Buffer Pool Manager

实现

① NewPage 和 FetchPage 有很多逻辑相同的部分，可以加个辅助函数来获取 frame_id。

② 注意，在 FetchPage 时，如果页面在内存中并且 pin_count_ = 0，则需要将其设置为不可淘汰的。

③ 在 UnpinPage 中，更新 is_dirty 属性时使用或运算，因为可能某个线程修改了页面数据，而其他线程没有修改。

④ 在 FlushPage 中，注释表示 REGARDLESS of the dirty flag，应该说的是函数调用者，我们在实现时可以根据 is_dirty 来判断是否实际刷盘。

补充

① 提交 GradeScope 报错时，下面会显示一堆 LeakSanitizer: detected memory leaks。但是没有关系，这应该是由于测试程序提前终止引发的，直接解决上面的错误就行。

② 实现 FetchPage 时，有个情况我忘记调用 RecordAccess，竟然通过所有线上测试了，后来检查代码才发现，修改后 QPS 快了一些。

Task #3 - Read/Write Page Guards

实现

① 使用移动构造和移动赋值后，需要清除 that 的元数据。

② 移动赋值的调用者，也就是 this，如果其 page_ != nullptr，那么需要先将其 Drop，再进行赋值操作。

③ 实现读写页面守卫的移动构造函数，可以直接赋值 std::move(that.guard_)，相当于调用之前实现的 BasicPageGuard 的移动赋值运算符。

④ 实现读写页面守卫的 Drop 时，需要注意在调用 guard_.Drop() 之后再解锁页面，所以在 Drop 之前需要保存一下指向页面的指针。

⑤ 在实现 BufferPoolManager 中的 FetchPageRead 和 FetchPageWrite 时，为页面加读写锁。

⑥ 和 PageGuard 有关的 FetchPage 函数会返回一个 PageGuard 对象，但是如果所有缓存页已经被 pin，那么该返回什么。一开始我是直接拿 nullptr 构造 PageGuard，但是发现不对，因为 PageGuard 对象并没有检查 page_ == nullptr 的函数，所以页面必须被 Fetch 到。要不就一直自旋，要不就使用条件变量，但是使用条件变量又要加个锁，防止通知丢失，那样锁竞争会很激烈啊。（不是很想改，BufferPoolManager 和 B+Tree 的线上测试都能过，暂时不管）

Leaderboard Task (Optional)

准备

性能分析

看到CMU 15-445 2023 P1 优化攻略中使用火焰图做性能分析，之前从来没听说过，打算学习一下。以下是几个不错的网站，奈何感觉很复杂啊。一开始我是用 perf 做分析，然后使用 speedscope 进行可视化，但是捣鼓半天还没弄明白，遇到很多问题，有空再搞吧。

• Brendan Gregg’s Homepage
• How to use flamegraphs for performance profiling
• profiling 与性能优化总结
• speedscope

LRU-K（对优化似乎没有帮助）

关于 LRU-K 的论文：The LRU-K Page Replacement Algorithm For Database Disk Buffering。

LRU 存在的问题：仅根据页面的最后一次访问时间进行淘汰，它不知道页面是否经常访问，从而可能将不经常访问的页面长时间保留在缓冲区中。（论文中对此有两个场景分析）

解决方案：① 页面池调优，缺点是需要人工操作，并且不能适应移动热点；② 查询执行计划分析，缺点是在多用户的场景下，查询优化器可能会以复杂的方式重叠；③ LRU-K，自适应的。（有点不是很懂）

LRU-K 和 LFU 的区别：LRU-K 有一个“老化”的概念，即只考虑对页面的最后 K 次引用，而 LFU 无法区分最近和过去的引用频率，因此无法应对不断变化的访问模式。

LRU-K 存在的问题：① Early Page Replacement，新加入缓冲池的页面因为访问次数不足 K（\(K\geq 2\)），所以相对于有 K 次访问历史的页面更容易被淘汰，但是该页面之后可能会有相关访问（原文是称作 Correlated References，并介绍了事务内、事务重试、进程内、进程间的相关访问）；② Page Reference Retained Information Problem，当页面被淘汰时，它的访问历史需要保留一段时间，如果超时再进行删除操作。

实现

更新：以下内容存在一些错误，将会在下一节纠正。

① 初次提交，所有函数开头一把大锁。提交相同的代码，排名波动挺大的，可能是因为没优化的代码跑分都差不多，QPS 大概四五千左右。

② 并行 IO 优化，尝试在进行 IO 操作时将大锁切换为单独的页锁（针对 frame_id，即缓冲池页面的锁），简单来说就是在 IO 之前拿到页锁，然后释放大锁。一定需要注意加锁和解锁的顺序，如果有部分代码先加大锁再加页锁，另一部分代码先加页锁再加大锁，那么就会产生死锁。优化半天，遇到不少 BUG，但是没遇到死锁，QPS 提升至五万多。（注意，我们优化的是磁盘页面读写，而不是缓存页面读写，不要混淆，说的就是我）

③ 死锁警告，调试最久的一次，线上提交五十多次（当时不知道本地有 bpm-bench 测试），结果发现是我理解有问题。尝试使用读写锁在 BufferPoolManager 内部锁定页面，但是读写锁是依赖于访问类型的，因为有 Unknown 类型的存在，实际上根本无法执行该优化，并且该优化并不会提高 IO 的并行量。PS：仔细想想后发现甚至根本就不可能这样做，因为 FetchPage 时需要修改共享变量肯定不能用读写锁。并且根本就不可能有什么性能提升，因为优化的部分不涉及 IO 等耗时操作，所以瞎折腾半天后放弃。

④ 参考CMU 15-445 2023 P1 优化攻略，似乎用的是写时复制的思想，刷盘的时候复制一份数据在新线程刷，这样就可以让当前线程做 ResetMemory 操作而不会产生冲突，具体的优化思路见文章。单纯的写时复制优化我觉得还行，刷盘之后就会释放复制页面占用的内存空间，读取的时候也可以重复利用。但是如果像文中那样固定为每个页面都保存缓存，那就相当于变相增加了缓冲池的容量，那还不如用下面的方法简单粗暴，并且时间和空间都应该是更优的。

⑤ 有个无耻的优化方式，把所有页面全部存到内存缓存中，读盘的时候读缓存，刷盘的时候刷缓存，最后析构的时候再进行实际的物理刷盘。具体实现的时候，不能在析构的时候刷盘，因为线上测试会在析构 BufferPoolManager 之前析构 DiskManager，但是这样也是可以通过线上测试的，QPS 两百多万（其实大部分测试结果只有一百多万）。然而，这已经不能算优化了，磁盘数据库不可能这么操作的，因为内存不太可能存下所有页面。

⑥ 本来想优化 LRU-K 的，但是想不到怎么根据访问类型来优化，怎么利用 zipfian 分布，暂时搁置。突然想到优化方法了，因为 Scan 线程是进行全表扫描，所以只被 Scan 线程访问过的页面就可以直接淘汰掉。我们可以在 LRUKNode 中维护一个布尔值，表示当前页面是否只被 Scan 线程访问，如果是就可以在 Evict 中直接淘汰，并且优先淘汰此类页面。回归正轨，基于 ② 优化提升大概三万 QPS，排名 12。（这优化完全是针对基准测试做的，没有什么适用性）

重做

实现纠错

在做 B+Tree 时发现上面第 ② 个实现有个 Bug，如果我新建一个缓存页面，然后它被淘汰刷盘，在刷盘之前，我会拿到该缓存页面的锁，然后释放缓冲池的独占锁，这会存在问题。为了避免死锁，加锁解锁的顺序是固定的，所以我释放缓冲池的独占锁后，不会再去尝试对它加锁。那么我就需要释放独占锁之前，修改完所有和缓冲池有关的共享变量（例如 page_table_），但是，如果在刷盘过程中，有另一个线程读取该页面，它在 page_table_ 中找不到该页面，所以它会去读取磁盘，这时页面还没有写入磁盘中，就会出现 “page not exist” 错误，错误在 disk_manager_memory.h 中被检测：

1
2
3
4

if (page_id >= static_cast<int>(data_.size()) || page_id < 0) {
    LOG_WARN("page not exist");
    return;
}

所以第 ② 种优化方式是不完善的。可以额外搞个哈希表存正在进行刷盘的 page_id 和 frame_id，然后加个锁，在刷盘的时候加到该表里，刷完的时候删除（注意在添加到表时持有 page_table_ 的锁，以确保在其他线程 FetchPage 时，表中已有该 page_id）。这时如果有其他线程 Fetch 该 page_id，不会直接从磁盘读，而是读这个表拿到之前的 frame_id，然后拷贝到当前缓存页。（之所以另开哈希表，而不是保留在原来的表里，是因为如果这样会导致混乱，当有其他线程 FetchPage 该 page_id 时，会发生已淘汰又被 pin 的情况，还会发生其他很复杂的情况）

如何优化

既然 B+Tree 把我打回来修复 Bug，那么我就想，有没有更好的优化方案。自己独自优化总觉得找不到方向，并且可能设计就是错的，而且优化方式很幼稚。在网上搜也搜不到具体的优化方案，我就想尝试看一看开源数据库都是怎么做的，最后在 PostgreSQL 项目中发现一份超级详细的 README（MySQL 为什么没有），省去我看源码的时间，以下是对它的简单概述（使用我们项目中的变量来解释）：

① 缓存页面的访问规则

• 读写页面时必须 pin 页面，并拿到相应的读写锁。（文中要求必须在上锁之前 pin）
• 在读页面时，可以释放页面的读锁，因为已经拿到页面的 pin。
• 在写页面时，必须拿到 pin 和写锁，并且需要检查 pincount_ == 1，如果不相等，则释放写锁并返回或者使用条件变量等待唤醒。（因为在读页面时会提前释放读锁，但没有 unpin，所以拿到写锁时，还需要等待）当进行写操作时，有可能页面会被 pin，但是没有关系，因为当前线程拿到写锁，其他线程 pin 之后还需要拿锁才能读写页面。

我们的项目和上面的描述不一样，但是无伤大雅，基本上 PageGuard 和 FetchPage 等函数已经提供了这些功能。

② 缓冲池管理器的内部锁定

• 访问 page_table_ 前需要拿到 page_table 的读写锁（文中称作 BufMappingLock）。如果是读页面，则在释放锁之前，需要拿到缓存页面的 pin。在修改 page_table_，或者修改缓存页面头部字段（应该是指 Page 的除 data_ 以外的成员变量，在本项目中就是 page_id_、pin_count_ 和 is_dirty_），或者从磁盘读物理页面到缓存页面时，需要拿到 page_table_ 的写锁。
• 可以将 BufMappingLock 拆分为 NUM_BUFFER_PARTITIONS 个锁，每个锁负责映射的一部分。每个 page_id_ 属于哪个分区，由 page_id_ 的哈希值的低比特位决定（其实就是有多个 page_table_，每个 page_id 会根据哈希函数来确定存放在哪个 page_table_ 中）。如果要同时锁定多个分区，则需要按照分区编号顺序锁定，以避免死锁。
• 为空闲列表和页面替换提供独占的自旋锁 buffer_strategy_lock ，当拿到该锁时，不应该去获取任何其他锁。
• 每个缓存页面都有一个自旋锁，在读写缓存页面头部字段时使用（疑问，如果有这个锁，在修改头部字段时似乎就不需要持有 BufMappingLock 锁）。
• BM_IO_IN_PROGRESS 标志是一种锁，用来等待缓存页面的 IO。在从磁盘读物理页面到缓存页面，或者将缓存页面刷到磁盘的过程中，会将该标志置位，操作完成后清除标志位。等待标志位被清除的线程会使用条件变量休眠（疑问，如果有这个标志，那么在从磁盘读物理页面到缓存页面时，就不需要持有 BufMappingLock 锁吧）。

缓冲池管理器的优化就靠这部分内容，但是有些描述还是不太清晰（是不是我理解错误，并且文中涉及日志相关的内容，不是很好懂），实现的时候再想吧。然后文中还提出了如何对线性扫描做优化，但是我认为单纯在缓冲池管理器里面做不了这个优化，因为没办法识别当前操作是否是线性扫描，而且优化需要另开一个小缓冲池，这应该是查询优化器的任务。

③ 后台线程刷盘

• 按照淘汰顺序扫描页面，选择 is_dirty_ == true && pin_count_ == 0 的页面，然后 pin 该页面并刷盘，最后回收到空闲列表。
• 还有一些优化方式，没看懂就不翻译了。

总结一下，该文件中提到的优化，有一些可能跟它的页面替换算法相关（PostgreSQL 使用的是时钟扫描算法），或者和该数据库的其它特性相关（提示位之类的），看得云里雾里的，我们能够做的优化大概就是上面提到的这些，具体怎么实现还是走一步看一步吧。

尝试实现

重构代码，轻松通过本地测试，哭死。惊了，线上就一个测试没过。

① FetchPage 在判断 page_id 是否在 page_table_ 时，需要使用 page_table_ 的独占锁。并且如果页面不在 page_table_ 中，则在函数返回 nullptr 或修改 page_table_ 之前不能释放该锁，以防止多次 FetchPage 同一个 page_id 时，多次从 free_list_ 中获取页面或者多次淘汰页面。

② 因为在 FetchPage 将淘汰页面刷盘时，我会释放所有锁，这时页面是可以被 pin 的，所以之后设置 pin_count_ 时，不能直接设置为 1，而是进行 ++ 操作。

第一次重构没有拆分 BufMappingLock，没有使用自旋锁，其他的锁基本都加了。QPS 和之前的第 ② 个优化差不多，其实也可以想到，毕竟只是加了一些锁保证正确性，基本上没有提高并行性。本来想使用自旋锁的，但是因为需要条件等待，而条件变量只能用 unique_lock 作为参数，并且 atomic_flag 的原子等待只有在 C++ 20 才有，不好实现，遂放弃挣扎（而且估计不会有什么提升）。不搞了，像个小丑，没意思。

调试

① 优化的时候一步一步优化，然后进行测试，要不然调试半天，都不知道 BUG 在代码的哪个位置。

② 优化时容易出问题的点就是 NewPage 和 FetchPage，以及 UnpinPage。像是 FlushPage、FlushAllPage 以及 DeletePage 都可以暂时不管（可以直接 return），这样比较方便调试。

补充

① 在 C++ 20 之前，结构化绑定不能被 lambda 表达式捕获。

② 遇到 Reference to non-static member function must be called 问题，解决方案在此。

③ MySQL Buffer Pool 的实现 15.5.1 Buffer Pool。

④ Linus Torvalds 发表的一篇评论：do not use spinlocks in user space, unless you actually know what you’re doing。

⑤ 条件变量如果使用不当，可能会导致唤醒丢失，必须利用锁保证不会在等待前执行唤醒操作。

⑥ 发现一个感觉不错的博客：MC++。

测试结果

测试通过！本地的测试数据比较弱，而且没有并发测试。如果线上测试遇到问题，可以通过添加打印语句，线上看输出来调试。基本上没遇到什么大问题，都是细节问题，很容易漏判断一些条件。另外，加锁优化是可选的，暴力加锁就可以通过测试。

优化任务让我的提交记录暴涨，特别是在尝试第 ③ 个优化方案时。一般等 4 分钟才能出结果，有时候评测机还会出问题，算下来等结果的时间都有 8 小时，离谱。

每次本地测试都需要输入很多命令，提交线上又要格式化，如果手动输入太麻烦了，可以写个 shell 脚本来执行：

1
2
3
4
5
6
7
8
9

#!/bin/bash
make lru_k_replacer_test buffer_pool_manager_test page_guard_test -j$(nproc)
./test/lru_k_replacer_test
./test/buffer_pool_manager_test
./test/page_guard_test
make format
make check-lint
make check-clang-tidy-p1
make submit-p1

项目小结

① 在做项目的时候，总是会想某个地方是不是有更优的写法，但是当时对整个项目结构不太清楚，以及代码实现是否正确也不清楚，所以基本上都是浪费时间。据此，我的收获就是先让代码跑起来，其他的之后再说。

② 虽然做的时候很艰辛，但是做完之后发现，好像也没有什么工作量，bpm 优化也就是简单减少锁的粒度，lru 的优化也完全是针对基准测试做的，感觉我的优化方式很烂，有没有更牛逼的优化方式啊。

③ 我好菜啊！！！前三个任务花了两天，优化花了好几天。

更新：发现 Lecture #06 就是讲 BufferPool 优化的（课堂笔记），不知道能不能在这用上，等做完所有 Project 再来试试。

作业准备

项目地址：Homework #1 - SQL。

准备工作：阅读 Chapters 1-2 27 3-5，学习 Lecture #01 #02，以及阅读课堂笔记。

Q1 [0 points] (q1_sample):

Ctrl + C，Ctrl +V。

Q2 [5 points] (q2_not_the_same_title):

查询只涉及 titles 表，比较简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

SELECT
	premiered,
	primary_title || ' (' || original_title || ')'
FROM
	titles
WHERE
	primary_title != original_title
	AND type = 'movie'
	AND genres LIKE '%Action%'
ORDER BY
	premiered DESC,
	primary_title
LIMIT
	10;

Q3 [5 points] (q3_longest_running_tv):

题目描述很不清晰啊，类型都不知道具体是什么。

1
2
3
4
5
6
7
8
9
10
11
12
13

SELECT
	primary_title,
	IIF(ended IS NULL, 2023, ended) - premiered AS runtime
FROM
	titles
WHERE
	primary_title IS NOT NULL
	AND type = 'tvSeries'
ORDER BY
	runtime DESC,
	primary_title
LIMIT
	20;

Q4 [10 points] (q4_directors_in_each_decade):

唯一要注意的就是使用 DISTINCT。

1
2
3
4
5
6
7
8
9
10
11
12
13

SELECT
	CAST(born / 10 * 10 AS TEXT) || 's' AS decade,
	COUNT(DISTINCT(people.person_id)) AS num_directors
FROM
	people
	INNER JOIN crew USING(person_id)
WHERE
	category = 'director'
	AND born >= 1900
GROUP BY
	decade
ORDER BY
	decade;

Q5 [10 points] (q5_german_type_ratings):

德语的缩写是 de。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

SELECT
	t.type,
	ROUND(AVG(r.rating), 2) AS avg_rating,
	MIN(r.rating),
	MAX(r.rating)
FROM
	akas as a
	INNER JOIN ratings as r USING(title_id)
	INNER JOIN titles as t USING(title_id)
WHERE
	a.language = 'de'
	AND a.types IN ('imdbDisplay', 'original')
GROUP BY
	t.type
ORDER BY
	avg_rating;

Q6 [10 points] (q6_who_played_a_batman):

坑点就是模糊查询时 Batman 两边要加上双引号，即 "Batman"。以及在连接 people 和 crew 表时，顺序很重要，如果使用 crew INNRE JOIN people USING(person_id) 会很慢（查询大概有 5 秒），具体不知道为什么，以下是它们的执行计划。

1
2
3
4
5
6
7
8
9
10
11
12
13

crew INNER JOIN people USING(person_id)

QUERY PLAN
|--SCAN crew USING INDEX ix_crew_person_id
|--SEARCH people USING INDEX sqlite_autoindex_people_1 (person_id=?)
`--USE TEMP B-TREE FOR DISTINCT

people INNER JOIN crew USING(person_id)

QUERY PLAN
|--SCAN crew
|--SEARCH people USING INDEX sqlite_autoindex_people_1 (person_id=?)
`--USE TEMP B-TREE FOR DISTINCT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

WITH t AS (
	SELECT
		DISTINCT(person_id),
		name
	FROM
		people
		INNER JOIN crew USING(person_id)
	WHERE
		category = 'actor'
		AND characters LIKE '%"Batman"%'
)

SELECT
	name,
	ROUND(AVG(rating), 2) AS avg_rating
FROM
	t
	INNER JOIN crew USING(person_id)
	INNER JOIN ratings USING(title_id)
GROUP BY
	person_id
ORDER BY
	avg_rating DESC
LIMIT
	10;

Q7 [15 points] (q7_born_with_prestige):

SQL 很容易写，但是性能和官解差两秒，等以后学习怎么优化再来看吧。

1
2
3
4
5
6
7
8
9

SELECT
	COUNT(DISTINCT(person_id))
FROM
	titles
	INNER JOIN people ON titles.premiered = people.born
	INNER JOIN crew USING(person_id)
WHERE
	primary_title = 'The Prestige'
	AND category IN ('actor', 'actress');

1
2
3
4
5

QUERY PLAN
|--USE TEMP B-TREE FOR count(DISTINCT)
|--SCAN crew
|--SEARCH people USING INDEX sqlite_autoindex_people_1 (person_id=?)
`--SEARCH titles USING INDEX ix_titles_primary_title (primary_title=?)

Q8 [15 points] (q8_directing_rose.sql):

比官解快一秒。注意使用 Rose% 而不是 Rose %。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

SELECT
	DISTINCT(name)
FROM
	crew
	INNER JOIN people USING(person_id)
WHERE
	category = 'director'
	AND title_id IN (
		SELECT
			title_id
		FROM
			crew
			INNER JOIN people USING(person_id)
		WHERE
			category = 'actress'
			AND name LIKE 'Rose%'
	)
ORDER BY
	name;

Q9 [15 points] (q9_ode_to_the_dead):

这就是窗口函数么，学习了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

WITH t AS (
	SELECT
		category,
		name,
		died,
		primary_title,
		runtime_minutes,
		DENSE_RANK() OVER(
			PARTITION BY category
			ORDER BY died, name
		) AS rank_died_name,
		DENSE_RANK() OVER(
			PARTITION BY category, person_id
			ORDER BY runtime_minutes DESC, title_id
		) AS rank_runtime_title
	FROM
		crew
		INNER JOIN people USING(person_id)
		INNER JOIN titles USING(title_id)
	WHERE
		died IS NOT NULL
		AND runtime_minutes IS NOT NULL
)

SELECT
	category,
	name,
	died,
	primary_title,
	runtime_minutes,
	rank_died_name
FROM
	t
WHERE
	rank_died_name <= 5
	AND rank_runtime_title = 1
ORDER BY
	category,
	rank_died_name;

Q10 [15 points] (q10_all_played_by_leo):

不会。。json_each 函数有点神奇，也看了下递归 CTE 的实现，只能说真想不出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

WITH t1(characters) AS (
	SELECT
		characters
	FROM
		people
		INNER JOIN crew USING(person_id)
	WHERE
		name = 'Leonardo DiCaprio'
		AND born = 1974
),
t2(value) AS (
	SELECT
		DISTINCT(value)
	FROM
		t1,
		json_each(t1.characters)
	WHERE
		value != ''
		AND value NOT LIKE '%SELF%'
	ORDER BY
		value
)

SELECT
	GROUP_CONCAT(value)
FROM
	t2;

作业小结

最难的是最后两题，前面几题还可以接受。因为比较在意连接顺序对查询性能的影响，所以多花了点时间。（虽然还没弄明白就是了）

项目准备

项目地址：Project #0 - C++ Primer。

准备工作：创建项目仓库，学习 Git 分支，复习 C++，阅读谷歌 C++ 风格指南，学习 GDB。

Task #1 - Copy-On-Write Trie

实现

Get 函数

没有什么特别需要注意的，实现比较简单。

实现逻辑：

• 如果 root_ == nullptr 为真，则返回 nullptr。
• 沿着 Trie 树遍历，如果节点不存在，则返回 nullptr。
• 如果目标节点不是 TrieNodeWithValue 类型，则返回 nullptr。
• 否则，返回目标节点的值。

Put 函数

一开始比较疑惑的点是，智能指针存储的都是 const 修饰的节点，如果要修改就必须克隆。但是沿着树遍历的话，如果需要修改子节点，那么同样也需要让父结点指向克隆后的子节点，然后一直向上到根节点，看上去似乎使用栈比较合理。那么能不能不使用栈呢？

其实通过观察可以发现，从根节点一直到目标节点（表示字符串的节点）都是需要克隆的，如果节点存在的话。那么这样我们就可以在遍历的过程中克隆，只需要维护新克隆节点的非 const 指针就能做到。

本来想加个冗余节点减少判断的代码，但是感觉好像怎么弄都逃不过判断 key.empty() 和 root_ == nullptr。

实现逻辑：

• 如果 key.empty() 为真：
  • 如果 root_ == nullptr 为真，则使用 value​ 构造 Trie 树并返回。
  • 否则，使用 root_->children_ 和 value 构造 Trie 树并返回。
• 根据 root_ == nullptr 条件初始化新 Trie 树的 root。
• 沿着旧 Trie 树克隆新 Trie 树的节点（最后一个字符对应的节点需要特殊处理）：
  • 如果克隆完所有字符，则返回新 Trie 树。
  • 否则，新 Trie 树继续创建旧 Trie 树不包含的节点，然后返回新 Trie 树。

Remove 函数

需要使用栈辅助删除，优化后代码好看多了，不像之前那么复杂（大概）。有以下几点需要注意：

① 节点不包含值需要转换为 TrieNode 类型，也就是说拷贝的时候需要调用 TrieNode::Clone()。

② 如果节点满足 children_.empty() && !is_value_node_ 条件，则需要移除该节点。一个节点的移除，可能会导致该节点的父节点也满足移除条件。移除时，记得 erase 父节点中 map 的 key。

实现逻辑：

• 如果 root_ == nullptr 为真，则返回 *this。
• 如果 key.empty() 为真，则调用 root_->TrieNode::Clone() 克隆，并返回新 Trie 树。
• 沿着旧 Trie 树遍历，并将对应的节点入栈，如果节点不存在，则返回 *this。
• 将栈顶的元素依次弹出，如果当前节点需要移除，则将其移除。
• 否则，依次克隆栈中的元素，然后返回新 Trie 树。

补充

C++

因为平时用的 Java，所以有几个使用 C++ 的坑点需要注意一下。

① 使用 at 访问 const map 对象，因为 [] 运算符可能会自动添加键值。

1
2
3

const map<int,int> m;
cout << m[1024]; // 错误，No viable overloaded operator[] for type 'const map<int, int>'
cout << m.at(1024); // 正确

② = 拷贝对象的底层结构，不像 Java 中拷贝的是对象的地址（相当于 C++ 中的指针吧）。

1
2
3
4
5

map<int,int> m;
m[1024] = 1024;
auto n = m;
n[1024] = 2048;
cout << m[1024]; // 输出：1024

③ 在 Java 中只要是对象就可以和 null 比较，而 C++ 中只有指针可以和 nullptr 比较。

GDB

① 使用 GDB 调试经常会看到 Python Exception <class ‘gdb.error’>: There is no member named _M_p，点击此处产生该问题的原因，以及相应的解决方案告诉我下载 libstdc++6-dbgsym，完美解决问题。本来不想管这个问题的，结果任务三需要在调试时打印字符串。

② 之前做 CSAPP 的二进制炸弹实验用过 GDB，可以在此查看该课程提供的 GDB 教程。以及可以阅读：GDB Tutorial: Finding Segmentation Faults。

③ 使用 GDB 调试时，最后会报错 LeakSanitizer has encountered a fatal error，因为 LeakSanitizer 不能在 GDB 下工作。不用去管这个错误，只要在不用 GDB 的情况下测试通过就行。

CMake

项目推荐使用 clang-14 作为编译器，解决方案在此。

Task #2 - Concurrent Key-Value Store

实现

因为 Trie 是写时复制的，所以似乎不需要考虑其他复杂的上锁操作，只需要简单的使用 std::mutex 即可。读操作在获取 root_ 时上锁，获取完即可解锁。写操作同理，并且需要在整个操作内对 write_lock_ 上锁。Put 时记得使用 std::move()，因为值可能是不可复制的。

补充

① 关于线程和锁的知识，推荐阅读 CS110 Lecture 10: Threads and Mutexes。

② C++ 有个复制省略（Copy elision）的优化。

③ 关于 C++ 模板的 FAQ、template 关键字的讨论 和 Dependent names 的定义。（好复杂啊）之所以查这些内容，是因为 CLion 给我生成了不同的表达式：

1
2
3

auto value = root.template Get<T>(key);
root = root.template Put(key, std::move(value));
root = root.Remove(key);

以我现在的理解，模板类型是根据实参推断的，如果无法推断则需要在调用时显示添加 <> 来指定类型。然后何时使用 template 没怎么弄明白。

Task #3 - Debugging

实现

挺简单的，文件 trie_debug_test.cpp 指出在 28 行打断点，但我是在 Put 时打断点调试的，应该差不多吧。

补充

无语的是，在修复上个问题时无意间下载了 gcc-12，导致在 make 时报错：/usr/bin/ld: cannot find -lstdc++: No such file or directory，问题原因以及解决方案在此。

Task #4 - SQL String Functions

实现

文件的路径：./src/include/execution/expressions 和 ./src/planner/plan_func_call.cpp。实现大小写转换比较简单，但是如果使用 std::tolower 或许有一些注意事项。注册函数时，需要保证参数是有效的，即参数只有一个并且是 VARCHAR 类型。

测试结果

就是过不去 TrieDebugger.TestCase，结果发现不是我的问题，而是因为本地的随机数和测试的随机数不同，详情见 Discord 讨论。

修改之后通过！

项目小结

任务一是项目的核心，主要还是把逻辑理清楚，以及注意到 key 为空串的特殊用例。一开始很多东西都不懂，查找资料学习花费了很多时间，还有就是 Debug 任务一也费了一番功夫，因为当时边界条件没弄清楚。