Adaptive Parallelization of Queries over Dependent Web Service Calls

We have developed a system to process database queries over composed data providing Web services. The queries are transformed into execution plans containing an operator that invokes any Web service for given arguments. A common pattern in these query execution plans is that the output of one Web service call is the input for another, etc. The challenge addressed in this paper is to develop methods to speed up such dependent calls in queries by parallelization. Since Web service calls incur high-latency and message set-up costs, a naive approach making the calls sequentially is time consuming and parallel invocations of the Web service calls should improve the speed. Our approach automatically parallelizes the web service calls by starting separate query processes, each managing a parameterized sub-query, a plan function, for different parameter tuples. For a given query, the query processes are automatically arranged in a multi-level process tree where plan functions are called in parallel. The parallel plan is defined in terms of an algebra operator, FF_APPLYP, to ship in parallel to other query processes the same plan function for different parameters. By using FF_APPLYP we first investigated ways to set up different process trees manually. We concluded from our experiments that the best performing query execution plan is an almost balanced bushy tree. To automatically achieve the optimal process tree we modified FF_APPLYP to an operator AFF_APPLYP that adapts a parallel plan locally in each query process until an optimized performance is achieved. AFF_APPLYP starts with a binary process tree. During execution each query process in the tree makes local decisions to expand or shrink its process sub-tree by comparing the average time to process each incoming tuple. The query execution time obtained with AFF_APPLYP is shown to be close to the best time achieved by manually built query process trees.

I. Introduction

There is a common need to search information supplied by data providing web services that return a set of objects for a given set of parameters without any side effects. For example, consider a query to find USAF Academy's Zip code and the State where it is located. The three different data providing web service calls in this query are GetAllStates [3] to retrieve all the states, GetInfoByState [19] to get all the Zip codes within a given state, and GetPlacesInside [4] to provide all the places having a given Zip code. A naïve implementation of the example query makes 5000 calls sequentially and takes nearly 2400 seconds to execute. The reason is that each web service call incurs high latency and message set-up costs.