1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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>
|
