[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3318464.3389739acmconferencesArticle/Chapter ViewAbstractPublication PagesmodConference Proceedingsconference-collections
research-article

Grizzly: Efficient Stream Processing Through Adaptive Query Compilation

Published: 31 May 2020 Publication History

Abstract

Stream Processing Engines (SPEs) execute long-running queries on unbounded data streams. They follow an interpretation-based processing model and do not perform runtime optimizations. This limits the utilization of modern hardware and neglects changing data characteristics at runtime. In this paper, we present Grizzly, a novel adaptive query compilation-based SPE, to enable highly efficient query execution. We extend query compilation and task-based parallelization for the unique requirements of stream processing and apply adaptive compilation to enable runtime re-optimizations. The combination of light-weight statistic gathering with just-in-time compilation enables Grizzly to adjust to changing data-characteristics dynamically at runtime. Our experiments show that Grizzly outperforms state-of-the-art SPEs by up to an order of magnitude in throughput.

Supplementary Material

MP4 File (3318464.3389739.mp4)
Presentation Video

References

[1]
Daniel J Abadi, Yanif Ahmad, Magdalena Balazinska, Ugur Cetintemel, Mitch Cherniack, Jeong-Hyon Hwang, Wolfgang Lindner, Anurag Maskey, Alex Rasin, Esther Ryvkina, et al. 2005. The design of the borealis stream processing engine. In CIDR, Vol. 5. 277--289.
[2]
Daniel J Abadi, Don Carney, Ugur cC etintemel, Mitch Cherniack, Christian Convey, Sangdon Lee, Michael Stonebraker, Nesime Tatbul, and Stan Zdonik. 2003. Aurora: a new model and architecture for data stream management. VLDB Journal, Vol. 12, 2 (2003), 120--139.
[3]
Sameer Agarwal, Davies Liu, and Reynold Xin. 2016. Apache Spark as a Compiler: Joining a Billion Rows per Second on a Laptop. https://databricks.com/blog/2016/05/23/apache-spark-as-a-compiler-joining-a-billion-rows-per-second-on-a-laptop.html. [Online; accessed 31.5.2019].
[4]
Yanif Ahmad and Christoph Koch. 2009. DBToaster: A SQL Compiler for High-performance Delta Processing in Main-memory Databases. In PVLDB. VLDB Endowment, 1566--1569.
[5]
Tyler Akidau, Alex Balikov, Kaya Bekiroug lu, Slava Chernyak, Josh Haberman, Reuven Lax, Sam McVeety, Daniel Mills, Paul Nordstrom, and Sam Whittle. 2013. MillWheel: fault-tolerant stream processing at internet scale. In PVLDB, Vol. 6. VLDB Endowment, 1033--1044.
[6]
John R Allen, Ken Kennedy, Carrie Porterfield, and Joe Warren. 1983. Conversion of control dependence to data dependence. In SIGPLAN. ACM, 177--189.
[7]
David I August, Wen-mei W Hwu, and Scott A Mahlke. 1997. A framework for balancing control flow and predication. In MICRO. IEEE, 92--103.
[8]
Shivnath Babu and Pedro Bizarro. 2005. Adaptive query processing in the looking glass. In CIDR.
[9]
Shivnath Babu, Pedro Bizarro, and David DeWitt. 2005. Proactive re-optimization. In SIGMOD. ACM, 107--118.
[10]
Alain Biem, Eric Bouillet, Hanhua Feng, Anand Ranganathan, Anton Riabov, Olivier Verscheure, Haris Koutsopoulos, and Carlos Moran. 2010. IBM infosphere streams for scalable, real-time, intelligent transportation services. In SIGMOD. ACM, 1093--1104.
[11]
Irina Botan, Roozbeh Derakhshan, Nihal Dindar, Laura Haas, Renée J Miller, and Nesime Tatbul. 2010. SECRET: A Model for Analysis of the Execution Semantics of Stream Processing Systems. In PVLDB, Vol. 3. VLDB Endowment, 232--243.
[12]
Sebastian Breß, Bastian Köcher, Henning Funke, Steffen Zeuch, Tilmann Rabl, and Volker Markl. 2018. Generating Custom Code for Efficient Query Execution on Heterogeneous Processors. The VLDB Journal, Vol. 27, 6 (2018), 797--822.
[13]
David Broneske, Sebastian Breß, and Gunter Saake. 2013. Database scan variants on modern CPUs: A performance study. In IMDM. Springer, 97--111.
[14]
David Broneske, Andreas Meister, and Gunter Saake. 2017. Hardware-sensitive scan operator variants for compiled selection pipelines. In BTW. Gesellschaft für Informatik, Bonn.
[15]
Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache Flink: Stream and Batch Processing in a Single Engine. IEEE Data Engineering Bulletin, Vol. 36, 4 (2015).
[16]
Paris Carbone, Jonas Traub, Asterios Katsifodimos, Seif Haridi, and Volker Markl. 2016. Cutty: Aggregate sharing for user-defined windows. In CIKM. 1201--1210.
[17]
Raul Castro Fernandez, Matteo Migliavacca, Evangelia Kalyvianaki, and Peter Pietzuch. 2013. Integrating scale out and fault tolerance in stream processing using operator state management. In SIGMOD. ACM, 725--736.
[18]
Badrish Chandramouli, Jonathan Goldstein, Mike Barnett, Robert DeLine, Danyel Fisher, John C. Platt, James F. Terwilliger, and John Wernsing. 2014. Trill: A High-performance Incremental Query Processor for Diverse Analytics. In PVLDB, Vol. 8. VLDB Endowment, 401--412.
[19]
Sirish Chandrasekaran, Owen Cooper, Amol Deshpande, Michael J Franklin, Joseph M Hellerstein, Wei Hong, Sailesh Krishnamurthy, Samuel Madden, Vijayshankar Raman, Frederick Reiss, et al. 2003. Telegraphcq: Continuous dataflow processing for an Uncertain world. In CIDR, Vol. 2. 4.
[20]
Jianjun Chen, David J DeWitt, Feng Tian, and Yuan Wang. 2000. NiagaraCQ: A scalable continuous query system for internet databases. In ACM SIGMOD Record, Vol. 29. ACM, 379--390.
[21]
Sanket Chintapalli, Derek Dagit, Bobby Evans, Reza Farivar, Thomas Graves, Mark Holderbaugh, Zhuo Liu, Kyle Nusbaum, Kishorkumar Patil, Boyang Jerry Peng, et al. 2016. Benchmarking Streaming Computation Engines: Storm, Flink and Spark Streaming. In IPDPS. IEEE, 1789--1792.
[22]
John Cieslewicz and Kenneth A Ross. 2007. Adaptive aggregation on chip multiprocessors. In VLDB. VLDB Endowment, 339--350.
[23]
Intel Corporation. 2016. Intel 64 and IA-32 Architectures Optimization Reference Manual.
[24]
Andrew Crotty, Alex Galakatos, Kayhan Dursun, Tim Kraska, Ugur cC etintemel, and Stanley B. Zdonik. 2015. Tupleware: "Big" Data, Big Analytics, Small Clusters. In CIDR.
[25]
Cristian Diaconu, Craig Freedman, Erik Ismert, Per-Ake Larson, Pravin Mittal, Ryan Stonecipher, Nitin Verma, and Mike Zwilling. 2013. Hekaton: SQL Server's Memory-optimized OLTP Engine. In SIGMOD. ACM, 1243--1254.
[26]
M. Dreseler, J. Kossmann, J. Frohnhofen, M. Uflacker, and H. Plattner. 2018. Fused Table Scans: Combining AVX-512 and JIT to Double the Performance of Multi-Predicate Scans. In ICDEW. 102--109.
[27]
Anshuman Dutt and Jayant R. Haritsa. 2014. Plan Bouquets: Query Processing Without Selectivity Estimation. In SIGMOD. ACM, New York, NY, USA, 1039--1050.
[28]
Grégory Essertel, Ruby Tahboub, and Tiark Rompf. 2018a. On-Stack Replacement for Program Generators and Source-to-Source Compilers. Preprint (2018).
[29]
Gré gory M. Essertel, Ruby Y. Tahboub, James M. Decker, Kevin J. Brown, Kunle Olukotun, and Tiark Rompf. 2018b. Flare: Optimizing Apache Spark with Native Compilation for Scale-Up Architectures and Medium-Size Data. In OSDI. 799--815.
[30]
Martin Faust, David Schwalb, and Jens Krueger. 2013. Fast column scans: Paged indices for in-memory column stores. In IMDM. Springer, 15--27.
[31]
Stephen J Fink and Feng Qian. 2003. Design, implementation and evaluation of adaptive recompilation with on-stack replacement. In CGO. IEEE, 241--252.
[32]
Agner Fog. 2009. How good is hyperthreading? https://www.agner.org/optimize/blog/read.php?i=6. [Online; accessed 31.5.2019].
[33]
Craig Freedman, Erik Ismert, and Per-Åke Larson. 2014. Compilation in the Microsoft SQL Server Hekaton Engine. IEEE Data Engineering Bulletin, Vol. 37 (2014), 22--30.
[34]
Bugra Gedik, Henrique Andrade, and Kun-Lung Wu. 2009. A code generation approach to optimizing high-performance distributed data stream processing. In CIKM. ACM, 847--856.
[35]
Goetz Graefe. 1990. Encapsulation of Parallelism in the Volcano Query Processing System. In SIGMOD. ACM, 102--111.
[36]
Jamie Grier. 2016. Extending the Yahoo! Streaming Benchmark. https://data-artisans.com/blog/extending-the-yahoo-streaming-benchmark. [Online; accessed 31.5.2019].
[37]
Martin Hirzel, Robert Soulé, Scott Schneider, Buugra Gedik, and Robert Grimm. 2014. A Catalog of Stream Processing Optimizations. Comput. Surveys, Vol. 46, 4, Article 46 (March 2014), 34 pages.
[38]
Urs Hölzle, Craig Chambers, and David Ungar. 1992. Debugging optimized code with dynamic deoptimization. In ACM Sigplan Notices, Vol. 27. ACM, 32--43.
[39]
Intel. 2019. Intel(R) Threading Building Blocks: Concurrent Hash Map. https://software.intel.com/en-us/node/506191. [Online; accessed 31.5.2019].
[40]
Paulo Jesus, Carlos Baquero, and Paulo Sérgio Almeida. 2014. A survey of distributed data aggregation algorithms. IEEE Communications Surveys & Tutorials, Vol. 17, 1 (2014), 381--404.
[41]
Jeyhun Karimov, Tilmann Rabl, Asterios Katsifodimos, Roman Samarev, Henri Heiskanen, and Volker Markl. 2018. Benchmarking distributed stream data processing systems. In ICDE. IEEE, 1507--1518.
[42]
Tim Kiefer, Benjamin Schlegel, and Wolfgang Lehner. 2013. Experimental evaluation of NUMA effects on database management systems. In BTW. Gesellschaft für Informatik eV.
[43]
Yannis Klonatos, Christoph Koch, Tiark Rompf, and Hassan Chafi. 2014. Building efficient query engines in a high-level language. In PVLDB, Vol. 7. VLDB Endowment, 853--864.
[44]
André Kohn, Viktor Leis, and Thomas Neumann. 2018. Adaptive execution of compiled queries. In ICDE. IEEE, 197--208.
[45]
Alexandros Koliousis, Matthias Weidlich, Raul Castro Fernandez, Alexander L Wolf, Paolo Costa, and Peter Pietzuch. 2016. Saber: Window-based hybrid stream processing for heterogeneous architectures. In SIGMOD. ACM, 555--569.
[46]
Konstantinos Krikellas, Stratis D Viglas, and Marcelo Cintra. 2010. Generating code for holistic query evaluation. In ICDE. 613--624.
[47]
Lars Kroll, Klas Segeljakt, Paris Carbone, Christian Schulte, and Seif Haridi. 2019. Arc: An IR for Batch and Stream Programming. In DBPL. ACM, New York, NY, USA, 53--58.
[48]
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 SIGMOD. ACM, 743--754.
[49]
Viktor Leis, Bernhard Radke, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2018. Query Optimization Through the Looking Glass, and What We Found Running the Join Order Benchmark. The VLDB Journal, Vol. 27, 5 (Oct. 2018), 643--668.
[50]
Yinan Li, Ippokratis Pandis, Rene Mueller, Vijayshankar Raman, and Guy M Lohman. 2013. NUMA-aware algorithms: the case of data shuffling. In CIDR.
[51]
Tobias Maier, Peter Sanders, and Roman Dementiev. 2019. Concurrent Hash Tables: Fast and General (?)! TOPC, Vol. 5, 4 (2019), 16.
[52]
Prashanth Menon, Todd C. Mowry, and Andrew Pavlo. 2017. Relaxed Operator Fusion for In-memory Databases: Making Compilation, Vectorization, and Prefetching Work Together at Last. In PVLDB, Vol. 11. VLDB Endowment, 1--13.
[53]
Hongyu Miao, Heejin Park, Myeongjae Jeon, Gennady Pekhimenko, Kathryn S. McKinley, and Felix Xiaozhu Lin. 2017. Strea: Modern Stream Processing on a Multicore Machine. In USENIX. 617--629.
[54]
Derek G Murray, Frank McSherry, Rebecca Isaacs, Michael Isard, Paul Barham, and Mart'in Abadi. 2013. Naiad: a timely dataflow system. In SOSP. ACM, 439--455.
[55]
Thomas Neumann. 2011. Efficiently Compiling Efficient Query Plans for Modern Hardware. In PVLDB, Vol. 4. VLDB Endowment, 539--550.
[56]
Paroski Paroski. 2016. Code generation: The inner sanctum of database performance. http://highscalability. com/blog/2016/9/7/code-generation-the-inner-sanctum-ofdatabase-performance. html. [Online; accessed 31.5.2019].
[57]
Peter Pietzuch, Panagiotis Garefalakis, Alexandros Koliousis, Holger Pirk, and George Theodorakis. 2018a. Do We Need Distributed Stream Processing? https://lsds.doc.ic.ac.uk/blog/do-we-need-distributed-stream-processing. [Online; accessed 31.5.2019].
[58]
Peter Pietzuch, Panagiotis Garefalakis, Alexandros Koliousis, Holger Pirk, and George Theodorakis. 2018b. StreamBench. https://github.com/lsds/StreamBench. [Online; accessed 31.5.2019].
[59]
Holger Pirk, Oscar Moll, Matei Zaharia, and Sam Madden. 2016. Voodoo - a Vector Algebra for Portable Database Performance on Modern Hardware. In PVLDB, Vol. 9. VLDB Endowment, 1707--1718.
[60]
Bogdan Rua ducanu, Peter Boncz, and Marcin Zukowski. 2013. Micro adaptivity in vectorwise. In SIGMOD. ACM, 1231--1242.
[61]
Jun Rao, Hamid Pirahesh, C Mohan, and Guy Lohman. 2006. Compiled query execution engine using JVM. In ICDE. IEEE.
[62]
Kenneth A Ross. 2004. Selection conditions in main memory. TODS, Vol. 29, 1 (2004), 132--161.
[63]
Michael Stillger, Guy M Lohman, Volker Markl, and Mokhtar Kandil. 2001. LEO-DB2's learning optimizer. In PVLDB, Vol. 1. 19--28.
[64]
Kanat Tangwongsan, Martin Hirzel, Scott Schneider, and Kun-Lung Wu. 2015. General incremental sliding-window aggregation. In PVLDB, Vol. 8. VLDB Endowment, 702--713.
[65]
Dan Terpstra, Heike Jagode, Haihang You, and Jack Dongarra. 2010. Collecting performance data with PAPI-C. In Tools for High Performance Computing 2009. Springer, 157--173.
[66]
Ankit Toshniwal, Siddarth Taneja, Amit Shukla, Karthik Ramasamy, Jignesh M Patel, Sanjeev Kulkarni, Jason Jackson, Krishna Gade, Maosong Fu, Jake Donham, et al. 2014. Storm@ twitter. In SIGMOD. ACM, 147--156.
[67]
Jonas Traub, Philipp M. Grulich, Alejandro Rodriguez Cuéllar, Sebastian Breß, Asterios Katsifodimos, Tilmann Rabl, and Volker Markl. 2018. Scotty: Efficient Window Aggregation for out-of-order Stream Processing. In ICDE. IEEE.
[68]
Jonas Traub, Philipp M. Grulich, Alejandro Rodriguez Cuéllar, Sebastian Breß, Asterios Katsifodimos, Tilmann Rabl, and Volker Markl. 2019. Efficient window aggregation with general stream slicing. In EDBT.
[69]
Skye Wanderman-Milne and Nong Li. 2014. Runtime Code Generation in Cloudera Impala. IEEE Data Engineering Bulletin (2014).
[70]
Thomas Willhalm, Nicolae Popovici, Yazan Boshmaf, Hasso Plattner, Alexander Zeier, and Jan Schaffner. 2009. SIMD-scan: Ultra Fast In-memory Table Scan Using On-chip Vector Processing Units. In PVLDB, Vol. 2. VLDB Endowment, 385--394.
[71]
Yingjun Wu and Kian-Lee Tan. 2015. ChronoStream: Elastic stateful stream computation in the cloud. In ICDE. IEEE, 723--734.
[72]
Matei Zaharia, Tathagata Das, Haoyuan Li, Timothy Hunter, Scott Shenker, and Ion Stoica. 2013. Discretized streams: Fault-tolerant streaming computation at scale. In SOSP. ACM, 423--438.
[73]
Steffen Zeuch, Ankit Chaudhary, Bonaventura Del Monte, Haralampos Gavriilidis, Dimitrios Giouroukis, Philipp M. Grulich, Sebastian Breß, Jonas Traub, and Volker Markl. 2020. The NebulaStream Platform for Data and Application Management in the Internet of Things. In CIDR.
[74]
Steffen Zeuch and Johann-Christoph Freytag. 2014. QTM: modelling query execution with tasks. In PVLDB, Vol. 7. VLDB Endowment.
[75]
Steffen Zeuch and Johann-Christoph Freytag. 2015. Selection on modern CPUs. In ADMS. ACM, 5.
[76]
Steffen Zeuch, Bonaventura Del Monte, Jeyhun Karimov, Clemens Lutz, Manuel Renz, Jonas Traub, Sebastian Breß, Tilmann Rabl, and Volker Markl. 2019. Analyzing efficient stream processing on modern hardware. In PVLDB, Vol. 12. VLDB Endowment, 516--530.
[77]
Steffen Zeuch, Holger Pirk, and Johann-Christoph Freytag. 2016. Non-Invasive Progressive Optimization for In-Memory Databases. In PVLDB, Vol. 9. 1659--1670.
[78]
Shuhao Zhang, Bingsheng He, Daniel Dahlmeier, Amelie Chi Zhou, and Thomas Heinze. 2017. Revisiting the Design of Data Stream Processing Systems on Multi-Core Processors. In ICDE. 659--670.
[79]
Shuhao Zhang, Jiong He, Chi Amelie Zhou, and Bingsheng He. 2019. BriskStream: Scaling Stream Processing on Multicore Architectures. In SIGMOD.
[80]
Jingren Zhou, John Cieslewicz, Kenneth A Ross, and Mihir Shah. 2005. Improving database performance on simultaneous multithreading processors. In PVLDB. VLDB Endowment, 49--60.
[81]
Yali Zhu, Elke A Rundensteiner, and George T Heineman. 2004. Dynamic plan migration for continuous queries over data streams. In SIGMOD. ACM, 431--442.

Cited By

View all
  • (2024)POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least ResistanceProceedings of the VLDB Endowment10.14778/3648160.364817517:6(1350-1363)Online publication date: 1-Feb-2024
  • (2024)Query Compilation Without RegretsProceedings of the ACM on Management of Data10.1145/36549682:3(1-28)Online publication date: 30-May-2024
  • (2024)Fault Tolerance Placement in the Internet of ThingsProceedings of the ACM on Management of Data10.1145/36549412:3(1-29)Online publication date: 30-May-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data
June 2020
2925 pages
ISBN:9781450367356
DOI:10.1145/3318464
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2020

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. adaptive query processing
  2. code generation
  3. hardware
  4. mutli-core
  5. query compilation
  6. stream processing

Qualifiers

  • Research-article

Funding Sources

Conference

SIGMOD/PODS '20
Sponsor:

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)130
  • Downloads (Last 6 weeks)12
Reflects downloads up to 17 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least ResistanceProceedings of the VLDB Endowment10.14778/3648160.364817517:6(1350-1363)Online publication date: 1-Feb-2024
  • (2024)Query Compilation Without RegretsProceedings of the ACM on Management of Data10.1145/36549682:3(1-28)Online publication date: 30-May-2024
  • (2024)Fault Tolerance Placement in the Internet of ThingsProceedings of the ACM on Management of Data10.1145/36549412:3(1-29)Online publication date: 30-May-2024
  • (2024)DIBA: A Re-Configurable Stream ProcessorIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.338119236:9(4550-4566)Online publication date: 1-Sep-2024
  • (2024)ML-Based Dynamic Operator-Level Query Mapping for Stream Processing Systems in Heterogeneous Computing Environments2024 IEEE International Conference on Cluster Computing (CLUSTER)10.1109/CLUSTER59578.2024.00027(226-237)Online publication date: 24-Sep-2024
  • (2024)Optimising Queries for Pattern Detection Over Large Scale Temporally Evolving GraphsIEEE Access10.1109/ACCESS.2024.341735212(86790-86808)Online publication date: 2024
  • (2023)Showcasing Data Management Challenges for Future IoT Applications with NebulaStreamProceedings of the VLDB Endowment10.14778/3611540.361158816:12(3930-3933)Online publication date: 1-Aug-2023
  • (2023)Analyzing Vectorized Hash Tables across CPU ArchitecturesProceedings of the VLDB Endowment10.14778/3611479.361148516:11(2755-2768)Online publication date: 24-Aug-2023
  • (2023)BladeDISC: Optimizing Dynamic Shape Machine Learning Workloads via Compiler ApproachProceedings of the ACM on Management of Data10.1145/36173271:3(1-29)Online publication date: 13-Nov-2023
  • (2023)Exploiting Access Pattern Characteristics for Join ReorderingProceedings of the 19th International Workshop on Data Management on New Hardware10.1145/3592980.3595304(10-18)Online publication date: 18-Jun-2023
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media