Line data Source code
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
29 3322 : pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
30 : {
31 3322 : const GISTSearchItem *sa = (const GISTSearchItem *) a;
32 3322 : const GISTSearchItem *sb = (const GISTSearchItem *) b;
33 3322 : IndexScanDesc scan = (IndexScanDesc) arg;
34 : int i;
35 :
36 : /* Order according to distance comparison */
37 3322 : for (i = 0; i < scan->numberOfOrderBys; i++)
38 : {
39 895 : if (sa->distances[i] != sb->distances[i])
40 895 : return (sa->distances[i] < sb->distances[i]) ? 1 : -1;
41 : }
42 :
43 : /* Heap items go before inner pages, to ensure a depth-first search */
44 2427 : if (GISTSearchItemIsHeap(*sa) && !GISTSearchItemIsHeap(*sb))
45 0 : return 1;
46 2427 : if (!GISTSearchItemIsHeap(*sa) && GISTSearchItemIsHeap(*sb))
47 0 : return -1;
48 :
49 2427 : return 0;
50 : }
51 :
52 :
53 : /*
54 : * Index AM API functions for scanning GiST indexes
55 : */
56 :
57 : IndexScanDesc
58 110 : gistbeginscan(Relation r, int nkeys, int norderbys)
59 : {
60 : IndexScanDesc scan;
61 : GISTSTATE *giststate;
62 : GISTScanOpaque so;
63 : MemoryContext oldCxt;
64 :
65 110 : scan = RelationGetIndexScan(r, nkeys, norderbys);
66 :
67 : /* First, set up a GISTSTATE with a scan-lifespan memory context */
68 110 : 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 110 : oldCxt = MemoryContextSwitchTo(giststate->scanCxt);
75 :
76 : /* initialize opaque data */
77 110 : so = (GISTScanOpaque) palloc0(sizeof(GISTScanOpaqueData));
78 110 : so->giststate = giststate;
79 110 : giststate->tempCxt = createTempGistContext();
80 110 : so->queue = NULL;
81 110 : so->queueCxt = giststate->scanCxt; /* see gistrescan */
82 :
83 : /* workspaces with size dependent on numberOfOrderBys: */
84 110 : so->distances = palloc(sizeof(double) * scan->numberOfOrderBys);
85 110 : so->qual_ok = true; /* in case there are zero keys */
86 110 : if (scan->numberOfOrderBys > 0)
87 : {
88 8 : scan->xs_orderbyvals = palloc0(sizeof(Datum) * scan->numberOfOrderBys);
89 8 : scan->xs_orderbynulls = palloc(sizeof(bool) * scan->numberOfOrderBys);
90 8 : memset(scan->xs_orderbynulls, true, sizeof(bool) * scan->numberOfOrderBys);
91 : }
92 :
93 110 : so->killedItems = NULL; /* until needed */
94 110 : so->numKilled = 0;
95 110 : so->curBlkno = InvalidBlockNumber;
96 110 : so->curPageLSN = InvalidXLogRecPtr;
97 :
98 110 : 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 110 : MemoryContextSwitchTo(oldCxt);
106 :
107 110 : return scan;
108 : }
109 :
110 : void
111 113 : gistrescan(IndexScanDesc scan, ScanKey key, int nkeys,
112 : ScanKey orderbys, int norderbys)
113 : {
114 : /* nkeys and norderbys arguments are ignored */
115 113 : 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 113 : if (so->queue == NULL)
133 : {
134 : /* first time through */
135 110 : Assert(so->queueCxt == so->giststate->scanCxt);
136 110 : first_time = true;
137 : }
138 3 : else if (so->queueCxt == so->giststate->scanCxt)
139 : {
140 : /* second time through */
141 2 : so->queueCxt = AllocSetContextCreate(so->giststate->scanCxt,
142 : "GiST queue context",
143 : ALLOCSET_DEFAULT_SIZES);
144 2 : first_time = false;
145 : }
146 : else
147 : {
148 : /* third or later time through */
149 1 : MemoryContextReset(so->queueCxt);
150 1 : 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 113 : 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 : */
169 48 : natts = RelationGetNumberOfAttributes(scan->indexRelation);
170 48 : so->giststate->fetchTupdesc = CreateTemplateTupleDesc(natts, false);
171 96 : for (attno = 1; attno <= natts; attno++)
172 : {
173 48 : TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
174 48 : scan->indexRelation->rd_opcintype[attno - 1],
175 : -1, 0);
176 : }
177 48 : scan->xs_hitupdesc = so->giststate->fetchTupdesc;
178 :
179 : /* Also create a memory context that will hold the returned tuples */
180 48 : so->pageDataCxt = AllocSetContextCreate(so->giststate->scanCxt,
181 : "GiST page data context",
182 : ALLOCSET_DEFAULT_SIZES);
183 : }
184 :
185 : /* create new, empty pairing heap for search queue */
186 113 : oldCxt = MemoryContextSwitchTo(so->queueCxt);
187 113 : so->queue = pairingheap_allocate(pairingheap_GISTSearchItem_cmp, scan);
188 113 : MemoryContextSwitchTo(oldCxt);
189 :
190 113 : so->firstCall = true;
191 :
192 : /* Update scan key, if a new one is given */
193 113 : if (key && scan->numberOfKeys > 0)
194 : {
195 110 : 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 110 : if (!first_time)
203 : {
204 3 : fn_extras = (void **) palloc(scan->numberOfKeys * sizeof(void *));
205 6 : for (i = 0; i < scan->numberOfKeys; i++)
206 3 : fn_extras[i] = scan->keyData[i].sk_func.fn_extra;
207 : }
208 :
209 110 : memmove(scan->keyData, key,
210 110 : 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 110 : so->qual_ok = true;
224 :
225 238 : for (i = 0; i < scan->numberOfKeys; i++)
226 : {
227 128 : ScanKey skey = scan->keyData + i;
228 :
229 : /*
230 : * Copy consistent support function to ScanKey structure instead
231 : * of function implementing filtering operator.
232 : */
233 256 : fmgr_info_copy(&(skey->sk_func),
234 128 : &(so->giststate->consistentFn[skey->sk_attno - 1]),
235 128 : so->giststate->scanCxt);
236 :
237 : /* Restore prior fn_extra pointers, if not first time */
238 128 : if (!first_time)
239 3 : skey->sk_func.fn_extra = fn_extras[i];
240 :
241 128 : if (skey->sk_flags & SK_ISNULL)
242 : {
243 4 : if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
244 0 : so->qual_ok = false;
245 : }
246 : }
247 :
248 110 : if (!first_time)
249 3 : pfree(fn_extras);
250 : }
251 :
252 : /* Update order-by key, if a new one is given */
253 113 : if (orderbys && scan->numberOfOrderBys > 0)
254 : {
255 10 : void **fn_extras = NULL;
256 :
257 : /* As above, preserve fn_extra if not first time through */
258 10 : if (!first_time)
259 : {
260 2 : fn_extras = (void **) palloc(scan->numberOfOrderBys * sizeof(void *));
261 4 : for (i = 0; i < scan->numberOfOrderBys; i++)
262 2 : fn_extras[i] = scan->orderByData[i].sk_func.fn_extra;
263 : }
264 :
265 10 : memmove(scan->orderByData, orderbys,
266 10 : scan->numberOfOrderBys * sizeof(ScanKeyData));
267 :
268 10 : 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 20 : for (i = 0; i < scan->numberOfOrderBys; i++)
278 : {
279 10 : ScanKey skey = scan->orderByData + i;
280 10 : FmgrInfo *finfo = &(so->giststate->distanceFn[skey->sk_attno - 1]);
281 :
282 : /* Check we actually have a distance function ... */
283 10 : if (!OidIsValid(finfo->fn_oid))
284 0 : elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
285 : GIST_DISTANCE_PROC, skey->sk_attno,
286 : RelationGetRelationName(scan->indexRelation));
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 : */
300 10 : so->orderByTypes[i] = get_func_rettype(skey->sk_func.fn_oid);
301 :
302 : /*
303 : * Copy distance support function to ScanKey structure instead of
304 : * function implementing ordering operator.
305 : */
306 10 : fmgr_info_copy(&(skey->sk_func), finfo, so->giststate->scanCxt);
307 :
308 : /* Restore prior fn_extra pointers, if not first time */
309 10 : if (!first_time)
310 2 : skey->sk_func.fn_extra = fn_extras[i];
311 : }
312 :
313 10 : if (!first_time)
314 2 : pfree(fn_extras);
315 : }
316 :
317 : /* any previous xs_hitup will have been pfree'd in context resets above */
318 113 : scan->xs_hitup = NULL;
319 113 : }
320 :
321 : void
322 104 : gistendscan(IndexScanDesc scan)
323 : {
324 104 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
325 :
326 : /*
327 : * freeGISTstate is enough to clean up everything made by gistbeginscan,
328 : * as well as the queueCxt if there is a separate context for it.
329 : */
330 104 : freeGISTstate(so->giststate);
331 104 : }
|
