Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training

Learned indexes使用机器学习模型学习键和它们在键值索引中对应位置的映射关系。这些索引使用映射信息作为训练数据。Learned indexes需要经常重新训练其模型以纳入更新查询引入的更改。为了有效地重新训练模型，现有的Learned indexes系统通常利用线性代数的QR分解技术进行矩阵分解。这种分解方法在每次重新训练时处理所有键-位置对，导致计算操作随键和它们的长度总数呈线性增长。因此，重新训练会创建严重的性能瓶颈，特别是对于变长字符串键，而重新训练对于保持高预测准确性和进而确保低查询服务延迟至关重要。 为了解决这个性能问题，我们开发了一种算法-硬件协同设计的字符串键Learned indexes系统，称为SIA。在设计SIA时，我们利用了基于矩阵分解的训练方法的一种独特算法属性。利用该属性，我们开发了一种基于记忆化的增量训练方案，该方案仅需要计算更新的键，而来自先前计算的非更新键的分解结果可以被重用。我们进一步增强了SIA，将这个训练过程的一部分卸载到FPGA加速器上，不仅为服务索引查询（即推理）释放CPU资源，而且加速训练本身。我们的评估显示，与ALEX、LIPP和SIndex等最先进的Learned indexes系统相比，SIA加速的Learned indexes在两个真实世界基准套件YCSB和Twitter cache trace上提供了2.6倍和3.4倍的吞吐量。

解决Learned Indexes模型需要频繁重训的性能瓶颈问题

设计了一种基于QR分解和FPGA加速的增量式训练方案，利用缓存机制和FPGA加速来减少重训时的计算量，从而提高性能

SIA系统在YCSB和Twitter cache trace数据集上相比目前最先进的学习索引系统ALEX、LIPP和SIndex，分别提高了2.6倍和3.4倍的吞吐量。同时，SIA系统还利用FPGA加速，实现了训练和推理的加速，具有很高的实用性和可扩展性。

其他相关研究包括：ALEX、LIPP和SIndex等学习索引系统，以及基于FPGA加速的机器学习加速器等。