Scheduling and Processor Allocation for Pipeline Execution of Multijoin Queries

Abstract

In this paper, we explore the scheduling and processor allocation for pipeline execution of multijoin queries. To improve the pipeline execution of hash joins in a multiprocessor system, a cost model is proposed to compute the execution time of a pipeline segment. Based on the model, two heuristic scheduling algorithms that produce a join sequence with shorter execution time for a pipeline segment, are presented . As for processor allocation, we also present two heuristic processor allocation algorithms to make the processors have least idle time. To show the performance of our algorithms, a testbed system has been implemented on a multiprocessor machine, 16 transputers connected with a ring. In our Experiments, LPC_pm has better performance that LPC_sm when the intermediate results of pipeline segments are small. And LIT_stage always performs better than LIT_seg for all cases.