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