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