1 /*-------------------------------------------------------------------------
2 *
3 * gistscan.c
4 * routines to manage scans on GiST index relations
5 *
6 *
7 * Portions Copyright (c) 1996-2016, 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/builtins.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
pairingheap_GISTSearchItem_cmp(const pairingheap_node * a,const pairingheap_node * b,void * arg)30 pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
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 */
60 if (GISTSearchItemIsHeap(*sa) && !GISTSearchItemIsHeap(*sb))
61 return 1;
62 if (!GISTSearchItemIsHeap(*sa) && GISTSearchItemIsHeap(*sb))
63 return -1;
64
65 return 0;
66 }
67
68
69 /*
70 * Index AM API functions for scanning GiST indexes
71 */
72
73 IndexScanDesc
gistbeginscan(Relation r,int nkeys,int norderbys)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 */
93 so = (GISTScanOpaque) palloc0(sizeof(GISTScanOpaqueData));
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;
111 so->curBlkno = InvalidBlockNumber;
112 so->curPageLSN = InvalidXLogRecPtr;
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
gistrescan(IndexScanDesc scan,ScanKey key,int nkeys,ScanKey orderbys,int norderbys)127 gistrescan(IndexScanDesc scan, ScanKey key, int nkeys,
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 */
157 so->queueCxt = AllocSetContextCreate(so->giststate->scanCxt,
158 "GiST queue context",
159 ALLOCSET_DEFAULT_SIZES);
160 first_time = false;
161 }
162 else
163 {
164 /* third or later time through */
165 MemoryContextReset(so->queueCxt);
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_itupdesc)
175 {
176 int natts;
177 int attno;
178
179 /*
180 * The storage type of the index can be different from the original
181 * datatype being indexed, so we cannot just grab the index's tuple
182 * descriptor. Instead, construct a descriptor with the original data
183 * types.
184 */
185 natts = RelationGetNumberOfAttributes(scan->indexRelation);
186 so->giststate->fetchTupdesc = CreateTemplateTupleDesc(natts, false);
187 for (attno = 1; attno <= natts; attno++)
188 {
189 TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
190 scan->indexRelation->rd_opcintype[attno - 1],
191 -1, 0);
192 }
193 scan->xs_itupdesc = so->giststate->fetchTupdesc;
194
195 so->pageDataCxt = AllocSetContextCreate(so->giststate->scanCxt,
196 "GiST page data context",
197 ALLOCSET_DEFAULT_SIZES);
198 }
199
200 /* create new, empty pairing heap for search queue */
201 oldCxt = MemoryContextSwitchTo(so->queueCxt);
202 so->queue = pairingheap_allocate(pairingheap_GISTSearchItem_cmp, scan);
203 MemoryContextSwitchTo(oldCxt);
204
205 so->firstCall = true;
206
207 /* Update scan key, if a new one is given */
208 if (key && scan->numberOfKeys > 0)
209 {
210 void **fn_extras = NULL;
211
212 /*
213 * If this isn't the first time through, preserve the fn_extra
214 * pointers, so that if the consistentFns are using them to cache
215 * data, that data is not leaked across a rescan.
216 */
217 if (!first_time)
218 {
219 fn_extras = (void **) palloc(scan->numberOfKeys * sizeof(void *));
220 for (i = 0; i < scan->numberOfKeys; i++)
221 fn_extras[i] = scan->keyData[i].sk_func.fn_extra;
222 }
223
224 memmove(scan->keyData, key,
225 scan->numberOfKeys * sizeof(ScanKeyData));
226
227 /*
228 * Modify the scan key so that the Consistent method is called for all
229 * comparisons. The original operator is passed to the Consistent
230 * function in the form of its strategy number, which is available
231 * from the sk_strategy field, and its subtype from the sk_subtype
232 * field.
233 *
234 * Next, if any of keys is a NULL and that key is not marked with
235 * SK_SEARCHNULL/SK_SEARCHNOTNULL then nothing can be found (ie, we
236 * assume all indexable operators are strict).
237 */
238 so->qual_ok = true;
239
240 for (i = 0; i < scan->numberOfKeys; i++)
241 {
242 ScanKey skey = scan->keyData + i;
243
244 /*
245 * Copy consistent support function to ScanKey structure instead
246 * of function implementing filtering operator.
247 */
248 fmgr_info_copy(&(skey->sk_func),
249 &(so->giststate->consistentFn[skey->sk_attno - 1]),
250 so->giststate->scanCxt);
251
252 /* Restore prior fn_extra pointers, if not first time */
253 if (!first_time)
254 skey->sk_func.fn_extra = fn_extras[i];
255
256 if (skey->sk_flags & SK_ISNULL)
257 {
258 if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
259 so->qual_ok = false;
260 }
261 }
262
263 if (!first_time)
264 pfree(fn_extras);
265 }
266
267 /* Update order-by key, if a new one is given */
268 if (orderbys && scan->numberOfOrderBys > 0)
269 {
270 void **fn_extras = NULL;
271
272 /* As above, preserve fn_extra if not first time through */
273 if (!first_time)
274 {
275 fn_extras = (void **) palloc(scan->numberOfOrderBys * sizeof(void *));
276 for (i = 0; i < scan->numberOfOrderBys; i++)
277 fn_extras[i] = scan->orderByData[i].sk_func.fn_extra;
278 }
279
280 memmove(scan->orderByData, orderbys,
281 scan->numberOfOrderBys * sizeof(ScanKeyData));
282
283 so->orderByTypes = (Oid *) palloc(scan->numberOfOrderBys * sizeof(Oid));
284
285 /*
286 * Modify the order-by key so that the Distance method is called for
287 * all comparisons. The original operator is passed to the Distance
288 * function in the form of its strategy number, which is available
289 * from the sk_strategy field, and its subtype from the sk_subtype
290 * field.
291 */
292 for (i = 0; i < scan->numberOfOrderBys; i++)
293 {
294 ScanKey skey = scan->orderByData + i;
295 FmgrInfo *finfo = &(so->giststate->distanceFn[skey->sk_attno - 1]);
296
297 /* Check we actually have a distance function ... */
298 if (!OidIsValid(finfo->fn_oid))
299 elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
300 GIST_DISTANCE_PROC, skey->sk_attno,
301 RelationGetRelationName(scan->indexRelation));
302
303 /*
304 * Look up the datatype returned by the original ordering
305 * operator. GiST always uses a float8 for the distance function,
306 * but the ordering operator could be anything else.
307 *
308 * XXX: The distance function is only allowed to be lossy if the
309 * ordering operator's result type is float4 or float8. Otherwise
310 * we don't know how to return the distance to the executor. But
311 * we cannot check that here, as we won't know if the distance
312 * function is lossy until it returns *recheck = true for the
313 * first time.
314 */
315 so->orderByTypes[i] = get_func_rettype(skey->sk_func.fn_oid);
316
317 /*
318 * Copy distance support function to ScanKey structure instead of
319 * function implementing ordering operator.
320 */
321 fmgr_info_copy(&(skey->sk_func), finfo, so->giststate->scanCxt);
322
323 /* Restore prior fn_extra pointers, if not first time */
324 if (!first_time)
325 skey->sk_func.fn_extra = fn_extras[i];
326 }
327
328 if (!first_time)
329 pfree(fn_extras);
330 }
331
332 /* any previous xs_itup will have been pfree'd in context resets above */
333 scan->xs_itup = NULL;
334 }
335
336 void
gistendscan(IndexScanDesc scan)337 gistendscan(IndexScanDesc scan)
338 {
339 GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
340
341 /*
342 * freeGISTstate is enough to clean up everything made by gistbeginscan,
343 * as well as the queueCxt if there is a separate context for it.
344 */
345 freeGISTstate(so->giststate);
346 }
347