Declustering Spatial Databases on a Multi-Computer Architecture

We present a technique to decluster a spatial access method on a shared-nothing multi-computer architecture [DGS + 90]. We propose a software architecture with the R-tree as the underlying spatial access method, with its non-leaf levels on the 'master-server' and its leaf nodes distributed across the servers. The major contribution of our work is the study of the optimal capacity of leaf nodes, or 'chunk size' (or 'striping unit'): we express the response time on range queries as a function of the 'chunk size', and we show how to optimize it. We implemented our method on a network of workstations, using a real dataset, and we compared the experimental and the theoretical results. The conclusion is that our formula for the response time is very accurate (the maximum relative error was 29%; the typical error was in the vicinity of 10-15%). We illustrate one of the possible ways to exploit such an accurate formula, by examining several 'what-if' scenarios. One major, practical conclusion is that a chunk size of 1 page gives either optimal or close to optimal results, for a wide range of the parameters.