Comparison of LSM Indexing Techniques for Storing Spatial Data

Abstract In the pre-big data era, many traditional databases supported spatial queries via spatial indexes. However, modern applications are seeing a rapid increase of the volume and ingestion rate of spatial data. LSM tree is used by many big data systems as their storage structure in order to support write-intensive large-volume workloads, which are usually only optimized for single-dimensional data. Research has studied how spatial indexes can be supported on LSM systems, but focused mainly on the local index organization, that is, how data is organized inside a single LSM component. In this paper, we study various aspects of LSM spatial indexing, including spatial merge policies, which determine when and how spatial components are merged. We consider three stack-based and one leveled merge policies, which we have implemented on the same big data system Apache AsterixDB. We evaluate the write and read performance on various workloads and discuss our findings and recommendations. A key finding is that Leveled policies are under-performing other stack-based merge policies for most types of spatial workloads.