PostgreSQL Source Code  git master
gistscan.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * gistscan.c
4  * routines to manage scans on GiST index relations
5  *
6  *
7  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
8  * Portions Copyright (c) 1994, Regents of the University of California
9  *
10  * IDENTIFICATION
11  * src/backend/access/gist/gistscan.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 #include "postgres.h"
16 
17 #include "access/gist_private.h"
18 #include "access/gistscan.h"
19 #include "access/relscan.h"
20 #include "utils/float.h"
21 #include "utils/lsyscache.h"
22 #include "utils/memutils.h"
23 #include "utils/rel.h"
24 
25 
26 /*
27  * Pairing heap comparison function for the GISTSearchItem queue
28  */
29 static int
31 {
32  const GISTSearchItem *sa = (const GISTSearchItem *) a;
33  const GISTSearchItem *sb = (const GISTSearchItem *) b;
34  IndexScanDesc scan = (IndexScanDesc) arg;
35  int i;
36 
37  /* Order according to distance comparison */
38  for (i = 0; i < scan->numberOfOrderBys; i++)
39  {
40  if (sa->distances[i].isnull)
41  {
42  if (!sb->distances[i].isnull)
43  return -1;
44  }
45  else if (sb->distances[i].isnull)
46  {
47  return 1;
48  }
49  else
50  {
51  int cmp = -float8_cmp_internal(sa->distances[i].value,
52  sb->distances[i].value);
53 
54  if (cmp != 0)
55  return cmp;
56  }
57  }
58 
59  /* Heap items go before inner pages, to ensure a depth-first search */
61  return 1;
63  return -1;
64 
65  return 0;
66 }
67 
68 
69 /*
70  * Index AM API functions for scanning GiST indexes
71  */
72 
74 gistbeginscan(Relation r, int nkeys, int norderbys)
75 {
76  IndexScanDesc scan;
77  GISTSTATE *giststate;
78  GISTScanOpaque so;
79  MemoryContext oldCxt;
80 
81  scan = RelationGetIndexScan(r, nkeys, norderbys);
82 
83  /* First, set up a GISTSTATE with a scan-lifespan memory context */
84  giststate = initGISTstate(scan->indexRelation);
85 
86  /*
87  * Everything made below is in the scanCxt, or is a child of the scanCxt,
88  * so it'll all go away automatically in gistendscan.
89  */
90  oldCxt = MemoryContextSwitchTo(giststate->scanCxt);
91 
92  /* initialize opaque data */
94  so->giststate = giststate;
95  giststate->tempCxt = createTempGistContext();
96  so->queue = NULL;
97  so->queueCxt = giststate->scanCxt; /* see gistrescan */
98 
99  /* workspaces with size dependent on numberOfOrderBys: */
100  so->distances = palloc(sizeof(so->distances[0]) * scan->numberOfOrderBys);
101  so->qual_ok = true; /* in case there are zero keys */
102  if (scan->numberOfOrderBys > 0)
103  {
104  scan->xs_orderbyvals = palloc0(sizeof(Datum) * scan->numberOfOrderBys);
105  scan->xs_orderbynulls = palloc(sizeof(bool) * scan->numberOfOrderBys);
106  memset(scan->xs_orderbynulls, true, sizeof(bool) * scan->numberOfOrderBys);
107  }
108 
109  so->killedItems = NULL; /* until needed */
110  so->numKilled = 0;
113 
114  scan->opaque = so;
115 
116  /*
117  * All fields required for index-only scans are initialized in gistrescan,
118  * as we don't know yet if we're doing an index-only scan or not.
119  */
120 
121  MemoryContextSwitchTo(oldCxt);
122 
123  return scan;
124 }
125 
126 void
128  ScanKey orderbys, int norderbys)
129 {
130  /* nkeys and norderbys arguments are ignored */
131  GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
132  bool first_time;
133  int i;
134  MemoryContext oldCxt;
135 
136  /* rescan an existing indexscan --- reset state */
137 
138  /*
139  * The first time through, we create the search queue in the scanCxt.
140  * Subsequent times through, we create the queue in a separate queueCxt,
141  * which is created on the second call and reset on later calls. Thus, in
142  * the common case where a scan is only rescan'd once, we just put the
143  * queue in scanCxt and don't pay the overhead of making a second memory
144  * context. If we do rescan more than once, the first queue is just left
145  * for dead until end of scan; this small wastage seems worth the savings
146  * in the common case.
147  */
148  if (so->queue == NULL)
149  {
150  /* first time through */
151  Assert(so->queueCxt == so->giststate->scanCxt);
152  first_time = true;
153  }
154  else if (so->queueCxt == so->giststate->scanCxt)
155  {
156  /* second time through */
158  "GiST queue context",
160  first_time = false;
161  }
162  else
163  {
164  /* third or later time through */
166  first_time = false;
167  }
168 
169  /*
170  * If we're doing an index-only scan, on the first call, also initialize a
171  * tuple descriptor to represent the returned index tuples and create a
172  * memory context to hold them during the scan.
173  */
174  if (scan->xs_want_itup && !scan->xs_hitupdesc)
175  {
176  int natts;
177  int nkeyatts;
178  int attno;
179 
180  /*
181  * The storage type of the index can be different from the original
182  * datatype being indexed, so we cannot just grab the index's tuple
183  * descriptor. Instead, construct a descriptor with the original data
184  * types.
185  */
189  for (attno = 1; attno <= nkeyatts; attno++)
190  {
191  TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
192  scan->indexRelation->rd_opcintype[attno - 1],
193  -1, 0);
194  }
195 
196  for (; attno <= natts; attno++)
197  {
198  /* taking opcintype from giststate->tupdesc */
199  TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
201  attno - 1)->atttypid,
202  -1, 0);
203  }
204  scan->xs_hitupdesc = so->giststate->fetchTupdesc;
205 
206  /* Also create a memory context that will hold the returned tuples */
208  "GiST page data context",
210  }
211 
212  /* create new, empty pairing heap for search queue */
213  oldCxt = MemoryContextSwitchTo(so->queueCxt);
215  MemoryContextSwitchTo(oldCxt);
216 
217  so->firstCall = true;
218 
219  /* Update scan key, if a new one is given */
220  if (key && scan->numberOfKeys > 0)
221  {
222  void **fn_extras = NULL;
223 
224  /*
225  * If this isn't the first time through, preserve the fn_extra
226  * pointers, so that if the consistentFns are using them to cache
227  * data, that data is not leaked across a rescan.
228  */
229  if (!first_time)
230  {
231  fn_extras = (void **) palloc(scan->numberOfKeys * sizeof(void *));
232  for (i = 0; i < scan->numberOfKeys; i++)
233  fn_extras[i] = scan->keyData[i].sk_func.fn_extra;
234  }
235 
236  memmove(scan->keyData, key,
237  scan->numberOfKeys * sizeof(ScanKeyData));
238 
239  /*
240  * Modify the scan key so that the Consistent method is called for all
241  * comparisons. The original operator is passed to the Consistent
242  * function in the form of its strategy number, which is available
243  * from the sk_strategy field, and its subtype from the sk_subtype
244  * field.
245  *
246  * Next, if any of keys is a NULL and that key is not marked with
247  * SK_SEARCHNULL/SK_SEARCHNOTNULL then nothing can be found (ie, we
248  * assume all indexable operators are strict).
249  */
250  so->qual_ok = true;
251 
252  for (i = 0; i < scan->numberOfKeys; i++)
253  {
254  ScanKey skey = scan->keyData + i;
255 
256  /*
257  * Copy consistent support function to ScanKey structure instead
258  * of function implementing filtering operator.
259  */
260  fmgr_info_copy(&(skey->sk_func),
261  &(so->giststate->consistentFn[skey->sk_attno - 1]),
262  so->giststate->scanCxt);
263 
264  /* Restore prior fn_extra pointers, if not first time */
265  if (!first_time)
266  skey->sk_func.fn_extra = fn_extras[i];
267 
268  if (skey->sk_flags & SK_ISNULL)
269  {
270  if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
271  so->qual_ok = false;
272  }
273  }
274 
275  if (!first_time)
276  pfree(fn_extras);
277  }
278 
279  /* Update order-by key, if a new one is given */
280  if (orderbys && scan->numberOfOrderBys > 0)
281  {
282  void **fn_extras = NULL;
283 
284  /* As above, preserve fn_extra if not first time through */
285  if (!first_time)
286  {
287  fn_extras = (void **) palloc(scan->numberOfOrderBys * sizeof(void *));
288  for (i = 0; i < scan->numberOfOrderBys; i++)
289  fn_extras[i] = scan->orderByData[i].sk_func.fn_extra;
290  }
291 
292  memmove(scan->orderByData, orderbys,
293  scan->numberOfOrderBys * sizeof(ScanKeyData));
294 
295  so->orderByTypes = (Oid *) palloc(scan->numberOfOrderBys * sizeof(Oid));
296 
297  /*
298  * Modify the order-by key so that the Distance method is called for
299  * all comparisons. The original operator is passed to the Distance
300  * function in the form of its strategy number, which is available
301  * from the sk_strategy field, and its subtype from the sk_subtype
302  * field.
303  */
304  for (i = 0; i < scan->numberOfOrderBys; i++)
305  {
306  ScanKey skey = scan->orderByData + i;
307  FmgrInfo *finfo = &(so->giststate->distanceFn[skey->sk_attno - 1]);
308 
309  /* Check we actually have a distance function ... */
310  if (!OidIsValid(finfo->fn_oid))
311  elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
314 
315  /*
316  * Look up the datatype returned by the original ordering
317  * operator. GiST always uses a float8 for the distance function,
318  * but the ordering operator could be anything else.
319  *
320  * XXX: The distance function is only allowed to be lossy if the
321  * ordering operator's result type is float4 or float8. Otherwise
322  * we don't know how to return the distance to the executor. But
323  * we cannot check that here, as we won't know if the distance
324  * function is lossy until it returns *recheck = true for the
325  * first time.
326  */
328 
329  /*
330  * Copy distance support function to ScanKey structure instead of
331  * function implementing ordering operator.
332  */
333  fmgr_info_copy(&(skey->sk_func), finfo, so->giststate->scanCxt);
334 
335  /* Restore prior fn_extra pointers, if not first time */
336  if (!first_time)
337  skey->sk_func.fn_extra = fn_extras[i];
338  }
339 
340  if (!first_time)
341  pfree(fn_extras);
342  }
343 
344  /* any previous xs_hitup will have been pfree'd in context resets above */
345  scan->xs_hitup = NULL;
346 }
347 
348 void
350 {
351  GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
352 
353  /*
354  * freeGISTstate is enough to clean up everything made by gistbeginscan,
355  * as well as the queueCxt if there is a separate context for it.
356  */
358 }
Definition: fmgr.h:56
#define InvalidXLogRecPtr
Definition: xlogdefs.h:28
IndexOrderByDistance * distances
Definition: gist_private.h:165
#define AllocSetContextCreate
Definition: memutils.h:170
IndexOrderByDistance distances[FLEXIBLE_ARRAY_MEMBER]
Definition: gist_private.h:142
OffsetNumber * killedItems
Definition: gist_private.h:168
struct ScanKeyData * orderByData
Definition: relscan.h:108
TupleDesc CreateTemplateTupleDesc(int natts)
Definition: tupdesc.c:44
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:425
static int pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
Definition: gistscan.c:30
MemoryContext createTempGistContext(void)
Definition: gist.c:114
pairingheap * queue
Definition: gist_private.h:159
#define TupleDescAttr(tupdesc, i)
Definition: tupdesc.h:92
struct TupleDescData * xs_hitupdesc
Definition: relscan.h:130
MemoryContext queueCxt
Definition: gist_private.h:160
BlockNumber curBlkno
Definition: gist_private.h:170
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum * xs_orderbyvals
Definition: relscan.h:146
pairingheap * pairingheap_allocate(pairingheap_comparator compare, void *arg)
Definition: pairingheap.c:42
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:136
unsigned int Oid
Definition: postgres_ext.h:31
MemoryContext pageDataCxt
Definition: gist_private.h:177
#define OidIsValid(objectId)
Definition: c.h:638
int float8_cmp_internal(float8 a, float8 b)
Definition: float.c:919
Oid get_func_rettype(Oid funcid)
Definition: lsyscache.c:1457
Relation indexRelation
Definition: relscan.h:103
GISTSTATE * giststate
Definition: gist_private.h:156
bool * xs_orderbynulls
Definition: relscan.h:147
void pfree(void *pointer)
Definition: mcxt.c:1056
FmgrInfo consistentFn[INDEX_MAX_KEYS]
Definition: gist_private.h:86
#define ERROR
Definition: elog.h:43
GISTScanOpaqueData * GISTScanOpaque
Definition: gist_private.h:181
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:192
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
Definition: fmgr.c:610
MemoryContext tempCxt
Definition: gist_private.h:78
void gistrescan(IndexScanDesc scan, ScanKey key, int nkeys, ScanKey orderbys, int norderbys)
Definition: gistscan.c:127
#define memmove(d, s, c)
Definition: c.h:1238
FmgrInfo sk_func
Definition: skey.h:71
#define RelationGetRelationName(relation)
Definition: rel.h:453
#define SK_SEARCHNOTNULL
Definition: skey.h:122
#define GISTSearchItemIsHeap(item)
Definition: gist_private.h:145
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:438
void TupleDescInitEntry(TupleDesc desc, AttrNumber attributeNumber, const char *attributeName, Oid oidtypeid, int32 typmod, int attdim)
Definition: tupdesc.c:603
#define SK_ISNULL
Definition: skey.h:115
void freeGISTstate(GISTSTATE *giststate)
Definition: gist.c:1614
TupleDesc leafTupdesc
Definition: gist_private.h:80
void * palloc0(Size size)
Definition: mcxt.c:980
uintptr_t Datum
Definition: postgres.h:367
GISTSTATE * initGISTstate(Relation index)
Definition: gist.c:1486
Oid fn_oid
Definition: fmgr.h:59
int sk_flags
Definition: skey.h:66
#define Assert(condition)
Definition: c.h:732
TupleDesc fetchTupdesc
Definition: gist_private.h:83
#define InvalidBlockNumber
Definition: block.h:33
#define GIST_DISTANCE_PROC
Definition: gist.h:36
FmgrInfo distanceFn[INDEX_MAX_KEYS]
Definition: gist_private.h:93
void * fn_extra
Definition: fmgr.h:64
struct ScanKeyData * keyData
Definition: relscan.h:107
void * palloc(Size size)
Definition: mcxt.c:949
HeapTuple xs_hitup
Definition: relscan.h:129
#define elog(elevel,...)
Definition: elog.h:226
int i
MemoryContext scanCxt
Definition: gist_private.h:77
void * arg
IndexScanDesc RelationGetIndexScan(Relation indexRelation, int nkeys, int norderbys)
Definition: genam.c:80
IndexScanDesc gistbeginscan(Relation r, int nkeys, int norderbys)
Definition: gistscan.c:74
void gistendscan(IndexScanDesc scan)
Definition: gistscan.c:349
int numberOfOrderBys
Definition: relscan.h:106
Oid * rd_opcintype
Definition: rel.h:159
struct IndexScanDescData * IndexScanDesc
Definition: genam.h:87
#define SK_SEARCHNULL
Definition: skey.h:121
AttrNumber sk_attno
Definition: skey.h:67
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742