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