Exploiting Inter-Operation Parallelism in XPRS

W. Hong

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M92/3
January 1992

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/ERL-92-3.pdf

In this paper, we study the scheduling and optimization problems of parallel query processing using inter-operation parallelism in a shared-memory environment and propose our solutions for XPRs. We first study the scheduling problem of a set or 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 the tasks whenever necessary. Real performance figures are shown to confirm the effectiveness of our scheduling algorithm. We then revisit the optimization problem of parallel execution plans of a single query and extend our previous results to also consider inter-operation parallelism by introducing a new cost estimation method to the query optimizer based on our scheduling algorithm. *This research was sponsored by the National Science Foundation under contract MIP 8715235.

BibTeX citation:

@techreport{Hong:M92/3,
    Author = {Hong, W.},
    Title = {Exploiting Inter-Operation Parallelism in XPRS},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1992},
    Month = {Jan},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/1927.html},
    Number = {UCB/ERL M92/3},
    Abstract = {In this paper, we study the scheduling and optimization problems of parallel query processing using inter-operation parallelism in a shared-memory environment and propose our solutions for XPRs. We first study the scheduling problem of a set or 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 the tasks whenever necessary.  Real performance figures are shown to confirm the effectiveness of our scheduling algorithm.  We then revisit the optimization problem of parallel execution plans of a single query and extend our previous results to also consider inter-operation parallelism by introducing a new cost estimation method to the query optimizer based on our scheduling algorithm. *This research was sponsored by the National Science Foundation under contract MIP 8715235.}
}

EndNote citation:

%0 Report
%A Hong, W.
%T Exploiting Inter-Operation Parallelism in XPRS
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/ERL M92/3
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/1927.html
%F Hong:M92/3