begriffs open source - ai-pg/blob - full-docs/html/hash-index.html

   1 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>65.6. Hash Indexes</title><link rel="stylesheet" type="text/css" href="stylesheet.css" /><link rev="made" href="pgsql-docs@lists.postgresql.org" /><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><link rel="prev" href="brin.html" title="65.5. BRIN Indexes" /><link rel="next" href="storage.html" title="Chapter 66. Database Physical Storage" /></head><body id="docContent" class="container-fluid col-10"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">65.6. Hash Indexes</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="brin.html" title="65.5. BRIN Indexes">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="indextypes.html" title="Chapter 65. Built-in Index Access Methods">Up</a></td><th width="60%" align="center">Chapter 65. Built-in Index Access Methods</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 18.0 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="storage.html" title="Chapter 66. Database Physical Storage">Next</a></td></tr></table><hr /></div><div class="sect1" id="HASH-INDEX"><div class="titlepage"><div><div><h2 class="title" style="clear: both">65.6. Hash Indexes <a href="#HASH-INDEX" class="id_link">#</a></h2></div></div></div><div class="toc"><dl class="toc"><dt><span class="sect2"><a href="hash-index.html#HASH-INTRO">65.6.1. Overview</a></span></dt><dt><span class="sect2"><a href="hash-index.html#HASH-IMPLEMENTATION">65.6.2. Implementation</a></span></dt></dl></div><a id="id-1.10.17.7.2" class="indexterm"></a><div class="sect2" id="HASH-INTRO"><div class="titlepage"><div><div><h3 class="title">65.6.1. Overview <a href="#HASH-INTRO" class="id_link">#</a></h3></div></div></div><p>
   3   <span class="productname">PostgreSQL</span>
   4   includes an implementation of persistent on-disk hash indexes,
   5   which are fully crash recoverable. Any data type can be indexed by a
   6   hash index, including data types that do not have a well-defined linear
   7   ordering. Hash indexes store only the hash value of the data being
   8   indexed, thus there are no restrictions on the size of the data column
   9   being indexed.
  10  </p><p>
  11   Hash indexes support only single-column indexes and do not allow
  12   uniqueness checking.
  13  </p><p>
  14   Hash indexes support only the <code class="literal">=</code> operator,
  15   so WHERE clauses that specify range operations will not be able to take
  16   advantage of hash indexes.
  17  </p><p>
  18   Each hash index tuple stores just the 4-byte hash value, not the actual
  19   column value. As a result, hash indexes may be much smaller than B-trees
  20   when indexing longer data items such as UUIDs, URLs, etc. The absence of
  21   the column value also makes all hash index scans lossy. Hash indexes may
  22   take part in bitmap index scans and backward scans.
  23  </p><p>
  24   Hash indexes are best optimized for SELECT and UPDATE-heavy workloads
  25   that use equality scans on larger tables. In a B-tree index, searches must
  26   descend through the tree until the leaf page is found. In tables with
  27   millions of rows, this descent can increase access time to data. The
  28   equivalent of a leaf page in a hash index is referred to as a bucket page. In
  29   contrast, a hash index allows accessing the bucket pages directly,
  30   thereby potentially reducing index access time in larger tables. This
  31   reduction in "logical I/O" becomes even more pronounced on indexes/data
  32   larger than shared_buffers/RAM.
  33  </p><p>
  34   Hash indexes have been designed to cope with uneven distributions of
  35   hash values. Direct access to the bucket pages works well if the hash
  36   values are evenly distributed. When inserts mean that the bucket page
  37   becomes full, additional overflow pages are chained to that specific
  38   bucket page, locally expanding the storage for index tuples that match
  39   that hash value. When scanning a hash bucket during queries, we need to
  40   scan through all of the overflow pages. Thus an unbalanced hash index
  41   might actually be worse than a B-tree in terms of number of block
  42   accesses required, for some data.
  43  </p><p>
  44   As a result of the overflow cases, we can say that hash indexes are
  45   most suitable for unique, nearly unique data or data with a low number
  46   of rows per hash bucket.
  47   One possible way to avoid problems is to exclude highly non-unique
  48   values from the index using a partial index condition, but this may
  49   not be suitable in many cases.
  50  </p><p>
  51   Like B-Trees, hash indexes perform simple index tuple deletion. This
  52   is a deferred maintenance operation that deletes index tuples that are
  53   known to be safe to delete (those whose item identifier's LP_DEAD bit
  54   is already set). If an insert finds no space is available on a page we
  55   try to avoid creating a new overflow page by attempting to remove dead
  56   index tuples. Removal cannot occur if the page is pinned at that time.
  57   Deletion of dead index pointers also occurs during VACUUM.
  58  </p><p>
  59   If it can, VACUUM will also try to squeeze the index tuples onto as
  60   few overflow pages as possible, minimizing the overflow chain. If an
  61   overflow page becomes empty, overflow pages can be recycled for reuse
  62   in other buckets, though we never return them to the operating system.
  63   There is currently no provision to shrink a hash index, other than by
  64   rebuilding it with REINDEX.
  65   There is no provision for reducing the number of buckets, either.
  66  </p><p>
  67   Hash indexes may expand the number of bucket pages as the number of
  68   rows indexed grows. The hash key-to-bucket-number mapping is chosen so that
  69   the index can be incrementally expanded. When a new bucket is to be added to
  70   the index, exactly one existing bucket will need to be "split", with some of
  71   its tuples being transferred to the new bucket according to the updated
  72   key-to-bucket-number mapping.
  73  </p><p>
  74   The expansion occurs in the foreground, which could increase execution
  75   time for user inserts. Thus, hash indexes may not be suitable for tables
  76   with rapidly increasing number of rows.
  77  </p></div><div class="sect2" id="HASH-IMPLEMENTATION"><div class="titlepage"><div><div><h3 class="title">65.6.2. Implementation <a href="#HASH-IMPLEMENTATION" class="id_link">#</a></h3></div></div></div><p>
  78   There are four kinds of pages in a hash index: the meta page (page zero),
  79   which contains statically allocated control information; primary bucket
  80   pages; overflow pages; and bitmap pages, which keep track of overflow
  81   pages that have been freed and are available for re-use. For addressing
  82   purposes, bitmap pages are regarded as a subset of the overflow pages.
  83  </p><p>
  84   Both scanning the index and inserting tuples require locating the bucket
  85   where a given tuple ought to be located. To do this, we need the bucket
  86   count, highmask, and lowmask from the metapage; however, it's undesirable
  87   for performance reasons to have to have to lock and pin the metapage for
  88   every such operation. Instead, we retain a cached copy of the metapage
  89   in each backend's relcache entry. This will produce the correct bucket
  90   mapping as long as the target bucket hasn't been split since the last
  91   cache refresh.
  92  </p><p>
  93   Primary bucket pages and overflow pages are allocated independently since
  94   any given index might need more or fewer overflow pages relative to its
  95   number of buckets. The hash code uses an interesting set of addressing
  96   rules to support a variable number of overflow pages while not having to
  97   move primary bucket pages around after they are created.
  98  </p><p>
  99   Each row in the table indexed is represented by a single index tuple in
 100   the hash index. Hash index tuples are stored in bucket pages, and if
 101   they exist, overflow pages. We speed up searches by keeping the index entries
 102   in any one index page sorted by hash code, thus allowing binary search to be
 103   used within an index page. Note however that there is *no* assumption about
 104   the relative ordering of hash codes across different index pages of a bucket.
 105  </p><p>
 106   The bucket splitting algorithms to expand the hash index are too complex to
 107   be worthy of mention here, though are described in more detail in
 108   <code class="filename">src/backend/access/hash/README</code>.
 109   The split algorithm is crash safe and can be restarted if not completed
 110   successfully.
 111  </p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="brin.html" title="65.5. BRIN Indexes">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="indextypes.html" title="Chapter 65. Built-in Index Access Methods">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="storage.html" title="Chapter 66. Database Physical Storage">Next</a></td></tr><tr><td width="40%" align="left" valign="top">65.5. BRIN Indexes </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 18.0 Documentation">Home</a></td><td width="40%" align="right" valign="top"> Chapter 66. Database Physical Storage</td></tr></table></div></body></html>