Hash Index for Arrow Acceleration

Experimental

Hash index is an experimental feature available in Spice v1.11.0-rc.2 and later.

The hash index is an optional, high-performance indexing feature for Arrow-accelerated datasets. It provides O(1) point lookups on primary key columns, dramatically improving query performance for equality predicates.

Key Features

• O(1) Point Lookups: Direct row access via primary key without full table scans
• 256-Shard Design: Minimizes lock contention for concurrent reads
• SIMD-Optimized Hashing: Uses XXH3_64 for fast, high-quality hashing
• Built-in Bloom Filter: Fast negative lookups to skip unnecessary hash table probes
• Auto-Threshold: Index is only built when data size exceeds a minimum threshold

Configuration

To use the hash index, explicitly enable it and specify a primary key:

datasets:
  - from: s3://bucket/orders.parquet
    name: orders
    acceleration:
      engine: arrow
      primary_key: order_id
    params:
      hash_index: enabled

Configuration Options

Parameter	Type	Required	Default	Description
hash_index	enabled/disabled	No	disabled	Enable hash indexing
primary_key	string or list	Yes (if hash_index enabled)	None	Column(s) to index

Supported Data Types

The hash index supports the following primary key column types:

Primitive Types

• Int8, Int16, Int32, Int64
• UInt8, UInt16, UInt32, UInt64

String Types

• Utf8, LargeUtf8

Binary Types

• Binary, LargeBinary

Query Optimization

The hash index automatically accelerates queries with equality predicates on indexed columns.

Optimized Queries

-- Single key lookup (uses index)
SELECT * FROM my_dataset WHERE id = 123;

-- Multiple key lookups (uses index for each key)
SELECT * FROM my_dataset WHERE id IN (1, 2, 3);

Non-Optimized Queries

-- Range queries (full scan)
SELECT * FROM my_dataset WHERE id > 100 AND id < 200;

-- Pattern matching (full scan)
SELECT * FROM my_dataset WHERE id LIKE 'A%';

-- Composite key partial match (full scan)
SELECT * FROM my_dataset WHERE region = 'US';
-- (If composite key is (region, customer_id), both must be specified)

Index Threshold

The hash index is only built when the dataset exceeds a minimum size:

threshold = 256 × CPU_cores

CPU Cores	Minimum Rows for Index
1	256
4	1,024
8	2,048
16	4,096
32	8,192

For small tables below the threshold, a full scan is faster than index maintenance overhead.

Performance

Bloom Filter Performance

The built-in bloom filter provides:

• ~0.82% false positive rate (10 bits/item, 7 hash functions)
• O(1) negative lookup confirmation
• Reduced unnecessary hash table probes for non-existent keys

Memory Usage

Component	Memory per Entry
Hash slot	16 bytes (8-byte hash + 8-byte location)
Bloom filter	~1.25 bytes
Total	~17.25 bytes per indexed row

Estimating Memory

For a 10 million row dataset:

Index memory ≈ 10M × 17.25 bytes ≈ 165 MB

Architecture

Sharded Hash Table

The index uses 256 independent shards to minimize lock contention:

┌────────────────────────────────────────────────┐
│                  HashIndex                     │
├────────────────────────────────────────────────┤
│  ┌─────────┐ ┌─────────┐      ┌─────────┐      │
│  │ Shard 0 │ │ Shard 1 │ ...  │Shard 255│      │
│  │ RwLock  │ │ RwLock  │      │ RwLock  │      │
│  └────┬────┘ └────┬────┘      └────┬────┘      │
│       │           │                │           │
│       ▼           ▼                ▼           │
│  ┌─────────┐ ┌─────────┐      ┌─────────┐      │
│  │  Hash   │ │  Hash   │ ...  │  Hash   │      │
│  │  Table  │ │  Table  │      │  Table  │      │
│  └─────────┘ └─────────┘      └─────────┘      │
├────────────────────────────────────────────────┤
│  ┌─────────────────────────────────────────┐   │
│  │        Optional Bloom Filter            │   │
│  │        (Fast Negative Lookups)          │   │
│  └─────────────────────────────────────────┘   │
└────────────────────────────────────────────────┘

Shard Selection: Uses XOR-folded hash bits: ((hash >> 56) ^ (hash >> 48) ^ hash) & 0xFF

Row Location

Each indexed key maps to a RowLocation:

RowLocation {
    partition: u32,  // Partition index
    batch: u32,      // Batch index within partition
    row: u32,        // Row index within batch
}

Hash Function

Uses XXH3_64 with a fixed seed (0x5370_6963_6541_4920 = "SpiceAI ") for:

• Deterministic hashing across instances
• High-quality distribution (passes SMHasher)
• SIMD acceleration on arm64/amd64

Limitations

1. Arrow Engine Only: Hash index is only available for engine: arrow acceleration
2. Single Key Lookups: Optimizes equality predicates, not ranges or patterns
3. Experimental: API and behavior may change in future releases
4. No Persistence: Index is rebuilt on restart (data persists, index is in-memory)
5. Duplicate Keys: Primary key columns must have unique values

Troubleshooting

"No index available for point lookup"

Cause: Dataset row count is below the index threshold.

Solution: This is expected behavior for small datasets. The full scan is faster than index overhead.

Warning: "Add 'hash_index: enabled' to use primary_key for fast lookups"

Cause: primary_key is specified but hash_index is not enabled.

Solution: Add hash_index: enabled to params:

params:
  hash_index: enabled

High Memory Usage

Cause: Index consumes ~17 bytes per row.

Solution:

• Disable hash_index for datasets where point lookups are rare
• Consider using a different acceleration engine for very large datasets