Optimization of response time in parallel pipelined n-joins

Author

Roussopoulos, Nick ; Tong, Li

Author_Institution

Dept. of Comput. Sci., Maryland Univ., College Park, MD, USA

fYear

1990

fDate

7-9 Mar 1990

Firstpage

496

Lastpage

498

Abstract

The optimization of the response time in a parallel pipelined join of n relations is formally defined and analyzed. Multiple data-flow streams in the pipeline are captured in a parallel processing tree (PPT) that models both the parallel and the sequential aspects of the pipeline. An optimal PPT achieves minimal first-page response time by balancing the data flow in the pipeline. It is shown that the optimal PPT problem is NP-complete and that only for a very limited set of queries can one obtain optimal PPT. The authors then provide heuristic algorithms for tree and nontree queries that construct a suboptimal PPT. The dynamic feature of the PPT is developed. Experiments have been conducted to verify the performance of the PPT obtained by the heuristic algorithm

Keywords

distributed databases; optimisation; parallel processing; trees (mathematics); NP-complete; heuristic algorithms; multiple data flow streams; nontree queries; optimization; parallel pipelined n-joins; parallel processing tree; response time; tree queries; Computer science; Delay; Educational institutions; Heuristic algorithms; Multiprocessing systems; Noise measurement; Parallel processing; Pipeline processing; Query processing; Tree graphs;

fLanguage

English

Publisher

ieee

Conference_Titel

Databases, Parallel Architectures and Their Applications,. PARBASE-90, International Conference on

Conference_Location

Miami Beach, FL

Print_ISBN

0-8186-2035-8

Type

conf

DOI

10.1109/PARBSE.1990.77187

Filename

77187