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 */
29static int
30pairingheap_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
73IndexScanDesc
74gistbeginscan(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
126void
127gistrescan(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 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 */
186 natts = RelationGetNumberOfAttributes(scan->indexRelation);
187 nkeyatts = IndexRelationGetNumberOfKeyAttributes(scan->indexRelation);
188 so->giststate->fetchTupdesc = CreateTemplateTupleDesc(natts);
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,
200 TupleDescAttr(so->giststate->leafTupdesc,
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 */
207 so->pageDataCxt = AllocSetContextCreate(so->giststate->scanCxt,
208 "GiST page data context",
209 ALLOCSET_DEFAULT_SIZES);
210 }
211
212 /* create new, empty pairing heap for search queue */
213 oldCxt = MemoryContextSwitchTo(so->queueCxt);
214 so->queue = pairingheap_allocate(pairingheap_GISTSearchItem_cmp, scan);
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\"",
312 GIST_DISTANCE_PROC, skey->sk_attno,
313 RelationGetRelationName(scan->indexRelation));
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 */
327 so->orderByTypes[i] = get_func_rettype(skey->sk_func.fn_oid);
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
348void
349gistendscan(IndexScanDesc scan)
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 */
357 freeGISTstate(so->giststate);
358}
359