Foundations and Trends® in Databases > Vol 1 > Issue 1

Adaptive Query Processing

Amol Deshpande, University of Maryland, USA, amol@cs.umd.edu Zachary Ives, University of Pennsylvania, USA, zives@cis.upenn.edu Vijayshankar Raman, IBM Almaden, USA, ravijay@us.ibm.com
 
Suggested Citation
Amol Deshpande, Zachary Ives and Vijayshankar Raman (2007), "Adaptive Query Processing", Foundations and TrendsĀ® in Databases: Vol. 1: No. 1, pp 1-140. http://dx.doi.org/10.1561/1900000001

Published: 08 Aug 2007
© 2007 A. Deshpande, Z. Ives and V. Raman
 
Subjects
Adaptive Query Processing
 

Free Preview:

Article Help

Share

Download Free Copy
In this article:
1. Introduction
2. Background: Conventional Optimization Techniques
3. Foundations of Adaptive Query Processing
4. Adaptive Selection Ordering
5. Adaptive Join Processing: Overview
6. Adaptive Join Processing: History-Independent Pipelined Execution
7. Adaptive Join Processing: History-Dependent Pipelined Execution
8. Adaptive Join Processing: Non-pipelined Execution
9. Summary and Open Questions
Acknowledgments
References

Abstract

As the data management field has diversified to consider settings in which queries are increasingly complex, statistics are less available, or data is stored remotely, there has been an acknowledgment that the traditional optimize-then-execute paradigm is insufficient. This has led to a plethora of new techniques, generally placed under the common banner of adaptive query processing, that focus on using runtime feedback to modify query processing in a way that provides better response time or more efficient CPU utilization.

In this survey paper, we identify many of the common issues, themes, and approaches that pervade this work, and the settings in which each piece of work is most appropriate. Our goal with this paper is to be a "value-add" over the existing papers on the material, providing not only a brief overview of each technique, but also a basic framework for understanding the field of adaptive query processing in general. We focus primarily on intra-query adaptivity of long-running, but not full-fledged streaming, queries. We conclude with a discussion of open research problems that are of high importance.

DOI:10.1561/1900000001
ISBN: 978-1-60198-034-2
160 pp. $110.00
Buy book
 
ISBN: 978-1-60198-035-9
160 pp. $125.00
Buy E-book
Table of contents:
1. Introduction
2. Background: Conventional Optimization Techniques
3. Foundations of Adaptive Query Processing
4. Adaptive Selection Ordering
5. Join Processing: Overview of Chapters 5-7
6. Adaptive Join Processing: History-Independent Pipelined Execution
7. Adaptive Join Processing: History-Dependent Pipelined Execution
8. Adaptive Join Processing: Non pipelined Execution
9. Summary and Open Questions
References

Adaptive Query Processing

Adaptive Query Processing surveys the fundamental issues, techniques, costs, and benefits of adaptive query processing. It begins with a broad overview of the field, identifying the dimensions of adaptive techniques. It then looks at the spectrum of approaches available to adapt query execution at runtime - primarily in a non-streaming context. The emphasis is on simplifying and abstracting the key concepts of each technique, rather than reproducing the full details available in the papers. The authors identify the strengths and limitations of the different techniques, demonstrate when they are most useful, and suggest possible avenues of future research.

Adaptive Query Processing serves as a valuable reference for students of databases, providing a thorough survey of the area. Database researchers will benefit from a more complete point of view, including a number of approaches which they may not have focused on within the scope of their own research.

 
DBS-001