Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * ginget.c
4 : : * fetch tuples from a GIN scan.
5 : : *
6 : : *
7 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
8 : : * Portions Copyright (c) 1994, Regents of the University of California
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/access/gin/ginget.c
12 : : *-------------------------------------------------------------------------
13 : : */
14 : :
15 : : #include "postgres.h"
16 : :
17 : : #include "access/gin_private.h"
18 : : #include "access/relscan.h"
19 : : #include "common/pg_prng.h"
20 : : #include "miscadmin.h"
21 : : #include "storage/predicate.h"
22 : : #include "utils/datum.h"
23 : : #include "utils/memutils.h"
24 : : #include "utils/rel.h"
25 : :
26 : : /* GUC parameter */
27 : : int GinFuzzySearchLimit = 0;
28 : :
29 : : typedef struct pendingPosition
30 : : {
31 : : Buffer pendingBuffer;
32 : : OffsetNumber firstOffset;
33 : : OffsetNumber lastOffset;
34 : : ItemPointerData item;
35 : : bool *hasMatchKey;
36 : : } pendingPosition;
37 : :
38 : :
39 : : /*
40 : : * Goes to the next page if current offset is outside of bounds
41 : : */
42 : : static bool
3040 teodor@sigaev.ru 43 :CBC 271095 : moveRightIfItNeeded(GinBtreeData *btree, GinBtreeStack *stack, Snapshot snapshot)
44 : : {
3749 kgrittn@postgresql.o 45 : 271095 : Page page = BufferGetPage(stack->buffer);
46 : :
6254 bruce@momjian.us 47 [ + + ]: 271095 : if (stack->off > PageGetMaxOffsetNumber(page))
48 : : {
49 : : /*
50 : : * We scanned the whole page, so we should take right page
51 : : */
52 [ + + ]: 2573 : if (GinPageRightMost(page))
53 : 304 : return false; /* no more pages */
54 : :
4643 heikki.linnakangas@i 55 : 2269 : stack->buffer = ginStepRight(stack->buffer, btree->index, GIN_SHARE);
56 : 2269 : stack->blkno = BufferGetBlockNumber(stack->buffer);
6645 tgl@sss.pgh.pa.us 57 : 2269 : stack->off = FirstOffsetNumber;
3005 teodor@sigaev.ru 58 : 2269 : PredicateLockPage(btree->index, stack->blkno, snapshot);
59 : : }
60 : :
6645 tgl@sss.pgh.pa.us 61 : 270791 : return true;
62 : : }
63 : :
64 : : /*
65 : : * Scan all pages of a posting tree and save all its heap ItemPointers
66 : : * in scanEntry->matchBitmap
67 : : */
68 : : static void
5679 69 : 8 : scanPostingTree(Relation index, GinScanEntry scanEntry,
70 : : BlockNumber rootPostingTree)
71 : : {
72 : : GinBtreeData btree;
73 : : GinBtreeStack *stack;
74 : : Buffer buffer;
75 : : Page page;
76 : :
77 : : /* Descend to the leftmost leaf page */
1052 tmunro@postgresql.or 78 : 8 : stack = ginScanBeginPostingTree(&btree, index, rootPostingTree);
4631 heikki.linnakangas@i 79 : 8 : buffer = stack->buffer;
80 : :
6645 tgl@sss.pgh.pa.us 81 : 8 : IncrBufferRefCount(buffer); /* prevent unpin in freeGinBtreeStack */
82 : :
4631 heikki.linnakangas@i 83 : 8 : freeGinBtreeStack(stack);
84 : :
85 : : /*
86 : : * Loop iterates through all leaf pages of posting tree
87 : : */
88 : : for (;;)
89 : : {
3749 kgrittn@postgresql.o 90 : 20 : page = BufferGetPage(buffer);
4568 heikki.linnakangas@i 91 [ + - ]: 20 : if ((GinPageGetOpaque(page)->flags & GIN_DELETED) == 0)
92 : : {
4464 bruce@momjian.us 93 : 20 : int n = GinDataLeafPageGetItemsToTbm(page, scanEntry->matchBitmap);
94 : :
4568 heikki.linnakangas@i 95 : 20 : scanEntry->predictNumberResult += n;
96 : : }
97 : :
6254 bruce@momjian.us 98 [ + + ]: 20 : if (GinPageRightMost(page))
5679 tgl@sss.pgh.pa.us 99 : 8 : break; /* no more pages */
100 : :
4643 heikki.linnakangas@i 101 : 12 : buffer = ginStepRight(buffer, index, GIN_SHARE);
102 : : }
103 : :
5679 tgl@sss.pgh.pa.us 104 : 8 : UnlockReleaseBuffer(buffer);
6645 105 : 8 : }
106 : :
107 : : /*
108 : : * Collects TIDs into scanEntry->matchBitmap for all heap tuples that
109 : : * match the search entry. This supports three different match modes:
110 : : *
111 : : * 1. Partial-match support: scan from current point until the
112 : : * comparePartialFn says we're done.
113 : : * 2. SEARCH_MODE_ALL: scan from current point (which should be first
114 : : * key for the current attnum) until we hit null items or end of attnum
115 : : * 3. SEARCH_MODE_EVERYTHING: scan from current point (which should be first
116 : : * key for the current attnum) until we hit end of attnum
117 : : *
118 : : * Returns true if done, false if it's necessary to restart scan from scratch
119 : : */
120 : : static bool
5679 121 : 486 : collectMatchBitmap(GinBtreeData *btree, GinBtreeStack *stack,
122 : : GinScanEntry scanEntry, Snapshot snapshot)
123 : : {
124 : : OffsetNumber attnum;
125 : : CompactAttribute *attr;
126 : :
127 : : /* Initialize empty bitmap result */
541 128 : 486 : scanEntry->matchBitmap = tbm_create(work_mem * (Size) 1024, NULL);
129 : :
130 : : /* Null query cannot partial-match anything */
5679 131 [ + + ]: 486 : if (scanEntry->isPartialMatch &&
132 [ - + ]: 301 : scanEntry->queryCategory != GIN_CAT_NORM_KEY)
5679 tgl@sss.pgh.pa.us 133 :UBC 0 : return true;
134 : :
135 : : /* Locate tupdesc entry for key column (for attbyval/attlen data) */
5679 tgl@sss.pgh.pa.us 136 :CBC 486 : attnum = scanEntry->attnum;
583 drowley@postgresql.o 137 : 486 : attr = TupleDescCompactAttr(btree->ginstate->origTupdesc, attnum - 1);
138 : :
139 : : /*
140 : : * Predicate lock entry leaf page, following pages will be locked by
141 : : * moveRightIfItNeeded()
142 : : */
1119 tmunro@postgresql.or 143 : 486 : PredicateLockPage(btree->index,
144 : : BufferGetBlockNumber(stack->buffer),
145 : : snapshot);
146 : :
147 : : for (;;)
6645 tgl@sss.pgh.pa.us 148 : 270601 : {
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 : : */
3040 teodor@sigaev.ru 157 [ + + ]: 271087 : if (moveRightIfItNeeded(btree, stack, snapshot) == false)
6645 tgl@sss.pgh.pa.us 158 : 486 : return true;
159 : :
3749 kgrittn@postgresql.o 160 : 270783 : page = BufferGetPage(stack->buffer);
6645 tgl@sss.pgh.pa.us 161 : 270783 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
162 : :
163 : : /*
164 : : * If tuple stores another attribute then stop scan
165 : : */
5679 166 [ - + ]: 270783 : if (gintuple_get_attrnum(btree->ginstate, itup) != attnum)
6589 tgl@sss.pgh.pa.us 167 :UBC 0 : return true;
168 : :
169 : : /* Safe to fetch attribute value */
5679 tgl@sss.pgh.pa.us 170 :CBC 270783 : idatum = gintuple_get_key(btree->ginstate, itup, &icategory);
171 : :
172 : : /*
173 : : * Check for appropriate scan stop conditions
174 : : */
175 [ + + ]: 270783 : 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 [ + + ]: 1395 : if (icategory != GIN_CAT_NORM_KEY)
184 : 5 : 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 : : */
5584 193 : 1390 : cmp = DatumGetInt32(FunctionCall4Coll(&btree->ginstate->comparePartialFn[attnum - 1],
3322 194 : 1390 : btree->ginstate->supportCollation[attnum - 1],
195 : : scanEntry->queryKey,
196 : : idatum,
197 : 1390 : UInt16GetDatum(scanEntry->strategy),
198 : 1390 : PointerGetDatum(scanEntry->extra_data)));
199 : :
5679 200 [ + + ]: 1390 : if (cmp > 0)
201 : 159 : return true;
202 [ + + ]: 1231 : else if (cmp < 0)
203 : : {
204 : 64 : stack->off++;
205 : 64 : continue;
206 : : }
207 : : }
208 [ + - ]: 269388 : 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 [ + + ]: 269388 : if (icategory == GIN_CAT_NULL_ITEM)
217 : 18 : return true;
218 : : }
219 : :
220 : : /*
221 : : * OK, we want to return the TIDs listed in this entry.
222 : : */
6254 bruce@momjian.us 223 [ + + ]: 270537 : if (GinIsPostingTree(itup))
224 : : {
6645 tgl@sss.pgh.pa.us 225 : 8 : 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 : : */
5679 234 [ + - ]: 8 : if (icategory == GIN_CAT_NORM_KEY)
235 : 8 : idatum = datumCopy(idatum, attr->attbyval, attr->attlen);
236 : :
6645 237 : 8 : LockBuffer(stack->buffer, GIN_UNLOCK);
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 : : */
3005 teodor@sigaev.ru 244 : 8 : PredicateLockPage(btree->index, rootPostingTree, snapshot);
245 : :
246 : : /* Collect all the TIDs in this entry's posting tree */
1052 tmunro@postgresql.or 247 : 8 : 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 : : */
6645 tgl@sss.pgh.pa.us 253 : 8 : LockBuffer(stack->buffer, GIN_SHARE);
3749 kgrittn@postgresql.o 254 : 8 : page = BufferGetPage(stack->buffer);
6254 bruce@momjian.us 255 [ + - ]: 8 : 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 : : */
6645 tgl@sss.pgh.pa.us 262 :UBC 0 : return false;
263 : : }
264 : :
265 : : /* Search forward to re-find idatum */
266 : : for (;;)
267 : : {
3040 teodor@sigaev.ru 268 [ - + ]:CBC 8 : if (moveRightIfItNeeded(btree, stack, snapshot) == false)
2159 tgl@sss.pgh.pa.us 269 [ # # ]:UBC 0 : ereport(ERROR,
270 : : (errcode(ERRCODE_INTERNAL_ERROR),
271 : : errmsg("failed to re-find tuple within index \"%s\"",
272 : : RelationGetRelationName(btree->index))));
273 : :
3749 kgrittn@postgresql.o 274 :CBC 8 : page = BufferGetPage(stack->buffer);
6645 tgl@sss.pgh.pa.us 275 : 8 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
276 : :
2159 277 [ + - ]: 8 : if (gintuple_get_attrnum(btree->ginstate, itup) == attnum)
278 : : {
279 : : Datum newDatum;
280 : : GinNullCategory newCategory;
281 : :
282 : 8 : newDatum = gintuple_get_key(btree->ginstate, itup,
283 : : &newCategory);
284 : :
285 [ + - ]: 8 : if (ginCompareEntries(btree->ginstate, attnum,
286 : : newDatum, newCategory,
287 : : idatum, icategory) == 0)
288 : 8 : break; /* Found! */
289 : : }
290 : :
6645 tgl@sss.pgh.pa.us 291 :UBC 0 : stack->off++;
292 : : }
293 : :
5679 tgl@sss.pgh.pa.us 294 [ + - - + ]:CBC 8 : if (icategory == GIN_CAT_NORM_KEY && !attr->attbyval)
5679 tgl@sss.pgh.pa.us 295 :UBC 0 : pfree(DatumGetPointer(idatum));
296 : : }
297 : : else
298 : : {
299 : : ItemPointer ipd;
300 : : int nipd;
301 : :
4568 heikki.linnakangas@i 302 :CBC 270529 : ipd = ginReadTuple(btree->ginstate, scanEntry->attnum, itup, &nipd);
303 : 270529 : tbm_add_tuples(scanEntry->matchBitmap, ipd, nipd, false);
6254 bruce@momjian.us 304 : 270529 : scanEntry->predictNumberResult += GinGetNPosting(itup);
3754 tgl@sss.pgh.pa.us 305 : 270529 : pfree(ipd);
306 : : }
307 : :
308 : : /*
309 : : * Done with this entry, go to the next
310 : : */
6645 311 : 270537 : stack->off++;
312 : : }
313 : : }
314 : :
315 : : /*
316 : : * Start* functions setup beginning state of searches: finds correct buffer and pins it.
317 : : */
318 : : static void
3761 kgrittn@postgresql.o 319 : 3827 : startScanEntry(GinState *ginstate, GinScanEntry entry, Snapshot snapshot)
320 : : {
321 : : GinBtreeData btreeEntry;
322 : : GinBtreeStack *stackEntry;
323 : : Page page;
324 : : bool needUnlock;
325 : :
5679 tgl@sss.pgh.pa.us 326 : 3827 : restartScanEntry:
6333 327 : 3827 : entry->buffer = InvalidBuffer;
5678 328 : 3827 : ItemPointerSetMin(&entry->curItem);
6333 329 : 3827 : entry->offset = InvalidOffsetNumber;
3787 330 [ - + ]: 3827 : if (entry->list)
3787 tgl@sss.pgh.pa.us 331 :UBC 0 : pfree(entry->list);
6333 tgl@sss.pgh.pa.us 332 :CBC 3827 : entry->list = NULL;
333 : 3827 : entry->nlist = 0;
5679 334 : 3827 : entry->matchBitmap = NULL;
517 melanieplageman@gmai 335 : 3827 : entry->matchNtuples = -1;
498 336 : 3827 : entry->matchResult.blockno = InvalidBlockNumber;
3266 peter_e@gmx.net 337 : 3827 : entry->reduceResult = false;
6333 tgl@sss.pgh.pa.us 338 : 3827 : 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 : : */
5679 344 : 3827 : ginPrepareEntryScan(&btreeEntry, entry->attnum,
345 : 3827 : entry->queryKey, entry->queryCategory,
346 : : ginstate);
1052 tmunro@postgresql.or 347 : 3827 : stackEntry = ginFindLeafPage(&btreeEntry, true, false);
3749 kgrittn@postgresql.o 348 : 3827 : page = BufferGetPage(stackEntry->buffer);
349 : :
350 : : /* ginFindLeafPage() will have already checked snapshot age. */
3266 peter_e@gmx.net 351 : 3827 : needUnlock = true;
352 : :
353 : 3827 : entry->isFinished = true;
354 : :
5679 tgl@sss.pgh.pa.us 355 [ + + ]: 3827 : if (entry->isPartialMatch ||
356 [ + + ]: 3526 : entry->queryCategory == GIN_CAT_EMPTY_QUERY)
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 : : */
6645 365 : 486 : btreeEntry.findItem(&btreeEntry, stackEntry);
3749 kgrittn@postgresql.o 366 : 486 : if (collectMatchBitmap(&btreeEntry, stackEntry, entry, snapshot)
367 [ - + ]: 486 : == 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 : : */
5679 tgl@sss.pgh.pa.us 374 [ # # ]:UBC 0 : if (entry->matchBitmap)
375 : : {
376 [ # # ]: 0 : if (entry->matchIterator)
585 melanieplageman@gmai 377 : 0 : tbm_end_private_iterate(entry->matchIterator);
5679 tgl@sss.pgh.pa.us 378 : 0 : entry->matchIterator = NULL;
379 : 0 : tbm_free(entry->matchBitmap);
380 : 0 : entry->matchBitmap = NULL;
381 : : }
6645 382 : 0 : LockBuffer(stackEntry->buffer, GIN_UNLOCK);
383 : 0 : freeGinBtreeStack(stackEntry);
5679 384 : 0 : goto restartScanEntry;
385 : : }
386 : :
5679 tgl@sss.pgh.pa.us 387 [ + - + + ]:CBC 486 : if (entry->matchBitmap && !tbm_is_empty(entry->matchBitmap))
388 : : {
585 melanieplageman@gmai 389 : 388 : entry->matchIterator =
390 : 388 : tbm_begin_private_iterate(entry->matchBitmap);
3266 peter_e@gmx.net 391 : 388 : entry->isFinished = false;
392 : : }
393 : : }
6645 tgl@sss.pgh.pa.us 394 [ + + ]: 3341 : else if (btreeEntry.findItem(&btreeEntry, stackEntry))
395 : : {
6669 teodor@sigaev.ru 396 : 2435 : IndexTuple itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stackEntry->off));
397 : :
398 [ + + ]: 2435 : if (GinIsPostingTree(itup))
399 : : {
400 : 39 : 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 : : */
3005 410 : 39 : 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 : : */
7390 419 : 39 : LockBuffer(stackEntry->buffer, GIN_UNLOCK);
3266 peter_e@gmx.net 420 : 39 : needUnlock = false;
421 : :
4561 heikki.linnakangas@i 422 : 39 : stack = ginScanBeginPostingTree(&entry->btree, ginstate->index,
423 : : rootPostingTree);
4631 424 : 39 : 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 : : */
6669 teodor@sigaev.ru 431 : 39 : IncrBufferRefCount(entry->buffer);
432 : :
1390 drowley@postgresql.o 433 : 39 : entrypage = BufferGetPage(entry->buffer);
434 : :
435 : : /*
436 : : * Load the first page into memory.
437 : : */
4561 heikki.linnakangas@i 438 : 39 : ItemPointerSetMin(&minItem);
1390 drowley@postgresql.o 439 : 39 : entry->list = GinDataLeafPageGetItems(entrypage, &entry->nlist, minItem);
440 : :
4568 heikki.linnakangas@i 441 : 39 : entry->predictNumberResult = stack->predictNumber * entry->nlist;
442 : :
7235 bruce@momjian.us 443 : 39 : LockBuffer(entry->buffer, GIN_UNLOCK);
4631 heikki.linnakangas@i 444 : 39 : freeGinBtreeStack(stack);
3266 peter_e@gmx.net 445 : 39 : 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 : : */
3005 teodor@sigaev.ru 457 : 2396 : PredicateLockPage(ginstate->index,
458 : : BufferGetBlockNumber(stackEntry->buffer),
459 : : snapshot);
460 [ + + ]: 2396 : if (GinGetNPosting(itup) > 0)
461 : : {
462 : 2392 : entry->list = ginReadTuple(ginstate, entry->attnum, itup,
463 : : &entry->nlist);
464 : 2392 : entry->predictNumberResult = entry->nlist;
465 : :
466 : 2392 : 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 : 906 : PredicateLockPage(ginstate->index,
477 : : BufferGetBlockNumber(stackEntry->buffer), snapshot);
478 : : }
479 : :
6669 480 [ + + ]: 3827 : if (needUnlock)
6254 bruce@momjian.us 481 : 3788 : LockBuffer(stackEntry->buffer, GIN_UNLOCK);
6669 teodor@sigaev.ru 482 : 3827 : freeGinBtreeStack(stackEntry);
7390 483 : 3827 : }
484 : :
485 : : /*
486 : : * Comparison function for scan entry indexes. Sorts by predictNumberResult,
487 : : * least frequent items first.
488 : : */
489 : : static int
4552 heikki.linnakangas@i 490 : 4871 : entryIndexByFrequencyCmp(const void *a1, const void *a2, void *arg)
491 : : {
269 peter@eisentraut.org 492 : 4871 : const GinScanKeyData *key = arg;
4552 heikki.linnakangas@i 493 : 4871 : int i1 = *(const int *) a1;
494 : 4871 : int i2 = *(const int *) a2;
495 : 4871 : uint32 n1 = key->scanEntry[i1]->predictNumberResult;
496 : 4871 : uint32 n2 = key->scanEntry[i2]->predictNumberResult;
497 : :
498 [ + + ]: 4871 : if (n1 < n2)
499 : 728 : return -1;
500 [ + + ]: 4143 : else if (n1 == n2)
501 : 3185 : return 0;
502 : : else
503 : 958 : return 1;
504 : : }
505 : :
506 : : static void
507 : 1229 : startScanKey(GinState *ginstate, GinScanOpaque so, GinScanKey key)
508 : : {
509 : 1229 : MemoryContext oldCtx = CurrentMemoryContext;
510 : : int *entryIndexes;
511 : :
5678 tgl@sss.pgh.pa.us 512 : 1229 : ItemPointerSetMin(&key->curItem);
513 : 1229 : key->curItemMatches = false;
514 : 1229 : key->recheckCurItem = false;
515 : 1229 : key->isFinished = false;
516 : :
517 : : /*
518 : : * Divide the entries into two distinct sets: required and additional.
519 : : * Additional entries are not enough for a match alone, without any items
520 : : * from the required set, but are needed by the consistent function to
521 : : * decide if an item matches. When scanning, we can skip over items from
522 : : * additional entries that have no corresponding matches in any of the
523 : : * required entries. That speeds up queries like "frequent & rare"
524 : : * considerably, if the frequent term can be put in the additional set.
525 : : *
526 : : * There can be many legal ways to divide them entries into these two
527 : : * sets. A conservative division is to just put everything in the required
528 : : * set, but the more you can put in the additional set, the more you can
529 : : * skip during the scan. To maximize skipping, we try to put as many
530 : : * frequent items as possible into additional, and less frequent ones into
531 : : * required. To do that, sort the entries by frequency
532 : : * (predictNumberResult), and put entries into the required set in that
533 : : * order, until the consistent function says that none of the remaining
534 : : * entries can form a match, without any items from the required set. The
535 : : * rest go to the additional set.
536 : : *
537 : : * Exclude-only scan keys are known to have no required entries.
538 : : */
2381 akorotkov@postgresql 539 [ + + ]: 1229 : if (key->excludeOnly)
540 : : {
541 : 26 : MemoryContextSwitchTo(so->keyCtx);
542 : :
543 : 26 : key->nrequired = 0;
544 : 26 : key->nadditional = key->nentries;
545 : 26 : key->additionalEntries = palloc(key->nadditional * sizeof(GinScanEntry));
15 peter@eisentraut.org 546 [ + + ]:GNC 30 : for (int i = 0; i < key->nadditional; i++)
2381 akorotkov@postgresql 547 :CBC 4 : key->additionalEntries[i] = key->scanEntry[i];
548 : : }
549 [ + + ]: 1203 : else if (key->nentries > 1)
550 : : {
551 : : uint32 i;
552 : : int j;
553 : :
4552 heikki.linnakangas@i 554 : 350 : MemoryContextSwitchTo(so->tempCtx);
555 : :
228 michael@paquier.xyz 556 : 350 : entryIndexes = palloc_array(int, key->nentries);
4552 heikki.linnakangas@i 557 [ + + ]: 3320 : for (i = 0; i < key->nentries; i++)
558 : 2970 : entryIndexes[i] = i;
559 : 350 : qsort_arg(entryIndexes, key->nentries, sizeof(int),
560 : : entryIndexByFrequencyCmp, key);
561 : :
507 tgl@sss.pgh.pa.us 562 [ + + ]: 2970 : for (i = 1; i < key->nentries; i++)
563 : 2620 : key->entryRes[entryIndexes[i]] = GIN_MAYBE;
4552 heikki.linnakangas@i 564 [ + + ]: 2538 : for (i = 0; i < key->nentries - 1; i++)
565 : : {
566 : : /* Pass all entries <= i as FALSE, and the rest as MAYBE */
507 tgl@sss.pgh.pa.us 567 : 2448 : key->entryRes[entryIndexes[i]] = GIN_FALSE;
568 : :
4552 heikki.linnakangas@i 569 [ + + ]: 2448 : if (key->triConsistentFn(key) == GIN_FALSE)
570 : 260 : break;
571 : :
572 : : /* Make this loop interruptible in case there are many keys */
507 tgl@sss.pgh.pa.us 573 [ - + ]: 2188 : CHECK_FOR_INTERRUPTS();
574 : : }
575 : : /* i is now the last required entry. */
576 : :
4190 heikki.linnakangas@i 577 : 350 : MemoryContextSwitchTo(so->keyCtx);
578 : :
4552 579 : 350 : key->nrequired = i + 1;
580 : 350 : key->nadditional = key->nentries - key->nrequired;
581 : 350 : key->requiredEntries = palloc(key->nrequired * sizeof(GinScanEntry));
582 : 350 : key->additionalEntries = palloc(key->nadditional * sizeof(GinScanEntry));
583 : :
584 : 350 : j = 0;
15 peter@eisentraut.org 585 [ + + ]:GNC 2888 : for (int k = 0; k < key->nrequired; k++)
586 : 2538 : key->requiredEntries[k] = key->scanEntry[entryIndexes[j++]];
587 [ + + ]: 782 : for (int k = 0; k < key->nadditional; k++)
588 : 432 : key->additionalEntries[k] = key->scanEntry[entryIndexes[j++]];
589 : :
590 : : /* clean up after consistentFn calls (also frees entryIndexes) */
4552 heikki.linnakangas@i 591 :CBC 350 : MemoryContextReset(so->tempCtx);
592 : : }
593 : : else
594 : : {
4190 595 : 853 : MemoryContextSwitchTo(so->keyCtx);
596 : :
4552 597 : 853 : key->nrequired = 1;
598 : 853 : key->nadditional = 0;
599 : 853 : key->requiredEntries = palloc(1 * sizeof(GinScanEntry));
600 : 853 : key->requiredEntries[0] = key->scanEntry[0];
601 : : }
4190 602 : 1229 : MemoryContextSwitchTo(oldCtx);
5678 tgl@sss.pgh.pa.us 603 : 1229 : }
604 : :
605 : : static void
606 : 1143 : startScan(IndexScanDesc scan)
607 : : {
608 : 1143 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
609 : 1143 : GinState *ginstate = &so->ginstate;
610 : : uint32 i;
611 : :
612 [ + + ]: 4970 : for (i = 0; i < so->totalentries; i++)
3761 kgrittn@postgresql.o 613 : 3827 : startScanEntry(ginstate, so->entries[i], scan->xs_snapshot);
614 : :
6669 teodor@sigaev.ru 615 [ + + ]: 1143 : if (GinFuzzySearchLimit > 0)
616 : : {
617 : : /*
618 : : * If all of keys more than threshold we will try to reduce result, we
619 : : * hope (and only hope, for intersection operation of array our
620 : : * supposition isn't true), that total result will not more than
621 : : * minimal predictNumberResult.
622 : : */
4196 heikki.linnakangas@i 623 : 4 : bool reduce = true;
624 : :
5678 tgl@sss.pgh.pa.us 625 [ + + ]: 8 : for (i = 0; i < so->totalentries; i++)
626 : : {
627 [ - + ]: 4 : if (so->entries[i]->predictNumberResult <= so->totalentries * GinFuzzySearchLimit)
628 : : {
4196 heikki.linnakangas@i 629 :UBC 0 : reduce = false;
630 : 0 : break;
631 : : }
632 : : }
4196 heikki.linnakangas@i 633 [ + - ]:CBC 4 : if (reduce)
634 : : {
635 [ + + ]: 8 : for (i = 0; i < so->totalentries; i++)
636 : : {
5678 tgl@sss.pgh.pa.us 637 : 4 : so->entries[i]->predictNumberResult /= so->totalentries;
3266 peter_e@gmx.net 638 : 4 : so->entries[i]->reduceResult = true;
639 : : }
640 : : }
641 : : }
642 : :
643 : : /*
644 : : * Now that we have the estimates for the entry frequencies, finish
645 : : * initializing the scan keys.
646 : : */
7235 bruce@momjian.us 647 [ + + ]: 2372 : for (i = 0; i < so->nkeys; i++)
4552 heikki.linnakangas@i 648 : 1229 : startScanKey(ginstate, so, so->keys + i);
7390 teodor@sigaev.ru 649 : 1143 : }
650 : :
651 : : /*
652 : : * Load the next batch of item pointers from a posting tree.
653 : : *
654 : : * Note that we copy the page into GinScanEntry->list array and unlock it, but
655 : : * keep it pinned to prevent interference with vacuum.
656 : : */
657 : : static void
3761 kgrittn@postgresql.o 658 : 63 : entryLoadMoreItems(GinState *ginstate, GinScanEntry entry,
659 : : ItemPointerData advancePast)
660 : : {
661 : : Page page;
662 : : int i;
663 : : bool stepright;
664 : :
4561 heikki.linnakangas@i 665 [ - + ]: 63 : if (!BufferIsValid(entry->buffer))
666 : : {
4561 heikki.linnakangas@i 667 :UBC 0 : entry->isFinished = true;
668 : 0 : return;
669 : : }
670 : :
671 : : /*
672 : : * We have two strategies for finding the correct page: step right from
673 : : * the current page, or descend the tree again from the root. If
674 : : * advancePast equals the current item, the next matching item should be
675 : : * on the next page, so we step right. Otherwise, descend from root.
676 : : */
4561 heikki.linnakangas@i 677 [ + + ]:CBC 63 : if (ginCompareItemPointers(&entry->curItem, &advancePast) == 0)
678 : : {
679 : 59 : stepright = true;
680 : 59 : LockBuffer(entry->buffer, GIN_SHARE);
681 : : }
682 : : else
683 : : {
684 : : GinBtreeStack *stack;
685 : :
686 : 4 : ReleaseBuffer(entry->buffer);
687 : :
688 : : /*
689 : : * Set the search key, and find the correct leaf page.
690 : : */
691 [ - + - - ]: 4 : if (ItemPointerIsLossyPage(&advancePast))
692 : : {
4561 heikki.linnakangas@i 693 :UBC 0 : ItemPointerSet(&entry->btree.itemptr,
694 : 0 : GinItemPointerGetBlockNumber(&advancePast) + 1,
695 : : FirstOffsetNumber);
696 : : }
697 : : else
698 : : {
3407 alvherre@alvh.no-ip. 699 :CBC 4 : ItemPointerSet(&entry->btree.itemptr,
700 : : GinItemPointerGetBlockNumber(&advancePast),
3322 tgl@sss.pgh.pa.us 701 : 4 : OffsetNumberNext(GinItemPointerGetOffsetNumber(&advancePast)));
702 : : }
4561 heikki.linnakangas@i 703 : 4 : entry->btree.fullScan = false;
1052 tmunro@postgresql.or 704 : 4 : stack = ginFindLeafPage(&entry->btree, true, false);
705 : :
706 : : /* we don't need the stack, just the buffer. */
4561 heikki.linnakangas@i 707 : 4 : entry->buffer = stack->buffer;
708 : 4 : IncrBufferRefCount(entry->buffer);
709 : 4 : freeGinBtreeStack(stack);
710 : 4 : stepright = false;
711 : : }
712 : :
713 [ - + ]: 63 : elog(DEBUG2, "entryLoadMoreItems, %u/%u, skip: %d",
714 : : GinItemPointerGetBlockNumber(&advancePast),
715 : : GinItemPointerGetOffsetNumber(&advancePast),
716 : : !stepright);
717 : :
3749 kgrittn@postgresql.o 718 : 63 : page = BufferGetPage(entry->buffer);
719 : : for (;;)
720 : : {
4561 heikki.linnakangas@i 721 : 67 : entry->offset = InvalidOffsetNumber;
722 [ + + ]: 67 : if (entry->list)
723 : : {
724 : 59 : pfree(entry->list);
725 : 59 : entry->list = NULL;
726 : 59 : entry->nlist = 0;
727 : : }
728 : :
729 [ + + ]: 67 : if (stepright)
730 : : {
731 : : /*
732 : : * We've processed all the entries on this page. If it was the
733 : : * last page in the tree, we're done.
734 : : */
735 [ + + ]: 63 : if (GinPageRightMost(page))
736 : : {
737 : 4 : UnlockReleaseBuffer(entry->buffer);
738 : 4 : entry->buffer = InvalidBuffer;
3266 peter_e@gmx.net 739 : 4 : entry->isFinished = true;
4561 heikki.linnakangas@i 740 : 4 : return;
741 : : }
742 : :
743 : : /*
744 : : * Step to next page, following the right link. then find the
745 : : * first ItemPointer greater than advancePast.
746 : : */
747 : 59 : entry->buffer = ginStepRight(entry->buffer,
748 : : ginstate->index,
749 : : GIN_SHARE);
3749 kgrittn@postgresql.o 750 : 59 : page = BufferGetPage(entry->buffer);
751 : : }
4561 heikki.linnakangas@i 752 : 63 : stepright = true;
753 : :
754 [ - + ]: 63 : if (GinPageGetOpaque(page)->flags & GIN_DELETED)
4464 bruce@momjian.us 755 :UBC 0 : continue; /* page was deleted by concurrent vacuum */
756 : :
757 : : /*
758 : : * The first item > advancePast might not be on this page, but
759 : : * somewhere to the right, if the page was split, or a non-match from
760 : : * another key in the query allowed us to skip some items from this
761 : : * entry. Keep following the right-links until we re-find the correct
762 : : * page.
763 : : */
4561 heikki.linnakangas@i 764 [ + + - + ]:CBC 87 : if (!GinPageRightMost(page) &&
765 : 24 : ginCompareItemPointers(&advancePast, GinDataPageGetRightBound(page)) >= 0)
766 : : {
767 : : /*
768 : : * the item we're looking is > the right bound of the page, so it
769 : : * can't be on this page.
770 : : */
4561 heikki.linnakangas@i 771 :UBC 0 : continue;
772 : : }
773 : :
4561 heikki.linnakangas@i 774 :CBC 63 : entry->list = GinDataLeafPageGetItems(page, &entry->nlist, advancePast);
775 : :
776 [ + + ]: 1279 : for (i = 0; i < entry->nlist; i++)
777 : : {
778 [ + + ]: 1275 : if (ginCompareItemPointers(&advancePast, &entry->list[i]) < 0)
779 : : {
780 : 59 : entry->offset = i;
781 : :
782 [ + + ]: 59 : if (GinPageRightMost(page))
783 : : {
784 : : /* after processing the copied items, we're done. */
785 : 35 : UnlockReleaseBuffer(entry->buffer);
786 : 35 : entry->buffer = InvalidBuffer;
787 : : }
788 : : else
789 : 24 : LockBuffer(entry->buffer, GIN_UNLOCK);
6669 teodor@sigaev.ru 790 : 59 : return;
791 : : }
792 : : }
793 : : }
794 : : }
795 : :
796 : : #define gin_rand() pg_prng_double(&pg_global_prng_state)
797 : : #define dropItem(e) ( gin_rand() > ((double)GinFuzzySearchLimit)/((double)((e)->predictNumberResult)) )
798 : :
799 : : /*
800 : : * Sets entry->curItem to next heap item pointer > advancePast, for one entry
801 : : * of one scan key, or sets entry->isFinished to true if there are no more.
802 : : *
803 : : * Item pointers are returned in ascending order.
804 : : *
805 : : * Note: this can return a "lossy page" item pointer, indicating that the
806 : : * entry potentially matches all items on that heap page. However, it is
807 : : * not allowed to return both a lossy page pointer and exact (regular)
808 : : * item pointers for the same page. (Doing so would break the key-combination
809 : : * logic in keyGetItem and scanGetItem; see comment in scanGetItem.) In the
810 : : * current implementation this is guaranteed by the behavior of tidbitmaps.
811 : : */
812 : : static void
4561 heikki.linnakangas@i 813 : 679743 : entryGetItem(GinState *ginstate, GinScanEntry entry,
814 : : ItemPointerData advancePast)
815 : : {
5839 tgl@sss.pgh.pa.us 816 [ - + ]: 679743 : Assert(!entry->isFinished);
817 : :
4561 heikki.linnakangas@i 818 [ + + - + ]: 679743 : Assert(!ItemPointerIsValid(&entry->curItem) ||
819 : : ginCompareItemPointers(&entry->curItem, &advancePast) <= 0);
820 : :
5678 tgl@sss.pgh.pa.us 821 [ + + ]: 679743 : if (entry->matchBitmap)
822 : : {
823 : : /* A bitmap result */
4561 heikki.linnakangas@i 824 : 174137 : BlockNumber advancePastBlk = GinItemPointerGetBlockNumber(&advancePast);
825 : 174137 : OffsetNumber advancePastOff = GinItemPointerGetOffsetNumber(&advancePast);
826 : :
827 : : for (;;)
828 : : {
829 : : /*
830 : : * If we've exhausted all items on this block, move to next block
831 : : * in the bitmap. tbm_private_iterate() sets matchResult.blockno
832 : : * to InvalidBlockNumber when the bitmap is exhausted.
833 : : */
498 melanieplageman@gmai 834 : 177424 : while ((!BlockNumberIsValid(entry->matchResult.blockno)) ||
835 [ + - ]: 177036 : (!entry->matchResult.lossy &&
517 836 [ + + ]: 177036 : entry->offset >= entry->matchNtuples) ||
498 837 [ + + - + : 524922 : entry->matchResult.blockno < advancePastBlk ||
- + ]
4460 heikki.linnakangas@i 838 [ - - ]: 173749 : (ItemPointerIsLossyPage(&advancePast) &&
498 melanieplageman@gmai 839 [ # # ]:UBC 0 : entry->matchResult.blockno == advancePastBlk))
840 : : {
498 melanieplageman@gmai 841 [ + + ]:CBC 3675 : if (!tbm_private_iterate(entry->matchIterator, &entry->matchResult))
842 : : {
843 [ - + ]: 388 : Assert(!BlockNumberIsValid(entry->matchResult.blockno));
5839 tgl@sss.pgh.pa.us 844 : 388 : ItemPointerSetInvalid(&entry->curItem);
585 melanieplageman@gmai 845 : 388 : tbm_end_private_iterate(entry->matchIterator);
5679 tgl@sss.pgh.pa.us 846 : 388 : entry->matchIterator = NULL;
3266 peter_e@gmx.net 847 : 388 : entry->isFinished = true;
6645 tgl@sss.pgh.pa.us 848 : 388 : break;
849 : : }
850 : :
851 : : /* Exact pages need their tuple offsets extracted. */
498 melanieplageman@gmai 852 [ + - ]: 3287 : if (!entry->matchResult.lossy)
853 : 3287 : entry->matchNtuples = tbm_extract_page_tuple(&entry->matchResult,
517 854 : 3287 : entry->matchOffsets,
855 : : TBM_MAX_TUPLES_PER_PAGE);
856 : :
857 : : /*
858 : : * Reset counter to the beginning of entry->matchResult. Note:
859 : : * entry->offset is still greater than matchResult.ntuples if
860 : : * matchResult is lossy. So, on next call we will get next
861 : : * result from TIDBitmap.
862 : : */
6645 tgl@sss.pgh.pa.us 863 : 3287 : entry->offset = 0;
864 : : }
4490 heikki.linnakangas@i 865 [ + + ]: 174137 : if (entry->isFinished)
866 : 388 : break;
867 : :
868 : : /*
869 : : * We're now on the first page after advancePast which has any
870 : : * items on it. If it's a lossy result, return that.
871 : : */
498 melanieplageman@gmai 872 [ - + ]: 173749 : if (entry->matchResult.lossy)
873 : : {
6333 tgl@sss.pgh.pa.us 874 :UBC 0 : ItemPointerSetLossyPage(&entry->curItem,
875 : : entry->matchResult.blockno);
876 : :
877 : : /*
878 : : * We might as well fall out of the loop; we could not
879 : : * estimate number of results on this page to support correct
880 : : * reducing of result even if it's enabled.
881 : : */
882 : 0 : break;
883 : : }
884 : :
885 : : /*
886 : : * Not a lossy page. If tuple offsets were extracted,
887 : : * entry->matchNtuples must be > -1
888 : : */
517 melanieplageman@gmai 889 [ - + ]:CBC 173749 : Assert(entry->matchNtuples > -1);
890 : :
891 : : /* Skip over any offsets <= advancePast, and return that. */
498 892 [ + + ]: 173749 : if (entry->matchResult.blockno == advancePastBlk)
893 : : {
517 894 [ - + ]: 170850 : Assert(entry->matchNtuples > 0);
895 : :
896 : : /*
897 : : * First, do a quick check against the last offset on the
898 : : * page. If that's > advancePast, so are all the other
899 : : * offsets, so just go back to the top to get the next page.
900 : : */
901 [ - + ]: 170850 : if (entry->matchOffsets[entry->matchNtuples - 1] <= advancePastOff)
902 : : {
517 melanieplageman@gmai 903 :UBC 0 : entry->offset = entry->matchNtuples;
4490 heikki.linnakangas@i 904 : 0 : continue;
905 : : }
906 : :
907 : : /* Otherwise scan to find the first item > advancePast */
517 melanieplageman@gmai 908 [ - + ]:CBC 170850 : while (entry->matchOffsets[entry->offset] <= advancePastOff)
4561 heikki.linnakangas@i 909 :UBC 0 : entry->offset++;
910 : : }
911 : :
6333 tgl@sss.pgh.pa.us 912 :CBC 173749 : ItemPointerSet(&entry->curItem,
913 : : entry->matchResult.blockno,
517 melanieplageman@gmai 914 : 173749 : entry->matchOffsets[entry->offset]);
6333 tgl@sss.pgh.pa.us 915 : 173749 : entry->offset++;
916 : :
917 : : /* Done unless we need to reduce the result */
2305 918 [ - + - - ]: 173749 : if (!entry->reduceResult || !dropItem(entry))
919 : : break;
920 : : }
921 : : }
6669 teodor@sigaev.ru 922 [ + + ]: 505606 : else if (!BufferIsValid(entry->buffer))
923 : : {
924 : : /*
925 : : * A posting list from an entry tuple, or the last page of a posting
926 : : * tree.
927 : : */
928 : : for (;;)
929 : : {
4561 heikki.linnakangas@i 930 [ + + ]: 245961 : if (entry->offset >= entry->nlist)
931 : : {
932 : 2100 : ItemPointerSetInvalid(&entry->curItem);
3266 peter_e@gmx.net 933 : 2100 : entry->isFinished = true;
4561 heikki.linnakangas@i 934 : 2100 : break;
935 : : }
936 : :
937 : 243861 : entry->curItem = entry->list[entry->offset++];
938 : :
939 : : /* If we're not past advancePast, keep scanning */
2305 tgl@sss.pgh.pa.us 940 [ + + ]: 243861 : if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
941 : 39787 : continue;
942 : :
943 : : /* Done unless we need to reduce the result */
944 [ + + + + ]: 204074 : if (!entry->reduceResult || !dropItem(entry))
945 : : break;
946 : : }
947 : : }
948 : : else
949 : : {
950 : : /* A posting tree */
951 : : for (;;)
952 : : {
953 : : /* If we've processed the current batch, load more items */
4561 heikki.linnakangas@i 954 [ + + ]: 423811 : while (entry->offset >= entry->nlist)
955 : : {
1052 tmunro@postgresql.or 956 : 63 : entryLoadMoreItems(ginstate, entry, advancePast);
957 : :
4561 heikki.linnakangas@i 958 [ + + ]: 63 : if (entry->isFinished)
959 : : {
960 : 4 : ItemPointerSetInvalid(&entry->curItem);
961 : 4 : return;
962 : : }
963 : : }
964 : :
965 : 423748 : entry->curItem = entry->list[entry->offset++];
966 : :
967 : : /* If we're not past advancePast, keep scanning */
2305 tgl@sss.pgh.pa.us 968 [ + + ]: 423748 : if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
969 : 31404 : continue;
970 : :
971 : : /* Done unless we need to reduce the result */
972 [ + + + + ]: 392344 : if (!entry->reduceResult || !dropItem(entry))
973 : : break;
974 : :
975 : : /*
976 : : * Advance advancePast (so that entryLoadMoreItems will load the
977 : : * right data), and keep scanning
978 : : */
979 : 79237 : advancePast = entry->curItem;
980 : : }
981 : : }
982 : : }
983 : :
984 : : /*
985 : : * Identify the "current" item among the input entry streams for this scan key
986 : : * that is greater than advancePast, and test whether it passes the scan key
987 : : * qual condition.
988 : : *
989 : : * The current item is the smallest curItem among the inputs. key->curItem
990 : : * is set to that value. key->curItemMatches is set to indicate whether that
991 : : * TID passes the consistentFn test. If so, key->recheckCurItem is set true
992 : : * iff recheck is needed for this item pointer (including the case where the
993 : : * item pointer is a lossy page pointer).
994 : : *
995 : : * If all entry streams are exhausted, sets key->isFinished to true.
996 : : *
997 : : * Item pointers must be returned in ascending order.
998 : : *
999 : : * Note: this can return a "lossy page" item pointer, indicating that the
1000 : : * key potentially matches all items on that heap page. However, it is
1001 : : * not allowed to return both a lossy page pointer and exact (regular)
1002 : : * item pointers for the same page. (Doing so would break the key-combination
1003 : : * logic in scanGetItem.)
1004 : : */
1005 : : static void
4561 heikki.linnakangas@i 1006 : 630153 : keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key,
1007 : : ItemPointerData advancePast)
1008 : : {
1009 : : ItemPointerData minItem;
1010 : : ItemPointerData curPageLossy;
1011 : : bool haveLossyEntry;
1012 : : GinScanEntry entry;
1013 : : GinTernaryValue res;
1014 : : MemoryContext oldCtx;
1015 : : bool allFinished;
1016 : :
5839 tgl@sss.pgh.pa.us 1017 [ - + ]: 630153 : 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 : : */
4561 heikki.linnakangas@i 1024 [ + + ]: 630153 : if (ginCompareItemPointers(&key->curItem, &advancePast) > 0)
1025 : 1151 : 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 : : */
5678 tgl@sss.pgh.pa.us 1035 : 630145 : ItemPointerSetMax(&minItem);
4561 heikki.linnakangas@i 1036 : 630145 : allFinished = true;
15 peter@eisentraut.org 1037 [ + + ]:GNC 1646272 : for (int i = 0; i < key->nrequired; i++)
1038 : : {
4552 heikki.linnakangas@i 1039 :CBC 1016127 : entry = key->requiredEntries[i];
1040 : :
1041 [ + + ]: 1016127 : if (entry->isFinished)
1042 : 282272 : 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 [ + + ]: 733855 : if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
1052 : : {
1052 tmunro@postgresql.or 1053 : 647232 : entryGetItem(ginstate, entry, advancePast);
4552 heikki.linnakangas@i 1054 [ + + ]: 647232 : if (entry->isFinished)
1055 : 2398 : continue;
1056 : : }
1057 : :
1058 : 731457 : allFinished = false;
1059 [ + + ]: 731457 : if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
1060 : 680686 : minItem = entry->curItem;
1061 : : }
1062 : :
2381 akorotkov@postgresql 1063 [ + + + + ]: 630145 : if (allFinished && !key->excludeOnly)
1064 : : {
1065 : : /* all entries are finished */
3266 peter_e@gmx.net 1066 : 1143 : key->isFinished = true;
5678 tgl@sss.pgh.pa.us 1067 : 1143 : return;
1068 : : }
1069 : :
2381 akorotkov@postgresql 1070 [ + + ]: 629002 : 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 [ - + - - ]: 625694 : if (ItemPointerIsLossyPage(&minItem))
1081 : : {
2381 akorotkov@postgresql 1082 [ # # ]:UBC 0 : if (GinItemPointerGetBlockNumber(&advancePast) <
1083 : 0 : GinItemPointerGetBlockNumber(&minItem))
1084 : : {
1085 : 0 : ItemPointerSet(&advancePast,
1086 : : GinItemPointerGetBlockNumber(&minItem),
1087 : : InvalidOffsetNumber);
1088 : : }
1089 : : }
1090 : : else
1091 : : {
2381 akorotkov@postgresql 1092 [ - + ]:CBC 625694 : Assert(GinItemPointerGetOffsetNumber(&minItem) > 0);
3407 alvherre@alvh.no-ip. 1093 : 625694 : ItemPointerSet(&advancePast,
1094 : : GinItemPointerGetBlockNumber(&minItem),
2381 akorotkov@postgresql 1095 : 625694 : OffsetNumberPrev(GinItemPointerGetOffsetNumber(&minItem)));
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 [ - + ]: 3308 : Assert(key->nrequired == 0);
1106 : 3308 : ItemPointerSet(&minItem,
1107 : : GinItemPointerGetBlockNumber(&advancePast),
1108 : 3308 : OffsetNumberNext(GinItemPointerGetOffsetNumber(&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 : : */
15 peter@eisentraut.org 1119 [ + + ]:GNC 668763 : for (int i = 0; i < key->nadditional; i++)
1120 : : {
4552 heikki.linnakangas@i 1121 :CBC 39761 : entry = key->additionalEntries[i];
1122 : :
1123 [ + + ]: 39761 : if (entry->isFinished)
1124 : 207 : continue;
1125 : :
1126 [ + + ]: 39554 : if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
1127 : : {
1052 tmunro@postgresql.or 1128 : 32511 : entryGetItem(ginstate, entry, advancePast);
4552 heikki.linnakangas@i 1129 [ + + ]: 32511 : if (entry->isFinished)
1130 : 94 : 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 [ - + ]: 39460 : if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
1139 : : {
4552 heikki.linnakangas@i 1140 [ # # # # ]:UBC 0 : Assert(ItemPointerIsLossyPage(&minItem));
1141 : 0 : 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 : : */
4552 heikki.linnakangas@i 1175 :CBC 629002 : key->curItem = minItem;
5678 tgl@sss.pgh.pa.us 1176 : 629002 : ItemPointerSetLossyPage(&curPageLossy,
1177 : : GinItemPointerGetBlockNumber(&key->curItem));
1178 : 629002 : haveLossyEntry = false;
15 peter@eisentraut.org 1179 [ + + ]:GNC 1681559 : for (uint32 i = 0; i < key->nentries; i++)
1180 : : {
5678 tgl@sss.pgh.pa.us 1181 :CBC 1052557 : entry = key->scanEntry[i];
3266 peter_e@gmx.net 1182 [ + + - + ]: 1823474 : if (entry->isFinished == false &&
5678 tgl@sss.pgh.pa.us 1183 : 770917 : ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0)
1184 : : {
4552 heikki.linnakangas@i 1185 [ # # ]:UBC 0 : if (i < key->nuserentries)
1186 : 0 : key->entryRes[i] = GIN_MAYBE;
1187 : : else
1188 : 0 : key->entryRes[i] = GIN_TRUE;
5678 tgl@sss.pgh.pa.us 1189 : 0 : haveLossyEntry = true;
1190 : : }
1191 : : else
4552 heikki.linnakangas@i 1192 :CBC 1052557 : key->entryRes[i] = GIN_FALSE;
1193 : : }
1194 : :
1195 : : /* prepare for calling consistentFn in temp context */
5678 tgl@sss.pgh.pa.us 1196 : 629002 : oldCtx = MemoryContextSwitchTo(tempCtx);
1197 : :
1198 [ - + ]: 629002 : if (haveLossyEntry)
1199 : : {
1200 : : /* Have lossy-page entries, so see if whole page matches */
4552 heikki.linnakangas@i 1201 :UBC 0 : res = key->triConsistentFn(key);
1202 : :
1203 [ # # # # ]: 0 : if (res == GIN_TRUE || res == GIN_MAYBE)
1204 : : {
1205 : : /* Yes, so clean up ... */
5678 tgl@sss.pgh.pa.us 1206 : 0 : MemoryContextSwitchTo(oldCtx);
1207 : 0 : MemoryContextReset(tempCtx);
1208 : :
1209 : : /* and return lossy pointer for whole page */
1210 : 0 : key->curItem = curPageLossy;
1211 : 0 : key->curItemMatches = true;
1212 : 0 : key->recheckCurItem = true;
1213 : 0 : 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 : : */
15 peter@eisentraut.org 1227 [ + + ]:GNC 1681559 : for (uint32 i = 0; i < key->nentries; i++)
1228 : : {
5678 tgl@sss.pgh.pa.us 1229 :CBC 1052557 : entry = key->scanEntry[i];
4552 heikki.linnakangas@i 1230 [ + + ]: 1052557 : if (entry->isFinished)
1231 : 281640 : 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 [ - + ]: 770917 : else if (ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0)
4552 heikki.linnakangas@i 1242 :UBC 0 : key->entryRes[i] = GIN_MAYBE;
4552 heikki.linnakangas@i 1243 [ + + ]:CBC 770917 : else if (ginCompareItemPointers(&entry->curItem, &minItem) == 0)
1244 : 671151 : key->entryRes[i] = GIN_TRUE;
1245 : : else
1246 : 99766 : key->entryRes[i] = GIN_FALSE;
1247 : : }
1248 : :
1249 : 629002 : res = key->triConsistentFn(key);
1250 : :
1251 [ + + + - ]: 629002 : switch (res)
1252 : : {
1253 : 542119 : case GIN_TRUE:
1254 : 542119 : key->curItemMatches = true;
1255 : : /* triConsistentFn set recheckCurItem */
1256 : 542119 : break;
1257 : :
1258 : 11444 : case GIN_FALSE:
1259 : 11444 : key->curItemMatches = false;
1260 : 11444 : break;
1261 : :
1262 : 75439 : case GIN_MAYBE:
1263 : 75439 : key->curItemMatches = true;
1264 : 75439 : key->recheckCurItem = true;
1265 : 75439 : break;
1266 : :
4552 heikki.linnakangas@i 1267 :UBC 0 : 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 : 0 : key->curItemMatches = true;
1274 : 0 : key->recheckCurItem = true;
1275 : 0 : 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 */
5678 tgl@sss.pgh.pa.us 1286 :CBC 629002 : MemoryContextSwitchTo(oldCtx);
1287 : 629002 : MemoryContextReset(tempCtx);
1288 : : }
1289 : :
1290 : : /*
1291 : : * Get next heap item pointer (after advancePast) from scan.
1292 : : * Returns true if anything found.
1293 : : * On success, *item and *recheck are set.
1294 : : *
1295 : : * Note: this is very nearly the same logic as in keyGetItem(), except
1296 : : * that we know the keys are to be combined with AND logic, whereas in
1297 : : * keyGetItem() the combination logic is known only to the consistentFn.
1298 : : */
1299 : : static bool
4561 heikki.linnakangas@i 1300 : 615329 : scanGetItem(IndexScanDesc scan, ItemPointerData advancePast,
1301 : : ItemPointerData *item, bool *recheck)
1302 : : {
5679 tgl@sss.pgh.pa.us 1303 : 615329 : 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 : : {
334 1330 [ - + ]: 626805 : CHECK_FOR_INTERRUPTS();
1331 : :
4561 heikki.linnakangas@i 1332 : 626805 : ItemPointerSetMin(item);
1333 : 626805 : match = true;
1334 [ + + + - ]: 1244371 : for (i = 0; i < so->nkeys && match; i++)
1335 : : {
5679 tgl@sss.pgh.pa.us 1336 : 630153 : 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 : : */
2381 akorotkov@postgresql 1342 [ - + - - : 630153 : if (ItemPointerIsLossyPage(item) && key->excludeOnly)
- - ]
1343 : : {
1344 : : /*
1345 : : * ginNewScanKey() should never mark the first key as
1346 : : * excludeOnly.
1347 : : */
2381 akorotkov@postgresql 1348 [ # # ]:UBC 0 : Assert(i > 0);
1349 : 0 : continue;
1350 : : }
1351 : :
1352 : : /* Fetch the next item for this key that is > advancePast. */
1052 tmunro@postgresql.or 1353 :CBC 630153 : keyGetItem(&so->ginstate, so->tempCtx, key, advancePast);
1354 : :
5679 tgl@sss.pgh.pa.us 1355 [ + + ]: 630153 : if (key->isFinished)
4561 heikki.linnakangas@i 1356 : 1143 : 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 [ + + ]: 629010 : if (!key->curItemMatches)
1363 : : {
1364 : 11444 : advancePast = key->curItem;
1365 : 11444 : match = false;
1366 : 11444 : 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 [ - + - - ]: 617566 : if (ItemPointerIsLossyPage(&key->curItem))
1377 : : {
4561 heikki.linnakangas@i 1378 [ # # ]:UBC 0 : if (GinItemPointerGetBlockNumber(&advancePast) <
1379 : 0 : GinItemPointerGetBlockNumber(&key->curItem))
1380 : : {
3407 alvherre@alvh.no-ip. 1381 : 0 : ItemPointerSet(&advancePast,
3322 tgl@sss.pgh.pa.us 1382 : 0 : GinItemPointerGetBlockNumber(&key->curItem),
1383 : : InvalidOffsetNumber);
1384 : : }
1385 : : }
1386 : : else
1387 : : {
3407 alvherre@alvh.no-ip. 1388 [ - + ]:CBC 617566 : Assert(GinItemPointerGetOffsetNumber(&key->curItem) > 0);
1389 : 617566 : ItemPointerSet(&advancePast,
1390 : 617566 : GinItemPointerGetBlockNumber(&key->curItem),
1391 : 617566 : OffsetNumberPrev(GinItemPointerGetOffsetNumber(&key->curItem)));
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 : : */
4561 heikki.linnakangas@i 1404 [ + + ]: 617566 : if (i == 0)
1405 : : {
1406 : 615286 : *item = key->curItem;
1407 : : }
1408 : : else
1409 : : {
1410 [ - + - - : 4560 : if (ItemPointerIsLossyPage(&key->curItem) ||
- + ]
1411 [ - - ]: 2280 : ItemPointerIsLossyPage(item))
1412 : : {
4464 bruce@momjian.us 1413 [ # # ]:UBC 0 : Assert(GinItemPointerGetBlockNumber(&key->curItem) >= GinItemPointerGetBlockNumber(item));
4561 heikki.linnakangas@i 1414 : 0 : match = (GinItemPointerGetBlockNumber(&key->curItem) ==
1415 : 0 : GinItemPointerGetBlockNumber(item));
1416 : : }
1417 : : else
1418 : : {
4561 heikki.linnakangas@i 1419 [ - + ]:CBC 2280 : Assert(ginCompareItemPointers(&key->curItem, item) >= 0);
1420 : 2280 : match = (ginCompareItemPointers(&key->curItem, item) == 0);
1421 : : }
1422 : : }
1423 : : }
1424 [ + + ]: 625662 : } while (!match);
1425 : :
1426 [ - + - - ]: 614186 : 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 : : */
5679 tgl@sss.pgh.pa.us 1435 : 614186 : *recheck = false;
1436 [ + + ]: 1145026 : for (i = 0; i < so->nkeys; i++)
1437 : : {
1438 : 614434 : GinScanKey key = so->keys + i;
1439 : :
1440 [ + + ]: 614434 : if (key->recheckCurItem)
1441 : : {
1442 : 83594 : *recheck = true;
1443 : 83594 : break;
1444 : : }
1445 : : }
1446 : :
3266 peter_e@gmx.net 1447 : 614186 : return true;
1448 : : }
1449 : :
1450 : :
1451 : : /*
1452 : : * Functions for scanning the pending list
1453 : : */
1454 : :
1455 : :
1456 : : /*
1457 : : * Get ItemPointer of next heap row to be checked from pending list.
1458 : : * Returns false if there are no more. On pages with several heap rows
1459 : : * it returns each row separately, on page with part of heap row returns
1460 : : * per page data. pos->firstOffset and pos->lastOffset are set to identify
1461 : : * the range of pending-list tuples belonging to this heap row.
1462 : : *
1463 : : * The pendingBuffer is presumed pinned and share-locked on entry, and is
1464 : : * pinned and share-locked on success exit. On failure exit it's released.
1465 : : */
1466 : : static bool
6333 tgl@sss.pgh.pa.us 1467 : 1072 : scanGetCandidate(IndexScanDesc scan, pendingPosition *pos)
1468 : : {
1469 : : OffsetNumber maxoff;
1470 : : Page page;
1471 : : IndexTuple itup;
1472 : :
6254 bruce@momjian.us 1473 : 1072 : ItemPointerSetInvalid(&pos->item);
1474 : : for (;;)
1475 : : {
3749 kgrittn@postgresql.o 1476 : 1072 : page = BufferGetPage(pos->pendingBuffer);
1477 : :
6333 tgl@sss.pgh.pa.us 1478 : 1072 : maxoff = PageGetMaxOffsetNumber(page);
6254 bruce@momjian.us 1479 [ + + ]: 1072 : if (pos->firstOffset > maxoff)
1480 : : {
6333 tgl@sss.pgh.pa.us 1481 : 110 : BlockNumber blkno = GinPageGetOpaque(page)->rightlink;
1482 : :
6254 bruce@momjian.us 1483 [ + - ]: 110 : if (blkno == InvalidBlockNumber)
1484 : : {
6333 tgl@sss.pgh.pa.us 1485 : 110 : UnlockReleaseBuffer(pos->pendingBuffer);
6254 bruce@momjian.us 1486 : 110 : pos->pendingBuffer = InvalidBuffer;
1487 : :
6333 tgl@sss.pgh.pa.us 1488 : 110 : 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 : : */
6254 bruce@momjian.us 1498 :UBC 0 : Buffer tmpbuf = ReadBuffer(scan->indexRelation, blkno);
1499 : :
6333 tgl@sss.pgh.pa.us 1500 : 0 : LockBuffer(tmpbuf, GIN_SHARE);
1501 : 0 : UnlockReleaseBuffer(pos->pendingBuffer);
1502 : :
1503 : 0 : pos->pendingBuffer = tmpbuf;
1504 : 0 : pos->firstOffset = FirstOffsetNumber;
1505 : : }
1506 : : }
1507 : : else
1508 : : {
6333 tgl@sss.pgh.pa.us 1509 :CBC 962 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->firstOffset));
1510 : 962 : pos->item = itup->t_tid;
6254 bruce@momjian.us 1511 [ + - ]: 962 : if (GinPageHasFullRow(page))
1512 : : {
1513 : : /*
1514 : : * find itempointer to the next row
1515 : : */
1516 [ + + ]: 2234 : for (pos->lastOffset = pos->firstOffset + 1; pos->lastOffset <= maxoff; pos->lastOffset++)
1517 : : {
6333 tgl@sss.pgh.pa.us 1518 : 2124 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->lastOffset));
1519 [ + + ]: 2124 : if (!ItemPointerEquals(&pos->item, &itup->t_tid))
1520 : 852 : break;
1521 : : }
1522 : : }
1523 : : else
1524 : : {
1525 : : /*
1526 : : * All itempointers are the same on this page
1527 : : */
6333 tgl@sss.pgh.pa.us 1528 :UBC 0 : 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 : : */
6333 tgl@sss.pgh.pa.us 1536 :CBC 962 : break;
1537 : : }
1538 : : }
1539 : :
1540 : 962 : return true;
1541 : : }
1542 : :
1543 : : /*
1544 : : * Scan pending-list page from current tuple (off) up till the first of:
1545 : : * - match is found (then returns true)
1546 : : * - no later match is possible
1547 : : * - tuple's attribute number is not equal to entry's attrnum
1548 : : * - reach end of page
1549 : : *
1550 : : * datum[]/category[]/datumExtracted[] arrays are used to cache the results
1551 : : * of gintuple_get_key() on the current page.
1552 : : */
1553 : : static bool
6333 tgl@sss.pgh.pa.us 1554 :UBC 0 : matchPartialInPendingList(GinState *ginstate, Page page,
1555 : : OffsetNumber off, OffsetNumber maxoff,
1556 : : GinScanEntry entry,
1557 : : Datum *datum, GinNullCategory *category,
1558 : : bool *datumExtracted)
1559 : : {
1560 : : IndexTuple itup;
1561 : : int32 cmp;
1562 : :
1563 : : /* Partial match to a null is not possible */
5679 1564 [ # # ]: 0 : if (entry->queryCategory != GIN_CAT_NORM_KEY)
1565 : 0 : return false;
1566 : :
6254 bruce@momjian.us 1567 [ # # ]: 0 : while (off < maxoff)
1568 : : {
6333 tgl@sss.pgh.pa.us 1569 : 0 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
1570 : :
5679 1571 [ # # ]: 0 : if (gintuple_get_attrnum(ginstate, itup) != entry->attnum)
6333 1572 : 0 : return false;
1573 : :
6254 bruce@momjian.us 1574 [ # # ]: 0 : if (datumExtracted[off - 1] == false)
1575 : : {
5679 tgl@sss.pgh.pa.us 1576 : 0 : datum[off - 1] = gintuple_get_key(ginstate, itup,
1577 : 0 : &category[off - 1]);
6254 bruce@momjian.us 1578 : 0 : datumExtracted[off - 1] = true;
1579 : : }
1580 : :
1581 : : /* Once we hit nulls, no further match is possible */
5679 tgl@sss.pgh.pa.us 1582 [ # # ]: 0 : if (category[off - 1] != GIN_CAT_NORM_KEY)
1583 : 0 : 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 : : */
5584 1592 : 0 : cmp = DatumGetInt32(FunctionCall4Coll(&ginstate->comparePartialFn[entry->attnum - 1],
3322 1593 : 0 : ginstate->supportCollation[entry->attnum - 1],
1594 : : entry->queryKey,
5584 1595 : 0 : datum[off - 1],
5526 bruce@momjian.us 1596 : 0 : UInt16GetDatum(entry->strategy),
3322 tgl@sss.pgh.pa.us 1597 : 0 : PointerGetDatum(entry->extra_data)));
6332 1598 [ # # ]: 0 : if (cmp == 0)
6333 1599 : 0 : return true;
6332 1600 [ # # ]: 0 : else if (cmp > 0)
6333 1601 : 0 : return false;
1602 : :
6321 teodor@sigaev.ru 1603 : 0 : off++;
1604 : : }
1605 : :
6333 tgl@sss.pgh.pa.us 1606 : 0 : return false;
1607 : : }
1608 : :
1609 : : /*
1610 : : * Set up the entryRes array for each key by looking at
1611 : : * every entry for current heap row in pending list.
1612 : : *
1613 : : * Returns true if each scan key has at least one entryRes match.
1614 : : * This corresponds to the situations where the normal index search will
1615 : : * try to apply the key's consistentFn. (A tuple not meeting that requirement
1616 : : * cannot be returned by the normal search since no entry stream will
1617 : : * source its TID.)
1618 : : *
1619 : : * The pendingBuffer is presumed pinned and share-locked on entry.
1620 : : */
1621 : : static bool
5679 tgl@sss.pgh.pa.us 1622 :CBC 962 : collectMatchesForHeapRow(IndexScanDesc scan, pendingPosition *pos)
1623 : : {
6254 bruce@momjian.us 1624 : 962 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
1625 : : OffsetNumber attrnum;
1626 : : Page page;
1627 : : IndexTuple itup;
1628 : :
1629 : : /*
1630 : : * Reset all entryRes and hasMatchKey flags
1631 : : */
15 peter@eisentraut.org 1632 [ + + ]:GNC 2610 : for (uint32 i = 0; i < so->nkeys; i++)
1633 : : {
6333 tgl@sss.pgh.pa.us 1634 :CBC 1648 : GinScanKey key = so->keys + i;
1635 : :
4552 heikki.linnakangas@i 1636 : 1648 : memset(key->entryRes, GIN_FALSE, key->nentries);
1637 : : }
3266 peter_e@gmx.net 1638 : 962 : memset(pos->hasMatchKey, false, so->nkeys);
1639 : :
1640 : : /*
1641 : : * Outer loop iterates over multiple pending-list pages when a single heap
1642 : : * row has entries spanning those pages.
1643 : : */
1644 : : for (;;)
6333 tgl@sss.pgh.pa.us 1645 :UBC 0 : {
1646 : : Datum datum[BLCKSZ / sizeof(IndexTupleData)];
1647 : : GinNullCategory category[BLCKSZ / sizeof(IndexTupleData)];
1648 : : bool datumExtracted[BLCKSZ / sizeof(IndexTupleData)];
1649 : :
6254 bruce@momjian.us 1650 [ - + ]:CBC 962 : Assert(pos->lastOffset > pos->firstOffset);
5679 tgl@sss.pgh.pa.us 1651 : 962 : memset(datumExtracted + pos->firstOffset - 1, 0,
1652 : 962 : sizeof(bool) * (pos->lastOffset - pos->firstOffset));
1653 : :
3749 kgrittn@postgresql.o 1654 : 962 : page = BufferGetPage(pos->pendingBuffer);
1655 : :
15 peter@eisentraut.org 1656 [ + + ]:GNC 2610 : for (uint32 i = 0; i < so->nkeys; i++)
1657 : : {
6254 bruce@momjian.us 1658 :CBC 1648 : GinScanKey key = so->keys + i;
1659 : :
15 peter@eisentraut.org 1660 [ + + ]:GNC 3184 : for (uint32 j = 0; j < key->nentries; j++)
1661 : : {
5678 tgl@sss.pgh.pa.us 1662 :CBC 1536 : GinScanEntry entry = key->scanEntry[j];
6254 bruce@momjian.us 1663 : 1536 : OffsetNumber StopLow = pos->firstOffset,
1664 : 1536 : StopHigh = pos->lastOffset,
1665 : : StopMiddle;
1666 : :
1667 : : /* If already matched on earlier page, do no extra work */
1668 [ - + ]: 1536 : if (key->entryRes[j])
6333 tgl@sss.pgh.pa.us 1669 :UBC 0 : continue;
1670 : :
1671 : : /*
1672 : : * Interesting tuples are from pos->firstOffset to
1673 : : * pos->lastOffset and they are ordered by (attnum, Datum) as
1674 : : * it's done in entry tree. So we can use binary search to
1675 : : * avoid linear scanning.
1676 : : */
6333 tgl@sss.pgh.pa.us 1677 [ + + ]:CBC 3422 : while (StopLow < StopHigh)
1678 : : {
1679 : : int res;
1680 : :
1681 : 2696 : StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
1682 : :
1683 : 2696 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, StopMiddle));
1684 : :
1685 : 2696 : attrnum = gintuple_get_attrnum(&so->ginstate, itup);
1686 : :
1687 [ + + ]: 2696 : if (key->attnum < attrnum)
1688 : : {
1689 : 532 : StopHigh = StopMiddle;
5679 1690 : 532 : continue;
1691 : : }
1692 [ + + ]: 2164 : if (key->attnum > attrnum)
1693 : : {
6333 1694 : 440 : StopLow = StopMiddle + 1;
5679 1695 : 440 : continue;
1696 : : }
1697 : :
1698 [ + + ]: 1724 : if (datumExtracted[StopMiddle - 1] == false)
1699 : : {
1700 : 3308 : datum[StopMiddle - 1] =
1701 : 1654 : gintuple_get_key(&so->ginstate, itup,
1702 : 1654 : &category[StopMiddle - 1]);
1703 : 1654 : datumExtracted[StopMiddle - 1] = true;
1704 : : }
1705 : :
1706 [ + + ]: 1724 : if (entry->queryCategory == GIN_CAT_EMPTY_QUERY)
1707 : : {
1708 : : /* special behavior depending on searchMode */
1709 [ + - ]: 722 : if (entry->searchMode == GIN_SEARCH_MODE_ALL)
1710 : : {
1711 : : /* match anything except NULL_ITEM */
1712 [ + + ]: 722 : if (category[StopMiddle - 1] == GIN_CAT_NULL_ITEM)
1713 : 252 : res = -1;
1714 : : else
1715 : 470 : res = 0;
1716 : : }
1717 : : else
1718 : : {
1719 : : /* match everything */
5679 tgl@sss.pgh.pa.us 1720 :UBC 0 : res = 0;
1721 : : }
1722 : : }
1723 : : else
1724 : : {
5761 tgl@sss.pgh.pa.us 1725 :CBC 1002 : res = ginCompareEntries(&so->ginstate,
1726 : 1002 : entry->attnum,
1727 : : entry->queryKey,
5679 1728 : 1002 : entry->queryCategory,
1729 : 1002 : datum[StopMiddle - 1],
1730 : 1002 : category[StopMiddle - 1]);
1731 : : }
1732 : :
1733 [ + + ]: 1724 : if (res == 0)
1734 : : {
1735 : : /*
1736 : : * Found exact match (there can be only one, except in
1737 : : * EMPTY_QUERY mode).
1738 : : *
1739 : : * If doing partial match, scan forward from here to
1740 : : * end of page to check for matches.
1741 : : *
1742 : : * See comment above about tuple's ordering.
1743 : : */
1744 [ - + ]: 810 : if (entry->isPartialMatch)
5679 tgl@sss.pgh.pa.us 1745 :UBC 0 : key->entryRes[j] =
1746 : 0 : matchPartialInPendingList(&so->ginstate,
1747 : : page,
1748 : : StopMiddle,
1749 : 0 : pos->lastOffset,
1750 : : entry,
1751 : : datum,
1752 : : category,
1753 : : datumExtracted);
1754 : : else
5679 tgl@sss.pgh.pa.us 1755 :CBC 810 : key->entryRes[j] = true;
1756 : :
1757 : : /* done with binary search */
1758 : 810 : break;
1759 : : }
1760 [ + + ]: 914 : else if (res < 0)
1761 : 886 : StopHigh = StopMiddle;
1762 : : else
1763 : 28 : StopLow = StopMiddle + 1;
1764 : : }
1765 : :
6254 bruce@momjian.us 1766 [ + + - + ]: 1536 : if (StopLow >= StopHigh && entry->isPartialMatch)
1767 : : {
1768 : : /*
1769 : : * No exact match on this page. If doing partial match,
1770 : : * scan from the first tuple greater than target value to
1771 : : * end of page. Note that since we don't remember whether
1772 : : * the comparePartialFn told us to stop early on a
1773 : : * previous page, we will uselessly apply comparePartialFn
1774 : : * to the first tuple on each subsequent page.
1775 : : */
6333 tgl@sss.pgh.pa.us 1776 :UBC 0 : key->entryRes[j] =
1777 : 0 : matchPartialInPendingList(&so->ginstate,
1778 : : page,
1779 : : StopHigh,
1780 : 0 : pos->lastOffset,
1781 : : entry,
1782 : : datum,
1783 : : category,
1784 : : datumExtracted);
1785 : : }
1786 : :
6099 teodor@sigaev.ru 1787 :CBC 1536 : pos->hasMatchKey[i] |= key->entryRes[j];
1788 : : }
1789 : : }
1790 : :
1791 : : /* Advance firstOffset over the scanned tuples */
6333 tgl@sss.pgh.pa.us 1792 : 962 : pos->firstOffset = pos->lastOffset;
1793 : :
6254 bruce@momjian.us 1794 [ + - ]: 962 : if (GinPageHasFullRow(page))
1795 : : {
1796 : : /*
1797 : : * We have examined all pending entries for the current heap row.
1798 : : * Break out of loop over pages.
1799 : : */
5679 tgl@sss.pgh.pa.us 1800 : 962 : break;
1801 : : }
1802 : : else
1803 : : {
1804 : : /*
1805 : : * Advance to next page of pending entries for the current heap
1806 : : * row. Complain if there isn't one.
1807 : : */
5679 tgl@sss.pgh.pa.us 1808 :UBC 0 : ItemPointerData item = pos->item;
1809 : :
1810 [ # # ]: 0 : if (scanGetCandidate(scan, pos) == false ||
1811 [ # # ]: 0 : !ItemPointerEquals(&pos->item, &item))
1812 [ # # ]: 0 : elog(ERROR, "could not find additional pending pages for same heap tuple");
1813 : : }
1814 : : }
1815 : :
1816 : : /*
1817 : : * All scan keys except excludeOnly require at least one entry to match.
1818 : : * excludeOnly keys are an exception, because their implied
1819 : : * GIN_CAT_EMPTY_QUERY scanEntry always matches. So return "true" if all
1820 : : * non-excludeOnly scan keys have at least one match.
1821 : : */
15 peter@eisentraut.org 1822 [ + + ]:GNC 1674 : for (uint32 i = 0; i < so->nkeys; i++)
1823 : : {
2381 akorotkov@postgresql 1824 [ + + + + ]:CBC 1304 : if (pos->hasMatchKey[i] == false && !so->keys[i].excludeOnly)
5679 tgl@sss.pgh.pa.us 1825 : 592 : return false;
1826 : : }
1827 : :
1828 : 370 : return true;
1829 : : }
1830 : :
1831 : : /*
1832 : : * Collect all matched rows from pending list into bitmap.
1833 : : */
1834 : : static void
6333 1835 : 1143 : scanPendingInsert(IndexScanDesc scan, TIDBitmap *tbm, int64 *ntids)
1836 : : {
1837 : 1143 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
1838 : : MemoryContext oldCtx;
1839 : : bool recheck,
1840 : : match;
1841 : : pendingPosition pos;
6254 bruce@momjian.us 1842 : 1143 : Buffer metabuffer = ReadBuffer(scan->indexRelation, GIN_METAPAGE_BLKNO);
1843 : : Page page;
1844 : : BlockNumber blkno;
1845 : :
6333 tgl@sss.pgh.pa.us 1846 : 1143 : *ntids = 0;
1847 : :
1848 : : /*
1849 : : * Acquire predicate lock on the metapage, to conflict with any fastupdate
1850 : : * insertions.
1851 : : */
3005 teodor@sigaev.ru 1852 : 1143 : PredicateLockPage(scan->indexRelation, GIN_METAPAGE_BLKNO, scan->xs_snapshot);
1853 : :
6333 tgl@sss.pgh.pa.us 1854 : 1143 : LockBuffer(metabuffer, GIN_SHARE);
3749 kgrittn@postgresql.o 1855 : 1143 : page = BufferGetPage(metabuffer);
3761 1856 : 1143 : blkno = GinPageGetMeta(page)->head;
1857 : :
1858 : : /*
1859 : : * fetch head of list before unlocking metapage. head page must be pinned
1860 : : * to prevent deletion by vacuum process
1861 : : */
6254 bruce@momjian.us 1862 [ + + ]: 1143 : if (blkno == InvalidBlockNumber)
1863 : : {
1864 : : /* No pending list, so proceed with normal scan */
1865 : 1033 : UnlockReleaseBuffer(metabuffer);
6333 tgl@sss.pgh.pa.us 1866 : 1033 : return;
1867 : : }
1868 : :
1869 : 110 : pos.pendingBuffer = ReadBuffer(scan->indexRelation, blkno);
1870 : 110 : LockBuffer(pos.pendingBuffer, GIN_SHARE);
1871 : 110 : pos.firstOffset = FirstOffsetNumber;
6254 bruce@momjian.us 1872 : 110 : UnlockReleaseBuffer(metabuffer);
228 michael@paquier.xyz 1873 : 110 : pos.hasMatchKey = palloc_array(bool, so->nkeys);
1874 : :
1875 : : /*
1876 : : * loop for each heap row. scanGetCandidate returns full row or row's
1877 : : * tuples from first page.
1878 : : */
6254 bruce@momjian.us 1879 [ + + ]: 1072 : while (scanGetCandidate(scan, &pos))
1880 : : {
1881 : : /*
1882 : : * Check entries in tuple and set up entryRes array.
1883 : : *
1884 : : * If pending tuples belonging to the current heap row are spread
1885 : : * across several pages, collectMatchesForHeapRow will read all of
1886 : : * those pages.
1887 : : */
5679 tgl@sss.pgh.pa.us 1888 [ + + ]: 962 : if (!collectMatchesForHeapRow(scan, &pos))
6333 1889 : 592 : continue;
1890 : :
1891 : : /*
1892 : : * Matching of entries of one row is finished, so check row using
1893 : : * consistent functions.
1894 : : */
1895 : 370 : oldCtx = MemoryContextSwitchTo(so->tempCtx);
1896 : 370 : recheck = false;
1897 : 370 : match = true;
1898 : :
15 peter@eisentraut.org 1899 [ + + ]:GNC 936 : for (uint32 i = 0; i < so->nkeys; i++)
1900 : : {
6254 bruce@momjian.us 1901 :CBC 568 : GinScanKey key = so->keys + i;
1902 : :
4552 heikki.linnakangas@i 1903 [ + + ]: 568 : if (!key->boolConsistentFn(key))
1904 : : {
6333 tgl@sss.pgh.pa.us 1905 : 2 : match = false;
6332 1906 : 2 : break;
1907 : : }
5838 1908 : 566 : recheck |= key->recheckCurItem;
1909 : : }
1910 : :
6333 1911 : 370 : MemoryContextSwitchTo(oldCtx);
1912 : 370 : MemoryContextReset(so->tempCtx);
1913 : :
6254 bruce@momjian.us 1914 [ + + ]: 370 : if (match)
1915 : : {
6333 tgl@sss.pgh.pa.us 1916 : 368 : tbm_add_tuples(tbm, &pos.item, 1, recheck);
1917 : 368 : (*ntids)++;
1918 : : }
1919 : : }
1920 : :
6099 teodor@sigaev.ru 1921 : 110 : pfree(pos.hasMatchKey);
1922 : : }
1923 : :
1924 : :
1925 : : #define GinIsVoidRes(s) ( ((GinScanOpaque) scan->opaque)->isVoidRes )
1926 : :
1927 : : int64
3843 tgl@sss.pgh.pa.us 1928 : 1151 : gingetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
1929 : : {
4195 heikki.linnakangas@i 1930 : 1151 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
1931 : : int64 ntids;
1932 : : ItemPointerData iptr;
1933 : : bool recheck;
1934 : :
1935 : : /*
1936 : : * Set up the scan keys, and check for unsatisfiable query.
1937 : : */
4082 bruce@momjian.us 1938 : 1151 : ginFreeScanKeys(so); /* there should be no keys yet, but just to be
1939 : : * sure */
4195 heikki.linnakangas@i 1940 : 1151 : ginNewScanKey(scan);
1941 : :
7116 teodor@sigaev.ru 1942 [ + + ]: 1151 : if (GinIsVoidRes(scan))
3843 tgl@sss.pgh.pa.us 1943 : 8 : return 0;
1944 : :
6333 1945 : 1143 : ntids = 0;
1946 : :
1947 : : /*
1948 : : * First, scan the pending list and collect any matching entries into the
1949 : : * bitmap. After we scan a pending item, some other backend could post it
1950 : : * into the main index, and so we might visit it a second time during the
1951 : : * main scan. This is okay because we'll just re-set the same bit in the
1952 : : * bitmap. (The possibility of duplicate visits is a major reason why GIN
1953 : : * can't support the amgettuple API, however.) Note that it would not do
1954 : : * to scan the main index before the pending list, since concurrent
1955 : : * cleanup could then make us miss entries entirely.
1956 : : */
1957 : 1143 : scanPendingInsert(scan, tbm, &ntids);
1958 : :
1959 : : /*
1960 : : * Now scan the main index.
1961 : : */
7116 teodor@sigaev.ru 1962 : 1143 : startScan(scan);
1963 : :
5839 tgl@sss.pgh.pa.us 1964 : 1143 : ItemPointerSetMin(&iptr);
1965 : :
1966 : : for (;;)
1967 : : {
4561 heikki.linnakangas@i 1968 [ + + ]: 615329 : if (!scanGetItem(scan, iptr, &iptr, &recheck))
7390 teodor@sigaev.ru 1969 : 1143 : break;
1970 : :
6254 bruce@momjian.us 1971 [ - + - - ]: 614186 : if (ItemPointerIsLossyPage(&iptr))
6333 tgl@sss.pgh.pa.us 1972 :UBC 0 : tbm_add_page(tbm, ItemPointerGetBlockNumber(&iptr));
1973 : : else
6333 tgl@sss.pgh.pa.us 1974 :CBC 614186 : tbm_add_tuples(tbm, &iptr, 1, recheck);
6681 1975 : 614186 : ntids++;
1976 : : }
1977 : :
3843 1978 : 1143 : return ntids;
1979 : : }
|
