| 1 |
src/backend/access/gin/README |
| 2 |
|
| 3 |
Gin for PostgreSQL |
| 4 |
================== |
| 5 |
|
| 6 |
Gin was sponsored by jfg://networks (http://www.jfg-networks.com/) |
| 7 |
|
| 8 |
Gin stands for Generalized Inverted Index and should be considered as a genie, |
| 9 |
not a drink. |
| 10 |
|
| 11 |
Generalized means that the index does not know which operation it accelerates. |
| 12 |
It instead works with custom strategies, defined for specific data types (read |
| 13 |
"Index Method Strategies" in the PostgreSQL documentation). In that sense, Gin |
| 14 |
is similar to GiST and differs from btree indices, which have predefined, |
| 15 |
comparison-based operations. |
| 16 |
|
| 17 |
An inverted index is an index structure storing a set of (key, posting list) |
| 18 |
pairs, where 'posting list' is a set of heap rows in which the key occurs. |
| 19 |
(A text document would usually contain many keys.) The primary goal of |
| 20 |
Gin indices is support for highly scalable, full-text search in PostgreSQL. |
| 21 |
|
| 22 |
A Gin index consists of a B-tree index constructed over key values, |
| 23 |
where each key is an element of some indexed items (element of array, lexeme |
| 24 |
for tsvector) and where each tuple in a leaf page contains either a pointer to |
| 25 |
a B-tree over item pointers (posting tree), or a simple list of item pointers |
| 26 |
(posting list) if the list is small enough. |
| 27 |
|
| 28 |
Note: There is no delete operation in the key (entry) tree. The reason for |
| 29 |
this is that in our experience, the set of distinct words in a large corpus |
| 30 |
changes very slowly. This greatly simplifies the code and concurrency |
| 31 |
algorithms. |
| 32 |
|
| 33 |
Core PostgreSQL includes built-in Gin support for one-dimensional arrays |
| 34 |
(eg. integer[], text[]). The following operations are available: |
| 35 |
|
| 36 |
* contains: value_array @> query_array |
| 37 |
* overlaps: value_array && query_array |
| 38 |
* is contained by: value_array <@ query_array |
| 39 |
|
| 40 |
Synopsis |
| 41 |
-------- |
| 42 |
|
| 43 |
=# create index txt_idx on aa using gin(a); |
| 44 |
|
| 45 |
Features |
| 46 |
-------- |
| 47 |
|
| 48 |
* Concurrency |
| 49 |
* Write-Ahead Logging (WAL). (Recoverability from crashes.) |
| 50 |
* User-defined opclasses. (The scheme is similar to GiST.) |
| 51 |
* Optimized index creation (Makes use of maintenance_work_mem to accumulate |
| 52 |
postings in memory.) |
| 53 |
* Text search support via an opclass |
| 54 |
* Soft upper limit on the returned results set using a GUC variable: |
| 55 |
gin_fuzzy_search_limit |
| 56 |
|
| 57 |
Gin Fuzzy Limit |
| 58 |
--------------- |
| 59 |
|
| 60 |
There are often situations when a full-text search returns a very large set of |
| 61 |
results. Since reading tuples from the disk and sorting them could take a |
| 62 |
lot of time, this is unacceptable for production. (Note that the search |
| 63 |
itself is very fast.) |
| 64 |
|
| 65 |
Such queries usually contain very frequent lexemes, so the results are not |
| 66 |
very helpful. To facilitate execution of such queries Gin has a configurable |
| 67 |
soft upper limit on the size of the returned set, determined by the |
| 68 |
'gin_fuzzy_search_limit' GUC variable. This is set to 0 by default (no |
| 69 |
limit). |
| 70 |
|
| 71 |
If a non-zero search limit is set, then the returned set is a subset of the |
| 72 |
whole result set, chosen at random. |
| 73 |
|
| 74 |
"Soft" means that the actual number of returned results could differ |
| 75 |
from the specified limit, depending on the query and the quality of the |
| 76 |
system's random number generator. |
| 77 |
|
| 78 |
From experience, a value of 'gin_fuzzy_search_limit' in the thousands |
| 79 |
(eg. 5000-20000) works well. This means that 'gin_fuzzy_search_limit' will |
| 80 |
have no effect for queries returning a result set with less tuples than this |
| 81 |
number. |
| 82 |
|
| 83 |
Index structure |
| 84 |
--------------- |
| 85 |
|
| 86 |
The "items" that a GIN index indexes are composite values that contain |
| 87 |
zero or more "keys". For example, an item might be an integer array, and |
| 88 |
then the keys would be the individual integer values. The index actually |
| 89 |
stores and searches for the key values, not the items per se. In the |
| 90 |
pg_opclass entry for a GIN opclass, the opcintype is the data type of the |
| 91 |
items, and the opckeytype is the data type of the keys. GIN is optimized |
| 92 |
for cases where items contain many keys and the same key values appear |
| 93 |
in many different items. |
| 94 |
|
| 95 |
A GIN index contains a metapage, a btree of key entries, and possibly |
| 96 |
"posting tree" pages, which hold the overflow when a key entry acquires |
| 97 |
too many heap tuple pointers to fit in a btree page. Additionally, if the |
| 98 |
fast-update feature is enabled, there can be "list pages" holding "pending" |
| 99 |
key entries that haven't yet been merged into the main btree. The list |
| 100 |
pages have to be scanned linearly when doing a search, so the pending |
| 101 |
entries should be merged into the main btree before there get to be too |
| 102 |
many of them. The advantage of the pending list is that bulk insertion of |
| 103 |
a few thousand entries can be much faster than retail insertion. (The win |
| 104 |
comes mainly from not having to do multiple searches/insertions when the |
| 105 |
same key appears in multiple new heap tuples.) |
| 106 |
|
| 107 |
Key entries are nominally of the same IndexTuple format as used in other |
| 108 |
index types, but since a leaf key entry typically refers to multiple heap |
| 109 |
tuples, there are significant differences. (See GinFormTuple, which works |
| 110 |
by building a "normal" index tuple and then modifying it.) The points to |
| 111 |
know are: |
| 112 |
|
| 113 |
* In a single-column index, a key tuple just contains the key datum, but |
| 114 |
in a multi-column index, a key tuple contains the pair (column number, |
| 115 |
key datum) where the column number is stored as an int2. This is needed |
| 116 |
to support different key data types in different columns. This much of |
| 117 |
the tuple is built by index_form_tuple according to the usual rules. |
| 118 |
The column number (if present) can never be null, but the key datum can |
| 119 |
be, in which case a null bitmap is present as usual. (As usual for index |
| 120 |
tuples, the size of the null bitmap is fixed at INDEX_MAX_KEYS.) |
| 121 |
|
| 122 |
* If the key datum is null (ie, IndexTupleHasNulls() is true), then |
| 123 |
just after the nominal index data (ie, at offset IndexInfoFindDataOffset |
| 124 |
or IndexInfoFindDataOffset + sizeof(int2)) there is a byte indicating |
| 125 |
the "category" of the null entry. These are the possible categories: |
| 126 |
1 = ordinary null key value extracted from an indexable item |
| 127 |
2 = placeholder for zero-key indexable item |
| 128 |
3 = placeholder for null indexable item |
| 129 |
Placeholder null entries are inserted into the index because otherwise |
| 130 |
there would be no index entry at all for an empty or null indexable item, |
| 131 |
which would mean that full index scans couldn't be done and various corner |
| 132 |
cases would give wrong answers. The different categories of null entries |
| 133 |
are treated as distinct keys by the btree, but heap itempointers for the |
| 134 |
same category of null entry are merged into one index entry just as happens |
| 135 |
with ordinary key entries. |
| 136 |
|
| 137 |
* In a key entry at the btree leaf level, at the next SHORTALIGN boundary, |
| 138 |
there is a list of item pointers, in compressed format (see Posting List |
| 139 |
Compression section), pointing to the heap tuples for which the indexable |
| 140 |
items contain this key. This is called the "posting list". |
| 141 |
|
| 142 |
If the list would be too big for the index tuple to fit on an index page, the |
| 143 |
ItemPointers are pushed out to a separate posting page or pages, and none |
| 144 |
appear in the key entry itself. The separate pages are called a "posting |
| 145 |
tree" (see below); Note that in either case, the ItemPointers associated with |
| 146 |
a key can easily be read out in sorted order; this is relied on by the scan |
| 147 |
algorithms. |
| 148 |
|
| 149 |
* The index tuple header fields of a leaf key entry are abused as follows: |
| 150 |
|
| 151 |
1) Posting list case: |
| 152 |
|
| 153 |
* ItemPointerGetBlockNumber(&itup->t_tid) contains the offset from index |
| 154 |
tuple start to the posting list. |
| 155 |
Access macros: GinGetPostingOffset(itup) / GinSetPostingOffset(itup,n) |
| 156 |
|
| 157 |
* ItemPointerGetOffsetNumber(&itup->t_tid) contains the number of elements |
| 158 |
in the posting list (number of heap itempointers). |
| 159 |
Access macros: GinGetNPosting(itup) / GinSetNPosting(itup,n) |
| 160 |
|
| 161 |
* If IndexTupleHasNulls(itup) is true, the null category byte can be |
| 162 |
accessed/set with GinGetNullCategory(itup,gs) / GinSetNullCategory(itup,gs,c) |
| 163 |
|
| 164 |
* The posting list can be accessed with GinGetPosting(itup) |
| 165 |
|
| 166 |
* If GinItupIsCompressed(itup), the posting list is stored in compressed |
| 167 |
format. Otherwise it is just an array of ItemPointers. New tuples are always |
| 168 |
stored in compressed format, uncompressed items can be present if the |
| 169 |
database was migrated from 9.3 or earlier version. |
| 170 |
|
| 171 |
2) Posting tree case: |
| 172 |
|
| 173 |
* ItemPointerGetBlockNumber(&itup->t_tid) contains the index block number |
| 174 |
of the root of the posting tree. |
| 175 |
Access macros: GinGetPostingTree(itup) / GinSetPostingTree(itup, blkno) |
| 176 |
|
| 177 |
* ItemPointerGetOffsetNumber(&itup->t_tid) contains the magic number |
| 178 |
GIN_TREE_POSTING, which distinguishes this from the posting-list case |
| 179 |
(it's large enough that that many heap itempointers couldn't possibly |
| 180 |
fit on an index page). This value is inserted automatically by the |
| 181 |
GinSetPostingTree macro. |
| 182 |
|
| 183 |
* If IndexTupleHasNulls(itup) is true, the null category byte can be |
| 184 |
accessed/set with GinGetNullCategory(itup,gs) / GinSetNullCategory(itup,gs,c) |
| 185 |
|
| 186 |
* The posting list is not present and must not be accessed. |
| 187 |
|
| 188 |
Use the macro GinIsPostingTree(itup) to determine which case applies. |
| 189 |
|
| 190 |
In both cases, itup->t_info & INDEX_SIZE_MASK contains actual total size of |
| 191 |
tuple, and the INDEX_VAR_MASK and INDEX_NULL_MASK bits have their normal |
| 192 |
meanings as set by index_form_tuple. |
| 193 |
|
| 194 |
Index tuples in non-leaf levels of the btree contain the optional column |
| 195 |
number, key datum, and null category byte as above. They do not contain |
| 196 |
a posting list. ItemPointerGetBlockNumber(&itup->t_tid) is the downlink |
| 197 |
to the next lower btree level, and ItemPointerGetOffsetNumber(&itup->t_tid) |
| 198 |
is InvalidOffsetNumber. Use the access macros GinGetDownlink/GinSetDownlink |
| 199 |
to get/set the downlink. |
| 200 |
|
| 201 |
Index entries that appear in "pending list" pages work a tad differently as |
| 202 |
well. The optional column number, key datum, and null category byte are as |
| 203 |
for other GIN index entries. However, there is always exactly one heap |
| 204 |
itempointer associated with a pending entry, and it is stored in the t_tid |
| 205 |
header field just as in non-GIN indexes. There is no posting list. |
| 206 |
Furthermore, the code that searches the pending list assumes that all |
| 207 |
entries for a given heap tuple appear consecutively in the pending list and |
| 208 |
are sorted by the column-number-plus-key-datum. The GIN_LIST_FULLROW page |
| 209 |
flag bit tells whether entries for a given heap tuple are spread across |
| 210 |
multiple pending-list pages. If GIN_LIST_FULLROW is set, the page contains |
| 211 |
all the entries for one or more heap tuples. If GIN_LIST_FULLROW is clear, |
| 212 |
the page contains entries for only one heap tuple, *and* they are not all |
| 213 |
the entries for that tuple. (Thus, a heap tuple whose entries do not all |
| 214 |
fit on one pending-list page must have those pages to itself, even if this |
| 215 |
results in wasting much of the space on the preceding page and the last |
| 216 |
page for the tuple.) |
| 217 |
|
| 218 |
GIN packs downlinks and pivot keys into internal page tuples in a different way |
| 219 |
than nbtree does. Lehman & Yao defines it as following. |
| 220 |
|
| 221 |
P_0, K_1, P_1, K_2, P_2, ... , K_n, P_n, K_{n+1} |
| 222 |
|
| 223 |
There P_i is a downlink and K_i is a key. K_i splits key space between P_{i-1} |
| 224 |
and P_i (0 <= i <= n). K_{n+1} is high key. |
| 225 |
|
| 226 |
In internal page tuple is key and downlink grouped together. nbtree packs |
| 227 |
keys and downlinks into tuples as following. |
| 228 |
|
| 229 |
(K_{n+1}, None), (-Inf, P_0), (K_1, P_1), ... , (K_n, P_n) |
| 230 |
|
| 231 |
There tuples are shown in parentheses. So, highkey is stored separately. P_i |
| 232 |
is grouped with K_i. P_0 is grouped with -Inf key. |
| 233 |
|
| 234 |
GIN packs keys and downlinks into tuples in a different way. |
| 235 |
|
| 236 |
(P_0, K_1), (P_1, K_2), ... , (P_n, K_{n+1}) |
| 237 |
|
| 238 |
P_i is grouped with K_{i+1}. -Inf key is not needed. |
| 239 |
|
| 240 |
There are a couple of additional notes regarding K_{n+1} key. |
| 241 |
1) In the entry tree on the rightmost page, a key coupled with P_n doesn't really matter. |
| 242 |
Highkey is assumed to be infinity. |
| 243 |
2) In the posting tree, a key coupled with P_n always doesn't matter. Highkey for |
| 244 |
non-rightmost pages is stored separately and accessed via |
| 245 |
GinDataPageGetRightBound(). |
| 246 |
|
| 247 |
Posting tree |
| 248 |
------------ |
| 249 |
|
| 250 |
If a posting list is too large to store in-line in a key entry, a posting tree |
| 251 |
is created. A posting tree is a B-tree structure, where the ItemPointer is |
| 252 |
used as the key. |
| 253 |
|
| 254 |
Internal posting tree pages use the standard PageHeader and the same "opaque" |
| 255 |
struct as other GIN page, but do not contain regular index tuples. Instead, |
| 256 |
the contents of the page is an array of PostingItem structs. Each PostingItem |
| 257 |
consists of the block number of the child page, and the right bound of that |
| 258 |
child page, as an ItemPointer. The right bound of the page is stored right |
| 259 |
after the page header, before the PostingItem array. |
| 260 |
|
| 261 |
Posting tree leaf pages also use the standard PageHeader and opaque struct, |
| 262 |
and the right bound of the page is stored right after the page header, but |
| 263 |
the page content comprises of a number of compressed posting lists. The |
| 264 |
compressed posting lists are stored one after each other, between page header |
| 265 |
and pd_lower. The space between pd_lower and pd_upper is unused, which allows |
| 266 |
full-page images of posting tree leaf pages to skip the unused space in middle |
| 267 |
(buffer_std = true in XLogRecData). |
| 268 |
|
| 269 |
The item pointers are stored in a number of independent compressed posting |
| 270 |
lists (also called segments), instead of one big one, to make random access |
| 271 |
to a given item pointer faster: to find an item in a compressed list, you |
| 272 |
have to read the list from the beginning, but when the items are split into |
| 273 |
multiple lists, you can first skip over to the list containing the item you're |
| 274 |
looking for, and read only that segment. Also, an update only needs to |
| 275 |
re-encode the affected segment. |
| 276 |
|
| 277 |
Posting List Compression |
| 278 |
------------------------ |
| 279 |
|
| 280 |
To fit as many item pointers on a page as possible, posting tree leaf pages |
| 281 |
and posting lists stored inline in entry tree leaf tuples use a lightweight |
| 282 |
form of compression. We take advantage of the fact that the item pointers |
| 283 |
are stored in sorted order. Instead of storing the block and offset number of |
| 284 |
each item pointer separately, we store the difference from the previous item. |
| 285 |
That in itself doesn't do much, but it allows us to use so-called varbyte |
| 286 |
encoding to compress them. |
| 287 |
|
| 288 |
Varbyte encoding is a method to encode integers, allowing smaller numbers to |
| 289 |
take less space at the cost of larger numbers. Each integer is represented by |
| 290 |
variable number of bytes. High bit of each byte in varbyte encoding determines |
| 291 |
whether the next byte is still part of this number. Therefore, to read a single |
| 292 |
varbyte encoded number, you have to read bytes until you find a byte with the |
| 293 |
high bit not set. |
| 294 |
|
| 295 |
When encoding, the block and offset number forming the item pointer are |
| 296 |
combined into a single integer. The offset number is stored in the 11 low |
| 297 |
bits (see MaxHeapTuplesPerPageBits in ginpostinglist.c), and the block number |
| 298 |
is stored in the higher bits. That requires 43 bits in total, which |
| 299 |
conveniently fits in at most 6 bytes. |
| 300 |
|
| 301 |
A compressed posting list is passed around and stored on disk in a |
| 302 |
GinPostingList struct. The first item in the list is stored uncompressed |
| 303 |
as a regular ItemPointerData, followed by the length of the list in bytes, |
| 304 |
followed by the packed items. |
| 305 |
|
| 306 |
Concurrency |
| 307 |
----------- |
| 308 |
|
| 309 |
The entry tree and each posting tree are B-trees, with right-links connecting |
| 310 |
sibling pages at the same level. This is the same structure that is used in |
| 311 |
the regular B-tree indexam (invented by Lehman & Yao), but we don't support |
| 312 |
scanning a GIN trees backwards, so we don't need left-links. The entry tree |
| 313 |
leaves don't have dedicated high keys, instead greatest leaf tuple serves as |
| 314 |
high key. That works because tuples are never deleted from the entry tree. |
| 315 |
|
| 316 |
The algorithms used to operate entry and posting trees are considered below. |
| 317 |
|
| 318 |
### Locating the leaf page |
| 319 |
|
| 320 |
When we search for leaf page in GIN btree to perform a read, we descend from |
| 321 |
the root page to the leaf through using downlinks taking pin and shared lock on |
| 322 |
one page at once. So, we release pin and shared lock on previous page before |
| 323 |
getting them on the next page. |
| 324 |
|
| 325 |
The picture below shows tree state after finding the leaf page. Lower case |
| 326 |
letters depicts tree pages. 'S' depicts shared lock on the page. |
| 327 |
|
| 328 |
a |
| 329 |
/ | \ |
| 330 |
b c d |
| 331 |
/ | \ | \ | \ |
| 332 |
eS f g h i j k |
| 333 |
|
| 334 |
### Steping right |
| 335 |
|
| 336 |
Concurrent page splits move the keyspace to right, so after following a |
| 337 |
downlink, the page actually containing the key we're looking for might be |
| 338 |
somewhere to the right of the page we landed on. In that case, we follow the |
| 339 |
right-links until we find the page we're looking for. |
| 340 |
|
| 341 |
During stepping right we take pin and shared lock on the right sibling before |
| 342 |
releasing them from the current page. This mechanism was designed to protect |
| 343 |
from stepping to delete page. We step to the right sibling while hold lock on |
| 344 |
the rightlink pointing there. So, it's guaranteed that nobody updates rightlink |
| 345 |
concurrently and doesn't delete right sibling accordingly. |
| 346 |
|
| 347 |
The picture below shows two pages locked at once during stepping right. |
| 348 |
|
| 349 |
a |
| 350 |
/ | \ |
| 351 |
b c d |
| 352 |
/ | \ | \ | \ |
| 353 |
eS fS g h i j k |
| 354 |
|
| 355 |
### Insert |
| 356 |
|
| 357 |
While finding appropriate leaf for insertion we also descend from the root to |
| 358 |
leaf, while shared locking one page at once in. But during insertion we don't |
| 359 |
release pins from root and internal pages. That could save us some lookups to |
| 360 |
the buffers hash table for downlinks insertion assuming parents are not changed |
| 361 |
due to concurrent splits. Once we reach leaf we re-lock the page in exclusive |
| 362 |
mode. |
| 363 |
|
| 364 |
The picture below shows leaf page locked in exclusive mode and ready for |
| 365 |
insertion. 'P' and 'E' depict pin and exclusive lock correspondingly. |
| 366 |
|
| 367 |
|
| 368 |
aP |
| 369 |
/ | \ |
| 370 |
b cP d |
| 371 |
/ | \ | \ | \ |
| 372 |
e f g hE i j k |
| 373 |
|
| 374 |
|
| 375 |
If insert causes a page split, the parent is locked in exclusive mode before |
| 376 |
unlocking the left child. So, insertion algorithm can exclusively lock both |
| 377 |
parent and child pages at once starting from child. |
| 378 |
|
| 379 |
The picture below shows tree state after leaf page split. 'q' is new page |
| 380 |
produced by split. Parent 'c' is about to have downlink inserted. |
| 381 |
|
| 382 |
aP |
| 383 |
/ | \ |
| 384 |
b cE d |
| 385 |
/ | \ / | \ | \ |
| 386 |
e f g hE q i j k |
| 387 |
|
| 388 |
|
| 389 |
### Page deletion |
| 390 |
|
| 391 |
Vacuum never deletes tuples or pages from the entry tree. It traverses entry |
| 392 |
tree leafs in logical order by rightlinks and removes deletable TIDs from |
| 393 |
posting lists. Posting trees are processed by links from entry tree leafs. They |
| 394 |
are vacuumed in two stages. At first stage, deletable TIDs are removed from |
| 395 |
leafs. If first stage detects at least one empty page, then at the second stage |
| 396 |
ginScanToDelete() deletes empty pages. |
| 397 |
|
| 398 |
ginScanToDelete() traverses the whole tree in depth-first manner. It starts |
| 399 |
from the full cleanup lock on the tree root. This lock prevents all the |
| 400 |
concurrent insertions into this tree while we're deleting pages. However, |
| 401 |
there are still might be some in-progress readers, who traversed root before |
| 402 |
we locked it. |
| 403 |
|
| 404 |
The picture below shows tree state after page deletion algorithm traversed to |
| 405 |
leftmost leaf of the tree. |
| 406 |
|
| 407 |
aE |
| 408 |
/ | \ |
| 409 |
bE c d |
| 410 |
/ | \ | \ | \ |
| 411 |
eE f g h i j k |
| 412 |
|
| 413 |
Deletion algorithm keeps exclusive locks on left siblings of pages comprising |
| 414 |
currently investigated path. Thus, if current page is to be removed, all |
| 415 |
required pages to remove both downlink and rightlink are already locked. That |
| 416 |
avoids potential right to left page locking order, which could deadlock with |
| 417 |
concurrent stepping right. |
| 418 |
|
| 419 |
A search concurrent to page deletion might already have read a pointer to the |
| 420 |
page to be deleted, and might be just about to follow it. A page can be reached |
| 421 |
via the right-link of its left sibling, or via its downlink in the parent. |
| 422 |
|
| 423 |
To prevent a backend from reaching a deleted page via a right-link, stepping |
| 424 |
right algorithm doesn't release lock on the current page until lock of the |
| 425 |
right page is acquired. |
| 426 |
|
| 427 |
The downlink is more tricky. A search descending the tree must release the lock |
| 428 |
on the parent page before locking the child, or it could deadlock with a |
| 429 |
concurrent split of the child page; a page split locks the parent, while already |
| 430 |
holding a lock on the child page. So, deleted page cannot be reclaimed |
| 431 |
immediately. Instead, we have to wait for every transaction, which might wait |
| 432 |
to reference this page, to finish. Corresponding processes must observe that |
| 433 |
the page is marked deleted and recover accordingly. |
| 434 |
|
| 435 |
The picture below shows tree state after page deletion algorithm further |
| 436 |
traversed the tree. Currently investigated path is 'a-c-h'. Left siblings 'b' |
| 437 |
and 'g' of 'c' and 'h' correspondingly are also exclusively locked. |
| 438 |
|
| 439 |
aE |
| 440 |
/ | \ |
| 441 |
bE cE d |
| 442 |
/ | \ | \ | \ |
| 443 |
e f gE hE i j k |
| 444 |
|
| 445 |
The next picture shows tree state after page 'h' was deleted. It's marked with |
| 446 |
'deleted' flag and newest xid, which might visit it. Downlink from 'c' to 'h' |
| 447 |
is also deleted. |
| 448 |
|
| 449 |
aE |
| 450 |
/ | \ |
| 451 |
bE cE d |
| 452 |
/ | \ \ | \ |
| 453 |
e f gE hD iE j k |
| 454 |
|
| 455 |
However, it's still possible that concurrent reader has seen downlink from 'c' |
| 456 |
to 'h' before we deleted it. In that case this reader will step right from 'h' |
| 457 |
to till find non-deleted page. Xid-marking of page 'h' guarantees that this |
| 458 |
page wouldn't be reused till all such readers gone. Next leaf page under |
| 459 |
investigation is 'i'. 'g' remains locked as it becomes left sibling of 'i'. |
| 460 |
|
| 461 |
The next picture shows tree state after 'i' and 'c' was deleted. Internal page |
| 462 |
'c' was deleted because it appeared to have no downlinks. The path under |
| 463 |
investigation is 'a-d-j'. Pages 'b' and 'g' are locked as self siblings of 'd' |
| 464 |
and 'j'. |
| 465 |
|
| 466 |
aE |
| 467 |
/ \ |
| 468 |
bE cD dE |
| 469 |
/ | \ | \ |
| 470 |
e f gE hD iD jE k |
| 471 |
|
| 472 |
During the replay of page deletion at standby, the page's left sibling, the |
| 473 |
target page, and its parent, are locked in that order. This order guarantees |
| 474 |
no deadlock with concurrent reads. |
| 475 |
|
| 476 |
Predicate Locking |
| 477 |
----------------- |
| 478 |
|
| 479 |
GIN supports predicate locking, for serializable snapshot isolation. |
| 480 |
A predicate locks represent that a scan has scanned a range of values. They |
| 481 |
are not concerned with physical pages as such, but the logical key values. |
| 482 |
A predicate lock on a page covers the key range that would belong on that |
| 483 |
page, whether or not there are any matching tuples there currently. In other |
| 484 |
words, a predicate lock on an index page covers the "gaps" between the index |
| 485 |
tuples. To minimize false positives, predicate locks are acquired at the |
| 486 |
finest level possible. |
| 487 |
|
| 488 |
* Like in the B-tree index, it is enough to lock only leaf pages, because all |
| 489 |
insertions happen at the leaf level. |
| 490 |
|
| 491 |
* In an equality search (i.e. not a partial match search), if a key entry has |
| 492 |
a posting tree, we lock the posting tree root page, to represent a lock on |
| 493 |
just that key entry. Otherwise, we lock the entry tree page. We also lock |
| 494 |
the entry tree page if no match is found, to lock the "gap" where the entry |
| 495 |
would've been, had there been one. |
| 496 |
|
| 497 |
* In a partial match search, we lock all the entry leaf pages that we scan, |
| 498 |
in addition to locks on posting tree roots, to represent the "gaps" between |
| 499 |
values. |
| 500 |
|
| 501 |
* In addition to the locks on entry leaf pages and posting tree roots, all |
| 502 |
scans grab a lock the metapage. This is to interlock with insertions to |
| 503 |
the fast update pending list. An insertion to the pending list can really |
| 504 |
belong anywhere in the tree, and the lock on the metapage represents that. |
| 505 |
|
| 506 |
The interlock for fastupdate pending lists means that with fastupdate=on, |
| 507 |
we effectively always grab a full-index lock, so you could get a lot of false |
| 508 |
positives. |
| 509 |
|
| 510 |
Compatibility |
| 511 |
------------- |
| 512 |
|
| 513 |
Compression of TIDs was introduced in 9.4. Some GIN indexes could remain in |
| 514 |
uncompressed format because of pg_upgrade from 9.3 or earlier versions. |
| 515 |
For compatibility, old uncompressed format is also supported. Following |
| 516 |
rules are used to handle it: |
| 517 |
|
| 518 |
* GIN_ITUP_COMPRESSED flag marks index tuples that contain a posting list. |
| 519 |
This flag is stored in high bit of ItemPointerGetBlockNumber(&itup->t_tid). |
| 520 |
Use GinItupIsCompressed(itup) to check the flag. |
| 521 |
|
| 522 |
* Posting tree pages in the new format are marked with the GIN_COMPRESSED flag. |
| 523 |
Macros GinPageIsCompressed(page) and GinPageSetCompressed(page) are used to |
| 524 |
check and set this flag. |
| 525 |
|
| 526 |
* All scan operations check format of posting list add use corresponding code |
| 527 |
to read its content. |
| 528 |
|
| 529 |
* When updating an index tuple containing an uncompressed posting list, it |
| 530 |
will be replaced with new index tuple containing a compressed list. |
| 531 |
|
| 532 |
* When updating an uncompressed posting tree leaf page, it's compressed. |
| 533 |
|
| 534 |
* If vacuum finds some dead TIDs in uncompressed posting lists, they are |
| 535 |
converted into compressed posting lists. This assumes that the compressed |
| 536 |
posting list fits in the space occupied by the uncompressed list. IOW, we |
| 537 |
assume that the compressed version of the page, with the dead items removed, |
| 538 |
takes less space than the old uncompressed version. |
| 539 |
|
| 540 |
Limitations |
| 541 |
----------- |
| 542 |
|
| 543 |
* Gin doesn't use scan->kill_prior_tuple & scan->ignore_killed_tuples |
| 544 |
* Gin searches entries only by equality matching, or simple range |
| 545 |
matching using the "partial match" feature. |
| 546 |
|
| 547 |
TODO |
| 548 |
---- |
| 549 |
|
| 550 |
Nearest future: |
| 551 |
|
| 552 |
* Opclasses for more types (no programming, just many catalog changes) |
| 553 |
|
| 554 |
Distant future: |
| 555 |
|
| 556 |
* Replace B-tree of entries to something like GiST |
| 557 |
|
| 558 |
Authors |
| 559 |
------- |
| 560 |
|
| 561 |
Original work was done by Teodor Sigaev ([email protected]) and Oleg Bartunov |
| 562 |
([email protected]). |