Query optimization for parallel execution

ABSTRACT

The decreasing cost of computing makes it economically viable to reduce the response time of decision support queries by using parallel execution to exploit inexpensive resources. This goal poses the following query optimization problem: Minimize response time subject to constraints on throughput, which we motivate as the dual of the traditional DBMS problem. We address this novel problem in the context of Select-Project-Join queries by extending the execution space, cost model and search algorithm that are widely used in commercial DBMSs. We incorporate the sources and deterrents of parallelism in the traditional execution space. We show that a cost model can predict response time while accounting for the new aspects due to parallelism. We observe that the response time optimization metric violates a fundamental assumption in the dynamic programming algorithm that is the linchpin in the optimizers of most commercial DBMSs. We extend dynamic programming and show how optimization metrics which correctly predict response time may be designed.

REFERENCES

• AHY83: P.M.G. Apers, A.R. Hevner, and S.B. Yao. Optimization Algorithms for Distributed Queries. IEEE Transactzon on Software Engineemng, 9(1), 1983.
• Bel57: R.E. Bellman. Dynamzc Programmzng. Princeton University Press, 1957.
• CHK+91: T. Connors , W. Hasan , C. Kolovson , M.-A. Neimat , D. Schneider , K. Wilkinson, The Papyrus integrated data server, Proceedings of the first international conference on Parallel and distributed information systems, p.139-141, December 1991, Miami, Florida, United States
• DG90: David J. DeWitt , Jim Gray, Parallel database systems: the future of database processing or a passing fad?, ACM SIGMOD Record, v.19 n.4, p.104-112, Dec. 1990 [doi>10.1145/122058.122071]
• DGS+90: D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990 [doi>10.1109/69.50905 ]
• GHK92: S. Ganguly, W. ttasan, and R. Krishnamurthy. Query Optimization for Parallel Execution. Technical report, HP Laboratories, 1992. HPL-DTD-92-3.
• Gra91: Jim Gray, Benchmark Handbook: For Database and Transaction Processing Systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• HS91: Wei Hong , Michael Stonebraker, Optimization of parallel query execution plans in XPRS, Proceedings of the first international conference on Parallel and distributed information systems, p.218-225, December 1991, Miami, Florida, United States
• PMC+90: tt Pirahesh, C. Mohan, J. Cheung, T.S. Liu. and P. Selinger. Parallelism in Relational Data Base Systems: Architectural Issues and Design Approaches. Technical report.. IB~I Research Division, September 1990. 1BM Research Report RJ 7724.
• SAC+79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• Sch90: Donovan Alfred Schneider , David J. Dewitt, Complex query processing in multiprocessor database machines, 1990
• SD89: Donovan A. Schneider , David J. DeWitt, A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.110-121, June 1989, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Algorithms, Performance, Theory