PostgreSQL Source Code  git master
ginget.c File Reference
#include "postgres.h"
#include "access/gin_private.h"
#include "access/relscan.h"
#include "common/pg_prng.h"
#include "miscadmin.h"
#include "storage/predicate.h"
#include "utils/datum.h"
#include "utils/memutils.h"
#include "utils/rel.h"
Include dependency graph for ginget.c:

Go to the source code of this file.

Data Structures

struct  pendingPosition
 

Macros

#define gin_rand()   pg_prng_double(&pg_global_prng_state)
 
#define dropItem(e)   ( gin_rand() > ((double)GinFuzzySearchLimit)/((double)((e)->predictNumberResult)) )
 
#define GinIsVoidRes(s)   ( ((GinScanOpaque) scan->opaque)->isVoidRes )
 

Typedefs

typedef struct pendingPosition pendingPosition
 

Functions

static bool moveRightIfItNeeded (GinBtreeData *btree, GinBtreeStack *stack, Snapshot snapshot)
 
static void scanPostingTree (Relation index, GinScanEntry scanEntry, BlockNumber rootPostingTree, Snapshot snapshot)
 
static bool collectMatchBitmap (GinBtreeData *btree, GinBtreeStack *stack, GinScanEntry scanEntry, Snapshot snapshot)
 
static void startScanEntry (GinState *ginstate, GinScanEntry entry, Snapshot snapshot)
 
static int entryIndexByFrequencyCmp (const void *a1, const void *a2, void *arg)
 
static void startScanKey (GinState *ginstate, GinScanOpaque so, GinScanKey key)
 
static void startScan (IndexScanDesc scan)
 
static void entryLoadMoreItems (GinState *ginstate, GinScanEntry entry, ItemPointerData advancePast, Snapshot snapshot)
 
static void entryGetItem (GinState *ginstate, GinScanEntry entry, ItemPointerData advancePast, Snapshot snapshot)
 
static void keyGetItem (GinState *ginstate, MemoryContext tempCtx, GinScanKey key, ItemPointerData advancePast, Snapshot snapshot)
 
static bool scanGetItem (IndexScanDesc scan, ItemPointerData advancePast, ItemPointerData *item, bool *recheck)
 
static bool scanGetCandidate (IndexScanDesc scan, pendingPosition *pos)
 
static bool matchPartialInPendingList (GinState *ginstate, Page page, OffsetNumber off, OffsetNumber maxoff, GinScanEntry entry, Datum *datum, GinNullCategory *category, bool *datumExtracted)
 
static bool collectMatchesForHeapRow (IndexScanDesc scan, pendingPosition *pos)
 
static void scanPendingInsert (IndexScanDesc scan, TIDBitmap *tbm, int64 *ntids)
 
int64 gingetbitmap (IndexScanDesc scan, TIDBitmap *tbm)
 

Variables

int GinFuzzySearchLimit = 0
 

Macro Definition Documentation

◆ dropItem

#define dropItem (   e)    ( gin_rand() > ((double)GinFuzzySearchLimit)/((double)((e)->predictNumberResult)) )

Definition at line 792 of file ginget.c.

◆ gin_rand

#define gin_rand ( )    pg_prng_double(&pg_global_prng_state)

Definition at line 791 of file ginget.c.

◆ GinIsVoidRes

#define GinIsVoidRes (   s)    ( ((GinScanOpaque) scan->opaque)->isVoidRes )

Definition at line 1915 of file ginget.c.

Typedef Documentation

◆ pendingPosition

Function Documentation

◆ collectMatchBitmap()

static bool collectMatchBitmap ( GinBtreeData btree,
GinBtreeStack stack,
GinScanEntry  scanEntry,
Snapshot  snapshot 
)
static

Definition at line 121 of file ginget.c.

123 {
125  Form_pg_attribute attr;
126 
127  /* Initialize empty bitmap result */
128  scanEntry->matchBitmap = tbm_create(work_mem * 1024L, NULL);
129 
130  /* Null query cannot partial-match anything */
131  if (scanEntry->isPartialMatch &&
132  scanEntry->queryCategory != GIN_CAT_NORM_KEY)
133  return true;
134 
135  /* Locate tupdesc entry for key column (for attbyval/attlen data) */
136  attnum = scanEntry->attnum;
137  attr = TupleDescAttr(btree->ginstate->origTupdesc, attnum - 1);
138 
139  /*
140  * Predicate lock entry leaf page, following pages will be locked by
141  * moveRightIfItNeeded()
142  */
143  PredicateLockPage(btree->index, stack->buffer, snapshot);
144 
145  for (;;)
146  {
147  Page page;
148  IndexTuple itup;
149  Datum idatum;
150  GinNullCategory icategory;
151 
152  /*
153  * stack->off points to the interested entry, buffer is already locked
154  */
155  if (moveRightIfItNeeded(btree, stack, snapshot) == false)
156  return true;
157 
158  page = BufferGetPage(stack->buffer);
159  TestForOldSnapshot(snapshot, btree->index, page);
160  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
161 
162  /*
163  * If tuple stores another attribute then stop scan
164  */
165  if (gintuple_get_attrnum(btree->ginstate, itup) != attnum)
166  return true;
167 
168  /* Safe to fetch attribute value */
169  idatum = gintuple_get_key(btree->ginstate, itup, &icategory);
170 
171  /*
172  * Check for appropriate scan stop conditions
173  */
174  if (scanEntry->isPartialMatch)
175  {
176  int32 cmp;
177 
178  /*
179  * In partial match, stop scan at any null (including
180  * placeholders); partial matches never match nulls
181  */
182  if (icategory != GIN_CAT_NORM_KEY)
183  return true;
184 
185  /*----------
186  * Check of partial match.
187  * case cmp == 0 => match
188  * case cmp > 0 => not match and finish scan
189  * case cmp < 0 => not match and continue scan
190  *----------
191  */
193  btree->ginstate->supportCollation[attnum - 1],
194  scanEntry->queryKey,
195  idatum,
196  UInt16GetDatum(scanEntry->strategy),
197  PointerGetDatum(scanEntry->extra_data)));
198 
199  if (cmp > 0)
200  return true;
201  else if (cmp < 0)
202  {
203  stack->off++;
204  continue;
205  }
206  }
207  else if (scanEntry->searchMode == GIN_SEARCH_MODE_ALL)
208  {
209  /*
210  * In ALL mode, we are not interested in null items, so we can
211  * stop if we get to a null-item placeholder (which will be the
212  * last entry for a given attnum). We do want to include NULL_KEY
213  * and EMPTY_ITEM entries, though.
214  */
215  if (icategory == GIN_CAT_NULL_ITEM)
216  return true;
217  }
218 
219  /*
220  * OK, we want to return the TIDs listed in this entry.
221  */
222  if (GinIsPostingTree(itup))
223  {
224  BlockNumber rootPostingTree = GinGetPostingTree(itup);
225 
226  /*
227  * We should unlock current page (but not unpin) during tree scan
228  * to prevent deadlock with vacuum processes.
229  *
230  * We save current entry value (idatum) to be able to re-find our
231  * tuple after re-locking
232  */
233  if (icategory == GIN_CAT_NORM_KEY)
234  idatum = datumCopy(idatum, attr->attbyval, attr->attlen);
235 
236  LockBuffer(stack->buffer, GIN_UNLOCK);
237 
238  /*
239  * Acquire predicate lock on the posting tree. We already hold a
240  * lock on the entry page, but insertions to the posting tree
241  * don't check for conflicts on that level.
242  */
243  PredicateLockPage(btree->index, rootPostingTree, snapshot);
244 
245  /* Collect all the TIDs in this entry's posting tree */
246  scanPostingTree(btree->index, scanEntry, rootPostingTree,
247  snapshot);
248 
249  /*
250  * We lock again the entry page and while it was unlocked insert
251  * might have occurred, so we need to re-find our position.
252  */
253  LockBuffer(stack->buffer, GIN_SHARE);
254  page = BufferGetPage(stack->buffer);
255  if (!GinPageIsLeaf(page))
256  {
257  /*
258  * Root page becomes non-leaf while we unlock it. We will
259  * start again, this situation doesn't occur often - root can
260  * became a non-leaf only once per life of index.
261  */
262  return false;
263  }
264 
265  /* Search forward to re-find idatum */
266  for (;;)
267  {
268  if (moveRightIfItNeeded(btree, stack, snapshot) == false)
269  ereport(ERROR,
270  (errcode(ERRCODE_INTERNAL_ERROR),
271  errmsg("failed to re-find tuple within index \"%s\"",
272  RelationGetRelationName(btree->index))));
273 
274  page = BufferGetPage(stack->buffer);
275  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
276 
277  if (gintuple_get_attrnum(btree->ginstate, itup) == attnum)
278  {
279  Datum newDatum;
280  GinNullCategory newCategory;
281 
282  newDatum = gintuple_get_key(btree->ginstate, itup,
283  &newCategory);
284 
285  if (ginCompareEntries(btree->ginstate, attnum,
286  newDatum, newCategory,
287  idatum, icategory) == 0)
288  break; /* Found! */
289  }
290 
291  stack->off++;
292  }
293 
294  if (icategory == GIN_CAT_NORM_KEY && !attr->attbyval)
295  pfree(DatumGetPointer(idatum));
296  }
297  else
298  {
299  ItemPointer ipd;
300  int nipd;
301 
302  ipd = ginReadTuple(btree->ginstate, scanEntry->attnum, itup, &nipd);
303  tbm_add_tuples(scanEntry->matchBitmap, ipd, nipd, false);
304  scanEntry->predictNumberResult += GinGetNPosting(itup);
305  pfree(ipd);
306  }
307 
308  /*
309  * Done with this entry, go to the next
310  */
311  stack->off++;
312  }
313 }
uint32 BlockNumber
Definition: block.h:31
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:4246
static Page BufferGetPage(Buffer buffer)
Definition: bufmgr.h:285
static void TestForOldSnapshot(Snapshot snapshot, Relation relation, Page page)
Definition: bufmgr.h:308
Pointer Page
Definition: bufpage.h:78
static Item PageGetItem(Page page, ItemId itemId)
Definition: bufpage.h:351
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition: bufpage.h:240
signed int int32
Definition: c.h:478
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
int errcode(int sqlerrcode)
Definition: elog.c:858
int errmsg(const char *fmt,...)
Definition: elog.c:1069
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:149
Datum FunctionCall4Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2, Datum arg3, Datum arg4)
Definition: fmgr.c:1168
#define GIN_SEARCH_MODE_ALL
Definition: gin.h:36
#define GIN_UNLOCK
Definition: gin_private.h:48
#define GIN_SHARE
Definition: gin_private.h:49
#define GinIsPostingTree(itup)
Definition: ginblock.h:231
#define GIN_CAT_NORM_KEY
Definition: ginblock.h:208
#define GinGetNPosting(itup)
Definition: ginblock.h:228
#define GinGetPostingTree(itup)
Definition: ginblock.h:233
signed char GinNullCategory
Definition: ginblock.h:206
#define GIN_CAT_NULL_ITEM
Definition: ginblock.h:211
#define GinPageIsLeaf(page)
Definition: ginblock.h:112
ItemPointer ginReadTuple(GinState *ginstate, OffsetNumber attnum, IndexTuple itup, int *nitems)
Definition: ginentrypage.c:163
static bool moveRightIfItNeeded(GinBtreeData *btree, GinBtreeStack *stack, Snapshot snapshot)
Definition: ginget.c:43
static void scanPostingTree(Relation index, GinScanEntry scanEntry, BlockNumber rootPostingTree, Snapshot snapshot)
Definition: ginget.c:69
OffsetNumber gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple)
Definition: ginutil.c:225
Datum gintuple_get_key(GinState *ginstate, IndexTuple tuple, GinNullCategory *category)
Definition: ginutil.c:258
int ginCompareEntries(GinState *ginstate, OffsetNumber attnum, Datum a, GinNullCategory categorya, Datum b, GinNullCategory categoryb)
Definition: ginutil.c:395
int work_mem
Definition: globals.c:125
IndexTupleData * IndexTuple
Definition: itup.h:53
void pfree(void *pointer)
Definition: mcxt.c:1436
uint16 OffsetNumber
Definition: off.h:24
int16 attnum
Definition: pg_attribute.h:74
FormData_pg_attribute * Form_pg_attribute
Definition: pg_attribute.h:209
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
uintptr_t Datum
Definition: postgres.h:64
static Datum UInt16GetDatum(uint16 X)
Definition: postgres.h:192
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:312
static int32 DatumGetInt32(Datum X)
Definition: postgres.h:202
void PredicateLockPage(Relation relation, BlockNumber blkno, Snapshot snapshot)
Definition: predicate.c:2533
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:747
#define RelationGetRelationName(relation)
Definition: rel.h:537
GinState * ginstate
Definition: gin_private.h:168
Relation index
Definition: gin_private.h:166
OffsetNumber off
Definition: gin_private.h:132
TIDBitmap * matchBitmap
Definition: gin_private.h:353
GinNullCategory queryCategory
Definition: gin_private.h:339
StrategyNumber strategy
Definition: gin_private.h:342
Pointer extra_data
Definition: gin_private.h:341
uint32 predictNumberResult
Definition: gin_private.h:364
OffsetNumber attnum
Definition: gin_private.h:344
FmgrInfo comparePartialFn[INDEX_MAX_KEYS]
Definition: gin_private.h:83
TupleDesc origTupdesc
Definition: gin_private.h:72
Oid supportCollation[INDEX_MAX_KEYS]
Definition: gin_private.h:87
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:376
TIDBitmap * tbm_create(long maxbytes, dsa_area *dsa)
Definition: tidbitmap.c:265
#define TupleDescAttr(tupdesc, i)
Definition: tupdesc.h:92

References GinScanEntryData::attnum, attnum, GinBtreeStack::buffer, BufferGetPage(), cmp(), GinState::comparePartialFn, datumCopy(), DatumGetInt32(), DatumGetPointer(), ereport, errcode(), errmsg(), ERROR, GinScanEntryData::extra_data, FunctionCall4Coll(), GIN_CAT_NORM_KEY, GIN_CAT_NULL_ITEM, GIN_SEARCH_MODE_ALL, GIN_SHARE, GIN_UNLOCK, ginCompareEntries(), GinGetNPosting, GinGetPostingTree, GinIsPostingTree, GinPageIsLeaf, ginReadTuple(), GinBtreeData::ginstate, gintuple_get_attrnum(), gintuple_get_key(), GinBtreeData::index, GinScanEntryData::isPartialMatch, LockBuffer(), GinScanEntryData::matchBitmap, moveRightIfItNeeded(), GinBtreeStack::off, GinState::origTupdesc, PageGetItem(), PageGetItemId(), pfree(), PointerGetDatum(), PredicateLockPage(), GinScanEntryData::predictNumberResult, GinScanEntryData::queryCategory, GinScanEntryData::queryKey, RelationGetRelationName, scanPostingTree(), GinScanEntryData::searchMode, GinScanEntryData::strategy, GinState::supportCollation, tbm_add_tuples(), tbm_create(), TestForOldSnapshot(), TupleDescAttr, UInt16GetDatum(), and work_mem.

Referenced by startScanEntry().

◆ collectMatchesForHeapRow()

static bool collectMatchesForHeapRow ( IndexScanDesc  scan,
pendingPosition pos 
)
static

Definition at line 1607 of file ginget.c.

1608 {
1609  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1610  OffsetNumber attrnum;
1611  Page page;
1612  IndexTuple itup;
1613  int i,
1614  j;
1615 
1616  /*
1617  * Reset all entryRes and hasMatchKey flags
1618  */
1619  for (i = 0; i < so->nkeys; i++)
1620  {
1621  GinScanKey key = so->keys + i;
1622 
1623  memset(key->entryRes, GIN_FALSE, key->nentries);
1624  }
1625  memset(pos->hasMatchKey, false, so->nkeys);
1626 
1627  /*
1628  * Outer loop iterates over multiple pending-list pages when a single heap
1629  * row has entries spanning those pages.
1630  */
1631  for (;;)
1632  {
1633  Datum datum[BLCKSZ / sizeof(IndexTupleData)];
1634  GinNullCategory category[BLCKSZ / sizeof(IndexTupleData)];
1635  bool datumExtracted[BLCKSZ / sizeof(IndexTupleData)];
1636 
1637  Assert(pos->lastOffset > pos->firstOffset);
1638  memset(datumExtracted + pos->firstOffset - 1, 0,
1639  sizeof(bool) * (pos->lastOffset - pos->firstOffset));
1640 
1641  page = BufferGetPage(pos->pendingBuffer);
1642  TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
1643 
1644  for (i = 0; i < so->nkeys; i++)
1645  {
1646  GinScanKey key = so->keys + i;
1647 
1648  for (j = 0; j < key->nentries; j++)
1649  {
1650  GinScanEntry entry = key->scanEntry[j];
1651  OffsetNumber StopLow = pos->firstOffset,
1652  StopHigh = pos->lastOffset,
1653  StopMiddle;
1654 
1655  /* If already matched on earlier page, do no extra work */
1656  if (key->entryRes[j])
1657  continue;
1658 
1659  /*
1660  * Interesting tuples are from pos->firstOffset to
1661  * pos->lastOffset and they are ordered by (attnum, Datum) as
1662  * it's done in entry tree. So we can use binary search to
1663  * avoid linear scanning.
1664  */
1665  while (StopLow < StopHigh)
1666  {
1667  int res;
1668 
1669  StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
1670 
1671  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, StopMiddle));
1672 
1673  attrnum = gintuple_get_attrnum(&so->ginstate, itup);
1674 
1675  if (key->attnum < attrnum)
1676  {
1677  StopHigh = StopMiddle;
1678  continue;
1679  }
1680  if (key->attnum > attrnum)
1681  {
1682  StopLow = StopMiddle + 1;
1683  continue;
1684  }
1685 
1686  if (datumExtracted[StopMiddle - 1] == false)
1687  {
1688  datum[StopMiddle - 1] =
1689  gintuple_get_key(&so->ginstate, itup,
1690  &category[StopMiddle - 1]);
1691  datumExtracted[StopMiddle - 1] = true;
1692  }
1693 
1694  if (entry->queryCategory == GIN_CAT_EMPTY_QUERY)
1695  {
1696  /* special behavior depending on searchMode */
1697  if (entry->searchMode == GIN_SEARCH_MODE_ALL)
1698  {
1699  /* match anything except NULL_ITEM */
1700  if (category[StopMiddle - 1] == GIN_CAT_NULL_ITEM)
1701  res = -1;
1702  else
1703  res = 0;
1704  }
1705  else
1706  {
1707  /* match everything */
1708  res = 0;
1709  }
1710  }
1711  else
1712  {
1714  entry->attnum,
1715  entry->queryKey,
1716  entry->queryCategory,
1717  datum[StopMiddle - 1],
1718  category[StopMiddle - 1]);
1719  }
1720 
1721  if (res == 0)
1722  {
1723  /*
1724  * Found exact match (there can be only one, except in
1725  * EMPTY_QUERY mode).
1726  *
1727  * If doing partial match, scan forward from here to
1728  * end of page to check for matches.
1729  *
1730  * See comment above about tuple's ordering.
1731  */
1732  if (entry->isPartialMatch)
1733  key->entryRes[j] =
1735  page,
1736  StopMiddle,
1737  pos->lastOffset,
1738  entry,
1739  datum,
1740  category,
1741  datumExtracted);
1742  else
1743  key->entryRes[j] = true;
1744 
1745  /* done with binary search */
1746  break;
1747  }
1748  else if (res < 0)
1749  StopHigh = StopMiddle;
1750  else
1751  StopLow = StopMiddle + 1;
1752  }
1753 
1754  if (StopLow >= StopHigh && entry->isPartialMatch)
1755  {
1756  /*
1757  * No exact match on this page. If doing partial match,
1758  * scan from the first tuple greater than target value to
1759  * end of page. Note that since we don't remember whether
1760  * the comparePartialFn told us to stop early on a
1761  * previous page, we will uselessly apply comparePartialFn
1762  * to the first tuple on each subsequent page.
1763  */
1764  key->entryRes[j] =
1766  page,
1767  StopHigh,
1768  pos->lastOffset,
1769  entry,
1770  datum,
1771  category,
1772  datumExtracted);
1773  }
1774 
1775  pos->hasMatchKey[i] |= key->entryRes[j];
1776  }
1777  }
1778 
1779  /* Advance firstOffset over the scanned tuples */
1780  pos->firstOffset = pos->lastOffset;
1781 
1782  if (GinPageHasFullRow(page))
1783  {
1784  /*
1785  * We have examined all pending entries for the current heap row.
1786  * Break out of loop over pages.
1787  */
1788  break;
1789  }
1790  else
1791  {
1792  /*
1793  * Advance to next page of pending entries for the current heap
1794  * row. Complain if there isn't one.
1795  */
1796  ItemPointerData item = pos->item;
1797 
1798  if (scanGetCandidate(scan, pos) == false ||
1799  !ItemPointerEquals(&pos->item, &item))
1800  elog(ERROR, "could not find additional pending pages for same heap tuple");
1801  }
1802  }
1803 
1804  /*
1805  * All scan keys except excludeOnly require at least one entry to match.
1806  * excludeOnly keys are an exception, because their implied
1807  * GIN_CAT_EMPTY_QUERY scanEntry always matches. So return "true" if all
1808  * non-excludeOnly scan keys have at least one match.
1809  */
1810  for (i = 0; i < so->nkeys; i++)
1811  {
1812  if (pos->hasMatchKey[i] == false && !so->keys[i].excludeOnly)
1813  return false;
1814  }
1815 
1816  return true;
1817 }
#define GIN_FALSE
Definition: gin.h:63
GinScanOpaqueData * GinScanOpaque
Definition: gin_private.h:385
#define GinPageHasFullRow(page)
Definition: ginblock.h:119
#define GIN_CAT_EMPTY_QUERY
Definition: ginblock.h:212
static bool matchPartialInPendingList(GinState *ginstate, Page page, OffsetNumber off, OffsetNumber maxoff, GinScanEntry entry, Datum *datum, GinNullCategory *category, bool *datumExtracted)
Definition: ginget.c:1539
static bool scanGetCandidate(IndexScanDesc scan, pendingPosition *pos)
Definition: ginget.c:1451
int j
Definition: isn.c:74
int i
Definition: isn.c:73
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
Definition: itemptr.c:35
struct IndexTupleData IndexTupleData
Assert(fmt[strlen(fmt) - 1] !='\n')
GinScanKey keys
Definition: gin_private.h:373
Relation indexRelation
Definition: relscan.h:118
struct SnapshotData * xs_snapshot
Definition: relscan.h:119
Buffer pendingBuffer
Definition: ginget.c:31
OffsetNumber lastOffset
Definition: ginget.c:33
OffsetNumber firstOffset
Definition: ginget.c:32
bool * hasMatchKey
Definition: ginget.c:35
ItemPointerData item
Definition: ginget.c:34

References Assert(), GinScanEntryData::attnum, BufferGetPage(), elog(), ERROR, GinScanKeyData::excludeOnly, pendingPosition::firstOffset, GIN_CAT_EMPTY_QUERY, GIN_CAT_NULL_ITEM, GIN_FALSE, GIN_SEARCH_MODE_ALL, ginCompareEntries(), GinPageHasFullRow, GinScanOpaqueData::ginstate, gintuple_get_attrnum(), gintuple_get_key(), pendingPosition::hasMatchKey, i, IndexScanDescData::indexRelation, GinScanEntryData::isPartialMatch, pendingPosition::item, ItemPointerEquals(), j, sort-test::key, GinScanOpaqueData::keys, pendingPosition::lastOffset, matchPartialInPendingList(), GinScanOpaqueData::nkeys, IndexScanDescData::opaque, PageGetItem(), PageGetItemId(), pendingPosition::pendingBuffer, GinScanEntryData::queryCategory, GinScanEntryData::queryKey, res, scanGetCandidate(), GinScanEntryData::searchMode, TestForOldSnapshot(), and IndexScanDescData::xs_snapshot.

Referenced by scanPendingInsert().

◆ entryGetItem()

static void entryGetItem ( GinState ginstate,
GinScanEntry  entry,
ItemPointerData  advancePast,
Snapshot  snapshot 
)
static

Definition at line 808 of file ginget.c.

810 {
811  Assert(!entry->isFinished);
812 
813  Assert(!ItemPointerIsValid(&entry->curItem) ||
814  ginCompareItemPointers(&entry->curItem, &advancePast) <= 0);
815 
816  if (entry->matchBitmap)
817  {
818  /* A bitmap result */
819  BlockNumber advancePastBlk = GinItemPointerGetBlockNumber(&advancePast);
820  OffsetNumber advancePastOff = GinItemPointerGetOffsetNumber(&advancePast);
821 
822  for (;;)
823  {
824  /*
825  * If we've exhausted all items on this block, move to next block
826  * in the bitmap.
827  */
828  while (entry->matchResult == NULL ||
829  (entry->matchResult->ntuples >= 0 &&
830  entry->offset >= entry->matchResult->ntuples) ||
831  entry->matchResult->blockno < advancePastBlk ||
832  (ItemPointerIsLossyPage(&advancePast) &&
833  entry->matchResult->blockno == advancePastBlk))
834  {
835  entry->matchResult = tbm_iterate(entry->matchIterator);
836 
837  if (entry->matchResult == NULL)
838  {
841  entry->matchIterator = NULL;
842  entry->isFinished = true;
843  break;
844  }
845 
846  /*
847  * Reset counter to the beginning of entry->matchResult. Note:
848  * entry->offset is still greater than matchResult->ntuples if
849  * matchResult is lossy. So, on next call we will get next
850  * result from TIDBitmap.
851  */
852  entry->offset = 0;
853  }
854  if (entry->isFinished)
855  break;
856 
857  /*
858  * We're now on the first page after advancePast which has any
859  * items on it. If it's a lossy result, return that.
860  */
861  if (entry->matchResult->ntuples < 0)
862  {
864  entry->matchResult->blockno);
865 
866  /*
867  * We might as well fall out of the loop; we could not
868  * estimate number of results on this page to support correct
869  * reducing of result even if it's enabled.
870  */
871  break;
872  }
873 
874  /*
875  * Not a lossy page. Skip over any offsets <= advancePast, and
876  * return that.
877  */
878  if (entry->matchResult->blockno == advancePastBlk)
879  {
880  /*
881  * First, do a quick check against the last offset on the
882  * page. If that's > advancePast, so are all the other
883  * offsets, so just go back to the top to get the next page.
884  */
885  if (entry->matchResult->offsets[entry->matchResult->ntuples - 1] <= advancePastOff)
886  {
887  entry->offset = entry->matchResult->ntuples;
888  continue;
889  }
890 
891  /* Otherwise scan to find the first item > advancePast */
892  while (entry->matchResult->offsets[entry->offset] <= advancePastOff)
893  entry->offset++;
894  }
895 
896  ItemPointerSet(&entry->curItem,
897  entry->matchResult->blockno,
898  entry->matchResult->offsets[entry->offset]);
899  entry->offset++;
900 
901  /* Done unless we need to reduce the result */
902  if (!entry->reduceResult || !dropItem(entry))
903  break;
904  }
905  }
906  else if (!BufferIsValid(entry->buffer))
907  {
908  /*
909  * A posting list from an entry tuple, or the last page of a posting
910  * tree.
911  */
912  for (;;)
913  {
914  if (entry->offset >= entry->nlist)
915  {
917  entry->isFinished = true;
918  break;
919  }
920 
921  entry->curItem = entry->list[entry->offset++];
922 
923  /* If we're not past advancePast, keep scanning */
924  if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
925  continue;
926 
927  /* Done unless we need to reduce the result */
928  if (!entry->reduceResult || !dropItem(entry))
929  break;
930  }
931  }
932  else
933  {
934  /* A posting tree */
935  for (;;)
936  {
937  /* If we've processed the current batch, load more items */
938  while (entry->offset >= entry->nlist)
939  {
940  entryLoadMoreItems(ginstate, entry, advancePast, snapshot);
941 
942  if (entry->isFinished)
943  {
945  return;
946  }
947  }
948 
949  entry->curItem = entry->list[entry->offset++];
950 
951  /* If we're not past advancePast, keep scanning */
952  if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
953  continue;
954 
955  /* Done unless we need to reduce the result */
956  if (!entry->reduceResult || !dropItem(entry))
957  break;
958 
959  /*
960  * Advance advancePast (so that entryLoadMoreItems will load the
961  * right data), and keep scanning
962  */
963  advancePast = entry->curItem;
964  }
965  }
966 }
static bool BufferIsValid(Buffer bufnum)
Definition: bufmgr.h:233
static int ginCompareItemPointers(ItemPointer a, ItemPointer b)
Definition: gin_private.h:487
#define ItemPointerSetLossyPage(p, b)
Definition: ginblock.h:173
#define GinItemPointerGetOffsetNumber(pointer)
Definition: ginblock.h:146
#define ItemPointerIsLossyPage(p)
Definition: ginblock.h:175
#define GinItemPointerGetBlockNumber(pointer)
Definition: ginblock.h:143
static void entryLoadMoreItems(GinState *ginstate, GinScanEntry entry, ItemPointerData advancePast, Snapshot snapshot)
Definition: ginget.c:653
#define dropItem(e)
Definition: ginget.c:792
static void ItemPointerSet(ItemPointerData *pointer, BlockNumber blockNumber, OffsetNumber offNum)
Definition: itemptr.h:135
static void ItemPointerSetInvalid(ItemPointerData *pointer)
Definition: itemptr.h:184
static bool ItemPointerIsValid(const ItemPointerData *pointer)
Definition: itemptr.h:83
ItemPointerData curItem
Definition: gin_private.h:350
TBMIterateResult * matchResult
Definition: gin_private.h:355
ItemPointerData * list
Definition: gin_private.h:358
TBMIterator * matchIterator
Definition: gin_private.h:354
OffsetNumber offset
Definition: gin_private.h:360
OffsetNumber offsets[FLEXIBLE_ARRAY_MEMBER]
Definition: tidbitmap.h:46
BlockNumber blockno
Definition: tidbitmap.h:42
void tbm_end_iterate(TBMIterator *iterator)
Definition: tidbitmap.c:1145
TBMIterateResult * tbm_iterate(TBMIterator *iterator)
Definition: tidbitmap.c:970

References Assert(), TBMIterateResult::blockno, GinScanEntryData::buffer, BufferIsValid(), GinScanEntryData::curItem, dropItem, entryLoadMoreItems(), ginCompareItemPointers(), GinItemPointerGetBlockNumber, GinItemPointerGetOffsetNumber, GinScanEntryData::isFinished, ItemPointerIsLossyPage, ItemPointerIsValid(), ItemPointerSet(), ItemPointerSetInvalid(), ItemPointerSetLossyPage, GinScanEntryData::list, GinScanEntryData::matchBitmap, GinScanEntryData::matchIterator, GinScanEntryData::matchResult, GinScanEntryData::nlist, TBMIterateResult::ntuples, GinScanEntryData::offset, TBMIterateResult::offsets, GinScanEntryData::reduceResult, tbm_end_iterate(), and tbm_iterate().

Referenced by keyGetItem().

◆ entryIndexByFrequencyCmp()

static int entryIndexByFrequencyCmp ( const void *  a1,
const void *  a2,
void *  arg 
)
static

Definition at line 488 of file ginget.c.

489 {
490  const GinScanKey key = (const GinScanKey) arg;
491  int i1 = *(const int *) a1;
492  int i2 = *(const int *) a2;
493  uint32 n1 = key->scanEntry[i1]->predictNumberResult;
494  uint32 n2 = key->scanEntry[i2]->predictNumberResult;
495 
496  if (n1 < n2)
497  return -1;
498  else if (n1 == n2)
499  return 0;
500  else
501  return 1;
502 }
unsigned int uint32
Definition: c.h:490
struct GinScanKeyData * GinScanKey
Definition: gin_private.h:263
static const FormData_pg_attribute a1
Definition: heap.c:141
static const FormData_pg_attribute a2
Definition: heap.c:155
void * arg

References a1, a2, arg, and sort-test::key.

Referenced by startScanKey().

◆ entryLoadMoreItems()

static void entryLoadMoreItems ( GinState ginstate,
GinScanEntry  entry,
ItemPointerData  advancePast,
Snapshot  snapshot 
)
static

Definition at line 653 of file ginget.c.

655 {
656  Page page;
657  int i;
658  bool stepright;
659 
660  if (!BufferIsValid(entry->buffer))
661  {
662  entry->isFinished = true;
663  return;
664  }
665 
666  /*
667  * We have two strategies for finding the correct page: step right from
668  * the current page, or descend the tree again from the root. If
669  * advancePast equals the current item, the next matching item should be
670  * on the next page, so we step right. Otherwise, descend from root.
671  */
672  if (ginCompareItemPointers(&entry->curItem, &advancePast) == 0)
673  {
674  stepright = true;
675  LockBuffer(entry->buffer, GIN_SHARE);
676  }
677  else
678  {
679  GinBtreeStack *stack;
680 
681  ReleaseBuffer(entry->buffer);
682 
683  /*
684  * Set the search key, and find the correct leaf page.
685  */
686  if (ItemPointerIsLossyPage(&advancePast))
687  {
688  ItemPointerSet(&entry->btree.itemptr,
689  GinItemPointerGetBlockNumber(&advancePast) + 1,
691  }
692  else
693  {
694  ItemPointerSet(&entry->btree.itemptr,
695  GinItemPointerGetBlockNumber(&advancePast),
697  }
698  entry->btree.fullScan = false;
699  stack = ginFindLeafPage(&entry->btree, true, false, snapshot);
700 
701  /* we don't need the stack, just the buffer. */
702  entry->buffer = stack->buffer;
703  IncrBufferRefCount(entry->buffer);
704  freeGinBtreeStack(stack);
705  stepright = false;
706  }
707 
708  elog(DEBUG2, "entryLoadMoreItems, %u/%u, skip: %d",
709  GinItemPointerGetBlockNumber(&advancePast),
710  GinItemPointerGetOffsetNumber(&advancePast),
711  !stepright);
712 
713  page = BufferGetPage(entry->buffer);
714  for (;;)
715  {
716  entry->offset = InvalidOffsetNumber;
717  if (entry->list)
718  {
719  pfree(entry->list);
720  entry->list = NULL;
721  entry->nlist = 0;
722  }
723 
724  if (stepright)
725  {
726  /*
727  * We've processed all the entries on this page. If it was the
728  * last page in the tree, we're done.
729  */
730  if (GinPageRightMost(page))
731  {
732  UnlockReleaseBuffer(entry->buffer);
733  entry->buffer = InvalidBuffer;
734  entry->isFinished = true;
735  return;
736  }
737 
738  /*
739  * Step to next page, following the right link. then find the
740  * first ItemPointer greater than advancePast.
741  */
742  entry->buffer = ginStepRight(entry->buffer,
743  ginstate->index,
744  GIN_SHARE);
745  page = BufferGetPage(entry->buffer);
746  }
747  stepright = true;
748 
749  if (GinPageGetOpaque(page)->flags & GIN_DELETED)
750  continue; /* page was deleted by concurrent vacuum */
751 
752  /*
753  * The first item > advancePast might not be on this page, but
754  * somewhere to the right, if the page was split, or a non-match from
755  * another key in the query allowed us to skip some items from this
756  * entry. Keep following the right-links until we re-find the correct
757  * page.
758  */
759  if (!GinPageRightMost(page) &&
760  ginCompareItemPointers(&advancePast, GinDataPageGetRightBound(page)) >= 0)
761  {
762  /*
763  * the item we're looking is > the right bound of the page, so it
764  * can't be on this page.
765  */
766  continue;
767  }
768 
769  entry->list = GinDataLeafPageGetItems(page, &entry->nlist, advancePast);
770 
771  for (i = 0; i < entry->nlist; i++)
772  {
773  if (ginCompareItemPointers(&advancePast, &entry->list[i]) < 0)
774  {
775  entry->offset = i;
776 
777  if (GinPageRightMost(page))
778  {
779  /* after processing the copied items, we're done. */
780  UnlockReleaseBuffer(entry->buffer);
781  entry->buffer = InvalidBuffer;
782  }
783  else
784  LockBuffer(entry->buffer, GIN_UNLOCK);
785  return;
786  }
787  }
788  }
789 }
#define InvalidBuffer
Definition: buf.h:25
void IncrBufferRefCount(Buffer buffer)
Definition: bufmgr.c:4043
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:4005
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:4028
#define DEBUG2
Definition: elog.h:29
#define GinPageGetOpaque(page)
Definition: ginblock.h:110
#define GIN_DELETED
Definition: ginblock.h:43
#define GinDataPageGetRightBound(page)
Definition: ginblock.h:288
#define GinPageRightMost(page)
Definition: ginblock.h:129
void freeGinBtreeStack(GinBtreeStack *stack)
Definition: ginbtree.c:194
GinBtreeStack * ginFindLeafPage(GinBtree btree, bool searchMode, bool rootConflictCheck, Snapshot snapshot)
Definition: ginbtree.c:80
Buffer ginStepRight(Buffer buffer, Relation index, int lockmode)
Definition: ginbtree.c:173
ItemPointer GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerData advancePast)
Definition: gindatapage.c:135
#define InvalidOffsetNumber
Definition: off.h:26
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
#define FirstOffsetNumber
Definition: off.h:27
ItemPointerData itemptr
Definition: gin_private.h:178
GinBtreeData btree
Definition: gin_private.h:365
Relation index
Definition: gin_private.h:58

References GinScanEntryData::btree, GinBtreeStack::buffer, GinScanEntryData::buffer, BufferGetPage(), BufferIsValid(), GinScanEntryData::curItem, DEBUG2, elog(), FirstOffsetNumber, freeGinBtreeStack(), GinBtreeData::fullScan, GIN_DELETED, GIN_SHARE, GIN_UNLOCK, ginCompareItemPointers(), GinDataLeafPageGetItems(), GinDataPageGetRightBound, ginFindLeafPage(), GinItemPointerGetBlockNumber, GinItemPointerGetOffsetNumber, GinPageGetOpaque, GinPageRightMost, ginStepRight(), i, IncrBufferRefCount(), GinState::index, InvalidBuffer, InvalidOffsetNumber, GinScanEntryData::isFinished, ItemPointerIsLossyPage, ItemPointerSet(), GinBtreeData::itemptr, GinScanEntryData::list, LockBuffer(), GinScanEntryData::nlist, GinScanEntryData::offset, OffsetNumberNext, pfree(), ReleaseBuffer(), and UnlockReleaseBuffer().

Referenced by entryGetItem().

◆ gingetbitmap()

int64 gingetbitmap ( IndexScanDesc  scan,
TIDBitmap tbm 
)

Definition at line 1918 of file ginget.c.

1919 {
1920  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1921  int64 ntids;
1922  ItemPointerData iptr;
1923  bool recheck;
1924 
1925  /*
1926  * Set up the scan keys, and check for unsatisfiable query.
1927  */
1928  ginFreeScanKeys(so); /* there should be no keys yet, but just to be
1929  * sure */
1930  ginNewScanKey(scan);
1931 
1932  if (GinIsVoidRes(scan))
1933  return 0;
1934 
1935  ntids = 0;
1936 
1937  /*
1938  * First, scan the pending list and collect any matching entries into the
1939  * bitmap. After we scan a pending item, some other backend could post it
1940  * into the main index, and so we might visit it a second time during the
1941  * main scan. This is okay because we'll just re-set the same bit in the
1942  * bitmap. (The possibility of duplicate visits is a major reason why GIN
1943  * can't support the amgettuple API, however.) Note that it would not do
1944  * to scan the main index before the pending list, since concurrent
1945  * cleanup could then make us miss entries entirely.
1946  */
1947  scanPendingInsert(scan, tbm, &ntids);
1948 
1949  /*
1950  * Now scan the main index.
1951  */
1952  startScan(scan);
1953 
1954  ItemPointerSetMin(&iptr);
1955 
1956  for (;;)
1957  {
1959 
1960  if (!scanGetItem(scan, iptr, &iptr, &recheck))
1961  break;
1962 
1963  if (ItemPointerIsLossyPage(&iptr))
1965  else
1966  tbm_add_tuples(tbm, &iptr, 1, recheck);
1967  ntids++;
1968  }
1969 
1970  return ntids;
1971 }
#define ItemPointerSetMin(p)
Definition: ginblock.h:166
static void scanPendingInsert(IndexScanDesc scan, TIDBitmap *tbm, int64 *ntids)
Definition: ginget.c:1823
static void startScan(IndexScanDesc scan)
Definition: ginget.c:601
#define GinIsVoidRes(s)
Definition: ginget.c:1915
static bool scanGetItem(IndexScanDesc scan, ItemPointerData advancePast, ItemPointerData *item, bool *recheck)
Definition: ginget.c:1285
void ginFreeScanKeys(GinScanOpaque so)
Definition: ginscan.c:233
void ginNewScanKey(IndexScanDesc scan)
Definition: ginscan.c:263
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition: itemptr.h:103
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:121
void tbm_add_page(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:442

References CHECK_FOR_INTERRUPTS, ginFreeScanKeys(), GinIsVoidRes, ginNewScanKey(), ItemPointerGetBlockNumber(), ItemPointerIsLossyPage, ItemPointerSetMin, IndexScanDescData::opaque, scanGetItem(), scanPendingInsert(), startScan(), tbm_add_page(), and tbm_add_tuples().

Referenced by ginhandler().

◆ keyGetItem()

static void keyGetItem ( GinState ginstate,
MemoryContext  tempCtx,
GinScanKey  key,
ItemPointerData  advancePast,
Snapshot  snapshot 
)
static

Definition at line 990 of file ginget.c.

992 {
993  ItemPointerData minItem;
994  ItemPointerData curPageLossy;
995  uint32 i;
996  bool haveLossyEntry;
997  GinScanEntry entry;
999  MemoryContext oldCtx;
1000  bool allFinished;
1001 
1002  Assert(!key->isFinished);
1003 
1004  /*
1005  * We might have already tested this item; if so, no need to repeat work.
1006  * (Note: the ">" case can happen, if advancePast is exact but we
1007  * previously had to set curItem to a lossy-page pointer.)
1008  */
1009  if (ginCompareItemPointers(&key->curItem, &advancePast) > 0)
1010  return;
1011 
1012  /*
1013  * Find the minimum item > advancePast among the active entry streams.
1014  *
1015  * Note: a lossy-page entry is encoded by a ItemPointer with max value for
1016  * offset (0xffff), so that it will sort after any exact entries for the
1017  * same page. So we'll prefer to return exact pointers not lossy
1018  * pointers, which is good.
1019  */
1020  ItemPointerSetMax(&minItem);
1021  allFinished = true;
1022  for (i = 0; i < key->nrequired; i++)
1023  {
1024  entry = key->requiredEntries[i];
1025 
1026  if (entry->isFinished)
1027  continue;
1028 
1029  /*
1030  * Advance this stream if necessary.
1031  *
1032  * In particular, since entry->curItem was initialized with
1033  * ItemPointerSetMin, this ensures we fetch the first item for each
1034  * entry on the first call.
1035  */
1036  if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
1037  {
1038  entryGetItem(ginstate, entry, advancePast, snapshot);
1039  if (entry->isFinished)
1040  continue;
1041  }
1042 
1043  allFinished = false;
1044  if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
1045  minItem = entry->curItem;
1046  }
1047 
1048  if (allFinished && !key->excludeOnly)
1049  {
1050  /* all entries are finished */
1051  key->isFinished = true;
1052  return;
1053  }
1054 
1055  if (!key->excludeOnly)
1056  {
1057  /*
1058  * For a normal scan key, we now know there are no matches < minItem.
1059  *
1060  * If minItem is lossy, it means that there were no exact items on the
1061  * page among requiredEntries, because lossy pointers sort after exact
1062  * items. However, there might be exact items for the same page among
1063  * additionalEntries, so we mustn't advance past them.
1064  */
1065  if (ItemPointerIsLossyPage(&minItem))
1066  {
1067  if (GinItemPointerGetBlockNumber(&advancePast) <
1068  GinItemPointerGetBlockNumber(&minItem))
1069  {
1070  ItemPointerSet(&advancePast,
1071  GinItemPointerGetBlockNumber(&minItem),
1073  }
1074  }
1075  else
1076  {
1077  Assert(GinItemPointerGetOffsetNumber(&minItem) > 0);
1078  ItemPointerSet(&advancePast,
1079  GinItemPointerGetBlockNumber(&minItem),
1081  }
1082  }
1083  else
1084  {
1085  /*
1086  * excludeOnly scan keys don't have any entries that are necessarily
1087  * present in matching items. So, we consider the item just after
1088  * advancePast.
1089  */
1090  Assert(key->nrequired == 0);
1091  ItemPointerSet(&minItem,
1092  GinItemPointerGetBlockNumber(&advancePast),
1094  }
1095 
1096  /*
1097  * We might not have loaded all the entry streams for this TID yet. We
1098  * could call the consistent function, passing MAYBE for those entries, to
1099  * see if it can decide if this TID matches based on the information we
1100  * have. But if the consistent-function is expensive, and cannot in fact
1101  * decide with partial information, that could be a big loss. So, load all
1102  * the additional entries, before calling the consistent function.
1103  */
1104  for (i = 0; i < key->nadditional; i++)
1105  {
1106  entry = key->additionalEntries[i];
1107 
1108  if (entry->isFinished)
1109  continue;
1110 
1111  if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
1112  {
1113  entryGetItem(ginstate, entry, advancePast, snapshot);
1114  if (entry->isFinished)
1115  continue;
1116  }
1117 
1118  /*
1119  * Normally, none of the items in additionalEntries can have a curItem
1120  * larger than minItem. But if minItem is a lossy page, then there
1121  * might be exact items on the same page among additionalEntries.
1122  */
1123  if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
1124  {
1125  Assert(ItemPointerIsLossyPage(&minItem));
1126  minItem = entry->curItem;
1127  }
1128  }
1129 
1130  /*
1131  * Ok, we've advanced all the entries up to minItem now. Set key->curItem,
1132  * and perform consistentFn test.
1133  *
1134  * Lossy-page entries pose a problem, since we don't know the correct
1135  * entryRes state to pass to the consistentFn, and we also don't know what
1136  * its combining logic will be (could be AND, OR, or even NOT). If the
1137  * logic is OR then the consistentFn might succeed for all items in the
1138  * lossy page even when none of the other entries match.
1139  *
1140  * Our strategy is to call the tri-state consistent function, with the
1141  * lossy-page entries set to MAYBE, and all the other entries FALSE. If it
1142  * returns FALSE, none of the lossy items alone are enough for a match, so
1143  * we don't need to return a lossy-page pointer. Otherwise, return a
1144  * lossy-page pointer to indicate that the whole heap page must be
1145  * checked. (On subsequent calls, we'll do nothing until minItem is past
1146  * the page altogether, thus ensuring that we never return both regular
1147  * and lossy pointers for the same page.)
1148  *
1149  * An exception is that it doesn't matter what we pass for lossy pointers
1150  * in "hidden" entries, because the consistentFn's result can't depend on
1151  * them. We could pass them as MAYBE as well, but if we're using the
1152  * "shim" implementation of a tri-state consistent function (see
1153  * ginlogic.c), it's better to pass as few MAYBEs as possible. So pass
1154  * them as true.
1155  *
1156  * Note that only lossy-page entries pointing to the current item's page
1157  * should trigger this processing; we might have future lossy pages in the
1158  * entry array, but they aren't relevant yet.
1159  */
1160  key->curItem = minItem;
1161  ItemPointerSetLossyPage(&curPageLossy,
1162  GinItemPointerGetBlockNumber(&key->curItem));
1163  haveLossyEntry = false;
1164  for (i = 0; i < key->nentries; i++)
1165  {
1166  entry = key->scanEntry[i];
1167  if (entry->isFinished == false &&
1168  ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0)
1169  {
1170  if (i < key->nuserentries)
1171  key->entryRes[i] = GIN_MAYBE;
1172  else
1173  key->entryRes[i] = GIN_TRUE;
1174  haveLossyEntry = true;
1175  }
1176  else
1177  key->entryRes[i] = GIN_FALSE;
1178  }
1179 
1180  /* prepare for calling consistentFn in temp context */
1181  oldCtx = MemoryContextSwitchTo(tempCtx);
1182 
1183  if (haveLossyEntry)
1184  {
1185  /* Have lossy-page entries, so see if whole page matches */
1186  res = key->triConsistentFn(key);
1187 
1188  if (res == GIN_TRUE || res == GIN_MAYBE)
1189  {
1190  /* Yes, so clean up ... */
1191  MemoryContextSwitchTo(oldCtx);
1192  MemoryContextReset(tempCtx);
1193 
1194  /* and return lossy pointer for whole page */
1195  key->curItem = curPageLossy;
1196  key->curItemMatches = true;
1197  key->recheckCurItem = true;
1198  return;
1199  }
1200  }
1201 
1202  /*
1203  * At this point we know that we don't need to return a lossy whole-page
1204  * pointer, but we might have matches for individual exact item pointers,
1205  * possibly in combination with a lossy pointer. Pass lossy pointers as
1206  * MAYBE to the ternary consistent function, to let it decide if this
1207  * tuple satisfies the overall key, even though we don't know if the lossy
1208  * entries match.
1209  *
1210  * Prepare entryRes array to be passed to consistentFn.
1211  */
1212  for (i = 0; i < key->nentries; i++)
1213  {
1214  entry = key->scanEntry[i];
1215  if (entry->isFinished)
1216  key->entryRes[i] = GIN_FALSE;
1217 #if 0
1218 
1219  /*
1220  * This case can't currently happen, because we loaded all the entries
1221  * for this item earlier.
1222  */
1223  else if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
1224  key->entryRes[i] = GIN_MAYBE;
1225 #endif
1226  else if (ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0)
1227  key->entryRes[i] = GIN_MAYBE;
1228  else if (ginCompareItemPointers(&entry->curItem, &minItem) == 0)
1229  key->entryRes[i] = GIN_TRUE;
1230  else
1231  key->entryRes[i] = GIN_FALSE;
1232  }
1233 
1234  res = key->triConsistentFn(key);
1235 
1236  switch (res)
1237  {
1238  case GIN_TRUE:
1239  key->curItemMatches = true;
1240  /* triConsistentFn set recheckCurItem */
1241  break;
1242 
1243  case GIN_FALSE:
1244  key->curItemMatches = false;
1245  break;
1246 
1247  case GIN_MAYBE:
1248  key->curItemMatches = true;
1249  key->recheckCurItem = true;
1250  break;
1251 
1252  default:
1253 
1254  /*
1255  * the 'default' case shouldn't happen, but if the consistent
1256  * function returns something bogus, this is the safe result
1257  */
1258  key->curItemMatches = true;
1259  key->recheckCurItem = true;
1260  break;
1261  }
1262 
1263  /*
1264  * We have a tuple, and we know if it matches or not. If it's a non-match,
1265  * we could continue to find the next matching tuple, but let's break out
1266  * and give scanGetItem a chance to advance the other keys. They might be
1267  * able to skip past to a much higher TID, allowing us to save work.
1268  */
1269 
1270  /* clean up after consistentFn calls */
1271  MemoryContextSwitchTo(oldCtx);
1272  MemoryContextReset(tempCtx);
1273 }
char GinTernaryValue
Definition: gin.h:58
#define GIN_MAYBE
Definition: gin.h:65
#define GIN_TRUE
Definition: gin.h:64
#define ItemPointerSetMax(p)
Definition: ginblock.h:171
static void entryGetItem(GinState *ginstate, GinScanEntry entry, ItemPointerData advancePast, Snapshot snapshot)
Definition: ginget.c:808
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:314
#define OffsetNumberPrev(offsetNumber)
Definition: off.h:54
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:138

References Assert(), GinScanEntryData::curItem, entryGetItem(), GIN_FALSE, GIN_MAYBE, GIN_TRUE, ginCompareItemPointers(), GinItemPointerGetBlockNumber, GinItemPointerGetOffsetNumber, i, InvalidOffsetNumber, GinScanEntryData::isFinished, ItemPointerIsLossyPage, ItemPointerSet(), ItemPointerSetLossyPage, ItemPointerSetMax, sort-test::key, MemoryContextReset(), MemoryContextSwitchTo(), OffsetNumberNext, OffsetNumberPrev, and res.

Referenced by scanGetItem().

◆ matchPartialInPendingList()

static bool matchPartialInPendingList ( GinState ginstate,
Page  page,
OffsetNumber  off,
OffsetNumber  maxoff,
GinScanEntry  entry,
Datum datum,
GinNullCategory category,
bool datumExtracted 
)
static

Definition at line 1539 of file ginget.c.

1544 {
1545  IndexTuple itup;
1546  int32 cmp;
1547 
1548  /* Partial match to a null is not possible */
1549  if (entry->queryCategory != GIN_CAT_NORM_KEY)
1550  return false;
1551 
1552  while (off < maxoff)
1553  {
1554  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
1555 
1556  if (gintuple_get_attrnum(ginstate, itup) != entry->attnum)
1557  return false;
1558 
1559  if (datumExtracted[off - 1] == false)
1560  {
1561  datum[off - 1] = gintuple_get_key(ginstate, itup,
1562  &category[off - 1]);
1563  datumExtracted[off - 1] = true;
1564  }
1565 
1566  /* Once we hit nulls, no further match is possible */
1567  if (category[off - 1] != GIN_CAT_NORM_KEY)
1568  return false;
1569 
1570  /*----------
1571  * Check partial match.
1572  * case cmp == 0 => match
1573  * case cmp > 0 => not match and end scan (no later match possible)
1574  * case cmp < 0 => not match and continue scan
1575  *----------
1576  */
1577  cmp = DatumGetInt32(FunctionCall4Coll(&ginstate->comparePartialFn[entry->attnum - 1],
1578  ginstate->supportCollation[entry->attnum - 1],
1579  entry->queryKey,
1580  datum[off - 1],
1581  UInt16GetDatum(entry->strategy),
1582  PointerGetDatum(entry->extra_data)));
1583  if (cmp == 0)
1584  return true;
1585  else if (cmp > 0)
1586  return false;
1587 
1588  off++;
1589  }
1590 
1591  return false;
1592 }

References GinScanEntryData::attnum, cmp(), GinState::comparePartialFn, DatumGetInt32(), GinScanEntryData::extra_data, FunctionCall4Coll(), GIN_CAT_NORM_KEY, gintuple_get_attrnum(), gintuple_get_key(), PageGetItem(), PageGetItemId(), PointerGetDatum(), GinScanEntryData::queryCategory, GinScanEntryData::queryKey, GinScanEntryData::strategy, GinState::supportCollation, and UInt16GetDatum().

Referenced by collectMatchesForHeapRow().

◆ moveRightIfItNeeded()

static bool moveRightIfItNeeded ( GinBtreeData btree,
GinBtreeStack stack,
Snapshot  snapshot 
)
static

Definition at line 43 of file ginget.c.

44 {
45  Page page = BufferGetPage(stack->buffer);
46 
47  if (stack->off > PageGetMaxOffsetNumber(page))
48  {
49  /*
50  * We scanned the whole page, so we should take right page
51  */
52  if (GinPageRightMost(page))
53  return false; /* no more pages */
54 
55  stack->buffer = ginStepRight(stack->buffer, btree->index, GIN_SHARE);
56  stack->blkno = BufferGetBlockNumber(stack->buffer);
57  stack->off = FirstOffsetNumber;
58  PredicateLockPage(btree->index, stack->blkno, snapshot);
59  }
60 
61  return true;
62 }
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2811
static OffsetNumber PageGetMaxOffsetNumber(Page page)
Definition: bufpage.h:369
BlockNumber blkno
Definition: gin_private.h:130

References GinBtreeStack::blkno, GinBtreeStack::buffer, BufferGetBlockNumber(), BufferGetPage(), FirstOffsetNumber, GIN_SHARE, GinPageRightMost, ginStepRight(), GinBtreeData::index, GinBtreeStack::off, PageGetMaxOffsetNumber(), and PredicateLockPage().

Referenced by collectMatchBitmap().

◆ scanGetCandidate()

static bool scanGetCandidate ( IndexScanDesc  scan,
pendingPosition pos 
)
static

Definition at line 1451 of file ginget.c.

1452 {
1453  OffsetNumber maxoff;
1454  Page page;
1455  IndexTuple itup;
1456 
1457  ItemPointerSetInvalid(&pos->item);
1458  for (;;)
1459  {
1460  page = BufferGetPage(pos->pendingBuffer);
1461  TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
1462 
1463  maxoff = PageGetMaxOffsetNumber(page);
1464  if (pos->firstOffset > maxoff)
1465  {
1466  BlockNumber blkno = GinPageGetOpaque(page)->rightlink;
1467 
1468  if (blkno == InvalidBlockNumber)
1469  {
1472 
1473  return false;
1474  }
1475  else
1476  {
1477  /*
1478  * Here we must prevent deletion of next page by insertcleanup
1479  * process, which may be trying to obtain exclusive lock on
1480  * current page. So, we lock next page before releasing the
1481  * current one
1482  */
1483  Buffer tmpbuf = ReadBuffer(scan->indexRelation, blkno);
1484 
1487 
1488  pos->pendingBuffer = tmpbuf;
1490  }
1491  }
1492  else
1493  {
1494  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->firstOffset));
1495  pos->item = itup->t_tid;
1496  if (GinPageHasFullRow(page))
1497  {
1498  /*
1499  * find itempointer to the next row
1500  */
1501  for (pos->lastOffset = pos->firstOffset + 1; pos->lastOffset <= maxoff; pos->lastOffset++)
1502  {
1503  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->lastOffset));
1504  if (!ItemPointerEquals(&pos->item, &itup->t_tid))
1505  break;
1506  }
1507  }
1508  else
1509  {
1510  /*
1511  * All itempointers are the same on this page
1512  */
1513  pos->lastOffset = maxoff + 1;
1514  }
1515 
1516  /*
1517  * Now pos->firstOffset points to the first tuple of current heap
1518  * row, pos->lastOffset points to the first tuple of next heap row
1519  * (or to the end of page)
1520  */
1521  break;
1522  }
1523  }
1524 
1525  return true;
1526 }
#define InvalidBlockNumber
Definition: block.h:33
int Buffer
Definition: buf.h:23
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:704
ItemPointerData t_tid
Definition: itup.h:37
static StringInfoData tmpbuf
Definition: walsender.c:160

References BufferGetPage(), pendingPosition::firstOffset, FirstOffsetNumber, GIN_SHARE, GinPageGetOpaque, GinPageHasFullRow, IndexScanDescData::indexRelation, InvalidBlockNumber, InvalidBuffer, pendingPosition::item, ItemPointerEquals(), ItemPointerSetInvalid(), pendingPosition::lastOffset, LockBuffer(), PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), pendingPosition::pendingBuffer, ReadBuffer(), IndexTupleData::t_tid, TestForOldSnapshot(), tmpbuf, UnlockReleaseBuffer(), and IndexScanDescData::xs_snapshot.

Referenced by collectMatchesForHeapRow(), and scanPendingInsert().

◆ scanGetItem()

static bool scanGetItem ( IndexScanDesc  scan,
ItemPointerData  advancePast,
ItemPointerData item,
bool recheck 
)
static

Definition at line 1285 of file ginget.c.

1287 {
1288  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1289  uint32 i;
1290  bool match;
1291 
1292  /*----------
1293  * Advance the scan keys in lock-step, until we find an item that matches
1294  * all the keys. If any key reports isFinished, meaning its subset of the
1295  * entries is exhausted, we can stop. Otherwise, set *item to the next
1296  * matching item.
1297  *
1298  * This logic works only if a keyGetItem stream can never contain both
1299  * exact and lossy pointers for the same page. Else we could have a
1300  * case like
1301  *
1302  * stream 1 stream 2
1303  * ... ...
1304  * 42/6 42/7
1305  * 50/1 42/0xffff
1306  * ... ...
1307  *
1308  * We would conclude that 42/6 is not a match and advance stream 1,
1309  * thus never detecting the match to the lossy pointer in stream 2.
1310  * (keyGetItem has a similar problem versus entryGetItem.)
1311  *----------
1312  */
1313  do
1314  {
1315  ItemPointerSetMin(item);
1316  match = true;
1317  for (i = 0; i < so->nkeys && match; i++)
1318  {
1319  GinScanKey key = so->keys + i;
1320 
1321  /*
1322  * If we're considering a lossy page, skip excludeOnly keys. They
1323  * can't exclude the whole page anyway.
1324  */
1325  if (ItemPointerIsLossyPage(item) && key->excludeOnly)
1326  {
1327  /*
1328  * ginNewScanKey() should never mark the first key as
1329  * excludeOnly.
1330  */
1331  Assert(i > 0);
1332  continue;
1333  }
1334 
1335  /* Fetch the next item for this key that is > advancePast. */
1336  keyGetItem(&so->ginstate, so->tempCtx, key, advancePast,
1337  scan->xs_snapshot);
1338 
1339  if (key->isFinished)
1340  return false;
1341 
1342  /*
1343  * If it's not a match, we can immediately conclude that nothing
1344  * <= this item matches, without checking the rest of the keys.
1345  */
1346  if (!key->curItemMatches)
1347  {
1348  advancePast = key->curItem;
1349  match = false;
1350  break;
1351  }
1352 
1353  /*
1354  * It's a match. We can conclude that nothing < matches, so the
1355  * other key streams can skip to this item.
1356  *
1357  * Beware of lossy pointers, though; from a lossy pointer, we can
1358  * only conclude that nothing smaller than this *block* matches.
1359  */
1360  if (ItemPointerIsLossyPage(&key->curItem))
1361  {
1362  if (GinItemPointerGetBlockNumber(&advancePast) <
1363  GinItemPointerGetBlockNumber(&key->curItem))
1364  {
1365  ItemPointerSet(&advancePast,
1366  GinItemPointerGetBlockNumber(&key->curItem),
1368  }
1369  }
1370  else
1371  {
1372  Assert(GinItemPointerGetOffsetNumber(&key->curItem) > 0);
1373  ItemPointerSet(&advancePast,
1374  GinItemPointerGetBlockNumber(&key->curItem),
1376  }
1377 
1378  /*
1379  * If this is the first key, remember this location as a potential
1380  * match, and proceed to check the rest of the keys.
1381  *
1382  * Otherwise, check if this is the same item that we checked the
1383  * previous keys for (or a lossy pointer for the same page). If
1384  * not, loop back to check the previous keys for this item (we
1385  * will check this key again too, but keyGetItem returns quickly
1386  * for that)
1387  */
1388  if (i == 0)
1389  {
1390  *item = key->curItem;
1391  }
1392  else
1393  {
1394  if (ItemPointerIsLossyPage(&key->curItem) ||
1395  ItemPointerIsLossyPage(item))
1396  {
1398  match = (GinItemPointerGetBlockNumber(&key->curItem) ==
1400  }
1401  else
1402  {
1403  Assert(ginCompareItemPointers(&key->curItem, item) >= 0);
1404  match = (ginCompareItemPointers(&key->curItem, item) == 0);
1405  }
1406  }
1407  }
1408  } while (!match);
1409 
1410  Assert(!ItemPointerIsMin(item));
1411 
1412  /*
1413  * Now *item contains the first ItemPointer after previous result that
1414  * satisfied all the keys for that exact TID, or a lossy reference to the
1415  * same page.
1416  *
1417  * We must return recheck = true if any of the keys are marked recheck.
1418  */
1419  *recheck = false;
1420  for (i = 0; i < so->nkeys; i++)
1421  {
1422  GinScanKey key = so->keys + i;
1423 
1424  if (key->recheckCurItem)
1425  {
1426  *recheck = true;
1427  break;
1428  }
1429  }
1430 
1431  return true;
1432 }
#define ItemPointerIsMin(p)
Definition: ginblock.h:168
static void keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, ItemPointerData advancePast, Snapshot snapshot)
Definition: ginget.c:990
MemoryContext tempCtx
Definition: gin_private.h:370

References Assert(), ginCompareItemPointers(), GinItemPointerGetBlockNumber, GinItemPointerGetOffsetNumber, GinScanOpaqueData::ginstate, i, InvalidOffsetNumber, ItemPointerIsLossyPage, ItemPointerSet(), ItemPointerSetMin, sort-test::key, keyGetItem(), GinScanOpaqueData::keys, GinScanOpaqueData::nkeys, OffsetNumberPrev, IndexScanDescData::opaque, GinScanOpaqueData::tempCtx, and IndexScanDescData::xs_snapshot.

Referenced by gingetbitmap().

◆ scanPendingInsert()

static void scanPendingInsert ( IndexScanDesc  scan,
TIDBitmap tbm,
int64 *  ntids 
)
static

Definition at line 1823 of file ginget.c.

1824 {
1825  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1826  MemoryContext oldCtx;
1827  bool recheck,
1828  match;
1829  int i;
1830  pendingPosition pos;
1831  Buffer metabuffer = ReadBuffer(scan->indexRelation, GIN_METAPAGE_BLKNO);
1832  Page page;
1833  BlockNumber blkno;
1834 
1835  *ntids = 0;
1836 
1837  /*
1838  * Acquire predicate lock on the metapage, to conflict with any fastupdate
1839  * insertions.
1840  */
1842 
1843  LockBuffer(metabuffer, GIN_SHARE);
1844  page = BufferGetPage(metabuffer);
1845  TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
1846  blkno = GinPageGetMeta(page)->head;
1847 
1848  /*
1849  * fetch head of list before unlocking metapage. head page must be pinned
1850  * to prevent deletion by vacuum process
1851  */
1852  if (blkno == InvalidBlockNumber)
1853  {
1854  /* No pending list, so proceed with normal scan */
1855  UnlockReleaseBuffer(metabuffer);
1856  return;
1857  }
1858 
1859  pos.pendingBuffer = ReadBuffer(scan->indexRelation, blkno);
1860  LockBuffer(pos.pendingBuffer, GIN_SHARE);
1861  pos.firstOffset = FirstOffsetNumber;
1862  UnlockReleaseBuffer(metabuffer);
1863  pos.hasMatchKey = palloc(sizeof(bool) * so->nkeys);
1864 
1865  /*
1866  * loop for each heap row. scanGetCandidate returns full row or row's
1867  * tuples from first page.
1868  */
1869  while (scanGetCandidate(scan, &pos))
1870  {
1871  /*
1872  * Check entries in tuple and set up entryRes array.
1873  *
1874  * If pending tuples belonging to the current heap row are spread
1875  * across several pages, collectMatchesForHeapRow will read all of
1876  * those pages.
1877  */
1878  if (!collectMatchesForHeapRow(scan, &pos))
1879  continue;
1880 
1881  /*
1882  * Matching of entries of one row is finished, so check row using
1883  * consistent functions.
1884  */
1885  oldCtx = MemoryContextSwitchTo(so->tempCtx);
1886  recheck = false;
1887  match = true;
1888 
1889  for (i = 0; i < so->nkeys; i++)
1890  {
1891  GinScanKey key = so->keys + i;
1892 
1893  if (!key->boolConsistentFn(key))
1894  {
1895  match = false;
1896  break;
1897  }
1898  recheck |= key->recheckCurItem;
1899  }
1900 
1901  MemoryContextSwitchTo(oldCtx);
1903 
1904  if (match)
1905  {
1906  tbm_add_tuples(tbm, &pos.item, 1, recheck);
1907  (*ntids)++;
1908  }
1909  }
1910 
1911  pfree(pos.hasMatchKey);
1912 }
#define GIN_METAPAGE_BLKNO
Definition: ginblock.h:51
#define GinPageGetMeta(p)
Definition: ginblock.h:104
static bool collectMatchesForHeapRow(IndexScanDesc scan, pendingPosition *pos)
Definition: ginget.c:1607
void * palloc(Size size)
Definition: mcxt.c:1210

References BufferGetPage(), collectMatchesForHeapRow(), FirstOffsetNumber, GIN_METAPAGE_BLKNO, GIN_SHARE, GinPageGetMeta, i, IndexScanDescData::indexRelation, InvalidBlockNumber, sort-test::key, GinScanOpaqueData::keys, LockBuffer(), MemoryContextReset(), MemoryContextSwitchTo(), GinScanOpaqueData::nkeys, IndexScanDescData::opaque, palloc(), pfree(), PredicateLockPage(), ReadBuffer(), scanGetCandidate(), tbm_add_tuples(), GinScanOpaqueData::tempCtx, TestForOldSnapshot(), UnlockReleaseBuffer(), and IndexScanDescData::xs_snapshot.

Referenced by gingetbitmap().

◆ scanPostingTree()

static void scanPostingTree ( Relation  index,
GinScanEntry  scanEntry,
BlockNumber  rootPostingTree,
Snapshot  snapshot 
)
static

Definition at line 69 of file ginget.c.

71 {
72  GinBtreeData btree;
73  GinBtreeStack *stack;
74  Buffer buffer;
75  Page page;
76 
77  /* Descend to the leftmost leaf page */
78  stack = ginScanBeginPostingTree(&btree, index, rootPostingTree, snapshot);
79  buffer = stack->buffer;
80 
81  IncrBufferRefCount(buffer); /* prevent unpin in freeGinBtreeStack */
82 
83  freeGinBtreeStack(stack);
84 
85  /*
86  * Loop iterates through all leaf pages of posting tree
87  */
88  for (;;)
89  {
90  page = BufferGetPage(buffer);
91  if ((GinPageGetOpaque(page)->flags & GIN_DELETED) == 0)
92  {
93  int n = GinDataLeafPageGetItemsToTbm(page, scanEntry->matchBitmap);
94 
95  scanEntry->predictNumberResult += n;
96  }
97 
98  if (GinPageRightMost(page))
99  break; /* no more pages */
100 
101  buffer = ginStepRight(buffer, index, GIN_SHARE);
102  }
103 
104  UnlockReleaseBuffer(buffer);
105 }
GinBtreeStack * ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno, Snapshot snapshot)
Definition: gindatapage.c:1930
int GinDataLeafPageGetItemsToTbm(Page page, TIDBitmap *tbm)
Definition: gindatapage.c:182
Definition: type.h:95

References GinBtreeStack::buffer, BufferGetPage(), freeGinBtreeStack(), GIN_DELETED, GIN_SHARE, GinDataLeafPageGetItemsToTbm(), GinPageGetOpaque, GinPageRightMost, ginScanBeginPostingTree(), ginStepRight(), IncrBufferRefCount(), GinScanEntryData::matchBitmap, GinScanEntryData::predictNumberResult, and UnlockReleaseBuffer().

Referenced by collectMatchBitmap().

◆ startScan()

static void startScan ( IndexScanDesc  scan)
static

Definition at line 601 of file ginget.c.

602 {
603  GinScanOpaque so = (GinScanOpaque) scan->opaque;
604  GinState *ginstate = &so->ginstate;
605  uint32 i;
606 
607  for (i = 0; i < so->totalentries; i++)
608  startScanEntry(ginstate, so->entries[i], scan->xs_snapshot);
609 
610  if (GinFuzzySearchLimit > 0)
611  {
612  /*
613  * If all of keys more than threshold we will try to reduce result, we
614  * hope (and only hope, for intersection operation of array our
615  * supposition isn't true), that total result will not more than
616  * minimal predictNumberResult.
617  */
618  bool reduce = true;
619 
620  for (i = 0; i < so->totalentries; i++)
621  {
623  {
624  reduce = false;
625  break;
626  }
627  }
628  if (reduce)
629  {
630  for (i = 0; i < so->totalentries; i++)
631  {
633  so->entries[i]->reduceResult = true;
634  }
635  }
636  }
637 
638  /*
639  * Now that we have the estimates for the entry frequencies, finish
640  * initializing the scan keys.
641  */
642  for (i = 0; i < so->nkeys; i++)
643  startScanKey(ginstate, so, so->keys + i);
644 }
static void startScanEntry(GinState *ginstate, GinScanEntry entry, Snapshot snapshot)
Definition: ginget.c:319
static void startScanKey(GinState *ginstate, GinScanOpaque so, GinScanKey key)
Definition: ginget.c:505
int GinFuzzySearchLimit
Definition: ginget.c:27
static void reduce(void)
Definition: parse.c:260
GinScanEntry * entries
Definition: gin_private.h:376

References GinScanOpaqueData::entries, GinFuzzySearchLimit, GinScanOpaqueData::ginstate, i, GinScanOpaqueData::keys, GinScanOpaqueData::nkeys, IndexScanDescData::opaque, GinScanEntryData::predictNumberResult, reduce(), GinScanEntryData::reduceResult, startScanEntry(), startScanKey(), GinScanOpaqueData::totalentries, and IndexScanDescData::xs_snapshot.

Referenced by gingetbitmap().

◆ startScanEntry()

static void startScanEntry ( GinState ginstate,
GinScanEntry  entry,
Snapshot  snapshot 
)
static

Definition at line 319 of file ginget.c.

320 {
321  GinBtreeData btreeEntry;
322  GinBtreeStack *stackEntry;
323  Page page;
324  bool needUnlock;
325 
326 restartScanEntry:
327  entry->buffer = InvalidBuffer;
328  ItemPointerSetMin(&entry->curItem);
329  entry->offset = InvalidOffsetNumber;
330  if (entry->list)
331  pfree(entry->list);
332  entry->list = NULL;
333  entry->nlist = 0;
334  entry->matchBitmap = NULL;
335  entry->matchResult = NULL;
336  entry->reduceResult = false;
337  entry->predictNumberResult = 0;
338 
339  /*
340  * we should find entry, and begin scan of posting tree or just store
341  * posting list in memory
342  */
343  ginPrepareEntryScan(&btreeEntry, entry->attnum,
344  entry->queryKey, entry->queryCategory,
345  ginstate);
346  stackEntry = ginFindLeafPage(&btreeEntry, true, false, snapshot);
347  page = BufferGetPage(stackEntry->buffer);
348 
349  /* ginFindLeafPage() will have already checked snapshot age. */
350  needUnlock = true;
351 
352  entry->isFinished = true;
353 
354  if (entry->isPartialMatch ||
356  {
357  /*
358  * btreeEntry.findItem locates the first item >= given search key.
359  * (For GIN_CAT_EMPTY_QUERY, it will find the leftmost index item
360  * because of the way the GIN_CAT_EMPTY_QUERY category code is
361  * assigned.) We scan forward from there and collect all TIDs needed
362  * for the entry type.
363  */
364  btreeEntry.findItem(&btreeEntry, stackEntry);
365  if (collectMatchBitmap(&btreeEntry, stackEntry, entry, snapshot)
366  == false)
367  {
368  /*
369  * GIN tree was seriously restructured, so we will cleanup all
370  * found data and rescan. See comments near 'return false' in
371  * collectMatchBitmap()
372  */
373  if (entry->matchBitmap)
374  {
375  if (entry->matchIterator)
377  entry->matchIterator = NULL;
378  tbm_free(entry->matchBitmap);
379  entry->matchBitmap = NULL;
380  }
381  LockBuffer(stackEntry->buffer, GIN_UNLOCK);
382  freeGinBtreeStack(stackEntry);
383  goto restartScanEntry;
384  }
385 
386  if (entry->matchBitmap && !tbm_is_empty(entry->matchBitmap))
387  {
389  entry->isFinished = false;
390  }
391  }
392  else if (btreeEntry.findItem(&btreeEntry, stackEntry))
393  {
394  IndexTuple itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stackEntry->off));
395 
396  if (GinIsPostingTree(itup))
397  {
398  BlockNumber rootPostingTree = GinGetPostingTree(itup);
399  GinBtreeStack *stack;
400  Page entrypage;
401  ItemPointerData minItem;
402 
403  /*
404  * This is an equality scan, so lock the root of the posting tree.
405  * It represents a lock on the exact key value, and covers all the
406  * items in the posting tree.
407  */
408  PredicateLockPage(ginstate->index, rootPostingTree, snapshot);
409 
410  /*
411  * We should unlock entry page before touching posting tree to
412  * prevent deadlocks with vacuum processes. Because entry is never
413  * deleted from page and posting tree is never reduced to the
414  * posting list, we can unlock page after getting BlockNumber of
415  * root of posting tree.
416  */
417  LockBuffer(stackEntry->buffer, GIN_UNLOCK);
418  needUnlock = false;
419 
420  stack = ginScanBeginPostingTree(&entry->btree, ginstate->index,
421  rootPostingTree, snapshot);
422  entry->buffer = stack->buffer;
423 
424  /*
425  * We keep buffer pinned because we need to prevent deletion of
426  * page during scan. See GIN's vacuum implementation. RefCount is
427  * increased to keep buffer pinned after freeGinBtreeStack() call.
428  */
429  IncrBufferRefCount(entry->buffer);
430 
431  entrypage = BufferGetPage(entry->buffer);
432 
433  /*
434  * Load the first page into memory.
435  */
436  ItemPointerSetMin(&minItem);
437  entry->list = GinDataLeafPageGetItems(entrypage, &entry->nlist, minItem);
438 
439  entry->predictNumberResult = stack->predictNumber * entry->nlist;
440 
441  LockBuffer(entry->buffer, GIN_UNLOCK);
442  freeGinBtreeStack(stack);
443  entry->isFinished = false;
444  }
445  else
446  {
447  /*
448  * Lock the entry leaf page. This is more coarse-grained than
449  * necessary, because it will conflict with any insertions that
450  * land on the same leaf page, not only the exact key we searched
451  * for. But locking an individual tuple would require updating
452  * that lock whenever it moves because of insertions or vacuums,
453  * which seems too complicated.
454  */
455  PredicateLockPage(ginstate->index,
456  BufferGetBlockNumber(stackEntry->buffer),
457  snapshot);
458  if (GinGetNPosting(itup) > 0)
459  {
460  entry->list = ginReadTuple(ginstate, entry->attnum, itup,
461  &entry->nlist);
462  entry->predictNumberResult = entry->nlist;
463 
464  entry->isFinished = false;
465  }
466  }
467  }
468  else
469  {
470  /*
471  * No entry found. Predicate lock the leaf page, to lock the place
472  * where the entry would've been, had there been one.
473  */
474  PredicateLockPage(ginstate->index,
475  BufferGetBlockNumber(stackEntry->buffer), snapshot);
476  }
477 
478  if (needUnlock)
479  LockBuffer(stackEntry->buffer, GIN_UNLOCK);
480  freeGinBtreeStack(stackEntry);
481 }
void ginPrepareEntryScan(GinBtree btree, OffsetNumber attnum, Datum key, GinNullCategory category, GinState *ginstate)
Definition: ginentrypage.c:745
static bool collectMatchBitmap(GinBtreeData *btree, GinBtreeStack *stack, GinScanEntry scanEntry, Snapshot snapshot)
Definition: ginget.c:121
bool(* findItem)(GinBtree, GinBtreeStack *)
Definition: gin_private.h:155
uint32 predictNumber
Definition: gin_private.h:135
void tbm_free(TIDBitmap *tbm)
Definition: tidbitmap.c:321
TBMIterator * tbm_begin_iterate(TIDBitmap *tbm)
Definition: tidbitmap.c:688
bool tbm_is_empty(const TIDBitmap *tbm)
Definition: tidbitmap.c:669

References GinScanEntryData::attnum, GinScanEntryData::btree, GinBtreeStack::buffer, GinScanEntryData::buffer, BufferGetBlockNumber(), BufferGetPage(), collectMatchBitmap(), GinScanEntryData::curItem, GinBtreeData::findItem, freeGinBtreeStack(), GIN_CAT_EMPTY_QUERY, GIN_UNLOCK, GinDataLeafPageGetItems(), ginFindLeafPage(), GinGetNPosting, GinGetPostingTree, GinIsPostingTree, ginPrepareEntryScan(), ginReadTuple(), ginScanBeginPostingTree(), IncrBufferRefCount(), GinState::index, InvalidBuffer, InvalidOffsetNumber, GinScanEntryData::isFinished, GinScanEntryData::isPartialMatch, ItemPointerSetMin, GinScanEntryData::list, LockBuffer(), GinScanEntryData::matchBitmap, GinScanEntryData::matchIterator, GinScanEntryData::matchResult, GinScanEntryData::nlist, GinBtreeStack::off, GinScanEntryData::offset, PageGetItem(), PageGetItemId(), pfree(), PredicateLockPage(), GinBtreeStack::predictNumber, GinScanEntryData::predictNumberResult, GinScanEntryData::queryCategory, GinScanEntryData::queryKey, GinScanEntryData::reduceResult, tbm_begin_iterate(), tbm_end_iterate(), tbm_free(), and tbm_is_empty().

Referenced by startScan().

◆ startScanKey()

static void startScanKey ( GinState ginstate,
GinScanOpaque  so,
GinScanKey  key 
)
static

Definition at line 505 of file ginget.c.

506 {
508  int i;
509  int j;
510  int *entryIndexes;
511 
512  ItemPointerSetMin(&key->curItem);
513  key->curItemMatches = false;
514  key->recheckCurItem = false;
515  key->isFinished = false;
516 
517  /*
518  * Divide the entries into two distinct sets: required and additional.
519  * Additional entries are not enough for a match alone, without any items
520  * from the required set, but are needed by the consistent function to
521  * decide if an item matches. When scanning, we can skip over items from
522  * additional entries that have no corresponding matches in any of the
523  * required entries. That speeds up queries like "frequent & rare"
524  * considerably, if the frequent term can be put in the additional set.
525  *
526  * There can be many legal ways to divide them entries into these two
527  * sets. A conservative division is to just put everything in the required
528  * set, but the more you can put in the additional set, the more you can
529  * skip during the scan. To maximize skipping, we try to put as many
530  * frequent items as possible into additional, and less frequent ones into
531  * required. To do that, sort the entries by frequency
532  * (predictNumberResult), and put entries into the required set in that
533  * order, until the consistent function says that none of the remaining
534  * entries can form a match, without any items from the required set. The
535  * rest go to the additional set.
536  *
537  * Exclude-only scan keys are known to have no required entries.
538  */
539  if (key->excludeOnly)
540  {
542 
543  key->nrequired = 0;
544  key->nadditional = key->nentries;
545  key->additionalEntries = palloc(key->nadditional * sizeof(GinScanEntry));
546  for (i = 0; i < key->nadditional; i++)
547  key->additionalEntries[i] = key->scanEntry[i];
548  }
549  else if (key->nentries > 1)
550  {
552 
553  entryIndexes = (int *) palloc(sizeof(int) * key->nentries);
554  for (i = 0; i < key->nentries; i++)
555  entryIndexes[i] = i;
556  qsort_arg(entryIndexes, key->nentries, sizeof(int),
558 
559  for (i = 0; i < key->nentries - 1; i++)
560  {
561  /* Pass all entries <= i as FALSE, and the rest as MAYBE */
562  for (j = 0; j <= i; j++)
563  key->entryRes[entryIndexes[j]] = GIN_FALSE;
564  for (j = i + 1; j < key->nentries; j++)
565  key->entryRes[entryIndexes[j]] = GIN_MAYBE;
566 
567  if (key->triConsistentFn(key) == GIN_FALSE)
568  break;
569  }
570  /* i is now the last required entry. */
571 
573 
574  key->nrequired = i + 1;
575  key->nadditional = key->nentries - key->nrequired;
576  key->requiredEntries = palloc(key->nrequired * sizeof(GinScanEntry));
577  key->additionalEntries = palloc(key->nadditional * sizeof(GinScanEntry));
578 
579  j = 0;
580  for (i = 0; i < key->nrequired; i++)
581  key->requiredEntries[i] = key->scanEntry[entryIndexes[j++]];
582  for (i = 0; i < key->nadditional; i++)
583  key->additionalEntries[i] = key->scanEntry[entryIndexes[j++]];
584 
585  /* clean up after consistentFn calls (also frees entryIndexes) */
587  }
588  else
589  {
591 
592  key->nrequired = 1;
593  key->nadditional = 0;
594  key->requiredEntries = palloc(1 * sizeof(GinScanEntry));
595  key->requiredEntries[0] = key->scanEntry[0];
596  }
597  MemoryContextSwitchTo(oldCtx);
598 }
static int entryIndexByFrequencyCmp(const void *a1, const void *a2, void *arg)
Definition: ginget.c:488
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
MemoryContext CurrentMemoryContext
Definition: mcxt.c:135
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
MemoryContext keyCtx
Definition: gin_private.h:380

References CurrentMemoryContext, entryIndexByFrequencyCmp(), GIN_FALSE, GIN_MAYBE, i, if(), ItemPointerSetMin, j, sort-test::key, GinScanOpaqueData::keyCtx, MemoryContextReset(), MemoryContextSwitchTo(), palloc(), qsort_arg(), and GinScanOpaqueData::tempCtx.

Referenced by startScan().

Variable Documentation

◆ GinFuzzySearchLimit

int GinFuzzySearchLimit = 0

Definition at line 27 of file ginget.c.

Referenced by startScan().