Batch spatial query processing using R-Tree over solid state drives (SSD): Leveraging internal parallelis

Spatial data management has become an integral part of many applications such as Geographic Information Systems (GIS). Range queries are one of the most important queries in spatial databases. Spatial indexing techniques like R-Tree are applied to improve the performance of such queries. Often database system receives multiple range queries, and in order to improve the overall performance, it processes them in batches, considering spatial characteristics of incoming requests. However, this performance of batch processing and operating index structure depend on the underlying storage hardware, such as hard drives (HDD). Database community has spent its valuable time, in past three decades, and energy in optimizing its systems in accordance with HDD features. But, now flash based Solid State Drives (SSDs) are emerging as main storage devices. They have completely different and better performance characteristics compared to HDD. With this new technology, we need to re-think the batch processing of spatial queries. In this work, we propose a new structure of R-Tree nodes for SSDs and based on that develop a general and static allocation-specific batching methods. Both methods avoid the resource contention that occurs due to long data movement time caused by interleaving and improve the overall performance. With our approach of R-Tree node representation, spatial queries can be batched without considering the spatial characteristics of incoming requests. We were able to achieve overall 80% gain in the performance as compared to non-batching methods over SSDs.