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