GPUHashIndex

Overview

GPUHashIndex builds a fixed-capacity uint32 key/value lookup table, and GPUHashIndexQuery looks up one logical sequence of packed keys without submission or CPU readback. Together they provide the sparse identity lookup that dense group arrays cannot: map stable object IDs to rows, join sparse feature IDs to attributes, deduplicate identifiers, or resolve categorical dictionaries whose key space is much larger than their population.

The first contract is deliberately bounded. Capacity is chosen up front, every row examines at most maxProbeCount slots, one key value is reserved as the empty marker, and both build and query publish collision-work statistics. This makes worst-case GPU work and memory visible to command- graph consumers instead of hiding resize, allocation, or readback behind a map-like API.

At a glance

Question	Answer
Problem	Map sparse uint32 keys to values without allocating a dense key-space-sized array.
Reads / writes	Reads keys/values; writes a fixed-capacity open-addressed table and probe diagnostics.
Ownership	Public inputs and outputs are caller-owned; scratch storage is graph-owned transient memory.
Output contract	A reusable GPUHashIndexView with explicit duplicate and overflow policy.
Expected work	Linear build/query rows with bounded open-addressing probes.
Chunks	Keys, values, and query outputs accept independent chunks; the shared table remains one bounded binding.
Conditions / budgets	May be conditioned with its dependent branch; encoding, submission, and publication remain application-owned.
Neighborhood	sparse keys/values → GPUHashIndex → GPUHashIndexQuery or GPUHashJoin.

CostTable load factor and hash distribution dominate work.

Common mistakeDo not ignore duplicate-key policy or probe-limit diagnostics.

Choosing the right hash-graph feature

These features compose; they do not provide competing command schedulers or silently concatenate their inputs:

Feature	Input it owns logically	Use it when
GPUHashIndex	One logical right-side sequence, stored in one or many chunks.	Build a shared dictionary with independently partitioned keys and values, or contiguous generated row IDs.
GPUBatchHashIndex	Several ordered right-side key chunks with batch metadata.	Supply per-chunk generated row-ID bases or validity masks with matching topology.
GPUHashIndexQuery	One logical left-side sequence against either index type.	Every source row must retain its position, a found mask, and an optional matched value.
GPUHashJoin	One logical left-side sequence against either index type.	Only matching left/right row pairs should be published, with an explicit output capacity.
GPUBatchHashJoin	Several preserved left-side chunks against either index type.	Independent source batches need separate stable pairs, counts, capacities, and diagnostics.

The right-index choice and left-query choice are independent. For example, a GPUBatchHashIndex can index many Arrow record batches while GPUHashIndexQuery looks up one interactive selection, or GPUBatchHashJoin can join many left batches against that same shared multi-batch index. Every object contributes commands to the caller's existing GPUCommandGraph.

Concepts

Sparse identity is different from dense grouping

GPUGroupAggregation is ideal when category IDs are dense: group i writes output row i. That would be wasteful for object IDs such as 17, 8042, and 3900000000, because a direct-address array must cover the largest possible ID. A hash index stores only a caller-selected capacity and turns each sparse key into a bounded sequence of table probes.

This is the useful bridge between GPU-resident datasets. A visibility result can contain stable object IDs while a property table uses unrelated row numbers; a hash query maps the IDs to rows so a later compute or render pass can gather attributes. The same mechanism supports sparse joins, feature registries, selection membership, and dictionary decoding.

Why hash instead of sort and binary search?

A sorted key/value table offers deterministic layout and logarithmic lookup, and is often better when ordered traversal or range queries are also required. A hash index targets repeated exact-key queries: build once, then resolve many changing batches with near-constant expected work. It also avoids sorting the source solely to establish an identity map.

The tradeoff is explicit. Open addressing becomes more expensive as the table fills, and hostile or unlucky key distributions can consume the probe limit. The build statistics make that cost observable so an application can choose a larger capacity, increase the probe bound, or switch to a sorted representation based on evidence.

Capacity, probing, and overflow

Capacity must be a positive power of two. Keys are hashed to an initial slot and use linear probing for at most maxProbeCount slots, which defaults to capacity. 0xffffffff is reserved as GPU_HASH_INDEX_EMPTY_KEY; source rows containing it are counted as invalid and query rows containing it are reported missing without probing.

The build never resizes. When a distinct key cannot claim or find a slot within the bound, its row increments the overflow statistic. At capacity, the number of retained distinct keys is exact but the retained subset is intentionally unspecified because parallel insertion order is not a source- order contract. Applications that require a particular retained subset must size the table to avoid overflow or preprocess the keys.

Duplicate keys retain a deterministic value

Parallel insertion order does not decide duplicate values. Each occupied slot atomically retains the lowest source-row index, and a final pass copies that row's value. Rebuilding the same inputs therefore produces the same key-to-value mapping even when workgroups execute in a different order. When no value input is supplied, the retained value is firstValue + sourceRow, making the primitive directly useful as a key-to-row index.

An empty explicit values view is also valid, including a zero-length view positioned at the end of its backing buffer. Empty rebuilds clear the table and statistics without binding unavailable input rows.

Chunks form one logical sequence

Keys, explicit values, and query outputs may have different physical boundaries. Lowering intersects those boundaries using borrowed views; it does not concatenate or copy caller data. Generated IDs and duplicate winners use global source positions, including when duplicates cross chunks. Empty chunks do not add rows, and empty builds and queries still clear their statistics.

Each nonempty build span contributes insertion and finalization passes to the shared table. Queries initialize statistics once and accumulate results across all spans. The table keys, table values, and build source-row scratch each remain one capacity-sized binding; individual active source and destination spans must fit device limits. Fragmentation increases dispatch count and repeats table finalization work. Partitioning may change physical table layout, probe counts, and the retained subset when overflow occurs; without overflow, key-to-value results remain stable.

Statistics expose the cost model

Build statistics contain:

[unique keys, duplicate rows, overflow rows, invalid rows, total probes, maximum probes]

Query statistics contain:

[found keys, missing keys, total probes, maximum probes]

The per-query probes output supports finer diagnostics. Load factor unique / capacity, average probes, maximum probes, and overflow together indicate whether the chosen capacity and bound are healthy. Counters are uint32; construction rejects workloads whose maximum aggregate probe count would overflow them.

Graph ownership and current scope

Callers own the persistent input and output buffers. The build contributes initialization, parallel insertion, and deterministic value-finalization passes; the graph owns only one transient source-row buffer. Query contributes statistics initialization and lookup. Neither object compiles, encodes, submits, resizes, or reads back on its own.

Build and query accept packed uint32 atomic views or vectors with independent chunk boundaries. GPUBatchHashIndex adds per-chunk generated row-ID bases and validity masks, while GPUHashJoin and GPUBatchHashJoin provide global or per-batch bounded row-pair publication. Deletion and tombstones, 64-bit keys, custom hash callbacks, independently partitioned right tables, and one-to-many matches remain outside the current contracts.

Usage

const index = new GPUHashIndex({
  keys: objectIds,
  values: objectRows,
  tableKeys,
  tableValues,
  statistics: buildStatistics,
  maxProbeCount: 32
});
graph.add(index);

graph.add(new GPUHashIndexQuery({
  index,
  keys: selectedObjectIds,
  values: selectedRows,
  found: selectedRowsFound,
  probes: selectedRowsProbeCounts,
  statistics: queryStatistics
}));

To generate row IDs instead of reading an aligned values buffer:

graph.add(new GPUHashIndex({
  keys: featureIds,
  firstValue: batchBaseRow,
  tableKeys,
  tableValues,
  statistics: buildStatistics
}));

Constructors

new GPUHashIndex({
  id?,
  keys,
  values?,
  firstValue?,
  tableKeys,
  tableValues,
  statistics,
  maxProbeCount?
});

new GPUHashIndexQuery({
  id?,
  index,
  keys,
  values,
  found,
  probes,
  statistics,
  maxProbeCount?
});

Keys, explicit values, and query outputs accept packed GraphDataView<'uint32'> or GraphVectorView<'uint32'> values in the target graph. Tables and statistics remain atomic views. Table key and value capacities must match, build statistics require six rows, query statistics require four rows, and aligned query outputs must match the query-key length. Writable views cannot overlap each other or their read inputs.