arXiv:2604.16725v1 [cs.DB] 17 Apr 2026
FliX: Flipped-Indexing for Scalable GPU Queries and Updates Rosina Kharal
Trevor Brown
University of Waterloo Waterloo, Canada [email protected]
University of Waterloo Waterloo, Canada [email protected]
Justus Henneberg
Felix Schuhknecht
Johannes Gutenberg University Mainz, Germany [email protected]
Johannes Gutenberg University Mainz, Germany [email protected]
ABSTRACT
some constraints on the indexing problem. Most notably, the latency to access GPU memory is relatively high, and the connection between CPU and GPU memory is extremely high bandwidth. This means GPU indexes rely on batching operations to amortize the latency of copying memory to/from the GPU. These batches might come from application side batching of user requests, or they might simply come from long running SQL queries that are compiled into a large number of index operations (e.g., large joins). Database indexes are often implemented as a map from a primary or secondary key to a tuple, via some kind of B-tree or LSM-tree if ordering is important, or via hashing if not. In modern, highly concurrent data systems, it is useful for such indexes to allow concurrent accesses by many threads. Concurrent data structure design is notoriously difficult, and while GPU data structures tend to take a more data parallel approach than CPU based concurrent data structures, the design of GPU-based concurrent data structures (CDSs), such as BTrees, skip-lists and hash tables, can be quite challenging. GPU-based CDSs are able to achieve extremely high-speed readonly query operations, often vastly outperforming CPU-based data structures [2, 5, 10, 15, 18]. However, existing designs either completely lack support for dynamic row insertions and deletions, or provide only limited support, and they struggle to achieve similarly high performance for these operations. For example, the GPU LSM-tree of Ashkiani et al. [3] supports insertion and deletions at the cost of high memory consumption. The ray-tracing powered RTIndex of Henneberg et al. [8] and the cuDPP static hash table [1] require a full rebuild of the index on insertions and deletions. The Warpcore hash table of Jünger et al. [10] supports insertion and deletion, but the table has a fixed size and cannot grow or shrink. The GPU B-tree of Awad et al. [5] supports both insertion and deletion, but as our experiments show, their approach to supporting fully dynamic updates incurs high overhead. Some of these also have limited or no support for reclaiming memory (see Section 2). All these traditional index data structures share that they have two layers: a data layer where data is stored or pointers to rows are stored, and an index layer that directs queries to the appropriate place in the data layer. For example, the index layer of the GPU Btree of Awad et al. [5] is the tree structure that must be traversed to find the correct leaf node; leaf nodes represent buckets of keys which form the data layer. As we will see in the following, our FliX approach drops this separation entirely, leading to a natural mapping of the indexing problem to GPUs.
GPU-based concurrent data structures (CDSs) achieve very high throughput for read-only queries, but efficient support for dynamic insertions and deletions on fully GPU-resident data remains challenging. Ordered CDSs (e.g., B-trees and LSM-trees) maintain an index layer that directs operations to a data layer (buckets or leaves), while hash tables avoid the cost of maintaining order but do not support range or successor queries. On GPUs, maintaining and traversing an index layer under frequent updates introduces contention, warp divergence, and memory overhead. To tackle these problems, in this work, we flip the traditional indexing paradigm on its head with FliX, a comparison-based flipped indexing strategy for dynamic, fully GPU-resident CDSs. Traditional GPU CDSs typically take a batch of operations and assign each operation to a GPU thread or warp. FliX, however, assigns compute (e.g., a warp) to each bucket in the data layer, and each bucket then locates operations it is responsible for in the batch. By further sorting the batch, FliX can replace potentially many index layer traversals with a single binary search on the batch, reducing redundant work and warp divergence. Further, it naturally simplifies the update procedure, as no index layer must be maintained. In our experiments, FliX achieves up to 6.5× reduced query latency compared to a leading state-of-the-art GPU B-tree and 1.5× compared to the leading GPU LSM-tree, while delivering 4× higher throughput per memory footprint than ordered competitors. Despite maintaining order, FliX also surpasses state-of-the-art unordered GPU hash tables in point-query and deletion performance, while remaining highly competitive in insertion performance. In updateheavy workloads, it outperforms the closest fully dynamic ordered baseline by over 8× in insertion throughput, while supporting range and successor queries and dynamic memory reclamation. These results suggest that eliminating the index layer and adopting a compute-to-bucket mapping can enable practical, fully dynamic GPU indexing without sacrificing query performance.
1
INTRODUCTION
Database indexing is a longstanding research area that has historically been dominated by data structures that run on the CPU. Recently, there has been significant interest in using GPUs to accelerate database indexing, especially for read-heavy workloads [6, 8, 12, 16, 19]. The unique architecture of GPUs imposes 1
Rosina Kharal, Trevor Brown, Justus Henneberg, and Felix Schuhknecht one bucket inspection per query!
data layer
data layer
data layer
3?
1
✘
1
1
3?
3 ✓
3
3
3?
5
✘
5
5
3?
7
✘
7
17?
8?
8 ✓
17?
8?
10 ✘
17?
8?
11 ✘
17?
8?
17 ✓
26?
18 ✘
26?
22 ✘
26?
26 ✓
26?
27 ✘
31
39
29
55
31
warp
3
one traversal per query!
8 17 26
access divergence!
31
Point-queries (sorted by key)
key relevant?
3 relevant queries
8 17
8✓
10?
10 ✘
11?
11 ✘
17?
17✓
55
(a) compute-to-operations
key relevant?
3 relevant queries
22
8
8?
8✓
10?
10 ✘
11?
11 ✘
17?
17✓
17
18 22
26
26 27
31
39
29
39
55
31
55
37 87
Point-queries (sorted by key)
18
locate queries [8, 17]
flipped index layer
26
7
8?
26 binary search for queries [8, 17]
27 29 31
37 87
warp
Point-queries (sorted by key)
warp
index layer
37 87
55
(b) compute-to-bucket (flipped index layer)
55
(c) compute-to-bucket (FliX)
Figure 1: Conceptual Figures: (a) index layer search required for each query key, (b) reduce index layer searches if bucket ranges are known advance, eliminate the index layer by performing binary search on the sorted batch of queries. Intro,inside by(c)side gure
Time (ms)
42
40
111 109
31
111 109
25
111 108
To understand the key insight behind the development of FliX, consider the following worked example involving the GPU B-tree of Awad et al. [5] and a list of batched read-only queries. The work is divided as follows: Each GPU warp takes 32 consecutive queries from the batch, and the warp then performs these queries, one by one, collaboratively. In other words, for each warp, for each key, the warp traverses the B-tree’s index layer to reach the correct bucket in the data layer (Figure 1 (a)). The reason for having an entire warp collaborate on a single index lookup is that performing simultaneous lookups of different keys would likely cause threads to traverse different paths from one another, causing warp divergence, which occurs when threads in a warp take different branches. One could induce temporal locality by first sorting queries by their keys, so that the queries a warp is responsible for are more likely to be located close to one another in the tree. This way, consecutive queries for nearby keys can benefit from nodes being cached by prior queries. However, depending on the workload, query keys may simply be too far apart for threads to realize caching benefits. And, even if many keys are close enough to realize caching benefits, a lot of time could be spent performing redundant searches, one by one, through the same parts of the tree. The key insight: if one could guarantee that each warp were always assigned keys destined for a single bucket, then we could simply perform a single traversal through the index layer. But, of course, a warp does not know which keys are destined for a given bucket until it has traversed the tree and reached the bucket. Imagine, then, that we flip this problem on its head and ask the opposite question: Rather than trying to determine which bucket a query key is destined for, we begin at the buckets, and ask which keys belong in this bucket? In this flipped paradigm, instead of traversing the index layer to map a key to a bucket, we traverse the query batch instead, to map a bucket to a set of queries, completely eliminating redundant traversals. For example, if each bucket stores some representation of the key range it is responsible for, one could build an index over the incoming queries, and use that index to
(a) Query Time (Hit/Miss) 110 109
30
111 109
Motivating the FliX Approach
111 108
1.1
20 15 10
FliX BTree
5 0
Queries/(sec x bytes)
fi
LSMu Hash_Warpcore Hash_Slab Hits/Misses
round 1 round 2 round 3 round 4 round 5 round 6 ins/query del/query ins/query del/query ins/query del/query (b) Throughput / Memory Footprint
1e 8
3 2 1 0
round 1
round 2
round 3
round 4
round 5
round 6
Figure 2: State-of-the-art GPU CDSs against FliX; alternating rounds of updates. Figure (a) shows query latency (ms) after each update. Figure (b) indicates throughput/ memory footprint; higher values indicate more efficient use of memory. search for the smallest and largest key that could appear in a given bucket (Figure 1 (b)). In fact, we can eliminate the index layer and traversals altogether, by simply sorting the query list (which is extremely fast on the GPU) and performing a single binary search to obtain the queries destined for a bucket (Figure 1 (c)). This approach leverages the extreme scale parallelism of GPUs to do exactly what GPUs are good at. Each bucket is effectively a task to be performed in a GPU kernel. In this kernel, a warp first rapidly determines whether the bucket it is responsible for has any corresponding queries in the batch, and if not, it terminates. Any bucket that survives this first step, then performs the queries 2
FliX: Flipped-Indexing for Scalable GPU Queries and Updates
destined for it sequentially. In essence, whereas traditional GPU indexes map compute onto queries, which then locate buckets, FliX maps compute onto buckets, which then locate relevant queries. The FliX approach has two key advantages: (1) We eliminate the need for a warp to traverse redundant or divergent paths in an index layer and replace this with a single binary search in the query batch. (2) Instead of performing tree traversals that are logarithmic in the size of the index, we perform binary searches that are logarithmic in the size of a batch, which would typically be much smaller. The key challenges of the FliX approach are as follows. First, whereas a B-tree automatically balances the amount of data across buckets, FliX does not have an index layer, so we must manually partition data (to obtain buckets), and this partitioning must be maintained over time to deal with distributional shift. Second, since FliX assigns compute to buckets, one could imagine that severe skew in the query batch could easily result in severe skew in the amount of work the buckets are responsible for. These challenges are addressed in a surprisingly straightforward way in Section 3. As a preview of our experiments, Figure 2 (a) shows that FliX is very competitive with the state-of-the-art for point queries when all point queries are all hits, and outperforms the state-of-the-art when they are all misses. Shockingly, two of the indexes that FliX outperforms are hash tables, which do not need to pay the considerable overhead of maintaining ordering internally. Moreover, Figure 2 (b) shows that the throughput obtained for the amount of GPU memory invested is quite favourable for FliX— more than 4× higher than its ordered competitors B-tree and LSMu, and comparable to or better than the best unordered ones. As our experiments in Section 6 demonstrate, FliX has superior performance when probing for successor keys (i.e., iterating in order; Section 6.5). In addition, FliX surpasses its most closely related ordered competitor, B-tree, in insertion performance by 8× on average, and outperforms both hash tables in deletion performance while remaining superior or comparable in insertion performance. By nature of removing the index layer, FliX does not directly support unsorted queries. Nevertheless, in Section 6.4 we evaluate unsorted queries by accounting for the cost of sorting in FliX, and find that FliX still outperforms all baselines.
1.2
insertions and deletions, and to bound memory consumption by gradually merging underfull nodes (nodes with few keys). This procedure runs entirely on the GPU and exploits the strengths of GPU architectures.
2
BACKGROUND AND RELATED WORK
GPU CDSs are becoming increasingly favoured for high performance real-time applications where multicore CPU systems are not able to match performance due to limitations in memory bandwidth and parallel thread executions. By offloading workloads to GPUs, and maintaining GPU-resident data, areas such as database management and machine learning are able to extract significant throughput gains [13, 18, 19, 21].
2.1
Concurrent Data Structures and Updatability
CDSs used for database indexing often implement an unordered or ordered map ADT, mapping keys to rows. Both ADTs typically offer operations to search for, insert or delete a key/value pair. Advanced ordered maps leverage their internal ordering to offer more operations like range queries and successor/predecessor queries which return, respectively, all keys (and associated values) in the map that fall in a specified key range, the next smaller key in the map, and the next larger key in the map. To support updates, some existing GPU CDSs require a full rebuild procedure [8, 11, 17], meaning that the structure is reconstructed from scratch using the current live keys together with a new batch of update keys, rerunning the original build procedure. Others allow fine-grained updates, but must perform a partial rebuild to maintain a structure that allows efficient access [3]. We define dynamic updatability for GPU CDSs as the ability to support the insertion and deletion of key-value pairs during longrunning GPU execution, without requiring full reconstruction, or depending on periodic structural repair as a necessary maintenance step. Moreover, for an updatable GPU CDS to be practical, efficient memory reclamation is desirable to prevent unbounded growth (and out-of-memory errors) in long-running applications. Although efficient updates are a key goal in this work, in most cases, we expect that an updatable GPU CDS should prioritize query performance, since queries dominate common database indexing workloads. Recent state-of-the-art GPU data structures do support fast read-only query operations [1, 2, 5, 10, 13], but, as our experiments show, they do not always scale well in workloads that require frequent updates on fully GPU-resident data. Updating GPU-based CDSs remains significantly more challenging than supporting read-only queries. Coordination between GPU threads must be carefully orchestrated if one is to effectively utilize tens of thousands of threads in a SIMD (Single Instruction, Multiple Data) architecture. Moreover, to obtain the highest level of performance, one must ensure that GPU memory accesses exhibit high spatial locality, so that many concurrent memory requests from threads in the same warp can be coalesced into a single bulk load from GPU memory. Frequent updates to different parts of an index can easily trigger non-contiguous, irregular write patterns that cannot be coalesced [3, 4]. Such scattered accesses are precisely what motivates our flipped indexing strategy.
Contributions (1) We present FliX, a novel flipped indexing paradigm and GPU CDS with dynamic updates and high performance queries that is well suited to database indexing. Unlike prior art, FliX starts at a bucket in the data layer, and searches for operations targeting that bucket. This allows multiple updates performed on a single bucket to be performed together with coalesced memory accesses. (2) We conduct formative synthetic experiments to identify the most effective GPU kernel configurations across different update/query ratios, key distributions, and batch sizes. This exploration is followed by extensive summative experiments over a wide variety of workloads that demonstrate FliX’s competitive, and often superior, performance compared to the state of the art. (3) We propose a restructuring procedure for FliX to maintain low query latencies in long-running applications with many 3
i(6) i(10) i(28) i(31) i(35) Insertions (sorted by key)
26
28 31 35
d(11)
d(8)
d(8) d(11) d(18) 36 38
d(26) d(28) d(35) Deletions (sorted by key)
10
underfull nodes m
31
ge
er
36 38
(c) Performing a batch of deletions
(b) Performing a batch of insertions
merge
4 6 10
31 36 38
maxKey = 3 maxKey = 11
d(8)
6
maxKey = 3
maxKey = 3
d(11)
4
3
maxKey = 38
i(4)
18
d(8)
maxBucket = 38 maxBucket = 11 maxBucket = 3
i(4)
d(8)
d(11)
maxKey = 11
i(6)
d(11)
1
maxKey = 38
i(10)
8
11
maxKey = 8
i(4)
10
3
maxKey = 26
i(6)
6
1
maxKey = 35
i(10)
4
maxKey = 11
i(4)
maxKey = 8
maxKey = 3
(a) Initial state of FliX
i(4)
i(6)
maxBucket = 38 maxBucket = 26 maxBucket = 11 maxBucket = 3
38
i(6)
i(10)
maxKey = 38
36
i(10)
3
maxKey = 26
26
Then compares 6, and so on …
1
maxKey = 35
18
Each thread compares 4 with its key [8, 11, -, -]
maxBucket = 38 maxBucket = 26 maxBucket = 11 maxBucket = 3
8 11
maxKey = 11
3
maxKey = 26
1
maxKey = 38
maxBucket = 38 maxBucket = 26 maxBucket = 11 maxBucket = 3
Rosina Kharal, Trevor Brown, Justus Henneberg, and Felix Schuhknecht
(d) Restructuring
Figure 3: (a) FliX initial build step: keys are divided into buckets. (b) A batch of keys is inserted. Each thread fetches a key from the current node ([8, 11, -, -]), and compares insert keys to its fetched key to determine where new keys go. (c) A batch of keys Figures about modi cations is deleted. (d) Restructuring occurs, flattening chains of nodes into individual buckets. Underfull nodes within the same bucket are merged to reclaim space.
2.2
Updatable GPU Data Structures
lines and organized as linked chains through side-link pointers following B-Link tree principles, allowing safe concurrent traversals. A warp-cooperative work sharing (WCWS) strategy minimizes divergence, and proactive splitting of nodes with restart-on-failure policies reduces contention during insertions. Experiments were performed on the NVIDIA Titan V GPU. Compared to LSM-tree, the B-tree achieves a greater speedup on pure query workloads of size 216 to 226 due to efficient upper level caching and warpcooperative traversals. While the LSM-tree is highly performant on very large insertion batches, the B-tree outperforms both the LSM-tree and a GPU Sorted Array baseline for batches of up to 100𝑘 elements. Unlike the LSM-tree, the B-tree does not require large auxiliary merge buffers. The B-tree is the closest comparable ordered CDS to FliX supporting all the same operations and compacting space immediately on deletions.
2.2.1 GPU LSM-Tree. The GPU LSM-tree [3] by Ashkiani et al. is a dynamic, comparison-based structure supporting concurrent insertions and fast queries. It adapts the traditional Log-Structured Merge (LSM [20]) tree design by batching inserts into fixed-size chunks (𝑏), which are sorted and merged into levels, with each new level larger than the previous by a multiplicative factor. Queries must search all levels to determine whether a key is present. The LSM-tree achieves excellent batch insertion performance, surpassing a Sorted Array (SA) construction on an NVIDIA K40c (Kepler) GPU, and maintaining competitive lookup rates at smaller batch sizes. However, this performance comes at the cost of significant memory overhead. The process of merging chunks into levels is not done in-place, and it requires auxiliary buffers proportional to the size of the tree’s largest level. Deletions are supported as a special case of insertions, whereby a marker (tombstone) is added as a new key-value pair, indicating that all further occurrences of the key in the data structure are invalid. Tombstones and stale keys, keys for which an updated value has been inserted, may persist in the tree until a cleanup step occurs to compact the structure. Lookup operations do not actively remove tombstones. Rather, they must check the most recent occurrence of a key and interpret a tombstone as a logical deletion. The existence of tombstones can significantly degrade query performance. Repeated cleanup steps would be required for a persistent, dynamic GPU-resident LSM-tree. We note that we improved the GPU LSM-tree design to derive a variant used as a baseline in our experiments. This is a minor contribution of our work and is further described in Section 5.1. fi
2.2.3 GPU Hash Tables. The slab-based hash table (HT-Slab) of Ashkiani et al. [2] supports concurrent updates using dynamic allocation of fixed-sized slabs containing key-value pairs stored as linked chains in the table. A custom allocator (SlabAlloc) enables GPU memory management without CPU intervention. Memory usage is largely pre-allocated; logical deletions occur first, and physical deletions are delayed until a compaction phase. HT-Warpcore [10] employs open addressing with a warpcooperative probing strategy; it can use flexible thread group sizes (1, 2, 4, 8, 16, or 32) to process operations, which significantly improves performance. It supports dynamic updates and both 32-bit and 64-bit keys. Deletions are tombstone-based and are marked but not reclaimed. Because the structure is unordered, tombstone slots can be reused for new insertions. Memory usage is primarily determined by pre-allocated table size and the load factor. Hash tables generally achieve state-of-the-art update throughput, but do not support comparison-based operations such as efficient range or successor queries.
2.2.2 GPU B-Tree. The GPU B-tree by Awad et al. [5] introduces a dynamic, concurrent B-Tree optimized for warp cooperative execution on GPU architectures. It supports point, range, and successor queries as well as update operations, providing a fully mutable GPUresident ordered index. B-tree nodes are aligned to 128-byte cache 4
FliX: Flipped-Indexing for Scalable GPU Queries and Updates
2.2.4 Hardware-Accelerated Ray Tracing Indexing. Henneberg et al.’s RTIndeX [8] and its updatable variant cgRXu [9] leverage NVIDIA hardware-accelerated ray tracing (HART) cores to accelerate database indexing. Keys are represented geometrically, and a bounding volume hierarchy (BVH) directs search rays to buckets. The BVH serves as the indexing layer, requiring relatively high memory usage compared to purely CUDA-based structures. While update support is fully dynamic, query performance is slowed down by the ray-tracing overhead.
is a tunable paramater. Less full nodes will support more insertions before node splitting is required. The largest key per group (every 𝑝 th key) is the maximum allowable key for the corresponding bucket (maxBucket). The maximum allowable keys for each bucket are stored in an array called the max key per bucket array (MKBA), which is omitted from our diagrams for simplicity. At build time, each bucket consists of a single node. As additional keys are inserted into FliX, new linked nodes may be added to a bucket; therefore, a bucket is formed by a chain of one or more nodes using node-link pointers. The maxBucket values are used to distinguish ranges across buckets (inter-bucket ranges), while node-level maximums, called maxKey, distinguish ranges within a bucket (intra-bucket ranges). Each node stores two pieces of metadata: its maxKey and size (the number of keys currently stored). For simplicity, the size field is omitted from the figure. Figure 3 (b) illustrates the insertion process after the initial build, where a tile of 4 threads processes keys from the insert list. At a high level, the tile advances key by key in the insert list, and for each key 𝑘, the threads in the tile collaborate (by taking ownership of a key in the node to assist in comparisons) to determine the correct location in the node where the key should reside. If a key is not already present, it is inserted into the node. If the node is full, it is split into two halves, and the insertion continues in the appropriate node. When a split occurs, the maxKey values are updated to reflect the new key ranges of the two nodes. Although node-level maximums may change over time, the maxBucket values remain fixed until restructuring occurs (Section 3.5). A more detailed description of the algorithm appears in Section 4. Figure 3 (c) illustrates the state of the data structure following a series of deletions. In FliX, deleted keys are physically removed immediately, with surviving keys shifted to compact the node and reclaim the free space. This is in contrast to prior GPU CDSs, which commonly perform deletions through the use of tombstones; whereby a key is logically deleted but remains physically resident until a deferred cleanup phase. Although this approach can simplify the deletion path, it allows logically deleted entries to accumulate over time, effectively introducing garbage into the data structure. As this garbage grows, it reduces usable memory and degrades query efficiency, since queries must explicitly identify and skip tombstoned entries. The LSM-tree, HT-Slab, and HTWarpcore all employ tombstone-based deletions.
Experimental baselines. We use B-tree, LSMu, HT-Slab, and HTWarpcore as baselines for comparison against FliX. The LSMu and B-tree provide fair comparisons as ordered, comparison-based indexing structures supporting point and range queries. The hash tables provide state-of-the-art lower bounds for query and update performance but do not support ordered operations.
3 THE FLIX APPROACH 3.1 Background The traditional indexing approach on GPUs has been to map compute to operations. For a batch of queries, for example, each unit of compute will attempt to answer a query for key 𝑘, and parallelizing the query workload across additional threads, such as a warp, achieves higher performance as long as contention is avoided. In a flipped-indexing model, we employ a compute-to-bucket mapping, where each GPU thread or tile is assigned responsibility for a single bucket. Buckets then pull work from the batch of operations. A tile is a subdivision of a GPU warp, also referred to as a cooperative group. GPUs are designed as an array of scalable processors called Streaming Multiprocessors (SMs), each of which is partitioned into four processing blocks, each with its own warp scheduler [7, 14]. While a warp typically consists of 32 threads, modern GPU architectures support interleaved execution within warps, enabling smaller execution units called tiles to make independent progress. Existing GPU CDSs [1–3, 5, 10, 15, 22], including those from Section 2, do not naturally support this simple but powerful compute-to-bucket model, because their algorithms are generally designed around the conventional GPU execution model in which operations are designated as tasks to be assigned to compute resources for processing. As a result, adapting these designs to a compute-to-bucket formulation is non-trivial. In the next section, we begin by describing the data structures that FliX uses. Then we explain how a collection of keys and values can be used to construct an initial instance of FliX. Next, we explain how to perform a batch of queries, then move to update algorithms in Section 4. Finally, we explain how to restructure FliX to adapt to distributional shift and imbalance in buckets.
3.2
3.3
Query Execution
Figure 4 illustrates the basic constructs of our data structure, which presupposes the query list is sorted. Sorting and merging are operations GPUs can perform very efficiently; the overhead cost of sorting the query list is discussed further in Section 6 and Table 1. Compute units stationed at each bucket pull relevant operations by performing a simple binary search on the query list, thereby taking all operations belonging to the bucket and executing them in place. As shown in Figure 4, each bucket will pull its relevant portion of query keys from the main query list. This effectively removes the need for a centralized index to direct traffic. As explained above, the maxBucket value determines the maximum allowable key supported by bucket 𝑏𝑖 . A single binary search for the key, maxBucket𝑏𝑖 −1 , is sufficient to retrieve the starting indexing of
Data Structures & Initial Build
Figure 3 (a) provides a visual illustration of the initial build stage of FliX based on an initial set of key-rowID pairs. The build keys are sorted and grouped into partitions of size p, and the groups determine which keys belong in each bucket. Values (rowIDs) corresponding to each key are left out of the diagram for simplicity. The capacity of each node, 𝑛𝑜𝑑𝑒𝑠𝑖𝑧𝑒, is 4 in the example, and we set 𝑝 = 𝑛𝑜𝑑𝑒𝑠𝑖𝑧𝑒 so that nodes are initially half full. The initial fill state 2 5
Rosina Kharal, Trevor Brown, Justus Henneberg, and Felix Schuhknecht
k(13) k(15) k(19) k(20) k(30) k(31) k(34) k(35) k(36)
6 8
18 26
27 29 30
maxKey = 3
10 11
Sort time (ms) 0.0542208 0.0546816 0.0549376 0.0559104 0.0729088 0.1301504 0.2383872
Build size 222 223 224 225 226 227 228
Sort time (ms) 0.4415472 0.8452096 1.6559521 3.2763393 6.5133057 12.9930237 25.9908081
Table 1: Average Sort time on NVIDIA A6000 GPU
30 32
36 38
compute per bucket mapping is already surprisingly robust, even under highly skewed workloads (Section 6.3). The next subsection describes our elastic strategy.
maxKey = 38
k(10)
4
maxKey = 11
k(8)
maxKey = 35
k(7)
3
maxKey = 8
k(5)
Build size 215 216 217 218 219 220 221
maxKey = 26
k(3)
1
maxKey = 30
k(2)
maxBucket = 38 maxBucket = 26 maxBucket = 11 maxBucket = 3
k(1)
3.5
Query List (sorted by key)
Restructuring
query keys belonging to 𝑏𝑖 ; we continue to perform queries in 𝑏𝑖 from this index until a key exceeds maxBucket𝑏𝑖 . Queries return a result buffer toProcess the host for the values (rowIDs) Query incorresponding FliX associated with each search key. In the case where a search key is a miss, a not found value is returned. In Section 6, we perform experiments for both point and successor (next-larger) queries. Range queries are not included in this study since only a limited number of baselines support this operation.
To address both distributional shift and sustained growth of the index, we provide a restructuring procedure that flattens large buckets containing many nodes into individual buckets (with one node per bucket). This is illustrated in Figure 3(d). This procedure effectively realigns the buckets (and compute) to the current distribution such that keys map uniformly to buckets, and can improve query performance by eliminating traversals of long chains of nodes. If there is no distributional shift, and the size of the index is relatively stable, then restructuring may be wholly unnecessary. One can think of the frequency of restructuring as a tunable knob that allows a system to invest more or less time in maintaining the structure to obtain a desired level of query performance. Restructuring also reclaims memory by merging underfull nodes. In Section 6.6, we quantify the memory reclaimed by restructuring in our experiments.
3.4
4
Figure 4: In FliX, each bucket binary searches the query list and pulls relevant keys.
Distributional Shift
OUTLINE OF UPDATE ALGORITHMS
Our primary design goal in FliX is to offer query performance that is competitive with the state of the art, and subject to that constraint, to offer high performance for updates. Modern GPUs provide different approaches for orchestrating the work done by a warp, and these approaches naturally lead to different update algorithms. We explore and compare two broad approaches previously used in the literature: single-threaded (ST) kernels [3, 8], and tiled (TL) kernels [2, 5, 10]. While previous work may choose to select one approach over the other, we perform a comparative analysis of the various types of kernels to evaluate the applicability of each. ST kernels are expressed as a single thread of execution, such that threads in a warp are independently executing tasks. In FliX, each thread operates on its own bucket, and insofar as the hardware can support doing so, multiple threads can run in parallel on the same SM, accessing mutually exclusive buckets. TL kernels, on the other hand, involve multiple threads in a warp collaborating on a single bucket. Recent hardware with support for cooperative groups can schedule multiple tiled subgroups to execute concurrently on a single warp [7]. ST kernels are simpler, but can suffer greater thread scheduling overhead and warp divergence compared to TL. The specific update algorithm at the bucket level may vary; however, the preprocessing steps for queries, insertions and deletions are common across all algorithms. We refer to a batch of keys to
We mitigate the impact of distributional shifts by changing how compute is assigned to buckets. This mapping need not be static, nor uniform. As a concrete example, consider an initial build based on uniformly distributed keys. Suppose that queries, insertions, and deletions also remain uniformly distributed for some time. Later, a distributional shift may occur in which a small portion of the key space becomes much more active, forming a region of hot buckets. For example, insertions may become concentrated within only 5% of the bucket range, and subsequent queries may also primarily target that same region. This results in a highly skewed workload. Insertions may create long chains of linked nodes in the hot bucket region, and queries may spend more time traversing those chains. Under the default one-unit-of-compute-per-bucket mapping, a single GPU tile or thread assigned to each bucket may also become overloaded. To mitigate these effects, we propose workload-aware strategies for assigning compute to buckets. These strategies can be adaptive and/or elastic. An adaptive strategy changes the amount of compute assigned to a bucket, assigning more or less threads per bucket as needed. An elastic strategy may split buckets with long chains of nodes, this effectively reduces the key range assigned per bucket. In the FliX approach, both adaptive and elastic strategies for mitigating the effects of distributional shifts are possible. However, our experiments indicate that the default (non-adaptive) one unit of 6
FliX: Flipped-Indexing for Scalable GPU Queries and Updates
curr
10
25
30
40
70
Thread 𝑡𝑖 key in 𝑡𝑖 regs
0 10
1 25
2 30
3 40
4 70
15
17
39
65
15 15 15
17 17 17
40 25 25
70 30 30
Insert 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 step 1: test-key=25, curr step 2: test-key=40, curr step 3: test-key=70, curr
10 10 10
5
39 39
6
40
7
70
Table 2: TL-Bulk in-place insertions. Threads lift original keys from curr into registers (blue) and merge 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 in place using successor boundaries (test-keys). Key 65 from 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 will be inserted following a node split of curr.
Common Steps
Single Threaded Insertions
4.2.1 Shift-Right Insertions: ST-Shift-Right. The current node, 𝑐𝑢𝑟𝑟 is searched using binary search to check for the existence of key 𝑘 from 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 . If not present, the appropriate insertion point in 𝑐𝑢𝑟𝑟 is returned. Keys ahead of the insertion point are shifted right, and the new key-rowID pair is inserted. If 𝑐𝑢𝑟𝑟 is determined to be full, a node_split function is called to split the keys into two halves. Subsequently, the insertion process continues at the appropriate node.
20
25
30
35
40
45
1 15
2 20
3 25
4 30
5 35
6 40
7 45
Delete list Tile Mask (deleted)
20 0
30 0
1
0
1
0
0
0
Shift-left distance Compacted keys
0 10
0 15
–
1 25
–
2 35
2 40
2 45
final state curr
10
15
25
35
40
45
4.3.3 Hybrid ST and TL Algorithms: ST-Hybrid & TL-Hybrid. Hybrid insertions combine shift-right and bulk strategies depending on the node fill state and workload. In Section 5, we evaluate the usefulness of this strategy.
4.4
4.2.2 Bulk Insertions: ST-Bulk. A single thread bulk-inserts all keys from 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 into 𝑏𝑖 using a copy space. The thread merges 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 and the contents of 𝑐𝑢𝑟𝑟 , copies them back to the original node and handles any necessary node splitting within the copyback step. Thread-local memory was the most performant strategy for maintaining a node copy space.
4.3
15
0 10
node into thread-private storage (typically registers). The TL-Bulk algorithm is illustrated with an example in Table 2. (1) Load node state: Threads in 𝑡𝑖𝑙𝑒𝑖 each load (lift) one key from curr. These keys are denoted the original keys. (2) Compute successor boundary: For the current insert key, 𝑘 in 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 , threads in 𝑡𝑖𝑙𝑒𝑖 collectively determine the successor key in curr, denoted test-key (the smallest original key > 𝑘). If no such key exists, test-key is +∞. (3) In-place merge for one boundary: For all insert keys 𝑘 ′ where 𝑘 ≤ 𝑘 ′ < test-key, one thread from 𝑡𝑖𝑙𝑒𝑖 writes 𝑘 ′ into the next free position in curr, overwriting original keys in curr. (4) Write-back original keys: When the next 𝑘 ′ reaches or exceeds test-key, compute test-key’, the next original key > 𝑘 ′ . Threads write back all original keys in the interval [test-key, test-key’) into the next available positions in curr. (5) Advance. Repeat Steps 2–4 until either (i) the node is full, or (ii) 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 is exhausted. If keys remain and 𝑘 ′ > node max of curr, advance 𝑐𝑢𝑟𝑟 ← 𝑐𝑢𝑟𝑟 .next and repeat from Step 1. If (i), and 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 is not exhausted – split the node and continue from Step 1 at the appropriate node.
The FliX approach assigns one unit of compute to each bucket. A unit of compute is a single thread in an ST algorithm, and a tile in a TL algorithm. Suppose there are 𝑛 buckets. FliX then assigns 𝑛 units of compute, 𝑐 0, ..., 𝑐𝑛 , to buckets, 𝑏 0, ..., 𝑏𝑛 , respectively In a similar manner to how queries are performed using binary search on the query list (Figure 4), each (𝑐𝑖 ) retrieves a 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 containing the keys destined for bucket 𝑏𝑖 from the update list. For a given key, 𝑘 from 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 , we traverse the nodes in 𝑏𝑖 by following node-link pointers until we reach the node where 𝑘 belongs – that is, the first node whose maxKey key satisfies 𝑘 ≤ 𝑚𝑎𝑥𝐾𝑒𝑦. In the algorithms that follow, the current node is denoted by 𝑐𝑢𝑟𝑟 . At this point, the update operation proceeds at the bucket level.
4.2
10
Thread 𝑡𝑖 key in 𝑡𝑖 regs
Table 3: TL-Bulk deletions with compaction. Each thread 𝑡𝑖 loads one key from curr. Keys 20 and 30 are removed; remaining keys shift left by the number of prior deletions.
be inserted or deleted as an update list, and a batch of keys to be queried as a query list.
4.1
curr
Deletion Kernels
We evaluate 3 deletion algorithms: (1) ST-Shift-Left, (2) TL-Shift-Left, and (3) TL-Bulk deletions. We do not employ a tombstone strategy because it associates a performance penalty with another operation (insertions or queries) and incurs memory overhead. ST-Shift-Left and TL-Shift-Left deletions mirror the Shift-Right insertion strategy. TL-Bulk is outlined below and illustrated with an example in Table 3. (1) Each tile completes Common Step from Section 4.1 and proceeds with a 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 for bucket 𝑏𝑖 . (2) Each thread in 𝑡𝑖𝑙𝑒𝑖 loads one key from 𝑐𝑢𝑟𝑟 . (3) For each delete key 𝑑𝑘, threads compare their stored key with 𝑑𝑘, marking matches; a counter tracks the del count. (4) A compaction step shifts surviving keys left; the shift distance per thread depends on the number of preceding deletions.
Cooperative Groups: Tiled Insertions
4.3.1 Tiled Shift-Right Insertions: TL-Shift-Right. Similar to ST, but performed in parallel by all threads in a tile. Each thread reads one key from 𝑐𝑢𝑟𝑟 ; shift-right is performed using parallel comparisons and writes. 4.3.2 Tiled Bulk Insertions: TL-Bulk. Threads in 𝑡𝑖𝑙𝑒𝑖 are tasked with inserting keys from 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 into bucket 𝑏𝑖 at the appropriate node. We avoid a copy space by lifting all original keys from a 7
Rosina Kharal, Trevor Brown, Justus Henneberg, and Felix Schuhknecht
NS-1CL A NS-1CL B NS-1CL C NS-1CL D NS3 A NS3 B NS3 C NS3 D NS4 A NS4 B NS4 C NS4 D NS5 A NS5 B NS5 C NS5 D NS-1CL A NS-1CL B NS-1CL C NS-1CL D NS3 A NS3 B NS3 C NS3 D NS4 A NS4 B NS4 C NS4 D NS5 A NS5 B NS5 C NS5 D NS-1CL A NS-1CL B NS-1CL C NS-1CL D NS3 A NS3 B NS3 C NS3 D NS4 A NS4 B NS4 C NS4 D NS5 A NS5 B NS5 C NS5 D NS-1CL A NS-1CL B NS-1CL C NS-1CL D NS3 A NS3 B NS3 C NS3 D NS4 A NS4 B NS4 C NS4 D NS5 A NS5 B NS5 C NS5 D
X12/Y90 round 1 1.6 1.8 1.8 1.8 1.2 1.3 1.3 1.4 1.8 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.8 2.0 2.0 1.2 1.2 1.3 1.4 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.5 1.4 1.3 1.2 1.4 1.3 1.2 1.1 1.4 1.3 1.2 1.1 1.3 1.2 1.1 1.0 1.8 1.6 1.3 1.3 1.6 1.5 1.2 1.2 1.7 1.5 1.2 1.2 1.8 1.6 1.3 1.2 X12/Y90 round 2 2.0 2.0 2.0 2.0 1.7 1.9 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.4 1.4 1.6 1.7 1.6 1.6 1.6 1.7 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.6 1.4 1.3 1.1 1.5 1.3 1.2 1.2 1.4 1.3 1.2 1.0 1.4 1.2 1.1 1.0 1.7 1.5 1.2 1.2 1.6 1.4 1.2 1.2 1.6 1.4 1.1 1.1 1.6 1.5 1.2 1.1 X12/Y90 round 3 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.7 1.7 1.9 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.6 1.4 1.3 1.2 1.6 1.4 1.4 1.3 1.5 1.3 1.2 1.1 1.4 1.2 1.1 1.0 1.6 1.5 1.2 1.1 1.6 1.4 1.2 1.2 1.5 1.4 1.1 1.1 1.5 1.4 1.1 1.1 X12/Y90 round 4 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.8 1.8 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.7 1.5 1.3 1.2 1.6 1.5 1.4 1.3 1.5 1.3 1.2 1.1 1.4 1.2 1.1 1.0 1.6 1.4 1.2 1.1 1.6 1.4 1.2 1.2 1.5 1.3 1.1 1.1 1.5 1.3 1.1 1.0 X25/Y90 round 1 1.6 1.7 1.7 1.8 1.2 1.2 1.3 1.3 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.8 1.4 1.7 1.8 1.1 1.0 1.0 1.1 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.7 1.5 1.3 1.2 1.5 1.3 1.2 1.1 1.5 1.3 1.2 1.1 1.4 1.3 1.2 1.1 1.9 1.7 1.4 1.3 1.7 1.5 1.3 1.2 1.8 1.6 1.3 1.2 1.9 1.7 1.4 1.3 X25/Y90 round 2 1.9 2.0 2.0 2.0 1.6 1.8 1.8 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.3 1.3 1.4 1.5 1.4 1.4 1.5 1.6 1.8 1.8 2.0 2.0 2.0 2.0 2.0 2.0 1.6 1.4 1.3 1.1 1.5 1.3 1.3 1.2 1.4 1.3 1.2 1.0 1.4 1.2 1.1 1.0 1.7 1.5 1.2 1.1 1.6 1.4 1.2 1.2 1.6 1.4 1.1 1.1 1.6 1.4 1.2 1.1 X25/Y90 round 3 2.0 2.0 2.0 2.0 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.5 1.5 1.6 1.7 1.7 1.7 1.7 1.8 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.6 1.5 1.3 1.2 1.5 1.4 1.3 1.2 1.5 1.3 1.2 1.1 1.4 1.2 1.1 1.0 1.7 1.5 1.2 1.1 1.6 1.4 1.2 1.2 1.5 1.4 1.1 1.1 1.6 1.4 1.1 1.1 X25/Y90 round 4 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.6 1.6 1.7 1.7 1.8 1.8 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.7 1.5 1.3 1.2 1.6 1.4 1.4 1.3 1.5 1.3 1.2 1.1 1.4 1.2 1.1 1.0 1.7 1.5 1.2 1.1 1.6 1.4 1.2 1.2 1.5 1.3 1.1 1.1 1.5 1.3 1.1 1.0 X50/Y90 round 1 2.0 2.0 2.0 2.0 1.7 1.8 1.8 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.6 1.7 1.9 1.1 1.1 1.0 1.1 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.9 2.0 2.0 1.9 1.7 2.0 2.0 1.9 1.7 2.0 2.0 1.9 1.7 2.0 2.0 2.0 2.0 2.0 2.0 1.9 1.8 2.0 2.0 2.0 1.9 2.0 2.0 2.0 2.0 X50/Y90 round 2 1.8 2.0 2.0 2.0 1.5 1.6 1.7 1.8 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.3 1.3 1.3 1.4 1.2 1.2 1.3 1.3 1.8 1.8 1.9 2.0 2.0 2.0 2.0 2.0 1.6 1.4 1.3 1.1 1.5 1.3 1.2 1.2 1.4 1.3 1.2 1.1 1.4 1.2 1.1 1.0 1.7 1.5 1.2 1.1 1.6 1.4 1.2 1.2 1.6 1.4 1.1 1.1 1.6 1.4 1.1 1.1 X50/Y90 round 3 2.0 2.0 2.0 2.0 1.7 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.3 1.3 1.4 1.4 1.4 1.4 1.4 1.5 1.8 1.8 1.9 2.0 2.0 2.0 2.0 2.0 1.7 1.5 1.3 1.2 1.6 1.4 1.3 1.2 1.5 1.3 1.2 1.1 1.4 1.2 1.1 1.0 1.7 1.5 1.2 1.1 1.6 1.4 1.2 1.2 1.5 1.4 1.1 1.0 1.6 1.4 1.1 1.0 X50/Y90 round 4 2.0 2.0 2.0 2.0 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.4 1.4 1.5 1.5 1.5 1.5 1.6 1.6 1.9 1.9 2.0 2.0 2.0 2.0 2.0 2.0 1.7 1.5 1.3 1.2 1.6 1.4 1.3 1.2 1.5 1.4 1.2 1.1 1.4 1.2 1.1 1.0 1.7 1.5 1.2 1.1 1.6 1.4 1.2 1.1 1.5 1.4 1.1 1.0 1.5 1.4 1.1 1.0 X90/Y90 round 1 2.0 2.0 2.0 2.0 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.8 1.7 1.4 1.4 1.2 1.2 1.0 1.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 X90/Y90 round 2 1.7 1.8 1.9 2.0 1.3 1.5 1.6 1.7 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.1 1.2 1.2 1.3 1.0 1.1 1.1 1.2 1.7 1.7 1.9 2.0 2.0 2.0 2.0 2.0 1.6 1.5 1.3 1.1 1.5 1.3 1.2 1.1 1.5 1.3 1.2 1.0 1.4 1.2 1.1 1.0 1.7 1.5 1.2 1.1 1.5 1.4 1.1 1.1 1.6 1.4 1.1 1.0 1.6 1.4 1.1 1.1 X90/Y90 round 3 1.8 2.0 2.0 2.0 1.6 1.8 1.8 1.9 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.3 1.3 1.3 1.4 1.2 1.2 1.3 1.3 1.8 1.8 1.9 2.0 2.0 2.0 2.0 2.0 1.7 1.5 1.3 1.2 1.5 1.4 1.2 1.1 1.5 1.3 1.2 1.1 1.4 1.2 1.1 1.0 1.7 1.5 1.2 1.1 1.6 1.4 1.2 1.1 1.5 1.4 1.1 1.0 1.5 1.4 1.1 1.0 X90/Y90 round 4 2.0 2.0 2.0 2.0 1.7 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0 1.3 1.4 1.4 1.4 1.3 1.3 1.4 1.5 1.8 1.8 1.9 2.0 2.0 2.0 2.0 2.0 1.7 1.5 1.4 1.2 1.6 1.4 1.3 1.2 1.6 1.4 1.2 1.1 1.4 1.2 1.1 1.0 1.7 1.5 1.2 1.1 1.6 1.4 1.2 1.1 1.6 1.4 1.1 1.0 1.5 1.4 1.1 1.0
ST-BULK
ST-Shift-Right
TL-BULK
TL-Shift-Right
Figure 5: Full heat map across varying insertion workloads with 4 rounds of insertions. The x-axis represents insertion algorithms, each evaluated under 16 configurations (4 node sizes × 4 TPB assignments (A-D)). Results indicate that Tiled Bulk insertions outperform alternatives in all rounds except the first round for uniform workloads (𝑋 = 50%, 𝑋 = 90%). (5) All del count keys are removed, the node size is reduced. Empty nodes are removed from the chain and made available for subsequent insertions. (6) Tile continues with the remaining delete keys from 𝑠𝑢𝑏𝑙𝑖𝑠𝑡𝑖 , traversing node-link pointers in bucket 𝑏𝑖 as needed.
30 25
Time (ms)
20 15
(a) Uniform Insertions ST-Shift-Right ST-Bulk ST-Hybrid TL-Shift-Right TL-Bulk TL-Hybrid
25 20 15
10
10
5
5 UPDATE EXPERIMENTS 5.1 Baselines Used in Experiments
0
5
round 1
round 2
round 3
round 4
0
round 1
round 2
round 3
round 4
Figure 6: Comparison of FliX insert kernels (ST or TL). (a) Uniform distribution with 100% growth. (b) Dense distribution where 25% of buckets receive 90% of keys with 200% growth.
In this study, we compare FliX against 4 GPU CDS baselines: the Btree [5], HT-Slab [2], HT-Warpcore [10], and LSMu, our extended variant of the GPU LSM-tree by Ashkiani et al. [3]. We configure these baselines as follows. For the B-tree we use the recommended node size of 15 keys (plus pointers and a side-link) to support the warp-cooperative traversal strategy of Awad et al. [5]. We initialize both hash tables at an 80% load factor to balance memory usage and performance. LSMu is our extended version of the GPU LSMtree [3]. We avoid the need for duplicate keys where deletions are a special case of insertions (i.e., inserted keys with tombstone values). Deletions are performed by locating the key and setting its associated value (rowID) to a tombstone in-place, such that binary search for queries continues to work with minimal impact on performance. We use a chunk-size of 16 which was suited for optimal query performance in the LSM-tree. We add an implementation for next-larger (successor) queries in LSMu.
5.2
(b) Dense Insertions
30
percentage of the distribution that receives update keys, and 𝑌 is the update percentage that defines how many update keys are assigned to 𝑋 . A workload such as 𝑋 = 12%, and 𝑌 = 90%, means that 12% of the distribution receives 90% of the update keys, ensuring that a set of hot buckets always receives the majority of updates. The remaining 10% of update keys are randomly distributed across the rest of the distribution to avoid caching bias. We perform experiments over a range of increasingly dense workload distributions, with 𝑋 varying from 90% to 3%. The case (𝑋 = 90%, 𝑌 = 90%) corresponds to a uniform distribution. Batches are pre-sorted on the GPU prior to experiments. This adds minimal overhead to the overall operation cost (≈ 6.5ms). Sorting performance for varying sizes of update and query lists is given in Table 1. In update experiments, 4 successive rounds of batched insertions insert 16.8 million key-rowID pairs per round, achieving an overall growth factor of 200% in the data structure. Experiments are performed on the A6000 NVIDIA GPU, which supports 84 SMs and has a maximum threads per block (TPB) assignment of 1024. The frontend benchmark is run on an Intel Xeon Gold 5220 system with 72 physical cores (144 logical threads).
Experiment Setup
The build and setup phase of FliX is described in detail in Section 3.2. To support efficient updatability, we test various update-heavy workloads with varying degrees of dense regions. Experiments in this Section use a build size of 225 (≈ 33 million keys) uniformly distributed key-rowID pairs; additional pairs are inserted through rounds of batched insertions and removed through rounds of batched deletions.
5.3
Formative Experiments
In our formative experiments, we perform a systematic analysis of parameter settings for each update kernel. We explore a cross product of configuration settings in Section 5.3.3 to identify the most performant combinations.
5.2.1 Workloads. Workloads are designed by varying the proportion of the distribution which receives updates. We assign two parameters, 𝑋 and 𝑌 , to define our workloads. 𝑋 is the key range 8
FliX: Flipped-Indexing for Scalable GPU Queries and Updates
Time (ms)
20 15 10 5
round 2
round 3
36
38
43
25
2.5
20
20
2.0
15
15
10
10
0
round 4
1e9
25
5
0 round 1
(d) Memory Footprint/Round
(c) Insert Time: 𝑋 = 6, 𝑌 = 90 197
30
35
39
38
(b) Insert Time: 𝑋 = 25, 𝑌 = 90 179
38
34
34
ST-Shift-Right (FliX) TL-Bulk (FliX) ST-TL-Mixed (FliX) BTree LSMu Hash_Slab Hash_Warpcore
30
Bytes
25
99
(a) Insert Time: 𝑋 = 90, 𝑌 = 90
30
1.5 1.0 0.5
5 round 1
round 2
round 3
0
round 4
FliX BTree LSMu Hash_Slab Hash_Warpcore
round 1
round 2
round 3
round 4
0.0 round 1
round 2
round 3
round 4
Figure 7: Experiments with 4 consecutive rounds of insertions across 3 workloads of varying key densities. The TL-Bulk implementation consistently outperforms the B-tree and HT-Slab and is very comparable to HT-Warpcore. LSMu has the strongest insert performance in all experiments at the cost of significantly higher memory consumption, illustrated in (d). Delete Time: 𝑋 = 90, 𝑌 = 90
Delete Time: 𝑋 = 6, 𝑌 = 90
5.3.2 Hybrid Algorithms (ST-Hybrid & TL-Hybrid). Our ST and TL update kernels can be combined to switch between bulk and shift-right insertions based on the data structure’s state. The default choice is bulk insertions unless certain conditions are satisfied, such as a high node fill state or a low minimum number of keys (MK) remaining to insert, in which case we prefer shift-right insertions. We evaluated various switch-condition heuristics, but the formative experiments indicated that hybrid insertion kernels were less performant than using one approach exclusively. Therefore, these variants are omitted from the heatmap.
Several patterns emerge in the full heat-map results shown in Figure 5. Each row represents one round of insertions tested across all 16 variants of each kernel. Values in each cell are normalized against the best-performing variant per row. A score of 2 indicates that the algorithm takes twice the time as the best-performing variant. The strongest performance and the highest number of 1.0 scores appear in the TL-Bulk insertion kernel with NS=25 and a TPB assignment of 128 threads. This aligns with our observations that tiled insertion algorithms perform best with lower TPB assignments and larger node sizes. This node size matches warp-level execution and reduces the scheduling overhead of smaller groups within a warp. For TL-Bulk specifically, larger node sizes provide additional space per node, enabling more keys to be inserted in a single bulk operation. In addition, the heat map illustrates that ST kernels, particularly ST-Shift-Right when using smaller node sizes (8, 14), remain valuable under lighter insertion pressure. The TL kernels run the risk of under-utilizing all threads in a tile and possibly require oversynchronization, which may impede performance when the perround work is modest. This effect is also visible in Figure 5 (round=0) under uniform distributions (𝑋 = 50%, 𝑋 = 90%), where the first round of insertions for TL-Bulk suggests that a lighter-weight ST strategy could be advantageous before the structure reaches a more insert-heavy state. We design a mixed-insertion strategy that aims to combine the strengths of ST-Shift-Right and TL-Bulk insertions. This strategy is described further in Section 5.3.5. In Section 4.4, we discussed 3 variants of deletion kernels for FliX. A similar cross-comparison heatmap was performed for the deletion kernels; TL-Bulk was found to be the best-performing variant across all workloads, with ideal parameters similar to those used for bulk insertions (NS=25 , TPB=128).
5.3.3 Heat Map: Assessing Node Size/TPB Assignments. In this set of experiments, we evaluate a cross product between workloads with varying 𝑋 , 𝑌 parameters, and two tunable parameters: the node size (𝑁 𝑆) and TPB assignments per kernel. We evaluate 4 node sizes and 4 TPB assignments: (1024(A), 512(B), 256(C), 128(D)), resulting in 16 variants per kernel. Node sizes range from 23 to 25 keys, along with 𝑁 𝑆=14 keys (one cache line (CL)). We evaluate all combinations under various workloads and present a single summary heat map in Figure 5. Each cell corresponds to one insert kernel variant (node size/TPB assignment); darker blue indicates better performance (lower insert time).
5.3.4 Single-Threaded Advantage. Figure 6 (a) is an experiment where the average insertions per bucket is relatively low volume. The data structure build size is 225 with an overall growth factor of 100% in 4 rounds. There are ≈ 4.2 million buckets and 8.38 million uniform insertions per round, resulting in an average of 2 − 3 keys per bucket. Figure 6(b) uses a more dense distribution; a heavier insert workload on a smaller proportion of buckets (25%), which is better suited for TL-Bulk insertions. In our experiments, we observe ST-Shift-Right performs strongly when node sizes are small (one CL or 23 keys), distributions are closer to uniform, and the workload does not exceed 2-5 keys inserted per bucket per
30
Time (ms)
25 20 15 10
ST-Shift-Left (FliX) TL-Shift-Left (FliX) TL-Bulk (FliX) BTree LSMu Hash_Slab Hash_Warpcore
25 20 15 10
5 0
30
5
round 5
round 6
round 7
round 8
0
round 5
round 6
round 7
round 8
Figure 8: Comparing FliX deletion kernels against baselines. 5.3.1 Tile Size, Node Size, and Splitting. The initial build of FliX defines a node size (𝑁 𝑆), which determines how many key-rowID pairs can be stored in addition to per-node metadata. The TL kernels also require a tile size (𝑇 𝑆), which determines how many threads participate in operations per bucket. For this reason, we couple 𝑁 𝑆 and 𝑇 𝑆 in our experiments, setting 𝑇 𝑆 to be the smallest power of two greater than or equal to 𝑁 𝑆. In the build phase, we use an initial node fill state of 50%, leaving room for future insertions before splitting is required. Splitting a node will divide keys into two even halves; maxKey values per node are adjusted accordingly.
9
Rosina Kharal, Trevor Brown, Justus Henneberg, and Felix Schuhknecht
Time (ms)
25
4
Queries/(sec x bytes)
33 42
42
111 109
41
111 109
38
111 109
110 108
111
111 109
111 107
111 108
(a) Query Time (Hit/Miss) 𝑋 = 90, 𝑌 = 90
30
1e 8
3
20 15
(b) Query Throughput / Memory Footprint
FliX BTree
LSMu Hash_Slab
Hash_Warpcore
2
10
FliX BTree
5
LSMu Hash_Warpcore Hash_Slab Hits/Misses
1
0 round 1
round 2 round 3 round 4 round 5 round 6 round 7 round 8 ins/query ins/query ins/query ins/query del/query del/query del/query del/query
0
round 1 round 2 round 3 round 4 round 5 round 6 round 7 round 8 ins/query ins/query ins/query ins/query del/query del/query del/query del/query
Figure 9: FliX (TL-Bulk) query performance against baselines following rounds of insertions and deletions. Figure (a) shows query performance (latency in ms) after each update. Figure (b) reports query throughput normalized by memory usage. Varying Build, Query Sizes
Time (ms)
16 15
12.5
due to the node size and TPB settings used in this approach (NS=3, TPB=256), which are more suitable for ST-Shift-Right insertions. The ST-TL-Mixed approach may nevertheless be useful in settings where the insertion strategy can be selected on a round-by-round basis, according to the expected workload characteristics. We leave this direction to future work. Across all baselines, LSMu achieves the best insertion performance overall, leveraging fast GPU sort-and-merge operations. This advantage comes with higher memory overhead, as indicated in Figure 7(d), due to auxiliary memory buffers required for merge operations. We observe in Figure 7 (d) that FliX’s memory consumption is 2.8× lower than that of LSMu and is also consistently lower than that of the B-tree.
Hash_Warpcore
33
15.0
LSMu Hash_Slab
66
FliX BTree
10.0 7.5 5.0 2.5 0.0
20_21
22_23
24_25
(Build, Query) Pair
25_26
Figure 10: Average query performance across builds.
5.4.1 Deletion Performance. The deletion experiments follow the setup in Figure 7, with 4 rounds of insertions followed by 4 rounds of deletions. Results in Figure 8 show the 4 deletion rounds. We observe that TL-Bulk dominates the other FliX kernels and outperforms all baselines except LSMu. On average, TL-Bulk deletions are 4.4× faster than B-tree, 2.2× faster than HT-Slab, and 1.8× faster than HT-Warpcore. In FliX, deletions merge empty nodes, while the restructuring procedure merges underfull nodes. As a future optimization, deletions could also merge underfull nodes.
round. In Figure 6, we see some applicability of hybrid kernels. We leave this discussion as direction for future work. 5.3.5 Mixed Insertions: ST-TL-Mixed. Motivated by the complementary strengths of ST-Shift-Right and TL-Bulk, we evaluate a dual ST-TL-Mixed insertion strategy on insert-heavy workloads. This approach is distinct from the hybrid kernels, which switch between shift-right and bulk insertions within the same category (ST or TL); instead, ST-TL-Mixed combines kernels across categories. For ST-TL-Mixed, we use NS=23 and TPB=C (256). Since ST-Shift-Right is faster in the first round, and TL-Bulk is faster in subsequent rounds, ST-TL-Mixed switches kernels after the first round. Results are presented in the following section, where we also compare this variant against baselines.
5.4
6
QUERY EXPERIMENTS
Queries in FliX are performed in a TL-Bulk manner as described in Section 3.3. We also tested an ST approach to queries and found it to be less performant, since the sheer number of queries is usually much higher than the total number of buckets in the data structure. In our experiments, 2 batches of point queries are performed at the end of every round, following a batch of insertions or deletions, testing for all hit and all miss keys.
Comparison with Baselines
We now compare the update kernels for FliX against state-of-theart baselines summarized in Figure 7. As in previous experiments, we test 4 consecutive rounds of insertions, achieving an overall 200% growth factor (for a final size that is 300% the initial size). Figure 7 shows that FliX TL-Bulk insertions consistently outperform the GPU B-tree and HT-Slab (over 8.2× faster than Btree and 1.6× faster than HT-Slab), and are comparable to HTWarpcore. The ST-TL-Mixed and ST-Shift-Right kernels, however, are more sensitive to increases in data structure size. In Figure 7 (b)–(c), the denser workloads amplify these differences. The ST-TL-Mixed insertions are less performant in subsequent rounds
6.1
Query Latency vs Memory Usage
We now describe the query experimental setup in detail. Each experiment begins with a uniformly distributed set of build keys. The build keys, plus the set of keys to be inserted in the data structure, are all pre-generated and form the generated key set. The build size in Figure 9 is 100 million keys with an overall growth factor of 100%, achieved through 4 successive rounds of insertions. Subsequently, the same keys are removed in 4 rounds of deletions, returning the 10
FliX: Flipped-Indexing for Scalable GPU Queries and Updates
102
10 6
round 1 round 2 round 3 round 4 round 5 round 6 round 7 round 8
Unsorted Queries (Linear Scale) 50
FliX Sort_time
BTree LSMu
Hash_Slab Hash_Warpcore
22,23
24,25
25,26
40 30 20
10 4
10
10,11
15,16
22,23
24,25
(Build, Query) Pair
0
25,26
(Build, Query) Pair
Figure 12: Unsorted query performance, baselines vs FliX (accounting for the cost of sorting).
Figure 11: Experiments with a build size of 224 achieving a 300% growth factor over 8 rounds of insertions; The degradation in query performance is very low (< 0.5𝑚𝑠), from uniform to highly skewed workloads.
Successor Query Performance FliX (Hits/Misses) FliX (Successor Hits/Successor Misses)
LSMu (Hits/Misses) LSMu (Successor Hits/Successor Misses)
345697 347917
214609 216255
259495 260996
57729 58648
Time (ms)
82850 86504
30 25 20 15 10 5 0 round 1 round 2 round 3 round 4 round 5 round 6 round 7 round 8 ins/query del/query ins/query del/query ins/query del/query ins/query del/query
structure to its original size. Query (probe) keys are drawn at the end of every round as follows: For all-hit experiments, probe keys are randomly selected according to a uniform distribution over the keys currently present in the data structure. For all-miss experiments, probe keys are selected from the generated key set, but restricted to keys that are not presently in the data structure in the current round; repetition is possible in both types of queries. Figure 9 (a) indicates performance for 100 million query keys on a uniform update workload. FliX query performance remains strong and clearly outperforms other ordered data structures; query response time is 6.5× less than the B-tree and on average 1.5× lower than LSMu. In these experiments, we observed very little degradation of query performance when testing with more dense workloads (𝑋 = 6%, 𝑋 = 3%). Round 4 does not contain any miss queries because all keys from the generated key set are contained within the data structure. Figure 9 (b) illustrates Query Throughput per Memory Footprint (QTMF) results, where higher values indicate better throughput per byte. Here, we observe that ordered baselines do not perform well due to high memory consumption. FliX QTMF remains strong even against unordered baselines. We additionally observe the hash tables experience a decline in query performance on miss keys following rounds of deletions. This is due to the accumulation of tombstones, i.e., removed keys that remain as markers in the data structure. The presence of tombstones increases probe lengths for unsuccessful searches, leading to noticeably worse miss performance after multiple rounds of deletions. By round 8 in Figure 9 (a), FliX outperforms both hash tables on miss key queries by 2 − 2.6×. FliX point query performance and QTMF are also illustrated in Figure 2 (Section 1), in experiments where alternate rounds of insertions and deletions occur.
6.2
Hash_Slab Hash_Warpcore
10 2
2 0
BTree LSMu
100
Time (ms)
4
FliX Sort_time
68 183
Unsorted Queries (Logarithmic Scale)
X90Y90
Time (ms)
X25Y90 X50Y90
172656 173312
X6Y90 X12Y90
79
Query Performance: Uniform to Dense Workloads
X2Y90 X3Y90
60865 61639
Time (ms)
6
Figure 13: Successor results comparing the LSMu and FliX.
6.3
Distributional Shifts: Dense Distributions
Recall, a distributional shift can occur when the data structure is built on one distribution, and subsequent operations adhere to a very different distributional spread. This may lead to many tiles remaining inactive, while others receive a large number of operations. We have discussed strategies to mitigate this effect (Section 3.4); however, we assess the impact of our default design strategy, engaging one tile per bucket, under skewed workload distributions. We move to a smaller build size to examine the impact of distributional shifts since, in previous experiments with a 100 million build size, we did not observe a significant performance penalty between uniform and skewed workloads. The experiment in Figure 11 uses a build size of 224 and achieves a 300% growth factor over 8 rounds of insertions; the query size per round is 225 keys. We observe that only a small performance degradation occurs in query performance even when the insertion workload is concentrated on 2% of the distribution. By round 8, 34 of the keys in the data structure originate from the dense key ranges indicated in the graph. There is a penalty of less than 0.5 ms in query performance at round 8 between workloads using a uniform distribution and those using only 2% of the key range. This appears to be a performance penalty we can live with; our results indicate GPU tile utility is highly robust to distributional shifts in the workload.
Varying Build/Query Sizes 6.4
Query performance is further evaluated in Figure 10 across varying build and query pairs. This figure reports the average query time over all hit and miss keys, measured across 5 rounds of insertions where the data structure growth is 200%. Our findings show that FliX remains highly competitive in query performance, often outperforming the baselines in most rounds.
Unsorted Queries
The baselines tested in our work all support unsorted queries, while FliX does not. To be fair to baselines, we experiment with their ability to support unsorted queries and add the cost of sorting to FliX. Figure 12 illustrates the average query performance across 4 rounds of unsorted all hit queries where the data structure growth 11
Rosina Kharal, Trevor Brown, Justus Henneberg, and Felix Schuhknecht
Table 4: Node recovery through restructuring after successive phases of insertions and deletions. Workload X25Y90 X25Y90 X25Y90 X90Y90 X90Y90 X90Y90
Build size 1M 33M 100M 1M 33M 100M
Final size 4M 134M 300M 4M 134M 300M
Nodes recovered through merging 54,623 1,745,428 3,928,746 81,307 2,603,137 6,130,104
7
% recovered 29% 29% 28% 43% 43% 46%
is 200%. We report FliX query time and include the cost of sorting as a stacked bar. We can see that for larger build sizes, the FliX approach of pre-sorting queries on the GPU and then performing an index-less query process is superior to index-based approaches. In the largest build size 225 (≈ 33 million keys), with a query size of 226 (≈ 67 million keys), FliX query latency, including the cost of sorting, is 5× faster than B-tree, over 14× faster than LSMu, and also outperforms both hash tables.
6.5
Successor Results: LSMu & FliX
A successor query returns the smallest key in the data structure that is greater than or equal to a given search key. That is, for a search key 𝑘, the successor operation returns the smallest key 𝑘 ′ satisfying 𝑘 ′ ≥ 𝑘. Figure 13 reports successor-query performance for LSMu and FliX (other baselines are not evaluated for successor queries). As the deletion rate increases, LSMu performance degrades markedly. By round 8, FliX successor query response time is ≈ 69000× lower than LSMu. This heavy degradation in LSMu successor performance stems from tombstone handling: successor queries must traverse levels in the tree while skipping deleted keys, which effectively can become a linear scan by each thread in each level to skip tombstones and locate the next active key. More generally, tombstones impose an unavoidable cost in GPU CDSs; they increase work in queries and insertions, require cleanup or compaction, and increase the memory footprint.
6.6
SUMMARY OF FINDINGS
Across a broad range of update workloads, we show that the choice of update kernel must be workload-aware. For insertions that sustain large growth (≥ 200% over the build size), or insertions containing high skew in the distribution, tiled bulk kernels for insertions and deletions provide the most performance. Under lighter insertion pressure and more modest growth (≤ 100%), single-threaded shiftright insertions remain highly competitive benefiting from smaller node sizes (8 or 14 keys) and avoiding tile-level synchronization overhead. FliX outperforms all baselines in deletion performance, including both hash tables. FliX is surprisingly competitive with, and often superior to, unordered baselines in query, insertion, and deletion performance. Although LSMu achieves strong update performance, it may cause issues for long-running workloads. The LSMu insertion process incurs high memory overhead due to merge operations, and deletions leave behind unconsolidated space. FliX makes more efficient use of GPU memory, surpasses LSMu in query performance and is vastly superior in successor-query performance. While range queries were not evaluated in this work, LSM trees generally struggle to provide competitive range-query performance. Compared to baselines, FliX achieves the best overall QTMF. Although nodes in FliX may contain some unoccupied space, its memory consumption remains far lower than that of LSMu, and is lower than or comparable to the other baselines. Merging underfull nodes through a restructuring process allows FliX to reclaim a significant proportion of memory for continued sustained growth on the GPU. We also find that FliX remains performant under significant distributional shift, with compute-to-bucket assignments continuing to perform well, even as workload skew increases.
8
CONCLUSION
In this work, we presented FliX, a fully GPU-resident indexing CDS that supports fast dynamic updates without sacrificing query performance. By eliminating the traditional index layer and adopting a flipped indexing paradigm that maps compute to buckets, FliX avoids many of the limitations of prior GPU indexing structures. Our results show that FliX achieves the best overall performance among ordered competitors, while also remaining surprisingly competitive with, and often superior to, unordered baselines such as hash tables. In addition, FliX supports sustained long-running execution through GPU-resident restructuring and memory reclamation, and remains robust under substantial distributional shift in workloads. Overall, these results suggest that flipped indexing could offer a practical, efficient, and scalable future for dynamic GPU database indexing.
Restructuring FliX
We evaluate the effect of restructuring by allowing FliX to grow by 300%. These experiments are designed to study how periodic restructuring supports sustained growth and maintains efficient operations over long-running executions. In our experiments, we perform 8 rounds of insertions followed by 8 rounds of deletions, and apply restructuring after the deletion phase. As shown in Table 4, this process recovers up to 46% of node space relative to the size of the data structure under uniform distribution. The recovered space is obtained by merging underfull nodes to form half-full nodes. This state is consistent with the original build configuration of FliX, allowing future insertions to proceed without the immediate need for further node splitting. Infrequent restructuring, which will realign the data structure after many insertions and deletions have occurred, can take anywhere from 200 − 800 ms, depending on the state of the data structure and the frequency.
REFERENCES [1] Dan A. Alcantara, Andrei Sharf, Fatemeh Abbasinejad, Shubhabrata Sengupta, Michael Mitzenmacher, John D. Owens, and Nina Amenta. 2009. Real-time parallel hashing on the GPU. ACM Trans. Graph. 28, 5 (2009), 154. https: //doi.org/10.1145/1618452.1618500 [2] Saman Ashkiani, Martin Farach-Colton, and John D. Owens. 2018. A Dynamic Hash Table for the GPU. In 2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21-25, 2018. IEEE Computer Society, Vancouver, BC, Canada, 419–429. https://doi.org/10.1109/ IPDPS.2018.00052 [3] Saman Ashkiani, Shengren Li, Martin Farach-Colton, Nina Amenta, and John D. Owens. 2018. GPU LSM: A Dynamic Dictionary Data Structure for the GPU. In 12
FliX: Flipped-Indexing for Scalable GPU Queries and Updates
Endowment 10, 3 (2016), 265–276. https://doi.org/10.14778/3021924.3021941 [14] Sparsh Mittal and Jeffrey S. Vetter. 2015. A Survey of CPU-GPU Heterogeneous Computing Management: GPU Architectures, Data Management and Scheduling Strategies. ACM Computing Surveys (CSUR) 47, 4 (2015), 1–38. https://doi.org/ 10.1145/2788396 [15] Nurit Moscovici, Nachshon Cohen, and Erez Petrank. 2017. A gpu-friendly skiplist algorithm. In 2017 26th International Conference on Parallel Architectures and Compilation Techniques (PACT). IEEE, Portland, OR, USA, 246–259. https: //doi.org/10.1109/PACT.2017.13 [16] Johns Paul, Shengliang Lu, and Bingsheng He. 2021. Database systems on GPUs. Foundations and Trends in Databases 11, 1 (2021), 1–108. https://doi.org/10.1561/ 1900000076 [17] Amirhesam Shahvarani and Hans-Arno Jacobsen. 2016. A hybrid B+-tree as solution for in-memory indexing on CPU-GPU heterogeneous computing platforms. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD ’16). Association for Computing Machinery, New York, NY, USA, 1523–1538. [18] Anil Shanbhag, Samuel Madden, and Xiangyao Yu. 2020. A study of the fundamental performance characteristics of GPUs and CPUs for database analytics. In Proceedings of the 2020 ACM SIGMOD international conference on Management of data. Association for Computing Machinery, New York, NY, USA, 1617–1632. https://doi.org/10.1145/3318464.3380595 [19] Harshit Sharma and Anmol Sharma. 2024. A Comprehensive Overview of GPU Accelerated Databases. CoRR abs/2406.13831 (2024). https://doi.org/10.48550/ ARXIV.2406.13831 arXiv:2406.13831 [20] Peng Wang, Guangyu Sun, Song Jiang, Jian Ouyang, Shiding Lin, Chen Zhang, and Jason Cong. 2014. An Efficient Design and Implementation of LSM-tree Based Key-Value Store on Open-Channel SSD. In Proceedings of the Ninth European Conference on Computer Systems. Association for Computing Machinery, New York, NY, USA, Article 16, 14 pages. https://doi.org/10.1145/2592798.2592804 [21] Yijie Wu. 2025. Fast Database Join on Ray-tracing Core Equipped GPU. Ph.D. Dissertation. University of Victoria. [22] Kai Zhang, Kaibo Wang, Yuan Yuan, Lei Guo, Rubao Lee, and Xiaodong Zhang. 2015. Mega-KV: A Case for GPUs to Maximize the Throughput of In-Memory Key-Value Stores. Proc. VLDB Endow. 8, 11 (2015), 1226–1237. https://doi.org/10. 14778/2809974.2809984
2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21-25, 2018. IEEE Computer Society, N/A, 430–440. https://doi.org/10.1109/IPDPS.2018.00053 [4] Muhammad Abdelghaffar Awad. 2022. Fully Concurrent GPU Data Structures. Ph.D. Dissertation. University of California, Davis. [5] Muhammad A. Awad, Saman Ashkiani, Rob Johnson, Martín Farach-Colton, and John D. Owens. 2019. Engineering a high-performance GPU B-Tree. In Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming (Washington, District of Columbia) (PPoPP ’19). Association for Computing Machinery, New York, NY, USA, 145–157. https://doi.org/10.1145/3293883.3295706 [6] Jiashen Cao, Rathijit Sen, Matteo Interlandi, Joy Arulraj, and Hyesoon Kim. 2023. Gpu database systems characterization and optimization. Proceedings of the VLDB Endowment 17, 3 (2023), 441–454. https://doi.org/10.14778/3632093.3632107 [7] Mark Harris and Kyrylo Perelygin. 2017. Cooperative Groups: Flexible CUDA Thread Programming. (2017). https://developer.nvidia.com/blog/cooperativegroups/ [8] Justus Henneberg and Felix Schuhknecht. 2023. RTIndeX: Exploiting HardwareAccelerated GPU Raytracing for Database Indexing. Proc. VLDB Endow. 16, 13 (2023), 4268–4281. https://www.vldb.org/pvldb/vol16/p4268-schuhknecht.pdf [9] Justus Henneberg, Felix Schuhknecht, Rosina Kharal, and Trevor Brown. 2025. More Bang for Your Buck(et): Fast and Space-Efficient Hardware-Accelerated Coarse-Granular Indexing on GPUs. In 2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE, Hong Kong, China, 1320–1333. https://doi. org/10.1109/ICDE65448.2025.00103 [10] Daniel Jünger, Robin Kobus, André Müller, Christian Hundt, Kai Xu, Weiguo Liu, and Bertil Schmidt. 2020. WarpCore: A Library for fast Hash Tables on GPUs. In 27th IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2020, Pune, India, December 16-19, 2020. IEEE, Pune, India, 11–20. https://doi.org/10.1109/HIPC50609.2020.00015 [11] Brenton Lessley, Shaomeng Li, and Hank Childs. 2020. HashFight: A PlatformPortable Hash Table for Multi-Core and Many-Core Architectures. Electronic Imaging 32, 1 (2020), 376–1–376–13. https://doi.org/10.2352/ISSN.2470-1173. 2020.1.VDA-376 [12] Hao Li, Yi-Cheng Tu, and Bo Zeng. 2019. Concurrent query processing in a GPU-based database system. PloS one 14, 4 (2019), e0214720. [13] Chunbin Lin, Benjamin Mandel, Yannis Papakonstantinou, and Matthias Springer. 2016. Fast In-Memory SQL Analytics on Typed Graphs. Proceedings of the VLDB
13