Debian Codegraph @

src/backend/access/nbtree/README

raw
1 src/backend/access/nbtree/README
2
3 Btree Indexing
4 ==============
5
6 This directory contains a correct implementation of Lehman and Yao's
7 high-concurrency B-tree management algorithm (P. Lehman and S. Yao,
8 Efficient Locking for Concurrent Operations on B-Trees, ACM Transactions
9 on Database Systems, Vol 6, No. 4, December 1981, pp 650-670). We also
10 use a simplified version of the deletion logic described in Lanin and
11 Shasha (V. Lanin and D. Shasha, A Symmetric Concurrent B-Tree Algorithm,
12 Proceedings of 1986 Fall Joint Computer Conference, pp 380-389).
13
14 The basic Lehman & Yao Algorithm
15 --------------------------------
16
17 Compared to a classic B-tree, L&Y adds a right-link pointer to each page,
18 to the page's right sibling. It also adds a "high key" to each page, which
19 is an upper bound on the keys that are allowed on that page. These two
20 additions make it possible to detect a concurrent page split, which allows
21 the tree to be searched without holding any read locks (except to keep a
22 single page from being modified while reading it).
23
24 When a search follows a downlink to a child page, it compares the page's
25 high key with the search key. If the search key is greater than the high
26 key, the page must've been split concurrently, and you must follow the
27 right-link to find the new page containing the key range you're looking
28 for. This might need to be repeated, if the page has been split more than
29 once.
30
31 Lehman and Yao talk about alternating "separator" keys and downlinks in
32 internal pages rather than tuples or records. We use the term "pivot"
33 tuple to refer to tuples which don't point to heap tuples, that are used
34 only for tree navigation. All tuples on non-leaf pages and high keys on
35 leaf pages are pivot tuples. Since pivot tuples are only used to represent
36 which part of the key space belongs on each page, they can have attribute
37 values copied from non-pivot tuples that were deleted and killed by VACUUM
38 some time ago. A pivot tuple may contain a "separator" key and downlink,
39 just a separator key (i.e. the downlink value is implicitly undefined), or
40 just a downlink (i.e. all attributes are truncated away).
41
42 The requirement that all btree keys be unique is satisfied by treating heap
43 TID as a tiebreaker attribute. Logical duplicates are sorted in heap TID
44 order. This is necessary because Lehman and Yao also require that the key
45 range for a subtree S is described by Ki < v <= Ki+1 where Ki and Ki+1 are
46 the adjacent keys in the parent page (Ki must be _strictly_ less than v,
47 which is assured by having reliably unique keys). Keys are always unique
48 on their level, with the exception of a leaf page's high key, which can be
49 fully equal to the last item on the page.
50
51 The Postgres implementation of suffix truncation must make sure that the
52 Lehman and Yao invariants hold, and represents that absent/truncated
53 attributes in pivot tuples have the sentinel value "minus infinity". The
54 later section on suffix truncation will be helpful if it's unclear how the
55 Lehman & Yao invariants work with a real world example.
56
57 Differences to the Lehman & Yao algorithm
58 -----------------------------------------
59
60 We have made the following changes in order to incorporate the L&Y algorithm
61 into Postgres:
62
63 Lehman and Yao don't require read locks, but assume that in-memory
64 copies of tree pages are unshared. Postgres shares in-memory buffers
65 among backends. As a result, we do page-level read locking on btree
66 pages in order to guarantee that no record is modified while we are
67 examining it. This reduces concurrency but guarantees correct
68 behavior.
69
70 We support the notion of an ordered "scan" of an index as well as
71 insertions, deletions, and simple lookups. A scan in the forward
72 direction is no problem, we just use the right-sibling pointers that
73 L&Y require anyway. (Thus, once we have descended the tree to the
74 correct start point for the scan, the scan looks only at leaf pages
75 and never at higher tree levels.) To support scans in the backward
76 direction, we also store a "left sibling" link much like the "right
77 sibling". (This adds an extra step to the L&Y split algorithm: while
78 holding the write lock on the page being split, we also lock its former
79 right sibling to update that page's left-link. This is safe since no
80 writer of that page can be interested in acquiring a write lock on our
81 page.) A backwards scan has one additional bit of complexity: after
82 following the left-link we must account for the possibility that the
83 left sibling page got split before we could read it. So, we have to
84 move right until we find a page whose right-link matches the page we
85 came from. (Actually, it's even harder than that; see page deletion
86 discussion below.)
87
88 Page read locks are held only for as long as a scan is examining a page.
89 To minimize lock/unlock traffic, an index scan always searches a leaf page
90 to identify all the matching items at once, copying their heap tuple IDs
91 into backend-local storage. The heap tuple IDs are then processed while
92 not holding any page lock within the index. We do continue to hold a pin
93 on the leaf page in some circumstances, to protect against concurrent
94 deletions (see below). In this state the scan is effectively stopped
95 "between" pages, either before or after the page it has pinned. This is
96 safe in the presence of concurrent insertions and even page splits, because
97 items are never moved across pre-existing page boundaries --- so the scan
98 cannot miss any items it should have seen, nor accidentally return the same
99 item twice. The scan must remember the page's right-link at the time it
100 was scanned, since that is the page to move right to; if we move right to
101 the current right-link then we'd re-scan any items moved by a page split.
102 We also remember the left-link, and follow it when the scan moves backwards
103 (though this requires extra handling to account for concurrent splits of
104 the left sibling; see detailed move-left algorithm below).
105
106 In most cases we release our lock and pin on a page before attempting
107 to acquire pin and lock on the page we are moving to. In a few places
108 it is necessary to lock the next page before releasing the current one.
109 This is safe when moving right or up, but not when moving left or down
110 (else we'd create the possibility of deadlocks).
111
112 Lehman and Yao fail to discuss what must happen when the root page
113 becomes full and must be split. Our implementation is to split the
114 root in the same way that any other page would be split, then construct
115 a new root page holding pointers to both of the resulting pages (which
116 now become siblings on the next level of the tree). The new root page
117 is then installed by altering the root pointer in the meta-data page (see
118 below). This works because the root is not treated specially in any
119 other way --- in particular, searches will move right using its link
120 pointer if the link is set. Therefore, searches will find the data
121 that's been moved into the right sibling even if they read the meta-data
122 page before it got updated. This is the same reasoning that makes a
123 split of a non-root page safe. The locking considerations are similar too.
124
125 When an inserter recurses up the tree, splitting internal pages to insert
126 links to pages inserted on the level below, it is possible that it will
127 need to access a page above the level that was the root when it began its
128 descent (or more accurately, the level that was the root when it read the
129 meta-data page). In this case the stack it made while descending does not
130 help for finding the correct page. When this happens, we find the correct
131 place by re-descending the tree until we reach the level one above the
132 level we need to insert a link to, and then moving right as necessary.
133 (Typically this will take only two fetches, the meta-data page and the new
134 root, but in principle there could have been more than one root split
135 since we saw the root. We can identify the correct tree level by means of
136 the level numbers stored in each page. The situation is rare enough that
137 we do not need a more efficient solution.)
138
139 Lehman and Yao must couple/chain locks as part of moving right when
140 relocating a child page's downlink during an ascent of the tree. This is
141 the only point where Lehman and Yao have to simultaneously hold three
142 locks (a lock on the child, the original parent, and the original parent's
143 right sibling). We don't need to couple internal page locks for pages on
144 the same level, though. We match a child's block number to a downlink
145 from a pivot tuple one level up, whereas Lehman and Yao match on the
146 separator key associated with the downlink that was followed during the
147 initial descent. We can release the lock on the original parent page
148 before acquiring a lock on its right sibling, since there is never any
149 need to deal with the case where the separator key that we must relocate
150 becomes the original parent's high key. Lanin and Shasha don't couple
151 locks here either, though they also don't couple locks between levels
152 during ascents. They are willing to "wait and try again" to avoid races.
153 Their algorithm is optimistic, which means that "an insertion holds no
154 more than one write lock at a time during its ascent". We more or less
155 stick with Lehman and Yao's approach of conservatively coupling parent and
156 child locks when ascending the tree, since it's far simpler.
157
158 Lehman and Yao assume fixed-size keys, but we must deal with
159 variable-size keys. Therefore there is not a fixed maximum number of
160 keys per page; we just stuff in as many as will fit. When we split a
161 page, we try to equalize the number of bytes, not items, assigned to
162 pages (though suffix truncation is also considered). Note we must include
163 the incoming item in this calculation, otherwise it is possible to find
164 that the incoming item doesn't fit on the split page where it needs to go!
165
166 Deleting index tuples during VACUUM
167 -----------------------------------
168
169 Before deleting a leaf item, we get a full cleanup lock on the target
170 page, so that no other backend has a pin on the page when the deletion
171 starts. This is not necessary for correctness in terms of the btree index
172 operations themselves; as explained above, index scans logically stop
173 "between" pages and so can't lose their place. The reason we do it is to
174 provide an interlock between VACUUM and index scans that are not prepared
175 to deal with concurrent TID recycling when visiting the heap. Since only
176 VACUUM can ever mark pointed-to items LP_UNUSED in the heap, and since
177 this only ever happens _after_ btbulkdelete returns, having index scans
178 hold on to the pin (used when reading from the leaf page) until _after_
179 they're done visiting the heap (for TIDs from pinned leaf page) prevents
180 concurrent TID recycling. VACUUM cannot get a conflicting cleanup lock
181 until the index scan is totally finished processing its leaf page.
182
183 This approach is fairly coarse, so we avoid it whenever possible. In
184 practice most index scans won't hold onto their pin, and so won't block
185 VACUUM. These index scans must deal with TID recycling directly, which is
186 more complicated and not always possible. See later section on making
187 concurrent TID recycling safe.
188
189 Opportunistic index tuple deletion performs almost the same page-level
190 modifications while only holding an exclusive lock. This is safe because
191 there is no question of TID recycling taking place later on -- only VACUUM
192 can make TIDs recyclable. See also simple deletion and bottom-up
193 deletion, below.
194
195 Because a pin is not always held, and a page can be split even while
196 someone does hold a pin on it, it is possible that an indexscan will
197 return items that are no longer stored on the page it has a pin on, but
198 rather somewhere to the right of that page. To ensure that VACUUM can't
199 prematurely make TIDs recyclable in this scenario, we require btbulkdelete
200 to obtain a cleanup lock on every leaf page in the index, even pages that
201 don't contain any deletable tuples. Note that this requirement does not
202 say that btbulkdelete must visit the pages in any particular order.
203
204 VACUUM's linear scan, concurrent page splits
205 --------------------------------------------
206
207 VACUUM accesses the index by doing a linear scan to search for deletable
208 TIDs, while considering the possibility of deleting empty pages in
209 passing. This is in physical/block order, not logical/keyspace order.
210 The tricky part of this is avoiding missing any deletable tuples in the
211 presence of concurrent page splits: a page split could easily move some
212 tuples from a page not yet passed over by the sequential scan to a
213 lower-numbered page already passed over.
214
215 To implement this, we provide a "vacuum cycle ID" mechanism that makes it
216 possible to determine whether a page has been split since the current
217 btbulkdelete cycle started. If btbulkdelete finds a page that has been
218 split since it started, and has a right-link pointing to a lower page
219 number, then it temporarily suspends its sequential scan and visits that
220 page instead. It must continue to follow right-links and vacuum dead
221 tuples until reaching a page that either hasn't been split since
222 btbulkdelete started, or is above the location of the outer sequential
223 scan. Then it can resume the sequential scan. This ensures that all
224 tuples are visited. It may be that some tuples are visited twice, but
225 that has no worse effect than an inaccurate index tuple count (and we
226 can't guarantee an accurate count anyway in the face of concurrent
227 activity). Note that this still works if the has-been-recently-split test
228 has a small probability of false positives, so long as it never gives a
229 false negative. This makes it possible to implement the test with a small
230 counter value stored on each index page.
231
232 Deleting entire pages during VACUUM
233 -----------------------------------
234
235 We consider deleting an entire page from the btree only when it's become
236 completely empty of items. (Merging partly-full pages would allow better
237 space reuse, but it seems impractical to move existing data items left or
238 right to make this happen --- a scan moving in the opposite direction
239 might miss the items if so.) Also, we *never* delete the rightmost page
240 on a tree level (this restriction simplifies the traversal algorithms, as
241 explained below). Page deletion always begins from an empty leaf page. An
242 internal page can only be deleted as part of deleting an entire subtree.
243 This is always a "skinny" subtree consisting of a "chain" of internal pages
244 plus a single leaf page. There is one page on each level of the subtree,
245 and each level/page covers the same key space.
246
247 Deleting a leaf page is a two-stage process. In the first stage, the page
248 is unlinked from its parent, and marked as half-dead. The parent page must
249 be found using the same type of search as used to find the parent during an
250 insertion split. We lock the target and the parent pages, change the
251 target's downlink to point to the right sibling, and remove its old
252 downlink. This causes the target page's key space to effectively belong to
253 its right sibling. (Neither the left nor right sibling pages need to
254 change their "high key" if any; so there is no problem with possibly not
255 having enough space to replace a high key.) At the same time, we mark the
256 target page as half-dead, which causes any subsequent searches to ignore it
257 and move right (or left, in a backwards scan). This leaves the tree in a
258 similar state as during a page split: the page has no downlink pointing to
259 it, but it's still linked to its siblings.
260
261 (Note: Lanin and Shasha prefer to make the key space move left, but their
262 argument for doing so hinges on not having left-links, which we have
263 anyway. So we simplify the algorithm by moving the key space right. This
264 is only possible because we don't match on a separator key when ascending
265 the tree during a page split, unlike Lehman and Yao/Lanin and Shasha -- it
266 doesn't matter if the downlink is re-found in a pivot tuple whose separator
267 key does not match the one encountered when inserter initially descended
268 the tree.)
269
270 To preserve consistency on the parent level, we cannot merge the key space
271 of a page into its right sibling unless the right sibling is a child of
272 the same parent --- otherwise, the parent's key space assignment changes
273 too, meaning we'd have to make bounding-key updates in its parent, and
274 perhaps all the way up the tree. Since we can't possibly do that
275 atomically, we forbid this case. That means that the rightmost child of a
276 parent node can't be deleted unless it's the only remaining child, in which
277 case we will delete the parent too (see below).
278
279 In the second-stage, the half-dead leaf page is unlinked from its siblings.
280 We first lock the left sibling (if any) of the target, the target page
281 itself, and its right sibling (there must be one) in that order. Then we
282 update the side-links in the siblings, and mark the target page deleted.
283
284 When we're about to delete the last remaining child of a parent page, things
285 are slightly more complicated. In the first stage, we leave the immediate
286 parent of the leaf page alone, and remove the downlink to the parent page
287 instead, from the grandparent. If it's the last child of the grandparent
288 too, we recurse up until we find a parent with more than one child, and
289 remove the downlink of that page. The leaf page is marked as half-dead, and
290 the block number of the page whose downlink was removed is stashed in the
291 half-dead leaf page. This leaves us with a chain of internal pages, with
292 one downlink each, leading to the half-dead leaf page, and no downlink
293 pointing to the topmost page in the chain.
294
295 While we recurse up to find the topmost parent in the chain, we keep the
296 leaf page locked, but don't need to hold locks on the intermediate pages
297 between the leaf and the topmost parent -- insertions into upper tree levels
298 happen only as a result of splits of child pages, and that can't happen as
299 long as we're keeping the leaf locked. The internal pages in the chain
300 cannot acquire new children afterwards either, because the leaf page is
301 marked as half-dead and won't be split.
302
303 Removing the downlink to the top of the to-be-deleted subtree/chain
304 effectively transfers the key space to the right sibling for all the
305 intermediate levels too, in one atomic operation. A concurrent search might
306 still visit the intermediate pages, but it will move right when it reaches
307 the half-dead page at the leaf level. In particular, the search will move to
308 the subtree to the right of the half-dead leaf page/to-be-deleted subtree,
309 since the half-dead leaf page's right sibling must be a "cousin" page, not a
310 "true" sibling page (or a second cousin page when the to-be-deleted chain
311 starts at leaf page's grandparent page, and so on).
312
313 In the second stage, the topmost page in the chain is unlinked from its
314 siblings, and the half-dead leaf page is updated to point to the next page
315 down in the chain. This is repeated until there are no internal pages left
316 in the chain. Finally, the half-dead leaf page itself is unlinked from its
317 siblings.
318
319 A deleted page cannot be recycled immediately, since there may be other
320 processes waiting to reference it (ie, search processes that just left the
321 parent, or scans moving right or left from one of the siblings). These
322 processes must be able to observe a deleted page for some time after the
323 deletion operation, in order to be able to at least recover from it (they
324 recover by moving right, as with concurrent page splits). Searchers never
325 have to worry about concurrent page recycling.
326
327 See "Placing deleted pages in the FSM" section below for a description of
328 when and how deleted pages become safe for VACUUM to make recyclable.
329
330 Page deletion and backwards scans
331 ---------------------------------
332
333 Moving left in a backward scan is complicated because we must consider
334 the possibility that the left sibling was just split (meaning we must find
335 the rightmost page derived from the left sibling), plus the possibility
336 that the page we were just on has now been deleted and hence isn't in the
337 sibling chain at all anymore. So the move-left algorithm becomes:
338
339 0. Remember the page we are on as the "original page".
340 1. Follow the original page's left-link (we're done if this is zero).
341 2. If the current page is live and its right-link matches the "original
342 page", we are done.
343 3. Otherwise, move right one or more times looking for a live page whose
344 right-link matches the "original page". If found, we are done. (In
345 principle we could scan all the way to the right end of the index, but
346 in practice it seems better to give up after a small number of tries.
347 It's unlikely the original page's sibling split more than a few times
348 while we were in flight to it; if we do not find a matching link in a
349 few tries, then most likely the original page is deleted.)
350 4. Return to the "original page". If it is still live, return to step 1
351 (we guessed wrong about it being deleted, and should restart with its
352 current left-link). If it is dead, move right until a non-dead page
353 is found (there must be one, since rightmost pages are never deleted),
354 mark that as the new "original page", and return to step 1.
355
356 This algorithm is correct because the live page found by step 4 will have
357 the same left keyspace boundary as the page we started from. Therefore,
358 when we ultimately exit, it must be on a page whose right keyspace
359 boundary matches the left boundary of where we started --- which is what
360 we need to be sure we don't miss or re-scan any items.
361
362 Page deletion and tree height
363 -----------------------------
364
365 Because we never delete the rightmost page of any level (and in particular
366 never delete the root), it's impossible for the height of the tree to
367 decrease. After massive deletions we might have a scenario in which the
368 tree is "skinny", with several single-page levels below the root.
369 Operations will still be correct in this case, but we'd waste cycles
370 descending through the single-page levels. To handle this we use an idea
371 from Lanin and Shasha: we keep track of the "fast root" level, which is
372 the lowest single-page level. The meta-data page keeps a pointer to this
373 level as well as the true root. All ordinary operations initiate their
374 searches at the fast root not the true root. When we split a page that is
375 alone on its level or delete the next-to-last page on a level (both cases
376 are easily detected), we have to make sure that the fast root pointer is
377 adjusted appropriately. In the split case, we do this work as part of the
378 atomic update for the insertion into the parent level; in the delete case
379 as part of the atomic update for the delete (either way, the metapage has
380 to be the last page locked in the update to avoid deadlock risks). This
381 avoids race conditions if two such operations are executing concurrently.
382
383 Placing deleted pages in the FSM
384 --------------------------------
385
386 Recycling a page is decoupled from page deletion. A deleted page can only
387 be put in the FSM to be recycled once there is no possible scan or search
388 that has a reference to it; until then, it must stay in place with its
389 sibling links undisturbed, as a tombstone that allows concurrent searches
390 to detect and then recover from concurrent deletions (which are rather
391 like concurrent page splits to searchers). This design is an
392 implementation of what Lanin and Shasha call "the drain technique".
393
394 We implement the technique by waiting until all active snapshots and
395 registered snapshots as of the page deletion are gone; which is overly
396 strong, but is simple to implement within Postgres. When marked fully
397 dead, a deleted page is labeled with the next-transaction counter value.
398 VACUUM can reclaim the page for re-use when the stored XID is guaranteed
399 to be "visible to everyone". As collateral damage, we wait for snapshots
400 taken until the next transaction to allocate an XID commits. We also wait
401 for running XIDs with no snapshots.
402
403 Prior to PostgreSQL 14, VACUUM would only place _old_ deleted pages that
404 it encounters during its linear scan (pages deleted by a previous VACUUM
405 operation) in the FSM. Newly deleted pages were never placed in the FSM,
406 because that was assumed to _always_ be unsafe. That assumption was
407 unnecessarily pessimistic in practice, though -- it often doesn't take
408 very long for newly deleted pages to become safe to place in the FSM.
409 There is no truly principled way to predict when deleted pages will become
410 safe to place in the FSM for recycling -- it might become safe almost
411 immediately (long before the current VACUUM completes), or it might not
412 even be safe by the time the next VACUUM takes place. Recycle safety is
413 purely a question of maintaining the consistency (or at least the apparent
414 consistency) of a physical data structure. The state within the backend
415 running VACUUM is simply not relevant.
416
417 PostgreSQL 14 added the ability for VACUUM to consider if it's possible to
418 recycle newly deleted pages at the end of the full index scan where the
419 page deletion took place. It is convenient to check if it's safe at that
420 point. This does require that VACUUM keep around a little bookkeeping
421 information about newly deleted pages, but that's very cheap. Using
422 in-memory state for this avoids the need to revisit newly deleted pages a
423 second time later on -- we can just use safexid values from the local
424 bookkeeping state to determine recycle safety in a deferred fashion.
425
426 The need for additional FSM indirection after a page deletion operation
427 takes place is a natural consequence of the highly permissive rules for
428 index scans with Lehman and Yao's design. In general an index scan
429 doesn't have to hold a lock or even a pin on any page when it descends the
430 tree (nothing that you'd usually think of as an interlock is held "between
431 levels"). At the same time, index scans cannot be allowed to land on a
432 truly unrelated page due to concurrent recycling (not to be confused with
433 concurrent deletion), because that results in wrong answers to queries.
434 Simpler approaches to page deletion that don't need to defer recycling are
435 possible, but none seem compatible with Lehman and Yao's design.
436
437 Placing an already-deleted page in the FSM to be recycled when needed
438 doesn't actually change the state of the page. The page will be changed
439 whenever it is subsequently taken from the FSM for reuse. The deleted
440 page's contents will be overwritten by the split operation (it will become
441 the new right sibling page).
442
443 Making concurrent TID recycling safe
444 ------------------------------------
445
446 As explained in the earlier section about deleting index tuples during
447 VACUUM, we implement a locking protocol that allows individual index scans
448 to avoid concurrent TID recycling. Index scans opt-out (and so drop their
449 leaf page pin when visiting the heap) whenever it's safe to do so, though.
450 Dropping the pin early is useful because it avoids blocking progress by
451 VACUUM. This is particularly important with index scans used by cursors,
452 since idle cursors sometimes stop for relatively long periods of time. In
453 extreme cases, a client application may hold on to an idle cursors for
454 hours or even days. Blocking VACUUM for that long could be disastrous.
455
456 Index scans that don't hold on to a buffer pin are protected by holding an
457 MVCC snapshot instead. This more limited interlock prevents wrong answers
458 to queries, but it does not prevent concurrent TID recycling itself (only
459 holding onto the leaf page pin while accessing the heap ensures that).
460
461 Index-only scans can never drop their buffer pin, since they are unable to
462 tolerate having a referenced TID become recyclable. Index-only scans
463 typically just visit the visibility map (not the heap proper), and so will
464 not reliably notice that any stale TID reference (for a TID that pointed
465 to a dead-to-all heap item at first) was concurrently marked LP_UNUSED in
466 the heap by VACUUM. This could easily allow VACUUM to set the whole heap
467 page to all-visible in the visibility map immediately afterwards. An MVCC
468 snapshot is only sufficient to avoid problems during plain index scans
469 because they must access granular visibility information from the heap
470 proper. A plain index scan will even recognize LP_UNUSED items in the
471 heap (items that could be recycled but haven't been just yet) as "not
472 visible" -- even when the heap page is generally considered all-visible.
473
474 LP_DEAD setting of index tuples by the kill_prior_tuple optimization
475 (described in full in simple deletion, below) is also more complicated for
476 index scans that drop their leaf page pins. We must be careful to avoid
477 LP_DEAD-marking any new index tuple that looks like a known-dead index
478 tuple because it happens to share the same TID, following concurrent TID
479 recycling. It's just about possible that some other session inserted a
480 new, unrelated index tuple, on the same leaf page, which has the same
481 original TID. It would be totally wrong to LP_DEAD-set this new,
482 unrelated index tuple.
483
484 We handle this kill_prior_tuple race condition by having affected index
485 scans conservatively assume that any change to the leaf page at all
486 implies that it was reached by btbulkdelete in the interim period when no
487 buffer pin was held. This is implemented by not setting any LP_DEAD bits
488 on the leaf page at all when the page's LSN has changed. (That won't work
489 with an unlogged index, so for now we don't ever apply the "don't hold
490 onto pin" optimization there.)
491
492 Fastpath For Index Insertion
493 ----------------------------
494
495 We optimize for a common case of insertion of increasing index key
496 values by caching the last page to which this backend inserted the last
497 value, if this page was the rightmost leaf page. For the next insert, we
498 can then quickly check if the cached page is still the rightmost leaf
499 page and also the correct place to hold the current value. We can avoid
500 the cost of walking down the tree in such common cases.
501
502 The optimization works on the assumption that there can only be one
503 non-ignorable leaf rightmost page, and so not even a visible-to-everyone
504 style interlock is required. We cannot fail to detect that our hint was
505 invalidated, because there can only be one such page in the B-Tree at
506 any time. It's possible that the page will be deleted and recycled
507 without a backend's cached page also being detected as invalidated, but
508 only when we happen to recycle a block that once again gets recycled as the
509 rightmost leaf page.
510
511 Simple deletion
512 ---------------
513
514 If a process visits a heap tuple and finds that it's dead and removable
515 (ie, dead to all open transactions, not only that process), then we can
516 return to the index and mark the corresponding index entry "known dead",
517 allowing subsequent index scans to skip visiting the heap tuple. The
518 "known dead" marking works by setting the index item's lp_flags state
519 to LP_DEAD. This is currently only done in plain indexscans, not bitmap
520 scans, because only plain scans visit the heap and index "in sync" and so
521 there's not a convenient way to do it for bitmap scans. Note also that
522 LP_DEAD bits are often set when checking a unique index for conflicts on
523 insert (this is simpler because it takes place when we hold an exclusive
524 lock on the leaf page).
525
526 Once an index tuple has been marked LP_DEAD it can actually be deleted
527 from the index immediately; since index scans only stop "between" pages,
528 no scan can lose its place from such a deletion. We separate the steps
529 because we allow LP_DEAD to be set with only a share lock (it's like a
530 hint bit for a heap tuple), but physically deleting tuples requires an
531 exclusive lock. We also need to generate a snapshotConflictHorizon for
532 each deletion operation's WAL record, which requires additional
533 coordinating with the tableam when the deletion actually takes place.
534 (snapshotConflictHorizon value may be used to generate a conflict during
535 subsequent REDO of the record by a standby.)
536
537 Delaying and batching index tuple deletion like this enables a further
538 optimization: opportunistic checking of "extra" nearby index tuples
539 (tuples that are not LP_DEAD-set) when they happen to be very cheap to
540 check in passing (because we already know that the tableam will be
541 visiting their table block to generate a snapshotConflictHorizon). Any
542 index tuples that turn out to be safe to delete will also be deleted.
543 Simple deletion will behave as if the extra tuples that actually turn
544 out to be delete-safe had their LP_DEAD bits set right from the start.
545
546 Deduplication can also prevent a page split, but index tuple deletion is
547 our preferred approach. Note that posting list tuples can only have
548 their LP_DEAD bit set when every table TID within the posting list is
549 known dead. This isn't much of a problem in practice because LP_DEAD
550 bits are just a starting point for deletion. What really matters is
551 that _some_ deletion operation that targets related nearby-in-table TIDs
552 takes place at some point before the page finally splits. That's all
553 that's required for the deletion process to perform granular removal of
554 groups of dead TIDs from posting list tuples (without the situation ever
555 being allowed to get out of hand).
556
557 Bottom-Up deletion
558 ------------------
559
560 We attempt to delete whatever duplicates happen to be present on the page
561 when the duplicates are suspected to be caused by version churn from
562 successive UPDATEs. This only happens when we receive an executor hint
563 indicating that optimizations like heapam's HOT have not worked out for
564 the index -- the incoming tuple must be a logically unchanged duplicate
565 which is needed for MVCC purposes, suggesting that that might well be the
566 dominant source of new index tuples on the leaf page in question. (Also,
567 bottom-up deletion is triggered within unique indexes in cases with
568 continual INSERT and DELETE related churn, since that is easy to detect
569 without any external hint.)
570
571 Simple deletion will already have failed to prevent a page split when a
572 bottom-up deletion pass takes place (often because no LP_DEAD bits were
573 ever set on the page). The two mechanisms have closely related
574 implementations. The same WAL records are used for each operation, and
575 the same tableam infrastructure is used to determine what TIDs/tuples are
576 actually safe to delete. The implementations only differ in how they pick
577 TIDs to consider for deletion, and whether or not the tableam will give up
578 before accessing all table blocks (bottom-up deletion lives with the
579 uncertainty of its success by keeping the cost of failure low). Even
580 still, the two mechanisms are clearly distinct at the conceptual level.
581
582 Bottom-up index deletion is driven entirely by heuristics (whereas simple
583 deletion is guaranteed to delete at least those index tuples that are
584 already LP_DEAD marked -- there must be at least one). We have no
585 certainty that we'll find even one index tuple to delete. That's why we
586 closely cooperate with the tableam to keep the costs it pays in balance
587 with the benefits we receive. The interface that we use for this is
588 described in detail in access/tableam.h.
589
590 Bottom-up index deletion can be thought of as a backstop mechanism against
591 unnecessary version-driven page splits. It is based in part on an idea
592 from generational garbage collection: the "generational hypothesis". This
593 is the empirical observation that "most objects die young". Within
594 nbtree, new index tuples often quickly appear in the same place, and then
595 quickly become garbage. There can be intense concentrations of garbage in
596 relatively few leaf pages with certain workloads (or there could be in
597 earlier versions of PostgreSQL without bottom-up index deletion, at
598 least). See doc/src/sgml/btree.sgml for a high-level description of the
599 design principles behind bottom-up index deletion in nbtree, including
600 details of how it complements VACUUM.
601
602 We expect to find a reasonably large number of tuples that are safe to
603 delete within each bottom-up pass. If we don't then we won't need to
604 consider the question of bottom-up deletion for the same leaf page for
605 quite a while (usually because the page splits, which resolves the
606 situation for the time being). We expect to perform regular bottom-up
607 deletion operations against pages that are at constant risk of unnecessary
608 page splits caused only by version churn. When the mechanism works well
609 we'll constantly be "on the verge" of having version-churn-driven page
610 splits, but never actually have even one.
611
612 Our duplicate heuristics work well despite being fairly simple.
613 Unnecessary page splits only occur when there are truly pathological
614 levels of version churn (in theory a small amount of version churn could
615 make a page split occur earlier than strictly necessary, but that's pretty
616 harmless). We don't have to understand the underlying workload; we only
617 have to understand the general nature of the pathology that we target.
618 Version churn is easy to spot when it is truly pathological. Affected
619 leaf pages are fairly homogeneous.
620
621 WAL Considerations
622 ------------------
623
624 The insertion and deletion algorithms in themselves don't guarantee btree
625 consistency after a crash. To provide robustness, we depend on WAL
626 replay. A single WAL entry is effectively an atomic action --- we can
627 redo it from the log if it fails to complete.
628
629 Ordinary item insertions (that don't force a page split) are of course
630 single WAL entries, since they only affect one page. The same for
631 leaf-item deletions (if the deletion brings the leaf page to zero items,
632 it is now a candidate to be deleted, but that is a separate action).
633
634 An insertion that causes a page split is logged as a single WAL entry for
635 the changes occurring on the insertion's level --- including update of the
636 right sibling's left-link --- followed by a second WAL entry for the
637 insertion on the parent level (which might itself be a page split, requiring
638 an additional insertion above that, etc).
639
640 For a root split, the follow-on WAL entry is a "new root" entry rather than
641 an "insertion" entry, but details are otherwise much the same.
642
643 Because splitting involves multiple atomic actions, it's possible that the
644 system crashes between splitting a page and inserting the downlink for the
645 new half to the parent. After recovery, the downlink for the new page will
646 be missing. The search algorithm works correctly, as the page will be found
647 by following the right-link from its left sibling, although if a lot of
648 downlinks in the tree are missing, performance will suffer. A more serious
649 consequence is that if the page without a downlink gets split again, the
650 insertion algorithm will fail to find the location in the parent level to
651 insert the downlink.
652
653 Our approach is to create any missing downlinks on-the-fly, when searching
654 the tree for a new insertion. It could be done during searches, too, but
655 it seems best not to put any extra updates in what would otherwise be a
656 read-only operation (updating is not possible in hot standby mode anyway).
657 It would seem natural to add the missing downlinks in VACUUM, but since
658 inserting a downlink might require splitting a page, it might fail if you
659 run out of disk space. That would be bad during VACUUM - the reason for
660 running VACUUM in the first place might be that you run out of disk space,
661 and now VACUUM won't finish because you're out of disk space. In contrast,
662 an insertion can require enlarging the physical file anyway. There is one
663 minor exception: VACUUM finishes interrupted splits of internal pages when
664 deleting their children. This allows the code for re-finding parent items
665 to be used by both page splits and page deletion.
666
667 To identify missing downlinks, when a page is split, the left page is
668 flagged to indicate that the split is not yet complete (INCOMPLETE_SPLIT).
669 When the downlink is inserted to the parent, the flag is cleared atomically
670 with the insertion. The child page is kept locked until the insertion in
671 the parent is finished and the flag in the child cleared, but can be
672 released immediately after that, before recursing up the tree if the parent
673 also needs to be split. This ensures that incompletely split pages should
674 not be seen under normal circumstances; only if insertion to the parent
675 has failed for some reason. (It's also possible for a reader to observe
676 a page with the incomplete split flag set during recovery; see later
677 section on "Scans during Recovery" for details.)
678
679 We flag the left page, even though it's the right page that's missing the
680 downlink, because it's more convenient to know already when following the
681 right-link from the left page to the right page that it will need to have
682 its downlink inserted to the parent.
683
684 When splitting a non-root page that is alone on its level, the required
685 metapage update (of the "fast root" link) is performed and logged as part
686 of the insertion into the parent level. When splitting the root page, the
687 metapage update is handled as part of the "new root" action.
688
689 Each step in page deletion is logged as a separate WAL entry: marking the
690 leaf as half-dead and removing the downlink is one record, and unlinking a
691 page is a second record. If vacuum is interrupted for some reason, or the
692 system crashes, the tree is consistent for searches and insertions. The
693 next VACUUM will find the half-dead leaf page and continue the deletion.
694
695 Before 9.4, we used to keep track of incomplete splits and page deletions
696 during recovery and finish them immediately at end of recovery, instead of
697 doing it lazily at the next insertion or vacuum. However, that made the
698 recovery much more complicated, and only fixed the problem when crash
699 recovery was performed. An incomplete split can also occur if an otherwise
700 recoverable error, like out-of-memory or out-of-disk-space, happens while
701 inserting the downlink to the parent.
702
703 Scans during Recovery
704 ---------------------
705
706 nbtree indexes support read queries in Hot Standby mode. Every atomic
707 action/WAL record makes isolated changes that leave the tree in a
708 consistent state for readers. Readers lock pages according to the same
709 rules that readers follow on the primary. (Readers may have to move
710 right to recover from a "concurrent" page split or page deletion, just
711 like on the primary.)
712
713 However, there are a couple of differences in how pages are locked by
714 replay/the startup process as compared to the original write operation
715 on the primary. The exceptions involve page splits and page deletions.
716 The first phase and second phase of a page split are processed
717 independently during replay, since they are independent atomic actions.
718 We do not attempt to recreate the coupling of parent and child page
719 write locks that took place on the primary. This is safe because readers
720 never care about the incomplete split flag anyway. Holding on to an
721 extra write lock on the primary is only necessary so that a second
722 writer cannot observe the incomplete split flag before the first writer
723 finishes the split. If we let concurrent writers on the primary observe
724 an incomplete split flag on the same page, each writer would attempt to
725 complete the unfinished split, corrupting the parent page. (Similarly,
726 replay of page deletion records does not hold a write lock on the target
727 leaf page throughout; only the primary needs to block out concurrent
728 writers that insert on to the page being deleted.)
729
730 WAL replay holds same-level locks in a way that matches the approach
731 taken during original execution, though. This prevent readers from
732 observing same-level inconsistencies. It's probably possible to be more
733 lax about how same-level locks are acquired during recovery (most kinds
734 of readers could still move right to recover if we didn't couple
735 same-level locks), but we prefer to be conservative here.
736
737 During recovery all index scans start with ignore_killed_tuples = false
738 and we never set kill_prior_tuple. We do this because the oldest xmin
739 on the standby server can be older than the oldest xmin on the primary
740 server, which means tuples can be marked LP_DEAD even when they are
741 still visible on the standby. We don't WAL log tuple LP_DEAD bits, but
742 they can still appear in the standby because of full page writes. So
743 we must always ignore them in standby, and that means it's not worth
744 setting them either. (When LP_DEAD-marked tuples are eventually deleted
745 on the primary, the deletion is WAL-logged. Queries that run on a
746 standby therefore get much of the benefit of any LP_DEAD setting that
747 takes place on the primary.)
748
749 Note that we talk about scans that are started during recovery. We go to
750 a little trouble to allow a scan to start during recovery and end during
751 normal running after recovery has completed. This is a key capability
752 because it allows running applications to continue while the standby
753 changes state into a normally running server.
754
755 The interlocking required to avoid returning incorrect results from
756 non-MVCC scans is not required on standby nodes. We still get a full
757 cleanup lock when replaying VACUUM records during recovery, but recovery
758 does not need to lock every leaf page (only those leaf pages that have
759 items to delete) -- that's sufficient to avoid breaking index-only scans
760 during recovery (see section above about making TID recycling safe). That
761 leaves concern only for plain index scans. (XXX: Not actually clear why
762 this is totally unnecessary during recovery.)
763
764 MVCC snapshot plain index scans are always safe, for the same reasons that
765 they're safe during original execution. HeapTupleSatisfiesToast() doesn't
766 use MVCC semantics, though that's because it doesn't need to - if the main
767 heap row is visible then the toast rows will also be visible. So as long
768 as we follow a toast pointer from a visible (live) tuple the corresponding
769 toast rows will also be visible, so we do not need to recheck MVCC on
770 them.
771
772 Other Things That Are Handy to Know
773 -----------------------------------
774
775 Page zero of every btree is a meta-data page. This page stores the
776 location of the root page --- both the true root and the current effective
777 root ("fast" root). To avoid fetching the metapage for every single index
778 search, we cache a copy of the meta-data information in the index's
779 relcache entry (rd_amcache). This is a bit ticklish since using the cache
780 implies following a root page pointer that could be stale. However, a
781 backend following a cached pointer can sufficiently verify whether it
782 reached the intended page; either by checking the is-root flag when it
783 is going to the true root, or by checking that the page has no siblings
784 when going to the fast root. At worst, this could result in descending
785 some extra tree levels if we have a cached pointer to a fast root that is
786 now above the real fast root. Such cases shouldn't arise often enough to
787 be worth optimizing; and in any case we can expect a relcache flush will
788 discard the cached metapage before long, since a VACUUM that's moved the
789 fast root pointer can be expected to issue a statistics update for the
790 index.
791
792 The algorithm assumes we can fit at least three items per page
793 (a "high key" and two real data items). Therefore it's unsafe
794 to accept items larger than 1/3rd page size. Larger items would
795 work sometimes, but could cause failures later on depending on
796 what else gets put on their page.
797
798 "ScanKey" data structures are used in two fundamentally different ways
799 in this code, which we describe as "search" scankeys and "insertion"
800 scankeys. A search scankey is the kind passed to btbeginscan() or
801 btrescan() from outside the btree code. The sk_func pointers in a search
802 scankey point to comparison functions that return boolean, such as int4lt.
803 There might be more than one scankey entry for a given index column, or
804 none at all. (We require the keys to appear in index column order, but
805 the order of multiple keys for a given column is unspecified.) An
806 insertion scankey ("BTScanInsert" data structure) uses a similar
807 array-of-ScanKey data structure, but the sk_func pointers point to btree
808 comparison support functions (ie, 3-way comparators that return int4 values
809 interpreted as <0, =0, >0). In an insertion scankey there is at most one
810 entry per index column. There is also other data about the rules used to
811 locate where to begin the scan, such as whether or not the scan is a
812 "nextkey" scan. Insertion scankeys are built within the btree code (eg, by
813 _bt_mkscankey()) and are used to locate the starting point of a scan, as
814 well as for locating the place to insert a new index tuple. (Note: in the
815 case of an insertion scankey built from a search scankey or built from a
816 truncated pivot tuple, there might be fewer keys than index columns,
817 indicating that we have no constraints for the remaining index columns.)
818 After we have located the starting point of a scan, the original search
819 scankey is consulted as each index entry is sequentially scanned to decide
820 whether to return the entry and whether the scan can stop (see
821 _bt_checkkeys()).
822
823 Notes about suffix truncation
824 -----------------------------
825
826 We truncate away suffix key attributes that are not needed for a page high
827 key during a leaf page split. The remaining attributes must distinguish
828 the last index tuple on the post-split left page as belonging on the left
829 page, and the first index tuple on the post-split right page as belonging
830 on the right page. Tuples logically retain truncated key attributes,
831 though they implicitly have "negative infinity" as their value, and have no
832 storage overhead. Since the high key is subsequently reused as the
833 downlink in the parent page for the new right page, suffix truncation makes
834 pivot tuples short. INCLUDE indexes are guaranteed to have non-key
835 attributes truncated at the time of a leaf page split, but may also have
836 some key attributes truncated away, based on the usual criteria for key
837 attributes. They are not a special case, since non-key attributes are
838 merely payload to B-Tree searches.
839
840 The goal of suffix truncation of key attributes is to improve index
841 fan-out. The technique was first described by Bayer and Unterauer (R.Bayer
842 and K.Unterauer, Prefix B-Trees, ACM Transactions on Database Systems, Vol
843 2, No. 1, March 1977, pp 11-26). The Postgres implementation is loosely
844 based on their paper. Note that Postgres only implements what the paper
845 refers to as simple prefix B-Trees. Note also that the paper assumes that
846 the tree has keys that consist of single strings that maintain the "prefix
847 property", much like strings that are stored in a suffix tree (comparisons
848 of earlier bytes must always be more significant than comparisons of later
849 bytes, and, in general, the strings must compare in a way that doesn't
850 break transitive consistency as they're split into pieces). Suffix
851 truncation in Postgres currently only works at the whole-attribute
852 granularity, but it would be straightforward to invent opclass
853 infrastructure that manufactures a smaller attribute value in the case of
854 variable-length types, such as text. An opclass support function could
855 manufacture the shortest possible key value that still correctly separates
856 each half of a leaf page split.
857
858 There is sophisticated criteria for choosing a leaf page split point. The
859 general idea is to make suffix truncation effective without unduly
860 influencing the balance of space for each half of the page split. The
861 choice of leaf split point can be thought of as a choice among points
862 *between* items on the page to be split, at least if you pretend that the
863 incoming tuple was placed on the page already (you have to pretend because
864 there won't actually be enough space for it on the page). Choosing the
865 split point between two index tuples where the first non-equal attribute
866 appears as early as possible results in truncating away as many suffix
867 attributes as possible. Evenly balancing space among each half of the
868 split is usually the first concern, but even small adjustments in the
869 precise split point can allow truncation to be far more effective.
870
871 Suffix truncation is primarily valuable because it makes pivot tuples
872 smaller, which delays splits of internal pages, but that isn't the only
873 reason why it's effective. Even truncation that doesn't make pivot tuples
874 smaller due to alignment still prevents pivot tuples from being more
875 restrictive than truly necessary in how they describe which values belong
876 on which pages.
877
878 While it's not possible to correctly perform suffix truncation during
879 internal page splits, it's still useful to be discriminating when splitting
880 an internal page. The split point that implies a downlink be inserted in
881 the parent that's the smallest one available within an acceptable range of
882 the fillfactor-wise optimal split point is chosen. This idea also comes
883 from the Prefix B-Tree paper. This process has much in common with what
884 happens at the leaf level to make suffix truncation effective. The overall
885 effect is that suffix truncation tends to produce smaller, more
886 discriminating pivot tuples, especially early in the lifetime of the index,
887 while biasing internal page splits makes the earlier, smaller pivot tuples
888 end up in the root page, delaying root page splits.
889
890 Logical duplicates are given special consideration. The logic for
891 selecting a split point goes to great lengths to avoid having duplicates
892 span more than one page, and almost always manages to pick a split point
893 between two user-key-distinct tuples, accepting a completely lopsided split
894 if it must. When a page that's already full of duplicates must be split,
895 the fallback strategy assumes that duplicates are mostly inserted in
896 ascending heap TID order. The page is split in a way that leaves the left
897 half of the page mostly full, and the right half of the page mostly empty.
898 The overall effect is that leaf page splits gracefully adapt to inserts of
899 large groups of duplicates, maximizing space utilization. Note also that
900 "trapping" large groups of duplicates on the same leaf page like this makes
901 deduplication more efficient. Deduplication can be performed infrequently,
902 without merging together existing posting list tuples too often.
903
904 Notes about deduplication
905 -------------------------
906
907 We deduplicate non-pivot tuples in non-unique indexes to reduce storage
908 overhead, and to avoid (or at least delay) page splits. Note that the
909 goals for deduplication in unique indexes are rather different; see later
910 section for details. Deduplication alters the physical representation of
911 tuples without changing the logical contents of the index, and without
912 adding overhead to read queries. Non-pivot tuples are merged together
913 into a single physical tuple with a posting list (a simple array of heap
914 TIDs with the standard item pointer format). Deduplication is always
915 applied lazily, at the point where it would otherwise be necessary to
916 perform a page split. It occurs only when LP_DEAD items have been
917 removed, as our last line of defense against splitting a leaf page
918 (bottom-up index deletion may be attempted first, as our second last line
919 of defense). We can set the LP_DEAD bit with posting list tuples, though
920 only when all TIDs are known dead.
921
922 Our lazy approach to deduplication allows the page space accounting used
923 during page splits to have absolutely minimal special case logic for
924 posting lists. Posting lists can be thought of as extra payload that
925 suffix truncation will reliably truncate away as needed during page
926 splits, just like non-key columns from an INCLUDE index tuple.
927 Incoming/new tuples can generally be treated as non-overlapping plain
928 items (though see section on posting list splits for information about how
929 overlapping new/incoming items are really handled).
930
931 The representation of posting lists is almost identical to the posting
932 lists used by GIN, so it would be straightforward to apply GIN's varbyte
933 encoding compression scheme to individual posting lists. Posting list
934 compression would break the assumptions made by posting list splits about
935 page space accounting (see later section), so it's not clear how
936 compression could be integrated with nbtree. Besides, posting list
937 compression does not offer a compelling trade-off for nbtree, since in
938 general nbtree is optimized for consistent performance with many
939 concurrent readers and writers. Compression would also make the deletion
940 of a subset of TIDs from a posting list slow and complicated, which would
941 be a big problem for workloads that depend heavily on bottom-up index
942 deletion.
943
944 A major goal of our lazy approach to deduplication is to limit the
945 performance impact of deduplication with random updates. Even concurrent
946 append-only inserts of the same key value will tend to have inserts of
947 individual index tuples in an order that doesn't quite match heap TID
948 order. Delaying deduplication minimizes page level fragmentation.
949
950 Deduplication in unique indexes
951 -------------------------------
952
953 Very often, the number of distinct values that can ever be placed on
954 almost any given leaf page in a unique index is fixed and permanent. For
955 example, a primary key on an identity column will usually only have leaf
956 page splits caused by the insertion of new logical rows within the
957 rightmost leaf page. If there is a split of a non-rightmost leaf page,
958 then the split must have been triggered by inserts associated with UPDATEs
959 of existing logical rows. Splitting a leaf page purely to store multiple
960 versions is a false economy. In effect, we're permanently degrading the
961 index structure just to absorb a temporary burst of duplicates.
962
963 Deduplication in unique indexes helps to prevent these pathological page
964 splits. Storing duplicates in a space efficient manner is not the goal,
965 since in the long run there won't be any duplicates anyway. Rather, we're
966 buying time for standard garbage collection mechanisms to run before a
967 page split is needed.
968
969 Unique index leaf pages only get a deduplication pass when an insertion
970 (that might have to split the page) observed an existing duplicate on the
971 page in passing. This is based on the assumption that deduplication will
972 only work out when _all_ new insertions are duplicates from UPDATEs. This
973 may mean that we miss an opportunity to delay a page split, but that's
974 okay because our ultimate goal is to delay leaf page splits _indefinitely_
975 (i.e. to prevent them altogether). There is little point in trying to
976 delay a split that is probably inevitable anyway. This allows us to avoid
977 the overhead of attempting to deduplicate with unique indexes that always
978 have few or no duplicates.
979
980 Note: Avoiding "unnecessary" page splits driven by version churn is also
981 the goal of bottom-up index deletion, which was added to PostgreSQL 14.
982 Bottom-up index deletion is now the preferred way to deal with this
983 problem (with all kinds of indexes, though especially with unique
984 indexes). Still, deduplication can sometimes augment bottom-up index
985 deletion. When deletion cannot free tuples (due to an old snapshot
986 holding up cleanup), falling back on deduplication provides additional
987 capacity. Delaying the page split by deduplicating can allow a future
988 bottom-up deletion pass of the same page to succeed.
989
990 Posting list splits
991 -------------------
992
993 When the incoming tuple happens to overlap with an existing posting list,
994 a posting list split is performed. Like a page split, a posting list
995 split resolves a situation where a new/incoming item "won't fit", while
996 inserting the incoming item in passing (i.e. as part of the same atomic
997 action). It's possible (though not particularly likely) that an insert of
998 a new item on to an almost-full page will overlap with a posting list,
999 resulting in both a posting list split and a page split. Even then, the
1000 atomic action that splits the posting list also inserts the new item
1001 (since page splits always insert the new item in passing). Including the
1002 posting list split in the same atomic action as the insert avoids problems
1003 caused by concurrent inserts into the same posting list -- the exact
1004 details of how we change the posting list depend upon the new item, and
1005 vice-versa. A single atomic action also minimizes the volume of extra
1006 WAL required for a posting list split, since we don't have to explicitly
1007 WAL-log the original posting list tuple.
1008
1009 Despite piggy-backing on the same atomic action that inserts a new tuple,
1010 posting list splits can be thought of as a separate, extra action to the
1011 insert itself (or to the page split itself). Posting list splits
1012 conceptually "rewrite" an insert that overlaps with an existing posting
1013 list into an insert that adds its final new item just to the right of the
1014 posting list instead. The size of the posting list won't change, and so
1015 page space accounting code does not need to care about posting list splits
1016 at all. This is an important upside of our design; the page split point
1017 choice logic is very subtle even without it needing to deal with posting
1018 list splits.
1019
1020 Only a few isolated extra steps are required to preserve the illusion that
1021 the new item never overlapped with an existing posting list in the first
1022 place: the heap TID of the incoming tuple has its TID replaced with the
1023 rightmost/max heap TID from the existing/originally overlapping posting
1024 list. Similarly, the original incoming item's TID is relocated to the
1025 appropriate offset in the posting list (we usually shift TIDs out of the
1026 way to make a hole for it). Finally, the posting-split-with-page-split
1027 case must generate a new high key based on an imaginary version of the
1028 original page that has both the final new item and the after-list-split
1029 posting tuple (page splits usually just operate against an imaginary
1030 version that contains the new item/item that won't fit).
1031
1032 This approach avoids inventing an "eager" atomic posting split operation
1033 that splits the posting list without simultaneously finishing the insert
1034 of the incoming item. This alternative design might seem cleaner, but it
1035 creates subtle problems for page space accounting. In general, there
1036 might not be enough free space on the page to split a posting list such
1037 that the incoming/new item no longer overlaps with either posting list
1038 half --- the operation could fail before the actual retail insert of the
1039 new item even begins. We'd end up having to handle posting list splits
1040 that need a page split anyway. Besides, supporting variable "split points"
1041 while splitting posting lists won't actually improve overall space
1042 utilization.
1043
1044 Notes About Data Representation
1045 -------------------------------
1046
1047 The right-sibling link required by L&Y is kept in the page "opaque
1048 data" area, as is the left-sibling link, the page level, and some flags.
1049 The page level counts upwards from zero at the leaf level, to the tree
1050 depth minus 1 at the root. (Counting up from the leaves ensures that we
1051 don't need to renumber any existing pages when splitting the root.)
1052
1053 The Postgres disk block data format (an array of items) doesn't fit
1054 Lehman and Yao's alternating-keys-and-pointers notion of a disk page,
1055 so we have to play some games. (The alternating-keys-and-pointers
1056 notion is important for internal page splits, which conceptually split
1057 at the middle of an existing pivot tuple -- the tuple's "separator" key
1058 goes on the left side of the split as the left side's new high key,
1059 while the tuple's pointer/downlink goes on the right side as the
1060 first/minus infinity downlink.)
1061
1062 On a page that is not rightmost in its tree level, the "high key" is
1063 kept in the page's first item, and real data items start at item 2.
1064 The link portion of the "high key" item goes unused. A page that is
1065 rightmost has no "high key" (it's implicitly positive infinity), so
1066 data items start with the first item. Putting the high key at the
1067 left, rather than the right, may seem odd, but it avoids moving the
1068 high key as we add data items.
1069
1070 On a leaf page, the data items are simply links to (TIDs of) tuples
1071 in the relation being indexed, with the associated key values.
1072
1073 On a non-leaf page, the data items are down-links to child pages with
1074 bounding keys. The key in each data item is a strict lower bound for
1075 keys on that child page, so logically the key is to the left of that
1076 downlink. The high key (if present) is the upper bound for the last
1077 downlink. The first data item on each such page has no lower bound
1078 --- or lower bound of minus infinity, if you prefer. The comparison
1079 routines must treat it accordingly. The actual key stored in the
1080 item is irrelevant, and need not be stored at all. This arrangement
1081 corresponds to the fact that an L&Y non-leaf page has one more pointer
1082 than key. Suffix truncation's negative infinity attributes behave in
1083 the same way.