|
Vol: 53(67) No: 3 / September 2008 Heuristics for Pipelined Parallelism Scheduling Problem in Parallel Query Optimization Carmen Odubăşteanu Department of Computer Science, “POLITEHNICA” University of Bucharest, Spl. Independentei 313, 77206 Bucharest, Romania, e-mail: carmen_od@yahoo.com Călin Munteanu Department of Automatics and Industrial Information,“POLITEHNICA” University of Bucharest, Spl. Independentei 313, 77206 Bucharest, Romania, e-mail: mc_aurel@yahoo.com Catalin Tudose ITC Networks, Calea Floreasca 167, Bucharest, Romania, e-mail: catalin_tudose@gmail.com Keywords: parallel databases, query optimization, pipeline scheduling Abstract Parallel query optimization is an important problem in the area of complex parallel database systems. To reduce the complexity of this optimization problem, some researchers have used a two-phase approach: join ordering and query rewriting followed by parallelization and scheduling. This paper presents seven heuristics for pipelined scheduling problem which consist in finding a schedule for the Pipelined Operator Tree (POT) that minimizes the total response time. This problem has been shown to be NP-hard. References [1] Chekuri, C., Hasan, W., and Motwani, R.,Scheduling Problems in Parallel Query Optimization, In Proceedings of Fourteenth ACM SIGACT-SIGMODSIGART Symposium on Principle of Database Systems, pp: 255-265, San Joes, California,May 1995. [2] Dewitt, D.J., and Gray, J, Parallel Database Systems: The Future of High Performance Database Systems, Communication of ACM, 35(6), pp:85-98, June 1992. [3] Florescu, D., Hasan, W., and Valdurize, P., Open Issues in Parallel Query Optimization, Sigmod Record, 25(3), pp:28-33, Sept. 1996. [4] Garey, M.R. and Johnson, D.S., Computers and Intractability. W.H. Freeman and Company, 1979 [5] Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G., Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey. Annals of Discrete Mathematics, 5:287-326, 1979. [6] Hasan,W., Optimization of SQL Queries for Parallel Machines, PhD. Thesis, Stanford University, Department of Computer Science, Dec. 1996. [7] Hasan, W., and Motwani, R., Optimization Algorithms for Exploiting the Parallelism, Communication Tradeoff in Pipelined Parallelism, In Proceedings of 20th International Conference on VLDB, pp:36-47, Santigo, Chile, September 1994. [8] Hong, W., Parallel Query Processing Using Shared Memory Multiprocessors and Disk Arrays, PhD.Thesis, University of California, Berkeley, Department of Computer Science, Aug. 1992. [9] Odubăşteanu, C., Paralelizarea operatiunilor de interogare a bazelor de date. Algoritmi, Research report, may 2005. [10] Odubăşteanu, C., Experimente asupra unor algoritmi paraleli pentru interogarea bazelor de date, Research report, june 2005. |