.png){kind=icon}
返回
Accelerating string search: A microarchitecture-aware index for variable-length data
.png){kind=icon}
PRE
AI
DOI：10.1016/j.sysarc.2026.103805.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
可变长度字符串索引是现代数据密集型系统的关键组件。然而，其性能通常远低于固定长度整数索引。本文首先进行细粒度微架构分析，揭示了可变长度字符串索引在现代处理器上的主要瓶颈：频繁的L1/LLC缓存未命中和分支误预测。基于这些发现，我们提出前缀字符串索引（PSI），这是一种根本性的微架构范式转变，而非简单的结构修补。PSI利用SIMD加速的保序编码，将可变长度字符串高效映射到紧凑的64位前缀空间，将复杂的字符串导航转化为硬件友好的整数搜索问题。内部机制上，PSI引入自适应节点机制，根据局部数据稀疏度动态切换扁平数组和子Trie结构，以最大化指令级并行性。关键在于，该自适应机制由确定性、硬件派生的常量控制，完全消除了针对不同数据集的手动超参数调优需求。此外，为减轻动态工作负载的严重重建开销，PSI集成了一个轻量级、无阻塞的O(n)模型重训练机制。在真实数据集（如URLs、身份证号）和YCSB工作负载上的实验结果表明，PSI不仅在平均吞吐量上超越当前最佳基线26%–33%，还保持了0.50ms至0.65ms的稳定中位延迟，在延迟敏感场景下表现出卓越的稳定性。值得注意的是，PSI在持续插入条件下将p99.99尾延迟降低2.2倍至8.0倍，验证了我们的微架构适配在提升检索性能和确保鲁棒动态执行方面的有效性。
Keyword:
string indexing
micro-architectural optimization
variable-length strings
SIMD acceleration
adaptive data structures
期刊
IF:
4.1
论文数:
3.0K
被引数:
4.2K
机构
暂无机构信息
引用论文
How good are multi-dimensional learned indexes? An experimental survey多维学习索引的效果如何？一项实验性综述.png)
VLDB JOURNAL
OAAI
VLDB JOURNALIF3.8
OAAI分享收藏Accelerating String-Key Learned Index Structures via Memoization-Based Incremental Training基于记忆化的增量训练加速字符串键学习索引结构
PREAI
分享收藏分享收藏
查看更多内容