HYBRID EXECUTION OF QUERIES TO ANALYTICAL DATABASES
Abstract
Analytical database engines should benefit from evolving heterogeneous distributed architectures
and utilize their resources efficiently: various accelerators, complex memory hierarchy,
and distributed nature of systems bring performance improvement opportunities. The article reviews
existing approaches for in-memory DBMS query executor implementation using hardware
accelerators, especially GPUs. Massive parallelism and high on-device memory bandwidth make
graphics processors a promising alternative as a core query evaluation device. Existing methods
do not utilize all modern hardware capabilities and usually are bound, performance-wise, by relatively
slow PCIe data transfer in a GPU-as-a-co-processor model for each kernel representing a
single relational algebra operator. Another existing approaches’ issue is explicit code base separation
for relational algebra operators code generation (for CPU and GPU) that significantly
limits possibilities of joint device usage for performance increase and make it less feasible. The
article presents an efficient query execution method using an example of two device classes (CPU
and GPU) by compiling queries into a single, device agnostic, intermediate representation (SPIRV)
and an approach for corresponding hybrid physical query plan optimization based on extended
classical “Exchange” operator with explicit control over heterogeneous resources and parallelism
level available. A cost model composition process using basic compute DBMS patterns benchmarking
and buses bandwidth data for both relational and auxiliary operators is proposed. Potential
processing speedup from holistic query optimization is estimated empirically with a commercial
open source DBMS OmniSci DB. Preliminary results show significant (3-8x, depending on
device choice) possible speedup even with just using the right device for the job.
References
multiple GPU-accelerated DBMSes, In Proceedings of the 16th International Workshop on Data
Management on New Hardware (DaMoN '20). Association for Computing Machinery, New York,
NY, USA, 2020, Article 16, pp. 1–3. Doi: https://doi.org/10.1145/3399666.3399907.
2. Henning Funke, Sebastian Breß, Stefan Noll, Volker Markl, and Jens Teubner. Pipelined Query
Processing in Coprocessor Environments. In Proceedings of the 2018 International Conference
on Management of Data (SIGMOD '18). Association for Computing Machinery, New
York, NY, USA, 2018, 16031618. Doi: https://doi.org/10.1145/3183713.3183734.
3. Clemens Lutz, Sebastian Breß, Steffen Zeuch, Tilmann Rabl, and Volker Markl. 2020. Pump
Up the Volume: Processing Large Data on GPUs with Fast Interconnects. In Proceedings of
the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD '20).
Association for Computing Machinery, New York, NY, USA, pp. 1633-1649.
Doi:https://doi.org/10.1145/3318464.3389705.
4. Breß S., Heimel M., Siegmund N., Bellatreche L., Saake G. GPU-Accelerated Database Systems:
Survey and Open Challenges. In: Hameurlain A. et al. (eds) Transactions on Large-Scale
Data- and Knowledge-Centered Systems XV. Lecture Notes in Computer Science, Vol. 8920.
Springer, Berlin, Heidelberg, 2014. Doi: https://doi.org/10.1007/978-3-662-45761-0_1.
5. Breß S., Heimel M., Siegmund N., Bellatreche L., Saake G. Exploring the Design Space of a
GPU-Aware Database Architecture. In: Catania B. et al. (eds) New Trends in Databases and
Information Systems. Advances in Intelligent Systems and Computing. Springer, Cham, 2014,
Vol. 241. Doi: https://doi.org/10.1007/978-3-319-01863-8_25.
6. Bingsheng He, Mian Lu, Ke Yang, Rui Fang, Naga K. Govindaraju, Qiong Luo, and Pedro V.
Sander. Relational query coprocessing on graphics processors. ACM Trans. Database Syst. 34,
4, Article 21 (December 2009), 39 p. Doi: https://doi.org/10.1145/1620585.1620588.
7. Heimel M., Markl V. A First Step Towards GPU-assisted Query Optimization. In: Bordawekar,
R. and Lang, C.A. (eds.) ADMS@VLDB, 2012, pp. 33-44.
8. Peter Bakkum and Kevin Skadron. Accelerating SQL database operations on a GPU with
CUDA. In Proceedings of the 3rd Workshop on General-Purpose Computation on Graphics
Processing Units (GPGPU-3). Association for Computing Machinery, New York, NY, USA,
2010. pp. 94-103. Doi: https://doi.org/10.1145/1735688.1735706.
9. Johns Paul, Jiong He, and Bingsheng He. GPL: A GPU-based Pipelined Query Processing
Engine. In Proceedings of the 2016 International Conference on Management of Data
(SIGMOD '16). Association for Computing Machinery, New York, NY, USA, 2016, pp. 1935-
1950. Doi: https://doi.org/10.1145/2882903.2915224.
10. Ilic, Aleksandar & Pratas, Frederico & Trancoso, Pedro & Sousa, Leonel. High-Performance
Computing on Heterogeneous Systems: Database Queries on ЦПУ and GPU, 2011. Doi
10.3233/978-1-60750-803-8-202.
11. Sebastian Breβ, Bastian Köcher, Henning Funke, Steffen Zeuch, Tilmann Rabl, and Volker Markl.
Generating custom code for efficient query execution on heterogeneous processors, The VLDB
Journal 27, 6 (December 2018), pp. 797-822. Doi: https://doi.org/10.1007/s00778-018-0512-y.
12. Owaida M., Sidler D., Kara K. and Alonso G. Centaur: A Framework for Hybrid ЦПУ-FPGA
Databases, 2017 IEEE 25th Annual International Symposium on Field-Programmable Custom
Computing Machines (FCCM), 2017, pp. 211-218. Doi: 10.1109/FCCM.2017.37.
13. Thomas Neumann. Efficiently compiling efficient query plans for modern hardware. Proc.
VLDB Endow. 4, 9 (June 2011), pp. 539-550. DOI:https://doi.org/10.14778/2002938.2002940.
14. Holger Pirk, Oscar Moll, Matei Zaharia, and Sam Madden. Voodoo - a vector algebra for
portable database performance on modern hardware. Proc. VLDB Endow. 9, 14 (October
2016), 1707–1718. Doi: https://doi.org/10.14778/3007328.3007336.
15. Periklis Chrysogelos, Manos Karpathiotakis, Raja Appuswamy, and Anastasia Ailamaki.
HetExchange: encapsulating heterogeneous ЦПУ-GPU parallelism in JIT compiled engines. Proc.
VLDB Endow. 12, 5 (January 2019), pp. 544-556. Doi: https://doi.org/10.14778/3303753.3303760.
16. Cummins C., Fisches Z.V., Ben-Nun T., Hoefler T., and Leather H. Programl: Graph-based
deep learning for program optimization and analysis, arXiv preprint arXiv:2003.10536, 2020.
17. Christopher Root and Todd Mostak. MapD: a GPU-powered big data analytics and visualization
platform. In ACM SIGGRAPH 2016 Talks (SIGGRAPH '16). Association for Computing
Machinery, New York, NY, USA, 2016, Article 73, pp. 1-2. Doi: https://doi.org/10.1145/
2897839.2927468.
18. https://www.khronos.org/registry/spir-v/.
19. New York (N.Y.). Taxi and Limousine Commission. New York City Taxi Trip Data, 2009-
2018. Inter-university Consortium for Political and Social Research [distributor], 2019-02-20.
https://doi.org/10.3886/ICPSR37254.v1.
20. Shanbhag, Anil and Madden, Samuel and Yu, Xiangyao. A Study of theFundamental Performance
Characteristics of GPUs and CPUs for DatabaseAnalytics, Proceedings of the 2020
ACM SIGMOD International Conferenceon Management of Data, Association for Computing
Machinery, New York,NY, USA, 2020, pp. 1617-1632.
