Stanford InfoLab Publication Server

Ordering Pipelined Query Operators with Precedence Constraints

Burge, Jen and Munagala, Kamesh and Srivastava, Utkarsh (2005) Ordering Pipelined Query Operators with Precedence Constraints. Technical Report. Stanford.




We consider the problem of optimally arranging a collection of query operators into a pipelined execution plan in the presence of precedence constraints among the operators. The goal of our optimization is to maximize the rate at which input data items can be processed through the pipelined plan. We consider two different scenarios: one in which each operator is fixed to run on a separate machine, and the other in which all operators run on the same machine. Due to parallelism in the former scenario, the cost of a plan is given by the maximum (or {\em bottleneck}) cost incurred by any operator in the plan. In the latter scenario, the cost of a plan is given by the {\em sum} of the costs incurred by the operators in the plan. These two different cost metrics lead to fundamentally different optimization problems: Under the bottleneck cost metric, we give a general, polynomial-time greedy algorithm that always finds the optimal plan. However, under the sum cost metric, the problem is much harder: We show that it is unlikely that any polynomial-time algorithm can approximate the optimal plan to within a factor smaller than $O(n^{\theta})$, where $n$ is the number of operators, and $\theta$ is some positive constant. Finally, under the sum cost metric, for the special case when the selectivity of each operator lies in $[\epsilon,1-\epsilon]$, we give an algorithm that produces a $2$-approximation to the optimal plan but has running time exponential in $1/\epsilon$.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:web services, data streams, query optimization, query processing, pipelined
Subjects:Computer Science > Data Streams
Computer Science > Distributed Systems
Computer Science > Query Processing
Related URLs:Project Homepage
ID Code:705
Deposited By:Import Account
Deposited On:13 Dec 2005 16:00
Last Modified:22 Dec 2008 17:55

Download statistics

Repository Staff Only: item control page