Hash index for equality in PostgreSQL - Deep Dive

Overview - Hash index for equality

What is it?

A hash index is a special kind of database index designed to speed up searches that check if a value equals another. It works by using a hash function to convert data into a fixed-size number, which helps the database quickly find matching rows. Hash indexes are mainly useful for queries that use the equals (=) operator. They are different from other indexes because they focus only on equality, not on sorting or range searches.

Why it matters

Without hash indexes, searching for exact matches in large tables can be slow because the database might have to look through many rows one by one. Hash indexes make these searches much faster, improving the performance of applications that rely on quick lookups, like user authentication or caching. Without them, systems would be slower and less efficient, especially when dealing with big data.

Where it fits

Before learning about hash indexes, you should understand basic database concepts like tables, rows, columns, and what an index is. After mastering hash indexes, you can explore other index types like B-tree and GIN indexes, and learn when to use each for different query patterns.

Mental Model

Core Idea

A hash index uses a hash function to turn values into numbers so the database can quickly find exact matches without scanning the whole table.

Think of it like...

Imagine a library where books are stored randomly, but you have a special card catalog that tells you exactly which shelf and spot a book is on by using a code made from the book's title. This code is like a hash, letting you find the book instantly without searching every shelf.

Table: Data values and their hash codes
┌─────────────┬─────────────┐
│ Value       │ Hash Code   │
├─────────────┼─────────────┤
│ 'apple'     │ 12345       │
│ 'banana'    │ 67890       │
│ 'cherry'    │ 54321       │
└─────────────┴─────────────┘

Flow:
[Query Value] → [Hash Function] → [Hash Code] → [Index Lookup] → [Row Found]

Build-Up - 7 Steps

1

Foundation

What is a database index?

Concept: Introduce the idea of an index as a tool to speed up data searches in a database.

A database index is like a shortcut that helps the database find data faster. Instead of looking through every row in a table, the database uses the index to jump directly to the rows it needs. Think of it like an index in a book that tells you the page number for a topic instead of reading the whole book.

Result

You understand that indexes help speed up data retrieval by avoiding full table scans.

Knowing what an index is helps you appreciate why different types of indexes exist and how they improve database performance.

2

Foundation

Understanding equality searches

Concept: Explain what equality searches are and why they matter.

An equality search is when you ask the database to find rows where a column exactly matches a value, like WHERE name = 'Alice'. These searches are very common, for example, looking up a user by ID or email. They need to be fast because they happen often.

Result

You see that equality searches are simple but important queries that benefit from special indexing.

Recognizing the importance of equality searches sets the stage for understanding why hash indexes exist.

3

Intermediate

How hash functions work in indexing

🤔Before reading on: do you think a hash function keeps the original data or changes it? Commit to your answer.

Concept: Introduce the hash function as a way to convert data into a fixed-size number for quick lookup.

A hash function takes any input value and turns it into a number called a hash code. This number is usually fixed in size and looks random. The database uses this number to find data quickly. However, different inputs can sometimes produce the same hash code, which is called a collision.

Result

You understand that hash functions transform data to numbers that help speed up equality searches.

Understanding hash functions explains how hash indexes can jump directly to data locations instead of scanning rows.

4

Intermediate

Creating and using hash indexes in PostgreSQL

🤔Before reading on: do you think hash indexes support range queries like > or

Concept: Show how to create a hash index in PostgreSQL and explain its usage limitations.

In PostgreSQL, you create a hash index with: CREATE INDEX index_name ON table_name USING HASH (column_name); This index speeds up queries like WHERE column_name = 'value'. However, hash indexes do NOT support range queries (like > or <) or sorting. They only work for exact matches.

Result

You can create a hash index and know when it helps and when it doesn't.

Knowing the limitations of hash indexes prevents misuse and helps choose the right index type.

5

Intermediate

Handling collisions in hash indexes

🤔Before reading on: do you think collisions cause incorrect query results? Commit to your answer.

Concept: Explain what collisions are and how PostgreSQL handles them in hash indexes.

Collisions happen when two different values produce the same hash code. PostgreSQL handles collisions by storing multiple entries in the same bucket and then checking the actual values to find the correct row. This means collisions slow down lookups a bit but do not cause wrong results.

Result

You understand that collisions are normal and safely handled, though they affect performance.

Knowing collision handling helps you understand the tradeoff between speed and accuracy in hash indexes.

6

Advanced

Hash index WAL logging and crash safety

🤔Before reading on: do you think hash indexes were always crash-safe in PostgreSQL? Commit to your answer.

Concept: Discuss the history and improvements in PostgreSQL hash indexes regarding write-ahead logging (WAL) and crash recovery.

Originally, PostgreSQL hash indexes were not WAL-logged, meaning they could be corrupted after a crash. Since PostgreSQL 10, hash indexes support WAL logging, making them crash-safe and reliable for production use. This change made hash indexes more trustworthy but still less commonly used than B-tree indexes.

Result

You know that modern PostgreSQL hash indexes are safe to use in production due to WAL logging.

Understanding the evolution of hash indexes' reliability explains why they were less popular before and how improvements changed that.

7

Expert

When hash indexes outperform B-tree indexes

🤔Before reading on: do you think hash indexes are always faster than B-tree indexes for equality? Commit to your answer.

Concept: Explore scenarios where hash indexes can be faster than B-tree indexes and when they are not.

Hash indexes can be faster than B-tree indexes for pure equality searches on large datasets because they avoid tree traversal and directly map to buckets. However, if queries involve sorting, range scans, or multiple conditions, B-tree indexes are better. Also, hash indexes can degrade if many collisions occur or if the table is small.

Result

You can decide when to use hash indexes for maximum performance benefit.

Knowing the performance tradeoffs helps experts optimize database queries by choosing the right index type for the workload.

Under the Hood

Hash indexes store data in buckets determined by applying a hash function to the indexed column's value. Each bucket holds pointers to table rows with matching hash codes. When a query searches for a value, the database hashes the search key, finds the bucket, and then scans only that bucket's entries to find exact matches. Collisions are handled by chaining multiple entries in the same bucket. PostgreSQL uses write-ahead logging (WAL) to ensure changes to hash indexes are crash-safe.

Why designed this way?

Hash indexes were designed to optimize equality searches by avoiding the overhead of tree traversal in B-tree indexes. Early implementations lacked WAL logging for simplicity and speed but risked corruption. Later, WAL was added to improve reliability. The design balances fast lookups with manageable collision handling, trading off range query support for speed in equality lookups.

┌───────────────┐
│ Query Value   │
└──────┬────────┘
       │ Hash Function
       ▼
┌───────────────┐
│ Hash Code     │
└──────┬────────┘
       │ Index Lookup
       ▼
┌───────────────┐
│ Bucket in     │
│ Hash Index    │
│ (multiple     │
│ entries if    │
│ collisions)   │
└──────┬────────┘
       │ Compare actual values
       ▼
┌───────────────┐
│ Matching Rows │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: do you think hash indexes support range queries like WHERE x > 5? Commit to yes or no.

Common Belief: Hash indexes can speed up any kind of search, including range queries.

Reality: Hash indexes only support equality searches (=). They cannot be used for range queries like >, <, or BETWEEN.

Why it matters: Using hash indexes for range queries will not improve performance and can cause the database to ignore the index, leading to slow queries.

Quick: do you think hash collisions cause incorrect query results? Commit to yes or no.

Common Belief: If two values have the same hash code, the database might return wrong rows.

Reality: PostgreSQL handles collisions by checking actual values after finding the bucket, so query results are always correct despite collisions.

Why it matters: Misunderstanding collisions can cause unnecessary fear of hash indexes and prevent their use where they are beneficial.

Quick: do you think hash indexes were always safe to use in production? Commit to yes or no.

Common Belief: Hash indexes have always been reliable and crash-safe in PostgreSQL.

Reality: Before PostgreSQL 10, hash indexes were not WAL-logged and could be corrupted after a crash. Now they are safe due to WAL support.

Why it matters: Using hash indexes on older PostgreSQL versions risks data corruption, so knowing this prevents serious production issues.

Quick: do you think hash indexes always outperform B-tree indexes for equality? Commit to yes or no.

Common Belief: Hash indexes are always faster than B-tree indexes for equality searches.

Reality: Hash indexes can be faster in some cases but not always. B-tree indexes are more versatile and sometimes faster depending on data size, collisions, and query patterns.

Why it matters: Assuming hash indexes are always better can lead to poor index choices and slower queries.

Expert Zone

1

Hash indexes require manual vacuuming to prevent bucket bloat, unlike B-tree indexes which are more self-maintaining.

2

Hash indexes do not support multi-column indexing directly; combining multiple columns requires workarounds or different index types.

3

The performance of hash indexes can degrade significantly if the hash function produces many collisions, so choosing good hash functions and data types matters.

When NOT to use

Avoid hash indexes when you need range queries, sorting, or multi-column indexes. Use B-tree indexes for general-purpose indexing and GIN or GiST indexes for full-text search or complex data types.

Production Patterns

In production, hash indexes are used for very fast lookups on large tables with frequent equality queries, such as caching layers or session stores. They are less common than B-tree indexes but valuable when exact-match speed is critical and range queries are not needed.

Connections

Hash functions in computer science

Hash indexes build directly on hash functions used in many algorithms and data structures.

Understanding general hash functions helps grasp how hash indexes map data to buckets and handle collisions.

B-tree index

Hash indexes and B-tree indexes are alternative indexing methods optimized for different query types.

Knowing the strengths and weaknesses of both helps choose the right index for specific database queries.

Cache lookup in operating systems

Both hash indexes and CPU caches use hashing to quickly find data without scanning everything.

Recognizing this shared pattern reveals how hashing is a universal technique for fast exact-match retrieval.

Common Pitfalls

#1 Trying to use a hash index for range queries.

Wrong approach:

SELECT * FROM users WHERE user_id > 100;
-- Assuming a hash index on user_id will speed this up

Correct approach:

CREATE INDEX idx_user_id_btree ON users (user_id);
SELECT * FROM users WHERE user_id > 100;

Root cause:

Misunderstanding that hash indexes only support equality and not range queries.

#2 Creating a hash index on a small table expecting big performance gains.

Wrong approach:

CREATE INDEX idx_small_table_hash ON small_table USING HASH (column);

Correct approach:

CREATE INDEX idx_small_table_btree ON small_table (column);

Root cause:

Not realizing that hash indexes have overhead and small tables benefit little from them.

#3 Using hash indexes on PostgreSQL versions before 10 in production.

Wrong approach:

CREATE INDEX idx_hash_old ON big_table USING HASH (column); -- on PostgreSQL 9.x

Correct approach:

Upgrade PostgreSQL to version 10 or later before using hash indexes in production.

Root cause:

Unawareness of the lack of WAL logging and crash safety in older PostgreSQL hash indexes.

Key Takeaways

Hash indexes speed up exact-match searches by using a hash function to map values to buckets.

They only support equality queries and cannot be used for range or sorting operations.

PostgreSQL hash indexes became crash-safe starting from version 10 due to write-ahead logging.

Choosing between hash and B-tree indexes depends on query patterns and data characteristics.

Understanding hash collisions and their handling is key to trusting hash index correctness and performance.