基于图结构索引的分布式OLAP加速方法
作者:
作者单位:

作者简介:

沈斯杰(1995-),男,博士生,主要研究领域为并行与分布式系统;陈榕(1981-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为操作系统,并行与分布式系统;陈海波(1982-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为操作系统,并行与分布式系统;臧斌宇(1965-),男,博士,教授,博士生导师,CCF会士,主要研究领域为操作系统.

通讯作者:

陈榕,E-mail:rongchen@sjtu.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金面上项目(61772335)


Accelerating Distributed OLAP with Graph Structure Indexing
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    As the scale of business data increases, distributed online analytical processing (OLAP) is widely performed in business intelligence (BI), enterprise resource planning (ERP), user behavior analysis, and other application scenarios to support large-scale data analysis. Moreover, distributed OLAP overcomes the limitations of single-machine storage and stores data in memory to improve the performance of OLAP. However, after the in-memory distributed OLAP eliminates disk input/output (I/O), the join operation becomes one of its new performance bottlenecks. As a common practice in OLAP, the join operation involves a huge amount of data accessing and computation operations. By analyzing existing methods for the join operation, this study presents a graph structure indexing method that can accelerate the join operation and a new join method called LinkJoin based on it. Graph structure indexing stores the in-memory position of data in the form of a graph structure according to the join relationship specified by users. The join method based on graph structure indexing reduces the amount of data accessing and computation operations with a low complexity equivalent to that of the hash join. This study expands the state-of-the-art open-source in-memory OLAP system called MonetDB from a single-machine system to a distributed one and designs and implements a join method based on graph structure indexing on it. A series of designs and optimizations are also conducted in the aspects of graph indexing structure, columnar storage, and distributed execution engine to improve the distributed OLAP performance of the system. The test results show that in the TPC-H benchmark tests, the join operation based on graph structure indexing improves the performance on queries with join operations by 1.64 times on average and 4.1 times at most. For the join operation part of these queries, it enhances the performance by 9.8–22.1 times.

    参考文献
    相似文献
    引证文献
引用本文

沈斯杰,陈榕,陈海波,臧斌宇.基于图结构索引的分布式OLAP加速方法.软件学报,2023,34(10):4661-4680

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-11-03
  • 最后修改日期:2021-12-17
  • 录用日期:
  • 在线发布日期: 2023-01-04
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号