Abstract
LSM-tree-based data stores are widely adopted in industries for their excellent performance. As data scales increase, disk-based join operations become indispensable yet costly for the database, making the selection of suitable join methods crucial for system optimization. Current LSM-based stores generally adhere to conventional relational database practices and support only a limited number of join methods. However, the LSM-tree delivers distinct read and write efficiency compared to the relational databases, which could accordingly impact the performance of various join methods. Therefore, it is necessary to reconsider the selection of join methods in this context to fully explore the potential of various join algorithms and index designs. In this work, we present a systematic study and an exhaustive benchmark for joins over LSM-trees. We define a configuration space for join methods, encompassing various join algorithms, secondary index types, and consistency strategies. We also summarize a theoretical analysis to evaluate the overhead of each join method for an in-depth understanding. Furthermore, we implement all join methods in the configuration space on a unified platform and compare their performance through extensive experiments. Our theoretical and experimental results yield several insights and takeaways tailored to joins in LSM-based stores that aid developers in choosing proper join methods based on their working conditions.
Introduction
Modern data stores like RocksDB, Cassandra, and HBase rely on Log-Structured Merge (LSM) trees for high-performance writes. However, when it comes to join operations—the fundamental building blocks of relational queries—these systems often rely on strategies inherited from traditional B+ tree-based databases.
The challenge is that LSM-trees behave fundamentally differently. They utilize out-of-place updates, where new data is appended and old data is eventually cleaned up during compaction, and leverage Bloom filters to accelerate lookups across multiple levels. These unique properties mean that a join algorithm optimized for a standard SQL database might perform poorly in an LSM-based store. This research systematically maps out the design space for joins over LSM-trees to determine how to choose the right strategy for modern workloads.
Mapping the Configuration Space
To understand the performance landscape, the researchers defined a configuration space consisting of 29 different join methods, broken down into four primitive components:
- Join Algorithms: Standard approaches including Indexed Nested Loop Join (INLJ), Sort-Merge Join (SJ), and Hash Join (HJ).
- Secondary Index Types:
- Eager Index (EI): Merges entries immediately on update, favoring fast reads at the cost of write performance.
- Lazy Index (LI): Appends entries and defers merging to background compaction.
- Composite Key Index: Uses a concatenated key (join attribute + primary key) to optimize specific access patterns.
- Consistency Strategies:
- Synchronous: Ensures the index is always perfectly in sync with the data.
- Validation: Allows the index to be slightly out of sync, verifying data validity only during the join operation.
- Covering vs. Non-Covering: Determines whether the index includes all necessary data or requires additional lookups in the main table.
Key Insights and Experimental Results
The study utilized both real-world datasets (Stack Overflow, IMDB, SOSD) and synthetic datasets (Uniform and Zipfian distributions) to stress-test these variables. The findings challenge traditional database wisdom:
The Impact of Entry Size and Frequency
In traditional databases, selectivity is the primary driver for join selection. In LSM-trees, entry size and join frequency are equally critical. For instance, as entry size increases from 32 to 4096 bytes, Hash Join latency can increase by 600%, while INLJ latency only rises by 50%. This is largely due to the efficiency of LSM-tree Bloom filters, which make point lookups in INLJ much more competitive as data grows.
Validation vs. Synchronous Consistency
While most systems default to Synchronous consistency, Validation strategies (checking validity at join-time) prove significantly faster when data entries are large (e.g., >512 bytes). This approach avoids the massive overhead of maintaining perfect index consistency during heavy write bursts. However, Validation has a "kryptonite": data skew. In highly skewed Zipfian distributions, Validation latency can skyrocket compared to Synchronous methods.
Summary of Findings
- Low Join Frequency: Hash Join (HJ-P) is typically the most efficient.
- High Join Frequency: Sort-Merge with dual indexes (SJ-PS) can become 50% faster than Hash Join as the frequency of queries increases relative to updates.
- Large Entry Sizes: Indexed Nested Loop Join (INLJ) becomes increasingly attractive due to the low cost of point lookups in LSM-trees.
Conclusion
The performance of joins in LSM-based stores is not a "one size fits all" scenario. Because no single method dominates across all workloads, future LSM-based engines should consider implementing adaptive query optimizers. These optimizers could switch join strategies on the fly as data distribution, entry size, or join frequency changes. While this study focuses on binary joins, it provides the foundational framework necessary to optimize more complex multi-way joins and hardware-accelerated LSM storage in the future.
Summary updated