Age Owner TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * ginentrypage.c
4 : * routines for handling GIN entry tree pages.
5 : *
6 : *
7 : * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
8 : * Portions Copyright (c) 1994, Regents of the University of California
9 : *
10 : * IDENTIFICATION
11 : * src/backend/access/gin/ginentrypage.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 "utils/rel.h"
22 :
23 : static void entrySplitPage(GinBtree btree, Buffer origbuf,
24 : GinBtreeStack *stack,
25 : GinBtreeEntryInsertData *insertData,
26 : BlockNumber updateblkno,
27 : Page *newlpage, Page *newrpage);
28 :
29 : /*
30 : * Form a tuple for entry tree.
31 : *
32 : * If the tuple would be too big to be stored, function throws a suitable
33 : * error if errorTooBig is true, or returns NULL if errorTooBig is false.
34 : *
35 : * See src/backend/access/gin/README for a description of the index tuple
36 : * format that is being built here. We build on the assumption that we
37 : * are making a leaf-level key entry containing a posting list of nipd items.
38 : * If the caller is actually trying to make a posting-tree entry, non-leaf
39 : * entry, or pending-list entry, it should pass dataSize = 0 and then overwrite
40 : * the t_tid fields as necessary. In any case, 'data' can be NULL to skip
41 : * filling in the posting list; the caller is responsible for filling it
42 : * afterwards if data = NULL and nipd > 0.
43 : */
44 : IndexTuple
4475 tgl 45 CBC 966547 : GinFormTuple(GinState *ginstate,
46 : OffsetNumber attnum, Datum key, GinNullCategory category,
47 : Pointer data, Size dataSize, int nipd,
48 : bool errorTooBig)
49 : {
50 : Datum datums[2];
51 : bool isnull[2];
52 : IndexTuple itup;
53 : uint32 newsize;
54 :
55 : /* Build the basic tuple: optional column number, plus key datum */
5050 bruce 56 966547 : if (ginstate->oneCol)
57 : {
4475 tgl 58 365614 : datums[0] = key;
59 365614 : isnull[0] = (category != GIN_CAT_NORM_KEY);
60 : }
61 : else
62 : {
5385 63 600933 : datums[0] = UInt16GetDatum(attnum);
4475 64 600933 : isnull[0] = false;
5385 65 600933 : datums[1] = key;
4475 66 600933 : isnull[1] = (category != GIN_CAT_NORM_KEY);
67 : }
68 :
69 966547 : itup = index_form_tuple(ginstate->tupdesc[attnum - 1], datums, isnull);
70 :
71 : /*
72 : * Determine and store offset to the posting list, making sure there is
73 : * room for the category byte if needed.
74 : *
75 : * Note: because index_form_tuple MAXALIGNs the tuple size, there may well
76 : * be some wasted pad space. Is it worth recomputing the data length to
77 : * prevent that? That would also allow us to Assert that the real data
78 : * doesn't overlap the GinNullCategory byte, which this code currently
79 : * takes on faith.
80 : */
81 966547 : newsize = IndexTupleSize(itup);
82 :
83 966547 : if (IndexTupleHasNulls(itup))
84 : {
85 : uint32 minsize;
86 :
87 118 : Assert(category != GIN_CAT_NORM_KEY);
88 118 : minsize = GinCategoryOffset(itup, ginstate) + sizeof(GinNullCategory);
89 118 : newsize = Max(newsize, minsize);
90 : }
91 :
3363 heikki.linnakangas 92 966547 : newsize = SHORTALIGN(newsize);
93 :
4475 tgl 94 966547 : GinSetPostingOffset(itup, newsize);
95 966547 : GinSetNPosting(itup, nipd);
96 :
97 : /*
98 : * Add space needed for posting list, if any. Then check that the tuple
99 : * won't be too big to store.
100 : */
3364 heikki.linnakangas 101 966547 : newsize += dataSize;
102 :
4475 tgl 103 966547 : newsize = MAXALIGN(newsize);
104 :
3364 heikki.linnakangas 105 966547 : if (newsize > GinMaxItemSize)
106 : {
4475 tgl 107 58 : if (errorTooBig)
4475 tgl 108 UBC 0 : ereport(ERROR,
109 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
110 : errmsg("index row size %zu exceeds maximum %zu for index \"%s\"",
111 : (Size) newsize, (Size) GinMaxItemSize,
112 : RelationGetRelationName(ginstate->index))));
4475 tgl 113 CBC 58 : pfree(itup);
114 58 : return NULL;
115 : }
116 :
117 : /*
118 : * Resize tuple if needed
119 : */
120 966489 : if (newsize != IndexTupleSize(itup))
121 : {
6031 bruce 122 270884 : itup = repalloc(itup, newsize);
123 :
124 : /*
125 : * PostgreSQL 9.3 and earlier did not clear this new space, so we
126 : * might find uninitialized padding when reading tuples from disk.
127 : */
3574 noah 128 270884 : memset((char *) itup + IndexTupleSize(itup),
129 270884 : 0, newsize - IndexTupleSize(itup));
130 : /* set new size in tuple header */
6031 bruce 131 270884 : itup->t_info &= ~INDEX_SIZE_MASK;
6186 teodor 132 270884 : itup->t_info |= newsize;
133 : }
134 :
135 : /*
136 : * Copy in the posting list, if provided
137 : */
3364 heikki.linnakangas 138 966489 : if (data)
139 : {
3260 bruce 140 270881 : char *ptr = GinGetPosting(itup);
141 :
3364 heikki.linnakangas 142 270881 : memcpy(ptr, data, dataSize);
143 : }
144 :
145 : /*
146 : * Insert category byte, if needed
147 : */
4475 tgl 148 966489 : if (category != GIN_CAT_NORM_KEY)
149 : {
150 118 : Assert(IndexTupleHasNulls(itup));
151 118 : GinSetNullCategory(itup, ginstate, category);
152 : }
6186 teodor 153 966489 : return itup;
154 : }
155 :
156 : /*
157 : * Read item pointers from leaf entry tuple.
158 : *
159 : * Returns a palloc'd array of ItemPointers. The number of items is returned
160 : * in *nitems.
161 : */
162 : ItemPointer
3364 heikki.linnakangas 163 220875 : ginReadTuple(GinState *ginstate, OffsetNumber attnum, IndexTuple itup,
164 : int *nitems)
165 : {
166 220875 : Pointer ptr = GinGetPosting(itup);
167 220875 : int nipd = GinGetNPosting(itup);
168 : ItemPointer ipd;
169 : int ndecoded;
170 :
171 220875 : if (GinItupIsCompressed(itup))
172 : {
173 220875 : if (nipd > 0)
174 : {
175 160878 : ipd = ginPostingListDecode((GinPostingList *) ptr, &ndecoded);
176 160878 : if (nipd != ndecoded)
3364 heikki.linnakangas 177 UBC 0 : elog(ERROR, "number of items mismatch in GIN entry tuple, %d in tuple header, %d decoded",
178 : nipd, ndecoded);
179 : }
180 : else
181 : {
3364 heikki.linnakangas 182 CBC 59997 : ipd = palloc(0);
183 : }
184 : }
185 : else
186 : {
3364 heikki.linnakangas 187 UBC 0 : ipd = (ItemPointer) palloc(sizeof(ItemPointerData) * nipd);
188 0 : memcpy(ipd, ptr, sizeof(ItemPointerData) * nipd);
189 : }
3364 heikki.linnakangas 190 CBC 220875 : *nitems = nipd;
191 220875 : return ipd;
192 : }
193 :
194 : /*
195 : * Form a non-leaf entry tuple by copying the key data from the given tuple,
196 : * which can be either a leaf or non-leaf entry tuple.
197 : *
198 : * Any posting list in the source tuple is not copied. The specified child
199 : * block number is inserted into t_tid.
200 : */
201 : static IndexTuple
4475 tgl 202 1834 : GinFormInteriorTuple(IndexTuple itup, Page page, BlockNumber childblk)
203 : {
204 : IndexTuple nitup;
205 :
206 1834 : if (GinPageIsLeaf(page) && !GinIsPostingTree(itup))
207 1834 : {
208 : /* Tuple contains a posting list, just copy stuff before that */
209 1834 : uint32 origsize = GinGetPostingOffset(itup);
210 :
211 1834 : origsize = MAXALIGN(origsize);
212 1834 : nitup = (IndexTuple) palloc(origsize);
213 1834 : memcpy(nitup, itup, origsize);
214 : /* ... be sure to fix the size header field ... */
215 1834 : nitup->t_info &= ~INDEX_SIZE_MASK;
216 1834 : nitup->t_info |= origsize;
217 : }
218 : else
219 : {
220 : /* Copy the tuple as-is */
4475 tgl 221 UBC 0 : nitup = (IndexTuple) palloc(IndexTupleSize(itup));
222 0 : memcpy(nitup, itup, IndexTupleSize(itup));
223 : }
224 :
225 : /* Now insert the correct downlink */
4475 tgl 226 CBC 1834 : GinSetDownlink(nitup, childblk);
227 :
228 1834 : return nitup;
229 : }
230 :
231 : /*
232 : * Entry tree is a "static", ie tuple never deletes from it,
233 : * so we don't use right bound, we use rightmost key instead.
234 : */
235 : static IndexTuple
6031 bruce 236 23701 : getRightMostTuple(Page page)
237 : {
6186 teodor 238 23701 : OffsetNumber maxoff = PageGetMaxOffsetNumber(page);
239 :
240 23701 : return (IndexTuple) PageGetItem(page, PageGetItemId(page, maxoff));
241 : }
242 :
243 : static bool
6031 bruce 244 262038 : entryIsMoveRight(GinBtree btree, Page page)
245 : {
246 : IndexTuple itup;
247 : OffsetNumber attnum;
248 : Datum key;
249 : GinNullCategory category;
250 :
251 262038 : if (GinPageRightMost(page))
2062 peter_e 252 240171 : return false;
253 :
5050 bruce 254 21867 : itup = getRightMostTuple(page);
4475 tgl 255 21867 : attnum = gintuple_get_attrnum(btree->ginstate, itup);
256 21867 : key = gintuple_get_key(btree->ginstate, itup, &category);
257 :
4557 258 21867 : if (ginCompareAttEntries(btree->ginstate,
2118 259 21867 : btree->entryAttnum, btree->entryKey, btree->entryCategory,
260 : attnum, key, category) > 0)
2062 peter_e 261 UBC 0 : return true;
262 :
2062 peter_e 263 CBC 21867 : return false;
264 : }
265 :
266 : /*
267 : * Find correct tuple in non-leaf page. It supposed that
268 : * page correctly chosen and searching value SHOULD be on page
269 : */
270 : static BlockNumber
6031 bruce 271 262038 : entryLocateEntry(GinBtree btree, GinBtreeStack *stack)
272 : {
273 : OffsetNumber low,
274 : high,
275 : maxoff;
276 262038 : IndexTuple itup = NULL;
277 : int result;
2545 kgrittn 278 262038 : Page page = BufferGetPage(stack->buffer);
279 :
6031 bruce 280 262038 : Assert(!GinPageIsLeaf(page));
281 262038 : Assert(!GinPageIsData(page));
282 :
283 262038 : if (btree->fullScan)
284 : {
6186 teodor 285 UBC 0 : stack->off = FirstOffsetNumber;
286 0 : stack->predictNumber *= PageGetMaxOffsetNumber(page);
3427 heikki.linnakangas 287 0 : return btree->getLeftMostChild(btree, page);
288 : }
289 :
6186 teodor 290 CBC 262038 : low = FirstOffsetNumber;
291 262038 : maxoff = high = PageGetMaxOffsetNumber(page);
6031 bruce 292 262038 : Assert(high >= low);
293 :
6186 teodor 294 262038 : high++;
295 :
6031 bruce 296 1808328 : while (high > low)
297 : {
6186 teodor 298 1546382 : OffsetNumber mid = low + ((high - low) / 2);
299 :
6031 bruce 300 1546382 : if (mid == maxoff && GinPageRightMost(page))
301 : {
302 : /* Right infinity */
6186 teodor 303 240216 : result = -1;
304 : }
305 : else
306 : {
307 : OffsetNumber attnum;
308 : Datum key;
309 : GinNullCategory category;
310 :
311 1306166 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, mid));
4475 tgl 312 1306166 : attnum = gintuple_get_attrnum(btree->ginstate, itup);
313 1306166 : key = gintuple_get_key(btree->ginstate, itup, &category);
4557 314 1306166 : result = ginCompareAttEntries(btree->ginstate,
315 1306166 : btree->entryAttnum,
316 : btree->entryKey,
4475 317 1306166 : btree->entryCategory,
318 : attnum, key, category);
319 : }
320 :
6031 bruce 321 1546382 : if (result == 0)
322 : {
6186 teodor 323 92 : stack->off = mid;
4475 tgl 324 92 : Assert(GinGetDownlink(itup) != GIN_ROOT_BLKNO);
325 92 : return GinGetDownlink(itup);
326 : }
6031 bruce 327 1546290 : else if (result > 0)
6186 teodor 328 1156249 : low = mid + 1;
329 : else
330 390041 : high = mid;
331 : }
332 :
6031 bruce 333 261946 : Assert(high >= FirstOffsetNumber && high <= maxoff);
334 :
6186 teodor 335 261946 : stack->off = high;
336 261946 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, high));
4475 tgl 337 261946 : Assert(GinGetDownlink(itup) != GIN_ROOT_BLKNO);
338 261946 : return GinGetDownlink(itup);
339 : }
340 :
341 : /*
342 : * Searches correct position for value on leaf page.
343 : * Page should be correctly chosen.
344 : * Returns true if value found on page.
345 : */
346 : static bool
6031 bruce 347 297466 : entryLocateLeafEntry(GinBtree btree, GinBtreeStack *stack)
348 : {
2545 kgrittn 349 297466 : Page page = BufferGetPage(stack->buffer);
350 : OffsetNumber low,
351 : high;
352 :
6031 bruce 353 297466 : Assert(GinPageIsLeaf(page));
354 297466 : Assert(!GinPageIsData(page));
355 :
356 297466 : if (btree->fullScan)
357 : {
6186 teodor 358 UBC 0 : stack->off = FirstOffsetNumber;
2062 peter_e 359 0 : return true;
360 : }
361 :
6186 teodor 362 CBC 297466 : low = FirstOffsetNumber;
363 297466 : high = PageGetMaxOffsetNumber(page);
364 :
6031 bruce 365 297466 : if (high < low)
366 : {
6186 teodor 367 253 : stack->off = FirstOffsetNumber;
368 253 : return false;
369 : }
370 :
371 297213 : high++;
372 :
6031 bruce 373 2249838 : while (high > low)
374 : {
6186 teodor 375 1994808 : OffsetNumber mid = low + ((high - low) / 2);
376 : IndexTuple itup;
377 : OffsetNumber attnum;
378 : Datum key;
379 : GinNullCategory category;
380 : int result;
381 :
382 1994808 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, mid));
4475 tgl 383 1994808 : attnum = gintuple_get_attrnum(btree->ginstate, itup);
384 1994808 : key = gintuple_get_key(btree->ginstate, itup, &category);
4557 385 1994808 : result = ginCompareAttEntries(btree->ginstate,
386 1994808 : btree->entryAttnum,
387 : btree->entryKey,
4475 388 1994808 : btree->entryCategory,
389 : attnum, key, category);
6031 bruce 390 1994808 : if (result == 0)
391 : {
6186 teodor 392 42183 : stack->off = mid;
393 42183 : return true;
394 : }
6031 bruce 395 1952625 : else if (result > 0)
6186 teodor 396 1831556 : low = mid + 1;
397 : else
398 121069 : high = mid;
399 : }
400 :
401 255030 : stack->off = high;
402 255030 : return false;
403 : }
404 :
405 : static OffsetNumber
6031 bruce 406 1714 : entryFindChildPtr(GinBtree btree, Page page, BlockNumber blkno, OffsetNumber storedOff)
407 : {
408 : OffsetNumber i,
409 1714 : maxoff = PageGetMaxOffsetNumber(page);
410 : IndexTuple itup;
411 :
412 1714 : Assert(!GinPageIsLeaf(page));
413 1714 : Assert(!GinPageIsData(page));
414 :
415 : /* if page isn't changed, we returns storedOff */
416 1714 : if (storedOff >= FirstOffsetNumber && storedOff <= maxoff)
417 : {
6186 teodor 418 1714 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, storedOff));
4475 tgl 419 1714 : if (GinGetDownlink(itup) == blkno)
6186 teodor 420 1714 : return storedOff;
421 :
422 : /*
423 : * we hope, that needed pointer goes to right. It's true if there
424 : * wasn't a deletion
425 : */
6031 bruce 426 UBC 0 : for (i = storedOff + 1; i <= maxoff; i++)
427 : {
6186 teodor 428 0 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));
4475 tgl 429 0 : if (GinGetDownlink(itup) == blkno)
6186 teodor 430 0 : return i;
431 : }
6031 bruce 432 0 : maxoff = storedOff - 1;
433 : }
434 :
435 : /* last chance */
436 0 : for (i = FirstOffsetNumber; i <= maxoff; i++)
437 : {
6186 teodor 438 0 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));
4475 tgl 439 0 : if (GinGetDownlink(itup) == blkno)
6186 teodor 440 0 : return i;
441 : }
442 :
443 0 : return InvalidOffsetNumber;
444 : }
445 :
446 : static BlockNumber
6031 bruce 447 0 : entryGetLeftMostPage(GinBtree btree, Page page)
448 : {
449 : IndexTuple itup;
450 :
451 0 : Assert(!GinPageIsLeaf(page));
452 0 : Assert(!GinPageIsData(page));
453 0 : Assert(PageGetMaxOffsetNumber(page) >= FirstOffsetNumber);
454 :
6186 teodor 455 0 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, FirstOffsetNumber));
4475 tgl 456 0 : return GinGetDownlink(itup);
457 : }
458 :
459 : static bool
3420 heikki.linnakangas 460 CBC 272632 : entryIsEnoughSpace(GinBtree btree, Buffer buf, OffsetNumber off,
461 : GinBtreeEntryInsertData *insertData)
462 : {
463 272632 : Size releasedsz = 0;
464 : Size addedsz;
2545 kgrittn 465 272632 : Page page = BufferGetPage(buf);
466 :
3420 heikki.linnakangas 467 272632 : Assert(insertData->entry);
6031 bruce 468 272632 : Assert(!GinPageIsData(page));
469 :
3420 heikki.linnakangas 470 272632 : if (insertData->isDelete)
471 : {
6031 bruce 472 16326 : IndexTuple itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
473 :
3420 heikki.linnakangas 474 16326 : releasedsz = MAXALIGN(IndexTupleSize(itup)) + sizeof(ItemIdData);
475 : }
476 :
477 272632 : addedsz = MAXALIGN(IndexTupleSize(insertData->entry)) + sizeof(ItemIdData);
478 :
479 272632 : if (PageGetFreeSpace(page) + releasedsz >= addedsz)
6186 teodor 480 270858 : return true;
481 :
482 1774 : return false;
483 : }
484 :
485 : /*
486 : * Delete tuple on leaf page if tuples existed and we
487 : * should update it, update old child blkno to new right page
488 : * if child split occurred
489 : */
490 : static void
3420 heikki.linnakangas 491 272632 : entryPreparePage(GinBtree btree, Page page, OffsetNumber off,
492 : GinBtreeEntryInsertData *insertData, BlockNumber updateblkno)
493 : {
494 272632 : Assert(insertData->entry);
6031 bruce 495 272632 : Assert(!GinPageIsData(page));
496 :
3420 heikki.linnakangas 497 272632 : if (insertData->isDelete)
498 : {
6031 bruce 499 16326 : Assert(GinPageIsLeaf(page));
6186 teodor 500 16326 : PageIndexTupleDelete(page, off);
501 : }
502 :
3420 heikki.linnakangas 503 272632 : if (!GinPageIsLeaf(page) && updateblkno != InvalidBlockNumber)
504 : {
6031 bruce 505 1714 : IndexTuple itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
506 :
3420 heikki.linnakangas 507 1714 : GinSetDownlink(itup, updateblkno);
508 : }
6186 teodor 509 272632 : }
510 :
511 : /*
512 : * Prepare to insert data on an entry page.
513 : *
514 : * If it will fit, return GPTP_INSERT after doing whatever setup is needed
515 : * before we enter the insertion critical section. *ptp_workspace can be
516 : * set to pass information along to the execPlaceToPage function.
517 : *
518 : * If it won't fit, perform a page split and return two temporary page
519 : * images into *newlpage and *newrpage, with result GPTP_SPLIT.
520 : *
521 : * In neither case should the given page buffer be modified here.
522 : *
523 : * Note: on insertion to an internal node, in addition to inserting the given
524 : * item, the downlink of the existing item at stack->off will be updated to
525 : * point to updateblkno.
526 : */
527 : static GinPlaceToPageRC
2545 tgl 528 272632 : entryBeginPlaceToPage(GinBtree btree, Buffer buf, GinBtreeStack *stack,
529 : void *insertPayload, BlockNumber updateblkno,
530 : void **ptp_workspace,
531 : Page *newlpage, Page *newrpage)
532 : {
3420 heikki.linnakangas 533 272632 : GinBtreeEntryInsertData *insertData = insertPayload;
3364 534 272632 : OffsetNumber off = stack->off;
535 :
536 : /* If it doesn't fit, deal with split case */
3420 537 272632 : if (!entryIsEnoughSpace(btree, buf, off, insertData))
538 : {
2545 tgl 539 1774 : entrySplitPage(btree, buf, stack, insertData, updateblkno,
540 : newlpage, newrpage);
541 1774 : return GPTP_SPLIT;
542 : }
543 :
544 : /* Else, we're ready to proceed with insertion */
545 270858 : return GPTP_INSERT;
546 : }
547 :
548 : /*
549 : * Perform data insertion after beginPlaceToPage has decided it will fit.
550 : *
551 : * This is invoked within a critical section, and XLOG record creation (if
552 : * needed) is already started. The target buffer is registered in slot 0.
553 : */
554 : static void
555 270858 : entryExecPlaceToPage(GinBtree btree, Buffer buf, GinBtreeStack *stack,
556 : void *insertPayload, BlockNumber updateblkno,
557 : void *ptp_workspace)
558 : {
559 270858 : GinBtreeEntryInsertData *insertData = insertPayload;
560 270858 : Page page = BufferGetPage(buf);
561 270858 : OffsetNumber off = stack->off;
562 : OffsetNumber placed;
563 :
3420 heikki.linnakangas 564 270858 : entryPreparePage(btree, page, off, insertData, updateblkno);
565 :
566 270858 : placed = PageAddItem(page,
567 : (Item) insertData->entry,
568 : IndexTupleSize(insertData->entry),
569 : off, false, false);
6031 bruce 570 270858 : if (placed != off)
6186 teodor 571 UBC 0 : elog(ERROR, "failed to add item to index page in \"%s\"",
572 : RelationGetRelationName(btree->index));
573 :
1467 heikki.linnakangas 574 CBC 270858 : if (RelationNeedsWAL(btree->index) && !btree->isBuild)
575 : {
576 : /*
577 : * This must be static, because it has to survive until XLogInsert,
578 : * and we can't palloc here. Ugly, but the XLogInsert infrastructure
579 : * isn't reentrant anyway.
580 : */
581 : static ginxlogInsertEntry data;
582 :
3062 583 76327 : data.isDelete = insertData->isDelete;
584 76327 : data.offset = off;
585 :
586 76327 : XLogRegisterBufData(0, (char *) &data,
587 : offsetof(ginxlogInsertEntry, tuple));
588 76327 : XLogRegisterBufData(0, (char *) insertData->entry,
589 76327 : IndexTupleSize(insertData->entry));
590 : }
6186 teodor 591 270858 : }
592 :
593 : /*
594 : * Split entry page and insert new data.
595 : *
596 : * Returns new temp pages to *newlpage and *newrpage.
597 : * The original buffer is left untouched.
598 : */
599 : static void
3364 heikki.linnakangas 600 1774 : entrySplitPage(GinBtree btree, Buffer origbuf,
601 : GinBtreeStack *stack,
602 : GinBtreeEntryInsertData *insertData,
603 : BlockNumber updateblkno,
604 : Page *newlpage, Page *newrpage)
605 : {
606 1774 : OffsetNumber off = stack->off;
607 : OffsetNumber i,
608 : maxoff,
6031 bruce 609 1774 : separator = InvalidOffsetNumber;
610 1774 : Size totalsize = 0;
611 1774 : Size lsize = 0,
612 : size;
613 : char *ptr;
614 : IndexTuple itup;
615 : Page page;
2545 kgrittn 616 1774 : Page lpage = PageGetTempPageCopy(BufferGetPage(origbuf));
617 1774 : Page rpage = PageGetTempPageCopy(BufferGetPage(origbuf));
6031 bruce 618 1774 : Size pageSize = PageGetPageSize(lpage);
619 : PGAlignedBlock tupstore[2]; /* could need 2 pages' worth of tuples */
620 :
3420 heikki.linnakangas 621 1774 : entryPreparePage(btree, lpage, off, insertData, updateblkno);
622 :
623 : /*
624 : * First, append all the existing tuples and the new tuple we're inserting
625 : * one after another in a temporary workspace.
626 : */
6186 teodor 627 1774 : maxoff = PageGetMaxOffsetNumber(lpage);
1681 tgl 628 1774 : ptr = tupstore[0].data;
6031 bruce 629 483722 : for (i = FirstOffsetNumber; i <= maxoff; i++)
630 : {
631 481948 : if (i == off)
632 : {
3420 heikki.linnakangas 633 UBC 0 : size = MAXALIGN(IndexTupleSize(insertData->entry));
634 0 : memcpy(ptr, insertData->entry, size);
6031 bruce 635 0 : ptr += size;
6186 teodor 636 0 : totalsize += size + sizeof(ItemIdData);
637 : }
638 :
6031 bruce 639 CBC 481948 : itup = (IndexTuple) PageGetItem(lpage, PageGetItemId(lpage, i));
640 481948 : size = MAXALIGN(IndexTupleSize(itup));
6186 teodor 641 481948 : memcpy(ptr, itup, size);
6031 bruce 642 481948 : ptr += size;
6186 teodor 643 481948 : totalsize += size + sizeof(ItemIdData);
644 : }
645 :
6031 bruce 646 1774 : if (off == maxoff + 1)
647 : {
3420 heikki.linnakangas 648 1774 : size = MAXALIGN(IndexTupleSize(insertData->entry));
649 1774 : memcpy(ptr, insertData->entry, size);
6031 bruce 650 1774 : ptr += size;
6186 teodor 651 1774 : totalsize += size + sizeof(ItemIdData);
652 : }
653 :
654 : /*
655 : * Initialize the left and right pages, and copy all the tuples back to
656 : * them.
657 : */
6031 bruce 658 1774 : GinInitPage(rpage, GinPageGetOpaque(lpage)->flags, pageSize);
659 1774 : GinInitPage(lpage, GinPageGetOpaque(rpage)->flags, pageSize);
660 :
1681 tgl 661 1774 : ptr = tupstore[0].data;
6031 bruce 662 1774 : maxoff++;
6186 teodor 663 1774 : lsize = 0;
664 :
665 1774 : page = lpage;
6031 bruce 666 485496 : for (i = FirstOffsetNumber; i <= maxoff; i++)
667 : {
668 483722 : itup = (IndexTuple) ptr;
669 :
670 : /*
671 : * Decide where to split. We try to equalize the pages' total data
672 : * size, not number of tuples.
673 : */
674 483722 : if (lsize > totalsize / 2)
675 : {
676 240523 : if (separator == InvalidOffsetNumber)
677 1774 : separator = i - 1;
6186 teodor 678 240523 : page = rpage;
679 : }
680 : else
681 : {
6031 bruce 682 243199 : lsize += MAXALIGN(IndexTupleSize(itup)) + sizeof(ItemIdData);
683 : }
684 :
5680 tgl 685 483722 : if (PageAddItem(page, (Item) itup, IndexTupleSize(itup), InvalidOffsetNumber, false, false) == InvalidOffsetNumber)
6186 teodor 686 UBC 0 : elog(ERROR, "failed to add item to index page in \"%s\"",
687 : RelationGetRelationName(btree->index));
6031 bruce 688 CBC 483722 : ptr += MAXALIGN(IndexTupleSize(itup));
689 : }
690 :
691 : /* return temp pages to caller */
3364 heikki.linnakangas 692 1774 : *newlpage = lpage;
693 1774 : *newrpage = rpage;
6186 teodor 694 1774 : }
695 :
696 : /*
697 : * Construct insertion payload for inserting the downlink for given buffer.
698 : */
699 : static void *
3427 heikki.linnakangas 700 1714 : entryPrepareDownlink(GinBtree btree, Buffer lbuf)
701 : {
702 : GinBtreeEntryInsertData *insertData;
2545 kgrittn 703 1714 : Page lpage = BufferGetPage(lbuf);
3420 heikki.linnakangas 704 1714 : BlockNumber lblkno = BufferGetBlockNumber(lbuf);
705 : IndexTuple itup;
706 :
3427 707 1714 : itup = getRightMostTuple(lpage);
708 :
3420 709 1714 : insertData = palloc(sizeof(GinBtreeEntryInsertData));
710 1714 : insertData->entry = GinFormInteriorTuple(itup, lpage, lblkno);
711 1714 : insertData->isDelete = false;
712 :
713 1714 : return insertData;
714 : }
715 :
716 : /*
717 : * Fills new root by rightest values from child.
718 : * Also called from ginxlog, should not use btree
719 : */
720 : void
721 60 : ginEntryFillRoot(GinBtree btree, Page root,
722 : BlockNumber lblkno, Page lpage,
723 : BlockNumber rblkno, Page rpage)
724 : {
725 : IndexTuple itup;
726 :
727 60 : itup = GinFormInteriorTuple(getRightMostTuple(lpage), lpage, lblkno);
728 60 : if (PageAddItem(root, (Item) itup, IndexTupleSize(itup), InvalidOffsetNumber, false, false) == InvalidOffsetNumber)
6186 teodor 729 UBC 0 : elog(ERROR, "failed to add item to index root page");
4634 tgl 730 CBC 60 : pfree(itup);
731 :
3420 heikki.linnakangas 732 60 : itup = GinFormInteriorTuple(getRightMostTuple(rpage), rpage, rblkno);
733 60 : if (PageAddItem(root, (Item) itup, IndexTupleSize(itup), InvalidOffsetNumber, false, false) == InvalidOffsetNumber)
6186 teodor 734 UBC 0 : elog(ERROR, "failed to add item to index root page");
4634 tgl 735 CBC 60 : pfree(itup);
6186 teodor 736 60 : }
737 :
738 : /*
739 : * Set up GinBtree for entry page access
740 : *
741 : * Note: during WAL recovery, there may be no valid data in ginstate
742 : * other than a faked-up Relation pointer; the key datum is bogus too.
743 : */
744 : void
4475 tgl 745 297466 : ginPrepareEntryScan(GinBtree btree, OffsetNumber attnum,
746 : Datum key, GinNullCategory category,
747 : GinState *ginstate)
748 : {
6186 teodor 749 297466 : memset(btree, 0, sizeof(GinBtreeData));
750 :
4475 tgl 751 297466 : btree->index = ginstate->index;
3420 heikki.linnakangas 752 297466 : btree->rootBlkno = GIN_ROOT_BLKNO;
4557 tgl 753 297466 : btree->ginstate = ginstate;
754 :
6186 teodor 755 297466 : btree->findChildPage = entryLocateEntry;
3427 heikki.linnakangas 756 297466 : btree->getLeftMostChild = entryGetLeftMostPage;
4557 tgl 757 297466 : btree->isMoveRight = entryIsMoveRight;
6186 teodor 758 297466 : btree->findItem = entryLocateLeafEntry;
759 297466 : btree->findChildPtr = entryFindChildPtr;
2545 tgl 760 297466 : btree->beginPlaceToPage = entryBeginPlaceToPage;
761 297466 : btree->execPlaceToPage = entryExecPlaceToPage;
4557 762 297466 : btree->fillRoot = ginEntryFillRoot;
3427 heikki.linnakangas 763 297466 : btree->prepareDownlink = entryPrepareDownlink;
764 :
2062 peter_e 765 297466 : btree->isData = false;
766 297466 : btree->fullScan = false;
767 297466 : btree->isBuild = false;
768 :
4557 tgl 769 297466 : btree->entryAttnum = attnum;
4475 770 297466 : btree->entryKey = key;
771 297466 : btree->entryCategory = category;
6186 teodor 772 297466 : }
|
