PostgreSQL Source Code  git master
ginscan.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * ginscan.c
4  * routines to manage scans of inverted index relations
5  *
6  *
7  * Portions Copyright (c) 1996-2020, 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 
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;
40  "Gin scan temporary context",
43  "Gin scan key context",
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
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  if (extra_data == NULL)
73  {
74  for (i = 0; i < so->totalentries; i++)
75  {
76  GinScanEntry prevEntry = so->entries[i];
77 
78  if (prevEntry->extra_data == NULL &&
79  prevEntry->isPartialMatch == isPartialMatch &&
80  prevEntry->strategy == strategy &&
81  prevEntry->searchMode == searchMode &&
82  prevEntry->attnum == attnum &&
83  ginCompareEntries(ginstate, attnum,
84  prevEntry->queryKey,
85  prevEntry->queryCategory,
86  queryKey,
87  queryCategory) == 0)
88  {
89  /* Successful match */
90  return prevEntry;
91  }
92  }
93  }
94 
95  /* Nope, create a new entry */
96  scanEntry = (GinScanEntry) palloc(sizeof(GinScanEntryData));
97  scanEntry->queryKey = queryKey;
98  scanEntry->queryCategory = queryCategory;
99  scanEntry->isPartialMatch = isPartialMatch;
100  scanEntry->extra_data = extra_data;
101  scanEntry->strategy = strategy;
102  scanEntry->searchMode = searchMode;
103  scanEntry->attnum = attnum;
104 
105  scanEntry->buffer = InvalidBuffer;
106  ItemPointerSetMin(&scanEntry->curItem);
107  scanEntry->matchBitmap = NULL;
108  scanEntry->matchIterator = NULL;
109  scanEntry->matchResult = NULL;
110  scanEntry->list = NULL;
111  scanEntry->nlist = 0;
112  scanEntry->offset = InvalidOffsetNumber;
113  scanEntry->isFinished = false;
114  scanEntry->reduceResult = false;
115 
116  /* Add it to so's array */
117  if (so->totalentries >= so->allocentries)
118  {
119  so->allocentries *= 2;
120  so->entries = (GinScanEntry *)
121  repalloc(so->entries, so->allocentries * sizeof(GinScanEntry));
122  }
123  so->entries[so->totalentries++] = scanEntry;
124 
125  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
138  GinNullCategory queryCategory)
139 {
140  int i = key->nentries++;
141 
142  /* strategy is of no interest because this is not a partial-match item */
143  key->scanEntry[i] = ginFillScanEntry(so, key->attnum,
145  (Datum) 0, queryCategory,
146  false, NULL);
147 }
148 
149 /*
150  * Initialize the next GinScanKey using the output from the extractQueryFn
151  */
152 static void
154  StrategyNumber strategy, int32 searchMode,
155  Datum query, uint32 nQueryValues,
156  Datum *queryValues, GinNullCategory *queryCategories,
157  bool *partial_matches, Pointer *extra_data)
158 {
159  GinScanKey key = &(so->keys[so->nkeys++]);
160  GinState *ginstate = &so->ginstate;
161  uint32 i;
162 
163  key->nentries = nQueryValues;
164  key->nuserentries = nQueryValues;
165 
166  /* Allocate one extra array slot for possible "hidden" entry */
167  key->scanEntry = (GinScanEntry *) palloc(sizeof(GinScanEntry) *
168  (nQueryValues + 1));
169  key->entryRes = (GinTernaryValue *) palloc0(sizeof(GinTernaryValue) *
170  (nQueryValues + 1));
171 
172  key->query = query;
173  key->queryValues = queryValues;
174  key->queryCategories = queryCategories;
175  key->extra_data = extra_data;
176  key->strategy = strategy;
177  key->searchMode = searchMode;
178  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  */
184  key->excludeOnly = (searchMode == GIN_SEARCH_MODE_ALL);
185 
186  ItemPointerSetMin(&key->curItem);
187  key->curItemMatches = false;
188  key->recheckCurItem = false;
189  key->isFinished = false;
190  key->nrequired = 0;
191  key->nadditional = 0;
192  key->requiredEntries = NULL;
193  key->additionalEntries = NULL;
194 
195  ginInitConsistentFunction(ginstate, key);
196 
197  /* Set up normal scan entries using extractQueryFn's outputs */
198  for (i = 0; i < nQueryValues; i++)
199  {
200  Datum queryKey;
201  GinNullCategory queryCategory;
202  bool isPartialMatch;
203  Pointer this_extra;
204 
205  queryKey = queryValues[i];
206  queryCategory = queryCategories[i];
207  isPartialMatch =
208  (ginstate->canPartialMatch[attnum - 1] && partial_matches)
209  ? partial_matches[i] : false;
210  this_extra = (extra_data) ? extra_data[i] : NULL;
211 
212  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  */
223  if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
225  else if (searchMode == GIN_SEARCH_MODE_EVERYTHING)
227 }
228 
229 /*
230  * Release current scan keys, if any.
231  */
232 void
234 {
235  uint32 i;
236 
237  if (so->keys == NULL)
238  return;
239 
240  for (i = 0; i < so->totalentries; i++)
241  {
242  GinScanEntry entry = so->entries[i];
243 
244  if (entry->buffer != InvalidBuffer)
245  ReleaseBuffer(entry->buffer);
246  if (entry->list)
247  pfree(entry->list);
248  if (entry->matchIterator)
250  if (entry->matchBitmap)
251  tbm_free(entry->matchBitmap);
252  }
253 
255 
256  so->keys = NULL;
257  so->nkeys = 0;
258  so->entries = NULL;
259  so->totalentries = 0;
260 }
261 
262 void
264 {
265  ScanKey scankey = scan->keyData;
266  GinScanOpaque so = (GinScanOpaque) scan->opaque;
267  int i;
268  bool hasNullQuery = false;
269  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  */
277  oldCtx = MemoryContextSwitchTo(so->keyCtx);
278 
279  /* if no scan keys provided, allocate extra EVERYTHING GinScanKey */
280  so->keys = (GinScanKey)
281  palloc(Max(scan->numberOfKeys, 1) * sizeof(GinScanKeyData));
282  so->nkeys = 0;
283 
284  /* initialize expansible array of GinScanEntry pointers */
285  so->totalentries = 0;
286  so->allocentries = 32;
287  so->entries = (GinScanEntry *)
288  palloc(so->allocentries * sizeof(GinScanEntry));
289 
290  so->isVoidRes = false;
291 
292  for (i = 0; i < scan->numberOfKeys; i++)
293  {
294  ScanKey skey = &scankey[i];
295  Datum *queryValues;
296  int32 nQueryValues = 0;
297  bool *partial_matches = NULL;
298  Pointer *extra_data = NULL;
299  bool *nullFlags = NULL;
300  GinNullCategory *categories;
301  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  */
307  if (skey->sk_flags & SK_ISNULL)
308  {
309  so->isVoidRes = true;
310  break;
311  }
312 
313  /* OK to call the extractQueryFn */
314  queryValues = (Datum *)
315  DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[skey->sk_attno - 1],
316  so->ginstate.supportCollation[skey->sk_attno - 1],
317  skey->sk_argument,
318  PointerGetDatum(&nQueryValues),
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  */
330  if (searchMode < GIN_SEARCH_MODE_DEFAULT ||
331  searchMode > GIN_SEARCH_MODE_ALL)
332  searchMode = GIN_SEARCH_MODE_ALL;
333 
334  /* Non-default modes require the index to have placeholders */
335  if (searchMode != GIN_SEARCH_MODE_DEFAULT)
336  hasNullQuery = true;
337 
338  /*
339  * In default mode, no keys means an unsatisfiable query.
340  */
341  if (queryValues == NULL || nQueryValues <= 0)
342  {
343  if (searchMode == GIN_SEARCH_MODE_DEFAULT)
344  {
345  so->isVoidRes = true;
346  break;
347  }
348  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  */
356  categories = (GinNullCategory *) palloc0(nQueryValues * sizeof(GinNullCategory));
357  if (nullFlags)
358  {
359  int32 j;
360 
361  for (j = 0; j < nQueryValues; j++)
362  {
363  if (nullFlags[j])
364  {
365  categories[j] = GIN_CAT_NULL_KEY;
366  hasNullQuery = true;
367  }
368  }
369  }
370 
371  ginFillScanKey(so, skey->sk_attno,
372  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 */
378  if (searchMode != GIN_SEARCH_MODE_ALL)
379  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  for (i = 0; i < so->nkeys; i++)
391  {
392  GinScanKey key = &so->keys[i];
393 
394  if (key->searchMode != GIN_SEARCH_MODE_ALL)
395  continue;
396 
397  if (!attrHasNormalScan[key->attnum - 1])
398  {
399  key->excludeOnly = false;
401  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  */
409  if (so->nkeys == 0 && !so->isVoidRes)
410  {
411  hasNullQuery = true;
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  */
423  if (hasNullQuery && !so->isVoidRes)
424  {
425  GinStatsData ginStats;
426 
427  ginGetStats(scan->indexRelation, &ginStats);
428  if (ginStats.ginVersion < 1)
429  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 
436  MemoryContextSwitchTo(oldCtx);
437 
438  pgstat_count_index_scan(scan->indexRelation);
439 }
440 
441 void
442 ginrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
443  ScanKey orderbys, int norderbys)
444 {
445  GinScanOpaque so = (GinScanOpaque) scan->opaque;
446 
447  ginFreeScanKeys(so);
448 
449  if (scankey && scan->numberOfKeys > 0)
450  {
451  memmove(scan->keyData, scankey,
452  scan->numberOfKeys * sizeof(ScanKeyData));
453  }
454 }
455 
456 
457 void
459 {
460  GinScanOpaque so = (GinScanOpaque) scan->opaque;
461 
462  ginFreeScanKeys(so);
463 
466 
467  pfree(so);
468 }
#define InvalidStrategy
Definition: stratnum.h:24
#define GIN_CAT_EMPTY_QUERY
Definition: ginblock.h:213
IndexScanDesc ginbeginscan(Relation rel, int nkeys, int norderbys)
Definition: ginscan.c:25
Datum * queryValues
Definition: gin_private.h:299
void ginendscan(IndexScanDesc scan)
Definition: ginscan.c:458
ItemPointerData curItem
Definition: gin_private.h:348
void tbm_end_iterate(TBMIterator *iterator)
Definition: tidbitmap.c:1145
void ginrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)
Definition: ginscan.c:442
OffsetNumber offset
Definition: gin_private.h:358
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:212
#define AllocSetContextCreate
Definition: memutils.h:170
int errhint(const char *fmt,...)
Definition: elog.c:1149
Pointer * extra_data
Definition: gin_private.h:301
static void ginScanKeyAddHiddenEntry(GinScanOpaque so, GinScanKey key, GinNullCategory queryCategory)
Definition: ginscan.c:137
#define PointerGetDatum(X)
Definition: postgres.h:556
TBMIterator * matchIterator
Definition: gin_private.h:352
#define GIN_SEARCH_MODE_EVERYTHING
Definition: gin.h:37
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define InvalidBuffer
Definition: buf.h:25
bool canPartialMatch[INDEX_MAX_KEYS]
Definition: gin_private.h:85
uint16 StrategyNumber
Definition: stratnum.h:22
int ginCompareEntries(GinState *ginstate, OffsetNumber attnum, Datum a, GinNullCategory categorya, Datum b, GinNullCategory categoryb)
Definition: ginutil.c:395
int errcode(int sqlerrcode)
Definition: elog.c:691
Pointer extra_data
Definition: gin_private.h:339
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3513
ItemPointerData * list
Definition: gin_private.h:356
signed int int32
Definition: c.h:417
Relation indexRelation
Definition: relscan.h:115
uint16 OffsetNumber
Definition: off.h:24
GinScanEntry * scanEntry
Definition: gin_private.h:273
#define GIN_SEARCH_MODE_ALL
Definition: gin.h:36
void pfree(void *pointer)
Definition: mcxt.c:1057
char * Pointer
Definition: c.h:406
#define GIN_SEARCH_MODE_INCLUDE_EMPTY
Definition: gin.h:35
#define ERROR
Definition: elog.h:43
signed char GinNullCategory
Definition: ginblock.h:207
Datum FunctionCall7Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2, Datum arg3, Datum arg4, Datum arg5, Datum arg6, Datum arg7)
Definition: fmgr.c:1287
struct GinScanKeyData * GinScanKey
Definition: gin_private.h:261
StrategyNumber sk_strategy
Definition: skey.h:68
char GinTernaryValue
Definition: gin.h:58
OffsetNumber attnum
Definition: gin_private.h:342
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:192
StrategyNumber strategy
Definition: gin_private.h:302
GinScanOpaqueData * GinScanOpaque
Definition: gin_private.h:383
static void ginFillScanKey(GinScanOpaque so, OffsetNumber attnum, StrategyNumber strategy, int32 searchMode, Datum query, uint32 nQueryValues, Datum *queryValues, GinNullCategory *queryCategories, bool *partial_matches, Pointer *extra_data)
Definition: ginscan.c:153
void tbm_free(TIDBitmap *tbm)
Definition: tidbitmap.c:321
static GinScanEntry ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum, StrategyNumber strategy, int32 searchMode, Datum queryKey, GinNullCategory queryCategory, bool isPartialMatch, Pointer extra_data)
Definition: ginscan.c:57
#define FirstOffsetNumber
Definition: off.h:27
MemoryContext keyCtx
Definition: gin_private.h:378
void initGinState(GinState *state, Relation index)
Definition: ginutil.c:95
GinTernaryValue * entryRes
Definition: gin_private.h:289
#define RelationGetRelationName(relation)
Definition: rel.h:491
#define pgstat_count_index_scan(rel)
Definition: pgstat.h:1497
unsigned int uint32
Definition: c.h:429
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
OffsetNumber attnum
Definition: gin_private.h:304
#define SK_ISNULL
Definition: skey.h:115
struct GinScanEntryData * GinScanEntry
Definition: gin_private.h:263
#define ItemPointerSetMin(p)
Definition: ginblock.h:167
uint32 nuserentries
Definition: gin_private.h:270
TIDBitmap * matchBitmap
Definition: gin_private.h:351
GinScanKey keys
Definition: gin_private.h:371
#define MemoryContextResetAndDeleteChildren(ctx)
Definition: memutils.h:67
MemoryContext tempCtx
Definition: gin_private.h:368
#define GIN_CAT_NULL_KEY
Definition: ginblock.h:210
GinScanEntry * requiredEntries
Definition: gin_private.h:283
void * palloc0(Size size)
Definition: mcxt.c:981
struct GinScanKeyData GinScanKeyData
uintptr_t Datum
Definition: postgres.h:367
void ginGetStats(Relation index, GinStatsData *stats)
Definition: ginutil.c:630
StrategyNumber strategy
Definition: gin_private.h:340
#define GIN_SEARCH_MODE_DEFAULT
Definition: gin.h:34
GinNullCategory * queryCategories
Definition: gin_private.h:300
TBMIterateResult * matchResult
Definition: gin_private.h:353
#define InvalidOffsetNumber
Definition: off.h:26
int16 attnum
Definition: pg_attribute.h:79
#define ereport(elevel,...)
Definition: elog.h:155
void ginNewScanKey(IndexScanDesc scan)
Definition: ginscan.c:263
#define Max(x, y)
Definition: c.h:976
int sk_flags
Definition: skey.h:66
#define Assert(condition)
Definition: c.h:800
GinNullCategory queryCategory
Definition: gin_private.h:337
#define INDEX_MAX_KEYS
ItemPointerData curItem
Definition: gin_private.h:327
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1070
int32 ginVersion
Definition: gin.h:49
#define DatumGetPointer(X)
Definition: postgres.h:549
struct ScanKeyData * keyData
Definition: relscan.h:119
void ginInitConsistentFunction(GinState *ginstate, GinScanKey key)
Definition: ginlogic.c:223
GinScanEntry * entries
Definition: gin_private.h:374
void * palloc(Size size)
Definition: mcxt.c:950
int errmsg(const char *fmt,...)
Definition: elog.c:902
GinScanEntry * additionalEntries
Definition: gin_private.h:285
int i
IndexScanDesc RelationGetIndexScan(Relation indexRelation, int nkeys, int norderbys)
Definition: genam.c:81
#define GIN_CAT_EMPTY_ITEM
Definition: ginblock.h:211
Datum sk_argument
Definition: skey.h:72
#define UInt16GetDatum(X)
Definition: postgres.h:465
AttrNumber sk_attno
Definition: skey.h:67
void ginFreeScanKeys(GinScanOpaque so)
Definition: ginscan.c:233