|
- <?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><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 12.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 class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="gin-extensibility.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="gin.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="gin-tips.html">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">Home</a></td><td width="40%" align="right" valign="top"> 66.5. GIN Tips and Tricks</td></tr></table></div></body></html>
|
