Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * ginscan.c
4 : : * routines to manage scans of inverted index relations
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/ginscan.c
12 : : *-------------------------------------------------------------------------
13 : : */
14 : :
15 : : #include "postgres.h"
16 : :
17 : : #include "access/gin_private.h"
18 : : #include "access/relscan.h"
19 : : #include "executor/instrument_node.h"
20 : : #include "pgstat.h"
21 : : #include "utils/memutils.h"
22 : : #include "utils/rel.h"
23 : :
24 : :
25 : : IndexScanDesc
26 : 1147 : ginbeginscan(Relation rel, int nkeys, int norderbys)
27 : : {
28 : : IndexScanDesc scan;
29 : : GinScanOpaque so;
30 : :
31 : : /* no order by operators allowed */
32 : : Assert(norderbys == 0);
33 : :
34 : 1147 : scan = RelationGetIndexScan(rel, nkeys, norderbys);
35 : :
36 : : /* allocate private workspace */
37 : 1147 : so = (GinScanOpaque) palloc_object(GinScanOpaqueData);
38 : 1147 : so->keys = NULL;
39 : 1147 : so->nkeys = 0;
40 : 1147 : so->tempCtx = AllocSetContextCreate(CurrentMemoryContext,
41 : : "Gin scan temporary context",
42 : : ALLOCSET_DEFAULT_SIZES);
43 : 1147 : so->keyCtx = AllocSetContextCreate(CurrentMemoryContext,
44 : : "Gin scan key context",
45 : : ALLOCSET_DEFAULT_SIZES);
46 : 1147 : initGinState(&so->ginstate, scan->indexRelation);
47 : :
48 : 1147 : scan->opaque = so;
49 : :
50 : 1147 : return scan;
51 : : }
52 : :
53 : : /*
54 : : * Create a new GinScanEntry, unless an equivalent one already exists,
55 : : * in which case just return it
56 : : */
57 : : static GinScanEntry
58 : 3827 : ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,
59 : : StrategyNumber strategy, int32 searchMode,
60 : : Datum queryKey, GinNullCategory queryCategory,
61 : : bool isPartialMatch, Pointer extra_data)
62 : : {
63 : 3827 : GinState *ginstate = &so->ginstate;
64 : : GinScanEntry scanEntry;
65 : : uint32 i;
66 : :
67 : : /*
68 : : * Look for an existing equivalent entry.
69 : : *
70 : : * Entries with non-null extra_data are never considered identical, since
71 : : * we can't know exactly what the opclass might be doing with that.
72 : : *
73 : : * Also, give up de-duplication once we have 100 entries. That avoids
74 : : * spending O(N^2) time on probably-fruitless de-duplication of large
75 : : * search-key sets. The threshold of 100 is arbitrary but matches
76 : : * predtest.c's threshold for what's a large array.
77 : : */
78 [ + + + + ]: 3827 : if (extra_data == NULL && so->totalentries < 100)
79 : : {
80 [ + + ]: 28397 : for (i = 0; i < so->totalentries; i++)
81 : : {
82 : 26685 : GinScanEntry prevEntry = so->entries[i];
83 : :
84 [ + + ]: 26685 : if (prevEntry->extra_data == NULL &&
85 [ + - ]: 26485 : prevEntry->isPartialMatch == isPartialMatch &&
86 [ + + ]: 26485 : prevEntry->strategy == strategy &&
87 [ + - ]: 26394 : prevEntry->searchMode == searchMode &&
88 [ + + - + ]: 52772 : prevEntry->attnum == attnum &&
89 : 26378 : ginCompareEntries(ginstate, attnum,
90 : : prevEntry->queryKey,
91 : 26378 : prevEntry->queryCategory,
92 : : queryKey,
93 : : queryCategory) == 0)
94 : : {
95 : : /* Successful match */
96 : 0 : return prevEntry;
97 : : }
98 : : }
99 : : }
100 : :
101 : : /* Nope, create a new entry */
102 : 3827 : scanEntry = palloc_object(GinScanEntryData);
103 : 3827 : scanEntry->queryKey = queryKey;
104 : 3827 : scanEntry->queryCategory = queryCategory;
105 : 3827 : scanEntry->isPartialMatch = isPartialMatch;
106 : 3827 : scanEntry->extra_data = extra_data;
107 : 3827 : scanEntry->strategy = strategy;
108 : 3827 : scanEntry->searchMode = searchMode;
109 : 3827 : scanEntry->attnum = attnum;
110 : :
111 : 3827 : scanEntry->buffer = InvalidBuffer;
112 : 3827 : ItemPointerSetMin(&scanEntry->curItem);
113 : 3827 : scanEntry->matchBitmap = NULL;
114 : 3827 : scanEntry->matchIterator = NULL;
115 : 3827 : scanEntry->matchResult.blockno = InvalidBlockNumber;
116 : 3827 : scanEntry->matchNtuples = -1;
117 : 3827 : scanEntry->list = NULL;
118 : 3827 : scanEntry->nlist = 0;
119 : 3827 : scanEntry->offset = InvalidOffsetNumber;
120 : 3827 : scanEntry->isFinished = false;
121 : 3827 : scanEntry->reduceResult = false;
122 : :
123 : : /* Add it to so's array */
124 [ + + ]: 3827 : if (so->totalentries >= so->allocentries)
125 : : {
126 : 23 : so->allocentries *= 2;
127 : 23 : so->entries = repalloc_array(so->entries, GinScanEntry, so->allocentries);
128 : : }
129 : 3827 : so->entries[so->totalentries++] = scanEntry;
130 : :
131 : 3827 : return scanEntry;
132 : : }
133 : :
134 : : /*
135 : : * Append hidden scan entry of given category to the scan key.
136 : : *
137 : : * NB: this had better be called at most once per scan key, since
138 : : * ginFillScanKey leaves room for only one hidden entry. Currently,
139 : : * it seems sufficiently clear that this is true that we don't bother
140 : : * with any cross-check logic.
141 : : */
142 : : static void
143 : 214 : ginScanKeyAddHiddenEntry(GinScanOpaque so, GinScanKey key,
144 : : GinNullCategory queryCategory)
145 : : {
146 : 214 : int i = key->nentries++;
147 : :
148 : : /* strategy is of no interest because this is not a partial-match item */
149 : 214 : key->scanEntry[i] = ginFillScanEntry(so, key->attnum,
150 : : InvalidStrategy, key->searchMode,
151 : : (Datum) 0, queryCategory,
152 : : false, NULL);
153 : 214 : }
154 : :
155 : : /*
156 : : * Initialize the next GinScanKey using the output from the extractQueryFn
157 : : */
158 : : static void
159 : 1229 : ginFillScanKey(GinScanOpaque so, OffsetNumber attnum,
160 : : StrategyNumber strategy, int32 searchMode,
161 : : Datum query, uint32 nQueryValues,
162 : : Datum *queryValues, GinNullCategory *queryCategories,
163 : : bool *partial_matches, Pointer *extra_data)
164 : : {
165 : 1229 : GinScanKey key = &(so->keys[so->nkeys++]);
166 : 1229 : GinState *ginstate = &so->ginstate;
167 : : uint32 i;
168 : :
169 : 1229 : key->nentries = nQueryValues;
170 : 1229 : key->nuserentries = nQueryValues;
171 : :
172 : : /* Allocate one extra array slot for possible "hidden" entry */
173 : 1229 : key->scanEntry = palloc_array(GinScanEntry, nQueryValues + 1);
174 : 1229 : key->entryRes = palloc0_array(GinTernaryValue, nQueryValues + 1);
175 : :
176 : 1229 : key->query = query;
177 : 1229 : key->queryValues = queryValues;
178 : 1229 : key->queryCategories = queryCategories;
179 : 1229 : key->extra_data = extra_data;
180 : 1229 : key->strategy = strategy;
181 : 1229 : key->searchMode = searchMode;
182 : 1229 : key->attnum = attnum;
183 : :
184 : : /*
185 : : * Initially, scan keys of GIN_SEARCH_MODE_ALL mode are marked
186 : : * excludeOnly. This might get changed later.
187 : : */
188 : 1229 : key->excludeOnly = (searchMode == GIN_SEARCH_MODE_ALL);
189 : :
190 : 1229 : ItemPointerSetMin(&key->curItem);
191 : 1229 : key->curItemMatches = false;
192 : 1229 : key->recheckCurItem = false;
193 : 1229 : key->isFinished = false;
194 : 1229 : key->nrequired = 0;
195 : 1229 : key->nadditional = 0;
196 : 1229 : key->requiredEntries = NULL;
197 : 1229 : key->additionalEntries = NULL;
198 : :
199 : 1229 : ginInitConsistentFunction(ginstate, key);
200 : :
201 : : /* Set up normal scan entries using extractQueryFn's outputs */
202 [ + + ]: 4842 : for (i = 0; i < nQueryValues; i++)
203 : : {
204 : : Datum queryKey;
205 : : GinNullCategory queryCategory;
206 : : bool isPartialMatch;
207 : : Pointer this_extra;
208 : :
209 : 3613 : queryKey = queryValues[i];
210 : 3613 : queryCategory = queryCategories[i];
211 : 3613 : isPartialMatch =
212 [ + - ]: 562 : (ginstate->canPartialMatch[attnum - 1] && partial_matches)
213 [ + + ]: 4175 : ? partial_matches[i] : false;
214 [ + + ]: 3613 : this_extra = (extra_data) ? extra_data[i] : NULL;
215 : :
216 : 3613 : key->scanEntry[i] = ginFillScanEntry(so, attnum,
217 : : strategy, searchMode,
218 : : queryKey, queryCategory,
219 : : isPartialMatch, this_extra);
220 : : }
221 : :
222 : : /*
223 : : * For GIN_SEARCH_MODE_INCLUDE_EMPTY and GIN_SEARCH_MODE_EVERYTHING search
224 : : * modes, we add the "hidden" entry immediately. GIN_SEARCH_MODE_ALL is
225 : : * handled later, since we might be able to omit the hidden entry for it.
226 : : */
227 [ + + ]: 1229 : if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
228 : 29 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_ITEM);
229 [ - + ]: 1200 : else if (searchMode == GIN_SEARCH_MODE_EVERYTHING)
230 : 0 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
231 : 1229 : }
232 : :
233 : : /*
234 : : * Release current scan keys, if any.
235 : : */
236 : : void
237 : 3449 : ginFreeScanKeys(GinScanOpaque so)
238 : : {
239 : : uint32 i;
240 : :
241 [ + + ]: 3449 : if (so->keys == NULL)
242 : 2298 : return;
243 : :
244 [ + + ]: 4978 : for (i = 0; i < so->totalentries; i++)
245 : : {
246 : 3827 : GinScanEntry entry = so->entries[i];
247 : :
248 [ - + ]: 3827 : if (entry->buffer != InvalidBuffer)
249 : 0 : ReleaseBuffer(entry->buffer);
250 [ + + ]: 3827 : if (entry->list)
251 : 2427 : pfree(entry->list);
252 [ - + ]: 3827 : if (entry->matchIterator)
253 : 0 : tbm_end_private_iterate(entry->matchIterator);
254 [ + + ]: 3827 : if (entry->matchBitmap)
255 : 486 : tbm_free(entry->matchBitmap);
256 : : }
257 : :
258 : 1151 : MemoryContextReset(so->keyCtx);
259 : :
260 : 1151 : so->keys = NULL;
261 : 1151 : so->nkeys = 0;
262 : 1151 : so->entries = NULL;
263 : 1151 : so->totalentries = 0;
264 : : }
265 : :
266 : : void
267 : 1151 : ginNewScanKey(IndexScanDesc scan)
268 : : {
269 : 1151 : ScanKey scankey = scan->keyData;
270 : 1151 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
271 : : int i;
272 : : int numExcludeOnly;
273 : 1151 : bool hasNullQuery = false;
274 : 1151 : bool attrHasNormalScan[INDEX_MAX_KEYS] = {false};
275 : : MemoryContext oldCtx;
276 : :
277 : : /*
278 : : * Allocate all the scan key information in the key context. (If
279 : : * extractQuery leaks anything there, it won't be reset until the end of
280 : : * scan or rescan, but that's OK.)
281 : : */
282 : 1151 : oldCtx = MemoryContextSwitchTo(so->keyCtx);
283 : :
284 : : /* if no scan keys provided, allocate extra EVERYTHING GinScanKey */
285 : 1151 : so->keys = (GinScanKey)
286 : 1151 : palloc(Max(scan->numberOfKeys, 1) * sizeof(GinScanKeyData));
287 : 1151 : so->nkeys = 0;
288 : :
289 : : /* initialize expansible array of GinScanEntry pointers */
290 : 1151 : so->totalentries = 0;
291 : 1151 : so->allocentries = 32;
292 : 1151 : so->entries = (GinScanEntry *)
293 : 1151 : palloc(so->allocentries * sizeof(GinScanEntry));
294 : :
295 : 1151 : so->isVoidRes = false;
296 : :
297 [ + + ]: 2380 : for (i = 0; i < scan->numberOfKeys; i++)
298 : : {
299 : 1237 : ScanKey skey = &scankey[i];
300 : : Datum *queryValues;
301 : 1237 : int32 nQueryValues = 0;
302 : 1237 : bool *partial_matches = NULL;
303 : 1237 : Pointer *extra_data = NULL;
304 : 1237 : bool *nullFlags = NULL;
305 : : GinNullCategory *categories;
306 : 1237 : int32 searchMode = GIN_SEARCH_MODE_DEFAULT;
307 : :
308 : : /*
309 : : * We assume that GIN-indexable operators are strict, so a null query
310 : : * argument means an unsatisfiable query.
311 : : */
312 [ - + ]: 1237 : if (skey->sk_flags & SK_ISNULL)
313 : : {
314 : 0 : so->isVoidRes = true;
315 : 8 : break;
316 : : }
317 : :
318 : : /* OK to call the extractQueryFn */
319 : : queryValues = (Datum *)
320 : 1237 : DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[skey->sk_attno - 1],
321 : 1237 : so->ginstate.supportCollation[skey->sk_attno - 1],
322 : : skey->sk_argument,
323 : : PointerGetDatum(&nQueryValues),
324 : 1237 : UInt16GetDatum(skey->sk_strategy),
325 : : PointerGetDatum(&partial_matches),
326 : : PointerGetDatum(&extra_data),
327 : : PointerGetDatum(&nullFlags),
328 : : PointerGetDatum(&searchMode)));
329 : :
330 : : /*
331 : : * If bogus searchMode is returned, treat as GIN_SEARCH_MODE_ALL; note
332 : : * in particular we don't allow extractQueryFn to select
333 : : * GIN_SEARCH_MODE_EVERYTHING.
334 : : */
335 [ + - ]: 1237 : if (searchMode < GIN_SEARCH_MODE_DEFAULT ||
336 [ - + ]: 1237 : searchMode > GIN_SEARCH_MODE_ALL)
337 : 0 : searchMode = GIN_SEARCH_MODE_ALL;
338 : :
339 : : /* Non-default modes require the index to have placeholders */
340 [ + + ]: 1237 : if (searchMode != GIN_SEARCH_MODE_DEFAULT)
341 : 240 : hasNullQuery = true;
342 : :
343 : : /*
344 : : * In default mode, no keys means an unsatisfiable query.
345 : : */
346 [ + + + + ]: 1237 : if (queryValues == NULL || nQueryValues <= 0)
347 : : {
348 [ + + ]: 201 : if (searchMode == GIN_SEARCH_MODE_DEFAULT)
349 : : {
350 : 8 : so->isVoidRes = true;
351 : 8 : break;
352 : : }
353 : 193 : nQueryValues = 0; /* ensure sane value */
354 : : }
355 : :
356 : : /*
357 : : * Create GinNullCategory representation. If the extractQueryFn
358 : : * didn't create a nullFlags array, we assume everything is non-null.
359 : : * While at it, detect whether any null keys are present.
360 : : */
361 : 1229 : categories = (GinNullCategory *) palloc0(nQueryValues * sizeof(GinNullCategory));
362 [ + + ]: 1229 : if (nullFlags)
363 : : {
364 : : int32 j;
365 : :
366 [ + + ]: 2167 : for (j = 0; j < nQueryValues; j++)
367 : : {
368 [ - + ]: 1799 : if (nullFlags[j])
369 : : {
370 : 0 : categories[j] = GIN_CAT_NULL_KEY;
371 : 0 : hasNullQuery = true;
372 : : }
373 : : }
374 : : }
375 : :
376 : 1229 : ginFillScanKey(so, skey->sk_attno,
377 : 1229 : skey->sk_strategy, searchMode,
378 : : skey->sk_argument, nQueryValues,
379 : : queryValues, categories,
380 : : partial_matches, extra_data);
381 : :
382 : : /* Remember if we had any non-excludeOnly keys */
383 [ + + ]: 1229 : if (searchMode != GIN_SEARCH_MODE_ALL)
384 : 1018 : attrHasNormalScan[skey->sk_attno - 1] = true;
385 : : }
386 : :
387 : : /*
388 : : * Processing GIN_SEARCH_MODE_ALL scan keys requires us to make a second
389 : : * pass over the scan keys. Above we marked each such scan key as
390 : : * excludeOnly. If the involved column has any normal (not excludeOnly)
391 : : * scan key as well, then we can leave it like that. Otherwise, one
392 : : * excludeOnly scan key must receive a GIN_CAT_EMPTY_QUERY hidden entry
393 : : * and be set to normal (excludeOnly = false).
394 : : */
395 : 1151 : numExcludeOnly = 0;
396 [ + + ]: 2380 : for (i = 0; i < so->nkeys; i++)
397 : : {
398 : 1229 : GinScanKey key = &so->keys[i];
399 : :
400 [ + + ]: 1229 : if (key->searchMode != GIN_SEARCH_MODE_ALL)
401 : 1018 : continue;
402 : :
403 [ + + ]: 211 : if (!attrHasNormalScan[key->attnum - 1])
404 : : {
405 : 185 : key->excludeOnly = false;
406 : 185 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
407 : 185 : attrHasNormalScan[key->attnum - 1] = true;
408 : : }
409 : : else
410 : 26 : numExcludeOnly++;
411 : : }
412 : :
413 : : /*
414 : : * If we left any excludeOnly scan keys as-is, move them to the end of the
415 : : * scan key array: they must appear after normal key(s).
416 : : */
417 [ + + ]: 1151 : if (numExcludeOnly > 0)
418 : : {
419 : : GinScanKey tmpkeys;
420 : : int iNormalKey;
421 : : int iExcludeOnly;
422 : :
423 : : /* We'd better have made at least one normal key */
424 : : Assert(numExcludeOnly < so->nkeys);
425 : : /* Make a temporary array to hold the re-ordered scan keys */
426 : 26 : tmpkeys = (GinScanKey) palloc(so->nkeys * sizeof(GinScanKeyData));
427 : : /* Re-order the keys ... */
428 : 26 : iNormalKey = 0;
429 : 26 : iExcludeOnly = so->nkeys - numExcludeOnly;
430 [ + + ]: 94 : for (i = 0; i < so->nkeys; i++)
431 : : {
432 : 68 : GinScanKey key = &so->keys[i];
433 : :
434 [ + + ]: 68 : if (key->excludeOnly)
435 : : {
436 : 26 : memcpy(tmpkeys + iExcludeOnly, key, sizeof(GinScanKeyData));
437 : 26 : iExcludeOnly++;
438 : : }
439 : : else
440 : : {
441 : 42 : memcpy(tmpkeys + iNormalKey, key, sizeof(GinScanKeyData));
442 : 42 : iNormalKey++;
443 : : }
444 : : }
445 : : Assert(iNormalKey == so->nkeys - numExcludeOnly);
446 : : Assert(iExcludeOnly == so->nkeys);
447 : : /* ... and copy them back to so->keys[] */
448 : 26 : memcpy(so->keys, tmpkeys, so->nkeys * sizeof(GinScanKeyData));
449 : 26 : pfree(tmpkeys);
450 : : }
451 : :
452 : : /*
453 : : * If there are no regular scan keys, generate an EVERYTHING scankey to
454 : : * drive a full-index scan.
455 : : */
456 [ + + - + ]: 1151 : if (so->nkeys == 0 && !so->isVoidRes)
457 : : {
458 : 0 : hasNullQuery = true;
459 : 0 : ginFillScanKey(so, FirstOffsetNumber,
460 : : InvalidStrategy, GIN_SEARCH_MODE_EVERYTHING,
461 : : (Datum) 0, 0,
462 : : NULL, NULL, NULL, NULL);
463 : : }
464 : :
465 : : /*
466 : : * If the index is version 0, it may be missing null and placeholder
467 : : * entries, which would render searches for nulls and full-index scans
468 : : * unreliable. Throw an error if so.
469 : : */
470 [ + + + - ]: 1151 : if (hasNullQuery && !so->isVoidRes)
471 : : {
472 : : GinStatsData ginStats;
473 : :
474 : 214 : ginGetStats(scan->indexRelation, &ginStats);
475 [ - + ]: 214 : if (ginStats.ginVersion < 1)
476 [ # # ]: 0 : ereport(ERROR,
477 : : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
478 : : errmsg("old GIN indexes do not support whole-index scans nor searches for nulls"),
479 : : errhint("To fix this, do REINDEX INDEX \"%s\".",
480 : : RelationGetRelationName(scan->indexRelation))));
481 : : }
482 : :
483 : 1151 : MemoryContextSwitchTo(oldCtx);
484 : :
485 [ - + - - : 1151 : pgstat_count_index_scan(scan->indexRelation);
+ - ]
486 [ + + ]: 1151 : if (scan->instrument)
487 : 42 : scan->instrument->nsearches++;
488 : 1151 : }
489 : :
490 : : void
491 : 1151 : ginrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
492 : : ScanKey orderbys, int norderbys)
493 : : {
494 : 1151 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
495 : :
496 : 1151 : ginFreeScanKeys(so);
497 : :
498 [ + - + - ]: 1151 : if (scankey && scan->numberOfKeys > 0)
499 : 1151 : memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
500 : 1151 : }
501 : :
502 : :
503 : : void
504 : 1147 : ginendscan(IndexScanDesc scan)
505 : : {
506 : 1147 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
507 : :
508 : 1147 : ginFreeScanKeys(so);
509 : :
510 : 1147 : MemoryContextDelete(so->tempCtx);
511 : 1147 : MemoryContextDelete(so->keyCtx);
512 : :
513 : 1147 : pfree(so);
514 : 1147 : }
|
