1 files changed, 64 insertions, 0 deletions
diff --git a/doc/src/sgml/html/gin-implementation.html b/doc/src/sgml/html/gin-implementation.html
new file mode 100644
index 0000000..76d42fa
--- /dev/null
+++ b/doc/src/sgml/html/gin-implementation.html
@@ -0,0 +1,64 @@
+<?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>66.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 V1.79.1" /><link rel="prev" href="gin-extensibility.html" title="66.3. Extensibility" /><link rel="next" href="gin-tips.html" title="66.5. GIN Tips and Tricks" /></head><body id="docContent" class="container-fluid col-10"><div xmlns="http://www.w3.org/TR/xhtml1/transitional" class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">66.4. Implementation</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="gin-extensibility.html" title="66.3. Extensibility">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="gin.html" title="Chapter 66. GIN Indexes">Up</a></td><th width="60%" align="center">Chapter 66. GIN Indexes</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 13.4 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="gin-tips.html" title="66.5. GIN Tips and Tricks">Next</a></td></tr></table><hr></hr></div><div class="sect1" id="GIN-IMPLEMENTATION"><div class="titlepage"><div><div><h2 class="title" style="clear: both">66.4. Implementation</h2></div></div></div><div class="toc"><dl class="toc"><dt><span class="sect2"><a href="gin-implementation.html#GIN-FAST-UPDATE">66.4.1. GIN Fast Update Technique</a></span></dt><dt><span class="sect2"><a href="gin-implementation.html#GIN-PARTIAL-MATCH">66.4.2. Partial Match Algorithm</a></span></dt></dl></div><p>
+  Internally, a <acronym class="acronym">GIN</acronym> index contains a B-tree index
+  constructed over keys, where each key is an element of one or more indexed
+  items (a member of an array, for example) and where each tuple in a leaf
+  page contains either a pointer to a B-tree of heap pointers (a
+  <span class="quote">“<span class="quote">posting tree</span>”</span>), or a simple list of heap pointers (a <span class="quote">“<span class="quote">posting
+  list</span>”</span>) when the list is small enough to fit into a single index tuple along
+  with the key value.  <a class="xref" href="gin-implementation.html#GIN-INTERNALS-FIGURE" title="Figure 66.1. GIN Internals">Figure 66.1</a> illustrates
+  these components of a GIN index.
+ </p><p>
+  As of <span class="productname">PostgreSQL</span> 9.1, null key values can be
+  included in the index.  Also, placeholder nulls are included in the index
+  for indexed items that are null or contain no keys according to
+  <code class="function">extractValue</code>.  This allows searches that should find empty
+  items to do so.
+ </p><p>
+  Multicolumn <acronym class="acronym">GIN</acronym> indexes are implemented by building
+  a single B-tree over composite values (column number, key value).  The
+  key values for different columns can be of different types.
+ </p><div class="figure" id="GIN-INTERNALS-FIGURE"><p class="title"><strong>Figure 66.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">66.4.1. GIN Fast Update Technique</h3></div></div></div><p>
+   Updating a <acronym class="acronym">GIN</acronym> index tends to be slow because of the
+   intrinsic nature of inverted indexes: inserting or updating one heap row
+   can cause many inserts into the index (one for each key extracted
+   from the indexed item). As of <span class="productname">PostgreSQL</span> 8.4,
+   <acronym class="acronym">GIN</acronym> is capable of postponing much of this work by inserting
+   new tuples into a temporary, unsorted list of pending entries.
+   When the table is vacuumed or autoanalyzed, or when
+   <code class="function">gin_clean_pending_list</code> function is called, or if the
+   pending list becomes larger than
+   <a class="xref" href="runtime-config-client.html#GUC-GIN-PENDING-LIST-LIMIT">gin_pending_list_limit</a>, the entries are moved to the
+   main <acronym class="acronym">GIN</acronym> data structure using the same bulk insert
+   techniques used during initial index creation.  This greatly improves
+   <acronym class="acronym">GIN</acronym> index update speed, even counting the additional
+   vacuum overhead.  Moreover the overhead work can be done by a background
+   process instead of in foreground query processing.
+  </p><p>
+   The main disadvantage of this approach is that searches must scan the list
+   of pending entries in addition to searching the regular index, and so
+   a large list of pending entries will slow searches significantly.
+   Another disadvantage is that, while most updates are fast, an update
+   that causes the pending list to become <span class="quote">“<span class="quote">too large</span>”</span> will incur an
+   immediate cleanup cycle and thus be much slower than other updates.
+   Proper use of autovacuum can minimize both of these problems.
+  </p><p>
+   If consistent response time is more important than update speed,
+   use of pending entries can be disabled by turning off the
+   <code class="literal">fastupdate</code> storage parameter for a
+   <acronym class="acronym">GIN</acronym> index.  See <a class="xref" href="sql-createindex.html" title="CREATE INDEX"><span class="refentrytitle">CREATE INDEX</span></a>
+   for details.
+  </p></div><div class="sect2" id="GIN-PARTIAL-MATCH"><div class="titlepage"><div><div><h3 class="title">66.4.2. Partial Match Algorithm</h3></div></div></div><p>
+   GIN can support <span class="quote">“<span class="quote">partial match</span>”</span> queries, in which the query
+   does not determine an exact match for one or more keys, but the possible
+   matches fall within a reasonably narrow range of key values (within the
+   key sorting order determined by the <code class="function">compare</code> support method).
+   The <code class="function">extractQuery</code> method, instead of returning a key value
+   to be matched exactly, returns a key value that is the lower bound of
+   the range to be searched, and sets the <code class="literal">pmatch</code> flag true.
+   The key range is then scanned using the <code class="function">comparePartial</code>
+   method.  <code class="function">comparePartial</code> must return zero for a matching
+   index key, less than zero for a non-match that is still within the range
+   to be searched, or greater than zero if the index key is past the range
+   that could match.
+  </p></div></div><div xmlns="http://www.w3.org/TR/xhtml1/transitional" class="navfooter"><hr></hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="gin-extensibility.html" title="66.3. Extensibility">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="gin.html" title="Chapter 66. GIN Indexes">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="gin-tips.html" title="66.5. GIN Tips and Tricks">Next</a></td></tr><tr><td width="40%" align="left" valign="top">66.3. Extensibility </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 13.4 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 66.5. GIN Tips and Tricks</td></tr></table></div></body></html>
+\ No newline at end of file