«Abstract of “ Query Performance Prediction for Analytical Workloads ” by Jennie Duggan, Ph.D., Brown University, May 2013 Modeling the complex ...»
of “ Query Performance Prediction
for Analytical Workloads ” by Jennie Duggan, Ph.D., Brown University, May 2013
Modeling the complex interactions that arise when query workloads share computing
resources and data is challenging albeit critical for a number of tasks such as Quality of Service (QoS) management in the emerging cloud-based database platforms,
eﬀective resource allocation for time-sensitive processing tasks, and user-experience
management for interactive systems. In our work, we develop practical models for query performance prediction (QPP) for heterogeneous, concurrent query workloads in analytical databases.
Speciﬁcally, we propose and evaluate several learning-based solutions for QPP.
We ﬁrst address QPP for static workloads that originate from well-known query classes. Then, we propose a more general solution for dynamic, ad hoc workloads.
Finally, we address the issue of generalizing QPP for diﬀerent hardware platforms such as those available from cloud-service providers.
Our solutions use a combination of isolated and concurrent query execution samples, as well as new query workload features and metrics that can capture how diﬀerent query classes behave for various levels of resource availability and contention. We implemented our solutions on top of PostgreSQL and evaluated them experimentally by quantifying their eﬀectiveness for analytical data and workloads, represented by the established benchmark suites TPC-H and TPC-DS. The results show that learning-based QPP can be both feasible and eﬀective for many static and dynamic workload scenarios.
Query Performance Prediction for Analytical Workloads by Jennie Duggan B.Sc., Rensselaer Polytechnic Institute; Troy, NY, 2003 Sci.M., Brown University; Providence, RI, 2009 A dissertation submitted in partial fulﬁllment of the requirements for the degree of Doctor of Philosophy in The Department of Computer Science at Brown University
PROVIDENCE, RHODE ISLANDMay 2013 c Copyright 2013 by Jennie Duggan This dissertation by Jennie Duggan is accepted in its present form by The Department of Computer Science as satisfying the dissertation requirement for the degree of Doctor of Philosophy.
Date U˘ur Cetintemel, Ph.D., Advisor g¸ Recommended to the Graduate Council Date Olga Papaemmanouil, Ph.D., Reader Brandeis University Date Eliezer Upfal, Ph.D., Reader Date Stanley Zdonik, Ph.D., Reader Approved by the Graduate Council Date
I would ﬁrst like to acknowledge Ugur Cetintemel. He has been an incredibly insightful and supportive advisor over the years. Ugur has tirelessly helped me navigate the ups and downs of the research process. His gift for explaining data management at both the high and detailed levels is both inspiring and instructive. His inimitable way of identifying compelling and high impact research problems has also made this journey possible.
I would also like to thank Olga Papaemmanouil. She has taught me how to peel the onion of the grad student experience from our years as oﬃcemates to her present post as an excellent professor at Brandeis. I learned how to drill deeply into research problems from her and she given me invaluable advice about how to convey my ideas into an accessible paper.
Eli Upfal has also been integral to my PhD odyssey. I am very grateful to him for all that he has done to teach me how to think through diﬃcult problems. Eli routinely demonstrates how to solve problems both elegantly and pragmatically.
Stan Zdonik has also served as an excellent role model for me. I am thankful for all of the times where he has given me feedback for my research. He has this great ability to rapidly understand and either poke holes or dramatically improve my initial ideas.
iv Roberto Tamassia has also been an inﬂuential mentor to me. In TAing his class I have learned so much about how to instruct students and excite them about my research. Roberto also taught me about how to navigate the department during my tenure as FGL. His can-do attitude is very inspiring.
The Brown Data Management group has also been an integral part of this process. I have been fortunate enough to have a wonderful set of colleagues including Yanif Ahmad, Tingjian Ge, Jeong-Hyon Hwang, Alex Rasin, Mert Akdere, Nathan Backman, Hideaki Kimura, Andy Pavlo and Justin Debrebant. Working with them has enriched my experience in this department and I am grateful for the opportunity.
I have also been lucky enough to have a great circle of friends around Brown CS.
The experience would not have been the same without Irina Calciu, Jason Pacheco, Micha Elsner, Steve Gomez and Yossi Lev. They provided a much needed sounding board through this intense time.
I would also like to thank my family for their continued support. My parents, Julie and John, and sisters Sarah and Katherine have spent years listening to me talk about my research and for that I am appreciative.
Finally I thank Matthew Duggan, my husband. His tireless support of this endeavor made so much of it possible. He has been patient through countless weekends of deadlines and very encouraging through the rough parts. I dedicate this dissertation to you, my love!
Introduction Concurrent query execution facilitates improved resource utilization and aggregate throughput, while making it a challenge to accurately predict individual query performance. Modeling the performance impact of complex interactions that arise when multiple queries share computing resources and data is diﬃcult albeit critical for a number of tasks such as Quality of Service (QoS) management in the emerging cloudbased database platforms, eﬀective resource allocation for time-sensitive processing tasks, and user experience management for interactive database systems.
Consider a cloud-based database-as-a-service platform for data analytics. The service provider would negotiate service level agreements (SLAs) with its users. Such SLAs are often expressed in terms of QoS (e.g., latency, throughput) requirements for various query classes, as well as penalties that kick in if the QoS targets are violated. The service provider has to allocate suﬃcient resources to user queries to avoid such violations, or else face consequences in the form of lost revenue and damaged reputation due to unhappy customers. Thus, it is important to be able to accurately predict the run-time of an incoming query on the available machines, as well as its impact on the existing queries, so that the scheduling of the query does not lead to any QoS violations. The service provider may have to scale up and allocate more cloud resources if it deems that existing resources are insuﬃcient to accommodate the incoming query.
Concurrent query performance prediction (cQPP) is relevant in many contexts.
We start by examining it broadly for analytical queries. We consider two approaches:
interaction and resource modeling. Next we extend this work to support distributed OLAP queries. Finally, we explore two approaches to OLTP throughput prediction.
1.1 Modeling Query Performance for Static Work
In our ﬁrst section, we address the performance prediction problem for analytical concurrent query workloads. Speciﬁcally, we study the following problem: ”Given a collection of queries q1, q2, q3,..., qn, concurrently executing on the same machine at arbitrary stages of their execution, predict when each query will ﬁnish its execution.” We assume that all queries are derived from a set of known query classes (e.g., instances of TPC-H query templates) and that they are mostly I/O bound (e.g., typical TPC-H queries).
We propose a two-phase solution for this problem.
1. (Model building) We build a composite, multivariate regression model that captures the execution behavior of concurrent queries as they go through distinct query mixes. We use this model to predict the execution speed for each query in a given concurrent workload.
2. (Timeline analysis) We analyze the execution timeline of the workload to predict the termination points for individual queries. This timeline analysis starts by predicting the ﬁrst query to complete and then repeatedly performs prediction for the remaining queries. The timeline can be either real-time or have access to a queue for batch-oriented planning.
One of our key ideas is to use Buﬀer Access Latency (BAL) as an eﬀective means to both capture the execution speed of a query as well as to quantify the performance impact of concurrently running queries. Our ﬁrst regression model uses the average BAL of the query execution to accurately predict runtimes of individual queries when run concurrently. We call this model ”BAL to Latency” (B2L).
While it is not tractable to sample how much BAL is aﬀected for all possible concurrent query combinations, we show that capturing only the ﬁrst- and secondorder eﬀects, which can be obtained by sampling isolated and pairwise-concurrent query runs, is suﬃcient to yield good predictions. Our second regression model, therefore, uses the base BAL for a query q (obtained from the isolated run of q), other queries in the mix, delta BALs (obtained from pairwise-concurrent runs for the concurrent queries in the mix) and limited higher multiprogramming level sampling to predict the change in average BAL for q. We refer to this multivariate regression model as ”BAL to concurrent BAL” (B2cB). As a ﬁnal step, we compose B2cB and B2L to obtain execution latency predictions for queries in the concurrent mix.
Finally, we adapt this system to support changing workloads by calculating incremental predictions of the execution latency for discrete mixes as they occur. When an incoming query is added to a mix we project how it will impact the currently running queries and estimate the execution latency we can expect for the new addition.
This technique also allows us to dynamically correct some of our previous estimates by re-evaluating with each scheduling decision. It can also allow for batch-based resource planning by modeling a larger queue of queries in our scheduling.
1.2 Query Performance Prediction for Dynamic
In our second section, we explore the idea of a more generalized concurrency model based on allocating speciﬁc resources for each query as we schedule it. This approach will allow us to model concurrency with a much lighter training phase. Concurrent query execution allows users to decrease the time required for a batch of queries [5, 8] in analytical workloads. When several queries execute simultaneously, hardware resources can be better used by exploiting parallelism. At the same time, concurrent execution raises a number of challenges, including predicting how interleaving queries will aﬀect each other’s rate of progress. As multiple queries compete for hardware resources, their interactions may be positive, neutral, or negative . For example, a positive interaction may occur if two queries share a large table scan: one query may pre-fetch data for the other and they both enjoy a modest speedup. In contrast, if two queries access disjoint data and are I/O-bound, they may slow each other down by a factor of two or more. Judicious scheduling of concurrent queries can signiﬁcantly impact the completion time of individual mix members as well as the entire batch .
Concurrent query execution allows users to decrease the time required for a batch of queries [5, 8] in analytical workloads. When several queries execute simultaneously, hardware resources can be better used by exploiting parallelism. At the same time, concurrent execution raises a number of challenges, including predicting how interleaving queries will aﬀect each other’s rate of progress. As multiple queries compete for hardware resources, their interactions may be positive, neutral, or negative .
For example, a positive interaction may occur if two queries share a large table scan:
one query may pre-fetch data for the other and they both enjoy a modest speedup.
In contrast, if two queries access disjoint data and are I/O-bound, they may slow each other down by a factor of two or more. Judicious scheduling of concurrent queries can signiﬁcantly impact the completion time of individual mix members as well as the entire batch .
Accurate concurrent query performance prediction (cQPP) stands to beneﬁt a variety of applications. This knowledge would allow system administrators to make better scheduling decisions for large batches of queries . With cQPP, cloud-based provisioning would be able to make more informed deployment plans [45, 1]. Performance prediction under concurrency can also create more reﬁned query progress indicators by analyzing in real time how physical resource availability aﬀects a query’s estimated completion time. Moreover, accurate cQPP could also enable query optimizers to create interaction-aware execution plans.
Because of its important applications, there has been signiﬁcant recent work on cQPP, which has primarily focused on static workloads [5, 23]. These solutions predict models on well-deﬁned sets of query templates where interactions within the workload must be sampled before predictions may be produced. Furthermore, the sampling requirements for these approaches grow exponentially in proportion to the complexity of their workloads, limiting their viability in real-world deployments. In this work, we propose a more general solution to target dynamic or ad hoc workloads, where new templates may be executed with queries from a well-known workload.
We create predictions for these unseen templates without the requirement to sample their interactions with our workload. In doing so, we retain the beneﬁts of the prior work, while accommodating unseen or changing workloads. Thus, this approach dramatically simpliﬁes the process of supporting unpredictable or evolving user requirements, which are present in many exploration-oriented database applications including science, engineering and business.