gpu-join

A unified benchmark and study of equi-join algorithms on GPUs — four hand-written CUDA implementations (vector/gather, non-partitioned hash, radix-partitioned hash, sort-merge), plus tensor-core and industrial-library (cuDF) baselines, evaluated across two-table micro-benchmarks and multi-table end-to-end workloads (SSB, TPC-H) on two GPUs with a 12× difference in L2 cache size.

The headline result: on dense primary-key / foreign-key joins, a simple gather (direct addressing) dominates by an order of magnitude, and the cache-cliff that governs join throughput is determined precisely by L2 cache capacity — confirmed both across GPUs and with Nsight Compute hardware counters.

Continuation of a CPU-side main-memory join study; this repo is the GPU phase.

Key results

Two-table join, |R| = 64M ⋈ |S| = 16M (G tuples/s):

Algorithm	RTX 4090	A10
VJ (gather / direct addressing)	37.6	6.31
SMJ (sort-merge)	4.95	2.71
NPO (non-partitioned hash)	2.84	1.80
PRO (radix-partitioned hash)	2.31	1.35

1. Dense-key gather (VJ) dominates — 13× over non-partitioned hash, 16× over cuDF. Its footprint is ~4× smaller than a hash table, so it stays L2-resident ~4× longer.
2. The cache-cliff = working set exceeding L2. On two GPUs whose L2 differs 12× (4090: 72 MB, A10: 6 MB), the VJ cliff moves by exactly 12× (|S| ≈ 18M ↔ 1.5M). Nsight Compute confirms the L2 hit rate collapses from 77–87% to 0.7–4% at the cliff.
3. Tensor-core (one-hot matmul) join is non-competitive for dense-key PK-FK joins: O(nR·nS²) cost, throughput collapses quadratically with key cardinality, OOMs early, and is 40× slower than VJ even at its best.
4. The effective GPU optimizations are structural, not CPU-style latency hiding. Block-level reduction of the aggregation gives 11.3×; shrinking the hash table (footprint) gives +29% near the L2 boundary; but software prefetch and cache-bypass (__ldcs) give ~0% — they are subsumed by massive multithreading (a sharp contrast with the CPU side, where prefetch was worth +54%).
5. cuDF (industrial GPU library) is slowest everywhere — 48–101× slower than the fused kernels on multi-table joins, because it materializes pairwise-merge intermediates.

See src/figs/ for all nine figures (cache-cliff, cross-GPU, ncu counters, skew, block-reduction, optimization knobs, tensor-core, library, multi-table).

Repository layout

datagen/            列存负载生成器 (rs / SSB / TPC-H), 自带正确性 oracle
  gen_join.c
src/
  common/           host 驱动: 列存加载、CPU golden reference、cudaEvent 计时、块归约
    columnar.hpp  reference.hpp  bench.hpp  cuda_util.cuh  harness.cpp
  twojoin/          两表四算法统一驱动 (vj | npo | pro | smj) + 优化变体
    twojoin.cu
  multijoin/        多表执行器 (SSB 星型 / TPC-H 六表)
    multijoin.cu
  baselines/        cuDF + PyTorch (tensor-core matmul / 排序张量) 基线
    cudf_join.py  torch_join.py
  scripts/          一键编译/验证/扫描/剖析/绘图脚本
  figs/             9 张结果图 (PNG)

Build & run

Requires a CUDA-capable NVIDIA GPU + CUDA toolkit (tested on CUDA 12.6/12.8).

# 1. build (ARCH: RTX 4090 = sm_89, A10 = sm_86, A100 = sm_80, ...)
cd datagen && make && cd ../src && make ARCH=sm_86

# 2. smoke test: compile + correctness gate (every kernel double-checked vs
#    an analytic oracle AND a CPU golden reference; expects 9/9 PASS)
bash scripts/smoke_gpu.sh

# 3. full experiment sweeps -> results/
bash scripts/run_all.sh        # 4 algorithms / crossover / skew / multi-table
bash scripts/run_baselines.sh  # tensor-core cardinality boundary + cuDF/torch
bash scripts/run_opt.sh        # optimization knobs (block-reduce / load-factor / ldcs / ILP)
bash scripts/run_ncu.sh        # Nsight Compute counters (needs root / profiling perm)

# 4. regenerate figures from results
python3 scripts/plot_results.py

Single-algorithm run:

./datagen/gen_join rs --rsize 64000000 --ssize 16000000 --out data/rs --verify
./src/twojoin/twojoin data/rs vj 10      # vj | npo | pro | smj

No GPU? The host layer (loader, CPU reference, oracle checking) is pure C++ and builds locally for testing the data path: cd src && make harness.

Correctness

Every join is verified two ways and must pass both:

• Analytic oracle — the generator produces full-match foreign keys (even coverage + Knuth shuffle), so the result cardinality equals |probe table| and the payload sum is known a priori (written to expected.txt).
• CPU golden reference — an independent CPU re-computation of the same join.

Design notes & papers

Algorithm and design notes (Sioulas ICDE'19, Rui&Tu SSDBM'17, TCUDB/TQP, Crystal, HeavyDB, etc.) informed the implementations; the optimization knobs and oracle scheme are ported from the CPU-side study. The benchmark deliberately uses dense surrogate keys (the OLAP dimension-table setting) where direct addressing applies.

License

MIT © 孙煜 (SyKM666)