Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * ginbtree.c
4 : : * page utilities routines for the postgres inverted index access method.
5 : : *
6 : : *
7 : : * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
8 : : * Portions Copyright (c) 1994, Regents of the University of California
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/access/gin/ginbtree.c
12 : : *-------------------------------------------------------------------------
13 : : */
14 : :
15 : : #include "postgres.h"
16 : :
17 : : #include "access/gin_private.h"
18 : : #include "access/ginxlog.h"
19 : : #include "access/xloginsert.h"
20 : : #include "miscadmin.h"
21 : : #include "storage/predicate.h"
22 : : #include "utils/injection_point.h"
23 : : #include "utils/memutils.h"
24 : : #include "utils/rel.h"
25 : :
26 : : static void ginFindParents(GinBtree btree, GinBtreeStack *stack);
27 : : static bool ginPlaceToPage(GinBtree btree, GinBtreeStack *stack,
28 : : void *insertdata, BlockNumber updateblkno,
29 : : Buffer childbuf, GinStatsData *buildStats);
30 : : static void ginFinishSplit(GinBtree btree, GinBtreeStack *stack,
31 : : bool freestack, GinStatsData *buildStats);
32 : : static void ginFinishOldSplit(GinBtree btree, GinBtreeStack *stack,
33 : : GinStatsData *buildStats, int access);
34 : :
35 : : /*
36 : : * Lock buffer by needed method for search.
37 : : */
38 : : int
6402 bruce@momjian.us 39 :CBC 811387 : ginTraverseLock(Buffer buffer, bool searchMode)
40 : : {
41 : : Page page;
42 : 811387 : int access = GIN_SHARE;
43 : :
6557 teodor@sigaev.ru 44 : 811387 : LockBuffer(buffer, GIN_SHARE);
2916 kgrittn@postgresql.o 45 : 811387 : page = BufferGetPage(buffer);
6402 bruce@momjian.us 46 [ + + ]: 811387 : if (GinPageIsLeaf(page))
47 : : {
2433 peter_e@gmx.net 48 [ + + ]: 413920 : if (searchMode == false)
49 : : {
50 : : /* we should relock our page */
6557 teodor@sigaev.ru 51 : 410533 : LockBuffer(buffer, GIN_UNLOCK);
52 : 410533 : LockBuffer(buffer, GIN_EXCLUSIVE);
53 : :
54 : : /* But root can become non-leaf during relock */
6402 bruce@momjian.us 55 [ - + ]: 410533 : if (!GinPageIsLeaf(page))
56 : : {
57 : : /* restore old lock type (very rare) */
6557 teodor@sigaev.ru 58 :UBC 0 : LockBuffer(buffer, GIN_UNLOCK);
59 : 0 : LockBuffer(buffer, GIN_SHARE);
60 : : }
61 : : else
6557 teodor@sigaev.ru 62 :CBC 410533 : access = GIN_EXCLUSIVE;
63 : : }
64 : : }
65 : :
66 : 811387 : return access;
67 : : }
68 : :
69 : : /*
70 : : * Descend the tree to the leaf page that contains or would contain the key
71 : : * we're searching for. The key should already be filled in 'btree', in
72 : : * tree-type specific manner. If btree->fullScan is true, descends to the
73 : : * leftmost leaf page.
74 : : *
75 : : * If 'searchmode' is false, on return stack->buffer is exclusively locked,
76 : : * and the stack represents the full path to the root. Otherwise stack->buffer
77 : : * is share-locked, and stack->parent is NULL.
78 : : *
79 : : * If 'rootConflictCheck' is true, tree root is checked for serialization
80 : : * conflict.
81 : : */
82 : : GinBtreeStack *
1935 akorotkov@postgresql 83 : 413922 : ginFindLeafPage(GinBtree btree, bool searchMode,
84 : : bool rootConflictCheck)
85 : : {
86 : : GinBtreeStack *stack;
87 : :
3798 heikki.linnakangas@i 88 : 413922 : stack = (GinBtreeStack *) palloc(sizeof(GinBtreeStack));
3791 89 : 413922 : stack->blkno = btree->rootBlkno;
90 : 413922 : stack->buffer = ReadBuffer(btree->index, btree->rootBlkno);
3798 91 : 413922 : stack->parent = NULL;
92 : 413922 : stack->predictNumber = 1;
93 : :
1935 akorotkov@postgresql 94 [ + + ]: 413922 : if (rootConflictCheck)
1538 tmunro@postgresql.or 95 : 24777 : CheckForSerializableConflictIn(btree->index, NULL, btree->rootBlkno);
96 : :
97 : : for (;;)
6402 bruce@momjian.us 98 : 397467 : {
99 : : Page page;
100 : : BlockNumber child;
101 : : int access;
102 : :
6557 teodor@sigaev.ru 103 : 811387 : stack->off = InvalidOffsetNumber;
104 : :
2916 kgrittn@postgresql.o 105 : 811387 : page = BufferGetPage(stack->buffer);
106 : :
3798 heikki.linnakangas@i 107 : 811387 : access = ginTraverseLock(stack->buffer, searchMode);
108 : :
109 : : /*
110 : : * If we're going to modify the tree, finish any incomplete splits we
111 : : * encounter on the way.
112 : : */
3791 113 [ + + + + ]: 811387 : if (!searchMode && GinPageIsIncompleteSplit(page))
76 heikki.linnakangas@i 114 :GBC 2 : ginFinishOldSplit(btree, stack, NULL, access);
115 : :
116 : : /*
117 : : * ok, page is correctly locked, we should check to move right ..,
118 : : * root never has a right link, so small optimization
119 : : */
2433 peter_e@gmx.net 120 [ + + + + :CBC 1209908 : while (btree->fullScan == false && stack->blkno != btree->rootBlkno &&
+ + ]
4846 tgl@sss.pgh.pa.us 121 : 397975 : btree->isMoveRight(btree, page))
122 : : {
6557 teodor@sigaev.ru 123 :GBC 546 : BlockNumber rightlink = GinPageGetOpaque(page)->rightlink;
124 : :
6402 bruce@momjian.us 125 [ - + ]: 546 : if (rightlink == InvalidBlockNumber)
126 : : /* rightmost page */
6557 teodor@sigaev.ru 127 :UBC 0 : break;
128 : :
3810 heikki.linnakangas@i 129 :GBC 546 : stack->buffer = ginStepRight(stack->buffer, btree->index, access);
6557 teodor@sigaev.ru 130 : 546 : stack->blkno = rightlink;
2916 kgrittn@postgresql.o 131 : 546 : page = BufferGetPage(stack->buffer);
132 : :
3791 heikki.linnakangas@i 133 [ + + - + ]: 546 : if (!searchMode && GinPageIsIncompleteSplit(page))
76 heikki.linnakangas@i 134 :UBC 0 : ginFinishOldSplit(btree, stack, NULL, access);
135 : : }
136 : :
6402 bruce@momjian.us 137 [ + + ]:CBC 811387 : if (GinPageIsLeaf(page)) /* we found, return locked page */
6557 teodor@sigaev.ru 138 : 413920 : return stack;
139 : :
140 : : /* now we have correct buffer, try to find child */
141 : 397467 : child = btree->findChildPage(btree, stack);
142 : :
143 : 397467 : LockBuffer(stack->buffer, GIN_UNLOCK);
6402 bruce@momjian.us 144 [ - + ]: 397467 : Assert(child != InvalidBlockNumber);
145 [ - + ]: 397467 : Assert(stack->blkno != child);
146 : :
3798 heikki.linnakangas@i 147 [ + + ]: 397467 : if (searchMode)
148 : : {
149 : : /* in search mode we may forget path to leaf */
6557 teodor@sigaev.ru 150 : 3397 : stack->blkno = child;
6402 bruce@momjian.us 151 : 3397 : stack->buffer = ReleaseAndReadBuffer(stack->buffer, btree->index, stack->blkno);
152 : : }
153 : : else
154 : : {
155 : 394070 : GinBtreeStack *ptr = (GinBtreeStack *) palloc(sizeof(GinBtreeStack));
156 : :
6557 teodor@sigaev.ru 157 : 394070 : ptr->parent = stack;
158 : 394070 : stack = ptr;
159 : 394070 : stack->blkno = child;
160 : 394070 : stack->buffer = ReadBuffer(btree->index, stack->blkno);
161 : 394070 : stack->predictNumber = 1;
162 : : }
163 : : }
164 : : }
165 : :
166 : : /*
167 : : * Step right from current page.
168 : : *
169 : : * The next page is locked first, before releasing the current page. This is
170 : : * crucial to prevent concurrent VACUUM from deleting a page that we are about
171 : : * to step to. (The lock-coupling isn't strictly necessary when we are
172 : : * traversing the tree to find an insert location, because page deletion grabs
173 : : * a cleanup lock on the root to prevent any concurrent inserts. See Page
174 : : * deletion section in the README. But there's no harm in doing it always.)
175 : : */
176 : : Buffer
3810 heikki.linnakangas@i 177 : 2314 : ginStepRight(Buffer buffer, Relation index, int lockmode)
178 : : {
179 : : Buffer nextbuffer;
2916 kgrittn@postgresql.o 180 : 2314 : Page page = BufferGetPage(buffer);
3810 heikki.linnakangas@i 181 : 2314 : bool isLeaf = GinPageIsLeaf(page);
182 : 2314 : bool isData = GinPageIsData(page);
3791 183 : 2314 : BlockNumber blkno = GinPageGetOpaque(page)->rightlink;
184 : :
3810 185 : 2314 : nextbuffer = ReadBuffer(index, blkno);
186 : 2314 : LockBuffer(nextbuffer, lockmode);
187 : 2314 : UnlockReleaseBuffer(buffer);
188 : :
189 : : /* Sanity check that the page we stepped to is of similar kind. */
2916 kgrittn@postgresql.o 190 : 2314 : page = BufferGetPage(nextbuffer);
3810 heikki.linnakangas@i 191 [ + - - + ]: 2314 : if (isLeaf != GinPageIsLeaf(page) || isData != GinPageIsData(page))
3810 heikki.linnakangas@i 192 [ # # ]:UBC 0 : elog(ERROR, "right sibling of GIN page is of different type");
193 : :
3810 heikki.linnakangas@i 194 :CBC 2314 : return nextbuffer;
195 : : }
196 : :
197 : : void
6402 bruce@momjian.us 198 : 413912 : freeGinBtreeStack(GinBtreeStack *stack)
199 : : {
200 [ + + ]: 1219539 : while (stack)
201 : : {
202 : 805627 : GinBtreeStack *tmp = stack->parent;
203 : :
204 [ + - ]: 805627 : if (stack->buffer != InvalidBuffer)
6557 teodor@sigaev.ru 205 : 805627 : ReleaseBuffer(stack->buffer);
206 : :
6402 bruce@momjian.us 207 : 805627 : pfree(stack);
6557 teodor@sigaev.ru 208 : 805627 : stack = tmp;
209 : : }
210 : 413912 : }
211 : :
212 : : /*
213 : : * Try to find parent for current stack position. Returns correct parent and
214 : : * child's offset in stack->parent. The root page is never released, to
215 : : * prevent conflict with vacuum process.
216 : : */
217 : : static void
3791 heikki.linnakangas@i 218 :UBC 0 : ginFindParents(GinBtree btree, GinBtreeStack *stack)
219 : : {
220 : : Page page;
221 : : Buffer buffer;
222 : : BlockNumber blkno,
223 : : leftmostBlkno;
224 : : OffsetNumber offset;
225 : : GinBtreeStack *root;
226 : : GinBtreeStack *ptr;
227 : :
228 : : /*
229 : : * Unwind the stack all the way up to the root, leaving only the root
230 : : * item.
231 : : *
232 : : * Be careful not to release the pin on the root page! The pin on root
233 : : * page is required to lock out concurrent vacuums on the tree.
234 : : */
235 : 0 : root = stack->parent;
236 [ # # ]: 0 : while (root->parent)
237 : : {
238 : 0 : ReleaseBuffer(root->buffer);
239 : 0 : root = root->parent;
240 : : }
241 : :
242 [ # # ]: 0 : Assert(root->blkno == btree->rootBlkno);
243 [ # # ]: 0 : Assert(BufferGetBlockNumber(root->buffer) == btree->rootBlkno);
6557 teodor@sigaev.ru 244 : 0 : root->off = InvalidOffsetNumber;
245 : :
3791 heikki.linnakangas@i 246 : 0 : blkno = root->blkno;
247 : 0 : buffer = root->buffer;
248 : :
249 : 0 : ptr = (GinBtreeStack *) palloc(sizeof(GinBtreeStack));
250 : :
251 : : for (;;)
252 : : {
6557 teodor@sigaev.ru 253 : 0 : LockBuffer(buffer, GIN_EXCLUSIVE);
2916 kgrittn@postgresql.o 254 : 0 : page = BufferGetPage(buffer);
6402 bruce@momjian.us 255 [ # # ]: 0 : if (GinPageIsLeaf(page))
6557 teodor@sigaev.ru 256 [ # # ]: 0 : elog(ERROR, "Lost path");
257 : :
3791 heikki.linnakangas@i 258 [ # # ]: 0 : if (GinPageIsIncompleteSplit(page))
259 : : {
260 [ # # ]: 0 : Assert(blkno != btree->rootBlkno);
261 : 0 : ptr->blkno = blkno;
262 : 0 : ptr->buffer = buffer;
263 : :
264 : : /*
265 : : * parent may be wrong, but if so, the ginFinishSplit call will
266 : : * recurse to call ginFindParents again to fix it.
267 : : */
268 : 0 : ptr->parent = root;
269 : 0 : ptr->off = InvalidOffsetNumber;
270 : :
76 271 : 0 : ginFinishOldSplit(btree, ptr, NULL, GIN_EXCLUSIVE);
272 : : }
273 : :
3798 274 : 0 : leftmostBlkno = btree->getLeftMostChild(btree, page);
275 : :
6402 bruce@momjian.us 276 [ # # ]: 0 : while ((offset = btree->findChildPtr(btree, page, stack->blkno, InvalidOffsetNumber)) == InvalidOffsetNumber)
277 : : {
6557 teodor@sigaev.ru 278 : 0 : blkno = GinPageGetOpaque(page)->rightlink;
6402 bruce@momjian.us 279 [ # # ]: 0 : if (blkno == InvalidBlockNumber)
280 : : {
281 : : /* Link not present in this level */
153 tgl@sss.pgh.pa.us 282 : 0 : LockBuffer(buffer, GIN_UNLOCK);
283 : : /* Do not release pin on the root buffer */
284 [ # # ]: 0 : if (buffer != root->buffer)
285 : 0 : ReleaseBuffer(buffer);
6557 teodor@sigaev.ru 286 : 0 : break;
287 : : }
3810 heikki.linnakangas@i 288 : 0 : buffer = ginStepRight(buffer, btree->index, GIN_EXCLUSIVE);
2916 kgrittn@postgresql.o 289 : 0 : page = BufferGetPage(buffer);
290 : :
291 : : /* finish any incomplete splits, as above */
3791 heikki.linnakangas@i 292 [ # # ]: 0 : if (GinPageIsIncompleteSplit(page))
293 : : {
294 [ # # ]: 0 : Assert(blkno != btree->rootBlkno);
295 : 0 : ptr->blkno = blkno;
296 : 0 : ptr->buffer = buffer;
297 : 0 : ptr->parent = root;
298 : 0 : ptr->off = InvalidOffsetNumber;
299 : :
76 300 : 0 : ginFinishOldSplit(btree, ptr, NULL, GIN_EXCLUSIVE);
301 : : }
302 : : }
303 : :
6402 bruce@momjian.us 304 [ # # ]: 0 : if (blkno != InvalidBlockNumber)
305 : : {
6557 teodor@sigaev.ru 306 : 0 : ptr->blkno = blkno;
307 : 0 : ptr->buffer = buffer;
3791 heikki.linnakangas@i 308 : 0 : ptr->parent = root; /* it may be wrong, but in next call we will
309 : : * correct */
6533 teodor@sigaev.ru 310 : 0 : ptr->off = offset;
6557 311 : 0 : stack->parent = ptr;
312 : 0 : return;
313 : : }
314 : :
315 : : /* Descend down to next level */
316 : 0 : blkno = leftmostBlkno;
3791 heikki.linnakangas@i 317 : 0 : buffer = ReadBuffer(btree->index, blkno);
318 : : }
319 : : }
320 : :
321 : : /*
322 : : * Insert a new item to a page.
323 : : *
324 : : * Returns true if the insertion was finished. On false, the page was split and
325 : : * the parent needs to be updated. (A root split returns true as it doesn't
326 : : * need any further action by the caller to complete.)
327 : : *
328 : : * When inserting a downlink to an internal page, 'childbuf' contains the
329 : : * child page that was split. Its GIN_INCOMPLETE_SPLIT flag will be cleared
330 : : * atomically with the insert. Also, the existing item at offset stack->off
331 : : * in the target page is updated to point to updateblkno.
332 : : *
333 : : * stack->buffer is locked on entry, and is kept locked.
334 : : * Likewise for childbuf, if given.
335 : : */
336 : : static bool
3791 heikki.linnakangas@i 337 :CBC 388180 : ginPlaceToPage(GinBtree btree, GinBtreeStack *stack,
338 : : void *insertdata, BlockNumber updateblkno,
339 : : Buffer childbuf, GinStatsData *buildStats)
340 : : {
2916 kgrittn@postgresql.o 341 : 388180 : Page page = BufferGetPage(stack->buffer);
342 : : bool result;
343 : : GinPlaceToPageRC rc;
3791 heikki.linnakangas@i 344 : 388180 : uint16 xlflags = 0;
345 : 388180 : Page childpage = NULL;
3631 bruce@momjian.us 346 : 388180 : Page newlpage = NULL,
347 : 388180 : newrpage = NULL;
2916 tgl@sss.pgh.pa.us 348 : 388180 : void *ptp_workspace = NULL;
349 : : MemoryContext tmpCxt;
350 : : MemoryContext oldCxt;
351 : :
352 : : /*
353 : : * We do all the work of this function and its subfunctions in a temporary
354 : : * memory context. This avoids leakages and simplifies APIs, since some
355 : : * subfunctions allocate storage that has to survive until we've finished
356 : : * the WAL insertion.
357 : : */
358 : 388180 : tmpCxt = AllocSetContextCreate(CurrentMemoryContext,
359 : : "ginPlaceToPage temporary context",
360 : : ALLOCSET_DEFAULT_SIZES);
361 : 388180 : oldCxt = MemoryContextSwitchTo(tmpCxt);
362 : :
3791 heikki.linnakangas@i 363 [ + + ]: 388180 : if (GinPageIsData(page))
364 : 24798 : xlflags |= GIN_INSERT_ISDATA;
365 [ + + ]: 388180 : if (GinPageIsLeaf(page))
366 : : {
367 : 385831 : xlflags |= GIN_INSERT_ISLEAF;
368 [ - + ]: 385831 : Assert(!BufferIsValid(childbuf));
369 [ - + ]: 385831 : Assert(updateblkno == InvalidBlockNumber);
370 : : }
371 : : else
372 : : {
373 [ - + ]: 2349 : Assert(BufferIsValid(childbuf));
374 [ - + ]: 2349 : Assert(updateblkno != InvalidBlockNumber);
2916 kgrittn@postgresql.o 375 : 2349 : childpage = BufferGetPage(childbuf);
376 : : }
377 : :
378 : : /*
379 : : * See if the incoming tuple will fit on the page. beginPlaceToPage will
380 : : * decide if the page needs to be split, and will compute the split
381 : : * contents if so. See comments for beginPlaceToPage and execPlaceToPage
382 : : * functions for more details of the API here.
383 : : */
tgl@sss.pgh.pa.us 384 : 388180 : rc = btree->beginPlaceToPage(btree, stack->buffer, stack,
385 : : insertdata, updateblkno,
386 : : &ptp_workspace,
387 : : &newlpage, &newrpage);
388 : :
389 [ - + ]: 388180 : if (rc == GPTP_NO_WORK)
390 : : {
391 : : /* Nothing to do */
2916 tgl@sss.pgh.pa.us 392 :UBC 0 : result = true;
393 : : }
2916 tgl@sss.pgh.pa.us 394 [ + + ]:CBC 388180 : else if (rc == GPTP_INSERT)
395 : : {
396 : : /* It will fit, perform the insertion */
397 : 385717 : START_CRIT_SECTION();
398 : :
1838 heikki.linnakangas@i 399 [ + + + + : 385717 : if (RelationNeedsWAL(btree->index) && !btree->isBuild)
+ + + - +
+ ]
2916 tgl@sss.pgh.pa.us 400 : 191169 : XLogBeginInsert();
401 : :
402 : : /*
403 : : * Perform the page update, dirty and register stack->buffer, and
404 : : * register any extra WAL data.
405 : : */
406 : 385717 : btree->execPlaceToPage(btree, stack->buffer, stack,
407 : : insertdata, updateblkno, ptp_workspace);
408 : :
409 : : /* An insert to an internal page finishes the split of the child. */
410 [ + + ]: 385717 : if (BufferIsValid(childbuf))
411 : : {
3791 heikki.linnakangas@i 412 : 2347 : GinPageGetOpaque(childpage)->flags &= ~GIN_INCOMPLETE_SPLIT;
413 : 2347 : MarkBufferDirty(childbuf);
174 jdavis@postgresql.or 414 [ + + + + :GNC 2347 : if (RelationNeedsWAL(btree->index) && !btree->isBuild)
+ + + - +
+ ]
415 : 1027 : XLogRegisterBuffer(1, childbuf, REGBUF_STANDARD);
416 : : }
417 : :
1838 heikki.linnakangas@i 418 [ + + + + :CBC 385717 : if (RelationNeedsWAL(btree->index) && !btree->isBuild)
+ + + - +
+ ]
419 : : {
420 : : XLogRecPtr recptr;
421 : : ginxlogInsert xlrec;
422 : : BlockIdData childblknos[2];
423 : :
3791 424 : 191169 : xlrec.flags = xlflags;
425 : :
3433 426 : 191169 : XLogRegisterData((char *) &xlrec, sizeof(ginxlogInsert));
427 : :
428 : : /*
429 : : * Log information about child if this was an insertion of a
430 : : * downlink.
431 : : */
2916 tgl@sss.pgh.pa.us 432 [ + + ]: 191169 : if (BufferIsValid(childbuf))
433 : : {
3791 heikki.linnakangas@i 434 : 1027 : BlockIdSet(&childblknos[0], BufferGetBlockNumber(childbuf));
435 : 1027 : BlockIdSet(&childblknos[1], GinPageGetOpaque(childpage)->rightlink);
3433 436 : 1027 : XLogRegisterData((char *) childblknos,
437 : : sizeof(BlockIdData) * 2);
438 : : }
439 : :
440 : 191169 : recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_INSERT);
3798 441 : 191169 : PageSetLSN(page, recptr);
2916 tgl@sss.pgh.pa.us 442 [ + + ]: 191169 : if (BufferIsValid(childbuf))
3791 heikki.linnakangas@i 443 : 1027 : PageSetLSN(childpage, recptr);
444 : : }
445 : :
3798 446 [ - + ]: 385717 : END_CRIT_SECTION();
447 : :
448 : : /* Insertion is complete. */
2916 tgl@sss.pgh.pa.us 449 : 385717 : result = true;
450 : : }
451 [ + - ]: 2463 : else if (rc == GPTP_SPLIT)
452 : : {
453 : : /*
454 : : * Didn't fit, need to split. The split has been computed in newlpage
455 : : * and newrpage, which are pointers to palloc'd pages, not associated
456 : : * with buffers. stack->buffer is not touched yet.
457 : : */
458 : : Buffer rbuffer;
459 : : BlockNumber savedRightLink;
460 : : ginxlogSplit data;
3791 heikki.linnakangas@i 461 : 2463 : Buffer lbuffer = InvalidBuffer;
462 : 2463 : Page newrootpg = NULL;
463 : :
464 : : /* Get a new index page to become the right page */
3798 465 : 2463 : rbuffer = GinNewBuffer(btree->index);
466 : :
467 : : /* During index build, count the new page */
468 [ + + ]: 2463 : if (buildStats)
469 : : {
470 [ + + ]: 551 : if (btree->isData)
471 : 46 : buildStats->nDataPages++;
472 : : else
473 : 505 : buildStats->nEntryPages++;
474 : : }
475 : :
3791 476 : 2463 : savedRightLink = GinPageGetOpaque(page)->rightlink;
477 : :
478 : : /* Begin setting up WAL record */
648 rhaas@postgresql.org 479 : 2463 : data.locator = btree->index->rd_locator;
3791 heikki.linnakangas@i 480 : 2463 : data.flags = xlflags;
2916 tgl@sss.pgh.pa.us 481 [ + + ]: 2463 : if (BufferIsValid(childbuf))
482 : : {
3791 heikki.linnakangas@i 483 :GBC 2 : data.leftChildBlkno = BufferGetBlockNumber(childbuf);
484 : 2 : data.rightChildBlkno = GinPageGetOpaque(childpage)->rightlink;
485 : : }
486 : : else
3791 heikki.linnakangas@i 487 :CBC 2461 : data.leftChildBlkno = data.rightChildBlkno = InvalidBlockNumber;
488 : :
489 [ + + ]: 2463 : if (stack->parent == NULL)
490 : : {
491 : : /*
492 : : * splitting the root, so we need to allocate new left page and
493 : : * place pointers to left and right page on root page.
494 : : */
495 : 114 : lbuffer = GinNewBuffer(btree->index);
496 : :
497 : : /* During index build, count the new left page */
498 [ + + ]: 114 : if (buildStats)
499 : : {
500 [ + + ]: 92 : if (btree->isData)
501 : 38 : buildStats->nDataPages++;
502 : : else
503 : 54 : buildStats->nEntryPages++;
504 : : }
505 : :
3433 506 : 114 : data.rrlink = InvalidBlockNumber;
3791 507 : 114 : data.flags |= GIN_SPLIT_ROOT;
508 : :
3735 509 : 114 : GinPageGetOpaque(newrpage)->rightlink = InvalidBlockNumber;
3798 510 : 114 : GinPageGetOpaque(newlpage)->rightlink = BufferGetBlockNumber(rbuffer);
511 : :
512 : : /*
513 : : * Construct a new root page containing downlinks to the new left
514 : : * and right pages. (Do this in a temporary copy rather than
515 : : * overwriting the original page directly, since we're not in the
516 : : * critical section yet.)
517 : : */
3735 518 : 114 : newrootpg = PageGetTempPage(newrpage);
519 : 114 : GinInitPage(newrootpg, GinPageGetOpaque(newlpage)->flags & ~(GIN_LEAF | GIN_COMPRESSED), BLCKSZ);
520 : :
3791 521 : 114 : btree->fillRoot(btree, newrootpg,
522 : : BufferGetBlockNumber(lbuffer), newlpage,
523 : : BufferGetBlockNumber(rbuffer), newrpage);
524 : :
2207 teodor@sigaev.ru 525 [ + + ]: 114 : if (GinPageIsLeaf(BufferGetPage(stack->buffer)))
526 : : {
527 : :
528 : 113 : PredicateLockPageSplit(btree->index,
529 : : BufferGetBlockNumber(stack->buffer),
530 : : BufferGetBlockNumber(lbuffer));
531 : :
532 : 113 : PredicateLockPageSplit(btree->index,
533 : : BufferGetBlockNumber(stack->buffer),
534 : : BufferGetBlockNumber(rbuffer));
535 : : }
536 : : }
537 : : else
538 : : {
539 : : /* splitting a non-root page */
3791 heikki.linnakangas@i 540 : 2349 : data.rrlink = savedRightLink;
541 : :
3735 542 : 2349 : GinPageGetOpaque(newrpage)->rightlink = savedRightLink;
3791 543 : 2349 : GinPageGetOpaque(newlpage)->flags |= GIN_INCOMPLETE_SPLIT;
3798 544 : 2349 : GinPageGetOpaque(newlpage)->rightlink = BufferGetBlockNumber(rbuffer);
545 : :
2207 teodor@sigaev.ru 546 [ + + ]: 2349 : if (GinPageIsLeaf(BufferGetPage(stack->buffer)))
547 : : {
548 : :
549 : 2348 : PredicateLockPageSplit(btree->index,
550 : : BufferGetBlockNumber(stack->buffer),
551 : : BufferGetBlockNumber(rbuffer));
552 : : }
553 : : }
554 : :
555 : : /*
556 : : * OK, we have the new contents of the left page in a temporary copy
557 : : * now (newlpage), and likewise for the new contents of the
558 : : * newly-allocated right block. The original page is still unchanged.
559 : : *
560 : : * If this is a root split, we also have a temporary page containing
561 : : * the new contents of the root.
562 : : */
563 : :
3791 heikki.linnakangas@i 564 : 2463 : START_CRIT_SECTION();
565 : :
566 : 2463 : MarkBufferDirty(rbuffer);
3735 567 : 2463 : MarkBufferDirty(stack->buffer);
568 : :
569 : : /*
570 : : * Restore the temporary copies over the real buffers.
571 : : */
3791 572 [ + + ]: 2463 : if (stack->parent == NULL)
573 : : {
574 : : /* Splitting the root, three pages to update */
575 : 114 : MarkBufferDirty(lbuffer);
2916 tgl@sss.pgh.pa.us 576 : 114 : memcpy(page, newrootpg, BLCKSZ);
kgrittn@postgresql.o 577 : 114 : memcpy(BufferGetPage(lbuffer), newlpage, BLCKSZ);
578 : 114 : memcpy(BufferGetPage(rbuffer), newrpage, BLCKSZ);
579 : : }
580 : : else
581 : : {
582 : : /* Normal split, only two pages to update */
tgl@sss.pgh.pa.us 583 : 2349 : memcpy(page, newlpage, BLCKSZ);
kgrittn@postgresql.o 584 : 2349 : memcpy(BufferGetPage(rbuffer), newrpage, BLCKSZ);
585 : : }
586 : :
587 : : /* We also clear childbuf's INCOMPLETE_SPLIT flag, if passed */
tgl@sss.pgh.pa.us 588 [ + + ]: 2463 : if (BufferIsValid(childbuf))
589 : : {
2916 tgl@sss.pgh.pa.us 590 :GBC 2 : GinPageGetOpaque(childpage)->flags &= ~GIN_INCOMPLETE_SPLIT;
591 : 2 : MarkBufferDirty(childbuf);
592 : : }
593 : :
594 : : /* write WAL record */
1838 heikki.linnakangas@i 595 [ + + + + :CBC 2463 : if (RelationNeedsWAL(btree->index) && !btree->isBuild)
+ + + - +
+ ]
596 : : {
597 : : XLogRecPtr recptr;
598 : :
3213 599 : 1042 : XLogBeginInsert();
600 : :
601 : : /*
602 : : * We just take full page images of all the split pages. Splits
603 : : * are uncommon enough that it's not worth complicating the code
604 : : * to be more efficient.
605 : : */
3433 606 [ + + ]: 1042 : if (stack->parent == NULL)
607 : : {
608 : 13 : XLogRegisterBuffer(0, lbuffer, REGBUF_FORCE_IMAGE | REGBUF_STANDARD);
609 : 13 : XLogRegisterBuffer(1, rbuffer, REGBUF_FORCE_IMAGE | REGBUF_STANDARD);
610 : 13 : XLogRegisterBuffer(2, stack->buffer, REGBUF_FORCE_IMAGE | REGBUF_STANDARD);
611 : : }
612 : : else
613 : : {
614 : 1029 : XLogRegisterBuffer(0, stack->buffer, REGBUF_FORCE_IMAGE | REGBUF_STANDARD);
615 : 1029 : XLogRegisterBuffer(1, rbuffer, REGBUF_FORCE_IMAGE | REGBUF_STANDARD);
616 : : }
617 [ + + ]: 1042 : if (BufferIsValid(childbuf))
2916 tgl@sss.pgh.pa.us 618 :GBC 2 : XLogRegisterBuffer(3, childbuf, REGBUF_STANDARD);
619 : :
3433 heikki.linnakangas@i 620 :CBC 1042 : XLogRegisterData((char *) &data, sizeof(ginxlogSplit));
621 : :
622 : 1042 : recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_SPLIT);
623 : :
2916 tgl@sss.pgh.pa.us 624 : 1042 : PageSetLSN(page, recptr);
kgrittn@postgresql.o 625 : 1042 : PageSetLSN(BufferGetPage(rbuffer), recptr);
3791 heikki.linnakangas@i 626 [ + + ]: 1042 : if (stack->parent == NULL)
2916 kgrittn@postgresql.o 627 : 13 : PageSetLSN(BufferGetPage(lbuffer), recptr);
3666 heikki.linnakangas@i 628 [ + + ]: 1042 : if (BufferIsValid(childbuf))
3666 heikki.linnakangas@i 629 :GBC 2 : PageSetLSN(childpage, recptr);
630 : : }
3791 heikki.linnakangas@i 631 [ - + ]:CBC 2463 : END_CRIT_SECTION();
632 : :
633 : : /*
634 : : * We can release the locks/pins on the new pages now, but keep
635 : : * stack->buffer locked. childbuf doesn't get unlocked either.
636 : : */
637 : 2463 : UnlockReleaseBuffer(rbuffer);
638 [ + + ]: 2463 : if (stack->parent == NULL)
639 : 114 : UnlockReleaseBuffer(lbuffer);
640 : :
641 : : /*
642 : : * If we split the root, we're done. Otherwise the split is not
643 : : * complete until the downlink for the new page has been inserted to
644 : : * the parent.
645 : : */
2916 tgl@sss.pgh.pa.us 646 : 2463 : result = (stack->parent == NULL);
647 : : }
648 : : else
649 : : {
1714 michael@paquier.xyz 650 [ # # ]:UBC 0 : elog(ERROR, "invalid return code from GIN beginPlaceToPage method: %d", rc);
651 : : result = false; /* keep compiler quiet */
652 : : }
653 : :
654 : : /* Clean up temp context */
2916 tgl@sss.pgh.pa.us 655 :CBC 388180 : MemoryContextSwitchTo(oldCxt);
656 : 388180 : MemoryContextDelete(tmpCxt);
657 : :
658 : 388180 : return result;
659 : : }
660 : :
661 : : /*
662 : : * Finish a split by inserting the downlink for the new page to parent.
663 : : *
664 : : * On entry, stack->buffer is exclusively locked.
665 : : *
666 : : * If freestack is true, all the buffers are released and unlocked as we
667 : : * crawl up the tree, and 'stack' is freed. Otherwise stack->buffer is kept
668 : : * locked, and stack is unmodified, except for possibly moving right to find
669 : : * the correct parent of page.
670 : : */
671 : : static void
3791 heikki.linnakangas@i 672 : 2350 : ginFinishSplit(GinBtree btree, GinBtreeStack *stack, bool freestack,
673 : : GinStatsData *buildStats)
674 : : {
675 : : Page page;
676 : : bool done;
677 : 2350 : bool first = true;
678 : :
679 : : /* this loop crawls up the stack until the insertion is complete */
680 : : do
681 : : {
682 : 2351 : GinBtreeStack *parent = stack->parent;
683 : : void *insertdata;
684 : : BlockNumber updateblkno;
685 : :
686 : : #ifdef USE_INJECTION_POINTS
76 heikki.linnakangas@i 687 [ + + ]:GNC 2351 : if (GinPageIsLeaf(BufferGetPage(stack->buffer)))
688 : 2349 : INJECTION_POINT("gin-leave-leaf-split-incomplete");
689 : : else
690 : 2 : INJECTION_POINT("gin-leave-internal-split-incomplete");
691 : : #endif
692 : :
693 : : /* search parent to lock */
6557 teodor@sigaev.ru 694 :CBC 2349 : LockBuffer(parent->buffer, GIN_EXCLUSIVE);
695 : :
696 : : /*
697 : : * If the parent page was incompletely split, finish that split first,
698 : : * then continue with the current one.
699 : : *
700 : : * Note: we have to finish *all* incomplete splits we encounter, even
701 : : * if we have to move right. Otherwise we might choose as the target a
702 : : * page that has no downlink in the parent, and splitting it further
703 : : * would fail.
704 : : */
2916 kgrittn@postgresql.o 705 [ - + ]: 2349 : if (GinPageIsIncompleteSplit(BufferGetPage(parent->buffer)))
76 heikki.linnakangas@i 706 :UBC 0 : ginFinishOldSplit(btree, parent, buildStats, GIN_EXCLUSIVE);
707 : :
708 : : /* move right if it's needed */
2916 kgrittn@postgresql.o 709 :CBC 2349 : page = BufferGetPage(parent->buffer);
6402 bruce@momjian.us 710 [ - + ]: 2349 : while ((parent->off = btree->findChildPtr(btree, page, stack->blkno, parent->off)) == InvalidOffsetNumber)
711 : : {
3791 heikki.linnakangas@i 712 [ # # ]:UBC 0 : if (GinPageRightMost(page))
713 : : {
714 : : /*
715 : : * rightmost page, but we don't find parent, we should use
716 : : * plain search...
717 : : */
3810 718 : 0 : LockBuffer(parent->buffer, GIN_UNLOCK);
3791 719 : 0 : ginFindParents(btree, stack);
6402 bruce@momjian.us 720 : 0 : parent = stack->parent;
4293 tgl@sss.pgh.pa.us 721 [ # # ]: 0 : Assert(parent != NULL);
6557 teodor@sigaev.ru 722 : 0 : break;
723 : : }
724 : :
3810 heikki.linnakangas@i 725 : 0 : parent->buffer = ginStepRight(parent->buffer, btree->index, GIN_EXCLUSIVE);
3791 726 : 0 : parent->blkno = BufferGetBlockNumber(parent->buffer);
2916 kgrittn@postgresql.o 727 : 0 : page = BufferGetPage(parent->buffer);
728 : :
729 [ # # ]: 0 : if (GinPageIsIncompleteSplit(BufferGetPage(parent->buffer)))
76 heikki.linnakangas@i 730 : 0 : ginFinishOldSplit(btree, parent, buildStats, GIN_EXCLUSIVE);
731 : : }
732 : :
733 : : /* insert the downlink */
3791 heikki.linnakangas@i 734 :CBC 2349 : insertdata = btree->prepareDownlink(btree, stack->buffer);
2916 kgrittn@postgresql.o 735 : 2349 : updateblkno = GinPageGetOpaque(BufferGetPage(stack->buffer))->rightlink;
3791 heikki.linnakangas@i 736 : 2349 : done = ginPlaceToPage(btree, parent,
737 : : insertdata, updateblkno,
738 : : stack->buffer, buildStats);
739 : 2349 : pfree(insertdata);
740 : :
741 : : /*
742 : : * If the caller requested to free the stack, unlock and release the
743 : : * child buffer now. Otherwise keep it pinned and locked, but if we
744 : : * have to recurse up the tree, we can unlock the upper pages, only
745 : : * keeping the page at the bottom of the stack locked.
746 : : */
747 [ + - + + ]: 2349 : if (!first || freestack)
748 : 2347 : LockBuffer(stack->buffer, GIN_UNLOCK);
749 [ + + ]: 2349 : if (freestack)
750 : : {
751 : 2347 : ReleaseBuffer(stack->buffer);
752 : 2347 : pfree(stack);
753 : : }
754 : 2349 : stack = parent;
755 : :
756 : 2349 : first = false;
757 [ + + ]: 2349 : } while (!done);
758 : :
759 : : /* unlock the parent */
760 : 2348 : LockBuffer(stack->buffer, GIN_UNLOCK);
761 : :
762 [ + + ]: 2348 : if (freestack)
763 : 2346 : freeGinBtreeStack(stack);
764 : 2348 : }
765 : :
766 : : /*
767 : : * An entry point to ginFinishSplit() that is used when we stumble upon an
768 : : * existing incompletely split page in the tree, as opposed to completing a
769 : : * split that we just made outselves. The difference is that stack->buffer may
770 : : * be merely share-locked on entry, and will be upgraded to exclusive mode.
771 : : *
772 : : * Note: Upgrading the lock momentarily releases it. Doing that in a scan
773 : : * would not be OK, because a concurrent VACUUM might delete the page while
774 : : * we're not holding the lock. It's OK in an insert, though, because VACUUM
775 : : * has a different mechanism that prevents it from running concurrently with
776 : : * inserts. (Namely, it holds a cleanup lock on the root.)
777 : : */
778 : : static void
76 heikki.linnakangas@i 779 :GBC 2 : ginFinishOldSplit(GinBtree btree, GinBtreeStack *stack, GinStatsData *buildStats, int access)
780 : : {
76 heikki.linnakangas@i 781 :GNC 2 : INJECTION_POINT("gin-finish-incomplete-split");
76 heikki.linnakangas@i 782 [ - + ]:GBC 2 : elog(DEBUG1, "finishing incomplete split of block %u in gin index \"%s\"",
783 : : stack->blkno, RelationGetRelationName(btree->index));
784 : :
785 [ + + ]: 2 : if (access == GIN_SHARE)
786 : : {
787 : 1 : LockBuffer(stack->buffer, GIN_UNLOCK);
788 : 1 : LockBuffer(stack->buffer, GIN_EXCLUSIVE);
789 : :
790 [ - + ]: 1 : if (!GinPageIsIncompleteSplit(BufferGetPage(stack->buffer)))
791 : : {
792 : : /*
793 : : * Someone else already completed the split while we were not
794 : : * holding the lock.
795 : : */
76 heikki.linnakangas@i 796 :UBC 0 : return;
797 : : }
798 : : }
799 : :
76 heikki.linnakangas@i 800 :GBC 2 : ginFinishSplit(btree, stack, false, buildStats);
801 : : }
802 : :
803 : : /*
804 : : * Insert a value to tree described by stack.
805 : : *
806 : : * The value to be inserted is given in 'insertdata'. Its format depends
807 : : * on whether this is an entry or data tree, ginInsertValue just passes it
808 : : * through to the tree-specific callback function.
809 : : *
810 : : * During an index build, buildStats is non-null and the counters it contains
811 : : * are incremented as needed.
812 : : *
813 : : * NB: the passed-in stack is freed, as though by freeGinBtreeStack.
814 : : */
815 : : void
3791 heikki.linnakangas@i 816 :CBC 385831 : ginInsertValue(GinBtree btree, GinBtreeStack *stack, void *insertdata,
817 : : GinStatsData *buildStats)
818 : : {
819 : : bool done;
820 : :
821 : : /* If the leaf page was incompletely split, finish the split first */
2916 kgrittn@postgresql.o 822 [ - + ]: 385831 : if (GinPageIsIncompleteSplit(BufferGetPage(stack->buffer)))
76 heikki.linnakangas@i 823 :UBC 0 : ginFinishOldSplit(btree, stack, buildStats, GIN_EXCLUSIVE);
824 : :
3791 heikki.linnakangas@i 825 :CBC 385831 : done = ginPlaceToPage(btree, stack,
826 : : insertdata, InvalidBlockNumber,
827 : : InvalidBuffer, buildStats);
828 [ + + ]: 385831 : if (done)
829 : : {
830 : 383483 : LockBuffer(stack->buffer, GIN_UNLOCK);
831 : 383483 : freeGinBtreeStack(stack);
832 : : }
833 : : else
834 : 2348 : ginFinishSplit(btree, stack, true, buildStats);
6557 teodor@sigaev.ru 835 : 385829 : }
|
