codekingpro/portable-devtools

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>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 16.3 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 <a href="#HASH-IMPLEMENTATION" class="id_link">#</a></h2></div></div></div><p>3  There are four kinds of pages in a hash index: the meta page (page zero),4  which contains statically allocated control information; primary bucket5  pages; overflow pages; and bitmap pages, which keep track of overflow6  pages that have been freed and are available for re-use. For addressing7  purposes, bitmap pages are regarded as a subset of the overflow pages.8 </p><p>9  Both scanning the index and inserting tuples require locating the bucket10  where a given tuple ought to be located. To do this, we need the bucket11  count, highmask, and lowmask from the metapage; however, it's undesirable12  for performance reasons to have to have to lock and pin the metapage for13  every such operation. Instead, we retain a cached copy of the metapage14  in each backend's relcache entry. This will produce the correct bucket15  mapping as long as the target bucket hasn't been split since the last16  cache refresh.17 </p><p>18  Primary bucket pages and overflow pages are allocated independently since19  any given index might need more or fewer overflow pages relative to its20  number of buckets. The hash code uses an interesting set of addressing21  rules to support a variable number of overflow pages while not having to22  move primary bucket pages around after they are created.23 </p><p>24  Each row in the table indexed is represented by a single index tuple in25  the hash index. Hash index tuples are stored in bucket pages, and if26  they exist, overflow pages. We speed up searches by keeping the index entries27  in any one index page sorted by hash code, thus allowing binary search to be28  used within an index page. Note however that there is *no* assumption about29  the relative ordering of hash codes across different index pages of a bucket.30 </p><p>31  The bucket splitting algorithms to expand the hash index are too complex to32  be worthy of mention here, though are described in more detail in33  <code class="filename">src/backend/access/hash/README</code>.34  The split algorithm is crash safe and can be restarted if not completed35  successfully.36 </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 16.3 Documentation">Home</a></td><td width="40%" align="right" valign="top"> Chapter 73. Database Physical Storage</td></tr></table></div></body></html>