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>
|
