PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, 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/lsyscache.h"
21 #include "utils/memutils.h"
22 #include "utils/rel.h"
23 
24 
25 /*
26  * Pairing heap comparison function for the GISTSearchItem queue
27  */
28 static int
30 {
31  const GISTSearchItem *sa = (const GISTSearchItem *) a;
32  const GISTSearchItem *sb = (const GISTSearchItem *) b;
33  IndexScanDesc scan = (IndexScanDesc) arg;
34  int i;
35 
36  /* Order according to distance comparison */
37  for (i = 0; i < scan->numberOfOrderBys; i++)
38  {
39  if (sa->distances[i] != sb->distances[i])
40  return (sa->distances[i] < sb->distances[i]) ? 1 : -1;
41  }
42 
43  /* Heap items go before inner pages, to ensure a depth-first search */
45  return 1;
47  return -1;
48 
49  return 0;
50 }
51 
52 
53 /*
54  * Index AM API functions for scanning GiST indexes
55  */
56 
58 gistbeginscan(Relation r, int nkeys, int norderbys)
59 {
60  IndexScanDesc scan;
61  GISTSTATE *giststate;
62  GISTScanOpaque so;
63  MemoryContext oldCxt;
64 
65  scan = RelationGetIndexScan(r, nkeys, norderbys);
66 
67  /* First, set up a GISTSTATE with a scan-lifespan memory context */
68  giststate = initGISTstate(scan->indexRelation);
69 
70  /*
71  * Everything made below is in the scanCxt, or is a child of the scanCxt,
72  * so it'll all go away automatically in gistendscan.
73  */
74  oldCxt = MemoryContextSwitchTo(giststate->scanCxt);
75 
76  /* initialize opaque data */
78  so->giststate = giststate;
79  giststate->tempCxt = createTempGistContext();
80  so->queue = NULL;
81  so->queueCxt = giststate->scanCxt; /* see gistrescan */
82 
83  /* workspaces with size dependent on numberOfOrderBys: */
84  so->distances = palloc(sizeof(double) * scan->numberOfOrderBys);
85  so->qual_ok = true; /* in case there are zero keys */
86  if (scan->numberOfOrderBys > 0)
87  {
88  scan->xs_orderbyvals = palloc0(sizeof(Datum) * scan->numberOfOrderBys);
89  scan->xs_orderbynulls = palloc(sizeof(bool) * scan->numberOfOrderBys);
90  memset(scan->xs_orderbynulls, true, sizeof(bool) * scan->numberOfOrderBys);
91  }
92 
93  so->killedItems = NULL; /* until needed */
94  so->numKilled = 0;
97 
98  scan->opaque = so;
99 
100  /*
101  * All fields required for index-only scans are initialized in gistrescan,
102  * as we don't know yet if we're doing an index-only scan or not.
103  */
104 
105  MemoryContextSwitchTo(oldCxt);
106 
107  return scan;
108 }
109 
110 void
111 gistrescan(IndexScanDesc scan, ScanKey key, int nkeys,
112  ScanKey orderbys, int norderbys)
113 {
114  /* nkeys and norderbys arguments are ignored */
115  GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
116  bool first_time;
117  int i;
118  MemoryContext oldCxt;
119 
120  /* rescan an existing indexscan --- reset state */
121 
122  /*
123  * The first time through, we create the search queue in the scanCxt.
124  * Subsequent times through, we create the queue in a separate queueCxt,
125  * which is created on the second call and reset on later calls. Thus, in
126  * the common case where a scan is only rescan'd once, we just put the
127  * queue in scanCxt and don't pay the overhead of making a second memory
128  * context. If we do rescan more than once, the first queue is just left
129  * for dead until end of scan; this small wastage seems worth the savings
130  * in the common case.
131  */
132  if (so->queue == NULL)
133  {
134  /* first time through */
135  Assert(so->queueCxt == so->giststate->scanCxt);
136  first_time = true;
137  }
138  else if (so->queueCxt == so->giststate->scanCxt)
139  {
140  /* second time through */
142  "GiST queue context",
144  first_time = false;
145  }
146  else
147  {
148  /* third or later time through */
150  first_time = false;
151  }
152 
153  /*
154  * If we're doing an index-only scan, on the first call, also initialize a
155  * tuple descriptor to represent the returned index tuples and create a
156  * memory context to hold them during the scan.
157  */
158  if (scan->xs_want_itup && !scan->xs_itupdesc)
159  {
160  int natts;
161  int attno;
162 
163  /*
164  * The storage type of the index can be different from the original
165  * datatype being indexed, so we cannot just grab the index's tuple
166  * descriptor. Instead, construct a descriptor with the original data
167  * types.
168  */
170  so->giststate->fetchTupdesc = CreateTemplateTupleDesc(natts, false);
171  for (attno = 1; attno <= natts; attno++)
172  {
174  scan->indexRelation->rd_opcintype[attno - 1],
175  -1, 0);
176  }
177  scan->xs_itupdesc = so->giststate->fetchTupdesc;
178 
180  "GiST page data context",
182  }
183 
184  /* create new, empty pairing heap for search queue */
185  oldCxt = MemoryContextSwitchTo(so->queueCxt);
187  MemoryContextSwitchTo(oldCxt);
188 
189  so->firstCall = true;
190 
191  /* Update scan key, if a new one is given */
192  if (key && scan->numberOfKeys > 0)
193  {
194  void **fn_extras = NULL;
195 
196  /*
197  * If this isn't the first time through, preserve the fn_extra
198  * pointers, so that if the consistentFns are using them to cache
199  * data, that data is not leaked across a rescan.
200  */
201  if (!first_time)
202  {
203  fn_extras = (void **) palloc(scan->numberOfKeys * sizeof(void *));
204  for (i = 0; i < scan->numberOfKeys; i++)
205  fn_extras[i] = scan->keyData[i].sk_func.fn_extra;
206  }
207 
208  memmove(scan->keyData, key,
209  scan->numberOfKeys * sizeof(ScanKeyData));
210 
211  /*
212  * Modify the scan key so that the Consistent method is called for all
213  * comparisons. The original operator is passed to the Consistent
214  * function in the form of its strategy number, which is available
215  * from the sk_strategy field, and its subtype from the sk_subtype
216  * field.
217  *
218  * Next, if any of keys is a NULL and that key is not marked with
219  * SK_SEARCHNULL/SK_SEARCHNOTNULL then nothing can be found (ie, we
220  * assume all indexable operators are strict).
221  */
222  so->qual_ok = true;
223 
224  for (i = 0; i < scan->numberOfKeys; i++)
225  {
226  ScanKey skey = scan->keyData + i;
227 
228  /*
229  * Copy consistent support function to ScanKey structure instead
230  * of function implementing filtering operator.
231  */
232  fmgr_info_copy(&(skey->sk_func),
233  &(so->giststate->consistentFn[skey->sk_attno - 1]),
234  so->giststate->scanCxt);
235 
236  /* Restore prior fn_extra pointers, if not first time */
237  if (!first_time)
238  skey->sk_func.fn_extra = fn_extras[i];
239 
240  if (skey->sk_flags & SK_ISNULL)
241  {
242  if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
243  so->qual_ok = false;
244  }
245  }
246 
247  if (!first_time)
248  pfree(fn_extras);
249  }
250 
251  /* Update order-by key, if a new one is given */
252  if (orderbys && scan->numberOfOrderBys > 0)
253  {
254  void **fn_extras = NULL;
255 
256  /* As above, preserve fn_extra if not first time through */
257  if (!first_time)
258  {
259  fn_extras = (void **) palloc(scan->numberOfOrderBys * sizeof(void *));
260  for (i = 0; i < scan->numberOfOrderBys; i++)
261  fn_extras[i] = scan->orderByData[i].sk_func.fn_extra;
262  }
263 
264  memmove(scan->orderByData, orderbys,
265  scan->numberOfOrderBys * sizeof(ScanKeyData));
266 
267  so->orderByTypes = (Oid *) palloc(scan->numberOfOrderBys * sizeof(Oid));
268 
269  /*
270  * Modify the order-by key so that the Distance method is called for
271  * all comparisons. The original operator is passed to the Distance
272  * function in the form of its strategy number, which is available
273  * from the sk_strategy field, and its subtype from the sk_subtype
274  * field.
275  */
276  for (i = 0; i < scan->numberOfOrderBys; i++)
277  {
278  ScanKey skey = scan->orderByData + i;
279  FmgrInfo *finfo = &(so->giststate->distanceFn[skey->sk_attno - 1]);
280 
281  /* Check we actually have a distance function ... */
282  if (!OidIsValid(finfo->fn_oid))
283  elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
286 
287  /*
288  * Look up the datatype returned by the original ordering
289  * operator. GiST always uses a float8 for the distance function,
290  * but the ordering operator could be anything else.
291  *
292  * XXX: The distance function is only allowed to be lossy if the
293  * ordering operator's result type is float4 or float8. Otherwise
294  * we don't know how to return the distance to the executor. But
295  * we cannot check that here, as we won't know if the distance
296  * function is lossy until it returns *recheck = true for the
297  * first time.
298  */
300 
301  /*
302  * Copy distance support function to ScanKey structure instead of
303  * function implementing ordering operator.
304  */
305  fmgr_info_copy(&(skey->sk_func), finfo, so->giststate->scanCxt);
306 
307  /* Restore prior fn_extra pointers, if not first time */
308  if (!first_time)
309  skey->sk_func.fn_extra = fn_extras[i];
310  }
311 
312  if (!first_time)
313  pfree(fn_extras);
314  }
315 }
316 
317 void
319 {
320  GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
321 
322  /*
323  * freeGISTstate is enough to clean up everything made by gistbeginscan,
324  * as well as the queueCxt if there is a separate context for it.
325  */
327 }
Definition: fmgr.h:53
#define InvalidXLogRecPtr
Definition: xlogdefs.h:28
OffsetNumber * killedItems
Definition: gist_private.h:164
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:419
static int pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
Definition: gistscan.c:29
MemoryContext createTempGistContext(void)
Definition: gist.c:110
pairingheap * queue
Definition: gist_private.h:155
MemoryContext queueCxt
Definition: gist_private.h:156
BlockNumber curBlkno
Definition: gist_private.h:166
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Datum * xs_orderbyvals
Definition: relscan.h:124
pairingheap * pairingheap_allocate(pairingheap_comparator compare, void *arg)
Definition: pairingheap.c:42
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:135
TupleDesc xs_itupdesc
Definition: relscan.h:109
unsigned int Oid
Definition: postgres_ext.h:31
MemoryContext pageDataCxt
Definition: gist_private.h:173
#define OidIsValid(objectId)
Definition: c.h:534
Oid get_func_rettype(Oid funcid)
Definition: lsyscache.c:1427
Relation indexRelation
Definition: relscan.h:89
GISTSTATE * giststate
Definition: gist_private.h:152
double distances[FLEXIBLE_ARRAY_MEMBER]
Definition: gist_private.h:139
bool * xs_orderbynulls
Definition: relscan.h:125
void pfree(void *pointer)
Definition: mcxt.c:992
FmgrInfo consistentFn[INDEX_MAX_KEYS]
Definition: gist_private.h:85
#define ERROR
Definition: elog.h:43
GISTScanOpaqueData * GISTScanOpaque
Definition: gist_private.h:177
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:145
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
Definition: fmgr.c:583
MemoryContext tempCxt
Definition: gist_private.h:79
void gistrescan(IndexScanDesc scan, ScanKey key, int nkeys, ScanKey orderbys, int norderbys)
Definition: gistscan.c:111
#define memmove(d, s, c)
Definition: c.h:1058
FmgrInfo sk_func
Definition: skey.h:71
#define RelationGetRelationName(relation)
Definition: rel.h:433
#define SK_SEARCHNOTNULL
Definition: skey.h:122
#define GISTSearchItemIsHeap(item)
Definition: gist_private.h:143
void TupleDescInitEntry(TupleDesc desc, AttrNumber attributeNumber, const char *attributeName, Oid oidtypeid, int32 typmod, int attdim)
Definition: tupdesc.c:493
#define SK_ISNULL
Definition: skey.h:115
void freeGISTstate(GISTSTATE *giststate)
Definition: gist.c:1510
MemoryContext AllocSetContextCreate(MemoryContext parent, const char *name, Size minContextSize, Size initBlockSize, Size maxBlockSize)
Definition: aset.c:440
void * palloc0(Size size)
Definition: mcxt.c:920
ScanKey orderByData
Definition: relscan.h:94
uintptr_t Datum
Definition: postgres.h:374
GISTSTATE * initGISTstate(Relation index)
Definition: gist.c:1423
Oid fn_oid
Definition: fmgr.h:56
bool xs_want_itup
Definition: relscan.h:95
int sk_flags
Definition: skey.h:66
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
TupleDesc fetchTupdesc
Definition: gist_private.h:82
#define InvalidBlockNumber
Definition: block.h:33
#define GIST_DISTANCE_PROC
Definition: gist.h:35
ScanKey keyData
Definition: relscan.h:93
FmgrInfo distanceFn[INDEX_MAX_KEYS]
Definition: gist_private.h:92
void * fn_extra
Definition: fmgr.h:61
TupleDesc CreateTemplateTupleDesc(int natts, bool hasoid)
Definition: tupdesc.c:41
void * palloc(Size size)
Definition: mcxt.c:891
int i
MemoryContext scanCxt
Definition: gist_private.h:78
void * arg
IndexScanDesc RelationGetIndexScan(Relation indexRelation, int nkeys, int norderbys)
Definition: genam.c:78
IndexScanDesc gistbeginscan(Relation r, int nkeys, int norderbys)
Definition: gistscan.c:58
void gistendscan(IndexScanDesc scan)
Definition: gistscan.c:318
int numberOfOrderBys
Definition: relscan.h:92
#define elog
Definition: elog.h:219
Oid * rd_opcintype
Definition: rel.h:179
struct IndexScanDescData * IndexScanDesc
Definition: genam.h:86
#define SK_SEARCHNULL
Definition: skey.h:121
AttrNumber sk_attno
Definition: skey.h:67