GPU数据库OLAP优化技术研究

GPU数据库近年来在学术界和工业界吸引了大量的关注. 尽管一些原型系统和商业系统(包括开源系统)开发了作为下一代的数据库系统, 但基于GPU的OLAP引擎性能是否真的超过CPU系统仍然存有疑问, 如果能够超越, 那什么样的负载/数据/查询处理模型更加适合, 则需要更深入的研究. 基于GPU的OLAP引擎有两个主要的技术路线: GPU内存处理模式和GPU加速模式. 前者将所有的数据集存储在GPU显存来充分利用GPU的计算性能和高带宽内存性能, 不足之处在于GPU容量有限的显存制约了数据集大小以及稀疏访问模式的数据存储降低GPU显存的存储效率. 后者只在GPU显存中存储部分数据集并通过GPU加速计算密集型负载来支持大数据集, 主要的挑战在于如何为GPU显存选择优化的数据分布和负载分布模型来最小化PCIe传输代价和最大化GPU计算效率. 致力于将两种技术路线集成到OLAP加速引擎中, 研究一个定制化的混合CPU-GPU平台上的OLAP框架OLAP Accelerator, 设计CPU内存计算、GPU内存计算和GPU加速3种OLAP计算模型, 实现GPU平台向量化查询处理技术, 优化显存利用率和查询性能, 探索GPU数据库的不同的技术路线和性能特征. 实验结果显示GPU内存向量化查询处理模型在性能和内存利用率两方面获得最佳性能, 与OmniSciDB和Hyper数据库相比性能达到3.1和4.2倍加速. 基于分区的GPU加速模式仅加速了连接负载来平衡CPU和GPU端的负载, 能够比GPU内存模式支持更大的数据集.     

向量分组聚集计算技术研究

分组聚集计算是OLAP重要的操作符之一,分组聚集操作是一种数据密集型负载。在内存数据库和GPU数据库应用场景下不仅需要研究其性能优化技术,还需要研究如何优化分配分组聚集计算执行场地以最小化CPU与GPU之间的数据传输代价。针对异构计算平台的硬件特征提出了向量聚集计算技术,将位于传统流水线末端的分组聚集计算按照“早分组,晚聚集”策略进行分解与下推,实现将数据密集型的分组聚集计算从流水线中分离,将操作与处理器计算特性优化匹配,实现异构计算平台上最优的负载分配。通过将传统基于哈希分组的聚集计算转换为向量分组聚集计算,显著提升了分组聚集计算性能。实验结果表明,向量分组聚集技术相对于具有代表性的高性能内存数据库Hyper、GPU数据库MapD最大达到5~8倍的性能提升。向量聚集计算不仅提高了OLAP聚集计算性能,而且实现了将数据密集型负载从查询计划中分离的目标,使异构计算平台能够根据处理器的硬件特性优化配置计算资源,提高异构计算平台OLAP的整体性能。     

向量计算Array OLAP查询处理技术

多核和众核处理器成为新的具有强大并行处理能力的大内存计算平台的主流配置。多核处理器遵循以LLC（Last Level Cache,最后一级cache）大小为中心的优化技术,而众核处理器,如Phi、GPU协处理器,则采用较小的cache并以更多的硬件级线程来掩盖内存访问延迟的设计。随着处理核心数量的增长,计算框架更倾向于面向大规模处理核心的、代码执行效率高并且扩展性强的设计思想。提出了一种基于数组存储和向量处理的内存分析处理框架Array OLAP,简化OLAP的存储模型和查询处理模型。在Array OLAP计算框架中,维表规范化为基于向量的维过滤器,事实表规范化为带有多维索引的度量属性。通过多维索引计算,一个多维查询被简化为事实表上的向量索引扫描并根据度量表达式进行聚集计算。规范化的向量查找和向量索引扫描具有较好的代码执行效率,并且阶段化的处理模型更好地适应不同的计算平台,将计算阶段分配给最适合的计算平台。同时,Array OLAP是一种面向数据仓库模式特点的设计,向量处理模型设计简单,对于数据仓库维表较小且增长缓慢的特点具有较好的效率。描述了在不同平台上的Array OLAP计算框架并且通过基准测试评估Array OLAP的性能,通过与当前的内存分析型数据库的性能对比,Array OLAP性能超过主流的内存分析型数据库并且可以平滑地迁移到新的硬件平台。     

内存数据库在TPC-H负载下的处理器性能

Ailamaki等人1999年研究了数据库管理系统(database management system,简称DBMS)在处理器上的时间开销分解.此后,相关研究集中在分析DBMS在处理器上的瓶颈.但这些研究工作均是在磁盘数据库DRDBs(disk resident databases)上开展的,而且都是分析DBMS上的TPC-C类负载.然而,随着硬件技术的进步,现代计算机的多级缓存结构(memory hierarchy)在逐渐地"上移".例如,容量越来越大的芯片内缓存(on-chip caches)和芯片外缓存(off-chip caches),容量越来越大的RAM,Flash Memory等等.为此,处理器负载分析的研究工作也应随之"上移".研究内存数据MMDBs(mainmemory resident databases)在计算密集型负载下的处理器行为特性.由于磁盘数据库的主要性能瓶颈是磁盘I/O,因而可以用索引、压缩等技术进行优化;然而,内存数据库的性能瓶颈却在于处理器和内存之间的数据交换.针对这一问题,首先分析了磁盘数据库和内存数据库在TPC-H负载下处理器性能瓶颈的差异,并给出了一些优化建议,提出了通过预取的优化方法.其次,通过实验比较了不同存储体系结构(行存储与列存储)对处理器利用率的差异,并探索了下一代内存数据库体系结构方面的解决方案.此外,还研究了索引结构对处理器多级缓存的影响,并给出了索引的优化建议.最后,提出一个微测试集用于评估内存数据库在DSS(decision support system)负载下处理器的性能及行为特性.研究结果会对运行于下一代处理器上的内存数据库体系结构设计和性能优化提供一定的实验依据.     

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

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

一种适应GPU的混合OLAP查询处理模型

通用GPU因其强大的并行计算能力成为新兴的高性能计算平台,并逐渐成为近年来学术界在高性能数据库实现技术领域的研究热点.但当前GPU数据库领域的研究沿袭的是ROLAP(relational OLAP)多维分析模型,研究主要集中在关系操作符在GPU平台上的算法实现和性能优化技术,以哈希连接的GPU并行算法研究为中心.GPU拥有数千个并行计算单元,但其逻辑控制单元较少,相对于CPU具有更强的并行计算能力,但逻辑控制和复杂内存管理能力较弱,因此并不适合需要复杂数据结构和复杂内存管理机制的内存数据库查询处理算法直接移植到GPU平台.提出了面向GPU向量计算特性的混合OLAP多维分析模型semi-MOLAP,将MOLAP(multidimensionalOLAP)模型的直接数组访问和计算特性与ROLAP模型的存储效率结合在一起,实现了一个基于完全数组结构的GPU semi-MOLAP多维分析模型,简化了GPU数据管理,降低了GPU semi-MOLAP算法复杂度,提高了GPU semi-MOLAP算法的代码执行率.同时,基于GPU和CPU计算的特点,将semi-MOLAP操作符拆分为CPU和GPU平台的协同计算,提高了CPU和GPU的利用率以及OLAP的查询整体性能.     

面向多核CPU和GPU平台的数据库星形连接优化

针对联机分析处理（OLAP）中事实表与多个维表之间的星形连接执行代价较高的问题,提出了一种在先进的多核中央处理器（CPU）和图形处理器（GPU）上的星形连接优化方法。首先,对于多核CPU和GPU平台的星形连接中的物化代价问题,提出了基于向量索引的CPU和GPU平台上的向量化星形连接算法;然后,通过面向CPU cache和GPU shared memory大小的向量划分来提出基于向量粒度的星形连接操作,从而优化星形连接中向量索引的物化代价;最后,提出了基于压缩向量的星形连接算法,将定长向量索引压缩为变长的二元向量索引,从而在低选择率时提高cache内向量索引的存储访问效率。实验结果表明,在CPU平台上向量化星形连接算法相对于常规的行式或列式连接性能提升了40%以上,在GPU平台上向量化星形连接算法相对于常规星形连接算法性能提升超过了15%;与当前主流的内存数据库和GPU数据库相比,优化的星形连接算法性能相对于最优内存数据库Hyper性能提升了130%,相对于最优的GPU数据库OmniSci性能提升了80%。可见基于向量索引的向量化星形连接优化技术有效地提高了多表连接性能,与传统优化技术相比,基于向量索引的向量化处理提高了较小cache上的数据存储访问效率,压缩向量进一步提升了向量索引在cache内的访问效率。     

云原生数据库综述

云基础设施的虚拟化、高可用、可弹性调度等特点,为云数据库提供了开箱即用、可靠可用、按需计费等优势.云数据库按照架构可以划分为云托管数据库(cloud-hosted database)以及云原生数据库(cloud-native database).云托管数据库将数据库系统直接部署到云上虚拟机环境中,具备低成本、易运维、高可靠的优势.在此基础上,云原生数据库充分利用云基础设施弹性伸缩的特点,采用计算存储分离的架构,实现了计算资源和存储资源的独立伸缩,进一步提升数据库性价比.然而计算存储分离的架构为数据库系统设计带来了新的挑战.深入分析云原生数据库系统的架构和技术.首先将云原生OLTP和云原生OLAP的数据库架构按照资源分离模式的差异分别进行归类分析,并对比各类架构的优势与局限.其次,基于计算存储分离的架构,按照各个功能模块深入探讨云原生数据库的关键技术:主要包括云原生OLTP关键技术(数据组织、副本一致性、主备同步、故障恢复以及混合负载处理)和云原生OLAP关键技术(存储管理、查询处理、无服务器感知计算、数据保护以及机器学习优化).最后,总结现有云原生数据库的技术挑战并展望未来研究方向.     

一个基于三元组存储的列式OLAP查询执行引擎

大数据与传统的数据仓库技术相结合产生了大数据实时分析处理需要（volume+velocity）,它要求大数据背景下的数据仓库不能过多地依赖物化、索引等高存储代价的优化技术,而要提高实时处理能力来应对大数据分析中数据量大、查询分析复杂等特点.这些查询分析操作一般表现为在事实表和维表之间连接操作的基础上对结果集上进行分组聚集等操作.因此,表连接和分组聚集操作是ROLAP（relational OLAP）性能的两个重要决定因素.研究了新硬件平台下针对大规模数据的OLAP查询的性能,设计新的列存储OLAP查询执行引擎CDDTA-MMDB（columnar direct dimensional tuple access-main memory databasequeryexecutionengine,直接维表元组访问的内存数据库查询执行引擎）.基于三元组的物化策略,使得CDDTA-MMDB能够减少内存列存储模型上表连接操作访问基表和中间数据结构的次数.首先,CDDTA-MMDB将查询分解为作用在维表和事实表上的子查询,如果只涉及过滤操作,子查询将生成<代理键,布尔值>二元组;否则,子查询生成<代理键,关键字,值>三元组.然后,只需一趟扫描事实表,利用事实表的外键映射函数直接定位相应三元组或者二元组,完成相应的过滤、连接或聚集操作.CDDTA-MMDB充分考虑了内存列存储数据库的设计原则,尽量减少随机内存访问.实验结果表明：CDDTA-MMDB是高效的,与具代表性的列存储数据库相比,比MonetDB 5.5快2.5倍,比C-store的invisible join快5倍;并且,CDDTA-MMDB在多核处理器上具有线性加速比.     

列存储数据库中压缩位图索引技术

为提高压缩码的利用率,提出一种适用于列存储数据库的压缩位图索引技术。定义反转、合并等操作,将所有计算的输入值与输出值格式化为位向量形式。通过活跃度衡量索引中位向量的复杂度,并对压缩位向量进行直接计算,优化where子句和group by子句在查询执行过程中的数据提取。在SSB数据集上的实验结果证明,该技术能提高29.7%~38.9%的压缩位图索引性能。     

云原生数据湖服务平台的设计与实现

云原生数据湖已经成为数据管理和分析领域的研究热点,相关技术和应用也得到了广泛的关注和探索。数据湖部署存在着成本高、组件之间兼容性差等问题,存算不分离制约着数据湖平台延展性,缺乏完备的数据入湖体系容易引起数据湖沼泽的形成,导致用户无法从中提取数据价值。该文设计并实现了云原生数据湖服务平台,平台以Kubernetes为底层构建云原生环境,结合容器技术将数据湖组件镜像化,同时设计数据湖存算分离方案来提高数据湖平台的可扩展性和可移植性,并配合监控、组装生产线将镜像容器化,实现数据湖上云操作。并建立用户入湖作业与云原生计算引擎之间的桥梁,对入湖信息进行预处理,提供多类型作业以满足多元化入湖场景,以统一catalog的方式将数据写入数据湖中。实际运行结果表明,该平台既提高了数据湖平台的灵活性和可靠性,又确保了元数据和数据资产的规范性存储。     

位图连接索引服务机制研究

位图连接索引是数据仓库中一种有效的优化表间连接操作性能的索引机制。在大内存分析处理应用场景下,位图连接索引不仅需要权衡索引的内存和CPU开销,还需要进一步考虑处理器平台所带来的性能收益和数据访问延迟。提出了基于服务的位图连接索引管理机制,其主要特点体现在三个方面：独立于数据库的自管理索引机制;基于存储空间约束的TOP K关键字位图连接索引机制;处理器敏感（processor-conscious）的位图连接索引技术。索引服务将索引从数据库中内置的数据结构变成数据库外的索引服务层,通过对用户查询负载的分析模块和索引服务管理模块改变传统的由数据库管理员人工管理索引的模式,同时借助于协处理器和内存云技术提高索引服务的性能和灵活性。实验测试结果表明,索引服务机制能够有效地提高索引存储和访问效率,在通用GPU的强大并行处理能力的支持下,位图连接索引服务的性能和数据库整体查询处理性能都得到了显著的提升。     

基于MCR框架的热力学数据库架构模式设计

分析了三层和n层架构模式的Web热力学数据库在数值计算方面存在的问题。提出了基于MCR框架的、多层的、分布式计算的Web热力学数据库架构模式,将Web热力学数据库业务逻辑层与数值计算过程分离,简化了数值计算的过程。同时,利用服务器群集技术构建数值计算引擎集群,大大提高了Web热力学数据库数值计算能力和速度。     

用于内存数据库的Hash索引的设计与实现

电信领域已成为数据密集型行业,需要高性能的数据库系统作为支撑系统,基于磁盘的数据库系统不能满足“实时”、“近实时”访问数据库的需求,将数据库核心数据驻留在内存中,可以使用内存数据库来满足需求。Hash索引是数据库系统中广泛使用的索引技术之一,它能够快速地访问数据,易于设计和实现。该文根据内存数据库的特点,为电信网管系统的内存数据库设计并实现了Hash索引。     

基于Hadoop的煤矿数据中心架构设计

根据煤矿安全生产业务需求及智慧矿山发展要求,新型的煤矿数据中心需满足对同一时空坐标体系下煤矿海量、多元数据的高效处理、缓存、计算、存储与发布。针对传统煤矿数据中心各类数据离散存储,数据集成、业务应用及数据分析难度大等问题,设计了一种基于Hadoop的煤矿数据中心架构。采用Storm实时数据流引擎进行数据实时计算,并应用MapReduce,Spark实现批处理计算和内存计算,解决高频时序数据存储与海量数据计算问题;采用Hadoop分布式文件系统(HDFS)实现文件的可靠存储,并采用HBase分布式存储数据库实现历史数据的持久化存储,利用其无模式稀疏设计满足同一时空坐标体系下的数据分析需求;采用Redis作为实时数据库存储数据快照进行最新数据检索。基于Hadoop的煤矿数据中心充分利用大数据技术的高速数据存取和压缩性能,通过统一的云计算数据中心,有效降低了煤炭企业数据应用的复杂度及数据中心日常运维难度,可为智慧矿山建设奠定数据基础。     

基于ARM V8平台的向量算法库实现与优化

基于ARM V8架构的VecOp向量算法库,提出一种基础向量算法在ARM V8平台上实现和优化的方案。从访存对界优化、指令集优化、基本块优化以及向量分支优化4个方面进行精细调优,提升向量算法函数在ARM V8平台上的性能,以实现VecOp算法库在ARM V8平台上的优化。实验结果表明,该方案在ARM V8计算平台上实现的向量算法库性能提升可达到10%～300%。     

基于行存储模型的模拟列存储策略研究

列存储模型在只读的数据仓库应用中表现出非常好的性能,很多研究表明对于典型的OLAP查询,列存储数据库的性能大大优于行存储数据库.根据列存储模型的特性及数据处理特点,在传统的行存储模型关系数据库中模拟列存储的存储模式及数据处理过程,并通过优化的基于聚类的列存储模型、全索引模型与典型的行存储方式进行类比性能测试.实验结果显示,采用传统行存储模型模拟的列存储模型针对OLAP类查询具有很高的数据访问速度及查询性能,整体性能介于行存储数据库与列存储数据库之间.对于实际应用系统来说,该方案减少了整体系统部署代价,而且无需为提高OLAP查询的性能增加额外系统(列存储)投入,从而为OLAP应用提供了良好的性能支持.     

DB4Trans:数据库内置知识图谱嵌入模型训练引擎

知识图谱嵌入技术将知识图谱中的实体和关系嵌入到连续的向量空间中,在简化图谱操作的同时保留知识图谱的固有结构,并有助于完成诸如图谱补全、链接预测等下游任务.随着基于知识的人工智能的日益普及和应用,知识图谱的数据规模正在急剧增加.然而,大部分的知识图谱嵌入工作主要关注模型训练的结果,忽略了对于数据规模的可扩展性,在处理大规模知识图谱时表现出较差的性能.近年来的一些研究工作将数据库技术应用于机器学习算法的优化,同时提供了用于数据库内机器学习的各类工具.通过将知识图谱嵌入模型与数据库在数据管理上的优势进行有效的结合,能够在保证知识图谱嵌入模型训练的准确率和效率的同时,提供更好的可扩展性以支持大规模知识图谱数据的训练.基于此,本文提出一种数据库内置知识图谱嵌入模型训练引擎DB4Trans.首先,设计了一种用于知识图谱嵌入模型训练的数据存储方案,对实体和关系进行编码并建立索引结构,以实现模型训练过程中对中间结果的快速访问和更新;其次,提出了一种数据库内置的模型训练优化算法,对数据库与内存间的数据批量交换方案进行设计以支持大规模数据的训练与存储;最后,在不同数据集上进行了测试,比较了模型训练与预测的...     

基于Supersonic的并行分组聚集

针对在分析型联机分析处理(OLAP)应用中频繁出现的数据密集型操作符——分组聚集耗时较多的问题,提出Cache友好的分组聚集算法对该操作进行性能优化。首先,为充分发挥列存储在数据密集型计算方面的优势,采用基于开源的列存储查询执行引擎Supersonic,并在此之上设计Cache友好的分组聚集算法;其次,为加速查询的执行,使用并行技术,将单线程的分组聚集算法改为多线程并行的分组聚集算法。基于Supersonic设计并实现4种并行分组聚集算法:无共享Hash表并行分组聚集(NSHPGA)算法、表锁共享Hash表并行分组聚集(TLSHPGA)算法、桶锁共享Hash表并行分组聚集(BLSHPGA)算法、节点锁共享Hash表并行分组聚集(NLSHPGA)算法,且在不同的分组势集、不同的线程数的情况下,针对上述4种算法做了多组实验。通过对比3种不同粒度的共享Hash表并行分组聚集算法的加速比,得出NLSHPGA算法在加速比和并发度两方面表现最好,部分查询可达到10倍加速比;通过比较NSHPGA算法和NLSHPGA算法的加速比、Cache miss内存使用等情况,得出NLSHPGA算法在分组势集大于8时,加速比超过NSHPGA算法,并且Cache miss更低,使用的内存更少。     

一种负载敏感的OLAP查询结果缓存管理技术

OLAP(On Line Analysis Processing)是数据仓库的典型应用,在数据仓库中频繁并发地执行涉及较大数据量的OLAP查询时,其查询处理效率易于逐渐降低。缓存技术是一种有效降低OLAP查询处理延时的方法。在现有的缓存数据存储、淘汰策略等研究工作的基础上,结合OLAP任务的负载特性、OLAP任务的结果集大小等因素对性能的影响,提出了一种负载敏感的OLAP查询缓存管理技术Workload-LRU,并实现了一个ROLAP(Relational OLAP)原型系统。实验证明,Workload-LRU技术获得了较好的性能提升效果。