Debian Codegraph @

src/backend/access/gist/README

raw
1 src/backend/access/gist/README
2
3 GiST Indexing
4 =============
5
6 This directory contains an implementation of GiST indexing for Postgres.
7
8 GiST stands for Generalized Search Tree. It was introduced in the seminal paper
9 "Generalized Search Trees for Database Systems", 1995, Joseph M. Hellerstein,
10 Jeffrey F. Naughton, Avi Pfeffer:
11
12 http://www.sai.msu.su/~megera/postgres/gist/papers/gist.ps
13 https://dsf.berkeley.edu/papers/sigmod97-gist.pdf
14
15 and implemented by J. Hellerstein and P. Aoki in an early version of
16 PostgreSQL (more details are available from The GiST Indexing Project
17 at Berkeley at http://gist.cs.berkeley.edu/). As a "university"
18 project it had a limited number of features and was in rare use.
19
20 The current implementation of GiST supports:
21
22 * Variable length keys
23 * Composite keys (multi-key)
24 * Ordered search (nearest-neighbor search)
25 * provides NULL-safe interface to GiST core
26 * Concurrency
27 * Recovery support via WAL logging
28 * Buffering build algorithm
29 * Sorted build method
30
31 The support for concurrency implemented in PostgreSQL was developed based on
32 the paper "Access Methods for Next-Generation Database Systems" by
33 Marcel Kornacker:
34
35 http://www.sai.msu.su/~megera/postgres/gist/papers/concurrency/access-methods-for-next-generation.pdf.gz
36
37 Buffering build algorithm for GiST was developed based on the paper "Efficient
38 Bulk Operations on Dynamic R-trees" by Lars Arge, Klaus Hinrichs, Jan Vahrenhold
39 and Jeffrey Scott Vitter.
40
41 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.9894&rep=rep1&type=pdf
42
43 The original algorithms were modified in several ways:
44
45 * They had to be adapted to PostgreSQL conventions. For example, the SEARCH
46 algorithm was considerably changed, because in PostgreSQL the search function
47 should return one tuple (next), not all tuples at once. Also, it should
48 release page locks between calls.
49 * Since we added support for variable length keys, it's not possible to
50 guarantee enough free space for all keys on pages after splitting. User
51 defined function picksplit doesn't have information about size of tuples
52 (each tuple may contain several keys as in multicolumn index while picksplit
53 could work with only one key) and pages.
54 * We modified original INSERT algorithm for performance reasons. In particular,
55 it is now a single-pass algorithm.
56 * Since the papers were theoretical, some details were omitted and we
57 had to find out ourself how to solve some specific problems.
58
59 Because of the above reasons, we have revised the interaction of GiST
60 core and PostgreSQL WAL system. Moreover, we encountered (and solved)
61 a problem of uncompleted insertions when recovering after crash, which
62 was not touched in the paper.
63
64 Search Algorithm
65 ----------------
66
67 The search code maintains a queue of unvisited items, where an "item" is
68 either a heap tuple known to satisfy the search conditions, or an index
69 page that is consistent with the search conditions according to inspection
70 of its parent page's downlink item. Initially the root page is searched
71 to find unvisited items in it. Then we pull items from the queue. A
72 heap tuple pointer is just returned immediately; an index page entry
73 causes that page to be searched, generating more queue entries.
74
75 The queue is kept ordered with heap tuple items at the front, then
76 index page entries, with any newly-added index page entry inserted
77 before existing index page entries. This ensures depth-first traversal
78 of the index, and in particular causes the first few heap tuples to be
79 returned as soon as possible. That is helpful in case there is a LIMIT
80 that requires only a few tuples to be produced.
81
82 To implement nearest-neighbor search, the queue entries are augmented
83 with distance data: heap tuple entries are labeled with exact distance
84 from the search argument, while index-page entries must be labeled with
85 the minimum distance that any of their children could have. Then,
86 queue entries are retrieved in smallest-distance-first order, with
87 entries having identical distances managed as stated in the previous
88 paragraph.
89
90 The search algorithm keeps an index page locked only long enough to scan
91 its entries and queue those that satisfy the search conditions. Since
92 insertions can occur concurrently with searches, it is possible for an
93 index child page to be split between the time we make a queue entry for it
94 (while visiting its parent page) and the time we actually reach and scan
95 the child page. To avoid missing the entries that were moved to the right
96 sibling, we detect whether a split has occurred by comparing the child
97 page's NSN (node sequence number, a special-purpose LSN) to the LSN that
98 the parent had when visited. If it did, the sibling page is immediately
99 added to the front of the queue, ensuring that its items will be scanned
100 in the same order as if they were still on the original child page.
101
102 As is usual in Postgres, the search algorithm only guarantees to find index
103 entries that existed before the scan started; index entries added during
104 the scan might or might not be visited. This is okay as long as all
105 searches use MVCC snapshot rules to reject heap tuples newer than the time
106 of scan start. In particular, this means that we need not worry about
107 cases where a parent page's downlink key is "enlarged" after we look at it.
108 Any such enlargement would be to add child items that we aren't interested
109 in returning anyway.
110
111
112 Insert Algorithm
113 ----------------
114
115 INSERT guarantees that the GiST tree remains balanced. User defined key method
116 Penalty is used for choosing a subtree to insert; method PickSplit is used for
117 the node splitting algorithm; method Union is used for propagating changes
118 upward to maintain the tree properties.
119
120 To insert a tuple, we first have to find a suitable leaf page to insert to.
121 The algorithm walks down the tree, starting from the root, along the path
122 of smallest Penalty. At each step:
123
124 1. Has this page been split since we looked at the parent? If so, it's
125 possible that we should be inserting to the other half instead, so retreat
126 back to the parent.
127 2. If this is a leaf node, we've found our target node.
128 3. Otherwise use Penalty to pick a new target subtree.
129 4. Check the key representing the target subtree. If it doesn't already cover
130 the key we're inserting, replace it with the Union of the old downlink key
131 and the key being inserted. (Actually, we always call Union, and just skip
132 the replacement if the Unioned key is the same as the existing key)
133 5. Replacing the key in step 4 might cause the page to be split. In that case,
134 propagate the change upwards and restart the algorithm from the first parent
135 that didn't need to be split.
136 6. Walk down to the target subtree, and goto 1.
137
138 This differs from the insertion algorithm in the original paper. In the
139 original paper, you first walk down the tree until you reach a leaf page, and
140 then you adjust the downlink in the parent, and propagate the adjustment up,
141 all the way up to the root in the worst case. But we adjust the downlinks to
142 cover the new key already when we walk down, so that when we reach the leaf
143 page, we don't need to update the parents anymore, except to insert the
144 downlinks if we have to split the page. This makes crash recovery simpler:
145 after inserting a key to the page, the tree is immediately self-consistent
146 without having to update the parents. Even if we split a page and crash before
147 inserting the downlink to the parent, the tree is self-consistent because the
148 right half of the split is accessible via the rightlink of the left page
149 (which replaced the original page).
150
151 Note that the algorithm can walk up and down the tree before reaching a leaf
152 page, if internal pages need to split while adjusting the downlinks for the
153 new key. Eventually, you should reach the bottom, and proceed with the
154 insertion of the new tuple.
155
156 Once we've found the target page to insert to, we check if there's room
157 for the new tuple. If there is, the tuple is inserted, and we're done.
158 If it doesn't fit, however, the page needs to be split. Note that it is
159 possible that a page needs to be split into more than two pages, if keys have
160 different lengths or more than one key is being inserted at a time (which can
161 happen when inserting downlinks for a page split that resulted in more than
162 two pages at the lower level). After splitting a page, the parent page needs
163 to be updated. The downlink for the new page needs to be inserted, and the
164 downlink for the old page, which became the left half of the split, needs to
165 be updated to only cover those tuples that stayed on the left page. Inserting
166 the downlink in the parent can again lead to a page split, recursing up to the
167 root page in the worst case.
168
169 gistplacetopage is the workhorse function that performs one step of the
170 insertion. If the tuple fits, it inserts it to the given page, otherwise
171 it splits the page, and constructs the new downlink tuples for the split
172 pages. The caller must then call gistplacetopage() on the parent page to
173 insert the downlink tuples. The parent page that holds the downlink to
174 the child might have migrated as a result of concurrent splits of the
175 parent, gistFindCorrectParent() is used to find the parent page.
176
177 Splitting the root page works slightly differently. At root split,
178 gistplacetopage() allocates the new child pages and replaces the old root
179 page with the new root containing downlinks to the new children, all in one
180 operation.
181
182
183 findPath is a subroutine of findParent, used when the correct parent page
184 can't be found by following the rightlinks at the parent level:
185
186 findPath( stack item )
187 push stack, [root, 0, 0] // page, LSN, parent
188 while( stack )
189 ptr = top of stack
190 latch( ptr->page, S-mode )
191 if ( ptr->parent->page->lsn < ptr->page->nsn )
192 push stack, [ ptr->page->rightlink, 0, ptr->parent ]
193 end
194 for( each tuple on page )
195 if ( tuple->pagepointer == item->page )
196 return stack
197 else
198 add to stack at the end [tuple->pagepointer,0, ptr]
199 end
200 end
201 unlatch( ptr->page )
202 pop stack
203 end
204
205
206 gistFindCorrectParent is used to re-find the parent of a page during
207 insertion. It might have migrated to the right since we traversed down the
208 tree because of page splits.
209
210 findParent( stack item )
211 parent = item->parent
212 if ( parent->page->lsn != parent->lsn )
213 while(true)
214 search parent tuple on parent->page, if found the return
215 rightlink = parent->page->rightlink
216 unlatch( parent->page )
217 if ( rightlink is incorrect )
218 break loop
219 end
220 parent->page = rightlink
221 latch( parent->page, X-mode )
222 end
223 newstack = findPath( item->parent )
224 replace part of stack to new one
225 latch( parent->page, X-mode )
226 return findParent( item )
227 end
228
229 pageSplit function decides how to distribute keys to the new pages after
230 page split:
231
232 pageSplit(page, allkeys)
233 (lkeys, rkeys) = pickSplit( allkeys )
234 if ( page is root )
235 lpage = new page
236 else
237 lpage = page
238 rpage = new page
239 if ( no space left on rpage )
240 newkeys = pageSplit( rpage, rkeys )
241 else
242 push newkeys, union(rkeys)
243 end
244 if ( no space left on lpage )
245 push newkeys, pageSplit( lpage, lkeys )
246 else
247 push newkeys, union(lkeys)
248 end
249 return newkeys
250
251
252
253 Concurrency control
254 -------------------
255 As a rule of thumb, if you need to hold a lock on multiple pages at the
256 same time, the locks should be acquired in the following order: child page
257 before parent, and left-to-right at the same level. Always acquiring the
258 locks in the same order avoids deadlocks.
259
260 The search algorithm only looks at and locks one page at a time. Consequently
261 there's a race condition between a search and a page split. A page split
262 happens in two phases: 1. The page is split 2. The downlink is inserted to the
263 parent. If a search looks at the parent page between those steps, before the
264 downlink is inserted, it will still find the new right half by following the
265 rightlink on the left half. But it must not follow the rightlink if it saw the
266 downlink in the parent, or the page will be visited twice!
267
268 A split initially marks the left page with the F_FOLLOW_RIGHT flag. If a scan
269 sees that flag set, it knows that the right page is missing the downlink, and
270 should be visited too. When split inserts the downlink to the parent, it
271 clears the F_FOLLOW_RIGHT flag in the child, and sets the NSN field in the
272 child page header to match the LSN of the insertion on the parent. If the
273 F_FOLLOW_RIGHT flag is not set, a scan compares the NSN on the child and the
274 LSN it saw in the parent. If the child's NSN is greater than the LSN seen on
275 the parent, the scan looked at the parent page before the downlink was
276 inserted, so it should follow the rightlink. Otherwise the scan saw the
277 downlink in the parent page, and will/did follow that as usual.
278
279 A scan can't normally see a page with the F_FOLLOW_RIGHT flag set, because
280 a page split keeps the child pages locked until the downlink has been inserted
281 to the parent and the flag cleared again. But if a crash happens in the middle
282 of a page split, before the downlinks are inserted into the parent, that will
283 leave a page with F_FOLLOW_RIGHT in the tree. Scans handle that just fine,
284 but we'll eventually want to fix that for performance reasons. And more
285 importantly, dealing with pages with missing downlink pointers in the parent
286 would complicate the insertion algorithm. So when an insertion sees a page
287 with F_FOLLOW_RIGHT set, it immediately tries to bring the split that
288 crashed in the middle to completion by adding the downlink in the parent.
289
290 Buffering build algorithm
291 -------------------------
292
293 In the buffering index build algorithm, some or all internal nodes have a
294 buffer attached to them. When a tuple is inserted at the top, the descend down
295 the tree is stopped as soon as a buffer is reached, and the tuple is pushed to
296 the buffer. When a buffer gets too full, all the tuples in it are flushed to
297 the lower level, where they again hit lower level buffers or leaf pages. This
298 makes the insertions happen in more of a breadth-first than depth-first order,
299 which greatly reduces the amount of random I/O required.
300
301 In the algorithm, levels are numbered so that leaf pages have level zero,
302 and internal node levels count up from 1. This numbering ensures that a page's
303 level number never changes, even when the root page is split.
304
305 Level Tree
306
307 3 *
308 / \
309 2 * *
310 / | \ / | \
311 1 * * * * * *
312 / \ / \ / \ / \ / \ / \
313 0 o o o o o o o o o o o o
314
315 * - internal page
316 o - leaf page
317
318 Internal pages that belong to certain levels have buffers associated with
319 them. Leaf pages never have buffers. Which levels have buffers is controlled
320 by "level step" parameter: level numbers that are multiples of level_step
321 have buffers, while others do not. For example, if level_step = 2, then
322 pages on levels 2, 4, 6, ... have buffers. If level_step = 1 then every
323 internal page has a buffer.
324
325 Level Tree (level_step = 1) Tree (level_step = 2)
326
327 3 * *
328 / \ / \
329 2 *(b) *(b) *(b) *(b)
330 / | \ / | \ / | \ / | \
331 1 *(b) *(b) *(b) *(b) *(b) *(b) * * * * * *
332 / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
333 0 o o o o o o o o o o o o o o o o o o o o o o o o
334
335 (b) - buffer
336
337 Logically, a buffer is just bunch of tuples. Physically, it is divided in
338 pages, backed by a temporary file. Each buffer can be in one of two states:
339 a) Last page of the buffer is kept in main memory. A node buffer is
340 automatically switched to this state when a new index tuple is added to it,
341 or a tuple is removed from it.
342 b) All pages of the buffer are swapped out to disk. When a buffer becomes too
343 full, and we start to flush it, all other buffers are switched to this state.
344
345 When an index tuple is inserted, its initial processing can end in one of the
346 following points:
347 1) Leaf page, if the depth of the index <= level_step, meaning that
348 none of the internal pages have buffers associated with them.
349 2) Buffer of topmost level page that has buffers.
350
351 New index tuples are processed until one of the buffers in the topmost
352 buffered level becomes half-full. When a buffer becomes half-full, it's added
353 to the emptying queue, and will be emptied before a new tuple is processed.
354
355 Buffer emptying process means that index tuples from the buffer are moved
356 into buffers at a lower level, or leaf pages. First, all the other buffers are
357 swapped to disk to free up the memory. Then tuples are popped from the buffer
358 one by one, and cascaded down the tree to the next buffer or leaf page below
359 the buffered node.
360
361 Emptying a buffer has the interesting dynamic property that any intermediate
362 pages between the buffer being emptied, and the next buffered or leaf level
363 below it, become cached. If there are no more buffers below the node, the leaf
364 pages where the tuples finally land on get cached too. If there are, the last
365 buffer page of each buffer below is kept in memory. This is illustrated in
366 the figures below:
367
368 Buffer being emptied to
369 lower-level buffers Buffer being emptied to leaf pages
370
371 +(fb) +(fb)
372 / \ / \
373 + + + +
374 / \ / \ / \ / \
375 *(ab) *(ab) *(ab) *(ab) x x x x
376
377 + - cached internal page
378 x - cached leaf page
379 * - non-cached internal page
380 (fb) - buffer being emptied
381 (ab) - buffers being appended to, with last page in memory
382
383 In the beginning of the index build, the level-step is chosen so that all those
384 pages involved in emptying one buffer fit in cache, so after each of those
385 pages have been accessed once and cached, emptying a buffer doesn't involve
386 any more I/O. This locality is where the speedup of the buffering algorithm
387 comes from.
388
389 Emptying one buffer can fill up one or more of the lower-level buffers,
390 triggering emptying of them as well. Whenever a buffer becomes too full, it's
391 added to the emptying queue, and will be emptied after the current buffer has
392 been processed.
393
394 To keep the size of each buffer limited even in the worst case, buffer emptying
395 is scheduled as soon as a buffer becomes half-full, and emptying it continues
396 until 1/2 of the nominal buffer size worth of tuples has been emptied. This
397 guarantees that when buffer emptying begins, all the lower-level buffers
398 are at most half-full. In the worst case that all the tuples are cascaded down
399 to the same lower-level buffer, that buffer therefore has enough space to
400 accommodate all the tuples emptied from the upper-level buffer. There is no
401 hard size limit in any of the data structures used, though, so this only needs
402 to be approximate; small overfilling of some buffers doesn't matter.
403
404 If an internal page that has a buffer associated with it is split, the buffer
405 needs to be split too. All tuples in the buffer are scanned through and
406 relocated to the correct sibling buffers, using the penalty function to decide
407 which buffer each tuple should go to.
408
409 After all tuples from the heap have been processed, there are still some index
410 tuples in the buffers. At this point, final buffer emptying starts. All buffers
411 are emptied in top-down order. This is slightly complicated by the fact that
412 new buffers can be allocated during the emptying, due to page splits. However,
413 the new buffers will always be siblings of buffers that haven't been fully
414 emptied yet; tuples never move upwards in the tree. The final emptying loops
415 through buffers at a given level until all buffers at that level have been
416 emptied, and then moves down to the next level.
417
418 Sorted build method
419 -------------------
420
421 Sort all input tuples, pack them into GiST leaf pages in the sorted order,
422 and create downlinks and internal pages as we go. This method builds the index
423 from the bottom up, similar to how the B-tree index is built.
424
425 The sorted method is used if the operator classes for all columns have a
426 "sortsupport" defined. Otherwise, we fall back on inserting tuples one by one
427 with optional buffering.
428
429 Sorting GiST build requires good linearization of the sort opclass. That is not
430 always the case in multidimensional data. To tackle the anomalies, we buffer
431 index tuples and apply a picksplit function that can be multidimensional-aware.
432
433 Bulk delete algorithm (VACUUM)
434 ------------------------------
435
436 VACUUM works in two stages:
437
438 In the first stage, we scan the whole index in physical order. To make sure
439 that we don't miss any dead tuples because a concurrent page split moved them,
440 we check the F_FOLLOW_RIGHT flags and NSN on each page, to detect if the
441 page has been concurrently split. If a concurrent page split is detected, and
442 one half of the page was moved to a position that we already scanned, we
443 "jump backwards" to scan the page again. This is the same mechanism that
444 B-tree VACUUM uses, but because we already have NSNs on pages, to detect page
445 splits during searches, we don't need a "vacuum cycle ID" concept for that
446 like B-tree does.
447
448 While we scan all the pages, we also make note of any completely empty leaf
449 pages. We will try to unlink them from the tree after the scan. We also record
450 the block numbers of all internal pages; they are needed to locate parents of
451 the empty pages while unlinking them.
452
453 We try to unlink any empty leaf pages from the tree, so that their space can
454 be reused. In order to delete an empty page, its downlink must be removed from
455 the parent. We scan all the internal pages, whose block numbers we memorized
456 in the first stage, and look for downlinks to pages that we have memorized as
457 being empty. Whenever we find one, we acquire a lock on the parent and child
458 page, re-check that the child page is still empty. Then, we remove the
459 downlink and mark the child as deleted, and release the locks.
460
461 The insertion algorithm would get confused, if an internal page was completely
462 empty. So we never delete the last child of an internal page, even if it's
463 empty. Currently, we only support deleting leaf pages.
464
465 This page deletion algorithm works on a best-effort basis. It might fail to
466 find a downlink, if a concurrent page split moved it after the first stage.
467 In that case, we won't be able to remove all empty pages. That's OK, it's
468 not expected to happen very often, and hopefully the next VACUUM will clean
469 it up.
470
471 When we have deleted a page, it's possible that an in-progress search will
472 still descend on the page, if it saw the downlink before we removed it. The
473 search will see that it is deleted, and ignore it, but as long as that can
474 happen, we cannot reuse the page. To "wait out" any in-progress searches, when
475 a page is deleted, it's labeled with the current next-transaction counter
476 value. The page is not recycled, until that XID is no longer visible to
477 anyone. That's much more conservative than necessary, but let's keep it
478 simple.
479
480
481 Authors:
482 Teodor Sigaev <[email protected]>
483 Oleg Bartunov <[email protected]>