article

Optimization of query streams using semantic prefetching

Authors:

Ivan T. Bowman,

Kenneth SalemAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 30, Issue 4

Pages 1056 - 1101

https://doi.org/10.1145/1114244.1114250

Published: 01 December 2005 Publication History

Abstract

Streams of relational queries submitted by client applications to database servers contain patterns that can be used to predict future requests. We present the Scalpel system, which detects these patterns and optimizes request streams using context-based predictions of future requests. Scalpel uses its predictions to provide a form of semantic prefetching, which involves combining a predicted series of requests into a single request that can be issued immediately. Scalpel's semantic prefetching reduces not only the latency experienced by the application but also the total cost of query evaluation. We describe how Scalpel learns to predict optimizable request patterns by observing the application's request stream during a training phase. We also describe the types of query pattern rewrites that Scalpels cost-based optimizer considers. Finally, we present empirical results that show the costs and benefits of Scalpel's optimizations.

References

[1]

Bernstein, P. A., Pal, S., and Shutt, D. 1999. Context-based prefetch for implementing objects on relations. In Proceedings of the 25th International Conference on Very Large Databases. Morgan Kaufmann, San Francisco, CA, 327--338.

Digital Library

[2]

Bowman, I. T. 2005. Scalpel: Optimizing query streams using semantic prefetching. Ph.D. dissertation, University of Waterloo.

Digital Library

[3]

Fegaras, L. and Maier, D. 2000. Optimizing object queries using an effective calculus. ACM Trans. Database Syst. 25, 4, 457--516.

Digital Library

[4]

Fernandez, M., Morishima, A., and Suciu, D. 2001. Efficient evaluation of XML middle-ware queries. In Proceedings of the ACM SIGMOD International Conference on the Management of Data. ACM, New York, 103--114.

Digital Library

[5]

Florescu, D., Levy, A. Y., Suciu, D., and Yagoub, K. 1999. Optimization of run-time management of data intensive web-sites. In Proceedings of the 25th International Conference on Very Large Databases. Morgan-Kaufmann, San Francisco, CA, 627--638.

Digital Library

[6]

Galindo-Legaria, C. and Joshi, M. 2001. Orthogonal optimization of subqueries and aggregation. In SIGMOD '01: Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data. ACM, New York, 571--581.

Digital Library

[7]

International Standards Organization. 1999. Database Language SQL---Part 2: Foundation (SQL/Foundation). International Standards Organization.

[8]

Mayr, T. and Seshadri, P. 1999. Client-site query extensions. In Proceedings of the ACM SIGMOD International Conference on the Management of Data (Philadelphia, PA). ACM New York.

Digital Library

[9]

Rahal, A., Zhu, Q., and Larson, P.-Å. 2004. Evolutionary techniques for updating query cost models in a dynamic multidatabase environment. VLDB J. 13, 2, 162--176.

Digital Library

[10]

Sellis, T. K. 1988. Multiple-query optimization. ACM Trans. Database Syst. 13, 1, 23--52.

Digital Library

[11]

Seshadri, P., Pirahesh, H., and Leung, T. Y. C. 1996. Complex query decorrelation. In Proceedings of the 12th International Conference on Data Engineering (Washington, DC). IEEE Computer Society Press, Los Alamitos, CA, 450--458.

Digital Library

[12]

Shanmugasundaram, J., Shekita, E., Barr, R., Carey, M., Lindsay, B., Pirahesh, H., and Reinwald, B. 2001. Efficiently publishing relational data as XML documents. VLDB J. 10, 2--3, 133--154.

Digital Library

[13]

Simader, D. 2004. SQL Ledger Accounting: User Guide and Reference Manual for Version 2.2.

[14]

Yao, Q. and An, A. 2003. Using user access patterns for semantic query caching. In Proceedings of the 14th International Conference on Database and Expert Systems Applications (Prague, Czech Republic).

[15]

Zhu, Q. 1995. Estimating local cost parameters for global query optimization in a multidatabase system. Ph.D. dissertation, University of Waterloo.

Digital Library

Cited By

Muse BNafi KKhomh FAntoniol G(2024)Data-access performance anti-patterns in data-intensive systemsEmpirical Software Engineering10.1007/s10664-024-10535-829:6Online publication date: 29-Aug-2024
https://dl.acm.org/doi/10.1007/s10664-024-10535-8
Holm JChiariotti FKalør ASoret BPedersen TPopovski P(2023)Goal-Oriented Scheduling in Sensor Networks With Application Timing AwarenessIEEE Transactions on Communications10.1109/TCOMM.2023.328225671:8(4513-4527)Online publication date: Aug-2023
https://doi.org/10.1109/TCOMM.2023.3282256
Chen YTong WFeng DWang Z(2022)CoraFuture Generation Computer Systems10.1016/j.future.2021.11.023129:C(331-346)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.future.2021.11.023
Show More Cited By

Index Terms

Optimization of query streams using semantic prefetching
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database transaction processing
      2. Parallel and distributed DBMSs

Recommendations

Optimization of query streams using semantic prefetching
SIGMOD '04: Proceedings of the 2004 ACM SIGMOD international conference on Management of data

Streams of relational queries submitted by client applications to database servers contain patterns that can be used to predict future requests. We present the Scalpel system, which detects these patterns and optimizes request streams using context-...
Stealth prefetching
Proceedings of the 2006 ASPLOS Conference

Prefetching in shared-memory multiprocessor systems is an increasingly difficult problem. As system designs grow to incorporate larger numbers of faster processors, memory latency and interconnect traffic increase. While aggressive prefetching ...
Stealth prefetching
ASPLOS XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems

Prefetching in shared-memory multiprocessor systems is an increasingly difficult problem. As system designs grow to incorporate larger numbers of faster processors, memory latency and interconnect traffic increase. While aggressive prefetching ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 30, Issue 4

Special Issue: SIGMOD/PODS 2004

December 2005

241 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/1114244

Issue’s Table of Contents

Copyright © 2005 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2005

Published in TODS Volume 30, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
1,037
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Muse BNafi KKhomh FAntoniol G(2024)Data-access performance anti-patterns in data-intensive systemsEmpirical Software Engineering10.1007/s10664-024-10535-829:6Online publication date: 29-Aug-2024
https://dl.acm.org/doi/10.1007/s10664-024-10535-8
Holm JChiariotti FKalør ASoret BPedersen TPopovski P(2023)Goal-Oriented Scheduling in Sensor Networks With Application Timing AwarenessIEEE Transactions on Communications10.1109/TCOMM.2023.328225671:8(4513-4527)Online publication date: Aug-2023
https://doi.org/10.1109/TCOMM.2023.3282256
Chen YTong WFeng DWang Z(2022)CoraFuture Generation Computer Systems10.1016/j.future.2021.11.023129:C(331-346)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.future.2021.11.023
Zhang JJiang B(2021)A kind of Metadata Prefetch Method for Distributed File System2021 International Conference on Big Data Analysis and Computer Science (BDACS)10.1109/BDACS53596.2021.00033(115-121)Online publication date: Jun-2021
https://doi.org/10.1109/BDACS53596.2021.00033
Shao SQiu ZYu XYang WJin GXie TWu X(2020)Database-Access Performance Antipatterns in Database-Backed Web Applications2020 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME46990.2020.00016(58-69)Online publication date: Sep-2020
https://doi.org/10.1109/ICSME46990.2020.00016
Abebe MGlasbergen BDaudjee K(2020)DynaMast: Adaptive Dynamic Mastering for Replicated Systems2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00123(1381-1392)Online publication date: Apr-2020
https://doi.org/10.1109/ICDE48307.2020.00123
Kuai SHu YZhao XQin DLi WLi X(2019)A Novel Efficient Query Strategy on HibernateProceedings of the 2019 8th International Conference on Software and Computer Applications10.1145/3316615.3316717(105-108)Online publication date: 19-Feb-2019
https://dl.acm.org/doi/10.1145/3316615.3316717
Chen YLi CLv MShao XLi YXu Y(2019)Explicit Data Correlations-Directed Metadata Prefetching Method in Distributed File SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.292176030:12(2692-2705)Online publication date: 1-Dec-2019
https://doi.org/10.1109/TPDS.2019.2921760
Glasbergen BAbebe MDaudjee K(2018)TutorialProceedings of the 19th International Middleware Conference Tutorials10.1145/3279945.3279946(1-5)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1145/3279945.3279946
Mior MRompf TAlexandrov A(2017)LocomotorProceedings of The 16th International Symposium on Database Programming Languages10.1145/3122831.3122840(1-5)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1145/3122831.3122840
Show More Cited By

View Options

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents