Title :
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
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;
Conference_Titel :
Databases, Parallel Architectures and Their Applications,. PARBASE-90, International Conference on
Conference_Location :
Miami Beach, FL
Print_ISBN :
0-8186-2035-8
DOI :
10.1109/PARBSE.1990.77187
