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 974 : 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 974 : scan = RelationGetIndexScan(rel, nkeys, norderbys);
35 :
36 : /* allocate private workspace */
37 974 : so = (GinScanOpaque) palloc_object(GinScanOpaqueData);
38 974 : so->keys = NULL;
39 974 : so->nkeys = 0;
40 974 : so->tempCtx = AllocSetContextCreate(CurrentMemoryContext,
41 : "Gin scan temporary context",
42 : ALLOCSET_DEFAULT_SIZES);
43 974 : so->keyCtx = AllocSetContextCreate(CurrentMemoryContext,
44 : "Gin scan key context",
45 : ALLOCSET_DEFAULT_SIZES);
46 974 : initGinState(&so->ginstate, scan->indexRelation);
47 :
48 974 : scan->opaque = so;
49 :
50 974 : 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 3538 : ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,
59 : StrategyNumber strategy, int32 searchMode,
60 : Datum queryKey, GinNullCategory queryCategory,
61 : bool isPartialMatch, Pointer extra_data)
62 : {
63 3538 : 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 3538 : if (extra_data == NULL && so->totalentries < 100)
79 : {
80 28067 : for (i = 0; i < so->totalentries; i++)
81 : {
82 26545 : GinScanEntry prevEntry = so->entries[i];
83 :
84 26545 : if (prevEntry->extra_data == NULL &&
85 26395 : prevEntry->isPartialMatch == isPartialMatch &&
86 26395 : prevEntry->strategy == strategy &&
87 26325 : prevEntry->searchMode == searchMode &&
88 52638 : prevEntry->attnum == attnum &&
89 26313 : ginCompareEntries(ginstate, attnum,
90 : prevEntry->queryKey,
91 26313 : 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 3538 : scanEntry = palloc_object(GinScanEntryData);
103 3538 : scanEntry->queryKey = queryKey;
104 3538 : scanEntry->queryCategory = queryCategory;
105 3538 : scanEntry->isPartialMatch = isPartialMatch;
106 3538 : scanEntry->extra_data = extra_data;
107 3538 : scanEntry->strategy = strategy;
108 3538 : scanEntry->searchMode = searchMode;
109 3538 : scanEntry->attnum = attnum;
110 :
111 3538 : scanEntry->buffer = InvalidBuffer;
112 3538 : ItemPointerSetMin(&scanEntry->curItem);
113 3538 : scanEntry->matchBitmap = NULL;
114 3538 : scanEntry->matchIterator = NULL;
115 3538 : scanEntry->matchResult.blockno = InvalidBlockNumber;
116 3538 : scanEntry->matchNtuples = -1;
117 3538 : scanEntry->list = NULL;
118 3538 : scanEntry->nlist = 0;
119 3538 : scanEntry->offset = InvalidOffsetNumber;
120 3538 : scanEntry->isFinished = false;
121 3538 : scanEntry->reduceResult = false;
122 :
123 : /* Add it to so's array */
124 3538 : if (so->totalentries >= so->allocentries)
125 : {
126 23 : so->allocentries *= 2;
127 23 : so->entries = repalloc_array(so->entries, GinScanEntry, so->allocentries);
128 : }
129 3538 : so->entries[so->totalentries++] = scanEntry;
130 :
131 3538 : 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 163 : ginScanKeyAddHiddenEntry(GinScanOpaque so, GinScanKey key,
144 : GinNullCategory queryCategory)
145 : {
146 163 : int i = key->nentries++;
147 :
148 : /* strategy is of no interest because this is not a partial-match item */
149 163 : key->scanEntry[i] = ginFillScanEntry(so, key->attnum,
150 : InvalidStrategy, key->searchMode,
151 : (Datum) 0, queryCategory,
152 : false, NULL);
153 163 : }
154 :
155 : /*
156 : * Initialize the next GinScanKey using the output from the extractQueryFn
157 : */
158 : static void
159 1037 : 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 1037 : GinScanKey key = &(so->keys[so->nkeys++]);
166 1037 : GinState *ginstate = &so->ginstate;
167 : uint32 i;
168 :
169 1037 : key->nentries = nQueryValues;
170 1037 : key->nuserentries = nQueryValues;
171 :
172 : /* Allocate one extra array slot for possible "hidden" entry */
173 1037 : key->scanEntry = palloc_array(GinScanEntry, nQueryValues + 1);
174 1037 : key->entryRes = palloc0_array(GinTernaryValue, nQueryValues + 1);
175 :
176 1037 : key->query = query;
177 1037 : key->queryValues = queryValues;
178 1037 : key->queryCategories = queryCategories;
179 1037 : key->extra_data = extra_data;
180 1037 : key->strategy = strategy;
181 1037 : key->searchMode = searchMode;
182 1037 : 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 1037 : key->excludeOnly = (searchMode == GIN_SEARCH_MODE_ALL);
189 :
190 1037 : ItemPointerSetMin(&key->curItem);
191 1037 : key->curItemMatches = false;
192 1037 : key->recheckCurItem = false;
193 1037 : key->isFinished = false;
194 1037 : key->nrequired = 0;
195 1037 : key->nadditional = 0;
196 1037 : key->requiredEntries = NULL;
197 1037 : key->additionalEntries = NULL;
198 :
199 1037 : ginInitConsistentFunction(ginstate, key);
200 :
201 : /* Set up normal scan entries using extractQueryFn's outputs */
202 4412 : for (i = 0; i < nQueryValues; i++)
203 : {
204 : Datum queryKey;
205 : GinNullCategory queryCategory;
206 : bool isPartialMatch;
207 : Pointer this_extra;
208 :
209 3375 : queryKey = queryValues[i];
210 3375 : queryCategory = queryCategories[i];
211 3375 : isPartialMatch =
212 503 : (ginstate->canPartialMatch[attnum - 1] && partial_matches)
213 3878 : ? partial_matches[i] : false;
214 3375 : this_extra = (extra_data) ? extra_data[i] : NULL;
215 :
216 3375 : 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 1037 : if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
228 22 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_ITEM);
229 1015 : else if (searchMode == GIN_SEARCH_MODE_EVERYTHING)
230 0 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
231 1037 : }
232 :
233 : /*
234 : * Release current scan keys, if any.
235 : */
236 : void
237 2928 : ginFreeScanKeys(GinScanOpaque so)
238 : {
239 : uint32 i;
240 :
241 2928 : if (so->keys == NULL)
242 1951 : return;
243 :
244 4515 : for (i = 0; i < so->totalentries; i++)
245 : {
246 3538 : GinScanEntry entry = so->entries[i];
247 :
248 3538 : if (entry->buffer != InvalidBuffer)
249 0 : ReleaseBuffer(entry->buffer);
250 3538 : if (entry->list)
251 2227 : pfree(entry->list);
252 3538 : if (entry->matchIterator)
253 0 : tbm_end_private_iterate(entry->matchIterator);
254 3538 : if (entry->matchBitmap)
255 440 : tbm_free(entry->matchBitmap);
256 : }
257 :
258 977 : MemoryContextReset(so->keyCtx);
259 :
260 977 : so->keys = NULL;
261 977 : so->nkeys = 0;
262 977 : so->entries = NULL;
263 977 : so->totalentries = 0;
264 : }
265 :
266 : void
267 977 : ginNewScanKey(IndexScanDesc scan)
268 : {
269 977 : ScanKey scankey = scan->keyData;
270 977 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
271 : int i;
272 : int numExcludeOnly;
273 977 : bool hasNullQuery = false;
274 977 : 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 977 : oldCtx = MemoryContextSwitchTo(so->keyCtx);
283 :
284 : /* if no scan keys provided, allocate extra EVERYTHING GinScanKey */
285 977 : so->keys = (GinScanKey)
286 977 : palloc(Max(scan->numberOfKeys, 1) * sizeof(GinScanKeyData));
287 977 : so->nkeys = 0;
288 :
289 : /* initialize expansible array of GinScanEntry pointers */
290 977 : so->totalentries = 0;
291 977 : so->allocentries = 32;
292 977 : so->entries = (GinScanEntry *)
293 977 : palloc(so->allocentries * sizeof(GinScanEntry));
294 :
295 977 : so->isVoidRes = false;
296 :
297 2014 : for (i = 0; i < scan->numberOfKeys; i++)
298 : {
299 1043 : ScanKey skey = &scankey[i];
300 : Datum *queryValues;
301 1043 : int32 nQueryValues = 0;
302 1043 : bool *partial_matches = NULL;
303 1043 : Pointer *extra_data = NULL;
304 1043 : bool *nullFlags = NULL;
305 : GinNullCategory *categories;
306 1043 : 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 1043 : if (skey->sk_flags & SK_ISNULL)
313 : {
314 0 : so->isVoidRes = true;
315 6 : break;
316 : }
317 :
318 : /* OK to call the extractQueryFn */
319 : queryValues = (Datum *)
320 3129 : DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[skey->sk_attno - 1],
321 1043 : so->ginstate.supportCollation[skey->sk_attno - 1],
322 : skey->sk_argument,
323 : PointerGetDatum(&nQueryValues),
324 1043 : 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 1043 : if (searchMode < GIN_SEARCH_MODE_DEFAULT ||
336 1043 : searchMode > GIN_SEARCH_MODE_ALL)
337 0 : searchMode = GIN_SEARCH_MODE_ALL;
338 :
339 : /* Non-default modes require the index to have placeholders */
340 1043 : if (searchMode != GIN_SEARCH_MODE_DEFAULT)
341 184 : hasNullQuery = true;
342 :
343 : /*
344 : * In default mode, no keys means an unsatisfiable query.
345 : */
346 1043 : if (queryValues == NULL || nQueryValues <= 0)
347 : {
348 154 : if (searchMode == GIN_SEARCH_MODE_DEFAULT)
349 : {
350 6 : so->isVoidRes = true;
351 6 : break;
352 : }
353 148 : 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 1037 : categories = (GinNullCategory *) palloc0(nQueryValues * sizeof(GinNullCategory));
362 1037 : if (nullFlags)
363 : {
364 : int32 j;
365 :
366 2017 : for (j = 0; j < nQueryValues; j++)
367 : {
368 1732 : if (nullFlags[j])
369 : {
370 0 : categories[j] = GIN_CAT_NULL_KEY;
371 0 : hasNullQuery = true;
372 : }
373 : }
374 : }
375 :
376 1037 : ginFillScanKey(so, skey->sk_attno,
377 1037 : 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 1037 : if (searchMode != GIN_SEARCH_MODE_ALL)
384 875 : 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 977 : numExcludeOnly = 0;
396 2014 : for (i = 0; i < so->nkeys; i++)
397 : {
398 1037 : GinScanKey key = &so->keys[i];
399 :
400 1037 : if (key->searchMode != GIN_SEARCH_MODE_ALL)
401 875 : continue;
402 :
403 162 : if (!attrHasNormalScan[key->attnum - 1])
404 : {
405 141 : key->excludeOnly = false;
406 141 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
407 141 : attrHasNormalScan[key->attnum - 1] = true;
408 : }
409 : else
410 21 : 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 977 : 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 21 : tmpkeys = (GinScanKey) palloc(so->nkeys * sizeof(GinScanKeyData));
427 : /* Re-order the keys ... */
428 21 : iNormalKey = 0;
429 21 : iExcludeOnly = so->nkeys - numExcludeOnly;
430 75 : for (i = 0; i < so->nkeys; i++)
431 : {
432 54 : GinScanKey key = &so->keys[i];
433 :
434 54 : if (key->excludeOnly)
435 : {
436 21 : memcpy(tmpkeys + iExcludeOnly, key, sizeof(GinScanKeyData));
437 21 : iExcludeOnly++;
438 : }
439 : else
440 : {
441 33 : memcpy(tmpkeys + iNormalKey, key, sizeof(GinScanKeyData));
442 33 : iNormalKey++;
443 : }
444 : }
445 : Assert(iNormalKey == so->nkeys - numExcludeOnly);
446 : Assert(iExcludeOnly == so->nkeys);
447 : /* ... and copy them back to so->keys[] */
448 21 : memcpy(so->keys, tmpkeys, so->nkeys * sizeof(GinScanKeyData));
449 21 : 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 977 : 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 977 : if (hasNullQuery && !so->isVoidRes)
471 : {
472 : GinStatsData ginStats;
473 :
474 164 : ginGetStats(scan->indexRelation, &ginStats);
475 164 : 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 977 : MemoryContextSwitchTo(oldCtx);
484 :
485 977 : pgstat_count_index_scan(scan->indexRelation);
486 977 : if (scan->instrument)
487 977 : scan->instrument->nsearches++;
488 977 : }
489 :
490 : void
491 977 : ginrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
492 : ScanKey orderbys, int norderbys)
493 : {
494 977 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
495 :
496 977 : ginFreeScanKeys(so);
497 :
498 977 : if (scankey && scan->numberOfKeys > 0)
499 977 : memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
500 977 : }
501 :
502 :
503 : void
504 974 : ginendscan(IndexScanDesc scan)
505 : {
506 974 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
507 :
508 974 : ginFreeScanKeys(so);
509 :
510 974 : MemoryContextDelete(so->tempCtx);
511 974 : MemoryContextDelete(so->keyCtx);
512 :
513 974 : pfree(so);
514 974 : }
|
