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