1

我正在用 C++ 从头开始​​编写一个非常简单的数据库以及一个 SQL 解析器。我已经做了一切。因此，如果我有这样的 SQL 输入：

SELECT * FROM table WHERE `First Name`="John" AND `Last Name`="Doe"

解析器对此进行解析。现在的问题是如何处理这些信息。我需要查看我的表并实际找到名字为 John 且姓氏为 Doe 的所有记录。

我在想我可以实现一棵树，它将 AND 作为主节点，并==作为它的子节点。左孩子是名字，右孩子是姓氏。只要它是真的，将该记录推入一个向量，然后在最后打印出该向量。

这一切在理论上听起来都很棒，但我不知道如何实际实现这一点。如果我有一个 if 语句

if(record.firstname == "John")

我如何动态改变==，也许可以!=。

4

1 回答 1

7

您需要将 SQL 翻译成可以直接执行的语言。这方面的技术术语是“查询计划”。查询计划是数据库引擎将执行的低级操作（例如索引搜索、连接、排序），以及这些操作如何组合在一起。

任何体面的数据库引擎都会为您提供查看查询计划的方法。对于 SQL 系统，它通常称为EXPLAIN. 我建议您购买您最喜欢的 DBMS（如果您没有最喜欢的，所有像样的开源 DBMS 都可以，包括 MySQL 和 PostgreSQL），并查看各种查询的计划，以了解哪种操作才是“真正的” "系统实施。

我还建议研究关系代数。如果您可以访问一个藏书丰富的图书馆，那么任何体面的数据库教科书都会有一节或章节，但询问谷歌会返回相当多的好参考资料。关系代数的优势在于它在理论上很好，并且有一种“明显”的方式来使用低级数据库操作来实现它。您最终可能会将其修改得面目全非，但这应该会给您一个良好的开端。

因此，让我们看一个基本概述。首先阅读有关关系代数的内容，然后继续阅读。

您需要实现的主要数据结构是元组流。流中的每个元组都是不同的，但它们都具有相同的形状：元组的每个字段都有一个名称和一个类型。查询操作采用一个或多个元组流（顺便说一下，可以将表视为元组流）并返回单个元组流。

考虑以下形式的基本 SQLSELECT语句：

SELECT fields
FROM table1,table2
WHERE select_conditions, join_conditions

在这里，select_conditions是任何条件，例如gender='F'或age > 18，其中将字段与常数进行比较。是任何将join_conditions一个表中的字段与另一表中的字段匹配的条件。（我们暂时忽略比较同一个表中的两个字段的情况。）

那么一个简单的查询计划可能是：

s1 := Select(table1, select_conditions_1)
s2 := Select(table2, select_conditions_2)
j := Join(join_conditions, s1, s2)
res := Project(fields, j)

该Select操作接受一个元组流，并返回一个具有相同形状的元组流，并删除任何不符合条件的元组。该Project操作接受一个元组流并返回一个不同类型的元组流；它所做的只是删除、重新排列或复制字段。最后，该Join操作将两个元组流连接在一起，连接任何两个匹配连接条件的元组。（如果你不知道什么是数据库连接操作，你真的需要知道这一点。问谷歌，并查找 Unix 的“连接”命令。）

因此，在这种情况下，s1是一个元组流，它表示表 1 中的元组，这些元组与适用于表 1 的选择条件相匹配。对于s2. 流j是流s1并s2根据加入条件加入。最后，您只投影查询中提到的字段。

将 SQL 转换为类似关系代数的中间形式实际上非常容易。然而，简单的翻译往往效率极低。在这里，我们通过检查表中的每条记录并仅返回匹配的记录来实现选择操作。因此，需要根据查询的结构以及表中可用的信息来优化查询。

例如，假设table1有字段age和gender，并且我们有选择条件age > 18和gender = 'F'。进一步假设在该字段上table1有一个索引（称为table1_age_idx）age，但在该字段上没有索引gender。显然我们应该使用索引。我们可以通过将操作拆分为两个更基本的操作来做到这一点：

s1a := IndexSelect(table1_age_idx, age > 18)
s2b := FilterSelect(s1a, gender = 'F')

在这里，我们将选择操作一分为二。第一个选择是使用索引查询实现的（请注意，选择现在在索引上，而不是表上！），第二个可以通过过滤流来实现，删除任何gender不是的元组'F'。

可以通过多种方式实现连接（排序合并连接和哈希连接很流行）。哪一个最好再次取决于查询和数据库。一些索引（例如 B-tree 和朋友）返回按键排序的记录，因此如果您已经IndexSelect对随后加入的字段进行了操作，那么排序合并连接可能会更好，因为排序是不必要的。ORDER BY如果连接字段上有子句，这同样适用。

正如你所看到的，这就是真正聪明的事情发生的地方。真正的查询优化器使用有关表大小和中间元组流的可能大小的统计信息作为其计算的一部分。在这里了解关于编译器的一两件事是值得的。

于 2013-02-21T05:37:02.420 回答