一种基于等价类的数据库内核查询优化方法

摘要

本发明适用软件领域，提供了一种基于等价类的数据库内核查询优化方法，所述方法包括：在查询语句进入子查询优化器之后，使用函数处理sql语句中关键词from之后以及关键词where之前的描述：处理显式连接的嵌套树结构或者一个没有指定连接方式的链表，提取表信息，获取表对象，初始化其包含的Col和Eclass位变量，填充链表RELS；处理sql语句中on之后和where之后的限制条件链表quals，依据Eclass位变量对限制条件进行传递；进入枚举器，依据Eclass位变量扩大计划搜索空间，枚举出更多的等价计划，进入代价计算器计算代价；获取最小代价的计划作为最终的执行计划，执行计划被编译成执行树，被传送到执行器中执行。本发明具有性能高的优点。

说明书

技术领域

本发明属于软件领域，尤其涉及一种基于等价类的数据库内核查询优化方法。 

背景技术

早期的数据库管理系统的整体架构，无论是从安全性还是内存硬件环境考虑上，都是以占用较小内存的角度进行设计。所以大多数传统关系数据库的数据检索执行操作都采用了一个需求——拉动的流水线机制（a demand-pull pipeline mechanism）：系统每次调用一个计划节点（plan node），这将从下面的节点获取一条记录或者空记录。内存中驻留的数据页个数最多只有查询树叶子节点个数，这种机制可以较大地节省内存的使用，它可以高效的应用于单表数据的简单提取、验证等工作。但是关系数据库管理系统的多表连接或者复杂计算时，往往需要大量数据驻留内存。现在计算机的内存技术高速发展，计算机配置的内存容量在不断增长，数据库内核也随此不断改进。在原始的需求——拉动的流水线机制下，传统数据库内核开始允许中间叶子节点的数据驻留。这样，新的问题出现，即当中间叶子节点的数据太大而超过内存时，内存的数据会与磁盘就行交互，即磁盘作为虚拟内存存在，这种场景下，数据库系统由于频繁的IO操作而使得性能迅速降低，因此，尽量减少中间叶子节点的数据量不但是对后面CPU的大量减少，也是IO的一个重要优化手段。 

传统关系数据库中使用等价类对等值连接的表进行标记，等价类标记的等值连接集合，被放在连接树的底层，被优先进行连接，这样做的好处是避免了笛卡尔积（cart-prod）连接先执行，所以，基于等价类的启发式策略可以很大程度上减少查询优化模块的计划搜索空间。另一方面，等价类是离散数学中的重要概念，自身具有自反性、对称性和传递性；它在数据库知识发现等领域大 量用来作为数据约简的重要手段，但是，现有数据库管理系统并没有在查询优化模块中充分利用等价类的属性约简特性，以及等价类成员的过滤条件的共享。等价类的这些特性的不充分利用直接导致数据库内核丧失了及早过滤数据的机会，使得中间结果过大，导致CPU和IO的消耗巨大，最终造成数据库查询性能的下降。 

再者，传统数据库管理系统大多是使用基于代价的查询优化方法（COST BASED OPTIMIZATION）。基于代价的优化器要尽可能的枚举出所有计划，计算每一个计划的代价，并最终选择代价最小的计划传递给执行器。传统数据库没有充分利用等价类挖掘潜在信息的功能，错失了更为优化的查询计划，直接导致最终的查询执行性能的降低。例如，优化器没有充分利用等价类使得没有获取到关系数据基表潜在特性，可能会使得基表不能过滤足够的数据，继而使得优化器没有启动索引，最终导致检索效率降低。 

发明内容

本发明实施例的目的在于提供一种基于等价类的数据库内核查询优化方法，其解决现有技术存在的数据库某些查询性能低的问题。 

本发明实施例是这样实现的，一方面，提供一种基于等价类的数据库内核查询优化方法，所述方法包括： 

在触发查询优化后，进入子查询优化器之后，使用函数处理sql语句中关键词from之后以及关键词where之前的描述：进入显式连接的嵌套树结构或者是一个没有指定连接方式的链表，提取表信息，获取表对象，初始化其包含的Col和Eclass位变量，填充链表RELS。 

处理sql语句中on之后的限制条件链表quals； 

处理sql语句中where之后的描述； 

遍历DISTINCT、ORDER BY、GROUP BY属于列特性的链表，根据Eclass变量找到其对应的等价类，将这些特性上升为整个等价类的特性；等价类将这些 特性传递到它的每一个成员中；对等价类的每个成员添加这些特性可以为后面的优化操作使用； 

遍历sql中的quals链表，对每一个单目的qual找到对应的列，根据列对象REL的Eclass对象找到对应的唯一一个等价类，根据这个等价类的位图变量Col找到其他的列，将单目约束条件qual传送到这些列成员之中； 

进入枚举器，每当产生一对输入条件，判断一对输入条件在等价类中是否存在，如存在，进入代价计算器；获取最小代价的计划作为最终的执行计划，执行计划被编译成执行树，被传送到执行器中执行。 

可选的，所述判断一对输入条件在等价类中是否存在的法则具体包括： 

计算一对输入条件中两个表对象REL中的位图变量Eclass的相与操作结果，如果与操作结果不为零，确定等价类中存在等值关联；否则，不存在等值关联。 

可选的，所述处理sql语句中on之后的限制条件链表quals具体包括： 

获取列对象，初始化其包含变量Rel和Eclass；Rel根据已有的REL对象赋值，根据COL生成一个等价类对象EC，Rel根据该EC生成为其包含的Eclass赋值，最终COL填充COLS链表；同时，该生成的等价类对象根据已有的RELS和COLS为其Rel和Col变量赋值。 

可选的，所述生成的等价类对象根据已有的RELS和COLS为其Rel和Col变量赋值包括： 

寻找inner连接的有效等值连接；如果存在有效的等值连接，应该检查ECS看看涉及到的两个等价类是否单独存在，如是，则将这两个等价类合并到一个等价类中，另一个等价类将被剔除，同时要修改REL和COL中的Eclass变量。 

可选的，所述处理sql语句中where之后的描述包括： 

回到sql语句中的目标链表，select之前，from之后，整理其他的列信息，生成对象COL，赋值Rel和Eclass变量，继续填充COLS链表；并添加对应的等价类。 

在本发明实施例中，本发明提供的技术方案充分利用等价类的传递性，将等价类中的一个成员的属性传递到该等价类的其他所有成员，为优化做好基础，并最终实现新的优化策略，所以其具有提高数据库查询性能的优点。 

附图说明

图1是本发明提供的一种基于等价类的数据库内核查询优化方法的流程图； 

图2是本发明实施例提供不同过滤条件的执行时间的折线图。 

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。 

首先，本发明的具体实施方式需要定义三个全局链表RELS、COLS、ECS分别用来存储在查询语句分析过程中逐次生成的表对象、列对象和等价类对象。RELS存储表对象（REL），REL包含两个位变量Col和Eclass，代表该表对象REL与其他列对象或等价类对象的关联；COLS存储列对象COL，列对象包含两个位变量Rel和Eclass，代表该列对象COL与其他表对象或等价类对象的关联；ECS存储等价类对象EC，EC包含两个位变量Rel和Col，代表该等价类对象EC与其他表对象或列对象的关联。 

本发明具体实施方式提供一种基于等价类的数据库内核查询优化方法，该方法如图1所示，包括： 

101、在触发查询优化后，进入子查询优化器之后，使用函数（process_from_clause，该函数也可以为其他形式的函数）处理sql语句（或者子sql语句）中关键词from之后以及关键词where之前的描述 

：进入显式连接的嵌套树结构或者是一个没有指定连接方式的链表，提取 表信息，获取表对象（REL），初始化其包含的Col和Eclass位变量，填充链表RELS。 

102、如果存在显式连接，处理sql语句（或者子sql语句）中on之后的限制条件链表quals；获取列对象(COL)，初始化其包含变量Rel和Eclass；Rel根据已有的REL对象赋值，根据COL生成一个等价类对象EC，Rel根据该EC生成为其包含的Eclass赋值，最终COL填充COLS链表；同时，该生成的等价类对象根据已有的RELS和COLS为其Rel和Col变量赋值。寻找inner连接的有效等值连接。非inner连接设计到的列不能加入等价类中形成新的等价类对象Eclass。如果存在有效的等值连接，应该检查ECS看看涉及到的两个等价类是否单独存在，如是，则将这两个等价类合并到一个等价类中，另一个等价类将被剔除。同时要修改REL和COL中的Eclass变量。 

103、处理sql语句中where之后的描述。回到sql语句中的目标链表（select之前，from之后），整理其他的列信息，生成对象COL，赋值Rel和Eclass变量，继续填充COLS链表；并添加对应的等价类，该等价类如果是新生成的，那么一般就只有一个等价类成员。 

104、遍历DISTINCT、ORDER BY、GROUP BY（后面会作为排序处理）等属于列特性的链表，根据Eclass变量找到其对应的等价类，将这些特性上升为整个等价类的特性。等价类将这些特性传递到它的每一个成员（列）中；对等价类的每个成员添加这些特性可以为后面的优化操作使用。 

105、遍历sql中的quals链表，对每一个单目的qual找到对应的列。根据列对象REL的Eclass对象找到对应的唯一一个等价类，根据这个等价类的位图变量Col找到其他的列。将单目约束条件qual（例如A>2）传送到这些列成员之中。 

106、进入枚举器，每当产生一对输入条件，判断一对输入条件在等价类中是否存在，如存在，进入代价计算器。判断的法则是计算一对输入条件中两个表对象REL中的位图变量Eclass的相与操作结果，如果与操作结果不为零，那 么意味着这两个表可以进行等值关联，可以进行连接操作；否则，不存在等值关联而进行连接操作会造成一个等价类节点的底层子节点出现笛卡尔连接，最终产生一个中间结果将会非常巨大的糟糕计划。 

107、进入代价计算器，获取最小代价的计划作为最终的执行计划，执行计划被编译成执行树，被传送到执行器中执行。 

实施例 

假设存在表t1、t2和t3，t1、t2和t3分别有两个列col1和col2。对于查询语句：“select t1.col1,t2.col2,t3.col2from t1,t2,t3where t1.col1=t2.col2and t2.col2=t3.col1and t1.col1>0.9order by t2.col2”，按照本发明的思路，具体的流程如下所示： 

1、进入查询计划器，循环进入子查询计划器，全局链表RELS、COLS、ECS分别用来存储在查询语句分析过程中生成的表对象、列对象和等价类对象。初始化链表如表1所示。当对象结构的个数超过八个，位图变量（如Rel\Col\Eclass）可以动态加载，这里只是使用一个字节的位来说明举例。全局位变量记录着各个对象的Id编号，而对象中的Rel\Col\Eclass记录与全局变量的对应以及变量之间的关联。 

表1：初始化全局链表RELS、COLS、ECS 

2、进入子查询优化器之后，处理sql语句中关键词from之后、关键词where之前的表t1、t2和t3。全局变量RELS初始化，如表2所示。继续处理on子句，由于本实例没有on子句，找不到列的信息以及inner join的信息，所以Col和Eclass没有发生变化。 

表2：全局变量RELS初始化 

3、进入where子句的处理中，遍历条件链表，出现等值连接的描述t1.col1=t2.col2，所以在这里改变全局等价类变量Eclass的值为10000000。即，出现等价类｛t1.col1t2.col2｝。改变Col为11000000，而t1、t2和t3中的Col变量分别为10000000、01000000和00000000，t1和t2中的Eclass变量都是10000000，t3中的Eclass变量是00000000。如表3所示。 

表3：处理where的RELS、COLS、ECS的变化 

4、继续遍历，出现第二个等值连接的描述t2.col2=t3.col1，添加新的列t3.col1。由于存在其他的等价类｛t1.col1t2.col2｝，而且该等价类的成员存在于等值连接的描述之中，所以需要考虑等价类的合并。即将t3.col1加入第一个等价类中，等价类变量Eclass不变，但是它的成员增加，Id编号为0的 等价类集合边为｛t1.col1t2.col2t3.col1｝。改变其Rel和Col的值为11100000，改变t3中的Col变量为00100000，改变t3中的Eclass变量为10000000。调整Id为2的COL对象的Rel和Eclass分别为00100000和10000000。如表5所示。 

表5：处理where的RELS、COLS、ECS的变化 

继续遍历，出现一个约束限制条件t1.col1>0.9，将限制条件记录在限制条件链表quals。如表6所示： 

表6：限制约束条件的记录 

5、回到sql语句中的目标链表（select之前，from之后）：列t1.col1和t2.col2已经存在，而t3.col2是不存在的，生成新对象COL，赋值Rel和Eclass变量，继续填充COLS链表；并添加对应的等价类，该等价类只有一个等价类成员。如表8所示： 

表8：目标属性的添加 

6、记载DISTINCT、ORDER BY、GROUP BY特性。在本例中存在“order by t2.col2“，所以COLS的相关修改信息如表9突出显示所示。 

表9：目标属性的添加 

7、遍历quals链表，找到单目约束条件t1.col1>0.9，t1根据其局部变量Eclass（值为10000000）找到t1.col1所属于的等价类｛t1.col1t2.col2t3.col1｝。将col>0.9的约束条件传播到该等价类的各个成员，即会获得t2.col2>0.9和t3.col1>0.9。并将该约束条件挂载到表t2和表t3的限制约束条件中。同时，由于存在order by t2.col2的特性，这个等价类中的其他成员也共享这个特性，所以都会具有排序的特性。修改之后的COLS如表10中突出显示所示： 

表10：列的特性传递 

8、进入计划枚举器。当产生t1和t3先于t2进行连接的时候，使用t1和t2的局部变量Eclass（都为10000000）进行位的与操作结果为10000000，即存在等价类｛t1.col1t2.col2t3.col1｝，尽管没有显式的t1.col1=t3.col1，但是仍然可以根据该等价类获得该连接条件，并会传到代价计算器中进行计算。最终选择代价最小的计划，传递到执行器执行查询操作。 

为了验证本申请提出的新的架构路线的有效性，在PostgreSQL的最新版本9.2.4中实现。本处将采用一组随机的试验数据，采用了1000000的随机数据的对比试验，试验的创建语句如下所示： 

CREATE TABLE rdmt1(random float); 

CREATE TABLE rdmt2(random float); 

INSERT INTO rdmt1SELECT random()FROM generate_series(1,1000000); 

INSERT INTO rdmt2SELECT random()FROM generate_series(1,1000000); 

其中random()是PostgreSQL的系统函数，随机产生0～1的随机数； 

generate_series(1，1000000)是产生从1到1000000的序列数。插入语句表示对表rdmt1和rdmt2分别插入1000000个随机浮点数（0～1）。将生成的数据分别导入到修改前后的数据库中。在PostgreSQL的客户端psql执行查询语句：“explain select count(*)from rdmt1,rdmt2where rdmt1.random=rdmt2.random and rdmt1.random>0.9;”。修改后的PostgreSQL得到的查询计划如下文所述。对表rdmt2创建一个常规B树索引rdmt2_random_idx，并分别查看查询计划，未改进的PostgreSQL产生查询计划没有改变。但是改进的PostgreSQL的查询计划有了非常大的变化如下文所述。 未修改的PostgreSQL得到的查询计划如下： 

修改后的PostgreSQL得到的查询计划如下： 

改进的PostgreSQL对有索引数据的查询计划如下： 

未修改的PostgreSQL得到的查询计划中显示，由于PostgreSQL9.2.4没有充分利用等价类的传递性，使得约束过滤条件（random>0.9::double precision）没有等价传递到主表rdmt2上，而修改后的PostgreSQL中，约束过滤条件可以传递到主表rdmt2上，查询计划的突出显示部分。而且，当给主表rdmt2增加一个b树索引之后，未改进的PostgreSQL的查询计划仍然不变。但是，改进的PostgreSQL的查询计划进一步变成改进的PostgreSQL对有索引 数据的查询计划（突出显示部分），即过滤条件等价传递到了主表rdmt2之后，触发了索引的使用。 

为了避免操作系统内存调度策略的影响以及PostgreSQL后台checkpoint周期操作的影响，每个计划执行了20次，并记录其中最短的时间。上面三个查询语句的执行花费的时间分别是495.871ms、280.945ms和216.502ms。可以看出执行的时间是不断减小的。由于random()产生的随机浮点数几乎是均匀分布的，限制条件“random>0.9”大概是过滤了十分之九的数据，所以改进后的PostgreSQL执行效率要提高很多。为查看过滤数据大小对执行性能的影响，本文又做了八组试验，将过滤的数据逐渐减小。将random的过滤条件每次减小0.1测的时间结果如下表11所示： 

表11：不同过滤条件的执行时间（单位：ms） 

表11的数据画成的折线图如图2所示。在表8中我们可以清晰的看到改进的PostgreSQL执行效率明显的优于未改进的PostgreSQL。并且改进的PostgreSQL在一定的条件下可以触发索引的使用。当限制数值为0.7、0.8、0.9的时候，索引被加入，也就是说优化器经计算加入索引的代价比较小，“最优”路径就加入了索引。所以在图中可以看出，限制数值在0.1到0.6之间，有无索引的改进PostgreSQL执行效率几乎是一样的。 

从表11中可以看出，当限制数值为0.9的时候，没有改进的方案的查询时间是495.871ms，改进后的PostgreSQL的执行时间是280.945ms，性能提高了43%。加入索引之后，原来的计划仍然没有改变，即并没有用到索引。而修改后的PostgreSQL使用了新的索引，并且执行时间为216.502ms，性能提高了56%。可以看出，性能有了比较大的提高，证明了本文设计的针对等价类的 新架构方法的高效性。 

本领域普通技术人员可以理解实现上述各实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，相应的程序可以存储于一计算机可读取存储介质中，所述的存储介质，如ROM/RAM、磁盘或光盘等。 

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。