Debian Codegraph @

src/backend/access/gin/ginscan.c

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