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-2024, 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 : */
29 : static int
30 363062 : pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
31 : {
32 363062 : const GISTSearchItem *sa = (const GISTSearchItem *) a;
33 363062 : const GISTSearchItem *sb = (const GISTSearchItem *) b;
34 363062 : IndexScanDesc scan = (IndexScanDesc) arg;
35 : int i;
36 :
37 : /* Order according to distance comparison */
38 367206 : for (i = 0; i < scan->numberOfOrderBys; i++)
39 : {
40 68718 : if (sa->distances[i].isnull)
41 : {
42 108 : if (!sb->distances[i].isnull)
43 108 : return -1;
44 : }
45 68610 : else if (sb->distances[i].isnull)
46 : {
47 14 : return 1;
48 : }
49 : else
50 : {
51 68596 : int cmp = -float8_cmp_internal(sa->distances[i].value,
52 : sb->distances[i].value);
53 :
54 68596 : if (cmp != 0)
55 64452 : return cmp;
56 : }
57 : }
58 :
59 : /* Heap items go before inner pages, to ensure a depth-first search */
60 298488 : if (GISTSearchItemIsHeap(*sa) && !GISTSearchItemIsHeap(*sb))
61 0 : return 1;
62 298488 : if (!GISTSearchItemIsHeap(*sa) && GISTSearchItemIsHeap(*sb))
63 2 : return -1;
64 :
65 298486 : return 0;
66 : }
67 :
68 :
69 : /*
70 : * Index AM API functions for scanning GiST indexes
71 : */
72 :
73 : IndexScanDesc
74 4644 : gistbeginscan(Relation r, int nkeys, int norderbys)
75 : {
76 : IndexScanDesc scan;
77 : GISTSTATE *giststate;
78 : GISTScanOpaque so;
79 : MemoryContext oldCxt;
80 :
81 4644 : scan = RelationGetIndexScan(r, nkeys, norderbys);
82 :
83 : /* First, set up a GISTSTATE with a scan-lifespan memory context */
84 4644 : 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 4644 : oldCxt = MemoryContextSwitchTo(giststate->scanCxt);
91 :
92 : /* initialize opaque data */
93 4644 : so = (GISTScanOpaque) palloc0(sizeof(GISTScanOpaqueData));
94 4644 : so->giststate = giststate;
95 4644 : giststate->tempCxt = createTempGistContext();
96 4644 : so->queue = NULL;
97 4644 : so->queueCxt = giststate->scanCxt; /* see gistrescan */
98 :
99 : /* workspaces with size dependent on numberOfOrderBys: */
100 4644 : so->distances = palloc(sizeof(so->distances[0]) * scan->numberOfOrderBys);
101 4644 : so->qual_ok = true; /* in case there are zero keys */
102 4644 : if (scan->numberOfOrderBys > 0)
103 : {
104 126 : scan->xs_orderbyvals = palloc0(sizeof(Datum) * scan->numberOfOrderBys);
105 126 : scan->xs_orderbynulls = palloc(sizeof(bool) * scan->numberOfOrderBys);
106 126 : memset(scan->xs_orderbynulls, true, sizeof(bool) * scan->numberOfOrderBys);
107 : }
108 :
109 4644 : so->killedItems = NULL; /* until needed */
110 4644 : so->numKilled = 0;
111 4644 : so->curBlkno = InvalidBlockNumber;
112 4644 : so->curPageLSN = InvalidXLogRecPtr;
113 :
114 4644 : 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 4644 : MemoryContextSwitchTo(oldCxt);
122 :
123 4644 : return scan;
124 : }
125 :
126 : void
127 4734 : gistrescan(IndexScanDesc scan, ScanKey key, int nkeys,
128 : ScanKey orderbys, int norderbys)
129 : {
130 : /* nkeys and norderbys arguments are ignored */
131 4734 : 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 4734 : if (so->queue == NULL)
149 : {
150 : /* first time through */
151 : Assert(so->queueCxt == so->giststate->scanCxt);
152 4644 : first_time = true;
153 : }
154 90 : else if (so->queueCxt == so->giststate->scanCxt)
155 : {
156 : /* second time through */
157 30 : so->queueCxt = AllocSetContextCreate(so->giststate->scanCxt,
158 : "GiST queue context",
159 : ALLOCSET_DEFAULT_SIZES);
160 30 : first_time = false;
161 : }
162 : else
163 : {
164 : /* third or later time through */
165 60 : MemoryContextReset(so->queueCxt);
166 60 : 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 4734 : 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 668 : natts = RelationGetNumberOfAttributes(scan->indexRelation);
187 668 : nkeyatts = IndexRelationGetNumberOfKeyAttributes(scan->indexRelation);
188 668 : so->giststate->fetchTupdesc = CreateTemplateTupleDesc(natts);
189 1362 : for (attno = 1; attno <= nkeyatts; attno++)
190 : {
191 694 : TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
192 694 : scan->indexRelation->rd_opcintype[attno - 1],
193 : -1, 0);
194 : }
195 :
196 668 : for (; attno <= natts; attno++)
197 : {
198 : /* taking opcintype from giststate->tupdesc */
199 0 : TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
200 0 : TupleDescAttr(so->giststate->leafTupdesc,
201 : attno - 1)->atttypid,
202 : -1, 0);
203 : }
204 668 : scan->xs_hitupdesc = so->giststate->fetchTupdesc;
205 :
206 : /* Also create a memory context that will hold the returned tuples */
207 668 : 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 4734 : oldCxt = MemoryContextSwitchTo(so->queueCxt);
214 4734 : so->queue = pairingheap_allocate(pairingheap_GISTSearchItem_cmp, scan);
215 4734 : MemoryContextSwitchTo(oldCxt);
216 :
217 4734 : so->firstCall = true;
218 :
219 : /* Update scan key, if a new one is given */
220 4734 : if (key && scan->numberOfKeys > 0)
221 : {
222 4584 : 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 4584 : if (!first_time)
230 : {
231 30 : fn_extras = (void **) palloc(scan->numberOfKeys * sizeof(void *));
232 60 : for (i = 0; i < scan->numberOfKeys; i++)
233 30 : fn_extras[i] = scan->keyData[i].sk_func.fn_extra;
234 : }
235 :
236 4584 : memmove(scan->keyData, key,
237 4584 : 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 4584 : so->qual_ok = true;
251 :
252 10850 : for (i = 0; i < scan->numberOfKeys; i++)
253 : {
254 6266 : ScanKey skey = scan->keyData + i;
255 :
256 : /*
257 : * Copy consistent support function to ScanKey structure instead
258 : * of function implementing filtering operator.
259 : */
260 6266 : fmgr_info_copy(&(skey->sk_func),
261 6266 : &(so->giststate->consistentFn[skey->sk_attno - 1]),
262 6266 : so->giststate->scanCxt);
263 :
264 : /* Restore prior fn_extra pointers, if not first time */
265 6266 : if (!first_time)
266 30 : skey->sk_func.fn_extra = fn_extras[i];
267 :
268 6266 : if (skey->sk_flags & SK_ISNULL)
269 : {
270 26 : if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
271 0 : so->qual_ok = false;
272 : }
273 : }
274 :
275 4584 : if (!first_time)
276 30 : pfree(fn_extras);
277 : }
278 :
279 : /* Update order-by key, if a new one is given */
280 4734 : if (orderbys && scan->numberOfOrderBys > 0)
281 : {
282 198 : void **fn_extras = NULL;
283 :
284 : /* As above, preserve fn_extra if not first time through */
285 198 : if (!first_time)
286 : {
287 72 : fn_extras = (void **) palloc(scan->numberOfOrderBys * sizeof(void *));
288 144 : for (i = 0; i < scan->numberOfOrderBys; i++)
289 72 : fn_extras[i] = scan->orderByData[i].sk_func.fn_extra;
290 : }
291 :
292 198 : memmove(scan->orderByData, orderbys,
293 198 : scan->numberOfOrderBys * sizeof(ScanKeyData));
294 :
295 198 : 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 396 : for (i = 0; i < scan->numberOfOrderBys; i++)
305 : {
306 198 : ScanKey skey = scan->orderByData + i;
307 198 : FmgrInfo *finfo = &(so->giststate->distanceFn[skey->sk_attno - 1]);
308 :
309 : /* Check we actually have a distance function ... */
310 198 : if (!OidIsValid(finfo->fn_oid))
311 0 : 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 198 : 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 198 : fmgr_info_copy(&(skey->sk_func), finfo, so->giststate->scanCxt);
334 :
335 : /* Restore prior fn_extra pointers, if not first time */
336 198 : if (!first_time)
337 72 : skey->sk_func.fn_extra = fn_extras[i];
338 : }
339 :
340 198 : if (!first_time)
341 72 : pfree(fn_extras);
342 : }
343 :
344 : /* any previous xs_hitup will have been pfree'd in context resets above */
345 4734 : scan->xs_hitup = NULL;
346 4734 : }
347 :
348 : void
349 4440 : gistendscan(IndexScanDesc scan)
350 : {
351 4440 : 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 4440 : freeGISTstate(so->giststate);
358 4440 : }
|
