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