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