J. Wu, J.-J. Chen, C.-W. Hsueh, and T.-W. Kuo (Taiwan)
Query execution plan, query optimization, approximation algorithm, distributed-memory multiprocessor.
For multiprocessor database systems, the scheduling of query execution plans (QEPs) is to map the physical op erators onto processors and execute them without violating their partial order. In this paper, we propose an algorithm for optimizing the schedule length for a collection of QEPs in a distributed-memory multiprocessor (DMM) database system, called physical operator scheduling (POS) algo rithm. We show that the worst schedule length of the POS algorithm is no more than 3 times the optimal sched ule length. The performance of our proposed algorithms were evaluated for input instances generated based on the TPC benchmark [1] and on a pseudo-random number gen erator. The experimental results show that our proposed scheduling algorithms is significantly outperform previous approaches.
Important Links:
Go Back
