基于自动累加表的查询优化技术

摘要:商务数据库中,决策支持相关的查询变得越来越频繁。使用什么样的技术来满足不断变化的信息源和快速响应的系统需求是查询优化要解决的一个重大技术问题。本文提出原子视角的概念,并对区分视角的粒度选择进行了详细分析,使用EQGM模型寻找候选自动累加表,然后通过匹配函数和规则进行自动累加表的规划。通过访问自动累加表来实现查询性能的优化和提升。实际项目运行结果表明,查询性能很大程度上获得了优化。

关键词:原子视角;自动累加表;自动累加表规划;数据粒度;匹配函数

1 引言/背景

决策支持系统(Decision Supporting System, DSS)最大的特点和优点就是数据积累[1],它最基本的两个组成部分就是数据的输入和输出,而报表是数据输出的主要手段。报表不仅是对业务活动过程的记录,及时反映企事业各部门的经营状况,还能从历史数据中进行数据挖掘归纳总结出有规律的信息,为管理决策层提供准确、直接的数据。

近年来,决策支持相关的查询有了很大的发展[4]。这些查询基本上要对海量数据进行多重连接和复杂的聚集操作。这些查询交互性需求变得越来越普遍,而且要求系统以秒为单位进行快速响应。传统的优化技术往往不能满足这些要求。

一般有两种方法对多重,分布或异构数据库的数据进行信息整合:虚拟视图技术和数据仓库的物化视图技术。物化视图是一个定时刷新的预存计算结果的表。当信息源经常变化时,虚拟试图的方法比较好。当信息源变化不是太频繁并且需要很快的查询响应时间时,物化视图的方法更有效。选择合适的基本数据的“共享”部分进行物化而不是物化所有的视图是一种更有效的方法。用户查询可以通过获取物化视图而不是原数据来优化查询。

本文提出的自动累加表功能上和物化视图类似,但是它是实际存在的物理表,将查询频率比较高和与业务查询密切相关的属性制作成自动累加表,可以同时满足信息源变化频繁和快速响应时间的要求。本文首先提出原子视角的概念,它消除了视角之间的函数依赖关系;然后使用EQGM模型工具来对统计查询进行了分析,从而得到查询和更新频率比较高的表以及它们的属性,并将它们作为候选自动累加表;然后遵循一定的规则和匹配函数,将这些表和属性制作成自动累加表(Automatic Summary Table,AST),并对自动累加表的累加程度进行了分析。在统计查询时就可以查询这些自动累加表,而不是事实表和维表,来实现查询性能的提升和优化。

2 相关文献

报表统计和数据库系统一般都是息息相关的,数据库的设计直接影响到报表统计的效率。根据应用系统的需要,有时一张报表与数据库中数张表相关联,使得报表统计的查询语句变的相当复杂,从而影响了报表的查询效率。报表的查询优化一般可以归为三大类:

(1)创建临时表。当系统应用有多张表关联的时候,且这些表数据比较庞大,而发现其中的某一张或者某几张表关联后得到的结果集非常小并且希望查询得到这个结果集的速度非常快,可以考虑创建“临时表”[2]。

(2)分裂大表。分裂大表可以分为临时分裂和永久分裂两种[3]。在永久分裂的基础上加设一个索引表,索引表中存放所有子表的名称和子表分裂的条件,索引表是该类信息的唯一操作入口。

(3)基于物化视图的查询优化。

①自动累加表(Automatic Summary Table, AST)。AST实际上是一种带有聚集函数的物化视图,考虑到其优化过程的自动性,所以称为自动累加表。文献通过QGM(Query Graph Model)工具,提出了查询和AST匹配模型,还归纳总结出了4种统一的匹配模式[5];然后通过AST对查询进行重写,查询时直接访问AST来实现查询的优化。

②重构视图(Restructured View)[6]。提出了一个可以将普通视图和重构视图统一处理的查询优化框架,适用于SQL的选择-投影-联接查询和有无聚集函数的视图。作者还对重构视图进行了可用性分析和查询重写的介绍。

③物化视图的选择。综合考虑存储空间、查询性能和维护成本等方面要求,提出了物化视图的两阶段选择算法MPL和MPL-CV[7]。

④MVPP。提出一个基于Multiple View Processing Plan(MVPP)[8]的启发式算法,从查询性能和维护成本因素考虑选择什么样的视图进行物化;还将物化视图的设计问题映射成0-1整形规划问题,保证了最优解的存在。

⑤两阶段算法。第一阶段负责优化总的查询响应时间,第二阶段在给定的维护时间成本约束下选择合适的视图进行物化[4]。

本文从数据粒度角度对原子视角进行了进一步的优化选择,同时针对自动累加表的规划过程提出了三条原则和AST的更新原则。

3 相关概念和定义

3.1事实表和维表

度量是数据的实际意义,也称为事实,即描述数据“是什么”。维是人们观察数据的特定角度。人们观察数据的某一维时可能存在细节程度不同,维的这种数据层次结构就是维的层级。一个维通常具有多个层级,例如时间维可以从日期、月份、季度、年等不同层级来进行描述。

事实表[9]是用来描述和存储多维立方体的度量值及各个维的码值,用于存放企业大量的事实数据,通常数据量都很大,且非规范化程度很高;维表[9]是用来描述维信息,它是围绕事实表建立的较小的表。一般用关系数据库的二维表来表示事实表和维表,也就是用“星形模式”和“雪花模式”来表示多维数据模型。星形模式通常有一个中心表(事实表)和多个维表组成。雪花模式是对星型模式的扩展。雪花模式[9]对星型模式的维表进一步层次化,将原来的各维表进一步的细化,拆分为更详细的维表,形成一些局部的“层次”区域。如图1所示的售票表和相关联的维表的雪花模式图,白色的表示事实表,灰色的表示维表。

3.2原子视角的规范化

在报表查询过程中,用户通过输入不同的查询条件进行相应的查询。系统需要知道从什么角度对用户需求数据进行筛选统计,然后按一定的排列方式呈现出来,这里引入查询视角的概念。所谓查询视角(Query Viewpoint)指的是系统从什么视角什么角度对数据进行筛选查询。系统会从不同的角度对数据库中的数据进行查询统计,用集合来表示一个应用系统的所有查询视角的集合:。

实际情况下, 的 个查询视角中,有的视角可能通过其他的视角来进行表示,如售票金额、售票数量和单价,只需要知道其中的两个,然后根据它们之间的函数关系得到另一个的值。在查询过程中,只需要知道这些相关联视角的部分,通过它们的函数关系得到全部的视角数值。为此引入原子视角的概念。所谓原子视角(Atomic Viewpoint),它实际上是一种特殊的查询视角集合,它消除了查询视角中的函数依赖关系,记为,其他的非原子视角记为原子视角满足以下规则:

因此,。公式1表示,在原子视角集合中,任意的原子视角之间都是独立正交的,不存在函数依赖,体现了它的原子性。公式2表示,在所有的统计视角中,任意一个视角都可以通过原子视角集合中的元素来进行表示。公式3,4表示,在原子视角集合中,原子视角可以通过一个非原子视角和其他的原子视角来表示,而这个非原子视角也是不可再分的。

在原子视角中,根据它们功能的不同分为两类:区分视角(Differentiation Perspective)和聚集视角(Aggregation Perspective)。所谓区分视角,指系统通过这些视角来筛选数据库中所需要的属性,对应于维表中的主码。一般用在查询中的选择-投影-连接运算中,但是不包含聚集函数,记为。聚集视角是查询中用于聚集函数中的属性,负责分组和聚集函数的计算,记为。因此,原子视角还可以表示为:。对于一个具体的区分视角来讲,还存在一个数据粒度[10]问题。即当某个维度存在不同层级时,应选择某维的哪个层级作为区分视角才会使查询更有效率。如果选择的维的层级太高,查询效率很高,但可以响应的查询就会受到限制;如果选择的维的层级太低,虽然可以响应大部分的查询,但是查询效率低下,而且操作复杂。因此,选择维的哪个层级作为区分视角要综合考虑数据粒度的利弊。图2是一个事实表和它的维的层级结构。

以财务款项流动这个维度即“售票员-售票窗口-港口-船务公司”来说明如何在某维度上选择合适的粒度。用维度上层级为的查询成本来表示,,其中表示第个查询的查询频率,表示第个查询消耗的系统资源,系统消耗的系统资源和需要处理的数据量成正比,所以可以用要处理的数据量作为表示。目标就是选择某一维度上最小的层级作为该维度上的区分视角。如果相同维度下存在两个相同的查询成本或者存在两个查询成本,值很接近,但明显大于其余层级的查询成本时,可以将这个维度的两个层级拆分为两个维度,分别都作为区分视角。

3.3EQGM(Extendable Query Graph Model)

EQGM是QGM(Query Graph Model)[5]的扩展形式,惟一的不同是QGM的叶节点是表,而EQGM在叶节点上添加了查询用到的属性。在EQGM中,查询通过一个非环形有向图来表示,其中叶节点表示带有属性的基本表,中间节点表示对表的操作,而边表示从子节点到父节点的记录流。每个非叶节点通过对输入数据的操作之后会产生一个关系表,输入数据也是一系列的关系表。EQGM的根结点返回最终的查询结果。

EQGM中的中间节点通过它们的操作类型来划分。最常见的两种类型为SELECT节点和GROUP-BY节点。SELECT节点代表查询的选择-投影-连接部分,通过使用WHERE或HAVING谓词来计算所有的出现在SELECT和GROUP-BY语句中的标量表达式。GROUP-BY节点执行分组并计算聚集函数。如图3中底部的SELECT节点通过SaleWindow-key(售票窗口编码)=Window-key(窗口编码)实现了window和Ticketselling表的连接,通过选择谓词WindowName(售票窗口名称)=Yantai01筛选售票窗口为yantan01的记录。GROUP-BY节点通过SaleID(售票人编码),SaleWindow-key进行分组,并计算SUM(price)的值。最后,顶部的SELECT节点通过HAVING谓词sm>10,000输出最终查询结果。

4. 统计匹配模型

4.1 匹配函数和自动累加表的规划

所有的统计(Statistics)集合记为,根据查询视角和原子视角的定义得知,一个具体的统计 可以表示为:

考虑到一般的统计视角都可以通过原子视角来进行表示,所以在实际分析统计查询的时候,可以将统计简化为。对于一些不包含聚集函数的查询统计,查询结果只需要调用数据库中维表的明细信息即可,相对来说操作不是很复杂,在这里不作考虑。因此,如果中为空,。每一个统计都是对表的一系列操作,本节使用EQGM模型工具来对统计查询进行分析,得到查询和更新频率比较高的表以及它们的属性,并将它们作为候选自动累加表;然后遵循一定的规则和匹配函数,将这些表和属性制作成自动累加表(Automatic Summary Table,AST),并从查询性能和维护成本等方面对自动累加表的累加程度进行了分析。在统计查询时就可以查询这些自动累加表,而不是事实表和维表,来实现查询性能的提升和优化。

对于一个统计查询,它的EQGM图4可以统一的表达为如图所示的形式。

首先要定义几个概念。如图4,在EQGM中最底层的GROUP-BY节点称为,最底层的叶节点称为,非最底层的叶节点称为,通常是维表。由于本文讨论的是非空的统计查询,所以图中至少有一个GROUP-BY节点,即一定存在。将及其以下的sub-EQGM所使用的表和表中的属性记录下来作为候选的自动累加表(Candidate Automatic Summary Table,)。在中只包含SELCT和GROUP-BY节点操作使用到的属性,不记录表中其他不相关的属性。在筛选的时候,应遵循以下几个规则:

多层原则。 将操作尽可能的分为多个层次,这样每个层次要处理的数据量就很少了。类似了数据的“分流”操作。 事实表尽量作为 输入,维表尽量作为 输入。

下拉原则。带有聚集函数的操作尽可能底层化。合适粒度的区分视角的谓词尽可能的下拉。

上拉原则。聚集视角的谓词尽可能的上拉。

下拉原则是为了将具有相同原子视角的数据进行压缩汇总,减少要处理的数据量。将聚集视角的谓词上拉是为了保证候选自动累加表可以具备一个“共享”的数据操作集合。换句话说,就是为了尽可能的使候选自动累加表可以满足所有的查询请求。

带有聚集函数的查询统计都会有这样的一个,接下来讨论如何对这些进行进一步的优化。对带有聚集函数的统计的候选自动累加表进行比较时会出现一下4种情况:

当和两者相同时,直接将或作为自动累加表;

当和两者为包含关系时,将包含原子视角多的作为自动累加表;

当和两者相离即没有公共交集时,将和分别作为自动累加表;

当和两者相交时,将作为自动累加表。

匹配过程如下:

步骤1:根据业务功能或逻辑将候选自动累加表进行职能分类;步骤2:然后对其各个逻辑模块中任意的两个之间进行按照以上的匹配规则进行判定;步骤3:将各个逻辑模块生成的自动累加表继续进行匹配,转到步骤2,直到该逻辑模块不再产生新的自动累加表为止;步骤4:将各个逻辑模块生成的自动累加表再逐一匹配,然后生成最终的自动累加表。

经过上述处理得到的自动累加表实际上是一种轻度综合数据,但相对于细节数据库(事实表和维表)中的数据量少得多。系统还可以根据业务的需求,在轻度综合数据(自动累加表)的基础上生成高度综合数据表,来进一步方便决策分析。对于所有统计来说,凡是涉及决策分析和统计聚集操作的查询都可以通过访问自动累加表得到快速响应;至于涉及一些细节数据的信息查询,还是要依赖细节数据库。

4.2 自动累加表的更新维护

每一项业务操作会对数据库中的数据产生影响。每执行一次业务操作,会同时在事实表和自动累加表中进行数据更新操作。不同的是,事实表只负责记录这个业务操作的详细信息,不对数据进行聚集操作;自动累加表会在业务操作所涉及的原子视角上进行数据的聚集操作。

当数据操作执行时,假设业务操作涉及个原子视角,业务操作所产生的数据在个原子视角下有各自的投影映射值,记为表示数据操作对应的原子视角下的数值;如果数据操作在对应原子视角下没有投影,则记为null。该业务操作同时会影响相关的自动累加表中数据的变化。假设受影响的自动累加表集合(Automatic Summary Table Operated,

由于业务操作对自动累加表的原理是类似的,只需对其中某一自动累加表进行分析即可。以自动累加表为例,假设此自动累加表中包含的原子视角为,集合表示对应的数值集合,表示自动累加表中原子视角下对应的值。执行业务操作后,变为:

,“+”表示值的更新,更新过程通过触发器来实现,更新时需要遵循以下规则:

(1)对应的原子视角为聚集视角,“+”表示按照业务操作的逻辑规则进行数据的累加或算术减操作。例如售票系统中,如果业务操作为售票,则在售票金额则在原来基础上进行累加;如果为退票,则在原来的基础上进行算术减操作。

(2)如果对应的原子视角为区分视角,需要遵循以下规则:

若区分视角下的值,它所对应的某一聚集视角为。用一个整形变量来统计该区分视角对应的某一具体聚集视角下记录的数量,

即 。

若,表示自动累加表中,已存在的值为的历史记录。此时,只需更新该区分视角对应的聚集视角即可,此时的仍为。

若,表示自动累加表中,在区分视角的值为时,没有历史记录。此时,需要在自动累加表中下写入一条新的记录,来实现区分视角值的更新。即就更新为。

5结束语

A港售票系统是一个具有售票、退票和改签功能的集成售票系统。

系统数据库中记录售票相关业务的事实表和维表为50多个,经过业务需求分析和匹配函数后,系统只需要八个自动累加表(表1为其中的一个自动累加表)就可以满足几乎全部的财务报表查询(业务数据的明细记录报表查询除外),且每月需要处理的数据量只有几千条数据左右。每月月底生成月度报表时,使用原子视角技术前,需要对基本数据进行分组汇总,消耗大量系统资源,一个月结报表的查询往往需要20分钟,有时还可能造成系统崩溃。现在只需要十几秒,报表查询的效率得到了质的提高。

6 结论

和传统优化技术相比,本文论述了自动累加表是如何进行规划的,是一种在数据库设计阶段对查询性能做得优化;而且所设计的自动累加表把查询所需要的时间分摊到数据操作时,在原子视角上进行数据的累加。而操作时这种视角上的数据累加所消耗的时间成本是可以忽略的。自动累加表技术是一种以少量空间换取大量时间的查询优化技术,并在实际的大型滚装船售票系统的报表查询中得到了充分运用,有效解决了对超大容量数据库报表查询快速响应的问题。

参考文献:

[1]郭荣,杨颖. PC服务器实现海量数据存取的方法[J].广西科学院学报,2009,25(1):33-35.

[2]黄艳,谭同德 等. 管理信息系统的报表统计策略[J].南阳师范学院学报(自然科学版),2003(12):52-54。

[3]尚展垒,陈慧,宋宇伟. 一种改进的查询优化技术――分裂大表[J].郑州轻工业学院学报,2002(9):61-63.

[4]W. Liang, H. Wang, M.E. Orlowska. Materialized view selection under the maintenance time constraint, Data & Knowledge Engineering 2001(37):203-216.

[5]M. Zaharioudakis, R. Cochrane, G. Lapis, H. Pirahesh, M. Ursta. Answering Complex SQL Queries Using Automatic Summary Tables, in: Proceedings of ACM SIGMOD International Conference on Management of Data,2000:40-49.

[6]Dongfeng Chen, R. Chirkova, F. Sadri. Query optimization using restructured views: Theory and experiments. Information Systems[J], 2009:353-370.

[7]Ming-Chuan Hung, Man-Lin Huang, Don-Lin Yang,etc. Efficient approaches for materialized views selection in a data warehouse. Information Sciences[J], 2007:1333-1348.

[8]Jian Yang, K. Karlapalem, Qing Li. Algorithms for Materialized View Design in Data Warehousing Environment. Proceedings of the 23rd VLDB Conference Athens, Greece, 1997:136-145.

[9]李泽海. 数据仓库中多维数据处理与查询相关技术的研究[J],吉林大学,2005(10):11-26.

[10]W.H.Inmon,王志海. 数据仓库[M].北京:机械工业出版社,2000.