Title: All You Need Is Binary Search! A Practical View on Lightweight Database Indexing on GPUs Show Chinese title

Title: 一切尽在二分查找！ GPU上轻量级数据库索引的实用观点

Abstract: Performing binary search on a sorted dense array is a widely used baseline when benchmarking sophisticated index structures: It is simple, fast to build, and indexes the dataset with minimal memory footprint. However, the popular opinion is that it cannot compete with sophisticated indexes in terms of lookup performance, and hence, should not actually be considered in practice. Interestingly, in our recent works on (even more sophisticated) GPU-resident index structures, we observed the surprisingly good performance of binary search in a variety of situations. As a consequence, in this work, we analyze the reasons for this and perform three types of optimizations to the standard implementation to push binary search to its limits on GPUs. We show that our highly-optimized version of binary search outperforms the naive variant by up to a factor of 2x which makes it a practical alternative to full-fledged indexes, such as the state-of-the-art GPU B+-Tree, while consuming considerably less space and having a shorter build time. Apart from the optimizations, we discuss a generalization of binary search in form of K-ary search, which is able to consistently outperform the B+-Tree by a factor of 1.5x to 2.7x while having a negligible space overhead over binary search. Show Chinese abstract

Abstract: 在排序后的密集数组上执行二分查找是基准测试复杂索引结构时广泛采用的基线：它简单易用，构建速度快，并且以最小的内存占用来索引数据集。然而，普遍的看法是，就查找性能而言，它无法与复杂的索引结构竞争，因此，在实践中不应予以考虑。 有趣的是，在我们最近关于（甚至更复杂的）GPU驻留索引结构的工作中，我们观察到二分查找在各种情况下的性能令人惊讶地好。 因此，在这项工作中，我们分析了这种现象的原因，并对标准实现进行了三种类型的优化，以在GPU上将二分查找推向极限。 我们证明，我们的高度优化版本的二分查找比原始变体快多达两倍，这使其成为全功能索引（如最先进的GPU B+-树）的一个实用替代方案，同时占用的空间更少，构建时间也更短。 除了这些优化之外，我们还讨论了一种K路查找的泛化形式，它能够始终比B+-树快1.5倍到2.7倍，而与二分查找相比，空间开销可以忽略不计。