ADMS '26 · VLDB 2026 · GPU query processing

Rubberband

Memory-elastic, skew-tolerant GPU hash joins

Hangdong Zhao · Rathijit Sen · Craig Peeper · Matteo Interlandi

The baseline

Open addressing is the default for CPU hash joins—and is becoming the go-to design for GPU hash joins too.

Build phase

h(t) = 8, so t starts at slot 8.

th(t) = 8 uh(u) = 1 w₁h(w) = 2 w₂h(w) = 2 v₁h(v) = 7 v₂h(v) = 7 v₃h(v) = 7 v₄h(v) = 7

probe key v h(v) = 7 · stride = 2

∅0

∅1

∅2

∅3

∅4

∅5

∅6

∅7

∅8

∅9

∅10

∅11

∅12

∅13

∅14

∅15

∅16

insertion path

Press Insert or Enter

w₁ and w₂ form one self-contained chain at slots 2 and 4; it does not involve any v row.

t hashes independently to slot 8. It sits physically between v₁ at slot 7 and v₂ at slot 9, but the stride-two v path jumps over it with no interference.

After v₄ lands, pause on the build-complete handoff. The next click visibly changes the whole slide to probe mode.

Probe v starts at slot 7, finds v₁ through v₄ at slots 7, 9, 11, and 13, then stops at empty slot 15. It never reads t at slot 8.

The OA slot hash h(·) and the Rubberband bucket mapping shown later reduce into different ranges, so their numerals need not match.

Build uses CAS. Probe does not use CAS; it performs scattered reads. The classic walk is shown; the evaluated baseline adds per-slot step counters to skip and terminate sooner.

Shortcoming 1

Skew makes both build and probe more expensive.

Rows can be interleaved in memory without sharing a probe path.

as the shared path grows

Build more CAS attempts

Probe more scattered reads

∅0

w₁2

∅3

w₂4

∅5

∅6

v₁7

v₂9

∅10

v₃11

∅12

v₄13

∅14

∅15

∅16

w chain2 → 4 v probe sequence7 → 9 → 11 → 13 → ∅15 tslot 8 · skipped

Shortcoming 2

Open addressing lacks memory elasticity.

The table is hard to shrink when HBM gets tight.

shrinking H by fudge factor risks a collision cliff

∅0

w₁2

∅3

w₂4

∅5

∅6

v₁7

v₂9

∅10

v₃11

∅12

v₄13

∅14

∅15

∅16

all 17 slots remain resident

Other DBMS components contend for HBM → H stays fixed at 17

Introducing Rubberband

Two new ingredients,
co-designed.

Logical rewrite

Equality hoisting

Physical layout

CSR-style hash-table layout

Idea 1 · equality hoisting

The hash-index resolution can be relaxed.

Exact lookup

hash join x = y

A.xB.y

hoist →

Approximate lookup

post-filterx = y

↑

bucket join φ(x) = φ(y)

A.xB.y

A ⋈_x=y B ≡ σ_x=y(A ⋈_φ(x)=φ(y) B)

φ(v) = v A.x = B.y

Hash join

φ ≡ 1 σ_x=y(A × B)

Nested loop join

φ(v) = hash(v) mod K flexible lookup resolution

Our tunable embedding

CSR stores rows densely.

Offsets mark contiguous buckets.

Dense rowIds

offsets

00 11 22 43 84 85

rowIds

w₁✓2

w₂✓3

v₁4

v₂5

v₃6

v₄7

N = 8 · no empty slots

Shrink K by removing boundaries.

Rows stay fixed. Buckets merge.

K: 5 → 3 · rows fixed

offsets

00 11 42 83

rowIds

u×1

w₁✓2

w₂✓3

v₁4

v₂5

v₃6

v₄7

same 8 rows · 6 → 4 offsets

Count

Two arrays, zeroed. Count one row per click.

tb0 ub1 w₁b2 w₂b2 v₁b3 v₂b3 v₃b3 v₄b3

count 0 / 8

offsets K + 1 = 6

0[0]

0[1]

0[2]

0[3]

0[4]

0[5]

rowIds N = 8

∅0

∅1

∅2

∅3

∅4

∅5

∅6

∅7

1countatomicAdd per row 2scansame buffer, new meaning 3scatteratomicAdd returns the slot

Probe

Probe key v. One hash locates the bucket.

probe key v φ(v) = h(v) mod 5 = 3

0 / 6

offsets

0[0]

1[1]

2[2]

4[3]

8[4]

8[5]

rowIds

w₁2

w₂3

v₁4

v₂5

v₃6

v₄7

read path

Press Hash or Enter

Recap

same exact output v₁ · v₂ · v₃ · v₄

Final open-addressing probe path across slots 7, 9, 11, 13, and empty slot 15 — **Scattered probe** 7 → 9 → 11 → 13 → empty 15

Final Rubberband probe with offsets 4 and 8 framing row IDs 4 through 7 — **Contiguous probe** offsets 4 and 8 frame rowIds[4, 8)

Open addressing checks occupancy Rubberband checks bucket boundaries

Experiments

Memory elasticity

TPC-H SF100 22 full queries

Skew tolerance

Production skewed workloads

H100 NVL94 GB HBM3 · CUDA 12.8 Production engineMicrosoft CoddSpeed · SIGMOD'26 Industry Best Paper Median of 5runs after warm-up

TPC-H SF100 · orders ⋈ lineitem

150M build × 600M probe · build + probe runtime

This companion view isolates one DataHotRod inner join over real SF100 columns: build 150,000,000 unique int32 orders.O_ORDERKEY values, then probe 600,037,902 lineitem.L_ORDERKEY values decoded from the captured TPC-H SF100 columnstore. Every probe row found exactly one order.

The timed region is only GPU hash-table build plus inner-join probe. Reading the extracted tensors and transferring them to the GPU happen before timing. Each plotted point is the median of five independent processes, each with one warm-up and five timed executions.

The memory labels use exact implementation allocations; the next suite slide uses a steady-state table model. OA allocates 2.807 GB for its table and step arrays. Rubberband allocates its offsets and row IDs, from 1.319 GB at K / N = 1.05 down to 0.632 GB at K / N = 0.05. The x-axis is the configured factor; the implementation selects an advised capacity, whose actual K / N is recorded in the accompanying CSV.

The 4.800 GB output-index allocation is identical for OA and Rubberband and is deliberately excluded from the table-memory savings. The unique orders build is detected at runtime, so Rubberband takes its production compact-unique probe path.

This is the microscope view. The next slide zooms out from one real PK–FK join to aggregate GPU execution across the full 22-query suite.

The final click reveals the takeaway after the complete memory sweep.

TPC-H SF100 · 22-query aggregate

GPU execution as the bucket budget tightens

This zooms out from the preceding join to a fresh reproduction on DataHotRod commit 914a73fc5 using the captured TPC-H SF100 CSI on this H100 NVL. The plotted value is the sum of GPU execution time across all 22 queries, normalized to open addressing within the same process round; lower is better.

Each point is the median of five independent processes. Every process performs one correctness warm-up and five timed executions per query. All 990 expected-result comparisons passed, including K / N = 0.05.

The shaded percentages are the steady-state single-key hash-table allocation model, not full-query peak memory: open addressing uses about 16N bytes, while Rubberband uses about 4(K + N). Scans, aggregates, cached inputs, and multi-key joins remain outside that table-only number.

As one concrete path, TPC-H Q3 joins customer (15M rows), orders (150M), and lineitem (600,037,902). The runner reports 28 ms for OA/default and 39 ms at K / N = 0.05; because per-query summaries are integer milliseconds, this is a coarse stress example and is not plotted.

This is a pre-spill tuning envelope rather than a forced host-spill experiment. The measured claim is continuity: tightening K adds scan work gradually, giving the engine a usable control before HBM exhaustion.

The final click reveals the takeaway after the complete memory sweep.

TPC-H SF100 · 6 PK–FK joins

Build, probe, and end-to-end speedup vs open addressing

Speedup vs OA · log

Default K / N = 1.05 47–57% of OA table

Tightened HBM K / N = 0.15 24–29% of OA table

TPC-H SF100 · 22 full queries

Peak intermediate HBM and end-to-end runtime · K / N = 1.05

* Join-heavy · hash table dominates peak HBM

11 production join captures

#0–2 mostly distinct · #3–10 duplicate-heavy

Speedup vs OA · log

Default K / N = 1.05 ≈50% of OA table

Tightened HBM K / N = 0.15 ≈25% of OA table

These were sampled from traces flagged as slow under the baseline, so they are the hard cases rather than a friendly average.

The upper panel is the default K = 1.05N setting. The lower panel tightens HBM to K = 0.15N.

Captures 0 to 2 are mostly distinct. Captures 3 to 10 hold 353K rows over only 15 to 300 distinct keys, so the build bars separate the two regimes immediately and barely move when K shrinks.

Finish the upper default-memory panel first: Build, then Probe, then End-to-end. The next click reveals the complete tightened-HBM panel in one step.

No hot-key detector, repartitioning pass, or separate skew kernel is used.

The next slide isolates capture #11 and reports the extreme-skew result. The following slide explains why it happens.

The final click reveals the takeaway only after the tightened-HBM result is complete.

Production capture #11

One key owns 55% of the build.

12.5M build rows · speedup over open addressing

Build-key distribution 12.5M rows

Default K / N = 1.05 ≈50% of OA table

435×Build 1,048×Probe 722×End-to-end

Two structural reasons

Why does Rubberband work so well under skew?

01 Regularize the hot path.

Retrying CAS and scattered chain walks become first-try adds and one contiguous scan.

Open addressing CAS + scattered chains

Build

CAS ↻

Retries pile onto the hot slot.

Probe

v···v···v···v

Each probe re-walks a long random chain.

Rubberband add + contiguous scan

Build

+1 ✓

Every atomicAdd commits first try.

Probe

K = 6 7 offsets

offsets

0666666

rowIds

vvvvvv

scan [0, 6)

One cooperative, bandwidth-bound scan.

The previous slide established the result. This slide gives the two structural reasons, not a special skew optimization.

Open addressing inserts with compare-and-swap. Under a hot key, millions of threads contend on a few slots, retries spiral, and probes repeatedly walk the resulting scattered chain.

Rubberband replaces that with additive atomics: tally and scatter each perform one atomicAdd per row, and every increment succeeds on the first try.

Probe loads one adjacent offset pair and scans the framed rowIds slice contiguously. The non-unique path cooperatively splits a fat bucket across threads, keeping each portion near 64 consecutive rows.

On the next click, keep the same demonstration in place. Open addressing dims while the Rubberband directory collapses from K = 6 to K = 1.

With six identical rows, K = 6 stores offsets [0, 6, 6, 6, 6, 6, 6]; K = 1 stores only [0, 6]. The rowIds array and probe scan [0, 6) do not move, so only five empty bucket boundaries disappear.

Strictly, one bucket uses two offset endpoints. General duplicate-heavy data is the same intuition less extremely: D stays far below N, so K can shrink substantially while remaining larger than D, preserving a low false-positive rate and similar runtime.

Summary

Rubberband:
Memory-Elastic, Skew-Tolerant GPU Hash Joins

Equality hoisting. Join on buckets, post-filter x = y.
Elastic CSR-style layout. Less HBM, more false positives.

Thank you

Rubberband

Open addressing is the default for CPU hash joins—and is becoming the go-to design for GPU hash joins too.

Skew makes both build and probe more expensive.

Open addressing lacks memory elasticity.

Two new ingredients,co-designed.

Equality hoisting

CSR-style hash-table layout

Idea 1 · equality hoisting

CSR stores rows densely.

Shrink K by removing boundaries.

Recap

Experiments

Memory elasticity

Skew tolerance

TPC-H SF100 · orders ⋈ lineitem

TPC-H SF100 · 22-query aggregate

TPC-H SF100 · 6 PK–FK joins

TPC-H SF100 · 22 full queries

11 production join captures

One key owns 55% of the build.

Why does Rubberband work so well under skew?

Rubberband:Memory-Elastic, Skew-Tolerant GPU Hash Joins

Two new ingredients,
co-designed.

Rubberband:
Memory-Elastic, Skew-Tolerant GPU Hash Joins