Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * gindatapage.c
4 : * routines for handling GIN posting tree pages.
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/gindatapage.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 "lib/ilist.h"
21 : #include "miscadmin.h"
22 : #include "storage/predicate.h"
23 : #include "utils/rel.h"
24 :
25 : /*
26 : * Min, Max and Target size of posting lists stored on leaf pages, in bytes.
27 : *
28 : * The code can deal with any size, but random access is more efficient when
29 : * a number of smaller lists are stored, rather than one big list. If a
30 : * posting list would become larger than Max size as a result of insertions,
31 : * it is split into two. If a posting list would be smaller than minimum
32 : * size, it is merged with the next posting list.
33 : */
34 : #define GinPostingListSegmentMaxSize 384
35 : #define GinPostingListSegmentTargetSize 256
36 : #define GinPostingListSegmentMinSize 128
37 :
38 : /*
39 : * At least this many items fit in a GinPostingListSegmentMaxSize-bytes
40 : * long segment. This is used when estimating how much space is required
41 : * for N items, at minimum.
42 : */
43 : #define MinTuplesPerSegment ((GinPostingListSegmentMaxSize - 2) / 6)
44 :
45 : /*
46 : * A working struct for manipulating a posting tree leaf page.
47 : */
48 : typedef struct
49 : {
50 : dlist_head segments; /* a list of leafSegmentInfos */
51 :
52 : /*
53 : * The following fields represent how the segments are split across pages,
54 : * if a page split is required. Filled in by leafRepackItems.
55 : */
56 : dlist_node *lastleft; /* last segment on left page */
57 : int lsize; /* total size on left page */
58 : int rsize; /* total size on right page */
59 :
60 : bool oldformat; /* page is in pre-9.4 format on disk */
61 :
62 : /*
63 : * If we need WAL data representing the reconstructed leaf page, it's
64 : * stored here by computeLeafRecompressWALData.
65 : */
66 : char *walinfo; /* buffer start */
67 : int walinfolen; /* and length */
68 : } disassembledLeaf;
69 :
70 : typedef struct
71 : {
72 : dlist_node node; /* linked list pointers */
73 :
74 : /*-------------
75 : * 'action' indicates the status of this in-memory segment, compared to
76 : * what's on disk. It is one of the GIN_SEGMENT_* action codes:
77 : *
78 : * UNMODIFIED no changes
79 : * DELETE the segment is to be removed. 'seg' and 'items' are
80 : * ignored
81 : * INSERT this is a completely new segment
82 : * REPLACE this replaces an existing segment with new content
83 : * ADDITEMS like REPLACE, but no items have been removed, and we track
84 : * in detail what items have been added to this segment, in
85 : * 'modifieditems'
86 : *-------------
87 : */
88 : char action;
89 :
90 : ItemPointerData *modifieditems;
91 : uint16 nmodifieditems;
92 :
93 : /*
94 : * The following fields represent the items in this segment. If 'items' is
95 : * not NULL, it contains a palloc'd array of the items in this segment. If
96 : * 'seg' is not NULL, it contains the items in an already-compressed
97 : * format. It can point to an on-disk page (!modified), or a palloc'd
98 : * segment in memory. If both are set, they must represent the same items.
99 : */
100 : GinPostingList *seg;
101 : ItemPointer items;
102 : int nitems; /* # of items in 'items', if items != NULL */
103 : } leafSegmentInfo;
104 :
105 : static ItemPointer dataLeafPageGetUncompressed(Page page, int *nitems);
106 : static void dataSplitPageInternal(GinBtree btree, Buffer origbuf,
107 : GinBtreeStack *stack,
108 : void *insertdata, BlockNumber updateblkno,
109 : Page *newlpage, Page *newrpage);
110 :
111 : static disassembledLeaf *disassembleLeaf(Page page);
112 : static bool leafRepackItems(disassembledLeaf *leaf, ItemPointer remaining);
113 : static bool addItemsToLeaf(disassembledLeaf *leaf, ItemPointer newItems,
114 : int nNewItems);
115 :
116 : static void computeLeafRecompressWALData(disassembledLeaf *leaf);
117 : static void dataPlaceToPageLeafRecompress(Buffer buf, disassembledLeaf *leaf);
118 : static void dataPlaceToPageLeafSplit(disassembledLeaf *leaf,
119 : ItemPointerData lbound, ItemPointerData rbound,
120 : Page lpage, Page rpage);
121 :
122 : /*
123 : * Read TIDs from leaf data page to single uncompressed array. The TIDs are
124 : * returned in ascending order.
125 : *
126 : * advancePast is a hint, indicating that the caller is only interested in
127 : * TIDs > advancePast. To return all items, use ItemPointerSetMin.
128 : *
129 : * Note: This function can still return items smaller than advancePast that
130 : * are in the same posting list as the items of interest, so the caller must
131 : * still check all the returned items. But passing it allows this function to
132 : * skip whole posting lists.
133 : */
134 : ItemPointer
135 164 : GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerData advancePast)
136 : {
137 : ItemPointer result;
138 :
139 164 : if (GinPageIsCompressed(page))
140 : {
141 164 : GinPostingList *seg = GinDataLeafPageGetPostingList(page);
142 164 : Size len = GinDataLeafPageGetPostingListSize(page);
143 164 : Pointer endptr = ((Pointer) seg) + len;
144 : GinPostingList *next;
145 :
146 : /* Skip to the segment containing advancePast+1 */
147 164 : if (ItemPointerIsValid(&advancePast))
148 : {
149 94 : next = GinNextPostingListSegment(seg);
150 178 : while ((Pointer) next < endptr &&
151 78 : ginCompareItemPointers(&next->first, &advancePast) <= 0)
152 : {
153 6 : seg = next;
154 6 : next = GinNextPostingListSegment(seg);
155 : }
156 94 : len = endptr - (Pointer) seg;
157 : }
158 :
159 164 : if (len > 0)
160 152 : result = ginPostingListDecodeAllSegments(seg, len, nitems);
161 : else
162 : {
163 12 : result = NULL;
164 12 : *nitems = 0;
165 : }
166 : }
167 : else
168 : {
169 0 : ItemPointer tmp = dataLeafPageGetUncompressed(page, nitems);
170 :
171 0 : result = palloc((*nitems) * sizeof(ItemPointerData));
172 0 : memcpy(result, tmp, (*nitems) * sizeof(ItemPointerData));
173 : }
174 :
175 164 : return result;
176 : }
177 :
178 : /*
179 : * Places all TIDs from leaf data page to bitmap.
180 : */
181 : int
182 30 : GinDataLeafPageGetItemsToTbm(Page page, TIDBitmap *tbm)
183 : {
184 : ItemPointer uncompressed;
185 : int nitems;
186 :
187 30 : if (GinPageIsCompressed(page))
188 : {
189 30 : GinPostingList *segment = GinDataLeafPageGetPostingList(page);
190 30 : Size len = GinDataLeafPageGetPostingListSize(page);
191 :
192 30 : nitems = ginPostingListDecodeAllSegmentsToTbm(segment, len, tbm);
193 : }
194 : else
195 : {
196 0 : uncompressed = dataLeafPageGetUncompressed(page, &nitems);
197 :
198 0 : if (nitems > 0)
199 0 : tbm_add_tuples(tbm, uncompressed, nitems, false);
200 : }
201 :
202 30 : return nitems;
203 : }
204 :
205 : /*
206 : * Get pointer to the uncompressed array of items on a pre-9.4 format
207 : * uncompressed leaf page. The number of items in the array is returned in
208 : * *nitems.
209 : */
210 : static ItemPointer
211 0 : dataLeafPageGetUncompressed(Page page, int *nitems)
212 : {
213 : ItemPointer items;
214 :
215 : Assert(!GinPageIsCompressed(page));
216 :
217 : /*
218 : * In the old pre-9.4 page format, the whole page content is used for
219 : * uncompressed items, and the number of items is stored in 'maxoff'
220 : */
221 0 : items = (ItemPointer) GinDataPageGetData(page);
222 0 : *nitems = GinPageGetOpaque(page)->maxoff;
223 :
224 0 : return items;
225 : }
226 :
227 : /*
228 : * Check if we should follow the right link to find the item we're searching
229 : * for.
230 : *
231 : * Compares inserting item pointer with the right bound of the current page.
232 : */
233 : static bool
234 26616 : dataIsMoveRight(GinBtree btree, Page page)
235 : {
236 26616 : ItemPointer iptr = GinDataPageGetRightBound(page);
237 :
238 26616 : if (GinPageRightMost(page))
239 26616 : return false;
240 :
241 0 : if (GinPageIsDeleted(page))
242 0 : return true;
243 :
244 0 : return (ginCompareItemPointers(&btree->itemptr, iptr) > 0);
245 : }
246 :
247 : /*
248 : * Find correct PostingItem in non-leaf page. It is assumed that this is
249 : * the correct page, and the searched value SHOULD be on the page.
250 : */
251 : static BlockNumber
252 26692 : dataLocateItem(GinBtree btree, GinBtreeStack *stack)
253 : {
254 : OffsetNumber low,
255 : high,
256 : maxoff;
257 26692 : PostingItem *pitem = NULL;
258 : int result;
259 26692 : Page page = BufferGetPage(stack->buffer);
260 :
261 : Assert(!GinPageIsLeaf(page));
262 : Assert(GinPageIsData(page));
263 :
264 26692 : if (btree->fullScan)
265 : {
266 76 : stack->off = FirstOffsetNumber;
267 76 : stack->predictNumber *= GinPageGetOpaque(page)->maxoff;
268 76 : return btree->getLeftMostChild(btree, page);
269 : }
270 :
271 26616 : low = FirstOffsetNumber;
272 26616 : maxoff = high = GinPageGetOpaque(page)->maxoff;
273 : Assert(high >= low);
274 :
275 26616 : high++;
276 :
277 79848 : while (high > low)
278 : {
279 53232 : OffsetNumber mid = low + ((high - low) / 2);
280 :
281 53232 : pitem = GinDataPageGetPostingItem(page, mid);
282 :
283 53232 : if (mid == maxoff)
284 : {
285 : /*
286 : * Right infinity, page already correctly chosen with a help of
287 : * dataIsMoveRight
288 : */
289 26616 : result = -1;
290 : }
291 : else
292 : {
293 26616 : pitem = GinDataPageGetPostingItem(page, mid);
294 26616 : result = ginCompareItemPointers(&btree->itemptr, &(pitem->key));
295 : }
296 :
297 53232 : if (result == 0)
298 : {
299 0 : stack->off = mid;
300 0 : return PostingItemGetBlockNumber(pitem);
301 : }
302 53232 : else if (result > 0)
303 26616 : low = mid + 1;
304 : else
305 26616 : high = mid;
306 : }
307 :
308 : Assert(high >= FirstOffsetNumber && high <= maxoff);
309 :
310 26616 : stack->off = high;
311 26616 : pitem = GinDataPageGetPostingItem(page, high);
312 26616 : return PostingItemGetBlockNumber(pitem);
313 : }
314 :
315 : /*
316 : * Find link to blkno on non-leaf page, returns offset of PostingItem
317 : */
318 : static OffsetNumber
319 46 : dataFindChildPtr(GinBtree btree, Page page, BlockNumber blkno, OffsetNumber storedOff)
320 : {
321 : OffsetNumber i,
322 46 : maxoff = GinPageGetOpaque(page)->maxoff;
323 : PostingItem *pitem;
324 :
325 : Assert(!GinPageIsLeaf(page));
326 : Assert(GinPageIsData(page));
327 :
328 : /* if page isn't changed, we return storedOff */
329 46 : if (storedOff >= FirstOffsetNumber && storedOff <= maxoff)
330 : {
331 46 : pitem = GinDataPageGetPostingItem(page, storedOff);
332 46 : if (PostingItemGetBlockNumber(pitem) == blkno)
333 46 : return storedOff;
334 :
335 : /*
336 : * we hope, that needed pointer goes to right. It's true if there
337 : * wasn't a deletion
338 : */
339 0 : for (i = storedOff + 1; i <= maxoff; i++)
340 : {
341 0 : pitem = GinDataPageGetPostingItem(page, i);
342 0 : if (PostingItemGetBlockNumber(pitem) == blkno)
343 0 : return i;
344 : }
345 :
346 0 : maxoff = storedOff - 1;
347 : }
348 :
349 : /* last chance */
350 0 : for (i = FirstOffsetNumber; i <= maxoff; i++)
351 : {
352 0 : pitem = GinDataPageGetPostingItem(page, i);
353 0 : if (PostingItemGetBlockNumber(pitem) == blkno)
354 0 : return i;
355 : }
356 :
357 0 : return InvalidOffsetNumber;
358 : }
359 :
360 : /*
361 : * Return blkno of leftmost child
362 : */
363 : static BlockNumber
364 76 : dataGetLeftMostPage(GinBtree btree, Page page)
365 : {
366 : PostingItem *pitem;
367 :
368 : Assert(!GinPageIsLeaf(page));
369 : Assert(GinPageIsData(page));
370 : Assert(GinPageGetOpaque(page)->maxoff >= FirstOffsetNumber);
371 :
372 76 : pitem = GinDataPageGetPostingItem(page, FirstOffsetNumber);
373 76 : return PostingItemGetBlockNumber(pitem);
374 : }
375 :
376 : /*
377 : * Add PostingItem to a non-leaf page.
378 : */
379 : void
380 258 : GinDataPageAddPostingItem(Page page, PostingItem *data, OffsetNumber offset)
381 : {
382 258 : OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
383 : char *ptr;
384 :
385 : Assert(PostingItemGetBlockNumber(data) != InvalidBlockNumber);
386 : Assert(!GinPageIsLeaf(page));
387 :
388 258 : if (offset == InvalidOffsetNumber)
389 : {
390 208 : ptr = (char *) GinDataPageGetPostingItem(page, maxoff + 1);
391 : }
392 : else
393 : {
394 50 : ptr = (char *) GinDataPageGetPostingItem(page, offset);
395 50 : if (offset != maxoff + 1)
396 50 : memmove(ptr + sizeof(PostingItem),
397 : ptr,
398 50 : (maxoff - offset + 1) * sizeof(PostingItem));
399 : }
400 258 : memcpy(ptr, data, sizeof(PostingItem));
401 :
402 258 : maxoff++;
403 258 : GinPageGetOpaque(page)->maxoff = maxoff;
404 :
405 : /*
406 : * Also set pd_lower to the end of the posting items, to follow the
407 : * "standard" page layout, so that we can squeeze out the unused space
408 : * from full-page images.
409 : */
410 258 : GinDataPageSetDataSize(page, maxoff * sizeof(PostingItem));
411 258 : }
412 :
413 : /*
414 : * Delete posting item from non-leaf page
415 : */
416 : void
417 12 : GinPageDeletePostingItem(Page page, OffsetNumber offset)
418 : {
419 12 : OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
420 :
421 : Assert(!GinPageIsLeaf(page));
422 : Assert(offset >= FirstOffsetNumber && offset <= maxoff);
423 :
424 12 : if (offset != maxoff)
425 12 : memmove(GinDataPageGetPostingItem(page, offset),
426 12 : GinDataPageGetPostingItem(page, offset + 1),
427 12 : sizeof(PostingItem) * (maxoff - offset));
428 :
429 12 : maxoff--;
430 12 : GinPageGetOpaque(page)->maxoff = maxoff;
431 :
432 12 : GinDataPageSetDataSize(page, maxoff * sizeof(PostingItem));
433 12 : }
434 :
435 : /*
436 : * Prepare to insert data on a leaf data page.
437 : *
438 : * If it will fit, return GPTP_INSERT after doing whatever setup is needed
439 : * before we enter the insertion critical section. *ptp_workspace can be
440 : * set to pass information along to the execPlaceToPage function.
441 : *
442 : * If it won't fit, perform a page split and return two temporary page
443 : * images into *newlpage and *newrpage, with result GPTP_SPLIT.
444 : *
445 : * In neither case should the given page buffer be modified here.
446 : */
447 : static GinPlaceToPageRC
448 49550 : dataBeginPlaceToPageLeaf(GinBtree btree, Buffer buf, GinBtreeStack *stack,
449 : void *insertdata,
450 : void **ptp_workspace,
451 : Page *newlpage, Page *newrpage)
452 : {
453 49550 : GinBtreeDataLeafInsertData *items = insertdata;
454 49550 : ItemPointer newItems = &items->items[items->curitem];
455 49550 : int maxitems = items->nitem - items->curitem;
456 49550 : Page page = BufferGetPage(buf);
457 : int i;
458 : ItemPointerData rbound;
459 : ItemPointerData lbound;
460 : bool needsplit;
461 : bool append;
462 : int segsize;
463 : Size freespace;
464 : disassembledLeaf *leaf;
465 : leafSegmentInfo *lastleftinfo;
466 : ItemPointerData maxOldItem;
467 : ItemPointerData remaining;
468 :
469 49550 : rbound = *GinDataPageGetRightBound(page);
470 :
471 : /*
472 : * Count how many of the new items belong to this page.
473 : */
474 49550 : if (!GinPageRightMost(page))
475 : {
476 0 : for (i = 0; i < maxitems; i++)
477 : {
478 0 : if (ginCompareItemPointers(&newItems[i], &rbound) > 0)
479 : {
480 : /*
481 : * This needs to go to some other location in the tree. (The
482 : * caller should've chosen the insert location so that at
483 : * least the first item goes here.)
484 : */
485 : Assert(i > 0);
486 0 : break;
487 : }
488 : }
489 0 : maxitems = i;
490 : }
491 :
492 : /* Disassemble the data on the page */
493 49550 : leaf = disassembleLeaf(page);
494 :
495 : /*
496 : * Are we appending to the end of the page? IOW, are all the new items
497 : * larger than any of the existing items.
498 : */
499 49550 : if (!dlist_is_empty(&leaf->segments))
500 : {
501 49550 : lastleftinfo = dlist_container(leafSegmentInfo, node,
502 : dlist_tail_node(&leaf->segments));
503 49550 : if (!lastleftinfo->items)
504 49550 : lastleftinfo->items = ginPostingListDecode(lastleftinfo->seg,
505 : &lastleftinfo->nitems);
506 49550 : maxOldItem = lastleftinfo->items[lastleftinfo->nitems - 1];
507 49550 : if (ginCompareItemPointers(&newItems[0], &maxOldItem) >= 0)
508 49550 : append = true;
509 : else
510 0 : append = false;
511 : }
512 : else
513 : {
514 0 : ItemPointerSetMin(&maxOldItem);
515 0 : append = true;
516 : }
517 :
518 : /*
519 : * If we're appending to the end of the page, we will append as many items
520 : * as we can fit (after splitting), and stop when the pages becomes full.
521 : * Otherwise we have to limit the number of new items to insert, because
522 : * once we start packing we can't just stop when we run out of space,
523 : * because we must make sure that all the old items still fit.
524 : */
525 49550 : if (GinPageIsCompressed(page))
526 49550 : freespace = GinDataLeafPageGetFreeSpace(page);
527 : else
528 0 : freespace = 0;
529 49550 : if (append)
530 : {
531 : /*
532 : * Even when appending, trying to append more items than will fit is
533 : * not completely free, because we will merge the new items and old
534 : * items into an array below. In the best case, every new item fits in
535 : * a single byte, and we can use all the free space on the old page as
536 : * well as the new page. For simplicity, ignore segment overhead etc.
537 : */
538 49550 : maxitems = Min(maxitems, freespace + GinDataPageMaxDataSize);
539 : }
540 : else
541 : {
542 : /*
543 : * Calculate a conservative estimate of how many new items we can fit
544 : * on the two pages after splitting.
545 : *
546 : * We can use any remaining free space on the old page to store full
547 : * segments, as well as the new page. Each full-sized segment can hold
548 : * at least MinTuplesPerSegment items
549 : */
550 : int nnewsegments;
551 :
552 0 : nnewsegments = freespace / GinPostingListSegmentMaxSize;
553 0 : nnewsegments += GinDataPageMaxDataSize / GinPostingListSegmentMaxSize;
554 0 : maxitems = Min(maxitems, nnewsegments * MinTuplesPerSegment);
555 : }
556 :
557 : /* Add the new items to the segment list */
558 49550 : if (!addItemsToLeaf(leaf, newItems, maxitems))
559 : {
560 : /* all items were duplicates, we have nothing to do */
561 0 : items->curitem += maxitems;
562 :
563 0 : return GPTP_NO_WORK;
564 : }
565 :
566 : /*
567 : * Pack the items back to compressed segments, ready for writing to disk.
568 : */
569 49550 : needsplit = leafRepackItems(leaf, &remaining);
570 :
571 : /*
572 : * Did all the new items fit?
573 : *
574 : * If we're appending, it's OK if they didn't. But as a sanity check,
575 : * verify that all the old items fit.
576 : */
577 49550 : if (ItemPointerIsValid(&remaining))
578 : {
579 40 : if (!append || ItemPointerCompare(&maxOldItem, &remaining) >= 0)
580 0 : elog(ERROR, "could not split GIN page; all old items didn't fit");
581 :
582 : /* Count how many of the new items did fit. */
583 304842 : for (i = 0; i < maxitems; i++)
584 : {
585 304842 : if (ginCompareItemPointers(&newItems[i], &remaining) >= 0)
586 40 : break;
587 : }
588 40 : if (i == 0)
589 0 : elog(ERROR, "could not split GIN page; no new items fit");
590 40 : maxitems = i;
591 : }
592 :
593 49550 : if (!needsplit)
594 : {
595 : /*
596 : * Great, all the items fit on a single page. If needed, prepare data
597 : * for a WAL record describing the changes we'll make.
598 : */
599 49400 : if (RelationNeedsWAL(btree->index) && !btree->isBuild)
600 49400 : computeLeafRecompressWALData(leaf);
601 :
602 : /*
603 : * We're ready to enter the critical section, but
604 : * dataExecPlaceToPageLeaf will need access to the "leaf" data.
605 : */
606 49400 : *ptp_workspace = leaf;
607 :
608 49400 : if (append)
609 49400 : elog(DEBUG2, "appended %d new items to block %u; %d bytes (%d to go)",
610 : maxitems, BufferGetBlockNumber(buf), (int) leaf->lsize,
611 : items->nitem - items->curitem - maxitems);
612 : else
613 0 : elog(DEBUG2, "inserted %d new items to block %u; %d bytes (%d to go)",
614 : maxitems, BufferGetBlockNumber(buf), (int) leaf->lsize,
615 : items->nitem - items->curitem - maxitems);
616 : }
617 : else
618 : {
619 : /*
620 : * Have to split.
621 : *
622 : * leafRepackItems already divided the segments between the left and
623 : * the right page. It filled the left page as full as possible, and
624 : * put the rest to the right page. When building a new index, that's
625 : * good, because the table is scanned from beginning to end and there
626 : * won't be any more insertions to the left page during the build.
627 : * This packs the index as tight as possible. But otherwise, split
628 : * 50/50, by moving segments from the left page to the right page
629 : * until they're balanced.
630 : *
631 : * As a further heuristic, when appending items to the end of the
632 : * page, try to make the left page 75% full, on the assumption that
633 : * subsequent insertions will probably also go to the end. This packs
634 : * the index somewhat tighter when appending to a table, which is very
635 : * common.
636 : */
637 150 : if (!btree->isBuild)
638 : {
639 260 : while (dlist_has_prev(&leaf->segments, leaf->lastleft))
640 : {
641 260 : lastleftinfo = dlist_container(leafSegmentInfo, node, leaf->lastleft);
642 :
643 : /* ignore deleted segments */
644 260 : if (lastleftinfo->action != GIN_SEGMENT_DELETE)
645 : {
646 260 : segsize = SizeOfGinPostingList(lastleftinfo->seg);
647 :
648 : /*
649 : * Note that we check that the right page doesn't become
650 : * more full than the left page even when appending. It's
651 : * possible that we added enough items to make both pages
652 : * more than 75% full.
653 : */
654 260 : if ((leaf->lsize - segsize) - (leaf->rsize + segsize) < 0)
655 48 : break;
656 212 : if (append)
657 : {
658 212 : if ((leaf->lsize - segsize) < (BLCKSZ * 3) / 4)
659 10 : break;
660 : }
661 :
662 202 : leaf->lsize -= segsize;
663 202 : leaf->rsize += segsize;
664 : }
665 202 : leaf->lastleft = dlist_prev_node(&leaf->segments, leaf->lastleft);
666 : }
667 : }
668 : Assert(leaf->lsize <= GinDataPageMaxDataSize);
669 : Assert(leaf->rsize <= GinDataPageMaxDataSize);
670 :
671 : /*
672 : * Fetch the max item in the left page's last segment; it becomes the
673 : * right bound of the page.
674 : */
675 150 : lastleftinfo = dlist_container(leafSegmentInfo, node, leaf->lastleft);
676 150 : if (!lastleftinfo->items)
677 150 : lastleftinfo->items = ginPostingListDecode(lastleftinfo->seg,
678 : &lastleftinfo->nitems);
679 150 : lbound = lastleftinfo->items[lastleftinfo->nitems - 1];
680 :
681 : /*
682 : * Now allocate a couple of temporary page images, and fill them.
683 : */
684 150 : *newlpage = palloc(BLCKSZ);
685 150 : *newrpage = palloc(BLCKSZ);
686 :
687 150 : dataPlaceToPageLeafSplit(leaf, lbound, rbound,
688 : *newlpage, *newrpage);
689 :
690 : Assert(GinPageRightMost(page) ||
691 : ginCompareItemPointers(GinDataPageGetRightBound(*newlpage),
692 : GinDataPageGetRightBound(*newrpage)) < 0);
693 :
694 150 : if (append)
695 150 : elog(DEBUG2, "appended %d items to block %u; split %d/%d (%d to go)",
696 : maxitems, BufferGetBlockNumber(buf), (int) leaf->lsize, (int) leaf->rsize,
697 : items->nitem - items->curitem - maxitems);
698 : else
699 0 : elog(DEBUG2, "inserted %d items to block %u; split %d/%d (%d to go)",
700 : maxitems, BufferGetBlockNumber(buf), (int) leaf->lsize, (int) leaf->rsize,
701 : items->nitem - items->curitem - maxitems);
702 : }
703 :
704 49550 : items->curitem += maxitems;
705 :
706 49550 : return needsplit ? GPTP_SPLIT : GPTP_INSERT;
707 : }
708 :
709 : /*
710 : * Perform data insertion after beginPlaceToPage has decided it will fit.
711 : *
712 : * This is invoked within a critical section, and XLOG record creation (if
713 : * needed) is already started. The target buffer is registered in slot 0.
714 : */
715 : static void
716 49400 : dataExecPlaceToPageLeaf(GinBtree btree, Buffer buf, GinBtreeStack *stack,
717 : void *insertdata, void *ptp_workspace)
718 : {
719 49400 : disassembledLeaf *leaf = (disassembledLeaf *) ptp_workspace;
720 :
721 : /* Apply changes to page */
722 49400 : dataPlaceToPageLeafRecompress(buf, leaf);
723 :
724 49400 : MarkBufferDirty(buf);
725 :
726 : /* If needed, register WAL data built by computeLeafRecompressWALData */
727 49400 : if (RelationNeedsWAL(btree->index) && !btree->isBuild)
728 : {
729 49400 : XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
730 49400 : XLogRegisterBufData(0, leaf->walinfo, leaf->walinfolen);
731 : }
732 49400 : }
733 :
734 : /*
735 : * Vacuum a posting tree leaf page.
736 : */
737 : void
738 48 : ginVacuumPostingTreeLeaf(Relation indexrel, Buffer buffer, GinVacuumState *gvs)
739 : {
740 48 : Page page = BufferGetPage(buffer);
741 : disassembledLeaf *leaf;
742 48 : bool removedsomething = false;
743 : dlist_iter iter;
744 :
745 48 : leaf = disassembleLeaf(page);
746 :
747 : /* Vacuum each segment. */
748 1002 : dlist_foreach(iter, &leaf->segments)
749 : {
750 954 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node, iter.cur);
751 : int oldsegsize;
752 : ItemPointer cleaned;
753 : int ncleaned;
754 :
755 954 : if (!seginfo->items)
756 954 : seginfo->items = ginPostingListDecode(seginfo->seg,
757 : &seginfo->nitems);
758 954 : if (seginfo->seg)
759 954 : oldsegsize = SizeOfGinPostingList(seginfo->seg);
760 : else
761 0 : oldsegsize = GinDataPageMaxDataSize;
762 :
763 954 : cleaned = ginVacuumItemPointers(gvs,
764 : seginfo->items,
765 : seginfo->nitems,
766 : &ncleaned);
767 954 : pfree(seginfo->items);
768 954 : seginfo->items = NULL;
769 954 : seginfo->nitems = 0;
770 954 : if (cleaned)
771 : {
772 900 : if (ncleaned > 0)
773 : {
774 : int npacked;
775 :
776 24 : seginfo->seg = ginCompressPostingList(cleaned,
777 : ncleaned,
778 : oldsegsize,
779 : &npacked);
780 : /* Removing an item never increases the size of the segment */
781 24 : if (npacked != ncleaned)
782 0 : elog(ERROR, "could not fit vacuumed posting list");
783 24 : seginfo->action = GIN_SEGMENT_REPLACE;
784 : }
785 : else
786 : {
787 876 : seginfo->seg = NULL;
788 876 : seginfo->items = NULL;
789 876 : seginfo->action = GIN_SEGMENT_DELETE;
790 : }
791 900 : seginfo->nitems = ncleaned;
792 :
793 900 : removedsomething = true;
794 : }
795 : }
796 :
797 : /*
798 : * If we removed any items, reconstruct the page from the pieces.
799 : *
800 : * We don't try to re-encode the segments here, even though some of them
801 : * might be really small now that we've removed some items from them. It
802 : * seems like a waste of effort, as there isn't really any benefit from
803 : * larger segments per se; larger segments only help to pack more items in
804 : * the same space. We might as well delay doing that until the next
805 : * insertion, which will need to re-encode at least part of the page
806 : * anyway.
807 : *
808 : * Also note if the page was in uncompressed, pre-9.4 format before, it is
809 : * now represented as one huge segment that contains all the items. It
810 : * might make sense to split that, to speed up random access, but we don't
811 : * bother. You'll have to REINDEX anyway if you want the full gain of the
812 : * new tighter index format.
813 : */
814 48 : if (removedsomething)
815 : {
816 : bool modified;
817 :
818 : /*
819 : * Make sure we have a palloc'd copy of all segments, after the first
820 : * segment that is modified. (dataPlaceToPageLeafRecompress requires
821 : * this).
822 : */
823 48 : modified = false;
824 1002 : dlist_foreach(iter, &leaf->segments)
825 : {
826 954 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
827 : iter.cur);
828 :
829 954 : if (seginfo->action != GIN_SEGMENT_UNMODIFIED)
830 900 : modified = true;
831 954 : if (modified && seginfo->action != GIN_SEGMENT_DELETE)
832 : {
833 78 : int segsize = SizeOfGinPostingList(seginfo->seg);
834 78 : GinPostingList *tmp = (GinPostingList *) palloc(segsize);
835 :
836 78 : memcpy(tmp, seginfo->seg, segsize);
837 78 : seginfo->seg = tmp;
838 : }
839 : }
840 :
841 48 : if (RelationNeedsWAL(indexrel))
842 12 : computeLeafRecompressWALData(leaf);
843 :
844 : /* Apply changes to page */
845 48 : START_CRIT_SECTION();
846 :
847 48 : dataPlaceToPageLeafRecompress(buffer, leaf);
848 :
849 48 : MarkBufferDirty(buffer);
850 :
851 48 : if (RelationNeedsWAL(indexrel))
852 : {
853 : XLogRecPtr recptr;
854 :
855 12 : XLogBeginInsert();
856 12 : XLogRegisterBuffer(0, buffer, REGBUF_STANDARD);
857 12 : XLogRegisterBufData(0, leaf->walinfo, leaf->walinfolen);
858 12 : recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_VACUUM_DATA_LEAF_PAGE);
859 12 : PageSetLSN(page, recptr);
860 : }
861 :
862 48 : END_CRIT_SECTION();
863 : }
864 48 : }
865 :
866 : /*
867 : * Construct a ginxlogRecompressDataLeaf record representing the changes
868 : * in *leaf. (Because this requires a palloc, we have to do it before
869 : * we enter the critical section that actually updates the page.)
870 : */
871 : static void
872 49412 : computeLeafRecompressWALData(disassembledLeaf *leaf)
873 : {
874 49412 : int nmodified = 0;
875 : char *walbufbegin;
876 : char *walbufend;
877 : dlist_iter iter;
878 : int segno;
879 : ginxlogRecompressDataLeaf *recompress_xlog;
880 :
881 : /* Count the modified segments */
882 891934 : dlist_foreach(iter, &leaf->segments)
883 : {
884 842522 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
885 : iter.cur);
886 :
887 842522 : if (seginfo->action != GIN_SEGMENT_UNMODIFIED)
888 49508 : nmodified++;
889 : }
890 :
891 : walbufbegin =
892 49412 : palloc(sizeof(ginxlogRecompressDataLeaf) +
893 : BLCKSZ + /* max size needed to hold the segment data */
894 49412 : nmodified * 2 /* (segno + action) per action */
895 : );
896 49412 : walbufend = walbufbegin;
897 :
898 49412 : recompress_xlog = (ginxlogRecompressDataLeaf *) walbufend;
899 49412 : walbufend += sizeof(ginxlogRecompressDataLeaf);
900 :
901 49412 : recompress_xlog->nactions = nmodified;
902 :
903 49412 : segno = 0;
904 891934 : dlist_foreach(iter, &leaf->segments)
905 : {
906 842522 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
907 : iter.cur);
908 842522 : int segsize = 0;
909 : int datalen;
910 842522 : uint8 action = seginfo->action;
911 :
912 842522 : if (action == GIN_SEGMENT_UNMODIFIED)
913 : {
914 793014 : segno++;
915 793014 : continue;
916 : }
917 :
918 49508 : if (action != GIN_SEGMENT_DELETE)
919 49472 : segsize = SizeOfGinPostingList(seginfo->seg);
920 :
921 : /*
922 : * If storing the uncompressed list of added item pointers would take
923 : * more space than storing the compressed segment as is, do that
924 : * instead.
925 : */
926 49508 : if (action == GIN_SEGMENT_ADDITEMS &&
927 49160 : seginfo->nmodifieditems * sizeof(ItemPointerData) > segsize)
928 : {
929 0 : action = GIN_SEGMENT_REPLACE;
930 : }
931 :
932 49508 : *((uint8 *) (walbufend++)) = segno;
933 49508 : *(walbufend++) = action;
934 :
935 49508 : switch (action)
936 : {
937 36 : case GIN_SEGMENT_DELETE:
938 36 : datalen = 0;
939 36 : break;
940 :
941 49160 : case GIN_SEGMENT_ADDITEMS:
942 49160 : datalen = seginfo->nmodifieditems * sizeof(ItemPointerData);
943 49160 : memcpy(walbufend, &seginfo->nmodifieditems, sizeof(uint16));
944 49160 : memcpy(walbufend + sizeof(uint16), seginfo->modifieditems, datalen);
945 49160 : datalen += sizeof(uint16);
946 49160 : break;
947 :
948 312 : case GIN_SEGMENT_INSERT:
949 : case GIN_SEGMENT_REPLACE:
950 312 : datalen = SHORTALIGN(segsize);
951 312 : memcpy(walbufend, seginfo->seg, segsize);
952 312 : break;
953 :
954 0 : default:
955 0 : elog(ERROR, "unexpected GIN leaf action %d", action);
956 : }
957 49508 : walbufend += datalen;
958 :
959 49508 : if (action != GIN_SEGMENT_INSERT)
960 49226 : segno++;
961 : }
962 :
963 : /* Pass back the constructed info via *leaf */
964 49412 : leaf->walinfo = walbufbegin;
965 49412 : leaf->walinfolen = walbufend - walbufbegin;
966 49412 : }
967 :
968 : /*
969 : * Assemble a disassembled posting tree leaf page back to a buffer.
970 : *
971 : * This just updates the target buffer; WAL stuff is caller's responsibility.
972 : *
973 : * NOTE: The segment pointers must not point directly to the same buffer,
974 : * except for segments that have not been modified and whose preceding
975 : * segments have not been modified either.
976 : */
977 : static void
978 49448 : dataPlaceToPageLeafRecompress(Buffer buf, disassembledLeaf *leaf)
979 : {
980 49448 : Page page = BufferGetPage(buf);
981 : char *ptr;
982 : int newsize;
983 49448 : bool modified = false;
984 : dlist_iter iter;
985 : int segsize;
986 :
987 : /*
988 : * If the page was in pre-9.4 format before, convert the header, and force
989 : * all segments to be copied to the page whether they were modified or
990 : * not.
991 : */
992 49448 : if (!GinPageIsCompressed(page))
993 : {
994 : Assert(leaf->oldformat);
995 0 : GinPageSetCompressed(page);
996 0 : GinPageGetOpaque(page)->maxoff = InvalidOffsetNumber;
997 0 : modified = true;
998 : }
999 :
1000 49448 : ptr = (char *) GinDataLeafPageGetPostingList(page);
1001 49448 : newsize = 0;
1002 892816 : dlist_foreach(iter, &leaf->segments)
1003 : {
1004 843368 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node, iter.cur);
1005 :
1006 843368 : if (seginfo->action != GIN_SEGMENT_UNMODIFIED)
1007 50354 : modified = true;
1008 :
1009 843368 : if (seginfo->action != GIN_SEGMENT_DELETE)
1010 : {
1011 842492 : segsize = SizeOfGinPostingList(seginfo->seg);
1012 :
1013 842492 : if (modified)
1014 49532 : memcpy(ptr, seginfo->seg, segsize);
1015 :
1016 842492 : ptr += segsize;
1017 842492 : newsize += segsize;
1018 : }
1019 : }
1020 :
1021 : Assert(newsize <= GinDataPageMaxDataSize);
1022 49448 : GinDataPageSetDataSize(page, newsize);
1023 49448 : }
1024 :
1025 : /*
1026 : * Like dataPlaceToPageLeafRecompress, but writes the disassembled leaf
1027 : * segments to two pages instead of one.
1028 : *
1029 : * This is different from the non-split cases in that this does not modify
1030 : * the original page directly, but writes to temporary in-memory copies of
1031 : * the new left and right pages.
1032 : */
1033 : static void
1034 150 : dataPlaceToPageLeafSplit(disassembledLeaf *leaf,
1035 : ItemPointerData lbound, ItemPointerData rbound,
1036 : Page lpage, Page rpage)
1037 : {
1038 : char *ptr;
1039 : int segsize;
1040 : int lsize;
1041 : int rsize;
1042 : dlist_node *node;
1043 : dlist_node *firstright;
1044 : leafSegmentInfo *seginfo;
1045 :
1046 : /* Initialize temporary pages to hold the new left and right pages */
1047 150 : GinInitPage(lpage, GIN_DATA | GIN_LEAF | GIN_COMPRESSED, BLCKSZ);
1048 150 : GinInitPage(rpage, GIN_DATA | GIN_LEAF | GIN_COMPRESSED, BLCKSZ);
1049 :
1050 : /*
1051 : * Copy the segments that go to the left page.
1052 : *
1053 : * XXX: We should skip copying the unmodified part of the left page, like
1054 : * we do when recompressing.
1055 : */
1056 150 : lsize = 0;
1057 150 : ptr = (char *) GinDataLeafPageGetPostingList(lpage);
1058 150 : firstright = dlist_next_node(&leaf->segments, leaf->lastleft);
1059 3586 : for (node = dlist_head_node(&leaf->segments);
1060 : node != firstright;
1061 3436 : node = dlist_next_node(&leaf->segments, node))
1062 : {
1063 3436 : seginfo = dlist_container(leafSegmentInfo, node, node);
1064 :
1065 3436 : if (seginfo->action != GIN_SEGMENT_DELETE)
1066 : {
1067 3436 : segsize = SizeOfGinPostingList(seginfo->seg);
1068 3436 : memcpy(ptr, seginfo->seg, segsize);
1069 3436 : ptr += segsize;
1070 3436 : lsize += segsize;
1071 : }
1072 : }
1073 : Assert(lsize == leaf->lsize);
1074 150 : GinDataPageSetDataSize(lpage, lsize);
1075 150 : *GinDataPageGetRightBound(lpage) = lbound;
1076 :
1077 : /* Copy the segments that go to the right page */
1078 150 : ptr = (char *) GinDataLeafPageGetPostingList(rpage);
1079 150 : rsize = 0;
1080 150 : for (node = firstright;
1081 : ;
1082 1944 : node = dlist_next_node(&leaf->segments, node))
1083 : {
1084 2094 : seginfo = dlist_container(leafSegmentInfo, node, node);
1085 :
1086 2094 : if (seginfo->action != GIN_SEGMENT_DELETE)
1087 : {
1088 2094 : segsize = SizeOfGinPostingList(seginfo->seg);
1089 2094 : memcpy(ptr, seginfo->seg, segsize);
1090 2094 : ptr += segsize;
1091 2094 : rsize += segsize;
1092 : }
1093 :
1094 2094 : if (!dlist_has_next(&leaf->segments, node))
1095 150 : break;
1096 : }
1097 : Assert(rsize == leaf->rsize);
1098 150 : GinDataPageSetDataSize(rpage, rsize);
1099 150 : *GinDataPageGetRightBound(rpage) = rbound;
1100 150 : }
1101 :
1102 : /*
1103 : * Prepare to insert data on an internal data page.
1104 : *
1105 : * If it will fit, return GPTP_INSERT after doing whatever setup is needed
1106 : * before we enter the insertion critical section. *ptp_workspace can be
1107 : * set to pass information along to the execPlaceToPage function.
1108 : *
1109 : * If it won't fit, perform a page split and return two temporary page
1110 : * images into *newlpage and *newrpage, with result GPTP_SPLIT.
1111 : *
1112 : * In neither case should the given page buffer be modified here.
1113 : *
1114 : * Note: on insertion to an internal node, in addition to inserting the given
1115 : * item, the downlink of the existing item at stack->off will be updated to
1116 : * point to updateblkno.
1117 : */
1118 : static GinPlaceToPageRC
1119 46 : dataBeginPlaceToPageInternal(GinBtree btree, Buffer buf, GinBtreeStack *stack,
1120 : void *insertdata, BlockNumber updateblkno,
1121 : void **ptp_workspace,
1122 : Page *newlpage, Page *newrpage)
1123 : {
1124 46 : Page page = BufferGetPage(buf);
1125 :
1126 : /* If it doesn't fit, deal with split case */
1127 46 : if (GinNonLeafDataPageGetFreeSpace(page) < sizeof(PostingItem))
1128 : {
1129 0 : dataSplitPageInternal(btree, buf, stack, insertdata, updateblkno,
1130 : newlpage, newrpage);
1131 0 : return GPTP_SPLIT;
1132 : }
1133 :
1134 : /* Else, we're ready to proceed with insertion */
1135 46 : return GPTP_INSERT;
1136 : }
1137 :
1138 : /*
1139 : * Perform data insertion after beginPlaceToPage has decided it will fit.
1140 : *
1141 : * This is invoked within a critical section, and XLOG record creation (if
1142 : * needed) is already started. The target buffer is registered in slot 0.
1143 : */
1144 : static void
1145 46 : dataExecPlaceToPageInternal(GinBtree btree, Buffer buf, GinBtreeStack *stack,
1146 : void *insertdata, BlockNumber updateblkno,
1147 : void *ptp_workspace)
1148 : {
1149 46 : Page page = BufferGetPage(buf);
1150 46 : OffsetNumber off = stack->off;
1151 : PostingItem *pitem;
1152 :
1153 : /* Update existing downlink to point to next page (on internal page) */
1154 46 : pitem = GinDataPageGetPostingItem(page, off);
1155 46 : PostingItemSetBlockNumber(pitem, updateblkno);
1156 :
1157 : /* Add new item */
1158 46 : pitem = (PostingItem *) insertdata;
1159 46 : GinDataPageAddPostingItem(page, pitem, off);
1160 :
1161 46 : MarkBufferDirty(buf);
1162 :
1163 46 : if (RelationNeedsWAL(btree->index) && !btree->isBuild)
1164 : {
1165 : /*
1166 : * This must be static, because it has to survive until XLogInsert,
1167 : * and we can't palloc here. Ugly, but the XLogInsert infrastructure
1168 : * isn't reentrant anyway.
1169 : */
1170 : static ginxlogInsertDataInternal data;
1171 :
1172 18 : data.offset = off;
1173 18 : data.newitem = *pitem;
1174 :
1175 18 : XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
1176 18 : XLogRegisterBufData(0, (char *) &data,
1177 : sizeof(ginxlogInsertDataInternal));
1178 : }
1179 46 : }
1180 :
1181 : /*
1182 : * Prepare to insert data on a posting-tree data page.
1183 : *
1184 : * If it will fit, return GPTP_INSERT after doing whatever setup is needed
1185 : * before we enter the insertion critical section. *ptp_workspace can be
1186 : * set to pass information along to the execPlaceToPage function.
1187 : *
1188 : * If it won't fit, perform a page split and return two temporary page
1189 : * images into *newlpage and *newrpage, with result GPTP_SPLIT.
1190 : *
1191 : * In neither case should the given page buffer be modified here.
1192 : *
1193 : * Note: on insertion to an internal node, in addition to inserting the given
1194 : * item, the downlink of the existing item at stack->off will be updated to
1195 : * point to updateblkno.
1196 : *
1197 : * Calls relevant function for internal or leaf page because they are handled
1198 : * very differently.
1199 : */
1200 : static GinPlaceToPageRC
1201 49596 : dataBeginPlaceToPage(GinBtree btree, Buffer buf, GinBtreeStack *stack,
1202 : void *insertdata, BlockNumber updateblkno,
1203 : void **ptp_workspace,
1204 : Page *newlpage, Page *newrpage)
1205 : {
1206 49596 : Page page = BufferGetPage(buf);
1207 :
1208 : Assert(GinPageIsData(page));
1209 :
1210 49596 : if (GinPageIsLeaf(page))
1211 49550 : return dataBeginPlaceToPageLeaf(btree, buf, stack, insertdata,
1212 : ptp_workspace,
1213 : newlpage, newrpage);
1214 : else
1215 46 : return dataBeginPlaceToPageInternal(btree, buf, stack,
1216 : insertdata, updateblkno,
1217 : ptp_workspace,
1218 : newlpage, newrpage);
1219 : }
1220 :
1221 : /*
1222 : * Perform data insertion after beginPlaceToPage has decided it will fit.
1223 : *
1224 : * This is invoked within a critical section, and XLOG record creation (if
1225 : * needed) is already started. The target buffer is registered in slot 0.
1226 : *
1227 : * Calls relevant function for internal or leaf page because they are handled
1228 : * very differently.
1229 : */
1230 : static void
1231 49446 : dataExecPlaceToPage(GinBtree btree, Buffer buf, GinBtreeStack *stack,
1232 : void *insertdata, BlockNumber updateblkno,
1233 : void *ptp_workspace)
1234 : {
1235 49446 : Page page = BufferGetPage(buf);
1236 :
1237 49446 : if (GinPageIsLeaf(page))
1238 49400 : dataExecPlaceToPageLeaf(btree, buf, stack, insertdata,
1239 : ptp_workspace);
1240 : else
1241 46 : dataExecPlaceToPageInternal(btree, buf, stack, insertdata,
1242 : updateblkno, ptp_workspace);
1243 49446 : }
1244 :
1245 : /*
1246 : * Split internal page and insert new data.
1247 : *
1248 : * Returns new temp pages to *newlpage and *newrpage.
1249 : * The original buffer is left untouched.
1250 : */
1251 : static void
1252 0 : dataSplitPageInternal(GinBtree btree, Buffer origbuf,
1253 : GinBtreeStack *stack,
1254 : void *insertdata, BlockNumber updateblkno,
1255 : Page *newlpage, Page *newrpage)
1256 : {
1257 0 : Page oldpage = BufferGetPage(origbuf);
1258 0 : OffsetNumber off = stack->off;
1259 0 : int nitems = GinPageGetOpaque(oldpage)->maxoff;
1260 : int nleftitems;
1261 : int nrightitems;
1262 0 : Size pageSize = PageGetPageSize(oldpage);
1263 0 : ItemPointerData oldbound = *GinDataPageGetRightBound(oldpage);
1264 : ItemPointer bound;
1265 : Page lpage;
1266 : Page rpage;
1267 : OffsetNumber separator;
1268 : PostingItem allitems[(BLCKSZ / sizeof(PostingItem)) + 1];
1269 :
1270 0 : lpage = PageGetTempPage(oldpage);
1271 0 : rpage = PageGetTempPage(oldpage);
1272 0 : GinInitPage(lpage, GinPageGetOpaque(oldpage)->flags, pageSize);
1273 0 : GinInitPage(rpage, GinPageGetOpaque(oldpage)->flags, pageSize);
1274 :
1275 : /*
1276 : * First construct a new list of PostingItems, which includes all the old
1277 : * items, and the new item.
1278 : */
1279 0 : memcpy(allitems, GinDataPageGetPostingItem(oldpage, FirstOffsetNumber),
1280 0 : (off - 1) * sizeof(PostingItem));
1281 :
1282 0 : allitems[off - 1] = *((PostingItem *) insertdata);
1283 0 : memcpy(&allitems[off], GinDataPageGetPostingItem(oldpage, off),
1284 0 : (nitems - (off - 1)) * sizeof(PostingItem));
1285 0 : nitems++;
1286 :
1287 : /* Update existing downlink to point to next page */
1288 0 : PostingItemSetBlockNumber(&allitems[off], updateblkno);
1289 :
1290 : /*
1291 : * When creating a new index, fit as many tuples as possible on the left
1292 : * page, on the assumption that the table is scanned from beginning to
1293 : * end. This packs the index as tight as possible.
1294 : */
1295 0 : if (btree->isBuild && GinPageRightMost(oldpage))
1296 0 : separator = GinNonLeafDataPageGetFreeSpace(rpage) / sizeof(PostingItem);
1297 : else
1298 0 : separator = nitems / 2;
1299 0 : nleftitems = separator;
1300 0 : nrightitems = nitems - separator;
1301 :
1302 0 : memcpy(GinDataPageGetPostingItem(lpage, FirstOffsetNumber),
1303 : allitems,
1304 : nleftitems * sizeof(PostingItem));
1305 0 : GinPageGetOpaque(lpage)->maxoff = nleftitems;
1306 0 : memcpy(GinDataPageGetPostingItem(rpage, FirstOffsetNumber),
1307 0 : &allitems[separator],
1308 : nrightitems * sizeof(PostingItem));
1309 0 : GinPageGetOpaque(rpage)->maxoff = nrightitems;
1310 :
1311 : /*
1312 : * Also set pd_lower for both pages, like GinDataPageAddPostingItem does.
1313 : */
1314 0 : GinDataPageSetDataSize(lpage, nleftitems * sizeof(PostingItem));
1315 0 : GinDataPageSetDataSize(rpage, nrightitems * sizeof(PostingItem));
1316 :
1317 : /* set up right bound for left page */
1318 0 : bound = GinDataPageGetRightBound(lpage);
1319 0 : *bound = GinDataPageGetPostingItem(lpage, nleftitems)->key;
1320 :
1321 : /* set up right bound for right page */
1322 0 : *GinDataPageGetRightBound(rpage) = oldbound;
1323 :
1324 : /* return temp pages to caller */
1325 0 : *newlpage = lpage;
1326 0 : *newrpage = rpage;
1327 0 : }
1328 :
1329 : /*
1330 : * Construct insertion payload for inserting the downlink for given buffer.
1331 : */
1332 : static void *
1333 46 : dataPrepareDownlink(GinBtree btree, Buffer lbuf)
1334 : {
1335 46 : PostingItem *pitem = palloc(sizeof(PostingItem));
1336 46 : Page lpage = BufferGetPage(lbuf);
1337 :
1338 46 : PostingItemSetBlockNumber(pitem, BufferGetBlockNumber(lbuf));
1339 46 : pitem->key = *GinDataPageGetRightBound(lpage);
1340 :
1341 46 : return pitem;
1342 : }
1343 :
1344 : /*
1345 : * Fills new root by right bound values from child.
1346 : * Also called from ginxlog, should not use btree
1347 : */
1348 : void
1349 104 : ginDataFillRoot(GinBtree btree, Page root, BlockNumber lblkno, Page lpage, BlockNumber rblkno, Page rpage)
1350 : {
1351 : PostingItem li,
1352 : ri;
1353 :
1354 104 : li.key = *GinDataPageGetRightBound(lpage);
1355 104 : PostingItemSetBlockNumber(&li, lblkno);
1356 104 : GinDataPageAddPostingItem(root, &li, InvalidOffsetNumber);
1357 :
1358 104 : ri.key = *GinDataPageGetRightBound(rpage);
1359 104 : PostingItemSetBlockNumber(&ri, rblkno);
1360 104 : GinDataPageAddPostingItem(root, &ri, InvalidOffsetNumber);
1361 104 : }
1362 :
1363 :
1364 : /*** Functions to work with disassembled leaf pages ***/
1365 :
1366 : /*
1367 : * Disassemble page into a disassembledLeaf struct.
1368 : */
1369 : static disassembledLeaf *
1370 49598 : disassembleLeaf(Page page)
1371 : {
1372 : disassembledLeaf *leaf;
1373 : GinPostingList *seg;
1374 : Pointer segbegin;
1375 : Pointer segend;
1376 :
1377 49598 : leaf = palloc0(sizeof(disassembledLeaf));
1378 49598 : dlist_init(&leaf->segments);
1379 :
1380 49598 : if (GinPageIsCompressed(page))
1381 : {
1382 : /*
1383 : * Create a leafSegmentInfo entry for each segment.
1384 : */
1385 49598 : seg = GinDataLeafPageGetPostingList(page);
1386 49598 : segbegin = (Pointer) seg;
1387 49598 : segend = segbegin + GinDataLeafPageGetPostingListSize(page);
1388 896332 : while ((Pointer) seg < segend)
1389 : {
1390 846734 : leafSegmentInfo *seginfo = palloc(sizeof(leafSegmentInfo));
1391 :
1392 846734 : seginfo->action = GIN_SEGMENT_UNMODIFIED;
1393 846734 : seginfo->seg = seg;
1394 846734 : seginfo->items = NULL;
1395 846734 : seginfo->nitems = 0;
1396 846734 : dlist_push_tail(&leaf->segments, &seginfo->node);
1397 :
1398 846734 : seg = GinNextPostingListSegment(seg);
1399 : }
1400 49598 : leaf->oldformat = false;
1401 : }
1402 : else
1403 : {
1404 : /*
1405 : * A pre-9.4 format uncompressed page is represented by a single
1406 : * segment, with an array of items. The corner case is uncompressed
1407 : * page containing no items, which is represented as no segments.
1408 : */
1409 : ItemPointer uncompressed;
1410 : int nuncompressed;
1411 : leafSegmentInfo *seginfo;
1412 :
1413 0 : uncompressed = dataLeafPageGetUncompressed(page, &nuncompressed);
1414 :
1415 0 : if (nuncompressed > 0)
1416 : {
1417 0 : seginfo = palloc(sizeof(leafSegmentInfo));
1418 :
1419 0 : seginfo->action = GIN_SEGMENT_REPLACE;
1420 0 : seginfo->seg = NULL;
1421 0 : seginfo->items = palloc(nuncompressed * sizeof(ItemPointerData));
1422 0 : memcpy(seginfo->items, uncompressed, nuncompressed * sizeof(ItemPointerData));
1423 0 : seginfo->nitems = nuncompressed;
1424 :
1425 0 : dlist_push_tail(&leaf->segments, &seginfo->node);
1426 : }
1427 :
1428 0 : leaf->oldformat = true;
1429 : }
1430 :
1431 49598 : return leaf;
1432 : }
1433 :
1434 : /*
1435 : * Distribute newItems to the segments.
1436 : *
1437 : * Any segments that acquire new items are decoded, and the new items are
1438 : * merged with the old items.
1439 : *
1440 : * Returns true if any new items were added. False means they were all
1441 : * duplicates of existing items on the page.
1442 : */
1443 : static bool
1444 49550 : addItemsToLeaf(disassembledLeaf *leaf, ItemPointer newItems, int nNewItems)
1445 : {
1446 : dlist_iter iter;
1447 49550 : ItemPointer nextnew = newItems;
1448 49550 : int newleft = nNewItems;
1449 49550 : bool modified = false;
1450 : leafSegmentInfo *newseg;
1451 :
1452 : /*
1453 : * If the page is completely empty, just construct one new segment to hold
1454 : * all the new items.
1455 : */
1456 49550 : if (dlist_is_empty(&leaf->segments))
1457 : {
1458 0 : newseg = palloc(sizeof(leafSegmentInfo));
1459 0 : newseg->seg = NULL;
1460 0 : newseg->items = newItems;
1461 0 : newseg->nitems = nNewItems;
1462 0 : newseg->action = GIN_SEGMENT_INSERT;
1463 0 : dlist_push_tail(&leaf->segments, &newseg->node);
1464 0 : return true;
1465 : }
1466 :
1467 845780 : dlist_foreach(iter, &leaf->segments)
1468 : {
1469 845780 : leafSegmentInfo *cur = (leafSegmentInfo *) dlist_container(leafSegmentInfo, node, iter.cur);
1470 : int nthis;
1471 : ItemPointer tmpitems;
1472 : int ntmpitems;
1473 :
1474 : /*
1475 : * How many of the new items fall into this segment?
1476 : */
1477 845780 : if (!dlist_has_next(&leaf->segments, iter.cur))
1478 49550 : nthis = newleft;
1479 : else
1480 : {
1481 : leafSegmentInfo *next;
1482 : ItemPointerData next_first;
1483 :
1484 796230 : next = (leafSegmentInfo *) dlist_container(leafSegmentInfo, node,
1485 : dlist_next_node(&leaf->segments, iter.cur));
1486 796230 : if (next->items)
1487 49538 : next_first = next->items[0];
1488 : else
1489 : {
1490 : Assert(next->seg != NULL);
1491 746692 : next_first = next->seg->first;
1492 : }
1493 :
1494 796230 : nthis = 0;
1495 796230 : while (nthis < newleft && ginCompareItemPointers(&nextnew[nthis], &next_first) < 0)
1496 0 : nthis++;
1497 : }
1498 845780 : if (nthis == 0)
1499 796230 : continue;
1500 :
1501 : /* Merge the new items with the existing items. */
1502 49550 : if (!cur->items)
1503 0 : cur->items = ginPostingListDecode(cur->seg, &cur->nitems);
1504 :
1505 : /*
1506 : * Fast path for the important special case that we're appending to
1507 : * the end of the page: don't let the last segment on the page grow
1508 : * larger than the target, create a new segment before that happens.
1509 : */
1510 99100 : if (!dlist_has_next(&leaf->segments, iter.cur) &&
1511 49550 : ginCompareItemPointers(&cur->items[cur->nitems - 1], &nextnew[0]) < 0 &&
1512 49550 : cur->seg != NULL &&
1513 49550 : SizeOfGinPostingList(cur->seg) >= GinPostingListSegmentTargetSize)
1514 : {
1515 368 : newseg = palloc(sizeof(leafSegmentInfo));
1516 368 : newseg->seg = NULL;
1517 368 : newseg->items = nextnew;
1518 368 : newseg->nitems = nthis;
1519 368 : newseg->action = GIN_SEGMENT_INSERT;
1520 368 : dlist_push_tail(&leaf->segments, &newseg->node);
1521 368 : modified = true;
1522 49550 : break;
1523 : }
1524 :
1525 49182 : tmpitems = ginMergeItemPointers(cur->items, cur->nitems,
1526 : nextnew, nthis,
1527 : &ntmpitems);
1528 49182 : if (ntmpitems != cur->nitems)
1529 : {
1530 : /*
1531 : * If there are no duplicates, track the added items so that we
1532 : * can emit a compact ADDITEMS WAL record later on. (it doesn't
1533 : * seem worth re-checking which items were duplicates, if there
1534 : * were any)
1535 : */
1536 49182 : if (ntmpitems == nthis + cur->nitems &&
1537 49182 : cur->action == GIN_SEGMENT_UNMODIFIED)
1538 : {
1539 49182 : cur->action = GIN_SEGMENT_ADDITEMS;
1540 49182 : cur->modifieditems = nextnew;
1541 49182 : cur->nmodifieditems = nthis;
1542 : }
1543 : else
1544 0 : cur->action = GIN_SEGMENT_REPLACE;
1545 :
1546 49182 : cur->items = tmpitems;
1547 49182 : cur->nitems = ntmpitems;
1548 49182 : cur->seg = NULL;
1549 49182 : modified = true;
1550 : }
1551 :
1552 49182 : nextnew += nthis;
1553 49182 : newleft -= nthis;
1554 49182 : if (newleft == 0)
1555 49182 : break;
1556 : }
1557 :
1558 49550 : return modified;
1559 : }
1560 :
1561 : /*
1562 : * Recompresses all segments that have been modified.
1563 : *
1564 : * If not all the items fit on two pages (ie. after split), we store as
1565 : * many items as fit, and set *remaining to the first item that didn't fit.
1566 : * If all items fit, *remaining is set to invalid.
1567 : *
1568 : * Returns true if the page has to be split.
1569 : */
1570 : static bool
1571 49550 : leafRepackItems(disassembledLeaf *leaf, ItemPointer remaining)
1572 : {
1573 49550 : int pgused = 0;
1574 49550 : bool needsplit = false;
1575 : dlist_iter iter;
1576 : int segsize;
1577 : leafSegmentInfo *nextseg;
1578 : int npacked;
1579 : bool modified;
1580 : dlist_node *cur_node;
1581 : dlist_node *next_node;
1582 :
1583 49550 : ItemPointerSetInvalid(remaining);
1584 :
1585 : /*
1586 : * cannot use dlist_foreach_modify here because we insert adjacent items
1587 : * while iterating.
1588 : */
1589 897494 : for (cur_node = dlist_head_node(&leaf->segments);
1590 : cur_node != NULL;
1591 847944 : cur_node = next_node)
1592 : {
1593 847984 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
1594 : cur_node);
1595 :
1596 847984 : if (dlist_has_next(&leaf->segments, cur_node))
1597 796598 : next_node = dlist_next_node(&leaf->segments, cur_node);
1598 : else
1599 51386 : next_node = NULL;
1600 :
1601 : /* Compress the posting list, if necessary */
1602 847984 : if (seginfo->action != GIN_SEGMENT_DELETE)
1603 : {
1604 847984 : if (seginfo->seg == NULL)
1605 : {
1606 51386 : if (seginfo->nitems > GinPostingListSegmentMaxSize)
1607 1870 : npacked = 0; /* no chance that it would fit. */
1608 : else
1609 : {
1610 49516 : seginfo->seg = ginCompressPostingList(seginfo->items,
1611 : seginfo->nitems,
1612 : GinPostingListSegmentMaxSize,
1613 : &npacked);
1614 : }
1615 51386 : if (npacked != seginfo->nitems)
1616 : {
1617 : /*
1618 : * Too large. Compress again to the target size, and
1619 : * create a new segment to represent the remaining items.
1620 : * The new segment is inserted after this one, so it will
1621 : * be processed in the next iteration of this loop.
1622 : */
1623 1876 : if (seginfo->seg)
1624 6 : pfree(seginfo->seg);
1625 1876 : seginfo->seg = ginCompressPostingList(seginfo->items,
1626 : seginfo->nitems,
1627 : GinPostingListSegmentTargetSize,
1628 : &npacked);
1629 1876 : if (seginfo->action != GIN_SEGMENT_INSERT)
1630 12 : seginfo->action = GIN_SEGMENT_REPLACE;
1631 :
1632 1876 : nextseg = palloc(sizeof(leafSegmentInfo));
1633 1876 : nextseg->action = GIN_SEGMENT_INSERT;
1634 1876 : nextseg->seg = NULL;
1635 1876 : nextseg->items = &seginfo->items[npacked];
1636 1876 : nextseg->nitems = seginfo->nitems - npacked;
1637 1876 : next_node = &nextseg->node;
1638 1876 : dlist_insert_after(cur_node, next_node);
1639 : }
1640 : }
1641 :
1642 : /*
1643 : * If the segment is very small, merge it with the next segment.
1644 : */
1645 847984 : if (SizeOfGinPostingList(seginfo->seg) < GinPostingListSegmentMinSize && next_node)
1646 : {
1647 : int nmerged;
1648 :
1649 0 : nextseg = dlist_container(leafSegmentInfo, node, next_node);
1650 :
1651 0 : if (seginfo->items == NULL)
1652 0 : seginfo->items = ginPostingListDecode(seginfo->seg,
1653 : &seginfo->nitems);
1654 0 : if (nextseg->items == NULL)
1655 0 : nextseg->items = ginPostingListDecode(nextseg->seg,
1656 : &nextseg->nitems);
1657 0 : nextseg->items =
1658 0 : ginMergeItemPointers(seginfo->items, seginfo->nitems,
1659 0 : nextseg->items, nextseg->nitems,
1660 : &nmerged);
1661 : Assert(nmerged == seginfo->nitems + nextseg->nitems);
1662 0 : nextseg->nitems = nmerged;
1663 0 : nextseg->seg = NULL;
1664 :
1665 0 : nextseg->action = GIN_SEGMENT_REPLACE;
1666 0 : nextseg->modifieditems = NULL;
1667 0 : nextseg->nmodifieditems = 0;
1668 :
1669 0 : if (seginfo->action == GIN_SEGMENT_INSERT)
1670 : {
1671 0 : dlist_delete(cur_node);
1672 0 : continue;
1673 : }
1674 : else
1675 : {
1676 0 : seginfo->action = GIN_SEGMENT_DELETE;
1677 0 : seginfo->seg = NULL;
1678 : }
1679 : }
1680 :
1681 847984 : seginfo->items = NULL;
1682 847984 : seginfo->nitems = 0;
1683 : }
1684 :
1685 847984 : if (seginfo->action == GIN_SEGMENT_DELETE)
1686 0 : continue;
1687 :
1688 : /*
1689 : * OK, we now have a compressed version of this segment ready for
1690 : * copying to the page. Did we exceed the size that fits on one page?
1691 : */
1692 847984 : segsize = SizeOfGinPostingList(seginfo->seg);
1693 847984 : if (pgused + segsize > GinDataPageMaxDataSize)
1694 : {
1695 190 : if (!needsplit)
1696 : {
1697 : /* switch to right page */
1698 : Assert(pgused > 0);
1699 150 : leaf->lastleft = dlist_prev_node(&leaf->segments, cur_node);
1700 150 : needsplit = true;
1701 150 : leaf->lsize = pgused;
1702 150 : pgused = 0;
1703 : }
1704 : else
1705 : {
1706 : /*
1707 : * Filled both pages. The last segment we constructed did not
1708 : * fit.
1709 : */
1710 40 : *remaining = seginfo->seg->first;
1711 :
1712 : /*
1713 : * remove all segments that did not fit from the list.
1714 : */
1715 80 : while (dlist_has_next(&leaf->segments, cur_node))
1716 40 : dlist_delete(dlist_next_node(&leaf->segments, cur_node));
1717 40 : dlist_delete(cur_node);
1718 40 : break;
1719 : }
1720 : }
1721 :
1722 847944 : pgused += segsize;
1723 : }
1724 :
1725 49550 : if (!needsplit)
1726 : {
1727 49400 : leaf->lsize = pgused;
1728 49400 : leaf->rsize = 0;
1729 : }
1730 : else
1731 150 : leaf->rsize = pgused;
1732 :
1733 : Assert(leaf->lsize <= GinDataPageMaxDataSize);
1734 : Assert(leaf->rsize <= GinDataPageMaxDataSize);
1735 :
1736 : /*
1737 : * Make a palloc'd copy of every segment after the first modified one,
1738 : * because as we start copying items to the original page, we might
1739 : * overwrite an existing segment.
1740 : */
1741 49550 : modified = false;
1742 897494 : dlist_foreach(iter, &leaf->segments)
1743 : {
1744 847944 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
1745 : iter.cur);
1746 :
1747 847944 : if (!modified && seginfo->action != GIN_SEGMENT_UNMODIFIED)
1748 : {
1749 49550 : modified = true;
1750 : }
1751 798394 : else if (modified && seginfo->action == GIN_SEGMENT_UNMODIFIED)
1752 : {
1753 : GinPostingList *tmp;
1754 :
1755 0 : segsize = SizeOfGinPostingList(seginfo->seg);
1756 0 : tmp = palloc(segsize);
1757 0 : memcpy(tmp, seginfo->seg, segsize);
1758 0 : seginfo->seg = tmp;
1759 : }
1760 : }
1761 :
1762 49550 : return needsplit;
1763 : }
1764 :
1765 :
1766 : /*** Functions that are exported to the rest of the GIN code ***/
1767 :
1768 : /*
1769 : * Creates new posting tree containing the given TIDs. Returns the page
1770 : * number of the root of the new posting tree.
1771 : *
1772 : * items[] must be in sorted order with no duplicates.
1773 : */
1774 : BlockNumber
1775 122 : createPostingTree(Relation index, ItemPointerData *items, uint32 nitems,
1776 : GinStatsData *buildStats, Buffer entrybuffer)
1777 : {
1778 : BlockNumber blkno;
1779 : Buffer buffer;
1780 : Page tmppage;
1781 : Page page;
1782 : Pointer ptr;
1783 : int nrootitems;
1784 : int rootsize;
1785 122 : bool is_build = (buildStats != NULL);
1786 :
1787 : /* Construct the new root page in memory first. */
1788 122 : tmppage = (Page) palloc(BLCKSZ);
1789 122 : GinInitPage(tmppage, GIN_DATA | GIN_LEAF | GIN_COMPRESSED, BLCKSZ);
1790 122 : GinPageGetOpaque(tmppage)->rightlink = InvalidBlockNumber;
1791 :
1792 : /*
1793 : * Write as many of the items to the root page as fit. In segments of max
1794 : * GinPostingListSegmentMaxSize bytes each.
1795 : */
1796 122 : nrootitems = 0;
1797 122 : rootsize = 0;
1798 122 : ptr = (Pointer) GinDataLeafPageGetPostingList(tmppage);
1799 2374 : while (nrootitems < nitems)
1800 : {
1801 : GinPostingList *segment;
1802 : int npacked;
1803 : int segsize;
1804 :
1805 2352 : segment = ginCompressPostingList(&items[nrootitems],
1806 2352 : nitems - nrootitems,
1807 : GinPostingListSegmentMaxSize,
1808 : &npacked);
1809 2352 : segsize = SizeOfGinPostingList(segment);
1810 2352 : if (rootsize + segsize > GinDataPageMaxDataSize)
1811 100 : break;
1812 :
1813 2252 : memcpy(ptr, segment, segsize);
1814 2252 : ptr += segsize;
1815 2252 : rootsize += segsize;
1816 2252 : nrootitems += npacked;
1817 2252 : pfree(segment);
1818 : }
1819 122 : GinDataPageSetDataSize(tmppage, rootsize);
1820 :
1821 : /*
1822 : * All set. Get a new physical page, and copy the in-memory page to it.
1823 : */
1824 122 : buffer = GinNewBuffer(index);
1825 122 : page = BufferGetPage(buffer);
1826 122 : blkno = BufferGetBlockNumber(buffer);
1827 :
1828 : /*
1829 : * Copy any predicate locks from the entry tree leaf (containing posting
1830 : * list) to the posting tree.
1831 : */
1832 122 : PredicateLockPageSplit(index, BufferGetBlockNumber(entrybuffer), blkno);
1833 :
1834 122 : START_CRIT_SECTION();
1835 :
1836 122 : PageRestoreTempPage(tmppage, page);
1837 122 : MarkBufferDirty(buffer);
1838 :
1839 122 : if (RelationNeedsWAL(index) && !is_build)
1840 : {
1841 : XLogRecPtr recptr;
1842 : ginxlogCreatePostingTree data;
1843 :
1844 34 : data.size = rootsize;
1845 :
1846 34 : XLogBeginInsert();
1847 34 : XLogRegisterData((char *) &data, sizeof(ginxlogCreatePostingTree));
1848 :
1849 34 : XLogRegisterData((char *) GinDataLeafPageGetPostingList(page),
1850 : rootsize);
1851 34 : XLogRegisterBuffer(0, buffer, REGBUF_WILL_INIT);
1852 :
1853 34 : recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_CREATE_PTREE);
1854 34 : PageSetLSN(page, recptr);
1855 : }
1856 :
1857 122 : UnlockReleaseBuffer(buffer);
1858 :
1859 122 : END_CRIT_SECTION();
1860 :
1861 : /* During index build, count the newly-added data page */
1862 122 : if (buildStats)
1863 76 : buildStats->nDataPages++;
1864 :
1865 122 : elog(DEBUG2, "created GIN posting tree with %d items", nrootitems);
1866 :
1867 : /*
1868 : * Add any remaining TIDs to the newly-created posting tree.
1869 : */
1870 122 : if (nitems > nrootitems)
1871 : {
1872 100 : ginInsertItemPointers(index, blkno,
1873 100 : items + nrootitems,
1874 : nitems - nrootitems,
1875 : buildStats);
1876 : }
1877 :
1878 122 : return blkno;
1879 : }
1880 :
1881 : static void
1882 49590 : ginPrepareDataScan(GinBtree btree, Relation index, BlockNumber rootBlkno)
1883 : {
1884 49590 : memset(btree, 0, sizeof(GinBtreeData));
1885 :
1886 49590 : btree->index = index;
1887 49590 : btree->rootBlkno = rootBlkno;
1888 :
1889 49590 : btree->findChildPage = dataLocateItem;
1890 49590 : btree->getLeftMostChild = dataGetLeftMostPage;
1891 49590 : btree->isMoveRight = dataIsMoveRight;
1892 49590 : btree->findItem = NULL;
1893 49590 : btree->findChildPtr = dataFindChildPtr;
1894 49590 : btree->beginPlaceToPage = dataBeginPlaceToPage;
1895 49590 : btree->execPlaceToPage = dataExecPlaceToPage;
1896 49590 : btree->fillRoot = ginDataFillRoot;
1897 49590 : btree->prepareDownlink = dataPrepareDownlink;
1898 :
1899 49590 : btree->isData = true;
1900 49590 : btree->fullScan = false;
1901 49590 : btree->isBuild = false;
1902 49590 : }
1903 :
1904 : /*
1905 : * Inserts array of item pointers, may execute several tree scan (very rare)
1906 : */
1907 : void
1908 49514 : ginInsertItemPointers(Relation index, BlockNumber rootBlkno,
1909 : ItemPointerData *items, uint32 nitem,
1910 : GinStatsData *buildStats)
1911 : {
1912 : GinBtreeData btree;
1913 : GinBtreeDataLeafInsertData insertdata;
1914 : GinBtreeStack *stack;
1915 :
1916 49514 : ginPrepareDataScan(&btree, index, rootBlkno);
1917 49514 : btree.isBuild = (buildStats != NULL);
1918 49514 : insertdata.items = items;
1919 49514 : insertdata.nitem = nitem;
1920 49514 : insertdata.curitem = 0;
1921 :
1922 99064 : while (insertdata.curitem < insertdata.nitem)
1923 : {
1924 : /* search for the leaf page where the first item should go to */
1925 49554 : btree.itemptr = insertdata.items[insertdata.curitem];
1926 49554 : stack = ginFindLeafPage(&btree, false, true);
1927 :
1928 49550 : ginInsertValue(&btree, stack, &insertdata, buildStats);
1929 : }
1930 49510 : }
1931 :
1932 : /*
1933 : * Starts a new scan on a posting tree.
1934 : */
1935 : GinBtreeStack *
1936 76 : ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno)
1937 : {
1938 : GinBtreeStack *stack;
1939 :
1940 76 : ginPrepareDataScan(btree, index, rootBlkno);
1941 :
1942 76 : btree->fullScan = true;
1943 :
1944 76 : stack = ginFindLeafPage(btree, true, false);
1945 :
1946 76 : return stack;
1947 : }
|
