数据库系统：查询编译
发布时间：2022-09-30 12:40:14 所属栏目：MySql教程 来源：
导读： 本科学得最不好的课大概就是编译原理了吧，各种文法分析、词法分析看得头晕目眩。本文是学习CMU15-721之后的理解和想法。
在数据库查询的执行过程中，经过优化器优化的查询计划需要变成计算机能够理解的
在数据库查询的执行过程中，经过优化器优化的查询计划需要变成计算机能够理解的
|
本科学得最不好的课大概就是编译原理了吧，各种文法分析、词法分析看得头晕目眩。本文是学习CMU15-721之后的理解和想法。 在数据库查询的执行过程中，经过优化器优化的查询计划需要变成计算机能够理解的代码才能被数据库系统执行。将抽象的查询计划转化成具体的可执行代码的过程就是查询编译。 在现代数据库系统里，查询编译器接收来自优化器的查询计划，计划里每个操作符（operator）的算法（比如用哪种连接算法，是否用索引）已经由优化器决定，编译器的只扮演将操作符实际转化成可执行代码的角色。 Interpretation 最简单的、将操作符转化成可执行代码的方法是interpretation，即“翻译”成可执行指令。SQL查询可以抽象成一棵由操作符组成的树数据库查询操作，树的每个节点都是一个操作符，所谓interpretation，就是动态构建这棵树的过程。 比如以下这个简单的查询： select * from A, B where A.a = 'a' and B.b = 'b' and A.aid=B.bid; 就可以抽象成一棵这样的树： 在数据库系统中，调用相关的函数，就可以构造出这样的一棵树： class QueryExecPlan { ... Operator* root; void exec(...); }; ... class Operator { Operator* child1, child2; void exec(...); } class HashJoinOp: Operator {...}; class SelectOp: Operator { void exec(....); Predicate* predicate; }; class ScanOp: Operator {...}; // scan the given table /// building execution plan QueryExecPlan* plan = new QueryExecPlan(); plan->root = new HashJoinOp(); plan->root->child1 = new SelectOp(...); .... plan->exec(); 从上面简单的示例可以看到，数据库在找到查询计划之后，动态生成一棵查询树的过程。通过这棵动态生成的树，就可以实际执行这个查询，并得到查询结果。 需要注意的是每个操作符都实现了一个exec函数，用来实际执行这个操作符的算法。尽管每个操作符的exec函数实现的内容都不一样，但它们都会满足一个编程范式（paradigm），而这个范式也是数据库系统的查询执行模型（query execution model）。常用的有iterator model (volcano model）、materialization model和vectorization model。本文只讨论最常见的iterator model。 这种简单interpretation方法有一个最致命的缺陷：对谓词（表达式）的处理。在上面这个例子中，需要判断A.a是否等于‘a'，看似很简单，但对于系统而言，却需要搞清楚两个方面的问题： 表达式的结构表达式中操作数（operand）的数据类型 第二点简洁明了：由于系统对不同数据类型的比较会产生不一样的结果，因此，在构造表达式的时候绑定类型非常必要。第一点对系统来说则更复杂。构造一个简单表达式，如“a==(b+c)/2+d"对计算机而言并不是那么简单。要判断这种表达式，计算机需要构造一棵表达式树，并递归地算出每部分的值，最后判断结果是否为真。 这就引入了一个十分巨大的优化空间：对简单表达式而言，如上述的"(b+c)/2+d"，如果这几个操作数都是整数，将之转化为cpu指令，要比转化为表达式树要少得多（至少不需要构造、遍历表达式树）。尤其是当这个表达式要被经常用来判断元组是否满足条件时，遍历树的成本显得十分显著。 Query Compilation 为了能活用现代计算机语言的表达式处理能力，query compilation应运而生。2010年的ICDE会议上，爱丁堡大学信息学院发表的论文：Generating code for holistic query evaluation（HIQUE），提出用代码模版（code template）的方法动态生成与查询计划对应的c++代码，并用编译器将其编译成可供系统调用的动态链接库，通过执行由codegen产生的代码来获得查询结果。 “...system call invokes the compiler to compile the source file into a shared library file. This step allows the application of aggressive compiler optimizations that target the code of the specifific query. The shared library file is then dynamically linked and loaded by the query executor. “ 论文的代码模版 除了codegen之外，为了让cpu尽可能访问处于cache中的数据，论文还对nested loop join做了一定程度的优化： hash join将对两个table做partition。如果连接属性的取值很少（value-partition map可以放入到cache里），那么这里将对这个属性值进行分组；反之，则利用别的哈希方法对整个元组进行分组（这里不会用到哈希表，避免random access而出现的cache miss）。之后，会对每个分组进行排序，排序完成之后再进行连接的操作。尽管这个算法看起来是nested loop join，但在内循环中，每个分组实际上是排好序的，可以根据属性值来判断是否需要继续进行连接，因此更像是sort-merge join。 除开论文对cache访问、存取的一些优化外，codegen对于查询效率提升也是巨大的。首先是c++语言对不同数据类型的支持，使得系统不需要再为类型绑定而烦恼。只需要在生成代码中“声明”不同类型的变量，就可以利用编译器轻松处理这些不同的数据类型。同时，在codegen生成的代码中，我们能轻易得到指向某个元组的裸指针，甚至能通过指针计算来更快访问下一个元组（而不是用iterator，但也可能不安全）。而最大的好处，则是对于谓词表达式，不再需要构建复杂的表达式树来判断不同的元组是否满足表达式的条件，而是通过生成c++的表达式，编译成cpu指令，执行效率得到巨大提升。 另外，编译器还可以针对生成的代码进行优化（如-O2），或者针对当前计算机的硬件进行特殊优化，都能使效率得到极大的提升。 JIT Compilation 当然，HIQUE并不是就无所不能。将codegen出来的代码进行编译，并被系统调用是一件开销非常大的事情。尤其是，当一个查询十分简单的时候，将代码编译成可执行的动态链接库就已经是一个非常显著的消耗。而且，正如作者在文中说的那样，HIQUE基于的iterator model本身就有不少的局限性： 过多的函数调用。每个operator都要调用next函数来获得child operator的结果。cpu会频繁更新寄存器和栈中的值，提高了指令复杂度。iterator model每次只会emit一个元组给上层的operator，但cache实际上能容纳更多的元组给上层处理。 基于这些缺点，TUM的Thomas Neumann在2011年的VLDB上发表了Efficiently Compiling Efficient Query Plan for Modern Hardware, 不但减少了HIQUE在编译上的过度消耗，还对已有的iterator model进行了优化，这也是Hyper系统的基础之一。 为了解决编译速度的问题，Hyper的codegen选择直接生成LLVM IR代码，它的编译速度比C++快很多。 And finally LLVM is a full strength optimizing compiler, which produces extremely fast machine code, and usually requires only a few milliseconds for query compilation, while C or C++ compilers would need seconds. 尽管编写LLVM IR模版代码的难度比C++大很多，但LLVM和C++之间的函数能够相互调用，在一定程度上这个问题得到了缓解。 But one can easily mix LLVM and C++, as C++ methods can be called directly from LLVM and vice versa. 除此之外，Hyper还对iterator model进行了深入的改良和优化。文中提到了pipeline breaker的概念——即必须要等待物化/传递数据完成的操作符。举个例子： 图中的聚集和连接操作，都需要拿到所有的数据之后才能继续进行操作，而在此之前，我们只能把现在得到的数据存下来。而选择操作符则相反，无论输入的元组是什么都能马上输出结果。Hyper根据查询计划，将其分成了若干个pipeline，每个pipeline内部是“非阻塞”的，即无论输入怎样的元组，都能马上得到输出。而每个pipeline都会被一个pipeline breaker阻塞，即要把当前得到的结果存下来，等pipeline的全部结果处理完之后才能继续。 另外，codegen的过程也和HIQUE有很大的差别。iterator model通过next/emit来在不同的operator之间传递结果，但频繁调用这些函数的缺点在于：cpu不断在不同的可执行过程之间切换，寄存器和栈的值也在不断的修改——这对系统的执行效率产生了极大的影响。为了让元组在寄存器（或者cache）中的时间尽可能长，Hyper的codegen用produce/consume的方式来获取下层operator的结果。 上层的操作符在执行开始时调用produce，则会触发其子操作符的produce，直到触发了叶子节点的produce。这时，叶子节点就会根据访问方法（access method）来对实际数据进行访问。这个produce方法会调用codegen模块，生成访问的实际代码。得到结果元组之后，叶子节点“调用上层operator的consume函数”，来对生成出来的元组进行进一步处理。这里要注意的是，consume函数并不是一个实际存在的函数，而是会调用codegen模块，生成处理这个元组的代码。处理完之后，继续调用上层操作符的consume，直到遇到pipeline breaker。pipeline breaker的“consume函数”会生成缓存当前元组的操作代码，并把这个元组写到内存里，等待其获取完所有需要操作的元组。同样的，pipeline breaker完成自己的所有操作之后也会触发其父操作符的consume函数。基本过程如下图所示： 数据库查询操作_工作表合计行数据设置为货币格式 利用菜单完成操作_操作必须使用一个可更新的查询 和传统iterator model不同的地方在于，Hyper是根据数据来规定处理边界的（每个pipeline为一个处理边界）。而iterator model则更符合直觉，让每个操作符成为处理边界。同时，iterator model通过让父操作符不断调用next函数来循环获取子操作符的结果；而Hyper则让子操作符产出数据之后，通过回调的方式，将满足条件的结果推给父操作符进行继续处理。这也是常说的“Pull vs. Push"。 总结 本文简单总结了数据库系统的查询编译过程，基本只是浅尝辄止，没有深入研究算法和实现的细节。希望以后能对此进行完善。 （编辑：PHP编程网 - 钦州站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐
浙公网安备 33038102330484号