Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * gindatapage.c
4 : : * routines for handling GIN posting tree pages.
5 : : *
6 : : *
7 : : * Portions Copyright (c) 1996-2026, 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 : : void *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 : 20 : GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerData advancePast)
136 : : {
137 : 20 : ItemPointer result;
138 : :
139 [ + - ]: 20 : if (GinPageIsCompressed(page))
140 : : {
141 : 20 : GinPostingList *seg = GinDataLeafPageGetPostingList(page);
142 : 20 : Size len = GinDataLeafPageGetPostingListSize(page);
143 : 20 : char *endptr = (char *) seg + len;
144 : 20 : GinPostingList *next;
145 : :
146 : : /* Skip to the segment containing advancePast+1 */
147 [ + + ]: 20 : if (ItemPointerIsValid(&advancePast))
148 : : {
149 : 12 : next = GinNextPostingListSegment(seg);
150 [ - + + + ]: 25 : while ((char *) next < endptr &&
151 : 13 : ginCompareItemPointers(&next->first, &advancePast) <= 0)
152 : : {
153 : 1 : seg = next;
154 : 1 : next = GinNextPostingListSegment(seg);
155 : : }
156 : 12 : len = endptr - (char *) seg;
157 : 12 : }
158 : :
159 [ + + ]: 20 : if (len > 0)
160 : 18 : result = ginPostingListDecodeAllSegments(seg, len, nitems);
161 : : else
162 : : {
163 : 2 : result = NULL;
164 : 2 : *nitems = 0;
165 : : }
166 : 20 : }
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 : 0 : }
174 : :
175 : 40 : return result;
176 : 20 : }
177 : :
178 : : /*
179 : : * Places all TIDs from leaf data page to bitmap.
180 : : */
181 : : int
182 : 5 : GinDataLeafPageGetItemsToTbm(Page page, TIDBitmap *tbm)
183 : : {
184 : 5 : ItemPointer uncompressed;
185 : 5 : int nitems;
186 : :
187 [ + - ]: 5 : if (GinPageIsCompressed(page))
188 : : {
189 : 5 : GinPostingList *segment = GinDataLeafPageGetPostingList(page);
190 : 5 : Size len = GinDataLeafPageGetPostingListSize(page);
191 : :
192 : 5 : nitems = ginPostingListDecodeAllSegmentsToTbm(segment, len, tbm);
193 : 5 : }
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 : 10 : return nitems;
203 : 5 : }
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 : 0 : ItemPointer items;
214 : :
215 [ # # ]: 0 : 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 : 0 : }
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 : 3008 : dataIsMoveRight(GinBtree btree, Page page)
235 : : {
236 : 3008 : ItemPointer iptr = GinDataPageGetRightBound(page);
237 : :
238 [ - + ]: 3008 : if (GinPageRightMost(page))
239 : 3008 : return false;
240 : :
241 [ # # ]: 0 : if (GinPageIsDeleted(page))
242 : 0 : return true;
243 : :
244 : 0 : return (ginCompareItemPointers(&btree->itemptr, iptr) > 0);
245 : 3008 : }
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 : 3017 : dataLocateItem(GinBtree btree, GinBtreeStack *stack)
253 : : {
254 : 3017 : OffsetNumber low,
255 : : high,
256 : : maxoff;
257 : 3017 : PostingItem *pitem = NULL;
258 : 3017 : int result;
259 : 3017 : Page page = BufferGetPage(stack->buffer);
260 : :
261 [ + - ]: 3017 : Assert(!GinPageIsLeaf(page));
262 [ + - ]: 3017 : Assert(GinPageIsData(page));
263 : :
264 [ + + ]: 3017 : if (btree->fullScan)
265 : : {
266 : 9 : stack->off = FirstOffsetNumber;
267 : 9 : stack->predictNumber *= GinPageGetOpaque(page)->maxoff;
268 : 9 : return btree->getLeftMostChild(btree, page);
269 : : }
270 : :
271 : 3008 : low = FirstOffsetNumber;
272 : 3008 : maxoff = high = GinPageGetOpaque(page)->maxoff;
273 [ + - ]: 3008 : Assert(high >= low);
274 : :
275 : 3008 : high++;
276 : :
277 [ + + ]: 9024 : while (high > low)
278 : : {
279 : 6016 : OffsetNumber mid = low + ((high - low) / 2);
280 : :
281 : 6016 : pitem = GinDataPageGetPostingItem(page, mid);
282 : :
283 [ + + ]: 6016 : if (mid == maxoff)
284 : : {
285 : : /*
286 : : * Right infinity, page already correctly chosen with a help of
287 : : * dataIsMoveRight
288 : : */
289 : 3008 : result = -1;
290 : 3008 : }
291 : : else
292 : : {
293 : 3008 : pitem = GinDataPageGetPostingItem(page, mid);
294 : 3008 : result = ginCompareItemPointers(&btree->itemptr, &(pitem->key));
295 : : }
296 : :
297 [ + - ]: 6016 : if (result == 0)
298 : : {
299 : 0 : stack->off = mid;
300 : 0 : return PostingItemGetBlockNumber(pitem);
301 : : }
302 [ + + ]: 6016 : else if (result > 0)
303 : 3008 : low = mid + 1;
304 : : else
305 : 3008 : high = mid;
306 [ - + ]: 6016 : }
307 : :
308 [ + - ]: 3008 : Assert(high >= FirstOffsetNumber && high <= maxoff);
309 : :
310 : 3008 : stack->off = high;
311 : 3008 : pitem = GinDataPageGetPostingItem(page, high);
312 : 3008 : return PostingItemGetBlockNumber(pitem);
313 : 3017 : }
314 : :
315 : : /*
316 : : * Find link to blkno on non-leaf page, returns offset of PostingItem
317 : : */
318 : : static OffsetNumber
319 : 5 : dataFindChildPtr(GinBtree btree, Page page, BlockNumber blkno, OffsetNumber storedOff)
320 : : {
321 : 5 : OffsetNumber i,
322 : 5 : maxoff = GinPageGetOpaque(page)->maxoff;
323 : 5 : PostingItem *pitem;
324 : :
325 [ + - ]: 5 : Assert(!GinPageIsLeaf(page));
326 [ + - ]: 5 : Assert(GinPageIsData(page));
327 : :
328 : : /* if page isn't changed, we return storedOff */
329 [ + - - + ]: 5 : if (storedOff >= FirstOffsetNumber && storedOff <= maxoff)
330 : : {
331 : 5 : pitem = GinDataPageGetPostingItem(page, storedOff);
332 [ + - ]: 5 : if (PostingItemGetBlockNumber(pitem) == blkno)
333 : 5 : 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 : 0 : }
345 : :
346 : 0 : maxoff = storedOff - 1;
347 : 0 : }
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 : 0 : }
356 : :
357 : 0 : return InvalidOffsetNumber;
358 : 5 : }
359 : :
360 : : /*
361 : : * Return blkno of leftmost child
362 : : */
363 : : static BlockNumber
364 : 9 : dataGetLeftMostPage(GinBtree btree, Page page)
365 : : {
366 : 9 : PostingItem *pitem;
367 : :
368 [ + - ]: 9 : Assert(!GinPageIsLeaf(page));
369 [ + - ]: 9 : Assert(GinPageIsData(page));
370 [ + - ]: 9 : Assert(GinPageGetOpaque(page)->maxoff >= FirstOffsetNumber);
371 : :
372 : 9 : pitem = GinDataPageGetPostingItem(page, FirstOffsetNumber);
373 : 18 : return PostingItemGetBlockNumber(pitem);
374 : 9 : }
375 : :
376 : : /*
377 : : * Add PostingItem to a non-leaf page.
378 : : */
379 : : void
380 : 15 : GinDataPageAddPostingItem(Page page, PostingItem *data, OffsetNumber offset)
381 : : {
382 : 15 : OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
383 : 15 : char *ptr;
384 : :
385 [ + - ]: 15 : Assert(PostingItemGetBlockNumber(data) != InvalidBlockNumber);
386 [ + - ]: 15 : Assert(!GinPageIsLeaf(page));
387 : :
388 [ + + ]: 15 : if (offset == InvalidOffsetNumber)
389 : : {
390 : 10 : ptr = (char *) GinDataPageGetPostingItem(page, maxoff + 1);
391 : 10 : }
392 : : else
393 : : {
394 : 5 : ptr = (char *) GinDataPageGetPostingItem(page, offset);
395 [ - + ]: 5 : if (offset != maxoff + 1)
396 : 5 : memmove(ptr + sizeof(PostingItem),
397 : : ptr,
398 : : (maxoff - offset + 1) * sizeof(PostingItem));
399 : : }
400 : 15 : memcpy(ptr, data, sizeof(PostingItem));
401 : :
402 : 15 : maxoff++;
403 : 15 : 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 [ + - ]: 15 : GinDataPageSetDataSize(page, maxoff * sizeof(PostingItem));
411 : 15 : }
412 : :
413 : : /*
414 : : * Delete posting item from non-leaf page
415 : : */
416 : : void
417 : 2 : GinPageDeletePostingItem(Page page, OffsetNumber offset)
418 : : {
419 : 2 : OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
420 : :
421 [ + - ]: 2 : Assert(!GinPageIsLeaf(page));
422 [ + - ]: 2 : Assert(offset >= FirstOffsetNumber && offset <= maxoff);
423 : :
424 [ - + ]: 2 : if (offset != maxoff)
425 : 2 : memmove(GinDataPageGetPostingItem(page, offset),
426 : : GinDataPageGetPostingItem(page, offset + 1),
427 : : sizeof(PostingItem) * (maxoff - offset));
428 : :
429 : 2 : maxoff--;
430 : 2 : GinPageGetOpaque(page)->maxoff = maxoff;
431 : :
432 [ + - ]: 2 : GinDataPageSetDataSize(page, maxoff * sizeof(PostingItem));
433 : 2 : }
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 : 3352 : dataBeginPlaceToPageLeaf(GinBtree btree, Buffer buf, GinBtreeStack *stack,
449 : : void *insertdata,
450 : : void **ptp_workspace,
451 : : Page *newlpage, Page *newrpage)
452 : : {
453 : 3352 : GinBtreeDataLeafInsertData *items = insertdata;
454 : 3352 : ItemPointer newItems = &items->items[items->curitem];
455 : 3352 : int maxitems = items->nitem - items->curitem;
456 : 3352 : Page page = BufferGetPage(buf);
457 : 3352 : int i;
458 : 3352 : ItemPointerData rbound;
459 : 3352 : ItemPointerData lbound;
460 : 3352 : bool needsplit;
461 : 3352 : bool append;
462 : 3352 : int segsize;
463 : 3352 : Size freespace;
464 : 3352 : disassembledLeaf *leaf;
465 : 3352 : leafSegmentInfo *lastleftinfo;
466 : 3352 : ItemPointerData maxOldItem;
467 : 3352 : ItemPointerData remaining;
468 : :
469 : 3352 : rbound = *GinDataPageGetRightBound(page);
470 : :
471 : : /*
472 : : * Count how many of the new items belong to this page.
473 : : */
474 [ + - ]: 3352 : 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 [ # # ]: 0 : Assert(i > 0);
486 : 0 : break;
487 : : }
488 : 0 : }
489 : 0 : maxitems = i;
490 : 0 : }
491 : :
492 : : /* Disassemble the data on the page */
493 : 3352 : 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 [ - + ]: 3352 : if (!dlist_is_empty(&leaf->segments))
500 : : {
501 : 3352 : lastleftinfo = dlist_container(leafSegmentInfo, node,
502 : : dlist_tail_node(&leaf->segments));
503 [ - + ]: 3352 : if (!lastleftinfo->items)
504 : 6704 : lastleftinfo->items = ginPostingListDecode(lastleftinfo->seg,
505 : 3352 : &lastleftinfo->nitems);
506 : 3352 : maxOldItem = lastleftinfo->items[lastleftinfo->nitems - 1];
507 [ + - ]: 3352 : if (ginCompareItemPointers(&newItems[0], &maxOldItem) >= 0)
508 : 3352 : append = true;
509 : : else
510 : 0 : append = false;
511 : 3352 : }
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 [ + - ]: 3352 : if (GinPageIsCompressed(page))
526 : 3352 : freespace = GinDataLeafPageGetFreeSpace(page);
527 : : else
528 : 0 : freespace = 0;
529 [ + - ]: 3352 : 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 [ + + ]: 3352 : maxitems = Min(maxitems, freespace + GinDataPageMaxDataSize);
539 : 3352 : }
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 : 0 : int nnewsegments;
551 : :
552 : 0 : nnewsegments = freespace / GinPostingListSegmentMaxSize;
553 : 0 : nnewsegments += GinDataPageMaxDataSize / GinPostingListSegmentMaxSize;
554 [ # # ]: 0 : maxitems = Min(maxitems, nnewsegments * MinTuplesPerSegment);
555 : 0 : }
556 : :
557 : : /* Add the new items to the segment list */
558 [ + + ]: 3352 : if (!addItemsToLeaf(leaf, newItems, maxitems))
559 : : {
560 : : /* all items were duplicates, we have nothing to do */
561 : 6684 : items->curitem += maxitems;
562 : :
563 : 6684 : return GPTP_NO_WORK;
564 : : }
565 : :
566 : : /*
567 : : * Pack the items back to compressed segments, ready for writing to disk.
568 : : */
569 : 10036 : 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 [ + + ]: 10036 : if (ItemPointerIsValid(&remaining))
578 : : {
579 [ + - ]: 4 : 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 [ - + ]: 30567 : for (i = 0; i < maxitems; i++)
584 : : {
585 [ + + ]: 30567 : if (ginCompareItemPointers(&newItems[i], &remaining) >= 0)
586 : 4 : break;
587 : 30563 : }
588 [ + - ]: 4 : if (i == 0)
589 [ # # # # ]: 0 : elog(ERROR, "could not split GIN page; no new items fit");
590 : 4 : maxitems = i;
591 : 4 : }
592 : :
593 [ + + ]: 10036 : 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 [ + + + - : 10026 : if (RelationNeedsWAL(btree->index) && !btree->isBuild)
+ - + + ]
600 : 3342 : 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 : 16710 : *ptp_workspace = leaf;
607 : :
608 [ + - ]: 16710 : if (append)
609 [ - + - + ]: 3342 : elog(DEBUG2, "appended %d new items to block %u; %d bytes (%d to go)",
610 : : maxitems, BufferGetBlockNumber(buf), 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), leaf->lsize,
615 : : items->nitem - items->curitem - maxitems);
616 : 3342 : }
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 [ + + ]: 10 : if (!btree->isBuild)
638 : : {
639 [ - + ]: 38 : while (dlist_has_prev(&leaf->segments, leaf->lastleft))
640 : : {
641 : 38 : lastleftinfo = dlist_container(leafSegmentInfo, node, leaf->lastleft);
642 : :
643 : : /* ignore deleted segments */
644 [ - + ]: 38 : if (lastleftinfo->action != GIN_SEGMENT_DELETE)
645 : : {
646 : 38 : 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 [ + + ]: 38 : if ((leaf->lsize - segsize) - (leaf->rsize + segsize) < 0)
655 : 8 : break;
656 [ - + ]: 30 : if (append)
657 : : {
658 [ + + ]: 30 : if ((leaf->lsize - segsize) < (BLCKSZ * 3) / 4)
659 : 1 : break;
660 : 29 : }
661 : :
662 : 29 : leaf->lsize -= segsize;
663 : 29 : leaf->rsize += segsize;
664 : 29 : }
665 : 29 : leaf->lastleft = dlist_prev_node(&leaf->segments, leaf->lastleft);
666 : : }
667 : 9 : }
668 [ + - ]: 10 : Assert(leaf->lsize <= GinDataPageMaxDataSize);
669 [ + - ]: 10 : 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 : 10 : lastleftinfo = dlist_container(leafSegmentInfo, node, leaf->lastleft);
676 [ - + ]: 10 : if (!lastleftinfo->items)
677 : 20 : lastleftinfo->items = ginPostingListDecode(lastleftinfo->seg,
678 : 10 : &lastleftinfo->nitems);
679 : 10 : lbound = lastleftinfo->items[lastleftinfo->nitems - 1];
680 : :
681 : : /*
682 : : * Now allocate a couple of temporary page images, and fill them.
683 : : */
684 : 10 : *newlpage = palloc(BLCKSZ);
685 : 10 : *newrpage = palloc(BLCKSZ);
686 : :
687 : 20 : dataPlaceToPageLeafSplit(leaf, lbound, rbound,
688 : 10 : *newlpage, *newrpage);
689 : :
690 [ - + # # ]: 10 : Assert(GinPageRightMost(page) ||
691 : : ginCompareItemPointers(GinDataPageGetRightBound(*newlpage),
692 : : GinDataPageGetRightBound(*newrpage)) < 0);
693 : :
694 [ + - ]: 10 : if (append)
695 [ - + - + ]: 10 : elog(DEBUG2, "appended %d items to block %u; split %d/%d (%d to go)",
696 : : maxitems, BufferGetBlockNumber(buf), leaf->lsize, 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), leaf->lsize, leaf->rsize,
701 : : items->nitem - items->curitem - maxitems);
702 : : }
703 : :
704 : 3352 : items->curitem += maxitems;
705 : :
706 : 3352 : return needsplit ? GPTP_SPLIT : GPTP_INSERT;
707 : 10036 : }
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 : 3342 : dataExecPlaceToPageLeaf(GinBtree btree, Buffer buf, GinBtreeStack *stack,
717 : : void *insertdata, void *ptp_workspace)
718 : : {
719 : 3342 : disassembledLeaf *leaf = (disassembledLeaf *) ptp_workspace;
720 : :
721 : : /* Apply changes to page */
722 : 3342 : dataPlaceToPageLeafRecompress(buf, leaf);
723 : :
724 : 3342 : MarkBufferDirty(buf);
725 : :
726 : : /* If needed, register WAL data built by computeLeafRecompressWALData */
727 [ + - + - : 3342 : if (RelationNeedsWAL(btree->index) && !btree->isBuild)
+ - + + ]
728 : : {
729 : 3342 : XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
730 : 3342 : XLogRegisterBufData(0, leaf->walinfo, leaf->walinfolen);
731 : 3342 : }
732 : 10026 : }
733 : :
734 : : /*
735 : : * Vacuum a posting tree leaf page.
736 : : */
737 : : void
738 : 6 : ginVacuumPostingTreeLeaf(Relation indexrel, Buffer buffer, GinVacuumState *gvs)
739 : : {
740 : 6 : Page page = BufferGetPage(buffer);
741 : 6 : disassembledLeaf *leaf;
742 : 6 : bool removedsomething = false;
743 : 6 : dlist_iter iter;
744 : :
745 : 6 : leaf = disassembleLeaf(page);
746 : :
747 : : /* Vacuum each segment. */
748 [ + - + + ]: 147 : dlist_foreach(iter, &leaf->segments)
749 : : {
750 : 141 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node, iter.cur);
751 : 141 : int oldsegsize;
752 : 141 : ItemPointer cleaned;
753 : 141 : int ncleaned;
754 : :
755 [ - + ]: 141 : if (!seginfo->items)
756 : 282 : seginfo->items = ginPostingListDecode(seginfo->seg,
757 : 141 : &seginfo->nitems);
758 [ + - ]: 141 : if (seginfo->seg)
759 : 141 : oldsegsize = SizeOfGinPostingList(seginfo->seg);
760 : : else
761 : 0 : oldsegsize = GinDataPageMaxDataSize;
762 : :
763 : 282 : cleaned = ginVacuumItemPointers(gvs,
764 : 141 : seginfo->items,
765 : 141 : seginfo->nitems,
766 : : &ncleaned);
767 : 141 : pfree(seginfo->items);
768 : 141 : seginfo->items = NULL;
769 : 141 : seginfo->nitems = 0;
770 [ - + ]: 141 : if (cleaned)
771 : : {
772 [ + + ]: 141 : if (ncleaned > 0)
773 : : {
774 : 1 : int npacked;
775 : :
776 : 2 : seginfo->seg = ginCompressPostingList(cleaned,
777 : 1 : ncleaned,
778 : 1 : oldsegsize,
779 : : &npacked);
780 : : /* Removing an item never increases the size of the segment */
781 [ + - ]: 1 : if (npacked != ncleaned)
782 [ # # # # ]: 0 : elog(ERROR, "could not fit vacuumed posting list");
783 : 1 : seginfo->action = GIN_SEGMENT_REPLACE;
784 : 1 : }
785 : : else
786 : : {
787 : 140 : seginfo->seg = NULL;
788 : 140 : seginfo->items = NULL;
789 : 140 : seginfo->action = GIN_SEGMENT_DELETE;
790 : : }
791 : 141 : seginfo->nitems = ncleaned;
792 : :
793 : 141 : removedsomething = true;
794 : 141 : }
795 : 141 : }
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 [ - + ]: 6 : if (removedsomething)
815 : : {
816 : 6 : 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 : 6 : modified = false;
824 [ + - + + ]: 147 : dlist_foreach(iter, &leaf->segments)
825 : : {
826 : 141 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
827 : : iter.cur);
828 : :
829 [ - + ]: 141 : if (seginfo->action != GIN_SEGMENT_UNMODIFIED)
830 : 141 : modified = true;
831 [ + - + + ]: 141 : if (modified && seginfo->action != GIN_SEGMENT_DELETE)
832 : : {
833 : 1 : int segsize = SizeOfGinPostingList(seginfo->seg);
834 : 1 : GinPostingList *tmp = (GinPostingList *) palloc(segsize);
835 : :
836 : 1 : memcpy(tmp, seginfo->seg, segsize);
837 : 1 : seginfo->seg = tmp;
838 : 1 : }
839 : 141 : }
840 : :
841 [ - + # # : 6 : if (RelationNeedsWAL(indexrel))
# # # # ]
842 : 0 : computeLeafRecompressWALData(leaf);
843 : :
844 : : /* Apply changes to page */
845 : 6 : START_CRIT_SECTION();
846 : :
847 : 6 : dataPlaceToPageLeafRecompress(buffer, leaf);
848 : :
849 : 6 : MarkBufferDirty(buffer);
850 : :
851 [ - + # # : 6 : if (RelationNeedsWAL(indexrel))
# # # # ]
852 : : {
853 : 0 : XLogRecPtr recptr;
854 : :
855 : 0 : XLogBeginInsert();
856 : 0 : XLogRegisterBuffer(0, buffer, REGBUF_STANDARD);
857 : 0 : XLogRegisterBufData(0, leaf->walinfo, leaf->walinfolen);
858 : 0 : recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_VACUUM_DATA_LEAF_PAGE);
859 : 0 : PageSetLSN(page, recptr);
860 : 0 : }
861 : :
862 [ + - ]: 6 : END_CRIT_SECTION();
863 : 6 : }
864 : 6 : }
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 : 3342 : computeLeafRecompressWALData(disassembledLeaf *leaf)
873 : : {
874 : 3342 : int nmodified = 0;
875 : 3342 : char *walbufbegin;
876 : 3342 : char *walbufend;
877 : 3342 : dlist_iter iter;
878 : 3342 : int segno;
879 : 3342 : ginxlogRecompressDataLeaf *recompress_xlog;
880 : :
881 : : /* Count the modified segments */
882 [ + - + + ]: 63145 : dlist_foreach(iter, &leaf->segments)
883 : : {
884 : 59803 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
885 : : iter.cur);
886 : :
887 [ + + ]: 59803 : if (seginfo->action != GIN_SEGMENT_UNMODIFIED)
888 : 3345 : nmodified++;
889 : 59803 : }
890 : :
891 : 3342 : walbufbegin =
892 : 3342 : palloc(sizeof(ginxlogRecompressDataLeaf) +
893 : 3342 : BLCKSZ + /* max size needed to hold the segment data */
894 : 3342 : nmodified * 2 /* (segno + action) per action */
895 : : );
896 : 3342 : walbufend = walbufbegin;
897 : :
898 : 3342 : recompress_xlog = (ginxlogRecompressDataLeaf *) walbufend;
899 : 3342 : walbufend += sizeof(ginxlogRecompressDataLeaf);
900 : :
901 : 3342 : recompress_xlog->nactions = nmodified;
902 : :
903 : 3342 : segno = 0;
904 [ + - + + ]: 63145 : dlist_foreach(iter, &leaf->segments)
905 : : {
906 : 59803 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
907 : : iter.cur);
908 : 59803 : int segsize = 0;
909 : 59803 : int datalen;
910 : 59803 : uint8 action = seginfo->action;
911 : :
912 [ + + ]: 59803 : if (action == GIN_SEGMENT_UNMODIFIED)
913 : : {
914 : 56458 : segno++;
915 : 56458 : continue;
916 : : }
917 : :
918 [ - + ]: 3345 : if (action != GIN_SEGMENT_DELETE)
919 : 3345 : 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 [ + + + - ]: 3345 : if (action == GIN_SEGMENT_ADDITEMS &&
927 : 3326 : seginfo->nmodifieditems * sizeof(ItemPointerData) > segsize)
928 : : {
929 : 0 : action = GIN_SEGMENT_REPLACE;
930 : 0 : }
931 : :
932 : 3345 : *((uint8 *) (walbufend++)) = segno;
933 : 3345 : *(walbufend++) = action;
934 : :
935 [ + - + - ]: 3345 : switch (action)
936 : : {
937 : : case GIN_SEGMENT_DELETE:
938 : 0 : datalen = 0;
939 : 0 : break;
940 : :
941 : : case GIN_SEGMENT_ADDITEMS:
942 : 3326 : datalen = seginfo->nmodifieditems * sizeof(ItemPointerData);
943 : 3326 : memcpy(walbufend, &seginfo->nmodifieditems, sizeof(uint16));
944 : 3326 : memcpy(walbufend + sizeof(uint16), seginfo->modifieditems, datalen);
945 : 3326 : datalen += sizeof(uint16);
946 : 3326 : break;
947 : :
948 : : case GIN_SEGMENT_INSERT:
949 : : case GIN_SEGMENT_REPLACE:
950 : 19 : datalen = SHORTALIGN(segsize);
951 : 19 : memcpy(walbufend, seginfo->seg, segsize);
952 : 19 : break;
953 : :
954 : : default:
955 [ # # # # ]: 0 : elog(ERROR, "unexpected GIN leaf action %d", action);
956 : 0 : }
957 : 3345 : walbufend += datalen;
958 : :
959 [ + + ]: 3345 : if (action != GIN_SEGMENT_INSERT)
960 : 3326 : segno++;
961 [ - + + ]: 59803 : }
962 : :
963 : : /* Pass back the constructed info via *leaf */
964 : 3342 : leaf->walinfo = walbufbegin;
965 : 3342 : leaf->walinfolen = walbufend - walbufbegin;
966 : 3342 : }
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 : 3348 : dataPlaceToPageLeafRecompress(Buffer buf, disassembledLeaf *leaf)
979 : : {
980 : 3348 : Page page = BufferGetPage(buf);
981 : 3348 : char *ptr;
982 : 3348 : int newsize;
983 : 3348 : bool modified = false;
984 : 3348 : dlist_iter iter;
985 : 3348 : 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 [ + - ]: 3348 : if (!GinPageIsCompressed(page))
993 : : {
994 [ # # ]: 0 : Assert(leaf->oldformat);
995 : 0 : GinPageSetCompressed(page);
996 : 0 : GinPageGetOpaque(page)->maxoff = InvalidOffsetNumber;
997 : 0 : modified = true;
998 : 0 : }
999 : :
1000 : 3348 : ptr = (char *) GinDataLeafPageGetPostingList(page);
1001 : 3348 : newsize = 0;
1002 [ + - + + ]: 63292 : dlist_foreach(iter, &leaf->segments)
1003 : : {
1004 : 59944 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node, iter.cur);
1005 : :
1006 [ + + ]: 59944 : if (seginfo->action != GIN_SEGMENT_UNMODIFIED)
1007 : 3486 : modified = true;
1008 : :
1009 [ + + ]: 59944 : if (seginfo->action != GIN_SEGMENT_DELETE)
1010 : : {
1011 : 59804 : segsize = SizeOfGinPostingList(seginfo->seg);
1012 : :
1013 [ + + ]: 59804 : if (modified)
1014 : 3346 : memcpy(ptr, seginfo->seg, segsize);
1015 : :
1016 : 59804 : ptr += segsize;
1017 : 59804 : newsize += segsize;
1018 : 59804 : }
1019 : 59944 : }
1020 : :
1021 [ - + ]: 3348 : Assert(newsize <= GinDataPageMaxDataSize);
1022 [ - + ]: 3348 : GinDataPageSetDataSize(page, newsize);
1023 : 3348 : }
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 : 10 : dataPlaceToPageLeafSplit(disassembledLeaf *leaf,
1035 : : ItemPointerData lbound, ItemPointerData rbound,
1036 : : Page lpage, Page rpage)
1037 : : {
1038 : 10 : char *ptr;
1039 : 10 : int segsize;
1040 : 10 : int lsize;
1041 : 10 : int rsize;
1042 : 10 : dlist_node *node;
1043 : 10 : dlist_node *firstright;
1044 : 10 : leafSegmentInfo *seginfo;
1045 : :
1046 : : /* Initialize temporary pages to hold the new left and right pages */
1047 : 10 : GinInitPage(lpage, GIN_DATA | GIN_LEAF | GIN_COMPRESSED, BLCKSZ);
1048 : 10 : 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 : 10 : lsize = 0;
1057 : 10 : ptr = (char *) GinDataLeafPageGetPostingList(lpage);
1058 : 10 : firstright = dlist_next_node(&leaf->segments, leaf->lastleft);
1059 [ + + ]: 241 : for (node = dlist_head_node(&leaf->segments);
1060 : 241 : node != firstright;
1061 : 231 : node = dlist_next_node(&leaf->segments, node))
1062 : : {
1063 : 231 : seginfo = dlist_container(leafSegmentInfo, node, node);
1064 : :
1065 [ - + ]: 231 : if (seginfo->action != GIN_SEGMENT_DELETE)
1066 : : {
1067 : 231 : segsize = SizeOfGinPostingList(seginfo->seg);
1068 : 231 : memcpy(ptr, seginfo->seg, segsize);
1069 : 231 : ptr += segsize;
1070 : 231 : lsize += segsize;
1071 : 231 : }
1072 : 231 : }
1073 [ + - ]: 10 : Assert(lsize == leaf->lsize);
1074 [ + - ]: 10 : GinDataPageSetDataSize(lpage, lsize);
1075 : 10 : *GinDataPageGetRightBound(lpage) = lbound;
1076 : :
1077 : : /* Copy the segments that go to the right page */
1078 : 10 : ptr = (char *) GinDataLeafPageGetPostingList(rpage);
1079 : 10 : rsize = 0;
1080 : 240 : for (node = firstright;
1081 : : ;
1082 : 230 : node = dlist_next_node(&leaf->segments, node))
1083 : : {
1084 : 240 : seginfo = dlist_container(leafSegmentInfo, node, node);
1085 : :
1086 [ - + ]: 240 : if (seginfo->action != GIN_SEGMENT_DELETE)
1087 : : {
1088 : 240 : segsize = SizeOfGinPostingList(seginfo->seg);
1089 : 240 : memcpy(ptr, seginfo->seg, segsize);
1090 : 240 : ptr += segsize;
1091 : 240 : rsize += segsize;
1092 : 240 : }
1093 : :
1094 [ + + ]: 240 : if (!dlist_has_next(&leaf->segments, node))
1095 : 10 : break;
1096 : 230 : }
1097 [ + - ]: 10 : Assert(rsize == leaf->rsize);
1098 [ + - ]: 10 : GinDataPageSetDataSize(rpage, rsize);
1099 : 10 : *GinDataPageGetRightBound(rpage) = rbound;
1100 : 10 : }
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 : 5 : dataBeginPlaceToPageInternal(GinBtree btree, Buffer buf, GinBtreeStack *stack,
1120 : : void *insertdata, BlockNumber updateblkno,
1121 : : void **ptp_workspace,
1122 : : Page *newlpage, Page *newrpage)
1123 : : {
1124 : 5 : Page page = BufferGetPage(buf);
1125 : :
1126 : : /* If it doesn't fit, deal with split case */
1127 [ - + ]: 5 : if (GinNonLeafDataPageGetFreeSpace(page) < sizeof(PostingItem))
1128 : : {
1129 : 0 : dataSplitPageInternal(btree, buf, stack, insertdata, updateblkno,
1130 : 0 : newlpage, newrpage);
1131 : 0 : return GPTP_SPLIT;
1132 : : }
1133 : :
1134 : : /* Else, we're ready to proceed with insertion */
1135 : 5 : return GPTP_INSERT;
1136 : 5 : }
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 : 5 : dataExecPlaceToPageInternal(GinBtree btree, Buffer buf, GinBtreeStack *stack,
1146 : : void *insertdata, BlockNumber updateblkno,
1147 : : void *ptp_workspace)
1148 : : {
1149 : 5 : Page page = BufferGetPage(buf);
1150 : 5 : OffsetNumber off = stack->off;
1151 : 5 : PostingItem *pitem;
1152 : :
1153 : : /* Update existing downlink to point to next page (on internal page) */
1154 : 5 : pitem = GinDataPageGetPostingItem(page, off);
1155 : 5 : PostingItemSetBlockNumber(pitem, updateblkno);
1156 : :
1157 : : /* Add new item */
1158 : 5 : pitem = (PostingItem *) insertdata;
1159 : 5 : GinDataPageAddPostingItem(page, pitem, off);
1160 : :
1161 : 5 : MarkBufferDirty(buf);
1162 : :
1163 [ + + + - : 5 : 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 : 3 : data.offset = off;
1173 : 3 : data.newitem = *pitem;
1174 : :
1175 : 3 : XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
1176 : 3 : XLogRegisterBufData(0, &data,
1177 : : sizeof(ginxlogInsertDataInternal));
1178 : 3 : }
1179 : 11 : }
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 : 3357 : dataBeginPlaceToPage(GinBtree btree, Buffer buf, GinBtreeStack *stack,
1202 : : void *insertdata, BlockNumber updateblkno,
1203 : : void **ptp_workspace,
1204 : : Page *newlpage, Page *newrpage)
1205 : : {
1206 : 3357 : Page page = BufferGetPage(buf);
1207 : :
1208 [ + - ]: 3357 : Assert(GinPageIsData(page));
1209 : :
1210 [ + + ]: 3357 : if (GinPageIsLeaf(page))
1211 : 6704 : return dataBeginPlaceToPageLeaf(btree, buf, stack, insertdata,
1212 : 3352 : ptp_workspace,
1213 : 3352 : newlpage, newrpage);
1214 : : else
1215 : 10 : return dataBeginPlaceToPageInternal(btree, buf, stack,
1216 : 5 : insertdata, updateblkno,
1217 : 5 : ptp_workspace,
1218 : 5 : newlpage, newrpage);
1219 : 3357 : }
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 : 3347 : dataExecPlaceToPage(GinBtree btree, Buffer buf, GinBtreeStack *stack,
1232 : : void *insertdata, BlockNumber updateblkno,
1233 : : void *ptp_workspace)
1234 : : {
1235 : 3347 : Page page = BufferGetPage(buf);
1236 : :
1237 [ + + ]: 3347 : if (GinPageIsLeaf(page))
1238 : 6684 : dataExecPlaceToPageLeaf(btree, buf, stack, insertdata,
1239 : 3342 : ptp_workspace);
1240 : : else
1241 : 10 : dataExecPlaceToPageInternal(btree, buf, stack, insertdata,
1242 : 5 : updateblkno, ptp_workspace);
1243 : 3347 : }
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 : 0 : int nleftitems;
1261 : 0 : int nrightitems;
1262 : 0 : Size pageSize = PageGetPageSize(oldpage);
1263 : 0 : ItemPointerData oldbound = *GinDataPageGetRightBound(oldpage);
1264 : 0 : ItemPointer bound;
1265 : 0 : Page lpage;
1266 : 0 : Page rpage;
1267 : 0 : OffsetNumber separator;
1268 : 0 : 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 : : (off - 1) * sizeof(PostingItem));
1281 : :
1282 : 0 : allitems[off - 1] = *((PostingItem *) insertdata);
1283 : 0 : memcpy(&allitems[off], GinDataPageGetPostingItem(oldpage, off),
1284 : : (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 : : &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 : 5 : dataPrepareDownlink(GinBtree btree, Buffer lbuf)
1334 : : {
1335 : 5 : PostingItem *pitem = palloc_object(PostingItem);
1336 : 5 : Page lpage = BufferGetPage(lbuf);
1337 : :
1338 : 5 : PostingItemSetBlockNumber(pitem, BufferGetBlockNumber(lbuf));
1339 : 5 : pitem->key = *GinDataPageGetRightBound(lpage);
1340 : :
1341 : 10 : return pitem;
1342 : 5 : }
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 : 5 : ginDataFillRoot(GinBtree btree, Page root, BlockNumber lblkno, Page lpage, BlockNumber rblkno, Page rpage)
1350 : : {
1351 : 5 : PostingItem li,
1352 : : ri;
1353 : :
1354 : 5 : li.key = *GinDataPageGetRightBound(lpage);
1355 : 5 : PostingItemSetBlockNumber(&li, lblkno);
1356 : 5 : GinDataPageAddPostingItem(root, &li, InvalidOffsetNumber);
1357 : :
1358 : 5 : ri.key = *GinDataPageGetRightBound(rpage);
1359 : 5 : PostingItemSetBlockNumber(&ri, rblkno);
1360 : 5 : GinDataPageAddPostingItem(root, &ri, InvalidOffsetNumber);
1361 : 5 : }
1362 : :
1363 : :
1364 : : /*** Functions to work with disassembled leaf pages ***/
1365 : :
1366 : : /*
1367 : : * Disassemble page into a disassembledLeaf struct.
1368 : : */
1369 : : static disassembledLeaf *
1370 : 3358 : disassembleLeaf(Page page)
1371 : : {
1372 : 3358 : disassembledLeaf *leaf;
1373 : 3358 : GinPostingList *seg;
1374 : 3358 : char *segbegin;
1375 : 3358 : char *segend;
1376 : :
1377 : 3358 : leaf = palloc0_object(disassembledLeaf);
1378 : 3358 : dlist_init(&leaf->segments);
1379 : :
1380 [ + - ]: 3358 : if (GinPageIsCompressed(page))
1381 : : {
1382 : : /*
1383 : : * Create a leafSegmentInfo entry for each segment.
1384 : : */
1385 : 3358 : seg = GinDataLeafPageGetPostingList(page);
1386 : 3358 : segbegin = (char *) seg;
1387 : 3358 : segend = segbegin + GinDataLeafPageGetPostingListSize(page);
1388 [ + + ]: 63544 : while ((char *) seg < segend)
1389 : : {
1390 : 60186 : leafSegmentInfo *seginfo = palloc_object(leafSegmentInfo);
1391 : :
1392 : 60186 : seginfo->action = GIN_SEGMENT_UNMODIFIED;
1393 : 60186 : seginfo->seg = seg;
1394 : 60186 : seginfo->items = NULL;
1395 : 60186 : seginfo->nitems = 0;
1396 : 60186 : dlist_push_tail(&leaf->segments, &seginfo->node);
1397 : :
1398 : 60186 : seg = GinNextPostingListSegment(seg);
1399 : 60186 : }
1400 : 3358 : leaf->oldformat = false;
1401 : 3358 : }
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 : 0 : ItemPointer uncompressed;
1410 : 0 : int nuncompressed;
1411 : 0 : leafSegmentInfo *seginfo;
1412 : :
1413 : 0 : uncompressed = dataLeafPageGetUncompressed(page, &nuncompressed);
1414 : :
1415 [ # # ]: 0 : if (nuncompressed > 0)
1416 : : {
1417 : 0 : seginfo = palloc_object(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 : 0 : }
1427 : :
1428 : 0 : leaf->oldformat = true;
1429 : 0 : }
1430 : :
1431 : 6716 : return leaf;
1432 : 3358 : }
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 : 3352 : addItemsToLeaf(disassembledLeaf *leaf, ItemPointer newItems, int nNewItems)
1445 : : {
1446 : 3352 : dlist_iter iter;
1447 : 3352 : ItemPointer nextnew = newItems;
1448 : 3352 : int newleft = nNewItems;
1449 : 3352 : bool modified = false;
1450 : 3352 : 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 [ - + ]: 3352 : if (dlist_is_empty(&leaf->segments))
1457 : : {
1458 : 0 : newseg = palloc_object(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 [ - + - + ]: 60045 : dlist_foreach(iter, &leaf->segments)
1468 : : {
1469 : 60045 : leafSegmentInfo *cur = (leafSegmentInfo *) dlist_container(leafSegmentInfo, node, iter.cur);
1470 : 60045 : int nthis;
1471 : 60045 : ItemPointer tmpitems;
1472 : 60045 : int ntmpitems;
1473 : :
1474 : : /*
1475 : : * How many of the new items fall into this segment?
1476 : : */
1477 [ + + ]: 60045 : if (!dlist_has_next(&leaf->segments, iter.cur))
1478 : 3352 : nthis = newleft;
1479 : : else
1480 : : {
1481 : 56693 : leafSegmentInfo *next;
1482 : 56693 : ItemPointerData next_first;
1483 : :
1484 : 56693 : next = (leafSegmentInfo *) dlist_container(leafSegmentInfo, node,
1485 : : dlist_next_node(&leaf->segments, iter.cur));
1486 [ + + ]: 56693 : if (next->items)
1487 : 3352 : next_first = next->items[0];
1488 : : else
1489 : : {
1490 [ + - ]: 53341 : Assert(next->seg != NULL);
1491 : 53341 : next_first = next->seg->first;
1492 : : }
1493 : :
1494 : 56693 : nthis = 0;
1495 [ - + - + ]: 56693 : while (nthis < newleft && ginCompareItemPointers(&nextnew[nthis], &next_first) < 0)
1496 : 0 : nthis++;
1497 : 56693 : }
1498 [ + + ]: 60045 : if (nthis == 0)
1499 : 56693 : continue;
1500 : :
1501 : : /* Merge the new items with the existing items. */
1502 [ + - ]: 3352 : 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 [ + - ]: 3352 : if (!dlist_has_next(&leaf->segments, iter.cur) &&
1511 [ + - ]: 3352 : ginCompareItemPointers(&cur->items[cur->nitems - 1], &nextnew[0]) < 0 &&
1512 [ + - + + ]: 3352 : cur->seg != NULL &&
1513 : 3352 : SizeOfGinPostingList(cur->seg) >= GinPostingListSegmentTargetSize)
1514 : : {
1515 : 25 : newseg = palloc_object(leafSegmentInfo);
1516 : 25 : newseg->seg = NULL;
1517 : 25 : newseg->items = nextnew;
1518 : 25 : newseg->nitems = nthis;
1519 : 25 : newseg->action = GIN_SEGMENT_INSERT;
1520 : 25 : dlist_push_tail(&leaf->segments, &newseg->node);
1521 : 25 : modified = true;
1522 : 25 : break;
1523 : : }
1524 : :
1525 : 6654 : tmpitems = ginMergeItemPointers(cur->items, cur->nitems,
1526 : 3327 : nextnew, nthis,
1527 : : &ntmpitems);
1528 [ - + ]: 3327 : 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 [ + - - + ]: 3327 : if (ntmpitems == nthis + cur->nitems &&
1537 : 3327 : cur->action == GIN_SEGMENT_UNMODIFIED)
1538 : : {
1539 : 3327 : cur->action = GIN_SEGMENT_ADDITEMS;
1540 : 3327 : cur->modifieditems = nextnew;
1541 : 3327 : cur->nmodifieditems = nthis;
1542 : 3327 : }
1543 : : else
1544 : 0 : cur->action = GIN_SEGMENT_REPLACE;
1545 : :
1546 : 3327 : cur->items = tmpitems;
1547 : 3327 : cur->nitems = ntmpitems;
1548 : 3327 : cur->seg = NULL;
1549 : 3327 : modified = true;
1550 : 3327 : }
1551 : :
1552 : 3327 : nextnew += nthis;
1553 : 3327 : newleft -= nthis;
1554 [ - + ]: 3327 : if (newleft == 0)
1555 : 3327 : break;
1556 [ - + + - ]: 60045 : }
1557 : :
1558 : 3352 : return modified;
1559 : 3352 : }
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 : 3352 : leafRepackItems(disassembledLeaf *leaf, ItemPointer remaining)
1572 : : {
1573 : 3352 : int pgused = 0;
1574 : 3352 : bool needsplit = false;
1575 : 3352 : dlist_iter iter;
1576 : 3352 : int segsize;
1577 : 3352 : leafSegmentInfo *nextseg;
1578 : 3352 : int npacked;
1579 : 3352 : bool modified;
1580 : 3352 : dlist_node *cur_node;
1581 : 3352 : dlist_node *next_node;
1582 : :
1583 : 3352 : ItemPointerSetInvalid(remaining);
1584 : :
1585 : : /*
1586 : : * cannot use dlist_foreach_modify here because we insert adjacent items
1587 : : * while iterating.
1588 : : */
1589 [ + + ]: 63626 : for (cur_node = dlist_head_node(&leaf->segments);
1590 : 63626 : cur_node != NULL;
1591 : 60274 : cur_node = next_node)
1592 : : {
1593 : 60278 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
1594 : : cur_node);
1595 : :
1596 [ + + ]: 60278 : if (dlist_has_next(&leaf->segments, cur_node))
1597 : 56718 : next_node = dlist_next_node(&leaf->segments, cur_node);
1598 : : else
1599 : 3560 : next_node = NULL;
1600 : :
1601 : : /* Compress the posting list, if necessary */
1602 [ - + ]: 60278 : if (seginfo->action != GIN_SEGMENT_DELETE)
1603 : : {
1604 [ + + ]: 60278 : if (seginfo->seg == NULL)
1605 : : {
1606 [ + + ]: 3560 : if (seginfo->nitems > GinPostingListSegmentMaxSize)
1607 : 211 : npacked = 0; /* no chance that it would fit. */
1608 : : else
1609 : : {
1610 : 6698 : seginfo->seg = ginCompressPostingList(seginfo->items,
1611 : 3349 : seginfo->nitems,
1612 : : GinPostingListSegmentMaxSize,
1613 : : &npacked);
1614 : : }
1615 [ + + ]: 3560 : 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 [ + + ]: 212 : if (seginfo->seg)
1624 : 1 : pfree(seginfo->seg);
1625 : 424 : seginfo->seg = ginCompressPostingList(seginfo->items,
1626 : 212 : seginfo->nitems,
1627 : : GinPostingListSegmentTargetSize,
1628 : : &npacked);
1629 [ + - ]: 212 : if (seginfo->action != GIN_SEGMENT_INSERT)
1630 : 0 : seginfo->action = GIN_SEGMENT_REPLACE;
1631 : :
1632 : 212 : nextseg = palloc_object(leafSegmentInfo);
1633 : 212 : nextseg->action = GIN_SEGMENT_INSERT;
1634 : 212 : nextseg->seg = NULL;
1635 : 212 : nextseg->items = &seginfo->items[npacked];
1636 : 212 : nextseg->nitems = seginfo->nitems - npacked;
1637 : 212 : next_node = &nextseg->node;
1638 : 212 : dlist_insert_after(cur_node, next_node);
1639 : 212 : }
1640 : 3560 : }
1641 : :
1642 : : /*
1643 : : * If the segment is very small, merge it with the next segment.
1644 : : */
1645 [ + + + - ]: 60278 : if (SizeOfGinPostingList(seginfo->seg) < GinPostingListSegmentMinSize && next_node)
1646 : : {
1647 : 0 : 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 : 0 : &seginfo->nitems);
1654 [ # # ]: 0 : if (nextseg->items == NULL)
1655 : 0 : nextseg->items = ginPostingListDecode(nextseg->seg,
1656 : 0 : &nextseg->nitems);
1657 : 0 : nextseg->items =
1658 : 0 : ginMergeItemPointers(seginfo->items, seginfo->nitems,
1659 : 0 : nextseg->items, nextseg->nitems,
1660 : : &nmerged);
1661 [ # # ]: 0 : 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 [ # # ]: 0 : }
1680 : :
1681 : 60278 : seginfo->items = NULL;
1682 : 60278 : seginfo->nitems = 0;
1683 : 60278 : }
1684 : :
1685 [ - + ]: 60278 : 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 : 60278 : segsize = SizeOfGinPostingList(seginfo->seg);
1693 [ + + ]: 60278 : if (pgused + segsize > GinDataPageMaxDataSize)
1694 : : {
1695 [ + + ]: 14 : if (!needsplit)
1696 : : {
1697 : : /* switch to right page */
1698 [ + - ]: 10 : Assert(pgused > 0);
1699 : 10 : leaf->lastleft = dlist_prev_node(&leaf->segments, cur_node);
1700 : 10 : needsplit = true;
1701 : 10 : leaf->lsize = pgused;
1702 : 10 : pgused = 0;
1703 : 10 : }
1704 : : else
1705 : : {
1706 : : /*
1707 : : * Filled both pages. The last segment we constructed did not
1708 : : * fit.
1709 : : */
1710 : 4 : *remaining = seginfo->seg->first;
1711 : :
1712 : : /*
1713 : : * remove all segments that did not fit from the list.
1714 : : */
1715 [ + + ]: 8 : while (dlist_has_next(&leaf->segments, cur_node))
1716 : 4 : dlist_delete(dlist_next_node(&leaf->segments, cur_node));
1717 : 4 : dlist_delete(cur_node);
1718 : 4 : break;
1719 : : }
1720 : 10 : }
1721 : :
1722 : 60274 : pgused += segsize;
1723 [ - - + + ]: 60278 : }
1724 : :
1725 [ + + ]: 3352 : if (!needsplit)
1726 : : {
1727 : 3342 : leaf->lsize = pgused;
1728 : 3342 : leaf->rsize = 0;
1729 : 3342 : }
1730 : : else
1731 : 10 : leaf->rsize = pgused;
1732 : :
1733 [ + - ]: 3352 : Assert(leaf->lsize <= GinDataPageMaxDataSize);
1734 [ + - ]: 3352 : 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 : 3352 : modified = false;
1742 [ + - + + ]: 63626 : dlist_foreach(iter, &leaf->segments)
1743 : : {
1744 : 60274 : leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
1745 : : iter.cur);
1746 : :
1747 [ + + + + ]: 60274 : if (!modified && seginfo->action != GIN_SEGMENT_UNMODIFIED)
1748 : : {
1749 : 3352 : modified = true;
1750 : 3352 : }
1751 [ + + + - ]: 56922 : else if (modified && seginfo->action == GIN_SEGMENT_UNMODIFIED)
1752 : : {
1753 : 0 : 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 : 0 : }
1760 : 60274 : }
1761 : :
1762 : 6704 : return needsplit;
1763 : 3352 : }
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 : 8 : createPostingTree(Relation index, ItemPointerData *items, uint32 nitems,
1776 : : GinStatsData *buildStats, Buffer entrybuffer)
1777 : : {
1778 : 8 : BlockNumber blkno;
1779 : 8 : Buffer buffer;
1780 : 8 : Page tmppage;
1781 : 8 : Page page;
1782 : 8 : char *ptr;
1783 : 8 : int nrootitems;
1784 : 8 : int rootsize;
1785 : 8 : bool is_build = (buildStats != NULL);
1786 : :
1787 : : /* Construct the new root page in memory first. */
1788 : 8 : tmppage = (Page) palloc(BLCKSZ);
1789 : 8 : GinInitPage(tmppage, GIN_DATA | GIN_LEAF | GIN_COMPRESSED, BLCKSZ);
1790 : 8 : 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 : 8 : nrootitems = 0;
1797 : 8 : rootsize = 0;
1798 : 8 : ptr = (char *) GinDataLeafPageGetPostingList(tmppage);
1799 [ + + ]: 121 : while (nrootitems < nitems)
1800 : : {
1801 : 118 : GinPostingList *segment;
1802 : 118 : int npacked;
1803 : 118 : int segsize;
1804 : :
1805 : 236 : segment = ginCompressPostingList(&items[nrootitems],
1806 : 118 : nitems - nrootitems,
1807 : : GinPostingListSegmentMaxSize,
1808 : : &npacked);
1809 : 118 : segsize = SizeOfGinPostingList(segment);
1810 [ + + ]: 118 : if (rootsize + segsize > GinDataPageMaxDataSize)
1811 : 5 : break;
1812 : :
1813 : 113 : memcpy(ptr, segment, segsize);
1814 : 113 : ptr += segsize;
1815 : 113 : rootsize += segsize;
1816 : 113 : nrootitems += npacked;
1817 : 113 : pfree(segment);
1818 [ - + + ]: 118 : }
1819 [ + - ]: 8 : GinDataPageSetDataSize(tmppage, rootsize);
1820 : :
1821 : : /*
1822 : : * All set. Get a new physical page, and copy the in-memory page to it.
1823 : : */
1824 : 8 : buffer = GinNewBuffer(index);
1825 : 8 : page = BufferGetPage(buffer);
1826 : 8 : 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 : 8 : PredicateLockPageSplit(index, BufferGetBlockNumber(entrybuffer), blkno);
1833 : :
1834 : 8 : START_CRIT_SECTION();
1835 : :
1836 : 8 : PageRestoreTempPage(tmppage, page);
1837 : 8 : MarkBufferDirty(buffer);
1838 : :
1839 [ + + + - : 8 : if (RelationNeedsWAL(index) && !is_build)
+ + + + ]
1840 : : {
1841 : 3 : XLogRecPtr recptr;
1842 : 3 : ginxlogCreatePostingTree data;
1843 : :
1844 : 3 : data.size = rootsize;
1845 : :
1846 : 3 : XLogBeginInsert();
1847 : 3 : XLogRegisterData(&data, sizeof(ginxlogCreatePostingTree));
1848 : :
1849 : 6 : XLogRegisterData(GinDataLeafPageGetPostingList(page),
1850 : 3 : rootsize);
1851 : 3 : XLogRegisterBuffer(0, buffer, REGBUF_WILL_INIT);
1852 : :
1853 : 3 : recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_CREATE_PTREE);
1854 : 3 : PageSetLSN(page, recptr);
1855 : 3 : }
1856 : :
1857 : 14 : UnlockReleaseBuffer(buffer);
1858 : :
1859 [ + - ]: 14 : END_CRIT_SECTION();
1860 : :
1861 : : /* During index build, count the newly-added data page */
1862 [ + + ]: 6 : if (buildStats)
1863 : 1 : buildStats->nDataPages++;
1864 : :
1865 [ - + - + ]: 6 : 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 [ + + ]: 6 : if (nitems > nrootitems)
1871 : : {
1872 : 10 : ginInsertItemPointers(index, blkno,
1873 : 5 : items + nrootitems,
1874 : 5 : nitems - nrootitems,
1875 : 5 : buildStats);
1876 : 5 : }
1877 : :
1878 : 12 : return blkno;
1879 : 6 : }
1880 : :
1881 : : static void
1882 : 3357 : ginPrepareDataScan(GinBtree btree, Relation index, BlockNumber rootBlkno)
1883 : : {
1884 : 3357 : memset(btree, 0, sizeof(GinBtreeData));
1885 : :
1886 : 3357 : btree->index = index;
1887 : 3357 : btree->rootBlkno = rootBlkno;
1888 : :
1889 : 3357 : btree->findChildPage = dataLocateItem;
1890 : 3357 : btree->getLeftMostChild = dataGetLeftMostPage;
1891 : 3357 : btree->isMoveRight = dataIsMoveRight;
1892 : 3357 : btree->findItem = NULL;
1893 : 3357 : btree->findChildPtr = dataFindChildPtr;
1894 : 3357 : btree->beginPlaceToPage = dataBeginPlaceToPage;
1895 : 3357 : btree->execPlaceToPage = dataExecPlaceToPage;
1896 : 3357 : btree->fillRoot = ginDataFillRoot;
1897 : 3357 : btree->prepareDownlink = dataPrepareDownlink;
1898 : :
1899 : 3357 : btree->isData = true;
1900 : 3357 : btree->fullScan = false;
1901 : 3357 : btree->isBuild = false;
1902 : 3357 : }
1903 : :
1904 : : /*
1905 : : * Inserts array of item pointers, may execute several tree scan (very rare)
1906 : : */
1907 : : void
1908 : 3348 : ginInsertItemPointers(Relation index, BlockNumber rootBlkno,
1909 : : ItemPointerData *items, uint32 nitem,
1910 : : GinStatsData *buildStats)
1911 : : {
1912 : 3348 : GinBtreeData btree;
1913 : 3348 : GinBtreeDataLeafInsertData insertdata;
1914 : 3348 : GinBtreeStack *stack;
1915 : :
1916 : 3348 : ginPrepareDataScan(&btree, index, rootBlkno);
1917 : 3348 : btree.isBuild = (buildStats != NULL);
1918 : 3348 : insertdata.items = items;
1919 : 3348 : insertdata.nitem = nitem;
1920 : 3348 : insertdata.curitem = 0;
1921 : :
1922 [ + + ]: 6700 : while (insertdata.curitem < insertdata.nitem)
1923 : : {
1924 : : /* search for the leaf page where the first item should go to */
1925 : 3352 : btree.itemptr = insertdata.items[insertdata.curitem];
1926 : 3352 : stack = ginFindLeafPage(&btree, false, true);
1927 : :
1928 : 3352 : ginInsertValue(&btree, stack, &insertdata, buildStats);
1929 : : }
1930 : 3348 : }
1931 : :
1932 : : /*
1933 : : * Starts a new scan on a posting tree.
1934 : : */
1935 : : GinBtreeStack *
1936 : 9 : ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno)
1937 : : {
1938 : 9 : GinBtreeStack *stack;
1939 : :
1940 : 9 : ginPrepareDataScan(btree, index, rootBlkno);
1941 : :
1942 : 9 : btree->fullScan = true;
1943 : :
1944 : 9 : stack = ginFindLeafPage(btree, true, false);
1945 : :
1946 : 18 : return stack;
1947 : 9 : }
|
