Age Owner Branch data TLA 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
4266 heikki.linnakangas@i 30 :CBC 199470 : pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
31 : : {
32 : 199470 : const GISTSearchItem *sa = (const GISTSearchItem *) a;
33 : 199470 : const GISTSearchItem *sb = (const GISTSearchItem *) b;
5746 tgl@sss.pgh.pa.us 34 : 199470 : IndexScanDesc scan = (IndexScanDesc) arg;
35 : : int i;
36 : :
37 : : /* Order according to distance comparison */
38 [ + + ]: 201521 : for (i = 0; i < scan->numberOfOrderBys; i++)
39 : : {
2534 akorotkov@postgresql 40 [ + + ]: 37909 : if (sa->distances[i].isnull)
41 : : {
42 [ + - ]: 68 : if (!sb->distances[i].isnull)
2545 43 : 68 : return -1;
44 : : }
2534 45 [ + + ]: 37841 : else if (sb->distances[i].isnull)
46 : : {
2545 47 : 16 : return 1;
48 : : }
49 : : else
50 : : {
2534 51 : 75650 : int cmp = -float8_cmp_internal(sa->distances[i].value,
52 : 37825 : sb->distances[i].value);
53 : :
2545 54 [ + + ]: 37825 : if (cmp != 0)
55 : 35774 : return cmp;
56 : : }
57 : : }
58 : :
59 : : /* Heap items go before inner pages, to ensure a depth-first search */
4266 heikki.linnakangas@i 60 [ + + - + ]: 163612 : if (GISTSearchItemIsHeap(*sa) && !GISTSearchItemIsHeap(*sb))
4266 heikki.linnakangas@i 61 :UBC 0 : return 1;
4209 heikki.linnakangas@i 62 [ + + + + ]:CBC 163612 : if (!GISTSearchItemIsHeap(*sa) && GISTSearchItemIsHeap(*sb))
63 : 2 : return -1;
64 : :
4266 65 : 163610 : return 0;
66 : : }
67 : :
68 : :
69 : : /*
70 : : * Index AM API functions for scanning GiST indexes
71 : : */
72 : :
73 : : IndexScanDesc
3875 tgl@sss.pgh.pa.us 74 : 6318 : gistbeginscan(Relation r, int nkeys, int norderbys)
75 : : {
76 : : IndexScanDesc scan;
77 : : GISTSTATE *giststate;
78 : : GISTScanOpaque so;
79 : : MemoryContext oldCxt;
80 : :
5747 81 : 6318 : scan = RelationGetIndexScan(r, nkeys, norderbys);
82 : :
83 : : /* First, set up a GISTSTATE with a scan-lifespan memory context */
5445 84 : 6318 : 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 : 6318 : oldCxt = MemoryContextSwitchTo(giststate->scanCxt);
91 : :
92 : : /* initialize opaque data */
260 michael@paquier.xyz 93 : 6318 : so = palloc0_object(GISTScanOpaqueData);
5445 tgl@sss.pgh.pa.us 94 : 6318 : so->giststate = giststate;
95 : 6318 : giststate->tempCxt = createTempGistContext();
96 : 6318 : so->queue = NULL;
5191 bruce@momjian.us 97 : 6318 : so->queueCxt = giststate->scanCxt; /* see gistrescan */
98 : :
99 : : /* workspaces with size dependent on numberOfOrderBys: */
10 michael@paquier.xyz 100 :GNC 6318 : so->distances = palloc_array(IndexOrderByDistance, scan->numberOfOrderBys);
5746 tgl@sss.pgh.pa.us 101 :CBC 6318 : so->qual_ok = true; /* in case there are zero keys */
4122 heikki.linnakangas@i 102 [ + + ]: 6318 : if (scan->numberOfOrderBys > 0)
103 : : {
260 michael@paquier.xyz 104 : 75 : scan->xs_orderbyvals = palloc0_array(Datum, scan->numberOfOrderBys);
105 : 75 : scan->xs_orderbynulls = palloc_array(bool, scan->numberOfOrderBys);
4114 tgl@sss.pgh.pa.us 106 : 75 : memset(scan->xs_orderbynulls, true, sizeof(bool) * scan->numberOfOrderBys);
107 : : }
108 : :
4005 teodor@sigaev.ru 109 : 6318 : so->killedItems = NULL; /* until needed */
110 : 6318 : so->numKilled = 0;
111 : 6318 : so->curBlkno = InvalidBlockNumber;
112 : 6318 : so->curPageLSN = InvalidXLogRecPtr;
113 : :
5747 tgl@sss.pgh.pa.us 114 : 6318 : 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 : :
5445 121 : 6318 : MemoryContextSwitchTo(oldCxt);
122 : :
3875 123 : 6318 : return scan;
124 : : }
125 : :
126 : : void
127 : 6398 : gistrescan(IndexScanDesc scan, ScanKey key, int nkeys,
128 : : ScanKey orderbys, int norderbys)
129 : : {
130 : : /* nkeys and norderbys arguments are ignored */
5747 131 : 6398 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
132 : : bool first_time;
133 : : int i;
134 : : MemoryContext oldCxt;
135 : :
136 : : /* Before leaving current page, deal with any killed items */
8 pg@bowt.ie 137 [ - + ]:GNC 6398 : if (so->numKilled > 0)
8 pg@bowt.ie 138 :UNC 0 : gistkillitems(scan);
139 : :
140 : : /* rescan an existing indexscan --- reset state */
8 pg@bowt.ie 141 :CBC 6398 : so->curBlkno = InvalidBlockNumber;
142 : 6398 : so->curPageLSN = InvalidXLogRecPtr;
143 : :
144 : : /*
145 : : * The first time through, we create the search queue in the scanCxt.
146 : : * Subsequent times through, we create the queue in a separate queueCxt,
147 : : * which is created on the second call and reset on later calls. Thus, in
148 : : * the common case where a scan is only rescan'd once, we just put the
149 : : * queue in scanCxt and don't pay the overhead of making a second memory
150 : : * context. If we do rescan more than once, the first queue is just left
151 : : * for dead until end of scan; this small wastage seems worth the savings
152 : : * in the common case.
153 : : */
5445 tgl@sss.pgh.pa.us 154 [ + + ]: 6398 : if (so->queue == NULL)
155 : : {
156 : : /* first time through */
157 [ - + ]: 6318 : Assert(so->queueCxt == so->giststate->scanCxt);
158 : 6318 : first_time = true;
159 : : }
160 [ + + ]: 80 : else if (so->queueCxt == so->giststate->scanCxt)
161 : : {
162 : : /* second time through */
163 : 40 : so->queueCxt = AllocSetContextCreate(so->giststate->scanCxt,
164 : : "GiST queue context",
165 : : ALLOCSET_DEFAULT_SIZES);
166 : 40 : first_time = false;
167 : : }
168 : : else
169 : : {
170 : : /* third or later time through */
171 : 40 : MemoryContextReset(so->queueCxt);
172 : 40 : first_time = false;
173 : : }
174 : :
175 : : /*
176 : : * If we're doing an index-only scan, on the first call, also initialize a
177 : : * tuple descriptor to represent the returned index tuples and create a
178 : : * memory context to hold them during the scan.
179 : : */
3468 180 [ + + + + ]: 6398 : if (scan->xs_want_itup && !scan->xs_hitupdesc)
181 : : {
182 : : int natts;
183 : : int nkeyatts;
184 : : int attno;
185 : :
186 : : /*
187 : : * The storage type of the index can be different from the original
188 : : * datatype being indexed, so we cannot just grab the index's tuple
189 : : * descriptor. Instead, construct a descriptor with the original data
190 : : * types.
191 : : */
4114 bruce@momjian.us 192 : 462 : natts = RelationGetNumberOfAttributes(scan->indexRelation);
2727 akorotkov@postgresql 193 : 462 : nkeyatts = IndexRelationGetNumberOfKeyAttributes(scan->indexRelation);
2837 andres@anarazel.de 194 : 462 : so->giststate->fetchTupdesc = CreateTemplateTupleDesc(natts);
2727 akorotkov@postgresql 195 [ + + ]: 945 : for (attno = 1; attno <= nkeyatts; attno++)
196 : : {
4172 heikki.linnakangas@i 197 : 483 : TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
198 : 483 : scan->indexRelation->rd_opcintype[attno - 1],
199 : : -1, 0);
200 : : }
201 : :
2727 akorotkov@postgresql 202 [ - + ]: 462 : for (; attno <= natts; attno++)
203 : : {
204 : : /* taking opcintype from giststate->tupdesc */
2727 akorotkov@postgresql 205 :UBC 0 : TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
206 : 0 : TupleDescAttr(so->giststate->leafTupdesc,
207 : : attno - 1)->atttypid,
208 : : -1, 0);
209 : : }
164 drowley@postgresql.o 210 :CBC 462 : TupleDescFinalize(so->giststate->fetchTupdesc);
3468 tgl@sss.pgh.pa.us 211 : 462 : scan->xs_hitupdesc = so->giststate->fetchTupdesc;
212 : :
213 : : /* Also create a memory context that will hold the returned tuples */
4172 heikki.linnakangas@i 214 : 462 : so->pageDataCxt = AllocSetContextCreate(so->giststate->scanCxt,
215 : : "GiST page data context",
216 : : ALLOCSET_DEFAULT_SIZES);
217 : : }
218 : :
219 : : /* create new, empty pairing heap for search queue */
5746 tgl@sss.pgh.pa.us 220 : 6398 : oldCxt = MemoryContextSwitchTo(so->queueCxt);
4266 heikki.linnakangas@i 221 : 6398 : so->queue = pairingheap_allocate(pairingheap_GISTSearchItem_cmp, scan);
5746 tgl@sss.pgh.pa.us 222 : 6398 : MemoryContextSwitchTo(oldCxt);
223 : :
224 : 6398 : so->firstCall = true;
225 : :
226 : : /* Update scan key, if a new one is given */
7772 neilc@samurai.com 227 [ + + + + ]: 6398 : if (key && scan->numberOfKeys > 0)
228 : : {
4858 tgl@sss.pgh.pa.us 229 : 6303 : void **fn_extras = NULL;
230 : :
231 : : /*
232 : : * If this isn't the first time through, preserve the fn_extra
233 : : * pointers, so that if the consistentFns are using them to cache
234 : : * data, that data is not leaked across a rescan.
235 : : */
5445 236 [ + + ]: 6303 : if (!first_time)
237 : : {
10 michael@paquier.xyz 238 :GNC 40 : fn_extras = palloc_array(void *, scan->numberOfKeys);
5445 tgl@sss.pgh.pa.us 239 [ + + ]:CBC 80 : for (i = 0; i < scan->numberOfKeys; i++)
4858 240 : 40 : fn_extras[i] = scan->keyData[i].sk_func.fn_extra;
241 : : }
242 : :
715 peter@eisentraut.org 243 : 6303 : memcpy(scan->keyData, key, scan->numberOfKeys * sizeof(ScanKeyData));
244 : :
245 : : /*
246 : : * Modify the scan key so that the Consistent method is called for all
247 : : * comparisons. The original operator is passed to the Consistent
248 : : * function in the form of its strategy number, which is available
249 : : * from the sk_strategy field, and its subtype from the sk_subtype
250 : : * field.
251 : : *
252 : : * Next, if any of keys is a NULL and that key is not marked with
253 : : * SK_SEARCHNULL/SK_SEARCHNOTNULL then nothing can be found (ie, we
254 : : * assume all indexable operators are strict).
255 : : */
5746 tgl@sss.pgh.pa.us 256 : 6303 : so->qual_ok = true;
257 : :
6286 bruce@momjian.us 258 [ + + ]: 16808 : for (i = 0; i < scan->numberOfKeys; i++)
259 : : {
5746 tgl@sss.pgh.pa.us 260 : 10505 : ScanKey skey = scan->keyData + i;
261 : :
262 : : /*
263 : : * Copy consistent support function to ScanKey structure instead
264 : : * of function implementing filtering operator.
265 : : */
4858 266 : 10505 : fmgr_info_copy(&(skey->sk_func),
267 : 10505 : &(so->giststate->consistentFn[skey->sk_attno - 1]),
268 : 10505 : so->giststate->scanCxt);
269 : :
270 : : /* Restore prior fn_extra pointers, if not first time */
271 [ + + ]: 10505 : if (!first_time)
272 : 40 : skey->sk_func.fn_extra = fn_extras[i];
273 : :
6082 274 [ + + ]: 10505 : if (skey->sk_flags & SK_ISNULL)
275 : : {
276 [ - + ]: 17 : if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
6523 teodor@sigaev.ru 277 :UBC 0 : so->qual_ok = false;
278 : : }
279 : : }
280 : :
4858 tgl@sss.pgh.pa.us 281 [ + + ]:CBC 6303 : if (!first_time)
282 : 40 : pfree(fn_extras);
283 : : }
284 : :
285 : : /* Update order-by key, if a new one is given */
5746 286 [ + + + + ]: 6398 : if (orderbys && scan->numberOfOrderBys > 0)
287 : : {
4858 288 : 123 : void **fn_extras = NULL;
289 : :
290 : : /* As above, preserve fn_extra if not first time through */
5445 291 [ + + ]: 123 : if (!first_time)
292 : : {
10 michael@paquier.xyz 293 :GNC 48 : fn_extras = palloc_array(void *, scan->numberOfOrderBys);
5445 tgl@sss.pgh.pa.us 294 [ + + ]:CBC 96 : for (i = 0; i < scan->numberOfOrderBys; i++)
4858 295 : 48 : fn_extras[i] = scan->orderByData[i].sk_func.fn_extra;
296 : : }
297 : :
715 peter@eisentraut.org 298 : 123 : memcpy(scan->orderByData, orderbys, scan->numberOfOrderBys * sizeof(ScanKeyData));
299 : :
10 michael@paquier.xyz 300 :GNC 123 : so->orderByTypes = palloc_array(Oid, scan->numberOfOrderBys);
301 : :
302 : : /*
303 : : * Modify the order-by key so that the Distance method is called for
304 : : * all comparisons. The original operator is passed to the Distance
305 : : * function in the form of its strategy number, which is available
306 : : * from the sk_strategy field, and its subtype from the sk_subtype
307 : : * field.
308 : : */
5746 tgl@sss.pgh.pa.us 309 [ + + ]:CBC 246 : for (i = 0; i < scan->numberOfOrderBys; i++)
310 : : {
311 : 123 : ScanKey skey = scan->orderByData + i;
4858 312 : 123 : FmgrInfo *finfo = &(so->giststate->distanceFn[skey->sk_attno - 1]);
313 : :
314 : : /* Check we actually have a distance function ... */
315 [ - + ]: 123 : if (!OidIsValid(finfo->fn_oid))
5746 tgl@sss.pgh.pa.us 316 [ # # ]:UBC 0 : elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
317 : : GIST_DISTANCE_PROC, skey->sk_attno,
318 : : RelationGetRelationName(scan->indexRelation));
319 : :
320 : : /*
321 : : * Look up the datatype returned by the original ordering
322 : : * operator. GiST always uses a float8 for the distance function,
323 : : * but the ordering operator could be anything else.
324 : : *
325 : : * XXX: The distance function is only allowed to be lossy if the
326 : : * ordering operator's result type is float4 or float8. Otherwise
327 : : * we don't know how to return the distance to the executor. But
328 : : * we cannot check that here, as we won't know if the distance
329 : : * function is lossy until it returns *recheck = true for the
330 : : * first time.
331 : : */
4122 heikki.linnakangas@i 332 :CBC 123 : so->orderByTypes[i] = get_func_rettype(skey->sk_func.fn_oid);
333 : :
334 : : /*
335 : : * Copy distance support function to ScanKey structure instead of
336 : : * function implementing ordering operator.
337 : : */
3859 teodor@sigaev.ru 338 : 123 : fmgr_info_copy(&(skey->sk_func), finfo, so->giststate->scanCxt);
339 : :
340 : : /* Restore prior fn_extra pointers, if not first time */
4858 tgl@sss.pgh.pa.us 341 [ + + ]: 123 : if (!first_time)
342 : 48 : skey->sk_func.fn_extra = fn_extras[i];
343 : : }
344 : :
345 [ + + ]: 123 : if (!first_time)
346 : 48 : pfree(fn_extras);
347 : : }
348 : :
349 : : /* any previous xs_hitup will have been pfree'd in context resets above */
3402 350 : 6398 : scan->xs_hitup = NULL;
10958 scrappy@hub.org 351 : 6398 : }
352 : :
353 : : void
3875 tgl@sss.pgh.pa.us 354 : 6053 : gistendscan(IndexScanDesc scan)
355 : : {
5747 356 : 6053 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
357 : :
358 : : /* Before leaving current page, deal with any killed items */
8 pg@bowt.ie 359 [ - + ]:GNC 6053 : if (so->numKilled > 0)
8 pg@bowt.ie 360 :UNC 0 : gistkillitems(scan);
361 : :
362 : : /*
363 : : * freeGISTstate is enough to clean up everything made by gistbeginscan,
364 : : * as well as the queueCxt if there is a separate context for it.
365 : : */
5746 tgl@sss.pgh.pa.us 366 :CBC 6053 : freeGISTstate(so->giststate);
10958 scrappy@hub.org 367 : 6053 : }
|
