short-paper

Cheetah: Accelerating Database Queries with Switch Pruning

Authors:

Muhammad Tirmazi,

Minlan YuAuthors Info & Claims

SIGCOMM Posters and Demos '19: Proceedings of the ACM SIGCOMM 2019 Conference Posters and Demos

Pages 72 - 74

https://doi.org/10.1145/3342280.3342311

Published: 19 August 2019 Publication History

Abstract

Modern database systems are growing increasingly distributed and struggle to reduce the query completion time with a large volume of data. In this poster, we propose to leverage programmable switches in the network to offload part of the query computation to the switch. While switches provide high performance, they also have many resource and programming constraints that make it hard to implement diverse database queries. To fit in these constraints, we introduce the concept of data pruning - filtering out entries which are guaranteed not to affect the output. The database system then runs the same query, but on the pruned data, which significantly reduces the processing time. We propose a set of pruning algorithms for a variety of queries. We implement our system, Cheetah, on a Barefoot Tofino switch and Spark. Our evaluation on the Berkeley AMPLab benchmark shows up to 3x improvement in the query completion time compared to Apache Spark.

References

[1]

Barefoot Tofino and Tofino 2 Switches. https://www.barefootnetworks.com/products/brief-tofino-2/.

[2]

IBM/Netezza. The Netezza Data Appliance Architecture: A Platform for High Performance Data Warehousing and Analytics, 2011. www.redbooks.ibm.com/abstracts/redp4725.html.

[3]

Andrew Pavlo, Erik Paulson, Alexander Rasin, Daniel J. Abadi, David J. DeWitt, Samuel Madden, Michael Stonebraker. A Comparison of Approaches to Large-Scale Data Analysis. ACM SIGMOD (2009).

Digital Library

[4]

Arasu, A., Blanas, S., Eguro, K., Joglekar, M., Kaushik, R., Kossmann, D., Ramamurthy, R., Upadhyaya, P., and Venkatesan, R. Secure database-as-aservice with cipherbase. In ACM SIGMOD (2013).

Digital Library

[5]

Basat, R. B., Einziger, G., Friedman, R., Luizelli, M. C., and Waisbard, E. Constant time updates in hierarchical heavy hitters. ACM SIGCOMM and CoRR/1707.06778 ( 2017).

Digital Library

[6]

Basat, R. B., Einziger, G., Keslassy, I., Orda, A., Vargaftik, S., and Waisbard, E. Memento: Making sliding windows efficient for heavy hitters. In ACM CoNEXT (2018).

Digital Library

[7]

Basat, R. B., Friedman, R., and Shahout, R. Stream frequency over interval queries. Proceedings of the VLDB Endowment 12, 4 (2018), 433--445.

Digital Library

[8]

Bosshart, P., Gibb, G., Kim, H.-S., Varghese, G., McKeown, N., Izzard, M., Mujica, F., and Horowitz, M. Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN. In SIGCOMM CCR (2013).

Digital Library

[9]

Dang, H. T., Sciascia, D., Canini, M., Pedone, F., and Soulé, R. Netpaxos: Consensus at network speed. In ACM SOSR (2015).

Digital Library

[10]

Dennl, C., Ziener, D., and Teich, J. On-the-fly composition of fpga-based sql query accelerators using a partially reconfigurable module library. In IEEE FCCM (2012).

Digital Library

[11]

Do, J., Kee, Y.-S., Patel, J. M., Park, C., Park, K., and DeWitt, D. J. Query processing on smart ssds: opportunities and challenges. In ACM SIGMOD (2013).

Digital Library

[12]

Harrison, R., Cai, Q., Gupta, A., and Rexford, J. Network-wide heavy hitter detection with commodity switches. In ACM SOSR (2018).

Digital Library

[13]

Huang, Q., Jin, X., Lee, P. P. C., Li, R., Tang, L., Chen, Y.-C., and Zhang, G. Sketchvisor: Robust network measurement for software packet processing. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication (New York, NY, USA, 2017), SIGCOMM '17, ACM, pp. 113--126.

Digital Library

[14]

Jepsen, T., Moshref, M., Carzaniga, A., Foster, N., and Soulé, R. Life in the fast lane: A line-rate linear road. In ACM SOSR (2018).

Digital Library

[15]

Jepsen, T., Moshref, M., Carzaniga, A., Foster, N., and Soulé, R. Packet subscriptions for programmable asics. In HotNets (2018).

Digital Library

[16]

Jin, X., Li, X., Zhang, H., Foster, N., Lee, J., Soulé, R., Kim, C., and Stoica, I. Netchain: Scale-free sub-rtt coordination. In USENIX NSDI (2018).

Digital Library

[17]

Jin, X., Li, X., Zhang, H., Soulé, R., Lee, J., Foster, N., Kim, C., and Stoica, I. Netcache: Balancing key-value stores with fast in-network caching. In ACM SOSP (2017).

Digital Library

[18]

Lerner, A., Hussein, R., Cudre-Mauroux, P., and eXascale Infolab, U. The case for network-accelerated query processing. In CIDR (2019).

[19]

Liu, Z., Ben-Basat, R., Einziger, G., Kassner, Y., Braverman, V., Friedman, R., and Sekar, V. Nitrosketch: Robust and general sketch-based monitoring in software switches. In ACM SIGCOMM (2019).

Digital Library

[20]

Miao, R., Zeng, H., Kim, C., Lee, J., and Yu, M. Silkroad: Making stateful layer-4 load balancing fast and cheap using switching asics. In ACM SIGCOMM (2017).

Digital Library

[21]

Michael Armbrust, Reynold S. Xin, Cheng Lian, Yin Huai, Davies Liu, Joseph K. Bradley, Xiangrui Meng, Tomer Kaftan, Michael J. Franklin, Ali Ghodsi, Matei Zaharia. Spark SQL: Relational Data Processing in Spark. ACM SIGMOD (2015).

Digital Library

[22]

Paul, J., He, J., and He, B. Gpl: A gpu-based pipelined query processing engine. In ACM SIGMOD (2016).

Digital Library

[23]

Ran Ben Basat, Xiaoqi Chen, Gil Einzinger, Ori Rottenstreich. Efficient Measurement on Programmable Switches Using Probabilistic Recirculation. In IEEE ICNP (2018).

[24]

Reynold Xin and Matei Zaharia. Lessons from Running Large Scale Spark Workloads. https://www.slideshare.net/databricks/large-scalesparktalk.

[25]

Sukhwani, B., Min, H., Thoennes, M., Dube, P., Iyer, B., Brezzo, B., Dillenberger, D., and Asaad, S. Database analytics acceleration using fpgas. In PACT (2012).

Digital Library

[26]

Thusoo, A., Shao, Z., Anthony, S., Borthakur, D., Jain, N., Sen Sarma, J., Murthy, R., and Liu, H. Data warehousing and analytics infrastructure at facebook. In ACM SIGMOD (2010).

Digital Library

[27]

Woods, L., István, Z., and Alonso, G. Ibex: an intelligent storage engine with support for advanced sql offloading. VLDB (2014).

Digital Library

[28]

Yang, T., Jiang, J., Liu, P., Huang, Q., Gong, J., Zhou, Y., Miao, R., Li, X., and Uhlig, S. Elastic sketch: Adaptive and fast network-wide measurements. In Proc. of ACM SIGCOMM (2018).

Digital Library

[29]

Yu, M., Jose, L., and Miao, R. Software defined traffic measurement with opens-ketch. In Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation (Berkeley, CA, USA, 2013), nsdi'13, USENIX Association, pp. 29--42.

Digital Library

Cited By

Jepsen TLerner APedone FSoulé RCudré-Mauroux P(2021)In-network support for transaction triagingProceedings of the VLDB Endowment10.14778/3461535.346155114:9(1626-1639)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.14778/3461535.3461551
Mustard CGoswami SGharavi NNider JBeschastnikh IFedorova AWassermann BMalka MChidambaram VRaz D(2021)JumpgateProceedings of the 14th ACM International Conference on Systems and Storage10.1145/3456727.3463770(1-12)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1145/3456727.3463770
Tirmazi MBen Basat RGao JYu MMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Cheetah: Accelerating Database Queries with Switch PruningProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389698(2407-2422)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389698
Show More Cited By

Index Terms

Cheetah: Accelerating Database Queries with Switch Pruning
1. Networks
  1. Network algorithms
    1. Data path algorithms

Recommendations

Cheetah: Accelerating Database Queries with Switch Pruning
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data

Modern database systems are growing increasingly distributed and struggle to reduce query completion time with a large volume of data. In this paper, we leverage programmable switches in the network to partially offload query computation to the switch. ...
Precise Time-synchronization in the Data-Plane using Programmable Switching ASICs
SOSR '19: Proceedings of the 2019 ACM Symposium on SDN Research

Current implementations of time synchronization protocols (e.g. PTP) in standard industry-grade switches handle the protocol stack in the slow-path (control-plane). With new use cases of in-network computing using programmable switching ASICs, global ...
SEPT: an efficient skyline join algorithm on massive data

Skyline join is an important operation in many applications to return all join tuples that are not dominated by any other join tuples. It is found that the existing algorithms cannot process skyline join on massive data efficiently. This paper presents ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM Posters and Demos '19: Proceedings of the ACM SIGCOMM 2019 Conference Posters and Demos

August 2019

183 pages

ISBN:9781450368865

DOI:10.1145/3342280

Copyright © 2019 ACM.

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 ACM 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

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 August 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper
Research
Refereed limited

Conference

SIGCOMM '19

Sponsor:

SIGCOMM

SIGCOMM '19: ACM SIGCOMM 2019 Conference

August 19 - 23, 2019

Beijing, China

Acceptance Rates

SIGCOMM Posters and Demos '19 Paper Acceptance Rate 62 of 102 submissions, 61%;

Overall Acceptance Rate 92 of 158 submissions, 58%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
353
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jepsen TLerner APedone FSoulé RCudré-Mauroux P(2021)In-network support for transaction triagingProceedings of the VLDB Endowment10.14778/3461535.346155114:9(1626-1639)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.14778/3461535.3461551
Mustard CGoswami SGharavi NNider JBeschastnikh IFedorova AWassermann BMalka MChidambaram VRaz D(2021)JumpgateProceedings of the 14th ACM International Conference on Systems and Storage10.1145/3456727.3463770(1-12)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1145/3456727.3463770
Tirmazi MBen Basat RGao JYu MMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Cheetah: Accelerating Database Queries with Switch PruningProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389698(2407-2422)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389698
Basat REinziger GTayh B(2020)Cooperative Network-wide Flow Selection2020 IEEE 28th International Conference on Network Protocols (ICNP)10.1109/ICNP49622.2020.9259395(1-11)Online publication date: 13-Oct-2020
https://doi.org/10.1109/ICNP49622.2020.9259395

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents