26uuu新地址 Geno: 基于代价的异构交融查询优化器
21世纪以来, 跟着互联网、物联网和出动规划技巧的发展, 东说念主们概况获取的数据鸿沟爆炸式增长26uuu新地址, 多半新式应用应时而生, 对数据的实时刻析需求越来越高. 摩尔定律增长变得逐渐, 传统以CPU为中心的规划技巧靠近“能耗墙”、“内存墙”的限制, 只是通过增多CPU主频来得到性能栽培的方式走到了绝顶. 高性能处理器技巧投入多核期间, 多核CPU在一定进度上缓解了规划性能栽培的瓶颈. 同期, 通用图形处理器(general purpose computing on graphics processing units, GPGPU)、现场可编程门阵列(field programmable gate array, FPGA)等专用处理器因为其具备大鸿沟并行规划的身手, 在处理海量数据方面具有后天不良的上风. 这使得“通用处理器+异构加快器”在很猛进度上成为当代规划的发展趋势, 这些发展所产生的影响是处事器硬件朝着高度异构的标的滚动. 因此, 高性能处理器和新式加快器的岀现, 使得传统的数据管理与分析系统从单CPU架构起初向异构、羼杂处理架构滚动[1, 2].
数据库是高效组织、存储、管理数据的软件, 数据库技巧是规划机信息系统和应用系统的蹙迫赞成. 跟着各样化应用的膨胀与潜入, 数据库管理的数据鸿沟越来越大, 查询处理愈加复杂刚毅, 而且实时性要求越来越高. 对于数据库系统而言, 硬件技巧是载体复古, 决定了数据存取和查询等处感性能的物理极限; 软件的见地是优化算法与数据结构的假想以提高软件与硬件的契合度, 最大化硬件使用着力, 同期掩饰或减少硬件固有的限制[3, 4]. 因此, 数据库系统要应答海量异构数据带来的巨大挑战, 必须充分哄骗多核CPU以及GPU/FPGA等异构硬件的高速并行处理身手, 将一部分CPU任务卸载到异构硬件上去实行, 比如规划密集型数据库操作, 如数据的SCAN、谓词过滤、多半数据排序、大表JOIN、聚拢等, 以及I/O密集型操作如压缩/解压缩、加密/解密等, 以充分阐扬各样规划资源的上风.
然则, 处理器架构的差异奏凯影响到数据库的职责着力, 数据库系统需要凭据不休发展的处理器架构作念出相应的优化. 凭据Stonebraker等东说念主[5]在2014年VLDB上发表的论文证据, 传统数据库的事务处理机制无法有用哄骗数十到上百个核处理身手. 新式异构规划架构也改变了数据库系统查询优化的代价模子, 查询优化假想与硬件特征的关联性越来越高, 所依赖的要素也愈加复杂, 查询优化的难度进一步增多. 现存数据库查询优化在面对新式异构硬件时存在的挑战主要有:
① 怎么哄骗异构硬件高效地完毕干系代数运算和丰富的干系算子.
② 查询优化所依赖的旅途代价规划奏凯影响到所遴荐查询谈论的优劣: 领先是现存的代价模子贫乏异构硬件身手的评估方法和异构算子旅途代价的规划方法, 部分现存基准代价与执行环境中硬件处理身手不匹配, 比如I/O基准代价莫得沟通SSD和HDD执行身手的差异, 基于元组的CPU代价固定为0.01; 其次, 统计信息不成实时准确捕捉数据散播的特征, 比如莫得表的数据页在缓存中的数目等统计信息, 莫得充分沟通内存大小对缓存射中率的影响, 而统计信息的准确度对代价估算模子中行数估算和代价估算至关蹙迫.
③ 怎么生成适合异构规划环境的代价最优的异构交融查询树, 指挥查询处理引擎的实行, 完毕各样规划资源的协同优化.
支捏异构交融的查询优化器是数据库系统在异构规划环境下高效实行、阐扬全部硬件性能的重要, 亦然保险查询高效、安全、提高系统健壮性的中枢部件. 本文提倡一种面向CPU/GPU/FPGA异构规划交融基于代价的查询优化器, 不错无邪编削并优化使用各样资源. 主要的孝顺是: 发现凭据系统环境硬件执行身手解救代价参数可显赫栽培查询谈论的准确性, 并提倡一种异构资源代价规划方法和校准器用; 通过对GPU/FPGA等异构硬件身手估算及对数据库系统硬件执行身手的校准, 开拓异构规划环境下查询处理的代价模子; 完毕了支捏遴荐、投影、诱骗、团聚的GPU算子和FPGA算子, 完毕了GPU算子交融及活水线假想、FPGA算子活水线假想; 通过基于代价的评估管理算子分拨和编削问题, 生成异构协同的实行谈论, 完毕异构规划资源的协同优化, 以充分阐扬各别构资源的上风.
本文第1节先容征询配景和关联职责. 第2节先容Geo的假想, 重心陈述异构资源代价校准的方法、异构规划环境下查询处理代价模子的开拓、基于代价评估的异构交融实行谈论生成、异构算子交融和活水线假想. 第3节通过实验对异构资源代价校准的方法和器用进行考证, 假想异构算子对比实验分析考证GPU/ FPGA的上风, 在TPC-H测试集上进行Geno与CPU数据库PostgreSQL、GPU数据库Hetero-DB的对比测试, 并对测试赶走加以分析. 临了, 在第4节进行回来.
1 关联职责查询优化是数据库系统最蹙迫的任务之一, 数据库的性能相称依赖于查询优化器. 查询优化表面的出身已有近50年, 学术界和工业界照旧形成了多个比较完善的查询优化框架, 但是围绕查询优化的中枢难题恒久没变, 即怎么哄骗有限的系统资源, 尽可能地为查询遴荐“好”的实行谈论, 从而镌汰查询实行资本. 影响查询实行资本的要素包括干系的数目、通讯资本、资源以及对大型散播式数据集的走访等, 查询优化被觉得是NP难题[6].
从处理器发展的角度看, 跟着硬件平台的变化, 数据库查询优化技巧资格了以I/O代价为中心、以Cache数据局部性为中心、以多核并行处感性能为中心和以异构规划性能为中心的不同发展阶段. 不同发展阶段的查询优化见地具有显赫的差异, 从减少面向磁盘的I/O数目, 到假想cache-conscious的数据结构和走访方法, 再到提高算法的并行处感性能[7]. 传统数据库的优化器是基于统计信息进行表诱骗策画, 跟着新式处理器技巧的发展, 处理器技巧从多核走向众核, 在中枢集成度、线程数目、缓存结构、访存技巧等方面与传统的x86多核处理器架构有很大的不同, 查询优化的见地也转向SIMD优化技巧[8]、面向GPU、FPGA等新式处理器和加快器的查询优化技巧[9-11], 查询优化假想与硬件特征的依赖性越来越高. 在新硬件环境下, 数据库异构查询优化问题愈加复杂, 除了传统优化器的基数算计问题和诱骗法例问题等传统征询难题外, 还有异构规划环境带来的代价模子变化、异构存储层、PCIe瓶颈等问题. 因此, 怎么对这些异构系统的数据处理进行协同优化是一个极具挑战的征扣问题.
(1) 代价估算和诱骗算法
基于代价的查询优化是基于采样信息和代价模子进行表诱骗策画, 对查询语句对应的待选实行旅途进行代价估算, 从待选旅途中遴荐代价最低的实行旅途作为最终的实行谈论. 传统模子的代价估算是将一语气页面索求的资本、就地页面索求的资本、处理元组的CPU资本和实行操作的资本等多个要素结合起来估算的. 这些要素与查询所影响的数据基数强关联, 而且每个因子的权重必须解救. 在新式硬件环境下, 领先是要进行新式硬件的身手校准和异构算子的代价估算; 其次是传统代价模子无法描摹新硬件环境下各样操作的走访特征, 举例最主要的性能瓶颈照旧从磁盘上法例和就地I/O比例过渡到了NVM的读写比例; 再次, 异构规划架构下更深的缓存层级和非一致的缓存读写代价也进一步使得新式硬件环境下的走访代价估算复杂化、动态化.因此, 怎么确保新式硬件环境下代价模子的有用性和正确性, 是极具挑战性的征询职责.
Van Aken等东说念主[12]提倡了一个通过东说念主工智能的方法细则数据库系统的最好设立参数系统OtterTune, 对不同的硬件、不同的负载细则更好的参数设立组合. 但主如果解救数据库系统已有的参数数值, 莫得沟通异构硬件. 同期, 该系统要实时地监控数据库运功绩态, 某些参数的解救需要重启数据库才能见效.
快速并准确地算计多维度的遴荐率, 是当代干系查询优化器的蹙迫组成部分. 该鸿沟的最新技巧是多维直方图, 它提供了考究的算计质地, 但构造复杂且难以重视. 内核密度算计(kernel density estimation, KDE)是一个有后劲的替代方法, 征询证据: KDE比直方图敛迹到基础散播更快, 且KDE模子易于构建和使用. 但现存的基于KDE的遴荐率算计器质地还需要提高. Heimel等东说念主[13]提倡了一个在数值上快速并准确地算计多维度遴荐率的KDE模子, 能大大改善遴荐率估算, 何况该KDE模子能动态凭据查询职责量变化而自动解救, 进而开发了GPU加快的自解救KDE模子, 使估算器能不休适合数据库和查询职责量变化. 同期, 为了快速估算遴荐率, 将遴荐率估算推送到GPU以提高性能. 但是优化的KDE模子只波及表数据的遴荐率, 莫得波及表扫描和诱骗方式等优化以及估算, GPU作用限于遴荐率估算, 伪善行数据库操作符.
已处理查询的得手, 很猛进度上取决于查询优化器所实施的搜索方法. 针对海量数据查询时经典的启发式方法(举例蚁群和遗传算法)无法覆盖通盘搜索空间, 并可能导致堕入局部最小值的问题, 文献[14]接纳量子启发式蚁群算法(QIACO)作为概率算法的一种羼杂战术, 以尽快找到使总实行时间最短的最好诱骗法例. 量子规划的各样化身手不错覆盖较大的查询空间, 这有助于遴荐最好旅途, 从而提高敛迹速率, 幸免堕入局部最优情状.
(2) 查询优化框架
Paul等东说念主[15]提倡了一种新颖的活水线查询实行引擎GPL, 指出现存的将GPU作为查询协处理器存在严重的资源着力不及, 给出了一个分析模子, 该模子不错细则参数的最好设立, 以提高基于GPU查询协同处理的资源哄骗率. 实行引擎GPL通过细则CPU和GPU间高效地通讯的最好参数设立, 减少内存停顿, 进而提高GPU算子的性能.
Breβ[16]开发了一个异构查询处理引擎HyPE, 结合CPU和GPU的优点进行基于代价的优化, 膨胀了传统的查询优化器, 支捏羼杂查询谈论的生成, 以最大限制地提高系统性能. HyPE接纳学习方法估算算子的实行时间, 为算子分拨最合适的处理器, 由3个部分组成: 代价算计器(cost estimator)、算法遴荐器(device- algorithm selector)、异构查询优化器(hybrid query optimizer). HyPE优化器框架接纳可移植分层假想, 可通过与特定数据库兼容的适配层, 表面上不错与任何GDBMS结合. 但是HyPE只在算子层级上决策算子在哪个规划中枢上实行, 每个算子作为一个沉寂的个体, 接纳贪念战术为算子分拨处理器, 接纳局部优化战术, 贫乏全局视线容易堕入局部最优解, 还可能形成无用要的数据传输代价. 同期, HyPE无法对多规划节点的散播式规划环境进行优化.
Breβ等东说念主[17]提倡一个负载感知的并行协同处理器CoGaDB, 其中枢是一个决策模子, 哄骗优化启发式算法WTAR(waiting-time-aware response time), 凭据多种协同器和CPU的职责负载及响适时间, 将数据库操作任务分拨给各个异构设备, 得到最好的规划资源哄骗率和总体性能. CoGaDB的决策模子必须结合第三方优化器HyPE才能生成查询谈论, 而且CoGaDB的协处理器摈弃在GPU, 不支捏FPGA.
Zhang等东说念主[18]完毕了一个基于异构规划和多种存储资源的下一代数据库系统Hetero-DB, 它的GPU查询引擎通过两个重要组件确保高资源哄骗率和系统性能: 一个查询编削器, 在GPU上保捏最好的并发级别和职责负载; 一个数据交换机制, 最大限制地提高GPU设备内存的有用哄骗率. Hetero-DB是从GPU内存空间的哄骗率等资源角度编削查询在CPU照旧GPU上实行.
Owaida等东说念主[19]完毕了一个CPU-FPGA羼杂架构的数据库系统Centaur, 该系统提供一种与现存数据库架构兼容的使用FPGA加快SQL的管理有谈论, 为进一步探索基于FPGA的数据处理提供了可能性. Centaur通过监视FPGA上的功课, 将查询实行谈论中的算子动态编削到可用FPGA资源上, 多个算子在FPGA上活水线化实行, 这些算子活水线也不错跨CPU和FPGA羼杂运行. 同期, Centaur十足兼容干系引擎, 比如与流行的列存储数据库MonetDB无缝集成. Philippos等东说念主[2]作念了一个FPGA加快在线分析处理的窥探, 指出其靠近的两个主要挑战. (1) 主机内存和FPGA间数据吞吐量受限于PCIe总线带宽, 现时每个PCIe邻接的速率约为6.5 GB/s, 而当代Intel处理器的读取速率突出80 GB/s, 写入速率达到38 GB/s; (2) FPGA加快效果受限于主机内存和FPGA间数据传输时延. FPGA加快器分为两类: 一类是框架, 包括Centaur、DoppioDB等专用框架和MaxCompiler通用框架; 另一类是算子加快, 包括用FPGA加快排序、遴荐、诱骗、字符串匹配、过滤等算子操作.
(3) 基于学习的查询优化
基于代价的查询优化存在着基数算计问题和诱骗法例问题等传统征询难题. 最近几年, 跟着东说念主工智能技巧的发展, AI4DB成为热点征询标的, 数据库社区尝试哄骗机器学习模子来立异查询优化器. 基于学习的查询优化(AI based optimization, ABO)汇集实行谈论的特征信息, 借助机器学习模子得到教学信息, 进而对实行谈论进行调优, 得到最优的实行谈论. ABO不错凭据历史数据学习, 并凭据系统近况在运行时进行动态解救.
文献[20]提倡了一种查询优化的端到端学习方法Neo (neural optimizer), 给定一组查询重写端正确保语义的正确性, Neo学会作念对于聚拢法例、运算符和索引遴荐的决定. Neo使用强化学习优化了这些决策, 凭据用户的数据库实例, 并凭据执行的查询蔓延进行决策. Neo的假想迷糊了传统查询优化器的主要组件(基数算计、代价模子和谈论搜索算法)之间的界限. Neo莫得明确算计基数算计及代价模子, 它将这两个功能组合为一个价值麇集、一个神经麇集, 接纳部分查询谈论并预测完成此部分谈论可能产生的最好预期运行时间; 通过价值麇集的指挥, Neo对查询实行浮浅的搜索策画空间作念决定; 跟着Neo发现更好的查询谈论, Neo的价值麇集也随之改善, 将搜索重心放在更好的谈论上. 但是, Neo仍然有许多蹙迫的局限性: 领先, Neo需要一个传统的查询优化器来教学它的学习过程; 其次, Neo需要提前具备查询重写端正学问以保证正确性; 第三, Neo查询优化器的特征是从一种特定的数据库中学习到的, 因此, Neo不成从一种数据库泛化到另一种数据库, 不具备通用性.
针对代价和基数算计的挑战, 李国良等东说念主[21]提倡了一个基于树结构模子的端到端学习代价估算框架, 不错同期进行代价和基数的估算. 他们提倡了一种有用的特征索乞降编码技巧, 在特征索求时, 同期沟通查询和物理实行, 将查询操作、元数据、查询谓词和一些样本编码到模子中. 他们把这些特征镶嵌到树状结构模子中, 哄骗树状结构算计资本和基数. 模子包含了镶嵌层、示意层和算计层, 概况有用地学习到每个子有谈论的示意, 何况这些示意用于资本和基数算计, 不错无缝取代传统的资本算计. 模子基于老师数据进行老师, 将更新的参数存储在模子中, 并估算新查询谈论的资本和基数.
总而言之, 天然连年来基于专用加快器对数据库进行加快的征询和应用取得了一定赶走, 但还存在较大的局限和不及: 领先, 现存职责大都是使用单一异构算力针对特定场景的加快方法, 鲜有交融CPU-GPU- FPGA的加快征询, 也莫得在通用数据库系统的得手应用; 其次, 针对异构规划环境下数据库查询优化问题的征询较少, 尚未出现存效管理新式硬件环境下数据库查询优化的管理有谈论. 已有的数据库加快征询都是接纳蛮力或端正方式将定制SQL查询卸载到异构加快硬件上, 毁灭了对异构算力的优化合营. 本文探讨了中兴通讯新一代数据库系统在新式硬件方朝上的征询实践, 给出了开拓支捏新式硬件异构算力的代价模子的方法和器用, 并提倡了支捏新式硬件异构交融的查询优化器, 不错生成最优(次优)的异构交融实行谈论, 充分阐扬各样规划资源的上风.
2 Geno的假想SQL是介于干系演算和干系代数之间的一种结构化查询讲话, 它只蔼然赶走而不蔼然过程, 即它只告诉数据库“想要什么”, 但是莫得告诉数据库“怎么获取”这个赶走, 这个“怎么获取”的过程是由数据库的“大脑”查询优化器来决定的. 在数据库系统中, 一个查询无为会有许多种获取赶走的方法, 每一种获取的方法被称为一个实行谈论, 优化器产生的实行谈论的优劣, 奏凯决定数据库的性能. 因此, 查询优化在数据库系统中具有相称蹙迫的作用.
无为数据库系统处理一条查询语句包含查询知道、查询优化和查询实行这3个阶段.
● 查询知道对查询语句作词法分析、语法分析和语义分析, 生成一个由干系算子组成的逻辑实行谈论.
● 查询优化对逻辑实行谈论进行优化, 最毕生成物理实行谈论. 传统的查询优化分为基于端正的优化(rule based optimization, RBO)和基于代价的优化(cost based optimization, CBO)两种: CBO领先对逻辑实行谈论进行逻辑上的等价变换, 陈设出等价的实行谈论; 然后, 查询优化器凭据统计信息和代价模子为每个实行谈论规齐整个“代价”(这里的统计信息描摹了数据的散播情况, 是由数据库统计模块自动产生的; 这里的代价无为是指实行谈论的实行时间).
● 临了, 查询优化器会在稠密等价谈论中遴荐一个“代价最小”的实行旅途作为最终的实行谈论, 传给查询实行模块.
在包含GPU/FPGA等异构加快器的规划环境中, 为了充分阐扬异构硬件的身手对数据库加快, 咱们提倡一种基于代价的异构交融查询优化器Geno, 其主要模块和处理历程如图 1所示. Geno凭据查询波及的数据集大小、具体操作和硬件资源身手, 规划各样可能旅途(包括异构实行旅途)的代价, 遴荐代价最低的旅途, 生成相应的谈论节点及实行代码. 查询实行阶段依据生成的异构交融查询实行旅途, 在各个谈论节点实行指定的动态实行代码.
图 1 Geno主要模块和处理历程
1) 与传统基于代价的优化器比较, Geno新增的模块有:
(1) Geno器用. 包括异构硬件资源感知、异构硬件规划身手评估、异构旅途代价评估这3个部分. 异构硬件资源感知模块自适合感知和加载GPU, FPGA异构资源, 使数据库集成异构硬件规划身手. 异构硬件规划身手的评估完成不同异构硬件处理身手的比较折算, 凭据硬件身手解救代价规划因子.异构旅途代价评估完成不同异构硬件扫描旅途、诱骗旅途、团聚旅途的代价评估.
(2) Geno算子. 包括GPU算子、FPGA算子: GPU算子集成GpuScan、GpuJoin、GpuAgg等GPU支捏的基本操作算子; FPGA算子集成FpgaScan、FpgaJoin、FpgaAgg等FPGA支捏的基本操作算子.
(3) GPU规划旅途. 为查询波及的每个基表生成GPUScan扫描旅途, 并调用异构旅途代价评估模块, 规划其启动代价和总代价; 生成基表诱骗旅途, 基于动态策画算法或遗传算法, 遍历基表之间各样可能的诱骗法例及诱骗方式, 经过异构旅途代价评估, 遴荐代价最低的诱骗旅途, 生成GpuJoin诱骗旅途以及该旅途的启动代价和总代价. 在Non-SPJ优化阶段, 同期生成GpuAgg团聚旅途, 得到其启动代价、总代价.
(4) FPGA规划旅途. 为查询波及的每个基表生成FpgaScan扫描旅途, 雷同基于动态策画算法或遗传算法, 生成FpgaJoin诱骗旅途, 在Non-SPJ优化阶段, 生成FpgaAgg团聚旅途, 并调用异构旅途代价评估模块, 规划FPGA各个旅途的启动代价和总代价, 供优化器进行旅途遴荐.
(5) 异构PipeLine旅途生成. 为了减少主机与异构硬件之间的数据传输, 凭据异构硬件性情, 接纳算子交融、活水线假想等技巧将多个GPU规划旅途进行交融, 组合成一个新的组划算子, 支捏GpuScan+ GpuJoin+GpuAgg, GpuScan+GpuJoin, GpuScan+GpuAgg; FPGA接纳动态设立SQL活水线, 支捏FpgaScan+FpgaJoin+FpgaAgg.
2) Geno处理历程:
(1) 运行异构规划身手评估器用, 规划并保存异构硬件的身手规划因子, 供Geno规划代价时使用. 数据库系统启动阶段, 调用异构硬件感知器用, 检测汇集可用的异构硬件信息, 并进走时行化.
(2) SQL语句经过数据库词法、语法、语义分析青年景查询树, 传递给Geno进行查询策画.
(3) Geno领先对SQL查询进行基于端正的逻辑优化, 哄骗干系代数中一些等价的逻辑变换端正对查询进行等价变换, 如子邻接和子查询栽培、外诱骗排斥、抒发式预处理、诱骗条目和过滤条目下推, 生成新的等价料理条目等.
(4) 在逻辑优化生成新的查询树后, Geno不绝进行物理优化, 开拓物理实行旅途. Geno默许使用动态策画算法来生成物理实行旅途, 当查询波及的基表数目大于设定的阈值时, Geno遴荐遗传算法来生成旅途, 这么不错保证在有限的时间内生成较优的查询谈论.
(5) 旅途生成第1阶段, 生成基表扫描旅途及代价, Geno凭据汇集的硬件信息, 调用CPU规划旅途、GPU规划旅途、FPGA规划旅途模块中扫描旅途生成接口, 为每个基表生成不同的扫描旅途, 包括SeqScan、IndexScan、GpuScan、FpgaScan, 凭据CPU旅途代价评估模子和异构规划旅途代价评估模子规划每条旅途的启动代价和总代价, Geno为每个基表保存候选的扫描旅途列表(总代价最优旅途、启动代价最优旅途、最优的排序旅途).
(6) 旅途生成第2阶段, 生成多表诱骗的旅途及代价, Geno接纳动态策画算法或遗传算法, 遍历不同的诱骗法例、诱骗方式, 调用CPU规划旅途、GPU规划旅途、FPGA规划旅途模块中诱骗旅途生成接口, 为诱骗表生成相应的诱骗旅途及代价. 比较各个旅途的代价, 淘汰较差的诱骗旅途, 适度谈论树鸿沟. 雷同地, Geno为每个诱骗表保存候选的实行旅途列表.
(7) 旅途生成第3阶段进行Non-SPJ优化, 调用CPU规划旅途、GPU规划旅途、FPGA规划旅途模块中团聚旅途生成接口, 生成Agg旅途及代价, 保存候选的旅途列表.
(8) 在候选旅途生成后, Geno为了提高异构硬件实行着力, 减少主机与异构硬件之间无用要的数据传输, 调用异构PipeLine旅途生成模块, 接纳算子交融、活水线技巧, 生成PipeLine旅途及代价.
临了, Geno凭据以上生成的通盘候选旅途, 遴荐一条最优的查询旅途生成羼杂查询谈论树. 为提高算子的实行着力, Geno哄骗JIT技巧, 为每个谈论节点生成专用实行代码, 将代码扁平化(inline), 奏凯调用对应的函数, 减少多半无用要的跳转和代码分支实行, 从而精减多半的实行请示. 查询实行器凭据最终的查询谈论树, 实行谈论节点指定的操作, 通过多种异构硬件算子数据传输方法, 在多个规划资源上对数据进行读取、处理、存储等操作, 给用户复返最终查询赶走.
2.1 异构加快算子的假想 2.1.1 GPU算子假想与常见的GPU数据库系统[22]一样, Geno以核函数为载体实行GPU规划, 接纳批处理、核函数交融等技巧来假想GPU关联算子, 充分挖掘GPU的并行处感性能. Geno将不同的SQL算子假想为GPU kernel, 供SQL实行引擎调用. Geno支捏GpuScan、GpuJoin (Hash, NestLoop)、GpuGroupBy、GpuAgg (MIN, MAX, SUM, COUNT)、GpuSortBy等算子. GPU kernel分3层假想: 第1层通用函数库层, 包括基本算术运算符、位操作运算符、数据类型转换、算术函数、三角函数、日历时间函数、文本函数、梯度乞降、hash等; 第2层为数据存取方法层, 包括行存、列存、数据块等; 第3层为干系运算符层, 包括遴荐、投影、排序、分组团聚和诱骗操作等.
数据库系统哄骗GPU加快的性能瓶颈在于主机内存与GPU显存之间的数据拷贝, 不错类比于散播式数据库中的麇集通讯支出, 这亦然在代价算计中必须沟通的最蹙迫的要素. 文献[23]等征询指出: PCIe总线瓶颈是通盘GPU算法不成暴戾的性能支出, 亦然GDBMS的性能瓶颈地方. 文献[24]对开源Alenka系统运行TPC-H基准测试并进行耀眼的性能分析, 发现唯有5%用在了GPU规划上, 大部分支出都用在了数据传输上.其次, 在多GPU环境的系统中, 由于多GPU频频分享PCIe总线, 因此多GPU下性能并不呈现浮浅的线性增长, 而且与之关联的管理资本和决策空间也相应变大. 因此, 如安在多GPU环境下优化查询性能仍然是一个难题. 以上要素共同作用形成了PCIe总线数据传输支出成为代价估算的重心和难点. Geno为减少主机和GPU间数据传输, 接纳了算子交融和活水线假想, 相应地, Geno在NO-SPJ优化后, 增多异构PipeLine旅途生成花式.
1) GPU算子交融假想
针对数据量大或者规划复杂的任务, Geno通过分析核函数之间对数据的依赖性, 将承载处理疏通数据的算子核函数合并交融在一都, 共同完成数据处理. 这么不但镌汰了数据在CPU和GPU之间的传输支出, 还不错减少全体核函数的数目, 简化查询处理的优化空间. Geno支捏Scan+Join+Agg、Scan+Join、Scan+Agg交融.以SELECT cat, count(*), avg(ax) FROM t0 NATURAL JOIN t1 WHERE aid < bid GROUP BY cat为例, 展示Scan+Join+Groupby交融算子假想.
如图 2所示, GpuScan算子扫描过滤t0上的数据, 不经过主机奏凯传输给GpuJoin算子; GpuJoin算子在t0, t1上运行JOIN操作, 也不经过主机奏凯传输给GpuAgg算子, GpuAgg算子通过GPU设备上的cat列运行GROUP BY操作后才传输给主机.
图 2 GPU算子交融
2) GPU算子活水线假想
有征询提倡对核函数进一步进行切分, 通过更细巧的粒度管理和活水线化编削, 提高GPU资源哄骗率.但是核函数切分是以更无为的核函数编削为代价, 数据传输代价和PCIe总线瓶颈的影响更大. Geno是从数据实行粒度上细巧化核函数的实行, 哄骗核函数规划和数据I/O瓜代使用不同硬件的特色, 通过切分核函数和核函数之间数据的活水化, 有用提高数据并发度.
如图 3所示, 数据以chunk块为单元进行编削和处理.
图 3 GPU算子活水线
输入干系表(举例T0和T1), 把T0表数据切分为chunk块t0i作为GpuScan Kernel的输入数据, 经过核函数扫描过滤后, 产生数据块$ t{0'_i} $并作为GpuJoin Kernel的输入数据, GpuJoin核函数同期加载内表T1的数据进行诱骗, 产生诱骗干捆绑果集$ {t''_i} $, 输入到GpuPreAgg Kernel进行分组操作, 产生GPU最终输出赶走t. 如果内表T1突出GPU内存无法加载, 则接纳Grace Hash join算法, 在诱骗前先对T0/T1表进行Hash分片, 并将分片文献缓存到磁盘, 然后加载成对的T0/T1表分片文献, 实行GpuJoin进行Hash诱骗.
2.1.2 FPGA算子假想FPGA是一种新式异构规划硬件, 存在出错和失效的可能. 对于FPGA的使用, 无法像CPU一样透明无感知, 数据库引擎需要凭据FPGA的情状来作念出相应的管理和任务编削. 提倡一种FPGA即处事(FPGA as service)架构, 将FPGA作为从数据库引擎中沉寂出来, 将FPGA的规划身手视作一种处事提供给SQL规划引擎, 从而镌汰SQL模块间的耦合性和全体的可用性. FPGA即处事提供FPGA硬件自身的运功绩态信息、FPGA入网算资源的忙绿舒坦情状、FPGA中算子的规划身手信息等信息.
为了使用FPGA加快SQL处理, 需要将SQL算子下推到FPGA中进行处理. 因此, 需要假想SQL算子在FPGA实行的逻辑. 具体来说, 是要将SQL算子假想为kernel, 以供SQL引擎调用. Geno支捏fpgaScan、fpgaFilter、fpgaJoin (Hash, Merge)、fpgaSortBy、fpgaGroupBy、fpgaAgg (MIN, MAX, SUM, COUNT) 等常用SQL算子.
FPGA kernel的假想自底朝上分为3层: 最底层是通用基本算子层, 提供最基本的算法功能模块以供表层组合调用, 包括基本的压缩解压算法、排序算法、基本运算符、bloomfilter和hash等; 中间层是SQL算子层, 哄骗通用基本算子层提供的基本功能组合出相应的SQL算子, 包括遴荐、投影、分类、分组团聚和诱骗操作等, 举例使用压缩解压算法、bloomfilter等算法模块组合出带有解压数据和过滤功能的扫描算子, 使用hash和基本运算符模块组合出哈希诱骗算子等; 最表层是软件接口层, 向下对中间层的SQL算子进行抽象, 朝上为用户提供友好易用的API调用接口. 通盘这个词假想自底朝表层层抽象又相对沉寂, 具有较好的膨胀性和易用性.
1) FPGA算子动态可设立的SQL活水线假想
一般来说, 查询优化器会将某一个或者几个SQL算子的处理下推到FPGA中. 在面对复杂查询时, 数据在FPGA和主机间的无为传输难以幸免, 从而会大大增多了处理蔓延和I/O的代价, 减轻了FPGA加快的效果.为排斥无用要的数据传递, 咱们提倡了一种动态可设立的SQL活水线假想.
该假想的念念路是: 在FPGA硬件中设立一条SQL节点的活水线, 活水线上的节点使用与否不错通过参数动态地适度, 从而达到适配大部分查询何况排斥与内存间无用要的数据交换的目的(如图 4所示).
图 4 FPGA活水线
2.2 异构规划代价模子
代价(cost)是数据库内查对给定SQL任求实行资本的算计, 是一个相对值, 以法例读取一个页面的时间(seq_page_cost)为基准单元1, 其他代价都是相对这个基准单元来规划. 一条SQL语句的代价估算主要从I/O代价、CPU规划两方面沟通. 领先, 凭据统计信息和查询条目, 估算出本次查询需要进行的I/O数目以及要获取的元组个数; 然后, 凭据代价参数规划出I/O代价和CPU代价; 临了, 玄虚沟通I/O代价和CPU代价即可得到总代价. 代价估算依赖表和索引占据的磁盘块数、表的元组数、合适条目的元组数、各个属性出现的次数等统计信息, 还需要用到法例读取一个页面的代价(seq_page_cost)、就地读写页面的代价(random_page_ cost)、CPU处理一条元组的代价(cpu_tuple_cost)、CPU处理一条索引元组的代价(cpu_index_tuple_cost)、CPU处理一个运算符的代价(cpu_operate_cost)、一个查询中通盘表的可用缓冲大小(effective_cache_size)等代价参数. 因为表的扫描方式、表的诱骗法例和表的诱骗方式不同, 疏通的SQL语句有不同的实行旅途, 对应的代价也不同, 旅途的总代价是启动代价和实行代价两者之和. 查询优化器即是从稠密可选的旅途中遴荐一条总代价最低的旅途.
传统数据库的代价模子莫得沟通系统硬件如HDD/SSD的执行身手差异, 奏凯将random_page_cost等代价参数固定, 也莫得充分沟通内存大小对缓存射中率的影响, 因此主机上I/O代价和CPU规划代价需要校准.在异构硬件环境下, 规划代价不单是包括CPU规划代价, 还包括GPU、FPGA等异构硬件规划代价. 而对异构硬件的支捏, 无为接纳教学值进行固定设立. 在不同的硬件运行环境中, 固定设立与硬件执行推崇出的身手比较差距比较大, 因此异构规划代价相对CPU规划代价必须凭据执行硬件身手进行校准. 同期, 因为异构硬件的加入, 还带来了主机内存与异构硬件设备内存间的数据传输, 这亦然在代价估算时必须沟通的蹙迫要素.玄虚以上要素, Geno提倡了异构硬件环境下的代价估算模子, 如公式(1)所示.
$ TotalCost=newCost_{I/O}+newCost_{compute}+Cost_{trans}$ (1)即, 一个谈论的总代价由凭据执行存储介质校准后的CPU、GPU、FPGA等I/O代价、凭据硬件身手校准后的CPU、GPU、FPGA等规划代价、主机内存与GPU、FPGA等异构硬件设备内存间的传输代价这3个部分组成.代价规划是一个自底朝上的过程: 领先规划扫描算子的代价, 然后凭据扫描算子的代价规划诱骗算子的代价以及Non-SPJ算子的代价.
2.2.1 异构规划代价校准● 主机I/O代价校准: seq_page_cost是法例读取一个页面的代价. seq_page_cost作为通盘这个词代价估算体系的基准代价, 是计算其他操作代价的基准. 校准接纳通用的磁盘I/O测试器用fio, 测试法例扫描数据的时间作为代价的基准时间T0, 其他操作耗时以这个为基准进行换算. random_page_cost是就地读取一个页面的代价, 校准方法和seq_page_cost疏通.
● 主机规划代价校准: 包括cpu_operator_cost、cpu_tuple_cost、cpu_index_tuple_cost这3个代价参数的校准.
➢ cpu_operator_cost是CPU实行一个运算符或函数调用的代价, 该值为抒发式规划的代价评估提供蹙迫参考. 由于浮点数处理是计算硬件性能的蹙迫方针, 是以遴荐浮点数相乘作为测试方法. 校准方法接纳在函数内轮回调用浮点数相乘, 将单次运算符实行时间除以基准时间T0, 得出运算符代价.
➢ cpu_tuple_cost是从主存中的页面读取并知道一个元组的代价, 与元组中字段数目和类型关联. 为了测试类型覆盖的全面性, 校准时创建包含int, string, float等常见类型的字段, 批量生成测试数据, 测试总知道时间, 用总时间除以元组数, 得出单个元组知道耗时, 单个元组知道耗时再除以基准时间T0, 得出元组处理代价.
➢ cpu_index_tuple_cost是从主存中的页面读取并知道一个索引元组的代价. 除了表上有构建索引, 校准念念路和方法与cpu_tuple_cost疏通.
● GPU规划代价校准: 主要校准gpu_ratio参数. gpu_ratio示意GPU与CPU运算代价折算比, 用来估算在GPU上实行雷同操作的代价, 为遴荐GPU照旧CPU实行操作提供蹙迫参考. 此处雷同遴荐浮点向量相乘作为测试次序. 校准接纳A, B, C这3个浮点向量, 用A与B对应位置元素相乘存入C对应位置, 分离在GPU上和CPU上进行浮点运算, 用GPU耗时除以CPU耗时, 得出GPU与CPU运算身手的折算比.
● FPGA规划代价校准: 主要校准fpga_ratio参数. fpga_ratio示意FPGA与CPU运算代价折算比, 用来估算在FPGA上实行雷同操作的代价, 为遴荐FPGA照旧CPU实行操作提供蹙迫参考. 同GPU规划代价校准, 遴荐A, B, C浮点数向量相乘作为测试次序, 分离在FPGA上和CPU上进行浮点运算, 用FPGA耗时除以CPU耗时, 得出FPGA与CPU运算身手的折算比.
2.2.2 索引扫描I/O代价校准索引扫描会就地走访在磁盘上数据页, 如果需要走访的数据页照旧存在于缓冲池中, 则不需要从磁盘上读取; 反之, 则会从磁盘上读取数据页, 产生磁盘I/O的代价. 索引扫描的性能在很猛进度上取决于执行需要走访的物理磁盘的页面数. 对于存在于缓冲池中的数据页, 可能由于其他并发走访的会话需要加载其他数据页, 而把之前的数据页替换出去, 导致下一次走访需要从物理磁盘上从头加载该数据页, 并发走访数越大, 对缓冲池资源的争抢也越热烈. 另外, 缓冲池越大, 系统可容纳的数据页越多, 数据页被替换出去的可能性也越低. 是以, 并发的肯求数蔼然冲池的大小成为决定物理页被走访次数的重要要素. 主流数据库中, 现存规划物理页走访次数的方法接纳了Mackert等东说念主[25]开拓的模子.
1) 当T≤b时, 物理页走访次数为min(2TNs/(2T+Ns), T).
2) 当T > b且Ns≤2Tb/(2T-b)时, 物理页走访次数为2TNs/(2T+Ns).
3) 当T > b且Ns > 2Tb/(2T-b)时, 物理页走访次数为b+(Ns-2Tb/(2T-b))*(T-b)/T.
其中, T为现时表中页面数目, N为表中元组数目, s为料理条目产生的遴荐率, b为现时表可用缓存大小.
b的规划公式为b=effective_cache_size*T/total_pages, 其中, effective_cache_size是指在一个查询中通盘表的可用缓冲大小, 假定均匀散播, 那么就不错推定现时表的可用缓存大小; total_pages是指现时查询中波及的通盘表的总页面数. 对于一个细则的查询来说, T和total_pages都是细则值, effective_cache_size的值的准确性决定了b值的准确性. 更进一局面, 在上述模子中, T, N, s都是细则值, b值的准确性决定了物理页走访次数的准确性. 因此, effective_cache_size值的准确性决定了物理页走访次数的准确性. 主流数据库中, effective_cache_ size使用固定值524 288 (4 GB). 澄莹, 这不是一个准确的值, 莫得体现缓冲区大小、并发查询数对估算物理页走访次数的影响, 导致估算的物理页走访次数也不可能准确.
Geno通过参数校准器用, 在实验基础上回来提倡公式(2).
$ effective\_cache\_size=a0+a1^{*}X+a2^{*}Y+a3^{*}X^{2}+a4^{*}X^{*}Y+a5^{*}Y^{2} $ (2)其中, X, Y分离代表buffer pool大小、并发查询数, 其余参数均为总计(a0=4150, a1=0.001735, a2=-89.42, a3= -8.039e-05, a4=0.004912, a5=0.8386). 该公式描摹了effective_cache_size和并发查询数、buffer pool大小之间的干系, 在查询肯求处理过程中, 输入buffer pool大小、并发查询数得到effective_cache_size最好值, 这个值进一步栽培了索引扫描代价估算的准确性.
2.2.3 异构规划传输代价估算● gpu_trans_cost: 主机和GPU之间传输数据的代价. 因GPU并行规划身手刚毅, 规划代价小, 因此传输代价对GPU总代价影响巨大. 校准时, 将chunk块从CPU传到GPU, 用总传输耗时除以基准时间T0得出GPU传输代价.
● fpga_trans_cost: 主机和FPGA之间传输数据的代价. 和校准GPU和主机间的传输代价相似, 校准时, 将chunk块从CPU传到FPGA, 用总传输耗时除以基准时间T0, 得出FPGA传输代价.
2.3 异构交融查询优化凭据异构规划代价模子, Geno哄骗校准后代价和异构硬件间传输代价进行旅途的代价估算, 从稠密可选的旅途中遴荐一条总代价最低的旅途, 并凭据语句执行实行时间动态更新统计信息, 并用于后续自动重优化.
2.3.1 异构规划旅途代价模子Geno在传统CBO优化器基础上增多了GPU, FPGA上运行的Scan, Join, Agg等旅途的代价估算, 用于优化器筛选最优查询旅途. 异构旅途代价估算关联GPU参数表参见表 1.
表 1 异构旅途代价估算关联参数表
GPU的异构规划旅途代价新增了主机与异构硬件之间的数据传输代价、核函数动态编译加载代价、GPU启动展期间价、GPU并行规划代价等. GPU启动展期间价是GPU处理首个chunk的代价S_delay=Cr/Nc, Nc代表GPU处理数据的chunk总和.
1) GPUScan旅途代价规划
(1) 启动代价Cs是核函数动态编译加载代价K与启动展期间价S_delay之和.
(2) 实行代价Cr包括表数据加载I/O代价、过滤条目抒发式规划代价、主机与GPU间数据传输代价这3部分, 如公式(3)所示.
$ C_{r}=S_{\rm{8K}}*N_{p}+E_{r}*R*N_{t}+T*(D_{s}+D_{s}*R_{e}) $ (3)其中, S8K代表法例读取一个8K页面的代价, Np代表基表占用磁盘总页数, Er代表抒发式一次实行代价, R代表GPU与CPU规划身手折算比, Nt代表GPU扫描的纪录条数, T代表主机与GPU之间传输一个chunk块的代价, Ds代表主机发送到GPU的chunk数, Re代表抒发式条目的遴荐率.
GPU支捏通过DMA传输奏凯从NVMeSSD盘上加载表数据, 幸免从主机内存拷贝数据至GPU设备内存, 量入计出总线带宽并显赫镌汰传输代价. 以DMA方式扫描表的实行代价解救为Cr=S8K*Np+Er*R*Nt+T*Ds*Re.
2) GPUHash诱骗旅途代价规划
(1) Hash诱骗旅途的启动代价Cs为核函数动态编译加载代价、外在扫描旅途启动代价、内表数据预加载代价、遴荐投影等抒发式的启动代价、GPU启动展期间价之和. 内表数据预加载代价为通盘内表数据扫描代价加上数据传输代价以及通盘内表构建HASH表的代价, 如公式(4)所示.
$ C_{s}=K+O\_{s}+I\_load+E\_{s}+S\_delay $ (4)其中, K为核函数动态编译加载代价; Os为外在扫描旅途启动代价; Es为抒发式启动代价; S_delay为启动展期间价; I_load为内表数据预加载代价, 规划式为$ \sum\limits_{k = 1}^{num\_inner} {({I_{ck}} + {I_{dk}} + {I_{hk}})} $, Ick为内表K扫描的总代价, Idk为内表K的数据传输代价, Ihk为内表K开拓Hash表的代价.
(2) Hash诱骗旅途实行代价Cr包括外在扫描旅途的实行代价、外在和诱骗表数据传输代价、Hash诱骗操作代价、诱骗表投影抒发式的GPU规划代价, 如公式(5)所示.
$ C_{r}=O_{r}+T*(O_{c}+J_{c})+C_{h}+E_{r}*R*J_{t} $ (5)其中, Or代表外在扫描旅途的运行代价; Oc代表外在数据大小(chunk数); Jc代表诱骗表数据大小; Ch代表Hash诱骗操作的代价; Jt代表诱骗表纪录数; T, Er, R同公式(3).
3) GPU NestLoop诱骗旅途代价规划
(1) NestLoop诱骗旅途启动代价Cs包括核函数动态编译加载代价、外在扫描旅途的启动代价、通盘内表数据预加载代价、投影和诱骗抒发式的启动代价、GPU启动展期间价, 如公式(6)所示.
$ C_{r}=K+O_{s}+I\_load+E_{s}+S\_delay $ (6)其中, K, Os, Es, I_load, S_delay同公式(4).
(2) NestLoop诱骗旅途代价Cr包括外在扫描旅途的实行代价、主机与GPU之间数据传输代价、NestLoop诱骗GPU并行规划代价、投影抒发式的实行代价, 如公式(7)所示.
$ C_{r}=O_{r}+T*(O_{c}+J_{c})+E_{jr}*R*O_{t}*I_{t}+E_{r}*R*J_{t} $ (7)其中, Or, T, Oc, Jc, R, Er, Jt同公式(5); Ejr代表诱骗抒发式一次实行代价; Ot代表外在的纪录总和; It代表内表的纪录总和.
4) GPU Agg旅途代价估算
(1) Agg旅途启动代价Cs包括核函数动态编译加载代价、主机与GPU数据传输代价、外在扫描旅途的总代价、GPU分组规划代价、GPU团聚规划代价和主机上最终团聚操作规划启动代价, 如公式(8)所示.
$ C_{r}=K+T*(O_{c}+A_{c})+(O_{s}+O_{r})+C_{gp}+C_{agg}+E_{aggs} $ (8)其中, K, T, Oc, Os, Or同上; Ac代表GPU预团聚操作输出数据大小(chunk数); Cgp代表GPU分组操作总代价; Cagg代表GPU团聚操作总代价; Eaggs代表主机最终团聚抒发式一次实行代价.
(2) Agg旅途运行代价Cr为Eaggr与At的乘积, 即Cr=Eaggr+At, 其中, Eaggr代表主机最终团聚抒发式一次实行代价, At代表GPU团聚输出纪录条数.
5) GPU Pipeline旅途代价解救
表层GPU旅途与基层GPU旅途进行一次核函数交融, 启动代价就要减少一次核函数动态编译加载代价, 即, 启动代价Cs=Cs-K. 实行代价减少一次CPU与GPU之间发送、给与数据的传输代价, 如公式(9)所示.
$ C_{r}=C_{r}-T*(O_{c}+J_{c})或C_{r}=C_{r}-T*(O_{c}+A_{c}) $ (9)其中, K, T, Oc, Ac同公式(8); Jc代表诱骗表数据大小.
6) FPGA旅途代价估算
由于以下原因, 针对FPGA算子的实行代价估算莫得通用的估算次序, 需要凭据算子的假想具体地分析.
(1) FPGA的频率(300 MHz傍边)自身要比CPU(GHz级别)慢许多.
(2) FPGA和GPU的加快道理不同, 不十足通过多核性情加快SQL, 很猛进度上依赖HBM的走访速率取胜(HBM的走访速率要比DDR要高).
(3) FPGA的加快效果也依赖于特定的电路的假想和优化, 雷同的算法, 不同的假想和优化导致的推崇会有很大差异, 和FPGA自身的身手不十足成正比. 因此, 规划特定kernel的代价更罕见念念道理.
底下以具体的Hash Join假想为例, 分析FPGA中SQL算子的规划代价公式的开拓. 在图 5所示的FPGA假想中, 通盘这个词join过程分为两个阶段: Build阶段+Probe阶段.
图 5 FPGAJoin算子假想
● Build阶段: 将需要作念Hash的内表通过HBM的多个通说念并行导入, 凭据SQL的诱骗条目散播到不同的build模块中并行地进行Hash操作, 快速地生成Hash表并存储到HBM中.
● Probe阶段: 将外在数据通过HBM的多个通说念并行导入, 雷同凭据SQL的诱骗条目散播到不同的build模块中并行地进行Hash操作, 通过规划到的Hash值在HBM上存储的hash表中进行匹配操作, 匹配纪录输出到collect模块后, 再汇集输出至host.
由于内表数据和对应的Hash表需要存储在FPGA里面的HBM上, 因此内表的大小不成突出HBM的大小; 而由于外在数据只进行Hash规划和匹配, 因此表面上外在无大小限制.
针对以上Hash Join的假想, 将Hash Join旅途代价分为启动代价Cs和实行代价Cr分离进行分析.
(1) 启动代价Cs是外在扫描旅途的启动代价Couter_s、启动FPGA的代价Kfpga与内表数据传入FPGA开拓HASH表的代价Cbuild三者之和. Cbuild不错示意为内表扫描旅途的代价Cinner_s、内表数据传输代价Cinner_trans与内表数据开拓hash表的代价Chash之和. 而内表数据是通过PCIe总线传输到FPGA中的, 因此内表数据传输代价为Cinner_trans为inner_size/pcie_speed, 其中, inner_size是内表数据大小, pcie_speed是PCIe传输速率. 内表数据开拓hash表是通过里面多条并行hash单元完毕的, 因此, 内表数据开拓hash表的代价如公式(10)所示.
$ {C_{hash}} = \frac{{inner\_tuples * hash\_cost}}{{hash\_concurrency}} $ (10)其中, inner_tuples是内表的元组数目, hash_concurrency是并发实行的hash单元个数, hash_cost是单个hash单元实行hash操作的代价.
因此, Hash Join旅途的启动代价如公式(11)所示.
$ {C_s} = {C_{outer\_s}} + {K_{fpga}} + {C_{inner\_s}} + \frac{{inner\_size}}{{pcie\_speed}} + \frac{{inner\_tuples * hash\_cost}}{{hash\_concurrency}} $ (11)(2) 实行代价Cr是外在数据传入FPGA的代价与实行probe操作的代价之和. 外在数据雷同是通过PCIe总线传输到FPGA中的, 因此外在数据传输代价Couter_trans为outer_size/pcie_speed, 其中, outer_size是内表数据大小, pcie_speed是PCIe传输速率. 而外在数据实行probe是通过里面多条并行hash单元完毕的, 因此外在数据实行probe的代价如公式(12)所示.
$ {C_{probe}} = \frac{{outer\_tuples * hash\_cost}}{{hash\_concurrency}} $ (12)其中, outer_tuples是外在的元组数目, hash_concurrency, hash_cost同公式(10).
因此, Hash Join旅途的实行代价如公式(13)所示.
$ {C_r} = \frac{{outer\_size}}{{pcie\_speed}} + \frac{{outer\_tuples * hash\_cost}}{{hash\_concurrency}} $ (13)7) FPGA算子活水表示径代价解救
针对Hash Join假想, 减少了内表和外在的传输代价.
(1) 启动代价Cs是外在扫描旅途的启动代价Couter_s、启动FPGA的代价Kfpga与内表数据传入FPGA开拓Hash表的代价Cbuild三者之和. Cbuild不错示意为内表扫描旅途的代价Cinner_s和内表数据开拓hash表的代价Chash之和. 因此, Hash Join旅途的启动代价如公式(14)所示.
$ {C_s} = {C_{outer\_s}} + {K_{fpga}} + {C_{inner\_s}} + \frac{{inner\_tuples * hash\_cost}}{{hash\_concurrency}} $ (14)(2) 实行代价Cr只包含实行probe操作的代价, 如公式(15)所示.
$ {C_r} = \frac{{outer\_tuples * hash\_cost}}{{hash\_concurrency}} $ (15) 2.3.2 异构交融规划旅途生成查询优化器的主要任务分红逻辑优化、物理优化、No-SPJ优化这3个阶段. 逻辑优化阶段针对查询树作念等价代数变换, 主如果栽培子查询/子邻接以及对常量/抒发式规划等进行预处理等, 与硬件身手无关, Geno不波及此阶段. 物理优化阶段主如果生成基本查询语句最小代价的旅途, 旅途用一棵树来鲜艳, 叶节点是基本表的扫描旅途, 中间节点是表的诱骗旅途. 基本表的扫描方式、两张表的诱骗方式和诱骗法例都影响旅途的代价, 在物理优化阶段接纳动态策画或者遗传算法遴荐一条最优旅途. 动态策画是一个自底朝上逐层构建的过程, 以N张表为例, 构建花式: 第1层, 针对每张基本表, 规划法例扫描、索引扫描等代价, 生成最优的表扫描旅途, 这么生成了一张基本表的扫描旅途; 第2层, 及第第1层的两张表进行诱骗, 凭据表的诱骗方式(嵌套轮回诱骗、归并诱骗、Hash诱骗)和诱骗法例(左诱骗、右诱骗)规划代价, 生成最优的诱骗, 这么生成了两张表的最优诱骗旅途; 第3层, 及第第2层的两张表或者第2层的一张表与第1层的一张表进行诱骗, 凭据表的诱骗方式和诱骗法例规划代价, 生成最优的诱骗, 这么生成了3张表的最优诱骗旅途. 依此类推, 直到第N层, 细则全部N张表的最优诱骗旅途. 动态策画算法的时间复杂度跟着表数目指数级飞腾, 因此当诱骗表数目突出指定阈值后, 为减少生成旅途的时间, 接纳遗传算法. 遗传算法是一种启发式算法, 不一定能找到最好的旅途, 只可找到相对较优的旅途. 将一张表的编号作为一个基因, N张表的一种可能诱骗旅途作为一个染色体, 花式如下: 就地运行化一个染色体(一条旅途)种群, 规划每个染色体的适合值(一条旅途的代价)比肩行, 按照一定战术遴荐两个父代染色体A, B, 父代染色体A, B进行杂交、变异, 生成新染色体C, 规划新染色体C的适合值, 插入种群中, 并去掉排行临了的染色体. 达到一定的迭代次数后, 遗传算法停止, 遴荐适合值最小的染色体, 生成N张的最优诱骗旅途法例. NO-SPJ阶段在物理优化生成旅途基础上, 凭据查询语句中AGG、Group by、Order by、distinct、limit等子句中添加Agg旅途(正常Agg、排序Agg、哈希Agg)、Group by旅途、Order by旅途、limit旅途、distinct旅途等, 生成圆善旅途.
物理优化、No-SPJ优化阶段都波及代价估算和旅途生成, 是需要Geno进行优化的阶段. 在扫描旅途、诱骗旅途、Agg旅途生成阶段, Geno提供相应的钩子来注册、调用异构规划进口函数, 生成异构规划的旅途及代价, 加入到对应的基表或诱骗表的候选旅途列表中. Geno凭据多条旅途的启动代价、总代价, 遴荐保存一条最优的查询旅途. 如图 6(a)所示, A表为行存表, B表为压缩的列存表, 实行SQL语句select sum(col2) from a, b where a.col1=b.col1.
图 6 异构规划旅途
Geno在扫描旅途生成阶段, 为A, B表分离生资本机CPU扫描旅途SeqScanPath、IndexScanPath, 以及GPU扫描旅途GpuScanPath、FPGA扫描旅途FPGAScanPath等候选旅途, 并为每条旅途规划启动代价和总代价, 临了, 优化器凭据各个候选旅途的代价遴荐一条最优的扫描旅途保存到对应基表的cheapest_total_path中. 在诱骗旅途生成阶段, 优化器为AB诱骗表生成CPU诱骗旅途HashJoinPath、NestLoopJoinPath, GPU诱骗旅途GPUJoinPath和FPGA诱骗旅途FPGAJoinPath等候选旅途, 为每条诱骗旅途规划启动代价和总代价, 遴荐一条代价最低的诱骗旅途保存到该AB诱骗表的cheapest_total_path中. 在Agg旅途生成节点生资腹地AggPath旅途、GPUAggPath旅途、FPGAAggPath旅途, 规划各旅途的启动代价和总代价, 遴荐代价最低的旅途保存到输出赶走的cheapest_total_path中.
Geno遴荐的最优查询旅途如图 6(b)所示.
$ A(GPUScanPath)+B(FPGAScanPath)+AB(GPUJoinPath)+Agg(GPUAggPath). $Geno凭据以上生成的最优查询旅途遍历通盘这个词查询旅途, 依据每个旅途节点类型生成对应的谈论节点, 构建生成实行谈论树, 临了调用实行引擎完成查询操作.
2.3.3 动态统计信息及自动重优化统计信息是规划旅途代价的基石, 统计信息的准确度对代价估算模子中行数估算和代价估算至关蹙迫, 奏凯影响查询优化器所细则的实行谈论的优劣. 如果查询波及的表缺失统计信息或者表上有多个谓词以及谓词包含有复杂操作, 以致于无法单独依赖于基表的统计信息, 将使得优化器不成准确估算基数. Geno概况使用动态统计信息来进行补充, 动态统计信息允许查询优化器强化现存的统计信息以获取愈加精准的基数估算, 不单是是为单表的走访, 而且也包含诱骗和分组谓词. Geno哄骗动态统计信息进行自动重优化, 概况为那些反复实行的具有基数估算症结的查询改善茬询谈论.
Geno哄骗一个SQL语句初度实行期间汇集到的信息来进行自动重优化. 在一个SQL语句的初度实行收尾时, 将它原本的基数估算和在实行期间不雅测到的执行基数进行比较, 如果估算值和执行值有显赫差异, 它会将正确的值存储起来供后续使用. 当查询再次实行时, 优化器会使用立异过的基数估算值, 而不是它原先的估算值来细则实行谈论. Geno在自动重优化阶段还会生成一些启发式端正, 使得其他SQL语句也能受益于此次运行实行中学到的信息. 举例, 当发生诱骗的两个表在诱骗列上有歪斜数据时, 这些端正不错指引优化器使用动态统计信息来得到愈加精准的诱骗基数估算.
2.4 数据存储异构规划环境下, 主机与异构硬件的数据传输和存储管理相称重要: 一方面, 要高效哄骗异构硬件内的内存资源来镌汰响适时延并提高吞吐量; 另一方面, 还要尽可能地减少PCIe上的数据移动和传输.
图 7(a)展示了多个异构硬件谈论节点间的数据传输. 每个谈论节点在主机上有一个实功绩态数据结构, 其中, TupleTableSlot用来保存节点实行的输出数据, 同期也作为表层谈论节点的输入数据. 实行节点从谈论树基层节点TupleTableSlot获取数据, 批量拷贝到异构硬件算子的输入数据缓冲区实行算子, 并把赶走数据拷贝回主机, 保存到实行谈论节点的TupleTableSlot中.
图 7 谈论节点间数据交换和交换花式
行存储花式表按照行数据为基本存储单元进行存储, 一滑中的通盘列数据存储在一都. 行存储恰当对表数据进行就地的增、删、改、查操作, 绝顶是需要无为插入或更新的场景; 但是对于遴荐投影操作, 即使只波及某几列, 所稀有据也都会被读取. 列存储花式的表按照列数据为基本存储单元进行存储, 消失个列的数据存储在一都, 且数据类型一致, 不错针对列的数据类型、数据量遴荐不同的压缩算法, 对列数据进行压缩存储, 比行式存储更量入计出空间; 由于各列沉寂存储, 查询过程中只读取波及的列, 概况减少无关I/O, 幸免全表扫描; 列存储还可针对各个列的运算进行并发实行, 以镌汰查询响适时间. 无为, 行存储表恰当于OLTP场景, 列存储恰当于OLAP场景. Geno优化器同期支捏行存储花式和列存储花式数据在异构硬件上的加快, 概况夸耀多种业务场景, 具有更好的适合性. 针对行存储表和列存储表, 假想不同的主机与异构硬件之间数据传输缓冲区: 主机侧只厚爱加载磁盘原始数据, 不合数据进行处理; 异构硬件侧对原始数据进行知道过滤, 充分哄骗异构硬件并行规划上风.
行存储表的数据交换花式如图 7(b)所示, 缓冲区的头包含缓冲区长度len、缓冲区类型type、行纪录数nitems、字段个数ncols、每个字段的类型信息colmeta、每条原始纪录在缓冲区的偏移量tup_index. 纪录tup_ item从缓冲区尾部起初填充, 直至缓冲区满或全部数据加载完成. GPU加载数据时, 以纪录tup_item为单元并行处理, 每个GPU core一次读取一札纪录进行处理, 凭据缓冲区中各个字段的类型信息colmeta, 知道出该札纪录通盘字段值, 实行遴荐、投影抒发式, 完成对行存储表的扫描.
列存储表数据交换花式如图 7(c)所示, 缓冲区头包含缓冲区长度len、缓冲区类型type、纪录数nitems、字段个数ncols、每个字段的类型信息colmeta等元数据信息、每个字段批数据coln_datas在缓冲区中的偏移量coln_index. 对于定长数据类型字段, coln_datas中奏凯存放相应的字段值, 对于变长数据类型字段, coln_ datas存放每个字段值的指针, 指向执行字段值存储的位置. 主机上只需要加载查询波及的字段到缓冲区, GPU加载数据时, 以字段为单元并行处理, 每个GPU core凭据缓冲区中字段的类型信息colmeta及数据偏移, 一次读取一个字段值, 实行遴荐、投影抒发式, 完成对该字段的扫描. 每个字段分拨一组GPU core进行并行处理.
3 实验与分析 3.1 实验环境实验环境设立见表 2.
表 2 实验环境设立
3.2 参数校准实验
3.2.1 规划关联代价参数校准实验
在环境A和环境B中运行参数校准器用, 得到校准后的代价参数见表 3. Geno优化器凭据校准后的代价参数来估算各样旅途的启动代价和总代价, 并凭据代价遴荐更优的实行谈论.
表 3 校准参数
CPU上, random_page_cost参数的缺省值为4, 环境A校准后的参数值为1.026 63, 环境B校准后的参数值为3.310 72. 由于SSD盘就地读性能接近于法例读的性能, 校准后的参数值更精准反应了不同环境的I/O代价因子差异. 由于环境B的CPU性能强于环境A, 环境B的cpu_tuple_cost、cpu_index_tuple_cost、cpu_ operator_cost这几个CPU关联的因子校准值比环境A的小. 而环境A的GPU规划身手更刚毅, 是以环境A的GPU与CPU规划身手折算比例gpu_ratio比环境B的gpu_ratio要小. 主机与GPU之间数据传输代价相对于腹地硬盘法例读8K页面数据的代价比例来说, 由于环境B的硬盘性能相对较差, 因而环境B的GPU传输代价相对于磁盘法例I/O代价比例小.
● 校准参数应用
底下咱们对校准前后的环境参数进行考证对比. 在环境A中使用优化器默许值与校准参数1, 在环境B中使用优化器默许值与校准参数2, 分离运行最常用的等值查询和范围查询语句.
Q1:select count(*) from t0, t1 where t0.id=t1.aid;
Q2:select count(*) from t1, t2 where t1.aid=t2.bid and t2.bid > 700000.
测试赶走如图 8所示.
图 8 校准参数应用
● 环境A上, Q1查询校准前, t0表接纳法例扫描, 然后与t1表进行Hash诱骗, 旅途估算代价为273; t0表接纳索引扫描, 然后与t1表进行嵌套诱骗, 旅途估算代价为282. 因此, Geno遴荐了代价相对较小的法例扫描和Hash诱骗旅途. 校准后, t0表接纳法例扫描, 然后与t1表进行Hash诱骗, 旅途估算代价校准为211; t0表接纳索引扫描并与t1表进行嵌套诱骗, 旅途估算代价为183. 因此, Geno遴荐了索引扫描和嵌套诱骗旅途, 查询时间从11.216 ms减少到6.934 ms;
● 环境B上, Q1查询校准前后, Geno都遴荐了法例扫描和Hash诱骗旅途, 因校准前后的代价参数不一样, 故旅途估算代价不同, 但实行旅途疏通故执行实行时间疏通.
● 环境A上, Q2查询校准前, GpuJoin旅途估算代价为27 567, MergeJoin旅途估算代价为49 332, Geno遴荐了GpuJoin; 校准后, GpuJoin旅途估算代价为19 421, MergeJoin旅途估算代价为16 493, Geno遴荐了MergeJoin, 查询时间从1 275.978 ms减少到931.862 ms;
● 而环境B上, Q2查询校准后, Geno也遴荐了旅途估算代价最小的MergeJoin旅途, 查询时间则从1 114.571 ms减少到988.636 ms.
通过以上实验分析, 不错得出校准后的参数值与硬件身手更匹配.
3.2.2 effective_cache_size参数校准实验测试接纳Sysbench器用, 通过解救effective_cache_size参数, 找出使得查询优化器算计值同执行值偏差最小的参数, 则该参数为最优参数. 由此考验执行测试的参数值是否同函数规划赶走一致, 如果两者基本一致, 则函数有用.
考证过程: 成立分享缓冲区大小为500 MB(凭据执行情况解救), 同期, 数据库在作念TPCC压力测试, 并发查询数为60. effective_cache_size取不同的值, 实行查询语句select * from test_b where a<N. N按序取值500, 1 000, 3 000, 6 000, 10 000, 20 000, 40 000, 60 000, 80 000, 100 000, 纪录估算出的总代价以及执行实行时间比值以及方差.
如图 9(a)所示, 疏通数据条目下, effective_cache_size参数取不同值: 4 GB, 2 GB, 1 GB, 500 MB, 300 MB, 分离测试上述10个SQL, 得到10组预估代价和执行时间, 取两者的比值, 再从10组比值中取最大值和最小值的差值, 不错得到预估代价和执行实行时间比值的波动值. 不错看出, 在各样场景中, 2 GB情况的波动值是最小的.
图 9 effective_cache_size参数校准实验
如图 9(b)所示, 分离规划不同参数下比值的方差. 不错看出, effective_cache_size参数取2 GB时, 优化器算计值与执行实行时间的比值方差最小. 索引扫描估算得到的代价与执行实行的时间之间的线性进度最好.也即是说, 此期间价估算最准确. 将实时的并发数(60)和系统缓存大小(500 MB)代入公式(2), 规划得到的effective_cache_size值为1.89 GB, 基本和实验得到的最好参数值一致. 与系统默许值4 GB比较, 有用栽培了索引代价估算的准确性.
对于诱骗查询, 其过程是按序获取外在的每一札纪录, 在内表中通过索引扫描查找夸耀诱骗条目的纪录.也即是说, 会对内表进行屡次串行的单表查询, 次数为外在纪录条数. 而effective_cache_size实验中, 单表查询实行屡次, 与诱骗查询过程雷同, 是以对于诱骗查询, 和单表查询的效果是一样的.
3.3 异构加快算子实验Geno支捏了遴荐、诱骗、团聚、活水线等GPU算子和FPGA算子. 为考证其效果, 本节在环境A上使用校准参数设立值, 基于TPC-H基准测试模子的表和300 GB数据, 假想了4个典型SQL语句.
● 遴荐: SELECT l_orderkey, l_partkey, l_suppkey, l_linenumber FROM lineitem1 WHERE l_linenumber=1.
● 诱骗: SELECT l_orderkey, s_name FROM supplier1, lineitem1 WHERE l_suppkey=s_suppkey and l_discount=l_tax*5.
● 团聚: SELECT sum(l_extendedprice*0.8+l_discount*0.2), sum(l_discount*200+l_tax*100), sum (l_orderkey*0.8+l_partkey*0.2) FROM lineitem1 where l_orderkey0 between 94 and 100.
jk黑丝● 活水线: SELECT sum(l_extendedprice*0.8+l_discount*0.2), sum(l_discount*200+l_tax*100), sum (l_orderkey*0.8+l_partkey*0.2) FROM lineitem1, supplier1 WHERE l_suppkey=s_suppkey and (l_orderkey/3)