Research And Implementation Of Cache-Conscious Join Algorithm In Spatial Database

As the development of the computer technology, cache is used to bridge the increasing gap between memory and processor. The purpose of the performance optimization has been transferring from the disk/memory level to the memory/Cache level for operations in spatial databases. Spatial Join is one of the most important operations in spatial databases and its efficiency has a direct influence on the performance of the spatial queries. However, most of the traditional spatial joins haven't taken enough consideration in the utilization of Cache and the advantage of parallel computation. Focusing on the utilization of Cache in spatial joins, this dissertation makes scientific researches on the Cache-Conscious join algorithm in spatial database and its implementation in QGIS.Firstly, this dissertation discusses the importance of Cache in computer architecture based on the analysis of different storage levels and the Chip Multi-Processor model. Besides, this paper is engaged in research of the mechanism of different kinds of computing penalties, and the applications of the code locality to the optimization of Cache performance.Secondly, to pack more entires in a node, the paper proposes a cache-conscious version of spatial join algorithm. It compresses MBR keys of spatial objects and quantizes the relative coordinate represention. Comparing with traditional join algorithm, Cache-Conscious join algorithm is proved to be more efficient by running time and Cache access misses or penalties. Besides, experiments are conducted to analyze the impact on spatial join and performance of access to cache with different node sizes.Thirdly, as most of the traditional spatial joins haven't taken enough consideration in the advantage of parallel computation, this dissertation proposes a parallel Cache-Conscious join algorithm based on OpenMP. By distributing a single task to several threads with different scheduling strategies, it enhances the performance of Cache-Conscious join algorithm. Experiments are conducted to prove the improvement and analyze the impact of the number of threads.Finally, a core plugin for BeyonDB database is exploited in QGIS platform. In this prototype system, all the cache-conscious algorithms proposed in the paper are implemented. Several join queries are carried out with different kinds of datasets such as point, line segment, and polygon, which can also be visible in the system.In conclusion, this dissertation discusses the Cache-Conscious join algorithm and its parallel variant, validates the enhancement by experiments and implements the advanced algorithm in QGIS.