Published Articles >> Table of Contents >> Abstract

18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers   p. 2b
Scheduling of Query Execution Plans in Symmetric Multiprocessor Database Systems
Jun Wu, National Chung Cheng University
Jian-Jia Chen, National Taiwan University
Chih-wen Hsueh, National Chung Cheng University
Tei-Wei Kuo, National Taiwan University

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2004.1302900
Send link to a friend

Abstract
While excellent research results have been proposed for query optimization, little work has been done for the scheduling of query execution plans. This paper targets the optimization problem of the schedule lengths of query execution plans in a symmetric multiprocessor (SMP) database system. We show the NP-hardness of the optimization problem. A critical-path-based algorithm is proposed to minimize the schedule length of a collection of query execution plans. When each query execution plan has a tree or a directed acyclic graph structure, we show that the approximation ratios of our proposed algorithm are 2 and (3 - 2^M), respectively, where M is the number of processors in the system. When the proposed algorithm is adopted for online usages, the competitive ratio of the algorithm is proven being (3 - 2^M). The proposed algorithm is optimal when there is a suf.cient number of processors. The performance of the proposed algorithm is evaluated based on the TPC-C benchmark.
Back to Top Additional Information
Citation:  Jun Wu, Jian-Jia Chen, Chih-wen Hsueh, Tei-Wei Kuo, "Scheduling of Query Execution Plans in Symmetric Multiprocessor Database Systems," ipdps, p. 2b,  18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers,  2004