diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-13 13:44:03 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-13 13:44:03 +0000 |
| commit | 293913568e6a7a86fd1479e1cff8e2ecb58d6568 (patch) | |
| tree | fc3b469a3ec5ab71b36ea97cc7aaddb838423a0c /doc/src/sgml/html/gin-implementation.html | |
| parent | Initial commit. (diff) | |
| download | postgresql-16-293913568e6a7a86fd1479e1cff8e2ecb58d6568.tar.xz postgresql-16-293913568e6a7a86fd1479e1cff8e2ecb58d6568.zip | |
Adding upstream version 16.2.upstream/16.2
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
| -rw-r--r-- | doc/src/sgml/html/gin-implementation.html | 64 |
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..b74ad9b --- /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>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.2 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> + 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 70.1. GIN Internals">Figure 70.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 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> + 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). + <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">70.4.2. Partial Match Algorithm <a href="#GIN-PARTIAL-MATCH" class="id_link">#</a></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" 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.2 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 70.5. GIN Tips and Tricks</td></tr></table></div></body></html>
\ No newline at end of file |