Exploiting inter-operation parallelism in XPRS

Abstract

In this paper, we study the scheduling and optimization problems of parallel query processing using interoperation parallelism in a shared-memory environment and propose our solutions for XPRS. We first study the scheduling problem of a set of a continuous sequence of independent tasks that are either from a bushy tree plan of a single query or from the plans of multiple queries, and present a clean and simple scheduling algorithm. Our scheduling algorithm achieves maximum resource utilizations by running an IO-bound task and a CPU-bound task in parallel with carefully calculated degrees of parallelism and maintains the maximum resource utilizations by dynamically adjusting the degrees of parallelism of running tasks whenever necessary. Real performance figures are shown to confirm the effectiveness of our scheduling algorithm. We also revisit the optimization problem of parallel execution plans of a single query and extend our previous results to consider inter-operation parallelism by introducing a new cost estimation method to the query optimizer based on our scheduling algorithm.