Sumit Ganguly
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.
- 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.Google Scholar
- Bel57.R.E. Bellman. Dynamzc Programmzng. Princeton University Press, 1957.Google Scholar
- CHK+91.T. Connors, W. Hasan, C. Kolovson, M.-A. Neimat, D. Schneider, and K. Wilkinson. The Papyrus integrated data server. In Proceedngs of the F~rst Internatzonal Conference on Parallel and Distmbuted Information Systems, December 1991. Google ScholarDigital Library
- DG90.D.J. DeWitt and J. Gray. Parallel Database Systems' The Future of Database Processing or a Passing Fad? A CM-SIGMOD Record, 19(4):104-112, December 1990. Google ScholarDigital Library
- DGS+90.D.J. DeWitt, S. Ghandeharizadeh, D. Schneider, A. Bricker, It.-I. Hsiao, and R. Rasmussen. The Gamma database machine project. IEEE Transact2ons on Knowledge and Data Engzneer~ng, 2(1), March 1990. Google ScholarDigital Library
- GHK92.S. Ganguly, W. ttasan, and R. Krishnamurthy. Query Optimization for Parallel Execution. Technical report, HP Laboratories, 1992. HPL-DTD-92-3.Google Scholar
- Gra91.J. Gray. The Benchmark Handbook for Database and Transaclzon Processing Systems. Morgan Kaufmann Pubhshers, Inc., 1991. Google ScholarDigital Library
- HS91.W. Hong and M. Stonebraker. Optimization of parallel query execution plans in xprs. In Proceedzngs of the Fzrst InlernalzonaI Conference on Parallel and D2slr~buled Information Systems, December 1991. Google ScholarDigital Library
- 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.Google Scholar
- SAC+79.P. Selinger, M. M. Astrahan, D. D. Chainberlin, R. A. Lorie, and T. G. Price. Access Path Selection in a Relational Database Management System. In Procee&ngs of A CM- SIGMOD Inlernatzonal Conference on Management of Data, 1979. Google ScholarDigital Library
- Sch90.D.A. Schneider. Complex Query Processzng in Multiprocessor Database Machines. PhD thesis, University of Wisconsin--Madison, September 1990. Computer Sciences Technical Report 965. Google ScholarDigital Library
- SD89.D.A. Schneider and D. J. DeWitt. A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment. In A CM SIGMOD, Portland, Oregon, June 1989. Google ScholarDigital Library
Index Terms
- Query optimization for parallel execution
Recommendations
Query optimization for massively parallel data processing
SOCC '11: Proceedings of the 2nd ACM Symposium on Cloud ComputingMapReduce has been widely recognized as an efficient tool for large-scale data analysis. It achieves high performance by exploiting parallelism among processing nodes while providing a simple interface for upper-layer applications. Some vendors have ...
Query optimization for parallel execution
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 ...
Exploring Query Optimization in Programming Codes by Reducing Run-Time Execution
COMPSAC '10: Proceedings of the 2010 IEEE 34th Annual Computer Software and Applications ConferenceObject querying is an abstraction of operations over collections, whereas manual implementations are performed at low level which forces the developers to specify how a task must be done. Some object-oriented languages allow the programmers to express ...
Comments