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>70.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="gin-extensibility.html" title="70.3. Extensibility" /><link rel="next" href="gin-tips.html" title="70.5. GIN Tips and Tricks" /></head><body id="docContent" class="container-fluid col-10"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">70.4. Implementation</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="gin-extensibility.html" title="70.3. Extensibility">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="gin.html" title="Chapter 70. GIN Indexes">Up</a></td><th width="60%" align="center">Chapter 70. GIN 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="gin-tips.html" title="70.5. GIN Tips and Tricks">Next</a></td></tr></table><hr /></div><div class="sect1" id="GIN-IMPLEMENTATION"><div class="titlepage"><div><div><h2 class="title" style="clear: both">70.4. Implementation <a href="#GIN-IMPLEMENTATION" class="id_link">#</a></h2></div></div></div><div class="toc"><dl class="toc"><dt><span class="sect2"><a href="gin-implementation.html#GIN-FAST-UPDATE">70.4.1. GIN Fast Update Technique</a></span></dt><dt><span class="sect2"><a href="gin-implementation.html#GIN-PARTIAL-MATCH">70.4.2. Partial Match Algorithm</a></span></dt></dl></div><p>3  Internally, a <acronym class="acronym">GIN</acronym> index contains a B-tree index4  constructed over keys, where each key is an element of one or more indexed5  items (a member of an array, for example) and where each tuple in a leaf6  page contains either a pointer to a B-tree of heap pointers (a7  <span class="quote">“<span class="quote">posting tree</span>”</span>), or a simple list of heap pointers (a <span class="quote">“<span class="quote">posting8  list</span>”</span>) when the list is small enough to fit into a single index tuple along9  with the key value.  <a class="xref" href="gin-implementation.html#GIN-INTERNALS-FIGURE" title="Figure 70.1. GIN Internals">Figure 70.1</a> illustrates10  these components of a GIN index.11 </p><p>12  As of <span class="productname">PostgreSQL</span> 9.1, null key values can be13  included in the index.  Also, placeholder nulls are included in the index14  for indexed items that are null or contain no keys according to15  <code class="function">extractValue</code>.  This allows searches that should find empty16  items to do so.17 </p><p>18  Multicolumn <acronym class="acronym">GIN</acronym> indexes are implemented by building19  a single B-tree over composite values (column number, key value).  The20  key values for different columns can be of different types.21 </p><div class="figure" id="GIN-INTERNALS-FIGURE"><p class="title"><strong>Figure 70.1. GIN Internals</strong></p><div class="figure-contents"><div class="mediaobject"><object type="image/svg+xml" data="gin.svg" width="100%"></object></div></div></div><br class="figure-break" /><div class="sect2" id="GIN-FAST-UPDATE"><div class="titlepage"><div><div><h3 class="title">70.4.1. GIN Fast Update Technique <a href="#GIN-FAST-UPDATE" class="id_link">#</a></h3></div></div></div><p>22   Updating a <acronym class="acronym">GIN</acronym> index tends to be slow because of the23   intrinsic nature of inverted indexes: inserting or updating one heap row24   can cause many inserts into the index (one for each key extracted25   from the indexed item).26   <acronym class="acronym">GIN</acronym> is capable of postponing much of this work by inserting27   new tuples into a temporary, unsorted list of pending entries.28   When the table is vacuumed or autoanalyzed, or when29   <code class="function">gin_clean_pending_list</code> function is called, or if the30   pending list becomes larger than31   <a class="xref" href="runtime-config-client.html#GUC-GIN-PENDING-LIST-LIMIT">gin_pending_list_limit</a>, the entries are moved to the32   main <acronym class="acronym">GIN</acronym> data structure using the same bulk insert33   techniques used during initial index creation.  This greatly improves34   <acronym class="acronym">GIN</acronym> index update speed, even counting the additional35   vacuum overhead.  Moreover the overhead work can be done by a background36   process instead of in foreground query processing.37  </p><p>38   The main disadvantage of this approach is that searches must scan the list39   of pending entries in addition to searching the regular index, and so40   a large list of pending entries will slow searches significantly.41   Another disadvantage is that, while most updates are fast, an update42   that causes the pending list to become <span class="quote">“<span class="quote">too large</span>”</span> will incur an43   immediate cleanup cycle and thus be much slower than other updates.44   Proper use of autovacuum can minimize both of these problems.45  </p><p>46   If consistent response time is more important than update speed,47   use of pending entries can be disabled by turning off the48   <code class="literal">fastupdate</code> storage parameter for a49   <acronym class="acronym">GIN</acronym> index.  See <a class="xref" href="sql-createindex.html" title="CREATE INDEX"><span class="refentrytitle">CREATE INDEX</span></a>50   for details.51  </p></div><div class="sect2" id="GIN-PARTIAL-MATCH"><div class="titlepage"><div><div><h3 class="title">70.4.2. Partial Match Algorithm <a href="#GIN-PARTIAL-MATCH" class="id_link">#</a></h3></div></div></div><p>52   GIN can support <span class="quote">“<span class="quote">partial match</span>”</span> queries, in which the query53   does not determine an exact match for one or more keys, but the possible54   matches fall within a reasonably narrow range of key values (within the55   key sorting order determined by the <code class="function">compare</code> support method).56   The <code class="function">extractQuery</code> method, instead of returning a key value57   to be matched exactly, returns a key value that is the lower bound of58   the range to be searched, and sets the <code class="literal">pmatch</code> flag true.59   The key range is then scanned using the <code class="function">comparePartial</code>60   method.  <code class="function">comparePartial</code> must return zero for a matching61   index key, less than zero for a non-match that is still within the range62   to be searched, or greater than zero if the index key is past the range63   that could match.64  </p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="gin-extensibility.html" title="70.3. Extensibility">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="gin.html" title="Chapter 70. GIN Indexes">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="gin-tips.html" title="70.5. GIN Tips and Tricks">Next</a></td></tr><tr><td width="40%" align="left" valign="top">70.3. Extensibility </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"> 70.5. GIN Tips and Tricks</td></tr></table></div></body></html>