An LSM-Tree Index for Spatial Data

Junjun He, Huahui ChenAlgorithms 2022 · OpenReview

TL;DR

This paper introduces the ER-tree, a novel embedded R-tree index designed for Log-Structured Merge-trees (LSM-trees) to efficiently handle spatial data queries. By integrating R-tree indexes directly into LSM-tree's storage components (SSTables) and organizing them hierarchically, the ER-tree significantly improves query performance and reduces read amplification compared to traditional standalone R-tree indexes.

What Problem Does This Paper Address?

LSM-trees are highly efficient for write-heavy workloads due to their sequential disk writing. However, they are primarily designed for key-based lookups and struggle with spatial queries (e.g., finding data within a geographic area). Existing solutions often involve adding separate, "standalone" R-tree indexes. This approach leads to significant "read amplification" – requiring multiple disk accesses to first query the R-tree for a key and then use that key to retrieve the actual data from the LSM-tree. Furthermore, as data grows, these standalone indexes become large and slow, and updates during LSM-tree compactions are costly. This paper aims to bridge this gap by creating a spatial index that is deeply integrated with the LSM-tree's structure, optimizing both query speed and update efficiency.

Methods

The core innovation is the ER-tree (embedded R-tree) index. This is built upon a SER-tree (embedded R-tree on an SSTable), which is an R-tree index constructed directly within each SSTable (a storage component of LSM-trees).

Here's a breakdown of the approach:

  • SER-tree: For each SSTable, an SER-tree is built. This index uses Hilbert curves to map spatial coordinates to keys, allowing spatial data to be stored in a somewhat ordered manner within the SSTable. The SER-tree directly points to data blocks within the SSTable, eliminating the need for a separate lookup for the actual data.
  • ER-tree: The SER-trees from individual SSTables are then organized hierarchically across different levels of the LSM-tree. They are linked together using a double linked list structure, forming the ER-tree. This hierarchical organization allows for efficient traversal and filtering of spatial queries across multiple SSTables.
  • Bottom-up Construction: The SER-trees are built using a bottom-up approach, which is more suitable for static SSTable data and helps minimize Minimum Bounding Rectangle (MBR) overlap, leading to more efficient queries.
  • Index Build Decider (IBD): To manage the overhead of building indexes, an IBD is proposed. It considers the lifetime of an SSTable and the potential query gain versus the build cost to decide whether to create an SER-tree index for a given SSTable.

Datasets

The paper evaluates their proposed ER-tree index using both simulated and real-world datasets:

  • Simulated Datasets: Randomly generated spatial data with varying volumes (1 million, 10 million, and 100 million data points).
  • Real Datasets:
    • Chinese national building data from OpenStreetMap (approx. 2.09 million elements).
  • New York building data from OpenStreetMap (approx. 3.78 million elements).

Key Insights and Ideas

  • Deep Integration is Key: The most significant insight is that embedding the spatial index directly within the LSM-tree's storage units (SSTables) is crucial for overcoming the read amplification problem inherent in standalone secondary indexes.
  • Hilbert Curves for Ordering: Using Hilbert curves to map spatial data to keys within SSTables provides a way to leverage the LSM-tree's inherent ordering for spatial queries.
  • Hierarchical Linking for Scalability: Organizing SER-trees hierarchically and linking them with a double linked list allows the ER-tree to efficiently manage spatial indexes across the entire LSM-tree structure.
  • Trade-offs in Indexing: The introduction of the Index Build Decider (IBD) highlights the practical consideration of balancing the cost of building and maintaining indexes against their performance benefits, especially in dynamic LSM-tree environments.
  • Bottom-up vs. Top-down: The paper argues that a bottom-up construction for SER-trees is more efficient for static SSTable data, leading to better spatial storage and reduced MBR overlap.

Key Results

The experimental results demonstrate the effectiveness of the ER-tree index:

  • Insertion Latency: The ER-tree showed lower insertion latency compared to standalone and hierarchical R-tree indexes, attributed to its more compact index structure built on SSTables.
  • Query Performance:
    • Point Queries: ER-tree achieved significantly better point query performance, with query times being orders of magnitude faster than standalone R-trees, especially as data volume increased. This is because ER-tree performs a single query pass, while others require two.
  • Range Queries: Similar to point queries, ER-tree exhibited superior range query performance across various range lengths and datasets.
  • Circle Queries: ER-tree also outperformed other methods for circle range queries.
  • Space Performance: The ER-tree index showed slightly better space efficiency compared to standalone R-tree indexes, due to its bottom-up construction minimizing wasted space.

Limitations and Future Work

  • Read-Write Workloads: The paper acknowledges that for highly mixed read-write workloads, the constant updates to indexes can still be a concern, though it notes that most LSM-tree structures remain stable, especially at higher levels. Further analysis is suggested for low-level SSTables.
  • SSTable Lifetime Threshold: The ER-tree employs an SSTable lifetime threshold (Tw = 50ms) to avoid building indexes on short-lived SSTables. The optimal value for this threshold might require further tuning.
  • Index Build Decider (IBD): While the IBD is proposed to manage index building costs, its precise implementation and the accuracy of its predictions for Gindex and Lindex would require further empirical validation.
  • Future Work: The paper suggests further analysis for low-level SSTables and potentially exploring more sophisticated strategies for the Index Build Decider. The authors also mention that circular range queries can be extended for KNN queries, hinting at future applications.

Summary updated

Abstract

An LSM-tree (log-structured merge-tree) is a hierarchical, orderly and disk-oriented data storage structure which makes full use of the characteristics of disk sequential writing, which are much better than those of random writing. However, an LSM-tree can only be queried by a key and cannot meet the needs of a spatial query. To improve the query efficiency of spatial data stored in LSM-trees, the traditional method is to introduce stand-alone tree-like secondary indexes, the problem with which is the read amplification brought about by dual index queries. Moreover, when more spatial data are stored, the index tree becomes increasingly large, bringing the problems of a lower query efficiency and a higher index update cost. To address the above problems, this paper proposes an ER-tree(embedded R-tree) index structure based on the orderliness of LSM-tree data. By building an SER-tree(embedded R-tree on an SSTable) index structure for each storage component, we optimised dual index queries into single and organised SER-tree indexes into an ER-tree index with a binary linked list. The experiments showed that the query performance of the ER-tree index was effectively improved compared to that of stand-alone R-tree indexes.
BibTeX
@inproceedings{he2022lsm,
  author = {Junjun He and Huahui Chen},
  title = {{An LSM-Tree Index for Spatial Data}},
  booktitle = {Algorithms},
  year = {2022},
  url = {https://openreview.net/forum?id=-HCmn5-CGX},
}
Figure