论文：LiveBin: A Localized and Version-Aware Binned Scan Index
会议：SIGMOD 2026
作者：Zikang Liu, Linwei Li, Fei Ye, Zhenying He, Yinan Jing, Wen He, Huichao Duan, Lixiong Zheng, X. Sean Wang
简介：近年来，Binned Scan Index的技术显示出其在加速主存分析型数据库中的扫描操作方面具有显著潜力。该能力源于草稿-精修范式（Draft-Refine paradigm），一种两阶段方法：首先生成近似的草稿结果，随后利用索引中存储的辅助数据对其进行精修。尽管现有设计已能实现较优的扫描性能，但仍受两大效率问题困扰：（1）精修阶段开销：尽管现有技术通过提高草稿的准确性来减少精修迭代次数，但每次精修操作仍会产生显著的随机内存访问开销；（2）动态数据效率低下：当考虑多版本并发控制（MVCC）时，扫描操作需要为当前事务确定记录的可见版本。可见性检查的开销远大于谓词判断的成本。因此，在MVCC场景下利用Binned Scan Index进行扫描，对总执行时间的改善甚微。
我们提出了LiveBin，一种局部化且感知版本的Binned Scan Index，它通过两项关键技术应对上述挑战：（1）局部化：将完整的索引划分为逻辑上独立的子索引。现有研究致力于通过更复杂的草稿生成来减少精修频率，而 LiveBin 则采用局部化来降低每次精修时的随机内存访问开销。这能在维持高效草稿生成的同时，有效降低精修阶段的开销。（2）版本感知索引：嵌入一种层次化的版本管理结构，将草稿-精修范式扩展至可见性检查。这种集成最大限度地减少了可见性验证和版本链遍历的开销。实验结果表明，在相同内存预算下，LiveBin 的扫描性能比现有最优方法快 2.2 至 2.6 倍。我们进一步将 LiveBin 集成到 DuckDB 中，集成后的系统在 TPC-H Q6 和 SSB Q1 查询上的端到端性能，相比原始 DuckDB 提升了 2.4 至 5.0 倍。
