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 1592 : 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 1592 : scan = RelationGetIndexScan(rel, nkeys, norderbys);
34 :
35 : /* allocate private workspace */
36 1592 : so = (GinScanOpaque) palloc(sizeof(GinScanOpaqueData));
37 1592 : so->keys = NULL;
38 1592 : so->nkeys = 0;
39 1592 : so->tempCtx = AllocSetContextCreate(CurrentMemoryContext,
40 : "Gin scan temporary context",
41 : ALLOCSET_DEFAULT_SIZES);
42 1592 : so->keyCtx = AllocSetContextCreate(CurrentMemoryContext,
43 : "Gin scan key context",
44 : ALLOCSET_DEFAULT_SIZES);
45 1592 : initGinState(&so->ginstate, scan->indexRelation);
46 :
47 1592 : scan->opaque = so;
48 :
49 1592 : 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 6692 : ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,
58 : StrategyNumber strategy, int32 searchMode,
59 : Datum queryKey, GinNullCategory queryCategory,
60 : bool isPartialMatch, Pointer extra_data)
61 : {
62 6692 : 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 6692 : if (extra_data == NULL && so->totalentries < 100)
78 : {
79 56010 : for (i = 0; i < so->totalentries; i++)
80 : {
81 53000 : GinScanEntry prevEntry = so->entries[i];
82 :
83 53000 : if (prevEntry->extra_data == NULL &&
84 52700 : prevEntry->isPartialMatch == isPartialMatch &&
85 52700 : prevEntry->strategy == strategy &&
86 52560 : prevEntry->searchMode == searchMode &&
87 105096 : prevEntry->attnum == attnum &&
88 52536 : ginCompareEntries(ginstate, attnum,
89 : prevEntry->queryKey,
90 52536 : 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 6692 : scanEntry = (GinScanEntry) palloc(sizeof(GinScanEntryData));
102 6692 : scanEntry->queryKey = queryKey;
103 6692 : scanEntry->queryCategory = queryCategory;
104 6692 : scanEntry->isPartialMatch = isPartialMatch;
105 6692 : scanEntry->extra_data = extra_data;
106 6692 : scanEntry->strategy = strategy;
107 6692 : scanEntry->searchMode = searchMode;
108 6692 : scanEntry->attnum = attnum;
109 :
110 6692 : scanEntry->buffer = InvalidBuffer;
111 6692 : ItemPointerSetMin(&scanEntry->curItem);
112 6692 : scanEntry->matchBitmap = NULL;
113 6692 : scanEntry->matchIterator = NULL;
114 6692 : scanEntry->matchResult.blockno = InvalidBlockNumber;
115 6692 : scanEntry->matchNtuples = -1;
116 6692 : scanEntry->list = NULL;
117 6692 : scanEntry->nlist = 0;
118 6692 : scanEntry->offset = InvalidOffsetNumber;
119 6692 : scanEntry->isFinished = false;
120 6692 : scanEntry->reduceResult = false;
121 :
122 : /* Add it to so's array */
123 6692 : 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 6692 : so->entries[so->totalentries++] = scanEntry;
130 :
131 6692 : 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 1714 : 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 1714 : GinScanKey key = &(so->keys[so->nkeys++]);
166 1714 : GinState *ginstate = &so->ginstate;
167 : uint32 i;
168 :
169 1714 : key->nentries = nQueryValues;
170 1714 : key->nuserentries = nQueryValues;
171 :
172 : /* Allocate one extra array slot for possible "hidden" entry */
173 3428 : key->scanEntry = (GinScanEntry *) palloc(sizeof(GinScanEntry) *
174 1714 : (nQueryValues + 1));
175 3428 : key->entryRes = (GinTernaryValue *) palloc0(sizeof(GinTernaryValue) *
176 1714 : (nQueryValues + 1));
177 :
178 1714 : key->query = query;
179 1714 : key->queryValues = queryValues;
180 1714 : key->queryCategories = queryCategories;
181 1714 : key->extra_data = extra_data;
182 1714 : key->strategy = strategy;
183 1714 : key->searchMode = searchMode;
184 1714 : 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 1714 : key->excludeOnly = (searchMode == GIN_SEARCH_MODE_ALL);
191 :
192 1714 : ItemPointerSetMin(&key->curItem);
193 1714 : key->curItemMatches = false;
194 1714 : key->recheckCurItem = false;
195 1714 : key->isFinished = false;
196 1714 : key->nrequired = 0;
197 1714 : key->nadditional = 0;
198 1714 : key->requiredEntries = NULL;
199 1714 : key->additionalEntries = NULL;
200 :
201 1714 : ginInitConsistentFunction(ginstate, key);
202 :
203 : /* Set up normal scan entries using extractQueryFn's outputs */
204 8080 : for (i = 0; i < nQueryValues; i++)
205 : {
206 : Datum queryKey;
207 : GinNullCategory queryCategory;
208 : bool isPartialMatch;
209 : Pointer this_extra;
210 :
211 6366 : queryKey = queryValues[i];
212 6366 : queryCategory = queryCategories[i];
213 6366 : isPartialMatch =
214 6366 : (ginstate->canPartialMatch[attnum - 1] && partial_matches)
215 6366 : ? partial_matches[i] : false;
216 6366 : this_extra = (extra_data) ? extra_data[i] : NULL;
217 :
218 6366 : 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 1714 : if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
230 44 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_ITEM);
231 1670 : else if (searchMode == GIN_SEARCH_MODE_EVERYTHING)
232 0 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
233 1714 : }
234 :
235 : /*
236 : * Release current scan keys, if any.
237 : */
238 : void
239 4788 : ginFreeScanKeys(GinScanOpaque so)
240 : {
241 : uint32 i;
242 :
243 4788 : if (so->keys == NULL)
244 3190 : return;
245 :
246 8290 : for (i = 0; i < so->totalentries; i++)
247 : {
248 6692 : GinScanEntry entry = so->entries[i];
249 :
250 6692 : if (entry->buffer != InvalidBuffer)
251 0 : ReleaseBuffer(entry->buffer);
252 6692 : if (entry->list)
253 4436 : pfree(entry->list);
254 6692 : if (entry->matchIterator)
255 0 : tbm_end_private_iterate(entry->matchIterator);
256 6692 : if (entry->matchBitmap)
257 534 : tbm_free(entry->matchBitmap);
258 : }
259 :
260 1598 : MemoryContextReset(so->keyCtx);
261 :
262 1598 : so->keys = NULL;
263 1598 : so->nkeys = 0;
264 1598 : so->entries = NULL;
265 1598 : so->totalentries = 0;
266 : }
267 :
268 : void
269 1598 : ginNewScanKey(IndexScanDesc scan)
270 : {
271 1598 : ScanKey scankey = scan->keyData;
272 1598 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
273 : int i;
274 1598 : bool hasNullQuery = false;
275 1598 : bool attrHasNormalScan[INDEX_MAX_KEYS] = {false};
276 : MemoryContext oldCtx;
277 :
278 : /*
279 : * Allocate all the scan key information in the key context. (If
280 : * extractQuery leaks anything there, it won't be reset until the end of
281 : * scan or rescan, but that's OK.)
282 : */
283 1598 : oldCtx = MemoryContextSwitchTo(so->keyCtx);
284 :
285 : /* if no scan keys provided, allocate extra EVERYTHING GinScanKey */
286 1598 : so->keys = (GinScanKey)
287 1598 : palloc(Max(scan->numberOfKeys, 1) * sizeof(GinScanKeyData));
288 1598 : so->nkeys = 0;
289 :
290 : /* initialize expansible array of GinScanEntry pointers */
291 1598 : so->totalentries = 0;
292 1598 : so->allocentries = 32;
293 1598 : so->entries = (GinScanEntry *)
294 1598 : palloc(so->allocentries * sizeof(GinScanEntry));
295 :
296 1598 : so->isVoidRes = false;
297 :
298 3312 : for (i = 0; i < scan->numberOfKeys; i++)
299 : {
300 1726 : ScanKey skey = &scankey[i];
301 : Datum *queryValues;
302 1726 : int32 nQueryValues = 0;
303 1726 : bool *partial_matches = NULL;
304 1726 : Pointer *extra_data = NULL;
305 1726 : bool *nullFlags = NULL;
306 : GinNullCategory *categories;
307 1726 : int32 searchMode = GIN_SEARCH_MODE_DEFAULT;
308 :
309 : /*
310 : * We assume that GIN-indexable operators are strict, so a null query
311 : * argument means an unsatisfiable query.
312 : */
313 1726 : if (skey->sk_flags & SK_ISNULL)
314 : {
315 0 : so->isVoidRes = true;
316 12 : break;
317 : }
318 :
319 : /* OK to call the extractQueryFn */
320 : queryValues = (Datum *)
321 5178 : DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[skey->sk_attno - 1],
322 1726 : so->ginstate.supportCollation[skey->sk_attno - 1],
323 : skey->sk_argument,
324 : PointerGetDatum(&nQueryValues),
325 1726 : UInt16GetDatum(skey->sk_strategy),
326 : PointerGetDatum(&partial_matches),
327 : PointerGetDatum(&extra_data),
328 : PointerGetDatum(&nullFlags),
329 : PointerGetDatum(&searchMode)));
330 :
331 : /*
332 : * If bogus searchMode is returned, treat as GIN_SEARCH_MODE_ALL; note
333 : * in particular we don't allow extractQueryFn to select
334 : * GIN_SEARCH_MODE_EVERYTHING.
335 : */
336 1726 : if (searchMode < GIN_SEARCH_MODE_DEFAULT ||
337 1726 : searchMode > GIN_SEARCH_MODE_ALL)
338 0 : searchMode = GIN_SEARCH_MODE_ALL;
339 :
340 : /* Non-default modes require the index to have placeholders */
341 1726 : if (searchMode != GIN_SEARCH_MODE_DEFAULT)
342 364 : hasNullQuery = true;
343 :
344 : /*
345 : * In default mode, no keys means an unsatisfiable query.
346 : */
347 1726 : if (queryValues == NULL || nQueryValues <= 0)
348 : {
349 304 : if (searchMode == GIN_SEARCH_MODE_DEFAULT)
350 : {
351 12 : so->isVoidRes = true;
352 12 : break;
353 : }
354 292 : nQueryValues = 0; /* ensure sane value */
355 : }
356 :
357 : /*
358 : * Create GinNullCategory representation. If the extractQueryFn
359 : * didn't create a nullFlags array, we assume everything is non-null.
360 : * While at it, detect whether any null keys are present.
361 : */
362 1714 : categories = (GinNullCategory *) palloc0(nQueryValues * sizeof(GinNullCategory));
363 1714 : if (nullFlags)
364 : {
365 : int32 j;
366 :
367 4034 : for (j = 0; j < nQueryValues; j++)
368 : {
369 3464 : if (nullFlags[j])
370 : {
371 0 : categories[j] = GIN_CAT_NULL_KEY;
372 0 : hasNullQuery = true;
373 : }
374 : }
375 : }
376 :
377 1714 : ginFillScanKey(so, skey->sk_attno,
378 1714 : skey->sk_strategy, searchMode,
379 : skey->sk_argument, nQueryValues,
380 : queryValues, categories,
381 : partial_matches, extra_data);
382 :
383 : /* Remember if we had any non-excludeOnly keys */
384 1714 : if (searchMode != GIN_SEARCH_MODE_ALL)
385 1394 : attrHasNormalScan[skey->sk_attno - 1] = true;
386 : }
387 :
388 : /*
389 : * Processing GIN_SEARCH_MODE_ALL scan keys requires us to make a second
390 : * pass over the scan keys. Above we marked each such scan key as
391 : * excludeOnly. If the involved column has any normal (not excludeOnly)
392 : * scan key as well, then we can leave it like that. Otherwise, one
393 : * excludeOnly scan key must receive a GIN_CAT_EMPTY_QUERY hidden entry
394 : * and be set to normal (excludeOnly = false).
395 : */
396 3312 : for (i = 0; i < so->nkeys; i++)
397 : {
398 1714 : GinScanKey key = &so->keys[i];
399 :
400 1714 : if (key->searchMode != GIN_SEARCH_MODE_ALL)
401 1394 : continue;
402 :
403 320 : 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 : }
410 :
411 : /*
412 : * If there are no regular scan keys, generate an EVERYTHING scankey to
413 : * drive a full-index scan.
414 : */
415 1598 : if (so->nkeys == 0 && !so->isVoidRes)
416 : {
417 0 : hasNullQuery = true;
418 0 : ginFillScanKey(so, FirstOffsetNumber,
419 : InvalidStrategy, GIN_SEARCH_MODE_EVERYTHING,
420 : (Datum) 0, 0,
421 : NULL, NULL, NULL, NULL);
422 : }
423 :
424 : /*
425 : * If the index is version 0, it may be missing null and placeholder
426 : * entries, which would render searches for nulls and full-index scans
427 : * unreliable. Throw an error if so.
428 : */
429 1598 : if (hasNullQuery && !so->isVoidRes)
430 : {
431 : GinStatsData ginStats;
432 :
433 324 : ginGetStats(scan->indexRelation, &ginStats);
434 324 : if (ginStats.ginVersion < 1)
435 0 : ereport(ERROR,
436 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
437 : errmsg("old GIN indexes do not support whole-index scans nor searches for nulls"),
438 : errhint("To fix this, do REINDEX INDEX \"%s\".",
439 : RelationGetRelationName(scan->indexRelation))));
440 : }
441 :
442 1598 : MemoryContextSwitchTo(oldCtx);
443 :
444 1598 : pgstat_count_index_scan(scan->indexRelation);
445 1598 : if (scan->instrument)
446 1598 : scan->instrument->nsearches++;
447 1598 : }
448 :
449 : void
450 1598 : ginrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
451 : ScanKey orderbys, int norderbys)
452 : {
453 1598 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
454 :
455 1598 : ginFreeScanKeys(so);
456 :
457 1598 : if (scankey && scan->numberOfKeys > 0)
458 1598 : memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
459 1598 : }
460 :
461 :
462 : void
463 1592 : ginendscan(IndexScanDesc scan)
464 : {
465 1592 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
466 :
467 1592 : ginFreeScanKeys(so);
468 :
469 1592 : MemoryContextDelete(so->tempCtx);
470 1592 : MemoryContextDelete(so->keyCtx);
471 :
472 1592 : pfree(so);
473 1592 : }
|