HP Labs Technical Reports

Query Optimization for Parallel Execution

Ganguly, Sumit; Hasan, Waqar; Krishnamurthy, Ravi



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.

Back to Index

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map][Home] [Hewlett-Packard]