Singularities Make Spatial Join Scheduling Hard

It is long known that scheduling relational joins, where relations reside on disk, is NP-hard in general. This result motivated a number of heuristics for scheduling spatial joins, where spatial data are distributed on disk blocks in spatial clusters. Since spatial clustering makes use of the rich structure of Euclidean space, the NP-hardness of relational join scheduling does not imply NP-hardness for spatial join scheduling. We show that indeed for a class of popular spatial clustering techniques used for spatial data structures, an optimum page fetch schedule can be computed in linear time. In full generality, we prove spatial join scheduling to be NP-hard. Our proof makes extensive use of a particular singularity; this leaves room for the development of further efficient scheduling algorithms for interesting spatial data structures. 1 Introduction In databases in general and spatial databases in particular, join processing is one of the most expensive operations. One of the reaso..