Adaptive Parallel Query Processing

摘要

The wide availability of clusters of low-cost personal computers (PCs) provides exciting opportunities to leverage on the available raw computing power to perform computationally intensive tasks. Particularly, we are interested in the leveraging of clusters of PC to parallelizing the task of query processing for data integration systems. In the database literature, most parallel query processing techniques focused on a coarse-grained approach towards query processing on multiple processors. Data is often partitioned across multiple processors and operators on each processor operate on a subset of the data. Adaptiveness was primarily achieved by run-time static and dynamic load balancing algorithms. In addition, depending on the type of partitioning technique used, data skew might occur which results in all the data being placed in one partition or execution skew might also occur, and result in all processing taking place on only one processor. In a wide-area environment, these traditional parallel query-processing techniques would not be effective since fluctuations pertinent to such environment are often not considered. Our main contribution lies in the Java implementation of a fine-grained adaptive parallel query processing mechanism that will adapt to these fluctuations in the query environment. We further proposed a new scheduling technique, called Tuple RTT scheduling, which will adapt to these run-time fluctuations and perform load balancing amongst multiple participating processors. Our initial implementation and performance study of the proposed scheduling technique indicates promising results.