Limitations

Every technology choice involves trade-offs. Hash indexes achieve O(1) point query performance by sacrificing capabilities that B+-trees provide effortlessly. Understanding these limitations isn't pessimism—it's engineering maturity. The worst outcome isn't choosing B+-tree over hash and losing some performance. The worst outcome is choosing hash and discovering, after deployment, that your workload requires capabilities hash indexes fundamentally cannot provide.

This page examines hash index limitations with the same rigor we applied to their strengths. By the end, you'll know exactly when to reach for hash indexes—and when to step back.

The most fundamental limitation of hash indexes is their complete inability to support range queries. This isn't a performance issue—it's a structural impossibility.

Why range queries fail:

Hash functions deliberately destroy key ordering. Consider keys 100, 101, and 102:

h(100) = 47
h(101) = 892
h(102) = 3

Consecutive keys hash to completely unrelated buckets. There is no path from bucket 47 to bucket 892 to bucket 3. The structure that would enable traversal simply doesn't exist.

Contrast with B+-tree:

In a B+-tree, keys 100, 101, 102 are stored sequentially in leaf nodes. A range query WHERE key BETWEEN 100 AND 200 starts at 100 and follows leaf pointers until reaching 200. The structure inherently supports ordered traversal.

The cost of range queries with hash indexes:

When a query requires range access on a hash-indexed column, the database must:

1. Ignore the hash index entirely — The optimizer recognizes it cannot help
2. Fall back to table scan — Read every row, test range condition
3. Or use a different index — If another index exists on the column

Example scenario:

-- You create a hash index for point queries
CREATE INDEX idx_order_date_hash ON orders USING HASH (order_date);

-- This query cannot use the hash index
SELECT * FROM orders 
WHERE order_date BETWEEN '2024-01-01' AND '2024-01-31';

-- The optimizer will use:
-- 1. Seq Scan on orders (full table scan)
-- 2. Any B+-tree index on order_date (if exists)
-- The hash index is useless for this query

Beyond range queries, hash indexes cannot contribute to any operation requiring sorted data.

ORDER BY clause:

SELECT * FROM employees ORDER BY employee_id;

With a B+-tree on employee_id, the optimizer can retrieve rows in sorted order directly—no sorting step needed. With a hash index, the database must:

1. Retrieve all matching rows (in arbitrary order)
2. Perform an explicit sort operation
3. Return sorted results

For large result sets, this sorting step can be expensive (O(n log n)) and may require disk-based sorting if results don't fit in memory.

GROUP BY optimization:

SELECT department_id, COUNT(*) 
FROM employees 
GROUP BY department_id;

If data arrives presorted by department_id, aggregation is efficient: scan once, accumulate counts as groups change. B+-trees enable this. Hash indexes deliver data in random order, forcing the optimizer to:

1. Build a hash table of groups (hash aggregation), or
2. Sort the data first, then aggregate (sort aggregation)

Both require O(n) extra space or O(n log n) extra time.

For composite (multi-column) hash indexes, an additional limitation emerges: partial key lookups are impossible.

The problem:

Consider a hash index on (department_id, employee_id):

CREATE INDEX idx_dept_emp_hash ON employees 
USING HASH (department_id, employee_id);

This index hashes the combination of both columns into a single bucket address:

bucket = hash(department_id || employee_id)

What works:

-- Full composite key provided
SELECT * FROM employees 
WHERE department_id = 10 AND employee_id = 500;
-- Hash is computed: h(10, 500) = bucket 47 ✓

What doesn't work:

-- Only first column provided
SELECT * FROM employees WHERE department_id = 10;
-- Cannot compute hash: need employee_id too!
-- Falls back to table scan ✗

Contrast with B+-tree:

A B+-tree on (department_id, employee_id) stores entries sorted by department_id first, then by employee_id within each department. This organization enables:

-- Full key: Navigate to exact position
WHERE department_id = 10 AND employee_id = 500;  ✓

-- Leftmost prefix: Navigate to department, scan
WHERE department_id = 10;  ✓

-- Range on first column: Navigate and scan
WHERE department_id BETWEEN 10 AND 20;  ✓

-- Range on second column (within first)
WHERE department_id = 10 AND employee_id > 400;  ✓

The B+-tree leftmost prefix rule:

For a B+-tree index on (A, B, C), these queries can use the index:

• WHERE A = ?
• WHERE A = ? AND B = ?
• WHERE A = ? AND B = ? AND C = ?
• WHERE A = ? AND B > ?
• WHERE A BETWEEN ? AND ?

Hash equivalent:

For a hash index on (A, B, C), only this query uses the index:

• WHERE A = ? AND B = ? AND C = ? (all columns, equality only)

Every other combination requires table scan.

Hash indexes cannot support pattern matching queries (LIKE, regular expressions). This limitation follows from the same principle as range query limitation: hashing destroys the character-by-character structure that makes pattern matching work.

Why LIKE queries fail:

-- Hash index on email column
CREATE INDEX idx_email_hash ON users USING HASH (email);

-- This query CANNOT use the hash index
SELECT * FROM users WHERE email LIKE 'john%';

The hash of 'john@example.com' (say, 847) has no relationship to the hash of 'john.doe@example.com' (say, 2931). The shared 'john' prefix provides no advantage.

B+-tree advantage:

B+-trees on strings store entries in lexicographic order:

• 'aaron@...' comes before 'bob@...'
• 'john.doe@...' is near 'john.smith@...'

Prefix queries (LIKE 'john%') can find the first 'john...' entry and scan until the prefix no longer matches—efficient range scan.

Note on suffix and contains patterns:

Neither B+-tree nor hash index helps with suffix or contains patterns on standard indexed columns. For these patterns, specialized indexes are needed:

• Trigram indexes (pg_trgm): Break strings into 3-character chunks for pattern matching
• Full-text indexes: Support word-based searching
• Reverse indexes: Store reversed strings for suffix matching

But for prefix matching—common in autocomplete, search suggestions, and filtering—B+-trees work and hash indexes don't.

Traditional (static) hash indexes are created with a fixed number of buckets. When data grows beyond this capacity, performance degrades—and recovering requires costly reorganization.

The static hashing problem:

Initial state:
- 10,000 buckets
- 50,000 records
- Load factor: 5 entries/bucket ✓

After growth:
- 10,000 buckets (unchanged)
- 500,000 records
- Load factor: 50 entries/bucket ✗

With 50 entries per bucket, overflow chains grow long. What was O(1) becomes O(50)—still constant, but a very different constant. If chains grow to disk pages, each lookup requires multiple I/Os.

B+-tree contrast:

B+-trees grow organically:

• Leaf splits when full → two half-full leaves
• Internal node splits propagate up
• Tree height increases slowly (logarithmically)
• No manual reorganization needed

A B+-tree with 10 million records has height ~4. A B+-tree with 100 million records has height ~5. The performance delta is one additional I/O—graceful degradation, not collapse.

Reorganization (rehashing):

When a static hash index becomes overloaded, the only solution is reorganization:

1. Create a new hash index with more buckets (say, 2x current)
2. For each entry in the old index:
   • Compute new hash
   • Insert into new bucket
3. Drop old index
4. Rename new index

Cost of reorganization:

Beyond query limitations, hash indexes present operational challenges that database administrators must consider.

Database-specific limitations:

The InnoDB adaptive hash perspective:

MySQL's InnoDB doesn't expose hash indexes to users. Instead, it maintains an adaptive hash index (AHI) internally:

• InnoDB observes B+-tree access patterns
• Frequently accessed pages get hash entries automatically
• No user configuration needed
• Combines B+-tree versatility with hash speed for hot data

This approach avoids forcing users to choose between hash and tree—the engine makes the decision dynamically based on actual workload.

Understanding failure modes prevents costly mistakes. Here are scenarios where hash indexes produce disastrous results.

Scenario 1: Wrong workload assumption

Initial assumption: "We only do point queries on user_id"

Created: Hash index on users(user_id)

Reality 6 months later:
- New feature: "Show users who signed up this week"
  SELECT * FROM users WHERE created_at > '2024-01-01';
  -- user_id hash index useless, full scan

- New feature: "List users alphabetically"
  SELECT * FROM users ORDER BY username;
  -- user_id hash index useless, full scan + sort

- Business request: "Users with IDs between 1000-2000"
  SELECT * FROM users WHERE user_id BETWEEN 1000 AND 2000;
  -- Even on indexed column, hash can't help!

Lesson: Requirements evolve. B+-tree's versatility provides insurance against changing needs.

Scenario 2: Pathological hash distribution

Data characteristic: All user emails from same domain
- john@company.com
- jane@company.com  
- bob@company.com
- ...

Hash function behavior:
If hash function uses early characters heavily:
- h('john@company.com') = 47
- h('jane@company.com') = 48  
- h('jill@company.com') = 48
- h('jim@company.com') = 48

Result: Massive clustering in buckets 47-50
All 'j' names in same few buckets → overflow chains

Expected: O(1) lookup
Actual: O(n/few_buckets) lookup ≈ O(n)

Lesson: Hash function quality depends on data distribution. Test with real data, not synthetic.

Scenario 3: Unbounded data growth

Initial sizing:
- Expected: 1 million users, ever
- Bucket count: 10,000
- Load factor: 100 entries/bucket (acceptable)

Actual growth:
- Year 1: 1 million users → works well
- Year 2: 5 million users → performance degrades
- Year 3: 20 million users → overflow chains of 200+ entries
- Year 4: Query latency spikes during peak hours
- Year 5: Desperate reindex during business hours → outage

Post-mortem: "We should have used B+-tree or extendible hashing"

Lesson: Static hash indexes require accurate long-term sizing. Uncertainty favors B+-tree.