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-2018, 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  * Initialize the next GinScanKey using the output from the extractQueryFn
130  */
131 static void
133  StrategyNumber strategy, int32 searchMode,
134  Datum query, uint32 nQueryValues,
135  Datum *queryValues, GinNullCategory *queryCategories,
136  bool *partial_matches, Pointer *extra_data)
137 {
138  GinScanKey key = &(so->keys[so->nkeys++]);
139  GinState *ginstate = &so->ginstate;
140  uint32 nUserQueryValues = nQueryValues;
141  uint32 i;
142 
143  /* Non-default search modes add one "hidden" entry to each key */
144  if (searchMode != GIN_SEARCH_MODE_DEFAULT)
145  nQueryValues++;
146  key->nentries = nQueryValues;
147  key->nuserentries = nUserQueryValues;
148 
149  key->scanEntry = (GinScanEntry *) palloc(sizeof(GinScanEntry) * nQueryValues);
150  key->entryRes = (GinTernaryValue *) palloc0(sizeof(GinTernaryValue) * nQueryValues);
151 
152  key->query = query;
153  key->queryValues = queryValues;
154  key->queryCategories = queryCategories;
155  key->extra_data = extra_data;
156  key->strategy = strategy;
157  key->searchMode = searchMode;
158  key->attnum = attnum;
159 
160  ItemPointerSetMin(&key->curItem);
161  key->curItemMatches = false;
162  key->recheckCurItem = false;
163  key->isFinished = false;
164  key->nrequired = 0;
165  key->nadditional = 0;
166  key->requiredEntries = NULL;
167  key->additionalEntries = NULL;
168 
169  ginInitConsistentFunction(ginstate, key);
170 
171  for (i = 0; i < nQueryValues; i++)
172  {
173  Datum queryKey;
174  GinNullCategory queryCategory;
175  bool isPartialMatch;
176  Pointer this_extra;
177 
178  if (i < nUserQueryValues)
179  {
180  /* set up normal entry using extractQueryFn's outputs */
181  queryKey = queryValues[i];
182  queryCategory = queryCategories[i];
183  isPartialMatch =
184  (ginstate->canPartialMatch[attnum - 1] && partial_matches)
185  ? partial_matches[i] : false;
186  this_extra = (extra_data) ? extra_data[i] : NULL;
187  }
188  else
189  {
190  /* set up hidden entry */
191  queryKey = (Datum) 0;
192  switch (searchMode)
193  {
195  queryCategory = GIN_CAT_EMPTY_ITEM;
196  break;
197  case GIN_SEARCH_MODE_ALL:
198  queryCategory = GIN_CAT_EMPTY_QUERY;
199  break;
201  queryCategory = GIN_CAT_EMPTY_QUERY;
202  break;
203  default:
204  elog(ERROR, "unexpected searchMode: %d", searchMode);
205  queryCategory = 0; /* keep compiler quiet */
206  break;
207  }
208  isPartialMatch = false;
209  this_extra = NULL;
210 
211  /*
212  * We set the strategy to a fixed value so that ginFillScanEntry
213  * can combine these entries for different scan keys. This is
214  * safe because the strategy value in the entry struct is only
215  * used for partial-match cases. It's OK to overwrite our local
216  * variable here because this is the last loop iteration.
217  */
218  strategy = InvalidStrategy;
219  }
220 
221  key->scanEntry[i] = ginFillScanEntry(so, attnum,
222  strategy, searchMode,
223  queryKey, queryCategory,
224  isPartialMatch, this_extra);
225  }
226 }
227 
228 /*
229  * Release current scan keys, if any.
230  */
231 void
233 {
234  uint32 i;
235 
236  if (so->keys == NULL)
237  return;
238 
239  for (i = 0; i < so->totalentries; i++)
240  {
241  GinScanEntry entry = so->entries[i];
242 
243  if (entry->buffer != InvalidBuffer)
244  ReleaseBuffer(entry->buffer);
245  if (entry->list)
246  pfree(entry->list);
247  if (entry->matchIterator)
249  if (entry->matchBitmap)
250  tbm_free(entry->matchBitmap);
251  }
252 
254 
255  so->keys = NULL;
256  so->nkeys = 0;
257  so->entries = NULL;
258  so->totalentries = 0;
259 }
260 
261 void
263 {
264  ScanKey scankey = scan->keyData;
265  GinScanOpaque so = (GinScanOpaque) scan->opaque;
266  int i;
267  bool hasNullQuery = false;
268  MemoryContext oldCtx;
269 
270  /*
271  * Allocate all the scan key information in the key context. (If
272  * extractQuery leaks anything there, it won't be reset until the end of
273  * scan or rescan, but that's OK.)
274  */
275  oldCtx = MemoryContextSwitchTo(so->keyCtx);
276 
277  /* if no scan keys provided, allocate extra EVERYTHING GinScanKey */
278  so->keys = (GinScanKey)
279  palloc(Max(scan->numberOfKeys, 1) * sizeof(GinScanKeyData));
280  so->nkeys = 0;
281 
282  /* initialize expansible array of GinScanEntry pointers */
283  so->totalentries = 0;
284  so->allocentries = 32;
285  so->entries = (GinScanEntry *)
286  palloc(so->allocentries * sizeof(GinScanEntry));
287 
288  so->isVoidRes = false;
289 
290  for (i = 0; i < scan->numberOfKeys; i++)
291  {
292  ScanKey skey = &scankey[i];
293  Datum *queryValues;
294  int32 nQueryValues = 0;
295  bool *partial_matches = NULL;
296  Pointer *extra_data = NULL;
297  bool *nullFlags = NULL;
298  GinNullCategory *categories;
299  int32 searchMode = GIN_SEARCH_MODE_DEFAULT;
300 
301  /*
302  * We assume that GIN-indexable operators are strict, so a null query
303  * argument means an unsatisfiable query.
304  */
305  if (skey->sk_flags & SK_ISNULL)
306  {
307  so->isVoidRes = true;
308  break;
309  }
310 
311  /* OK to call the extractQueryFn */
312  queryValues = (Datum *)
314  so->ginstate.supportCollation[skey->sk_attno - 1],
315  skey->sk_argument,
316  PointerGetDatum(&nQueryValues),
318  PointerGetDatum(&partial_matches),
319  PointerGetDatum(&extra_data),
320  PointerGetDatum(&nullFlags),
321  PointerGetDatum(&searchMode)));
322 
323  /*
324  * If bogus searchMode is returned, treat as GIN_SEARCH_MODE_ALL; note
325  * in particular we don't allow extractQueryFn to select
326  * GIN_SEARCH_MODE_EVERYTHING.
327  */
328  if (searchMode < GIN_SEARCH_MODE_DEFAULT ||
329  searchMode > GIN_SEARCH_MODE_ALL)
330  searchMode = GIN_SEARCH_MODE_ALL;
331 
332  /* Non-default modes require the index to have placeholders */
333  if (searchMode != GIN_SEARCH_MODE_DEFAULT)
334  hasNullQuery = true;
335 
336  /*
337  * In default mode, no keys means an unsatisfiable query.
338  */
339  if (queryValues == NULL || nQueryValues <= 0)
340  {
341  if (searchMode == GIN_SEARCH_MODE_DEFAULT)
342  {
343  so->isVoidRes = true;
344  break;
345  }
346  nQueryValues = 0; /* ensure sane value */
347  }
348 
349  /*
350  * Create GinNullCategory representation. If the extractQueryFn
351  * didn't create a nullFlags array, we assume everything is non-null.
352  * While at it, detect whether any null keys are present.
353  */
354  categories = (GinNullCategory *) palloc0(nQueryValues * sizeof(GinNullCategory));
355  if (nullFlags)
356  {
357  int32 j;
358 
359  for (j = 0; j < nQueryValues; j++)
360  {
361  if (nullFlags[j])
362  {
363  categories[j] = GIN_CAT_NULL_KEY;
364  hasNullQuery = true;
365  }
366  }
367  }
368 
369  ginFillScanKey(so, skey->sk_attno,
370  skey->sk_strategy, searchMode,
371  skey->sk_argument, nQueryValues,
372  queryValues, categories,
373  partial_matches, extra_data);
374  }
375 
376  /*
377  * If there are no regular scan keys, generate an EVERYTHING scankey to
378  * drive a full-index scan.
379  */
380  if (so->nkeys == 0 && !so->isVoidRes)
381  {
382  hasNullQuery = true;
385  (Datum) 0, 0,
386  NULL, NULL, NULL, NULL);
387  }
388 
389  /*
390  * If the index is version 0, it may be missing null and placeholder
391  * entries, which would render searches for nulls and full-index scans
392  * unreliable. Throw an error if so.
393  */
394  if (hasNullQuery && !so->isVoidRes)
395  {
396  GinStatsData ginStats;
397 
398  ginGetStats(scan->indexRelation, &ginStats);
399  if (ginStats.ginVersion < 1)
400  ereport(ERROR,
401  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
402  errmsg("old GIN indexes do not support whole-index scans nor searches for nulls"),
403  errhint("To fix this, do REINDEX INDEX \"%s\".",
405  }
406 
407  MemoryContextSwitchTo(oldCtx);
408 
410 }
411 
412 void
413 ginrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
414  ScanKey orderbys, int norderbys)
415 {
416  GinScanOpaque so = (GinScanOpaque) scan->opaque;
417 
418  ginFreeScanKeys(so);
419 
420  if (scankey && scan->numberOfKeys > 0)
421  {
422  memmove(scan->keyData, scankey,
423  scan->numberOfKeys * sizeof(ScanKeyData));
424  }
425 }
426 
427 
428 void
430 {
431  GinScanOpaque so = (GinScanOpaque) scan->opaque;
432 
433  ginFreeScanKeys(so);
434 
437 
438  pfree(so);
439 }
#define InvalidStrategy
Definition: stratnum.h:24
#define GIN_CAT_EMPTY_QUERY
Definition: ginblock.h:206
IndexScanDesc ginbeginscan(Relation rel, int nkeys, int norderbys)
Definition: ginscan.c:25
Datum * queryValues
Definition: gin_private.h:296
void ginendscan(IndexScanDesc scan)
Definition: ginscan.c:429
Oid supportCollation[INDEX_MAX_KEYS]
Definition: gin_private.h:82
ItemPointerData curItem
Definition: gin_private.h:331
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:413
OffsetNumber offset
Definition: gin_private.h:341
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:211
int errhint(const char *fmt,...)
Definition: elog.c:987
Pointer * extra_data
Definition: gin_private.h:298
#define PointerGetDatum(X)
Definition: postgres.h:539
TBMIterator * matchIterator
Definition: gin_private.h:335
#define GIN_SEARCH_MODE_EVERYTHING
Definition: gin.h:36
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define InvalidBuffer
Definition: buf.h:25
bool canPartialMatch[INDEX_MAX_KEYS]
Definition: gin_private.h:80
uint16 StrategyNumber
Definition: stratnum.h:22
int ginCompareEntries(GinState *ginstate, OffsetNumber attnum, Datum a, GinNullCategory categorya, Datum b, GinNullCategory categoryb)
Definition: ginutil.c:393
int errcode(int sqlerrcode)
Definition: elog.c:575
Pointer extra_data
Definition: gin_private.h:322
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3309
ItemPointerData * list
Definition: gin_private.h:339
signed int int32
Definition: c.h:313
Relation indexRelation
Definition: relscan.h:91
uint16 OffsetNumber
Definition: off.h:24
GinScanEntry * scanEntry
Definition: gin_private.h:270
#define GIN_SEARCH_MODE_ALL
Definition: gin.h:35
void pfree(void *pointer)
Definition: mcxt.c:1031
char * Pointer
Definition: c.h:302
#define GIN_SEARCH_MODE_INCLUDE_EMPTY
Definition: gin.h:34
#define ERROR
Definition: elog.h:43
signed char GinNullCategory
Definition: ginblock.h:200
Datum FunctionCall7Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2, Datum arg3, Datum arg4, Datum arg5, Datum arg6, Datum arg7)
Definition: fmgr.c:1267
struct GinScanKeyData * GinScanKey
Definition: gin_private.h:258
StrategyNumber sk_strategy
Definition: skey.h:68
char GinTernaryValue
Definition: gin.h:57
OffsetNumber attnum
Definition: gin_private.h:325
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:192
StrategyNumber strategy
Definition: gin_private.h:299
GinScanOpaqueData * GinScanOpaque
Definition: gin_private.h:366
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:132
#define memmove(d, s, c)
Definition: c.h:1100
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:361
void initGinState(GinState *state, Relation index)
Definition: ginutil.c:88
GinTernaryValue * entryRes
Definition: gin_private.h:286
#define RelationGetRelationName(relation)
Definition: rel.h:441
#define pgstat_count_index_scan(rel)
Definition: pgstat.h:1291
unsigned int uint32
Definition: c.h:325
FmgrInfo extractQueryFn[INDEX_MAX_KEYS]
Definition: gin_private.h:75
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
OffsetNumber attnum
Definition: gin_private.h:301
#define SK_ISNULL
Definition: skey.h:115
#define ereport(elevel, rest)
Definition: elog.h:122
struct GinScanEntryData * GinScanEntry
Definition: gin_private.h:260
#define ItemPointerSetMin(p)
Definition: ginblock.h:157
uint32 nuserentries
Definition: gin_private.h:267
#define AllocSetContextCreate(parent, name, allocparams)
Definition: memutils.h:170
TIDBitmap * matchBitmap
Definition: gin_private.h:334
GinScanKey keys
Definition: gin_private.h:354
#define MemoryContextResetAndDeleteChildren(ctx)
Definition: memutils.h:67
MemoryContext tempCtx
Definition: gin_private.h:351
#define GIN_CAT_NULL_KEY
Definition: ginblock.h:203
GinScanEntry * requiredEntries
Definition: gin_private.h:280
void * palloc0(Size size)
Definition: mcxt.c:955
struct GinScanKeyData GinScanKeyData
uintptr_t Datum
Definition: postgres.h:365
void ginGetStats(Relation index, GinStatsData *stats)
Definition: ginutil.c:642
StrategyNumber strategy
Definition: gin_private.h:323
#define GIN_SEARCH_MODE_DEFAULT
Definition: gin.h:33
GinNullCategory * queryCategories
Definition: gin_private.h:297
TBMIterateResult * matchResult
Definition: gin_private.h:336
#define InvalidOffsetNumber
Definition: off.h:26
int16 attnum
Definition: pg_attribute.h:79
void ginNewScanKey(IndexScanDesc scan)
Definition: ginscan.c:262
#define Max(x, y)
Definition: c.h:851
int sk_flags
Definition: skey.h:66
#define Assert(condition)
Definition: c.h:699
GinNullCategory queryCategory
Definition: gin_private.h:320
ScanKey keyData
Definition: relscan.h:95
ItemPointerData curItem
Definition: gin_private.h:310
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1044
int32 ginVersion
Definition: gin.h:48
#define DatumGetPointer(X)
Definition: postgres.h:532
void ginInitConsistentFunction(GinState *ginstate, GinScanKey key)
Definition: ginlogic.c:225
GinScanEntry * entries
Definition: gin_private.h:357
void * palloc(Size size)
Definition: mcxt.c:924
int errmsg(const char *fmt,...)
Definition: elog.c:797
GinScanEntry * additionalEntries
Definition: gin_private.h:282
int i
IndexScanDesc RelationGetIndexScan(Relation indexRelation, int nkeys, int norderbys)
Definition: genam.c:78
#define elog
Definition: elog.h:219
#define GIN_CAT_EMPTY_ITEM
Definition: ginblock.h:204
Datum sk_argument
Definition: skey.h:72
#define UInt16GetDatum(X)
Definition: postgres.h:448
AttrNumber sk_attno
Definition: skey.h:67
void ginFreeScanKeys(GinScanOpaque so)
Definition: ginscan.c:232