面向异构架构的关系型算子并发计算框架OmegaDB

doi:10.11772/j.issn.1001-9081.2022071131

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (7): 2017-2025.DOI: 10.11772/j.issn.1001-9081.2022071131

所属专题：第39届CCF中国数据库学术会议(NDBC 2022)

• 第39届CCF中国数据库学术会议(NDBC 2022) • 上一篇下一篇

面向异构架构的关系型算子并发计算框架OmegaDB

赖锦辉¹, 徐子晨¹(), 涂亦澄², 谭国龙¹

^1.南昌大学数学与计算机学院，南昌 330031
^2.嘉兴云豹科技有限公司，浙江嘉兴 314006

收稿日期:2022-08-02 修回日期:2022-08-27 接受日期:2022-09-05 发布日期:2023-07-20 出版日期:2023-07-10
通讯作者: 徐子晨
作者简介:赖锦辉（1998—），男，江西吉安人，硕士研究生，主要研究方向：数据库；
徐子晨（1985—），男，江西南昌人，教授，博士，CCF会员，主要研究方向：计算机系统架构、节能计算、高性能计算、分布式存储、数据库；
涂亦澄（1973—），男，湖南益阳人，教授，博士，主要研究方向：数据库、大数据管理、并行和分布式系统；
谭国龙（1996—），男，江西上饶人，硕士，主要研究方向：数据库、Flink。

OmegaDB： concurrent computing framework of relational operators for heterogeneous architecture

Jinhui LAI¹, Zichen XU¹(), Yicheng TU², Guolong TAN¹

^1.School of Mathematics and Computer Science，Nanchang University，Nanchang Jiangxi 330031，China
^2.Jiaxing Yunbao Technology Company Limited，Jiaxing Zhejiang 314006，China

Received:2022-08-02 Revised:2022-08-27 Accepted:2022-09-05 Online:2023-07-20 Published:2023-07-10
Contact: Zichen XU
About author:LAI Jinhui， born in 1998， M. S. candidate. His research interests include database.
XU Zichen， born in 1985， Ph. D.， professor. His research interests include computer system architecture， energy-saving computing， high-performance computing， distributed storage， database.
TU Yicheng， born in 1973， Ph. D.， professor. His research interests include database， big data management， parallel and distributed systems.
TAN Guolong， born in 1996， M. S. His research interests include database， Flink.

摘要/Abstract

摘要：

数据库系统的不同查询之间存在访问数据路径重叠和计算共享的可能，而工作负载中的查询分批处理称为多条查询一次执行（Multiple-Query-at-a-Time）模型。一些已开发的多查询处理框架已经被证明有效，然而都缺乏构建完整查询处理和优化方法的普适框架。在基于等价变换来构建查询时算子合并优化框架的基础上，提出一种面向异构架构的关系型算子并发计算框架OmegaDB。该框架通过研究面向GPU的关系算子流批计算模型并构建关系数据查询流水，在CPU-GPU异构架构上实现了聚合多查询的流批计算方法。在实验及原型实现上，通过理论分析和实验结果验证OmegaDB相对传统关系型数据库管理系统（RDBMS）所具备的优势，以及OmegaDB利用新硬件的潜力。根据基于传统关系代数规则的多条查询一次执行模型的查询优化框架的理论研究，提出多个优化方法并展望未来研究方向。使用TPC-H商业智能计算作为基准测试程序，实验结果表明OmegaDB与现代先进的商业数据库系统SQL SERVER相比，在消耗更低的磁盘I/O和CPU时间的情况下，最高可以达到24倍的端到端加速。

关键词: 高并发关系数据库, 多条查询一次执行, 关系代数, 流批计算, 硬件加速

Abstract:

There is a possibility of overlapping access data paths and shared computation among different queries in database systems， and batch processing of queries in workloads is called Multiple-Query-at-a-Time model. Several developed multi-query processing frameworks have been proven effective， but all of them lack a general framework for building complete query processing and optimization methods. On the basis of a query time operator merging optimization framework constructed based on equivalent transformation， a relational operator concurrent computing framework for heterogeneous architectures， called OmegaDB， was proposed. In this framework， by studying the GPU-oriented relational operator flow-batch computing model， and constructing the relational data query pipeline， a flow-batch computing method aggregating multiple-query was implemented on the CPU-GPU heterogeneous architecture. On experiments and prototype implementation， the advantages of OmegaDB were verified through theoretical analysis and experimental results by comparing with Relational Database Management System （RDBMS）， and the potential of OmegaDB in utilizing new hardware was shown. According to the theoretical study of query optimization frameworks of Multiple-Query-at-a-Time models based on the traditional relational algebraic rules， several optimization methods were proposed and future research directions were prospected. Using TPC-H business intelligence computing as a benchmarking program， the results show that OmegaDB achieves up to 24 times end-to-end speedup while consuming lower disk I/O and CPU time than the modern advanced commercial database system SQL SERVER.

Key words: highly concurrent relational database, Multiple-Query-at-a-Time, relational algebra, flow-batch computing, hardware acceleration

中图分类号:

TP391.1

赖锦辉, 徐子晨, 涂亦澄, 谭国龙. 面向异构架构的关系型算子并发计算框架OmegaDB[J]. 计算机应用, 2023, 43(7): 2017-2025.

Jinhui LAI, Zichen XU, Yicheng TU, Guolong TAN. OmegaDB： concurrent computing framework of relational operators for heterogeneous architecture[J]. Journal of Computer Applications, 2023, 43(7): 2017-2025.

图/表 14

图1 查询之间存在的数据共享

Fig. 1 Data sharing existed between queries

图2 OmegaDB框架

Fig. 2 Framework of OmegaDB

图3 OmegaDB实现架构

Fig. 3 Implementation architecture of OmegaDB

表1 OmegaDB实现参数

Tab. 1 OmegaDB implementation parameters

参数	描述
$S s q l$	数据库系统产生中间结果（全局关系）元组平均速率，运行时速率大体恒定，取决于不同查询类别和数据库大小
$S i n s$	中间结果表元组载入速率，与CPU单核性能正相关
$D q u e u e$	输入缓冲池大小，根据批量大小在运行前设定
$T f w$	中间结果分发器分发每批数据平均耗时，与CPU性能正相关
$D b a t c h$	每个批次的数据量，运行前设定
$D t o t a l$	中间结果（全局关系）的大小，可以根据经验估计

表1 OmegaDB实现参数

Tab. 1 OmegaDB implementation parameters

参数	描述
$S s q l$	数据库系统产生中间结果（全局关系）元组平均速率，运行时速率大体恒定，取决于不同查询类别和数据库大小
$S i n s$	中间结果表元组载入速率，与CPU单核性能正相关
$D q u e u e$	输入缓冲池大小，根据批量大小在运行前设定
$T f w$	中间结果分发器分发每批数据平均耗时，与CPU性能正相关
$D b a t c h$	每个批次的数据量，运行前设定
$D t o t a l$	中间结果（全局关系）的大小，可以根据经验估计

图4 OmegaDB的流计算

Fig. 4 Stream computing of OmegaDB

表2 实验平台

Tab. 2 Experimental platform

组件	属性
ODBC	ODBC 17.0
CUDA	CUDA 10.0
DBMS	MS SQL Server 2019 Standard
GCC	C++17
CPU	Intel Xeon E5-2698v4@2.2 GHz
GPU	Nvidia Tesla V100 PCIE 32 GB
ODBC	ODBC 17.0
SysMemory	128 GB DDR4 2 400 MHz
OS	Ubuntu 18.04 （LTS）
Storage	4×2 TB 7 200 RPM HDD

图5 OmegaDB实验流程

Fig. 5 OmegaDB experimental flow

图6 在不同SF因子下，基于CPU的OmegaDB相较于SQL SERVER的加速比

Fig. 6 Speedup of CPU-based OmegaDB compared to SQL SERVER under different SF factors

图7 在不同SF因子下，基于GPU的OmegaDB相较于SQL SERVER的加速比

Fig. 7 Speedup of GPU-based OmegaDB compared to SQL SERVER under different SF factors

图8 在不同SF因子下，OmegaDB只计算全局查询耗时与SQL SERVER查询耗时的对比

Fig. 8 Comparison of time of OmegaDB only calculating global queries and SQL SERVER query time under different SF factors

图9 在不同SF因子下，OmegaDB只计算全局查询耗时与端到端总耗时的对比

Fig. 9 Comparison of time of OmegaDB only calculating global queries and end-to-end query time under different SF factors

图10 OmegaDB和SQL SERVER在同等工作负载下消耗CPU时间量的对比

Fig. 10 Comparison of CPU time consumption between OmegaDB and SQL SERVER under same workload

图11 OmegaDB和SQL SERVER在同等工作负载下消耗磁盘I/O量的对比

Fig. 11 Comparison of disk I/O consumption between OmegaDB and SQL SERVER under same workload

图12 OmegaDB和SQL SERVER在同等工作负载下消耗逻辑I/O量的对比

Fig. 12 Comparison of logical I/O consumption between OmegaDB and SQL SERVER under same workload

参考文献 25

1	HAN J， SONG M N， SONG J D. A novel solution of distributed memory NoSQL database for cloud computing ［C］// Proceedings of the 10th IEEE/ACIS International Conference on Computer and Information Science. Piscataway： IEEE， 2011： 351-355. 10.1109/icis.2011.61
2	PAVLO A， ASLETT M. What's really new with NewSQL？［J］. ACM SIGMOD Record， 2016， 45（2）： 45-55. 10.1145/3003665.3003674
3	PAPADIMITRIOU C H. The serializability of concurrent database updates［J］. Journal of the ACM， 1979， 26（4）： 631-653. 10.1145/322154.322158
4	FINKELSTEIN S. Common expression analysis in database applications ［C］// Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1982： 235-245. 10.1145/582353.582400
5	GIANNIKIS G， ALONSO G， KOSSMANN D. SharedDB： killing one thousand queries with one stone［J］. Proceedings of the VLDB Endowment， 2012， 5（6）： 526-537. 10.14778/2168651.2168654
6	ARUMUGAM S， DOBRA A， JERMAINE C M， et al. The DataPath system： a data-centric analytic processing engine for large data warehouses ［C］// Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2010： 519-530. 10.1145/1807167.1807224
7	SELLIS T K. Multiple-query optimization［J］. ACM Transactions on Database Systems， 1988， 13（1）： 23-52. 10.1145/42201.42203
8	HARIZOPOULOS S， SHKAPENYUK V， AILAMAKI A. QPipe： a simultaneously pipelined relational query engine ［C］// Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2005： 383-394. 10.1145/1066157.1066201
9	ULLMAN J D. Principles of Database Systems［M］. 2nd ed. Rockville， MD： Computer Science Press， 1982.
10	CODD E F. A relational model of data for large shared data banks［M］// BROY M， DENERT E. Software Pioneers： Contributions to Software Engineering. Berlin： Springer， 2002： 263-294. 10.1007/978-3-642-59412-0_16
11	BRATBERGSENGEN K. Hashing methods and relational algebra operations ［C］// Proceedings of the 10th International Conference on Very Large Database Conference. San Francisco： Morgan Kaufmann Publishers Inc.， 1984： 323-333.
12	AKAMA K， NANTAJEEWARAWAT E. Computing logically with generation of equivalent transformation rules［J］. International Journal of Innovative Computing， Information and Control， 2022， 18（1）： 315-330.
13	GALLAIRE H， MINKER J， NICOLAS J M. Logic and databases： a deductive approach［M］// MYLOPOLOUS J， BRODIE M. Readings in Artificial Intelligence and Databases. San Francisco： Morgan Kaufmann Publishers Inc.， 1989： 231-247. 10.1016/b978-0-934613-53-8.50020-0
14	LIU M C. Deductive database languages： problems and solutions［J］. ACM Computing Surveys， 1999， 31（1）： 27-62. 10.1145/311531.311533
15	SELLIS T， GHOSH S. On the multiple-query optimization problem［J］. IEEE Transactions on Knowledge and Data Engineering， 1990， 2（2）： 262-266. 10.1109/69.54724
16	SHIM K， SELLIS T， NAU D. Improvements on a heuristic algorithm for multiple-query optimization［J］. Data and Knowledge Engineering， 1994， 12（2）： 197-222. 10.1016/0169-023x(94)90014-0
17	ROY P， SESHADRI S， SUDARSHAN S， et al. Efficient and extensible algorithms for multi query optimization ［C］// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2000： 249-260. 10.1145/335191.335419
18	BAYIR M A， TOROSLU I H， COSAR A. Genetic algorithm for the multiple-query optimization problem［J］. IEEE Transactions on Systems， Man， and Cybernetics， Part C （Applications and Reviews）， 2007， 37（1）： 147-153. 10.1109/tsmcc.2006.876060
19	TRUMMER I， KOCH C. Multiple query optimization on the D-Wave 2X adiabatic quantum computer［J］. Proceedings of the VLDB Endowment， 2016， 9（9）： 648-659. 10.14778/2947618.2947621
20	CANDEA G， POLYZOTIS N， VINGRALEK R. A scalable， predictable join operator for highly concurrent data warehouses ［C］// Proceedings of the VLDB Endowment， 2009， 2（1）： 277-288. 10.14778/1687627.1687659
21	ROOT C， MOSTAK T. MapD： a GPU-powered big data analytics and visualization platform ［C］// ACM SIGGRAPH 2016 Talks. New York： 2016： No.73. 10.1145/2897839.2927468
22	WANG K B， ZHANG K， YUAN Y， et al. Concurrent analytical query processing with GPUs［J］. Proceedings of the VLDB Endowment， 2014， 7（11）： 1011-1022. 10.14778/2732967.2732976
23	YUAN Y， LEE R B， ZHANG X D. The Yin and Yang of processing data warehousing queries on GPU devices［J］. Proceedings of the VLDB Endowment， 2013， 6（10）： 817-828. 10.14778/2536206.2536210
24	FANG R， HE B S， LU M， et al. GPUQP： query co-processing using graphics processors ［C］// Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2007： 1061-1063. 10.1145/1247480.1247606
25	ESLAMI M， TU Y C， CHARKHGARD H， et al. PsiDB： a framework for batched query processing and optimization ［C］// Proceedings of the 2019 IEEE International Conference on Big Data. Piscataway： IEEE， 2019： 6046-6048. 10.1109/bigdata47090.2019.9005486

[1]	王晓峰, 蒋彭龙, 周辉, 赵雄波. 面向卷积神经网络的高并行度FPGA加速器设计[J]. 计算机应用, 2021, 41(3): 812-819.
[2]	张雲轲, 刘丹. 基于小型Zynq SoC硬件加速的改进TINY YOLO实时车辆检测算法实现[J]. 计算机应用, 2019, 39(1): 192-198.
[3]	范宏伟, 胡宇翔, 兰巨龙. 两段式虚拟网络功能硬件加速资源部署机制[J]. 计算机应用, 2018, 38(9): 2575-2580.
[4]	丁鑫哲, 张兆功, 李建中, 谭龙, 刘勇. 压缩数据上的关系代数操作算法[J]. 计算机应用, 2016, 36(1): 21-26.
[5]	孟祥扬, 林琦. 基于NetMagic平台的MD5算法硬件加速模型[J]. 计算机应用, 2015, 35(4): 991-995.
[6]	陆忠华陈定方. 基于粒子约束的布料实时模拟[J]. 计算机应用, 2011, 31(01): 289-292.
[7]	李瑞瑞张一天秦桂明秦开怀. 并行绘制系统中基于网络处理单元的图像合成及显示[J]. 计算机应用, 2011, 31(01): 11-15.
[8]	杨岳郭绍忠何晓忠. 基于扩展关系代数的数据集成映射模式的研究[J]. 计算机应用, 2009, 29(12): 3290-3292.
[9]	张静俞辉. 一种多模态信息融合的视频检索模型[J]. 计算机应用, 2008, 28(1): 199-201,.

面向异构架构的关系型算子并发计算框架OmegaDB

OmegaDB： concurrent computing framework of relational operators for heterogeneous architecture

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 25

相关文章 9

编辑推荐

Metrics