PostgreSQL Source Code  git master
ginget.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * ginget.c
4  * fetch tuples from a GIN scan.
5  *
6  *
7  * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
8  * Portions Copyright (c) 1994, Regents of the University of California
9  *
10  * IDENTIFICATION
11  * src/backend/access/gin/ginget.c
12  *-------------------------------------------------------------------------
13  */
14 
15 #include "postgres.h"
16 
17 #include "access/gin_private.h"
18 #include "access/relscan.h"
19 #include "miscadmin.h"
20 #include "storage/predicate.h"
21 #include "utils/datum.h"
22 #include "utils/memutils.h"
23 #include "utils/rel.h"
24 
25 /* GUC parameter */
27 
28 typedef struct pendingPosition
29 {
34  bool *hasMatchKey;
36 
37 
38 /*
39  * Place predicate lock on GIN page if needed.
40  */
41 static void
43 {
44  /*
45  * When fast update is on then no need in locking pages, because we
46  * anyway need to lock the whole index.
47  */
48  if (!GinGetUseFastUpdate(index))
49  PredicateLockPage(index, blkno, snapshot);
50 }
51 
52 /*
53  * Goes to the next page if current offset is outside of bounds
54  */
55 static bool
57 {
58  Page page = BufferGetPage(stack->buffer);
59 
60  if (stack->off > PageGetMaxOffsetNumber(page))
61  {
62  /*
63  * We scanned the whole page, so we should take right page
64  */
65  if (GinPageRightMost(page))
66  return false; /* no more pages */
67 
68  stack->buffer = ginStepRight(stack->buffer, btree->index, GIN_SHARE);
69  stack->blkno = BufferGetBlockNumber(stack->buffer);
70  stack->off = FirstOffsetNumber;
71  GinPredicateLockPage(btree->index, stack->blkno, snapshot);
72  }
73 
74  return true;
75 }
76 
77 /*
78  * Scan all pages of a posting tree and save all its heap ItemPointers
79  * in scanEntry->matchBitmap
80  */
81 static void
83  BlockNumber rootPostingTree, Snapshot snapshot)
84 {
85  GinBtreeData btree;
86  GinBtreeStack *stack;
87  Buffer buffer;
88  Page page;
89 
90  /* Descend to the leftmost leaf page */
91  stack = ginScanBeginPostingTree(&btree, index, rootPostingTree, snapshot);
92  buffer = stack->buffer;
93 
94  IncrBufferRefCount(buffer); /* prevent unpin in freeGinBtreeStack */
95 
96  freeGinBtreeStack(stack);
97 
98  /*
99  * Loop iterates through all leaf pages of posting tree
100  */
101  for (;;)
102  {
103  /*
104  * Predicate lock each leaf page in posting tree
105  */
106  GinPredicateLockPage(index, BufferGetBlockNumber(buffer), snapshot);
107 
108  page = BufferGetPage(buffer);
109  if ((GinPageGetOpaque(page)->flags & GIN_DELETED) == 0)
110  {
111  int n = GinDataLeafPageGetItemsToTbm(page, scanEntry->matchBitmap);
112 
113  scanEntry->predictNumberResult += n;
114  }
115 
116  if (GinPageRightMost(page))
117  break; /* no more pages */
118 
119  buffer = ginStepRight(buffer, index, GIN_SHARE);
120  }
121 
122  UnlockReleaseBuffer(buffer);
123 }
124 
125 /*
126  * Collects TIDs into scanEntry->matchBitmap for all heap tuples that
127  * match the search entry. This supports three different match modes:
128  *
129  * 1. Partial-match support: scan from current point until the
130  * comparePartialFn says we're done.
131  * 2. SEARCH_MODE_ALL: scan from current point (which should be first
132  * key for the current attnum) until we hit null items or end of attnum
133  * 3. SEARCH_MODE_EVERYTHING: scan from current point (which should be first
134  * key for the current attnum) until we hit end of attnum
135  *
136  * Returns true if done, false if it's necessary to restart scan from scratch
137  */
138 static bool
140  GinScanEntry scanEntry, Snapshot snapshot)
141 {
143  Form_pg_attribute attr;
144 
145  /* Initialize empty bitmap result */
146  scanEntry->matchBitmap = tbm_create(work_mem * 1024L, NULL);
147 
148  /* Null query cannot partial-match anything */
149  if (scanEntry->isPartialMatch &&
150  scanEntry->queryCategory != GIN_CAT_NORM_KEY)
151  return true;
152 
153  /* Locate tupdesc entry for key column (for attbyval/attlen data) */
154  attnum = scanEntry->attnum;
155  attr = TupleDescAttr(btree->ginstate->origTupdesc, attnum - 1);
156 
157  /*
158  * Predicate lock entry leaf page, following pages will be locked by
159  * moveRightIfItNeeded()
160  */
161  GinPredicateLockPage(btree->index, stack->buffer, snapshot);
162 
163  for (;;)
164  {
165  Page page;
166  IndexTuple itup;
167  Datum idatum;
168  GinNullCategory icategory;
169 
170  /*
171  * stack->off points to the interested entry, buffer is already locked
172  */
173  if (moveRightIfItNeeded(btree, stack, snapshot) == false)
174  return true;
175 
176  page = BufferGetPage(stack->buffer);
177  TestForOldSnapshot(snapshot, btree->index, page);
178  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
179 
180  /*
181  * If tuple stores another attribute then stop scan
182  */
183  if (gintuple_get_attrnum(btree->ginstate, itup) != attnum)
184  return true;
185 
186  /* Safe to fetch attribute value */
187  idatum = gintuple_get_key(btree->ginstate, itup, &icategory);
188 
189  /*
190  * Check for appropriate scan stop conditions
191  */
192  if (scanEntry->isPartialMatch)
193  {
194  int32 cmp;
195 
196  /*
197  * In partial match, stop scan at any null (including
198  * placeholders); partial matches never match nulls
199  */
200  if (icategory != GIN_CAT_NORM_KEY)
201  return true;
202 
203  /*----------
204  * Check of partial match.
205  * case cmp == 0 => match
206  * case cmp > 0 => not match and finish scan
207  * case cmp < 0 => not match and continue scan
208  *----------
209  */
210  cmp = DatumGetInt32(FunctionCall4Coll(&btree->ginstate->comparePartialFn[attnum - 1],
211  btree->ginstate->supportCollation[attnum - 1],
212  scanEntry->queryKey,
213  idatum,
214  UInt16GetDatum(scanEntry->strategy),
215  PointerGetDatum(scanEntry->extra_data)));
216 
217  if (cmp > 0)
218  return true;
219  else if (cmp < 0)
220  {
221  stack->off++;
222  continue;
223  }
224  }
225  else if (scanEntry->searchMode == GIN_SEARCH_MODE_ALL)
226  {
227  /*
228  * In ALL mode, we are not interested in null items, so we can
229  * stop if we get to a null-item placeholder (which will be the
230  * last entry for a given attnum). We do want to include NULL_KEY
231  * and EMPTY_ITEM entries, though.
232  */
233  if (icategory == GIN_CAT_NULL_ITEM)
234  return true;
235  }
236 
237  /*
238  * OK, we want to return the TIDs listed in this entry.
239  */
240  if (GinIsPostingTree(itup))
241  {
242  BlockNumber rootPostingTree = GinGetPostingTree(itup);
243 
244  /*
245  * We should unlock current page (but not unpin) during tree scan
246  * to prevent deadlock with vacuum processes.
247  *
248  * We save current entry value (idatum) to be able to re-find our
249  * tuple after re-locking
250  */
251  if (icategory == GIN_CAT_NORM_KEY)
252  idatum = datumCopy(idatum, attr->attbyval, attr->attlen);
253 
254  LockBuffer(stack->buffer, GIN_UNLOCK);
255 
256  /* Collect all the TIDs in this entry's posting tree */
257  scanPostingTree(btree->index, scanEntry, rootPostingTree,
258  snapshot);
259 
260  /*
261  * We lock again the entry page and while it was unlocked insert
262  * might have occurred, so we need to re-find our position.
263  */
264  LockBuffer(stack->buffer, GIN_SHARE);
265  page = BufferGetPage(stack->buffer);
266  if (!GinPageIsLeaf(page))
267  {
268  /*
269  * Root page becomes non-leaf while we unlock it. We will
270  * start again, this situation doesn't occur often - root can
271  * became a non-leaf only once per life of index.
272  */
273  return false;
274  }
275 
276  /* Search forward to re-find idatum */
277  for (;;)
278  {
279  Datum newDatum;
280  GinNullCategory newCategory;
281 
282  if (moveRightIfItNeeded(btree, stack, snapshot) == false)
283  elog(ERROR, "lost saved point in index"); /* must not happen !!! */
284 
285  page = BufferGetPage(stack->buffer);
286  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
287 
288  if (gintuple_get_attrnum(btree->ginstate, itup) != attnum)
289  elog(ERROR, "lost saved point in index"); /* must not happen !!! */
290  newDatum = gintuple_get_key(btree->ginstate, itup,
291  &newCategory);
292 
293  if (ginCompareEntries(btree->ginstate, attnum,
294  newDatum, newCategory,
295  idatum, icategory) == 0)
296  break; /* Found! */
297 
298  stack->off++;
299  }
300 
301  if (icategory == GIN_CAT_NORM_KEY && !attr->attbyval)
302  pfree(DatumGetPointer(idatum));
303  }
304  else
305  {
306  ItemPointer ipd;
307  int nipd;
308 
309  ipd = ginReadTuple(btree->ginstate, scanEntry->attnum, itup, &nipd);
310  tbm_add_tuples(scanEntry->matchBitmap, ipd, nipd, false);
311  scanEntry->predictNumberResult += GinGetNPosting(itup);
312  pfree(ipd);
313  }
314 
315  /*
316  * Done with this entry, go to the next
317  */
318  stack->off++;
319  }
320 }
321 
322 /*
323  * Start* functions setup beginning state of searches: finds correct buffer and pins it.
324  */
325 static void
326 startScanEntry(GinState *ginstate, GinScanEntry entry, Snapshot snapshot)
327 {
328  GinBtreeData btreeEntry;
329  GinBtreeStack *stackEntry;
330  Page page;
331  bool needUnlock;
332 
333 restartScanEntry:
334  entry->buffer = InvalidBuffer;
335  ItemPointerSetMin(&entry->curItem);
336  entry->offset = InvalidOffsetNumber;
337  if (entry->list)
338  pfree(entry->list);
339  entry->list = NULL;
340  entry->nlist = 0;
341  entry->matchBitmap = NULL;
342  entry->matchResult = NULL;
343  entry->reduceResult = false;
344  entry->predictNumberResult = 0;
345 
346  /*
347  * we should find entry, and begin scan of posting tree or just store
348  * posting list in memory
349  */
350  ginPrepareEntryScan(&btreeEntry, entry->attnum,
351  entry->queryKey, entry->queryCategory,
352  ginstate);
353  stackEntry = ginFindLeafPage(&btreeEntry, true, snapshot);
354  page = BufferGetPage(stackEntry->buffer);
355 
356  /* ginFindLeafPage() will have already checked snapshot age. */
357  needUnlock = true;
358 
359  entry->isFinished = true;
360 
361  if (entry->isPartialMatch ||
363  {
364  /*
365  * btreeEntry.findItem locates the first item >= given search key.
366  * (For GIN_CAT_EMPTY_QUERY, it will find the leftmost index item
367  * because of the way the GIN_CAT_EMPTY_QUERY category code is
368  * assigned.) We scan forward from there and collect all TIDs needed
369  * for the entry type.
370  */
371  btreeEntry.findItem(&btreeEntry, stackEntry);
372  if (collectMatchBitmap(&btreeEntry, stackEntry, entry, snapshot)
373  == false)
374  {
375  /*
376  * GIN tree was seriously restructured, so we will cleanup all
377  * found data and rescan. See comments near 'return false' in
378  * collectMatchBitmap()
379  */
380  if (entry->matchBitmap)
381  {
382  if (entry->matchIterator)
384  entry->matchIterator = NULL;
385  tbm_free(entry->matchBitmap);
386  entry->matchBitmap = NULL;
387  }
388  LockBuffer(stackEntry->buffer, GIN_UNLOCK);
389  freeGinBtreeStack(stackEntry);
390  goto restartScanEntry;
391  }
392 
393  if (entry->matchBitmap && !tbm_is_empty(entry->matchBitmap))
394  {
396  entry->isFinished = false;
397  }
398  }
399  else if (btreeEntry.findItem(&btreeEntry, stackEntry))
400  {
401  IndexTuple itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stackEntry->off));
402 
403  /* Predicate lock visited entry leaf page */
404  GinPredicateLockPage(ginstate->index,
405  BufferGetBlockNumber(stackEntry->buffer), snapshot);
406 
407  if (GinIsPostingTree(itup))
408  {
409  BlockNumber rootPostingTree = GinGetPostingTree(itup);
410  GinBtreeStack *stack;
411  Page page;
412  ItemPointerData minItem;
413 
414  /*
415  * We should unlock entry page before touching posting tree to
416  * prevent deadlocks with vacuum processes. Because entry is never
417  * deleted from page and posting tree is never reduced to the
418  * posting list, we can unlock page after getting BlockNumber of
419  * root of posting tree.
420  */
421  LockBuffer(stackEntry->buffer, GIN_UNLOCK);
422  needUnlock = false;
423 
424  stack = ginScanBeginPostingTree(&entry->btree, ginstate->index,
425  rootPostingTree, snapshot);
426  entry->buffer = stack->buffer;
427 
428  /*
429  * Predicate lock visited posting tree page, following pages
430  * will be locked by moveRightIfItNeeded or entryLoadMoreItems
431  */
432  GinPredicateLockPage(ginstate->index, BufferGetBlockNumber(entry->buffer), snapshot);
433 
434  /*
435  * We keep buffer pinned because we need to prevent deletion of
436  * page during scan. See GIN's vacuum implementation. RefCount is
437  * increased to keep buffer pinned after freeGinBtreeStack() call.
438  */
439  IncrBufferRefCount(entry->buffer);
440 
441  page = BufferGetPage(entry->buffer);
442 
443  /*
444  * Load the first page into memory.
445  */
446  ItemPointerSetMin(&minItem);
447  entry->list = GinDataLeafPageGetItems(page, &entry->nlist, minItem);
448 
449  entry->predictNumberResult = stack->predictNumber * entry->nlist;
450 
451  LockBuffer(entry->buffer, GIN_UNLOCK);
452  freeGinBtreeStack(stack);
453  entry->isFinished = false;
454  }
455  else if (GinGetNPosting(itup) > 0)
456  {
457  entry->list = ginReadTuple(ginstate, entry->attnum, itup,
458  &entry->nlist);
459  entry->predictNumberResult = entry->nlist;
460 
461  entry->isFinished = false;
462  }
463  }
464 
465  if (needUnlock)
466  LockBuffer(stackEntry->buffer, GIN_UNLOCK);
467  freeGinBtreeStack(stackEntry);
468 }
469 
470 /*
471  * Comparison function for scan entry indexes. Sorts by predictNumberResult,
472  * least frequent items first.
473  */
474 static int
475 entryIndexByFrequencyCmp(const void *a1, const void *a2, void *arg)
476 {
477  const GinScanKey key = (const GinScanKey) arg;
478  int i1 = *(const int *) a1;
479  int i2 = *(const int *) a2;
480  uint32 n1 = key->scanEntry[i1]->predictNumberResult;
481  uint32 n2 = key->scanEntry[i2]->predictNumberResult;
482 
483  if (n1 < n2)
484  return -1;
485  else if (n1 == n2)
486  return 0;
487  else
488  return 1;
489 }
490 
491 static void
493 {
495  int i;
496  int j;
497  int *entryIndexes;
498 
499  ItemPointerSetMin(&key->curItem);
500  key->curItemMatches = false;
501  key->recheckCurItem = false;
502  key->isFinished = false;
503 
504  /*
505  * Divide the entries into two distinct sets: required and additional.
506  * Additional entries are not enough for a match alone, without any items
507  * from the required set, but are needed by the consistent function to
508  * decide if an item matches. When scanning, we can skip over items from
509  * additional entries that have no corresponding matches in any of the
510  * required entries. That speeds up queries like "frequent & rare"
511  * considerably, if the frequent term can be put in the additional set.
512  *
513  * There can be many legal ways to divide them entries into these two
514  * sets. A conservative division is to just put everything in the required
515  * set, but the more you can put in the additional set, the more you can
516  * skip during the scan. To maximize skipping, we try to put as many
517  * frequent items as possible into additional, and less frequent ones into
518  * required. To do that, sort the entries by frequency
519  * (predictNumberResult), and put entries into the required set in that
520  * order, until the consistent function says that none of the remaining
521  * entries can form a match, without any items from the required set. The
522  * rest go to the additional set.
523  */
524  if (key->nentries > 1)
525  {
527 
528  entryIndexes = (int *) palloc(sizeof(int) * key->nentries);
529  for (i = 0; i < key->nentries; i++)
530  entryIndexes[i] = i;
531  qsort_arg(entryIndexes, key->nentries, sizeof(int),
533 
534  for (i = 0; i < key->nentries - 1; i++)
535  {
536  /* Pass all entries <= i as false, and the rest as MAYBE */
537  for (j = 0; j <= i; j++)
538  key->entryRes[entryIndexes[j]] = GIN_FALSE;
539  for (j = i + 1; j < key->nentries; j++)
540  key->entryRes[entryIndexes[j]] = GIN_MAYBE;
541 
542  if (key->triConsistentFn(key) == GIN_FALSE)
543  break;
544  }
545  /* i is now the last required entry. */
546 
548 
549  key->nrequired = i + 1;
550  key->nadditional = key->nentries - key->nrequired;
551  key->requiredEntries = palloc(key->nrequired * sizeof(GinScanEntry));
552  key->additionalEntries = palloc(key->nadditional * sizeof(GinScanEntry));
553 
554  j = 0;
555  for (i = 0; i < key->nrequired; i++)
556  key->requiredEntries[i] = key->scanEntry[entryIndexes[j++]];
557  for (i = 0; i < key->nadditional; i++)
558  key->additionalEntries[i] = key->scanEntry[entryIndexes[j++]];
559 
560  /* clean up after consistentFn calls (also frees entryIndexes) */
562  }
563  else
564  {
566 
567  key->nrequired = 1;
568  key->nadditional = 0;
569  key->requiredEntries = palloc(1 * sizeof(GinScanEntry));
570  key->requiredEntries[0] = key->scanEntry[0];
571  }
572  MemoryContextSwitchTo(oldCtx);
573 }
574 
575 static void
577 {
578  GinScanOpaque so = (GinScanOpaque) scan->opaque;
579  GinState *ginstate = &so->ginstate;
580  uint32 i;
581 
582  for (i = 0; i < so->totalentries; i++)
583  startScanEntry(ginstate, so->entries[i], scan->xs_snapshot);
584 
585  if (GinFuzzySearchLimit > 0)
586  {
587  /*
588  * If all of keys more than threshold we will try to reduce result, we
589  * hope (and only hope, for intersection operation of array our
590  * supposition isn't true), that total result will not more than
591  * minimal predictNumberResult.
592  */
593  bool reduce = true;
594 
595  for (i = 0; i < so->totalentries; i++)
596  {
598  {
599  reduce = false;
600  break;
601  }
602  }
603  if (reduce)
604  {
605  for (i = 0; i < so->totalentries; i++)
606  {
608  so->entries[i]->reduceResult = true;
609  }
610  }
611  }
612 
613  /*
614  * Now that we have the estimates for the entry frequencies, finish
615  * initializing the scan keys.
616  */
617  for (i = 0; i < so->nkeys; i++)
618  startScanKey(ginstate, so, so->keys + i);
619 }
620 
621 /*
622  * Load the next batch of item pointers from a posting tree.
623  *
624  * Note that we copy the page into GinScanEntry->list array and unlock it, but
625  * keep it pinned to prevent interference with vacuum.
626  */
627 static void
629  ItemPointerData advancePast, Snapshot snapshot)
630 {
631  Page page;
632  int i;
633  bool stepright;
634 
635  if (!BufferIsValid(entry->buffer))
636  {
637  entry->isFinished = true;
638  return;
639  }
640 
641  /*
642  * We have two strategies for finding the correct page: step right from
643  * the current page, or descend the tree again from the root. If
644  * advancePast equals the current item, the next matching item should be
645  * on the next page, so we step right. Otherwise, descend from root.
646  */
647  if (ginCompareItemPointers(&entry->curItem, &advancePast) == 0)
648  {
649  stepright = true;
650  LockBuffer(entry->buffer, GIN_SHARE);
651  }
652  else
653  {
654  GinBtreeStack *stack;
655 
656  ReleaseBuffer(entry->buffer);
657 
658  /*
659  * Set the search key, and find the correct leaf page.
660  */
661  if (ItemPointerIsLossyPage(&advancePast))
662  {
663  ItemPointerSet(&entry->btree.itemptr,
664  GinItemPointerGetBlockNumber(&advancePast) + 1,
666  }
667  else
668  {
669  ItemPointerSet(&entry->btree.itemptr,
670  GinItemPointerGetBlockNumber(&advancePast),
672  }
673  entry->btree.fullScan = false;
674  stack = ginFindLeafPage(&entry->btree, true, snapshot);
675 
676  GinPredicateLockPage(ginstate->index, BufferGetBlockNumber(stack->buffer), snapshot);
677 
678  /* we don't need the stack, just the buffer. */
679  entry->buffer = stack->buffer;
680  IncrBufferRefCount(entry->buffer);
681  freeGinBtreeStack(stack);
682  stepright = false;
683  }
684 
685  elog(DEBUG2, "entryLoadMoreItems, %u/%u, skip: %d",
686  GinItemPointerGetBlockNumber(&advancePast),
687  GinItemPointerGetOffsetNumber(&advancePast),
688  !stepright);
689 
690  page = BufferGetPage(entry->buffer);
691  for (;;)
692  {
693  entry->offset = InvalidOffsetNumber;
694  if (entry->list)
695  {
696  pfree(entry->list);
697  entry->list = NULL;
698  entry->nlist = 0;
699  }
700 
701  if (stepright)
702  {
703  /*
704  * We've processed all the entries on this page. If it was the
705  * last page in the tree, we're done.
706  */
707  if (GinPageRightMost(page))
708  {
709  UnlockReleaseBuffer(entry->buffer);
710  entry->buffer = InvalidBuffer;
711  entry->isFinished = true;
712  return;
713  }
714 
715  /*
716  * Step to next page, following the right link. then find the
717  * first ItemPointer greater than advancePast.
718  */
719  entry->buffer = ginStepRight(entry->buffer,
720  ginstate->index,
721  GIN_SHARE);
722 
723  GinPredicateLockPage(ginstate->index, BufferGetBlockNumber(entry->buffer), snapshot);
724 
725 
726  page = BufferGetPage(entry->buffer);
727  }
728  stepright = true;
729 
730  if (GinPageGetOpaque(page)->flags & GIN_DELETED)
731  continue; /* page was deleted by concurrent vacuum */
732 
733  /*
734  * The first item > advancePast might not be on this page, but
735  * somewhere to the right, if the page was split, or a non-match from
736  * another key in the query allowed us to skip some items from this
737  * entry. Keep following the right-links until we re-find the correct
738  * page.
739  */
740  if (!GinPageRightMost(page) &&
741  ginCompareItemPointers(&advancePast, GinDataPageGetRightBound(page)) >= 0)
742  {
743  /*
744  * the item we're looking is > the right bound of the page, so it
745  * can't be on this page.
746  */
747  continue;
748  }
749 
750  entry->list = GinDataLeafPageGetItems(page, &entry->nlist, advancePast);
751 
752  for (i = 0; i < entry->nlist; i++)
753  {
754  if (ginCompareItemPointers(&advancePast, &entry->list[i]) < 0)
755  {
756  entry->offset = i;
757 
758  if (GinPageRightMost(page))
759  {
760  /* after processing the copied items, we're done. */
761  UnlockReleaseBuffer(entry->buffer);
762  entry->buffer = InvalidBuffer;
763  }
764  else
765  LockBuffer(entry->buffer, GIN_UNLOCK);
766  return;
767  }
768  }
769  }
770 }
771 
772 #define gin_rand() (((double) random()) / ((double) MAX_RANDOM_VALUE))
773 #define dropItem(e) ( gin_rand() > ((double)GinFuzzySearchLimit)/((double)((e)->predictNumberResult)) )
774 
775 /*
776  * Sets entry->curItem to next heap item pointer > advancePast, for one entry
777  * of one scan key, or sets entry->isFinished to true if there are no more.
778  *
779  * Item pointers are returned in ascending order.
780  *
781  * Note: this can return a "lossy page" item pointer, indicating that the
782  * entry potentially matches all items on that heap page. However, it is
783  * not allowed to return both a lossy page pointer and exact (regular)
784  * item pointers for the same page. (Doing so would break the key-combination
785  * logic in keyGetItem and scanGetItem; see comment in scanGetItem.) In the
786  * current implementation this is guaranteed by the behavior of tidbitmaps.
787  */
788 static void
790  ItemPointerData advancePast, Snapshot snapshot)
791 {
792  Assert(!entry->isFinished);
793 
794  Assert(!ItemPointerIsValid(&entry->curItem) ||
795  ginCompareItemPointers(&entry->curItem, &advancePast) <= 0);
796 
797  if (entry->matchBitmap)
798  {
799  /* A bitmap result */
800  BlockNumber advancePastBlk = GinItemPointerGetBlockNumber(&advancePast);
801  OffsetNumber advancePastOff = GinItemPointerGetOffsetNumber(&advancePast);
802  bool gotitem = false;
803 
804  do
805  {
806  /*
807  * If we've exhausted all items on this block, move to next block
808  * in the bitmap.
809  */
810  while (entry->matchResult == NULL ||
811  (entry->matchResult->ntuples >= 0 &&
812  entry->offset >= entry->matchResult->ntuples) ||
813  entry->matchResult->blockno < advancePastBlk ||
814  (ItemPointerIsLossyPage(&advancePast) &&
815  entry->matchResult->blockno == advancePastBlk))
816  {
817  entry->matchResult = tbm_iterate(entry->matchIterator);
818 
819  if (entry->matchResult == NULL)
820  {
823  entry->matchIterator = NULL;
824  entry->isFinished = true;
825  break;
826  }
827 
828  /*
829  * Reset counter to the beginning of entry->matchResult. Note:
830  * entry->offset is still greater than matchResult->ntuples if
831  * matchResult is lossy. So, on next call we will get next
832  * result from TIDBitmap.
833  */
834  entry->offset = 0;
835  }
836  if (entry->isFinished)
837  break;
838 
839  /*
840  * We're now on the first page after advancePast which has any
841  * items on it. If it's a lossy result, return that.
842  */
843  if (entry->matchResult->ntuples < 0)
844  {
846  entry->matchResult->blockno);
847 
848  /*
849  * We might as well fall out of the loop; we could not
850  * estimate number of results on this page to support correct
851  * reducing of result even if it's enabled.
852  */
853  gotitem = true;
854  break;
855  }
856 
857  /*
858  * Not a lossy page. Skip over any offsets <= advancePast, and
859  * return that.
860  */
861  if (entry->matchResult->blockno == advancePastBlk)
862  {
863  /*
864  * First, do a quick check against the last offset on the
865  * page. If that's > advancePast, so are all the other
866  * offsets.
867  */
868  if (entry->matchResult->offsets[entry->matchResult->ntuples - 1] <= advancePastOff)
869  {
870  entry->offset = entry->matchResult->ntuples;
871  continue;
872  }
873 
874  /* Otherwise scan to find the first item > advancePast */
875  while (entry->matchResult->offsets[entry->offset] <= advancePastOff)
876  entry->offset++;
877  }
878 
879  ItemPointerSet(&entry->curItem,
880  entry->matchResult->blockno,
881  entry->matchResult->offsets[entry->offset]);
882  entry->offset++;
883  gotitem = true;
884  } while (!gotitem || (entry->reduceResult == true && dropItem(entry)));
885  }
886  else if (!BufferIsValid(entry->buffer))
887  {
888  /*
889  * A posting list from an entry tuple, or the last page of a posting
890  * tree.
891  */
892  do
893  {
894  if (entry->offset >= entry->nlist)
895  {
897  entry->isFinished = true;
898  break;
899  }
900 
901  entry->curItem = entry->list[entry->offset++];
902  } while (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0);
903  /* XXX: shouldn't we apply the fuzzy search limit here? */
904  }
905  else
906  {
907  /* A posting tree */
908  do
909  {
910  /* If we've processed the current batch, load more items */
911  while (entry->offset >= entry->nlist)
912  {
913  entryLoadMoreItems(ginstate, entry, advancePast, snapshot);
914 
915  if (entry->isFinished)
916  {
918  return;
919  }
920  }
921 
922  entry->curItem = entry->list[entry->offset++];
923 
924  } while (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0 ||
925  (entry->reduceResult == true && dropItem(entry)));
926  }
927 }
928 
929 /*
930  * Identify the "current" item among the input entry streams for this scan key
931  * that is greater than advancePast, and test whether it passes the scan key
932  * qual condition.
933  *
934  * The current item is the smallest curItem among the inputs. key->curItem
935  * is set to that value. key->curItemMatches is set to indicate whether that
936  * TID passes the consistentFn test. If so, key->recheckCurItem is set true
937  * iff recheck is needed for this item pointer (including the case where the
938  * item pointer is a lossy page pointer).
939  *
940  * If all entry streams are exhausted, sets key->isFinished to true.
941  *
942  * Item pointers must be returned in ascending order.
943  *
944  * Note: this can return a "lossy page" item pointer, indicating that the
945  * key potentially matches all items on that heap page. However, it is
946  * not allowed to return both a lossy page pointer and exact (regular)
947  * item pointers for the same page. (Doing so would break the key-combination
948  * logic in scanGetItem.)
949  */
950 static void
951 keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key,
952  ItemPointerData advancePast, Snapshot snapshot)
953 {
954  ItemPointerData minItem;
955  ItemPointerData curPageLossy;
956  uint32 i;
957  bool haveLossyEntry;
958  GinScanEntry entry;
959  GinTernaryValue res;
960  MemoryContext oldCtx;
961  bool allFinished;
962 
963  Assert(!key->isFinished);
964 
965  /*
966  * We might have already tested this item; if so, no need to repeat work.
967  * (Note: the ">" case can happen, if advancePast is exact but we
968  * previously had to set curItem to a lossy-page pointer.)
969  */
970  if (ginCompareItemPointers(&key->curItem, &advancePast) > 0)
971  return;
972 
973  /*
974  * Find the minimum item > advancePast among the active entry streams.
975  *
976  * Note: a lossy-page entry is encoded by a ItemPointer with max value for
977  * offset (0xffff), so that it will sort after any exact entries for the
978  * same page. So we'll prefer to return exact pointers not lossy
979  * pointers, which is good.
980  */
981  ItemPointerSetMax(&minItem);
982  allFinished = true;
983  for (i = 0; i < key->nrequired; i++)
984  {
985  entry = key->requiredEntries[i];
986 
987  if (entry->isFinished)
988  continue;
989 
990  /*
991  * Advance this stream if necessary.
992  *
993  * In particular, since entry->curItem was initialized with
994  * ItemPointerSetMin, this ensures we fetch the first item for each
995  * entry on the first call.
996  */
997  if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
998  {
999  entryGetItem(ginstate, entry, advancePast, snapshot);
1000  if (entry->isFinished)
1001  continue;
1002  }
1003 
1004  allFinished = false;
1005  if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
1006  minItem = entry->curItem;
1007  }
1008 
1009  if (allFinished)
1010  {
1011  /* all entries are finished */
1012  key->isFinished = true;
1013  return;
1014  }
1015 
1016  /*
1017  * Ok, we now know that there are no matches < minItem.
1018  *
1019  * If minItem is lossy, it means that there were no exact items on the
1020  * page among requiredEntries, because lossy pointers sort after exact
1021  * items. However, there might be exact items for the same page among
1022  * additionalEntries, so we mustn't advance past them.
1023  */
1024  if (ItemPointerIsLossyPage(&minItem))
1025  {
1026  if (GinItemPointerGetBlockNumber(&advancePast) <
1027  GinItemPointerGetBlockNumber(&minItem))
1028  {
1029  ItemPointerSet(&advancePast,
1030  GinItemPointerGetBlockNumber(&minItem),
1032  }
1033  }
1034  else
1035  {
1036  Assert(GinItemPointerGetOffsetNumber(&minItem) > 0);
1037  ItemPointerSet(&advancePast,
1038  GinItemPointerGetBlockNumber(&minItem),
1040  }
1041 
1042  /*
1043  * We might not have loaded all the entry streams for this TID yet. We
1044  * could call the consistent function, passing MAYBE for those entries, to
1045  * see if it can decide if this TID matches based on the information we
1046  * have. But if the consistent-function is expensive, and cannot in fact
1047  * decide with partial information, that could be a big loss. So, load all
1048  * the additional entries, before calling the consistent function.
1049  */
1050  for (i = 0; i < key->nadditional; i++)
1051  {
1052  entry = key->additionalEntries[i];
1053 
1054  if (entry->isFinished)
1055  continue;
1056 
1057  if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
1058  {
1059  entryGetItem(ginstate, entry, advancePast, snapshot);
1060  if (entry->isFinished)
1061  continue;
1062  }
1063 
1064  /*
1065  * Normally, none of the items in additionalEntries can have a curItem
1066  * larger than minItem. But if minItem is a lossy page, then there
1067  * might be exact items on the same page among additionalEntries.
1068  */
1069  if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
1070  {
1071  Assert(ItemPointerIsLossyPage(&minItem));
1072  minItem = entry->curItem;
1073  }
1074  }
1075 
1076  /*
1077  * Ok, we've advanced all the entries up to minItem now. Set key->curItem,
1078  * and perform consistentFn test.
1079  *
1080  * Lossy-page entries pose a problem, since we don't know the correct
1081  * entryRes state to pass to the consistentFn, and we also don't know what
1082  * its combining logic will be (could be AND, OR, or even NOT). If the
1083  * logic is OR then the consistentFn might succeed for all items in the
1084  * lossy page even when none of the other entries match.
1085  *
1086  * Our strategy is to call the tri-state consistent function, with the
1087  * lossy-page entries set to MAYBE, and all the other entries false. If it
1088  * returns false, none of the lossy items alone are enough for a match, so
1089  * we don't need to return a lossy-page pointer. Otherwise, return a
1090  * lossy-page pointer to indicate that the whole heap page must be
1091  * checked. (On subsequent calls, we'll do nothing until minItem is past
1092  * the page altogether, thus ensuring that we never return both regular
1093  * and lossy pointers for the same page.)
1094  *
1095  * An exception is that it doesn't matter what we pass for lossy pointers
1096  * in "hidden" entries, because the consistentFn's result can't depend on
1097  * them. We could pass them as MAYBE as well, but if we're using the
1098  * "shim" implementation of a tri-state consistent function (see
1099  * ginlogic.c), it's better to pass as few MAYBEs as possible. So pass
1100  * them as true.
1101  *
1102  * Note that only lossy-page entries pointing to the current item's page
1103  * should trigger this processing; we might have future lossy pages in the
1104  * entry array, but they aren't relevant yet.
1105  */
1106  key->curItem = minItem;
1107  ItemPointerSetLossyPage(&curPageLossy,
1109  haveLossyEntry = false;
1110  for (i = 0; i < key->nentries; i++)
1111  {
1112  entry = key->scanEntry[i];
1113  if (entry->isFinished == false &&
1114  ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0)
1115  {
1116  if (i < key->nuserentries)
1117  key->entryRes[i] = GIN_MAYBE;
1118  else
1119  key->entryRes[i] = GIN_TRUE;
1120  haveLossyEntry = true;
1121  }
1122  else
1123  key->entryRes[i] = GIN_FALSE;
1124  }
1125 
1126  /* prepare for calling consistentFn in temp context */
1127  oldCtx = MemoryContextSwitchTo(tempCtx);
1128 
1129  if (haveLossyEntry)
1130  {
1131  /* Have lossy-page entries, so see if whole page matches */
1132  res = key->triConsistentFn(key);
1133 
1134  if (res == GIN_TRUE || res == GIN_MAYBE)
1135  {
1136  /* Yes, so clean up ... */
1137  MemoryContextSwitchTo(oldCtx);
1138  MemoryContextReset(tempCtx);
1139 
1140  /* and return lossy pointer for whole page */
1141  key->curItem = curPageLossy;
1142  key->curItemMatches = true;
1143  key->recheckCurItem = true;
1144  return;
1145  }
1146  }
1147 
1148  /*
1149  * At this point we know that we don't need to return a lossy whole-page
1150  * pointer, but we might have matches for individual exact item pointers,
1151  * possibly in combination with a lossy pointer. Pass lossy pointers as
1152  * MAYBE to the ternary consistent function, to let it decide if this
1153  * tuple satisfies the overall key, even though we don't know if the lossy
1154  * entries match.
1155  *
1156  * Prepare entryRes array to be passed to consistentFn.
1157  */
1158  for (i = 0; i < key->nentries; i++)
1159  {
1160  entry = key->scanEntry[i];
1161  if (entry->isFinished)
1162  key->entryRes[i] = GIN_FALSE;
1163 #if 0
1164 
1165  /*
1166  * This case can't currently happen, because we loaded all the entries
1167  * for this item earlier.
1168  */
1169  else if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
1170  key->entryRes[i] = GIN_MAYBE;
1171 #endif
1172  else if (ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0)
1173  key->entryRes[i] = GIN_MAYBE;
1174  else if (ginCompareItemPointers(&entry->curItem, &minItem) == 0)
1175  key->entryRes[i] = GIN_TRUE;
1176  else
1177  key->entryRes[i] = GIN_FALSE;
1178  }
1179 
1180  res = key->triConsistentFn(key);
1181 
1182  switch (res)
1183  {
1184  case GIN_TRUE:
1185  key->curItemMatches = true;
1186  /* triConsistentFn set recheckCurItem */
1187  break;
1188 
1189  case GIN_FALSE:
1190  key->curItemMatches = false;
1191  break;
1192 
1193  case GIN_MAYBE:
1194  key->curItemMatches = true;
1195  key->recheckCurItem = true;
1196  break;
1197 
1198  default:
1199 
1200  /*
1201  * the 'default' case shouldn't happen, but if the consistent
1202  * function returns something bogus, this is the safe result
1203  */
1204  key->curItemMatches = true;
1205  key->recheckCurItem = true;
1206  break;
1207  }
1208 
1209  /*
1210  * We have a tuple, and we know if it matches or not. If it's a non-match,
1211  * we could continue to find the next matching tuple, but let's break out
1212  * and give scanGetItem a chance to advance the other keys. They might be
1213  * able to skip past to a much higher TID, allowing us to save work.
1214  */
1215 
1216  /* clean up after consistentFn calls */
1217  MemoryContextSwitchTo(oldCtx);
1218  MemoryContextReset(tempCtx);
1219 }
1220 
1221 /*
1222  * Get next heap item pointer (after advancePast) from scan.
1223  * Returns true if anything found.
1224  * On success, *item and *recheck are set.
1225  *
1226  * Note: this is very nearly the same logic as in keyGetItem(), except
1227  * that we know the keys are to be combined with AND logic, whereas in
1228  * keyGetItem() the combination logic is known only to the consistentFn.
1229  */
1230 static bool
1232  ItemPointerData *item, bool *recheck)
1233 {
1234  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1235  uint32 i;
1236  bool match;
1237 
1238  /*----------
1239  * Advance the scan keys in lock-step, until we find an item that matches
1240  * all the keys. If any key reports isFinished, meaning its subset of the
1241  * entries is exhausted, we can stop. Otherwise, set *item to the next
1242  * matching item.
1243  *
1244  * This logic works only if a keyGetItem stream can never contain both
1245  * exact and lossy pointers for the same page. Else we could have a
1246  * case like
1247  *
1248  * stream 1 stream 2
1249  * ... ...
1250  * 42/6 42/7
1251  * 50/1 42/0xffff
1252  * ... ...
1253  *
1254  * We would conclude that 42/6 is not a match and advance stream 1,
1255  * thus never detecting the match to the lossy pointer in stream 2.
1256  * (keyGetItem has a similar problem versus entryGetItem.)
1257  *----------
1258  */
1259  do
1260  {
1261  ItemPointerSetMin(item);
1262  match = true;
1263  for (i = 0; i < so->nkeys && match; i++)
1264  {
1265  GinScanKey key = so->keys + i;
1266 
1267  /* Fetch the next item for this key that is > advancePast. */
1268  keyGetItem(&so->ginstate, so->tempCtx, key, advancePast,
1269  scan->xs_snapshot);
1270 
1271  if (key->isFinished)
1272  return false;
1273 
1274  /*
1275  * If it's not a match, we can immediately conclude that nothing
1276  * <= this item matches, without checking the rest of the keys.
1277  */
1278  if (!key->curItemMatches)
1279  {
1280  advancePast = key->curItem;
1281  match = false;
1282  break;
1283  }
1284 
1285  /*
1286  * It's a match. We can conclude that nothing < matches, so the
1287  * other key streams can skip to this item.
1288  *
1289  * Beware of lossy pointers, though; from a lossy pointer, we can
1290  * only conclude that nothing smaller than this *block* matches.
1291  */
1292  if (ItemPointerIsLossyPage(&key->curItem))
1293  {
1294  if (GinItemPointerGetBlockNumber(&advancePast) <
1296  {
1297  ItemPointerSet(&advancePast,
1300  }
1301  }
1302  else
1303  {
1305  ItemPointerSet(&advancePast,
1308  }
1309 
1310  /*
1311  * If this is the first key, remember this location as a potential
1312  * match, and proceed to check the rest of the keys.
1313  *
1314  * Otherwise, check if this is the same item that we checked the
1315  * previous keys for (or a lossy pointer for the same page). If
1316  * not, loop back to check the previous keys for this item (we
1317  * will check this key again too, but keyGetItem returns quickly
1318  * for that)
1319  */
1320  if (i == 0)
1321  {
1322  *item = key->curItem;
1323  }
1324  else
1325  {
1326  if (ItemPointerIsLossyPage(&key->curItem) ||
1327  ItemPointerIsLossyPage(item))
1328  {
1330  match = (GinItemPointerGetBlockNumber(&key->curItem) ==
1332  }
1333  else
1334  {
1335  Assert(ginCompareItemPointers(&key->curItem, item) >= 0);
1336  match = (ginCompareItemPointers(&key->curItem, item) == 0);
1337  }
1338  }
1339  }
1340  } while (!match);
1341 
1343 
1344  /*
1345  * Now *item contains the first ItemPointer after previous result that
1346  * satisfied all the keys for that exact TID, or a lossy reference to the
1347  * same page.
1348  *
1349  * We must return recheck = true if any of the keys are marked recheck.
1350  */
1351  *recheck = false;
1352  for (i = 0; i < so->nkeys; i++)
1353  {
1354  GinScanKey key = so->keys + i;
1355 
1356  if (key->recheckCurItem)
1357  {
1358  *recheck = true;
1359  break;
1360  }
1361  }
1362 
1363  return true;
1364 }
1365 
1366 
1367 /*
1368  * Functions for scanning the pending list
1369  */
1370 
1371 
1372 /*
1373  * Get ItemPointer of next heap row to be checked from pending list.
1374  * Returns false if there are no more. On pages with several heap rows
1375  * it returns each row separately, on page with part of heap row returns
1376  * per page data. pos->firstOffset and pos->lastOffset are set to identify
1377  * the range of pending-list tuples belonging to this heap row.
1378  *
1379  * The pendingBuffer is presumed pinned and share-locked on entry, and is
1380  * pinned and share-locked on success exit. On failure exit it's released.
1381  */
1382 static bool
1384 {
1385  OffsetNumber maxoff;
1386  Page page;
1387  IndexTuple itup;
1388 
1389  ItemPointerSetInvalid(&pos->item);
1390  for (;;)
1391  {
1392  page = BufferGetPage(pos->pendingBuffer);
1393  TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
1394 
1395  maxoff = PageGetMaxOffsetNumber(page);
1396  if (pos->firstOffset > maxoff)
1397  {
1398  BlockNumber blkno = GinPageGetOpaque(page)->rightlink;
1399 
1400  if (blkno == InvalidBlockNumber)
1401  {
1404 
1405  return false;
1406  }
1407  else
1408  {
1409  /*
1410  * Here we must prevent deletion of next page by insertcleanup
1411  * process, which may be trying to obtain exclusive lock on
1412  * current page. So, we lock next page before releasing the
1413  * current one
1414  */
1415  Buffer tmpbuf = ReadBuffer(scan->indexRelation, blkno);
1416 
1417  LockBuffer(tmpbuf, GIN_SHARE);
1419 
1420  pos->pendingBuffer = tmpbuf;
1422  }
1423  }
1424  else
1425  {
1426  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->firstOffset));
1427  pos->item = itup->t_tid;
1428  if (GinPageHasFullRow(page))
1429  {
1430  /*
1431  * find itempointer to the next row
1432  */
1433  for (pos->lastOffset = pos->firstOffset + 1; pos->lastOffset <= maxoff; pos->lastOffset++)
1434  {
1435  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->lastOffset));
1436  if (!ItemPointerEquals(&pos->item, &itup->t_tid))
1437  break;
1438  }
1439  }
1440  else
1441  {
1442  /*
1443  * All itempointers are the same on this page
1444  */
1445  pos->lastOffset = maxoff + 1;
1446  }
1447 
1448  /*
1449  * Now pos->firstOffset points to the first tuple of current heap
1450  * row, pos->lastOffset points to the first tuple of next heap row
1451  * (or to the end of page)
1452  */
1453  break;
1454  }
1455  }
1456 
1457  return true;
1458 }
1459 
1460 /*
1461  * Scan pending-list page from current tuple (off) up till the first of:
1462  * - match is found (then returns true)
1463  * - no later match is possible
1464  * - tuple's attribute number is not equal to entry's attrnum
1465  * - reach end of page
1466  *
1467  * datum[]/category[]/datumExtracted[] arrays are used to cache the results
1468  * of gintuple_get_key() on the current page.
1469  */
1470 static bool
1472  OffsetNumber off, OffsetNumber maxoff,
1473  GinScanEntry entry,
1474  Datum *datum, GinNullCategory *category,
1475  bool *datumExtracted)
1476 {
1477  IndexTuple itup;
1478  int32 cmp;
1479 
1480  /* Partial match to a null is not possible */
1481  if (entry->queryCategory != GIN_CAT_NORM_KEY)
1482  return false;
1483 
1484  while (off < maxoff)
1485  {
1486  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
1487 
1488  if (gintuple_get_attrnum(ginstate, itup) != entry->attnum)
1489  return false;
1490 
1491  if (datumExtracted[off - 1] == false)
1492  {
1493  datum[off - 1] = gintuple_get_key(ginstate, itup,
1494  &category[off - 1]);
1495  datumExtracted[off - 1] = true;
1496  }
1497 
1498  /* Once we hit nulls, no further match is possible */
1499  if (category[off - 1] != GIN_CAT_NORM_KEY)
1500  return false;
1501 
1502  /*----------
1503  * Check partial match.
1504  * case cmp == 0 => match
1505  * case cmp > 0 => not match and end scan (no later match possible)
1506  * case cmp < 0 => not match and continue scan
1507  *----------
1508  */
1509  cmp = DatumGetInt32(FunctionCall4Coll(&ginstate->comparePartialFn[entry->attnum - 1],
1510  ginstate->supportCollation[entry->attnum - 1],
1511  entry->queryKey,
1512  datum[off - 1],
1513  UInt16GetDatum(entry->strategy),
1514  PointerGetDatum(entry->extra_data)));
1515  if (cmp == 0)
1516  return true;
1517  else if (cmp > 0)
1518  return false;
1519 
1520  off++;
1521  }
1522 
1523  return false;
1524 }
1525 
1526 /*
1527  * Set up the entryRes array for each key by looking at
1528  * every entry for current heap row in pending list.
1529  *
1530  * Returns true if each scan key has at least one entryRes match.
1531  * This corresponds to the situations where the normal index search will
1532  * try to apply the key's consistentFn. (A tuple not meeting that requirement
1533  * cannot be returned by the normal search since no entry stream will
1534  * source its TID.)
1535  *
1536  * The pendingBuffer is presumed pinned and share-locked on entry.
1537  */
1538 static bool
1540 {
1541  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1542  OffsetNumber attrnum;
1543  Page page;
1544  IndexTuple itup;
1545  int i,
1546  j;
1547 
1548  /*
1549  * Reset all entryRes and hasMatchKey flags
1550  */
1551  for (i = 0; i < so->nkeys; i++)
1552  {
1553  GinScanKey key = so->keys + i;
1554 
1555  memset(key->entryRes, GIN_FALSE, key->nentries);
1556  }
1557  memset(pos->hasMatchKey, false, so->nkeys);
1558 
1559  /*
1560  * Outer loop iterates over multiple pending-list pages when a single heap
1561  * row has entries spanning those pages.
1562  */
1563  for (;;)
1564  {
1565  Datum datum[BLCKSZ / sizeof(IndexTupleData)];
1566  GinNullCategory category[BLCKSZ / sizeof(IndexTupleData)];
1567  bool datumExtracted[BLCKSZ / sizeof(IndexTupleData)];
1568 
1569  Assert(pos->lastOffset > pos->firstOffset);
1570  memset(datumExtracted + pos->firstOffset - 1, 0,
1571  sizeof(bool) * (pos->lastOffset - pos->firstOffset));
1572 
1573  page = BufferGetPage(pos->pendingBuffer);
1574  TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
1575 
1576  for (i = 0; i < so->nkeys; i++)
1577  {
1578  GinScanKey key = so->keys + i;
1579 
1580  for (j = 0; j < key->nentries; j++)
1581  {
1582  GinScanEntry entry = key->scanEntry[j];
1583  OffsetNumber StopLow = pos->firstOffset,
1584  StopHigh = pos->lastOffset,
1585  StopMiddle;
1586 
1587  /* If already matched on earlier page, do no extra work */
1588  if (key->entryRes[j])
1589  continue;
1590 
1591  /*
1592  * Interesting tuples are from pos->firstOffset to
1593  * pos->lastOffset and they are ordered by (attnum, Datum) as
1594  * it's done in entry tree. So we can use binary search to
1595  * avoid linear scanning.
1596  */
1597  while (StopLow < StopHigh)
1598  {
1599  int res;
1600 
1601  StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
1602 
1603  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, StopMiddle));
1604 
1605  attrnum = gintuple_get_attrnum(&so->ginstate, itup);
1606 
1607  if (key->attnum < attrnum)
1608  {
1609  StopHigh = StopMiddle;
1610  continue;
1611  }
1612  if (key->attnum > attrnum)
1613  {
1614  StopLow = StopMiddle + 1;
1615  continue;
1616  }
1617 
1618  if (datumExtracted[StopMiddle - 1] == false)
1619  {
1620  datum[StopMiddle - 1] =
1621  gintuple_get_key(&so->ginstate, itup,
1622  &category[StopMiddle - 1]);
1623  datumExtracted[StopMiddle - 1] = true;
1624  }
1625 
1626  if (entry->queryCategory == GIN_CAT_EMPTY_QUERY)
1627  {
1628  /* special behavior depending on searchMode */
1629  if (entry->searchMode == GIN_SEARCH_MODE_ALL)
1630  {
1631  /* match anything except NULL_ITEM */
1632  if (category[StopMiddle - 1] == GIN_CAT_NULL_ITEM)
1633  res = -1;
1634  else
1635  res = 0;
1636  }
1637  else
1638  {
1639  /* match everything */
1640  res = 0;
1641  }
1642  }
1643  else
1644  {
1645  res = ginCompareEntries(&so->ginstate,
1646  entry->attnum,
1647  entry->queryKey,
1648  entry->queryCategory,
1649  datum[StopMiddle - 1],
1650  category[StopMiddle - 1]);
1651  }
1652 
1653  if (res == 0)
1654  {
1655  /*
1656  * Found exact match (there can be only one, except in
1657  * EMPTY_QUERY mode).
1658  *
1659  * If doing partial match, scan forward from here to
1660  * end of page to check for matches.
1661  *
1662  * See comment above about tuple's ordering.
1663  */
1664  if (entry->isPartialMatch)
1665  key->entryRes[j] =
1667  page,
1668  StopMiddle,
1669  pos->lastOffset,
1670  entry,
1671  datum,
1672  category,
1673  datumExtracted);
1674  else
1675  key->entryRes[j] = true;
1676 
1677  /* done with binary search */
1678  break;
1679  }
1680  else if (res < 0)
1681  StopHigh = StopMiddle;
1682  else
1683  StopLow = StopMiddle + 1;
1684  }
1685 
1686  if (StopLow >= StopHigh && entry->isPartialMatch)
1687  {
1688  /*
1689  * No exact match on this page. If doing partial match,
1690  * scan from the first tuple greater than target value to
1691  * end of page. Note that since we don't remember whether
1692  * the comparePartialFn told us to stop early on a
1693  * previous page, we will uselessly apply comparePartialFn
1694  * to the first tuple on each subsequent page.
1695  */
1696  key->entryRes[j] =
1698  page,
1699  StopHigh,
1700  pos->lastOffset,
1701  entry,
1702  datum,
1703  category,
1704  datumExtracted);
1705  }
1706 
1707  pos->hasMatchKey[i] |= key->entryRes[j];
1708  }
1709  }
1710 
1711  /* Advance firstOffset over the scanned tuples */
1712  pos->firstOffset = pos->lastOffset;
1713 
1714  if (GinPageHasFullRow(page))
1715  {
1716  /*
1717  * We have examined all pending entries for the current heap row.
1718  * Break out of loop over pages.
1719  */
1720  break;
1721  }
1722  else
1723  {
1724  /*
1725  * Advance to next page of pending entries for the current heap
1726  * row. Complain if there isn't one.
1727  */
1728  ItemPointerData item = pos->item;
1729 
1730  if (scanGetCandidate(scan, pos) == false ||
1731  !ItemPointerEquals(&pos->item, &item))
1732  elog(ERROR, "could not find additional pending pages for same heap tuple");
1733  }
1734  }
1735 
1736  /*
1737  * Now return "true" if all scan keys have at least one matching datum
1738  */
1739  for (i = 0; i < so->nkeys; i++)
1740  {
1741  if (pos->hasMatchKey[i] == false)
1742  return false;
1743  }
1744 
1745  return true;
1746 }
1747 
1748 /*
1749  * Collect all matched rows from pending list into bitmap. Also function
1750  * takes PendingLockRelation if it's needed.
1751  */
1752 static void
1753 scanPendingInsert(IndexScanDesc scan, TIDBitmap *tbm, int64 *ntids)
1754 {
1755  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1756  MemoryContext oldCtx;
1757  bool recheck,
1758  match;
1759  int i;
1760  pendingPosition pos;
1761  Buffer metabuffer = ReadBuffer(scan->indexRelation, GIN_METAPAGE_BLKNO);
1762  Page page;
1763  BlockNumber blkno;
1764 
1765  *ntids = 0;
1766 
1767  LockBuffer(metabuffer, GIN_SHARE);
1768  page = BufferGetPage(metabuffer);
1769  TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
1770  blkno = GinPageGetMeta(page)->head;
1771 
1772  /*
1773  * fetch head of list before unlocking metapage. head page must be pinned
1774  * to prevent deletion by vacuum process
1775  */
1776  if (blkno == InvalidBlockNumber)
1777  {
1778  /* No pending list, so proceed with normal scan */
1779  UnlockReleaseBuffer(metabuffer);
1780 
1781  /*
1782  * If fast update is enabled, we acquire a predicate lock on the entire
1783  * relation as fast update postpones the insertion of tuples into index
1784  * structure due to which we can't detect rw conflicts.
1785  */
1788 
1789  return;
1790  }
1791 
1792  /*
1793  * Pending list is not empty, we need to lock the index doesn't despite on
1794  * fastupdate state
1795  */
1797 
1798  pos.pendingBuffer = ReadBuffer(scan->indexRelation, blkno);
1799  LockBuffer(pos.pendingBuffer, GIN_SHARE);
1800  pos.firstOffset = FirstOffsetNumber;
1801  UnlockReleaseBuffer(metabuffer);
1802  pos.hasMatchKey = palloc(sizeof(bool) * so->nkeys);
1803 
1804  /*
1805  * loop for each heap row. scanGetCandidate returns full row or row's
1806  * tuples from first page.
1807  */
1808  while (scanGetCandidate(scan, &pos))
1809  {
1810  /*
1811  * Check entries in tuple and set up entryRes array.
1812  *
1813  * If pending tuples belonging to the current heap row are spread
1814  * across several pages, collectMatchesForHeapRow will read all of
1815  * those pages.
1816  */
1817  if (!collectMatchesForHeapRow(scan, &pos))
1818  continue;
1819 
1820  /*
1821  * Matching of entries of one row is finished, so check row using
1822  * consistent functions.
1823  */
1824  oldCtx = MemoryContextSwitchTo(so->tempCtx);
1825  recheck = false;
1826  match = true;
1827 
1828  for (i = 0; i < so->nkeys; i++)
1829  {
1830  GinScanKey key = so->keys + i;
1831 
1832  if (!key->boolConsistentFn(key))
1833  {
1834  match = false;
1835  break;
1836  }
1837  recheck |= key->recheckCurItem;
1838  }
1839 
1840  MemoryContextSwitchTo(oldCtx);
1842 
1843  if (match)
1844  {
1845  tbm_add_tuples(tbm, &pos.item, 1, recheck);
1846  (*ntids)++;
1847  }
1848  }
1849 
1850  pfree(pos.hasMatchKey);
1851 }
1852 
1853 
1854 #define GinIsVoidRes(s) ( ((GinScanOpaque) scan->opaque)->isVoidRes )
1855 
1856 int64
1858 {
1859  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1860  int64 ntids;
1861  ItemPointerData iptr;
1862  bool recheck;
1863 
1864  /*
1865  * Set up the scan keys, and check for unsatisfiable query.
1866  */
1867  ginFreeScanKeys(so); /* there should be no keys yet, but just to be
1868  * sure */
1869  ginNewScanKey(scan);
1870 
1871  if (GinIsVoidRes(scan))
1872  return 0;
1873 
1874  ntids = 0;
1875 
1876  /*
1877  * First, scan the pending list and collect any matching entries into the
1878  * bitmap. After we scan a pending item, some other backend could post it
1879  * into the main index, and so we might visit it a second time during the
1880  * main scan. This is okay because we'll just re-set the same bit in the
1881  * bitmap. (The possibility of duplicate visits is a major reason why GIN
1882  * can't support the amgettuple API, however.) Note that it would not do
1883  * to scan the main index before the pending list, since concurrent
1884  * cleanup could then make us miss entries entirely.
1885  */
1886  scanPendingInsert(scan, tbm, &ntids);
1887 
1888  /*
1889  * Now scan the main index.
1890  */
1891  startScan(scan);
1892 
1893  ItemPointerSetMin(&iptr);
1894 
1895  for (;;)
1896  {
1898 
1899  if (!scanGetItem(scan, iptr, &iptr, &recheck))
1900  break;
1901 
1902  if (ItemPointerIsLossyPage(&iptr))
1904  else
1905  tbm_add_tuples(tbm, &iptr, 1, recheck);
1906  ntids++;
1907  }
1908 
1909  return ntids;
1910 }
#define GinPageHasFullRow(page)
Definition: ginblock.h:118
static void startScanKey(GinState *ginstate, GinScanOpaque so, GinScanKey key)
Definition: ginget.c:492
#define ItemPointerIsValid(pointer)
Definition: itemptr.h:60
#define GIN_TRUE
Definition: gin.h:60
#define GIN_UNLOCK
Definition: gin_private.h:43
#define GIN_DELETED
Definition: ginblock.h:41
#define GIN_CAT_EMPTY_QUERY
Definition: ginblock.h:206
int64 gingetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
Definition: ginget.c:1857
GinBtreeData btree
Definition: gin_private.h:346
Oid supportCollation[INDEX_MAX_KEYS]
Definition: gin_private.h:82
ItemPointerData curItem
Definition: gin_private.h:331
void tbm_end_iterate(TBMIterator *iterator)
Definition: tidbitmap.c:1145
void PredicateLockPage(Relation relation, BlockNumber blkno, Snapshot snapshot)
Definition: predicate.c:2475
OffsetNumber offset
Definition: gin_private.h:341
static void TestForOldSnapshot(Snapshot snapshot, Relation relation, Page page)
Definition: bufmgr.h:265
GinState * ginstate
Definition: gin_private.h:164
uint32 predictNumberResult
Definition: gin_private.h:345
static void entryGetItem(GinState *ginstate, GinScanEntry entry, ItemPointerData advancePast, Snapshot snapshot)
Definition: ginget.c:789
Buffer pendingBuffer
Definition: ginget.c:30
Relation index
Definition: gin_private.h:53
#define DatumGetInt32(X)
Definition: postgres.h:455
#define dropItem(e)
Definition: ginget.c:773
#define GinItemPointerGetOffsetNumber(pointer)
Definition: ginblock.h:137
OffsetNumber off
Definition: gin_private.h:128
#define GIN_MAYBE
Definition: gin.h:61
#define PointerGetDatum(X)
Definition: postgres.h:539
static bool matchPartialInPendingList(GinState *ginstate, Page page, OffsetNumber off, OffsetNumber maxoff, GinScanEntry entry, Datum *datum, GinNullCategory *category, bool *datumExtracted)
Definition: ginget.c:1471
TIDBitmap * tbm_create(long maxbytes, dsa_area *dsa)
Definition: tidbitmap.c:265
#define TupleDescAttr(tupdesc, i)
Definition: tupdesc.h:93
void PredicateLockRelation(Relation relation, Snapshot snapshot)
Definition: predicate.c:2452
static void scanPendingInsert(IndexScanDesc scan, TIDBitmap *tbm, int64 *ntids)
Definition: ginget.c:1753
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:376
TBMIterator * matchIterator
Definition: gin_private.h:335
ItemPointerData t_tid
Definition: itup.h:37
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Snapshot xs_snapshot
Definition: relscan.h:92
#define InvalidBuffer
Definition: buf.h:25
static void GinPredicateLockPage(Relation index, BlockNumber blkno, Snapshot snapshot)
Definition: ginget.c:42
int ginCompareEntries(GinState *ginstate, OffsetNumber attnum, Datum a, GinNullCategory categorya, Datum b, GinNullCategory categoryb)
Definition: ginutil.c:393
Pointer extra_data
Definition: gin_private.h:322
#define ItemPointerIsLossyPage(p)
Definition: ginblock.h:169
#define GinGetNPosting(itup)
Definition: ginblock.h:222
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:136
Datum FunctionCall4Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2, Datum arg3, Datum arg4)
Definition: fmgr.c:1179
uint32 BlockNumber
Definition: block.h:31
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3309
#define GinPageGetOpaque(page)
Definition: ginblock.h:109
#define GIN_METAPAGE_BLKNO
Definition: ginblock.h:50
static void startScanEntry(GinState *ginstate, GinScanEntry entry, Snapshot snapshot)
Definition: ginget.c:326
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:353
ItemPointerData * list
Definition: gin_private.h:339
bool(* findItem)(GinBtree, GinBtreeStack *)
Definition: gin_private.h:151
signed int int32
Definition: c.h:313
int GinFuzzySearchLimit
Definition: ginget.c:26
Relation indexRelation
Definition: relscan.h:91
uint16 OffsetNumber
Definition: off.h:24
Definition: type.h:89
GinBtreeStack * ginFindLeafPage(GinBtree btree, bool searchMode, Snapshot snapshot)
Definition: ginbtree.c:77
BlockNumber blockno
Definition: tidbitmap.h:42
GinScanEntry * scanEntry
Definition: gin_private.h:270
#define GIN_SEARCH_MODE_ALL
Definition: gin.h:35
void pfree(void *pointer)
Definition: mcxt.c:1031
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3332
#define ERROR
Definition: elog.h:43
#define GinPageRightMost(page)
Definition: ginblock.h:128
signed char GinNullCategory
Definition: ginblock.h:200
#define ItemPointerSetLossyPage(p, b)
Definition: ginblock.h:167
struct GinScanKeyData * GinScanKey
Definition: gin_private.h:258
static void startScan(IndexScanDesc scan)
Definition: ginget.c:576
char GinTernaryValue
Definition: gin.h:57
OffsetNumber attnum
Definition: gin_private.h:325
#define DEBUG2
Definition: elog.h:24
OffsetNumber gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple)
Definition: ginutil.c:217
#define GIN_CAT_NORM_KEY
Definition: ginblock.h:202
GinScanOpaqueData * GinScanOpaque
Definition: gin_private.h:366
FmgrInfo comparePartialFn[INDEX_MAX_KEYS]
Definition: gin_private.h:78
void tbm_free(TIDBitmap *tbm)
Definition: tidbitmap.c:321
OffsetNumber offsets[FLEXIBLE_ARRAY_MEMBER]
Definition: tidbitmap.h:46
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
MemoryContext keyCtx
Definition: gin_private.h:361
GinBtreeStack * ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno, Snapshot snapshot)
Definition: gindatapage.c:1923
GinTernaryValue * entryRes
Definition: gin_private.h:286
static bool collectMatchesForHeapRow(IndexScanDesc scan, pendingPosition *pos)
Definition: ginget.c:1539
Buffer ginStepRight(Buffer buffer, Relation index, int lockmode)
Definition: ginbtree.c:166
static void scanPostingTree(Relation index, GinScanEntry scanEntry, BlockNumber rootPostingTree, Snapshot snapshot)
Definition: ginget.c:82
static void entryLoadMoreItems(GinState *ginstate, GinScanEntry entry, ItemPointerData advancePast, Snapshot snapshot)
Definition: ginget.c:628
FormData_pg_attribute * Form_pg_attribute
Definition: pg_attribute.h:197
unsigned int uint32
Definition: c.h:325
OffsetNumber firstOffset
Definition: ginget.c:31
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define GinPageIsLeaf(page)
Definition: ginblock.h:111
OffsetNumber attnum
Definition: gin_private.h:301
Datum gintuple_get_key(GinState *ginstate, IndexTuple tuple, GinNullCategory *category)
Definition: ginutil.c:250
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define ItemPointerIsMin(p)
Definition: ginblock.h:159
void ginPrepareEntryScan(GinBtree btree, OffsetNumber attnum, Datum key, GinNullCategory category, GinState *ginstate)
Definition: ginentrypage.c:745
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:128
#define ItemPointerSetMin(p)
Definition: ginblock.h:157
#define GIN_SHARE
Definition: gin_private.h:44
bool * hasMatchKey
Definition: ginget.c:34
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
Definition: qsort_arg.c:113
TIDBitmap * matchBitmap
Definition: gin_private.h:334
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
GinScanKey keys
Definition: gin_private.h:354
MemoryContext tempCtx
Definition: gin_private.h:351
static bool scanGetItem(IndexScanDesc scan, ItemPointerData advancePast, ItemPointerData *item, bool *recheck)
Definition: ginget.c:1231
bool(* boolConsistentFn)(GinScanKey key)
Definition: gin_private.h:287
GinScanEntry * requiredEntries
Definition: gin_private.h:280
static int entryIndexByFrequencyCmp(const void *a1, const void *a2, void *arg)
Definition: ginget.c:475
uintptr_t Datum
Definition: postgres.h:365
struct IndexTupleData IndexTupleData
StrategyNumber strategy
Definition: gin_private.h:323
bool tbm_is_empty(const TIDBitmap *tbm)
Definition: tidbitmap.c:669
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
#define GIN_CAT_NULL_ITEM
Definition: ginblock.h:205
int work_mem
Definition: globals.c:122
Relation index
Definition: gin_private.h:162
static void keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, ItemPointerData advancePast, Snapshot snapshot)
Definition: ginget.c:951
TBMIterateResult * matchResult
Definition: gin_private.h:336
#define InvalidOffsetNumber
Definition: off.h:26
int16 attnum
Definition: pg_attribute.h:79
static bool moveRightIfItNeeded(GinBtreeData *btree, GinBtreeStack *stack, Snapshot snapshot)
Definition: ginget.c:56
GinTernaryValue(* triConsistentFn)(GinScanKey key)
Definition: gin_private.h:288
void ginNewScanKey(IndexScanDesc scan)
Definition: ginscan.c:262
static FormData_pg_attribute a1
Definition: heap.c:147
TBMIterateResult * tbm_iterate(TBMIterator *iterator)
Definition: tidbitmap.c:970
#define Assert(condition)
Definition: c.h:699
GinNullCategory queryCategory
Definition: gin_private.h:320
#define GinIsVoidRes(s)
Definition: ginget.c:1854
WalTimeSample buffer[LAG_TRACKER_BUFFER_SIZE]
Definition: walsender.c:215
#define GIN_FALSE
Definition: gin.h:59
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:594
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
TBMIterator * tbm_begin_iterate(TIDBitmap *tbm)
Definition: tidbitmap.c:688
#define InvalidBlockNumber
Definition: block.h:33
#define OffsetNumberPrev(offsetNumber)
Definition: off.h:55
#define BufferIsValid(bufnum)
Definition: bufmgr.h:114
ItemPointer ginReadTuple(GinState *ginstate, OffsetNumber attnum, IndexTuple itup, int *nitems)
Definition: ginentrypage.c:163
BlockNumber blkno
Definition: gin_private.h:126
ItemPointerData curItem
Definition: gin_private.h:310
#define GinGetUseFastUpdate(relation)
Definition: gin_private.h:32
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
Definition: itemptr.c:29
#define GinGetPostingTree(itup)
Definition: ginblock.h:227
#define ItemPointerSetMax(p)
Definition: ginblock.h:162
#define DatumGetPointer(X)
Definition: postgres.h:532
static StringInfoData tmpbuf
Definition: walsender.c:163
static int ginCompareItemPointers(ItemPointer a, ItemPointer b)
Definition: gin_private.h:463
uint32 predictNumber
Definition: gin_private.h:131
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2605
void tbm_add_page(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:442
static bool collectMatchBitmap(GinBtreeData *btree, GinBtreeStack *stack, GinScanEntry scanEntry, Snapshot snapshot)
Definition: ginget.c:139
#define ItemPointerSetInvalid(pointer)
Definition: itemptr.h:150
int GinDataLeafPageGetItemsToTbm(Page page, TIDBitmap *tbm)
Definition: gindatapage.c:182
#define GinDataPageGetRightBound(page)
Definition: ginblock.h:282
GinScanEntry * entries
Definition: gin_private.h:357
#define GinIsPostingTree(itup)
Definition: ginblock.h:225
void * palloc(Size size)
Definition: mcxt.c:924
void freeGinBtreeStack(GinBtreeStack *stack)
Definition: ginbtree.c:194
ItemPointerData itemptr
Definition: gin_private.h:174
GinScanEntry * additionalEntries
Definition: gin_private.h:282
int i
void * arg
ItemPointer GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerData advancePast)
Definition: gindatapage.c:135
TupleDesc origTupdesc
Definition: gin_private.h:67
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:98
#define GinPageGetMeta(p)
Definition: ginblock.h:103
#define elog
Definition: elog.h:219
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:76
static bool scanGetCandidate(IndexScanDesc scan, pendingPosition *pos)
Definition: ginget.c:1383
ItemPointerData item
Definition: ginget.c:33
struct pendingPosition pendingPosition
#define GinItemPointerGetBlockNumber(pointer)
Definition: ginblock.h:134
int Buffer
Definition: buf.h:23
#define UInt16GetDatum(X)
Definition: postgres.h:448
void IncrBufferRefCount(Buffer buffer)
Definition: bufmgr.c:3347
OffsetNumber lastOffset
Definition: ginget.c:32
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
Pointer Page
Definition: bufpage.h:74
#define ItemPointerSet(pointer, blockNumber, offNum)
Definition: itemptr.h:105
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
static FormData_pg_attribute a2
Definition: heap.c:153
void ginFreeScanKeys(GinScanOpaque so)
Definition: ginscan.c:232