Query processing in spatial database systems: declustering and clustering techniques (1997)

Range and join queries are the two most important queries in a spatial database system.\nIn spatial query processing, spatial objects are compared with each other using spatial\nrelationships. A spatial range-query is an operation that returns objects from a set of spatial\nobjects which satisfy a spatial predicate with a given range. A spatial join operation\ncombines objects of two or more relations, according to a predicate defined on the spatial\nattributes of the objects. The research question in this thesis concerns how to parallelize\nthe spatial range and join query processing in order to support a high performance spatial\ndatabase application. A spatial query can be parallelized either by function-partitioning\nor by data-part itioning. Data-Partitioning techniques divide the data among different processors\nand then independently execute the sequential algorithm on each processor. Data\npartitioning for the range query operation involves declustering of spatial data, while data\npartitioning for the spatial join involves clustering of spatial data. If the static partitioning\nmethods fail to equally distribute the load among different processors, the load-balance\nmay be improved by redistributing parts of the data to idle processors using Dynamic\nLoad-Balancing (DLB) techniques.\nDeclustering and load-balancing are important issues in the parallelization of rangequery\noperations. The current literature provides efficient methods for declustering spatial\npoint-data. However, there has been little work done towards developing efficient declustering\nmethods for collections of extended objects like chains of line-segments and polygons. In\nthis thesis, we provide a framework for declustering collections of extended spatial objects\nby identifying the following key issues: (i) the work-load metric, (ii) the spatial-extent of\nthe work-load, (iii) the dist_ribution of the work-load over the spatial-extent, and (iv) the\ndeclustering method. We identify and experimentally evaluate alternatives for each of these\nissues. In addition, we also provide a framework for dynamically balancing the load between different\nprocessors. We experimentally evaluate the proposed declustering and load-balancing\nmethods on a distributed memory MIMD machine (Cray T3D) and shared-memory machine\n(SGI Challenge). Experimental results show that the spatial-extent and the work-load metric\nare important issues in developing a declustering method. Experiments also show that\nthe replication of data is usually needed to facilitate dynamic load-balancing, as the cost of\nlocal processing is often less than the cost of data transfer for extended spatial objects. In\naddition, we also show that the effectiveness of dynamic load-balancing techniques can be\nimproved by using declustering methods to determine the subsets of spatial objects to be\ntransferred during run-time.\nA spatial join is often performed in two steps: a filter step and a refinement step. In\nthis thesis, we focus on the refinement step of the spatial join. The refinement step of the\nspatial join takes as input a sequence of pairs of tuples and checks each tuple to see if the\njoin predicate is satisfied for that tuple. This is similar to the join index processing done in\ntraditional relational databases. We develop min-cut graph partitioning based methods for\njoin processing using a join index. We use min-cut graph partitioning as a new heuristic\nfor solving the page access sequence problem for fixed size buffer in sequential systems. We\nshow that the number of page accesses needed to compute a join using join index in a fixed\nbuffer environment is bounded by the sum of sizes of the base relations and the size of\nthe cut-set of the page connectivity graph. Since the min-cut graph partitioning aims to\nminimize the size of t he cut-set, this proposed heuristic is a direct method. Experiments\nwith benchmark data sets show that the graph-partitioning based heuristic out performs\nthe existing methods, particularly when join selectivity is high and buffer space is small.\nIn parallel systems, the join index partitioninig problem to balance the load and to improve\nthe data localization can be modelled as min-cut page connectivity graph partitioning\nproblem. This formulation provides a formal framework for the join index partitioning problem.\nIn addt ion, it also yields superior ·performance over other methods as shown in our\nexperiments with shared-disk architecture for processing benchmark data sets.