GPU以其超高速计算能力和超大数据处理带宽受到数据库厂商及研究人员的青睐,以GPU计算为核心的数据库分支(GDBMS)蓬勃发展,以其吞吐量大、响应时间短、成本低廉、易于扩展的特点,与人工智能、时空数据分析、数据可视化、商务智能交互融合能力,彻底改变了数据分析领域的格局.将对GDBMS的四大核心组件——查询编译器、查询处理器、查询优化器和存储管理器进行综述,希望促进未来的GDBMS研究和商业应用.
In recent years, GPU is favored by database manufacturers and researchers for its ultra-high-speed computing capacity and huge data processing bandwidth. The database branch—GPU accelerating database or GPU database (GDBMS) is developing vigorously. With the characteristics of high throughput, low response time, high cost performance, and easy to expand, integrated with artificial intelligence (AI), business intelligence (BI), spatial-temporal data analysis, data visualization, GDBMS have the potential to change the world pattern of data analysis field. This study surveys the four core components of GDBMS: query compiler, query processor, query optimizer, and storage manager, hoping to promote the future research and commercial application of GDBMS.
近年来, GPU已经从专业的图形处理器发展成为通用的计算处理器(general-purpose computing on graphics processing units, 简称GPGPU)[
由于受能耗墙(“heat wall”)限制[
GPU与CPU具有不同的体系结构和处理模式, 将更多的片上空间用于计算单元, 控制单元和缓存单元相对很少, 使得单块GPU上拥有数千个并发计算核心.因此, 在同样的主频下, GPU能够取得更高的并发计算能力, 也使GPU具有满足大数据处理需求的巨大潜能.与CPU不同, GPU每两年取得性能上的突破, 保持了近似摩尔定律的性能增长: 以英伟达公司当年最顶级显卡的单精度浮点数计算峰值为例, 2013年, Titan Black为5 TFLOPS (每秒运行5兆次单精度浮点数计算指令); 2015年, Titan X达到7 TFLOPS; 2017年, Titan V为15 TFLOPS; 2020年, RTX 3090达到36 TFLOPS.与基于CPU的分析技术相比, 基于GPU的数据库可实现数量级的加速, 并具有更高的性价比.同时, 由于单个GPU包含大量计算能力, 因此扩展GPU数据库仅需要向服务器添加更多GPU, 而不是添加更多服务器.在时空数据OLAP分析任务和结果的可视化展示方面, 几十个GPU的GPU数据库可以取得近千台普通CPU服务的数据库处理能力, 而其响应时间甚至更短.比如: Tesla V100 GPU提供120 TFLOPS的计算力, 8块互联即可以顶上160台双CPU的服务器!GPU极大地加速了可以并行化的操作, 即使数据集增长到数百万或数十亿条记录, GPU数据库也可以在毫秒内返回复杂的查询.
除了极高的性能之外, GPU数据库还在功能上日趋完善: 基于商务智能BI的可视化交互式图表查询界面, 让数据查询和探索更人性化; 同时支持标准SQL查询语言, 相较于其他大数据OLAP分析平台, 分析周期大大缩短, 往往只要几分钟就可以完成以往数天乃至一周的工作; 时空数据分析功能, 让基于位置的数据分析更高效、及时; GoAI(GPU open analytics initiative, GPU开放分析计划)产业联盟和GPU数据帧(GPU data frame, GDF)构建了数据库库和人工智能应用程序之间数据交换标准, 使数据科学家可以停留在GPU上的同时探索数据, 训练机器学习算法并构建人工智能应用程序.现在, 我们可以使用GPU数据库分析每周数十亿次的电视观看记录, 以做出广告决策; 根据移动定位推进时空思考、计算和工程设计, 从自然灾害到能源可持续性, 解决全球挑战, 都需要了解现象在时间和空间上的联系.Covid-19疫情以来, 接触者追踪为GPU数据库带来新的挑战和机遇, 通过将人口统计数据与运动数据集成在一起, 并在地理和时间多个维度聚合数据, 人们可以及时获得了疫情第一手资料, 做出防疫决策.
纵观整个GPU数据库领域, 不管是开源系统还是商业系统, 其核心研究内容主要集中在查询编译器(query compilation)、查询处理器(query processing)、查询优化器(query optimizer)和存储管理器(memory management)等4大部件: 查询编译器要将用户的SQL语言描述的查询需求转化为CPU- GPU异构计算环境下的查询计划; 查询处理器需要应用GPU并行计算技术实现关系型数据处理的各种算子, 挖掘GPU峰值计算能力; 查询优化器利用机器学习乃至人工智能技术, 结合CPU-GPU异构计算环境和查询计划特点以及数据分布特征, 生成最优(次优)的异构查询计划; 存储管理器需要在异构数据存储管理、数据存储格式、数据压缩、数据访问等问题上做出决策.本文余下部分将依次对GPU数据库的4大部件的关键技术进行综述.
GDBMS(GPU database management system or GPU accelerated database management system), 顾名思义, 就是使用GPU进行或加速数据增删改查的数据库管理系统.从GDBMS的系统形态上, 本文将其分为研究原型(R-GDBMS: for research)和商用系统(C-GDBMS: for commercial)两大类, 如
GDBMS系统全景图
GDBMS landscape
商用GDBMS中, 进一步可以分为3类.
● 第1类是支持GPU计算的传统数据库.这类GDBMS在已有传统数据库基础之上, 将特定算子部署到GPU上用以加速的查询处理, 包括以PostgreSQL为基础的PG-Storm系统和DB2的扩展模块DB2 BLU.这类数据库与现有数据库集成度高、周边工具完善、且具有一定的与OLTP系统集成的能力;
● 第2类是非内存型GDBMS, 使用GPU完成全部或者大部分数据库关系运算, 可以分析超过10TB的数据量, 包括SQream和BlazingDB;
● 第3类是内存型GDBMS, 该类系统将数据全部驻留内存, 以发挥GPU的全部潜在性能、提高数据处理速度, 可以处理1TB~10TB的较小数据集, 包括OmniSci(原MapD), Kinetica(原GPUDB), MegaWise, Brytlyt.
一般来说, 后两类GDBMS由于专为GPU计算设计, 没有传统数据库中束缚性能的遗留冗余模块, 所以性能更高.
目前, 商用GDBMS普遍比基于CPU的解决方案在性能上有几个数量级的提升.比如: 根据OmniSci(MapD)最新的白皮书介绍[
研究原型GDBMS将重点放在了全GPU计算上, 研究数据可以在GPU显存上存储的情况下, GPU加速所能获得的最高性能.根据支持显卡厂商, 可分为专用GDBMS和通用GDBMS: 前者因为使用CUDA而只能在Nvidia显卡上运行, 包括MapD(OmniSci)[
GDBMS层次架构图[
Layered architecture of GDBMS[
数据库管理系统大都使用SQL或其他高层逻辑API, 而查询编译器作为将SQL转化为数据库内部执行逻辑并向用户返回结果的重要组件, 处在GDBMS的前端, 与查询处理器、查询优化器、存储管理器深度耦合协同工作, 共同为用户提供查询服务.
传统数据库中, SQL编译器的词法分析、大部分编译技术同样适用GDBMS, 所不同的是, GDBMS需要应对的异构计算硬件环境和数据处理模式变化的双重挑战.
● 首先, 查询编译器需要利用CUDA\OpenCL编译工具生成GPU可执行代码, 同时要创新SQL编译模式, 尽可能减少SQL编译的开销, 使整体的性能最优;
● 其次, 传统的“火山模型”不适合GPU计算, GDBMS查询编译器面临着关系数据处理模式的变化, 需要将向量化(vector-wise)、一次一算子(operator-at-a-time)和批量执行(bulk processing model)这3种策略结合起来.
➢ 向量化, 原指将多个关系型数据以向量形式作为一个SIMD(single instruction multiple data)指令的多个操作数来处理的方法, 可以有效提高查询处理吞吐量.在GPU中, 向量化思想可以用GPU的单指令多线程(single instruction multiple thread, 简称SIMT)进一步加大数据处理的吞吐量;
➢ “一次一算子”与“一次一数据”是数据处理的两种模式: 前者就是先将所有数据同时完成第1个算子的处理, 并保存中间结果, 作为下一个算子的输入数据, 直至全部处理完; 而后者是指先让一条数据经过所有算子计算得出结果, 再计算下一条数据的策略, 是基于CPU计算常采用的策略;
➢ 批量执行就是尽可能一批处理更多的数据, 通过提高单次处理数据的数量, 弥补处理频次不高的缺点;
由于GPU由于编程模型和计算架构与CPU不同, GDBMS借鉴了CPU计算中的向量化、“一次一算子”、批量执行这3种策略, 并使之适应GPU大规模并发计算的特点, 我们将在第3.2节详细介绍GDBMS编译器的数据处理模式.
传统数据库系统支持SQL作为查询语言, 在大数据集合上进行ad-hoc查询.数据库系统直到运行时才能知道用户查询的语义信息, 因此, DBMS大多采用解释型的SQL前端, 通过语法解析、语义解析模块将查询query解析为可为查询执行引擎使用的内部任务表示, 即逻辑执行树.尽管传统的基于迭代的查询执行模型(即火山模型或tuple-at-a-time)具有很高的灵活性, 但是由于生成查询计划的过程必然经过多次虚函数的调用, 这种在CPU环境中行之有效的编译方案, 在GPU上执行效率却很低, 不符合GPU大规模线程并发SIMT的编程范式, 使查询编译消耗的时间日益成为高性能数据库查询处理时延的主要部分, 进而使查询编译器处于数据库性能优化的关键路径.
为提高查询编译性能, GDBMS采用解释型查询编译器, 采用JIT即时编译技术, 通过将常用的query子句预编译为可执行代码块, 并在运行时组合调用, 实践中可取得与编译原生代码几乎相同的性能.SQL是非常适合JIT技术的语言, 这方面技术解决方案也非常多.早在1999年, AT & T实验室的Daytona数据管理系统(1999)支持SQL作为子集的高级查询语言(cymbal)[
因此, GDBMS查询编译器采用3种不同的编译模型来解决异构环境下SQL编译难题, 即JIT代码生成(并发原语)、SQL虚拟机和适配器模式.
● 第一, MapD[
● 第二, 在SQL虚拟机模式下[
● 第三, 在适配器模式主要是解决不同厂商GPU接口不兼容的问题.GPUDB编译器直接使用代码生成模块, 将SQL直接编译为CUDA或OpenCL驱动能执行的代码, 以算子为单位进行即时编译[
基于LLVM中间表示的GPU通用编译工具能够很好地隔离硬件多样性, 做到编译各阶段彼此孤立, 给GDBMS在编译的各个阶段进行优化提供了可能.未来, 基于编译自动化工具的研究将极大提升GDBMS系统的性能.
数据库中, 从数据处理模型来看, 可分为3种: 迭代模式(iteration)、批量模式(batching)或二者的混合.传统的DBMS往往采用一次一行的流式迭代模型, 也就是著名的火山模型(volcano model)处理查询请求.时至今日, 研究界和工业界提出了各种改进版的火山模型来规避其缺点, 比如增加每次迭代的数据量、使用SIMD指令一次处理多个数据、推拉结合的数据获取方式等, 目前仍然是数据库中的主流编译技术.批量模式是将每个查询编译为可执行代码, 采用完全物化的方式处理所有数据.批量模式相较火山模型的迭代模式, 在提高局部性、减少运行时解释开销、使用SIMD指令方面有很大优势, 但在实现ad-hoc查询上, 面临灵活度不够、物化存储空间要求过高的问题.因此, 实践中将两者结合的方式更有优势, 比如微批量化查询处理.该类方案使用不同的粒度作为数据处理的单元, 仍然在逻辑上组织成树型结构, 让数据自底向上流动完成查询操作, 兼具迭代模型的灵活性和批处理的高吞吐量的优点.
GDBMS普遍采用向量化一次一算子数据处理模式, 并以此改造查询编译器.
● 首先, 迭代模式并不适合GDBMS, 因为火山模型赖以存在的虚函数机制因为GPU缺乏对应的复杂逻辑控制模块, 在GPU上不可实现或者引起严重的线程分支恶化问题.迭代模型的灵活性是“彼之蜜糖, 我之毒药”, 实际上会损害GPU的性能.GPU的SIMT采用大规模线程并发的方式来提高数据处理的速度, 批量执行可以有效降低生成计划的函数调用次数, 将列数据细粒度分配给GPU线程, 并用循环展开的方式, 可有效减少控制指令总量, 有效降低分支恶化的风险;
● 其次, 列式处理更适合GDBMS.一次一行的处理数据方式在代码上需要做大量的逻辑判断, 而这正是GPU的劣势; 一次一列来处理数据时, 由于每列数据类型一致, 可以用向量化方式处理, 避免了分支判断劣化性能问题, 更适合GPU计算.此外, 有研究[
● 再次, 由于GPU的大规模并行编程模型依赖于对数据的并行处理, 很多算法想在GPU上运行必须适应单指令多线程(SIMT)的编程范式, 所以需要对关系算子进行并行化改造, 使得同一指令同时处理多个关系数据处理需求, 充分利用GPU的并发编程优势.“一次一算子”的数据处理模式就是: 让数据在GPU向量化算子间流动, 每次采用完全物化的策略保存算子输出的中间结果, 作为下一个算子的输入数据;
● 最后, 为了降低物化代价, 通过适当分区切分数据, 可以使GDBMS兼具迭代模式的最大的优点——流水化处理数据的能力[
GDBMS查询处理引擎接受处理查询编译器输出的查询计划树QEP(query execution plan)并执行查询返回结果, 是利用GPU-CPU异构计算处理用户查询请求的核心模块.从功能角度来看, GDBMS查询处理引擎面对的核心问题就是如何利用GPU实现关系代数运算, 即实现选择、投影、连接、聚合基本的关系算子, 同时还需要实现的空间数据(geo-spatial data)处理、OLAP聚合查询等功能复杂的算子, 这是GDBMS查询处理引擎面临的功能挑战.在执行模式上, GPU上执行的代码被称为kernel核函数, 以核函数为基础的查询处理技术(KBE)是GDBMS查询处理引擎的必然选择.但是核函数的并发执行并不完全在程序的控制之下, 如何在GPU高并发SIMT模式下以何种粒度切分关系查询树来最大化查询处理性能, 是GDBMS面临的性能挑战.
面对查询功能挑战和性能挑战, GDBMS采用了分而治之的策略, 在逻辑查询树级别, 用KBE融合或切分的策略, 提升GPU的资源利用率和查询并发度; 而在算子级别, 则采用了设计专门针对GPU优化的算子的方法, 即数据并发原语的方法.
在GPU上实现选择、投影、连接等基本关系代数算子, 是实现GDBMS数据库的基础.传统的数据库系统中, 关系代数多由CPU算法实现, GDBMS必须将关系算子用相应的GPU算法达到相同目的, 而GPU算法在编程模型、并发执行、访存方式、控制逻辑上与CPU存在很大不同, 这是制约GDBMS发展的难点之一.早期的GDBMS使用图形流式编程接口[
GDBMS系统普遍借鉴了GDB[
并发原语功能说明
Data parallel primitives' description
原语 | 功能简介 | 相关文献 |
1. Map映射 | 对每个输入数据运行一个处理函数, 根据条件过滤(predicate or filter), 设置结果位. | [ |
2. Scatter分散 | 按照特定序列散射输入 | [ |
3. Gather聚集 | 按顺序聚集数据 | [ |
4. Reduce归约 | 根据条件归约数据, 得出聚合的结果, 用于去掉不符合条件的数据. | [ |
5. Prefix Sum前缀求和 | 求到指定位置的非零数据之和, 用于计算非冲突的写入位置. | [ |
6. Split划分 | 按划分函数将数据分区, 用于hash表建立、排序等. | [ |
7. Sort排序 | 排序 | [ |
8. Scan扫描 | 已废弃, 类似于Reduce | [ |
9. Product乘积 | 两个元组每元素生成笛卡尔乘积对 | [ |
采用并发原语机制具有如下优点[
基于并发原语的算子实现方法可以在实现中充分利用GPU编程特点进行优化, 如用写入位置不同解决并发冲突、合并访存方法、shared memory优化、用计算隐藏数据传输时延、循环展开等技术, 写出高效的CUDA程序.同时, 并发原语策略也是一种分解合并问题的策略, 采用了分层隔离的设计理念, 未来还可根据GPGPU技术发展对原语进行升级而不影响上层应用.尽管如此, 并发原语策略以增加算子处理步骤为代价, 进而增加了物化中间结果的代价, 存在一定的显存浪费.每个原语按需请求显存资源的方式给全局显存管理提出了挑战, 增大了算子失败的概率.而算子一旦失败, 会造成多个关联算子的级联失败, 造成严重的性能问题.
相较于选择、投影、扫描等基本的关系代数算子, 复杂的关系代数算子(join连接算子、聚集函数)因其逻辑功能复杂, 相对计算量大, 更能发挥GPU大规模并发计算的优势, 因此成为GDBMS优势所在.
Join连接算子对于数据库来说至关重要, 往往成为一个查询计划的性能瓶颈, 是数据库查询优化的重点. Join算子本身的计算量大, 适合利用GPU大规模并发线程技术进行计算.文献[
在CPU-GPU集成架构上, 文献[
实践表明: GDBMS在处理Join算子上比CPU方案效果好得多, 平均可以取得2倍~15倍的加速比.这是由于Join算子是计算制约算子(compute-bounded)决定的, 也是GDBMS主要的优势所在.未来, 如何进一步优化GPU上Join算子算法以及如何调整连接顺序(join-order problem), 仍是GDBMS领域收益最高的研究热点之一.
聚集函数算子是又一个计算负载很高(compute-bounded)的关系代数算子, 适合使用GPU加速.在OLAP分析工作任务中, 切片(slicing)、切块(dicing)、上卷(Roll-up)、向下钻取(drill-down)以及数据立方(cube)函数是OLAP业务中经常用到的算子, 结合sum, average, maximum, minimum, median, count等各类聚集函数, 提供给用户强大的分类汇总复杂信息的能力.借助GPU高并发高性能计算能力加速聚集函数算子, 可以有效提升GDBMS竞争力.
现有研究聚焦到如何用GPU的高并发计算能力和可编程的存储层次结构加速多维聚集算子.文献[
随着移动互联网、物联网、车联网的发展, 基于位置服务越来越普及, 空间数据查询变得越来越重要.为应对大规模空间数据处理的需求, 大数据处理平台开发出了一系列产品, 比如HadoopGIS, SpatialHadoop, SpatialSpark, GeoSpark, LocationSpark等.综述文献[
GDBMS作为新兴数据库分支, 以超过传统GIS系统两到三个数量级的时空数据处理速度和数据可视化交互式查询接口, 引领了时空信息系统的发展潮流.其中, OmniSci(MapD)与Kinetica数据库可以借助GPU优秀的高速并发处理和图形化渲染两大优势的结合, 以接近实时的处理速度进行时空大数据量查询和可视化, 取得了极佳的用户体验.GDBMS原型系统GalacticaDB[
在算法设计层面, 综述文献[
在空间索引方面, 将历史数据构建驻留GPU的空间索引, 能够处理大部分时空数据查询, 是未来发展方向之一.文献[
在GPU空间查询理论方面, 文献[
在查询执行引擎实现方式上, 由于GDBMS普遍采用的CUDA\OpenCL以核函数(kernel)为载体执行协处理器计算, 所以大部分GDBMS使用基于核函数(kernel based execution, 简称KBE)[
在核函数融合方面, 文献[
在核函数切分方面, 文献[
此外, 为了适应未来GPU的性能扩展以及多厂商间编程接口的差异, 使用核函数适配的方式可以赋予GDBMS一定的硬件无关性, 减少系统开发和维护成本.GDBMS系统OmniDB[
基于核函数的查询执行模式适应GPU编程的范式, 是目前GDBMS采用的主流技术.该技术兼顾灵活性和实效性, 通过将算子预编译为不同粒度的核函数, 在运行时根据数据的规模启动不同维度的线程块(warp)执行查询, 同时保留了进一步优化的空间.但是, 基于核函数的执行策略还面临数据传输瓶颈的考验和核函数容易崩溃的问题, 当数据超过一定限度或者中间结果物化代价过大超过显存容量时, 需要引入全局的优化策略避免核函数失败重做的代价.同时, KBE策略普遍没有考虑数据规模的问题, 依赖于在运行时启动多少核函数、分配多大显存的策略, 在实践中, 这样的策略往往过于复杂而采用全列运算来避归, 付出了过大的计算代价.
保证事务的ACID属性, 是支撑OLTP业务的关键.可惜, 众多GDBMS并没有致力于解决并发事务处理的问题.GPUTx[
查询执行器是GDBMS所有计算真正执行的核心引擎, 决定了GDBMS的几乎全部的功能特性, 是真正为用户提供价值的重要组件.数据库技术发展到今天, 很难有一体适用的数据库技术包打天下, 而GDBMS作为后来者, 尽管有很大的应用前景和性能提升潜力, 其功能应该是GDBMS设计者应该关注的重点.GDBMS查询执行引擎核心功能是实现关系代数算子, 目前主流的方法是采用并发数据原语分解关系代数的功能
目前, GDBMS更多地面向OLAP业务, 在查询与报表工具、多维分析工具、统计工具、空间数据处理、数据可视化、人工智能系统等方面努力寻找商业应用场景, 业已在残酷的商业化竞争中占有一席之地.但是我们也注意到, 鲜有研究[
GDBMS查询优化器按功能可分为代价估计系统、查询重写规则、任务调度系统这3大部分, 以查询编译器输出的逻辑执行计划作为输入, 以生成适应CPU-GPU异构计算环境的代价最优的异构查询树为目标, 并指导查询处理引擎执行计划.目前, 大多数的GDBMS或者缺乏统一的优化器, 由查询执行器按规则决定如何执行查询操作; 或者用任务调度来代替优化器的作用, 这就造成了一旦SQL编译完成, 其执行过程就已经固定, 放弃了优化查询的机会.而研究表明, 未经优化的查询计划与最优的查询计划之间的性能可能有数量级上的差距.未来, 优化器将扮演越来越重要的角色, 是GDBMS能否在CPU-GPU异构计算环境下高效执行、发挥全部硬件性能的关键, 也是保障查询安全、提高系统健壮性的核心部件, 值得深究: 首先, 如何建立GDBMS查询处理的代价模型, 是查询优化的核心问题; 其次, 在代价模型指导下, 构建适应GPU查询处理的启发式规则体系对查询树进行等价改写, 是GDBMS优化器的重要问题; 再次, GDBMS查询优化问题在一定程度上可以抽象为算子在何种类型的计算核心(CPU or GPU)上进行处理的问题, 即算子分配问题, 解决了算子分配问题, 就能最大程度地发挥GDBMS整体性能优势; 最后, 如何在真实系统中设计实时高效的查询优化器, 与数据库系统的其他模块协同工作, 是制约GDBMS发展的关键问题.
代价是数据库内核对给定SQL任务执行成本的估计, 在传统数据库中包括CPU执行代价和IO代价两部分, 是逻辑查询计划向物理查询计划转化过程中选择最优物理执行计划的依据.构建GDBMS代价模型, 需要考虑GPU-CPU混合计算和异构存储层次特点, 特别是PCI-E总线瓶颈问题, 使其仍是一个未解决的开放问题.下面介绍构建GDBMS代价模型所面临的挑战以及两种常用的采用代价估计方法——基于代码分析的“白盒方法”和基于学习的“黑盒方法”, 并简要介绍算子选择率的估计方法.
SQL优化过程可以分为逻辑优化和物理优化两个阶段: 在逻辑优化阶段, 优化器根据关系代数等价定律、算子下推启发式规则、子查询重写等规则对逻辑执行计划进行改写, 以得到执行代价更小的物理执行计划; 而在物理优化阶段, 需要为逻辑查询计划中的算子选择特定的算法和数据访问方法, 并选择其中代价最低的一条生成路径作为最终的查询计划.这里非常关键的一点是如何估算查询的代价.传统的以磁盘为中心的数据库在查询执行代价估计方面有很成熟的经验, 一般以磁盘IO和CPU计算的加权平均和作为最终的查询执行代价; 在分布式数据库系统中, 通信代价也是非常重要的度量标准; 在内存数据库中, 由于数据尽量放在内存中, 消除了磁盘IO, 代价估计的重点是内存访问.而在GDBMS中, 查询代价的估计问题变得很不一样.
● 首先, GDBMS的计算代价不仅仅包括CPU计算, 还包括GPU计算, 而GPU计算能力往往是CPU的10倍以上.传统的方法以查询涉及的tuple条目的数量之和来估计其计算代价, 这是基于各CUP的计算能力大致相同的假设; 但在GDBMS中, 必须根据tuple计算的位置(在CUP中还是在GPU中)来分别计算其代价.在GPU中, 计算的代价由于其速率更高所以必须乘以一个经验系数(比如0.1);
● 其次, GDBMS访存代价的估计变得更加复杂.与内存数据库类似, GDBMS将数据尽可能地存放在内存中以消除磁盘IO瓶颈, 甚至有的方案将数据完全放在GPU显存中, 因此, GDBMS中存储层次体系更加复杂——既包括传统的缓存-内存-硬盘三级存储管理, 又包括主机内存与GPU设备内存的异构存储体系管理, 这决定了GDBMS必须设计独有的、能够充分反映GDBMS存储特性的访存代价估计函数;
● 最后, GDBMS的性能瓶颈在于主机内存与GPU显存之间的数据拷贝, 可以类比于分布式数据库中的网络通信开销, 这也是在代价估计中必须考虑的最重要的因素.文献[
以上因素共同作用, 造成了PCIe总线数据传输开销成为了GDBMS代价估计的重点和难点.
目前, GDBMS主要有两种方法获取查询计划的代价: 基于代码分析的“白盒”方法(analytical)[
而基于学习的方法将算子视作黑盒, 通过机器学习的方法, 经过观测算子的过往行为, 估计该算子的执行代价, 并在运行时利用反馈机制修正算子代价.这种方法在一定程度上避免了静态方法的一些问题, 但同样不够完美: 首先, 基于学习的方法需要一定的训练过程, 这在实际生产环境下面临冷启动缺乏基础统计数据的问题, 造成优化器可发挥作用的时效性低, 切换任务后面临新的“训练空窗期”; 其次, 基于学习的方法对算子代价的估计是不精确的——执行计划的代价估计需要考虑的空间过大, 很难在训练阶段穷举所有的情况, 这就造成了对算子代价的估计模型的训练上面临训练样本空间和测试样本空间不重叠、训练样本过少的问题, 模型必然存在精度不高和泛化能力不足的问题; 最后, 现有基于学习的方法没有考虑多显卡、多计算节点分布式的应用场景, 低估了PCIe总线瓶颈的影响.基于学习的cost模型中, 文献[
在现今复杂多变的硬件环境、不断变化升级的异构计算图景(landscape)、分析任务的越来越复杂、与操作系统之间交互的不确定性等原因, 分析型的查询代价估计在实践中很难做到高精确度, 而且基于训练模型再预测的学习型代价估计系统在时效性、准确度、泛化能力上难以满足数据库系统的要求.因此, 将两种方法结合的优化器cost模型在未来会很有前景, 比如用分析模型为学习型cost系统设定初值, 来解决学习型代价系统的冷启动问题.
HyPE[
对于一个特定的关系算子来说, 基数估计(cardinality estimation)就是对算子运行前后数据的变化量评估的技术, 其中, 选择率(selectivity)评估占据了重要的位置.选择率是指满足算子条件的数据数量与数据总量之间的比值.算子选择率的精确估计对中间结果大小估计、算子代价估计、最优join顺序等都有重要影响, 不但直接决定了优化器的准确性, 甚至对GPU内存管理产生直接影响.因此, 选择率的快速而精准的估计对GDBMS来说十分重要.目前最好的解决方案是基于抽样的柱状图方法, 即等宽或等值地抽取数据, 事先建立多区间的统计条形图, 查询时, 结合查询条件及柱状图信息估计算子的选择率.
文献[
针对空间join的选择率估计问题, 文献[
目前, 由于现有选择率估计的精度和性能仍有待提高, 无法根据其对数据的估计结果精确控制用以存储中间结果的缓冲区.但是, 利用深度学习等智能算法计算选择率提升空间很大, 值得进一步探索.比如, 可以利用深度神经网络(DNN)来预测一个算子的选择率, 而GDBMS中由于数据就在GPU上, 可以进行本地训练DNN, 可以预见, 其性能将比传统的CPU算法要高.
查询重写是指优化器对逻辑查询树等价变形, 以达到提高查询效率的目的.在GDBMS中, 传统的查询改写策略同样适用, 当然也有细微的不同之处, 比如对于“下推算子”策略, 由于投影操作在列式存储下可以直接用物理投影解决, 因此不存在下推投影的问题.目前的研究主要致力于改进Join算子的性能和合理消减copy算子来控制数据PCIe总线传输总量上.
文献[
对于OLAP业务中最常用的两个表间的PK-FK Join, CoGaDB则使用文献[
表连接的顺序是查询性能优化的关键.在现有的GDBMS中, 各系统放弃了连接顺序的优化, 采用确定性的查询计划构建方法, 留下了较大的优化空间.文献[
对于查询优化, 可以通过查询重写技术减少copy算子的数量为目标, 来减少在PCIe上来回反复传输的数据量, 从而提升性能.文献[
文献[
此外, 前文提到的KBE核函数执行策略中, 核函数融合技术能够有效减少copy算子的数目; 而核函数切分则会显著增加copy算子数量, 增加本就繁重的PCIe通信成本.综合应用核函数融合和切分技术, 有望进一步提高GDBMS的查询性能.如何有效综合各种优化策略来减少copy算子, 将成为未来GDBMS优化器设计的重中之重.
GDBMS与传统CPU数据库的不同之处在于, 可以利用CPU-GPU异构计算平台并行处理数据.为保证多个计算设备(CPU和GPU)处于“繁忙”状态, 保证系统整体性能[
以响应时间为优化目标下, 可以使用SRT(simple response time简单响应时间最小策略)或WTAR(waiting time-aware response time, 停等时间最少)调度策略[
以系统整体吞吐率[
● Round-robin(RR)策略将算子轮番均分给各个任务队列, 以公平的策略进行调度;
● TBO(thread-based optimization)基于阈值, 给每个计算核心CU一个阈值, 超过阈值之后就不再往该任务队列中分配任务.这样有两点好处: 首先, TBO解决了SRT策略负载不均衡的问题, 避免了因并发算子过多引起的资源耗尽问题; 其次, TBO给了我们选择次优执行计划的能力, 这在一定程度上避免了cost代价估计不准而造成的分配失效的问题;
● PBO利用归一化指数概率函数
RR\TBO\PBO都是在算子层面上对最佳CU选择上的调度策略, 在保证响应时间接近最优的情况下, 以负载均衡的方式提升系统整体的吞吐量.
现有研究表明: 启发式调度策略解决算子分配问题, WTAR策略是最优的方案.但是在更大的范围来看, GDBMS算子分配问题是一个多目标的优化问题, 启发式调度算子策略无法解决关联算子切换CU过程中引起的数据传输代价, 还需要进一步改进以扩大优化视野.
HyPE优化器框架采用可移植分层设计, 在很好地解决了查询性能预测(query performance prediction)和算子分配问题的基础上, 可通过与特定数据库兼容的适配层, 理论上有与任何GDBMS结合的可能性[
HyPE工作流程图
HyPE workflow
● 首先, 在HyPE中, 假设算子跟其处理的数据是一个整体
● 其次, 算子流中的算子依次经过优化器HyPE中, 经由代价估计器(cost estimator, 简称STEMOD)[
HyPE的3个模块内部工作流程如
HyPE架构图[
HyPE architecture[
尽管HyPE优化器基于机器学习的方法估计算子执行代价, 并组合多种启发式规则选择算子的物理实现算法, 但是将查询优化问题等价为在运行时处理算子分配问题的优化策略对GDBMS来说未必是最有效的.文献[
此外, PG-Storm[
传统数据库的经验表明, 未经优化的执行计划和最优执行计划之间的性能差异是巨大的.考虑到异构计算环境特点、代价模型的变化、最优连接顺序问题、算子分配问题、PCIe瓶颈问题、查询规模估计等难题, 异构查询优化问题更加复杂.未来, 人工智能赋能的异构查询优化器将成为研究的热点, 在GDBMS的架构中发挥核心关键作用.
数据库管理系统的任务, 本质上是在一定的存储介质上读写数据.因此, 存储管理器成为其密不可分的关键模块.传统的DBMS与GDBMS在存储管理器上存在以下不同.
● 第一, 从功能上说, 面向磁盘的数据库主要包括内存管理和外存管理两部分; 而对于GDBMS来说, 还增加了GPU显存管理的任务.如何充分发挥异构存储体系的性能优势, 是GDBMS数据管理最核心的问题;
● 第二, 压缩数据能够有效减少需要处理的数据总量, 进而成比例增加GDBMS的性能.如何在GPU异构显存体系下尽可能获得更大的压缩比, 充满了挑战;
● 第三, 索引能够加速以硬盘为中心的数据查询处理, 但是在GDBMS大量物化的全量处理模型中是否还有存在的价值、如何发挥索引长处加速查询处理, 也是GDBMS存储管理需要研究的重要问题.
本节将就GDBMS存储管理面对的挑战、GPU数据压缩技术、GPU数据索引技术以及提升GDBMS处理数据容量的软硬件技术进行深入细致的分析, 希望对未来的GDBMS研究和开发有所启发.
在数据存储模型上, 列式存储在OLAP业务中比行式存储在性能上有明显优势[
● 第一, 列式存储更方便压缩.属性值之间值域有限、高相似度、等位宽等特点可以获得更高效的压缩解压缩算法、获得更高的压缩比, 甚至可以直接用压缩格式进行查询处理.比如采用字典压缩的方式下, 完全可以在压缩形式的数据上进行查询操作而无需引入解压缩的负载;
● 第二, 列式存储减少了需要处理的数据容量.由于分析类查询往往只涉及记录中有限的属性列, 列式存储可以实现“物理投影”, 进而减少不必要的数据获取、处理开销; 其次, 使用尽可能晚的物化操作、通过“位置”等中间信息生成最终结果, 而在查询处理过程中无需进行多余的行式结果构造, 也对性能提升帮助很大, 比如CoGaDB使用tid在GPU和CPU之间传递中间结果;
● 第三, 列式存储更适合GPU处理.由于关系表中一个列内的数据在数据类型上一致, 因此对列中每个元素的处理存在等价性, 设计向量化算法非常适合GPU的大规模并发编程模型.
在此基础上, 一些针对列式存储的优化方法(比如invisible join[
在数据存储位置上, 由于GDBMS需要管理硬盘(包括机械键盘和SSD等)、内存(CPU端)和GPU显存这3层存储结构, 其中, GPU显存包含了超过8种不同类型的存储空间——全局显存(global)、共享显存(shared)、常量显存(constant)、纹理显存(texture)以及各级缓存(cache), GDBMS的存储管理需要考虑的空间变大了.文献[
GDBMS普遍采用内存驻留(memory-resident)的技术, 将数据尽可能放在内存中(甚至放在GPU显存上)来避免磁盘IO瓶颈.文献[
如果只用内存完全不用硬盘, 会极大增加部署GDBMS系统的成本, 限制GDBMS能够处理的数据容量, 并且内存断电后数据丢失的特性, 也给数据安全带来挑战, 在与其他大数据处理系统竞争中也将失去优势.商业的GDBMS普遍采用硬盘存储数据, 在系统加载时, 将数据尽可能部署到内存中, 并利用基于代价的优化器或启发式规则, 尽可能地选择GPU进行查询处理.PG-Storm[
现有研究型GDBMS原型系统, 如CoGaDB, GPUQP, GPUDB, OmniDB等都针对单显卡系统, 鲜有多显卡GDBMS的相关研究, 限制GDBMS容量扩展的一个直观因素是显卡的容量.但是相应的GPU单块显卡的显存容量上的提升不像其计算能力的增长迅速, 比如K80显卡通过集成两块GPU核心已经可以达到24GB的显存, 最新一代Nvidia显卡单块容量普遍还是在12G~16G之间, 虽然最高容量已经达到64GB, 但相应的价格也过于昂贵.商业GDBMS在这方面走在了研究界的前面.将多块GPU合并处理SQL请求, 是扩展数据库处理能力、提高数据库容量的自然解决方案.DB2 BLU[
未来, 随着GPU显存容量和速度的继续提升和分布式技术的引入以及分片分区策略的使用, 相信GDBMS会在数据库容量上不断提升, 逐步拓展应用场景, 前景一片光明.
数据压缩技术历史悠久, 早在关系代数理论创立之初, 人们就致力于将数据压缩用于到数据库管理系统中来.GDBMS普遍采取压缩技术, 以降低数据存储空间, 节约宝贵的内存、显存资源.采用压缩技术存储数据, 还可以降低设备与主机间必须传输的数据容量, 缓解PCIe总线瓶颈问题.但是, 利用压缩技术引入了压缩-解压缩步骤, 增加了系统响应时延, 在实践中必须做出权衡.
在传统的以CPU计算为中心的内存数据库系统环境下, 文献[
适用于GDBMS的压缩算法选择上必须遵守如下原则.
● 第一, 必须是无损压缩算法, 因为数据库业务的要求, 数据如果压缩后有损失, 那么势必影响查询的准确性, 任何以损失业务正确性来提升性能的措施都是不可取的;
● 第二, 一般采用轻量、上下文相关度低的压缩算法, 这样压缩-解压缩过程的负载开销不大, 不会造成严重的性能问题;
● 第三, 解压缩算法应该易于并行化, 方便利用GPU富裕的计算资源.相比于压缩过程, 解压缩流程一般处于查询处理的关键路径上, 对查询速率的影响更加关键;
● 第四, 多种压缩算法可以组合使用, 进一步提高压缩比.而如何选择合适的组合策略, 将会成为将来研究的热点.
在GPU数据库中, Kinetica为用户提供snappy等传统数据块压缩算法, 在查询执行之前先解压再在未压缩数据上执行查询.这样虽然可以支持全部的SQL查询算子, 但是代价也非常巨大.文献[
在GPGPU研究领域, 一些研究通过在现有的异构计算环境软硬件栈的不同位置引入压缩-解压缩缓冲层的方案, 对加速GDBMS也许有借鉴价值.文献[
压缩算法的引入可以有效减少数据的总容积, 同时在轻量级压缩上可以直接查询, 消除了解压缩负载, 进而全面提升GDBMS的性能.在未来的研究中, 适应于GPU处理的易并行、压缩比更大的压缩算法将成为研究的重点.而在应用领域, 轻量级压缩算法的使用会越来越多, 并逐渐寻找大压缩比算法的适用场景.
传统数据库中, 使用B+树等索引结构减少访问数据时磁盘读写的负载.在GDBMS中, 由于索引结构在访存特性上的随机性, 不满足GPU对齐合并访问的特点, 传统的索引结构照搬到GPU异构计算环境下性能不高; 甚至, 由于GDBMS全内存存储和一次一算子全物化的查询处理方式, 不使用索引一样可以达到很高的性能.因此, 在GDBMS中, 如果使用全显存存储数据, 索引可能是多余的模块; 但对于要直接从硬盘存取数据的GDBMS, 索引可在绝大多数情况下有效消除了磁盘IO.比如: PG-Storm由于要从磁盘读取数据, 且无法改变PostgreSQL的存储引擎, 因此选择用BRIN-index减少查询需要传输到GPU的数据量[
使用全内存存储的内存数据库中, 索引查询成为新的性能瓶颈.文献[
GPU索引研究现状
Research status of GPU index
索引类型 | 实现细节 | 性能(每秒次查询, M=百万) |
radix trees[ |
支持点查询和范围查询 | 100M~130M点查询 |
CSS-Tree[ |
针对NLJ优化索引, 使用定长且cache优化的数组 | N/A |
HB-Tree(异构B+树)[ |
动态使用CPU-GPU异构计算资源, 使用负载均衡策略 | 240M |
FAST[ |
根据硬件特性自调整静态二叉树 |
50M CPU |
R-Tree[ |
对多维空间数据进行查询 | N/A |
Hash index[ |
对KV数据存储进行索引 | 160+MOPS(KV get/set) |
GPU LSM[ |
可更新日志结构树, 对写优化 | |
GPU Btree[ |
实现可更新的GPU B-Tree索引 | 1000M点查询 |
基于树的索引使用分层查找的策略, 用尽可能访问少的内部节点而找到真正记录tuple的位置信息, 进而将对整个数据空间的查找范围缩短为最多为树高的多个内部节点的查找.一般分为创建索引、索引搜索、更新索引这3个步骤.在索引查找步骤中, GPU的实现方式重点在单个数组内找到特定值的指向位置, 可安排线程块中每个线程记住内部节点的键, 使用map原语进行比较, 将结果用reduce原语统计, 执行下一步查找.与CPU方案针对Cache块进行优化不同, GPU中shared memory更大, 对树节点大小要求不高, 因而可以在GPU上实现树高更低的索引结构, 加上GPU大规模并发计算能力的贡献, GPU索引查询效率更高.FAST[
以上使用GPU加速索引操作的研究取得了可喜的成果, 但GDBMS普遍将数据存储在内存中, 避免了传统数据库中最影响性能的磁盘IO瓶颈, 因而索引是否是必要的模块有待研究.另一方面, OLAP业务涉及数据量大, 在数据获取上多采用全表扫描、全物化策略执行查询, 这都进一步减少了索引存在的必要性.但是对于OLTP业务, 单个事务的数据获取量少, GPU索引就能发挥应有的作用.未来, GPU加速索引查询的研究方向将围绕可更新索引、加速Join算子、高效空间数据索引这3个方向展开.
异构存储体系下GPU数据的存储管理、压缩和索引是GDBMS存储管理器的核心功能, 一方面要高效利用“小而快”的GPU显存降低查询响应时延提高吞吐量; 另一方面, 又要利用SSD、硬盘存储空间大、可持久存储的特点, 增大GDBMS能够处理数据的总量和高可用性, 同时还要尽可能减少PCIe上的数据迁移.
近10年间, 尤其是CUDA\OpenCL异构统一计算语言的提出, 使得GPU成为数据库可用的强大的可编程的通用协处理器, 并涌现了一大批面向复杂查询的商用GDBMS或研究原型, 这必将深刻改变高性能数据库系统的格局.数据库系统作为数据密集型系统应用软件, 其性能的提升依赖于数据获取能力和计算能力的分别大规模提升: 前者的提升依赖于大容量内存计算、分布式技术、SSD磁盘阵列、NVM[
尽管如此, GPU并不是专为关系型数据处理而开发, 其硬件体系结构还有很多不适应GDBMS发展的地方, 未来需要在如下几个方面进一步研究.
● 对于GDBMS查询编译器, 一方面, 以代码即时生成JIT技术和LLVM编译技术为依托, 进一步压缩SQL的编译时间, 是未来GDBMS查询编译器的研究方向.同时, 如何充分利用不同架构、不同厂商GPU功能特性的同时, 保证SQL编译器的稳定高效, 也是研究热点之一.另一方面, 在“一次一算子”编译模式下, 以更多粒度批量编译查询请求, 为不同规模的查询需求编译出规模适中的查询计划或多个查询计划的组合, 避免因资源限制导致的查询失败, 提高系统的稳定性, 是GDBMS编译器在数据处理模式上的新挑战.同时, 考虑数据所在位置(是否在GPU显存上)和系统运行状态生成“动态”的查询计划, 是未来的研究热点之一.总之, GDBMS查询编译器主要面临压缩异构查询计划的编译时间和根据不同数据查询规模、存储位置而生成高效查询计划两方面的挑战;
● 在GDBMS查询处理器领域, 数据库算法的GPU改造将成为未来主要的研究方向, 尤其是以Join为代表的复杂关系算子的GPU高效实现, 将成为GDBMS性能提升的关键.此外, 通过与查询编译器和查询优化器协同, KBE对核函数的融合与切分的智能化、动态化乃至跨GPU改造, 将成为GDBMS执行引擎的研究热点之一.而在功能上, GDBMS对OLTP业务支撑离不开对事务ACID属性的支持, 这将成为GDBMS亟待突破的难点, 也成为最有潜力的研究方向之一;
● GDBMS查询优化器的研究, 将逐渐从以算子为中心到以查询计划树(QEP)为核心转变.以算子为单位的查询优化在异构查询代价模型、算子选择率、算子分配问题上取得了阶段性成果, 尤其是以机器学习方法估计算子查询代价的HyPE框架的提出, 给GDBMS查询优化器的设计提供了范本.但算子层次的优化缺乏全局视野, 无法保证生成最优的查询计划.未来, 以降低整个查询计划树的异构执行代价为目标的全局优化方案, 是GDBMS查询优化器的研究重点.此外, 多表连接的最佳顺序问题, 仍是GDBMS优化器未解难题之一, 其动态规划解决方案尚没有GPU版本的算法;
● 在GDBMS存储管理器方面, 列式存储、全GPU计算、内存数据驻留带来的超高的计算性能仍是GDBMS的基石, 但固态硬盘SSD的引入十分必要, 在高速度和大容量之间的权衡, 将是GDBMS存储引擎设计的主要问题.未来, 在降低性能前提下提升存储容量, 将成为GDBMS存储引擎未来的研究方向, SSD与GPU数据直连、跨GPU分布式存储等技术非常有潜力.在数据压缩方面, 研究降低解压缩成本为核心的轻量级GPU数据压缩算法, 比更高压缩比的通用GPU压缩算法对GDBMS系统来说更为重要.对于GPU索引的研究, 算法层面将向减少全局数据同步点、面向更新的数据结构、降低PCIe瓶颈方向努力; 而在系统层面, 将继续探索GPU索引技术在GDBMS中的应用场景.
可以预见: 随着GPU性能随摩尔定律而提升和GDBMS四大核心模块技术的发展, GDBMS一定会在技术上越来越成熟、性能优势越来越明显, 从而在根本上改变当下数据处理系统软件的格局.
本文由“支撑人工智能的数据管理与分析技术”专刊特约编辑陈雷教授、王宏志教授、童咏昕教授、高宏教授推荐.
Owens JD, Luebke D, Govindaraju N, Harris M, Krüger J, Lefohn AE, Purcell TJ. A survey of general-Purpose computation on graphics hardware. Computer Graphics Forum, 2010, 26(1): 80-113. [doi: 10.1111/j.1467-8659.2007.01012.x]
doi: 10.1109/MICRO.1999.10004]]]>
http://arxiv.org/abs/1803.00254]]>
https://www.omnisci.com/platform]]>
doi: 10.1145/2897839.2927468]]]>
doi: 10.5441/002/edbt.2014.22]]]>
doi: 10.1007/978-3-642-40683-6_22]]]>
doi: 10.1007/978-3-319-01863-8_25]]]>
Breß S, Beier F, Rauhe H, Sattler KU, Schallehn E, Saake G. Efficient co-processor utilization in database query processing. Information Systems, 2013, 38(8): 1084-1096. [doi: 10.1016/j.is.2013.05.004]
Breß S. The design and implementation of cogadb: A column-oriented GPU-accelerated DBMS. Datenbank-Spektrum, 2014, 14(3): 199-209. [doi: 10.1007/s13222-014-0164-z]
Breß S, Siegmund N, Heimel M, Saecker M, Lauer T, Bellatreche L, Saake G. Load-Aware inter-co-processor parallelism in database query processing. Data Knowledge Engineering, 2014, 93: 60-79. [doi: 10.1016/j.datak.2014.07.003]
Breß S, Saake G. Why it is time for a hype: A hybrid query processing engine for efficient GPU coprocessing in DBMS. Proc. of the VLDB Endowment, 2013, 6(12): 1398-1403. [doi: 10.14778/2536274.2536325]
Breß S, Kocher B, Heimel M, Markl V, Saecker M, Saake G. Ocelot/hype: Optimized data processing on heterogeneous hardware. Proc. of the VLDB Endowment, 2014, 7(13): 1609-1612. [doi: 10.14778/2733004.2733042]
doi: 10.1145/2882903.2882936]]]>
doi: 10.1007/978-3-642-33074-2_5]]]>
doi: 10.1145/1247480.1247606]]]>
He B, Lu M, Yang K, Fang R, Govindaraju NK, Luo Q, Sander PV. Relational query coprocessing on graphics processors. ACM Trans. on Database Systems (TODS), 2009, 34(4): 1-39. [doi: 10.1145/1620585.1620588]
Wang K, Zhang K, Yuan Y, Ma S, Lee R, Ding X, Zhang X. Concurrent analytical query processing with GPUs. Proc. of the VLDB Endowment, 2014, 7(11): 1011-1022. [doi: 10.14778/2732967.2732976]
Yuan Y, Lee R, Zhang X. The yin and yang of processing data warehousing queries on GPU devices. VLDB Journal, 2013, 6(10): 817-828. [doi: 10.14778/2536206.2536210]
doi: 10.1145/3076113.3076119]]]>
doi: 10.1109/icccri.2015.26]]]>
Li J, Tseng HW, Lin C, Papakonstantinou Y, Swanson S. Hippogriffdb: Balancing I/O and GPU bandwidth in big data analytics. VLDB, 2016, 9(14): 1647-1658. [doi: 10.14778/3007328.3007331]
doi: 10.1145/2484838.2484871]]]>
10.1145/3085504.3085521]]]>
Zhang S, He J, He B, Lu M. Omnidb: Towards portable and efficient query processing on parallel CPU/GPU architectures. Proc. of the VLDB Endowment, 2013, 6(12): 1374-1377. [doi: 10.14778/2536274.2536319]
https://hgpu.org/?p=13546]]]>
doi: http://hgpu.org/?p=7180]]]>
doi: 10.1145/1735688.1735706]]]>
He B, Yu JX. High-Throughput transaction executions on graphics processors. Proc. of the VLDB Endowment, 2011, 4(5): 314-325. [doi: 10.14778/1952376.1952381]
doi: 10.1007/978-3-662-45761-0_1]]]>
doi: 10.1145/304182.304242]]]>
Lattner C, Adve V. LLVM: A compilation framework for lifelong program analysis & transformation. In: Proc. of the Int'l Symp. on Code Generation and Optimization: Feedback-Directed and Runtime Optimization. Palo Alto: IEEE Computer Society, 2004. 75. [doi: 10.1109/CGO.2004.1281665]
doi: 10.1145/2854038.2854041]]]>
Nugteren C, Corporaal H. Bones: An automatic skeleton-based c-to-cuda compiler for GPUs. ACM Trans. on Archit. Code Optim. , 2014, 11(4): 1-25. [doi: 10.1145/2665079]
Saecker M, Saecker M, Pirk H, Manegold S, Markl V. Hardware-Oblivious parallelism for in-memory column-stores. Proc. of the VLDB Endowment, 2013, 6(9): 709-720. [doi: 10.14778/2536360.2536370]
Abadi DJ, Madden SR, Hachem N. Column-Stores vs. Row-stores: How different are they really? In: Proc. of the 2008 ACM SIGMOD Int'l Conf. on Management of Data. Vancouver: ACM, 2008. 967-980. [doi: 10.1145/1376616.1376712]
Boncz P. Monet, a next-generation DBMS kernel for query-intensive applications[Ph. D. Thesis]. Amsterdam: Universiteit van Amsterdam, 2002. 1-180. https://dare.uva.nl/search?identifier=aa4f797f-853d-4a75-8383-6d6a60948fac
Boncz PA, Zukowski M, Nes NJ. Monetdb/x100: Hyper-pipelining query execution. In: Proc. of the 2005 CIDR Conf. Asilomar: Very Large Data Base Endowment (VLDB), 2005. 225-237.
Neumann T. Efficiently compiling efficient query plans for modern hardware. Proc. of the VLDB Endowment, 2011, 4(9): 539-550. [doi: 10.14778/2002938.2002940]
doi: 10.1145/2882903.2915224]]]>
Diamos GF, Wu H, Lele A, Wang J. Efficient relational algebra algorithms and data structures for GPU. In: Proc. of the CERS. Georgia, 2012.
doi: 10.1145/1376616.1376670]]]>
doi: 10.1145/1362622.1362684]]]>
https://arxiv.org/abs/1709.02520]]>
doi: 10.1145/1142473.1142511]]]>
doi: 10.1109/ICDE.2013.6544839]]]>
https://hgpu.org/?p=13546]]>
Yabuta M, Nguyen A, Kato S, Edahiro M, Kawashima H. Relational joins on GPUs: A closer look. IEEE Trans. on Parallel and Distributed Systems, 2017, 28(9): 2663-2673. [doi: 10.1109/TPDS.2017.2677451]
He J, Lu M, He B. Revisiting co-processing for hash joins on the coupled CPU-GPU architecture. VLDB, 2013, 6(10): 889-900. [doi: 10.14778/2536206.2536216]
D. Xiangwu, C. Jinxin. Optimizing parallel join of column-stores on heterogeneous computing platforms. In: Proc. of the 2016 IEEE Information Technology, Networking, Electronic and Automation Control Conf. 2016. 621-625. [doi: 10.1109/ITNEC.2016.7560435]
Zhou G. Parallel cube computation on modern CPUs and GPUs. Journal of Supercomputing, 2012, 61(3): 394-417. [doi: 10.1007/s11227-011-0575-7]
doi: 10.1145/1871940.1871958]]]>
Zhang Y, Zhang YS, Chen H, Wang S. GPU adaptive hybrid OLAP query processing model. Ruan Jian Xue Bao/Journal of Software, 2016, 27(4): 1246-1265(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4828.htm [doi: 10.13328/j.cnki.jos.004828]
张宇, 张延松, 陈红, 王珊. 一种适应GPU的混合OLAP查询处理模型. 软件学报, 2016, 27(4): 1246-1265. http://www.jos.org.cn/1000-9825/4828.htm [doi: 10.13328/j.cnki.jos.004828]
doi: 10.5555/1946370.1946396]]]>
doi: 10.1109/TELFOR.2018.8611821]]]>
k query processing on massively parallel hardware. In: Proc. of the 2018 Int'l Conf. on Management of Data. Houston: ACM, 2018. 1557-1570. [doi: 10.1145/3183713.3183735]]]>
Pandey V, Kipf A, Neumann T, Kemper A. How good are modern spatial analytics systems? Proc. of the Vldb Endowment, 2018, 11(11): 1661-1673. [doi: 10.14778/3236187.3236213]
Güting RH. Geo-Relational Algebra: A Model and Query Language for Geometric Database Systems. Berlin Heidelberg: Springer, 1988.
doi: 10.1145/3006386.3006390]]]>
Jacox EH, Samet H. Spatial join techniques. ACM Trans. on Database Systems, 2007, 32(1): 7. [doi: 10.1145/1206049.1206056]
doi: 10.1145/1206049.1206056]]]>
Zacharatou ET, Doraiswamy H, Ailamaki A, Silva CT, Freiref J. GPU rasterization for real-time spatial aggregation over arbitrary polygons. Proc. of the VLDB Endowment, 2017, 11(3): 352-365. [doi: 10.14778/3157794.3157803]
doi: 10.1109/ICDE.2016.7498315]]]>
10.1145/3221269.3221296]]]>
doi: 10.1145/3318464.3389774]]]>
doi: 10.1109/MICRO.2012.19]]]>
Menon P, Mowry TC, Pavlo A. Relaxed operator fusion for in-memory databases: Making compilation, vectorization, and prefetching work together at last. Proc. of the VLDB Endowment, 2017, 11(1): 1-13. [doi: 10.14778/3151113.3151114]
Zhong J, He B. Kernelet: High-throughput gpu kernel executions with dynamic slicing and scheduling. IEEE Trans. on Parallel & Distributed Systems, 2014, 25(6): 1522-1532. [doi: 10.1109/TPDS.2013.257]
Gregg C, Hazelwood K. Where is the data? Why you cannot debate CPU vs. GPU performance without the answer. In: Proc. of the IEEE Int'l Symp. on PERFORMANCE Analysis of Systems and Software. Austin: IEEE, 2011. 134-144. [doi: 10.1109/ISPASS.2011.5762730]
Breß S, Geist I, Schallehn E, Mory M, Saake G. A framework for cost based optimization of hybrid CPU/GPU query plans in database systems. Control & Cybernetics, 2012, 41(4): 715-742.
doi: 10.1109/IPDPS.2009.5161068]]]>
doi: 10.1109/icde.2012.64]]]>
doi: 10.1145/2723372.2749438]]]>
doi: 10.1109/ICDE.2017.236]]]>
https://dare.uva.nl/personal/pure/en/publications/accelerating-foreignkey-joins-usingasymmetric-memory-channels(bd88a910-2b4f-4e7d-9743-656b56c63d41).html]]>
Leis V, Gubichev A, Mirchev A, Boncz P, Kemper A, Neumann T. How good are query optimizers, really? Proc. of the VLDB Endowment, 2015, 9(3): 204-215. [doi: 10.14778/2850583.2850594]
Han WS, Kwak W, Lee J, Lohman GM, Markl V. Parallelizing query optimization. Proc. of the VLDB Endowment, 2008, 1(1): 188-200. [doi: 10.14778/1453856.1453882]
http://ceur-ws.org/Vol-1594/paper16.pdf]]>
https://pdfs.semanticscholar.org/7cd1/50c5e35a65854572159d14b6dab42da0df0e.pdf]]>
Karnagel T, Habich D, Lehner W. Local vs. global optimization: Operator placement strategies in heterogeneous environments. In: Proc. of the Workshops of the EDBT/ICDT 2015 Joint Conf. 2015. 48-55.
https://heterodb.github.io/pg-strom/]]>
https://www.brytlyt.com/]]>
doi: 10.1109/CLUSTER.2017.42]]]>
Bergman S, Brokhman T, Cohen T, Silberstein M. Spin: Seamless operating system integration of peer-to-peer dma between SSDS and GPUs. ACM Trans. on Comput. Syst. , 2019, 36(2): 1-26. [doi: 10.1145/3309987]
doi: 10.1145/2882903.2903735]]]>
https://sqream.com/]]>
doi: 10.1109/HPCA.2019.00063]]]>
Mittal S, Vetter JS. A survey of architectural approaches for data compression in cache and main memory systems. IEEE Trans. on Parallel & Distributed Systems, 2016, 27(5): 1524-1536. [doi: 10.1109/TPDS.2015.2435788]
doi: 10.1145/3226595.3226638]]]>
doi: 10.1145/1142473.1142548]]]>
Fang W, He B, Luo Q. Database compression on graphics processors. Proc. of the VLDB Endowment, 2010, 3(1): 670-680. [doi: 10.14778/1920841.1920927]
doi: 10.1145/3365109.3368789]]]>
doi: 10.1145/2872887.2750399]]]>
doi: 10.1145/2872887.2750417]]]>
http://www.irisa.fr/alf/downloads/ADA/Sathish_LinkCompressionGPGPU_PACT12.pdf]]>
Zhang K, Wang K, Yuan Y, Guo L, Lee R, Zhang X. Mega-KV: A case for GPUs to maximize the throughput of in-memory key-value stores. Proc. of the VLDB Endowment, 2015, 8(11): 1226-1237. [doi: 10.14778/2809974.2809984]
doi: 10.1109/HPCCSmartCity-DSS.2016.0212]]]>
doi: 10.1145/2882903.2882918]]]>
doi: 10.1145/1807167.1807206]]]>
doi: 10.1109/IPDPS.2018.00053]]]>
doi: 10.1145/3293883.3295706]]]>
Pan W, Li ZH, Du HT, Zhou CC, Su J. State-of-the-Art survey of transaction processing in non-volatile memory environments. Ruan Jian Xue Bao/Journal of Software, 2017, 28(1): 59-83(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5141.htm [doi: 10.13328/j.cnki.j0s.005141]
潘巍, 李战怀, 杜洪涛, 周陈超, 苏静. 新型非易失存储环境下事务型数据管理技术研究. 软件学报, 2017, 28(1): 59-83. http://www.jos.org.cn/1000-9825/5141.htm [doi: 10.13328/j.cnki.j0s.005141]