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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
$PostgreSQL: pgsql/src/backend/access/gin/README,v 1.6 2008/07/08 03:25:42 neilc Exp $
Gin for PostgreSQL
==================
Gin was sponsored by jfg://networks (http://www.jfg-networks.com/)
Gin stands for Generalized Inverted Index and should be considered as a genie,
not a drink.
Generalized means that the index does not know which operation it accelerates.
It instead works with custom strategies, defined for specific data types (read
"Index Method Strategies" in the PostgreSQL documentation). In that sense, Gin
is similar to GiST and differs from btree indices, which have predefined,
comparison-based operations.
An inverted index is an index structure storing a set of (key, posting list)
pairs, where 'posting list' is a set of documents in which the key occurs.
(A text document would usually contain many keys.) The primary goal of
Gin indices is support for highly scalable, full-text search in PostgreSQL.
Gin consists of a B-tree index constructed over entries (ET, entries tree),
where each entry is an element of the indexed value (element of array, lexeme
for tsvector) and where each tuple in a leaf page is either a pointer to a
B-tree over item pointers (PT, posting tree), or a list of item pointers
(PL, posting list) if the tuple is small enough.
Note: There is no delete operation for ET. The reason for this is that in
our experience, the set of distinct words in a large corpus changes very
rarely. This greatly simplifies the code and concurrency algorithms.
Gin comes with built-in support for one-dimensional arrays (eg. integer[],
text[]), but no support for NULL elements. The following operations are
available:
* contains: value_array @> query_array
* overlaps: value_array && query_array
* is contained by: value_array <@ query_array
Synopsis
--------
=# create index txt_idx on aa using gin(a);
Features
--------
* Concurrency
* Write-Ahead Logging (WAL). (Recoverability from crashes.)
* User-defined opclasses. (The scheme is similar to GiST.)
* Optimized index creation (Makes use of maintenance_work_mem to accumulate
postings in memory.)
* Text search support via an opclass
* Soft upper limit on the returned results set using a GUC variable:
gin_fuzzy_search_limit
Gin Fuzzy Limit
---------------
There are often situations when a full-text search returns a very large set of
results. Since reading tuples from the disk and sorting them could take a
lot of time, this is unacceptable for production. (Note that the search
itself is very fast.)
Such queries usually contain very frequent lexemes, so the results are not
very helpful. To facilitate execution of such queries Gin has a configurable
soft upper limit on the size of the returned set, determined by the
'gin_fuzzy_search_limit' GUC variable. This is set to 0 by default (no
limit).
If a non-zero search limit is set, then the returned set is a subset of the
whole result set, chosen at random.
"Soft" means that the actual number of returned results could slightly differ
from the specified limit, depending on the query and the quality of the
system's random number generator.
From experience, a value of 'gin_fuzzy_search_limit' in the thousands
(eg. 5000-20000) works well. This means that 'gin_fuzzy_search_limit' will
have no effect for queries returning a result set with less tuples than this
number.
Concurrency
-----------
The entry tree and each posting tree is a B-tree, with right-links connecting
sibling pages at the same level. This is the same structure that is used in
the regular B-tree indexam (invented by Lehman & Yao), but we don't support
scanning a GIN trees backwards, so we don't need left-links.
To avoid deadlocks, B-tree pages must always be locked in the same order:
left to right, and bottom to top. When searching, the tree is traversed from
top to bottom, so the lock on the parent page must be released before
descending to the next level. Concurrent page splits move the keyspace to
right, so after following a downlink, the page actually containing the key
we're looking for might be somewhere to the right of the page we landed on.
In that case, we follow the right-links until we find the page we're looking
for.
To delete a page, the page's left sibling, the target page, and its parent,
are locked in that order, and the page is marked as deleted. However, a
concurrent search might already have read a pointer to the page, and might be
just about to follow it. A page can be reached via the right-link of its left
sibling, or via its downlink in the parent.
To prevent a backend from reaching a deleted page via a right-link, when
following a right-link the lock on the previous page is not released until
the lock on next page has been acquired.
The downlink is more tricky. A search descending the tree must release the
lock on the parent page before locking the child, or it could deadlock with
a concurrent split of the child page; a page split locks the parent, while
already holding a lock on the child page. However, posting trees are only
fully searched from left to right, starting from the leftmost leaf. (The
tree-structure is only needed by insertions, to quickly find the correct
insert location). So as long as we don't delete the leftmost page on each
level, a search can never follow a downlink to page that's about to be
deleted.
The previous paragraph's reasoning only applies to searches, and only to
posting trees. To protect from inserters following a downlink to a deleted
page, vacuum simply locks out all concurrent insertions to the posting tree,
by holding a super-exclusive lock on the posting tree root. Inserters hold a
pin on the root page, but searches do not, so while new searches cannot begin
while root page is locked, any already-in-progress scans can continue
concurrently with vacuum. In the entry tree, we never delete pages.
(This is quite different from the mechanism the btree indexam uses to make
page-deletions safe; it stamps the deleted pages with an XID and keeps the
deleted pages around with the right-link intact until all concurrent scans
have finished.)
Limitations
-----------
* No support for multicolumn indices
* Gin doesn't uses scan->kill_prior_tuple & scan->ignore_killed_tuples
* Gin searches entries only by equality matching. This may be improved in
future.
* Gin doesn't support full scans of indices.
* Gin doesn't index NULL values.
Open Items
----------
We appreciate any comments, help and suggestions.
* Teach optimizer/executor that GIN is intrinsically clustered. i.e., it
always returns ItemPointer in ascending order.
* Tweak gincostestimate.
* GIN stores several ItemPointer to heap tuple, so VACUUM FULL produces
this warning message:
WARNING: index "idx" contains 88395 row versions, but table contains
51812 row versions
HINT: Rebuild the index with REINDEX.
**** Workaround added
TODO
----
Nearest future:
* Opclasses for all types (no programming, just many catalog changes).
Distant future:
* Replace B-tree of entries to something like GiST
* Add multicolumn support
* Optimize insert operations (background index insertion)
Authors
-------
All work was done by Teodor Sigaev (teodor@sigaev.ru) and Oleg Bartunov
(oleg@sai.msu.su).
|
