Learned Index Acceleration with FPGAs: A SMART Approach

Indexes in database systems such as B+trees and hash tables retrieve data quickly. Much research has been conducted on the faster index lookup in recent years. A learned index is one such area of study. Learned index approaches, such as radix spline (RS) [1] can achieve significant performance improvement over traditional indexing techniques. However, query performance with learned indexes is limited by the constraints imposed by CPU architecture. This paper introduces a novel methodology that leverages the benefits of learned indexes and FPGAs. We term this approach as the Selective Mathematical operation AcceleRaTion (SMART) with an FPGA for an end-to-end acceleration of learned indexes. As a hybrid of CPU and FPGA approaches, the SMART model of index acceleration surpasses the throughput of CPU-based implementations while preserving the data structure storage on the CPU. Our proposed FPGA-based RS learned index architecture (Figure 1) consists of two major stages: Build and Lookup. The Build model <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(SMART-RS_{Build})$</tex> accelerates the build stage on an FPGA, while the Lookup model <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(SMART-RS_{Lookup})$</tex> executes the FPGA-based lookup acceleration. The build stage is accelerated by offloading the computationally intensive interpolation operation onto an FPGA. In this stage, the index data is stored on a CPU while the interpolation operation is executed on an FPGA. As shown in Figure 1, input to the FPGA-based <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$SMART-RS_{Build}$</tex> are key, max spline error, and previously stored CDF point. Here, the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Y$</tex> coordinates are the bounding box of a spline. The FPGA-based build-stage accelerator will output the orientation type: clockwise (CW), counter-clockwise (CCW), or collinear. Based on the orientation obtained, upper and lower limits are set and the previous CDF point is stored as the next spline point. RadixSpline is constructed over a sorted data set. The module AddKeyToSpline iterates over the input sorted data set and will create the array of resultant splines. The decision-making in deciding the orientation type is offloaded to the module SMART-@ <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$RS_{Build-Interp}$</tex> on the FPGA. The output from the FPGA is the type of orientation that will make the following decision during spline construction: Store the input key and its position in the dataset in the spline points array (SplinePoints). • Store the spline index in the radix table (Radix TABLE). • Update the upper and lower error bounds. In the lookup stage acceleration, the radix table and set of spline points are offloaded to our lookup-stage accelerator (SMART@ <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$RS_{Lookup}$</tex>), where they are stored in BRAMs/SRLs as partitioned arrays. With our approach, Speedup of 5.5× as compared to a CPU -based RS index. • Specific compute-intensive operations were identified, thereby avoiding the need for a full-scale FPGA implementation. • Complexities associated with debugging RTL-related issues were reduced. • Controlled on-chip and off-chip memory resource usage. • More accurate comparison between CPU and FPGA implementations.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.