Scheduling and Caching in MultiQuery Optimization

Abstract

Database systems frequently have to execute a batch of related queries. Multi-query optimization exploits evalu-ation plans that share common results. Current approaches to multi-query optimization assume there is infinite disk space, and very limited memory space. Pipelining was the only option considered for avoiding expensive disk writes. The availability of fairly large and inexpensive main mem-ory motivates the need to make best use of available main memory for caching shared results, and scheduling queries in a manner that facilitates caching. Pipelining needs to be exploited at the same time. We look at the problem of multi-query optimization tak-ing into account query scheduling, caching and pipelining. We first prove that MQO with either just query scheduling or just caching is NP-complete. We then provide the first known algorithms for the most general MQO problem with scheduling, caching and pipelining. After showing the con-nections of this problem with other traditional scheduling problems and graph theoretic problems we outline heuris-tics for MQO with scheduling, caching and pipelining.