作业准备

项目地址：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 任务一也费了一番功夫，因为当时边界条件没弄清楚。