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/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_hitupdesc)
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_hitupdesc = so->giststate->fetchTupdesc;
194
195 /* Also create a memory context that will hold the returned tuples */
196 so->pageDataCxt = AllocSetContextCreate(so->giststate->scanCxt,
197 "GiST page data context",
198 ALLOCSET_DEFAULT_SIZES);
199 }
200
201 /* create new, empty pairing heap for search queue */
202 oldCxt = MemoryContextSwitchTo(so->queueCxt);
203 so->queue = pairingheap_allocate(pairingheap_GISTSearchItem_cmp, scan);
204 MemoryContextSwitchTo(oldCxt);
205
206 so->firstCall = true;
207
208 /* Update scan key, if a new one is given */
209 if (key && scan->numberOfKeys > 0)
210 {
211 void **fn_extras = NULL;
212
213 /*
214 * If this isn't the first time through, preserve the fn_extra
215 * pointers, so that if the consistentFns are using them to cache
216 * data, that data is not leaked across a rescan.
217 */
218 if (!first_time)
219 {
220 fn_extras = (void **) palloc(scan->numberOfKeys * sizeof(void *));
221 for (i = 0; i < scan->numberOfKeys; i++)
222 fn_extras[i] = scan->keyData[i].sk_func.fn_extra;
223 }
224
225 memmove(scan->keyData, key,
226 scan->numberOfKeys * sizeof(ScanKeyData));
227
228 /*
229 * Modify the scan key so that the Consistent method is called for all
230 * comparisons. The original operator is passed to the Consistent
231 * function in the form of its strategy number, which is available
232 * from the sk_strategy field, and its subtype from the sk_subtype
233 * field.
234 *
235 * Next, if any of keys is a NULL and that key is not marked with
236 * SK_SEARCHNULL/SK_SEARCHNOTNULL then nothing can be found (ie, we
237 * assume all indexable operators are strict).
238 */
239 so->qual_ok = true;
240
241 for (i = 0; i < scan->numberOfKeys; i++)
242 {
243 ScanKey skey = scan->keyData + i;
244
245 /*
246 * Copy consistent support function to ScanKey structure instead
247 * of function implementing filtering operator.
248 */
249 fmgr_info_copy(&(skey->sk_func),
250 &(so->giststate->consistentFn[skey->sk_attno - 1]),
251 so->giststate->scanCxt);
252
253 /* Restore prior fn_extra pointers, if not first time */
254 if (!first_time)
255 skey->sk_func.fn_extra = fn_extras[i];
256
257 if (skey->sk_flags & SK_ISNULL)
258 {
259 if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
260 so->qual_ok = false;
261 }
262 }
263
264 if (!first_time)
265 pfree(fn_extras);
266 }
267
268 /* Update order-by key, if a new one is given */
269 if (orderbys && scan->numberOfOrderBys > 0)
270 {
271 void **fn_extras = NULL;
272
273 /* As above, preserve fn_extra if not first time through */
274 if (!first_time)
275 {
276 fn_extras = (void **) palloc(scan->numberOfOrderBys * sizeof(void *));
277 for (i = 0; i < scan->numberOfOrderBys; i++)
278 fn_extras[i] = scan->orderByData[i].sk_func.fn_extra;
279 }
280
281 memmove(scan->orderByData, orderbys,
282 scan->numberOfOrderBys * sizeof(ScanKeyData));
283
284 so->orderByTypes = (Oid *) palloc(scan->numberOfOrderBys * sizeof(Oid));
285
286 /*
287 * Modify the order-by key so that the Distance method is called for
288 * all comparisons. The original operator is passed to the Distance
289 * function in the form of its strategy number, which is available
290 * from the sk_strategy field, and its subtype from the sk_subtype
291 * field.
292 */
293 for (i = 0; i < scan->numberOfOrderBys; i++)
294 {
295 ScanKey skey = scan->orderByData + i;
296 FmgrInfo *finfo = &(so->giststate->distanceFn[skey->sk_attno - 1]);
297
298 /* Check we actually have a distance function ... */
299 if (!OidIsValid(finfo->fn_oid))
300 elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
301 GIST_DISTANCE_PROC, skey->sk_attno,
302 RelationGetRelationName(scan->indexRelation));
303
304 /*
305 * Look up the datatype returned by the original ordering
306 * operator. GiST always uses a float8 for the distance function,
307 * but the ordering operator could be anything else.
308 *
309 * XXX: The distance function is only allowed to be lossy if the
310 * ordering operator's result type is float4 or float8. Otherwise
311 * we don't know how to return the distance to the executor. But
312 * we cannot check that here, as we won't know if the distance
313 * function is lossy until it returns *recheck = true for the
314 * first time.
315 */
316 so->orderByTypes[i] = get_func_rettype(skey->sk_func.fn_oid);
317
318 /*
319 * Copy distance support function to ScanKey structure instead of
320 * function implementing ordering operator.
321 */
322 fmgr_info_copy(&(skey->sk_func), finfo, so->giststate->scanCxt);
323
324 /* Restore prior fn_extra pointers, if not first time */
325 if (!first_time)
326 skey->sk_func.fn_extra = fn_extras[i];
327 }
328
329 if (!first_time)
330 pfree(fn_extras);
331 }
332
333 /* any previous xs_hitup will have been pfree'd in context resets above */
334 scan->xs_hitup = NULL;
335 }
336
337 void
gistendscan(IndexScanDesc scan)338 gistendscan(IndexScanDesc scan)
339 {
340 GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
341
342 /*
343 * freeGISTstate is enough to clean up everything made by gistbeginscan,
344 * as well as the queueCxt if there is a separate context for it.
345 */
346 freeGISTstate(so->giststate);
347 }
348