Web services are becoming a standard method of sharing data and functionality among loosely-coupled systems. We propose a general-purpose Web Service Management System (WSMS) that enables querying multiple web services in a transparent and integrated fashion. In this paper, we consider the problem of query optimization inside a WSMS for Select-Project-Join queries spanning multiple web services. Our main result is an algorithm for optimally arranging the web services in a query into a pipelined execution plan that minimizes the total running time of the query. We also give an algorithm for determining the optimal granularity of data ``chunks'' to be used for each web service call. Experiments with an initial prototype indicate that our algorithms can lead to significant performance improvement over more straightforward techniques.

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 bottleneck) cost incurred by any operator in the plan. In the latter scenario, the cost of a plan is given by the 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^θ), where n is the number of operators, and θ is some positive constant. Finally, under the sum cost metric, for the special case when the selectivity of each operator lies in [e,1-e], we give an algorithm that produces a 2-approximation to the optimal plan but has running time exponential in 1/e.