| 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. |