C++ SQL解析器到表

Question

我正在用C++编写一个非常简单的数据库和一个SQL解析器.我做了一切.所以如果我有这样的SQL输入:

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

解析器解析它.现在的问题是用这些信息做些什么.我需要查看我的表,然后找到所有记录的名字是John,姓氏是Doe.

我以为我可以实现一个将AND作为主节点的树,==以及它的子节点.左边的孩子是姓,右边的孩子是姓.只要它是真的,将该记录推入向量,然后在最后打印出向量.

这在理论上听起来很棒,但我不知道如何实际实现这一点.如果我有if语句就好

if(record.firstname == "John")

我如何动态改变==,也许它可能是!=.

Answer 1

您需要的是将SQL转换为可以直接执行的语言.对此的技术术语是"查询计划".查询计划是数据库引擎将执行的低级操作(例如,索引搜索,连接,排序),以及操作如何组合在一起.

任何体面的数据库引擎都会为您提供查看查询计划的方法.在SQL系统的情况下,它通常被称为EXPLAIN.我建议你得到你最喜欢的DBMS(如果你没有最喜欢的,所有体面的开源DBMS都会这样做,包括MySQL和PostgreSQL),并查看各种查询的计划只是为了看看什么样的操作"真实"系统实施.

我也建议研究关系代数.如果您可以访问库存充足的库,那么任何体面的数据库教科书都会有一个部分或章节,但要求Google返回一些很好的参考资料.关系代数的优点在于它在理论上都很好,并且具有使用低级数据库操作实现它的"明显"方法.您最终可能会将其修改为无法识别,但这应该会给您一个良好的开端.

那么让我们看一下基本概述.首先阅读有关关系代数的内容,然后继续阅读.

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

考虑SELECT表单的基本SQL 语句:

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操作将两个元组流连接在一起,连接任何两个与连接条件匹配的元组.(如果你不知道数据库连接操作是什么,你真的需要知道这一点.问Google,并查看Unix"join"命令.)

所以在这种情况下,s1是一个元组流,表示表1中的元组,它们与适用于表1的选择条件相匹配.这是一个类似的故事s2.流j是流s1并s2根据连接条件连接.最后,只计划查询中提到的字段.

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

例如,假设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')

在这里,我们将select操作拆分为两个.第一个选择是使用索引查询实现的(请注意,select现在位于索引上,而不是表!),第二个选择可以通过过滤流来实现,删除任何gender不是的元组'F'.

实现连接可以通过多种方式完成(排序合并连接和散列连接很受欢迎).哪一个最好再次取决于查询和数据库.一些索引(例如B树和朋友)返回按键排序的记录,因此如果您已经IndexSelect在随后加入的字段上完成了,那么排序合并连接可能更好,因为排序是不必要的.如果ORDER BY连接字段上有子句,则同样适用.

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