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

Generated by: LCOV version 1.13