A cost model for analytical query optimization

Petr Kurapov, Daniil Kulikov, Areg Melik-Adamyan


Analytical query performance improvement can be achieved via efficient work distribution among devices of a heterogeneous system. The resulting performance gain highly depends on the ability of an optimizer to compare execution plans. One way to manage the complexity of a heterogeneous system is to develop cost models to that support multiple devices. Reusing existing CPU models is complicated if not impossible. This paper introduces a methodology for analytical query execution time estimation in a heterogeneous system by matching its plan to a set of computational patterns with known performance characteristics. We identify key and most common patterns and show how a query plan maps to them. We provide a general algorithm for cost calculation and evaluate model effectiveness by building a library of portable implementations and comparing their performance to a real in-memory DBMS.

Full Text:

PDF (Russian)


Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. How Good Are Query Optimizers, Really? Proc. VLDB Endow. 9, 3 (Nov. 2015), 204–215. https://doi.org/10.14778/2850583.2850594

Andrea Lottarini, Alex Ramirez, Joel Coburn, Martha A. Kim, Parthasarathy Ranganathan, Daniel Stodolsky, and Mark Wachsler. 2018. Vbench: Benchmarking Video Transcoding in the Cloud. Association for Computing Machinery, New York, NY, USA, 797–809. https://doi.org/10.1145/3173162.3173207

Chihping Wang and Ming-Syan Chen. 1996. On the complexity of distributed query optimization. IEEE Transactions on Knowledge and Data Engineering8, 4(1996), 650–662. https://doi.org/10.1109/69.536256

Timo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo, and Peter Boncz. 2018. Everything You Always Wanted to Know about Compiled and Vectorized Queries but Were Afraid to Ask. Proc. VLDB Endow. 11, 13 (Sept. 2018), 2209–2222. https://doi.org/10.14778/3275366.3284966

Sebastian Breß, Max Heimel, Norbert Siegmund, Ladjel Bellatreche, and Gunter Saake. 2014. GPU-Accelerated Database Systems: Survey and Open Challenges. Springer Berlin Heidelberg, Berlin, Heidelberg, 1–35. https://link.springer.com/chapter/10.1007/978-3-662-45761-0_1

Periklis Chrysogelos, Panagiotis Sioulas, and A. Ailamaki. 2019. Hardware-conscious Query Processing in GPU-accelerated Analytical Engines. In CIDR. http://cidrdb.org/cidr2019/papers/p127-chrysogelos-cidr19.pdf

Kuznetsov S.D. In anticipation of native DBMS architectures based on non-volatile main memory. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2020;32(1):153-180. (In Russ.) https://doi.org/10.15514/ISPRAS-2020-32(1)-9

Yannis E. Ioannidis. 1996. Query Optimization. ACM Comput. Surv. 28, 1 (March 1996), 121–123. https://doi.org/10.1145/234313.234367

Avi Silberschatz, Henry F. Korth, and S. Sudarshan. 2020. Database System Concepts, Seventh Edition. McGraw-Hill Book Company. https://www.db-book.com/db7/index.html

Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska, Olga Papaemmanouil, and Nesime Tatbul. 2019. Neo: A Learned Query Optimizer. Proc. VLDB Endow. 12, 11 (July 2019), 1705–1718. https://dl.acm.org/doi/10.14778/3342263.3342644

Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Alizadeh, and Tim Kraska. 2021. Bao: Making Learned Query Optimization Practical. In Proceedings of the 2021 International Conference on Management of Data (Virtual Event, China) (SIGMOD/PODS ’21). Association for Computing Machinery, New York, NY, USA, 1275–1288. https://dl.acm.org/doi/10.1145/3448016.3452838

Krste Asanovi ́c, Ras Bodik, Bryan Christopher Catanzaro, Joseph James Gebis, Parry Husbands, Kurt Keutzer, David A. Patterson, William Lester Plishker, John Shalf, Samuel Webb Williams, and Katherine A. Yelick. 2006. The Landscape of Parallel Computing Research: A View from Berkeley. Technical Report UCB/EECS-2006-183. EECS Department, University of California, Berkeley. http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.html

Duane G. Merrill and Andrew S. Grimshaw. 2010. Revisiting Sorting for GPGPU Stream Architectures. In Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques (Vienna, Austria) (PACT’10). Association for Computing Machinery, New York, NY, USA, 545–546. https://doi.org/10.1145/1854273.1854344

Jeronimo Castrillon, Matthias Lieber, Sascha Kl ̈uppelholz, Marcus V ̈olp, Nils Asmussen, Uwe Aßmann, Franz Baader, Christel Baier, Gerhard Fettweis, Jochen Fr ̈ohlich, Andr ́es Goens, Sebastian Haas, Dirk Habich, Hermann H ̈artig, Mattis Hasler, Immo Huismann, Tomas Karnagel, Sven Karol, Akash Kumar, Wolfgang Lehner, Linda Leuschner, Siqi Ling, Steffen M ̈arcker, Christian Menard, Johannes Mey, Wolfgang Nagel, Benedikt N ̈othen, Rafael Pe ̃naloza, Michael Raitza, J ̈org Stiller, Annett Ungeth ̈um, Axel Voigt, and Sascha Wunderlich. 2018. A Hardware/Software Stack for Heterogeneous Systems. IEEE Transactions on Multi-Scale Computing Systems 4, 3 (2018), 243–259. https://doi.org/10.1109/TMSCS.2017.2771750

Peter Boncz, Marcin Zukowski, and Niels Nes. 2005. MonetDB/X100: Hyper-pipelining query execution. In In CIDR. http://cidrdb.org/cidr2005/papers/P19.pdf

John E. Stone, David Gohara, and Guochun Shi. 2010. OpenCL: A Parallel Programming Standard for Heterogeneous Computing Systems. Computing in Science Engineering 12, 3 (2010), 66–73. https://doi.org/10.1109/MCSE.2010.69

Emily Furst, Mark Oskin, and Bill Howe. 2017. Profiling a GPU Database Implementation: A Holistic View of GPU Resource Utilization on TPC-H Queries. In Proceedings of the 13th International Workshop on Data Management on New Hardware (Chicago, Illinois) (DAMON ’17). Association for Computing Machinery, New York, NY, USA, Article 3, 6 pages. https://doi.org/10.1145/3076113.3076119

Daniil Kulikov, Daria Nikolskaia, and Petr Kurapov. 2021. Efficient Hardware-Agnostic DBMS Operator Implementation Using SYCL. In 2021 International Conference Engineering and Telecommunication (En T). 1–5. https://doi.org/10.1109/EnT50460.2021.9681747

Yansong Zhang, Yu Zhang, Jiaheng Lu, Shan Wang, Zhuan Liu, and Ruichen Han. 2020. One size does not fit all: accelerating OLAP workloads with GPUs. Distributed and Parallel Databases 38 (12 2020). https://doi.org/10.1007/s10619-020-07304-z

Thomas Neumann. 2011. Efficiently Compiling Efficient Query Plans for Modern Hardware. Proc. VLDB Endow. 4, 9 (June 2011), 539–550. https://doi.org/10.14778/2002938.2002940

Viktor Leis, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2014. Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (Snowbird, Utah, USA) (SIGMOD ’14). Association for Computing Machinery, New York, NY, USA, 743–754. https://doi.org/10.1145/2588555.2610507

Henning Funke, Sebastian Breß, Stefan Noll, Volker Markl, and Jens Teubner. 2018. Pipelined Query Processing in Coprocessor Environments. In Proceedings of the 2018 International Conference on Management of Data (Houston, TX, USA) (SIGMOD ’18). Association for Computing Machinery, New York, NY, USA, 1603–1618. https://doi.org/10.1145/3183713.3183734

Michael Voss, Rafael Asenjo, and James Reinders. 2019. Pro TBB: C++ Parallel Programming with Threading Building Blocks (1st ed.). Apress, USA. https://dl.acm.org/doi/book/10.5555/3364289

Ben Ashbaugh, Alexey Bader, James Brodman, Jeff Hammond, Michael Kinsner, John Pennycook, Roland Schulz, and Jason Sewall. 2020. Data Parallel C++: Enhancing SYCL Through Extensions for Productivity and Performance. In Proceedings of the International Workshop on OpenCL (Munich, Germany) (IWOCL’20). Association for Computing Machinery, New York, NY, USA, Article 7, 2 pages. https://doi.org/10.1145/3388333.3388653

TPCH http://www.tpc.org/tpch/

Wenfei Fan, Jianzhong Li, Shuai Ma, Nan Tang, Yinghui Wu, and Yunpeng Wu. 2010. Graph Pattern Matching: From Intractable to Polynomial Time. Proc. VLDB Endow. 3, 1–2 (sep 2010), 264–275. https://doi.org/10.14778/1920841.1920878


  • There are currently no refbacks.

Abava  Absolutech Convergent 2022

ISSN: 2307-8162