More Bang For Your Buck(et): Fast and Space-efficient Hardware-accelerated Coarse-granular Indexing on GPUs

最近的研究表明，NVIDIA的RTX显卡上的光线追踪核心可以被利用来实现GPU内存中数据库索引的硬件加速查找。在高层次上，这个概念将所有的键都实现为3D场景中的三角形，并对它们进行索引。查找是通过向场景中发射光线并利用索引结构以硬件加速的方式检测命中来完成的。虽然这种方法称为RTIndeX（或简称RX）是有前途的，但它目前存在三个限制：（1）每个键的显著内存开销，（2）缓慢的范围查找，以及（3）更新性差。在这项工作中，我们展示了一个单一的设计改变可以解决所有三个问题：将RX通用化为粗粒度索引cgRX。cgRX不是索引单个键，而是索引键的桶，在检索后进行后过滤。这大大减少了内存开销，导致生成更小、更高效的索引结构，并实现了快速的范围查找和更新。我们将看到，将桶在3D空间中表示，以便正确且有效地查找键，需要按特定顺序精心编排发射光线。我们的实验评估表明，与相应的支持范围查找的基线相比，cgRX提供的吞吐量与内存占用的比率高1.5-3倍。同时，cgRX提高了范围查找性能，比RX高出最多2倍，并提供实用的更新性能，比从头开始重建快多达5.5倍。

解决问题：论文旨在通过设计新的索引结构来解决RX方案的三个问题：大量的内存开销、慢速的范围查找和差劲的可更新性。

关键思路：cgRX方案将密钥的粒度从单个密钥扩展到密钥桶，以提高内存利用率并改进查询和更新速度。将密钥桶表示为三维空间中的三角形，并通过特定顺序的射线发射来实现高效查询。

亮点：cgRX方案通过实验评估表明，在与其他基准方案相比，其吞吐量与内存占用之比提高了1.5-3倍，并且比RX方案的范围查找性能提高了2倍，同时提供了实用的更新性能，速度比从头开始重建快了5.5倍。

相关研究：最近的相关研究包括利用GPU加速的数据库索引结构和范围查询算法的研究，例如“GPU加速的B +树索引”和“基于GPU的高效范围查询算法”。