diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-16 19:46:48 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-16 19:46:48 +0000 |
| commit | 311bcfc6b3acdd6fd152798c7f287ddf74fa2a98 (patch) | |
| tree | 0ec307299b1dada3701e42f4ca6eda57d708261e /doc/src/sgml/html/hash-implementation.html | |
| parent | Initial commit. (diff) | |
| download | postgresql-15-311bcfc6b3acdd6fd152798c7f287ddf74fa2a98.tar.xz postgresql-15-311bcfc6b3acdd6fd152798c7f287ddf74fa2a98.zip | |
Adding upstream version 15.4.upstream/15.4upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'doc/src/sgml/html/hash-implementation.html')
| -rw-r--r-- | doc/src/sgml/html/hash-implementation.html | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/doc/src/sgml/html/hash-implementation.html b/doc/src/sgml/html/hash-implementation.html new file mode 100644 index 0000000..449299b --- /dev/null +++ b/doc/src/sgml/html/hash-implementation.html @@ -0,0 +1,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.4 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.4 Documentation">Home</a></td><td width="40%" align="right" valign="top"> Chapter 73. Database Physical Storage</td></tr></table></div></body></html>
\ No newline at end of file |