OmegaDB： concurrent computing framework of relational operators for heterogeneous architecture

doi:10.11772/j.issn.1001-9081.2022071131

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (7): 2017-2025.DOI: 10.11772/j.issn.1001-9081.2022071131

• The 39th CCF National Database Conference (NDBC 2022) • Previous Articles

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.

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

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

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

通讯作者: 徐子晨
作者简介:赖锦辉（1998—），男，江西吉安人，硕士研究生，主要研究方向：数据库；
徐子晨（1985—），男，江西南昌人，教授，博士，CCF会员，主要研究方向：计算机系统架构、节能计算、高性能计算、分布式存储、数据库；
涂亦澄（1973—），男，湖南益阳人，教授，博士，主要研究方向：数据库、大数据管理、并行和分布式系统；
谭国龙（1996—），男，江西上饶人，硕士，主要研究方向：数据库、Flink。

Abstract

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

摘要：

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

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

CLC Number:

TP391.1

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.

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

Figures/Tables 14

Fig. 1 Data sharing existed between queries

Fig. 2 Framework of OmegaDB

Fig. 3 Implementation architecture of 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$	中间结果（全局关系）的大小，可以根据经验估计

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$	中间结果（全局关系）的大小，可以根据经验估计

Fig. 4 Stream computing of OmegaDB

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

Fig. 5 OmegaDB experimental flow

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

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

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

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

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

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

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

References 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]	ZHANG Yunke, LIU Dan. Real-time implementation of improved TINY YOLO vehicle detection algorithm based on Zynq SoC hardware acceleration [J]. Journal of Computer Applications, 2019, 39(1): 192-198.
[2]	FAN Hongwei, HU Yuxiang, LAN Julong. Two-stage hardware acceleration resource deployment mechanism for virtual network function [J]. Journal of Computer Applications, 2018, 38(9): 2575-2580.
[3]	DING Xinzhe, ZHANG Zhaogong, LI Jianzhong, TAN Long, LIU Yong. Relational algebraic operation algorithm on compressed data [J]. Journal of Computer Applications, 2016, 36(1): 21-26.
[4]	MENG Xiangyang, LIN Qi. Hardware acceleration model of MD5 algorithm based on NetMagic platform [J]. Journal of Computer Applications, 2015, 35(4): 991-995.
[5]	. Real-time cloth simulation based on particle constraints [J]. Journal of Computer Applications, 2011, 31(01): 289-292.

OmegaDB： concurrent computing framework of relational operators for heterogeneous architecture

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 25

Related Articles 5

Recommended Articles

Metrics