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(sizeof(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 = (GinScanEntry) palloc(sizeof(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 = (GinScanEntry *)
127 46 : repalloc(so->entries, so->allocentries * sizeof(GinScanEntry));
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 4148 : key->scanEntry = (GinScanEntry *) palloc(sizeof(GinScanEntry) *
174 2074 : (nQueryValues + 1));
175 4148 : key->entryRes = (GinTernaryValue *) palloc0(sizeof(GinTernaryValue) *
176 2074 : (nQueryValues + 1));
177 :
178 2074 : key->query = query;
179 2074 : key->queryValues = queryValues;
180 2074 : key->queryCategories = queryCategories;
181 2074 : key->extra_data = extra_data;
182 2074 : key->strategy = strategy;
183 2074 : key->searchMode = searchMode;
184 2074 : key->attnum = attnum;
185 :
186 : /*
187 : * Initially, scan keys of GIN_SEARCH_MODE_ALL mode are marked
188 : * excludeOnly. This might get changed later.
189 : */
190 2074 : key->excludeOnly = (searchMode == GIN_SEARCH_MODE_ALL);
191 :
192 2074 : ItemPointerSetMin(&key->curItem);
193 2074 : key->curItemMatches = false;
194 2074 : key->recheckCurItem = false;
195 2074 : key->isFinished = false;
196 2074 : key->nrequired = 0;
197 2074 : key->nadditional = 0;
198 2074 : key->requiredEntries = NULL;
199 2074 : key->additionalEntries = NULL;
200 :
201 2074 : ginInitConsistentFunction(ginstate, key);
202 :
203 : /* Set up normal scan entries using extractQueryFn's outputs */
204 8824 : for (i = 0; i < nQueryValues; i++)
205 : {
206 : Datum queryKey;
207 : GinNullCategory queryCategory;
208 : bool isPartialMatch;
209 : Pointer this_extra;
210 :
211 6750 : queryKey = queryValues[i];
212 6750 : queryCategory = queryCategories[i];
213 6750 : isPartialMatch =
214 6750 : (ginstate->canPartialMatch[attnum - 1] && partial_matches)
215 6750 : ? partial_matches[i] : false;
216 6750 : this_extra = (extra_data) ? extra_data[i] : NULL;
217 :
218 6750 : key->scanEntry[i] = ginFillScanEntry(so, attnum,
219 : strategy, searchMode,
220 : queryKey, queryCategory,
221 : isPartialMatch, this_extra);
222 : }
223 :
224 : /*
225 : * For GIN_SEARCH_MODE_INCLUDE_EMPTY and GIN_SEARCH_MODE_EVERYTHING search
226 : * modes, we add the "hidden" entry immediately. GIN_SEARCH_MODE_ALL is
227 : * handled later, since we might be able to omit the hidden entry for it.
228 : */
229 2074 : if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
230 44 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_ITEM);
231 2030 : else if (searchMode == GIN_SEARCH_MODE_EVERYTHING)
232 0 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
233 2074 : }
234 :
235 : /*
236 : * Release current scan keys, if any.
237 : */
238 : void
239 5856 : ginFreeScanKeys(GinScanOpaque so)
240 : {
241 : uint32 i;
242 :
243 5856 : if (so->keys == NULL)
244 3902 : return;
245 :
246 9030 : for (i = 0; i < so->totalentries; i++)
247 : {
248 7076 : GinScanEntry entry = so->entries[i];
249 :
250 7076 : if (entry->buffer != InvalidBuffer)
251 0 : ReleaseBuffer(entry->buffer);
252 7076 : if (entry->list)
253 4454 : pfree(entry->list);
254 7076 : if (entry->matchIterator)
255 0 : tbm_end_private_iterate(entry->matchIterator);
256 7076 : if (entry->matchBitmap)
257 880 : tbm_free(entry->matchBitmap);
258 : }
259 :
260 1954 : MemoryContextReset(so->keyCtx);
261 :
262 1954 : so->keys = NULL;
263 1954 : so->nkeys = 0;
264 1954 : so->entries = NULL;
265 1954 : so->totalentries = 0;
266 : }
267 :
268 : void
269 1954 : ginNewScanKey(IndexScanDesc scan)
270 : {
271 1954 : ScanKey scankey = scan->keyData;
272 1954 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
273 : int i;
274 : int numExcludeOnly;
275 1954 : bool hasNullQuery = false;
276 1954 : bool attrHasNormalScan[INDEX_MAX_KEYS] = {false};
277 : MemoryContext oldCtx;
278 :
279 : /*
280 : * Allocate all the scan key information in the key context. (If
281 : * extractQuery leaks anything there, it won't be reset until the end of
282 : * scan or rescan, but that's OK.)
283 : */
284 1954 : oldCtx = MemoryContextSwitchTo(so->keyCtx);
285 :
286 : /* if no scan keys provided, allocate extra EVERYTHING GinScanKey */
287 1954 : so->keys = (GinScanKey)
288 1954 : palloc(Max(scan->numberOfKeys, 1) * sizeof(GinScanKeyData));
289 1954 : so->nkeys = 0;
290 :
291 : /* initialize expansible array of GinScanEntry pointers */
292 1954 : so->totalentries = 0;
293 1954 : so->allocentries = 32;
294 1954 : so->entries = (GinScanEntry *)
295 1954 : palloc(so->allocentries * sizeof(GinScanEntry));
296 :
297 1954 : so->isVoidRes = false;
298 :
299 4028 : for (i = 0; i < scan->numberOfKeys; i++)
300 : {
301 2086 : ScanKey skey = &scankey[i];
302 : Datum *queryValues;
303 2086 : int32 nQueryValues = 0;
304 2086 : bool *partial_matches = NULL;
305 2086 : Pointer *extra_data = NULL;
306 2086 : bool *nullFlags = NULL;
307 : GinNullCategory *categories;
308 2086 : int32 searchMode = GIN_SEARCH_MODE_DEFAULT;
309 :
310 : /*
311 : * We assume that GIN-indexable operators are strict, so a null query
312 : * argument means an unsatisfiable query.
313 : */
314 2086 : if (skey->sk_flags & SK_ISNULL)
315 : {
316 0 : so->isVoidRes = true;
317 12 : break;
318 : }
319 :
320 : /* OK to call the extractQueryFn */
321 : queryValues = (Datum *)
322 6258 : DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[skey->sk_attno - 1],
323 2086 : so->ginstate.supportCollation[skey->sk_attno - 1],
324 : skey->sk_argument,
325 : PointerGetDatum(&nQueryValues),
326 2086 : UInt16GetDatum(skey->sk_strategy),
327 : PointerGetDatum(&partial_matches),
328 : PointerGetDatum(&extra_data),
329 : PointerGetDatum(&nullFlags),
330 : PointerGetDatum(&searchMode)));
331 :
332 : /*
333 : * If bogus searchMode is returned, treat as GIN_SEARCH_MODE_ALL; note
334 : * in particular we don't allow extractQueryFn to select
335 : * GIN_SEARCH_MODE_EVERYTHING.
336 : */
337 2086 : if (searchMode < GIN_SEARCH_MODE_DEFAULT ||
338 2086 : searchMode > GIN_SEARCH_MODE_ALL)
339 0 : searchMode = GIN_SEARCH_MODE_ALL;
340 :
341 : /* Non-default modes require the index to have placeholders */
342 2086 : if (searchMode != GIN_SEARCH_MODE_DEFAULT)
343 368 : hasNullQuery = true;
344 :
345 : /*
346 : * In default mode, no keys means an unsatisfiable query.
347 : */
348 2086 : if (queryValues == NULL || nQueryValues <= 0)
349 : {
350 308 : if (searchMode == GIN_SEARCH_MODE_DEFAULT)
351 : {
352 12 : so->isVoidRes = true;
353 12 : break;
354 : }
355 296 : nQueryValues = 0; /* ensure sane value */
356 : }
357 :
358 : /*
359 : * Create GinNullCategory representation. If the extractQueryFn
360 : * didn't create a nullFlags array, we assume everything is non-null.
361 : * While at it, detect whether any null keys are present.
362 : */
363 2074 : categories = (GinNullCategory *) palloc0(nQueryValues * sizeof(GinNullCategory));
364 2074 : if (nullFlags)
365 : {
366 : int32 j;
367 :
368 4034 : for (j = 0; j < nQueryValues; j++)
369 : {
370 3464 : if (nullFlags[j])
371 : {
372 0 : categories[j] = GIN_CAT_NULL_KEY;
373 0 : hasNullQuery = true;
374 : }
375 : }
376 : }
377 :
378 2074 : ginFillScanKey(so, skey->sk_attno,
379 2074 : skey->sk_strategy, searchMode,
380 : skey->sk_argument, nQueryValues,
381 : queryValues, categories,
382 : partial_matches, extra_data);
383 :
384 : /* Remember if we had any non-excludeOnly keys */
385 2074 : if (searchMode != GIN_SEARCH_MODE_ALL)
386 1750 : attrHasNormalScan[skey->sk_attno - 1] = true;
387 : }
388 :
389 : /*
390 : * Processing GIN_SEARCH_MODE_ALL scan keys requires us to make a second
391 : * pass over the scan keys. Above we marked each such scan key as
392 : * excludeOnly. If the involved column has any normal (not excludeOnly)
393 : * scan key as well, then we can leave it like that. Otherwise, one
394 : * excludeOnly scan key must receive a GIN_CAT_EMPTY_QUERY hidden entry
395 : * and be set to normal (excludeOnly = false).
396 : */
397 1954 : numExcludeOnly = 0;
398 4028 : for (i = 0; i < so->nkeys; i++)
399 : {
400 2074 : GinScanKey key = &so->keys[i];
401 :
402 2074 : if (key->searchMode != GIN_SEARCH_MODE_ALL)
403 1750 : continue;
404 :
405 324 : if (!attrHasNormalScan[key->attnum - 1])
406 : {
407 282 : key->excludeOnly = false;
408 282 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
409 282 : attrHasNormalScan[key->attnum - 1] = true;
410 : }
411 : else
412 42 : numExcludeOnly++;
413 : }
414 :
415 : /*
416 : * If we left any excludeOnly scan keys as-is, move them to the end of the
417 : * scan key array: they must appear after normal key(s).
418 : */
419 1954 : if (numExcludeOnly > 0)
420 : {
421 : GinScanKey tmpkeys;
422 : int iNormalKey;
423 : int iExcludeOnly;
424 :
425 : /* We'd better have made at least one normal key */
426 : Assert(numExcludeOnly < so->nkeys);
427 : /* Make a temporary array to hold the re-ordered scan keys */
428 42 : tmpkeys = (GinScanKey) palloc(so->nkeys * sizeof(GinScanKeyData));
429 : /* Re-order the keys ... */
430 42 : iNormalKey = 0;
431 42 : iExcludeOnly = so->nkeys - numExcludeOnly;
432 150 : for (i = 0; i < so->nkeys; i++)
433 : {
434 108 : GinScanKey key = &so->keys[i];
435 :
436 108 : if (key->excludeOnly)
437 : {
438 42 : memcpy(tmpkeys + iExcludeOnly, key, sizeof(GinScanKeyData));
439 42 : iExcludeOnly++;
440 : }
441 : else
442 : {
443 66 : memcpy(tmpkeys + iNormalKey, key, sizeof(GinScanKeyData));
444 66 : iNormalKey++;
445 : }
446 : }
447 : Assert(iNormalKey == so->nkeys - numExcludeOnly);
448 : Assert(iExcludeOnly == so->nkeys);
449 : /* ... and copy them back to so->keys[] */
450 42 : memcpy(so->keys, tmpkeys, so->nkeys * sizeof(GinScanKeyData));
451 42 : pfree(tmpkeys);
452 : }
453 :
454 : /*
455 : * If there are no regular scan keys, generate an EVERYTHING scankey to
456 : * drive a full-index scan.
457 : */
458 1954 : if (so->nkeys == 0 && !so->isVoidRes)
459 : {
460 0 : hasNullQuery = true;
461 0 : ginFillScanKey(so, FirstOffsetNumber,
462 : InvalidStrategy, GIN_SEARCH_MODE_EVERYTHING,
463 : (Datum) 0, 0,
464 : NULL, NULL, NULL, NULL);
465 : }
466 :
467 : /*
468 : * If the index is version 0, it may be missing null and placeholder
469 : * entries, which would render searches for nulls and full-index scans
470 : * unreliable. Throw an error if so.
471 : */
472 1954 : if (hasNullQuery && !so->isVoidRes)
473 : {
474 : GinStatsData ginStats;
475 :
476 328 : ginGetStats(scan->indexRelation, &ginStats);
477 328 : if (ginStats.ginVersion < 1)
478 0 : ereport(ERROR,
479 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
480 : errmsg("old GIN indexes do not support whole-index scans nor searches for nulls"),
481 : errhint("To fix this, do REINDEX INDEX \"%s\".",
482 : RelationGetRelationName(scan->indexRelation))));
483 : }
484 :
485 1954 : MemoryContextSwitchTo(oldCtx);
486 :
487 1954 : pgstat_count_index_scan(scan->indexRelation);
488 1954 : if (scan->instrument)
489 1954 : scan->instrument->nsearches++;
490 1954 : }
491 :
492 : void
493 1954 : ginrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
494 : ScanKey orderbys, int norderbys)
495 : {
496 1954 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
497 :
498 1954 : ginFreeScanKeys(so);
499 :
500 1954 : if (scankey && scan->numberOfKeys > 0)
501 1954 : memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
502 1954 : }
503 :
504 :
505 : void
506 1948 : ginendscan(IndexScanDesc scan)
507 : {
508 1948 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
509 :
510 1948 : ginFreeScanKeys(so);
511 :
512 1948 : MemoryContextDelete(so->tempCtx);
513 1948 : MemoryContextDelete(so->keyCtx);
514 :
515 1948 : pfree(so);
516 1948 : }
|
