Age Owner Branch data TLA 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-2024, 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
3010 tgl@sss.pgh.pa.us 25 :CBC 796 : ginbeginscan(Relation rel, int nkeys, int norderbys)
26 : : {
27 : : IndexScanDesc scan;
28 : : GinScanOpaque so;
29 : :
30 : : /* no order by operators allowed */
4882 31 [ - + ]: 796 : Assert(norderbys == 0);
32 : :
33 : 796 : scan = RelationGetIndexScan(rel, nkeys, norderbys);
34 : :
35 : : /* allocate private workspace */
36 : 796 : so = (GinScanOpaque) palloc(sizeof(GinScanOpaqueData));
37 : 796 : so->keys = NULL;
38 : 796 : so->nkeys = 0;
39 : 796 : so->tempCtx = AllocSetContextCreate(CurrentMemoryContext,
40 : : "Gin scan temporary context",
41 : : ALLOCSET_DEFAULT_SIZES);
3357 heikki.linnakangas@i 42 : 796 : so->keyCtx = AllocSetContextCreate(CurrentMemoryContext,
43 : : "Gin scan key context",
44 : : ALLOCSET_DEFAULT_SIZES);
4882 tgl@sss.pgh.pa.us 45 : 796 : initGinState(&so->ginstate, scan->indexRelation);
46 : :
47 : 796 : scan->opaque = so;
48 : :
3010 49 : 796 : 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
4845 57 : 3346 : ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,
58 : : StrategyNumber strategy, int32 searchMode,
59 : : Datum queryKey, GinNullCategory queryCategory,
60 : : bool isPartialMatch, Pointer extra_data)
61 : : {
62 : 3346 : 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 [ + + ]: 3346 : if (extra_data == NULL)
73 : : {
74 [ + + ]: 228505 : for (i = 0; i < so->totalentries; i++)
75 : : {
76 : 226000 : GinScanEntry prevEntry = so->entries[i];
77 : :
78 [ + + ]: 226000 : if (prevEntry->extra_data == NULL &&
79 [ + - ]: 225850 : prevEntry->isPartialMatch == isPartialMatch &&
80 [ + + ]: 225850 : prevEntry->strategy == strategy &&
81 [ + - ]: 225780 : prevEntry->searchMode == searchMode &&
82 [ + + - + ]: 451548 : prevEntry->attnum == attnum &&
83 : 225768 : ginCompareEntries(ginstate, attnum,
84 : : prevEntry->queryKey,
85 : 225768 : prevEntry->queryCategory,
86 : : queryKey,
87 : : queryCategory) == 0)
88 : : {
89 : : /* Successful match */
4845 tgl@sss.pgh.pa.us 90 :UBC 0 : return prevEntry;
91 : : }
92 : : }
93 : : }
94 : :
95 : : /* Nope, create a new entry */
4845 tgl@sss.pgh.pa.us 96 :CBC 3346 : scanEntry = (GinScanEntry) palloc(sizeof(GinScanEntryData));
97 : 3346 : scanEntry->queryKey = queryKey;
98 : 3346 : scanEntry->queryCategory = queryCategory;
99 : 3346 : scanEntry->isPartialMatch = isPartialMatch;
100 : 3346 : scanEntry->extra_data = extra_data;
101 : 3346 : scanEntry->strategy = strategy;
102 : 3346 : scanEntry->searchMode = searchMode;
103 : 3346 : scanEntry->attnum = attnum;
104 : :
105 : 3346 : scanEntry->buffer = InvalidBuffer;
106 : 3346 : ItemPointerSetMin(&scanEntry->curItem);
107 : 3346 : scanEntry->matchBitmap = NULL;
108 : 3346 : scanEntry->matchIterator = NULL;
109 : 3346 : scanEntry->matchResult = NULL;
110 : 3346 : scanEntry->list = NULL;
111 : 3346 : scanEntry->nlist = 0;
112 : 3346 : scanEntry->offset = InvalidOffsetNumber;
113 : 3346 : scanEntry->isFinished = false;
114 : 3346 : scanEntry->reduceResult = false;
115 : :
116 : : /* Add it to so's array */
117 [ + + ]: 3346 : if (so->totalentries >= so->allocentries)
118 : : {
119 : 23 : so->allocentries *= 2;
120 : 23 : so->entries = (GinScanEntry *)
121 : 23 : repalloc(so->entries, so->allocentries * sizeof(GinScanEntry));
122 : : }
123 : 3346 : so->entries[so->totalentries++] = scanEntry;
124 : :
125 : 3346 : return scanEntry;
126 : : }
127 : :
128 : : /*
129 : : * Append hidden scan entry of given category to the scan key.
130 : : *
131 : : * NB: this had better be called at most once per scan key, since
132 : : * ginFillScanKey leaves room for only one hidden entry. Currently,
133 : : * it seems sufficiently clear that this is true that we don't bother
134 : : * with any cross-check logic.
135 : : */
136 : : static void
1548 akorotkov@postgresql 137 : 163 : ginScanKeyAddHiddenEntry(GinScanOpaque so, GinScanKey key,
138 : : GinNullCategory queryCategory)
139 : : {
140 : 163 : int i = key->nentries++;
141 : :
142 : : /* strategy is of no interest because this is not a partial-match item */
143 : 163 : key->scanEntry[i] = ginFillScanEntry(so, key->attnum,
144 : : InvalidStrategy, key->searchMode,
145 : : (Datum) 0, queryCategory,
146 : : false, NULL);
147 : 163 : }
148 : :
149 : : /*
150 : : * Initialize the next GinScanKey using the output from the extractQueryFn
151 : : */
152 : : static void
4845 tgl@sss.pgh.pa.us 153 : 857 : ginFillScanKey(GinScanOpaque so, OffsetNumber attnum,
154 : : StrategyNumber strategy, int32 searchMode,
155 : : Datum query, uint32 nQueryValues,
156 : : Datum *queryValues, GinNullCategory *queryCategories,
157 : : bool *partial_matches, Pointer *extra_data)
158 : : {
159 : 857 : GinScanKey key = &(so->keys[so->nkeys++]);
160 : 857 : GinState *ginstate = &so->ginstate;
161 : : uint32 i;
162 : :
4846 163 : 857 : key->nentries = nQueryValues;
1548 akorotkov@postgresql 164 : 857 : key->nuserentries = nQueryValues;
165 : :
166 : : /* Allocate one extra array slot for possible "hidden" entry */
167 : 1714 : key->scanEntry = (GinScanEntry *) palloc(sizeof(GinScanEntry) *
168 : 857 : (nQueryValues + 1));
169 : 1714 : key->entryRes = (GinTernaryValue *) palloc0(sizeof(GinTernaryValue) *
170 : 857 : (nQueryValues + 1));
171 : :
4846 tgl@sss.pgh.pa.us 172 : 857 : key->query = query;
173 : 857 : key->queryValues = queryValues;
174 : 857 : key->queryCategories = queryCategories;
175 : 857 : key->extra_data = extra_data;
6557 teodor@sigaev.ru 176 : 857 : key->strategy = strategy;
4846 tgl@sss.pgh.pa.us 177 : 857 : key->searchMode = searchMode;
5756 178 : 857 : key->attnum = attnum;
179 : :
180 : : /*
181 : : * Initially, scan keys of GIN_SEARCH_MODE_ALL mode are marked
182 : : * excludeOnly. This might get changed later.
183 : : */
1548 akorotkov@postgresql 184 : 857 : key->excludeOnly = (searchMode == GIN_SEARCH_MODE_ALL);
185 : :
5006 tgl@sss.pgh.pa.us 186 : 857 : ItemPointerSetMin(&key->curItem);
4845 187 : 857 : key->curItemMatches = false;
188 : 857 : key->recheckCurItem = false;
189 : 857 : key->isFinished = false;
3362 heikki.linnakangas@i 190 : 857 : key->nrequired = 0;
191 : 857 : key->nadditional = 0;
192 : 857 : key->requiredEntries = NULL;
193 : 857 : key->additionalEntries = NULL;
194 : :
3719 195 : 857 : ginInitConsistentFunction(ginstate, key);
196 : :
197 : : /* Set up normal scan entries using extractQueryFn's outputs */
4846 tgl@sss.pgh.pa.us 198 [ + + ]: 4040 : for (i = 0; i < nQueryValues; i++)
199 : : {
200 : : Datum queryKey;
201 : : GinNullCategory queryCategory;
202 : : bool isPartialMatch;
203 : : Pointer this_extra;
204 : :
1548 akorotkov@postgresql 205 : 3183 : queryKey = queryValues[i];
206 : 3183 : queryCategory = queryCategories[i];
207 : 3183 : isPartialMatch =
208 [ + + + - ]: 3183 : (ginstate->canPartialMatch[attnum - 1] && partial_matches)
209 [ + + + + ]: 3183 : ? partial_matches[i] : false;
210 [ + + ]: 3183 : this_extra = (extra_data) ? extra_data[i] : NULL;
211 : :
4845 tgl@sss.pgh.pa.us 212 : 3183 : key->scanEntry[i] = ginFillScanEntry(so, attnum,
213 : : strategy, searchMode,
214 : : queryKey, queryCategory,
215 : : isPartialMatch, this_extra);
216 : : }
217 : :
218 : : /*
219 : : * For GIN_SEARCH_MODE_INCLUDE_EMPTY and GIN_SEARCH_MODE_EVERYTHING search
220 : : * modes, we add the "hidden" entry immediately. GIN_SEARCH_MODE_ALL is
221 : : * handled later, since we might be able to omit the hidden entry for it.
222 : : */
1548 akorotkov@postgresql 223 [ + + ]: 857 : if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
224 : 22 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_ITEM);
225 [ - + ]: 835 : else if (searchMode == GIN_SEARCH_MODE_EVERYTHING)
1548 akorotkov@postgresql 226 :UBC 0 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
6557 teodor@sigaev.ru 227 :CBC 857 : }
228 : :
229 : : /*
230 : : * Release current scan keys, if any.
231 : : */
232 : : void
3362 heikki.linnakangas@i 233 : 2394 : ginFreeScanKeys(GinScanOpaque so)
234 : : {
235 : : uint32 i;
236 : :
4845 tgl@sss.pgh.pa.us 237 [ + + ]: 2394 : if (so->keys == NULL)
6557 teodor@sigaev.ru 238 : 1595 : return;
239 : :
4845 tgl@sss.pgh.pa.us 240 [ + + ]: 4145 : for (i = 0; i < so->totalentries; i++)
241 : : {
242 : 3346 : GinScanEntry entry = so->entries[i];
243 : :
244 [ - + ]: 3346 : if (entry->buffer != InvalidBuffer)
4845 tgl@sss.pgh.pa.us 245 :UBC 0 : ReleaseBuffer(entry->buffer);
2954 tgl@sss.pgh.pa.us 246 [ + + ]:CBC 3346 : if (entry->list)
247 : 2218 : pfree(entry->list);
4845 248 [ - + ]: 3346 : if (entry->matchIterator)
4845 tgl@sss.pgh.pa.us 249 :UBC 0 : tbm_end_iterate(entry->matchIterator);
4845 tgl@sss.pgh.pa.us 250 [ + + ]:CBC 3346 : if (entry->matchBitmap)
251 : 267 : tbm_free(entry->matchBitmap);
252 : : }
253 : :
151 nathan@postgresql.or 254 :GNC 799 : MemoryContextReset(so->keyCtx);
255 : :
3357 heikki.linnakangas@i 256 :CBC 799 : so->keys = NULL;
257 : 799 : so->nkeys = 0;
4845 tgl@sss.pgh.pa.us 258 : 799 : so->entries = NULL;
259 : 799 : so->totalentries = 0;
260 : : }
261 : :
262 : : void
4928 263 : 799 : ginNewScanKey(IndexScanDesc scan)
264 : : {
6402 bruce@momjian.us 265 : 799 : ScanKey scankey = scan->keyData;
6557 teodor@sigaev.ru 266 : 799 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
267 : : int i;
4846 tgl@sss.pgh.pa.us 268 : 799 : bool hasNullQuery = false;
1548 akorotkov@postgresql 269 : 799 : bool attrHasNormalScan[INDEX_MAX_KEYS] = {false};
270 : : MemoryContext oldCtx;
271 : :
272 : : /*
273 : : * Allocate all the scan key information in the key context. (If
274 : : * extractQuery leaks anything there, it won't be reset until the end of
275 : : * scan or rescan, but that's OK.)
276 : : */
3357 heikki.linnakangas@i 277 : 799 : oldCtx = MemoryContextSwitchTo(so->keyCtx);
278 : :
279 : : /* if no scan keys provided, allocate extra EVERYTHING GinScanKey */
4846 tgl@sss.pgh.pa.us 280 : 799 : so->keys = (GinScanKey)
281 : 799 : palloc(Max(scan->numberOfKeys, 1) * sizeof(GinScanKeyData));
4845 282 : 799 : so->nkeys = 0;
283 : :
284 : : /* initialize expansible array of GinScanEntry pointers */
285 : 799 : so->totalentries = 0;
286 : 799 : so->allocentries = 32;
287 : 799 : so->entries = (GinScanEntry *)
2954 288 : 799 : palloc(so->allocentries * sizeof(GinScanEntry));
289 : :
6283 teodor@sigaev.ru 290 : 799 : so->isVoidRes = false;
291 : :
6402 bruce@momjian.us 292 [ + + ]: 1656 : for (i = 0; i < scan->numberOfKeys; i++)
293 : : {
5499 tgl@sss.pgh.pa.us 294 : 863 : ScanKey skey = &scankey[i];
295 : : Datum *queryValues;
4846 296 : 863 : int32 nQueryValues = 0;
5421 bruce@momjian.us 297 : 863 : bool *partial_matches = NULL;
298 : 863 : Pointer *extra_data = NULL;
4846 tgl@sss.pgh.pa.us 299 : 863 : bool *nullFlags = NULL;
300 : : GinNullCategory *categories;
301 : 863 : int32 searchMode = GIN_SEARCH_MODE_DEFAULT;
302 : :
303 : : /*
304 : : * We assume that GIN-indexable operators are strict, so a null query
305 : : * argument means an unsatisfiable query.
306 : : */
5499 307 [ - + ]: 863 : if (skey->sk_flags & SK_ISNULL)
308 : : {
5488 teodor@sigaev.ru 309 :UBC 0 : so->isVoidRes = true;
310 : 0 : break;
311 : : }
312 : :
313 : : /* OK to call the extractQueryFn */
314 : : queryValues = (Datum *)
4741 tgl@sss.pgh.pa.us 315 :CBC 2589 : DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[skey->sk_attno - 1],
2489 316 : 863 : so->ginstate.supportCollation[skey->sk_attno - 1],
317 : : skey->sk_argument,
318 : : PointerGetDatum(&nQueryValues),
319 : 863 : UInt16GetDatum(skey->sk_strategy),
320 : : PointerGetDatum(&partial_matches),
321 : : PointerGetDatum(&extra_data),
322 : : PointerGetDatum(&nullFlags),
323 : : PointerGetDatum(&searchMode)));
324 : :
325 : : /*
326 : : * If bogus searchMode is returned, treat as GIN_SEARCH_MODE_ALL; note
327 : : * in particular we don't allow extractQueryFn to select
328 : : * GIN_SEARCH_MODE_EVERYTHING.
329 : : */
4846 330 [ + - ]: 863 : if (searchMode < GIN_SEARCH_MODE_DEFAULT ||
331 [ - + ]: 863 : searchMode > GIN_SEARCH_MODE_ALL)
4846 tgl@sss.pgh.pa.us 332 :UBC 0 : searchMode = GIN_SEARCH_MODE_ALL;
333 : :
334 : : /* Non-default modes require the index to have placeholders */
4846 tgl@sss.pgh.pa.us 335 [ + + ]:CBC 863 : if (searchMode != GIN_SEARCH_MODE_DEFAULT)
336 : 182 : hasNullQuery = true;
337 : :
338 : : /*
339 : : * In default mode, no keys means an unsatisfiable query.
340 : : */
341 [ + + + + ]: 863 : if (queryValues == NULL || nQueryValues <= 0)
342 : : {
343 [ + + ]: 152 : if (searchMode == GIN_SEARCH_MODE_DEFAULT)
344 : : {
345 : 6 : so->isVoidRes = true;
346 : 6 : break;
347 : : }
348 : 146 : nQueryValues = 0; /* ensure sane value */
349 : : }
350 : :
351 : : /*
352 : : * Create GinNullCategory representation. If the extractQueryFn
353 : : * didn't create a nullFlags array, we assume everything is non-null.
354 : : * While at it, detect whether any null keys are present.
355 : : */
2301 peter_e@gmx.net 356 : 857 : categories = (GinNullCategory *) palloc0(nQueryValues * sizeof(GinNullCategory));
357 [ + + ]: 857 : if (nullFlags)
358 : : {
359 : : int32 j;
360 : :
4846 tgl@sss.pgh.pa.us 361 [ + + ]: 2017 : for (j = 0; j < nQueryValues; j++)
362 : : {
363 [ - + ]: 1732 : if (nullFlags[j])
364 : : {
2301 peter_e@gmx.net 365 :UBC 0 : categories[j] = GIN_CAT_NULL_KEY;
4846 tgl@sss.pgh.pa.us 366 : 0 : hasNullQuery = true;
367 : : }
368 : : }
369 : : }
370 : :
4845 tgl@sss.pgh.pa.us 371 :CBC 857 : ginFillScanKey(so, skey->sk_attno,
372 : 857 : skey->sk_strategy, searchMode,
373 : : skey->sk_argument, nQueryValues,
374 : : queryValues, categories,
375 : : partial_matches, extra_data);
376 : :
377 : : /* Remember if we had any non-excludeOnly keys */
1548 akorotkov@postgresql 378 [ + + ]: 857 : if (searchMode != GIN_SEARCH_MODE_ALL)
379 : 697 : attrHasNormalScan[skey->sk_attno - 1] = true;
380 : : }
381 : :
382 : : /*
383 : : * Processing GIN_SEARCH_MODE_ALL scan keys requires us to make a second
384 : : * pass over the scan keys. Above we marked each such scan key as
385 : : * excludeOnly. If the involved column has any normal (not excludeOnly)
386 : : * scan key as well, then we can leave it like that. Otherwise, one
387 : : * excludeOnly scan key must receive a GIN_CAT_EMPTY_QUERY hidden entry
388 : : * and be set to normal (excludeOnly = false).
389 : : */
390 [ + + ]: 1656 : for (i = 0; i < so->nkeys; i++)
391 : : {
392 : 857 : GinScanKey key = &so->keys[i];
393 : :
394 [ + + ]: 857 : if (key->searchMode != GIN_SEARCH_MODE_ALL)
395 : 697 : continue;
396 : :
397 [ + + ]: 160 : if (!attrHasNormalScan[key->attnum - 1])
398 : : {
399 : 141 : key->excludeOnly = false;
400 : 141 : ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
401 : 141 : attrHasNormalScan[key->attnum - 1] = true;
402 : : }
403 : : }
404 : :
405 : : /*
406 : : * If there are no regular scan keys, generate an EVERYTHING scankey to
407 : : * drive a full-index scan.
408 : : */
4845 tgl@sss.pgh.pa.us 409 [ + + - + ]: 799 : if (so->nkeys == 0 && !so->isVoidRes)
410 : : {
4846 tgl@sss.pgh.pa.us 411 :UBC 0 : hasNullQuery = true;
4845 412 : 0 : ginFillScanKey(so, FirstOffsetNumber,
413 : : InvalidStrategy, GIN_SEARCH_MODE_EVERYTHING,
414 : : (Datum) 0, 0,
415 : : NULL, NULL, NULL, NULL);
416 : : }
417 : :
418 : : /*
419 : : * If the index is version 0, it may be missing null and placeholder
420 : : * entries, which would render searches for nulls and full-index scans
421 : : * unreliable. Throw an error if so.
422 : : */
4846 tgl@sss.pgh.pa.us 423 [ + + + - ]:CBC 799 : if (hasNullQuery && !so->isVoidRes)
424 : : {
425 : : GinStatsData ginStats;
426 : :
427 : 162 : ginGetStats(scan->indexRelation, &ginStats);
428 [ - + ]: 162 : if (ginStats.ginVersion < 1)
4846 tgl@sss.pgh.pa.us 429 [ # # ]:UBC 0 : ereport(ERROR,
430 : : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
431 : : errmsg("old GIN indexes do not support whole-index scans nor searches for nulls"),
432 : : errhint("To fix this, do REINDEX INDEX \"%s\".",
433 : : RelationGetRelationName(scan->indexRelation))));
434 : : }
435 : :
3357 heikki.linnakangas@i 436 :CBC 799 : MemoryContextSwitchTo(oldCtx);
437 : :
6167 tgl@sss.pgh.pa.us 438 [ - + - - : 799 : pgstat_count_index_scan(scan->indexRelation);
+ - ]
6557 teodor@sigaev.ru 439 : 799 : }
440 : :
441 : : void
3010 tgl@sss.pgh.pa.us 442 : 799 : ginrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
443 : : ScanKey orderbys, int norderbys)
444 : : {
4882 445 : 799 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
446 : :
3362 heikki.linnakangas@i 447 : 799 : ginFreeScanKeys(so);
448 : :
6402 bruce@momjian.us 449 [ + - + - ]: 799 : if (scankey && scan->numberOfKeys > 0)
450 : : {
6557 teodor@sigaev.ru 451 : 799 : memmove(scan->keyData, scankey,
6402 bruce@momjian.us 452 : 799 : scan->numberOfKeys * sizeof(ScanKeyData));
453 : : }
6557 teodor@sigaev.ru 454 : 799 : }
455 : :
456 : :
457 : : void
3010 tgl@sss.pgh.pa.us 458 : 796 : ginendscan(IndexScanDesc scan)
459 : : {
6402 bruce@momjian.us 460 : 796 : GinScanOpaque so = (GinScanOpaque) scan->opaque;
461 : :
3362 heikki.linnakangas@i 462 : 796 : ginFreeScanKeys(so);
463 : :
4882 tgl@sss.pgh.pa.us 464 : 796 : MemoryContextDelete(so->tempCtx);
3357 heikki.linnakangas@i 465 : 796 : MemoryContextDelete(so->keyCtx);
466 : :
4882 tgl@sss.pgh.pa.us 467 : 796 : pfree(so);
6557 teodor@sigaev.ru 468 : 796 : }
|
