summaryrefslogtreecommitdiffstats
path: root/doc/src/sgml/html/hash-implementation.html
blob: 83f2b29ea4827d2d599acde1dd8a0ca5d1ce821f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!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>72.2. Implementation</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="hash-intro.html" title="72.1. Overview" /><link rel="next" href="storage.html" title="Chapter 73. 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">72.2. Implementation</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="hash-intro.html" title="72.1. Overview">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="hash-index.html" title="Chapter 72. Hash Indexes">Up</a></td><th width="60%" align="center">Chapter 72. Hash Indexes</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 15.7 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="storage.html" title="Chapter 73. Database Physical Storage">Next</a></td></tr></table><hr /></div><div class="sect1" id="HASH-IMPLEMENTATION"><div class="titlepage"><div><div><h2 class="title" style="clear: both">72.2. Implementation</h2></div></div></div><p>
  There are four kinds of pages in a hash index: the meta page (page zero),
  which contains statically allocated control information; primary bucket
  pages; overflow pages; and bitmap pages, which keep track of overflow
  pages that have been freed and are available for re-use. For addressing
  purposes, bitmap pages are regarded as a subset of the overflow pages.
 </p><p>
  Both scanning the index and inserting tuples require locating the bucket
  where a given tuple ought to be located. To do this, we need the bucket
  count, highmask, and lowmask from the metapage; however, it's undesirable
  for performance reasons to have to have to lock and pin the metapage for
  every such operation. Instead, we retain a cached copy of the metapage
  in each backend's relcache entry. This will produce the correct bucket
  mapping as long as the target bucket hasn't been split since the last
  cache refresh.
 </p><p>
  Primary bucket pages and overflow pages are allocated independently since
  any given index might need more or fewer overflow pages relative to its
  number of buckets. The hash code uses an interesting set of addressing
  rules to support a variable number of overflow pages while not having to
  move primary bucket pages around after they are created.
 </p><p>
  Each row in the table indexed is represented by a single index tuple in
  the hash index. Hash index tuples are stored in bucket pages, and if
  they exist, overflow pages. We speed up searches by keeping the index entries
  in any one index page sorted by hash code, thus allowing binary search to be
  used within an index page. Note however that there is *no* assumption about
  the relative ordering of hash codes across different index pages of a bucket.
 </p><p>
  The bucket splitting algorithms to expand the hash index are too complex to
  be worthy of mention here, though are described in more detail in
  <code class="filename">src/backend/access/hash/README</code>.
  The split algorithm is crash safe and can be restarted if not completed
  successfully.
 </p></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="hash-intro.html" title="72.1. Overview">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="hash-index.html" title="Chapter 72. Hash Indexes">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="storage.html" title="Chapter 73. Database Physical Storage">Next</a></td></tr><tr><td width="40%" align="left" valign="top">72.1. Overview </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 15.7 Documentation">Home</a></td><td width="40%" align="right" valign="top"> Chapter 73. Database Physical Storage</td></tr></table></div></body></html>