基于图结构索引的分布式OLAP加速方法

作者：沈斯杰; 陈榕^*; 陈海波; 臧斌宇

来源：软件学报, 2023, 34(10): 4661-4680.

DOI：10.13328/j.cnki.jos.006665

• OLAP系统
• 分布式系统
• 连接操作
• 索引技术
• 图结构

随着业务数据的规模增大,一些重要的应用场景需要使用分布式在线分析处理(OLAP)支持大规模数据的分析,例如商务智能(BI),企业资源计划(ERP),用户行为分析等.同时,分布式OLAP打破单机存储的限制,可以将数据放在内存中以提升OLAP的处理性能.然而,基于内存的分布式OLAP在消除磁盘I/O后,性能瓶颈转移到了连接操作.连接操作是OLAP中的一种常用操作,会进行大量的数据读取与计算操作.通过对现有的几种连接操作方式进行分析,提出了一种能够加速连接操作的图结构索引以及基于图结构索引的连接操作方式LinkJoin.图结构索引通过用户所指定的连接关系,将数据在内存中的位置以图结构的形式进行存储.基于图结构索引的连接方式,不仅能够有等同于哈希连接的较低复杂度,而且在执行过程中能减少数据读取与计算操作次数.将目前先进的开源内存OLAP系统MonetDB从单机系统扩展成分布式系统,并且在该系统上设计与实现了基于图结构索引的连接操作方式.针对该系统的图索引结构,列式存储以及分布式执行引擎这3个重要方面,进行一系列设计与优化,以提升系统的分布式OLAP处理性能.测试结果表明,在TPC-H标准测试中,基于图结构索引的连接操作对于有连接操作的查询的平均性能提升达1.64倍(最多达4.1倍).对于这些查询中的连接操作,性能提升达9.8–22.1倍.

• 出版日期2023
• 单位上海交通大学