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.

Practice

1.

What is the main advantage of using a hash index in PostgreSQL?

easy

A. It speeds up equality searches on a column.

B. It improves performance of range queries.

C. It compresses data to save disk space.

D. It automatically updates foreign keys.

Solution

1. Step 1: Understand hash index purpose

   Hash indexes are designed to speed up searches where you look for exact matches (equality) on a column.

2. Step 2: Compare with other index types

   Unlike B-tree indexes, hash indexes do not support range queries or ordering, so they are not useful for those.

3. Final Answer:

   It speeds up equality searches on a column. -> Option A

4. Quick Check:

   Hash index = equality speedup [OK]

Hint: Hash indexes are for exact matches, not ranges. [OK]

Common Mistakes:

• Thinking hash indexes speed up range queries
• Confusing hash indexes with data compression
• Assuming hash indexes handle foreign keys automatically

2.

Which of the following is the correct syntax to create a hash index on the email column of a table named users?

?

easy

A. CREATE INDEX ON users HASH (email);

B. CREATE HASH INDEX users_email ON users (email);

C. CREATE INDEX users_email ON users USING btree (email);

D. CREATE INDEX users_email_hash ON users USING hash (email);

Solution

1. Step 1: Recall hash index syntax

   The correct syntax uses CREATE INDEX, specifies the index name, the table, and uses USING hash to indicate a hash index.

2. Step 2: Check each option

   CREATE INDEX users_email_hash ON users USING hash (email); matches the correct syntax exactly. The other options have syntax errors or use the wrong index type.

3. Final Answer:

   CREATE INDEX users_email_hash ON users USING hash (email); -> Option D

4. Quick Check:

   CREATE INDEX ... USING hash ... [OK]

Hint: Use 'CREATE INDEX name ON table USING hash (column);' [OK]

Common Mistakes:

• Using CREATE HASH INDEX instead of CREATE INDEX
• Forgetting 'USING hash' clause
• Using btree instead of hash for hash index

3.

Given the table products(id INT, name TEXT) with a hash index on id, what will the query SELECT * FROM products WHERE id = 10; most likely use?

medium

A. A sequential scan ignoring the index

B. A hash index scan for fast equality lookup

C. A bitmap index scan for range search

D. A full table lock before scanning

Solution

1. Step 1: Identify query condition type

   The query uses an equality condition on the id column: id = 10.

2. Step 2: Match index type to query

   Since there is a hash index on id, PostgreSQL will use a hash index scan to quickly find rows where id equals 10.

3. Final Answer:

   A hash index scan for fast equality lookup -> Option B

4. Quick Check:

   Equality query + hash index = hash index scan [OK]

Hint: Equality WHERE uses hash index scan if available. [OK]

Common Mistakes:

• Assuming sequential scan always happens
• Confusing bitmap index with hash index
• Thinking hash index supports range queries

4.

Consider the following SQL commands:
CREATE TABLE employees(id INT, name TEXT);
CREATE INDEX emp_id_hash ON employees USING hash (id);
SELECT * FROM employees WHERE id > 5;
What is the problem with using the hash index in this query?

medium

A. The table must have a primary key before creating a hash index.

B. The index name is invalid for hash indexes.

C. Hash indexes do not support range queries like id > 5.

D. The query syntax is incorrect for using indexes.

Solution

1. Step 1: Understand hash index limitations

   Hash indexes only support equality searches, not range conditions like id > 5.

2. Step 2: Analyze the query condition

   The query uses a range condition, so the hash index cannot be used efficiently here.

3. Final Answer:

   Hash indexes do not support range queries like id > 5. -> Option C

4. Quick Check:

   Range query + hash index = no use [OK]

Hint: Hash indexes only work with '=' conditions. [OK]

Common Mistakes:

• Thinking hash indexes support range queries
• Believing index names must follow special rules
• Assuming primary key is required for hash index

5.

You have a large table orders(order_id INT, customer_id INT, status TEXT). You often query orders by customer_id with equality conditions, but sometimes you query by status with range-like conditions (e.g., status > 'A'). Which indexing strategy is best?

hard

A. Create a hash index on customer_id and a B-tree index on status.

B. Create hash indexes on both customer_id and status.

C. Create a B-tree index on customer_id only.

D. Create no indexes to avoid overhead.

Solution

1. Step 1: Match index types to query patterns

   Hash indexes are good for equality searches, so use one on customer_id. B-tree indexes support range queries, so use one on status.

2. Step 2: Evaluate options

   Create a hash index on customer_id and a B-tree index on status. correctly assigns hash index for equality and B-tree for range. Create hash indexes on both customer_id and status. wrongly uses hash for range. Create a B-tree index on customer_id only. misses index on status. Create no indexes to avoid overhead. ignores performance.

3. Final Answer:

   Create a hash index on customer_id and a B-tree index on status. -> Option A

4. Quick Check:

   Equality = hash, range = B-tree [OK]

Hint: Use hash for '=' and B-tree for ranges together. [OK]

Common Mistakes:

• Using hash index for range queries
• Not indexing frequently queried columns
• Avoiding indexes due to overhead without reason