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

基于图结构索引的分布式 OLAP 加速方法*沈斯杰,陈榕,陈海波,臧斌宇(上海交通大学并行与分布式系统研究所,上海200240)通信作者:陈榕,E-mail:摘要:随着业务数据的规模增大,一些重要的应用场景需要使用分布式在线分析处理(OLAP)支持大规模数据的分析,例如商务智能(BI),企业资源计划(ERP),用户行为分析等.同时,分布式 OLAP 打破单机存储的限制,可以将数据放在内存中以提升 OLAP 的处理性能.然而,基于内存的分布式 OLAP 在消除磁盘 I/O 后,性能瓶颈转移到了连接操作.连接操作是 OLAP 中的一种常用操作,会进行大量的数据读取与计算操作.通过对现有的几种连接操作方式进行分析,提出了一种能够加速连接操作的图结构索引以及基于图结构索引的连接操作方式 LinkJoin.图结构索引通过用户所指定的连接关系,将数据在内存中的位置以图结构的形式进行存储.基于图结构索引的连接方式,不仅能够有等同于哈希连接的较低复杂度,而且在执行过程中能减少数据读取与计算操作次数.将目前先进的开源内存 OLAP 系统 MonetDB 从单机系统扩展成分布式系统,并且在该系统上设计与实现了基于图结构索引的连接操作方式.针对该系统的图索引结构,列式存储以及分布式执行引擎这 3 个重要方面,进行一系列设计与优化,以提升系统的分布式 OLAP 处理性能.测试结果表明,在 TPC-H 标准测试中,基于图结构索引的连接操作对于有连接操作的查询的平均性能提升达 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(InstituteofParallelandDistributedSystems,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 scenarios 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 performance 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 called 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 graphstructureindexingreducestheamountofdataaccessingandcomputationoperationswithalowcomplexityequivalenttothatofthehashjoin.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:Journal of Software,2023,34(10):46614680doi:10.13328/ki.jos.006665http:/中国科学院软件研究所版权所有.Tel:[phone]distributedoneanddesignsandimplementsajoinmethodbasedongraphstructureindexingonit.Aseriesofdesignsandoptimizationsarealsoconductedintheaspectsofgraphindexingstructure,columnarstorage,anddistributedexecutionenginetoimprovethedistributedOLAP performance of the system.The test results show that in the TPC-H benchmark tests,the join operation based on graph structureindexingimprovestheperformanceonquerieswithjoinoperationsby1.64timesonaverageand4.1timesatmost.Forthejoinoperationpartofthesequeries,itenhancestheperformanceby9.822.1times.Key words:onlineanalyticalprocessing(OLAP)system;distributedsystem;joinoperation;indexing;graphstructure随着业务数据的不断增长,分布式在线分析处理(onlineanalyticalprocessing,OLAP)应用在商务智能(businessintelligence,BI),企业资源计划(enterpriseresourceplanning,ERP),用户行为分析等不同场景1,2.同时,由于分布式系统能够打破单机系统在内存上的限制,分布式 OLAP 系统能够将主要数据保留在内存中,加速分析的性能,提高查询的时效性.因此,一批分布式数据库与内存数据库已投入研究和使用以支撑内存场景的数据处理27.相较于传统基于磁盘的 OLAP 处理系统,基于内存的分布式 OLAP 系统虽然规避了由于读写磁盘 I/O 而产生的性能瓶颈,但是又出现了一些新的性能挑战.连接操作(joinoperation)就是其中的一个典型.连接操作是用来将多张数据库表进行笛卡尔积并且筛选出匹配一定条件数据的操作.在 OLAP 处理中,用户常用通过连接操作来得到跨数据库表的信息.例如,在用户行为分析中,将用户表和订单表进行连接操作,能得到用户的订单情况(如用户平均消费等).OLAP 的基准测试 TPC-H8提供了 22 个标准查询,其中有 20 个查询都直接或间接地使用了连接操作9.连接操作是数据库中标准操作,而且也是一个耗时的操作.在基于磁盘的数据库中,连接操作会导致大量的读写磁盘 I/O,因此这些系统会通过减少 I/O 对连接操作进行优化,例如优化的内嵌循环连接(nestedloopjoin),哈希连接(hashjoin),排序归并连接(sort-mergejoin)1013.尽管分布式内存 OLAP 系统能够避免磁盘 I/O,连接操作却仍旧是一个耗时操作,此时连接操作的性能瓶颈已经转变为筛选匹配数据的操作.尤其是对于一类稀疏连接(sparsejoin)的查询,匹配选出的数据占所有数据的比例很低.例如在 TPC-H 数据集8中,与一条订单所对应的订单条目平均只有 4 条,而订单条目的总数却在上百万条,并且会随着伸缩因子(scalefactor)上升而增大.因此,有必要对于分布式内存 OLAP 系统中连接操作进行进一步的性能优化.近年来,随着大数据技术的发展以及数据模型的复杂化,为了表示数据之间的关联,图结构被常用来存储这些关联数据,例如 RDF 图,社交网络图等.同时,一些用于查询与分析图结构数据的图处理系统也出现了,它们将数据维护成顶点和边以体现数据之间的关联.而对于关系型数据库,实体关系模型(entity-relationshipmodel)与数据库模式(schema)本身也是图结构.我们观察到,通过数据库表之间的关系(relationship)构建一个专门用于连接操作的图结构索引,相较于使用传统的单表上的关系型索引(例如 B+树索引,哈希索引等),能够有数量级上的性能提升(实验见第 5.4 节).因此,图结构索引可以通过预处理的数据结构,提升连接操作时间占比大的 OLAP 处理性能.然而,由于现有的业务数据大量基于关系型数据库,使用关系型数据模型进行存储10,14,15,因此直接使用图处理系统或者图数据库(如 Neo4j16等),会带来数据格式转换的跨系统开销和额外的维护成本.同时,在关系型数据库上长期积累的优化经验(例如列式存储模型及其执行优化),也未在现有图数据库上得到完整移植.而在关系型数据库中,直接使用关系模型实现图结构,也不能充分利用图结构的性能优势17.因此,如何在关系型数据库上进行图结构的设计,使关系型数据在连接操作上得到图结构的性能,是本文研究的主要内容.本文提出了一个基于图结构索引的分布式 OLAP 连接方法 LinkJoin,通过在关系型数据库上建立图结构索引以提升分布式内存 OLAP 系统中对于关系型数据的连接操作性能.为了对基于图结构索引的连接方法 LinkJoin进行验证,我们首先将一个目前先进的开源内存 OLAP 系统 MonetDB(常被作为代表系统用于研究与分析1821)从单机扩展成了分布式系统,并且使用了 LinkJoin 的连接方式(本文将该系统简称为 LinkJoin 系统).为了保证 OLAP处理的性能,系统使用了列式存储以利用 OLAP 处理过程中的数据局部性(尽管 LinkJoin 系统在存储上使用了列式存储以加速 OLAP 处理,但对于数据模型仍使用关系模型,因此按照 C-Store12,MonetDB4等相关系统的定义,仍称为关系型数据库).然而,在使用图结构索引时,LinkJoin 和系统的设计将会面临性能方面的挑战,例如如何实现一个高效的图索引结构,如何保证图索引结构的使用和对数据结构的改造不影响其他操作的性能,以及如何对4662软件学报2023 年第 34 卷第 10 期分布式执行引擎进行改造.针对这些方面的挑战,LinkJoin 系统通过对图结构索引,列式存储以及分布式执行引擎进行优化与改造,充分利用数据的物理位置信息,减少数据查询过程中的内存访问以及跳转.我们在一个 4 台机器的集群中进行了系统的测试.测试使用 TPC-H8标准测试,通过增加图索引结构,LinkJoin 相比 MonetDB 原有的连接方式能够在带有连接的查询中平均性能提升 1.64 倍(取决于连接操作占整个查询中的比重),对于连接操作比重较大的查询,整个查询的性能提升最多达到 4.1 倍.对于这些查询中的连接操作,使用 LinkJoin 所带来的性能提升达 9.822.1 倍.我们将 LinkJoin 系统集成到一个分布式内存混合负载系统 VEGITO22中(代码地址:https:/ OLAP 系统中的连接操作方式的分析(第 2 节),提出新型的基于图结构索引的连接方式 LinkJoin,并给出其复杂度分析.(2)给出基于 LinkJoin 技术的分布式 OLAP 系统(即 LinkJoin 系统)的框架(第 3 节).针对系统设计的挑战,提出 3 个方面(图索引结构,列式存储结构以及分布式执行引擎)的优化和改造技术,以实现一个高效的基于图结构索引的内存 OLAP 系统(第 4 节).(3)将先进的 MonetDB 从单机扩展到分布式系统,并进行了一组证明 LinkJoin 技术和系统有效性的实验,以验证图索引结构在 OLAP 系统中能够加速分析查询(第 5 节).(4)给出了 LinkJoin 及系统实现上的讨论与展望(第 6 节),以及其他相关工作分析(第 7 节).1 背景知识 1.1 在线分析处理(OLAP)在线分析处理(OLAP)是一种常见的数据库系统对于数据处理的模式,常用于数据的查询分析,例如商务智能(BI),企业资源计划(ERP),用户行为分析等1,2.OLAP 的特征是对数据的操作以只读操作为主,而对于数据的修改(包括增加,修改,删除)等操作会使用离线的批量加载方式.由于这种特征,对于 OLAP 中的数据处理能够避免读写冲突,因此能够减少读写并发控制方面的考虑,而查询处理的执行时间是 OLAP 系统性能优化的一个主要目标,并且可以通过一些预分配的数据结构进行查询的加速优化1,5,6,2327.对于传统基于磁盘的 OLAP 处理系统,磁盘的 I/O 开销是查询处理的一个主要性能瓶颈.由于分布式系统能够打破单机内存的限制,并且随着内存容量的扩大以及内存计算的发展,传统基于磁盘的 OLAP 处理正在向着内存 OLAP 进行转变.内存 OLAP 将分析所需要使用的数据存在内存中,在分析过程中仅需要从内存中读取数据,而完全避免磁盘 I/O 的开销.目前,已经有不少面向内存 OLAP 的数据库系统用于商业或研究使用,例如 MonetDB4,SingleStore11,HyPer18,SAPHANA23等.基于内存的分布式 OLAP 处理系统不仅了消除了磁盘 I/O 的开销,同时也使用了不同于磁盘数据库的新型内存技术,通过充分发挥硬件特性以进一步提升分析处理的性能,例如列式存储能够充分利用数据的局部性特征以最大化查询过程中的 CPU 缓存(cache)利用率4,11,12;向量化执行能够充分使用 CPU 的向量指令集加速对列式存储的数据计算24;根据现代处理器的多核特性使用并行技术缩短查询的执行时间和提高查询处理的吞吐26;以及减少中间结果的网络通信11等.1.2 连接操作(join operation)在关系型数据库中,连接操作是用来组合两张数据库表信息的操作.如图 1 所示,我们简化了一个标准测试TPC-H8中所使用的数据集:在关系型数据库中有两张数据库表 ORDERS 与 LINEITEM,分别存放订单和每个订单所属的条目.订单表 ORDERS 会记录订单号 O_ID 与订单日期 O_ENTRY_D 等信息,订单条目表 LINEITEM会存放订单条目的主键 L_ID 以及所属的订单号 L_O_ID.一个常用的查询会检查某类订单所属的条目,这就需要用连接操作将两张表的信息进行组合.连接操作的语义是将两张数据库表的信息进行笛卡尔积(数据库表 R 与 S沈斯杰等:基于图结构索引的分布式 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_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中,通常支持内嵌循环连接,排序归并连接,哈希连接等连接方式,以及它们的优化和变种.表 1 给出了这些典型 OLAP 系统所支持的不同连接方式,这些连接方式可以供系统的用户根据不同的场景和性能要求进行选择.表1典型 OLAP 系统对于不同连接方式的支持连接方式SAPHANA10SingleStore11C-Store12Hyrise13MonetDB4Vectorwise28内嵌循环连接排序归并连接哈希连接(1)内嵌循环连接(nestedloopjoin,NLJ).NLJ 是和连接操作的语义最接近的实现方式,通过嵌套的循环来遍历两张需要连接的表,并且在内层循环中根据匹配条件进行筛选.这种方式支持的筛选条件广泛(例如相等,不等,字符串匹配等条件或者它们的组合条件).对于基于磁盘的关系型数据库,其主要的性能瓶颈在于数据从磁盘上读取的 I/O 开销.以图 1 的查询为例,外循环是 ORDERS,内循环是 LINEITEM.对于每一条 ORDERS 的数据,都需要读取完整的 LINEITEM 数据,即把这个表的磁盘页面依次读出.设 ORDERS 的行数为 R(O),ORDERS 与ORERLINE 的磁盘页面数分别为 P(O)与 P(OL),则 I/O 次数至少为 P(O)+R(O)P(OL).因此,一些优化方式往往通过充分利用每次被读入的磁盘页面(如通过分块的方式减少 I/O 次数),或者针对新型的存储介质(如 SSD)进行特定的优化29.(2)排序归并连接(sort-mergejoin,SMJ).SMJ 是针对筛选条件中的列可排序,并且是表内的顺序是按照该列进行排序的.对于已经排序的表而言,连接过程是一个简单的归并过程,因此两张表只需各遍历一遍,其 I/O 开销为 P(O)+P(OL).然而,这种连接方式的问题在于:其一,对于没有排序的表而言,需要按照筛选条件中的列进行排序,引入额外的排序开销;其二,对于无法排序的列和筛选条件,无法使用,因此在语义上受限.(3)哈希连接(hashjoin,HJ).在连接操作的筛选条件是值相等的情况下,为了进一步提高查询效率与减少查询过程中的不必要 I/O 开销,HJ 使用哈希结构加速连接.HJ 分为准备阶段与匹配阶段.在准备阶段,HJ 使用了一个辅助的哈希划分,通过尽量减少不必要的读取来提升连接速度.在这一阶段中,会将两张表中需要比对的列使用一4664软件学报2023 年第 34 卷第 10 期个哈希函数进行计算哈希值,并且根据该哈希值将两张表的行分为不同的数据划分.由于两个值相等的必要条件是它们的哈希值相等,因此匹配的两行只可能是在对应的数据划分中进行.所以,在第 2 个阶段,即匹配阶段中,仅需要在对应的数据划分中进行匹配连接.在以上所介绍的连接方法中,对于两张表的连接操作,都可以看作有两层主要的循环来进行数据的匹配和筛选,这两层循环分别对应着两张表的顺序.首先遍历第 1 张表,对于第 1 张表的每一行,通过不同的匹配方式(例如嵌套循环中的遍历操作,排序归并中的归并操作,哈希连接中的哈希匹配操作等)去筛选第 2 张表的数据.因此,在连接操作中,由于上述的第 1 张表会出现在外层循环中,会称之为外层表(outertable).与此对应,第 2 张表成为内层表(innertable).1.3 索引(index)索引是数据库系统中用于加速数据查询的一种经典方法.在关系型数据库系统中,为了避免逐条查询某条数据,会维护一种称为索引的数据结构,将数据的某个属性(列)的值作为键,通过索引映射到这个属性值所对应的数据的物理位置或主键.因此,根据应用的工作负载来建立合适的索引,能够提升数据库的查询效率.查询一般是针对数据的某个属性或者多个属性进行筛选.根据筛选条件的形式可以将查询分为两类:点查询与范围查询.点查询给定的筛选条件一般是等值查询,即筛选出某一个属性(或者多个属性)等于某个值的数据行.与之相反,范围查询的筛选条件是某一个范围(例如数值的大于,小于,以及字符串的匹配操作 like 等).与之相对,索引结构主要有两类索引用以加速不同类型的查询:哈希索引与树状索引.哈希索引由于其 O(1)的查找复杂度,对于点查询有很好的支持,然而却不能支持范围查询,对于使用哈希索引进行范围查询,将遍历范围内的每一个值从而转换为点查询,这不仅在查找效率上会变差,而且一些范围查询(如浮点数的范围或者大范围的整数)将无法进行转化.树状索引(例如 B+树,以及其变种如跳表等)单次查找的复杂度是 O(logn),但是树状索引由于其顺序结构,能够在给定最大值或最小值后选定一部分范围进行范围查询.本文将这些关系型数据库中所使用的索引(包括树状索引和哈希索引等),称为关系型索引(relationalindex).因此,一般而言,在关系型索引中,哈希索引对点查询更为适合,而树状索引对于范围查询更为适合.由于这些查询能够加速对于数据的查询,因此也会用于加速连接操作(例如在嵌套循环连接中,对内层表使用索引进行筛选).然而,如何设计一个本身针对连接场景的索引,仍旧是一个开放问题.2 现有连接方式分析相比基于磁盘的 OLAP,内存 OLAP 的性能瓶颈已经不是原来的 I/O 开销,而是转移为内存读取与复杂计算.连接操作则是一个典型的代表,在复杂的分析场景中,跨表的查询十分常见.以 OLAP 的基准测试 TPC-H8为例,其 22 个查询中有 20 个查询使用了连接操作9以进行跨表的数据分析.仅有 2 个查询(Q01 与 Q06)是进行单表内的数据分析而不需要进行连接操作.而在我们的测试中(实验配置:4 台机器,每台机器部署 20 个工作线程,每台机器 SF=10),连接操作的时间占比甚至会达到 80%的时间(详见图 2,柱上标识连接操作占总查询时间的百分比).因此,需要对目前常用的连接方式进行算法层面(第 2.1 节)与实际运行层面(第 2.2 节)的分析,以提出对于连接操作的优化方法,从而对优化整个查询的性能有所助益.2 0001 6001 2008004000执行时间(ms)Q03Q04Q08Q09Q10Q12Q18Q215%59%39%20%9%58%80%32%连接操作剩余部分图2使用 MonetDB 对 TPC-H 中部分查询的查询时间拆解沈斯杰等:基于图结构索引的分布式 OLAP 加速方法4665 2.1 常用连接方式的算法复杂度在基于磁盘的数据库研究中,对于连接操作的性能研究会从连接操作的 I/O 开销(cost)进行考虑,例如对于不同连接操作所需要加载的磁盘页面数(详见第 1.2 节).对于内存数据库而言,由于这样的 I/O 开销已经去除,因此计算 I/O 开销以评估连接方式性能的方法已不合适.因此,我们需要通过研究不同连接方式的算法复杂度,来评估它们在内存计算时的性能.我们将不同的连接方式的使用分为先后两个阶段:准备阶段与匹配阶段.第 1 阶段(准备阶段)是连接之前准备特定的数据结构,例如排序归并连接中的排序以及哈希连接中的构建哈希表的操作.第 2 阶段(匹配阶段)是按照连接条件进行对应行筛选的过程.同时为了进行有效分析,我们假设连接操作的两张表是“一对多(onetomany)”的关系,即外层表的一条数据可能与内层表的多条数据匹配,而内层表的一条数据至多与外层表的一条数据匹配30.若没有这个假设,则这些常用连接方法的复杂度在最坏情况下为 O(mn),例如外层表的所有数据都与内层表的所有数据匹配.表 2 的第 24 列给出了内存中,使用 3 种连接方式,即内嵌循环连接,排序归并连接以及哈希连接在两个阶段的时间复杂度3032.表 2 中,进行连接操作的外层表与内层表的行数分别为 m 和 n.对于排序归并连接,表中给出的初始化复杂度为两张表是未排序时的复杂度,未排序的表在进行归并操作前需要进行排序.表2内存中不同连接方式的时间复杂度分析阶段 内嵌循环连接排序归并连接哈希连接 内嵌循环连接(树状索引)内嵌循环连接(哈希索引)图结构索引连接LinkJoin准备O(mlogm+nlogn)O(n)匹配O(mn)O(m+n)O(m+n)O(mlogn+n)O(m+n)O(m+n)通过表 2 的第 24 列可以看到,相比于内嵌循环连接,排序归并连接与哈希连接能够减少匹配阶段的时间复杂度,但是需要不少时间进行数据结构的初始化准备,而且对于归并-排序连接,这种初始化时间可能会比匹配时间更长,而哈希连接的实际匹配时间也与哈希函数的选择以及哈希桶的数目相关.内嵌循环连接,是不需要第 1 阶段进行数据结构的初始化的.因此,在数据库中,也会使用内嵌循环连接以避免初始化开销,其中一种常用的优化即基于索引的内嵌循环连接33,34,在 MySQL,SQLServer,PostgreSQL,SAPHANA 等商用数据库中也得以使用.基于索引的内嵌循环连接是对于内嵌循环连接的一种有效优化,该优化复用数据库中已有的索引结构,因此不需要准备阶段.其进行连接的复杂度与所选用的索引结构有关.使用索引进行连接操作时,类似于内嵌循环连接使用两层主要的循环,其中外循环仍需要遍历外层表的每一项,而内层表的遍历则变成了使用外层表的属性去匹配索引.树状索引和哈希索引一次查找的复杂度为 O(logn)与 O(1),同时最坏情况下需要遍历一次所有内层表的数据,因此这两种索引结构下的连接操作复杂度分别为 O(mlogn+n)与 O(m+n),如表 2 的 56 列所示.如表 2 所示,在目前常用的连接方式中,使用哈希索引的连接方式在内存计算时的算法复杂度最小,其复杂度取决于外层表的大小.而表 2 中的最后一列中,使用基于图结构索引的连接方式 LinkJoin,能够获得同样最小的复杂度(详见第 3.2 节),在此基础上,我们进行系统层面的优化,达到相比其他连接方式更优的连接性能.2.2 连接操作的实际用时占比分析为了进一步确定连接操作在内存 OLAP 处理中所占的时间比重,我们选择使用一个先进的开源内存数据库MonetDB4进行测试分析.MonetDB 在近年关于内存 OLAP 的研究中常被作为代表系统用于研究或者进行分析1821.我们在 MonetDB 上进行连接操作的实际用时占比分析,并且建立了哈希索引进行连接操作的加速.实验针对 OLAP 的基准测试 TPC-H 进行纯内存查询,对于每个查询进行拆解分析,即测量每个查询所用时间以及其中连接操作所占用的时间.如图 2 所示,我们选取了连接操作用时占整个查询用时的比例不小于 5%的查询作为连接操作占比明显的查询进行分析.可以看到在选取的 8 个查询中,连接操作占整个查询时间的比重最高可以达到 80%(Q18).在 22 个查询中,有 7 个查询的连接操作用时比重超过 20%.其中,有 3 个查询的连接操作用时比重超过 50%,成为整个查4666软件学报2023 年第 34 卷第 10 期询中的主要性能瓶颈.可以发现,即使使用算法复杂度较小的基于哈希索引优化的内嵌循环连接方式,连接操作仍旧是在内存查询处理中耗时的操作之一.因此,对于一些连接操作用时占比较大的查询而言,优化连接操作的时间能够对于优化整个内存查询的性能起到关键的作用.3 研究动机与系统架构 3.1 图结构索引近年来,随着大数据技术的不断发展,数据不仅是从体量上增大,数据之间的关系也越发复杂,为了更好地刻画这些数据之间的关系,相比原来关系型数据库中的关系模型,用图结构存储数据能够更好地表达这些数据之间的关联.使用图结构存放数据时,数据分为点(vertex)和边(edge)两类数据,点用于存放一些实体信息,例如人员信息,商品信息等,而边存放点之间的关系,例如购买情况等.然而,对于关系型数据库,在数据库层缺少表与表之间的关系信息.如图 1 中的示例,订单 ORDERS 与订单条目 LINEITEM 的连接匹配只能通过值匹配来进行.即使是使用了索引结构来加速连接操作也是需要通过索引结构的查询.图 3(a)给出了在关系型数据库中使用连接操作的执行过程.示例中的连接查询使用了 3 张表:订单表(ORDERS),订单条目表(LINEITEM)以及物品信息表(ITEM).一个常用的查询是,通过订单查询订单中所购买的物品信息,因此需要连接 ORDERS,LINEITEM 与 ITEM 这 3 张表.在连接过程中,ORDERS 中每一条订单信息通过订单条目的编号(L_ID)来找到 LINEITEM 表中对应的订单条目,订单条目再通过货品编号(I_ID)来找到ITEM 表中对应的货品信息.为了提升连接的性能,在对应的属性列(LINEITEM 的 L_ID 列,ITEM 的 I_ID 列)上建立了关系型索引结构(如树状或哈希索引).对于使用索引进行连接操作,对于每一行表中的数据,都需要通过索引查询到另一张表中对应数据所在的位置.如果是多张表的连接,则需要在筛选出部分结果后继续进行索引的查询.可以看到,在关系型数据库中的索引本身是用于查询数据的加速,而并不是为了连接操作而设计的,只能减少连接操作中不必要的读取和筛选.在图 3(a)的示例中,为了筛选一条结果集中的数据,都需要经历两次索引结构的查询.ORDERSLINEITEMITEML_O_IDI_ID关系型索引(树状/哈希)关系型索引(树状/哈希)ORDERSLINEITEMITEM图结构索引(a)使用关系型索引结构(b)使用图结构索引图3关系型数据库中 3 张表的连接操作示例对于关系型索引而言,进行连接操作的匹配是通过值的查询和匹配所完成的,因此需要引入查询的开销.而数据库在制定表的结构(schema)时,所建立起的语义信息(例如外键),是缺失的.而图结构能够在表达数据之间的关联,提供更丰富的语义.因此,我们观察到是引入一个图结构的索引能够加速关系型数据库的连接操作,减少连接过程中查询索引所带来的开销(实验见第 5.4 节).一个图结构的索引如图 3(b)所示,该实例中仍旧进行的是 ORDERS,LINEITEM 和 ITEM 这 3 张表之间的连接,但是提供了一个图结构的索引.图结构索引通过存储数据库数据之间的拓扑结构来加速连接操作.在该索引中,图的顶点表示数据库中的一行数据(例如示例中的蓝色顶点表示 ORDERS 中的一行),这个顶点仅存放这这条数据的位置信息(例如同一台计算节点中的内存地址或偏移,跨计算节点的节点编号和内存偏移等)和类型,而不沈斯杰等:基于图结构索引的分布式 OLAP 加速方法4667会存放实际的属性.而图结构中的边,则表示的是数据库数据之间的关系,例如 ORDERS 所对应的顶点会有出边指向 LINEITEM 一个顶点(红色顶点),表示一条订单项.以此类推,一条 OERDERLINE 的数据也会指向一个 ITEM(黄色顶点).由于顶点中存放着数据的位置信息,因此,可以根据出边直接在连接操作时定位对应的数据.在图 3(b)的示例中,当进行 3 张表的连接操作时,首先通过 ORDERS 中的一行数据找到它在图结构索引中所对应的节点,然后通过其出边找到它的订单项,并通过位置可以获取该订单项的实际数据.同时,可以通过订单项的出边,找到 ITEM 的信息.通过以上示例可以看出,原有建立在数据库表上的关系型索引(例如树状索引,哈希索引等)主要是为了直接加速单表查询而设计的,而连接操作复用这些索引虽然能够减少一定的查询时间,但是仍旧有一定的查询开销(通过对多表进行连接操作的视图后建立关系型索引,也是一种在效果上建立多表索引的方式,然而对多表建立这种视图会产生大量的存储开销)而图结构索引保存着数据之间的拓扑关系,它的设计是为了加速连接操作,与为了加速单表查询的索引相比,图结构索引在加速连接操作时有以下几个优势:(1)减少索引的查询开销.由于图结构索引的节点中直接存放对应数据的位置信息,因此可以通过 O(1)的时间复杂度直接进行定位与查询.尤其是当数据在其他计算节点上,可以通过位置信息减少远端计算节点上的计算操作(如数据查找和筛选)而直接获取数据.(2)提供数据之间的拓扑结构信息,优化特定连接操作的执行.例如,对于 COUNT 操作能够直接通过出边的数量而直接返回.对于没有匹配数据的也能够减少不必要的索引查询.(3)减少多张表连接的索引查询次数.当需要多张表进行连接操作时,对于每一条结果集的数据,索引的查询只需要遍历一次图结构即可完成,而在为单表查询建立的索引需要在每张表(除了最外层表)上进行索引的查询.3.2 复杂度分析本节我们将从算法复杂度的角度来分析基于图结构的连接操作.与基于索引的内嵌循环连接一样,索引是在数据加载时离线计算的,因此也不需要额外的准备阶段,可以在进行连接操作时直接使用.因此,仅需考虑其匹配阶段的复杂度即可.算法 1 给出了使用图结构索引进行连接操作的主要步骤,设连接操作的外层表与内层表分别为 R 与 S.与一般的基于索引的内嵌循环连接类似,基于图结构索引的连接操作对于外层表的每一行进行遍历.不同的是,需要通过 locate_vertex 过程获取该行在图结构索引中所对应的顶点(第 12 行).由于图结构索引在建立时,会将与该顶点的数据有匹配关系的数据作为该顶点的邻居进行存储,因此内循环对该顶点的邻居进行遍历(第 35 行).由于为了空间节省,在顶点的邻居中保存的是数据的标识符(即算法中的 s_id)而非数据本身,因此需要通过 locate_row过程进行定位(第 4 行).然后,再将两张表中匹配的数据进行处理与输出(第 5 行).算法 1.基于图结构索引的连接操作.R:连接操作的外层表S:连接操作的内存表1.foreachr inR:2.v=locate_vertex(r)3.foreachs_idinv.neighbors:4.s=S.locate_row(s_id)5.process_and_output(r,s)根据算法 1 主要步骤,我们可以对该索引方法进行算法复杂度分析.与第 2.1 节和表 2 一致,我们设外层表和内层表的行数分别为 m 和 n.并且为了进行有效分析,同样假设连接操作的形式是两张表“一对多”的形式.对于外层表的每一