| 1 |
<!-- doc/src/sgml/hash.sgml --> |
| 2 |
|
| 3 |
<sect1 id="hash-index"> |
| 4 |
<title>Hash Indexes</title> |
| 5 |
|
| 6 |
<indexterm> |
| 7 |
<primary>index</primary> |
| 8 |
<secondary>Hash</secondary> |
| 9 |
</indexterm> |
| 10 |
|
| 11 |
<sect2 id="hash-intro"> |
| 12 |
<title>Overview</title> |
| 13 |
|
| 14 |
<para> |
| 15 |
<productname>PostgreSQL</productname> |
| 16 |
includes an implementation of persistent on-disk hash indexes, |
| 17 |
which are fully crash recoverable. Any data type can be indexed by a |
| 18 |
hash index, including data types that do not have a well-defined linear |
| 19 |
ordering. Hash indexes store only the hash value of the data being |
| 20 |
indexed, thus there are no restrictions on the size of the data column |
| 21 |
being indexed. |
| 22 |
</para> |
| 23 |
|
| 24 |
<para> |
| 25 |
Hash indexes support only single-column indexes and do not allow |
| 26 |
uniqueness checking. |
| 27 |
</para> |
| 28 |
|
| 29 |
<para> |
| 30 |
Hash indexes support only the <literal>=</literal> operator, |
| 31 |
so WHERE clauses that specify range operations will not be able to take |
| 32 |
advantage of hash indexes. |
| 33 |
</para> |
| 34 |
|
| 35 |
<para> |
| 36 |
Each hash index tuple stores just the 4-byte hash value, not the actual |
| 37 |
column value. As a result, hash indexes may be much smaller than B-trees |
| 38 |
when indexing longer data items such as UUIDs, URLs, etc. The absence of |
| 39 |
the column value also makes all hash index scans lossy. Hash indexes may |
| 40 |
take part in bitmap index scans and backward scans. |
| 41 |
</para> |
| 42 |
|
| 43 |
<para> |
| 44 |
Hash indexes are best optimized for SELECT and UPDATE-heavy workloads |
| 45 |
that use equality scans on larger tables. In a B-tree index, searches must |
| 46 |
descend through the tree until the leaf page is found. In tables with |
| 47 |
millions of rows, this descent can increase access time to data. The |
| 48 |
equivalent of a leaf page in a hash index is referred to as a bucket page. In |
| 49 |
contrast, a hash index allows accessing the bucket pages directly, |
| 50 |
thereby potentially reducing index access time in larger tables. This |
| 51 |
reduction in "logical I/O" becomes even more pronounced on indexes/data |
| 52 |
larger than shared_buffers/RAM. |
| 53 |
</para> |
| 54 |
|
| 55 |
<para> |
| 56 |
Hash indexes have been designed to cope with uneven distributions of |
| 57 |
hash values. Direct access to the bucket pages works well if the hash |
| 58 |
values are evenly distributed. When inserts mean that the bucket page |
| 59 |
becomes full, additional overflow pages are chained to that specific |
| 60 |
bucket page, locally expanding the storage for index tuples that match |
| 61 |
that hash value. When scanning a hash bucket during queries, we need to |
| 62 |
scan through all of the overflow pages. Thus an unbalanced hash index |
| 63 |
might actually be worse than a B-tree in terms of number of block |
| 64 |
accesses required, for some data. |
| 65 |
</para> |
| 66 |
|
| 67 |
<para> |
| 68 |
As a result of the overflow cases, we can say that hash indexes are |
| 69 |
most suitable for unique, nearly unique data or data with a low number |
| 70 |
of rows per hash bucket. |
| 71 |
One possible way to avoid problems is to exclude highly non-unique |
| 72 |
values from the index using a partial index condition, but this may |
| 73 |
not be suitable in many cases. |
| 74 |
</para> |
| 75 |
|
| 76 |
<para> |
| 77 |
Like B-Trees, hash indexes perform simple index tuple deletion. This |
| 78 |
is a deferred maintenance operation that deletes index tuples that are |
| 79 |
known to be safe to delete (those whose item identifier's LP_DEAD bit |
| 80 |
is already set). If an insert finds no space is available on a page we |
| 81 |
try to avoid creating a new overflow page by attempting to remove dead |
| 82 |
index tuples. Removal cannot occur if the page is pinned at that time. |
| 83 |
Deletion of dead index pointers also occurs during VACUUM. |
| 84 |
</para> |
| 85 |
|
| 86 |
<para> |
| 87 |
If it can, VACUUM will also try to squeeze the index tuples onto as |
| 88 |
few overflow pages as possible, minimizing the overflow chain. If an |
| 89 |
overflow page becomes empty, overflow pages can be recycled for reuse |
| 90 |
in other buckets, though we never return them to the operating system. |
| 91 |
There is currently no provision to shrink a hash index, other than by |
| 92 |
rebuilding it with REINDEX. |
| 93 |
There is no provision for reducing the number of buckets, either. |
| 94 |
</para> |
| 95 |
|
| 96 |
<para> |
| 97 |
Hash indexes may expand the number of bucket pages as the number of |
| 98 |
rows indexed grows. The hash key-to-bucket-number mapping is chosen so that |
| 99 |
the index can be incrementally expanded. When a new bucket is to be added to |
| 100 |
the index, exactly one existing bucket will need to be "split", with some of |
| 101 |
its tuples being transferred to the new bucket according to the updated |
| 102 |
key-to-bucket-number mapping. |
| 103 |
</para> |
| 104 |
|
| 105 |
<para> |
| 106 |
The expansion occurs in the foreground, which could increase execution |
| 107 |
time for user inserts. Thus, hash indexes may not be suitable for tables |
| 108 |
with rapidly increasing number of rows. |
| 109 |
</para> |
| 110 |
|
| 111 |
</sect2> |
| 112 |
|
| 113 |
<sect2 id="hash-implementation"> |
| 114 |
<title>Implementation</title> |
| 115 |
|
| 116 |
<para> |
| 117 |
There are four kinds of pages in a hash index: the meta page (page zero), |
| 118 |
which contains statically allocated control information; primary bucket |
| 119 |
pages; overflow pages; and bitmap pages, which keep track of overflow |
| 120 |
pages that have been freed and are available for re-use. For addressing |
| 121 |
purposes, bitmap pages are regarded as a subset of the overflow pages. |
| 122 |
</para> |
| 123 |
|
| 124 |
<para> |
| 125 |
Both scanning the index and inserting tuples require locating the bucket |
| 126 |
where a given tuple ought to be located. To do this, we need the bucket |
| 127 |
count, highmask, and lowmask from the metapage; however, it's undesirable |
| 128 |
for performance reasons to have to lock and pin the metapage for every such |
| 129 |
operation. Instead, we retain a cached copy of the metapage in each |
| 130 |
backend's relcache entry. This will produce the correct bucket mapping as |
| 131 |
long as the target bucket hasn't been split since the last cache refresh. |
| 132 |
</para> |
| 133 |
|
| 134 |
<para> |
| 135 |
Primary bucket pages and overflow pages are allocated independently since |
| 136 |
any given index might need more or fewer overflow pages relative to its |
| 137 |
number of buckets. The hash code uses an interesting set of addressing |
| 138 |
rules to support a variable number of overflow pages while not having to |
| 139 |
move primary bucket pages around after they are created. |
| 140 |
</para> |
| 141 |
|
| 142 |
<para> |
| 143 |
Each row in the table indexed is represented by a single index tuple in |
| 144 |
the hash index. Hash index tuples are stored in bucket pages, and if |
| 145 |
they exist, overflow pages. We speed up searches by keeping the index entries |
| 146 |
in any one index page sorted by hash code, thus allowing binary search to be |
| 147 |
used within an index page. Note however that there is *no* assumption about |
| 148 |
the relative ordering of hash codes across different index pages of a bucket. |
| 149 |
</para> |
| 150 |
|
| 151 |
<para> |
| 152 |
The bucket splitting algorithms to expand the hash index are too complex to |
| 153 |
be worthy of mention here, though are described in more detail in |
| 154 |
<filename>src/backend/access/hash/README</filename>. |
| 155 |
The split algorithm is crash safe and can be restarted if not completed |
| 156 |
successfully. |
| 157 |
</para> |
| 158 |
|
| 159 |
</sect2> |
| 160 |
|
| 161 |
</sect1> |