PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
gist.c
Go to the documentation of this file.
1/*-------------------------------------------------------------------------
2 *
3 * gist.c
4 * interface routines for the postgres GiST index access method.
5 *
6 *
7 * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
9 *
10 * IDENTIFICATION
11 * src/backend/access/gist/gist.c
12 *
13 *-------------------------------------------------------------------------
14 */
15#include "postgres.h"
16
17#include "access/gist_private.h"
18#include "access/gistscan.h"
19#include "access/xloginsert.h"
21#include "commands/vacuum.h"
22#include "miscadmin.h"
23#include "nodes/execnodes.h"
24#include "storage/predicate.h"
25#include "utils/fmgrprotos.h"
27#include "utils/memutils.h"
28#include "utils/rel.h"
29
30/* non-export function prototypes */
31static void gistfixsplit(GISTInsertState *state, GISTSTATE *giststate);
33 GISTSTATE *giststate, IndexTuple tuple, OffsetNumber oldoffnum);
35 GISTSTATE *giststate,
36 IndexTuple *tuples, int ntup, OffsetNumber oldoffnum,
38 bool unlockbuf, bool unlockleftchild);
40 GISTSTATE *giststate, List *splitinfo, bool unlockbuf);
41static void gistprunepage(Relation rel, Page page, Buffer buffer,
42 Relation heapRel);
43
44
45#define ROTATEDIST(d) do { \
46 SplitPageLayout *tmp = (SplitPageLayout *) palloc0(sizeof(SplitPageLayout)); \
47 tmp->block.blkno = InvalidBlockNumber; \
48 tmp->buffer = InvalidBuffer; \
49 tmp->next = (d); \
50 (d)=tmp; \
51} while(0)
52
53
54/*
55 * GiST handler function: return IndexAmRoutine with access method parameters
56 * and callbacks.
57 */
60{
62
63 amroutine->amstrategies = 0;
64 amroutine->amsupport = GISTNProcs;
66 amroutine->amcanorder = false;
67 amroutine->amcanorderbyop = true;
68 amroutine->amcanbackward = false;
69 amroutine->amcanunique = false;
70 amroutine->amcanmulticol = true;
71 amroutine->amoptionalkey = true;
72 amroutine->amsearcharray = false;
73 amroutine->amsearchnulls = true;
74 amroutine->amstorage = true;
75 amroutine->amclusterable = true;
76 amroutine->ampredlocks = true;
77 amroutine->amcanparallel = false;
78 amroutine->amcanbuildparallel = false;
79 amroutine->amcaninclude = true;
80 amroutine->amusemaintenanceworkmem = false;
81 amroutine->amsummarizing = false;
82 amroutine->amparallelvacuumoptions =
84 amroutine->amkeytype = InvalidOid;
85
86 amroutine->ambuild = gistbuild;
87 amroutine->ambuildempty = gistbuildempty;
88 amroutine->aminsert = gistinsert;
89 amroutine->aminsertcleanup = NULL;
90 amroutine->ambulkdelete = gistbulkdelete;
92 amroutine->amcanreturn = gistcanreturn;
94 amroutine->amgettreeheight = NULL;
95 amroutine->amoptions = gistoptions;
96 amroutine->amproperty = gistproperty;
97 amroutine->ambuildphasename = NULL;
98 amroutine->amvalidate = gistvalidate;
100 amroutine->ambeginscan = gistbeginscan;
101 amroutine->amrescan = gistrescan;
102 amroutine->amgettuple = gistgettuple;
103 amroutine->amgetbitmap = gistgetbitmap;
104 amroutine->amendscan = gistendscan;
105 amroutine->ammarkpos = NULL;
106 amroutine->amrestrpos = NULL;
107 amroutine->amestimateparallelscan = NULL;
108 amroutine->aminitparallelscan = NULL;
109 amroutine->amparallelrescan = NULL;
110
111 PG_RETURN_POINTER(amroutine);
112}
113
114/*
115 * Create and return a temporary memory context for use by GiST. We
116 * _always_ invoke user-provided methods in a temporary memory
117 * context, so that memory leaks in those functions cannot cause
118 * problems. Also, we use some additional temporary contexts in the
119 * GiST code itself, to avoid the need to do some awkward manual
120 * memory management.
121 */
124{
126 "GiST temporary context",
128}
129
130/*
131 * gistbuildempty() -- build an empty gist index in the initialization fork
132 */
133void
135{
136 Buffer buffer;
137
138 /* Initialize the root page */
141
142 /* Initialize and xlog buffer */
144 GISTInitBuffer(buffer, F_LEAF);
145 MarkBufferDirty(buffer);
146 log_newpage_buffer(buffer, true);
148
149 /* Unlock and release the buffer */
150 UnlockReleaseBuffer(buffer);
151}
152
153/*
154 * gistinsert -- wrapper for GiST tuple insertion.
155 *
156 * This is the public interface routine for tuple insertion in GiSTs.
157 * It doesn't do any work; just locks the relation and passes the buck.
158 */
159bool
160gistinsert(Relation r, Datum *values, bool *isnull,
161 ItemPointer ht_ctid, Relation heapRel,
162 IndexUniqueCheck checkUnique,
163 bool indexUnchanged,
164 IndexInfo *indexInfo)
165{
166 GISTSTATE *giststate = (GISTSTATE *) indexInfo->ii_AmCache;
167 IndexTuple itup;
168 MemoryContext oldCxt;
169
170 /* Initialize GISTSTATE cache if first call in this statement */
171 if (giststate == NULL)
172 {
173 oldCxt = MemoryContextSwitchTo(indexInfo->ii_Context);
174 giststate = initGISTstate(r);
175 giststate->tempCxt = createTempGistContext();
176 indexInfo->ii_AmCache = giststate;
177 MemoryContextSwitchTo(oldCxt);
178 }
179
180 oldCxt = MemoryContextSwitchTo(giststate->tempCxt);
181
182 itup = gistFormTuple(giststate, r, values, isnull, true);
183 itup->t_tid = *ht_ctid;
184
185 gistdoinsert(r, itup, 0, giststate, heapRel, false);
186
187 /* cleanup */
188 MemoryContextSwitchTo(oldCxt);
189 MemoryContextReset(giststate->tempCxt);
190
191 return false;
192}
193
194
195/*
196 * Place tuples from 'itup' to 'buffer'. If 'oldoffnum' is valid, the tuple
197 * at that offset is atomically removed along with inserting the new tuples.
198 * This is used to replace a tuple with a new one.
199 *
200 * If 'leftchildbuf' is valid, we're inserting the downlink for the page
201 * to the right of 'leftchildbuf', or updating the downlink for 'leftchildbuf'.
202 * F_FOLLOW_RIGHT flag on 'leftchildbuf' is cleared and NSN is set.
203 *
204 * If 'markfollowright' is true and the page is split, the left child is
205 * marked with F_FOLLOW_RIGHT flag. That is the normal case. During buffered
206 * index build, however, there is no concurrent access and the page splitting
207 * is done in a slightly simpler fashion, and false is passed.
208 *
209 * If there is not enough room on the page, it is split. All the split
210 * pages are kept pinned and locked and returned in *splitinfo, the caller
211 * is responsible for inserting the downlinks for them. However, if
212 * 'buffer' is the root page and it needs to be split, gistplacetopage()
213 * performs the split as one atomic operation, and *splitinfo is set to NIL.
214 * In that case, we continue to hold the root page locked, and the child
215 * pages are released; note that new tuple(s) are *not* on the root page
216 * but in one of the new child pages.
217 *
218 * If 'newblkno' is not NULL, returns the block number of page the first
219 * new/updated tuple was inserted to. Usually it's the given page, but could
220 * be its right sibling if the page was split.
221 *
222 * Returns 'true' if the page was split, 'false' otherwise.
223 */
224bool
225gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
226 Buffer buffer,
227 IndexTuple *itup, int ntup, OffsetNumber oldoffnum,
228 BlockNumber *newblkno,
229 Buffer leftchildbuf,
230 List **splitinfo,
231 bool markfollowright,
232 Relation heapRel,
233 bool is_build)
234{
235 BlockNumber blkno = BufferGetBlockNumber(buffer);
236 Page page = BufferGetPage(buffer);
237 bool is_leaf = (GistPageIsLeaf(page)) ? true : false;
238 XLogRecPtr recptr;
239 bool is_split;
240
241 /*
242 * Refuse to modify a page that's incompletely split. This should not
243 * happen because we finish any incomplete splits while we walk down the
244 * tree. However, it's remotely possible that another concurrent inserter
245 * splits a parent page, and errors out before completing the split. We
246 * will just throw an error in that case, and leave any split we had in
247 * progress unfinished too. The next insert that comes along will clean up
248 * the mess.
249 */
250 if (GistFollowRight(page))
251 elog(ERROR, "concurrent GiST page split was incomplete");
252
253 /* should never try to insert to a deleted page */
255
256 *splitinfo = NIL;
257
258 /*
259 * if isupdate, remove old key: This node's key has been modified, either
260 * because a child split occurred or because we needed to adjust our key
261 * for an insert in a child node. Therefore, remove the old version of
262 * this node's key.
263 *
264 * for WAL replay, in the non-split case we handle this by setting up a
265 * one-element todelete array; in the split case, it's handled implicitly
266 * because the tuple vector passed to gistSplit won't include this tuple.
267 */
268 is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
269
270 /*
271 * If leaf page is full, try at first to delete dead tuples. And then
272 * check again.
273 */
274 if (is_split && GistPageIsLeaf(page) && GistPageHasGarbage(page))
275 {
276 gistprunepage(rel, page, buffer, heapRel);
277 is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
278 }
279
280 if (is_split)
281 {
282 /* no space for insertion */
283 IndexTuple *itvec;
284 int tlen;
285 SplitPageLayout *dist = NULL,
286 *ptr;
288 GistNSN oldnsn = 0;
289 SplitPageLayout rootpg;
290 bool is_rootsplit;
291 int npage;
292
293 is_rootsplit = (blkno == GIST_ROOT_BLKNO);
294
295 /*
296 * Form index tuples vector to split. If we're replacing an old tuple,
297 * remove the old version from the vector.
298 */
299 itvec = gistextractpage(page, &tlen);
300 if (OffsetNumberIsValid(oldoffnum))
301 {
302 /* on inner page we should remove old tuple */
303 int pos = oldoffnum - FirstOffsetNumber;
304
305 tlen--;
306 if (pos != tlen)
307 memmove(itvec + pos, itvec + pos + 1, sizeof(IndexTuple) * (tlen - pos));
308 }
309 itvec = gistjoinvector(itvec, &tlen, itup, ntup);
310 dist = gistSplit(rel, page, itvec, tlen, giststate);
311
312 /*
313 * Check that split didn't produce too many pages.
314 */
315 npage = 0;
316 for (ptr = dist; ptr; ptr = ptr->next)
317 npage++;
318 /* in a root split, we'll add one more page to the list below */
319 if (is_rootsplit)
320 npage++;
321 if (npage > GIST_MAX_SPLIT_PAGES)
322 elog(ERROR, "GiST page split into too many halves (%d, maximum %d)",
323 npage, GIST_MAX_SPLIT_PAGES);
324
325 /*
326 * Set up pages to work with. Allocate new buffers for all but the
327 * leftmost page. The original page becomes the new leftmost page, and
328 * is just replaced with the new contents.
329 *
330 * For a root-split, allocate new buffers for all child pages, the
331 * original page is overwritten with new root page containing
332 * downlinks to the new child pages.
333 */
334 ptr = dist;
335 if (!is_rootsplit)
336 {
337 /* save old rightlink and NSN */
338 oldrlink = GistPageGetOpaque(page)->rightlink;
339 oldnsn = GistPageGetNSN(page);
340
341 dist->buffer = buffer;
342 dist->block.blkno = BufferGetBlockNumber(buffer);
344
345 /* clean all flags except F_LEAF */
346 GistPageGetOpaque(dist->page)->flags = (is_leaf) ? F_LEAF : 0;
347
348 ptr = ptr->next;
349 }
350 for (; ptr; ptr = ptr->next)
351 {
352 /* Allocate new page */
353 ptr->buffer = gistNewBuffer(rel, heapRel);
354 GISTInitBuffer(ptr->buffer, (is_leaf) ? F_LEAF : 0);
355 ptr->page = BufferGetPage(ptr->buffer);
356 ptr->block.blkno = BufferGetBlockNumber(ptr->buffer);
358 BufferGetBlockNumber(buffer),
359 BufferGetBlockNumber(ptr->buffer));
360 }
361
362 /*
363 * Now that we know which blocks the new pages go to, set up downlink
364 * tuples to point to them.
365 */
366 for (ptr = dist; ptr; ptr = ptr->next)
367 {
368 ItemPointerSetBlockNumber(&(ptr->itup->t_tid), ptr->block.blkno);
369 GistTupleSetValid(ptr->itup);
370 }
371
372 /*
373 * If this is a root split, we construct the new root page with the
374 * downlinks here directly, instead of requiring the caller to insert
375 * them. Add the new root page to the list along with the child pages.
376 */
377 if (is_rootsplit)
378 {
379 IndexTuple *downlinks;
380 int ndownlinks = 0;
381 int i;
382
383 rootpg.buffer = buffer;
385 GistPageGetOpaque(rootpg.page)->flags = 0;
386
387 /* Prepare a vector of all the downlinks */
388 for (ptr = dist; ptr; ptr = ptr->next)
389 ndownlinks++;
390 downlinks = palloc(sizeof(IndexTuple) * ndownlinks);
391 for (i = 0, ptr = dist; ptr; ptr = ptr->next)
392 downlinks[i++] = ptr->itup;
393
394 rootpg.block.blkno = GIST_ROOT_BLKNO;
395 rootpg.block.num = ndownlinks;
396 rootpg.list = gistfillitupvec(downlinks, ndownlinks,
397 &(rootpg.lenlist));
398 rootpg.itup = NULL;
399
400 rootpg.next = dist;
401 dist = &rootpg;
402 }
403 else
404 {
405 /* Prepare split-info to be returned to caller */
406 for (ptr = dist; ptr; ptr = ptr->next)
407 {
409
410 si->buf = ptr->buffer;
411 si->downlink = ptr->itup;
412 *splitinfo = lappend(*splitinfo, si);
413 }
414 }
415
416 /*
417 * Fill all pages. All the pages are new, ie. freshly allocated empty
418 * pages, or a temporary copy of the old page.
419 */
420 for (ptr = dist; ptr; ptr = ptr->next)
421 {
422 char *data = (char *) (ptr->list);
423
424 for (int i = 0; i < ptr->block.num; i++)
425 {
426 IndexTuple thistup = (IndexTuple) data;
427
428 if (PageAddItem(ptr->page, (Item) data, IndexTupleSize(thistup), i + FirstOffsetNumber, false, false) == InvalidOffsetNumber)
429 elog(ERROR, "failed to add item to index page in \"%s\"", RelationGetRelationName(rel));
430
431 /*
432 * If this is the first inserted/updated tuple, let the caller
433 * know which page it landed on.
434 */
435 if (newblkno && ItemPointerEquals(&thistup->t_tid, &(*itup)->t_tid))
436 *newblkno = ptr->block.blkno;
437
438 data += IndexTupleSize(thistup);
439 }
440
441 /* Set up rightlinks */
442 if (ptr->next && ptr->block.blkno != GIST_ROOT_BLKNO)
443 GistPageGetOpaque(ptr->page)->rightlink =
444 ptr->next->block.blkno;
445 else
446 GistPageGetOpaque(ptr->page)->rightlink = oldrlink;
447
448 /*
449 * Mark the all but the right-most page with the follow-right
450 * flag. It will be cleared as soon as the downlink is inserted
451 * into the parent, but this ensures that if we error out before
452 * that, the index is still consistent. (in buffering build mode,
453 * any error will abort the index build anyway, so this is not
454 * needed.)
455 */
456 if (ptr->next && !is_rootsplit && markfollowright)
457 GistMarkFollowRight(ptr->page);
458 else
459 GistClearFollowRight(ptr->page);
460
461 /*
462 * Copy the NSN of the original page to all pages. The
463 * F_FOLLOW_RIGHT flags ensure that scans will follow the
464 * rightlinks until the downlinks are inserted.
465 */
466 GistPageSetNSN(ptr->page, oldnsn);
467 }
468
469 /*
470 * gistXLogSplit() needs to WAL log a lot of pages, prepare WAL
471 * insertion for that. NB: The number of pages and data segments
472 * specified here must match the calculations in gistXLogSplit()!
473 */
474 if (!is_build && RelationNeedsWAL(rel))
475 XLogEnsureRecordSpace(npage, 1 + npage * 2);
476
478
479 /*
480 * Must mark buffers dirty before XLogInsert, even though we'll still
481 * be changing their opaque fields below.
482 */
483 for (ptr = dist; ptr; ptr = ptr->next)
484 MarkBufferDirty(ptr->buffer);
485 if (BufferIsValid(leftchildbuf))
486 MarkBufferDirty(leftchildbuf);
487
488 /*
489 * The first page in the chain was a temporary working copy meant to
490 * replace the old page. Copy it over the old page.
491 */
493 dist->page = BufferGetPage(dist->buffer);
494
495 /*
496 * Write the WAL record.
497 *
498 * If we're building a new index, however, we don't WAL-log changes
499 * yet. The LSN-NSN interlock between parent and child requires that
500 * LSNs never move backwards, so set the LSNs to a value that's
501 * smaller than any real or fake unlogged LSN that might be generated
502 * later. (There can't be any concurrent scans during index build, so
503 * we don't need to be able to detect concurrent splits yet.)
504 */
505 if (is_build)
506 recptr = GistBuildLSN;
507 else
508 {
509 if (RelationNeedsWAL(rel))
510 recptr = gistXLogSplit(is_leaf,
511 dist, oldrlink, oldnsn, leftchildbuf,
512 markfollowright);
513 else
514 recptr = gistGetFakeLSN(rel);
515 }
516
517 for (ptr = dist; ptr; ptr = ptr->next)
518 PageSetLSN(ptr->page, recptr);
519
520 /*
521 * Return the new child buffers to the caller.
522 *
523 * If this was a root split, we've already inserted the downlink
524 * pointers, in the form of a new root page. Therefore we can release
525 * all the new buffers, and keep just the root page locked.
526 */
527 if (is_rootsplit)
528 {
529 for (ptr = dist->next; ptr; ptr = ptr->next)
530 UnlockReleaseBuffer(ptr->buffer);
531 }
532 }
533 else
534 {
535 /*
536 * Enough space. We always get here if ntup==0.
537 */
539
540 /*
541 * Delete old tuple if any, then insert new tuple(s) if any. If
542 * possible, use the fast path of PageIndexTupleOverwrite.
543 */
544 if (OffsetNumberIsValid(oldoffnum))
545 {
546 if (ntup == 1)
547 {
548 /* One-for-one replacement, so use PageIndexTupleOverwrite */
549 if (!PageIndexTupleOverwrite(page, oldoffnum, (Item) *itup,
550 IndexTupleSize(*itup)))
551 elog(ERROR, "failed to add item to index page in \"%s\"",
553 }
554 else
555 {
556 /* Delete old, then append new tuple(s) to page */
557 PageIndexTupleDelete(page, oldoffnum);
558 gistfillbuffer(page, itup, ntup, InvalidOffsetNumber);
559 }
560 }
561 else
562 {
563 /* Just append new tuples at the end of the page */
564 gistfillbuffer(page, itup, ntup, InvalidOffsetNumber);
565 }
566
567 MarkBufferDirty(buffer);
568
569 if (BufferIsValid(leftchildbuf))
570 MarkBufferDirty(leftchildbuf);
571
572 if (is_build)
573 recptr = GistBuildLSN;
574 else
575 {
576 if (RelationNeedsWAL(rel))
577 {
578 OffsetNumber ndeloffs = 0,
579 deloffs[1];
580
581 if (OffsetNumberIsValid(oldoffnum))
582 {
583 deloffs[0] = oldoffnum;
584 ndeloffs = 1;
585 }
586
587 recptr = gistXLogUpdate(buffer,
588 deloffs, ndeloffs, itup, ntup,
589 leftchildbuf);
590 }
591 else
592 recptr = gistGetFakeLSN(rel);
593 }
594 PageSetLSN(page, recptr);
595
596 if (newblkno)
597 *newblkno = blkno;
598 }
599
600 /*
601 * If we inserted the downlink for a child page, set NSN and clear
602 * F_FOLLOW_RIGHT flag on the left child, so that concurrent scans know to
603 * follow the rightlink if and only if they looked at the parent page
604 * before we inserted the downlink.
605 *
606 * Note that we do this *after* writing the WAL record. That means that
607 * the possible full page image in the WAL record does not include these
608 * changes, and they must be replayed even if the page is restored from
609 * the full page image. There's a chicken-and-egg problem: if we updated
610 * the child pages first, we wouldn't know the recptr of the WAL record
611 * we're about to write.
612 */
613 if (BufferIsValid(leftchildbuf))
614 {
615 Page leftpg = BufferGetPage(leftchildbuf);
616
617 GistPageSetNSN(leftpg, recptr);
618 GistClearFollowRight(leftpg);
619
620 PageSetLSN(leftpg, recptr);
621 }
622
624
625 return is_split;
626}
627
628/*
629 * Workhorse routine for doing insertion into a GiST index. Note that
630 * this routine assumes it is invoked in a short-lived memory context,
631 * so it does not bother releasing palloc'd allocations.
632 */
633void
635 GISTSTATE *giststate, Relation heapRel, bool is_build)
636{
637 ItemId iid;
638 IndexTuple idxtuple;
639 GISTInsertStack firststack;
640 GISTInsertStack *stack;
642 bool xlocked = false;
643
644 memset(&state, 0, sizeof(GISTInsertState));
645 state.freespace = freespace;
646 state.r = r;
647 state.heapRel = heapRel;
648 state.is_build = is_build;
649
650 /* Start from the root */
651 firststack.blkno = GIST_ROOT_BLKNO;
652 firststack.lsn = 0;
653 firststack.retry_from_parent = false;
654 firststack.parent = NULL;
656 state.stack = stack = &firststack;
657
658 /*
659 * Walk down along the path of smallest penalty, updating the parent
660 * pointers with the key we're inserting as we go. If we crash in the
661 * middle, the tree is consistent, although the possible parent updates
662 * were a waste.
663 */
664 for (;;)
665 {
666 /*
667 * If we split an internal page while descending the tree, we have to
668 * retry at the parent. (Normally, the LSN-NSN interlock below would
669 * also catch this and cause us to retry. But LSNs are not updated
670 * during index build.)
671 */
672 while (stack->retry_from_parent)
673 {
674 if (xlocked)
676 xlocked = false;
677 ReleaseBuffer(stack->buffer);
678 state.stack = stack = stack->parent;
679 }
680
681 if (XLogRecPtrIsInvalid(stack->lsn))
682 stack->buffer = ReadBuffer(state.r, stack->blkno);
683
684 /*
685 * Be optimistic and grab shared lock first. Swap it for an exclusive
686 * lock later if we need to update the page.
687 */
688 if (!xlocked)
689 {
691 gistcheckpage(state.r, stack->buffer);
692 }
693
694 stack->page = (Page) BufferGetPage(stack->buffer);
695 stack->lsn = xlocked ?
696 PageGetLSN(stack->page) : BufferGetLSNAtomic(stack->buffer);
698
699 /*
700 * If this page was split but the downlink was never inserted to the
701 * parent because the inserting backend crashed before doing that, fix
702 * that now.
703 */
704 if (GistFollowRight(stack->page))
705 {
706 if (!xlocked)
707 {
710 xlocked = true;
711 /* someone might've completed the split when we unlocked */
712 if (!GistFollowRight(stack->page))
713 continue;
714 }
715 gistfixsplit(&state, giststate);
716
718 xlocked = false;
719 state.stack = stack = stack->parent;
720 continue;
721 }
722
723 if ((stack->blkno != GIST_ROOT_BLKNO &&
724 stack->parent->lsn < GistPageGetNSN(stack->page)) ||
725 GistPageIsDeleted(stack->page))
726 {
727 /*
728 * Concurrent split or page deletion detected. There's no
729 * guarantee that the downlink for this page is consistent with
730 * the tuple we're inserting anymore, so go back to parent and
731 * rechoose the best child.
732 */
734 xlocked = false;
735 state.stack = stack = stack->parent;
736 continue;
737 }
738
739 if (!GistPageIsLeaf(stack->page))
740 {
741 /*
742 * This is an internal page so continue to walk down the tree.
743 * Find the child node that has the minimum insertion penalty.
744 */
745 BlockNumber childblkno;
746 IndexTuple newtup;
747 GISTInsertStack *item;
748 OffsetNumber downlinkoffnum;
749
750 downlinkoffnum = gistchoose(state.r, stack->page, itup, giststate);
751 iid = PageGetItemId(stack->page, downlinkoffnum);
752 idxtuple = (IndexTuple) PageGetItem(stack->page, iid);
753 childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
754
755 /*
756 * Check that it's not a leftover invalid tuple from pre-9.1
757 */
758 if (GistTupleIsInvalid(idxtuple))
760 (errmsg("index \"%s\" contains an inner tuple marked as invalid",
762 errdetail("This is caused by an incomplete page split at crash recovery before upgrading to PostgreSQL 9.1."),
763 errhint("Please REINDEX it.")));
764
765 /*
766 * Check that the key representing the target child node is
767 * consistent with the key we're inserting. Update it if it's not.
768 */
769 newtup = gistgetadjusted(state.r, idxtuple, itup, giststate);
770 if (newtup)
771 {
772 /*
773 * Swap shared lock for an exclusive one. Beware, the page may
774 * change while we unlock/lock the page...
775 */
776 if (!xlocked)
777 {
780 xlocked = true;
781 stack->page = (Page) BufferGetPage(stack->buffer);
782
783 if (PageGetLSN(stack->page) != stack->lsn)
784 {
785 /* the page was changed while we unlocked it, retry */
786 continue;
787 }
788 }
789
790 /*
791 * Update the tuple.
792 *
793 * We still hold the lock after gistinserttuple(), but it
794 * might have to split the page to make the updated tuple fit.
795 * In that case the updated tuple might migrate to the other
796 * half of the split, so we have to go back to the parent and
797 * descend back to the half that's a better fit for the new
798 * tuple.
799 */
800 if (gistinserttuple(&state, stack, giststate, newtup,
801 downlinkoffnum))
802 {
803 /*
804 * If this was a root split, the root page continues to be
805 * the parent and the updated tuple went to one of the
806 * child pages, so we just need to retry from the root
807 * page.
808 */
809 if (stack->blkno != GIST_ROOT_BLKNO)
810 {
812 xlocked = false;
813 state.stack = stack = stack->parent;
814 }
815 continue;
816 }
817 }
819 xlocked = false;
820
821 /* descend to the chosen child */
822 item = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
823 item->blkno = childblkno;
824 item->parent = stack;
825 item->downlinkoffnum = downlinkoffnum;
826 state.stack = stack = item;
827 }
828 else
829 {
830 /*
831 * Leaf page. Insert the new key. We've already updated all the
832 * parents on the way down, but we might have to split the page if
833 * it doesn't fit. gistinserttuple() will take care of that.
834 */
835
836 /*
837 * Swap shared lock for an exclusive one. Be careful, the page may
838 * change while we unlock/lock the page...
839 */
840 if (!xlocked)
841 {
844 xlocked = true;
845 stack->page = (Page) BufferGetPage(stack->buffer);
846 stack->lsn = PageGetLSN(stack->page);
847
848 if (stack->blkno == GIST_ROOT_BLKNO)
849 {
850 /*
851 * the only page that can become inner instead of leaf is
852 * the root page, so for root we should recheck it
853 */
854 if (!GistPageIsLeaf(stack->page))
855 {
856 /*
857 * very rare situation: during unlock/lock index with
858 * number of pages = 1 was increased
859 */
861 xlocked = false;
862 continue;
863 }
864
865 /*
866 * we don't need to check root split, because checking
867 * leaf/inner is enough to recognize split for root
868 */
869 }
870 else if ((GistFollowRight(stack->page) ||
871 stack->parent->lsn < GistPageGetNSN(stack->page)) ||
872 GistPageIsDeleted(stack->page))
873 {
874 /*
875 * The page was split or deleted while we momentarily
876 * unlocked the page. Go back to parent.
877 */
879 xlocked = false;
880 state.stack = stack = stack->parent;
881 continue;
882 }
883 }
884
885 /* now state.stack->(page, buffer and blkno) points to leaf page */
886
887 gistinserttuple(&state, stack, giststate, itup,
890
891 /* Release any pins we might still hold before exiting */
892 for (; stack; stack = stack->parent)
893 ReleaseBuffer(stack->buffer);
894 break;
895 }
896 }
897}
898
899/*
900 * Traverse the tree to find path from root page to specified "child" block.
901 *
902 * returns a new insertion stack, starting from the parent of "child", up
903 * to the root. *downlinkoffnum is set to the offset of the downlink in the
904 * direct parent of child.
905 *
906 * To prevent deadlocks, this should lock only one page at a time.
907 */
908static GISTInsertStack *
910{
911 Page page;
912 Buffer buffer;
914 maxoff;
915 ItemId iid;
916 IndexTuple idxtuple;
917 List *fifo;
918 GISTInsertStack *top,
919 *ptr;
920 BlockNumber blkno;
921
922 top = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
923 top->blkno = GIST_ROOT_BLKNO;
925
926 fifo = list_make1(top);
927 while (fifo != NIL)
928 {
929 /* Get next page to visit */
930 top = linitial(fifo);
931 fifo = list_delete_first(fifo);
932
933 buffer = ReadBuffer(r, top->blkno);
934 LockBuffer(buffer, GIST_SHARE);
935 gistcheckpage(r, buffer);
936 page = (Page) BufferGetPage(buffer);
937
938 if (GistPageIsLeaf(page))
939 {
940 /*
941 * Because we scan the index top-down, all the rest of the pages
942 * in the queue must be leaf pages as well.
943 */
944 UnlockReleaseBuffer(buffer);
945 break;
946 }
947
948 /* currently, internal pages are never deleted */
950
951 top->lsn = BufferGetLSNAtomic(buffer);
952
953 /*
954 * If F_FOLLOW_RIGHT is set, the page to the right doesn't have a
955 * downlink. This should not normally happen..
956 */
957 if (GistFollowRight(page))
958 elog(ERROR, "concurrent GiST page split was incomplete");
959
960 if (top->parent && top->parent->lsn < GistPageGetNSN(page) &&
961 GistPageGetOpaque(page)->rightlink != InvalidBlockNumber /* sanity check */ )
962 {
963 /*
964 * Page was split while we looked elsewhere. We didn't see the
965 * downlink to the right page when we scanned the parent, so add
966 * it to the queue now.
967 *
968 * Put the right page ahead of the queue, so that we visit it
969 * next. That's important, because if this is the lowest internal
970 * level, just above leaves, we might already have queued up some
971 * leaf pages, and we assume that there can't be any non-leaf
972 * pages behind leaf pages.
973 */
974 ptr = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
975 ptr->blkno = GistPageGetOpaque(page)->rightlink;
977 ptr->parent = top->parent;
978
979 fifo = lcons(ptr, fifo);
980 }
981
982 maxoff = PageGetMaxOffsetNumber(page);
983
984 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
985 {
986 iid = PageGetItemId(page, i);
987 idxtuple = (IndexTuple) PageGetItem(page, iid);
988 blkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
989 if (blkno == child)
990 {
991 /* Found it! */
992 UnlockReleaseBuffer(buffer);
993 *downlinkoffnum = i;
994 return top;
995 }
996 else
997 {
998 /* Append this child to the list of pages to visit later */
999 ptr = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
1000 ptr->blkno = blkno;
1001 ptr->downlinkoffnum = i;
1002 ptr->parent = top;
1003
1004 fifo = lappend(fifo, ptr);
1005 }
1006 }
1007
1008 UnlockReleaseBuffer(buffer);
1009 }
1010
1011 elog(ERROR, "failed to re-find parent of a page in index \"%s\", block %u",
1012 RelationGetRelationName(r), child);
1013 return NULL; /* keep compiler quiet */
1014}
1015
1016/*
1017 * Updates the stack so that child->parent is the correct parent of the
1018 * child. child->parent must be exclusively locked on entry, and will
1019 * remain so at exit, but it might not be the same page anymore.
1020 */
1021static void
1023{
1024 GISTInsertStack *parent = child->parent;
1025 ItemId iid;
1026 IndexTuple idxtuple;
1027 OffsetNumber maxoff;
1028 GISTInsertStack *ptr;
1029
1030 gistcheckpage(r, parent->buffer);
1031 parent->page = (Page) BufferGetPage(parent->buffer);
1032 maxoff = PageGetMaxOffsetNumber(parent->page);
1033
1034 /* Check if the downlink is still where it was before */
1035 if (child->downlinkoffnum != InvalidOffsetNumber && child->downlinkoffnum <= maxoff)
1036 {
1037 iid = PageGetItemId(parent->page, child->downlinkoffnum);
1038 idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
1039 if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
1040 return; /* still there */
1041 }
1042
1043 /*
1044 * The page has changed since we looked. During normal operation, every
1045 * update of a page changes its LSN, so the LSN we memorized should have
1046 * changed too. During index build, however, we don't WAL-log the changes
1047 * until we have built the index, so the LSN doesn't change. There is no
1048 * concurrent activity during index build, but we might have changed the
1049 * parent ourselves.
1050 */
1051 Assert(parent->lsn != PageGetLSN(parent->page) || is_build);
1052
1053 /*
1054 * Scan the page to re-find the downlink. If the page was split, it might
1055 * have moved to a different page, so follow the right links until we find
1056 * it.
1057 */
1058 while (true)
1059 {
1061
1062 maxoff = PageGetMaxOffsetNumber(parent->page);
1063 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1064 {
1065 iid = PageGetItemId(parent->page, i);
1066 idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
1067 if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
1068 {
1069 /* yes!!, found */
1070 child->downlinkoffnum = i;
1071 return;
1072 }
1073 }
1074
1075 parent->blkno = GistPageGetOpaque(parent->page)->rightlink;
1077 UnlockReleaseBuffer(parent->buffer);
1078 if (parent->blkno == InvalidBlockNumber)
1079 {
1080 /*
1081 * End of chain and still didn't find parent. It's a very-very
1082 * rare situation when the root was split.
1083 */
1084 break;
1085 }
1086 parent->buffer = ReadBuffer(r, parent->blkno);
1088 gistcheckpage(r, parent->buffer);
1089 parent->page = (Page) BufferGetPage(parent->buffer);
1090 }
1091
1092 /*
1093 * awful!!, we need search tree to find parent ... , but before we should
1094 * release all old parent
1095 */
1096
1097 ptr = child->parent->parent; /* child->parent already released above */
1098 while (ptr)
1099 {
1100 ReleaseBuffer(ptr->buffer);
1101 ptr = ptr->parent;
1102 }
1103
1104 /* ok, find new path */
1105 ptr = parent = gistFindPath(r, child->blkno, &child->downlinkoffnum);
1106
1107 /* read all buffers as expected by caller */
1108 /* note we don't lock them or gistcheckpage them here! */
1109 while (ptr)
1110 {
1111 ptr->buffer = ReadBuffer(r, ptr->blkno);
1112 ptr->page = (Page) BufferGetPage(ptr->buffer);
1113 ptr = ptr->parent;
1114 }
1115
1116 /* install new chain of parents to stack */
1117 child->parent = parent;
1118
1119 /* make recursive call to normal processing */
1121 gistFindCorrectParent(r, child, is_build);
1122}
1123
1124/*
1125 * Form a downlink pointer for the page in 'buf'.
1126 */
1127static IndexTuple
1129 GISTInsertStack *stack, bool is_build)
1130{
1131 Page page = BufferGetPage(buf);
1132 OffsetNumber maxoff;
1133 OffsetNumber offset;
1134 IndexTuple downlink = NULL;
1135
1136 maxoff = PageGetMaxOffsetNumber(page);
1137 for (offset = FirstOffsetNumber; offset <= maxoff; offset = OffsetNumberNext(offset))
1138 {
1139 IndexTuple ituple = (IndexTuple)
1140 PageGetItem(page, PageGetItemId(page, offset));
1141
1142 if (downlink == NULL)
1143 downlink = CopyIndexTuple(ituple);
1144 else
1145 {
1146 IndexTuple newdownlink;
1147
1148 newdownlink = gistgetadjusted(rel, downlink, ituple,
1149 giststate);
1150 if (newdownlink)
1151 downlink = newdownlink;
1152 }
1153 }
1154
1155 /*
1156 * If the page is completely empty, we can't form a meaningful downlink
1157 * for it. But we have to insert a downlink for the page. Any key will do,
1158 * as long as its consistent with the downlink of parent page, so that we
1159 * can legally insert it to the parent. A minimal one that matches as few
1160 * scans as possible would be best, to keep scans from doing useless work,
1161 * but we don't know how to construct that. So we just use the downlink of
1162 * the original page that was split - that's as far from optimal as it can
1163 * get but will do..
1164 */
1165 if (!downlink)
1166 {
1167 ItemId iid;
1168
1170 gistFindCorrectParent(rel, stack, is_build);
1171 iid = PageGetItemId(stack->parent->page, stack->downlinkoffnum);
1172 downlink = (IndexTuple) PageGetItem(stack->parent->page, iid);
1173 downlink = CopyIndexTuple(downlink);
1175 }
1176
1178 GistTupleSetValid(downlink);
1179
1180 return downlink;
1181}
1182
1183
1184/*
1185 * Complete the incomplete split of state->stack->page.
1186 */
1187static void
1189{
1190 GISTInsertStack *stack = state->stack;
1191 Buffer buf;
1192 Page page;
1193 List *splitinfo = NIL;
1194
1195 ereport(LOG,
1196 (errmsg("fixing incomplete split in index \"%s\", block %u",
1197 RelationGetRelationName(state->r), stack->blkno)));
1198
1199 Assert(GistFollowRight(stack->page));
1201
1202 buf = stack->buffer;
1203
1204 /*
1205 * Read the chain of split pages, following the rightlinks. Construct a
1206 * downlink tuple for each page.
1207 */
1208 for (;;)
1209 {
1211 IndexTuple downlink;
1212
1213 page = BufferGetPage(buf);
1214
1215 /* Form the new downlink tuples to insert to parent */
1216 downlink = gistformdownlink(state->r, buf, giststate, stack, state->is_build);
1217
1218 si->buf = buf;
1219 si->downlink = downlink;
1220
1221 splitinfo = lappend(splitinfo, si);
1222
1223 if (GistFollowRight(page))
1224 {
1225 /* lock next page */
1226 buf = ReadBuffer(state->r, GistPageGetOpaque(page)->rightlink);
1228 }
1229 else
1230 break;
1231 }
1232
1233 /* Insert the downlinks */
1234 gistfinishsplit(state, stack, giststate, splitinfo, false);
1235}
1236
1237/*
1238 * Insert or replace a tuple in stack->buffer. If 'oldoffnum' is valid, the
1239 * tuple at 'oldoffnum' is replaced, otherwise the tuple is inserted as new.
1240 * 'stack' represents the path from the root to the page being updated.
1241 *
1242 * The caller must hold an exclusive lock on stack->buffer. The lock is still
1243 * held on return, but the page might not contain the inserted tuple if the
1244 * page was split. The function returns true if the page was split, false
1245 * otherwise.
1246 */
1247static bool
1249 GISTSTATE *giststate, IndexTuple tuple, OffsetNumber oldoffnum)
1250{
1251 return gistinserttuples(state, stack, giststate, &tuple, 1, oldoffnum,
1252 InvalidBuffer, InvalidBuffer, false, false);
1253}
1254
1255/* ----------------
1256 * An extended workhorse version of gistinserttuple(). This version allows
1257 * inserting multiple tuples, or replacing a single tuple with multiple tuples.
1258 * This is used to recursively update the downlinks in the parent when a page
1259 * is split.
1260 *
1261 * If leftchild and rightchild are valid, we're inserting/replacing the
1262 * downlink for rightchild, and leftchild is its left sibling. We clear the
1263 * F_FOLLOW_RIGHT flag and update NSN on leftchild, atomically with the
1264 * insertion of the downlink.
1265 *
1266 * To avoid holding locks for longer than necessary, when recursing up the
1267 * tree to update the parents, the locking is a bit peculiar here. On entry,
1268 * the caller must hold an exclusive lock on stack->buffer, as well as
1269 * leftchild and rightchild if given. On return:
1270 *
1271 * - Lock on stack->buffer is released, if 'unlockbuf' is true. The page is
1272 * always kept pinned, however.
1273 * - Lock on 'leftchild' is released, if 'unlockleftchild' is true. The page
1274 * is kept pinned.
1275 * - Lock and pin on 'rightchild' are always released.
1276 *
1277 * Returns 'true' if the page had to be split. Note that if the page was
1278 * split, the inserted/updated tuples might've been inserted to a right
1279 * sibling of stack->buffer instead of stack->buffer itself.
1280 */
1281static bool
1283 GISTSTATE *giststate,
1284 IndexTuple *tuples, int ntup, OffsetNumber oldoffnum,
1286 bool unlockbuf, bool unlockleftchild)
1287{
1288 List *splitinfo;
1289 bool is_split;
1290
1291 /*
1292 * Check for any rw conflicts (in serializable isolation level) just
1293 * before we intend to modify the page
1294 */
1296
1297 /* Insert the tuple(s) to the page, splitting the page if necessary */
1298 is_split = gistplacetopage(state->r, state->freespace, giststate,
1299 stack->buffer,
1300 tuples, ntup,
1301 oldoffnum, NULL,
1302 leftchild,
1303 &splitinfo,
1304 true,
1305 state->heapRel,
1306 state->is_build);
1307
1308 /*
1309 * Before recursing up in case the page was split, release locks on the
1310 * child pages. We don't need to keep them locked when updating the
1311 * parent.
1312 */
1315 if (BufferIsValid(leftchild) && unlockleftchild)
1317
1318 /*
1319 * If we had to split, insert/update the downlinks in the parent. If the
1320 * caller requested us to release the lock on stack->buffer, tell
1321 * gistfinishsplit() to do that as soon as it's safe to do so. If we
1322 * didn't have to split, release it ourselves.
1323 */
1324 if (splitinfo)
1325 gistfinishsplit(state, stack, giststate, splitinfo, unlockbuf);
1326 else if (unlockbuf)
1327 LockBuffer(stack->buffer, GIST_UNLOCK);
1328
1329 return is_split;
1330}
1331
1332/*
1333 * Finish an incomplete split by inserting/updating the downlinks in parent
1334 * page. 'splitinfo' contains all the child pages involved in the split,
1335 * from left-to-right.
1336 *
1337 * On entry, the caller must hold a lock on stack->buffer and all the child
1338 * pages in 'splitinfo'. If 'unlockbuf' is true, the lock on stack->buffer is
1339 * released on return. The child pages are always unlocked and unpinned.
1340 */
1341static void
1343 GISTSTATE *giststate, List *splitinfo, bool unlockbuf)
1344{
1345 GISTPageSplitInfo *right;
1346 GISTPageSplitInfo *left;
1347 IndexTuple tuples[2];
1348
1349 /* A split always contains at least two halves */
1350 Assert(list_length(splitinfo) >= 2);
1351
1352 /*
1353 * We need to insert downlinks for each new page, and update the downlink
1354 * for the original (leftmost) page in the split. Begin at the rightmost
1355 * page, inserting one downlink at a time until there's only two pages
1356 * left. Finally insert the downlink for the last new page and update the
1357 * downlink for the original page as one operation.
1358 */
1360
1361 /*
1362 * Insert downlinks for the siblings from right to left, until there are
1363 * only two siblings left.
1364 */
1365 for (int pos = list_length(splitinfo) - 1; pos > 1; pos--)
1366 {
1367 right = (GISTPageSplitInfo *) list_nth(splitinfo, pos);
1368 left = (GISTPageSplitInfo *) list_nth(splitinfo, pos - 1);
1369
1370 gistFindCorrectParent(state->r, stack, state->is_build);
1371 if (gistinserttuples(state, stack->parent, giststate,
1372 &right->downlink, 1,
1374 left->buf, right->buf, false, false))
1375 {
1376 /*
1377 * If the parent page was split, the existing downlink might have
1378 * moved.
1379 */
1381 }
1382 /* gistinserttuples() released the lock on right->buf. */
1383 }
1384
1385 right = (GISTPageSplitInfo *) lsecond(splitinfo);
1386 left = (GISTPageSplitInfo *) linitial(splitinfo);
1387
1388 /*
1389 * Finally insert downlink for the remaining right page and update the
1390 * downlink for the original page to not contain the tuples that were
1391 * moved to the new pages.
1392 */
1393 tuples[0] = left->downlink;
1394 tuples[1] = right->downlink;
1395 gistFindCorrectParent(state->r, stack, state->is_build);
1396 (void) gistinserttuples(state, stack->parent, giststate,
1397 tuples, 2,
1398 stack->downlinkoffnum,
1399 left->buf, right->buf,
1400 true, /* Unlock parent */
1401 unlockbuf /* Unlock stack->buffer if caller
1402 * wants that */
1403 );
1404
1405 /*
1406 * The downlink might have moved when we updated it. Even if the page
1407 * wasn't split, because gistinserttuples() implements updating the old
1408 * tuple by removing and re-inserting it!
1409 */
1411
1412 Assert(left->buf == stack->buffer);
1413
1414 /*
1415 * If we split the page because we had to adjust the downlink on an
1416 * internal page, while descending the tree for inserting a new tuple,
1417 * then this might no longer be the correct page for the new tuple. The
1418 * downlink to this page might not cover the new tuple anymore, it might
1419 * need to go to the newly-created right sibling instead. Tell the caller
1420 * to walk back up the stack, to re-check at the parent which page to
1421 * insert to.
1422 *
1423 * Normally, the LSN-NSN interlock during the tree descend would also
1424 * detect that a concurrent split happened (by ourselves), and cause us to
1425 * retry at the parent. But that mechanism doesn't work during index
1426 * build, because we don't do WAL-logging, and don't update LSNs, during
1427 * index build.
1428 */
1429 stack->retry_from_parent = true;
1430}
1431
1432/*
1433 * gistSplit -- split a page in the tree and fill struct
1434 * used for XLOG and real writes buffers. Function is recursive, ie
1435 * it will split page until keys will fit in every page.
1436 */
1439 Page page,
1440 IndexTuple *itup, /* contains compressed entry */
1441 int len,
1442 GISTSTATE *giststate)
1443{
1444 IndexTuple *lvectup,
1445 *rvectup;
1447 int i;
1448 SplitPageLayout *res = NULL;
1449
1450 /* this should never recurse very deeply, but better safe than sorry */
1452
1453 /* there's no point in splitting an empty page */
1454 Assert(len > 0);
1455
1456 /*
1457 * If a single tuple doesn't fit on a page, no amount of splitting will
1458 * help.
1459 */
1460 if (len == 1)
1461 ereport(ERROR,
1462 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1463 errmsg("index row size %zu exceeds maximum %zu for index \"%s\"",
1464 IndexTupleSize(itup[0]), GiSTPageSize,
1466
1467 memset(v.spl_lisnull, true,
1468 sizeof(bool) * giststate->nonLeafTupdesc->natts);
1469 memset(v.spl_risnull, true,
1470 sizeof(bool) * giststate->nonLeafTupdesc->natts);
1471 gistSplitByKey(r, page, itup, len, giststate, &v, 0);
1472
1473 /* form left and right vector */
1474 lvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * (len + 1));
1475 rvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * (len + 1));
1476
1477 for (i = 0; i < v.splitVector.spl_nleft; i++)
1478 lvectup[i] = itup[v.splitVector.spl_left[i] - 1];
1479
1480 for (i = 0; i < v.splitVector.spl_nright; i++)
1481 rvectup[i] = itup[v.splitVector.spl_right[i] - 1];
1482
1483 /* finalize splitting (may need another split) */
1484 if (!gistfitpage(rvectup, v.splitVector.spl_nright))
1485 {
1486 res = gistSplit(r, page, rvectup, v.splitVector.spl_nright, giststate);
1487 }
1488 else
1489 {
1490 ROTATEDIST(res);
1491 res->block.num = v.splitVector.spl_nright;
1492 res->list = gistfillitupvec(rvectup, v.splitVector.spl_nright, &(res->lenlist));
1493 res->itup = gistFormTuple(giststate, r, v.spl_rattr, v.spl_risnull, false);
1494 }
1495
1496 if (!gistfitpage(lvectup, v.splitVector.spl_nleft))
1497 {
1498 SplitPageLayout *resptr,
1499 *subres;
1500
1501 resptr = subres = gistSplit(r, page, lvectup, v.splitVector.spl_nleft, giststate);
1502
1503 /* install on list's tail */
1504 while (resptr->next)
1505 resptr = resptr->next;
1506
1507 resptr->next = res;
1508 res = subres;
1509 }
1510 else
1511 {
1512 ROTATEDIST(res);
1513 res->block.num = v.splitVector.spl_nleft;
1514 res->list = gistfillitupvec(lvectup, v.splitVector.spl_nleft, &(res->lenlist));
1515 res->itup = gistFormTuple(giststate, r, v.spl_lattr, v.spl_lisnull, false);
1516 }
1517
1518 return res;
1519}
1520
1521/*
1522 * Create a GISTSTATE and fill it with information about the index
1523 */
1524GISTSTATE *
1526{
1527 GISTSTATE *giststate;
1528 MemoryContext scanCxt;
1529 MemoryContext oldCxt;
1530 int i;
1531
1532 /* safety check to protect fixed-size arrays in GISTSTATE */
1533 if (index->rd_att->natts > INDEX_MAX_KEYS)
1534 elog(ERROR, "numberOfAttributes %d > %d",
1535 index->rd_att->natts, INDEX_MAX_KEYS);
1536
1537 /* Create the memory context that will hold the GISTSTATE */
1539 "GiST scan context",
1541 oldCxt = MemoryContextSwitchTo(scanCxt);
1542
1543 /* Create and fill in the GISTSTATE */
1544 giststate = (GISTSTATE *) palloc(sizeof(GISTSTATE));
1545
1546 giststate->scanCxt = scanCxt;
1547 giststate->tempCxt = scanCxt; /* caller must change this if needed */
1548 giststate->leafTupdesc = index->rd_att;
1549
1550 /*
1551 * The truncated tupdesc for non-leaf index tuples, which doesn't contain
1552 * the INCLUDE attributes.
1553 *
1554 * It is used to form tuples during tuple adjustment and page split.
1555 * B-tree creates shortened tuple descriptor for every truncated tuple,
1556 * because it is doing this less often: it does not have to form truncated
1557 * tuples during page split. Also, B-tree is not adjusting tuples on
1558 * internal pages the way GiST does.
1559 */
1562
1564 {
1565 fmgr_info_copy(&(giststate->consistentFn[i]),
1567 scanCxt);
1568 fmgr_info_copy(&(giststate->unionFn[i]),
1570 scanCxt);
1571
1572 /* opclasses are not required to provide a Compress method */
1574 fmgr_info_copy(&(giststate->compressFn[i]),
1576 scanCxt);
1577 else
1578 giststate->compressFn[i].fn_oid = InvalidOid;
1579
1580 /* opclasses are not required to provide a Decompress method */
1582 fmgr_info_copy(&(giststate->decompressFn[i]),
1584 scanCxt);
1585 else
1586 giststate->decompressFn[i].fn_oid = InvalidOid;
1587
1588 fmgr_info_copy(&(giststate->penaltyFn[i]),
1590 scanCxt);
1591 fmgr_info_copy(&(giststate->picksplitFn[i]),
1593 scanCxt);
1594 fmgr_info_copy(&(giststate->equalFn[i]),
1596 scanCxt);
1597
1598 /* opclasses are not required to provide a Distance method */
1600 fmgr_info_copy(&(giststate->distanceFn[i]),
1602 scanCxt);
1603 else
1604 giststate->distanceFn[i].fn_oid = InvalidOid;
1605
1606 /* opclasses are not required to provide a Fetch method */
1608 fmgr_info_copy(&(giststate->fetchFn[i]),
1610 scanCxt);
1611 else
1612 giststate->fetchFn[i].fn_oid = InvalidOid;
1613
1614 /*
1615 * If the index column has a specified collation, we should honor that
1616 * while doing comparisons. However, we may have a collatable storage
1617 * type for a noncollatable indexed data type. If there's no index
1618 * collation then specify default collation in case the support
1619 * functions need collation. This is harmless if the support
1620 * functions don't care about collation, so we just do it
1621 * unconditionally. (We could alternatively call get_typcollation,
1622 * but that seems like expensive overkill --- there aren't going to be
1623 * any cases where a GiST storage type has a nondefault collation.)
1624 */
1625 if (OidIsValid(index->rd_indcollation[i]))
1626 giststate->supportCollation[i] = index->rd_indcollation[i];
1627 else
1628 giststate->supportCollation[i] = DEFAULT_COLLATION_OID;
1629 }
1630
1631 /* No opclass information for INCLUDE attributes */
1632 for (; i < index->rd_att->natts; i++)
1633 {
1634 giststate->consistentFn[i].fn_oid = InvalidOid;
1635 giststate->unionFn[i].fn_oid = InvalidOid;
1636 giststate->compressFn[i].fn_oid = InvalidOid;
1637 giststate->decompressFn[i].fn_oid = InvalidOid;
1638 giststate->penaltyFn[i].fn_oid = InvalidOid;
1639 giststate->picksplitFn[i].fn_oid = InvalidOid;
1640 giststate->equalFn[i].fn_oid = InvalidOid;
1641 giststate->distanceFn[i].fn_oid = InvalidOid;
1642 giststate->fetchFn[i].fn_oid = InvalidOid;
1643 giststate->supportCollation[i] = InvalidOid;
1644 }
1645
1646 MemoryContextSwitchTo(oldCxt);
1647
1648 return giststate;
1649}
1650
1651void
1653{
1654 /* It's sufficient to delete the scanCxt */
1655 MemoryContextDelete(giststate->scanCxt);
1656}
1657
1658/*
1659 * gistprunepage() -- try to remove LP_DEAD items from the given page.
1660 * Function assumes that buffer is exclusively locked.
1661 */
1662static void
1663gistprunepage(Relation rel, Page page, Buffer buffer, Relation heapRel)
1664{
1666 int ndeletable = 0;
1667 OffsetNumber offnum,
1668 maxoff;
1669
1670 Assert(GistPageIsLeaf(page));
1671
1672 /*
1673 * Scan over all items to see which ones need to be deleted according to
1674 * LP_DEAD flags.
1675 */
1676 maxoff = PageGetMaxOffsetNumber(page);
1677 for (offnum = FirstOffsetNumber;
1678 offnum <= maxoff;
1679 offnum = OffsetNumberNext(offnum))
1680 {
1681 ItemId itemId = PageGetItemId(page, offnum);
1682
1683 if (ItemIdIsDead(itemId))
1684 deletable[ndeletable++] = offnum;
1685 }
1686
1687 if (ndeletable > 0)
1688 {
1689 TransactionId snapshotConflictHorizon = InvalidTransactionId;
1690
1692 snapshotConflictHorizon =
1693 index_compute_xid_horizon_for_tuples(rel, heapRel, buffer,
1694 deletable, ndeletable);
1695
1697
1698 PageIndexMultiDelete(page, deletable, ndeletable);
1699
1700 /*
1701 * Mark the page as not containing any LP_DEAD items. This is not
1702 * certainly true (there might be some that have recently been marked,
1703 * but weren't included in our target-item list), but it will almost
1704 * always be true and it doesn't seem worth an additional page scan to
1705 * check it. Remember that F_HAS_GARBAGE is only a hint anyway.
1706 */
1708
1709 MarkBufferDirty(buffer);
1710
1711 /* XLOG stuff */
1712 if (RelationNeedsWAL(rel))
1713 {
1714 XLogRecPtr recptr;
1715
1716 recptr = gistXLogDelete(buffer,
1717 deletable, ndeletable,
1718 snapshotConflictHorizon,
1719 heapRel);
1720
1721 PageSetLSN(page, recptr);
1722 }
1723 else
1724 PageSetLSN(page, gistGetFakeLSN(rel));
1725
1727 }
1728
1729 /*
1730 * Note: if we didn't find any LP_DEAD items, then the page's
1731 * F_HAS_GARBAGE hint bit is falsely set. We do not bother expending a
1732 * separate write to clear it, however. We will clear it when we split
1733 * the page.
1734 */
1735}
uint32 BlockNumber
Definition: block.h:31
#define InvalidBlockNumber
Definition: block.h:33
static Datum values[MAXATTR]
Definition: bootstrap.c:151
int Buffer
Definition: buf.h:23
#define InvalidBuffer
Definition: buf.h:25
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:3724
Buffer ExtendBufferedRel(BufferManagerRelation bmr, ForkNumber forkNum, BufferAccessStrategy strategy, uint32 flags)
Definition: bufmgr.c:846
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:4924
XLogRecPtr BufferGetLSNAtomic(Buffer buffer)
Definition: bufmgr.c:3985
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:4941
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:2532
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:5158
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:746
static Page BufferGetPage(Buffer buffer)
Definition: bufmgr.h:400
@ EB_SKIP_EXTENSION_LOCK
Definition: bufmgr.h:74
@ EB_LOCK_FIRST
Definition: bufmgr.h:86
#define BMR_REL(p_rel)
Definition: bufmgr.h:107
static bool BufferIsValid(Buffer bufnum)
Definition: bufmgr.h:351
void PageRestoreTempPage(Page tempPage, Page oldPage)
Definition: bufpage.c:413
void PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems)
Definition: bufpage.c:1150
Page PageGetTempPageCopySpecial(Page page)
Definition: bufpage.c:391
bool PageIndexTupleOverwrite(Page page, OffsetNumber offnum, Item newtup, Size newsize)
Definition: bufpage.c:1394
void PageIndexTupleDelete(Page page, OffsetNumber offnum)
Definition: bufpage.c:1041
Pointer Page
Definition: bufpage.h:81
static Item PageGetItem(Page page, ItemId itemId)
Definition: bufpage.h:354
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition: bufpage.h:243
static void PageSetLSN(Page page, XLogRecPtr lsn)
Definition: bufpage.h:391
static XLogRecPtr PageGetLSN(const char *page)
Definition: bufpage.h:386
static OffsetNumber PageGetMaxOffsetNumber(Page page)
Definition: bufpage.h:372
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
Definition: bufpage.h:471
#define Assert(condition)
Definition: c.h:812
uint32 TransactionId
Definition: c.h:606
#define OidIsValid(objectId)
Definition: c.h:729
size_t Size
Definition: c.h:559
int errdetail(const char *fmt,...)
Definition: elog.c:1203
int errhint(const char *fmt,...)
Definition: elog.c:1317
int errcode(int sqlerrcode)
Definition: elog.c:853
int errmsg(const char *fmt,...)
Definition: elog.c:1070
#define LOG
Definition: elog.h:31
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
#define ereport(elevel,...)
Definition: elog.h:149
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
Definition: fmgr.c:580
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define rightchild(x)
Definition: fsmpage.c:30
#define leftchild(x)
Definition: fsmpage.c:29
TransactionId index_compute_xid_horizon_for_tuples(Relation irel, Relation hrel, Buffer ibuf, OffsetNumber *itemnos, int nitems)
Definition: genam.c:294
IndexUniqueCheck
Definition: genam.h:118
SplitPageLayout * gistSplit(Relation r, Page page, IndexTuple *itup, int len, GISTSTATE *giststate)
Definition: gist.c:1438
GISTSTATE * initGISTstate(Relation index)
Definition: gist.c:1525
static GISTInsertStack * gistFindPath(Relation r, BlockNumber child, OffsetNumber *downlinkoffnum)
Definition: gist.c:909
void gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate, Relation heapRel, bool is_build)
Definition: gist.c:634
static void gistfixsplit(GISTInsertState *state, GISTSTATE *giststate)
Definition: gist.c:1188
static void gistprunepage(Relation rel, Page page, Buffer buffer, Relation heapRel)
Definition: gist.c:1663
bool gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate, Buffer buffer, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber *newblkno, Buffer leftchildbuf, List **splitinfo, bool markfollowright, Relation heapRel, bool is_build)
Definition: gist.c:225
bool gistinsert(Relation r, Datum *values, bool *isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, bool indexUnchanged, IndexInfo *indexInfo)
Definition: gist.c:160
void gistbuildempty(Relation index)
Definition: gist.c:134
static bool gistinserttuples(GISTInsertState *state, GISTInsertStack *stack, GISTSTATE *giststate, IndexTuple *tuples, int ntup, OffsetNumber oldoffnum, Buffer leftchild, Buffer rightchild, bool unlockbuf, bool unlockleftchild)
Definition: gist.c:1282
MemoryContext createTempGistContext(void)
Definition: gist.c:123
void freeGISTstate(GISTSTATE *giststate)
Definition: gist.c:1652
static bool gistinserttuple(GISTInsertState *state, GISTInsertStack *stack, GISTSTATE *giststate, IndexTuple tuple, OffsetNumber oldoffnum)
Definition: gist.c:1248
#define ROTATEDIST(d)
Definition: gist.c:45
static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack, GISTSTATE *giststate, List *splitinfo, bool unlockbuf)
Definition: gist.c:1342
static void gistFindCorrectParent(Relation r, GISTInsertStack *child, bool is_build)
Definition: gist.c:1022
static IndexTuple gistformdownlink(Relation rel, Buffer buf, GISTSTATE *giststate, GISTInsertStack *stack, bool is_build)
Definition: gist.c:1128
Datum gisthandler(PG_FUNCTION_ARGS)
Definition: gist.c:59
#define GIST_DECOMPRESS_PROC
Definition: gist.h:34
#define GIST_PICKSPLIT_PROC
Definition: gist.h:36
#define GistMarkFollowRight(page)
Definition: gist.h:183
#define F_LEAF
Definition: gist.h:48
#define GIST_CONSISTENT_PROC
Definition: gist.h:31
#define GistClearFollowRight(page)
Definition: gist.h:184
#define GIST_UNION_PROC
Definition: gist.h:32
#define GIST_FETCH_PROC
Definition: gist.h:39
#define GIST_COMPRESS_PROC
Definition: gist.h:33
#define GISTNProcs
Definition: gist.h:43
#define GistClearPageHasGarbage(page)
Definition: gist.h:180
#define GIST_PENALTY_PROC
Definition: gist.h:35
#define GistPageIsLeaf(page)
Definition: gist.h:169
#define GistFollowRight(page)
Definition: gist.h:182
#define GIST_OPTIONS_PROC
Definition: gist.h:40
#define GIST_DISTANCE_PROC
Definition: gist.h:38
#define GistPageSetNSN(page, val)
Definition: gist.h:187
#define GistPageIsDeleted(page)
Definition: gist.h:172
#define GistPageGetOpaque(page)
Definition: gist.h:167
#define GIST_EQUAL_PROC
Definition: gist.h:37
#define GistPageHasGarbage(page)
Definition: gist.h:178
#define GistPageGetNSN(page)
Definition: gist.h:186
XLogRecPtr GistNSN
Definition: gist.h:62
#define GistBuildLSN
Definition: gist.h:69
#define GIST_MAX_SPLIT_PAGES
Definition: gist_private.h:39
#define GistTupleSetValid(itup)
Definition: gist_private.h:289
#define GIST_UNLOCK
Definition: gist_private.h:44
#define GIST_ROOT_BLKNO
Definition: gist_private.h:262
#define GIST_EXCLUSIVE
Definition: gist_private.h:43
#define GiSTPageSize
Definition: gist_private.h:476
#define GistTupleIsInvalid(itup)
Definition: gist_private.h:288
#define GIST_SHARE
Definition: gist_private.h:42
IndexBuildResult * gistbuild(Relation heap, Relation index, IndexInfo *indexInfo)
Definition: gistbuild.c:179
bool gistgettuple(IndexScanDesc scan, ScanDirection dir)
Definition: gistget.c:612
int64 gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
Definition: gistget.c:743
bool gistcanreturn(Relation index, int attno)
Definition: gistget.c:793
IndexScanDesc gistbeginscan(Relation r, int nkeys, int norderbys)
Definition: gistscan.c:74
void gistendscan(IndexScanDesc scan)
Definition: gistscan.c:347
void gistrescan(IndexScanDesc scan, ScanKey key, int nkeys, ScanKey orderbys, int norderbys)
Definition: gistscan.c:127
void gistSplitByKey(Relation r, Page page, IndexTuple *itup, int len, GISTSTATE *giststate, GistSplitVector *v, int attno)
Definition: gistsplit.c:623
bytea * gistoptions(Datum reloptions, bool validate)
Definition: gistutil.c:912
Buffer gistNewBuffer(Relation r, Relation heaprel)
Definition: gistutil.c:824
bool gistproperty(Oid index_oid, int attno, IndexAMProperty prop, const char *propname, bool *res, bool *isnull)
Definition: gistutil.c:933
bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace)
Definition: gistutil.c:59
void gistfillbuffer(Page page, IndexTuple *itup, int len, OffsetNumber off)
Definition: gistutil.c:34
IndexTuple gistFormTuple(GISTSTATE *giststate, Relation r, const Datum *attdata, const bool *isnull, bool isleaf)
Definition: gistutil.c:575
IndexTuple * gistextractpage(Page page, int *len)
Definition: gistutil.c:95
bool gistfitpage(IndexTuple *itvec, int len)
Definition: gistutil.c:79
IndexTuple gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
Definition: gistutil.c:316
OffsetNumber gistchoose(Relation r, Page p, IndexTuple it, GISTSTATE *giststate)
Definition: gistutil.c:374
XLogRecPtr gistGetFakeLSN(Relation rel)
Definition: gistutil.c:1016
IndexTuple * gistjoinvector(IndexTuple *itvec, int *len, IndexTuple *additvec, int addlen)
Definition: gistutil.c:114
void GISTInitBuffer(Buffer b, uint32 f)
Definition: gistutil.c:773
void gistcheckpage(Relation rel, Buffer buf)
Definition: gistutil.c:785
IndexTupleData * gistfillitupvec(IndexTuple *vec, int veclen, int *memlen)
Definition: gistutil.c:127
IndexBulkDeleteResult * gistvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
Definition: gistvacuum.c:75
IndexBulkDeleteResult * gistbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state)
Definition: gistvacuum.c:59
void gistadjustmembers(Oid opfamilyoid, Oid opclassoid, List *operators, List *functions)
Definition: gistvalidate.c:295
bool gistvalidate(Oid opclassoid)
Definition: gistvalidate.c:33
XLogRecPtr gistXLogSplit(bool page_is_leaf, SplitPageLayout *dist, BlockNumber origrlink, GistNSN orignsn, Buffer leftchildbuf, bool markfollowright)
Definition: gistxlog.c:495
XLogRecPtr gistXLogDelete(Buffer buffer, OffsetNumber *todelete, int ntodelete, TransactionId snapshotConflictHorizon, Relation heaprel)
Definition: gistxlog.c:670
XLogRecPtr gistXLogUpdate(Buffer buffer, OffsetNumber *todelete, int ntodelete, IndexTuple *itup, int ituplen, Buffer leftchildbuf)
Definition: gistxlog.c:629
for(;;)
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:862
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:828
IndexTuple CopyIndexTuple(IndexTuple source)
Definition: indextuple.c:547
int i
Definition: isn.c:72
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:76
Pointer Item
Definition: item.h:17
#define ItemIdIsDead(itemId)
Definition: itemid.h:113
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
Definition: itemptr.c:35
static void ItemPointerSetBlockNumber(ItemPointerData *pointer, BlockNumber blockNumber)
Definition: itemptr.h:147
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition: itemptr.h:103
IndexTupleData * IndexTuple
Definition: itup.h:53
#define IndexTupleSize(itup)
Definition: itup.h:70
#define MaxIndexTuplesPerPage
Definition: itup.h:167
List * lappend(List *list, void *datum)
Definition: list.c:339
List * list_delete_first(List *list)
Definition: list.c:943
List * lcons(void *datum, List *list)
Definition: list.c:495
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:383
void * palloc0(Size size)
Definition: mcxt.c:1347
void * palloc(Size size)
Definition: mcxt.c:1317
MemoryContext CurrentMemoryContext
Definition: mcxt.c:143
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:454
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:160
#define START_CRIT_SECTION()
Definition: miscadmin.h:149
#define END_CRIT_SECTION()
Definition: miscadmin.h:151
#define makeNode(_type_)
Definition: nodes.h:155
#define InvalidOffsetNumber
Definition: off.h:26
#define OffsetNumberIsValid(offsetNumber)
Definition: off.h:39
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
uint16 OffsetNumber
Definition: off.h:24
#define FirstOffsetNumber
Definition: off.h:27
#define INDEX_MAX_KEYS
const void size_t len
const void * data
static int list_length(const List *l)
Definition: pg_list.h:152
#define NIL
Definition: pg_list.h:68
#define list_make1(x1)
Definition: pg_list.h:212
static void * list_nth(const List *list, int n)
Definition: pg_list.h:299
#define linitial(l)
Definition: pg_list.h:178
#define lsecond(l)
Definition: pg_list.h:183
static char * buf
Definition: pg_test_fsync.c:72
uintptr_t Datum
Definition: postgres.h:64
#define InvalidOid
Definition: postgres_ext.h:36
void PredicateLockPageSplit(Relation relation, BlockNumber oldblkno, BlockNumber newblkno)
Definition: predicate.c:3134
void CheckForSerializableConflictIn(Relation relation, ItemPointer tid, BlockNumber blkno)
Definition: predicate.c:4326
MemoryContextSwitchTo(old_ctx)
#define RelationGetRelationName(relation)
Definition: rel.h:539
#define RelationNeedsWAL(relation)
Definition: rel.h:628
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:524
@ INIT_FORKNUM
Definition: relpath.h:61
void gistcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
Definition: selfuncs.c:7184
void check_stack_depth(void)
Definition: stack_depth.c:95
Oid fn_oid
Definition: fmgr.h:59
BlockNumber blkno
Definition: gist_private.h:210
OffsetNumber downlinkoffnum
Definition: gist_private.h:228
struct GISTInsertStack * parent
Definition: gist_private.h:231
IndexTuple downlink
Definition: gist_private.h:422
FmgrInfo fetchFn[INDEX_MAX_KEYS]
Definition: gist_private.h:94
TupleDesc leafTupdesc
Definition: gist_private.h:80
TupleDesc nonLeafTupdesc
Definition: gist_private.h:81
FmgrInfo penaltyFn[INDEX_MAX_KEYS]
Definition: gist_private.h:90
MemoryContext tempCxt
Definition: gist_private.h:78
Oid supportCollation[INDEX_MAX_KEYS]
Definition: gist_private.h:97
FmgrInfo distanceFn[INDEX_MAX_KEYS]
Definition: gist_private.h:93
FmgrInfo consistentFn[INDEX_MAX_KEYS]
Definition: gist_private.h:86
MemoryContext scanCxt
Definition: gist_private.h:77
FmgrInfo decompressFn[INDEX_MAX_KEYS]
Definition: gist_private.h:89
FmgrInfo compressFn[INDEX_MAX_KEYS]
Definition: gist_private.h:88
FmgrInfo equalFn[INDEX_MAX_KEYS]
Definition: gist_private.h:92
FmgrInfo unionFn[INDEX_MAX_KEYS]
Definition: gist_private.h:87
FmgrInfo picksplitFn[INDEX_MAX_KEYS]
Definition: gist_private.h:91
int spl_nleft
Definition: gist.h:143
OffsetNumber * spl_right
Definition: gist.h:147
int spl_nright
Definition: gist.h:148
OffsetNumber * spl_left
Definition: gist.h:142
GIST_SPLITVEC splitVector
Definition: gist_private.h:237
Datum spl_lattr[INDEX_MAX_KEYS]
Definition: gist_private.h:239
bool spl_lisnull[INDEX_MAX_KEYS]
Definition: gist_private.h:241
Datum spl_rattr[INDEX_MAX_KEYS]
Definition: gist_private.h:243
bool spl_risnull[INDEX_MAX_KEYS]
Definition: gist_private.h:245
ambuildphasename_function ambuildphasename
Definition: amapi.h:289
ambuildempty_function ambuildempty
Definition: amapi.h:279
amvacuumcleanup_function amvacuumcleanup
Definition: amapi.h:283
bool amclusterable
Definition: amapi.h:253
amoptions_function amoptions
Definition: amapi.h:287
amestimateparallelscan_function amestimateparallelscan
Definition: amapi.h:301
amrestrpos_function amrestrpos
Definition: amapi.h:298
aminsert_function aminsert
Definition: amapi.h:280
amendscan_function amendscan
Definition: amapi.h:296
uint16 amoptsprocnum
Definition: amapi.h:233
amparallelrescan_function amparallelrescan
Definition: amapi.h:303
Oid amkeytype
Definition: amapi.h:269
bool ampredlocks
Definition: amapi.h:255
uint16 amsupport
Definition: amapi.h:231
amcostestimate_function amcostestimate
Definition: amapi.h:285
bool amcanorderbyop
Definition: amapi.h:237
amadjustmembers_function amadjustmembers
Definition: amapi.h:291
ambuild_function ambuild
Definition: amapi.h:278
bool amstorage
Definition: amapi.h:251
uint16 amstrategies
Definition: amapi.h:229
bool amoptionalkey
Definition: amapi.h:245
amgettuple_function amgettuple
Definition: amapi.h:294
amcanreturn_function amcanreturn
Definition: amapi.h:284
bool amcanunique
Definition: amapi.h:241
amgetbitmap_function amgetbitmap
Definition: amapi.h:295
amproperty_function amproperty
Definition: amapi.h:288
ambulkdelete_function ambulkdelete
Definition: amapi.h:282
bool amsearcharray
Definition: amapi.h:247
bool amsummarizing
Definition: amapi.h:265
amvalidate_function amvalidate
Definition: amapi.h:290
ammarkpos_function ammarkpos
Definition: amapi.h:297
bool amcanmulticol
Definition: amapi.h:243
bool amusemaintenanceworkmem
Definition: amapi.h:263
ambeginscan_function ambeginscan
Definition: amapi.h:292
bool amcanparallel
Definition: amapi.h:257
amrescan_function amrescan
Definition: amapi.h:293
bool amcanorder
Definition: amapi.h:235
bool amcanbuildparallel
Definition: amapi.h:259
aminitparallelscan_function aminitparallelscan
Definition: amapi.h:302
uint8 amparallelvacuumoptions
Definition: amapi.h:267
aminsertcleanup_function aminsertcleanup
Definition: amapi.h:281
bool amcanbackward
Definition: amapi.h:239
amgettreeheight_function amgettreeheight
Definition: amapi.h:286
bool amcaninclude
Definition: amapi.h:261
bool amsearchnulls
Definition: amapi.h:249
void * ii_AmCache
Definition: execnodes.h:210
MemoryContext ii_Context
Definition: execnodes.h:211
ItemPointerData t_tid
Definition: itup.h:37
Definition: pg_list.h:54
gistxlogPage block
Definition: gist_private.h:193
struct SplitPageLayout * next
Definition: gist_private.h:200
IndexTuple itup
Definition: gist_private.h:196
IndexTupleData * list
Definition: gist_private.h:194
BlockNumber blkno
Definition: gist_private.h:186
Definition: type.h:96
Definition: regguts.h:323
#define InvalidTransactionId
Definition: transam.h:31
TupleDesc CreateTupleDescTruncatedCopy(TupleDesc tupdesc, int natts)
Definition: tupdesc.c:279
#define VACUUM_OPTION_PARALLEL_BULKDEL
Definition: vacuum.h:48
#define VACUUM_OPTION_PARALLEL_COND_CLEANUP
Definition: vacuum.h:55
#define XLogStandbyInfoActive()
Definition: xlog.h:123
#define XLogRecPtrIsInvalid(r)
Definition: xlogdefs.h:29
uint64 XLogRecPtr
Definition: xlogdefs.h:21
XLogRecPtr log_newpage_buffer(Buffer buffer, bool page_std)
Definition: xloginsert.c:1237
void XLogEnsureRecordSpace(int max_block_id, int ndatas)
Definition: xloginsert.c:175