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>67.4. 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="btree-support-funcs.html" title="67.3. B-Tree Support Functions" /><link rel="next" href="gist.html" title="Chapter 68. GiST Indexes" /></head><body id="docContent" class="container-fluid col-10"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">67.4. Implementation</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="btree-support-funcs.html" title="67.3. B-Tree Support Functions">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="btree.html" title="Chapter 67. B-Tree Indexes">Up</a></td><th width="60%" align="center">Chapter 67. B-Tree 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="gist.html" title="Chapter 68. GiST Indexes">Next</a></td></tr></table><hr /></div><div class="sect1" id="BTREE-IMPLEMENTATION"><div class="titlepage"><div><div><h2 class="title" style="clear: both">67.4. Implementation <a href="#BTREE-IMPLEMENTATION" class="id_link">#</a></h2></div></div></div><div class="toc"><dl class="toc"><dt><span class="sect2"><a href="btree-implementation.html#BTREE-STRUCTURE">67.4.1. B-Tree Structure</a></span></dt><dt><span class="sect2"><a href="btree-implementation.html#BTREE-DELETION">67.4.2. Bottom-up Index Deletion</a></span></dt><dt><span class="sect2"><a href="btree-implementation.html#BTREE-DEDUPLICATION">67.4.3. Deduplication</a></span></dt></dl></div><p>3  This section covers B-Tree index implementation details that may be4  of use to advanced users.  See5  <code class="filename">src/backend/access/nbtree/README</code> in the source6  distribution for a much more detailed, internals-focused description7  of the B-Tree implementation.8 </p><div class="sect2" id="BTREE-STRUCTURE"><div class="titlepage"><div><div><h3 class="title">67.4.1. B-Tree Structure <a href="#BTREE-STRUCTURE" class="id_link">#</a></h3></div></div></div><p>9   <span class="productname">PostgreSQL</span> B-Tree indexes are10   multi-level tree structures, where each level of the tree can be11   used as a doubly-linked list of pages.  A single metapage is stored12   in a fixed position at the start of the first segment file of the13   index.  All other pages are either leaf pages or internal pages.14   Leaf pages are the pages on the lowest level of the tree.  All15   other levels consist of internal pages.  Each leaf page contains16   tuples that point to table rows.  Each internal page contains17   tuples that point to the next level down in the tree.  Typically,18   over 99% of all pages are leaf pages.  Both internal pages and leaf19   pages use the standard page format described in <a class="xref" href="storage-page-layout.html" title="73.6. Database Page Layout">Section 73.6</a>.20  </p><p>21   New leaf pages are added to a B-Tree index when an existing leaf22   page cannot fit an incoming tuple.  A <em class="firstterm">page23    split</em> operation makes room for items that originally24   belonged on the overflowing page by moving a portion of the items25   to a new page.  Page splits must also insert a new26   <em class="firstterm">downlink</em> to the new page in the parent page,27   which may cause the parent to split in turn.  Page splits28   <span class="quote">“<span class="quote">cascade upwards</span>”</span> in a recursive fashion.  When the29   root page finally cannot fit a new downlink, a <em class="firstterm">root page30    split</em> operation takes place.  This adds a new level to31   the tree structure by creating a new root page that is one level32   above the original root page.33  </p></div><div class="sect2" id="BTREE-DELETION"><div class="titlepage"><div><div><h3 class="title">67.4.2. Bottom-up Index Deletion <a href="#BTREE-DELETION" class="id_link">#</a></h3></div></div></div><p>34   B-Tree indexes are not directly aware that under MVCC, there might35   be multiple extant versions of the same logical table row; to an36   index, each tuple is an independent object that needs its own index37   entry.  <span class="quote">“<span class="quote">Version churn</span>”</span> tuples may sometimes38   accumulate and adversely affect query latency and throughput.  This39   typically occurs with <code class="command">UPDATE</code>-heavy workloads40   where most individual updates cannot apply the41   <a class="link" href="storage-hot.html" title="73.7. Heap-Only Tuples (HOT)"><acronym class="acronym">HOT</acronym> optimization.</a>42   Changing the value of only43   one column covered by one index during an <code class="command">UPDATE</code>44   <span class="emphasis"><em>always</em></span> necessitates a new set of index tuples45   — one for <span class="emphasis"><em>each and every</em></span> index on the46   table.  Note in particular that this includes indexes that were not47   <span class="quote">“<span class="quote">logically modified</span>”</span> by the <code class="command">UPDATE</code>.48   All indexes will need a successor physical index tuple that points49   to the latest version in the table.  Each new tuple within each50   index will generally need to coexist with the original51   <span class="quote">“<span class="quote">updated</span>”</span> tuple for a short period of time (typically52   until shortly after the <code class="command">UPDATE</code> transaction53   commits).54  </p><p>55   B-Tree indexes incrementally delete version churn index tuples by56   performing <em class="firstterm">bottom-up index deletion</em> passes.57   Each deletion pass is triggered in reaction to an anticipated58   <span class="quote">“<span class="quote">version churn page split</span>”</span>.  This only happens with59   indexes that are not logically modified by60   <code class="command">UPDATE</code> statements, where concentrated build up61   of obsolete versions in particular pages would occur otherwise.  A62   page split will usually be avoided, though it's possible that63   certain implementation-level heuristics will fail to identify and64   delete even one garbage index tuple (in which case a page split or65   deduplication pass resolves the issue of an incoming new tuple not66   fitting on a leaf page).  The worst-case number of versions that67   any index scan must traverse (for any single logical row) is an68   important contributor to overall system responsiveness and69   throughput.  A bottom-up index deletion pass targets suspected70   garbage tuples in a single leaf page based on71   <span class="emphasis"><em>qualitative</em></span> distinctions involving logical72   rows and versions.  This contrasts with the <span class="quote">“<span class="quote">top-down</span>”</span>73   index cleanup performed by autovacuum workers, which is triggered74   when certain <span class="emphasis"><em>quantitative</em></span> table-level75   thresholds are exceeded (see <a class="xref" href="routine-vacuuming.html#AUTOVACUUM" title="25.1.6. The Autovacuum Daemon">Section 25.1.6</a>).76  </p><div class="note"><h3 class="title">Note</h3><p>77    Not all deletion operations that are performed within B-Tree78    indexes are bottom-up deletion operations.  There is a distinct79    category of index tuple deletion: <em class="firstterm">simple index tuple80     deletion</em>.  This is a deferred maintenance operation81    that deletes index tuples that are known to be safe to delete82    (those whose item identifier's <code class="literal">LP_DEAD</code> bit is83    already set).  Like bottom-up index deletion, simple index84    deletion takes place at the point that a page split is anticipated85    as a way of avoiding the split.86   </p><p>87    Simple deletion is opportunistic in the sense that it can only88    take place when recent index scans set the89    <code class="literal">LP_DEAD</code> bits of affected items in passing.90    Prior to <span class="productname">PostgreSQL</span> 14, the only91    category of B-Tree deletion was simple deletion.  The main92    differences between it and bottom-up deletion are that only the93    former is opportunistically driven by the activity of passing94    index scans, while only the latter specifically targets version95    churn from <code class="command">UPDATE</code>s that do not logically modify96    indexed columns.97   </p></div><p>98   Bottom-up index deletion performs the vast majority of all garbage99   index tuple cleanup for particular indexes with certain workloads.100   This is expected with any B-Tree index that is subject to101   significant version churn from <code class="command">UPDATE</code>s that102   rarely or never logically modify the columns that the index covers.103   The average and worst-case number of versions per logical row can104   be kept low purely through targeted incremental deletion passes.105   It's quite possible that the on-disk size of certain indexes will106   never increase by even one single page/block despite107   <span class="emphasis"><em>constant</em></span> version churn from108   <code class="command">UPDATE</code>s.  Even then, an exhaustive <span class="quote">“<span class="quote">clean109    sweep</span>”</span> by a <code class="command">VACUUM</code> operation (typically110   run in an autovacuum worker process) will eventually be required as111   a part of <span class="emphasis"><em>collective</em></span> cleanup of the table and112   each of its indexes.113  </p><p>114   Unlike <code class="command">VACUUM</code>, bottom-up index deletion does not115   provide any strong guarantees about how old the oldest garbage116   index tuple may be.  No index can be permitted to retain117   <span class="quote">“<span class="quote">floating garbage</span>”</span> index tuples that became dead prior118   to a conservative cutoff point shared by the table and all of its119   indexes collectively.  This fundamental table-level invariant makes120   it safe to recycle table <acronym class="acronym">TID</acronym>s.  This is how it121   is possible for distinct logical rows to reuse the same table122   <acronym class="acronym">TID</acronym> over time (though this can never happen with123   two logical rows whose lifetimes span the same124   <code class="command">VACUUM</code> cycle).125  </p></div><div class="sect2" id="BTREE-DEDUPLICATION"><div class="titlepage"><div><div><h3 class="title">67.4.3. Deduplication <a href="#BTREE-DEDUPLICATION" class="id_link">#</a></h3></div></div></div><p>126   A duplicate is a leaf page tuple (a tuple that points to a table127   row) where <span class="emphasis"><em>all</em></span> indexed key columns have values128   that match corresponding column values from at least one other leaf129   page tuple in the same index.  Duplicate tuples are quite common in130   practice.  B-Tree indexes can use a special, space-efficient131   representation for duplicates when an optional technique is132   enabled: <em class="firstterm">deduplication</em>.133  </p><p>134   Deduplication works by periodically merging groups of duplicate135   tuples together, forming a single <em class="firstterm">posting list</em> tuple for each136   group.  The column key value(s) only appear once in this137   representation.  This is followed by a sorted array of138   <acronym class="acronym">TID</acronym>s that point to rows in the table.  This139   significantly reduces the storage size of indexes where each value140   (or each distinct combination of column values) appears several141   times on average.  The latency of queries can be reduced142   significantly.  Overall query throughput may increase143   significantly.  The overhead of routine index vacuuming may also be144   reduced significantly.145  </p><div class="note"><h3 class="title">Note</h3><p>146    B-Tree deduplication is just as effective with147    <span class="quote">“<span class="quote">duplicates</span>”</span> that contain a NULL value, even though148    NULL values are never equal to each other according to the149    <code class="literal">=</code> member of any B-Tree operator class.  As far150    as any part of the implementation that understands the on-disk151    B-Tree structure is concerned, NULL is just another value from the152    domain of indexed values.153   </p></div><p>154   The deduplication process occurs lazily, when a new item is155   inserted that cannot fit on an existing leaf page, though only when156   index tuple deletion could not free sufficient space for the new157   item (typically deletion is briefly considered and then skipped158   over).  Unlike GIN posting list tuples, B-Tree posting list tuples159   do not need to expand every time a new duplicate is inserted; they160   are merely an alternative physical representation of the original161   logical contents of the leaf page.  This design prioritizes162   consistent performance with mixed read-write workloads.  Most163   client applications will at least see a moderate performance164   benefit from using deduplication.  Deduplication is enabled by165   default.166  </p><p>167   <code class="command">CREATE INDEX</code> and <code class="command">REINDEX</code>168   apply deduplication to create posting list tuples, though the169   strategy they use is slightly different.  Each group of duplicate170   ordinary tuples encountered in the sorted input taken from the171   table is merged into a posting list tuple172   <span class="emphasis"><em>before</em></span> being added to the current pending leaf173   page.  Individual posting list tuples are packed with as many174   <acronym class="acronym">TID</acronym>s as possible.  Leaf pages are written out in175   the usual way, without any separate deduplication pass.  This176   strategy is well-suited to <code class="command">CREATE INDEX</code> and177   <code class="command">REINDEX</code> because they are once-off batch178   operations.179  </p><p>180   Write-heavy workloads that don't benefit from deduplication due to181   having few or no duplicate values in indexes will incur a small,182   fixed performance penalty (unless deduplication is explicitly183   disabled).  The <code class="literal">deduplicate_items</code> storage184   parameter can be used to disable deduplication within individual185   indexes.  There is never any performance penalty with read-only186   workloads, since reading posting list tuples is at least as187   efficient as reading the standard tuple representation.  Disabling188   deduplication isn't usually helpful.189  </p><p>190   It is sometimes possible for unique indexes (as well as unique191   constraints) to use deduplication.  This allows leaf pages to192   temporarily <span class="quote">“<span class="quote">absorb</span>”</span> extra version churn duplicates.193   Deduplication in unique indexes augments bottom-up index deletion,194   especially in cases where a long-running transaction holds a195   snapshot that blocks garbage collection.  The goal is to buy time196   for the bottom-up index deletion strategy to become effective197   again.  Delaying page splits until a single long-running198   transaction naturally goes away can allow a bottom-up deletion pass199   to succeed where an earlier deletion pass failed.200  </p><div class="tip"><h3 class="title">Tip</h3><p>201    A special heuristic is applied to determine whether a202    deduplication pass in a unique index should take place.  It can203    often skip straight to splitting a leaf page, avoiding a204    performance penalty from wasting cycles on unhelpful deduplication205    passes.  If you're concerned about the overhead of deduplication,206    consider setting <code class="literal">deduplicate_items = off</code>207    selectively.  Leaving deduplication enabled in unique indexes has208    little downside.209   </p></div><p>210   Deduplication cannot be used in all cases due to211   implementation-level restrictions.  Deduplication safety is212   determined when <code class="command">CREATE INDEX</code> or213   <code class="command">REINDEX</code> is run.214  </p><p>215   Note that deduplication is deemed unsafe and cannot be used in the216   following cases involving semantically significant differences217   among equal datums:218  </p><p>219   </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>220      <code class="type">text</code>, <code class="type">varchar</code>, and <code class="type">char</code>221      cannot use deduplication when a222      <span class="emphasis"><em>nondeterministic</em></span> collation is used.  Case223      and accent differences must be preserved among equal datums.224     </p></li><li class="listitem"><p>225      <code class="type">numeric</code> cannot use deduplication.  Numeric display226      scale must be preserved among equal datums.227     </p></li><li class="listitem"><p>228      <code class="type">jsonb</code> cannot use deduplication, since the229      <code class="type">jsonb</code> B-Tree operator class uses230      <code class="type">numeric</code> internally.231     </p></li><li class="listitem"><p>232      <code class="type">float4</code> and <code class="type">float8</code> cannot use233      deduplication.  These types have distinct representations for234      <code class="literal">-0</code> and <code class="literal">0</code>, which are235      nevertheless considered equal.  This difference must be236      preserved.237     </p></li></ul></div><p>238  </p><p>239   There is one further implementation-level restriction that may be240   lifted in a future version of241   <span class="productname">PostgreSQL</span>:242  </p><p>243   </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>244      Container types (such as composite types, arrays, or range245      types) cannot use deduplication.246     </p></li></ul></div><p>247  </p><p>248   There is one further implementation-level restriction that applies249   regardless of the operator class or collation used:250  </p><p>251   </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>252      <code class="literal">INCLUDE</code> indexes can never use deduplication.253     </p></li></ul></div><p>254  </p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="btree-support-funcs.html" title="67.3. B-Tree Support Functions">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="btree.html" title="Chapter 67. B-Tree Indexes">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="gist.html" title="Chapter 68. GiST Indexes">Next</a></td></tr><tr><td width="40%" align="left" valign="top">67.3. B-Tree Support Functions </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 68. GiST Indexes</td></tr></table></div></body></html>