查询处理及优化教案

查询处理及优化教案（共1篇）

1.查询处理及优化教案 篇一

近年来,一些数据密集的应用已经广为人知,这些应用中数据的到达非常快速,并且会随时间而变,甚至可能是无法预测的,数据量看起来也是无界的,这样的应用例子有:金融应用、网络监测、安全、通讯数据管理、Web应用和制造和传感网络等。这些应用中,数据源会不断地产生出大量的数据,比如股票交易中,股票的交易数据会不断涌入,这种类型的数据应该被视为易逝的数据流[1]。

在数据流模型中,不支持对部分或全部数据的随机访问,而是以持续数据流的形式到达。概括地说,与传统存储关系模型不同,数据流主要有如下几个方面的特征:

实时性数据流中的数据元素是在线到达的,并要求对它的处理也是近乎实时的;

无序性系统无法控制将要处理的新到达的数据元素的顺序,不论是对一个数据流还是在多个数据流之间;

无穷性流式数据本身就意味着数据量的无限大,而系统存储的数据相对数据流大小则是非常有限的;

瞬时性流中的数据一旦经过处理,要么被丢弃,要么被归档存储。但被丢弃的数据元素可能需要再次被访问。

时序性数据流模型中查询是相对静止不变的,而数据是时刻变化的。

对持续数据流的查询和对传统数据库的查询类似,但数据流模型下的查询具有两个一般数据库系统所没有的特点:

第一个特点是存在一次性查询和持续查询的区别。一次性查询是根据某个时间点数据集的状态计算查询结果,再把结果返回给用户。传统的数据库管理系统(DBMS)查询通常都属于一次性查询。相反,持续查询是在数据流持续到达情况下的持续计算。在数据流模型下,持续查询比一次性查询更普遍,持续查询的答案是基于时间的,它反映了到目前为止已到达的数据流的情况。当新的数据到达时,持续查询的结果可以被存储或更新。有时候查询结果本身也可表现为持续的数据流。数据流模型下一次采用一次性查询还是持续查询,得根据具体应用环境确定。例如,需要多次执行,但每次执行只产生少量的查询结果的聚集查询适合存储数据库模型下的一次性查询;而连接查询往往只需执行一次,但执行一次需要很长时间,并且产生持续的、海量的查询结果,更适合使用数据流模型下的持续查询。

第二个特点是存在预定义查询和特定查询的区别。预定义查询是指在任何相关数据到达前就已经提交给数据流管理系统的一种查询。虽然一次性查询也可以被预先定义,但预定义查询通常是持续查询。与此相反,特定查询是指在数据流已经到达后的在线查询。由于特定查询不能提前预知,因此无法找出不同查询间的公共子表达式从而对查询进行优化;计算特定查询有时需要引用数据流中历史的数据元素,而这些数据很可能已经丢弃了。

此外,传统数据库查询的数据对象是相对稳定的,至少在查询进行的过程中被认为是不变的;而数据流查询的数据对象则不断的变化,持续增长。传统查询执行的过程中可以利用索引、排序或分类等技术对数据对象进行随机存取,查询执行的次数完全取决于应用系统;而数据流查询对于持续输入的数据流只能采取线性扫描算法,在数据对象过期之前进行有限次数的查询[2]。

由于数据流在容量上可能是无限的,为了计算数据流查询的精确结果,所需的存储器容量也会无限制地增长。传统的处理数据集的算法不适合于数据流应用系统,因为它不支持持续查询。由于存储器的容量是有限的,对无限的数据流查询就不可能总是产生精确的结果,用高质量的近似结果来替代准确结果往往是可以接受的。数据流问题的近似算法在近年来已成为一个富有成效的研究领域,这其中高效查询的优化处理就成为其中的一个热点。

1 优化处理算法模块设计

当前数据流系统中存在如下几个显著的特征[3]:

(1)DS系统中存在着大量的查询,系统应该尽快地找到关心该数据的查询。

(2)对单个查询而言最优的查询计划未必对全局来说是最优的。

(3)大量查询中存在着的共同特征,查询分组技术已经在传统DBMS和一些DSMS中被证明为一种非常有效的技术。

(4)数据流系统的执行效率不仅和输入数据的速率有关,还和系统中算子的数量有关,和实际引发的查询的数量有关。如何尽量减少系统中存在的活动算子的数量也是优化需要考虑的一个问题。

基于此,设计优化模块时提出的基本目标就是:充分利用查询之间的共同特征,尽可能在查询之间实现共享;另外,调度器采用高效的调度算法使得运行时的开销最小;追求系统整体性能的提高[4]。

优化处理算法模块的组成结构如图1所示。

图1中查询优化的输入是解析后的查询树。DSMS以访问内存数据为主,且查询的数量非常庞大,因此DSMS系统的主要优化方向是减少DSMS系统中实际引发的查询的数量。连接运算代价非常大,因此DSMS将连接运算向下压,先进行连接运算,多个查询共享一个连接运算,减少了实际引发的连接操作的数量。因此,优化处理模型中的优化首先对连接进行分组,以便较大程度地在不同的连接之间共享中间结果,节约了DSMS系统中最为宝贵的主存资源。完成连接分组后,再对谓词进行分组,将相同结构的谓词组织在一个表结构中,这样实际引发的查询的数量就会大大减少[5]。

2 基于连接谓词约束的等值连接分组算法

目前为止,虽然对连接查询提出了大量的优化算法,但是针对多查询优化的连接分组优化算法却未见应用于数据流系统中,这里实现的是基于连接谓词约束的等值连接分组算法。

2.1 连接分组算法设计

连接分组的输入条件是Get Table Link中的表列和Get Where中的等值连接条件。输出结果是网络节点。如果一个节点表示一个用户查询的话,则就称该节点为终端节点,在用户明确地将查询删除以前,终端节点是不能删除的,与之相对应的是非终端节点,非终端节点没有对应的用户查询,只是保存连接的中间结果,当连接计划改变后非终端节点可能会被删除。我们的连接分组连接结果都只是增加一个基本表(流),采用类似System R优化器的结构,也特别适合流水线处理,而对于数据流来说,所需的处理方式正是流水处理方式。

基于连接谓词约束的等值连接分组算法中,连接运算的优化分为两个阶段;第一阶段为增量分组阶段;每当一个新的查询提交后,系统查找当前存在的分组,检测是否存在一个分组与新提交的查询对应,如果存在则不用创建任何分组,只需要把这个分组的引用次数加一即可;如果不存在则需要创建新的分组与这个查询对应,新的分组可以利用已经存在的分组作为自己实现的一部分。

连接运算查询优化的第二阶段为动态重分组阶段;增量分组对新加入的查询进行分组而不对存在的查询进行重分组,尽管这种查询也是有效的,可扩展的,但是它可能导致只是局部的优化,已经存在的查询没有在新查询加入时为了适应新的全局优化要求而获得重新分组的机会。

随着增量分组的进行,系统中创建了很多分组,但是对当前存在的所有查询来说,有一些分组是不必要的,或者说是冗余的,冗余分组的计算消耗了系统很多资源,因此应该动态地把这些冗余分组删除,重新创建系统的分组图,使系统尽可能地达到全局最优。

2.2 连接分组算法实现

2.2.1 基本数据结构

所有的连接节点在逻辑上是一个有向无环图,图中的每个节点都代表一个分组计划中的一个连接表达式,该节点的结构为:

2.2.2算法表示

1)增量分组Increment Group

输入:int tableids,连接约束A(目前实现的是等值连接),inttime＿t。

输出:目的节点。

示意代码实现如下所示:

该算法的过程是:

Find MaxGroup:用于找到输入的连接对应的最大连接分组,输入是表列tableids和连接约束条件,以及时间窗口。连接的中间结果都是通过索引结构记录下来,因此,Find Max只需按照哈希表的长度由大到小地遍历哈希表即可,一旦找到就停止。由于,目前为止我们规定表的最大长度为10,因此这一步的开销并不是很大。另外,目前的连接约束条件只包含等值连接,只有符合约束的连接才会被用到。

Get Constraint:得到节点B的连接约束条件,B是A的一个子集。

Get Left Table Id:得到剩余表的列表。

Ramdom Join:利用约束条件Left Constraint在node和剩下的表列随机生成连接结果(也可以按照刷新频率由小到大的次序选择基本表)。

2)动态重分组Re Group

当系统经过一段时间时,查询有的是新加入的,有的则运行一段时间后便从系统中注销,因此这时候系统的状态不一定是最优的。因此,运行一段时间后就需要对系统进行重新分组。

输入:不同长度的哈希表。

输出:重新分组优化后的查询网络。

动态重分组中,首先按照长度从大到小的规律遍历哈希表,因为终端节点是不能删除的,因此首先检查每个终端节点,如果该终端节点的父母节点的孩子节点不是此终端节点,就用子节点代替这个孩子节点,代替的过程同时检查约束条件,只有符合约束条件才能替代。检查完终端节点后,再检查非终端节点,如果发现非终端节点的引用计数等于零,就将其删除,因为已经没有父母节点引用该节点的结果了。

由于动态重分组每次都遍历哈希表,因此代价很高,可以在系统空闲的时候进行这个操作。

3 谓词分组算法

谓词分组技术在很多系统中都有应用[5],将具有相同结构的过滤条件组织在一起(通常采用索引),当数据到来时,对该分组进行过滤操作,使用高效的组织手段,因此分组过滤操作执行效率可能会比较高(相对于单独执行时)。

Argus系统中谓词分组的输入是连接分组的结果网络节点和查询解析器解析的Wheres子句的内容,它将结构相似的谓词组织在一个称为常数表的结构中,当数据到来时查找该常数表,然后找到其目的节点。

下面我们讨论一下谓词的标记以及常数表的结构和基于常数表的连接算子。

3.1 谓词的标记

为了更简便,我们以下面的两个查询为例子来说明谓词的标记:

查询1:

我们比较一下这两个查询,两者的其它部分都相同,唯一不同的就是选择常数一个是pku,另外一个是nju。我们称这两个查询的标记相同。谓词的标记由下面几个部分生成:数据源,关系操作符。

3.2 常数表结构

常数表就是存放相同查询标记的查询常数值的一个结构。常数表的结构如表1所示。

常数表的第一列是常数值,第二列是引用次数,比如可能有两个查询的常数值是“云计算”,这个“云计算”的引用次数是3,第三列是目的算子的地址。

3.3 算法实现

在对数据流管理系统模型进行多查询优化时,预先对数据流进行连接,其实现如图2所示。

图2中每条数据流都有多个谓词分组,一个谓词分组对应一条或多条(有部分重复的)查询。再通过这些谓词分组生成查询计划,使整体代价较小,并且记录或删除查询不需要更改其它查询的谓词分组[6]。

算法的实现包括查询的更新和撤销两部分。算法的更新查询部分复杂度为O(n×m3),其中n为两流之间最大的不同连接因子数,m为数据流的查询连接数。而算法的撤销部分复杂度为O(m)。由于参与连接的数据流一般不会太多(少于10条),所以记录和撤消查询的算法复杂度是可接受的。

谓词分组算法的过程是:首先根据pre＿node和pre＿node的谓词找到对应的常数表,用哈希表保存常数表的地址,因此查找的速度通常会很快。如果没有对应的常数表,则创建一个常数表Create Table。然后在该表中查找是否具有取值等于过滤常数的一行,如果没有,则新生成一行,直接插入,并返回插入新行的目的网络节点的地址。如果找到对应的行,则将该行的引用计数值增1,然后返回改行对应的网络节点的地址。

3.4 常数表连接算子

由于有了常数表将所有结构相同的查询组织在一起,这样每次流A中的数据到来的时候,不用分别每次调用Filter算子,只要根据元组的相应列在常数表中查找就是了,将该查找工作用一个特定的算子Join Const实现。元组是以队列的形式存放的,和常数表的结构类似,该查找操作和连接操作很相似,我们称之为常数表连接算子Join Const。

4 实验及结果分析

查询优化的输出是查询网络,底层的调度器调度该网络上的算子节点。查询用测试用例如下所示:

4.1 实验参数说明

1)查询的总数N系统中注册的连续查询的总数量,是系统扩展性的一个重要量度。

2)算子的数量系统中存在的算子的数量。由于大量的查询可能会共享相同的算子,因此如果优化器能够实现这些计算之间的共享,算子的数量并不会和查询数量成正比。

3)数据源生成数据的速度当数据源的速度过高时可能会超出系统的处理能力,使得元组积累,内存消耗增加,从而性能急剧降低。因此采用了模拟的数据源,使数据生成速度随时可调。

4.2 优化前的算子数量对比优化后算子的数量

优化算法分别对连接和过滤操作进行分组,图3所示表示了改进前后算子数量的变化情况。

图3中由于结构相似,每个查询都会分解为数目相同的算子,因此未优化时算子的增长为直线。在采用优化方案后,由于大量的过滤算子共享同一个常数表连接算子,因此算子的数量增加很缓慢,当查询的数量足够多时(例如大于400),则算子呈直线上升,斜率约等于1,即只是增加每个查询的Map算子(投影共享),其他算子增加幅度相对减少。

另外,在很多的连接查询条件下,一条查询的优化可能会牵涉到其它许多的查询,迫使它们修正正在执行的查询计划。而查询计划的调整是非常复杂和耗资源的。这种情况在记录大量查询并频繁更新的数据流管理系统是不愿看到的[6]。如果记录查询的数量是n,本优化算法复杂度为O(lnn),而且对一条查询的优化对一条查询的优化基本不会牵涉到其它查询,性能也在可接受的范围内。

本文提出的高效查询优化处理算法的优化很简单,对一条查询的优化基本不会牵涉到其它查询。为考察该算法的性能,设计了一个实验模拟数据流的连接查询,实验结果与预期的基本吻合,有效地验证了算法的性能。本算法同样适用于硬件处理的查询计划生成,因硬件希望查询计划相对稳定。当然,它更适合应用于查询的更新频率很高的系统。

5 结语

详细讨论了用于高效查询的优化处理模型的算法。该算法的追求目标是尽量在查询之间的共享计算,优化算法采用的主要方法是分组,包括连接分组和谓词分组,分组方法是基于索引的。连接分组在大量的连接之间共享中间结果,一方面减少了内存需求,另一方面减少了连接的计算量。谓词分组将标记相同的谓词组织在一起,采用常数表将其存储起来,这样,多个过滤操作转化为数据源和常数表之间的连接操作,大大减少了系统引发的数量,并减少了系统的存储空间。

实验结果表明,本查询子系统在效率和资源节约上都取得了比较好的效果,初步可以应对网络环境中海量用户查询的挑战。

数据流产生的数据是有始无终的,而且很多环境下查询的数量是海量的,从而对硬件的资源要求很高,这就和我们有限的硬件资源产生了冲突,因此,数据化简技术也成为人们关注的焦点,数据化简技术的目标就是在查询准确性和硬件资源之间取得权衡,如果能够高效地将这些技术应用到DSMS中,会给DSMS提供更强大的效率和功能。

摘要：提出一种新颖的优化方案。方案采用了查询谓词分组和连接分组技术,在众多的查询之间实现了计算共享,较大地节约了系统中存在的算子的数量并提高了处理速度。连接分组首先检查系统当前有无可以利用的中间结果,在这个基础上进行后续连接操作。谓词分组将相同结构的谓词组织在一起,通过引入常数表的这个数据结构将这些查询组织在一起,并将多个过滤操作转化为连接操作,减少了过滤算子的数量。实验结果表明,该方法不仅节约了内存空间,而且还较好地提高了系统的运行效率。

关键词：数据流,滑动窗口,连接分组,常数表,谓词分组

参考文献

[1]左利云,马英杰.基于数据流处理模型的多查询优化算法[J].计算机工程与科学,2009,31(3):71-74

[2]陈磊松.面向高速网络的数据流处理模型研究[J].漳州师范学院学报:自然科学版,2006(2):31-33.

[3]谭博阅,刘宁.数据流中的近似查询技术[J].世界科技研究与发展,2006(4):57-60.

[4]Silberschatz A,等.数据库系统概念[M].杨冬青,唐世渭,等译.北京:机械工业出版社,2000.

[5]游凤荷,黄樟灿,李亮,等.具有物理模型数据处理的多目标优化及其算法[J].武汉大学学报:理学版,2001,47(1):57-60.