Article

Pipelining in multi-query optimization

Authors:

Nilesh N. Dalvi,

Sumit K. Sanghai,

Prasan Roy,

S. SudarshanAuthors Info & Claims

PODS '01: Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Pages 59 - 70

https://doi.org/10.1145/375551.375561

Published: 01 May 2001 Publication History

Get Access

Abstract

Database systems frequently have to execute a set of related queries, which share several common subexpressions. Multi-query optimization exploits this, by finding evaluation plans that share common results. Current approaches to multi-query optimization assume that common subexpressions are materialized. Significant performance benefits can be had if common subexpressions are pipelined to their uses, without being materialized. However, plans with pipelining may not always be realizable with limited buffer space, as we show. We present a general model for schedules with pipelining, and present a necessary and sufficient condition for determining validity of a schedule under our model. We show that finding a valid schedule with minimum cost is NP-hard. We present a greedy heuristic for finding good schedules. Finally, we present a performance study that shows the benefit of our algorithms on batches of queries from the TPCD benchmark.

References

[1]

Chandra Chekuri, Waqar Hasan, and Rajeev Motwani. Scheduling problems in parallel query optimization. In ACM Symp. on Principles of Database Systems, pages 255-265, 1995.

Digital Library

Google Scholar

[2]

Latha Colby, Richard L. Cole, Edward Haslam, Nasi Jazayeri, Galt Johnson, William J. McKenna, Lee Schumacher, and David Wilhite. Redbrick Vista: Aggregate computation and management. In Intl. Conf. on Data Engineering, 1998.

Digital Library

Google Scholar

[3]

Cormen, Lieserson, and Rivest. Introduction to Algorithms. Prentice-Hall, 1990.

Digital Library

Google Scholar

[4]

Ahmet Cosar, Ee-Peng Lim, and Jaideep Srivastava. Multiple query optimization with depth-first branch-and-bound and dynamic query ordering. In Intl. Conf. on Information and Knowledge Management (CIKM), pages 433-438, 1993.

Digital Library

Google Scholar

[5]

Goetz Graefe. Query evaluation techniques for large databases. ACM Computing Surveys, 25(2):73-170, 1993.

Digital Library

Google Scholar

[6]

Goetz Graefe and William J. McKenna. Extensibility and Search Efficiency in the Volcano Optimizer Generator. In Intl. Conf. on Data Engineering, 1993.

Digital Library

Google Scholar

[7]

Wei Hong. Exploiting inter-operation parallelism in XPRS. In SIGMOD Intl. Conf. on Management of Data, pages 19-28, 1992.

Digital Library

Google Scholar

[8]

Arnon Rosenthal and Upen S. Chakravarthy. Anatomy of a modular multiple query optimizer. In Intl. Conf. Very Large Databases, pages 230-239, 1988.

Digital Library

Google Scholar

[9]

Prasan Roy, S. Seshadri, S. Sudarshan, and S. Bhobhe. Efficient and extensible algorithms for multi-query optimization. In SIGMOD Intl. Conf. on Management of Data, 2000.

Digital Library

Google Scholar

[10]

Timos K. Sellis. Multiple query optimization. ACM Transactions on Database Systems, 13(1):23-52, March 1988.

Digital Library

Google Scholar

[11]

Amit Shukla, Prasad Deshpande, and Jeffrey F. Naughton. Materialized view selection for multidimensional datasets. In Intl. Conf. Very Large Databases, pages 488-499, 1998.

Digital Library

Google Scholar

[12]

K. Tan and H. Lu. Workload scheduling for multiple query processing. In Information Processing Letters, volume 55, pages 251-257, 1995.

Digital Library

Google Scholar

Cited By

View all

Monye SAdeniran Afolalu SAkinwumi AIsioma Monye SOkokpujie IAgbemuko DKayode JBello Aderemi K(2024)Memory Interfacing in Mechatronics Systems: Constraints and Considerations2024 International Conference on Science, Engineering and Business for Driving Sustainable Development Goals (SEB4SDG)10.1109/SEB4SDG60871.2024.10630195(1-9)Online publication date: 2-Apr-2024
https://doi.org/10.1109/SEB4SDG60871.2024.10630195
Yamada HGoda KKitsuregawa M(2023)Nested Loops Revisited Again2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00299(3708-3717)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00299
Nakandala SKumar AIves ZBonifati AEl Abbadi A(2022)Nautilus: An Optimized System for Deep Transfer Learning over Evolving Training DatasetsProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517846(506-520)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517846
Show More Cited By

Index Terms

Pipelining in multi-query optimization
1. Information systems
  1. Data management systems
    1. Database management system engines
    2. Query languages
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query languages (principles)

Recommendations

Pipelining in multi-query optimization
Special issu on PODS 2001

Database systems frequently have to execute a set of related queries, which share several common subexpressions. Multi-query optimization exploits this, by finding evaluation plans that share common results. Current approaches to multi-query ...
Timing optimization via nest-loop pipelining considering code size

Embedded systems have strict timing and code size requirements. Software pipelining is one of the most important optimization techniques to improve the execution time of loops by increasing the parallelism among successive loop iterations. However, ...
Single-Dimension Software Pipelining for Multi-Dimensional Loops
CGO '04: Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization

Traditionally, software pipelining is applied either to theinnermost loop of a given loop nest or from the innermostloop to outer loops. In this paper, we propose a three-stepapproach, called Single-dimension Software Pipelining(SSP), to software ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODS '01: Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

May 2001

301 pages

ISBN:1581133618

DOI:10.1145/375551

Chairman:
Peter Buneman
Univ. of Pennsylvania

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS01

Sponsor:

SIGMOD

SIGMOD/PODS01: ACM SIGMOD International Conference on Management of Data

California, Santa Barbara, USA

Acceptance Rates

PODS '01 Paper Acceptance Rate 26 of 99 submissions, 26%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
682
Total Downloads

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

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Monye SAdeniran Afolalu SAkinwumi AIsioma Monye SOkokpujie IAgbemuko DKayode JBello Aderemi K(2024)Memory Interfacing in Mechatronics Systems: Constraints and Considerations2024 International Conference on Science, Engineering and Business for Driving Sustainable Development Goals (SEB4SDG)10.1109/SEB4SDG60871.2024.10630195(1-9)Online publication date: 2-Apr-2024
https://doi.org/10.1109/SEB4SDG60871.2024.10630195
Yamada HGoda KKitsuregawa M(2023)Nested Loops Revisited Again2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00299(3708-3717)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00299
Nakandala SKumar AIves ZBonifati AEl Abbadi A(2022)Nautilus: An Optimized System for Deep Transfer Learning over Evolving Training DatasetsProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517846(506-520)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517846
Tu YEslami MXu ZCharkhgard H(2022)Multi-Query Optimization Revisited: A Full-Query Algebraic Method2022 IEEE International Conference on Big Data (Big Data)10.1109/BigData55660.2022.10020338(252-261)Online publication date: 17-Dec-2022
https://doi.org/10.1109/BigData55660.2022.10020338
Sioulas PAilamaki ALi GLi ZIdreos SSrivastava D(2021)Scalable Multi-Query Execution using Reinforcement LearningProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452799(1651-1663)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452799
Mhedhbi AKankanamge CSalihoglu S(2021)Optimizing One-time and Continuous Subgraph Queries using Worst-case Optimal JoinsACM Transactions on Database Systems10.1145/344698046:2(1-45)Online publication date: 29-May-2021
https://dl.acm.org/doi/10.1145/3446980
Michiardi PCarra DMigliorini S(2021)Cache-Based Multi-Query Optimization for Data-Intensive Scalable Computing FrameworksInformation Systems Frontiers10.1007/s10796-020-09995-223:1(35-51)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s10796-020-09995-2
Heo SSong SKim BKim H(2020)Sharing-aware Data Acquisition Scheduling for Multiple Rules in the IoT2020 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS48715.2020.00-18(43-55)Online publication date: Apr-2020
https://doi.org/10.1109/RTAS48715.2020.00-18
Giannikis GMakreshanski DAlonso GKossmann D(2014)Shared workload optimizationProceedings of the VLDB Endowment10.14778/2732279.27322807:6(429-440)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.14778/2732279.2732280
Ge XYao BGuo MXu CZhou JWu CXue G(2014)LSShareDistributed and Parallel Databases10.1007/s10619-014-7150-132:4(583-605)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1007/s10619-014-7150-1
Show More Cited By

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.

Cited By

Index Terms

Recommendations

Pipelining in multi-query optimization

Timing optimization via nest-loop pipelining considering code size

Single-Dimension Software Pipelining for Multi-Dimensional Loops