《GPU 数据库核心技术综述》论文学习

文章目录

• 一、背景
• 二、GPU 数据库分类与层次
• • 1.商用型C-GDBMS 中分为3类
  • 2.研究型R-GDBMS
• 三、查询编译器
• • 1.GDBMS编译模型
  • 2.GPU数据处理模型
• 四、查询处理器
• • 1.GPU关系代数和并发原语
  • 2.复杂关系算子
  • 3.空间数据查询
  • 4.KBE查询执行引擎
  • 5.GPU事务处理
• 五、查询优化器
• • 1.代价模型
  • 2.查询重写
  • 3.异构计算任务队列
  • 4.真实GDBMS系统中的优化器
• 六、存储管理
• • 1.GDBMS数据存储体系
  • 2.GPU数据压缩
  • 3.GPU索引技术

一、背景

1.GPU性能极高

• GPU 与 CPU 具有不同的体系结构和处理模式,将更多的片上空间用于计算单元,控制单元和缓存单元相对很少,使得单块 GPU 上拥有数千个并发计算核心。因此,在同样的主频下,GPU 能够取得更高的并发计算能力,也使 GPU 具有满足大数据处理需求的巨大潜能。

• 在时空数据 OLAP 分析任务和结果的可视化展示方面,几十个 GPU 的 GPU 数据库可以取得近千台普通 CPU 服务的数据库处理能力,而其响应时间甚至更短。

2.GPU数据库功能上日趋完善

• 基于商务智能 BI 的可视化交互式图表查询界面支持标准 SQL 查询语言，往往只要几分钟就可以完成以往数天乃至一周的工作。

• GoAI(GPU open analytics initiative,GPU 开放分析计划)产业联盟和 GPU 数据帧(GPU data frame,GDF)构建了数据库库和人工智能应用程序之间数据交换标准,使数据科学家可以停留在 GPU 上的同时探索数据,训练机器学习算法并构建人工智能应用程序。

GPU数据库领域的核心研究内容：

• 查询编译器(query compilation)：将用户的 SQL 语言描述的查询需求转化为 CPU- GPU 异构计算环境下的查询计划;

• 查询处理器(query processing)：应用 GPU 并行计算技术实现关系型数据处理的各种算子,挖掘 GPU 峰值计算能力;

• 查询优化器(query optimizer)：用机器学习乃至人工智能技术,结合 CPU-GPU 异构计算环境和查询计划特点以及数据分布特征,生成最优(次优)的异构查询计划;

• 存储管理器(memory management)：需要在异构数据存储管理、数据存储格式、数据压缩、数据访问等问题上做出决策

二、GPU 数据库分类与层次

GDBMS(GPU database management system or GPU accelerated database management system，使用 GPU 进行或加速数据增删改查的数据库管理系统)。

分为研究型R-GDBMS: for research和商用型C-GDBMS: for commercial

1.商用型C-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

以一台普通服务器配备多个 GPU 显卡就能取得分布式大数据系统一个集群的处理能力.超大吞吐量、超低时延以及更低的成本,让 GDBMS 在 OLAP 业务上优势明显

2.研究型R-GDBMS

研究原型 GDBMS 将重点放在了全 GPU 计算上，DB的数据数据可以在 GPU 显存上存储的情况下,GPU 加速所能获得的最高性能.根据支持显卡厂商,可分为专用 GDBMS （因为使用 CUDA 而只能在
Nvidia 显卡上运行）和通用 GDBMS（后者使用 OpenCL,在 Nvidia 卡和 AMD 卡上都可以运行）。

三、查询编译器

• 首先,查询编译器需要利用 CUDAOpenCL 编译工具生成 GPU 可执行代码,同时要创新 SQL 编译模式,尽可能减少 SQL 编译的开销,使整体的性能最优;

• 其次,传统的“火山模型”不适合 GPU 计算,GDBMS 查询编译器面临着关系数据处理模式的变化,需要将向量化(vector-wise)、一次一算子(operator-at-a-time)和批量执行(bulk processing model)这 3 种策略结合起来
（1）向量化，原指将多个关系型数据以向量形式作为一个 SIMD(single instruction multiple data)指令的多个操作数来处理的方法,可以有效提高查询处理吞吐量.
（2）在 GPU 中,向量化思想可以用 GPU的单指令多线程(single instruction multiple thread,简称 SIMT)进一步加大数据处理的吞吐量;
（3）“一次一算子”与“一次一数据”是数据处理的两种模式:
前者就是先将所有数据同时完成第 1 个算子的处理,并保存中间结果,作为下一个算子的输入数据,直至全部处理完;
而后者是指先让一条数据经过所有算子计算得出结果,再计算下一条数据的策略,是基于 CPU 计算常采用的策略;
（4）批量执行就是尽可能一批处理更多的数据,通过提高单次处理数据的数量,弥补处理频次不高的缺点;

GDBMS 借鉴了 CPU 计算中的向量化、 “一次一算子”、批量执行这 3 种策略,并使之适应 GPU 大规模并发计算的特点

1.GDBMS编译模型

DBMS 大多采用解释型的 SQL 前端

• 通过语法解析、语义解析模块将查询query解析为，可为查询执行引擎使用的内部任务表示，即逻辑执行树

GDBMS 查询编译器采用 3 种不同的编译模型来解决异构环境下 SQL 编译难题,即 JIT 代码生成(并发原语)、 SQL 虚拟机和适配器模式

• 基于底层虚拟机(LLVM)编译器框架来即时编译 SQL 代码（预编译并发原语），是目前 GDBMS 系统编译器实现的主流方法。
  （1）该方法使用基于 LLVM[32]的 nvcc 编译器，将关系算子分为更小的原语 primitives，并把原语预编译为架构无关汇编代码 PTX，在运行时，由编译器只需完成 SQL 语言到算子的编译工作；
  （2）查询执行器在优化器指导之下完成算子到并发原语的映射。
• 虚拟机模式
  优点：将 SQL 编译为操作码(opcode)作为中间表示,将整个 DB 系统视为一个虚拟机,Opcode 操作码对应的算子被预编译为cudabin 可执行代码,直接发送到 GPU 端执行（CUDA 编译器由google提出）。
  缺点：虚拟机模式放弃了SQL 优化的机会,无法提供查询重写、基于代价的优化;
• 适配器模式
  GPUDB 编译器直接使用代码生成模块,将 SQL 直接编译为 CUDA 或 OpenCL 驱动能执行的代码，以算子为单位进行即时编译，适配器模式在运行时的编译负载会比较高。

2.GPU数据处理模型

,从数据处理模型来看,可分为 3 种:

• 迭代模式(iteration)
  改进版的火山模型，如增加每次迭代的数据量、使用 SIMD 指令一次处理多个数据、推拉结合的数据获取方式等

• 批量模式(batching)
  将每个查询编译为可执行代码，采用完全物化的方式处理所有数据。
  但在实现 ad-hoc 查询上,面临灵活度不够、物化存储空间要求过高的问题。

• 二者的混合
  比如微批量化查询处理.该类方案使用不同的粒度作为数据处理的单元,仍然在逻辑上组织成树型结构,让数据自底向上流动完成查询操作,兼具迭代模型的灵活性和批处理的高吞吐量的优点

GDBMS 普遍采用向量化一次一算子数据处理模式,并以此改造查询编译器，原因如下：

• 首先,迭代模式并不适合 GDBMS,因为火山模型赖以存在的虚函数机制因为 GPU 缺乏对应的复杂逻辑控制模块,在 GPU 上不可实现或者引起严重的线程分支恶化问题。
  GPU应采取的操作是：
  将列数据细粒度分配给 GPU 线程,并用循环展开的方式,可有效减少控制指令总量,有效降低分支恶化的风险

• 列式处理更适合 GDBMS
  一次一列来处理数据时,由于每列数据类型一致,可以用向量化方式处理,避免了分支判断劣化性能问题；
  GDBMS 系统普遍采用列式处理模型[30],比如 Ocelot[13],CoGaDB[10]等

• 由于 GPU 的大规模并行编程模型依赖于对数据的并行处理,很多算法想在 GPU 上运行必须适应单指令多线程(SIMT)的编程范式,所以需要对关系算子进行并行化改造
  “一次一算子”的数据处理模式就是:让数据在 GPU向量化算子间流动，每次采用完全物化的策略保存算子输出的中间结果，作为下一个算子的输入数据

• 为了降低物化代价，通过适当分区切分数据，采用数据流水化处理(pipelining data processing),有效提高数据处理并行度

四、查询处理器

GDBMS 查询处理引擎，接受处理查询编译器输出的查询计划树 QEP(query execution plan)并执行查询返回结果。

GDBMS 查询处理引擎面对的核心问题是：

• 功能上，如何利用 GPU 实现关系代数运算,即实现选择、投影、连接、聚合基本的关系算子,同时还需要实现的空间数据(geo-spatial data)处理、 OLAP 聚合查询等功能复杂的算子
• 在执行模式上，GPU 上执行的代码被称为 kernel 核函数，以核函数为基础的查询处理技术(KBE)是GDBMS 查询处理引擎的必然选择
  （1）如何在 GPU 高并发SIMT 模式下以何种粒度切分关系查询树来最大化查询处理性能，是 GDBMS 面临的性能挑战
  （2）GDBMS采用的策略：
  在逻辑查询树级别，用 KBE 融合或切分的策略，提升 GPU 的资源利用率和查询并发度;
  在算子级别，则采用了设计专门针对 GPU 优化的算子的方法，即数据并发原语的方法

1.GPU关系代数和并发原语

在 GPU 上实现选择、投影、连接等基本关系代数算子,是实现 GDBMS 数据库的基础。

• .CUDA/OpenCL 赋予了程序员使用 CC++代码控制 GPU 大规模并行环境的能力,简化了GDBMS 开发的难度,促进了GDBMS 的繁荣。
• GDBMS使用分层设计，将关系代数功能拆解为算子层(operator)和原语层(primitives)两部分，设计了一系列的适应 GPU 计算的数据并行原语(primitives)。
  如下所示是大部分的 GPU 并发原语
  
• eg：比如:scatter 原语[43]通过分区散射操作,在每个 load-store 周期内处理一个分区的散射操作,增加了数据访问聚合读写；
  很多算子映射成原语的单个或多个组合,能够充分利用 GPU 高并发计算能力.通过以上原语的排列组合,大部分简单的关系代数算子可以进行有效拆解.比如选择算子可以用 filter 原语实现,同时,filter 原语是由 map 原语、 prefix sum 原语和 scatter 原语实现的。

2.复杂关系算子

Join 算子

• :GDBMS 在处理 Join 算子上比 CPU 方案效果好得多，这是由于 Join 算子是计算制约算子(compute-bounded)决定的
• 如何进一步优化GPU 上 Join 算子算法以及如何调整连接顺序(join-order problem)，仍是GDBMS 领域收益最高的研究热点之一

OLAP 聚集函数算子

• 聚集函数算子是又一个计算负载很高(compute-bounded)的关系代数算子,适合使用 GPU 加速。
• 在 OLAP 分析工作任务中,切片(slicing)、切块(dicing)、上卷(Roll-up)、向下钻取(drill-down)以及数据立方(cube)函数是OLAP 业务中经常用到的算子，结合
  sum,average,maximum,minimum,median,count 等各类聚集函数，提供给用户

3.空间数据查询

在空间索引方面，将历史数据构建驻留GPU 的空间索引，能够处理大部分时空数据查询，是未来发展方向之一。

4.KBE查询执行引擎

在查询执行引擎实现方式上，由于 GDBMS 普遍采用的 CUDAOpenCL 以核函数(kernel)为载体执行协处理器计算。

• 所以大部分 GDBMS 使用基于核函数(kernel based execution,简称 KBE)[40]的查询执行引擎

• 一种自然的实现 KBE 的方法就是将每个关系算子以一个 kernel 函数执行,大部分 GDBMS 基于此实现自己的查询处理引擎,比如 CoGaDB,MapD 等。

• 在此基础之上,已有研究在核函数的层次上进行合并融合或细致切分两种策略:
  （1）针对数据量大或计算复杂的任务,通过将多个核函数融合(kernel fusion)到一起,共同完成查询处理;
  （2）而对于相对简单的任务,则进一步切分核函数(mini-kernel),做到精细化管理,以合理利用 GPU 资源

5.GPU事务处理 五、查询优化器 1.代价模型 2.查询重写 3.异构计算任务队列 4.真实GDBMS系统中的优化器 六、存储管理 1.GDBMS数据存储体系 2.GPU数据压缩 3.GPU索引技术