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