LCOV - code coverage report
Current view: top level - src/backend/access/spgist - spgscan.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 385 412 93.4 %
Date: 2019-09-22 07:07:17 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-2019, 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     2942166 : pairingheap_SpGistSearchItem_cmp(const pairingheap_node *a,
      40             :                                  const pairingheap_node *b, void *arg)
      41             : {
      42     2942166 :     const SpGistSearchItem *sa = (const SpGistSearchItem *) a;
      43     2942166 :     const SpGistSearchItem *sb = (const SpGistSearchItem *) b;
      44     2942166 :     SpGistScanOpaque so = (SpGistScanOpaque) arg;
      45             :     int         i;
      46             : 
      47     2942166 :     if (sa->isNull)
      48             :     {
      49         362 :         if (!sb->isNull)
      50         334 :             return -1;
      51             :     }
      52     2941804 :     else if (sb->isNull)
      53             :     {
      54         344 :         return 1;
      55             :     }
      56             :     else
      57             :     {
      58             :         /* Order according to distance comparison */
      59     3101360 :         for (i = 0; i < so->numberOfOrderBys; i++)
      60             :         {
      61     2688274 :             if (isnan(sa->distances[i]) && isnan(sb->distances[i]))
      62           0 :                 continue;       /* NaN == NaN */
      63     2688274 :             if (isnan(sa->distances[i]))
      64           0 :                 return -1;      /* NaN > number */
      65     2688274 :             if (isnan(sb->distances[i]))
      66           0 :                 return 1;       /* number < NaN */
      67     2688274 :             if (sa->distances[i] != sb->distances[i])
      68     2528374 :                 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      413114 :     if (sa->isLeaf && !sb->isLeaf)
      74        2814 :         return 1;
      75      410300 :     if (!sa->isLeaf && sb->isLeaf)
      76        3188 :         return -1;
      77             : 
      78      407112 :     return 0;
      79             : }
      80             : 
      81             : static void
      82      308976 : spgFreeSearchItem(SpGistScanOpaque so, SpGistSearchItem *item)
      83             : {
      84      617952 :     if (!so->state.attLeafType.attbyval &&
      85      308976 :         DatumGetPointer(item->value) != NULL)
      86      253348 :         pfree(DatumGetPointer(item->value));
      87             : 
      88      308976 :     if (item->traversalValue)
      89       29592 :         pfree(item->traversalValue);
      90             : 
      91      308976 :     pfree(item);
      92      308976 : }
      93             : 
      94             : /*
      95             :  * Add SpGistSearchItem to queue
      96             :  *
      97             :  * Called in queue context
      98             :  */
      99             : static void
     100      310700 : spgAddSearchItemToQueue(SpGistScanOpaque so, SpGistSearchItem *item)
     101             : {
     102      310700 :     pairingheap_add(so->scanQueue, &item->phNode);
     103      310700 : }
     104             : 
     105             : static SpGistSearchItem *
     106      310700 : spgAllocSearchItem(SpGistScanOpaque so, bool isnull, double *distances)
     107             : {
     108             :     /* allocate distance array only for non-NULL items */
     109      310700 :     SpGistSearchItem *item =
     110      310700 :     palloc(SizeOfSpGistSearchItem(isnull ? 0 : so->numberOfNonNullOrderBys));
     111             : 
     112      310700 :     item->isNull = isnull;
     113             : 
     114      310700 :     if (!isnull && so->numberOfNonNullOrderBys > 0)
     115      251708 :         memcpy(item->distances, distances,
     116      251708 :                sizeof(item->distances[0]) * so->numberOfNonNullOrderBys);
     117             : 
     118      310700 :     return item;
     119             : }
     120             : 
     121             : static void
     122         628 : spgAddStartItem(SpGistScanOpaque so, bool isnull)
     123             : {
     124         628 :     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      487576 :     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     1757548 : 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     1757548 :     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     1757468 :         MemoryContext oldCxt = MemoryContextSwitchTo(so->tempCxt);
     495             : 
     496     1757468 :         in.scankeys = so->keyData;
     497     1757468 :         in.nkeys = so->numberOfKeys;
     498     1757468 :         in.orderbys = so->orderByData;
     499     1757468 :         in.norderbys = so->numberOfNonNullOrderBys;
     500     1757468 :         in.reconstructedValue = item->value;
     501     1757468 :         in.traversalValue = item->traversalValue;
     502     1757468 :         in.level = item->level;
     503     1757468 :         in.returnData = so->want_itup;
     504     1757468 :         in.leafDatum = SGLTDATUM(leafTuple, &so->state);
     505             : 
     506     1757468 :         out.leafValue = (Datum) 0;
     507     1757468 :         out.recheck = false;
     508     1757468 :         out.distances = NULL;
     509     1757468 :         out.recheckDistances = false;
     510             : 
     511     1757468 :         result = DatumGetBool(FunctionCall2Coll(&so->leafConsistentFn,
     512             :                                                 so->indexCollation,
     513             :                                                 PointerGetDatum(&in),
     514             :                                                 PointerGetDatum(&out)));
     515     1757468 :         recheck = out.recheck;
     516     1757468 :         recheckDistances = out.recheckDistances;
     517     1757468 :         leafValue = out.leafValue;
     518     1757468 :         distances = out.distances;
     519             : 
     520     1757468 :         MemoryContextSwitchTo(oldCxt);
     521             :     }
     522             : 
     523     1757548 :     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     1757548 :     return result;
     553             : }
     554             : 
     555             : /* A bundle initializer for inner_consistent methods */
     556             : static void
     557       16988 : spgInitInnerConsistentIn(spgInnerConsistentIn *in,
     558             :                          SpGistScanOpaque so,
     559             :                          SpGistSearchItem *item,
     560             :                          SpGistInnerTuple innerTuple)
     561             : {
     562       16988 :     in->scankeys = so->keyData;
     563       16988 :     in->orderbys = so->orderByData;
     564       16988 :     in->nkeys = so->numberOfKeys;
     565       16988 :     in->norderbys = so->numberOfNonNullOrderBys;
     566       16988 :     in->reconstructedValue = item->value;
     567       16988 :     in->traversalMemoryContext = so->traversalCxt;
     568       16988 :     in->traversalValue = item->traversalValue;
     569       16988 :     in->level = item->level;
     570       16988 :     in->returnData = so->want_itup;
     571       16988 :     in->allTheSame = innerTuple->allTheSame;
     572       16988 :     in->hasPrefix = (innerTuple->prefixSize > 0);
     573       16988 :     in->prefixDatum = SGITDATUM(innerTuple, &so->state);
     574       16988 :     in->nNodes = innerTuple->nNodes;
     575       16988 :     in->nodeLabels = spgExtractNodeLabels(&so->state, innerTuple);
     576       16988 : }
     577             : 
     578             : static SpGistSearchItem *
     579       66268 : spgMakeInnerItem(SpGistScanOpaque so,
     580             :                  SpGistSearchItem *parentItem,
     581             :                  SpGistNodeTuple tuple,
     582             :                  spgInnerConsistentOut *out, int i, bool isnull,
     583             :                  double *distances)
     584             : {
     585       66268 :     SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
     586             : 
     587       66268 :     item->heapPtr = tuple->t_tid;
     588      163440 :     item->level = out->levelAdds ? parentItem->level + out->levelAdds[i]
     589       97172 :         : parentItem->level;
     590             : 
     591             :     /* Must copy value out of temp context */
     592      132536 :     item->value = out->reconstructedValues
     593       22368 :         ? datumCopy(out->reconstructedValues[i],
     594       11184 :                     so->state.attLeafType.attbyval,
     595       11184 :                     so->state.attLeafType.attlen)
     596       77452 :         : (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       66268 :     item->traversalValue =
     604       66268 :         out->traversalValues ? out->traversalValues[i] : NULL;
     605             : 
     606       66268 :     item->isLeaf = false;
     607       66268 :     item->recheck = false;
     608       66268 :     item->recheckDistances = false;
     609             : 
     610       66268 :     return item;
     611             : }
     612             : 
     613             : static void
     614       16988 : spgInnerTest(SpGistScanOpaque so, SpGistSearchItem *item,
     615             :              SpGistInnerTuple innerTuple, bool isnull)
     616             : {
     617       16988 :     MemoryContext oldCxt = MemoryContextSwitchTo(so->tempCxt);
     618             :     spgInnerConsistentOut out;
     619       16988 :     int         nNodes = innerTuple->nNodes;
     620             :     int         i;
     621             : 
     622       16988 :     memset(&out, 0, sizeof(out));
     623             : 
     624       16988 :     if (!isnull)
     625             :     {
     626             :         spgInnerConsistentIn in;
     627             : 
     628       16988 :         spgInitInnerConsistentIn(&in, so, item, innerTuple);
     629             : 
     630             :         /* use user-defined inner consistent method */
     631       16988 :         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       16988 :     if (innerTuple->allTheSame && out.nNodes != 0 && out.nNodes != nNodes)
     647           0 :         elog(ERROR, "inconsistent inner_consistent results for allTheSame inner tuple");
     648             : 
     649       16988 :     if (out.nNodes)
     650             :     {
     651             :         /* collect node pointers */
     652             :         SpGistNodeTuple node;
     653       16988 :         SpGistNodeTuple *nodes = (SpGistNodeTuple *) palloc(
     654             :                                                             sizeof(SpGistNodeTuple) * nNodes);
     655             : 
     656      155168 :         SGITITERATE(innerTuple, i, node)
     657             :         {
     658      138180 :             nodes[i] = node;
     659             :         }
     660             : 
     661       16988 :         MemoryContextSwitchTo(so->traversalCxt);
     662             : 
     663      128600 :         for (i = 0; i < out.nNodes; i++)
     664             :         {
     665      111612 :             int         nodeN = out.nodeNumbers[i];
     666             :             SpGistSearchItem *innerItem;
     667             :             double     *distances;
     668             : 
     669             :             Assert(nodeN >= 0 && nodeN < nNodes);
     670             : 
     671      111612 :             node = nodes[nodeN];
     672             : 
     673      111612 :             if (!ItemPointerIsValid(&node->t_tid))
     674       45344 :                 continue;
     675             : 
     676             :             /*
     677             :              * Use infinity distances if innerConsistentFn() failed to return
     678             :              * them or if is a NULL item (their distances are really unused).
     679             :              */
     680       66268 :             distances = out.distances ? out.distances[i] : so->infDistances;
     681             : 
     682       66268 :             innerItem = spgMakeInnerItem(so, item, node, &out, i, isnull,
     683             :                                          distances);
     684             : 
     685       66268 :             spgAddSearchItemToQueue(so, innerItem);
     686             :         }
     687             :     }
     688             : 
     689       16988 :     MemoryContextSwitchTo(oldCxt);
     690       16988 : }
     691             : 
     692             : /* Returns a next item in an (ordered) scan or null if the index is exhausted */
     693             : static SpGistSearchItem *
     694      309548 : spgGetNextQueueItem(SpGistScanOpaque so)
     695             : {
     696      309548 :     if (pairingheap_is_empty(so->scanQueue))
     697         572 :         return NULL;            /* Done when both heaps are empty */
     698             : 
     699             :     /* Return item; caller is responsible to pfree it */
     700      308976 :     return (SpGistSearchItem *) pairingheap_remove_first(so->scanQueue);
     701             : }
     702             : 
     703             : enum SpGistSpecialOffsetNumbers
     704             : {
     705             :     SpGistBreakOffsetNumber = InvalidOffsetNumber,
     706             :     SpGistRedirectOffsetNumber = MaxOffsetNumber + 1,
     707             :     SpGistErrorOffsetNumber = MaxOffsetNumber + 2
     708             : };
     709             : 
     710             : static OffsetNumber
     711     1757548 : spgTestLeafTuple(SpGistScanOpaque so,
     712             :                  SpGistSearchItem *item,
     713             :                  Page page, OffsetNumber offset,
     714             :                  bool isnull, bool isroot,
     715             :                  bool *reportedSome,
     716             :                  storeRes_func storeRes)
     717             : {
     718     1757548 :     SpGistLeafTuple leafTuple = (SpGistLeafTuple)
     719     1757548 :     PageGetItem(page, PageGetItemId(page, offset));
     720             : 
     721     1757548 :     if (leafTuple->tupstate != SPGIST_LIVE)
     722             :     {
     723           0 :         if (!isroot)            /* all tuples on root should be live */
     724             :         {
     725           0 :             if (leafTuple->tupstate == SPGIST_REDIRECT)
     726             :             {
     727             :                 /* redirection tuple should be first in chain */
     728             :                 Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
     729             :                 /* transfer attention to redirect point */
     730           0 :                 item->heapPtr = ((SpGistDeadTuple) leafTuple)->pointer;
     731             :                 Assert(ItemPointerGetBlockNumber(&item->heapPtr) != SPGIST_METAPAGE_BLKNO);
     732           0 :                 return SpGistRedirectOffsetNumber;
     733             :             }
     734             : 
     735           0 :             if (leafTuple->tupstate == SPGIST_DEAD)
     736             :             {
     737             :                 /* dead tuple should be first in chain */
     738             :                 Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
     739             :                 /* No live entries on this page */
     740             :                 Assert(leafTuple->nextOffset == InvalidOffsetNumber);
     741           0 :                 return SpGistBreakOffsetNumber;
     742             :             }
     743             :         }
     744             : 
     745             :         /* We should not arrive at a placeholder */
     746           0 :         elog(ERROR, "unexpected SPGiST tuple state: %d", leafTuple->tupstate);
     747             :         return SpGistErrorOffsetNumber;
     748             :     }
     749             : 
     750             :     Assert(ItemPointerIsValid(&leafTuple->heapPtr));
     751             : 
     752     1757548 :     spgLeafTest(so, item, leafTuple, isnull, reportedSome, storeRes);
     753             : 
     754     1757548 :     return leafTuple->nextOffset;
     755             : }
     756             : 
     757             : /*
     758             :  * Walk the tree and report all tuples passing the scan quals to the storeRes
     759             :  * subroutine.
     760             :  *
     761             :  * If scanWholeIndex is true, we'll do just that.  If not, we'll stop at the
     762             :  * next page boundary once we have reported at least one tuple.
     763             :  */
     764             : static void
     765      251978 : spgWalk(Relation index, SpGistScanOpaque so, bool scanWholeIndex,
     766             :         storeRes_func storeRes, Snapshot snapshot)
     767             : {
     768      251978 :     Buffer      buffer = InvalidBuffer;
     769      251978 :     bool        reportedSome = false;
     770             : 
     771      812932 :     while (scanWholeIndex || !reportedSome)
     772             :     {
     773      309548 :         SpGistSearchItem *item = spgGetNextQueueItem(so);
     774             : 
     775      309548 :         if (item == NULL)
     776         572 :             break;              /* No more items in queue -> done */
     777             : 
     778             : redirect:
     779             :         /* Check for interrupts, just in case of infinite loop */
     780      308976 :         CHECK_FOR_INTERRUPTS();
     781             : 
     782      308976 :         if (item->isLeaf)
     783             :         {
     784             :             /* We store heap items in the queue only in case of ordered search */
     785             :             Assert(so->numberOfNonNullOrderBys > 0);
     786      484392 :             storeRes(so, &item->heapPtr, item->value, item->isNull,
     787      484392 :                      item->recheck, item->recheckDistances, item->distances);
     788      242196 :             reportedSome = true;
     789             :         }
     790             :         else
     791             :         {
     792       66780 :             BlockNumber blkno = ItemPointerGetBlockNumber(&item->heapPtr);
     793       66780 :             OffsetNumber offset = ItemPointerGetOffsetNumber(&item->heapPtr);
     794             :             Page        page;
     795             :             bool        isnull;
     796             : 
     797       66780 :             if (buffer == InvalidBuffer)
     798             :             {
     799       13712 :                 buffer = ReadBuffer(index, blkno);
     800       13712 :                 LockBuffer(buffer, BUFFER_LOCK_SHARE);
     801             :             }
     802       53068 :             else if (blkno != BufferGetBlockNumber(buffer))
     803             :             {
     804       36980 :                 UnlockReleaseBuffer(buffer);
     805       36980 :                 buffer = ReadBuffer(index, blkno);
     806       36980 :                 LockBuffer(buffer, BUFFER_LOCK_SHARE);
     807             :             }
     808             : 
     809             :             /* else new pointer points to the same page, no work needed */
     810             : 
     811       66780 :             page = BufferGetPage(buffer);
     812       66780 :             TestForOldSnapshot(snapshot, index, page);
     813             : 
     814       66780 :             isnull = SpGistPageStoresNulls(page) ? true : false;
     815             : 
     816       66780 :             if (SpGistPageIsLeaf(page))
     817             :             {
     818             :                 /* Page is a leaf - that is, all it's tuples are heap items */
     819       49792 :                 OffsetNumber max = PageGetMaxOffsetNumber(page);
     820             : 
     821       49916 :                 if (SpGistBlockIsRoot(blkno))
     822             :                 {
     823             :                     /* When root is a leaf, examine all its tuples */
     824        3660 :                     for (offset = FirstOffsetNumber; offset <= max; offset++)
     825        3536 :                         (void) spgTestLeafTuple(so, item, page, offset,
     826             :                                                 isnull, true,
     827             :                                                 &reportedSome, storeRes);
     828             :                 }
     829             :                 else
     830             :                 {
     831             :                     /* Normal case: just examine the chain we arrived at */
     832     1853348 :                     while (offset != InvalidOffsetNumber)
     833             :                     {
     834             :                         Assert(offset >= FirstOffsetNumber && offset <= max);
     835     1754012 :                         offset = spgTestLeafTuple(so, item, page, offset,
     836             :                                                   isnull, false,
     837             :                                                   &reportedSome, storeRes);
     838     1754012 :                         if (offset == SpGistRedirectOffsetNumber)
     839           0 :                             goto redirect;
     840             :                     }
     841             :                 }
     842             :             }
     843             :             else                /* page is inner */
     844             :             {
     845       16988 :                 SpGistInnerTuple innerTuple = (SpGistInnerTuple)
     846       16988 :                 PageGetItem(page, PageGetItemId(page, offset));
     847             : 
     848       16988 :                 if (innerTuple->tupstate != SPGIST_LIVE)
     849             :                 {
     850           0 :                     if (innerTuple->tupstate == SPGIST_REDIRECT)
     851             :                     {
     852             :                         /* transfer attention to redirect point */
     853           0 :                         item->heapPtr = ((SpGistDeadTuple) innerTuple)->pointer;
     854             :                         Assert(ItemPointerGetBlockNumber(&item->heapPtr) !=
     855             :                                SPGIST_METAPAGE_BLKNO);
     856           0 :                         goto redirect;
     857             :                     }
     858           0 :                     elog(ERROR, "unexpected SPGiST tuple state: %d",
     859             :                          innerTuple->tupstate);
     860             :                 }
     861             : 
     862       16988 :                 spgInnerTest(so, item, innerTuple, isnull);
     863             :             }
     864             :         }
     865             : 
     866             :         /* done with this scan item */
     867      308976 :         spgFreeSearchItem(so, item);
     868             :         /* clear temp context before proceeding to the next one */
     869      308976 :         MemoryContextReset(so->tempCxt);
     870             :     }
     871             : 
     872      251978 :     if (buffer != InvalidBuffer)
     873       13712 :         UnlockReleaseBuffer(buffer);
     874      251978 : }
     875             : 
     876             : 
     877             : /* storeRes subroutine for getbitmap case */
     878             : static void
     879      701464 : storeBitmap(SpGistScanOpaque so, ItemPointer heapPtr,
     880             :             Datum leafValue, bool isnull, bool recheck, bool recheckDistances,
     881             :             double *distances)
     882             : {
     883             :     Assert(!recheckDistances && !distances);
     884      701464 :     tbm_add_tuples(so->tbm, heapPtr, 1, recheck);
     885      701464 :     so->ntids++;
     886      701464 : }
     887             : 
     888             : int64
     889         224 : spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
     890             : {
     891         224 :     SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
     892             : 
     893             :     /* Copy want_itup to *so so we don't need to pass it around separately */
     894         224 :     so->want_itup = false;
     895             : 
     896         224 :     so->tbm = tbm;
     897         224 :     so->ntids = 0;
     898             : 
     899         224 :     spgWalk(scan->indexRelation, so, true, storeBitmap, scan->xs_snapshot);
     900             : 
     901         224 :     return so->ntids;
     902             : }
     903             : 
     904             : /* storeRes subroutine for gettuple case */
     905             : static void
     906      670856 : storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr,
     907             :               Datum leafValue, bool isnull, bool recheck, bool recheckDistances,
     908             :               double *nonNullDistances)
     909             : {
     910             :     Assert(so->nPtrs < MaxIndexTuplesPerPage);
     911      670856 :     so->heapPtrs[so->nPtrs] = *heapPtr;
     912      670856 :     so->recheck[so->nPtrs] = recheck;
     913      670856 :     so->recheckDistances[so->nPtrs] = recheckDistances;
     914             : 
     915      670856 :     if (so->numberOfOrderBys > 0)
     916             :     {
     917      242196 :         if (isnull || so->numberOfNonNullOrderBys <= 0)
     918          32 :             so->distances[so->nPtrs] = NULL;
     919             :         else
     920             :         {
     921      242164 :             IndexOrderByDistance *distances =
     922      242164 :             palloc(sizeof(distances[0]) * so->numberOfOrderBys);
     923             :             int         i;
     924             : 
     925      484340 :             for (i = 0; i < so->numberOfOrderBys; i++)
     926             :             {
     927      242176 :                 int         offset = so->nonNullOrderByOffsets[i];
     928             : 
     929      242176 :                 if (offset >= 0)
     930             :                 {
     931             :                     /* Copy non-NULL distance value */
     932      242172 :                     distances[i].value = nonNullDistances[offset];
     933      242172 :                     distances[i].isnull = false;
     934             :                 }
     935             :                 else
     936             :                 {
     937             :                     /* Set distance's NULL flag. */
     938           4 :                     distances[i].value = 0.0;
     939           4 :                     distances[i].isnull = true;
     940             :                 }
     941             :             }
     942             : 
     943      242164 :             so->distances[so->nPtrs] = distances;
     944             :         }
     945             :     }
     946             : 
     947      670856 :     if (so->want_itup)
     948             :     {
     949             :         /*
     950             :          * Reconstruct index data.  We have to copy the datum out of the temp
     951             :          * context anyway, so we may as well create the tuple here.
     952             :          */
     953      612876 :         so->reconTups[so->nPtrs] = heap_form_tuple(so->indexTupDesc,
     954             :                                                    &leafValue,
     955             :                                                    &isnull);
     956             :     }
     957      670856 :     so->nPtrs++;
     958      670856 : }
     959             : 
     960             : bool
     961      671140 : spggettuple(IndexScanDesc scan, ScanDirection dir)
     962             : {
     963      671140 :     SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
     964             : 
     965      671140 :     if (dir != ForwardScanDirection)
     966           0 :         elog(ERROR, "SP-GiST only supports forward scan direction");
     967             : 
     968             :     /* Copy want_itup to *so so we don't need to pass it around separately */
     969      671140 :     so->want_itup = scan->xs_want_itup;
     970             : 
     971             :     for (;;)
     972             :     {
     973     1173952 :         if (so->iPtr < so->nPtrs)
     974             :         {
     975             :             /* continuing to return reported tuples */
     976      670792 :             scan->xs_heaptid = so->heapPtrs[so->iPtr];
     977      670792 :             scan->xs_recheck = so->recheck[so->iPtr];
     978      670792 :             scan->xs_hitup = so->reconTups[so->iPtr];
     979             : 
     980      670792 :             if (so->numberOfOrderBys > 0)
     981      484392 :                 index_store_float8_orderby_distances(scan, so->orderByTypes,
     982      242196 :                                                      so->distances[so->iPtr],
     983      242196 :                                                      so->recheckDistances[so->iPtr]);
     984      670792 :             so->iPtr++;
     985      670792 :             return true;
     986             :         }
     987             : 
     988      251754 :         if (so->numberOfOrderBys > 0)
     989             :         {
     990             :             /* Must pfree distances to avoid memory leak */
     991             :             int         i;
     992             : 
     993      484416 :             for (i = 0; i < so->nPtrs; i++)
     994      242184 :                 if (so->distances[i])
     995      242152 :                     pfree(so->distances[i]);
     996             :         }
     997             : 
     998      251754 :         if (so->want_itup)
     999             :         {
    1000             :             /* Must pfree reconstructed tuples to avoid memory leak */
    1001             :             int         i;
    1002             : 
    1003      806742 :             for (i = 0; i < so->nPtrs; i++)
    1004      612788 :                 pfree(so->reconTups[i]);
    1005             :         }
    1006      251754 :         so->iPtr = so->nPtrs = 0;
    1007             : 
    1008      251754 :         spgWalk(scan->indexRelation, so, false, storeGettuple,
    1009             :                 scan->xs_snapshot);
    1010             : 
    1011      251754 :         if (so->nPtrs == 0)
    1012         348 :             break;              /* must have completed scan */
    1013             :     }
    1014             : 
    1015         348 :     return false;
    1016             : }
    1017             : 
    1018             : bool
    1019        1156 : spgcanreturn(Relation index, int attno)
    1020             : {
    1021             :     SpGistCache *cache;
    1022             : 
    1023             :     /* We can do it if the opclass config function says so */
    1024        1156 :     cache = spgGetCache(index);
    1025             : 
    1026        1156 :     return cache->config.canReturnData;
    1027             : }

Generated by: LCOV version 1.13