Research Projects

Dynamic Scheduling of Query Mixes in QShuffler

Database systems handle concurrent execution of queries of many different types. Often, the interaction of these queries among themselves can impact the performance of the system significantly. However, standard methods of query optimization used by most commercial database systems are based primarily on evaluating the cost of each query in isolation from the rest. QShuffler, a query scheduler, takes into consideration the interaction of different concurrent queries in order to minimize the completion time of a business intelligence workload. Given a large set of queries, it selects good query mixes to send to the database system for execution. As queries complete, QShuffler chooses the next query to add to the current mix by selecting the most expensive query that keeps the overall load below a predefined load threshold.

We looked at the issue of query scheduling from several different angles, and proposed alternative solutions to further improve query scheduling. QShuffler assumes that the optimal number M of concurrent queries is determined in advance. M is treated as a constant throughout scheduling. However, keeping M fixed poses several disadvantages such as the potential for system overload, data-contention thrashing, and resource underutilization. We explored improvements to the scheduling algorithm of QShuffler that allow for a varying number of concurrent queries to be executed in an efficient way. Furthermore, we explored improvements to the performance model used by the QShuffler on-line scheduling algorithm that would allow the model to learn from the query mixes that it has executed (i.e. online learning). By updating the model at runtime, we have the potential to minimize the number of offline samples needed to train the linear regression model. Hence, the amount of time needed to bootstrap the model can be decreased considerably.

QShuffler Architecture
QShuffler Architecture

Publications