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