UW SciDB branch

ArrayStore is a new read-only storage manager for complex, parallel array processing that that is developed in the University of Washington. ArrayStore supports a parallel and complex workload comprising not only range-queries, but also binary operations such as joins and complex user-defined functions.

We made two contributions in this project. First, we examined several storage management and array partitioning strategies to identify which combination is best suited for the array-processing workload above. Second, we developed a new and efficient storage management mechanism that enables parallel processing of operations that must access data from adjacent partitions. The proposed mechanism is called overlap processing.

For example, given a 2D telescope image, astronomers often run user defined functions that extract certain objects such as bright stars or galaxies. Because telescope images can be large, they need to partition these images and distribute them over multiple nodes. Then they run an observation (star) detection query in parallel on top of each partition. But how to detect objects that cross partition boundaries? Such objects can either be detected multiple times, once in each partition where they appear, or we can implement a complex post-processing merge operation that prunes duplicate results. A much nicer solution, however, is to provide each partition with a margin of overlapping data along its boundaries. The challenge, however, is how to select the appropriate amount of data overlap when partitioning the array.

Tuning the system to find the right overlap-size is a difficult task. The overlap-size that is optimum for one workload incurs huge overhead on other workloads. In ArrayStore, I overcome this challenge by introducing a new technique that benefits from multi-layer overlapping strategy with materialized overlap views which is represented in Figure 1. This techniques significantly outperform approaches that do not provide overlap or provide only a pre-defined single overlap layer. Figure 1 shows different overlap execution techniques presented in the ArrayStore project. The overall performance gain when applying the technique that we developed was up to a factor of two for real queries on real data from astronomy and oceanography domains.

After developping ArrayStore, we looked further at efficient strategies for parallel array processing. We examined different types of array operations and reviewed how they can be processed in parallel using two different techniques. The first technique, called merge, consists in partitioning an array, processing the partitions in parallel, then merging the result to reconcile any computations that need to span partition boundary. The second technique, called overlap, consists in partitioning an array into subarrays that overlap by a given number of cells along each dimension. Thanks to this overlap, the array partitions can be processed in parallel without any merge phase.

We studied when each technique can be applied to an array operation. We showed that even for a single array operation a different approach may yield the best performance for different regions of an array. The overall performance of a distributed query is defined by the most time-consuming partition. A hybrid technique can alleviate those worst case scenarios. Following this observation, we developed a new parallel array processing technique that combines the merge and overlap approaches. Our technique enables a parallel array processing system to mix-and-match the merge and overlap techniques within a single operation on an array. We am now working on automating the selection of the best strategy to use.