2024-06-03
Innovation Highlights
提出了一种全局范围过滤器结构Global Range Filter (GRF)来减少查询过滤器的时间开销。在不产生额外内存开销的情况下将全局过滤器支持了范围查询，通过形状编码来保证查询结果在并发场景下的正确性。
Achievements Summary
通过形状编码构建LSM-Tree全局范围过滤器—GRF
LSM-Tree是一种非常常见的键值对数据存储引擎。LSM-Tree在磁盘上维护多个排序数组，牺牲了部分查询性能来换取高效的写入性能。随着数据量的扩大以及排序数组个数的增加，查询这些过滤器的时间逐渐变成了性能瓶颈。过往工作通过建立全局过滤器，减少过滤器查询次数的方式来降低这一瓶颈。但是过往的全局过滤器往往无法加速范围查询，同时在并发查询的场景下会产生正确性的问题。
图1. 全局过滤器的多版本并发控制（MVCC）问题
张焕晨团队提出了一种全局范围过滤器结构（GRF）来减少查询过滤器的时间开销。在不产生额外内存开销的情况下将全局过滤器支持了范围查询，通过形状编码来保证查询结果在并发场景下的正确性。
图2. GRF概览
GRF的优点具体包括：
（1）可以同时加速点查询和范围查询。
（2）使用形状编码技术来存储每个键在LSM-Tree中的分布情况。与传统的过滤器相比，形状编码能够更有效地表示键的未来位置，从而减少每次压缩操作时所需的更新。
（3）通过支持MVCC增强了并发查询的能力，解决了并发读写场景下查询结果不正确的问题。
（4）该数据结构的维护代价很低，在LSM-Tree合并多个排序数组的时候不需要额外处理，由此提高了LSM-Tree的写性能。
图3. 在具有形状编码的快照中搜索键
该工作提出的GRF在提高数据库系统性能，尤其是在需要处理大量写入和查询的现代应用场景中，具有显著的应用价值。本论文一作为上海期智研究院实习生、清华大学交叉信息学院博士生王恒睿。
更多信息请阅读论文：
1. GRF:A Global Range Filter for LSM-Trees with Shape Encoding, Hengrui Wang, Te Guo, Junzhao Yang, Huanchen Zhang*, SIGMOD 2024.
2. LeCo: Lightweight Compression Via Learning Serial Correlations, Yihao Liu, Xinyu Zeng, Huanchen Zhang*, SIGMOD 2024.
3. Making In-Memory Learned Indexes Efficient on Disk, Jiaoyi Zhang, Kai Su, Huanchen Zhang*, SIGMOD 2024.
4. SALI: A Scalable Adaptive Learned Index Framework based on Probability Models, Jiake Ge, Huanchen Zhang, Boyu Shi, Yuanhui Luo, Yunda Guo, Yunpeng Chai, Yuxing Chen, and Anqun Pan*, SIGMOD 2024.
5. PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware, Shuangyu Cai, Boyu Tian, Huanchen Zhang, and Mingyu Gao*, SIGMOD 2024.
