基于FPGA的软硬件协同的多表哈希连接加速器

1

作者 吴婧雅 卢文岩 +1 位作者 鄢贵海 李晓维 《高技术通讯》 CAS 2023年第11期1123-1135,共13页

多表连接操作难以实现硬件加速。一方面,多表连接请求中表的数目不确定且连接方式多变,这种灵活的计算请求与固定的硬件行为之间存在矛盾;另一方面,多表连接的中间结果随表的增加而扩充,数据结构的管理和维护也要求更高的硬件开销。为... 多表连接操作难以实现硬件加速。一方面,多表连接请求中表的数目不确定且连接方式多变,这种灵活的计算请求与固定的硬件行为之间存在矛盾;另一方面,多表连接的中间结果随表的增加而扩充,数据结构的管理和维护也要求更高的硬件开销。为支持灵活高效的多表连接计算,本文提出一种软硬件协同的优化方法。软件部分,将多表连接抽象为正向和反向2种计算模式并支持不同方式的多表连接。硬件设计采用访存和计算协同优化的方法:设计一种规则的硬件哈希表结构以提高内存访存带宽;设计支持正反向计算的同构专用计算引擎,配置多数据通道和指令控制系统实现高效的并行运算,提升多表哈希连接的计算效率。实验结果表明,相比中央处理器(CPU)执行表连接操作,单计算引擎能够提升性能9.2~11.0倍。通过多路并行的技术,实现8路并行的多表哈希引擎,能够充分利用板卡片外(DDR)内存带宽,实现相比CPU超过71.1倍的性能提升。 展开更多

关键词 现场可编程门阵列(FPGA) 多表连接 哈希连接 软硬件协同

下载PDF 职称材料

基于向量引用Platform-Oblivious内存连接优化技术 被引量：2

2

作者 张延松 张宇 王珊 《软件学报》 EI CSCD 北大核心 2018年第3期883-895,共13页

以MapD为代表的图分析数据库系统通过GPU、Phi等新型众核处理器来支持高性能分析处理,在面向复杂数据模式时,连接操作仍然是重要的性能瓶颈.近年来,异构处理器逐渐成为高性能计算的主流平台,内存连接性能的研究从多核CPU平台扩展到新兴... 以MapD为代表的图分析数据库系统通过GPU、Phi等新型众核处理器来支持高性能分析处理,在面向复杂数据模式时,连接操作仍然是重要的性能瓶颈.近年来,异构处理器逐渐成为高性能计算的主流平台,内存连接性能的研究从多核CPU平台扩展到新兴的众核处理器,但众多的研究成果并未系统地揭示连接算法性能、连接数据集大小、硬件架构之间的内在联系,难以为未来异构处理器平台的数据库提供连接平台优化选择策略.以面向多核CPU、Xeon Phi、GPU处理器平台的内存连接优化技术为目标,通过优化内存哈希表设计,实现以向量映射替代哈希映射操作,消除哈希代价对内存连接算法的影响,从而更加准确地测量内存连接算法在多核CPU的cache大小、Xeon Phi的cache大小、Xeon Phi的并发多线程、GPU的SIMT(单指令多线程)机制等硬件相关因素影响下的性能特征.实验结果表明,缓存与并发多线程机制是提高内存连接算法性能的重要影响因素.缓存机制对于满足cache大小的连接操作具有性能优势,而GPU的并发多线程机制则在较大表的连接操作中具有较高的性能,Xeon Phi则在满足其L2 cache大小的连接操作中具有最高性能.实验结果揭示了内存连接操作性能与异构处理器硬件特性的联系,为未来异构处理器平台内存数据库查询优化器提供了优化策略. 展开更多

关键词 内存连接操作 哈希连接 向量映射 异构处理器平台

下载PDF 职称材料

SQL性能优化——表连接的分析

3

作者 黄春凤 《通信管理与技术》 2008年第6期37-40,共4页

介绍两个表连接的几种常用方式和不同方式的内部机制。在比较3种不同表连接方式的优缺点基础上,选择一种好的方式来优化表连接,以提高查询速度,并结合中国邮政报刊发行系统数据库开发中遇到的生产实际,分析3种表连接方式的优劣。

关键词 SQL 表连接 嵌套循环连接 排列合并连接 哈希连接

原文传递

对Transact-SQL中groupby子句异常的分析

4

作者 潘虎 《襄樊学院学报》 2003年第2期60-65,共6页

分析了在某些特定情况下,SQL Sever 2000查询优化器所决定的执行方案出现失误的原因,同时提出了解决这一问题的方法:在相关操作命令之后加上order by子句.

关键词 查询优化器 groupBy 嵌套循环内连接 哈希连接 哈希汇总

下载PDF 职称材料

外包数据库中的哈希连接一致性算法 被引量：1

5

作者 马莎 杨波 李康顺 《计算机科学》 CSCD 北大核心 2012年第2期198-202,221,共6页

外包数据库中的连接查询比范围查询更困难,因为客户端需要验证连接结果的一致性,而传统的对单个表的签名不能有效地支持对连接查询结果的直接验证。提出了使用哈希连接保证数据一致性的2种算法,它们分别通过在服务器端和客户端计算哈希... 外包数据库中的连接查询比范围查询更困难,因为客户端需要验证连接结果的一致性,而传统的对单个表的签名不能有效地支持对连接查询结果的直接验证。提出了使用哈希连接保证数据一致性的2种算法,它们分别通过在服务器端和客户端计算哈希函数来实现连接查询。给出了这2种算法的详细描述,证明了它们满足一致性要求,而且分析了算法在通信量、服务器端和客户端执行的代价。最后在实验中通过设置不同的参数对它们在服务器端和客户端的运行时间进行了比较,总结了它们在实际应用中的优缺点。 展开更多

关键词 数据库安全 外包数据库 哈希连接 数据一致性

下载PDF 职称材料

Hashjoin算子矢量化优化

6

作者 徐庆岳 何清法 +1 位作者 蒋志勇 赵殿奎 《计算机与数字工程》 2014年第11期2041-2044,2211,共5页

针对Hashjion性能瓶颈,为了提高数据库性能,加快查询响应能力,提出矢量化方法优化Hashjoin。矢量化又叫批处理,是针对目前数据库处理系统存在的按行迭代,流水线操作方式而提出的一种优化思路。矢量是构建阶段使用大小为n作为输入向量,... 针对Hashjion性能瓶颈,为了提高数据库性能,加快查询响应能力,提出矢量化方法优化Hashjoin。矢量化又叫批处理,是针对目前数据库处理系统存在的按行迭代,流水线操作方式而提出的一种优化思路。矢量是构建阶段使用大小为n作为输入向量,并允许任意列的组合的原则处理它们的输入。执行器执行查询计划树,每次迭代算子执行以矢量即批量元组为单位而不是以行为单位。通过仿真实验得出批处理最终加快了Hashjoin算子处理速度近30倍,结果在查询中涉及到Hashjoin的查询分析性能大大提升。 展开更多

关键词 哈希连接 矢量化 哈希表 算子

下载PDF 职称材料

ALFHJ:一种面向众核协处理器的自适应无锁哈希连接算法

7

作者 周开来 陈红 +2 位作者 孙辉 李翠平 董兆安 《计算机学报》 EI CSCD 北大核心 2017年第10期2404-2420,共17页

众核协处理器因其良好的并行计算能力和能源效率,正成为当前高性能计算普遍采用的加速设备.无划分哈希连接算法是多核平台上一种简单高效的连接算法,但随着众核上并发线程数的增加,其共享哈希表的锁同步问题正成为算法并行化的瓶颈.为... 众核协处理器因其良好的并行计算能力和能源效率,正成为当前高性能计算普遍采用的加速设备.无划分哈希连接算法是多核平台上一种简单高效的连接算法,但随着众核上并发线程数的增加,其共享哈希表的锁同步问题正成为算法并行化的瓶颈.为解决上述问题,该文提出一种面向众核协处理器的自适应无锁哈希连接算法ALFHJ.该算法通过评估数据集的潜在冲突度动态调整算法参数及处理流程,支持基于CAS(比较与交换)原子操作的无锁共享哈希表构建,并利用SIMD指令进行哈希表探测.同时,该文进行了热点代码分析,讨论了一致性问题、ABA问题以及收敛性问题.在Xeon Phi上的实验结果表明,相比最新的基于锁同步的NPO(优化的无分区哈希连接)算法,ALFHJ算法有以下两点优势:(1)在提高哈希表空间利用率的同时,更能保持性能的相对稳定;(2)并行执行时间对于均匀数据集减少约10%,对于倾斜数据集减少约30%~50%. 展开更多

关键词 哈希连接 无锁 众核 协处理器 比较与交换

下载PDF 职称材料

基于一种简单性能模型的数据库连接索引的选择

8

作者 琚耀 《区域治理》 2018年第5期289-290,共2页

分析已经存在的连接算法的基础上,实现基于连接索引的代价评估,从数据模型理论上去佐证每个连接查询的性能.在这里,合理利用了分配的内存,只扫描关系中参与连接的部分,尽量避免了冗余的I/O的同时,考虑到排序的代价,以及影响到算法性能... 分析已经存在的连接算法的基础上,实现基于连接索引的代价评估,从数据模型理论上去佐证每个连接查询的性能.在这里,合理利用了分配的内存,只扫描关系中参与连接的部分,尽量避免了冗余的I/O的同时,考虑到排序的代价,以及影响到算法性能的多种因素. 展开更多

关键词 索引 I/O时间 块访问 块嵌套循环 哈希连接

下载PDF 职称材料

Oracle中hash join研究

9

作者 马立和 韩锋 王艳 《科技信息》 2012年第27期86-86,109,共2页

哈希连接引入目的主要是为了解决嵌套循环连接中大量随机读取的问题,又要解决排序合并连接中排序代价过大的问题。在缺少有用的索引时,哈希连接比嵌套循环连接更加有效。哈希连接可能优于嵌套循环连,因为哈希表在内存中比检索B树速度更... 哈希连接引入目的主要是为了解决嵌套循环连接中大量随机读取的问题,又要解决排序合并连接中排序代价过大的问题。在缺少有用的索引时,哈希连接比嵌套循环连接更加有效。哈希连接可能优于嵌套循环连,因为哈希表在内存中比检索B树速度更快。然而,在排序合并连接中,由于两张表都需要先做排序,然后再做MERGE操作,因此效率相对最差。现在Oracle的优化器发展趋势是越来多使用哈希连接来处理表间关联问题。 展开更多

关键词 哈希连接 Nested LOOP ORACLE

下载PDF 职称材料

基于DSVM和消息传递的并行哈希连接算法的性能分析 被引量：1

10

作者 方强 王国仁 +1 位作者 叶峰 于戈 《东北大学学报（自然科学版）》 EI CAS CSCD 北大核心 1999年第6期583-586,共4页

基于分布式共享虚拟存储器（ＤＳＶＭ） 的软件设计方法是运行在网络工作站（ＮＯＷ） 上的支持并行计算与分布处理的新途径，它与传统的消息传递的编程方法不同·描述了在面向对象的分布式数据库系统ＳｈｕｓｓｅＵｏ 上，用Ｄ... 基于分布式共享虚拟存储器（ＤＳＶＭ） 的软件设计方法是运行在网络工作站（ＮＯＷ） 上的支持并行计算与分布处理的新途径，它与传统的消息传递的编程方法不同·描述了在面向对象的分布式数据库系统ＳｈｕｓｓｅＵｏ 上，用ＤＳＶＭ 和消息传递两种方式分别实现并行哈希连接操作的３种算法；设计了测试数据库和３ 种不同的负载；并分析了ＤＳＶＭ 和消息传递这两种设计方法的性能·大量的测试结果表明，基于ＤＳＶＭ 的算法的性能比传统的消息传递的算法稍差，但ＤＳＶＭ 具有易编程等优点，因此在并行处理上仍是一项很有研究和开发价值的技术· 展开更多

关键词 哈希连接算法 并行连接算法 DSVM 消息传递

下载PDF 职称材料

LCDJ:面向内存集群计算的局部感知连接算法

11

作者 张磊 周敏奇 王立 《华东师范大学学报（自然科学版）》 CAS CSCD 北大核心 2014年第5期228-239,共12页

等值连接是数据库系统中最为重要的操作之一,哈希连接在处理等值连接时,表现出较高的性能.在分布式内存数据库系统中,数据即已分布式地存储于多个节点上,哈希连接通常情况需要将参与连接的两个关系表在连接属性上按照相同的哈希函数进... 等值连接是数据库系统中最为重要的操作之一,哈希连接在处理等值连接时,表现出较高的性能.在分布式内存数据库系统中,数据即已分布式地存储于多个节点上,哈希连接通常情况需要将参与连接的两个关系表在连接属性上按照相同的哈希函数进行数据重分区,从而保证连接属性值相同的元组被传输到同一个节点上进行本地连接操作.由于内存数据处理速率远远高于网络的数据传输速率,因此数据重分区占据了连接算法的绝大部分时间,成为分布式内存数据库系统中等值连接操作的性能瓶颈.本文提出了一种新颖的分布式内存数据库环境下的等值连接算法LCDJ(Locality Conscious Distributed Join),在充分利用高效的内存计算的同时尽量减少网络数据传输量.算法首先对每个表连接属性的数据分布进行精确的统计,并结合并行度和计算负载均衡因素,进而建立代价模型来衡量不同调度策略下的时间开销,并求出最优的调度策略.LCDJ实现于基于内存的分布式原型系统Claims中.实验结果表明,本文所提算法有效地降低了网络传输代价,大幅度减少了响应时间,比起当前流行的Hive和Shark等系统有明显的性能提升. 展开更多

关键词 分布式哈希连接 内存数据库 网络传输优化 负载均衡 分布式系统

下载PDF 职称材料