LCOV - code coverage report
Current view: top level - src/backend/access/spgist - spgscan.c (source / functions) Hit Total Coverage
Test: PostgreSQL 15devel Lines: 407 434 93.8 %
Date: 2021-12-09 03:08:47 Functions: 23 23 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * spgscan.c
       4             :  *    routines for scanning SP-GiST indexes
       5             :  *
       6             :  *
       7             :  * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
       8             :  * Portions Copyright (c) 1994, Regents of the University of California
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *          src/backend/access/spgist/spgscan.c
      12             :  *
      13             :  *-------------------------------------------------------------------------
      14             :  */
      15             : 
      16             : #include "postgres.h"
      17             : 
      18             : #include "access/genam.h"
      19             : #include "access/relscan.h"
      20             : #include "access/spgist_private.h"
      21             : #include "miscadmin.h"
      22             : #include "pgstat.h"
      23             : #include "storage/bufmgr.h"
      24             : #include "utils/datum.h"
      25             : #include "utils/float.h"
      26             : #include "utils/lsyscache.h"
      27             : #include "utils/memutils.h"
      28             : #include "utils/rel.h"
      29             : 
      30             : typedef void (*storeRes_func) (SpGistScanOpaque so, ItemPointer heapPtr,
      31             :                                Datum leafValue, bool isNull,
      32             :                                SpGistLeafTuple leafTuple, bool recheck,
      33             :                                bool recheckDistances, double *distances);
      34             : 
      35             : /*
      36             :  * Pairing heap comparison function for the SpGistSearchItem queue.
      37             :  * KNN-searches currently only support NULLS LAST.  So, preserve this logic
      38             :  * here.
      39             :  */
      40             : static int
      41     2945452 : pairingheap_SpGistSearchItem_cmp(const pairingheap_node *a,
      42             :                                  const pairingheap_node *b, void *arg)
      43             : {
      44     2945452 :     const SpGistSearchItem *sa = (const SpGistSearchItem *) a;
      45     2945452 :     const SpGistSearchItem *sb = (const SpGistSearchItem *) b;
      46     2945452 :     SpGistScanOpaque so = (SpGistScanOpaque) arg;
      47             :     int         i;
      48             : 
      49     2945452 :     if (sa->isNull)
      50             :     {
      51         358 :         if (!sb->isNull)
      52         330 :             return -1;
      53             :     }
      54     2945094 :     else if (sb->isNull)
      55             :     {
      56         278 :         return 1;
      57             :     }
      58             :     else
      59             :     {
      60             :         /* Order according to distance comparison */
      61     3104968 :         for (i = 0; i < so->numberOfNonNullOrderBys; i++)
      62             :         {
      63     2689958 :             if (isnan(sa->distances[i]) && isnan(sb->distances[i]))
      64           0 :                 continue;       /* NaN == NaN */
      65     2689958 :             if (isnan(sa->distances[i]))
      66           0 :                 return -1;      /* NaN > number */
      67     2689958 :             if (isnan(sb->distances[i]))
      68           0 :                 return 1;       /* number < NaN */
      69     2689958 :             if (sa->distances[i] != sb->distances[i])
      70     2529806 :                 return (sa->distances[i] < sb->distances[i]) ? 1 : -1;
      71             :         }
      72             :     }
      73             : 
      74             :     /* Leaf items go before inner pages, to ensure a depth-first search */
      75      415038 :     if (sa->isLeaf && !sb->isLeaf)
      76        2870 :         return 1;
      77      412168 :     if (!sa->isLeaf && sb->isLeaf)
      78        3186 :         return -1;
      79             : 
      80      408982 :     return 0;
      81             : }
      82             : 
      83             : static void
      84      308760 : spgFreeSearchItem(SpGistScanOpaque so, SpGistSearchItem *item)
      85             : {
      86             :     /* value is of type attType if isLeaf, else of type attLeafType */
      87             :     /* (no, that is not backwards; yes, it's confusing) */
      88      308760 :     if (!(item->isLeaf ? so->state.attType.attbyval :
      89      308760 :           so->state.attLeafType.attbyval) &&
      90      308760 :         DatumGetPointer(item->value) != NULL)
      91      195908 :         pfree(DatumGetPointer(item->value));
      92             : 
      93      308760 :     if (item->leafTuple)
      94          40 :         pfree(item->leafTuple);
      95             : 
      96      308760 :     if (item->traversalValue)
      97       29600 :         pfree(item->traversalValue);
      98             : 
      99      308760 :     pfree(item);
     100      308760 : }
     101             : 
     102             : /*
     103             :  * Add SpGistSearchItem to queue
     104             :  *
     105             :  * Called in queue context
     106             :  */
     107             : static void
     108      310606 : spgAddSearchItemToQueue(SpGistScanOpaque so, SpGistSearchItem *item)
     109             : {
     110      310606 :     pairingheap_add(so->scanQueue, &item->phNode);
     111      310606 : }
     112             : 
     113             : static SpGistSearchItem *
     114      310606 : spgAllocSearchItem(SpGistScanOpaque so, bool isnull, double *distances)
     115             : {
     116             :     /* allocate distance array only for non-NULL items */
     117             :     SpGistSearchItem *item =
     118      310606 :     palloc(SizeOfSpGistSearchItem(isnull ? 0 : so->numberOfNonNullOrderBys));
     119             : 
     120      310606 :     item->isNull = isnull;
     121             : 
     122      310606 :     if (!isnull && so->numberOfNonNullOrderBys > 0)
     123      251946 :         memcpy(item->distances, distances,
     124      251946 :                sizeof(item->distances[0]) * so->numberOfNonNullOrderBys);
     125             : 
     126      310606 :     return item;
     127             : }
     128             : 
     129             : static void
     130         656 : spgAddStartItem(SpGistScanOpaque so, bool isnull)
     131             : {
     132             :     SpGistSearchItem *startEntry =
     133         656 :     spgAllocSearchItem(so, isnull, so->zeroDistances);
     134             : 
     135         656 :     ItemPointerSet(&startEntry->heapPtr,
     136             :                    isnull ? SPGIST_NULL_BLKNO : SPGIST_ROOT_BLKNO,
     137             :                    FirstOffsetNumber);
     138         656 :     startEntry->isLeaf = false;
     139         656 :     startEntry->level = 0;
     140         656 :     startEntry->value = (Datum) 0;
     141         656 :     startEntry->leafTuple = NULL;
     142         656 :     startEntry->traversalValue = NULL;
     143         656 :     startEntry->recheck = false;
     144         656 :     startEntry->recheckDistances = false;
     145             : 
     146         656 :     spgAddSearchItemToQueue(so, startEntry);
     147         656 : }
     148             : 
     149             : /*
     150             :  * Initialize queue to search the root page, resetting
     151             :  * any previously active scan
     152             :  */
     153             : static void
     154         620 : resetSpGistScanOpaque(SpGistScanOpaque so)
     155             : {
     156             :     MemoryContext oldCtx;
     157             : 
     158         620 :     MemoryContextReset(so->traversalCxt);
     159             : 
     160         620 :     oldCtx = MemoryContextSwitchTo(so->traversalCxt);
     161             : 
     162             :     /* initialize queue only for distance-ordered scans */
     163         620 :     so->scanQueue = pairingheap_allocate(pairingheap_SpGistSearchItem_cmp, so);
     164             : 
     165         620 :     if (so->searchNulls)
     166             :         /* Add a work item to scan the null index entries */
     167          44 :         spgAddStartItem(so, true);
     168             : 
     169         620 :     if (so->searchNonNulls)
     170             :         /* Add a work item to scan the non-null index entries */
     171         612 :         spgAddStartItem(so, false);
     172             : 
     173         620 :     MemoryContextSwitchTo(oldCtx);
     174             : 
     175         620 :     if (so->numberOfOrderBys > 0)
     176             :     {
     177             :         /* Must pfree distances to avoid memory leak */
     178             :         int         i;
     179             : 
     180          60 :         for (i = 0; i < so->nPtrs; i++)
     181           8 :             if (so->distances[i])
     182           8 :                 pfree(so->distances[i]);
     183             :     }
     184             : 
     185         620 :     if (so->want_itup)
     186             :     {
     187             :         /* Must pfree reconstructed tuples to avoid memory leak */
     188             :         int         i;
     189             : 
     190          60 :         for (i = 0; i < so->nPtrs; i++)
     191          44 :             pfree(so->reconTups[i]);
     192             :     }
     193         620 :     so->iPtr = so->nPtrs = 0;
     194         620 : }
     195             : 
     196             : /*
     197             :  * Prepare scan keys in SpGistScanOpaque from caller-given scan keys
     198             :  *
     199             :  * Sets searchNulls, searchNonNulls, numberOfKeys, keyData fields of *so.
     200             :  *
     201             :  * The point here is to eliminate null-related considerations from what the
     202             :  * opclass consistent functions need to deal with.  We assume all SPGiST-
     203             :  * indexable operators are strict, so any null RHS value makes the scan
     204             :  * condition unsatisfiable.  We also pull out any IS NULL/IS NOT NULL
     205             :  * conditions; their effect is reflected into searchNulls/searchNonNulls.
     206             :  */
     207             : static void
     208         620 : spgPrepareScanKeys(IndexScanDesc scan)
     209             : {
     210         620 :     SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
     211             :     bool        qual_ok;
     212             :     bool        haveIsNull;
     213             :     bool        haveNotNull;
     214             :     int         nkeys;
     215             :     int         i;
     216             : 
     217         620 :     so->numberOfOrderBys = scan->numberOfOrderBys;
     218         620 :     so->orderByData = scan->orderByData;
     219             : 
     220         620 :     if (so->numberOfOrderBys <= 0)
     221         568 :         so->numberOfNonNullOrderBys = 0;
     222             :     else
     223             :     {
     224          52 :         int         j = 0;
     225             : 
     226             :         /*
     227             :          * Remove all NULL keys, but remember their offsets in the original
     228             :          * array.
     229             :          */
     230         116 :         for (i = 0; i < scan->numberOfOrderBys; i++)
     231             :         {
     232          64 :             ScanKey     skey = &so->orderByData[i];
     233             : 
     234          64 :             if (skey->sk_flags & SK_ISNULL)
     235           4 :                 so->nonNullOrderByOffsets[i] = -1;
     236             :             else
     237             :             {
     238          60 :                 if (i != j)
     239           4 :                     so->orderByData[j] = *skey;
     240             : 
     241          60 :                 so->nonNullOrderByOffsets[i] = j++;
     242             :             }
     243             :         }
     244             : 
     245          52 :         so->numberOfNonNullOrderBys = j;
     246             :     }
     247             : 
     248         620 :     if (scan->numberOfKeys <= 0)
     249             :     {
     250             :         /* If no quals, whole-index scan is required */
     251          36 :         so->searchNulls = true;
     252          36 :         so->searchNonNulls = true;
     253          36 :         so->numberOfKeys = 0;
     254          36 :         return;
     255             :     }
     256             : 
     257             :     /* Examine the given quals */
     258         584 :     qual_ok = true;
     259         584 :     haveIsNull = haveNotNull = false;
     260         584 :     nkeys = 0;
     261        1172 :     for (i = 0; i < scan->numberOfKeys; i++)
     262             :     {
     263         588 :         ScanKey     skey = &scan->keyData[i];
     264             : 
     265         588 :         if (skey->sk_flags & SK_SEARCHNULL)
     266           8 :             haveIsNull = true;
     267         580 :         else if (skey->sk_flags & SK_SEARCHNOTNULL)
     268          16 :             haveNotNull = true;
     269         564 :         else if (skey->sk_flags & SK_ISNULL)
     270             :         {
     271             :             /* ordinary qual with null argument - unsatisfiable */
     272           0 :             qual_ok = false;
     273           0 :             break;
     274             :         }
     275             :         else
     276             :         {
     277             :             /* ordinary qual, propagate into so->keyData */
     278         564 :             so->keyData[nkeys++] = *skey;
     279             :             /* this effectively creates a not-null requirement */
     280         564 :             haveNotNull = true;
     281             :         }
     282             :     }
     283             : 
     284             :     /* IS NULL in combination with something else is unsatisfiable */
     285         584 :     if (haveIsNull && haveNotNull)
     286           0 :         qual_ok = false;
     287             : 
     288             :     /* Emit results */
     289         584 :     if (qual_ok)
     290             :     {
     291         584 :         so->searchNulls = haveIsNull;
     292         584 :         so->searchNonNulls = haveNotNull;
     293         584 :         so->numberOfKeys = nkeys;
     294             :     }
     295             :     else
     296             :     {
     297           0 :         so->searchNulls = false;
     298           0 :         so->searchNonNulls = false;
     299           0 :         so->numberOfKeys = 0;
     300             :     }
     301             : }
     302             : 
     303             : IndexScanDesc
     304         604 : spgbeginscan(Relation rel, int keysz, int orderbysz)
     305             : {
     306             :     IndexScanDesc scan;
     307             :     SpGistScanOpaque so;
     308             :     int         i;
     309             : 
     310         604 :     scan = RelationGetIndexScan(rel, keysz, orderbysz);
     311             : 
     312         604 :     so = (SpGistScanOpaque) palloc0(sizeof(SpGistScanOpaqueData));
     313         604 :     if (keysz > 0)
     314         576 :         so->keyData = (ScanKey) palloc(sizeof(ScanKeyData) * keysz);
     315             :     else
     316          28 :         so->keyData = NULL;
     317         604 :     initSpGistState(&so->state, scan->indexRelation);
     318             : 
     319         604 :     so->tempCxt = AllocSetContextCreate(CurrentMemoryContext,
     320             :                                         "SP-GiST search temporary context",
     321             :                                         ALLOCSET_DEFAULT_SIZES);
     322         604 :     so->traversalCxt = AllocSetContextCreate(CurrentMemoryContext,
     323             :                                              "SP-GiST traversal-value context",
     324             :                                              ALLOCSET_DEFAULT_SIZES);
     325             : 
     326             :     /*
     327             :      * Set up reconTupDesc and xs_hitupdesc in case it's an index-only scan,
     328             :      * making sure that the key column is shown as being of type attType.
     329             :      * (It's rather annoying to do this work when it might be wasted, but for
     330             :      * most opclasses we can re-use the index reldesc instead of making one.)
     331             :      */
     332         604 :     so->reconTupDesc = scan->xs_hitupdesc =
     333         604 :         getSpGistTupleDesc(rel, &so->state.attType);
     334             : 
     335             :     /* Allocate various arrays needed for order-by scans */
     336         604 :     if (scan->numberOfOrderBys > 0)
     337             :     {
     338             :         /* This will be filled in spgrescan, but allocate the space here */
     339          44 :         so->orderByTypes = (Oid *)
     340          44 :             palloc(sizeof(Oid) * scan->numberOfOrderBys);
     341          44 :         so->nonNullOrderByOffsets = (int *)
     342          44 :             palloc(sizeof(int) * scan->numberOfOrderBys);
     343             : 
     344             :         /* These arrays have constant contents, so we can fill them now */
     345          44 :         so->zeroDistances = (double *)
     346          44 :             palloc(sizeof(double) * scan->numberOfOrderBys);
     347          44 :         so->infDistances = (double *)
     348          44 :             palloc(sizeof(double) * scan->numberOfOrderBys);
     349             : 
     350          92 :         for (i = 0; i < scan->numberOfOrderBys; i++)
     351             :         {
     352          48 :             so->zeroDistances[i] = 0.0;
     353          48 :             so->infDistances[i] = get_float8_infinity();
     354             :         }
     355             : 
     356          44 :         scan->xs_orderbyvals = (Datum *)
     357          44 :             palloc0(sizeof(Datum) * scan->numberOfOrderBys);
     358          44 :         scan->xs_orderbynulls = (bool *)
     359          44 :             palloc(sizeof(bool) * scan->numberOfOrderBys);
     360          44 :         memset(scan->xs_orderbynulls, true,
     361          44 :                sizeof(bool) * scan->numberOfOrderBys);
     362             :     }
     363             : 
     364         604 :     fmgr_info_copy(&so->innerConsistentFn,
     365             :                    index_getprocinfo(rel, 1, SPGIST_INNER_CONSISTENT_PROC),
     366             :                    CurrentMemoryContext);
     367             : 
     368         604 :     fmgr_info_copy(&so->leafConsistentFn,
     369             :                    index_getprocinfo(rel, 1, SPGIST_LEAF_CONSISTENT_PROC),
     370             :                    CurrentMemoryContext);
     371             : 
     372         604 :     so->indexCollation = rel->rd_indcollation[0];
     373             : 
     374         604 :     scan->opaque = so;
     375             : 
     376         604 :     return scan;
     377             : }
     378             : 
     379             : void
     380         620 : spgrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
     381             :           ScanKey orderbys, int norderbys)
     382             : {
     383         620 :     SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
     384             : 
     385             :     /* copy scankeys into local storage */
     386         620 :     if (scankey && scan->numberOfKeys > 0)
     387         584 :         memmove(scan->keyData, scankey,
     388         584 :                 scan->numberOfKeys * sizeof(ScanKeyData));
     389             : 
     390             :     /* initialize order-by data if needed */
     391         620 :     if (orderbys && scan->numberOfOrderBys > 0)
     392             :     {
     393             :         int         i;
     394             : 
     395          52 :         memmove(scan->orderByData, orderbys,
     396          52 :                 scan->numberOfOrderBys * sizeof(ScanKeyData));
     397             : 
     398         116 :         for (i = 0; i < scan->numberOfOrderBys; i++)
     399             :         {
     400          64 :             ScanKey     skey = &scan->orderByData[i];
     401             : 
     402             :             /*
     403             :              * Look up the datatype returned by the original ordering
     404             :              * operator. SP-GiST always uses a float8 for the distance
     405             :              * function, but the ordering operator could be anything else.
     406             :              *
     407             :              * XXX: The distance function is only allowed to be lossy if the
     408             :              * ordering operator's result type is float4 or float8.  Otherwise
     409             :              * we don't know how to return the distance to the executor.  But
     410             :              * we cannot check that here, as we won't know if the distance
     411             :              * function is lossy until it returns *recheck = true for the
     412             :              * first time.
     413             :              */
     414          64 :             so->orderByTypes[i] = get_func_rettype(skey->sk_func.fn_oid);
     415             :         }
     416             :     }
     417             : 
     418             :     /* preprocess scankeys, set up the representation in *so */
     419         620 :     spgPrepareScanKeys(scan);
     420             : 
     421             :     /* set up starting queue entries */
     422         620 :     resetSpGistScanOpaque(so);
     423             : 
     424             :     /* count an indexscan for stats */
     425         620 :     pgstat_count_index_scan(scan->indexRelation);
     426         620 : }
     427             : 
     428             : void
     429         604 : spgendscan(IndexScanDesc scan)
     430             : {
     431         604 :     SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
     432             : 
     433         604 :     MemoryContextDelete(so->tempCxt);
     434         604 :     MemoryContextDelete(so->traversalCxt);
     435             : 
     436         604 :     if (so->keyData)
     437         576 :         pfree(so->keyData);
     438             : 
     439         604 :     if (so->state.leafTupDesc &&
     440         604 :         so->state.leafTupDesc != RelationGetDescr(so->state.index))
     441           6 :         FreeTupleDesc(so->state.leafTupDesc);
     442             : 
     443         604 :     if (so->state.deadTupleStorage)
     444         604 :         pfree(so->state.deadTupleStorage);
     445             : 
     446         604 :     if (scan->numberOfOrderBys > 0)
     447             :     {
     448          44 :         pfree(so->orderByTypes);
     449          44 :         pfree(so->nonNullOrderByOffsets);
     450          44 :         pfree(so->zeroDistances);
     451          44 :         pfree(so->infDistances);
     452          44 :         pfree(scan->xs_orderbyvals);
     453          44 :         pfree(scan->xs_orderbynulls);
     454             :     }
     455             : 
     456         604 :     pfree(so);
     457         604 : }
     458             : 
     459             : /*
     460             :  * Leaf SpGistSearchItem constructor, called in queue context
     461             :  */
     462             : static SpGistSearchItem *
     463      243942 : spgNewHeapItem(SpGistScanOpaque so, int level, SpGistLeafTuple leafTuple,
     464             :                Datum leafValue, bool recheck, bool recheckDistances,
     465             :                bool isnull, double *distances)
     466             : {
     467      243942 :     SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
     468             : 
     469      243942 :     item->level = level;
     470      243942 :     item->heapPtr = leafTuple->heapPtr;
     471             : 
     472             :     /*
     473             :      * If we need the reconstructed value, copy it to queue cxt out of tmp
     474             :      * cxt.  Caution: the leaf_consistent method may not have supplied a value
     475             :      * if we didn't ask it to, and mildly-broken methods might supply one of
     476             :      * the wrong type.  The correct leafValue type is attType not leafType.
     477             :      */
     478      243942 :     if (so->want_itup)
     479             :     {
     480      186238 :         item->value = isnull ? (Datum) 0 :
     481      186214 :             datumCopy(leafValue, so->state.attType.attbyval,
     482      186214 :                       so->state.attType.attlen);
     483             : 
     484             :         /*
     485             :          * If we're going to need to reconstruct INCLUDE attributes, store the
     486             :          * whole leaf tuple so we can get the INCLUDE attributes out of it.
     487             :          */
     488      186238 :         if (so->state.leafTupDesc->natts > 1)
     489             :         {
     490         138 :             item->leafTuple = palloc(leafTuple->size);
     491         138 :             memcpy(item->leafTuple, leafTuple, leafTuple->size);
     492             :         }
     493             :         else
     494      186100 :             item->leafTuple = NULL;
     495             :     }
     496             :     else
     497             :     {
     498       57704 :         item->value = (Datum) 0;
     499       57704 :         item->leafTuple = NULL;
     500             :     }
     501      243942 :     item->traversalValue = NULL;
     502      243942 :     item->isLeaf = true;
     503      243942 :     item->recheck = recheck;
     504      243942 :     item->recheckDistances = recheckDistances;
     505             : 
     506      243942 :     return item;
     507             : }
     508             : 
     509             : /*
     510             :  * Test whether a leaf tuple satisfies all the scan keys
     511             :  *
     512             :  * *reportedSome is set to true if:
     513             :  *      the scan is not ordered AND the item satisfies the scankeys
     514             :  */
     515             : static bool
     516     1761642 : spgLeafTest(SpGistScanOpaque so, SpGistSearchItem *item,
     517             :             SpGistLeafTuple leafTuple, bool isnull,
     518             :             bool *reportedSome, storeRes_func storeRes)
     519             : {
     520             :     Datum       leafValue;
     521             :     double     *distances;
     522             :     bool        result;
     523             :     bool        recheck;
     524             :     bool        recheckDistances;
     525             : 
     526     1761642 :     if (isnull)
     527             :     {
     528             :         /* Should not have arrived on a nulls page unless nulls are wanted */
     529             :         Assert(so->searchNulls);
     530          80 :         leafValue = (Datum) 0;
     531          80 :         distances = NULL;
     532          80 :         recheck = false;
     533          80 :         recheckDistances = false;
     534          80 :         result = true;
     535             :     }
     536             :     else
     537             :     {
     538             :         spgLeafConsistentIn in;
     539             :         spgLeafConsistentOut out;
     540             : 
     541             :         /* use temp context for calling leaf_consistent */
     542     1761562 :         MemoryContext oldCxt = MemoryContextSwitchTo(so->tempCxt);
     543             : 
     544     1761562 :         in.scankeys = so->keyData;
     545     1761562 :         in.nkeys = so->numberOfKeys;
     546     1761562 :         in.orderbys = so->orderByData;
     547     1761562 :         in.norderbys = so->numberOfNonNullOrderBys;
     548             :         Assert(!item->isLeaf);   /* else reconstructedValue would be wrong type */
     549     1761562 :         in.reconstructedValue = item->value;
     550     1761562 :         in.traversalValue = item->traversalValue;
     551     1761562 :         in.level = item->level;
     552     1761562 :         in.returnData = so->want_itup;
     553     1761562 :         in.leafDatum = SGLTDATUM(leafTuple, &so->state);
     554             : 
     555     1761562 :         out.leafValue = (Datum) 0;
     556     1761562 :         out.recheck = false;
     557     1761562 :         out.distances = NULL;
     558     1761562 :         out.recheckDistances = false;
     559             : 
     560     1761562 :         result = DatumGetBool(FunctionCall2Coll(&so->leafConsistentFn,
     561             :                                                 so->indexCollation,
     562             :                                                 PointerGetDatum(&in),
     563             :                                                 PointerGetDatum(&out)));
     564     1761562 :         recheck = out.recheck;
     565     1761562 :         recheckDistances = out.recheckDistances;
     566     1761562 :         leafValue = out.leafValue;
     567     1761562 :         distances = out.distances;
     568             : 
     569     1761562 :         MemoryContextSwitchTo(oldCxt);
     570             :     }
     571             : 
     572     1761642 :     if (result)
     573             :     {
     574             :         /* item passes the scankeys */
     575     1374166 :         if (so->numberOfNonNullOrderBys > 0)
     576             :         {
     577             :             /* the scan is ordered -> add the item to the queue */
     578      243942 :             MemoryContext oldCxt = MemoryContextSwitchTo(so->traversalCxt);
     579      243942 :             SpGistSearchItem *heapItem = spgNewHeapItem(so, item->level,
     580             :                                                         leafTuple,
     581             :                                                         leafValue,
     582             :                                                         recheck,
     583             :                                                         recheckDistances,
     584             :                                                         isnull,
     585             :                                                         distances);
     586             : 
     587      243942 :             spgAddSearchItemToQueue(so, heapItem);
     588             : 
     589      243942 :             MemoryContextSwitchTo(oldCxt);
     590             :         }
     591             :         else
     592             :         {
     593             :             /* non-ordered scan, so report the item right away */
     594             :             Assert(!recheckDistances);
     595     1130224 :             storeRes(so, &leafTuple->heapPtr, leafValue, isnull,
     596             :                      leafTuple, recheck, false, NULL);
     597     1130224 :             *reportedSome = true;
     598             :         }
     599             :     }
     600             : 
     601     1761642 :     return result;
     602             : }
     603             : 
     604             : /* A bundle initializer for inner_consistent methods */
     605             : static void
     606       16724 : spgInitInnerConsistentIn(spgInnerConsistentIn *in,
     607             :                          SpGistScanOpaque so,
     608             :                          SpGistSearchItem *item,
     609             :                          SpGistInnerTuple innerTuple)
     610             : {
     611       16724 :     in->scankeys = so->keyData;
     612       16724 :     in->orderbys = so->orderByData;
     613       16724 :     in->nkeys = so->numberOfKeys;
     614       16724 :     in->norderbys = so->numberOfNonNullOrderBys;
     615             :     Assert(!item->isLeaf);       /* else reconstructedValue would be wrong type */
     616       16724 :     in->reconstructedValue = item->value;
     617       16724 :     in->traversalMemoryContext = so->traversalCxt;
     618       16724 :     in->traversalValue = item->traversalValue;
     619       16724 :     in->level = item->level;
     620       16724 :     in->returnData = so->want_itup;
     621       16724 :     in->allTheSame = innerTuple->allTheSame;
     622       16724 :     in->hasPrefix = (innerTuple->prefixSize > 0);
     623       16724 :     in->prefixDatum = SGITDATUM(innerTuple, &so->state);
     624       16724 :     in->nNodes = innerTuple->nNodes;
     625       16724 :     in->nodeLabels = spgExtractNodeLabels(&so->state, innerTuple);
     626       16724 : }
     627             : 
     628             : static SpGistSearchItem *
     629       66008 : spgMakeInnerItem(SpGistScanOpaque so,
     630             :                  SpGistSearchItem *parentItem,
     631             :                  SpGistNodeTuple tuple,
     632             :                  spgInnerConsistentOut *out, int i, bool isnull,
     633             :                  double *distances)
     634             : {
     635       66008 :     SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
     636             : 
     637       66008 :     item->heapPtr = tuple->t_tid;
     638      163168 :     item->level = out->levelAdds ? parentItem->level + out->levelAdds[i]
     639       66008 :         : parentItem->level;
     640             : 
     641             :     /* Must copy value out of temp context */
     642             :     /* (recall that reconstructed values are of type leafType) */
     643      132016 :     item->value = out->reconstructedValues
     644       11400 :         ? datumCopy(out->reconstructedValues[i],
     645       11400 :                     so->state.attLeafType.attbyval,
     646       11400 :                     so->state.attLeafType.attlen)
     647       66008 :         : (Datum) 0;
     648             : 
     649       66008 :     item->leafTuple = NULL;
     650             : 
     651             :     /*
     652             :      * Elements of out.traversalValues should be allocated in
     653             :      * in.traversalMemoryContext, which is actually a long lived context of
     654             :      * index scan.
     655             :      */
     656       66008 :     item->traversalValue =
     657       66008 :         out->traversalValues ? out->traversalValues[i] : NULL;
     658             : 
     659       66008 :     item->isLeaf = false;
     660       66008 :     item->recheck = false;
     661       66008 :     item->recheckDistances = false;
     662             : 
     663       66008 :     return item;
     664             : }
     665             : 
     666             : static void
     667       16724 : spgInnerTest(SpGistScanOpaque so, SpGistSearchItem *item,
     668             :              SpGistInnerTuple innerTuple, bool isnull)
     669             : {
     670       16724 :     MemoryContext oldCxt = MemoryContextSwitchTo(so->tempCxt);
     671             :     spgInnerConsistentOut out;
     672       16724 :     int         nNodes = innerTuple->nNodes;
     673             :     int         i;
     674             : 
     675       16724 :     memset(&out, 0, sizeof(out));
     676             : 
     677       16724 :     if (!isnull)
     678             :     {
     679             :         spgInnerConsistentIn in;
     680             : 
     681       16724 :         spgInitInnerConsistentIn(&in, so, item, innerTuple);
     682             : 
     683             :         /* use user-defined inner consistent method */
     684       16724 :         FunctionCall2Coll(&so->innerConsistentFn,
     685             :                           so->indexCollation,
     686             :                           PointerGetDatum(&in),
     687             :                           PointerGetDatum(&out));
     688             :     }
     689             :     else
     690             :     {
     691             :         /* force all children to be visited */
     692           0 :         out.nNodes = nNodes;
     693           0 :         out.nodeNumbers = (int *) palloc(sizeof(int) * nNodes);
     694           0 :         for (i = 0; i < nNodes; i++)
     695           0 :             out.nodeNumbers[i] = i;
     696             :     }
     697             : 
     698             :     /* If allTheSame, they should all or none of them match */
     699       16724 :     if (innerTuple->allTheSame && out.nNodes != 0 && out.nNodes != nNodes)
     700           0 :         elog(ERROR, "inconsistent inner_consistent results for allTheSame inner tuple");
     701             : 
     702       16724 :     if (out.nNodes)
     703             :     {
     704             :         /* collect node pointers */
     705             :         SpGistNodeTuple node;
     706       16724 :         SpGistNodeTuple *nodes = (SpGistNodeTuple *) palloc(sizeof(SpGistNodeTuple) * nNodes);
     707             : 
     708      154356 :         SGITITERATE(innerTuple, i, node)
     709             :         {
     710      137632 :             nodes[i] = node;
     711             :         }
     712             : 
     713       16724 :         MemoryContextSwitchTo(so->traversalCxt);
     714             : 
     715      127436 :         for (i = 0; i < out.nNodes; i++)
     716             :         {
     717      110712 :             int         nodeN = out.nodeNumbers[i];
     718             :             SpGistSearchItem *innerItem;
     719             :             double     *distances;
     720             : 
     721             :             Assert(nodeN >= 0 && nodeN < nNodes);
     722             : 
     723      110712 :             node = nodes[nodeN];
     724             : 
     725      110712 :             if (!ItemPointerIsValid(&node->t_tid))
     726       44704 :                 continue;
     727             : 
     728             :             /*
     729             :              * Use infinity distances if innerConsistentFn() failed to return
     730             :              * them or if is a NULL item (their distances are really unused).
     731             :              */
     732       66008 :             distances = out.distances ? out.distances[i] : so->infDistances;
     733             : 
     734       66008 :             innerItem = spgMakeInnerItem(so, item, node, &out, i, isnull,
     735             :                                          distances);
     736             : 
     737       66008 :             spgAddSearchItemToQueue(so, innerItem);
     738             :         }
     739             :     }
     740             : 
     741       16724 :     MemoryContextSwitchTo(oldCxt);
     742       16724 : }
     743             : 
     744             : /* Returns a next item in an (ordered) scan or null if the index is exhausted */
     745             : static SpGistSearchItem *
     746      309352 : spgGetNextQueueItem(SpGistScanOpaque so)
     747             : {
     748      309352 :     if (pairingheap_is_empty(so->scanQueue))
     749         592 :         return NULL;            /* Done when both heaps are empty */
     750             : 
     751             :     /* Return item; caller is responsible to pfree it */
     752      308760 :     return (SpGistSearchItem *) pairingheap_remove_first(so->scanQueue);
     753             : }
     754             : 
     755             : enum SpGistSpecialOffsetNumbers
     756             : {
     757             :     SpGistBreakOffsetNumber = InvalidOffsetNumber,
     758             :     SpGistRedirectOffsetNumber = MaxOffsetNumber + 1,
     759             :     SpGistErrorOffsetNumber = MaxOffsetNumber + 2
     760             : };
     761             : 
     762             : static OffsetNumber
     763     1761642 : spgTestLeafTuple(SpGistScanOpaque so,
     764             :                  SpGistSearchItem *item,
     765             :                  Page page, OffsetNumber offset,
     766             :                  bool isnull, bool isroot,
     767             :                  bool *reportedSome,
     768             :                  storeRes_func storeRes)
     769             : {
     770     1761642 :     SpGistLeafTuple leafTuple = (SpGistLeafTuple)
     771     1761642 :     PageGetItem(page, PageGetItemId(page, offset));
     772             : 
     773     1761642 :     if (leafTuple->tupstate != SPGIST_LIVE)
     774             :     {
     775           0 :         if (!isroot)            /* all tuples on root should be live */
     776             :         {
     777           0 :             if (leafTuple->tupstate == SPGIST_REDIRECT)
     778             :             {
     779             :                 /* redirection tuple should be first in chain */
     780             :                 Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
     781             :                 /* transfer attention to redirect point */
     782           0 :                 item->heapPtr = ((SpGistDeadTuple) leafTuple)->pointer;
     783             :                 Assert(ItemPointerGetBlockNumber(&item->heapPtr) != SPGIST_METAPAGE_BLKNO);
     784           0 :                 return SpGistRedirectOffsetNumber;
     785             :             }
     786             : 
     787           0 :             if (leafTuple->tupstate == SPGIST_DEAD)
     788             :             {
     789             :                 /* dead tuple should be first in chain */
     790             :                 Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
     791             :                 /* No live entries on this page */
     792             :                 Assert(SGLT_GET_NEXTOFFSET(leafTuple) == InvalidOffsetNumber);
     793           0 :                 return SpGistBreakOffsetNumber;
     794             :             }
     795             :         }
     796             : 
     797             :         /* We should not arrive at a placeholder */
     798           0 :         elog(ERROR, "unexpected SPGiST tuple state: %d", leafTuple->tupstate);
     799             :         return SpGistErrorOffsetNumber;
     800             :     }
     801             : 
     802             :     Assert(ItemPointerIsValid(&leafTuple->heapPtr));
     803             : 
     804     1761642 :     spgLeafTest(so, item, leafTuple, isnull, reportedSome, storeRes);
     805             : 
     806     1761642 :     return SGLT_GET_NEXTOFFSET(leafTuple);
     807             : }
     808             : 
     809             : /*
     810             :  * Walk the tree and report all tuples passing the scan quals to the storeRes
     811             :  * subroutine.
     812             :  *
     813             :  * If scanWholeIndex is true, we'll do just that.  If not, we'll stop at the
     814             :  * next page boundary once we have reported at least one tuple.
     815             :  */
     816             : static void
     817      251522 : spgWalk(Relation index, SpGistScanOpaque so, bool scanWholeIndex,
     818             :         storeRes_func storeRes, Snapshot snapshot)
     819             : {
     820      251522 :     Buffer      buffer = InvalidBuffer;
     821      251522 :     bool        reportedSome = false;
     822             : 
     823      560282 :     while (scanWholeIndex || !reportedSome)
     824             :     {
     825      309352 :         SpGistSearchItem *item = spgGetNextQueueItem(so);
     826             : 
     827      309352 :         if (item == NULL)
     828         592 :             break;              /* No more items in queue -> done */
     829             : 
     830      308760 : redirect:
     831             :         /* Check for interrupts, just in case of infinite loop */
     832      308760 :         CHECK_FOR_INTERRUPTS();
     833             : 
     834      308760 :         if (item->isLeaf)
     835             :         {
     836             :             /* We store heap items in the queue only in case of ordered search */
     837             :             Assert(so->numberOfNonNullOrderBys > 0);
     838      242236 :             storeRes(so, &item->heapPtr, item->value, item->isNull,
     839      242236 :                      item->leafTuple, item->recheck,
     840      242236 :                      item->recheckDistances, item->distances);
     841      242236 :             reportedSome = true;
     842             :         }
     843             :         else
     844             :         {
     845       66524 :             BlockNumber blkno = ItemPointerGetBlockNumber(&item->heapPtr);
     846       66524 :             OffsetNumber offset = ItemPointerGetOffsetNumber(&item->heapPtr);
     847             :             Page        page;
     848             :             bool        isnull;
     849             : 
     850       66524 :             if (buffer == InvalidBuffer)
     851             :             {
     852       13224 :                 buffer = ReadBuffer(index, blkno);
     853       13224 :                 LockBuffer(buffer, BUFFER_LOCK_SHARE);
     854             :             }
     855       53300 :             else if (blkno != BufferGetBlockNumber(buffer))
     856             :             {
     857       37008 :                 UnlockReleaseBuffer(buffer);
     858       37008 :                 buffer = ReadBuffer(index, blkno);
     859       37008 :                 LockBuffer(buffer, BUFFER_LOCK_SHARE);
     860             :             }
     861             : 
     862             :             /* else new pointer points to the same page, no work needed */
     863             : 
     864       66524 :             page = BufferGetPage(buffer);
     865       66524 :             TestForOldSnapshot(snapshot, index, page);
     866             : 
     867       66524 :             isnull = SpGistPageStoresNulls(page) ? true : false;
     868             : 
     869       66524 :             if (SpGistPageIsLeaf(page))
     870             :             {
     871             :                 /* Page is a leaf - that is, all it's tuples are heap items */
     872       49800 :                 OffsetNumber max = PageGetMaxOffsetNumber(page);
     873             : 
     874       49800 :                 if (SpGistBlockIsRoot(blkno))
     875             :                 {
     876             :                     /* When root is a leaf, examine all its tuples */
     877        4084 :                     for (offset = FirstOffsetNumber; offset <= max; offset++)
     878        3952 :                         (void) spgTestLeafTuple(so, item, page, offset,
     879             :                                                 isnull, true,
     880             :                                                 &reportedSome, storeRes);
     881             :                 }
     882             :                 else
     883             :                 {
     884             :                     /* Normal case: just examine the chain we arrived at */
     885     1807358 :                     while (offset != InvalidOffsetNumber)
     886             :                     {
     887             :                         Assert(offset >= FirstOffsetNumber && offset <= max);
     888     1757690 :                         offset = spgTestLeafTuple(so, item, page, offset,
     889             :                                                   isnull, false,
     890             :                                                   &reportedSome, storeRes);
     891     1757690 :                         if (offset == SpGistRedirectOffsetNumber)
     892           0 :                             goto redirect;
     893             :                     }
     894             :                 }
     895             :             }
     896             :             else                /* page is inner */
     897             :             {
     898       16724 :                 SpGistInnerTuple innerTuple = (SpGistInnerTuple)
     899       16724 :                 PageGetItem(page, PageGetItemId(page, offset));
     900             : 
     901       16724 :                 if (innerTuple->tupstate != SPGIST_LIVE)
     902             :                 {
     903           0 :                     if (innerTuple->tupstate == SPGIST_REDIRECT)
     904             :                     {
     905             :                         /* transfer attention to redirect point */
     906           0 :                         item->heapPtr = ((SpGistDeadTuple) innerTuple)->pointer;
     907             :                         Assert(ItemPointerGetBlockNumber(&item->heapPtr) !=
     908             :                                SPGIST_METAPAGE_BLKNO);
     909           0 :                         goto redirect;
     910             :                     }
     911           0 :                     elog(ERROR, "unexpected SPGiST tuple state: %d",
     912             :                          innerTuple->tupstate);
     913             :                 }
     914             : 
     915       16724 :                 spgInnerTest(so, item, innerTuple, isnull);
     916             :             }
     917             :         }
     918             : 
     919             :         /* done with this scan item */
     920      308760 :         spgFreeSearchItem(so, item);
     921             :         /* clear temp context before proceeding to the next one */
     922      308760 :         MemoryContextReset(so->tempCxt);
     923             :     }
     924             : 
     925      251522 :     if (buffer != InvalidBuffer)
     926       13224 :         UnlockReleaseBuffer(buffer);
     927      251522 : }
     928             : 
     929             : 
     930             : /* storeRes subroutine for getbitmap case */
     931             : static void
     932      701476 : storeBitmap(SpGistScanOpaque so, ItemPointer heapPtr,
     933             :             Datum leafValue, bool isnull,
     934             :             SpGistLeafTuple leafTuple, bool recheck,
     935             :             bool recheckDistances, double *distances)
     936             : {
     937             :     Assert(!recheckDistances && !distances);
     938      701476 :     tbm_add_tuples(so->tbm, heapPtr, 1, recheck);
     939      701476 :     so->ntids++;
     940      701476 : }
     941             : 
     942             : int64
     943         232 : spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
     944             : {
     945         232 :     SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
     946             : 
     947             :     /* Copy want_itup to *so so we don't need to pass it around separately */
     948         232 :     so->want_itup = false;
     949             : 
     950         232 :     so->tbm = tbm;
     951         232 :     so->ntids = 0;
     952             : 
     953         232 :     spgWalk(scan->indexRelation, so, true, storeBitmap, scan->xs_snapshot);
     954             : 
     955         232 :     return so->ntids;
     956             : }
     957             : 
     958             : /* storeRes subroutine for gettuple case */
     959             : static void
     960      670984 : storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr,
     961             :               Datum leafValue, bool isnull,
     962             :               SpGistLeafTuple leafTuple, bool recheck,
     963             :               bool recheckDistances, double *nonNullDistances)
     964             : {
     965             :     Assert(so->nPtrs < MaxIndexTuplesPerPage);
     966      670984 :     so->heapPtrs[so->nPtrs] = *heapPtr;
     967      670984 :     so->recheck[so->nPtrs] = recheck;
     968      670984 :     so->recheckDistances[so->nPtrs] = recheckDistances;
     969             : 
     970      670984 :     if (so->numberOfOrderBys > 0)
     971             :     {
     972      242236 :         if (isnull || so->numberOfNonNullOrderBys <= 0)
     973          32 :             so->distances[so->nPtrs] = NULL;
     974             :         else
     975             :         {
     976             :             IndexOrderByDistance *distances =
     977      242204 :             palloc(sizeof(distances[0]) * so->numberOfOrderBys);
     978             :             int         i;
     979             : 
     980      484420 :             for (i = 0; i < so->numberOfOrderBys; i++)
     981             :             {
     982      242216 :                 int         offset = so->nonNullOrderByOffsets[i];
     983             : 
     984      242216 :                 if (offset >= 0)
     985             :                 {
     986             :                     /* Copy non-NULL distance value */
     987      242212 :                     distances[i].value = nonNullDistances[offset];
     988      242212 :                     distances[i].isnull = false;
     989             :                 }
     990             :                 else
     991             :                 {
     992             :                     /* Set distance's NULL flag. */
     993           4 :                     distances[i].value = 0.0;
     994           4 :                     distances[i].isnull = true;
     995             :                 }
     996             :             }
     997             : 
     998      242204 :             so->distances[so->nPtrs] = distances;
     999             :         }
    1000             :     }
    1001             : 
    1002      670984 :     if (so->want_itup)
    1003             :     {
    1004             :         /*
    1005             :          * Reconstruct index data.  We have to copy the datum out of the temp
    1006             :          * context anyway, so we may as well create the tuple here.
    1007             :          */
    1008             :         Datum       leafDatums[INDEX_MAX_KEYS];
    1009             :         bool        leafIsnulls[INDEX_MAX_KEYS];
    1010             : 
    1011             :         /* We only need to deform the old tuple if it has INCLUDE attributes */
    1012      612960 :         if (so->state.leafTupDesc->natts > 1)
    1013          76 :             spgDeformLeafTuple(leafTuple, so->state.leafTupDesc,
    1014             :                                leafDatums, leafIsnulls, isnull);
    1015             : 
    1016      612960 :         leafDatums[spgKeyColumn] = leafValue;
    1017      612960 :         leafIsnulls[spgKeyColumn] = isnull;
    1018             : 
    1019      612960 :         so->reconTups[so->nPtrs] = heap_form_tuple(so->reconTupDesc,
    1020             :                                                    leafDatums,
    1021             :                                                    leafIsnulls);
    1022             :     }
    1023      670984 :     so->nPtrs++;
    1024      670984 : }
    1025             : 
    1026             : bool
    1027      671280 : spggettuple(IndexScanDesc scan, ScanDirection dir)
    1028             : {
    1029      671280 :     SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
    1030             : 
    1031      671280 :     if (dir != ForwardScanDirection)
    1032           0 :         elog(ERROR, "SP-GiST only supports forward scan direction");
    1033             : 
    1034             :     /* Copy want_itup to *so so we don't need to pass it around separately */
    1035      671280 :     so->want_itup = scan->xs_want_itup;
    1036             : 
    1037             :     for (;;)
    1038             :     {
    1039      922210 :         if (so->iPtr < so->nPtrs)
    1040             :         {
    1041             :             /* continuing to return reported tuples */
    1042      670920 :             scan->xs_heaptid = so->heapPtrs[so->iPtr];
    1043      670920 :             scan->xs_recheck = so->recheck[so->iPtr];
    1044      670920 :             scan->xs_hitup = so->reconTups[so->iPtr];
    1045             : 
    1046      670920 :             if (so->numberOfOrderBys > 0)
    1047      242236 :                 index_store_float8_orderby_distances(scan, so->orderByTypes,
    1048      242236 :                                                      so->distances[so->iPtr],
    1049      242236 :                                                      so->recheckDistances[so->iPtr]);
    1050      670920 :             so->iPtr++;
    1051      670920 :             return true;
    1052             :         }
    1053             : 
    1054      251290 :         if (so->numberOfOrderBys > 0)
    1055             :         {
    1056             :             /* Must pfree distances to avoid memory leak */
    1057             :             int         i;
    1058             : 
    1059      484492 :             for (i = 0; i < so->nPtrs; i++)
    1060      242220 :                 if (so->distances[i])
    1061      242188 :                     pfree(so->distances[i]);
    1062             :         }
    1063             : 
    1064      251290 :         if (so->want_itup)
    1065             :         {
    1066             :             /* Must pfree reconstructed tuples to avoid memory leak */
    1067             :             int         i;
    1068             : 
    1069      806350 :             for (i = 0; i < so->nPtrs; i++)
    1070      612868 :                 pfree(so->reconTups[i]);
    1071             :         }
    1072      251290 :         so->iPtr = so->nPtrs = 0;
    1073             : 
    1074      251290 :         spgWalk(scan->indexRelation, so, false, storeGettuple,
    1075             :                 scan->xs_snapshot);
    1076             : 
    1077      251290 :         if (so->nPtrs == 0)
    1078         360 :             break;              /* must have completed scan */
    1079             :     }
    1080             : 
    1081         360 :     return false;
    1082             : }
    1083             : 
    1084             : bool
    1085        1236 : spgcanreturn(Relation index, int attno)
    1086             : {
    1087             :     SpGistCache *cache;
    1088             : 
    1089             :     /* INCLUDE attributes can always be fetched for index-only scans */
    1090        1236 :     if (attno > 1)
    1091          24 :         return true;
    1092             : 
    1093             :     /* We can do it if the opclass config function says so */
    1094        1212 :     cache = spgGetCache(index);
    1095             : 
    1096        1212 :     return cache->config.canReturnData;
    1097             : }

Generated by: LCOV version 1.14