论文部分内容阅读
窗口函数作为一种分析型的OLAP函数加入SQL标准已有十多年,而且随着分析型应用需求的增长,窗口函数有着越来越广泛的应用前景。窗口函数的语法非常简单,却可以表达诸如rank、moving average、cumulative sum等复杂的查询。尽管目前主流的商业数据库几乎都支持窗口函数,但是现有的执行策略效率低下,不能满足大批量数据的处理需求。目前已有许多学者着眼于窗口函数优化,也提出了一些基于共享计算思想的优化框架,取得了不错的成果。但针对特定窗口函数的个性化优化工作略显不足,本文着眼于MIN/MAX窗口函数的优化工作,改进了已有的TW算法[1],提出更为高效的IM~2算法;此外,在当前很多应用场景中,用户并不追求完全精确的分析结果,更加注重时间效率,而且每个用户对于精确度和时间的需求不尽相同。现有的优化工作不仅在优化能力的进一步提升上存在瓶颈,更重要的是无法针对不同用户的需求进行定制化的分析服务,系统交互性差。因此,本文针对这种在线分析的需求,还提出了基于采样技术的窗口函数执行框架,进一步提升分析和交互性能。本文主要包括以下四方面的工作:·MIN/MAX窗口函数优化算法本文针对MIN/MAX窗口函数,提出了基于SKYLINE元组值的IM~2优化算法。SKYLINE元组的特性是其满足在当前窗口内部不小于(对于MAX函数)或者不大于(对于MIN函数)其后面任意一个元组,IM~2算法通过保存TOP-K个SKYLINE元组的值,用于窗口计算的结果返回,以达到控制额外内存和减少计算的目的。·窗口局部采样优化算法在线计算系统中,人们更加注重查询的响应速度,可以容忍一定范围的结果误差。基于这种目的本文提出使用局部采样的方法计算窗口函数,该算法只选取每个窗口内部的部分元组参与计算以达到节省计算时间的目的,而且根据相邻窗口的重叠特性进一步采用增量式计算提升算法性能。·窗口全局采样优化算法局部采样完整地保留了每个窗口的计算结果,然而邻近窗口结果的相似性往往使得数据存在冗余。在用户对结果完整性没有严格要求时,可以使用全局采样进一步降低计算代价。本文的窗口全局算法的核心思想是在数据计算之前先对原始数据进行采样生成小数据,之后对小数据集进行相关操作,根据窗口函数ROW和RANGE两种不同的计算模式分别设计了算法。·算法实现与验证本文不仅从时空复杂性理论分析层面证明所提出算法的高效性,而且在目前主流的开源数据库Postgre SQL中实现本文提出的算法,与其他商业数据库对比有着显著的优化效果。此外,针对两类采样优化算法,更是给出了用于计算置信区间的推导过程。