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 791 of file ginget.c.

Referenced by entryGetItem().

◆ gin_rand

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

Definition at line 790 of file ginget.c.

◆ GinIsVoidRes

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

Definition at line 1914 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, 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().

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

References Assert, GinScanKeyData::attnum, GinScanEntryData::attnum, BufferGetPage, elog, GinScanKeyData::entryRes, 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(), sort-test::key, 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().

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

◆ entryGetItem()

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

Definition at line 807 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().

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

References sort-test::key, GinScanEntryData::predictNumberResult, and GinScanKeyData::scanEntry.

Referenced by startScanKey().

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

◆ entryLoadMoreItems()

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

Definition at line 652 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().

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

◆ gingetbitmap()

int64 gingetbitmap ( IndexScanDesc  scan,
TIDBitmap tbm 
)

Definition at line 1917 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().

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

◆ keyGetItem()

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

Definition at line 989 of file ginget.c.

References GinScanKeyData::additionalEntries, Assert, GinScanKeyData::curItem, GinScanEntryData::curItem, GinScanKeyData::curItemMatches, entryGetItem(), GinScanKeyData::entryRes, GinScanKeyData::excludeOnly, 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, OffsetNumberNext, OffsetNumberPrev, GinScanKeyData::recheckCurItem, GinScanKeyData::requiredEntries, GinScanKeyData::scanEntry, and GinScanKeyData::triConsistentFn.

Referenced by scanGetItem().

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

1543 {
1544  IndexTuple itup;
1545  int32 cmp;
1546 
1547  /* Partial match to a null is not possible */
1548  if (entry->queryCategory != GIN_CAT_NORM_KEY)
1549  return false;
1550 
1551  while (off < maxoff)
1552  {
1553  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
1554 
1555  if (gintuple_get_attrnum(ginstate, itup) != entry->attnum)
1556  return false;
1557 
1558  if (datumExtracted[off - 1] == false)
1559  {
1560  datum[off - 1] = gintuple_get_key(ginstate, itup,
1561  &category[off - 1]);
1562  datumExtracted[off - 1] = true;
1563  }
1564 
1565  /* Once we hit nulls, no further match is possible */
1566  if (category[off - 1] != GIN_CAT_NORM_KEY)
1567  return false;
1568 
1569  /*----------
1570  * Check partial match.
1571  * case cmp == 0 => match
1572  * case cmp > 0 => not match and end scan (no later match possible)
1573  * case cmp < 0 => not match and continue scan
1574  *----------
1575  */
1576  cmp = DatumGetInt32(FunctionCall4Coll(&ginstate->comparePartialFn[entry->attnum - 1],
1577  ginstate->supportCollation[entry->attnum - 1],
1578  entry->queryKey,
1579  datum[off - 1],
1580  UInt16GetDatum(entry->strategy),
1581  PointerGetDatum(entry->extra_data)));
1582  if (cmp == 0)
1583  return true;
1584  else if (cmp > 0)
1585  return false;
1586 
1587  off++;
1588  }
1589 
1590  return false;
1591 }
Oid supportCollation[INDEX_MAX_KEYS]
Definition: gin_private.h:87
#define DatumGetInt32(X)
Definition: postgres.h:472
#define PointerGetDatum(X)
Definition: postgres.h:556
Pointer extra_data
Definition: gin_private.h:339
Datum FunctionCall4Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2, Datum arg3, Datum arg4)
Definition: fmgr.c:1199
signed int int32
Definition: c.h:363
OffsetNumber attnum
Definition: gin_private.h:342
OffsetNumber gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple)
Definition: ginutil.c:224
#define GIN_CAT_NORM_KEY
Definition: ginblock.h:209
FmgrInfo comparePartialFn[INDEX_MAX_KEYS]
Definition: gin_private.h:83
IndexTupleData * IndexTuple
Definition: itup.h:53
Datum gintuple_get_key(GinState *ginstate, IndexTuple tuple, GinNullCategory *category)
Definition: ginutil.c:257
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
StrategyNumber strategy
Definition: gin_private.h:340
GinNullCategory queryCategory
Definition: gin_private.h:337
#define UInt16GetDatum(X)
Definition: postgres.h:465
#define PageGetItem(page, itemId)
Definition: bufpage.h:340
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:2521
OffsetNumber off
Definition: gin_private.h:131
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:357
#define GinPageRightMost(page)
Definition: ginblock.h:130
#define FirstOffsetNumber
Definition: off.h:27
Buffer ginStepRight(Buffer buffer, Relation index, int lockmode)
Definition: ginbtree.c:173
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
#define GIN_SHARE
Definition: gin_private.h:49
Relation index
Definition: gin_private.h:165
BlockNumber blkno
Definition: gin_private.h:129
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2661
Pointer Page
Definition: bufpage.h:78

◆ scanGetCandidate()

static bool scanGetCandidate ( IndexScanDesc  scan,
pendingPosition pos 
)
static

Definition at line 1450 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().

1451 {
1452  OffsetNumber maxoff;
1453  Page page;
1454  IndexTuple itup;
1455 
1456  ItemPointerSetInvalid(&pos->item);
1457  for (;;)
1458  {
1459  page = BufferGetPage(pos->pendingBuffer);
1460  TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
1461 
1462  maxoff = PageGetMaxOffsetNumber(page);
1463  if (pos->firstOffset > maxoff)
1464  {
1465  BlockNumber blkno = GinPageGetOpaque(page)->rightlink;
1466 
1467  if (blkno == InvalidBlockNumber)
1468  {
1471 
1472  return false;
1473  }
1474  else
1475  {
1476  /*
1477  * Here we must prevent deletion of next page by insertcleanup
1478  * process, which may be trying to obtain exclusive lock on
1479  * current page. So, we lock next page before releasing the
1480  * current one
1481  */
1482  Buffer tmpbuf = ReadBuffer(scan->indexRelation, blkno);
1483 
1484  LockBuffer(tmpbuf, GIN_SHARE);
1486 
1487  pos->pendingBuffer = tmpbuf;
1489  }
1490  }
1491  else
1492  {
1493  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->firstOffset));
1494  pos->item = itup->t_tid;
1495  if (GinPageHasFullRow(page))
1496  {
1497  /*
1498  * find itempointer to the next row
1499  */
1500  for (pos->lastOffset = pos->firstOffset + 1; pos->lastOffset <= maxoff; pos->lastOffset++)
1501  {
1502  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->lastOffset));
1503  if (!ItemPointerEquals(&pos->item, &itup->t_tid))
1504  break;
1505  }
1506  }
1507  else
1508  {
1509  /*
1510  * All itempointers are the same on this page
1511  */
1512  pos->lastOffset = maxoff + 1;
1513  }
1514 
1515  /*
1516  * Now pos->firstOffset points to the first tuple of current heap
1517  * row, pos->lastOffset points to the first tuple of next heap row
1518  * (or to the end of page)
1519  */
1520  break;
1521  }
1522  }
1523 
1524  return true;
1525 }
#define GinPageHasFullRow(page)
Definition: ginblock.h:120
static void TestForOldSnapshot(Snapshot snapshot, Relation relation, Page page)
Definition: bufmgr.h:277
Buffer pendingBuffer
Definition: ginget.c:30
ItemPointerData t_tid
Definition: itup.h:37
#define InvalidBuffer
Definition: buf.h:25
struct SnapshotData * xs_snapshot
Definition: relscan.h:116
uint32 BlockNumber
Definition: block.h:31
#define GinPageGetOpaque(page)
Definition: ginblock.h:111
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:357
Relation indexRelation
Definition: relscan.h:115
uint16 OffsetNumber
Definition: off.h:24
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3534
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
OffsetNumber firstOffset
Definition: ginget.c:31
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
#define GIN_SHARE
Definition: gin_private.h:49
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3750
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:607
#define InvalidBlockNumber
Definition: block.h:33
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
Definition: itemptr.c:29
static StringInfoData tmpbuf
Definition: walsender.c:159
#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:340
Pointer Page
Definition: bufpage.h:78

◆ scanGetItem()

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

Definition at line 1284 of file ginget.c.

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

Referenced by gingetbitmap().

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

◆ scanPendingInsert()

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

Definition at line 1822 of file ginget.c.

References GinScanKeyData::boolConsistentFn, 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(), GinScanKeyData::recheckCurItem, scanGetCandidate(), tbm_add_tuples(), GinScanOpaqueData::tempCtx, TestForOldSnapshot(), UnlockReleaseBuffer(), and IndexScanDescData::xs_snapshot.

Referenced by gingetbitmap().

1823 {
1824  GinScanOpaque so = (GinScanOpaque) scan->opaque;
1825  MemoryContext oldCtx;
1826  bool recheck,
1827  match;
1828  int i;
1829  pendingPosition pos;
1830  Buffer metabuffer = ReadBuffer(scan->indexRelation, GIN_METAPAGE_BLKNO);
1831  Page page;
1832  BlockNumber blkno;
1833 
1834  *ntids = 0;
1835 
1836  /*
1837  * Acquire predicate lock on the metapage, to conflict with any fastupdate
1838  * insertions.
1839  */
1841 
1842  LockBuffer(metabuffer, GIN_SHARE);
1843  page = BufferGetPage(metabuffer);
1844  TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
1845  blkno = GinPageGetMeta(page)->head;
1846 
1847  /*
1848  * fetch head of list before unlocking metapage. head page must be pinned
1849  * to prevent deletion by vacuum process
1850  */
1851  if (blkno == InvalidBlockNumber)
1852  {
1853  /* No pending list, so proceed with normal scan */
1854  UnlockReleaseBuffer(metabuffer);
1855  return;
1856  }
1857 
1858  pos.pendingBuffer = ReadBuffer(scan->indexRelation, blkno);
1859  LockBuffer(pos.pendingBuffer, GIN_SHARE);
1860  pos.firstOffset = FirstOffsetNumber;
1861  UnlockReleaseBuffer(metabuffer);
1862  pos.hasMatchKey = palloc(sizeof(bool) * so->nkeys);
1863 
1864  /*
1865  * loop for each heap row. scanGetCandidate returns full row or row's
1866  * tuples from first page.
1867  */
1868  while (scanGetCandidate(scan, &pos))
1869  {
1870  /*
1871  * Check entries in tuple and set up entryRes array.
1872  *
1873  * If pending tuples belonging to the current heap row are spread
1874  * across several pages, collectMatchesForHeapRow will read all of
1875  * those pages.
1876  */
1877  if (!collectMatchesForHeapRow(scan, &pos))
1878  continue;
1879 
1880  /*
1881  * Matching of entries of one row is finished, so check row using
1882  * consistent functions.
1883  */
1884  oldCtx = MemoryContextSwitchTo(so->tempCtx);
1885  recheck = false;
1886  match = true;
1887 
1888  for (i = 0; i < so->nkeys; i++)
1889  {
1890  GinScanKey key = so->keys + i;
1891 
1892  if (!key->boolConsistentFn(key))
1893  {
1894  match = false;
1895  break;
1896  }
1897  recheck |= key->recheckCurItem;
1898  }
1899 
1900  MemoryContextSwitchTo(oldCtx);
1902 
1903  if (match)
1904  {
1905  tbm_add_tuples(tbm, &pos.item, 1, recheck);
1906  (*ntids)++;
1907  }
1908  }
1909 
1910  pfree(pos.hasMatchKey);
1911 }
void PredicateLockPage(Relation relation, BlockNumber blkno, Snapshot snapshot)
Definition: predicate.c:2521
static void TestForOldSnapshot(Snapshot snapshot, Relation relation, Page page)
Definition: bufmgr.h:277
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
struct SnapshotData * xs_snapshot
Definition: relscan.h:116
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:137
uint32 BlockNumber
Definition: block.h:31
#define GIN_METAPAGE_BLKNO
Definition: ginblock.h:52
Relation indexRelation
Definition: relscan.h:115
void pfree(void *pointer)
Definition: mcxt.c:1057
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3534
GinScanOpaqueData * GinScanOpaque
Definition: gin_private.h:383
#define FirstOffsetNumber
Definition: off.h:27
static bool collectMatchesForHeapRow(IndexScanDesc scan, pendingPosition *pos)
Definition: ginget.c:1606
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
#define GIN_SHARE
Definition: gin_private.h:49
GinScanKey keys
Definition: gin_private.h:371
MemoryContext tempCtx
Definition: gin_private.h:368
bool(* boolConsistentFn)(GinScanKey key)
Definition: gin_private.h:290
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3750
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:607
#define InvalidBlockNumber
Definition: block.h:33
void * palloc(Size size)
Definition: mcxt.c:950
int i
#define GinPageGetMeta(p)
Definition: ginblock.h:105
static bool scanGetCandidate(IndexScanDesc scan, pendingPosition *pos)
Definition: ginget.c:1450
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:78

◆ scanPostingTree()

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

Definition at line 68 of file ginget.c.

References GinBtreeStack::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:43
uint32 predictNumberResult
Definition: gin_private.h:362
#define GinPageGetOpaque(page)
Definition: ginblock.h:111
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3534
#define GinPageRightMost(page)
Definition: ginblock.h:130
GinBtreeStack * ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno, Snapshot snapshot)
Definition: gindatapage.c:1930
Buffer ginStepRight(Buffer buffer, Relation index, int lockmode)
Definition: ginbtree.c:173
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
#define GIN_SHARE
Definition: gin_private.h:49
TIDBitmap * matchBitmap
Definition: gin_private.h:351
int GinDataLeafPageGetItemsToTbm(Page page, TIDBitmap *tbm)
Definition: gindatapage.c:182
void freeGinBtreeStack(GinBtreeStack *stack)
Definition: ginbtree.c:194
int Buffer
Definition: buf.h:23
void IncrBufferRefCount(Buffer buffer)
Definition: bufmgr.c:3549
Pointer Page
Definition: bufpage.h:78

◆ startScan()

static void startScan ( IndexScanDesc  scan)
static

Definition at line 600 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().

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

◆ startScanEntry()

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

Definition at line 318 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().

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

◆ startScanKey()

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

Definition at line 504 of file ginget.c.

References GinScanKeyData::additionalEntries, GinScanKeyData::curItem, GinScanKeyData::curItemMatches, CurrentMemoryContext, entryIndexByFrequencyCmp(), GinScanKeyData::entryRes, GinScanKeyData::excludeOnly, 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().

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

Variable Documentation

◆ GinFuzzySearchLimit

int GinFuzzySearchLimit = 0

Definition at line 26 of file ginget.c.

Referenced by startScan().