Page 206 - 《软件学报》2020年第11期

杨佐希 等:基于时序分区的时态索引与查询 3521

跟踪数据变化和预测未来发展.另一方面,时间本身具有严格的单向性(时间的增长是严格的单调递增),多维性
(包括有效时间、事务时间和自定义时间等)和相互关系的复杂度(ALLEN 时间关系 [19] ),常规的关系数据库无法
根据这些特性来进行查询的优化,这就导致常规的关系数据处理框架难以高效地查询时态数据.近年来,数据库
领域中还出现时空众包数据的管理技术 [20−22], 其核心思想是将具备时空属性的众包任务分配为众包参与者,并
且要求参与者在完成任务的同时需要满足指定的时空约束,是一种新型的计算模式,但是该模式也仍然需要一
种通用性强的时空索引结构 [23] .
随着 TimeDB [24] 、TempDB [25] 等时态中间件的出现,用户可以直接通过时态标准查询语言 TSQL [26] 提出查询
请求.时态查询操作变得更为自然友好和简便,时态数据库因而得以更广泛的应用,对时态数据库的进一步发展
起到了推动的作用.而时态索引是实现时态数据高效存储和管理的关键部分.针对不同的应用场景,构建不同的
时态索引模型,研究人员从不同角度提出了多种解决方案.文献[7]提出了一种基于 B+-tree 的 Time Index 索引方
式,是最早提出的时态索引模型之一,它是单一的在时间属性的基础上建立索引.通过对时间属性和关键字进行
索引创建,文献[8]提出了一种基于 B-tree 的 Multi-Version 索引方式,结合 I/O 优化,实现对时态数据的有效管理.
总的来说,这一类的索引会将“数据本体”和“时态信息”依次处理,首先采用时态关系投影、选择和连接等 [4,5,9,10]
处理时态信息,再将处理得到的数据进行常规处理.该类方法主要通过“时态关系代数”等模型进行构建.而在时
空数据 [11−13] 的应用场景下,时间常常被视为空间数据的一个“新”的维度,将“时态信息”处理归结到非时态部分,
通过构建一维时间与二维空间的“三维”空间体进行处理,最终对时态数据和空间数据统一进行处理.该类处理
方法能够结合 B-tree 和 R-tree 等技术实现高效地处理时态数据.但是,这种处理方式在某种程度上忽视了时间数
据与空间数据的不同特性.时间数据和空间数据都可以转换为二维数组[X,Y]进行表示,但是两者的区别在于时
间数据通常是具备顺序序列关系,即在二维数组中通常满足 X≤Y.而在空间数据中,X 和 Y 一般不具备序列信息.
还有一类处理手段是将“数据本体”与“时态信息”协同处理 [14−16] .这种方法不同上述的两种处理类型,这类方法
充分考虑时间本身的特征,并把“数据本体”与“时态信息”的相互关联与相互约束结合在一起.通过建立具有时
间特性的时态索引框架,并整合了非时态查询的需求,从而实现“时态查询”与“非时态查询”的协同.通过将有效
时间与结构进行整合,文献[14,15]等提出了时态 XML 索引模型.索引的构建充分考虑时态数据、结构信息和语
言信息各自的数据特性,将 3 类信息整合在一起,并优化“数据本体”与“时态信息”协同处理的顺序,最终实现对
时态 XML 查询和非时态 XML 查询的优化,这些工作关注的都是“有效时间”的查询.文献[16]提出一个一般的时
态索引框架 TDindex,该索引可以应用于多种场景中,并实现“数据本体”与“时态信息”的协同处理.而且其基于外
存的存储模式可以有效地避免时态索引对于机器性能过高的需求,具有一定的普遍适用性.
这些索引模型是在小规模的历史数据上(部分还针对特定的数据类型)进行模型的构建.然而在数据规模增
大、数据本体复杂的情况下,传统的时态索引在进行海量数据的存储和管理时遇到性能上的瓶颈.例如,存在结
构存在冗余、空间开销过大的问题,这主要体现在大规模数据上创建时态索引的时间开销过大甚至当数据到
达一定规模时难以创建完整时态索引,以及创建索引时需要较大的空间开销、存在不同程度上的空间浪费;在
索引更新方面,部分索引没有考虑索引的更新问题或由于索引的结构过于复杂而导致索引的维护代价过高;另
一方面,传统的时态索引结构对于时态数据不具有较优的过滤与筛选,在进行时态查询操作时需要遍历海量的
索引树结构或进行大量的线性扫描,容易造成查询效率较低或查询效果不理想.
另外一方面,传统的时态索引技术大多是基于单线程技术设计的,相比之下对于并行化的时态索引模型研
究较少.大量实验 [17] 表明,在支持多核、大内存和 NUMA 的现代化硬件(例如 SAP HANA [27] )上,几乎所有传统的
时态索引性能都不佳.经过深入研究发现,原因在于这些传统的索引不能很好地支持并行化处理,难以有效地利
用目前计算机体系结构的优势.文献[17,28]提出一种新颖的时态索引结构 Timeline.它可以很好地结合并行化计
算,是一种针对内存列存储方式的“事物时间”版本管理的索引技术.但是 Timeline 对于机器的性能要求极高,默
认机器内存高达 192GB,限制了其索引模型的普遍应用,且在进行时态查询时需要执行大量的线性扫描.尽管如
此,Timeline 提出的并行化优化方法、具有顺序结构的索引模型等方案,仍然具有很好的借鉴意义.
综合考虑上述问题,结合大数据时代的背景,通过对时态数据的“有效时间”进行深入分析,本文提出一种适