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_hitupdesc)
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_hitupdesc = so->giststate->fetchTupdesc;
178 
179  /* Also create a memory context that will hold the returned tuples */
181  "GiST page data context",
183  }
184 
185  /* create new, empty pairing heap for search queue */
186  oldCxt = MemoryContextSwitchTo(so->queueCxt);
188  MemoryContextSwitchTo(oldCxt);
189 
190  so->firstCall = true;
191 
192  /* Update scan key, if a new one is given */
193  if (key && scan->numberOfKeys > 0)
194  {
195  void **fn_extras = NULL;
196 
197  /*
198  * If this isn't the first time through, preserve the fn_extra
199  * pointers, so that if the consistentFns are using them to cache
200  * data, that data is not leaked across a rescan.
201  */
202  if (!first_time)
203  {
204  fn_extras = (void **) palloc(scan->numberOfKeys * sizeof(void *));
205  for (i = 0; i < scan->numberOfKeys; i++)
206  fn_extras[i] = scan->keyData[i].sk_func.fn_extra;
207  }
208 
209  memmove(scan->keyData, key,
210  scan->numberOfKeys * sizeof(ScanKeyData));
211 
212  /*
213  * Modify the scan key so that the Consistent method is called for all
214  * comparisons. The original operator is passed to the Consistent
215  * function in the form of its strategy number, which is available
216  * from the sk_strategy field, and its subtype from the sk_subtype
217  * field.
218  *
219  * Next, if any of keys is a NULL and that key is not marked with
220  * SK_SEARCHNULL/SK_SEARCHNOTNULL then nothing can be found (ie, we
221  * assume all indexable operators are strict).
222  */
223  so->qual_ok = true;
224 
225  for (i = 0; i < scan->numberOfKeys; i++)
226  {
227  ScanKey skey = scan->keyData + i;
228 
229  /*
230  * Copy consistent support function to ScanKey structure instead
231  * of function implementing filtering operator.
232  */
233  fmgr_info_copy(&(skey->sk_func),
234  &(so->giststate->consistentFn[skey->sk_attno - 1]),
235  so->giststate->scanCxt);
236 
237  /* Restore prior fn_extra pointers, if not first time */
238  if (!first_time)
239  skey->sk_func.fn_extra = fn_extras[i];
240 
241  if (skey->sk_flags & SK_ISNULL)
242  {
243  if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
244  so->qual_ok = false;
245  }
246  }
247 
248  if (!first_time)
249  pfree(fn_extras);
250  }
251 
252  /* Update order-by key, if a new one is given */
253  if (orderbys && scan->numberOfOrderBys > 0)
254  {
255  void **fn_extras = NULL;
256 
257  /* As above, preserve fn_extra if not first time through */
258  if (!first_time)
259  {
260  fn_extras = (void **) palloc(scan->numberOfOrderBys * sizeof(void *));
261  for (i = 0; i < scan->numberOfOrderBys; i++)
262  fn_extras[i] = scan->orderByData[i].sk_func.fn_extra;
263  }
264 
265  memmove(scan->orderByData, orderbys,
266  scan->numberOfOrderBys * sizeof(ScanKeyData));
267 
268  so->orderByTypes = (Oid *) palloc(scan->numberOfOrderBys * sizeof(Oid));
269 
270  /*
271  * Modify the order-by key so that the Distance method is called for
272  * all comparisons. The original operator is passed to the Distance
273  * function in the form of its strategy number, which is available
274  * from the sk_strategy field, and its subtype from the sk_subtype
275  * field.
276  */
277  for (i = 0; i < scan->numberOfOrderBys; i++)
278  {
279  ScanKey skey = scan->orderByData + i;
280  FmgrInfo *finfo = &(so->giststate->distanceFn[skey->sk_attno - 1]);
281 
282  /* Check we actually have a distance function ... */
283  if (!OidIsValid(finfo->fn_oid))
284  elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
287 
288  /*
289  * Look up the datatype returned by the original ordering
290  * operator. GiST always uses a float8 for the distance function,
291  * but the ordering operator could be anything else.
292  *
293  * XXX: The distance function is only allowed to be lossy if the
294  * ordering operator's result type is float4 or float8. Otherwise
295  * we don't know how to return the distance to the executor. But
296  * we cannot check that here, as we won't know if the distance
297  * function is lossy until it returns *recheck = true for the
298  * first time.
299  */
301 
302  /*
303  * Copy distance support function to ScanKey structure instead of
304  * function implementing ordering operator.
305  */
306  fmgr_info_copy(&(skey->sk_func), finfo, so->giststate->scanCxt);
307 
308  /* Restore prior fn_extra pointers, if not first time */
309  if (!first_time)
310  skey->sk_func.fn_extra = fn_extras[i];
311  }
312 
313  if (!first_time)
314  pfree(fn_extras);
315  }
316 }
317 
318 void
320 {
321  GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
322 
323  /*
324  * freeGISTstate is enough to clean up everything made by gistbeginscan,
325  * as well as the queueCxt if there is a separate context for it.
326  */
328 }
Definition: fmgr.h:56
#define InvalidXLogRecPtr
Definition: xlogdefs.h:28
OffsetNumber * killedItems
Definition: gist_private.h:164
#define RelationGetNumberOfAttributes(relation)
Definition: rel.h:423
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:131
pairingheap * pairingheap_allocate(pairingheap_comparator compare, void *arg)
Definition: pairingheap.c:42
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:135
unsigned int Oid
Definition: postgres_ext.h:31
MemoryContext pageDataCxt
Definition: gist_private.h:173
#define OidIsValid(objectId)
Definition: c.h:538
TupleDesc xs_hitupdesc
Definition: relscan.h:116
Oid get_func_rettype(Oid funcid)
Definition: lsyscache.c:1459
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:132
void pfree(void *pointer)
Definition: mcxt.c:950
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:165
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
Definition: fmgr.c:524
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:437
#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:497
#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:322
void * palloc0(Size size)
Definition: mcxt.c:878
ScanKey orderByData
Definition: relscan.h:94
uintptr_t Datum
Definition: postgres.h:372
GISTSTATE * initGISTstate(Relation index)
Definition: gist.c:1423
Oid fn_oid
Definition: fmgr.h:59
bool xs_want_itup
Definition: relscan.h:95
int sk_flags
Definition: skey.h:66
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
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:64
TupleDesc CreateTemplateTupleDesc(int natts, bool hasoid)
Definition: tupdesc.c:41
void * palloc(Size size)
Definition: mcxt.c:849
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:319
int numberOfOrderBys
Definition: relscan.h:92
#define elog
Definition: elog.h:219
Oid * rd_opcintype
Definition: rel.h:183
struct IndexScanDescData * IndexScanDesc
Definition: genam.h:86
#define SK_SEARCHNULL
Definition: skey.h:121
AttrNumber sk_attno
Definition: skey.h:67