PostgreSQL Source Code  git master
gistutil.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * gistutil.c
4  * utilities routines for the postgres GiST index access method.
5  *
6  *
7  * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
8  * Portions Copyright (c) 1994, Regents of the University of California
9  *
10  * IDENTIFICATION
11  * src/backend/access/gist/gistutil.c
12  *-------------------------------------------------------------------------
13  */
14 #include "postgres.h"
15 
16 #include <math.h>
17 
18 #include "access/gist_private.h"
19 #include "access/htup_details.h"
20 #include "access/reloptions.h"
21 #include "catalog/pg_opclass.h"
22 #include "storage/indexfsm.h"
23 #include "storage/lmgr.h"
24 #include "utils/float.h"
25 #include "utils/lsyscache.h"
26 #include "utils/snapmgr.h"
27 #include "utils/syscache.h"
28 
29 /*
30  * Write itup vector to page, has no control of free space.
31  */
32 void
34 {
35  int i;
36 
37  if (off == InvalidOffsetNumber)
38  off = (PageIsEmpty(page)) ? FirstOffsetNumber :
40 
41  for (i = 0; i < len; i++)
42  {
43  Size sz = IndexTupleSize(itup[i]);
44  OffsetNumber l;
45 
46  l = PageAddItem(page, (Item) itup[i], sz, off, false, false);
47  if (l == InvalidOffsetNumber)
48  elog(ERROR, "failed to add item to GiST index page, item %d out of %d, size %d bytes",
49  i, len, (int) sz);
50  off++;
51  }
52 }
53 
54 /*
55  * Check space for itup vector on page
56  */
57 bool
58 gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace)
59 {
60  unsigned int size = freespace,
61  deleted = 0;
62  int i;
63 
64  for (i = 0; i < len; i++)
65  size += IndexTupleSize(itvec[i]) + sizeof(ItemIdData);
66 
67  if (todelete != InvalidOffsetNumber)
68  {
69  IndexTuple itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, todelete));
70 
71  deleted = IndexTupleSize(itup) + sizeof(ItemIdData);
72  }
73 
74  return (PageGetFreeSpace(page) + deleted < size);
75 }
76 
77 bool
78 gistfitpage(IndexTuple *itvec, int len)
79 {
80  int i;
81  Size size = 0;
82 
83  for (i = 0; i < len; i++)
84  size += IndexTupleSize(itvec[i]) + sizeof(ItemIdData);
85 
86  /* TODO: Consider fillfactor */
87  return (size <= GiSTPageSize);
88 }
89 
90 /*
91  * Read buffer into itup vector
92  */
93 IndexTuple *
94 gistextractpage(Page page, int *len /* out */ )
95 {
97  maxoff;
98  IndexTuple *itvec;
99 
100  maxoff = PageGetMaxOffsetNumber(page);
101  *len = maxoff;
102  itvec = palloc(sizeof(IndexTuple) * maxoff);
103  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
104  itvec[i - FirstOffsetNumber] = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));
105 
106  return itvec;
107 }
108 
109 /*
110  * join two vectors into one
111  */
112 IndexTuple *
113 gistjoinvector(IndexTuple *itvec, int *len, IndexTuple *additvec, int addlen)
114 {
115  itvec = (IndexTuple *) repalloc((void *) itvec, sizeof(IndexTuple) * ((*len) + addlen));
116  memmove(&itvec[*len], additvec, sizeof(IndexTuple) * addlen);
117  *len += addlen;
118  return itvec;
119 }
120 
121 /*
122  * make plain IndexTuple vector
123  */
124 
126 gistfillitupvec(IndexTuple *vec, int veclen, int *memlen)
127 {
128  char *ptr,
129  *ret;
130  int i;
131 
132  *memlen = 0;
133 
134  for (i = 0; i < veclen; i++)
135  *memlen += IndexTupleSize(vec[i]);
136 
137  ptr = ret = palloc(*memlen);
138 
139  for (i = 0; i < veclen; i++)
140  {
141  memcpy(ptr, vec[i], IndexTupleSize(vec[i]));
142  ptr += IndexTupleSize(vec[i]);
143  }
144 
145  return (IndexTupleData *) ret;
146 }
147 
148 /*
149  * Make unions of keys in IndexTuple vector (one union datum per index column).
150  * Union Datums are returned into the attr/isnull arrays.
151  * Resulting Datums aren't compressed.
152  */
153 void
154 gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len,
155  Datum *attr, bool *isnull)
156 {
157  int i;
158  GistEntryVector *evec;
159  int attrsize;
160 
161  evec = (GistEntryVector *) palloc((len + 2) * sizeof(GISTENTRY) + GEVHDRSZ);
162 
163  for (i = 0; i < giststate->nonLeafTupdesc->natts; i++)
164  {
165  int j;
166 
167  /* Collect non-null datums for this column */
168  evec->n = 0;
169  for (j = 0; j < len; j++)
170  {
171  Datum datum;
172  bool IsNull;
173 
174  datum = index_getattr(itvec[j], i + 1, giststate->leafTupdesc,
175  &IsNull);
176  if (IsNull)
177  continue;
178 
179  gistdentryinit(giststate, i,
180  evec->vector + evec->n,
181  datum,
182  NULL, NULL, (OffsetNumber) 0,
183  false, IsNull);
184  evec->n++;
185  }
186 
187  /* If this column was all NULLs, the union is NULL */
188  if (evec->n == 0)
189  {
190  attr[i] = (Datum) 0;
191  isnull[i] = true;
192  }
193  else
194  {
195  if (evec->n == 1)
196  {
197  /* unionFn may expect at least two inputs */
198  evec->n = 2;
199  evec->vector[1] = evec->vector[0];
200  }
201 
202  /* Make union and store in attr array */
203  attr[i] = FunctionCall2Coll(&giststate->unionFn[i],
204  giststate->supportCollation[i],
205  PointerGetDatum(evec),
206  PointerGetDatum(&attrsize));
207 
208  isnull[i] = false;
209  }
210  }
211 }
212 
213 /*
214  * Return an IndexTuple containing the result of applying the "union"
215  * method to the specified IndexTuple vector.
216  */
218 gistunion(Relation r, IndexTuple *itvec, int len, GISTSTATE *giststate)
219 {
220  Datum attr[INDEX_MAX_KEYS];
221  bool isnull[INDEX_MAX_KEYS];
222 
223  gistMakeUnionItVec(giststate, itvec, len, attr, isnull);
224 
225  return gistFormTuple(giststate, r, attr, isnull, false);
226 }
227 
228 /*
229  * makes union of two key
230  */
231 void
232 gistMakeUnionKey(GISTSTATE *giststate, int attno,
233  GISTENTRY *entry1, bool isnull1,
234  GISTENTRY *entry2, bool isnull2,
235  Datum *dst, bool *dstisnull)
236 {
237  /* we need a GistEntryVector with room for exactly 2 elements */
238  union
239  {
240  GistEntryVector gev;
241  char padding[2 * sizeof(GISTENTRY) + GEVHDRSZ];
242  } storage;
243  GistEntryVector *evec = &storage.gev;
244  int dstsize;
245 
246  evec->n = 2;
247 
248  if (isnull1 && isnull2)
249  {
250  *dstisnull = true;
251  *dst = (Datum) 0;
252  }
253  else
254  {
255  if (isnull1 == false && isnull2 == false)
256  {
257  evec->vector[0] = *entry1;
258  evec->vector[1] = *entry2;
259  }
260  else if (isnull1 == false)
261  {
262  evec->vector[0] = *entry1;
263  evec->vector[1] = *entry1;
264  }
265  else
266  {
267  evec->vector[0] = *entry2;
268  evec->vector[1] = *entry2;
269  }
270 
271  *dstisnull = false;
272  *dst = FunctionCall2Coll(&giststate->unionFn[attno],
273  giststate->supportCollation[attno],
274  PointerGetDatum(evec),
275  PointerGetDatum(&dstsize));
276  }
277 }
278 
279 bool
280 gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b)
281 {
282  bool result;
283 
284  FunctionCall3Coll(&giststate->equalFn[attno],
285  giststate->supportCollation[attno],
286  a, b,
287  PointerGetDatum(&result));
288  return result;
289 }
290 
291 /*
292  * Decompress all keys in tuple
293  */
294 void
296  OffsetNumber o, GISTENTRY *attdata, bool *isnull)
297 {
298  int i;
299 
300  for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(r); i++)
301  {
302  Datum datum;
303 
304  datum = index_getattr(tuple, i + 1, giststate->leafTupdesc, &isnull[i]);
305  gistdentryinit(giststate, i, &attdata[i],
306  datum, r, p, o,
307  false, isnull[i]);
308  }
309 }
310 
311 /*
312  * Forms union of oldtup and addtup, if union == oldtup then return NULL
313  */
316 {
317  bool neednew = false;
318  GISTENTRY oldentries[INDEX_MAX_KEYS],
319  addentries[INDEX_MAX_KEYS];
320  bool oldisnull[INDEX_MAX_KEYS],
321  addisnull[INDEX_MAX_KEYS];
322  Datum attr[INDEX_MAX_KEYS];
323  bool isnull[INDEX_MAX_KEYS];
324  IndexTuple newtup = NULL;
325  int i;
326 
327  gistDeCompressAtt(giststate, r, oldtup, NULL,
328  (OffsetNumber) 0, oldentries, oldisnull);
329 
330  gistDeCompressAtt(giststate, r, addtup, NULL,
331  (OffsetNumber) 0, addentries, addisnull);
332 
333  for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(r); i++)
334  {
335  gistMakeUnionKey(giststate, i,
336  oldentries + i, oldisnull[i],
337  addentries + i, addisnull[i],
338  attr + i, isnull + i);
339 
340  if (neednew)
341  /* we already need new key, so we can skip check */
342  continue;
343 
344  if (isnull[i])
345  /* union of key may be NULL if and only if both keys are NULL */
346  continue;
347 
348  if (!addisnull[i])
349  {
350  if (oldisnull[i] ||
351  !gistKeyIsEQ(giststate, i, oldentries[i].key, attr[i]))
352  neednew = true;
353  }
354  }
355 
356  if (neednew)
357  {
358  /* need to update key */
359  newtup = gistFormTuple(giststate, r, attr, isnull, false);
360  newtup->t_tid = oldtup->t_tid;
361  }
362 
363  return newtup;
364 }
365 
366 /*
367  * Search an upper index page for the entry with lowest penalty for insertion
368  * of the new index key contained in "it".
369  *
370  * Returns the index of the page entry to insert into.
371  */
373 gistchoose(Relation r, Page p, IndexTuple it, /* it has compressed entry */
374  GISTSTATE *giststate)
375 {
376  OffsetNumber result;
377  OffsetNumber maxoff;
378  OffsetNumber i;
379  float best_penalty[INDEX_MAX_KEYS];
380  GISTENTRY entry,
381  identry[INDEX_MAX_KEYS];
382  bool isnull[INDEX_MAX_KEYS];
383  int keep_current_best;
384 
385  Assert(!GistPageIsLeaf(p));
386 
387  gistDeCompressAtt(giststate, r,
388  it, NULL, (OffsetNumber) 0,
389  identry, isnull);
390 
391  /* we'll return FirstOffsetNumber if page is empty (shouldn't happen) */
392  result = FirstOffsetNumber;
393 
394  /*
395  * The index may have multiple columns, and there's a penalty value for
396  * each column. The penalty associated with a column that appears earlier
397  * in the index definition is strictly more important than the penalty of
398  * a column that appears later in the index definition.
399  *
400  * best_penalty[j] is the best penalty we have seen so far for column j,
401  * or -1 when we haven't yet examined column j. Array entries to the
402  * right of the first -1 are undefined.
403  */
404  best_penalty[0] = -1;
405 
406  /*
407  * If we find a tuple that's exactly as good as the currently best one, we
408  * could use either one. When inserting a lot of tuples with the same or
409  * similar keys, it's preferable to descend down the same path when
410  * possible, as that's more cache-friendly. On the other hand, if all
411  * inserts land on the same leaf page after a split, we're never going to
412  * insert anything to the other half of the split, and will end up using
413  * only 50% of the available space. Distributing the inserts evenly would
414  * lead to better space usage, but that hurts cache-locality during
415  * insertion. To get the best of both worlds, when we find a tuple that's
416  * exactly as good as the previous best, choose randomly whether to stick
417  * to the old best, or use the new one. Once we decide to stick to the
418  * old best, we keep sticking to it for any subsequent equally good tuples
419  * we might find. This favors tuples with low offsets, but still allows
420  * some inserts to go to other equally-good subtrees.
421  *
422  * keep_current_best is -1 if we haven't yet had to make a random choice
423  * whether to keep the current best tuple. If we have done so, and
424  * decided to keep it, keep_current_best is 1; if we've decided to
425  * replace, keep_current_best is 0. (This state will be reset to -1 as
426  * soon as we've made the replacement, but sometimes we make the choice in
427  * advance of actually finding a replacement best tuple.)
428  */
429  keep_current_best = -1;
430 
431  /*
432  * Loop over tuples on page.
433  */
434  maxoff = PageGetMaxOffsetNumber(p);
435  Assert(maxoff >= FirstOffsetNumber);
436 
437  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
438  {
439  IndexTuple itup = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
440  bool zero_penalty;
441  int j;
442 
443  zero_penalty = true;
444 
445  /* Loop over index attributes. */
446  for (j = 0; j < IndexRelationGetNumberOfKeyAttributes(r); j++)
447  {
448  Datum datum;
449  float usize;
450  bool IsNull;
451 
452  /* Compute penalty for this column. */
453  datum = index_getattr(itup, j + 1, giststate->leafTupdesc,
454  &IsNull);
455  gistdentryinit(giststate, j, &entry, datum, r, p, i,
456  false, IsNull);
457  usize = gistpenalty(giststate, j, &entry, IsNull,
458  &identry[j], isnull[j]);
459  if (usize > 0)
460  zero_penalty = false;
461 
462  if (best_penalty[j] < 0 || usize < best_penalty[j])
463  {
464  /*
465  * New best penalty for column. Tentatively select this tuple
466  * as the target, and record the best penalty. Then reset the
467  * next column's penalty to "unknown" (and indirectly, the
468  * same for all the ones to its right). This will force us to
469  * adopt this tuple's penalty values as the best for all the
470  * remaining columns during subsequent loop iterations.
471  */
472  result = i;
473  best_penalty[j] = usize;
474 
476  best_penalty[j + 1] = -1;
477 
478  /* we have new best, so reset keep-it decision */
479  keep_current_best = -1;
480  }
481  else if (best_penalty[j] == usize)
482  {
483  /*
484  * The current tuple is exactly as good for this column as the
485  * best tuple seen so far. The next iteration of this loop
486  * will compare the next column.
487  */
488  }
489  else
490  {
491  /*
492  * The current tuple is worse for this column than the best
493  * tuple seen so far. Skip the remaining columns and move on
494  * to the next tuple, if any.
495  */
496  zero_penalty = false; /* so outer loop won't exit */
497  break;
498  }
499  }
500 
501  /*
502  * If we looped past the last column, and did not update "result",
503  * then this tuple is exactly as good as the prior best tuple.
504  */
505  if (j == IndexRelationGetNumberOfKeyAttributes(r) && result != i)
506  {
507  if (keep_current_best == -1)
508  {
509  /* we didn't make the random choice yet for this old best */
510  keep_current_best = (random() <= (MAX_RANDOM_VALUE / 2)) ? 1 : 0;
511  }
512  if (keep_current_best == 0)
513  {
514  /* we choose to use the new tuple */
515  result = i;
516  /* choose again if there are even more exactly-as-good ones */
517  keep_current_best = -1;
518  }
519  }
520 
521  /*
522  * If we find a tuple with zero penalty for all columns, and we've
523  * decided we don't want to search for another tuple with equal
524  * penalty, there's no need to examine remaining tuples; just break
525  * out of the loop and return it.
526  */
527  if (zero_penalty)
528  {
529  if (keep_current_best == -1)
530  {
531  /* we didn't make the random choice yet for this old best */
532  keep_current_best = (random() <= (MAX_RANDOM_VALUE / 2)) ? 1 : 0;
533  }
534  if (keep_current_best == 1)
535  break;
536  }
537  }
538 
539  return result;
540 }
541 
542 /*
543  * initialize a GiST entry with a decompressed version of key
544  */
545 void
546 gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
547  Datum k, Relation r, Page pg, OffsetNumber o,
548  bool l, bool isNull)
549 {
550  if (!isNull)
551  {
552  GISTENTRY *dep;
553 
554  gistentryinit(*e, k, r, pg, o, l);
555 
556  /* there may not be a decompress function in opclass */
557  if (!OidIsValid(giststate->decompressFn[nkey].fn_oid))
558  return;
559 
560  dep = (GISTENTRY *)
562  giststate->supportCollation[nkey],
563  PointerGetDatum(e)));
564  /* decompressFn may just return the given pointer */
565  if (dep != e)
566  gistentryinit(*e, dep->key, dep->rel, dep->page, dep->offset,
567  dep->leafkey);
568  }
569  else
570  gistentryinit(*e, (Datum) 0, r, pg, o, l);
571 }
572 
575  Datum *attdata, bool *isnull, bool isleaf)
576 {
577  Datum compatt[INDEX_MAX_KEYS];
578  IndexTuple res;
579 
580  gistCompressValues(giststate, r, attdata, isnull, isleaf, compatt);
581 
582  res = index_form_tuple(isleaf ? giststate->leafTupdesc :
583  giststate->nonLeafTupdesc,
584  compatt, isnull);
585 
586  /*
587  * The offset number on tuples on internal pages is unused. For historical
588  * reasons, it is set to 0xffff.
589  */
590  ItemPointerSetOffsetNumber(&(res->t_tid), 0xffff);
591  return res;
592 }
593 
594 void
596  Datum *attdata, bool *isnull, bool isleaf, Datum *compatt)
597 {
598  int i;
599 
600  /*
601  * Call the compress method on each attribute.
602  */
603  for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(r); i++)
604  {
605  if (isnull[i])
606  compatt[i] = (Datum) 0;
607  else
608  {
609  GISTENTRY centry;
610  GISTENTRY *cep;
611 
612  gistentryinit(centry, attdata[i], r, NULL, (OffsetNumber) 0,
613  isleaf);
614  /* there may not be a compress function in opclass */
615  if (OidIsValid(giststate->compressFn[i].fn_oid))
616  cep = (GISTENTRY *)
618  giststate->supportCollation[i],
619  PointerGetDatum(&centry)));
620  else
621  cep = &centry;
622  compatt[i] = cep->key;
623  }
624  }
625 
626  if (isleaf)
627  {
628  /*
629  * Emplace each included attribute if any.
630  */
631  for (; i < r->rd_att->natts; i++)
632  {
633  if (isnull[i])
634  compatt[i] = (Datum) 0;
635  else
636  compatt[i] = attdata[i];
637  }
638  }
639 }
640 
641 /*
642  * initialize a GiST entry with fetched value in key field
643  */
644 static Datum
645 gistFetchAtt(GISTSTATE *giststate, int nkey, Datum k, Relation r)
646 {
647  GISTENTRY fentry;
648  GISTENTRY *fep;
649 
650  gistentryinit(fentry, k, r, NULL, (OffsetNumber) 0, false);
651 
652  fep = (GISTENTRY *)
653  DatumGetPointer(FunctionCall1Coll(&giststate->fetchFn[nkey],
654  giststate->supportCollation[nkey],
655  PointerGetDatum(&fentry)));
656 
657  /* fetchFn set 'key', return it to the caller */
658  return fep->key;
659 }
660 
661 /*
662  * Fetch all keys in tuple.
663  * Returns a new HeapTuple containing the originally-indexed data.
664  */
665 HeapTuple
667 {
668  MemoryContext oldcxt = MemoryContextSwitchTo(giststate->tempCxt);
670  bool isnull[INDEX_MAX_KEYS];
671  int i;
672 
673  for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(r); i++)
674  {
675  Datum datum;
676 
677  datum = index_getattr(tuple, i + 1, giststate->leafTupdesc, &isnull[i]);
678 
679  if (giststate->fetchFn[i].fn_oid != InvalidOid)
680  {
681  if (!isnull[i])
682  fetchatt[i] = gistFetchAtt(giststate, i, datum, r);
683  else
684  fetchatt[i] = (Datum) 0;
685  }
686  else if (giststate->compressFn[i].fn_oid == InvalidOid)
687  {
688  /*
689  * If opclass does not provide compress method that could change
690  * original value, att is necessarily stored in original form.
691  */
692  if (!isnull[i])
693  fetchatt[i] = datum;
694  else
695  fetchatt[i] = (Datum) 0;
696  }
697  else
698  {
699  /*
700  * Index-only scans not supported for this column. Since the
701  * planner chose an index-only scan anyway, it is not interested
702  * in this column, and we can replace it with a NULL.
703  */
704  isnull[i] = true;
705  fetchatt[i] = (Datum) 0;
706  }
707  }
708 
709  /*
710  * Get each included attribute.
711  */
712  for (; i < r->rd_att->natts; i++)
713  {
714  fetchatt[i] = index_getattr(tuple, i + 1, giststate->leafTupdesc,
715  &isnull[i]);
716  }
717  MemoryContextSwitchTo(oldcxt);
718 
719  return heap_form_tuple(giststate->fetchTupdesc, fetchatt, isnull);
720 }
721 
722 float
723 gistpenalty(GISTSTATE *giststate, int attno,
724  GISTENTRY *orig, bool isNullOrig,
725  GISTENTRY *add, bool isNullAdd)
726 {
727  float penalty = 0.0;
728 
729  if (giststate->penaltyFn[attno].fn_strict == false ||
730  (isNullOrig == false && isNullAdd == false))
731  {
732  FunctionCall3Coll(&giststate->penaltyFn[attno],
733  giststate->supportCollation[attno],
734  PointerGetDatum(orig),
735  PointerGetDatum(add),
736  PointerGetDatum(&penalty));
737  /* disallow negative or NaN penalty */
738  if (isnan(penalty) || penalty < 0.0)
739  penalty = 0.0;
740  }
741  else if (isNullOrig && isNullAdd)
742  penalty = 0.0;
743  else
744  {
745  /* try to prevent mixing null and non-null values */
746  penalty = get_float4_infinity();
747  }
748 
749  return penalty;
750 }
751 
752 /*
753  * Initialize a new index page
754  */
755 void
757 {
758  GISTPageOpaque opaque;
759  Size pageSize = BLCKSZ;
760 
761  PageInit(page, pageSize, sizeof(GISTPageOpaqueData));
762 
763  opaque = GistPageGetOpaque(page);
764  /* page was already zeroed by PageInit, so this is not needed: */
765  /* memset(&(opaque->nsn), 0, sizeof(GistNSN)); */
766  opaque->rightlink = InvalidBlockNumber;
767  opaque->flags = f;
768  opaque->gist_page_id = GIST_PAGE_ID;
769 }
770 
771 /*
772  * Initialize a new index buffer
773  */
774 void
776 {
777  Page page;
778 
779  page = BufferGetPage(b);
780  gistinitpage(page, f);
781 }
782 
783 /*
784  * Verify that a freshly-read page looks sane.
785  */
786 void
788 {
789  Page page = BufferGetPage(buf);
790 
791  /*
792  * ReadBuffer verifies that every newly-read page passes
793  * PageHeaderIsValid, which means it either contains a reasonably sane
794  * page header or is all-zero. We have to defend against the all-zero
795  * case, however.
796  */
797  if (PageIsNew(page))
798  ereport(ERROR,
799  (errcode(ERRCODE_INDEX_CORRUPTED),
800  errmsg("index \"%s\" contains unexpected zero page at block %u",
802  BufferGetBlockNumber(buf)),
803  errhint("Please REINDEX it.")));
804 
805  /*
806  * Additionally check that the special area looks sane.
807  */
808  if (PageGetSpecialSize(page) != MAXALIGN(sizeof(GISTPageOpaqueData)))
809  ereport(ERROR,
810  (errcode(ERRCODE_INDEX_CORRUPTED),
811  errmsg("index \"%s\" contains corrupted page at block %u",
813  BufferGetBlockNumber(buf)),
814  errhint("Please REINDEX it.")));
815 }
816 
817 
818 /*
819  * Allocate a new page (either by recycling, or by extending the index file)
820  *
821  * The returned buffer is already pinned and exclusive-locked
822  *
823  * Caller is responsible for initializing the page by calling GISTInitBuffer
824  */
825 Buffer
827 {
828  Buffer buffer;
829  bool needLock;
830 
831  /* First, try to get a page from FSM */
832  for (;;)
833  {
834  BlockNumber blkno = GetFreeIndexPage(r);
835 
836  if (blkno == InvalidBlockNumber)
837  break; /* nothing left in FSM */
838 
839  buffer = ReadBuffer(r, blkno);
840 
841  /*
842  * We have to guard against the possibility that someone else already
843  * recycled this page; the buffer may be locked if so.
844  */
845  if (ConditionalLockBuffer(buffer))
846  {
847  Page page = BufferGetPage(buffer);
848 
849  /*
850  * If the page was never initialized, it's OK to use.
851  */
852  if (PageIsNew(page))
853  return buffer;
854 
855  gistcheckpage(r, buffer);
856 
857  /*
858  * Otherwise, recycle it if deleted, and too old to have any
859  * processes interested in it.
860  */
861  if (gistPageRecyclable(page))
862  {
863  /*
864  * If we are generating WAL for Hot Standby then create a WAL
865  * record that will allow us to conflict with queries running
866  * on standby, in case they have snapshots older than the
867  * page's deleteXid.
868  */
870  gistXLogPageReuse(r, blkno, GistPageGetDeleteXid(page));
871 
872  return buffer;
873  }
874 
875  LockBuffer(buffer, GIST_UNLOCK);
876  }
877 
878  /* Can't use it, so release buffer and try again */
879  ReleaseBuffer(buffer);
880  }
881 
882  /* Must extend the file */
883  needLock = !RELATION_IS_LOCAL(r);
884 
885  if (needLock)
887 
888  buffer = ReadBuffer(r, P_NEW);
889  LockBuffer(buffer, GIST_EXCLUSIVE);
890 
891  if (needLock)
893 
894  return buffer;
895 }
896 
897 /* Can this page be recycled yet? */
898 bool
900 {
901  if (PageIsNew(page))
902  return true;
903  if (GistPageIsDeleted(page))
904  {
905  /*
906  * The page was deleted, but when? If it was just deleted, a scan
907  * might have seen the downlink to it, and will read the page later.
908  * As long as that can happen, we must keep the deleted page around as
909  * a tombstone.
910  *
911  * For that check if the deletion XID could still be visible to
912  * anyone. If not, then no scan that's still in progress could have
913  * seen its downlink, and we can recycle it.
914  */
915  FullTransactionId deletexid_full = GistPageGetDeleteXid(page);
916 
917  return GlobalVisIsRemovableFullXid(NULL, deletexid_full);
918  }
919  return false;
920 }
921 
922 bytea *
923 gistoptions(Datum reloptions, bool validate)
924 {
925  static const relopt_parse_elt tab[] = {
926  {"fillfactor", RELOPT_TYPE_INT, offsetof(GiSTOptions, fillfactor)},
927  {"buffering", RELOPT_TYPE_ENUM, offsetof(GiSTOptions, buffering_mode)}
928  };
929 
930  return (bytea *) build_reloptions(reloptions, validate,
932  sizeof(GiSTOptions),
933  tab, lengthof(tab));
934 }
935 
936 /*
937  * gistproperty() -- Check boolean properties of indexes.
938  *
939  * This is optional for most AMs, but is required for GiST because the core
940  * property code doesn't support AMPROP_DISTANCE_ORDERABLE. We also handle
941  * AMPROP_RETURNABLE here to save opening the rel to call gistcanreturn.
942  */
943 bool
944 gistproperty(Oid index_oid, int attno,
945  IndexAMProperty prop, const char *propname,
946  bool *res, bool *isnull)
947 {
948  Oid opclass,
949  opfamily,
950  opcintype;
951  int16 procno;
952 
953  /* Only answer column-level inquiries */
954  if (attno == 0)
955  return false;
956 
957  /*
958  * Currently, GiST distance-ordered scans require that there be a distance
959  * function in the opclass with the default types (i.e. the one loaded
960  * into the relcache entry, see initGISTstate). So we assume that if such
961  * a function exists, then there's a reason for it (rather than grubbing
962  * through all the opfamily's operators to find an ordered one).
963  *
964  * Essentially the same code can test whether we support returning the
965  * column data, since that's true if the opclass provides a fetch proc.
966  */
967 
968  switch (prop)
969  {
971  procno = GIST_DISTANCE_PROC;
972  break;
973  case AMPROP_RETURNABLE:
974  procno = GIST_FETCH_PROC;
975  break;
976  default:
977  return false;
978  }
979 
980  /* First we need to know the column's opclass. */
981  opclass = get_index_column_opclass(index_oid, attno);
982  if (!OidIsValid(opclass))
983  {
984  *isnull = true;
985  return true;
986  }
987 
988  /* Now look up the opclass family and input datatype. */
989  if (!get_opclass_opfamily_and_input_type(opclass, &opfamily, &opcintype))
990  {
991  *isnull = true;
992  return true;
993  }
994 
995  /* And now we can check whether the function is provided. */
996 
998  ObjectIdGetDatum(opfamily),
999  ObjectIdGetDatum(opcintype),
1000  ObjectIdGetDatum(opcintype),
1001  Int16GetDatum(procno));
1002 
1003  /*
1004  * Special case: even without a fetch function, AMPROP_RETURNABLE is true
1005  * if the opclass has no compress function.
1006  */
1007  if (prop == AMPROP_RETURNABLE && !*res)
1008  {
1010  ObjectIdGetDatum(opfamily),
1011  ObjectIdGetDatum(opcintype),
1012  ObjectIdGetDatum(opcintype),
1014  }
1015 
1016  *isnull = false;
1017 
1018  return true;
1019 }
1020 
1021 /*
1022  * Some indexes are not WAL-logged, but we need LSNs to detect concurrent page
1023  * splits anyway. This function provides a fake sequence of LSNs for that
1024  * purpose.
1025  */
1026 XLogRecPtr
1028 {
1029  if (rel->rd_rel->relpersistence == RELPERSISTENCE_TEMP)
1030  {
1031  /*
1032  * Temporary relations are only accessible in our session, so a simple
1033  * backend-local counter will do.
1034  */
1035  static XLogRecPtr counter = FirstNormalUnloggedLSN;
1036 
1037  return counter++;
1038  }
1039  else if (rel->rd_rel->relpersistence == RELPERSISTENCE_PERMANENT)
1040  {
1041  /*
1042  * WAL-logging on this relation will start after commit, so its LSNs
1043  * must be distinct numbers smaller than the LSN at the next commit.
1044  * Emit a dummy WAL record if insert-LSN hasn't advanced after the
1045  * last call.
1046  */
1047  static XLogRecPtr lastlsn = InvalidXLogRecPtr;
1048  XLogRecPtr currlsn = GetXLogInsertRecPtr();
1049 
1050  /* Shouldn't be called for WAL-logging relations */
1051  Assert(!RelationNeedsWAL(rel));
1052 
1053  /* No need for an actual record if we already have a distinct LSN */
1054  if (!XLogRecPtrIsInvalid(lastlsn) && lastlsn == currlsn)
1055  currlsn = gistXLogAssignLSN();
1056 
1057  lastlsn = currlsn;
1058  return currlsn;
1059  }
1060  else
1061  {
1062  /*
1063  * Unlogged relations are accessible from other backends, and survive
1064  * (clean) restarts. GetFakeLSNForUnloggedRel() handles that for us.
1065  */
1066  Assert(rel->rd_rel->relpersistence == RELPERSISTENCE_UNLOGGED);
1067  return GetFakeLSNForUnloggedRel();
1068  }
1069 }
Relation rel
Definition: gist.h:153
signed short int16
Definition: c.h:362
static Datum gistFetchAtt(GISTSTATE *giststate, int nkey, Datum k, Relation r)
Definition: gistutil.c:645
XLogRecPtr gistXLogAssignLSN(void)
Definition: gistxlog.c:601
#define InvalidXLogRecPtr
Definition: xlogdefs.h:28
#define GistPageIsDeleted(page)
Definition: gist.h:164
#define PageIsEmpty(page)
Definition: bufpage.h:222
int errhint(const char *fmt,...)
Definition: elog.c:1068
#define GIST_FETCH_PROC
Definition: gist.h:38
IndexAMProperty
Definition: amapi.h:34
FmgrInfo fetchFn[INDEX_MAX_KEYS]
Definition: gist_private.h:94
#define ExclusiveLock
Definition: lockdefs.h:44
Oid supportCollation[INDEX_MAX_KEYS]
Definition: gist_private.h:97
#define PointerGetDatum(X)
Definition: postgres.h:556
long random(void)
Definition: random.c:22
FmgrInfo compressFn[INDEX_MAX_KEYS]
Definition: gist_private.h:88
void gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p, OffsetNumber o, GISTENTRY *attdata, bool *isnull)
Definition: gistutil.c:295
FmgrInfo equalFn[INDEX_MAX_KEYS]
Definition: gist_private.h:92
#define RELATION_IS_LOCAL(relation)
Definition: rel.h:583
ItemPointerData t_tid
Definition: itup.h:37
void gistfillbuffer(Page page, IndexTuple *itup, int len, OffsetNumber off)
Definition: gistutil.c:33
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define Int16GetDatum(X)
Definition: postgres.h:451
Pointer Item
Definition: item.h:17
int32 n
Definition: gist.h:227
#define SearchSysCacheExists4(cacheId, key1, key2, key3, key4)
Definition: syscache.h:189
int errcode(int sqlerrcode)
Definition: elog.c:610
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
Definition: bufpage.h:416
#define GIST_UNLOCK
Definition: gist_private.h:44
uint32 BlockNumber
Definition: block.h:31
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3513
#define P_NEW
Definition: bufmgr.h:91
HeapTuple heap_form_tuple(TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: heaptuple.c:1020
#define lengthof(array)
Definition: c.h:676
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1152
Form_pg_class rd_rel
Definition: rel.h:109
unsigned int Oid
Definition: postgres_ext.h:31
bytea * gistoptions(Datum reloptions, bool validate)
Definition: gistutil.c:923
#define OidIsValid(objectId)
Definition: c.h:652
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:357
IndexTuple gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
Definition: gistutil.c:315
void gistinitpage(Page page, uint32 f)
Definition: gistutil.c:756
#define fetchatt(A, T)
Definition: tupmacs.h:41
XLogRecPtr gistGetFakeLSN(Relation rel)
Definition: gistutil.c:1027
Size PageGetFreeSpace(Page page)
Definition: bufpage.c:790
bool gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b)
Definition: gistutil.c:280
void * build_reloptions(Datum reloptions, bool validate, relopt_kind kind, Size relopt_struct_size, const relopt_parse_elt *relopt_elems, int num_relopt_elems)
Definition: reloptions.c:1887
uint16 OffsetNumber
Definition: off.h:24
Page page
Definition: gist.h:154
GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]
Definition: gist.h:228
IndexTuple index_form_tuple(TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: indextuple.c:47
bool get_opclass_opfamily_and_input_type(Oid opclass, Oid *opfamily, Oid *opcintype)
Definition: lsyscache.c:1174
IndexTuple * gistextractpage(Page page, int *len)
Definition: gistutil.c:94
uint16 gist_page_id
Definition: gist.h:74
#define GEVHDRSZ
Definition: gist.h:231
float gistpenalty(GISTSTATE *giststate, int attno, GISTENTRY *orig, bool isNullOrig, GISTENTRY *add, bool isNullAdd)
Definition: gistutil.c:723
void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e, Datum k, Relation r, Page pg, OffsetNumber o, bool l, bool isNull)
Definition: gistutil.c:546
struct GISTENTRY GISTENTRY
#define ObjectIdGetDatum(X)
Definition: postgres.h:507
#define ERROR
Definition: elog.h:43
bool fn_strict
Definition: fmgr.h:61
#define GIST_COMPRESS_PROC
Definition: gist.h:32
int fillfactor
Definition: pgbench.c:160
XLogRecPtr GetFakeLSNForUnloggedRel(void)
Definition: xlog.c:4949
XLogRecPtr GetXLogInsertRecPtr(void)
Definition: xlog.c:11519
MemoryContext tempCxt
Definition: gist_private.h:78
void gistXLogPageReuse(Relation rel, BlockNumber blkno, FullTransactionId latestRemovedXid)
Definition: gistxlog.c:619
Datum key
Definition: gist.h:152
static char * buf
Definition: pg_test_fsync.c:68
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
#define MAX_RANDOM_VALUE
bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace)
Definition: gistutil.c:58
#define RelationGetRelationName(relation)
Definition: rel.h:490
FmgrInfo penaltyFn[INDEX_MAX_KEYS]
Definition: gist_private.h:90
unsigned int uint32
Definition: c.h:375
void gistCompressValues(GISTSTATE *giststate, Relation r, Datum *attdata, bool *isnull, bool isleaf, Datum *compatt)
Definition: gistutil.c:595
struct ItemIdData ItemIdData
uint16 flags
Definition: gist.h:73
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:475
HeapTuple gistFetchTuple(GISTSTATE *giststate, Relation r, IndexTuple tuple)
Definition: gistutil.c:666
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
FmgrInfo decompressFn[INDEX_MAX_KEYS]
Definition: gist_private.h:89
bool ConditionalLockBuffer(Buffer buffer)
Definition: bufmgr.c:3778
bool leafkey
Definition: gist.h:156
TupleDesc leafTupdesc
Definition: gist_private.h:80
OffsetNumber gistchoose(Relation r, Page p, IndexTuple it, GISTSTATE *giststate)
Definition: gistutil.c:373
#define GistPageIsLeaf(page)
Definition: gist.h:161
#define XLogRecPtrIsInvalid(r)
Definition: xlogdefs.h:29
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
void LockRelationForExtension(Relation relation, LOCKMODE lockmode)
Definition: lmgr.c:402
#define GiSTPageSize
Definition: gist_private.h:474
IndexTuple * gistjoinvector(IndexTuple *itvec, int *len, IndexTuple *additvec, int addlen)
Definition: gistutil.c:113
void UnlockRelationForExtension(Relation relation, LOCKMODE lockmode)
Definition: lmgr.c:452
#define FirstNormalUnloggedLSN
Definition: xlogdefs.h:36
uintptr_t Datum
Definition: postgres.h:367
bool GlobalVisIsRemovableFullXid(Relation rel, FullTransactionId fxid)
Definition: procarray.c:4138
Datum FunctionCall1Coll(FmgrInfo *flinfo, Oid collation, Datum arg1)
Definition: fmgr.c:1132
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3752
#define XLogStandbyInfoActive()
Definition: xlog.h:205
TupleDesc rd_att
Definition: rel.h:110
#define InvalidOffsetNumber
Definition: off.h:26
#define InvalidOid
Definition: postgres_ext.h:36
TupleDesc nonLeafTupdesc
Definition: gist_private.h:81
Oid fn_oid
Definition: fmgr.h:59
#define ereport(elevel,...)
Definition: elog.h:144
Datum FunctionCall3Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2, Datum arg3)
Definition: fmgr.c:1174
BlockNumber GetFreeIndexPage(Relation rel)
Definition: indexfsm.c:38
bool gistfitpage(IndexTuple *itvec, int len)
Definition: gistutil.c:78
#define GistPageGetOpaque(page)
Definition: gist.h:159
void gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len, Datum *attr, bool *isnull)
Definition: gistutil.c:154
uint64 XLogRecPtr
Definition: xlogdefs.h:21
#define Assert(condition)
Definition: c.h:746
#define gistentryinit(e, k, r, pg, o, l)
Definition: gist.h:236
TupleDesc fetchTupdesc
Definition: gist_private.h:83
void gistcheckpage(Relation rel, Buffer buf)
Definition: gistutil.c:787
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:607
void gistMakeUnionKey(GISTSTATE *giststate, int attno, GISTENTRY *entry1, bool isnull1, GISTENTRY *entry2, bool isnull2, Datum *dst, bool *dstisnull)
Definition: gistutil.c:232
#define INDEX_MAX_KEYS
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
size_t Size
Definition: c.h:474
IndexTuple gistFormTuple(GISTSTATE *giststate, Relation r, Datum *attdata, bool *isnull, bool isleaf)
Definition: gistutil.c:574
IndexTupleData * gistfillitupvec(IndexTuple *vec, int veclen, int *memlen)
Definition: gistutil.c:126
#define InvalidBlockNumber
Definition: block.h:33
#define GIST_DISTANCE_PROC
Definition: gist.h:37
#define MAXALIGN(LEN)
Definition: c.h:699
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
#define RelationNeedsWAL(relation)
Definition: rel.h:562
#define PageGetSpecialSize(page)
Definition: bufpage.h:300
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1070
#define DatumGetPointer(X)
Definition: postgres.h:549
#define ItemPointerSetOffsetNumber(pointer, offsetNumber)
Definition: itemptr.h:148
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2663
e
Definition: preproc-init.c:82
static FullTransactionId GistPageGetDeleteXid(Page page)
Definition: gist.h:207
IndexTuple gistunion(Relation r, IndexTuple *itvec, int len, GISTSTATE *giststate)
Definition: gistutil.c:218
bool gistPageRecyclable(Page page)
Definition: gistutil.c:899
Oid get_index_column_opclass(Oid index_oid, int attno)
Definition: lsyscache.c:3287
#define PageIsNew(page)
Definition: bufpage.h:229
void * palloc(Size size)
Definition: mcxt.c:950
int errmsg(const char *fmt,...)
Definition: elog.c:821
#define elog(elevel,...)
Definition: elog.h:214
int i
void GISTInitBuffer(Buffer b, uint32 f)
Definition: gistutil.c:775
BlockNumber rightlink
Definition: gist.h:72
Definition: c.h:563
FmgrInfo unionFn[INDEX_MAX_KEYS]
Definition: gist_private.h:87
#define GIST_EXCLUSIVE
Definition: gist_private.h:43
OffsetNumber offset
Definition: gist.h:155
bool gistproperty(Oid index_oid, int attno, IndexAMProperty prop, const char *propname, bool *res, bool *isnull)
Definition: gistutil.c:944
int Buffer
Definition: buf.h:23
#define GIST_PAGE_ID
Definition: gist.h:103
Buffer gistNewBuffer(Relation r)
Definition: gistutil.c:826
#define offsetof(type, field)
Definition: c.h:669
#define PageGetItem(page, itemId)
Definition: bufpage.h:340
Pointer Page
Definition: bufpage.h:78
#define IndexTupleSize(itup)
Definition: itup.h:71
static float4 get_float4_infinity(void)
Definition: float.h:73
void PageInit(Page page, Size pageSize, Size specialSize)
Definition: bufpage.c:42