24 Hash

24.1 Overview

A hash index¹ provides the ability to quickly find a tuple ID (TID) by a particular index key. Roughly speaking, it is simply a hash table stored on disk. The only operation supported by a hash index is search by the equality condition.

When a value is inserted into an index,² the hash function of the index key is computed. In PostgreSQL, hash functions return 32-bit or 64-bit integers; several lowest bits of these values are used as the number of the corresponding bucket. The TID and the hash code of the key are added into the chosen bucket. The key itself is not stored in the index because it is more convenient to deal with small fixed-length values.

The hash table of an index is expanded dynamically.³ The minimal number of buckets is two. As the number of indexed tuples grows, one of the buckets gets split into two. This operation uses one more bit of the hash code, so the elements are redistributed only between the two buckets resulting from the split; the composition of other buckets of the hash table remains the same.⁴

The index search operation⁵ calculates the hash function of the index key and the corresponding bucket number. Of all the bucket contents, the search will return only those TIDs that correspond to the hash code of the key. As bucket elements are ordered by the keys’ hash codes, binary search can return matching TIDs quite efficiently.

Since keys are not stored in the hash table, the index access method may return redundant TIDs because of hash collisions. Therefore, the indexing engine has to recheck all the results fetched by the access method. An index-only scan is not supported for the same reason. (p. 328)

24.2 Page Layout

Unlike a regular hash table, the hash index is stored on disk. Therefore, all the data has to be arranged into pages, preferably in such a way that index operations (search, insertion, deletion) require access to as few pages as possible.

A hash index uses four types of pages:

• metapage—page zero that provides the “table of contents” of an index

• bucket pages—the main pages of an index, one per bucket

• overflow pages—additional pages that are used when the main bucket page cannot accommodate all the elements

• bitmap pages—pages containing the bit array used to track overflow pages that have been freed and can be reused

We can peek into index pages using the pageinspect extension. (v. 10)

Let’s begin with an empty table:

=> CREATE EXTENSION pageinspect;
=> CREATE TABLE t(n integer);
=> ANALYZE t;
=> CREATE INDEX ON t USING hash(n);

I have analyzed the table, so the created index will have the minimal size possible; otherwise, the number of buckets would have been selected based on the assumption that the table contains ten pages.⁶ (v. 14)

The index contains four pages: the metapage, two bucket pages, and one bitmap page (created at once for future use):

=> SELECT page, hash_page_type(get_raw_page('t_n_idx', page))
FROM generate_series(0,3) page;
 page | hash_page_type
------+----------------
    0 | metapage
    1 | bucket
    2 | bucket
    3 | bitmap
(4 rows)

The metapage contains all the control information about the index. We are interested only in a few values at the moment:

=> SELECT ntuples, ffactor, maxbucket
FROM hash_metapage_info(get_raw_page('t_n_idx', 0));
 ntuples | ffactor | maxbucket
---------+---------+-----------
       0 |     307 |         1
(1 row)

The estimated number of rows per bucket is shown in the ffactor field. This value is calculated based on the block size and the fillfactor storage parameter value. By absolutely uniform data distribution and no hash collisions you could use a higher fillfactor value, but in real-life databases it increases the risk of page overflows. (default: 75)

The worst scenario for a hash index is a large skew in data distribution, when a key is repeated multiple times. Since the hash function will be returning the same value, all the data will be placed into the same bucket, and increasing the number of buckets will not help.

Now the index is empty, as shown by the ntuples field. Let’s cause a bucket page overflow by inserting multiple rows with the same value of the index key. An overflow page appears in the index: (v. 10)

=> INSERT INTO t(n)
  SELECT 0 FROM generate_series(1,500); -- the same value
=> SELECT page, hash_page_type(get_raw_page('t_n_idx', page))
FROM generate_series(0,4) page;
 page | hash_page_type
------+----------------
    0 | metapage
    1 | bucket
    2 | bucket
    3 | bitmap
    4 | overflow
(5 rows)

The combined statistics on all the pages shows that bucket 0 is empty, while all the values have been placed into bucket 1: some of them are located in the main page, and those that did not fit it can be found in the overflow page.

=> SELECT page, live_items, free_size, hasho_bucket
FROM (VALUES (1), (2), (4)) p(page),
  hash_page_stats(get_raw_page('t_n_idx', page));
 page | live_items | free_size | hasho_bucket
------+------------+-----------+--------------
    1 |          0 |      8148 |            0
    2 |        407 |         8 |            1
    4 |         93 |      6288 |            1
(3 rows)

It is clear that if the elements of the bucket are spread over several pages, performance will suffer. A hash index shows best results if data distribution is uniform.

Now let’s take a look at how a bucket can be split. It happens when the number of rows in the index exceeds the estimated ffactor value for the available buckets. Here we have two buckets, and the ffactor is 307, so it will happen when the 615th row is inserted into the index:

=> SELECT ntuples, ffactor, maxbucket, ovflpoint
FROM hash_metapage_info(get_raw_page('t_n_idx', 0));
 ntuples | ffactor | maxbucket | ovflpoint
---------+---------+-----------+-----------
     500 |     307 |         1 |         1
(1 row)
=> INSERT INTO t(n)
  SELECT n FROM generate_series(1,115) n; -- now values are different
=> SELECT ntuples, ffactor, maxbucket, ovflpoint
FROM hash_metapage_info(get_raw_page('t_n_idx', 0));
 ntuples | ffactor | maxbucket | ovflpoint
---------+---------+-----------+-----------
     615 |     307 |         2 |         2
(1 row)

The maxbucket value has been increased to two: now we have three buckets, numbered from 0 to 2. But even though we have added only one bucket, the number of pages has doubled:

=> SELECT page, hash_page_type(get_raw_page('t_n_idx', page))
FROM generate_series(0,6) page;
 page | hash_page_type
------+----------------
    0 | metapage
    1 | bucket
    2 | bucket
    3 | bitmap
    4 | overflow
    5 | bucket
    6 | unused
(7 rows)

One of the new pages is used by bucket 2, while the other one remains free and will be used by bucket 3 as soon as it appears.

=> SELECT page, live_items, free_size, hasho_bucket
FROM (
    VALUES (1), (2), (4), (5)
  ) p(page),
  hash_page_stats(get_raw_page('t_n_idx', page));
 page | live_items | free_size | hasho_bucket
------+------------+-----------+--------------
    1 |         27 |      7608 |            0
    2 |        407 |         8 |            1
    4 |        158 |      4988 |            1
    5 |         23 |      7688 |            2
(4 rows)

Thus, from the point of view of the operating system, the hash index grows in spurts, although from the logical standpoint the hash table shows gradual growth.

To level out this growth to some extent and avoid allocating too many pages at a time, starting from the tenth increase pages get allocated in four equal batches rather than all at once. (v. 10)

Two more fields of the metapage, which are virtually bit masks, provide the details on bucket addresses:

=> SELECT maxbucket, highmask::bit(4), lowmask::bit(4)
FROM hash_metapage_info(get_raw_page('t_n_idx', 0));
 maxbucket | highmask | lowmask
-----------+----------+---------
         2 | 0011     | 0001
(1 row)

A bucket number is defined by the hash code bits that correspond to the highmask. But if the received bucket number does not exist (exceeds maxbucket), the lowmask bits are taken.⁷ In this particular case, we take two lowest bits, which gives us the values from 0 to 3; but if we got 3, we would take only one lowest bit, that is, use bucket 1 instead of bucket 3.

Each time the size is doubled, new bucket pages are allocated as a single continuous chunk, while overflow and bitmap pages get inserted between these fragments as required. The metapage keeps the number of pages inserted into each of the chunks in the spares array, which gives us an opportunity to calculate the number of its main page based on the bucket number using simple arithmetic.⁸

In this particular case, the first increase was followed by insertion of two pages (a bitmap page and an overflow page), but no additions have happened after the second increase yet:

=> SELECT spares[2], spares[3]
FROM hash_metapage_info(get_raw_page('t_n_idx', 0));
 spares | spares
--------+--------
      2 |      2
(1 row)

The metapage also stores an array of pointers to bitmap pages:

=> SELECT mapp[1]
FROM hash_metapage_info(get_raw_page('t_n_idx', 0));
 mapp
------
    3
(1 row)

spares

meta-bucket 0bucket 0 bucket 1bucket 1 bitmap bucket 1bucket 1 bucket 2bucket 2 page

mmap

The space within index pages is freed when pointers to dead tuples are removed. It happens during page pruning (which is triggered by an attempt to insert an element into a completely filled page)⁹ or when routine vacuuming is performed.

However, a hash index cannot shrink: once allocated, index pages will not be returned to the operating system. The main pages are permanently assigned to their buckets, even if they contain no elements at all; the cleared overflow pages are tracked in the bitmap and can be reused (possibly by another bucket). The only way to reduce the physical size of an index is to rebuild it using the REINDEX or VACUUM FULL commands. (p. 135)

The query plan has no indication of the index type:

=> CREATE INDEX ON flights USING hash(flight_no);
=> EXPLAIN (costs off)
SELECT *
FROM flights
WHERE flight_no = 'PG0001';
                    QUERY PLAN
--------------------------------------------------
 Bitmap Heap Scan on flights
   Recheck Cond: (flight_no = 'PG0001'::bpchar)
   -> Bitmap Index Scan on flights_flight_no_idx
       Index Cond: (flight_no = 'PG0001'::bpchar)
(4 rows)

24.3 Operator Class

Prior to PostgreSQL 10, hash indexes were not logged, that is, they were neither protected against failures nor replicated, and consequently, it was not recommended to use them. But even then they had their own value. The thing is that the hashing algorithm is widely used (in particular, to perform hash joins and grouping), and the system must know which hash function can be used for a certain data type. However, this correspondence is not static: it cannot be defined once and for all since PostgreSQL allows adding new data types on the fly. Therefore, it is maintained by the operator class of the hash index and a particular data type. The hash function itself is represented by the support function of the class: (p. 367) (p. 315)

=> SELECT opfname AS opfamily_name,
  amproc::regproc AS opfamily_procedure
FROM pg_am am
  JOIN pg_opfamily opf ON opfmethod = am.oid
  JOIN pg_amproc amproc ON amprocfamily = opf.oid
WHERE amname = 'hash'
AND amprocnum = 1
ORDER BY opfamily_name, opfamily_procedure;
   opfamily_name    | opfamily_procedure
--------------------+--------------------
 aclitem_ops        | hash_aclitem
 array_ops          | hash_array
 bool_ops           | hashchar
 bpchar_ops         | hashbpchar
 ...
 timetz_ops         | timetz_hash
 uuid_ops           | uuid_hash
 xid8_ops           | hashint8
 xid_ops            | hashint4
(38 rows)

These functions return 32-bit integers. Although they are not documented, they can be used to calculate the hash code for a value of the corresponding type.

For example, the text_ops family uses the hashtext function:

=> SELECT hashtext('one'), hashtext('two');
  hashtext  |  hashtext
------------+------------
 1793019229 | 1590507854
(1 row)

The operator class of the hash index provides only the equal to operator:

=> SELECT opfname AS opfamily_name,
  left(amopopr::regoperator::text, 20) AS opfamily_operator
FROM pg_am am
  JOIN pg_opfamily opf ON opfmethod = am.oid
  JOIN pg_amop amop ON amopfamily = opf.oid
WHERE amname = 'hash'
ORDER BY opfamily_name, opfamily_operator;
   opfamily_name    |   opfamily_operator
--------------------+------------------------
 aclitem_ops        | =(aclitem,aclitem)
 array_ops          | =(anyarray,anyarray)
 bool_ops           | =(boolean,boolean)
 bpchar_ops         | =(character,character)
 ...
 uuid_ops           | =(uuid,uuid)
 xid8_ops           | =(xid8,xid8)
 xid_ops            | =(xid,xid)
(48 rows)

24.4 Properties

Let’s take a look at the index-level properties that the hash access method imparts to the system. (p. 322)

Access Method Properties

=> SELECT a.amname, p.name, pg_indexam_has_property(a.oid, p.name)
FROM pg_am a, unnest(array[
  'can_order', 'can_unique', 'can_multi_col',
  'can_exclude', 'can_include'
]) p(name)
WHERE a.amname = 'hash';
 amname |     name      | pg_indexam_has_property
--------+---------------+-------------------------
 hash   | can_order     | f
 hash   | can_unique    | f
 hash   | can_multi_col | f
 hash   | can_exclude   | t
 hash   | can_include   | f
(5 rows)

It is clear that hash indexes cannot be used for row ordering: the hash function mixes the data more or less randomly.

Unique constraints are not supported either. However, hash indexes can enforce exclusion constraints, and since the only supported function is equal to, this exclusion attains the meaning of uniqueness: (p. 325)

=> ALTER TABLE aircrafts_data
  ADD CONSTRAINT unique_range EXCLUDE USING hash(range WITH =);
=> INSERT INTO aircrafts_data
  VALUES ('744','{"ru": "Boeing 747-400"}',11100);
ERROR:  conflicting key value violates exclusion constraint
"unique_range"
DETAIL:  Key (range)=(11100) conflicts with existing key
(range)=(11100).

Multicolumn indexes and additional INCLUDE columns are not supported either.

Index-Level Properties

=>  SELECT p.name, pg_index_has_property('flights_flight_no_idx', p.name)
FROM unnest(array[
  'clusterable', 'index_scan', 'bitmap_scan', 'backward_scan'
]) p(name);
     name      | pg_index_has_property
---------------+-----------------------
 clusterable   | f
 index_scan    | t
 bitmap_scan   | t
 backward_scan | t
(4 rows)

The hash index supports both a regular index scan and a bitmap scan.

Table clusterization by the hash index is not supported. It is quite logical, as it is hard to imagine why it may be necessary to physically order heap data based on the hash function value.

Column-Level Properties

Column-level properties are virtually defined by the index access method and always take the same values.

=> SELECT p.name,
  pg_index_column_has_property('flights_flight_no_idx', 1, p.name)
FROM unnest(array[
  'asc', 'desc', 'nulls_first', 'nulls_last', 'orderable',
  'distance_orderable', 'returnable', 'search_array', 'search_nulls'
]) p(name);
        name        | pg_index_column_has_property
--------------------+------------------------------
 asc                | f
 desc               | f
 nulls_first        | f
 nulls_last         | f
 orderable          | f
 distance_orderable | f
 returnable         | f
 search_array       | f
 search_nulls       | f
(9 rows)

Since the hash function does not preserve the order of values, all the properties related to ordering are inapplicable to the hash index.

The hash index cannot participate in an index-only scan, as it does not store the index key and requires heap access.

The hash index does not support NULL values, since the equal to operation is inapplicable to them.

Search for elements in an array is not implemented either.