Adaptive Query Processing (foundations And Trends(r) In Databases)

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. 1601980345 1 Introduction 12 Query Processing in Relational Database Systems 14 Motivations for AQP 16 Road Map 19 Related Work 19 Background: Conventional Optimization Techniques 20 Query Optimization 20 Choosing an Effective Plan 31 Summary 35 Foundations of Adaptive Query Processing 38 New Operators 39 Adaptivity Loop 46 Post-mortem Analysis of Adaptive Techniques 51 Adaptivity Loop and Post-mortem in Some Example Systems 53 Scope of the Remainder of the Survey 56 Adaptive Selection Ordering 58 Adaptive Greedy 59 Adaptation using Eddies 63 Parallel and Distributed Scenarios 68 Summary 69 Adaptive Join Processing: Overview 72 Adaptive Join Processing: History-Independent Pipelined Execution 76 Pipelined Plans with a Single Driver Relation 76 Pipelined Plans with Multiple Drivers 81 Adaptive Caching (A-Caching) 90 Summary 93 Adaptive Join Processing: History-Dependent Pipelined Execution 96 Corrective Query Processing 97 Eddies with Binary Join Operators 104 Eddies with STAIRs 112 Dynamic Plan Migration in CAPE 117 Summary 118 Adaptive Join Processing: Non-pipelined Execution 120 Plan Staging 121 Mid-Query Reoptimization 122 Query Scrambling 131 Summary and Post-mortem Analysis 132 Summary and Open Questions 136 Trade-Offs and Constraints 136 Adaptive Mechanisms 140 Conclusions and Challenge Problems 141 Acknowledgments 146 References 148 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.