G-Learned Index: Enabling Efficient Learned Index on GPU

Jiesong Liu

doi:10.1109/TPDS.2024.3381214

G-Learned Index: Enabling Efficient Learned Index on GPU

2024-06-01

1

PRE

AI

DOI：10.1109/TPDS.2024.3381214

Original

Original request for help

Save

Abstract

En 中文

AI and GPU technologies have been widely applied to solve Big Data problems. The total data volume worldwide reaches 200 zettabytes in 2022. How to efficiently index the required content among massive data becomes serious. Recently, a promising learned index has been proposed to address this challenge: It has extremely high efficiency while retaining marginal space overhead. However, we notice that previous learned indexes have mainly focused on CPU architecture, while ignoring the advantages of GPU. Because traditional indexes like B-Tree, LSM, and bitmap have greatly benefited from GPU acceleration, a combination of a learned index and GPU has great potentials to reach tremendous speedups. In this paper, we propose a GPU-based learned index, called G-Learned Index, to significantly improve the performance of learned index structures. The primary challenges in developing G-Learned Index lie in the use of thousands of GPU cores including minimization of synchronization and branch divergence, data structure design for parallel operations, and usage of memory bandwidth including limited memory transactions and multi-memory hierarchy. To overcome these challenges, a series of novel technologies are developed, including efficient thread organization, succinct data structures, and heterogeneous memory hierarchy utilization. Compared to the state-of-the-art learned index, the proposed G-Learned Index achieves an average of 174x speedup (and 107x of its parallel version). Meanwhile, we attain 2x less query time over the state-of-the-art GPU B-Tree. Our further exploration of range queries shows that G-Learned Index is 17x faster than CPU multi-dimensional learned index.

Keywords:

Learned index

parallel

GPU

acceleration

G-Learned Index: Enabling Efficient Learned Index on GPU

Abstract

Journal

Organization