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

Generated by: LCOV version 1.13