PostgreSQL Source Code  git master
spgutils.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * spgutils.c
4  * various support functions for SP-GiST
5  *
6  *
7  * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
8  * Portions Copyright (c) 1994, Regents of the University of California
9  *
10  * IDENTIFICATION
11  * src/backend/access/spgist/spgutils.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 
16 #include "postgres.h"
17 
18 #include "access/reloptions.h"
19 #include "access/spgist_private.h"
20 #include "access/transam.h"
21 #include "access/xact.h"
22 #include "storage/bufmgr.h"
23 #include "storage/indexfsm.h"
24 #include "storage/lmgr.h"
25 #include "utils/builtins.h"
26 #include "utils/index_selfuncs.h"
27 #include "utils/lsyscache.h"
28 
29 
30 /*
31  * SP-GiST handler function: return IndexAmRoutine with access method parameters
32  * and callbacks.
33  */
34 Datum
36 {
38 
39  amroutine->amstrategies = 0;
40  amroutine->amsupport = SPGISTNProc;
41  amroutine->amcanorder = false;
42  amroutine->amcanorderbyop = false;
43  amroutine->amcanbackward = false;
44  amroutine->amcanunique = false;
45  amroutine->amcanmulticol = false;
46  amroutine->amoptionalkey = true;
47  amroutine->amsearcharray = false;
48  amroutine->amsearchnulls = true;
49  amroutine->amstorage = false;
50  amroutine->amclusterable = false;
51  amroutine->ampredlocks = false;
52  amroutine->amcanparallel = false;
53  amroutine->amkeytype = InvalidOid;
54 
55  amroutine->ambuild = spgbuild;
56  amroutine->ambuildempty = spgbuildempty;
57  amroutine->aminsert = spginsert;
58  amroutine->ambulkdelete = spgbulkdelete;
59  amroutine->amvacuumcleanup = spgvacuumcleanup;
60  amroutine->amcanreturn = spgcanreturn;
61  amroutine->amcostestimate = spgcostestimate;
62  amroutine->amoptions = spgoptions;
63  amroutine->amproperty = NULL;
64  amroutine->amvalidate = spgvalidate;
65  amroutine->ambeginscan = spgbeginscan;
66  amroutine->amrescan = spgrescan;
67  amroutine->amgettuple = spggettuple;
68  amroutine->amgetbitmap = spggetbitmap;
69  amroutine->amendscan = spgendscan;
70  amroutine->ammarkpos = NULL;
71  amroutine->amrestrpos = NULL;
72  amroutine->amestimateparallelscan = NULL;
73  amroutine->aminitparallelscan = NULL;
74  amroutine->amparallelrescan = NULL;
75 
76  PG_RETURN_POINTER(amroutine);
77 }
78 
79 /* Fill in a SpGistTypeDesc struct with info about the specified data type */
80 static void
82 {
83  desc->type = type;
84  get_typlenbyval(type, &desc->attlen, &desc->attbyval);
85 }
86 
87 /*
88  * Fetch local cache of AM-specific info about the index, initializing it
89  * if necessary
90  */
93 {
94  SpGistCache *cache;
95 
96  if (index->rd_amcache == NULL)
97  {
98  Oid atttype;
99  spgConfigIn in;
100  FmgrInfo *procinfo;
101  Buffer metabuffer;
102  SpGistMetaPageData *metadata;
103 
104  cache = MemoryContextAllocZero(index->rd_indexcxt,
105  sizeof(SpGistCache));
106 
107  /* SPGiST doesn't support multi-column indexes */
108  Assert(index->rd_att->natts == 1);
109 
110  /*
111  * Get the actual data type of the indexed column from the index
112  * tupdesc. We pass this to the opclass config function so that
113  * polymorphic opclasses are possible.
114  */
115  atttype = TupleDescAttr(index->rd_att, 0)->atttypid;
116 
117  /* Call the config function to get config info for the opclass */
118  in.attType = atttype;
119 
120  procinfo = index_getprocinfo(index, 1, SPGIST_CONFIG_PROC);
121  FunctionCall2Coll(procinfo,
122  index->rd_indcollation[0],
123  PointerGetDatum(&in),
124  PointerGetDatum(&cache->config));
125 
126  /* Get the information we need about each relevant datatype */
127  fillTypeDesc(&cache->attType, atttype);
128 
129  if (OidIsValid(cache->config.leafType) &&
130  cache->config.leafType != atttype)
131  {
133  ereport(ERROR,
134  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
135  errmsg("compress method must not defined when leaf type is different from input type")));
136 
137  fillTypeDesc(&cache->attLeafType, cache->config.leafType);
138  }
139  else
140  {
141  cache->attLeafType = cache->attType;
142  }
143 
144  fillTypeDesc(&cache->attPrefixType, cache->config.prefixType);
145  fillTypeDesc(&cache->attLabelType, cache->config.labelType);
146 
147  /* Last, get the lastUsedPages data from the metapage */
148  metabuffer = ReadBuffer(index, SPGIST_METAPAGE_BLKNO);
149  LockBuffer(metabuffer, BUFFER_LOCK_SHARE);
150 
151  metadata = SpGistPageGetMeta(BufferGetPage(metabuffer));
152 
153  if (metadata->magicNumber != SPGIST_MAGIC_NUMBER)
154  elog(ERROR, "index \"%s\" is not an SP-GiST index",
155  RelationGetRelationName(index));
156 
157  cache->lastUsedPages = metadata->lastUsedPages;
158 
159  UnlockReleaseBuffer(metabuffer);
160 
161  index->rd_amcache = (void *) cache;
162  }
163  else
164  {
165  /* assume it's up to date */
166  cache = (SpGistCache *) index->rd_amcache;
167  }
168 
169  return cache;
170 }
171 
172 /* Initialize SpGistState for working with the given index */
173 void
175 {
176  SpGistCache *cache;
177 
178  /* Get cached static information about index */
179  cache = spgGetCache(index);
180 
181  state->config = cache->config;
182  state->attType = cache->attType;
183  state->attLeafType = cache->attLeafType;
184  state->attPrefixType = cache->attPrefixType;
185  state->attLabelType = cache->attLabelType;
186 
187  /* Make workspace for constructing dead tuples */
189 
190  /* Set XID to use in redirection tuples */
191  state->myXid = GetTopTransactionIdIfAny();
192 
193  /* Assume we're not in an index build (spgbuild will override) */
194  state->isBuild = false;
195 }
196 
197 /*
198  * Allocate a new page (either by recycling, or by extending the index file).
199  *
200  * The returned buffer is already pinned and exclusive-locked.
201  * Caller is responsible for initializing the page by calling SpGistInitBuffer.
202  */
203 Buffer
205 {
206  Buffer buffer;
207  bool needLock;
208 
209  /* First, try to get a page from FSM */
210  for (;;)
211  {
212  BlockNumber blkno = GetFreeIndexPage(index);
213 
214  if (blkno == InvalidBlockNumber)
215  break; /* nothing known to FSM */
216 
217  /*
218  * The fixed pages shouldn't ever be listed in FSM, but just in case
219  * one is, ignore it.
220  */
221  if (SpGistBlockIsFixed(blkno))
222  continue;
223 
224  buffer = ReadBuffer(index, blkno);
225 
226  /*
227  * We have to guard against the possibility that someone else already
228  * recycled this page; the buffer may be locked if so.
229  */
230  if (ConditionalLockBuffer(buffer))
231  {
232  Page page = BufferGetPage(buffer);
233 
234  if (PageIsNew(page))
235  return buffer; /* OK to use, if never initialized */
236 
237  if (SpGistPageIsDeleted(page) || PageIsEmpty(page))
238  return buffer; /* OK to use */
239 
241  }
242 
243  /* Can't use it, so release buffer and try again */
244  ReleaseBuffer(buffer);
245  }
246 
247  /* Must extend the file */
248  needLock = !RELATION_IS_LOCAL(index);
249  if (needLock)
251 
252  buffer = ReadBuffer(index, P_NEW);
254 
255  if (needLock)
257 
258  return buffer;
259 }
260 
261 /*
262  * Update index metapage's lastUsedPages info from local cache, if possible
263  *
264  * Updating meta page isn't critical for index working, so
265  * 1 use ConditionalLockBuffer to improve concurrency
266  * 2 don't WAL-log metabuffer changes to decrease WAL traffic
267  */
268 void
270 {
271  SpGistCache *cache = (SpGistCache *) index->rd_amcache;
272 
273  if (cache != NULL)
274  {
275  Buffer metabuffer;
276 
277  metabuffer = ReadBuffer(index, SPGIST_METAPAGE_BLKNO);
278 
279  if (ConditionalLockBuffer(metabuffer))
280  {
281  Page metapage = BufferGetPage(metabuffer);
282  SpGistMetaPageData *metadata = SpGistPageGetMeta(metapage);
283 
284  metadata->lastUsedPages = cache->lastUsedPages;
285 
286  /*
287  * Set pd_lower just past the end of the metadata. This is
288  * essential, because without doing so, metadata will be lost if
289  * xlog.c compresses the page. (We must do this here because
290  * pre-v11 versions of PG did not set the metapage's pd_lower
291  * correctly, so a pg_upgraded index might contain the wrong
292  * value.)
293  */
294  ((PageHeader) metapage)->pd_lower =
295  ((char *) metadata + sizeof(SpGistMetaPageData)) - (char *) metapage;
296 
297  MarkBufferDirty(metabuffer);
298  UnlockReleaseBuffer(metabuffer);
299  }
300  else
301  {
302  ReleaseBuffer(metabuffer);
303  }
304  }
305 }
306 
307 /* Macro to select proper element of lastUsedPages cache depending on flags */
308 /* Masking flags with SPGIST_CACHED_PAGES is just for paranoia's sake */
309 #define GET_LUP(c, f) (&(c)->lastUsedPages.cachedPage[((unsigned int) (f)) % SPGIST_CACHED_PAGES])
310 
311 /*
312  * Allocate and initialize a new buffer of the type and parity specified by
313  * flags. The returned buffer is already pinned and exclusive-locked.
314  *
315  * When requesting an inner page, if we get one with the wrong parity,
316  * we just release the buffer and try again. We will get a different page
317  * because GetFreeIndexPage will have marked the page used in FSM. The page
318  * is entered in our local lastUsedPages cache, so there's some hope of
319  * making use of it later in this session, but otherwise we rely on VACUUM
320  * to eventually re-enter the page in FSM, making it available for recycling.
321  * Note that such a page does not get marked dirty here, so unless it's used
322  * fairly soon, the buffer will just get discarded and the page will remain
323  * as it was on disk.
324  *
325  * When we return a buffer to the caller, the page is *not* entered into
326  * the lastUsedPages cache; we expect the caller will do so after it's taken
327  * whatever space it will use. This is because after the caller has used up
328  * some space, the page might have less space than whatever was cached already
329  * so we'd rather not trash the old cache entry.
330  */
331 static Buffer
333 {
334  SpGistCache *cache = spgGetCache(index);
335  uint16 pageflags = 0;
336 
337  if (GBUF_REQ_LEAF(flags))
338  pageflags |= SPGIST_LEAF;
339  if (GBUF_REQ_NULLS(flags))
340  pageflags |= SPGIST_NULLS;
341 
342  for (;;)
343  {
344  Buffer buffer;
345 
346  buffer = SpGistNewBuffer(index);
347  SpGistInitBuffer(buffer, pageflags);
348 
349  if (pageflags & SPGIST_LEAF)
350  {
351  /* Leaf pages have no parity concerns, so just use it */
352  return buffer;
353  }
354  else
355  {
356  BlockNumber blkno = BufferGetBlockNumber(buffer);
357  int blkFlags = GBUF_INNER_PARITY(blkno);
358 
359  if ((flags & GBUF_PARITY_MASK) == blkFlags)
360  {
361  /* Page has right parity, use it */
362  return buffer;
363  }
364  else
365  {
366  /* Page has wrong parity, record it in cache and try again */
367  if (pageflags & SPGIST_NULLS)
368  blkFlags |= GBUF_NULLS;
369  cache->lastUsedPages.cachedPage[blkFlags].blkno = blkno;
370  cache->lastUsedPages.cachedPage[blkFlags].freeSpace =
372  UnlockReleaseBuffer(buffer);
373  }
374  }
375  }
376 }
377 
378 /*
379  * Get a buffer of the type and parity specified by flags, having at least
380  * as much free space as indicated by needSpace. We use the lastUsedPages
381  * cache to assign the same buffer previously requested when possible.
382  * The returned buffer is already pinned and exclusive-locked.
383  *
384  * *isNew is set true if the page was initialized here, false if it was
385  * already valid.
386  */
387 Buffer
388 SpGistGetBuffer(Relation index, int flags, int needSpace, bool *isNew)
389 {
390  SpGistCache *cache = spgGetCache(index);
391  SpGistLastUsedPage *lup;
392 
393  /* Bail out if even an empty page wouldn't meet the demand */
394  if (needSpace > SPGIST_PAGE_CAPACITY)
395  elog(ERROR, "desired SPGiST tuple size is too big");
396 
397  /*
398  * If possible, increase the space request to include relation's
399  * fillfactor. This ensures that when we add unrelated tuples to a page,
400  * we try to keep 100-fillfactor% available for adding tuples that are
401  * related to the ones already on it. But fillfactor mustn't cause an
402  * error for requests that would otherwise be legal.
403  */
404  needSpace += RelationGetTargetPageFreeSpace(index,
406  needSpace = Min(needSpace, SPGIST_PAGE_CAPACITY);
407 
408  /* Get the cache entry for this flags setting */
409  lup = GET_LUP(cache, flags);
410 
411  /* If we have nothing cached, just turn it over to allocNewBuffer */
412  if (lup->blkno == InvalidBlockNumber)
413  {
414  *isNew = true;
415  return allocNewBuffer(index, flags);
416  }
417 
418  /* fixed pages should never be in cache */
420 
421  /* If cached freeSpace isn't enough, don't bother looking at the page */
422  if (lup->freeSpace >= needSpace)
423  {
424  Buffer buffer;
425  Page page;
426 
427  buffer = ReadBuffer(index, lup->blkno);
428 
429  if (!ConditionalLockBuffer(buffer))
430  {
431  /*
432  * buffer is locked by another process, so return a new buffer
433  */
434  ReleaseBuffer(buffer);
435  *isNew = true;
436  return allocNewBuffer(index, flags);
437  }
438 
439  page = BufferGetPage(buffer);
440 
441  if (PageIsNew(page) || SpGistPageIsDeleted(page) || PageIsEmpty(page))
442  {
443  /* OK to initialize the page */
444  uint16 pageflags = 0;
445 
446  if (GBUF_REQ_LEAF(flags))
447  pageflags |= SPGIST_LEAF;
448  if (GBUF_REQ_NULLS(flags))
449  pageflags |= SPGIST_NULLS;
450  SpGistInitBuffer(buffer, pageflags);
451  lup->freeSpace = PageGetExactFreeSpace(page) - needSpace;
452  *isNew = true;
453  return buffer;
454  }
455 
456  /*
457  * Check that page is of right type and has enough space. We must
458  * recheck this since our cache isn't necessarily up to date.
459  */
460  if ((GBUF_REQ_LEAF(flags) ? SpGistPageIsLeaf(page) : !SpGistPageIsLeaf(page)) &&
462  {
463  int freeSpace = PageGetExactFreeSpace(page);
464 
465  if (freeSpace >= needSpace)
466  {
467  /* Success, update freespace info and return the buffer */
468  lup->freeSpace = freeSpace - needSpace;
469  *isNew = false;
470  return buffer;
471  }
472  }
473 
474  /*
475  * fallback to allocation of new buffer
476  */
477  UnlockReleaseBuffer(buffer);
478  }
479 
480  /* No success with cache, so return a new buffer */
481  *isNew = true;
482  return allocNewBuffer(index, flags);
483 }
484 
485 /*
486  * Update lastUsedPages cache when done modifying a page.
487  *
488  * We update the appropriate cache entry if it already contained this page
489  * (its freeSpace is likely obsolete), or if this page has more space than
490  * whatever we had cached.
491  */
492 void
494 {
495  SpGistCache *cache = spgGetCache(index);
496  SpGistLastUsedPage *lup;
497  int freeSpace;
498  Page page = BufferGetPage(buffer);
499  BlockNumber blkno = BufferGetBlockNumber(buffer);
500  int flags;
501 
502  /* Never enter fixed pages (root pages) in cache, though */
503  if (SpGistBlockIsFixed(blkno))
504  return;
505 
506  if (SpGistPageIsLeaf(page))
507  flags = GBUF_LEAF;
508  else
509  flags = GBUF_INNER_PARITY(blkno);
510  if (SpGistPageStoresNulls(page))
511  flags |= GBUF_NULLS;
512 
513  lup = GET_LUP(cache, flags);
514 
515  freeSpace = PageGetExactFreeSpace(page);
516  if (lup->blkno == InvalidBlockNumber || lup->blkno == blkno ||
517  lup->freeSpace < freeSpace)
518  {
519  lup->blkno = blkno;
520  lup->freeSpace = freeSpace;
521  }
522 }
523 
524 /*
525  * Initialize an SPGiST page to empty, with specified flags
526  */
527 void
529 {
530  SpGistPageOpaque opaque;
531 
532  PageInit(page, BLCKSZ, MAXALIGN(sizeof(SpGistPageOpaqueData)));
533  opaque = SpGistPageGetOpaque(page);
534  memset(opaque, 0, sizeof(SpGistPageOpaqueData));
535  opaque->flags = f;
536  opaque->spgist_page_id = SPGIST_PAGE_ID;
537 }
538 
539 /*
540  * Initialize a buffer's page to empty, with specified flags
541  */
542 void
544 {
545  Assert(BufferGetPageSize(b) == BLCKSZ);
547 }
548 
549 /*
550  * Initialize metadata page
551  */
552 void
554 {
555  SpGistMetaPageData *metadata;
556  int i;
557 
559  metadata = SpGistPageGetMeta(page);
560  memset(metadata, 0, sizeof(SpGistMetaPageData));
561  metadata->magicNumber = SPGIST_MAGIC_NUMBER;
562 
563  /* initialize last-used-page cache to empty */
564  for (i = 0; i < SPGIST_CACHED_PAGES; i++)
566 
567  /*
568  * Set pd_lower just past the end of the metadata. This is essential,
569  * because without doing so, metadata will be lost if xlog.c compresses
570  * the page.
571  */
572  ((PageHeader) page)->pd_lower =
573  ((char *) metadata + sizeof(SpGistMetaPageData)) - (char *) page;
574 }
575 
576 /*
577  * reloptions processing for SPGiST
578  */
579 bytea *
580 spgoptions(Datum reloptions, bool validate)
581 {
582  return default_reloptions(reloptions, validate, RELOPT_KIND_SPGIST);
583 }
584 
585 /*
586  * Get the space needed to store a non-null datum of the indicated type.
587  * Note the result is already rounded up to a MAXALIGN boundary.
588  * Also, we follow the SPGiST convention that pass-by-val types are
589  * just stored in their Datum representation (compare memcpyDatum).
590  */
591 unsigned int
593 {
594  unsigned int size;
595 
596  if (att->attbyval)
597  size = sizeof(Datum);
598  else if (att->attlen > 0)
599  size = att->attlen;
600  else
601  size = VARSIZE_ANY(datum);
602 
603  return MAXALIGN(size);
604 }
605 
606 /*
607  * Copy the given non-null datum to *target
608  */
609 static void
610 memcpyDatum(void *target, SpGistTypeDesc *att, Datum datum)
611 {
612  unsigned int size;
613 
614  if (att->attbyval)
615  {
616  memcpy(target, &datum, sizeof(Datum));
617  }
618  else
619  {
620  size = (att->attlen > 0) ? att->attlen : VARSIZE_ANY(datum);
621  memcpy(target, DatumGetPointer(datum), size);
622  }
623 }
624 
625 /*
626  * Construct a leaf tuple containing the given heap TID and datum value
627  */
630  Datum datum, bool isnull)
631 {
632  SpGistLeafTuple tup;
633  unsigned int size;
634 
635  /* compute space needed (note result is already maxaligned) */
636  size = SGLTHDRSZ;
637  if (!isnull)
638  size += SpGistGetTypeSize(&state->attLeafType, datum);
639 
640  /*
641  * Ensure that we can replace the tuple with a dead tuple later. This
642  * test is unnecessary when !isnull, but let's be safe.
643  */
644  if (size < SGDTSIZE)
645  size = SGDTSIZE;
646 
647  /* OK, form the tuple */
648  tup = (SpGistLeafTuple) palloc0(size);
649 
650  tup->size = size;
652  tup->heapPtr = *heapPtr;
653  if (!isnull)
654  memcpyDatum(SGLTDATAPTR(tup), &state->attLeafType, datum);
655 
656  return tup;
657 }
658 
659 /*
660  * Construct a node (to go into an inner tuple) containing the given label
661  *
662  * Note that the node's downlink is just set invalid here. Caller will fill
663  * it in later.
664  */
667 {
668  SpGistNodeTuple tup;
669  unsigned int size;
670  unsigned short infomask = 0;
671 
672  /* compute space needed (note result is already maxaligned) */
673  size = SGNTHDRSZ;
674  if (!isnull)
675  size += SpGistGetTypeSize(&state->attLabelType, label);
676 
677  /*
678  * Here we make sure that the size will fit in the field reserved for it
679  * in t_info.
680  */
681  if ((size & INDEX_SIZE_MASK) != size)
682  ereport(ERROR,
683  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
684  errmsg("index row requires %zu bytes, maximum size is %zu",
685  (Size) size, (Size) INDEX_SIZE_MASK)));
686 
687  tup = (SpGistNodeTuple) palloc0(size);
688 
689  if (isnull)
690  infomask |= INDEX_NULL_MASK;
691  /* we don't bother setting the INDEX_VAR_MASK bit */
692  infomask |= size;
693  tup->t_info = infomask;
694 
695  /* The TID field will be filled in later */
697 
698  if (!isnull)
699  memcpyDatum(SGNTDATAPTR(tup), &state->attLabelType, label);
700 
701  return tup;
702 }
703 
704 /*
705  * Construct an inner tuple containing the given prefix and node array
706  */
708 spgFormInnerTuple(SpGistState *state, bool hasPrefix, Datum prefix,
709  int nNodes, SpGistNodeTuple *nodes)
710 {
711  SpGistInnerTuple tup;
712  unsigned int size;
713  unsigned int prefixSize;
714  int i;
715  char *ptr;
716 
717  /* Compute size needed */
718  if (hasPrefix)
719  prefixSize = SpGistGetTypeSize(&state->attPrefixType, prefix);
720  else
721  prefixSize = 0;
722 
723  size = SGITHDRSZ + prefixSize;
724 
725  /* Note: we rely on node tuple sizes to be maxaligned already */
726  for (i = 0; i < nNodes; i++)
727  size += IndexTupleSize(nodes[i]);
728 
729  /*
730  * Ensure that we can replace the tuple with a dead tuple later. This
731  * test is unnecessary given current tuple layouts, but let's be safe.
732  */
733  if (size < SGDTSIZE)
734  size = SGDTSIZE;
735 
736  /*
737  * Inner tuple should be small enough to fit on a page
738  */
739  if (size > SPGIST_PAGE_CAPACITY - sizeof(ItemIdData))
740  ereport(ERROR,
741  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
742  errmsg("SP-GiST inner tuple size %zu exceeds maximum %zu",
743  (Size) size,
744  SPGIST_PAGE_CAPACITY - sizeof(ItemIdData)),
745  errhint("Values larger than a buffer page cannot be indexed.")));
746 
747  /*
748  * Check for overflow of header fields --- probably can't fail if the
749  * above succeeded, but let's be paranoid
750  */
751  if (size > SGITMAXSIZE ||
752  prefixSize > SGITMAXPREFIXSIZE ||
753  nNodes > SGITMAXNNODES)
754  elog(ERROR, "SPGiST inner tuple header field is too small");
755 
756  /* OK, form the tuple */
757  tup = (SpGistInnerTuple) palloc0(size);
758 
759  tup->nNodes = nNodes;
760  tup->prefixSize = prefixSize;
761  tup->size = size;
762 
763  if (hasPrefix)
764  memcpyDatum(SGITDATAPTR(tup), &state->attPrefixType, prefix);
765 
766  ptr = (char *) SGITNODEPTR(tup);
767 
768  for (i = 0; i < nNodes; i++)
769  {
770  SpGistNodeTuple node = nodes[i];
771 
772  memcpy(ptr, node, IndexTupleSize(node));
773  ptr += IndexTupleSize(node);
774  }
775 
776  return tup;
777 }
778 
779 /*
780  * Construct a "dead" tuple to replace a tuple being deleted.
781  *
782  * The state can be SPGIST_REDIRECT, SPGIST_DEAD, or SPGIST_PLACEHOLDER.
783  * For a REDIRECT tuple, a pointer (blkno+offset) must be supplied, and
784  * the xid field is filled in automatically.
785  *
786  * This is called in critical sections, so we don't use palloc; the tuple
787  * is built in preallocated storage. It should be copied before another
788  * call with different parameters can occur.
789  */
792  BlockNumber blkno, OffsetNumber offnum)
793 {
795 
796  tuple->tupstate = tupstate;
797  tuple->size = SGDTSIZE;
799 
800  if (tupstate == SPGIST_REDIRECT)
801  {
802  ItemPointerSet(&tuple->pointer, blkno, offnum);
804  tuple->xid = state->myXid;
805  }
806  else
807  {
809  tuple->xid = InvalidTransactionId;
810  }
811 
812  return tuple;
813 }
814 
815 /*
816  * Extract the label datums of the nodes within innerTuple
817  *
818  * Returns NULL if label datums are NULLs
819  */
820 Datum *
822 {
823  Datum *nodeLabels;
824  int i;
825  SpGistNodeTuple node;
826 
827  /* Either all the labels must be NULL, or none. */
828  node = SGITNODEPTR(innerTuple);
829  if (IndexTupleHasNulls(node))
830  {
831  SGITITERATE(innerTuple, i, node)
832  {
833  if (!IndexTupleHasNulls(node))
834  elog(ERROR, "some but not all node labels are null in SPGiST inner tuple");
835  }
836  /* They're all null, so just return NULL */
837  return NULL;
838  }
839  else
840  {
841  nodeLabels = (Datum *) palloc(sizeof(Datum) * innerTuple->nNodes);
842  SGITITERATE(innerTuple, i, node)
843  {
844  if (IndexTupleHasNulls(node))
845  elog(ERROR, "some but not all node labels are null in SPGiST inner tuple");
846  nodeLabels[i] = SGNTDATUM(node, state);
847  }
848  return nodeLabels;
849  }
850 }
851 
852 /*
853  * Add a new item to the page, replacing a PLACEHOLDER item if possible.
854  * Return the location it's inserted at, or InvalidOffsetNumber on failure.
855  *
856  * If startOffset isn't NULL, we start searching for placeholders at
857  * *startOffset, and update that to the next place to search. This is just
858  * an optimization for repeated insertions.
859  *
860  * If errorOK is false, we throw error when there's not enough room,
861  * rather than returning InvalidOffsetNumber.
862  */
865  OffsetNumber *startOffset, bool errorOK)
866 {
867  SpGistPageOpaque opaque = SpGistPageGetOpaque(page);
868  OffsetNumber i,
869  maxoff,
870  offnum;
871 
872  if (opaque->nPlaceholder > 0 &&
873  PageGetExactFreeSpace(page) + SGDTSIZE >= MAXALIGN(size))
874  {
875  /* Try to replace a placeholder */
876  maxoff = PageGetMaxOffsetNumber(page);
877  offnum = InvalidOffsetNumber;
878 
879  for (;;)
880  {
881  if (startOffset && *startOffset != InvalidOffsetNumber)
882  i = *startOffset;
883  else
884  i = FirstOffsetNumber;
885  for (; i <= maxoff; i++)
886  {
888  PageGetItemId(page, i));
889 
890  if (it->tupstate == SPGIST_PLACEHOLDER)
891  {
892  offnum = i;
893  break;
894  }
895  }
896 
897  /* Done if we found a placeholder */
898  if (offnum != InvalidOffsetNumber)
899  break;
900 
901  if (startOffset && *startOffset != InvalidOffsetNumber)
902  {
903  /* Hint was no good, re-search from beginning */
904  *startOffset = InvalidOffsetNumber;
905  continue;
906  }
907 
908  /* Hmm, no placeholder found? */
909  opaque->nPlaceholder = 0;
910  break;
911  }
912 
913  if (offnum != InvalidOffsetNumber)
914  {
915  /* Replace the placeholder tuple */
916  PageIndexTupleDelete(page, offnum);
917 
918  offnum = PageAddItem(page, item, size, offnum, false, false);
919 
920  /*
921  * We should not have failed given the size check at the top of
922  * the function, but test anyway. If we did fail, we must PANIC
923  * because we've already deleted the placeholder tuple, and
924  * there's no other way to keep the damage from getting to disk.
925  */
926  if (offnum != InvalidOffsetNumber)
927  {
928  Assert(opaque->nPlaceholder > 0);
929  opaque->nPlaceholder--;
930  if (startOffset)
931  *startOffset = offnum + 1;
932  }
933  else
934  elog(PANIC, "failed to add item of size %u to SPGiST index page",
935  (int) size);
936 
937  return offnum;
938  }
939  }
940 
941  /* No luck in replacing a placeholder, so just add it to the page */
942  offnum = PageAddItem(page, item, size,
943  InvalidOffsetNumber, false, false);
944 
945  if (offnum == InvalidOffsetNumber && !errorOK)
946  elog(ERROR, "failed to add item of size %u to SPGiST index page",
947  (int) size);
948 
949  return offnum;
950 }
ambeginscan_function ambeginscan
Definition: amapi.h:208
void SpGistUpdateMetaPage(Relation index)
Definition: spgutils.c:269
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:321
SpGistTypeDesc attLeafType
#define SGITNODEPTR(x)
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
Definition: fmgr.h:56
SpGistTypeDesc attPrefixType
ambulkdelete_function ambulkdelete
Definition: amapi.h:201
Datum * spgExtractNodeLabels(SpGistState *state, SpGistInnerTuple innerTuple)
Definition: spgutils.c:821
bool amcanmulticol
Definition: amapi.h:179
uint16 amsupport
Definition: amapi.h:169
SpGistInnerTupleData * SpGistInnerTuple
#define PageIsEmpty(page)
Definition: bufpage.h:218
#define SpGistPageIsLeaf(page)
SpGistDeadTuple spgFormDeadTuple(SpGistState *state, int tupstate, BlockNumber blkno, OffsetNumber offnum)
Definition: spgutils.c:791
int errhint(const char *fmt,...)
Definition: elog.c:987
SpGistCache * spgGetCache(Relation index)
Definition: spgutils.c:92
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:855
#define SGITMAXPREFIXSIZE
#define SGDTSIZE
amgettuple_function amgettuple
Definition: amapi.h:210
#define SPGIST_REDIRECT
bool amcanorderbyop
Definition: amapi.h:173
amproperty_function amproperty
Definition: amapi.h:206
#define GET_LUP(c, f)
Definition: spgutils.c:309
void PageIndexTupleDelete(Page page, OffsetNumber offnum)
Definition: bufpage.c:723
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1450
#define ExclusiveLock
Definition: lockdefs.h:44
#define PointerGetDatum(X)
Definition: postgres.h:562
#define TupleDescAttr(tupdesc, i)
Definition: tupdesc.h:90
IndexBulkDeleteResult * spgvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
Definition: spgvacuum.c:917
#define SGITITERATE(x, i, nt)
#define RELATION_IS_LOCAL(relation)
Definition: rel.h:532
SpGistTypeDesc attLeafType
ItemPointerData t_tid
Definition: itup.h:37
#define SPGIST_PLACEHOLDER
amparallelrescan_function amparallelrescan
Definition: amapi.h:219
#define Min(x, y)
Definition: c.h:826
SpGistTypeDesc attType
#define SPGIST_NULLS
bool amstorage
Definition: amapi.h:187
void SpGistSetLastUsedPage(Relation index, Buffer buffer)
Definition: spgutils.c:493
Pointer Item
Definition: item.h:17
#define SGLTDATAPTR(x)
#define INDEX_SIZE_MASK
Definition: itup.h:65
int errcode(int sqlerrcode)
Definition: elog.c:575
void spgrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)
Definition: spgscan.c:207
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
Definition: bufpage.h:412
static Buffer allocNewBuffer(Relation index, int flags)
Definition: spgutils.c:332
bool ampredlocks
Definition: amapi.h:191
uint32 BlockNumber
Definition: block.h:31
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3309
SpGistTypeDesc attLabelType
#define IndexTupleHasNulls(itup)
Definition: itup.h:72
#define P_NEW
Definition: bufmgr.h:82
aminsert_function aminsert
Definition: amapi.h:200
Oid attType
Definition: spgist.h:42
bool spginsert(Relation index, Datum *values, bool *isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, IndexInfo *indexInfo)
Definition: spginsert.c:208
#define SGNTHDRSZ
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:89
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1042
unsigned int Oid
Definition: postgres_ext.h:31
SpGistTypeDesc attType
Oid amkeytype
Definition: amapi.h:195
void spgendscan(IndexScanDesc scan)
Definition: spgscan.c:227
#define OidIsValid(objectId)
Definition: c.h:586
#define PANIC
Definition: elog.h:53
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:353
bool amoptionalkey
Definition: amapi.h:181
amvalidate_function amvalidate
Definition: amapi.h:207
int natts
Definition: tupdesc.h:79
SpGistLUPCache lastUsedPages
bool spgcanreturn(Relation index, int attno)
Definition: spgscan.c:648
uint16 OffsetNumber
Definition: off.h:24
Definition: type.h:89
#define SPGIST_DEFAULT_FILLFACTOR
Definition: spgist.h:25
spgConfigOut config
SpGistLastUsedPage cachedPage[SPGIST_CACHED_PAGES]
#define GBUF_REQ_NULLS(flags)
unsigned short uint16
Definition: c.h:305
amgetbitmap_function amgetbitmap
Definition: amapi.h:211
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3332
Oid * rd_indcollation
Definition: rel.h:193
ItemPointerData pointer
#define ERROR
Definition: elog.h:43
IndexBulkDeleteResult * spgbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state)
Definition: spgvacuum.c:886
ambuild_function ambuild
Definition: amapi.h:198
amoptions_function amoptions
Definition: amapi.h:205
#define SPGIST_PAGE_ID
#define GBUF_INNER_PARITY(x)
unsigned int prefixSize
amcostestimate_function amcostestimate
Definition: amapi.h:204
bool amcanunique
Definition: amapi.h:177
#define SGITMAXSIZE
#define SGITDATAPTR(x)
amvacuumcleanup_function amvacuumcleanup
Definition: amapi.h:202
amendscan_function amendscan
Definition: amapi.h:212
bool amcanbackward
Definition: amapi.h:175
#define FirstOffsetNumber
Definition: off.h:27
SpGistInnerTuple spgFormInnerTuple(SpGistState *state, bool hasPrefix, Datum prefix, int nNodes, SpGistNodeTuple *nodes)
Definition: spgutils.c:708
#define SPGIST_METAPAGE_BLKNO
void initSpGistState(SpGistState *state, Relation index)
Definition: spgutils.c:174
SpGistDeadTupleData * SpGistDeadTuple
#define InvalidTransactionId
Definition: transam.h:31
#define RelationGetRelationName(relation)
Definition: rel.h:445
int64 spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
Definition: spgscan.c:568
#define SpGistBlockIsFixed(blkno)
TransactionId myXid
void spgbuildempty(Relation index)
Definition: spginsert.c:157
#define INDEX_NULL_MASK
Definition: itup.h:68
TransactionId GetTopTransactionIdIfAny(void)
Definition: xact.c:405
void SpGistInitBuffer(Buffer b, uint16 f)
Definition: spgutils.c:543
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define SGITMAXNNODES
#define ereport(elevel, rest)
Definition: elog.h:122
amrescan_function amrescan
Definition: amapi.h:209
bool amcanparallel
Definition: amapi.h:193
bool ConditionalLockBuffer(Buffer buffer)
Definition: bufmgr.c:3572
#define SPGIST_META
#define SGLTHDRSZ
#define RelationGetTargetPageFreeSpace(relation, defaultff)
Definition: rel.h:316
#define GBUF_LEAF
bytea * spgoptions(Datum reloptions, bool validate)
Definition: spgutils.c:580
unsigned int SpGistGetTypeSize(SpGistTypeDesc *att, Datum datum)
Definition: spgutils.c:592
#define SPGIST_MAGIC_NUMBER
spgConfigOut config
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
SpGistLeafTuple spgFormLeafTuple(SpGistState *state, ItemPointer heapPtr, Datum datum, bool isnull)
Definition: spgutils.c:629
void LockRelationForExtension(Relation relation, LOCKMODE lockmode)
Definition: lmgr.c:332
bool amsearchnulls
Definition: amapi.h:185
SpGistLUPCache lastUsedPages
void * palloc0(Size size)
Definition: mcxt.c:864
unsigned int tupstate
void UnlockRelationForExtension(Relation relation, LOCKMODE lockmode)
Definition: lmgr.c:382
uintptr_t Datum
Definition: postgres.h:372
#define BufferGetPageSize(buffer)
Definition: bufmgr.h:147
static char * label
Definition: pg_basebackup.c:82
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
#define SPGIST_PAGE_CAPACITY
char * deadTupleStorage
bool amclusterable
Definition: amapi.h:189
Oid prefixType
Definition: spgist.h:47
TupleDesc rd_att
Definition: rel.h:115
#define VARSIZE_ANY(PTR)
Definition: postgres.h:334
void * MemoryContextAllocZero(MemoryContext context, Size size)
Definition: mcxt.c:728
Buffer SpGistNewBuffer(Relation index)
Definition: spgutils.c:204
OffsetNumber nextOffset
bool amsearcharray
Definition: amapi.h:183
#define InvalidOffsetNumber
Definition: off.h:26
#define InvalidOid
Definition: postgres_ext.h:36
#define GBUF_PARITY_MASK
BlockNumber GetFreeIndexPage(Relation rel)
Definition: indexfsm.c:38
#define SpGistPageStoresNulls(page)
void spgcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
Definition: selfuncs.c:7282
#define makeNode(_type_)
Definition: nodes.h:560
PageHeaderData * PageHeader
Definition: bufpage.h:162
#define Assert(condition)
Definition: c.h:680
Definition: regguts.h:298
#define SpGistPageIsDeleted(page)
#define SGNTDATAPTR(x)
Buffer SpGistGetBuffer(Relation index, int flags, int needSpace, bool *isNew)
Definition: spgutils.c:388
WalTimeSample buffer[LAG_TRACKER_BUFFER_SIZE]
Definition: walsender.c:215
#define SPGIST_COMPRESS_PROC
Definition: spgist.h:33
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:594
#define SPGIST_CONFIG_PROC
Definition: spgist.h:28
size_t Size
Definition: c.h:414
void SpGistInitMetapage(Page page)
Definition: spgutils.c:553
#define InvalidBlockNumber
Definition: block.h:33
void get_typlenbyval(Oid typid, int16 *typlen, bool *typbyval)
Definition: lsyscache.c:2020
#define MAXALIGN(LEN)
Definition: c.h:633
#define GBUF_NULLS
OffsetNumber nextOffset
ammarkpos_function ammarkpos
Definition: amapi.h:213
bool amcanorder
Definition: amapi.h:171
#define SPGIST_CACHED_PAGES
#define SpGistPageGetMeta(p)
amestimateparallelscan_function amestimateparallelscan
Definition: amapi.h:217
SpGistTypeDesc attLabelType
IndexBuildResult * spgbuild(Relation heap, Relation index, IndexInfo *indexInfo)
Definition: spginsert.c:70
#define DatumGetPointer(X)
Definition: postgres.h:555
Size PageGetExactFreeSpace(Page page)
Definition: bufpage.c:629
#define SpGistPageGetOpaque(page)
uint16 amstrategies
Definition: amapi.h:167
bytea * default_reloptions(Datum reloptions, bool validate, relopt_kind kind)
Definition: reloptions.c:1326
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2605
#define ItemPointerSetInvalid(pointer)
Definition: itemptr.h:150
static void memcpyDatum(void *target, SpGistTypeDesc *att, Datum datum)
Definition: spgutils.c:610
#define PageIsNew(page)
Definition: bufpage.h:225
void SpGistInitPage(Page page, uint16 f)
Definition: spgutils.c:528
void * palloc(Size size)
Definition: mcxt.c:835
int errmsg(const char *fmt,...)
Definition: elog.c:797
#define SPGISTNProc
Definition: spgist.h:35
bool spgvalidate(Oid opclassoid)
Definition: spgvalidate.c:39
bool spggettuple(IndexScanDesc scan, ScanDirection dir)
Definition: spgscan.c:605
ambuildempty_function ambuildempty
Definition: amapi.h:199
MemoryContext rd_indexcxt
Definition: rel.h:179
Oid labelType
Definition: spgist.h:48
int i
Oid leafType
Definition: spgist.h:49
#define BUFFER_LOCK_SHARE
Definition: bufmgr.h:88
SpGistTypeDesc attPrefixType
Definition: c.h:497
#define PG_FUNCTION_ARGS
Definition: fmgr.h:158
#define SGNTDATUM(x, s)
IndexScanDesc spgbeginscan(Relation rel, int keysz, int orderbysz)
Definition: spgscan.c:181
static void fillTypeDesc(SpGistTypeDesc *desc, Oid type)
Definition: spgutils.c:81
ItemPointerData heapPtr
#define elog
Definition: elog.h:219
unsigned short t_info
Definition: itup.h:49
#define TransactionIdIsValid(xid)
Definition: transam.h:41
void * rd_amcache
Definition: rel.h:192
SpGistLeafTupleData * SpGistLeafTuple
#define SPGIST_LEAF
int Buffer
Definition: buf.h:23
amcanreturn_function amcanreturn
Definition: amapi.h:203
OffsetNumber SpGistPageAddNewItem(SpGistState *state, Page page, Item item, Size size, OffsetNumber *startOffset, bool errorOK)
Definition: spgutils.c:864
SpGistNodeTuple spgFormNodeTuple(SpGistState *state, Datum label, bool isnull)
Definition: spgutils.c:666
#define SGITHDRSZ
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
Pointer Page
Definition: bufpage.h:74
#define IndexTupleSize(itup)
Definition: itup.h:70
#define ItemPointerSet(pointer, blockNumber, offNum)
Definition: itemptr.h:105
aminitparallelscan_function aminitparallelscan
Definition: amapi.h:218
Datum spghandler(PG_FUNCTION_ARGS)
Definition: spgutils.c:35
amrestrpos_function amrestrpos
Definition: amapi.h:214
SpGistNodeTupleData * SpGistNodeTuple
void PageInit(Page page, Size pageSize, Size specialSize)
Definition: bufpage.c:41
#define GBUF_REQ_LEAF(flags)
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:821