基于图结构索引的分布式OLAP加速方法.pdf
《基于图结构索引的分布式OLAP加速方法.pdf》由会员分享,可在线阅读,更多相关《基于图结构索引的分布式OLAP加速方法.pdf(20页珍藏版)》请在咨信网上搜索。
1、基于图结构索引的分布式 OLAP 加速方法*沈斯杰,陈榕,陈海波,臧斌宇(上海交通大学并行与分布式系统研究所,上海200240)通信作者:陈榕,E-mail:摘要:随着业务数据的规模增大,一些重要的应用场景需要使用分布式在线分析处理(OLAP)支持大规模数据的分析,例如商务智能(BI),企业资源计划(ERP),用户行为分析等.同时,分布式 OLAP 打破单机存储的限制,可以将数据放在内存中以提升 OLAP 的处理性能.然而,基于内存的分布式 OLAP 在消除磁盘 I/O 后,性能瓶颈转移到了连接操作.连接操作是 OLAP 中的一种常用操作,会进行大量的数据读取与计算操作.通过对现有的几种连接操
2、作方式进行分析,提出了一种能够加速连接操作的图结构索引以及基于图结构索引的连接操作方式 LinkJoin.图结构索引通过用户所指定的连接关系,将数据在内存中的位置以图结构的形式进行存储.基于图结构索引的连接方式,不仅能够有等同于哈希连接的较低复杂度,而且在执行过程中能减少数据读取与计算操作次数.将目前先进的开源内存 OLAP 系统 MonetDB 从单机系统扩展成分布式系统,并且在该系统上设计与实现了基于图结构索引的连接操作方式.针对该系统的图索引结构,列式存储以及分布式执行引擎这 3 个重要方面,进行一系列设计与优化,以提升系统的分布式 OLAP 处理性能.测试结果表明,在 TPC-H 标准
3、测试中,基于图结构索引的连接操作对于有连接操作的查询的平均性能提升达 1.64 倍(最多达 4.1 倍).对于这些查询中的连接操作,性能提升达 9.822.1 倍.关键词:OLAP 系统;分布式系统;连接操作;索引技术;图结构中图法分类号:TP311中文引用格式:沈斯杰,陈榕,陈海波,臧斌宇.基于图结构索引的分布式OLAP加速方法.软件学报,2023,34(10):46614680.http:/ Distributed OLAP with Graph Structure IndexingSHENSi-Jie,CHENRong,CHENHai-Bo,ZANGBin-Yu(InstituteofP
4、arallelandDistributedSystems,ShanghaiJiaoTongUniversity,Shanghai200240,China)Abstract:As the scale of business data increases,distributed online analytical processing(OLAP)is widely performed in businessintelligence(BI),enterprise resource planning(ERP),user behavior analysis,and other application s
5、cenarios to support large-scale dataanalysis.Moreover,distributed OLAP overcomes the limitations of single-machine storage and stores data in memory to improve theperformanceofOLAP.However,afterthein-memorydistributedOLAPeliminatesdiskinput/output(I/O),thejoinoperationbecomesoneof its new performanc
6、e bottlenecks.As a common practice in OLAP,the join operation involves a huge amount of data accessing andcomputation operations.By analyzing existing methods for the join operation,this study presents a graph structure indexing method thatcan accelerate the join operation and a new join method call
7、ed LinkJoin based on it.Graph structure indexing stores the in-memoryposition of data in the form of a graph structure according to the join relationship specified by users.The join method based on graphstructureindexingreducestheamountofdataaccessingandcomputationoperationswithalowcomplexityequival
8、enttothatofthehashjoin.This study expands the state-of-the-art open-source in-memory OLAP system called MonetDB from a single-machine system to a*基金项目:国家自然科学基金面上项目(61772335)收稿时间:2021-11-03;修改时间:2021-12-17;采用时间:2022-03-03;jos 在线出版时间:2023-01-04CNKI 网络首发时间:2023-01-05软件学报ISSN1000-9825,CODENRUXUEWE-mail:
9、Journal of Software,2023,34(10):46614680doi:10.13328/ki.jos.006665http:/中国科学院软件研究所版权所有.Tel:+86-10-62562563distributedoneanddesignsandimplementsajoinmethodbasedongraphstructureindexingonit.Aseriesofdesignsandoptimizationsarealsoconductedintheaspectsofgraphindexingstructure,columnarstorage,anddistribu
10、tedexecutionenginetoimprovethedistributedOLAP performance of the system.The test results show that in the TPC-H benchmark tests,the join operation based on graph structureindexingimprovestheperformanceonquerieswithjoinoperationsby1.64timesonaverageand4.1timesatmost.Forthejoinoperationpartofthesequer
11、ies,itenhancestheperformanceby9.822.1times.Key words:onlineanalyticalprocessing(OLAP)system;distributedsystem;joinoperation;indexing;graphstructure随着业务数据的不断增长,分布式在线分析处理(onlineanalyticalprocessing,OLAP)应用在商务智能(businessintelligence,BI),企业资源计划(enterpriseresourceplanning,ERP),用户行为分析等不同场景1,2.同时,由于分布式系统能够
12、打破单机系统在内存上的限制,分布式 OLAP 系统能够将主要数据保留在内存中,加速分析的性能,提高查询的时效性.因此,一批分布式数据库与内存数据库已投入研究和使用以支撑内存场景的数据处理27.相较于传统基于磁盘的 OLAP 处理系统,基于内存的分布式 OLAP 系统虽然规避了由于读写磁盘 I/O 而产生的性能瓶颈,但是又出现了一些新的性能挑战.连接操作(joinoperation)就是其中的一个典型.连接操作是用来将多张数据库表进行笛卡尔积并且筛选出匹配一定条件数据的操作.在 OLAP 处理中,用户常用通过连接操作来得到跨数据库表的信息.例如,在用户行为分析中,将用户表和订单表进行连接操作,能
13、得到用户的订单情况(如用户平均消费等).OLAP 的基准测试 TPC-H8提供了 22 个标准查询,其中有 20 个查询都直接或间接地使用了连接操作9.连接操作是数据库中标准操作,而且也是一个耗时的操作.在基于磁盘的数据库中,连接操作会导致大量的读写磁盘 I/O,因此这些系统会通过减少 I/O 对连接操作进行优化,例如优化的内嵌循环连接(nestedloopjoin),哈希连接(hashjoin),排序归并连接(sort-mergejoin)1013.尽管分布式内存 OLAP 系统能够避免磁盘 I/O,连接操作却仍旧是一个耗时操作,此时连接操作的性能瓶颈已经转变为筛选匹配数据的操作.尤其是对于
14、一类稀疏连接(sparsejoin)的查询,匹配选出的数据占所有数据的比例很低.例如在 TPC-H 数据集8中,与一条订单所对应的订单条目平均只有 4 条,而订单条目的总数却在上百万条,并且会随着伸缩因子(scalefactor)上升而增大.因此,有必要对于分布式内存 OLAP 系统中连接操作进行进一步的性能优化.近年来,随着大数据技术的发展以及数据模型的复杂化,为了表示数据之间的关联,图结构被常用来存储这些关联数据,例如 RDF 图,社交网络图等.同时,一些用于查询与分析图结构数据的图处理系统也出现了,它们将数据维护成顶点和边以体现数据之间的关联.而对于关系型数据库,实体关系模型(entit
15、y-relationshipmodel)与数据库模式(schema)本身也是图结构.我们观察到,通过数据库表之间的关系(relationship)构建一个专门用于连接操作的图结构索引,相较于使用传统的单表上的关系型索引(例如 B+树索引,哈希索引等),能够有数量级上的性能提升(实验见第 5.4 节).因此,图结构索引可以通过预处理的数据结构,提升连接操作时间占比大的 OLAP 处理性能.然而,由于现有的业务数据大量基于关系型数据库,使用关系型数据模型进行存储10,14,15,因此直接使用图处理系统或者图数据库(如 Neo4j16等),会带来数据格式转换的跨系统开销和额外的维护成本.同时,在关系
16、型数据库上长期积累的优化经验(例如列式存储模型及其执行优化),也未在现有图数据库上得到完整移植.而在关系型数据库中,直接使用关系模型实现图结构,也不能充分利用图结构的性能优势17.因此,如何在关系型数据库上进行图结构的设计,使关系型数据在连接操作上得到图结构的性能,是本文研究的主要内容.本文提出了一个基于图结构索引的分布式 OLAP 连接方法 LinkJoin,通过在关系型数据库上建立图结构索引以提升分布式内存 OLAP 系统中对于关系型数据的连接操作性能.为了对基于图结构索引的连接方法 LinkJoin进行验证,我们首先将一个目前先进的开源内存 OLAP 系统 MonetDB(常被作为代表系
17、统用于研究与分析1821)从单机扩展成了分布式系统,并且使用了 LinkJoin 的连接方式(本文将该系统简称为 LinkJoin 系统).为了保证 OLAP处理的性能,系统使用了列式存储以利用 OLAP 处理过程中的数据局部性(尽管 LinkJoin 系统在存储上使用了列式存储以加速 OLAP 处理,但对于数据模型仍使用关系模型,因此按照 C-Store12,MonetDB4等相关系统的定义,仍称为关系型数据库).然而,在使用图结构索引时,LinkJoin 和系统的设计将会面临性能方面的挑战,例如如何实现一个高效的图索引结构,如何保证图索引结构的使用和对数据结构的改造不影响其他操作的性能,以
18、及如何对4662软件学报2023 年第 34 卷第 10 期分布式执行引擎进行改造.针对这些方面的挑战,LinkJoin 系统通过对图结构索引,列式存储以及分布式执行引擎进行优化与改造,充分利用数据的物理位置信息,减少数据查询过程中的内存访问以及跳转.我们在一个 4 台机器的集群中进行了系统的测试.测试使用 TPC-H8标准测试,通过增加图索引结构,LinkJoin 相比 MonetDB 原有的连接方式能够在带有连接的查询中平均性能提升 1.64 倍(取决于连接操作占整个查询中的比重),对于连接操作比重较大的查询,整个查询的性能提升最多达到 4.1 倍.对于这些查询中的连接操作,使用 Link
19、Join 所带来的性能提升达 9.822.1 倍.我们将 LinkJoin 系统集成到一个分布式内存混合负载系统 VEGITO22中(代码地址:https:/ OLAP 系统中的连接操作方式的分析(第 2 节),提出新型的基于图结构索引的连接方式 LinkJoin,并给出其复杂度分析.(2)给出基于 LinkJoin 技术的分布式 OLAP 系统(即 LinkJoin 系统)的框架(第 3 节).针对系统设计的挑战,提出 3 个方面(图索引结构,列式存储结构以及分布式执行引擎)的优化和改造技术,以实现一个高效的基于图结构索引的内存 OLAP 系统(第 4 节).(3)将先进的 MonetDB
20、从单机扩展到分布式系统,并进行了一组证明 LinkJoin 技术和系统有效性的实验,以验证图索引结构在 OLAP 系统中能够加速分析查询(第 5 节).(4)给出了 LinkJoin 及系统实现上的讨论与展望(第 6 节),以及其他相关工作分析(第 7 节).1 背景知识 1.1 在线分析处理(OLAP)在线分析处理(OLAP)是一种常见的数据库系统对于数据处理的模式,常用于数据的查询分析,例如商务智能(BI),企业资源计划(ERP),用户行为分析等1,2.OLAP 的特征是对数据的操作以只读操作为主,而对于数据的修改(包括增加,修改,删除)等操作会使用离线的批量加载方式.由于这种特征,对于
21、OLAP 中的数据处理能够避免读写冲突,因此能够减少读写并发控制方面的考虑,而查询处理的执行时间是 OLAP 系统性能优化的一个主要目标,并且可以通过一些预分配的数据结构进行查询的加速优化1,5,6,2327.对于传统基于磁盘的 OLAP 处理系统,磁盘的 I/O 开销是查询处理的一个主要性能瓶颈.由于分布式系统能够打破单机内存的限制,并且随着内存容量的扩大以及内存计算的发展,传统基于磁盘的 OLAP 处理正在向着内存 OLAP 进行转变.内存 OLAP 将分析所需要使用的数据存在内存中,在分析过程中仅需要从内存中读取数据,而完全避免磁盘 I/O 的开销.目前,已经有不少面向内存 OLAP 的
22、数据库系统用于商业或研究使用,例如 MonetDB4,SingleStore11,HyPer18,SAPHANA23等.基于内存的分布式 OLAP 处理系统不仅了消除了磁盘 I/O 的开销,同时也使用了不同于磁盘数据库的新型内存技术,通过充分发挥硬件特性以进一步提升分析处理的性能,例如列式存储能够充分利用数据的局部性特征以最大化查询过程中的 CPU 缓存(cache)利用率4,11,12;向量化执行能够充分使用 CPU 的向量指令集加速对列式存储的数据计算24;根据现代处理器的多核特性使用并行技术缩短查询的执行时间和提高查询处理的吞吐26;以及减少中间结果的网络通信11等.1.2 连接操作(j
23、oin operation)在关系型数据库中,连接操作是用来组合两张数据库表信息的操作.如图 1 所示,我们简化了一个标准测试TPC-H8中所使用的数据集:在关系型数据库中有两张数据库表 ORDERS 与 LINEITEM,分别存放订单和每个订单所属的条目.订单表 ORDERS 会记录订单号 O_ID 与订单日期 O_ENTRY_D 等信息,订单条目表 LINEITEM会存放订单条目的主键 L_ID 以及所属的订单号 L_O_ID.一个常用的查询会检查某类订单所属的条目,这就需要用连接操作将两张表的信息进行组合.连接操作的语义是将两张数据库表的信息进行笛卡尔积(数据库表 R 与 S沈斯杰等:基
24、于图结构索引的分布式 OLAP 加速方法4663的笛卡尔积,即把 R 的每一行与 S 的每一行进行组合得到结果集,该结果集的属性数(列数)是 R 与 S 的属性数之和,结果集的元组数(行数)是 R 与 S 的元组数之积)的操作,然后再根据条件(如 WHERE 从句后的条件)进行筛选,得到结果集.SELECTCOUNT(*)FROMORDERS,LINEITEMWHEREO_IDO_ENTRY_D10012021-08-0710022021-08-0710032021-08-08L_ID100011002100021027100031002100041003=O_IDO_ENTRY_DL_IDL
25、_O_ID10022021-08-0710001100210022021-08-0710003100210032021-08-08100041003ORDERSLINEITEMO_ID=L_O_ID AND O_ENTRY_D in L_O_ID图1关系型数据库的连接操作示例由于连接操作在做笛卡尔积后的中间结果行数会等于原来两个表行数乘积,然后再进行筛选,因此一般在数据库中,会将筛选和组合在一起完成,以减少中间结果集的大小.在实现上,常用的 OLAP 处理系统,如 SAPHANA10,SingleStore11,C-Store12,Hyrise13,MonetDB4中,通常支持内嵌循环连接,排
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 结构 索引 分布式 OLAP 加速 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。