PostgreSQL Source Code  git master
ginget.c File Reference
#include "postgres.h"
#include "access/gin_private.h"
#include "access/relscan.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()   (((double) random()) / ((double) MAX_RANDOM_VALUE))
 
#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 775 of file ginget.c.

Referenced by entryGetItem().

◆ gin_rand

#define gin_rand ( )    (((double) random()) / ((double) MAX_RANDOM_VALUE))

Definition at line 774 of file ginget.c.

◆ GinIsVoidRes

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

Definition at line 1846 of file ginget.c.

Referenced by gingetbitmap().

Typedef Documentation

◆ pendingPosition

Function Documentation

◆ collectMatchBitmap()

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

Definition at line 120 of file ginget.c.

References attnum, GinScanEntryData::attnum, GinBtreeStack::buffer, BufferGetPage, cmp(), GinState::comparePartialFn, datumCopy(), DatumGetInt32, DatumGetPointer, elog, 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, scanPostingTree(), GinScanEntryData::searchMode, GinScanEntryData::strategy, GinState::supportCollation, tbm_add_tuples(), tbm_create(), TestForOldSnapshot(), TupleDescAttr, UInt16GetDatum, and work_mem.

Referenced by startScanEntry().

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
239  * a 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 }
#define GIN_UNLOCK
Definition: gin_private.h:43
Oid supportCollation[INDEX_MAX_KEYS]
Definition: gin_private.h:82
void PredicateLockPage(Relation relation, BlockNumber blkno, Snapshot snapshot)
Definition: predicate.c:2475
static void TestForOldSnapshot(Snapshot snapshot, Relation relation, Page page)
Definition: bufmgr.h:265
GinState * ginstate
Definition: gin_private.h:162
uint32 predictNumberResult
Definition: gin_private.h:342
#define DatumGetInt32(X)
Definition: postgres.h:457
OffsetNumber off
Definition: gin_private.h:126
#define PointerGetDatum(X)
Definition: postgres.h:541
TIDBitmap * tbm_create(long maxbytes, dsa_area *dsa)
Definition: tidbitmap.c:265
#define TupleDescAttr(tupdesc, i)
Definition: tupdesc.h:93
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:376
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:319
#define GinGetNPosting(itup)
Definition: ginblock.h:222
Datum FunctionCall4Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2, Datum arg3, Datum arg4)
Definition: fmgr.c:1180
uint32 BlockNumber
Definition: block.h:31
signed int int32
Definition: c.h:313
uint16 OffsetNumber
Definition: off.h:24
#define GIN_SEARCH_MODE_ALL
Definition: gin.h:35
void pfree(void *pointer)
Definition: mcxt.c:1031
#define ERROR
Definition: elog.h:43
signed char GinNullCategory
Definition: ginblock.h:200
OffsetNumber attnum
Definition: gin_private.h:322
OffsetNumber gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple)
Definition: ginutil.c:217
#define GIN_CAT_NORM_KEY
Definition: ginblock.h:202
FmgrInfo comparePartialFn[INDEX_MAX_KEYS]
Definition: gin_private.h:78
IndexTupleData * IndexTuple
Definition: itup.h:53
static void scanPostingTree(Relation index, GinScanEntry scanEntry, BlockNumber rootPostingTree, Snapshot snapshot)
Definition: ginget.c:68
FormData_pg_attribute * Form_pg_attribute
Definition: pg_attribute.h:197
#define GinPageIsLeaf(page)
Definition: ginblock.h:111
Datum gintuple_get_key(GinState *ginstate, IndexTuple tuple, GinNullCategory *category)
Definition: ginutil.c:250
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:128
#define GIN_SHARE
Definition: gin_private.h:44
TIDBitmap * matchBitmap
Definition: gin_private.h:331
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
uintptr_t Datum
Definition: postgres.h:367
StrategyNumber strategy
Definition: gin_private.h:320
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
#define GIN_CAT_NULL_ITEM
Definition: ginblock.h:205
int work_mem
Definition: globals.c:122
Relation index
Definition: gin_private.h:160
int16 attnum
Definition: pg_attribute.h:79
static bool moveRightIfItNeeded(GinBtreeData *btree, GinBtreeStack *stack, Snapshot snapshot)
Definition: ginget.c:42
GinNullCategory queryCategory
Definition: gin_private.h:317
ItemPointer ginReadTuple(GinState *ginstate, OffsetNumber attnum, IndexTuple itup, int *nitems)
Definition: ginentrypage.c:163
#define GinGetPostingTree(itup)
Definition: ginblock.h:227
#define DatumGetPointer(X)
Definition: postgres.h:534
#define GinIsPostingTree(itup)
Definition: ginblock.h:225
TupleDesc origTupdesc
Definition: gin_private.h:67
#define elog
Definition: elog.h:219
#define UInt16GetDatum(X)
Definition: postgres.h:450
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
Pointer Page
Definition: bufpage.h:74
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ collectMatchesForHeapRow()

static bool collectMatchesForHeapRow ( IndexScanDesc  scan,
pendingPosition pos 
)
static

Definition at line 1541 of file ginget.c.

References Assert, GinScanKeyData::attnum, GinScanEntryData::attnum, BufferGetPage, elog, GinScanKeyData::entryRes, ERROR, 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(), GinScanOpaqueData::keys, pendingPosition::lastOffset, matchPartialInPendingList(), GinScanKeyData::nentries, GinScanOpaqueData::nkeys, IndexScanDescData::opaque, PageGetItem, PageGetItemId, pendingPosition::pendingBuffer, GinScanEntryData::queryCategory, GinScanEntryData::queryKey, GinScanKeyData::scanEntry, scanGetCandidate(), GinScanEntryData::searchMode, TestForOldSnapshot(), and IndexScanDescData::xs_snapshot.

Referenced by scanPendingInsert().

1542 {
1543  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1544  OffsetNumber attrnum;
1545  Page page;
1546  IndexTuple itup;
1547  int i,
1548  j;
1549 
1550  /*
1551  * Reset all entryRes and hasMatchKey flags
1552  */
1553  for (i = 0; i < so->nkeys; i++)
1554  {
1555  GinScanKey key = so->keys + i;
1556 
1557  memset(key->entryRes, GIN_FALSE, key->nentries);
1558  }
1559  memset(pos->hasMatchKey, false, so->nkeys);
1560 
1561  /*
1562  * Outer loop iterates over multiple pending-list pages when a single heap
1563  * row has entries spanning those pages.
1564  */
1565  for (;;)
1566  {
1567  Datum datum[BLCKSZ / sizeof(IndexTupleData)];
1568  GinNullCategory category[BLCKSZ / sizeof(IndexTupleData)];
1569  bool datumExtracted[BLCKSZ / sizeof(IndexTupleData)];
1570 
1571  Assert(pos->lastOffset > pos->firstOffset);
1572  memset(datumExtracted + pos->firstOffset - 1, 0,
1573  sizeof(bool) * (pos->lastOffset - pos->firstOffset));
1574 
1575  page = BufferGetPage(pos->pendingBuffer);
1576  TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
1577 
1578  for (i = 0; i < so->nkeys; i++)
1579  {
1580  GinScanKey key = so->keys + i;
1581 
1582  for (j = 0; j < key->nentries; j++)
1583  {
1584  GinScanEntry entry = key->scanEntry[j];
1585  OffsetNumber StopLow = pos->firstOffset,
1586  StopHigh = pos->lastOffset,
1587  StopMiddle;
1588 
1589  /* If already matched on earlier page, do no extra work */
1590  if (key->entryRes[j])
1591  continue;
1592 
1593  /*
1594  * Interesting tuples are from pos->firstOffset to
1595  * pos->lastOffset and they are ordered by (attnum, Datum) as
1596  * it's done in entry tree. So we can use binary search to
1597  * avoid linear scanning.
1598  */
1599  while (StopLow < StopHigh)
1600  {
1601  int res;
1602 
1603  StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
1604 
1605  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, StopMiddle));
1606 
1607  attrnum = gintuple_get_attrnum(&so->ginstate, itup);
1608 
1609  if (key->attnum < attrnum)
1610  {
1611  StopHigh = StopMiddle;
1612  continue;
1613  }
1614  if (key->attnum > attrnum)
1615  {
1616  StopLow = StopMiddle + 1;
1617  continue;
1618  }
1619 
1620  if (datumExtracted[StopMiddle - 1] == false)
1621  {
1622  datum[StopMiddle - 1] =
1623  gintuple_get_key(&so->ginstate, itup,
1624  &category[StopMiddle - 1]);
1625  datumExtracted[StopMiddle - 1] = true;
1626  }
1627 
1628  if (entry->queryCategory == GIN_CAT_EMPTY_QUERY)
1629  {
1630  /* special behavior depending on searchMode */
1631  if (entry->searchMode == GIN_SEARCH_MODE_ALL)
1632  {
1633  /* match anything except NULL_ITEM */
1634  if (category[StopMiddle - 1] == GIN_CAT_NULL_ITEM)
1635  res = -1;
1636  else
1637  res = 0;
1638  }
1639  else
1640  {
1641  /* match everything */
1642  res = 0;
1643  }
1644  }
1645  else
1646  {
1647  res = ginCompareEntries(&so->ginstate,
1648  entry->attnum,
1649  entry->queryKey,
1650  entry->queryCategory,
1651  datum[StopMiddle - 1],
1652  category[StopMiddle - 1]);
1653  }
1654 
1655  if (res == 0)
1656  {
1657  /*
1658  * Found exact match (there can be only one, except in
1659  * EMPTY_QUERY mode).
1660  *
1661  * If doing partial match, scan forward from here to
1662  * end of page to check for matches.
1663  *
1664  * See comment above about tuple's ordering.
1665  */
1666  if (entry->isPartialMatch)
1667  key->entryRes[j] =
1669  page,
1670  StopMiddle,
1671  pos->lastOffset,
1672  entry,
1673  datum,
1674  category,
1675  datumExtracted);
1676  else
1677  key->entryRes[j] = true;
1678 
1679  /* done with binary search */
1680  break;
1681  }
1682  else if (res < 0)
1683  StopHigh = StopMiddle;
1684  else
1685  StopLow = StopMiddle + 1;
1686  }
1687 
1688  if (StopLow >= StopHigh && entry->isPartialMatch)
1689  {
1690  /*
1691  * No exact match on this page. If doing partial match,
1692  * scan from the first tuple greater than target value to
1693  * end of page. Note that since we don't remember whether
1694  * the comparePartialFn told us to stop early on a
1695  * previous page, we will uselessly apply comparePartialFn
1696  * to the first tuple on each subsequent page.
1697  */
1698  key->entryRes[j] =
1700  page,
1701  StopHigh,
1702  pos->lastOffset,
1703  entry,
1704  datum,
1705  category,
1706  datumExtracted);
1707  }
1708 
1709  pos->hasMatchKey[i] |= key->entryRes[j];
1710  }
1711  }
1712 
1713  /* Advance firstOffset over the scanned tuples */
1714  pos->firstOffset = pos->lastOffset;
1715 
1716  if (GinPageHasFullRow(page))
1717  {
1718  /*
1719  * We have examined all pending entries for the current heap row.
1720  * Break out of loop over pages.
1721  */
1722  break;
1723  }
1724  else
1725  {
1726  /*
1727  * Advance to next page of pending entries for the current heap
1728  * row. Complain if there isn't one.
1729  */
1730  ItemPointerData item = pos->item;
1731 
1732  if (scanGetCandidate(scan, pos) == false ||
1733  !ItemPointerEquals(&pos->item, &item))
1734  elog(ERROR, "could not find additional pending pages for same heap tuple");
1735  }
1736  }
1737 
1738  /*
1739  * Now return "true" if all scan keys have at least one matching datum
1740  */
1741  for (i = 0; i < so->nkeys; i++)
1742  {
1743  if (pos->hasMatchKey[i] == false)
1744  return false;
1745  }
1746 
1747  return true;
1748 }
#define GinPageHasFullRow(page)
Definition: ginblock.h:118
#define GIN_CAT_EMPTY_QUERY
Definition: ginblock.h:206
static void TestForOldSnapshot(Snapshot snapshot, Relation relation, Page page)
Definition: bufmgr.h:265
Buffer pendingBuffer
Definition: ginget.c:30
static bool matchPartialInPendingList(GinState *ginstate, Page page, OffsetNumber off, OffsetNumber maxoff, GinScanEntry entry, Datum *datum, GinNullCategory *category, bool *datumExtracted)
Definition: ginget.c:1473
Snapshot xs_snapshot
Definition: relscan.h:92
int ginCompareEntries(GinState *ginstate, OffsetNumber attnum, Datum a, GinNullCategory categorya, Datum b, GinNullCategory categoryb)
Definition: ginutil.c:393
Relation indexRelation
Definition: relscan.h:91
uint16 OffsetNumber
Definition: off.h:24
GinScanEntry * scanEntry
Definition: gin_private.h:267
#define GIN_SEARCH_MODE_ALL
Definition: gin.h:35
#define ERROR
Definition: elog.h:43
signed char GinNullCategory
Definition: ginblock.h:200
OffsetNumber attnum
Definition: gin_private.h:322
OffsetNumber gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple)
Definition: ginutil.c:217
GinScanOpaqueData * GinScanOpaque
Definition: gin_private.h:363
IndexTupleData * IndexTuple
Definition: itup.h:53
GinTernaryValue * entryRes
Definition: gin_private.h:283
OffsetNumber firstOffset
Definition: ginget.c:31
OffsetNumber attnum
Definition: gin_private.h:298
Datum gintuple_get_key(GinState *ginstate, IndexTuple tuple, GinNullCategory *category)
Definition: ginutil.c:250
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
bool * hasMatchKey
Definition: ginget.c:34
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
GinScanKey keys
Definition: gin_private.h:351
uintptr_t Datum
Definition: postgres.h:367
struct IndexTupleData IndexTupleData
#define GIN_CAT_NULL_ITEM
Definition: ginblock.h:205
#define Assert(condition)
Definition: c.h:699
GinNullCategory queryCategory
Definition: gin_private.h:317
#define GIN_FALSE
Definition: gin.h:59
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
Definition: itemptr.c:29
int i
#define elog
Definition: elog.h:219
static bool scanGetCandidate(IndexScanDesc scan, pendingPosition *pos)
Definition: ginget.c:1385
ItemPointerData item
Definition: ginget.c:33
OffsetNumber lastOffset
Definition: ginget.c:32
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
Pointer Page
Definition: bufpage.h:74

◆ entryGetItem()

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

Definition at line 791 of file ginget.c.

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().

793 {
794  Assert(!entry->isFinished);
795 
796  Assert(!ItemPointerIsValid(&entry->curItem) ||
797  ginCompareItemPointers(&entry->curItem, &advancePast) <= 0);
798 
799  if (entry->matchBitmap)
800  {
801  /* A bitmap result */
802  BlockNumber advancePastBlk = GinItemPointerGetBlockNumber(&advancePast);
803  OffsetNumber advancePastOff = GinItemPointerGetOffsetNumber(&advancePast);
804  bool gotitem = false;
805 
806  do
807  {
808  /*
809  * If we've exhausted all items on this block, move to next block
810  * in the bitmap.
811  */
812  while (entry->matchResult == NULL ||
813  (entry->matchResult->ntuples >= 0 &&
814  entry->offset >= entry->matchResult->ntuples) ||
815  entry->matchResult->blockno < advancePastBlk ||
816  (ItemPointerIsLossyPage(&advancePast) &&
817  entry->matchResult->blockno == advancePastBlk))
818  {
819  entry->matchResult = tbm_iterate(entry->matchIterator);
820 
821  if (entry->matchResult == NULL)
822  {
825  entry->matchIterator = NULL;
826  entry->isFinished = true;
827  break;
828  }
829 
830  /*
831  * Reset counter to the beginning of entry->matchResult. Note:
832  * entry->offset is still greater than matchResult->ntuples if
833  * matchResult is lossy. So, on next call we will get next
834  * result from TIDBitmap.
835  */
836  entry->offset = 0;
837  }
838  if (entry->isFinished)
839  break;
840 
841  /*
842  * We're now on the first page after advancePast which has any
843  * items on it. If it's a lossy result, return that.
844  */
845  if (entry->matchResult->ntuples < 0)
846  {
848  entry->matchResult->blockno);
849 
850  /*
851  * We might as well fall out of the loop; we could not
852  * estimate number of results on this page to support correct
853  * reducing of result even if it's enabled.
854  */
855  gotitem = true;
856  break;
857  }
858 
859  /*
860  * Not a lossy page. Skip over any offsets <= advancePast, and
861  * return that.
862  */
863  if (entry->matchResult->blockno == advancePastBlk)
864  {
865  /*
866  * First, do a quick check against the last offset on the
867  * page. If that's > advancePast, so are all the other
868  * offsets.
869  */
870  if (entry->matchResult->offsets[entry->matchResult->ntuples - 1] <= advancePastOff)
871  {
872  entry->offset = entry->matchResult->ntuples;
873  continue;
874  }
875 
876  /* Otherwise scan to find the first item > advancePast */
877  while (entry->matchResult->offsets[entry->offset] <= advancePastOff)
878  entry->offset++;
879  }
880 
881  ItemPointerSet(&entry->curItem,
882  entry->matchResult->blockno,
883  entry->matchResult->offsets[entry->offset]);
884  entry->offset++;
885  gotitem = true;
886  } while (!gotitem || (entry->reduceResult == true && dropItem(entry)));
887  }
888  else if (!BufferIsValid(entry->buffer))
889  {
890  /*
891  * A posting list from an entry tuple, or the last page of a posting
892  * tree.
893  */
894  do
895  {
896  if (entry->offset >= entry->nlist)
897  {
899  entry->isFinished = true;
900  break;
901  }
902 
903  entry->curItem = entry->list[entry->offset++];
904  } while (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0);
905  /* XXX: shouldn't we apply the fuzzy search limit here? */
906  }
907  else
908  {
909  /* A posting tree */
910  do
911  {
912  /* If we've processed the current batch, load more items */
913  while (entry->offset >= entry->nlist)
914  {
915  entryLoadMoreItems(ginstate, entry, advancePast, snapshot);
916 
917  if (entry->isFinished)
918  {
920  return;
921  }
922  }
923 
924  entry->curItem = entry->list[entry->offset++];
925 
926  } while (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0 ||
927  (entry->reduceResult == true && dropItem(entry)));
928  }
929 }
#define ItemPointerIsValid(pointer)
Definition: itemptr.h:82
ItemPointerData curItem
Definition: gin_private.h:328
void tbm_end_iterate(TBMIterator *iterator)
Definition: tidbitmap.c:1145
OffsetNumber offset
Definition: gin_private.h:338
#define dropItem(e)
Definition: ginget.c:775
#define GinItemPointerGetOffsetNumber(pointer)
Definition: ginblock.h:137
TBMIterator * matchIterator
Definition: gin_private.h:332
#define ItemPointerIsLossyPage(p)
Definition: ginblock.h:169
uint32 BlockNumber
Definition: block.h:31
ItemPointerData * list
Definition: gin_private.h:336
uint16 OffsetNumber
Definition: off.h:24
BlockNumber blockno
Definition: tidbitmap.h:42
#define ItemPointerSetLossyPage(p, b)
Definition: ginblock.h:167
OffsetNumber offsets[FLEXIBLE_ARRAY_MEMBER]
Definition: tidbitmap.h:46
static void entryLoadMoreItems(GinState *ginstate, GinScanEntry entry, ItemPointerData advancePast, Snapshot snapshot)
Definition: ginget.c:636
TIDBitmap * matchBitmap
Definition: gin_private.h:331
TBMIterateResult * matchResult
Definition: gin_private.h:333
TBMIterateResult * tbm_iterate(TBMIterator *iterator)
Definition: tidbitmap.c:970
#define Assert(condition)
Definition: c.h:699
#define BufferIsValid(bufnum)
Definition: bufmgr.h:114
static int ginCompareItemPointers(ItemPointer a, ItemPointer b)
Definition: gin_private.h:460
#define ItemPointerSetInvalid(pointer)
Definition: itemptr.h:172
#define GinItemPointerGetBlockNumber(pointer)
Definition: ginblock.h:134
#define ItemPointerSet(pointer, blockNumber, offNum)
Definition: itemptr.h:127

◆ entryIndexByFrequencyCmp()

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

Definition at line 483 of file ginget.c.

References GinScanEntryData::predictNumberResult, and GinScanKeyData::scanEntry.

Referenced by startScanKey().

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 }
uint32 predictNumberResult
Definition: gin_private.h:342
GinScanEntry * scanEntry
Definition: gin_private.h:267
struct GinScanKeyData * GinScanKey
Definition: gin_private.h:255
unsigned int uint32
Definition: c.h:325
static FormData_pg_attribute a1
Definition: heap.c:147
void * arg
static FormData_pg_attribute a2
Definition: heap.c:153

◆ entryLoadMoreItems()

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

Definition at line 636 of file ginget.c.

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().

638 {
639  Page page;
640  int i;
641  bool stepright;
642 
643  if (!BufferIsValid(entry->buffer))
644  {
645  entry->isFinished = true;
646  return;
647  }
648 
649  /*
650  * We have two strategies for finding the correct page: step right from
651  * the current page, or descend the tree again from the root. If
652  * advancePast equals the current item, the next matching item should be
653  * on the next page, so we step right. Otherwise, descend from root.
654  */
655  if (ginCompareItemPointers(&entry->curItem, &advancePast) == 0)
656  {
657  stepright = true;
658  LockBuffer(entry->buffer, GIN_SHARE);
659  }
660  else
661  {
662  GinBtreeStack *stack;
663 
664  ReleaseBuffer(entry->buffer);
665 
666  /*
667  * Set the search key, and find the correct leaf page.
668  */
669  if (ItemPointerIsLossyPage(&advancePast))
670  {
671  ItemPointerSet(&entry->btree.itemptr,
672  GinItemPointerGetBlockNumber(&advancePast) + 1,
674  }
675  else
676  {
677  ItemPointerSet(&entry->btree.itemptr,
678  GinItemPointerGetBlockNumber(&advancePast),
680  }
681  entry->btree.fullScan = false;
682  stack = ginFindLeafPage(&entry->btree, true, snapshot);
683 
684  /* we don't need the stack, just the buffer. */
685  entry->buffer = stack->buffer;
686  IncrBufferRefCount(entry->buffer);
687  freeGinBtreeStack(stack);
688  stepright = false;
689  }
690 
691  elog(DEBUG2, "entryLoadMoreItems, %u/%u, skip: %d",
692  GinItemPointerGetBlockNumber(&advancePast),
693  GinItemPointerGetOffsetNumber(&advancePast),
694  !stepright);
695 
696  page = BufferGetPage(entry->buffer);
697  for (;;)
698  {
699  entry->offset = InvalidOffsetNumber;
700  if (entry->list)
701  {
702  pfree(entry->list);
703  entry->list = NULL;
704  entry->nlist = 0;
705  }
706 
707  if (stepright)
708  {
709  /*
710  * We've processed all the entries on this page. If it was the
711  * last page in the tree, we're done.
712  */
713  if (GinPageRightMost(page))
714  {
715  UnlockReleaseBuffer(entry->buffer);
716  entry->buffer = InvalidBuffer;
717  entry->isFinished = true;
718  return;
719  }
720 
721  /*
722  * Step to next page, following the right link. then find the
723  * first ItemPointer greater than advancePast.
724  */
725  entry->buffer = ginStepRight(entry->buffer,
726  ginstate->index,
727  GIN_SHARE);
728  page = BufferGetPage(entry->buffer);
729  }
730  stepright = true;
731 
732  if (GinPageGetOpaque(page)->flags & GIN_DELETED)
733  continue; /* page was deleted by concurrent vacuum */
734 
735  /*
736  * The first item > advancePast might not be on this page, but
737  * somewhere to the right, if the page was split, or a non-match from
738  * another key in the query allowed us to skip some items from this
739  * entry. Keep following the right-links until we re-find the correct
740  * page.
741  */
742  if (!GinPageRightMost(page) &&
743  ginCompareItemPointers(&advancePast, GinDataPageGetRightBound(page)) >= 0)
744  {
745  /*
746  * the item we're looking is > the right bound of the page, so it
747  * can't be on this page.
748  */
749  continue;
750  }
751 
752  entry->list = GinDataLeafPageGetItems(page, &entry->nlist, advancePast);
753 
754  for (i = 0; i < entry->nlist; i++)
755  {
756  if (ginCompareItemPointers(&advancePast, &entry->list[i]) < 0)
757  {
758  entry->offset = i;
759 
760  if (GinPageRightMost(page))
761  {
762  /* after processing the copied items, we're done. */
763  UnlockReleaseBuffer(entry->buffer);
764  entry->buffer = InvalidBuffer;
765  }
766  else
767  LockBuffer(entry->buffer, GIN_UNLOCK);
768  return;
769  }
770  }
771  }
772 }
#define GIN_UNLOCK
Definition: gin_private.h:43
#define GIN_DELETED
Definition: ginblock.h:41
GinBtreeData btree
Definition: gin_private.h:343
ItemPointerData curItem
Definition: gin_private.h:328
OffsetNumber offset
Definition: gin_private.h:338
Relation index
Definition: gin_private.h:53
#define GinItemPointerGetOffsetNumber(pointer)
Definition: ginblock.h:137
#define InvalidBuffer
Definition: buf.h:25
#define ItemPointerIsLossyPage(p)
Definition: ginblock.h:169
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3309
#define GinPageGetOpaque(page)
Definition: ginblock.h:109
ItemPointerData * list
Definition: gin_private.h:336
GinBtreeStack * ginFindLeafPage(GinBtree btree, bool searchMode, Snapshot snapshot)
Definition: ginbtree.c:77
void pfree(void *pointer)
Definition: mcxt.c:1031
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3332
#define GinPageRightMost(page)
Definition: ginblock.h:128
#define DEBUG2
Definition: elog.h:24
#define FirstOffsetNumber
Definition: off.h:27
Buffer ginStepRight(Buffer buffer, Relation index, int lockmode)
Definition: ginbtree.c:169
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define GIN_SHARE
Definition: gin_private.h:44
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
#define InvalidOffsetNumber
Definition: off.h:26
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
#define BufferIsValid(bufnum)
Definition: bufmgr.h:114
static int ginCompareItemPointers(ItemPointer a, ItemPointer b)
Definition: gin_private.h:460
#define GinDataPageGetRightBound(page)
Definition: ginblock.h:282
void freeGinBtreeStack(GinBtreeStack *stack)
Definition: ginbtree.c:197
ItemPointerData itemptr
Definition: gin_private.h:172
int i
ItemPointer GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerData advancePast)
Definition: gindatapage.c:135
#define elog
Definition: elog.h:219
#define GinItemPointerGetBlockNumber(pointer)
Definition: ginblock.h:134
void IncrBufferRefCount(Buffer buffer)
Definition: bufmgr.c:3347
Pointer Page
Definition: bufpage.h:74
#define ItemPointerSet(pointer, blockNumber, offNum)
Definition: itemptr.h:127

◆ gingetbitmap()

int64 gingetbitmap ( IndexScanDesc  scan,
TIDBitmap tbm 
)

Definition at line 1849 of file ginget.c.

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().

1850 {
1851  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1852  int64 ntids;
1853  ItemPointerData iptr;
1854  bool recheck;
1855 
1856  /*
1857  * Set up the scan keys, and check for unsatisfiable query.
1858  */
1859  ginFreeScanKeys(so); /* there should be no keys yet, but just to be
1860  * sure */
1861  ginNewScanKey(scan);
1862 
1863  if (GinIsVoidRes(scan))
1864  return 0;
1865 
1866  ntids = 0;
1867 
1868  /*
1869  * First, scan the pending list and collect any matching entries into the
1870  * bitmap. After we scan a pending item, some other backend could post it
1871  * into the main index, and so we might visit it a second time during the
1872  * main scan. This is okay because we'll just re-set the same bit in the
1873  * bitmap. (The possibility of duplicate visits is a major reason why GIN
1874  * can't support the amgettuple API, however.) Note that it would not do
1875  * to scan the main index before the pending list, since concurrent
1876  * cleanup could then make us miss entries entirely.
1877  */
1878  scanPendingInsert(scan, tbm, &ntids);
1879 
1880  /*
1881  * Now scan the main index.
1882  */
1883  startScan(scan);
1884 
1885  ItemPointerSetMin(&iptr);
1886 
1887  for (;;)
1888  {
1890 
1891  if (!scanGetItem(scan, iptr, &iptr, &recheck))
1892  break;
1893 
1894  if (ItemPointerIsLossyPage(&iptr))
1896  else
1897  tbm_add_tuples(tbm, &iptr, 1, recheck);
1898  ntids++;
1899  }
1900 
1901  return ntids;
1902 }
static void scanPendingInsert(IndexScanDesc scan, TIDBitmap *tbm, int64 *ntids)
Definition: ginget.c:1754
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:376
#define ItemPointerIsLossyPage(p)
Definition: ginblock.h:169
static void startScan(IndexScanDesc scan)
Definition: ginget.c:584
GinScanOpaqueData * GinScanOpaque
Definition: gin_private.h:363
#define ItemPointerSetMin(p)
Definition: ginblock.h:157
static bool scanGetItem(IndexScanDesc scan, ItemPointerData advancePast, ItemPointerData *item, bool *recheck)
Definition: ginget.c:1233
void ginNewScanKey(IndexScanDesc scan)
Definition: ginscan.c:262
#define GinIsVoidRes(s)
Definition: ginget.c:1846
void tbm_add_page(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:442
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:98
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:98
void ginFreeScanKeys(GinScanOpaque so)
Definition: ginscan.c:232

◆ keyGetItem()

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

Definition at line 953 of file ginget.c.

References GinScanKeyData::additionalEntries, Assert, GinScanKeyData::curItem, GinScanEntryData::curItem, GinScanKeyData::curItemMatches, entryGetItem(), GinScanKeyData::entryRes, GIN_FALSE, GIN_MAYBE, GIN_TRUE, ginCompareItemPointers(), GinItemPointerGetBlockNumber, GinItemPointerGetOffsetNumber, i, InvalidOffsetNumber, GinScanKeyData::isFinished, GinScanEntryData::isFinished, ItemPointerIsLossyPage, ItemPointerSet, ItemPointerSetLossyPage, ItemPointerSetMax, MemoryContextReset(), MemoryContextSwitchTo(), GinScanKeyData::nadditional, GinScanKeyData::nentries, GinScanKeyData::nrequired, OffsetNumberPrev, GinScanKeyData::recheckCurItem, GinScanKeyData::requiredEntries, GinScanKeyData::scanEntry, and GinScanKeyData::triConsistentFn.

Referenced by scanGetItem().

955 {
956  ItemPointerData minItem;
957  ItemPointerData curPageLossy;
958  uint32 i;
959  bool haveLossyEntry;
960  GinScanEntry entry;
961  GinTernaryValue res;
962  MemoryContext oldCtx;
963  bool allFinished;
964 
965  Assert(!key->isFinished);
966 
967  /*
968  * We might have already tested this item; if so, no need to repeat work.
969  * (Note: the ">" case can happen, if advancePast is exact but we
970  * previously had to set curItem to a lossy-page pointer.)
971  */
972  if (ginCompareItemPointers(&key->curItem, &advancePast) > 0)
973  return;
974 
975  /*
976  * Find the minimum item > advancePast among the active entry streams.
977  *
978  * Note: a lossy-page entry is encoded by a ItemPointer with max value for
979  * offset (0xffff), so that it will sort after any exact entries for the
980  * same page. So we'll prefer to return exact pointers not lossy
981  * pointers, which is good.
982  */
983  ItemPointerSetMax(&minItem);
984  allFinished = true;
985  for (i = 0; i < key->nrequired; i++)
986  {
987  entry = key->requiredEntries[i];
988 
989  if (entry->isFinished)
990  continue;
991 
992  /*
993  * Advance this stream if necessary.
994  *
995  * In particular, since entry->curItem was initialized with
996  * ItemPointerSetMin, this ensures we fetch the first item for each
997  * entry on the first call.
998  */
999  if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
1000  {
1001  entryGetItem(ginstate, entry, advancePast, snapshot);
1002  if (entry->isFinished)
1003  continue;
1004  }
1005 
1006  allFinished = false;
1007  if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
1008  minItem = entry->curItem;
1009  }
1010 
1011  if (allFinished)
1012  {
1013  /* all entries are finished */
1014  key->isFinished = true;
1015  return;
1016  }
1017 
1018  /*
1019  * Ok, we now know that there are no matches < minItem.
1020  *
1021  * If minItem is lossy, it means that there were no exact items on the
1022  * page among requiredEntries, because lossy pointers sort after exact
1023  * items. However, there might be exact items for the same page among
1024  * additionalEntries, so we mustn't advance past them.
1025  */
1026  if (ItemPointerIsLossyPage(&minItem))
1027  {
1028  if (GinItemPointerGetBlockNumber(&advancePast) <
1029  GinItemPointerGetBlockNumber(&minItem))
1030  {
1031  ItemPointerSet(&advancePast,
1032  GinItemPointerGetBlockNumber(&minItem),
1034  }
1035  }
1036  else
1037  {
1038  Assert(GinItemPointerGetOffsetNumber(&minItem) > 0);
1039  ItemPointerSet(&advancePast,
1040  GinItemPointerGetBlockNumber(&minItem),
1042  }
1043 
1044  /*
1045  * We might not have loaded all the entry streams for this TID yet. We
1046  * could call the consistent function, passing MAYBE for those entries, to
1047  * see if it can decide if this TID matches based on the information we
1048  * have. But if the consistent-function is expensive, and cannot in fact
1049  * decide with partial information, that could be a big loss. So, load all
1050  * the additional entries, before calling the consistent function.
1051  */
1052  for (i = 0; i < key->nadditional; i++)
1053  {
1054  entry = key->additionalEntries[i];
1055 
1056  if (entry->isFinished)
1057  continue;
1058 
1059  if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
1060  {
1061  entryGetItem(ginstate, entry, advancePast, snapshot);
1062  if (entry->isFinished)
1063  continue;
1064  }
1065 
1066  /*
1067  * Normally, none of the items in additionalEntries can have a curItem
1068  * larger than minItem. But if minItem is a lossy page, then there
1069  * might be exact items on the same page among additionalEntries.
1070  */
1071  if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
1072  {
1073  Assert(ItemPointerIsLossyPage(&minItem));
1074  minItem = entry->curItem;
1075  }
1076  }
1077 
1078  /*
1079  * Ok, we've advanced all the entries up to minItem now. Set key->curItem,
1080  * and perform consistentFn test.
1081  *
1082  * Lossy-page entries pose a problem, since we don't know the correct
1083  * entryRes state to pass to the consistentFn, and we also don't know what
1084  * its combining logic will be (could be AND, OR, or even NOT). If the
1085  * logic is OR then the consistentFn might succeed for all items in the
1086  * lossy page even when none of the other entries match.
1087  *
1088  * Our strategy is to call the tri-state consistent function, with the
1089  * lossy-page entries set to MAYBE, and all the other entries FALSE. If it
1090  * returns FALSE, none of the lossy items alone are enough for a match, so
1091  * we don't need to return a lossy-page pointer. Otherwise, return a
1092  * lossy-page pointer to indicate that the whole heap page must be
1093  * checked. (On subsequent calls, we'll do nothing until minItem is past
1094  * the page altogether, thus ensuring that we never return both regular
1095  * and lossy pointers for the same page.)
1096  *
1097  * An exception is that it doesn't matter what we pass for lossy pointers
1098  * in "hidden" entries, because the consistentFn's result can't depend on
1099  * them. We could pass them as MAYBE as well, but if we're using the
1100  * "shim" implementation of a tri-state consistent function (see
1101  * ginlogic.c), it's better to pass as few MAYBEs as possible. So pass
1102  * them as true.
1103  *
1104  * Note that only lossy-page entries pointing to the current item's page
1105  * should trigger this processing; we might have future lossy pages in the
1106  * entry array, but they aren't relevant yet.
1107  */
1108  key->curItem = minItem;
1109  ItemPointerSetLossyPage(&curPageLossy,
1111  haveLossyEntry = false;
1112  for (i = 0; i < key->nentries; i++)
1113  {
1114  entry = key->scanEntry[i];
1115  if (entry->isFinished == false &&
1116  ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0)
1117  {
1118  if (i < key->nuserentries)
1119  key->entryRes[i] = GIN_MAYBE;
1120  else
1121  key->entryRes[i] = GIN_TRUE;
1122  haveLossyEntry = true;
1123  }
1124  else
1125  key->entryRes[i] = GIN_FALSE;
1126  }
1127 
1128  /* prepare for calling consistentFn in temp context */
1129  oldCtx = MemoryContextSwitchTo(tempCtx);
1130 
1131  if (haveLossyEntry)
1132  {
1133  /* Have lossy-page entries, so see if whole page matches */
1134  res = key->triConsistentFn(key);
1135 
1136  if (res == GIN_TRUE || res == GIN_MAYBE)
1137  {
1138  /* Yes, so clean up ... */
1139  MemoryContextSwitchTo(oldCtx);
1140  MemoryContextReset(tempCtx);
1141 
1142  /* and return lossy pointer for whole page */
1143  key->curItem = curPageLossy;
1144  key->curItemMatches = true;
1145  key->recheckCurItem = true;
1146  return;
1147  }
1148  }
1149 
1150  /*
1151  * At this point we know that we don't need to return a lossy whole-page
1152  * pointer, but we might have matches for individual exact item pointers,
1153  * possibly in combination with a lossy pointer. Pass lossy pointers as
1154  * MAYBE to the ternary consistent function, to let it decide if this
1155  * tuple satisfies the overall key, even though we don't know if the lossy
1156  * entries match.
1157  *
1158  * Prepare entryRes array to be passed to consistentFn.
1159  */
1160  for (i = 0; i < key->nentries; i++)
1161  {
1162  entry = key->scanEntry[i];
1163  if (entry->isFinished)
1164  key->entryRes[i] = GIN_FALSE;
1165 #if 0
1166 
1167  /*
1168  * This case can't currently happen, because we loaded all the entries
1169  * for this item earlier.
1170  */
1171  else if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
1172  key->entryRes[i] = GIN_MAYBE;
1173 #endif
1174  else if (ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0)
1175  key->entryRes[i] = GIN_MAYBE;
1176  else if (ginCompareItemPointers(&entry->curItem, &minItem) == 0)
1177  key->entryRes[i] = GIN_TRUE;
1178  else
1179  key->entryRes[i] = GIN_FALSE;
1180  }
1181 
1182  res = key->triConsistentFn(key);
1183 
1184  switch (res)
1185  {
1186  case GIN_TRUE:
1187  key->curItemMatches = true;
1188  /* triConsistentFn set recheckCurItem */
1189  break;
1190 
1191  case GIN_FALSE:
1192  key->curItemMatches = false;
1193  break;
1194 
1195  case GIN_MAYBE:
1196  key->curItemMatches = true;
1197  key->recheckCurItem = true;
1198  break;
1199 
1200  default:
1201 
1202  /*
1203  * the 'default' case shouldn't happen, but if the consistent
1204  * function returns something bogus, this is the safe result
1205  */
1206  key->curItemMatches = true;
1207  key->recheckCurItem = true;
1208  break;
1209  }
1210 
1211  /*
1212  * We have a tuple, and we know if it matches or not. If it's a non-match,
1213  * we could continue to find the next matching tuple, but let's break out
1214  * and give scanGetItem a chance to advance the other keys. They might be
1215  * able to skip past to a much higher TID, allowing us to save work.
1216  */
1217 
1218  /* clean up after consistentFn calls */
1219  MemoryContextSwitchTo(oldCtx);
1220  MemoryContextReset(tempCtx);
1221 }
#define GIN_TRUE
Definition: gin.h:60
ItemPointerData curItem
Definition: gin_private.h:328
static void entryGetItem(GinState *ginstate, GinScanEntry entry, ItemPointerData advancePast, Snapshot snapshot)
Definition: ginget.c:791
#define GinItemPointerGetOffsetNumber(pointer)
Definition: ginblock.h:137
#define GIN_MAYBE
Definition: gin.h:61
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define ItemPointerIsLossyPage(p)
Definition: ginblock.h:169
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:136
GinScanEntry * scanEntry
Definition: gin_private.h:267
#define ItemPointerSetLossyPage(p, b)
Definition: ginblock.h:167
char GinTernaryValue
Definition: gin.h:57
GinTernaryValue * entryRes
Definition: gin_private.h:283
unsigned int uint32
Definition: c.h:325
GinScanEntry * requiredEntries
Definition: gin_private.h:277
#define InvalidOffsetNumber
Definition: off.h:26
GinTernaryValue(* triConsistentFn)(GinScanKey key)
Definition: gin_private.h:285
#define Assert(condition)
Definition: c.h:699
#define GIN_FALSE
Definition: gin.h:59
#define OffsetNumberPrev(offsetNumber)
Definition: off.h:55
ItemPointerData curItem
Definition: gin_private.h:307
#define ItemPointerSetMax(p)
Definition: ginblock.h:162
static int ginCompareItemPointers(ItemPointer a, ItemPointer b)
Definition: gin_private.h:460
GinScanEntry * additionalEntries
Definition: gin_private.h:279
int i
#define GinItemPointerGetBlockNumber(pointer)
Definition: ginblock.h:134
#define ItemPointerSet(pointer, blockNumber, offNum)
Definition: itemptr.h:127

◆ matchPartialInPendingList()

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

Definition at line 1473 of file ginget.c.

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().

1478 {
1479  IndexTuple itup;
1480  int32 cmp;
1481 
1482  /* Partial match to a null is not possible */
1483  if (entry->queryCategory != GIN_CAT_NORM_KEY)
1484  return false;
1485 
1486  while (off < maxoff)
1487  {
1488  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
1489 
1490  if (gintuple_get_attrnum(ginstate, itup) != entry->attnum)
1491  return false;
1492 
1493  if (datumExtracted[off - 1] == false)
1494  {
1495  datum[off - 1] = gintuple_get_key(ginstate, itup,
1496  &category[off - 1]);
1497  datumExtracted[off - 1] = true;
1498  }
1499 
1500  /* Once we hit nulls, no further match is possible */
1501  if (category[off - 1] != GIN_CAT_NORM_KEY)
1502  return false;
1503 
1504  /*----------
1505  * Check partial match.
1506  * case cmp == 0 => match
1507  * case cmp > 0 => not match and end scan (no later match possible)
1508  * case cmp < 0 => not match and continue scan
1509  *----------
1510  */
1511  cmp = DatumGetInt32(FunctionCall4Coll(&ginstate->comparePartialFn[entry->attnum - 1],
1512  ginstate->supportCollation[entry->attnum - 1],
1513  entry->queryKey,
1514  datum[off - 1],
1515  UInt16GetDatum(entry->strategy),
1516  PointerGetDatum(entry->extra_data)));
1517  if (cmp == 0)
1518  return true;
1519  else if (cmp > 0)
1520  return false;
1521 
1522  off++;
1523  }
1524 
1525  return false;
1526 }
Oid supportCollation[INDEX_MAX_KEYS]
Definition: gin_private.h:82
#define DatumGetInt32(X)
Definition: postgres.h:457
#define PointerGetDatum(X)
Definition: postgres.h:541
Pointer extra_data
Definition: gin_private.h:319
Datum FunctionCall4Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2, Datum arg3, Datum arg4)
Definition: fmgr.c:1180
signed int int32
Definition: c.h:313
OffsetNumber attnum
Definition: gin_private.h:322
OffsetNumber gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple)
Definition: ginutil.c:217
#define GIN_CAT_NORM_KEY
Definition: ginblock.h:202
FmgrInfo comparePartialFn[INDEX_MAX_KEYS]
Definition: gin_private.h:78
IndexTupleData * IndexTuple
Definition: itup.h:53
Datum gintuple_get_key(GinState *ginstate, IndexTuple tuple, GinNullCategory *category)
Definition: ginutil.c:250
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
StrategyNumber strategy
Definition: gin_private.h:320
GinNullCategory queryCategory
Definition: gin_private.h:317
#define UInt16GetDatum(X)
Definition: postgres.h:450
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ moveRightIfItNeeded()

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

Definition at line 42 of file ginget.c.

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

Referenced by collectMatchBitmap().

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 }
void PredicateLockPage(Relation relation, BlockNumber blkno, Snapshot snapshot)
Definition: predicate.c:2475
OffsetNumber off
Definition: gin_private.h:126
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:353
#define GinPageRightMost(page)
Definition: ginblock.h:128
#define FirstOffsetNumber
Definition: off.h:27
Buffer ginStepRight(Buffer buffer, Relation index, int lockmode)
Definition: ginbtree.c:169
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define GIN_SHARE
Definition: gin_private.h:44
Relation index
Definition: gin_private.h:160
BlockNumber blkno
Definition: gin_private.h:124
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2605
Pointer Page
Definition: bufpage.h:74

◆ scanGetCandidate()

static bool scanGetCandidate ( IndexScanDesc  scan,
pendingPosition pos 
)
static

Definition at line 1385 of file ginget.c.

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().

1386 {
1387  OffsetNumber maxoff;
1388  Page page;
1389  IndexTuple itup;
1390 
1391  ItemPointerSetInvalid(&pos->item);
1392  for (;;)
1393  {
1394  page = BufferGetPage(pos->pendingBuffer);
1395  TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
1396 
1397  maxoff = PageGetMaxOffsetNumber(page);
1398  if (pos->firstOffset > maxoff)
1399  {
1400  BlockNumber blkno = GinPageGetOpaque(page)->rightlink;
1401 
1402  if (blkno == InvalidBlockNumber)
1403  {
1406 
1407  return false;
1408  }
1409  else
1410  {
1411  /*
1412  * Here we must prevent deletion of next page by insertcleanup
1413  * process, which may be trying to obtain exclusive lock on
1414  * current page. So, we lock next page before releasing the
1415  * current one
1416  */
1417  Buffer tmpbuf = ReadBuffer(scan->indexRelation, blkno);
1418 
1419  LockBuffer(tmpbuf, GIN_SHARE);
1421 
1422  pos->pendingBuffer = tmpbuf;
1424  }
1425  }
1426  else
1427  {
1428  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->firstOffset));
1429  pos->item = itup->t_tid;
1430  if (GinPageHasFullRow(page))
1431  {
1432  /*
1433  * find itempointer to the next row
1434  */
1435  for (pos->lastOffset = pos->firstOffset + 1; pos->lastOffset <= maxoff; pos->lastOffset++)
1436  {
1437  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->lastOffset));
1438  if (!ItemPointerEquals(&pos->item, &itup->t_tid))
1439  break;
1440  }
1441  }
1442  else
1443  {
1444  /*
1445  * All itempointers are the same on this page
1446  */
1447  pos->lastOffset = maxoff + 1;
1448  }
1449 
1450  /*
1451  * Now pos->firstOffset points to the first tuple of current heap
1452  * row, pos->lastOffset points to the first tuple of next heap row
1453  * (or to the end of page)
1454  */
1455  break;
1456  }
1457  }
1458 
1459  return true;
1460 }
#define GinPageHasFullRow(page)
Definition: ginblock.h:118
static void TestForOldSnapshot(Snapshot snapshot, Relation relation, Page page)
Definition: bufmgr.h:265
Buffer pendingBuffer
Definition: ginget.c:30
ItemPointerData t_tid
Definition: itup.h:37
Snapshot xs_snapshot
Definition: relscan.h:92
#define InvalidBuffer
Definition: buf.h:25
uint32 BlockNumber
Definition: block.h:31
#define GinPageGetOpaque(page)
Definition: ginblock.h:109
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:353
Relation indexRelation
Definition: relscan.h:91
uint16 OffsetNumber
Definition: off.h:24
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3332
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
OffsetNumber firstOffset
Definition: ginget.c:31
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define GIN_SHARE
Definition: gin_private.h:44
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:594
#define InvalidBlockNumber
Definition: block.h:33
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
Definition: itemptr.c:29
static StringInfoData tmpbuf
Definition: walsender.c:163
#define ItemPointerSetInvalid(pointer)
Definition: itemptr.h:172
ItemPointerData item
Definition: ginget.c:33
int Buffer
Definition: buf.h:23
OffsetNumber lastOffset
Definition: ginget.c:32
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
Pointer Page
Definition: bufpage.h:74

◆ scanGetItem()

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

Definition at line 1233 of file ginget.c.

References Assert, GinScanKeyData::curItem, GinScanKeyData::curItemMatches, ginCompareItemPointers(), GinItemPointerGetBlockNumber, GinItemPointerGetOffsetNumber, GinScanOpaqueData::ginstate, i, InvalidOffsetNumber, GinScanKeyData::isFinished, pendingPosition::item, ItemPointerIsLossyPage, ItemPointerIsMin, ItemPointerSet, ItemPointerSetMin, keyGetItem(), GinScanOpaqueData::keys, GinScanOpaqueData::nkeys, OffsetNumberPrev, IndexScanDescData::opaque, GinScanKeyData::recheckCurItem, GinScanOpaqueData::tempCtx, and IndexScanDescData::xs_snapshot.

Referenced by gingetbitmap().

1235 {
1236  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1237  uint32 i;
1238  bool match;
1239 
1240  /*----------
1241  * Advance the scan keys in lock-step, until we find an item that matches
1242  * all the keys. If any key reports isFinished, meaning its subset of the
1243  * entries is exhausted, we can stop. Otherwise, set *item to the next
1244  * matching item.
1245  *
1246  * This logic works only if a keyGetItem stream can never contain both
1247  * exact and lossy pointers for the same page. Else we could have a
1248  * case like
1249  *
1250  * stream 1 stream 2
1251  * ... ...
1252  * 42/6 42/7
1253  * 50/1 42/0xffff
1254  * ... ...
1255  *
1256  * We would conclude that 42/6 is not a match and advance stream 1,
1257  * thus never detecting the match to the lossy pointer in stream 2.
1258  * (keyGetItem has a similar problem versus entryGetItem.)
1259  *----------
1260  */
1261  do
1262  {
1263  ItemPointerSetMin(item);
1264  match = true;
1265  for (i = 0; i < so->nkeys && match; i++)
1266  {
1267  GinScanKey key = so->keys + i;
1268 
1269  /* Fetch the next item for this key that is > advancePast. */
1270  keyGetItem(&so->ginstate, so->tempCtx, key, advancePast,
1271  scan->xs_snapshot);
1272 
1273  if (key->isFinished)
1274  return false;
1275 
1276  /*
1277  * If it's not a match, we can immediately conclude that nothing
1278  * <= this item matches, without checking the rest of the keys.
1279  */
1280  if (!key->curItemMatches)
1281  {
1282  advancePast = key->curItem;
1283  match = false;
1284  break;
1285  }
1286 
1287  /*
1288  * It's a match. We can conclude that nothing < matches, so the
1289  * other key streams can skip to this item.
1290  *
1291  * Beware of lossy pointers, though; from a lossy pointer, we can
1292  * only conclude that nothing smaller than this *block* matches.
1293  */
1294  if (ItemPointerIsLossyPage(&key->curItem))
1295  {
1296  if (GinItemPointerGetBlockNumber(&advancePast) <
1298  {
1299  ItemPointerSet(&advancePast,
1302  }
1303  }
1304  else
1305  {
1307  ItemPointerSet(&advancePast,
1310  }
1311 
1312  /*
1313  * If this is the first key, remember this location as a potential
1314  * match, and proceed to check the rest of the keys.
1315  *
1316  * Otherwise, check if this is the same item that we checked the
1317  * previous keys for (or a lossy pointer for the same page). If
1318  * not, loop back to check the previous keys for this item (we
1319  * will check this key again too, but keyGetItem returns quickly
1320  * for that)
1321  */
1322  if (i == 0)
1323  {
1324  *item = key->curItem;
1325  }
1326  else
1327  {
1328  if (ItemPointerIsLossyPage(&key->curItem) ||
1329  ItemPointerIsLossyPage(item))
1330  {
1332  match = (GinItemPointerGetBlockNumber(&key->curItem) ==
1334  }
1335  else
1336  {
1337  Assert(ginCompareItemPointers(&key->curItem, item) >= 0);
1338  match = (ginCompareItemPointers(&key->curItem, item) == 0);
1339  }
1340  }
1341  }
1342  } while (!match);
1343 
1344  Assert(!ItemPointerIsMin(item));
1345 
1346  /*
1347  * Now *item contains the first ItemPointer after previous result that
1348  * satisfied all the keys for that exact TID, or a lossy reference to the
1349  * same page.
1350  *
1351  * We must return recheck = true if any of the keys are marked recheck.
1352  */
1353  *recheck = false;
1354  for (i = 0; i < so->nkeys; i++)
1355  {
1356  GinScanKey key = so->keys + i;
1357 
1358  if (key->recheckCurItem)
1359  {
1360  *recheck = true;
1361  break;
1362  }
1363  }
1364 
1365  return true;
1366 }
#define GinItemPointerGetOffsetNumber(pointer)
Definition: ginblock.h:137
Snapshot xs_snapshot
Definition: relscan.h:92
#define ItemPointerIsLossyPage(p)
Definition: ginblock.h:169
GinScanOpaqueData * GinScanOpaque
Definition: gin_private.h:363
unsigned int uint32
Definition: c.h:325
#define ItemPointerIsMin(p)
Definition: ginblock.h:159
#define ItemPointerSetMin(p)
Definition: ginblock.h:157
GinScanKey keys
Definition: gin_private.h:351
MemoryContext tempCtx
Definition: gin_private.h:348
static void keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, ItemPointerData advancePast, Snapshot snapshot)
Definition: ginget.c:953
#define InvalidOffsetNumber
Definition: off.h:26
#define Assert(condition)
Definition: c.h:699
#define OffsetNumberPrev(offsetNumber)
Definition: off.h:55
ItemPointerData curItem
Definition: gin_private.h:307
static int ginCompareItemPointers(ItemPointer a, ItemPointer b)
Definition: gin_private.h:460
int i
#define GinItemPointerGetBlockNumber(pointer)
Definition: ginblock.h:134
#define ItemPointerSet(pointer, blockNumber, offNum)
Definition: itemptr.h:127

◆ scanPendingInsert()

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

Definition at line 1754 of file ginget.c.

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

Referenced by gingetbitmap().

1755 {
1756  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1757  MemoryContext oldCtx;
1758  bool recheck,
1759  match;
1760  int i;
1761  pendingPosition pos;
1762  Buffer metabuffer = ReadBuffer(scan->indexRelation, GIN_METAPAGE_BLKNO);
1763  Page page;
1764  BlockNumber blkno;
1765 
1766  *ntids = 0;
1767 
1768  /*
1769  * Acquire predicate lock on the metapage, to conflict with any
1770  * fastupdate insertions.
1771  */
1773 
1774  LockBuffer(metabuffer, GIN_SHARE);
1775  page = BufferGetPage(metabuffer);
1776  TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
1777  blkno = GinPageGetMeta(page)->head;
1778 
1779  /*
1780  * fetch head of list before unlocking metapage. head page must be pinned
1781  * to prevent deletion by vacuum process
1782  */
1783  if (blkno == InvalidBlockNumber)
1784  {
1785  /* No pending list, so proceed with normal scan */
1786  UnlockReleaseBuffer(metabuffer);
1787  return;
1788  }
1789 
1790  pos.pendingBuffer = ReadBuffer(scan->indexRelation, blkno);
1791  LockBuffer(pos.pendingBuffer, GIN_SHARE);
1792  pos.firstOffset = FirstOffsetNumber;
1793  UnlockReleaseBuffer(metabuffer);
1794  pos.hasMatchKey = palloc(sizeof(bool) * so->nkeys);
1795 
1796  /*
1797  * loop for each heap row. scanGetCandidate returns full row or row's
1798  * tuples from first page.
1799  */
1800  while (scanGetCandidate(scan, &pos))
1801  {
1802  /*
1803  * Check entries in tuple and set up entryRes array.
1804  *
1805  * If pending tuples belonging to the current heap row are spread
1806  * across several pages, collectMatchesForHeapRow will read all of
1807  * those pages.
1808  */
1809  if (!collectMatchesForHeapRow(scan, &pos))
1810  continue;
1811 
1812  /*
1813  * Matching of entries of one row is finished, so check row using
1814  * consistent functions.
1815  */
1816  oldCtx = MemoryContextSwitchTo(so->tempCtx);
1817  recheck = false;
1818  match = true;
1819 
1820  for (i = 0; i < so->nkeys; i++)
1821  {
1822  GinScanKey key = so->keys + i;
1823 
1824  if (!key->boolConsistentFn(key))
1825  {
1826  match = false;
1827  break;
1828  }
1829  recheck |= key->recheckCurItem;
1830  }
1831 
1832  MemoryContextSwitchTo(oldCtx);
1834 
1835  if (match)
1836  {
1837  tbm_add_tuples(tbm, &pos.item, 1, recheck);
1838  (*ntids)++;
1839  }
1840  }
1841 
1842  pfree(pos.hasMatchKey);
1843 }
void PredicateLockPage(Relation relation, BlockNumber blkno, Snapshot snapshot)
Definition: predicate.c:2475
static void TestForOldSnapshot(Snapshot snapshot, Relation relation, Page page)
Definition: bufmgr.h:265
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:376
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Snapshot xs_snapshot
Definition: relscan.h:92
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:136
uint32 BlockNumber
Definition: block.h:31
#define GIN_METAPAGE_BLKNO
Definition: ginblock.h:50
Relation indexRelation
Definition: relscan.h:91
void pfree(void *pointer)
Definition: mcxt.c:1031
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3332
GinScanOpaqueData * GinScanOpaque
Definition: gin_private.h:363
#define FirstOffsetNumber
Definition: off.h:27
static bool collectMatchesForHeapRow(IndexScanDesc scan, pendingPosition *pos)
Definition: ginget.c:1541
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define GIN_SHARE
Definition: gin_private.h:44
GinScanKey keys
Definition: gin_private.h:351
MemoryContext tempCtx
Definition: gin_private.h:348
bool(* boolConsistentFn)(GinScanKey key)
Definition: gin_private.h:284
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:594
#define InvalidBlockNumber
Definition: block.h:33
void * palloc(Size size)
Definition: mcxt.c:924
int i
#define GinPageGetMeta(p)
Definition: ginblock.h:103
static bool scanGetCandidate(IndexScanDesc scan, pendingPosition *pos)
Definition: ginget.c:1385
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:74

◆ scanPostingTree()

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

Definition at line 68 of file ginget.c.

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

Referenced by collectMatchBitmap().

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 }
#define GIN_DELETED
Definition: ginblock.h:41
uint32 predictNumberResult
Definition: gin_private.h:342
#define GinPageGetOpaque(page)
Definition: ginblock.h:109
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3332
#define GinPageRightMost(page)
Definition: ginblock.h:128
GinBtreeStack * ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno, Snapshot snapshot)
Definition: gindatapage.c:1922
Buffer ginStepRight(Buffer buffer, Relation index, int lockmode)
Definition: ginbtree.c:169
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define GIN_SHARE
Definition: gin_private.h:44
TIDBitmap * matchBitmap
Definition: gin_private.h:331
WalTimeSample buffer[LAG_TRACKER_BUFFER_SIZE]
Definition: walsender.c:215
int GinDataLeafPageGetItemsToTbm(Page page, TIDBitmap *tbm)
Definition: gindatapage.c:182
void freeGinBtreeStack(GinBtreeStack *stack)
Definition: ginbtree.c:197
int Buffer
Definition: buf.h:23
void IncrBufferRefCount(Buffer buffer)
Definition: bufmgr.c:3347
Pointer Page
Definition: bufpage.h:74

◆ startScan()

static void startScan ( IndexScanDesc  scan)
static

Definition at line 584 of file ginget.c.

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

Referenced by gingetbitmap().

585 {
586  GinScanOpaque so = (GinScanOpaque) scan->opaque;
587  GinState *ginstate = &so->ginstate;
588  uint32 i;
589 
590  for (i = 0; i < so->totalentries; i++)
591  startScanEntry(ginstate, so->entries[i], scan->xs_snapshot);
592 
593  if (GinFuzzySearchLimit > 0)
594  {
595  /*
596  * If all of keys more than threshold we will try to reduce result, we
597  * hope (and only hope, for intersection operation of array our
598  * supposition isn't true), that total result will not more than
599  * minimal predictNumberResult.
600  */
601  bool reduce = true;
602 
603  for (i = 0; i < so->totalentries; i++)
604  {
606  {
607  reduce = false;
608  break;
609  }
610  }
611  if (reduce)
612  {
613  for (i = 0; i < so->totalentries; i++)
614  {
616  so->entries[i]->reduceResult = true;
617  }
618  }
619  }
620 
621  /*
622  * Now that we have the estimates for the entry frequencies, finish
623  * initializing the scan keys.
624  */
625  for (i = 0; i < so->nkeys; i++)
626  startScanKey(ginstate, so, so->keys + i);
627 }
static void startScanKey(GinState *ginstate, GinScanOpaque so, GinScanKey key)
Definition: ginget.c:500
uint32 predictNumberResult
Definition: gin_private.h:342
Snapshot xs_snapshot
Definition: relscan.h:92
static void startScanEntry(GinState *ginstate, GinScanEntry entry, Snapshot snapshot)
Definition: ginget.c:314
int GinFuzzySearchLimit
Definition: ginget.c:26
GinScanOpaqueData * GinScanOpaque
Definition: gin_private.h:363
unsigned int uint32
Definition: c.h:325
GinScanKey keys
Definition: gin_private.h:351
GinScanEntry * entries
Definition: gin_private.h:354
int i

◆ startScanEntry()

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

Definition at line 314 of file ginget.c.

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().

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, 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 exacty 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 }
#define GIN_UNLOCK
Definition: gin_private.h:43
#define GIN_CAT_EMPTY_QUERY
Definition: ginblock.h:206
GinBtreeData btree
Definition: gin_private.h:343
ItemPointerData curItem
Definition: gin_private.h:328
void tbm_end_iterate(TBMIterator *iterator)
Definition: tidbitmap.c:1145
void PredicateLockPage(Relation relation, BlockNumber blkno, Snapshot snapshot)
Definition: predicate.c:2475
OffsetNumber offset
Definition: gin_private.h:338
uint32 predictNumberResult
Definition: gin_private.h:342
Relation index
Definition: gin_private.h:53
OffsetNumber off
Definition: gin_private.h:126
TBMIterator * matchIterator
Definition: gin_private.h:332
#define InvalidBuffer
Definition: buf.h:25
#define GinGetNPosting(itup)
Definition: ginblock.h:222
uint32 BlockNumber
Definition: block.h:31
ItemPointerData * list
Definition: gin_private.h:336
bool(* findItem)(GinBtree, GinBtreeStack *)
Definition: gin_private.h:149
GinBtreeStack * ginFindLeafPage(GinBtree btree, bool searchMode, Snapshot snapshot)
Definition: ginbtree.c:77
void pfree(void *pointer)
Definition: mcxt.c:1031
OffsetNumber attnum
Definition: gin_private.h:322
void tbm_free(TIDBitmap *tbm)
Definition: tidbitmap.c:321
IndexTupleData * IndexTuple
Definition: itup.h:53
GinBtreeStack * ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno, Snapshot snapshot)
Definition: gindatapage.c:1922
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
void ginPrepareEntryScan(GinBtree btree, OffsetNumber attnum, Datum key, GinNullCategory category, GinState *ginstate)
Definition: ginentrypage.c:745
#define ItemPointerSetMin(p)
Definition: ginblock.h:157
TIDBitmap * matchBitmap
Definition: gin_private.h:331
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
bool tbm_is_empty(const TIDBitmap *tbm)
Definition: tidbitmap.c:669
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
TBMIterateResult * matchResult
Definition: gin_private.h:333
#define InvalidOffsetNumber
Definition: off.h:26
GinNullCategory queryCategory
Definition: gin_private.h:317
TBMIterator * tbm_begin_iterate(TIDBitmap *tbm)
Definition: tidbitmap.c:688
ItemPointer ginReadTuple(GinState *ginstate, OffsetNumber attnum, IndexTuple itup, int *nitems)
Definition: ginentrypage.c:163
#define GinGetPostingTree(itup)
Definition: ginblock.h:227
uint32 predictNumber
Definition: gin_private.h:129
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2605
static bool collectMatchBitmap(GinBtreeData *btree, GinBtreeStack *stack, GinScanEntry scanEntry, Snapshot snapshot)
Definition: ginget.c:120
#define GinIsPostingTree(itup)
Definition: ginblock.h:225
void freeGinBtreeStack(GinBtreeStack *stack)
Definition: ginbtree.c:197
ItemPointer GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerData advancePast)
Definition: gindatapage.c:135
void IncrBufferRefCount(Buffer buffer)
Definition: bufmgr.c:3347
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
Pointer Page
Definition: bufpage.h:74

◆ startScanKey()

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

Definition at line 500 of file ginget.c.

References GinScanKeyData::additionalEntries, GinScanKeyData::curItem, GinScanKeyData::curItemMatches, CurrentMemoryContext, entryIndexByFrequencyCmp(), GinScanKeyData::entryRes, GIN_FALSE, GIN_MAYBE, i, GinScanKeyData::isFinished, ItemPointerSetMin, GinScanOpaqueData::keyCtx, MemoryContextReset(), MemoryContextSwitchTo(), GinScanKeyData::nadditional, GinScanKeyData::nentries, GinScanKeyData::nrequired, palloc(), qsort_arg(), GinScanKeyData::recheckCurItem, GinScanKeyData::requiredEntries, GinScanKeyData::scanEntry, GinScanOpaqueData::tempCtx, and GinScanKeyData::triConsistentFn.

Referenced by startScan().

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  if (key->nentries > 1)
533  {
535 
536  entryIndexes = (int *) palloc(sizeof(int) * key->nentries);
537  for (i = 0; i < key->nentries; i++)
538  entryIndexes[i] = i;
539  qsort_arg(entryIndexes, key->nentries, sizeof(int),
541 
542  for (i = 0; i < key->nentries - 1; i++)
543  {
544  /* Pass all entries <= i as FALSE, and the rest as MAYBE */
545  for (j = 0; j <= i; j++)
546  key->entryRes[entryIndexes[j]] = GIN_FALSE;
547  for (j = i + 1; j < key->nentries; j++)
548  key->entryRes[entryIndexes[j]] = GIN_MAYBE;
549 
550  if (key->triConsistentFn(key) == GIN_FALSE)
551  break;
552  }
553  /* i is now the last required entry. */
554 
556 
557  key->nrequired = i + 1;
558  key->nadditional = key->nentries - key->nrequired;
559  key->requiredEntries = palloc(key->nrequired * sizeof(GinScanEntry));
560  key->additionalEntries = palloc(key->nadditional * sizeof(GinScanEntry));
561 
562  j = 0;
563  for (i = 0; i < key->nrequired; i++)
564  key->requiredEntries[i] = key->scanEntry[entryIndexes[j++]];
565  for (i = 0; i < key->nadditional; i++)
566  key->additionalEntries[i] = key->scanEntry[entryIndexes[j++]];
567 
568  /* clean up after consistentFn calls (also frees entryIndexes) */
570  }
571  else
572  {
574 
575  key->nrequired = 1;
576  key->nadditional = 0;
577  key->requiredEntries = palloc(1 * sizeof(GinScanEntry));
578  key->requiredEntries[0] = key->scanEntry[0];
579  }
580  MemoryContextSwitchTo(oldCtx);
581 }
#define GIN_MAYBE
Definition: gin.h:61
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:136
GinScanEntry * scanEntry
Definition: gin_private.h:267
MemoryContext keyCtx
Definition: gin_private.h:358
GinTernaryValue * entryRes
Definition: gin_private.h:283
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define ItemPointerSetMin(p)
Definition: ginblock.h:157
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
Definition: qsort_arg.c:113
MemoryContext tempCtx
Definition: gin_private.h:348
GinScanEntry * requiredEntries
Definition: gin_private.h:277
static int entryIndexByFrequencyCmp(const void *a1, const void *a2, void *arg)
Definition: ginget.c:483
GinTernaryValue(* triConsistentFn)(GinScanKey key)
Definition: gin_private.h:285
#define GIN_FALSE
Definition: gin.h:59
ItemPointerData curItem
Definition: gin_private.h:307
void * palloc(Size size)
Definition: mcxt.c:924
GinScanEntry * additionalEntries
Definition: gin_private.h:279
int i

Variable Documentation

◆ GinFuzzySearchLimit

int GinFuzzySearchLimit = 0

Definition at line 26 of file ginget.c.

Referenced by startScan().