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

Go to the source code of this file.

Data Structures

struct   pendingPosition
 

Macros

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

Typedefs

typedef struct pendingPosition  pendingPosition
 

Functions

static bool  moveRightIfItNeeded (GinBtreeData *btree, GinBtreeStack *stack, Snapshot snapshot)
 
static void  scanPostingTree (Relation index, GinScanEntry scanEntry, BlockNumber rootPostingTree)
 
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)
 
static void  entryGetItem (GinState *ginstate, GinScanEntry entry, ItemPointerData advancePast)
 
static void  keyGetItem (GinState *ginstate, MemoryContext tempCtx, GinScanKey key, ItemPointerData advancePast)
 
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 796 of file ginget.c.

◆ gin_rand

#define gin_rand ( )    pg_prng_double(&pg_global_prng_state)

Definition at line 795 of file ginget.c.

◆ GinIsVoidRes

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

Definition at line 1928 of file ginget.c.

Typedef Documentation

◆ pendingPosition

typedef struct pendingPosition pendingPosition

Function Documentation

◆ collectMatchBitmap()

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

Definition at line 121 of file ginget.c.

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

References CompactAttribute::attbyval, CompactAttribute::attlen, GinScanEntryData::attnum, attnum, GinBtreeStack::buffer, BufferGetBlockNumber(), 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(), TupleDescCompactAttr(), UInt16GetDatum(), and work_mem.

Referenced by startScanEntry().

◆ collectMatchesForHeapRow()

static bool collectMatchesForHeapRow ( IndexScanDesc  scan,
pendingPosition *  pos 
)
static

Definition at line 1622 of file ginget.c.

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

References Assert(), GinScanEntryData::attnum, BufferGetPage(), elog, ERROR, GinScanKeyData::excludeOnly, pendingPosition::firstOffset, for(), 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, GinScanEntryData::isPartialMatch, pendingPosition::item, ItemPointerEquals(), j, sort-test::key, GinScanOpaqueData::keys, pendingPosition::lastOffset, matchPartialInPendingList(), GinScanOpaqueData::nkeys, IndexScanDescData::opaque, PageGetItem(), PageGetItemId(), pendingPosition::pendingBuffer, GinScanEntryData::queryCategory, GinScanEntryData::queryKey, scanGetCandidate(), and GinScanEntryData::searchMode.

Referenced by scanPendingInsert().

◆ entryGetItem()

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

Definition at line 812 of file ginget.c.

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

References Assert(), TBMIterateResult::blockno, BlockNumberIsValid(), GinScanEntryData::buffer, BufferIsValid(), GinScanEntryData::curItem, dropItem, entryLoadMoreItems(), ginCompareItemPointers(), GinItemPointerGetBlockNumber, GinItemPointerGetOffsetNumber, GinScanEntryData::isFinished, ItemPointerIsLossyPage, ItemPointerIsValid(), ItemPointerSet(), ItemPointerSetInvalid(), ItemPointerSetLossyPage, GinScanEntryData::list, TBMIterateResult::lossy, GinScanEntryData::matchBitmap, GinScanEntryData::matchIterator, GinScanEntryData::matchNtuples, GinScanEntryData::matchOffsets, GinScanEntryData::matchResult, GinScanEntryData::nlist, GinScanEntryData::offset, GinScanEntryData::reduceResult, tbm_end_private_iterate(), tbm_extract_page_tuple(), TBM_MAX_TUPLES_PER_PAGE, and tbm_private_iterate().

Referenced by keyGetItem().

◆ entryIndexByFrequencyCmp()

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

Definition at line 490 of file ginget.c.

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

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

Referenced by startScanKey().

◆ entryLoadMoreItems()

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

Definition at line 657 of file ginget.c.

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

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

Referenced by entryGetItem().

◆ gingetbitmap()

int64 gingetbitmap ( IndexScanDesc  scan,
TIDBitmap *  tbm 
)

Definition at line 1931 of file ginget.c.

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

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

Referenced by ginhandler().

◆ keyGetItem()

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

Definition at line 1005 of file ginget.c.

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

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

Referenced by scanGetItem().

◆ matchPartialInPendingList()

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

Definition at line 1554 of file ginget.c.

1559{
1560 IndexTuple itup;
1561 int32 cmp;
1562
1563 /* Partial match to a null is not possible */
1564 if (entry->queryCategory != GIN_CAT_NORM_KEY)
1565 return false;
1566
1567 while (off < maxoff)
1568 {
1569 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
1570
1571 if (gintuple_get_attrnum(ginstate, itup) != entry->attnum)
1572 return false;
1573
1574 if (datumExtracted[off - 1] == false)
1575 {
1576 datum[off - 1] = gintuple_get_key(ginstate, itup,
1577 &category[off - 1]);
1578 datumExtracted[off - 1] = true;
1579 }
1580
1581 /* Once we hit nulls, no further match is possible */
1582 if (category[off - 1] != GIN_CAT_NORM_KEY)
1583 return false;
1584
1585 /*----------
1586 * Check partial match.
1587 * case cmp == 0 => match
1588 * case cmp > 0 => not match and end scan (no later match possible)
1589 * case cmp < 0 => not match and continue scan
1590 *----------
1591 */
1593 ginstate->supportCollation[entry->attnum - 1],
1594 entry->queryKey,
1595 datum[off - 1],
1596 UInt16GetDatum(entry->strategy),
1597 PointerGetDatum(entry->extra_data)));
1598 if (cmp == 0)
1599 return true;
1600 else if (cmp > 0)
1601 return false;
1602
1603 off++;
1604 }
1605
1606 return false;
1607}

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

Referenced by collectMatchesForHeapRow().

◆ moveRightIfItNeeded()

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

Definition at line 43 of file ginget.c.

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

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

Referenced by collectMatchBitmap().

◆ scanGetCandidate()

static bool scanGetCandidate ( IndexScanDesc  scan,
pendingPosition *  pos 
)
static

Definition at line 1467 of file ginget.c.

1468{
1469 OffsetNumber maxoff;
1470 Page page;
1471 IndexTuple itup;
1472
1474 for (;;)
1475 {
1476 page = BufferGetPage(pos->pendingBuffer);
1477
1478 maxoff = PageGetMaxOffsetNumber(page);
1479 if (pos->firstOffset > maxoff)
1480 {
1481 BlockNumber blkno = GinPageGetOpaque(page)->rightlink;
1482
1483 if (blkno == InvalidBlockNumber)
1484 {
1487
1488 return false;
1489 }
1490 else
1491 {
1492 /*
1493 * Here we must prevent deletion of next page by insertcleanup
1494 * process, which may be trying to obtain exclusive lock on
1495 * current page. So, we lock next page before releasing the
1496 * current one
1497 */
1498 Buffer tmpbuf = ReadBuffer(scan->indexRelation, blkno);
1499
1502
1503 pos->pendingBuffer = tmpbuf;
1505 }
1506 }
1507 else
1508 {
1509 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->firstOffset));
1510 pos->item = itup->t_tid;
1511 if (GinPageHasFullRow(page))
1512 {
1513 /*
1514 * find itempointer to the next row
1515 */
1516 for (pos->lastOffset = pos->firstOffset + 1; pos->lastOffset <= maxoff; pos->lastOffset++)
1517 {
1518 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->lastOffset));
1519 if (!ItemPointerEquals(&pos->item, &itup->t_tid))
1520 break;
1521 }
1522 }
1523 else
1524 {
1525 /*
1526 * All itempointers are the same on this page
1527 */
1528 pos->lastOffset = maxoff + 1;
1529 }
1530
1531 /*
1532 * Now pos->firstOffset points to the first tuple of current heap
1533 * row, pos->lastOffset points to the first tuple of next heap row
1534 * (or to the end of page)
1535 */
1536 break;
1537 }
1538 }
1539
1540 return true;
1541}
#define InvalidBlockNumber
Definition: block.h:33
int Buffer
Definition: buf.h:23
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:758
Relation indexRelation
Definition: relscan.h:137
ItemPointerData t_tid
Definition: itup.h:37
static StringInfoData tmpbuf
Definition: walsender.c:178

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, tmpbuf, and UnlockReleaseBuffer().

Referenced by collectMatchesForHeapRow(), and scanPendingInsert().

◆ scanGetItem()

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

Definition at line 1300 of file ginget.c.

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

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

Referenced by gingetbitmap().

◆ scanPendingInsert()

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

Definition at line 1837 of file ginget.c.

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

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

Referenced by gingetbitmap().

◆ scanPostingTree()

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

Definition at line 69 of file ginget.c.

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

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

Referenced by collectMatchBitmap().

◆ startScan()

static void startScan ( IndexScanDesc  scan )
static

Definition at line 605 of file ginget.c.

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

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

Referenced by gingetbitmap().

◆ startScanEntry()

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

Definition at line 319 of file ginget.c.

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

References GinScanEntryData::attnum, TBMIterateResult::blockno, 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, InvalidBlockNumber, InvalidBuffer, InvalidOffsetNumber, GinScanEntryData::isFinished, GinScanEntryData::isPartialMatch, ItemPointerSetMin, GinScanEntryData::list, LockBuffer(), GinScanEntryData::matchBitmap, GinScanEntryData::matchIterator, GinScanEntryData::matchNtuples, GinScanEntryData::matchResult, GinScanEntryData::nlist, GinBtreeStack::off, GinScanEntryData::offset, PageGetItem(), PageGetItemId(), pfree(), PredicateLockPage(), GinBtreeStack::predictNumber, GinScanEntryData::predictNumberResult, GinScanEntryData::queryCategory, GinScanEntryData::queryKey, GinScanEntryData::reduceResult, tbm_begin_private_iterate(), tbm_end_private_iterate(), tbm_free(), and tbm_is_empty().

Referenced by startScan().

◆ startScanKey()

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

Definition at line 507 of file ginget.c.

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

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

Referenced by startScan().

Variable Documentation

◆ GinFuzzySearchLimit

int GinFuzzySearchLimit = 0

Definition at line 27 of file ginget.c.

Referenced by startScan().

AltStyle によって変換されたページ (->オリジナル) /