你需要的是将SQL翻译成可以直接执行的语言。技术术语是“查询计划”。查询计划是数据库引擎将执行的低级操作(例如索引搜索,连接,排序)以及操作如何组合在一起。
任何体面的数据库引擎都会为您提供查看查询计划的方法。在SQL系统的情况下,通常称为EXPLAIN
。我建议让你最喜欢的数据库管理系统(如果你没有最喜欢的,所有体面的开源数据库管理系统都会这样做,包括MySQL和PostgreSQL),并查看各种查询的计划,以查看“真实“系统实施。
我也推荐关注关系代数。如果您可以访问库存充足的图书馆,任何正规的数据库教科书都会有一个章节或章节,但要求Google返回不少好的参考资料。关系代数的优点是它在理论上都很好,并且有一个“明显”的方式来使用低级别的数据库操作来实现它。您最终可能会将其修改为无法识别,但这应该会给您一个良好的开始。
让我们来看一个基本的概述。先阅读有关关系代数的内容,然后继续阅读。
您需要实现的主要数据结构是元组流。流中的每个元组都是不同的,但它们都具有相同的形状:元组的每个字段都有一个名称和一个类型。查询操作采用一个或多个元组流(顺便提一下,表可以看作是元组流)并返回单个元组流。
考虑形式的基本的SQL语句SELECT
:
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
在age
字段上有一个索引(称为table1_age_idx
),但在gender
字段上没有索引。显然我们应该使用索引。我们可以通过拆分操作做到这一点到两个基本操作:
s1a := IndexSelect(table1_age_idx, age > 18)
s2b := FilterSelect(s1a, gender = 'F')
在这里,我们分离了选择操作两成。第一个选择是使用索引查询实现的(请注意,select现在位于索引上,而不是表!),第二个可以通过过滤流实现,删除gender
不是'F'
的任何元组。
实现连接可以通过很多方式完成(排序合并连接和散列连接都很流行)。哪一个最好再次取决于查询和数据库。某些索引(例如B树和朋友)会返回按键排序的记录,因此如果您已经在随后加入的字段上完成了IndexSelect
,则排序合并连接可能会更好,因为排序是不必要的。如果连接字段上有ORDER BY
子句,则同样适用。
正如你所看到的,这是真正聪明的东西发生的地方。真正的查询优化器使用有关表的大小以及中间元组流的可能大小的统计信息作为其计算的一部分。在这里知道一些关于编译器的东西是值得的。
只是一个小小的评论。也许你可以在SQLite代码中找到一些答案 – cha 2013-02-21 05:21:13
制作一个数据库很困难,甚至很简单。一个使用动态查询语言的人真的很难。 – 2013-02-21 05:22:59
与您的问题更相关,如果您之前没有编译/解释器,这将会非常困难。 – 2013-02-21 05:24:31