Branch data 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-2026, 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 : 14977 : pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
31 : : {
32 : 14977 : const GISTSearchItem *sa = (const GISTSearchItem *) a;
33 : 14977 : const GISTSearchItem *sb = (const GISTSearchItem *) b;
34 : 14977 : IndexScanDesc scan = (IndexScanDesc) arg;
35 : 14977 : int i;
36 : :
37 : : /* Order according to distance comparison */
38 [ + + ]: 15021 : for (i = 0; i < scan->numberOfOrderBys; i++)
39 : : {
40 [ + + ]: 2879 : if (sa->distances[i].isnull)
41 : : {
42 [ - + ]: 14 : if (!sb->distances[i].isnull)
43 : 14 : return -1;
44 : 0 : }
45 [ + + ]: 2865 : else if (sb->distances[i].isnull)
46 : : {
47 : 1 : return 1;
48 : : }
49 : : else
50 : : {
51 : 5728 : int cmp = -float8_cmp_internal(sa->distances[i].value,
52 : 2864 : sb->distances[i].value);
53 : :
54 [ + + ]: 2864 : if (cmp != 0)
55 : 2820 : return cmp;
56 [ + + ]: 2864 : }
57 : 44 : }
58 : :
59 : : /* Heap items go before inner pages, to ensure a depth-first search */
60 [ + + + - ]: 12142 : if (GISTSearchItemIsHeap(*sa) && !GISTSearchItemIsHeap(*sb))
61 : 0 : return 1;
62 [ + + + - ]: 12142 : if (!GISTSearchItemIsHeap(*sa) && GISTSearchItemIsHeap(*sb))
63 : 0 : return -1;
64 : :
65 : 12142 : return 0;
66 : 14977 : }
67 : :
68 : :
69 : : /*
70 : : * Index AM API functions for scanning GiST indexes
71 : : */
72 : :
73 : : IndexScanDesc
74 : 769 : gistbeginscan(Relation r, int nkeys, int norderbys)
75 : : {
76 : 769 : IndexScanDesc scan;
77 : 769 : GISTSTATE *giststate;
78 : 769 : GISTScanOpaque so;
79 : 769 : MemoryContext oldCxt;
80 : :
81 : 769 : scan = RelationGetIndexScan(r, nkeys, norderbys);
82 : :
83 : : /* First, set up a GISTSTATE with a scan-lifespan memory context */
84 : 769 : 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 : 769 : oldCxt = MemoryContextSwitchTo(giststate->scanCxt);
91 : :
92 : : /* initialize opaque data */
93 : 769 : so = palloc0_object(GISTScanOpaqueData);
94 : 769 : so->giststate = giststate;
95 : 769 : giststate->tempCxt = createTempGistContext();
96 : 769 : so->queue = NULL;
97 : 769 : so->queueCxt = giststate->scanCxt; /* see gistrescan */
98 : :
99 : : /* workspaces with size dependent on numberOfOrderBys: */
100 : 769 : so->distances = palloc(sizeof(so->distances[0]) * scan->numberOfOrderBys);
101 : 769 : so->qual_ok = true; /* in case there are zero keys */
102 [ + + ]: 769 : if (scan->numberOfOrderBys > 0)
103 : : {
104 : 12 : scan->xs_orderbyvals = palloc0_array(Datum, scan->numberOfOrderBys);
105 : 12 : scan->xs_orderbynulls = palloc_array(bool, scan->numberOfOrderBys);
106 : 12 : memset(scan->xs_orderbynulls, true, sizeof(bool) * scan->numberOfOrderBys);
107 : 12 : }
108 : :
109 : 769 : so->killedItems = NULL; /* until needed */
110 : 769 : so->numKilled = 0;
111 : 769 : so->curBlkno = InvalidBlockNumber;
112 : 769 : so->curPageLSN = InvalidXLogRecPtr;
113 : :
114 : 769 : 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 : 769 : MemoryContextSwitchTo(oldCxt);
122 : :
123 : 1538 : return scan;
124 : 769 : }
125 : :
126 : : void
127 : 784 : gistrescan(IndexScanDesc scan, ScanKey key, int nkeys,
128 : : ScanKey orderbys, int norderbys)
129 : : {
130 : : /* nkeys and norderbys arguments are ignored */
131 : 784 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
132 : 784 : bool first_time;
133 : 784 : int i;
134 : 784 : 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 [ + + ]: 784 : if (so->queue == NULL)
149 : : {
150 : : /* first time through */
151 [ + - ]: 769 : Assert(so->queueCxt == so->giststate->scanCxt);
152 : 769 : first_time = true;
153 : 769 : }
154 [ + + ]: 15 : else if (so->queueCxt == so->giststate->scanCxt)
155 : : {
156 : : /* second time through */
157 : 5 : so->queueCxt = AllocSetContextCreate(so->giststate->scanCxt,
158 : : "GiST queue context",
159 : : ALLOCSET_DEFAULT_SIZES);
160 : 5 : first_time = false;
161 : 5 : }
162 : : else
163 : : {
164 : : /* third or later time through */
165 : 10 : MemoryContextReset(so->queueCxt);
166 : 10 : 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 [ + + + + ]: 784 : if (scan->xs_want_itup && !scan->xs_hitupdesc)
175 : : {
176 : 72 : int natts;
177 : 72 : int nkeyatts;
178 : 72 : 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 : 72 : natts = RelationGetNumberOfAttributes(scan->indexRelation);
187 : 72 : nkeyatts = IndexRelationGetNumberOfKeyAttributes(scan->indexRelation);
188 : 72 : so->giststate->fetchTupdesc = CreateTemplateTupleDesc(natts);
189 [ + + ]: 148 : for (attno = 1; attno <= nkeyatts; attno++)
190 : : {
191 : 152 : TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
192 : 76 : scan->indexRelation->rd_opcintype[attno - 1],
193 : : -1, 0);
194 : 76 : }
195 : :
196 [ - + ]: 72 : 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 : 0 : attno - 1)->atttypid,
202 : : -1, 0);
203 : 0 : }
204 : 72 : scan->xs_hitupdesc = so->giststate->fetchTupdesc;
205 : :
206 : : /* Also create a memory context that will hold the returned tuples */
207 : 72 : so->pageDataCxt = AllocSetContextCreate(so->giststate->scanCxt,
208 : : "GiST page data context",
209 : : ALLOCSET_DEFAULT_SIZES);
210 : 72 : }
211 : :
212 : : /* create new, empty pairing heap for search queue */
213 : 784 : oldCxt = MemoryContextSwitchTo(so->queueCxt);
214 : 784 : so->queue = pairingheap_allocate(pairingheap_GISTSearchItem_cmp, scan);
215 : 784 : MemoryContextSwitchTo(oldCxt);
216 : :
217 : 784 : so->firstCall = true;
218 : :
219 : : /* Update scan key, if a new one is given */
220 [ + - + + ]: 784 : if (key && scan->numberOfKeys > 0)
221 : : {
222 : 768 : 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 [ + + ]: 768 : if (!first_time)
230 : : {
231 : 5 : fn_extras = (void **) palloc(scan->numberOfKeys * sizeof(void *));
232 [ + + ]: 10 : for (i = 0; i < scan->numberOfKeys; i++)
233 : 5 : fn_extras[i] = scan->keyData[i].sk_func.fn_extra;
234 : 5 : }
235 : :
236 : 768 : memcpy(scan->keyData, key, scan->numberOfKeys * sizeof(ScanKeyData));
237 : :
238 : : /*
239 : : * Modify the scan key so that the Consistent method is called for all
240 : : * comparisons. The original operator is passed to the Consistent
241 : : * function in the form of its strategy number, which is available
242 : : * from the sk_strategy field, and its subtype from the sk_subtype
243 : : * field.
244 : : *
245 : : * Next, if any of keys is a NULL and that key is not marked with
246 : : * SK_SEARCHNULL/SK_SEARCHNOTNULL then nothing can be found (ie, we
247 : : * assume all indexable operators are strict).
248 : : */
249 : 768 : so->qual_ok = true;
250 : :
251 [ + + ]: 1972 : for (i = 0; i < scan->numberOfKeys; i++)
252 : : {
253 : 1204 : ScanKey skey = scan->keyData + i;
254 : :
255 : : /*
256 : : * Copy consistent support function to ScanKey structure instead
257 : : * of function implementing filtering operator.
258 : : */
259 : 2408 : fmgr_info_copy(&(skey->sk_func),
260 : 1204 : &(so->giststate->consistentFn[skey->sk_attno - 1]),
261 : 1204 : so->giststate->scanCxt);
262 : :
263 : : /* Restore prior fn_extra pointers, if not first time */
264 [ + + ]: 1204 : if (!first_time)
265 : 5 : skey->sk_func.fn_extra = fn_extras[i];
266 : :
267 [ + + ]: 1204 : if (skey->sk_flags & SK_ISNULL)
268 : : {
269 [ + - ]: 4 : if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
270 : 0 : so->qual_ok = false;
271 : 4 : }
272 : 1204 : }
273 : :
274 [ + + ]: 768 : if (!first_time)
275 : 5 : pfree(fn_extras);
276 : 768 : }
277 : :
278 : : /* Update order-by key, if a new one is given */
279 [ + + + + ]: 784 : if (orderbys && scan->numberOfOrderBys > 0)
280 : : {
281 : 24 : void **fn_extras = NULL;
282 : :
283 : : /* As above, preserve fn_extra if not first time through */
284 [ + + ]: 24 : if (!first_time)
285 : : {
286 : 12 : fn_extras = (void **) palloc(scan->numberOfOrderBys * sizeof(void *));
287 [ + + ]: 24 : for (i = 0; i < scan->numberOfOrderBys; i++)
288 : 12 : fn_extras[i] = scan->orderByData[i].sk_func.fn_extra;
289 : 12 : }
290 : :
291 : 24 : memcpy(scan->orderByData, orderbys, scan->numberOfOrderBys * sizeof(ScanKeyData));
292 : :
293 : 24 : so->orderByTypes = (Oid *) palloc(scan->numberOfOrderBys * sizeof(Oid));
294 : :
295 : : /*
296 : : * Modify the order-by key so that the Distance method is called for
297 : : * all comparisons. The original operator is passed to the Distance
298 : : * function in the form of its strategy number, which is available
299 : : * from the sk_strategy field, and its subtype from the sk_subtype
300 : : * field.
301 : : */
302 [ + + ]: 48 : for (i = 0; i < scan->numberOfOrderBys; i++)
303 : : {
304 : 24 : ScanKey skey = scan->orderByData + i;
305 : 24 : FmgrInfo *finfo = &(so->giststate->distanceFn[skey->sk_attno - 1]);
306 : :
307 : : /* Check we actually have a distance function ... */
308 [ + - ]: 24 : if (!OidIsValid(finfo->fn_oid))
309 [ # # # # ]: 0 : elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
310 : : GIST_DISTANCE_PROC, skey->sk_attno,
311 : : RelationGetRelationName(scan->indexRelation));
312 : :
313 : : /*
314 : : * Look up the datatype returned by the original ordering
315 : : * operator. GiST always uses a float8 for the distance function,
316 : : * but the ordering operator could be anything else.
317 : : *
318 : : * XXX: The distance function is only allowed to be lossy if the
319 : : * ordering operator's result type is float4 or float8. Otherwise
320 : : * we don't know how to return the distance to the executor. But
321 : : * we cannot check that here, as we won't know if the distance
322 : : * function is lossy until it returns *recheck = true for the
323 : : * first time.
324 : : */
325 : 24 : so->orderByTypes[i] = get_func_rettype(skey->sk_func.fn_oid);
326 : :
327 : : /*
328 : : * Copy distance support function to ScanKey structure instead of
329 : : * function implementing ordering operator.
330 : : */
331 : 24 : fmgr_info_copy(&(skey->sk_func), finfo, so->giststate->scanCxt);
332 : :
333 : : /* Restore prior fn_extra pointers, if not first time */
334 [ + + ]: 24 : if (!first_time)
335 : 12 : skey->sk_func.fn_extra = fn_extras[i];
336 : 24 : }
337 : :
338 [ + + ]: 24 : if (!first_time)
339 : 12 : pfree(fn_extras);
340 : 24 : }
341 : :
342 : : /* any previous xs_hitup will have been pfree'd in context resets above */
343 : 784 : scan->xs_hitup = NULL;
344 : 784 : }
345 : :
346 : : void
347 : 726 : gistendscan(IndexScanDesc scan)
348 : : {
349 : 726 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
350 : :
351 : : /*
352 : : * freeGISTstate is enough to clean up everything made by gistbeginscan,
353 : : * as well as the queueCxt if there is a separate context for it.
354 : : */
355 : 726 : freeGISTstate(so->giststate);
356 : 726 : }
|
