LCOV - code coverage report
Current view: top level - src/backend/access/gist - gistscan.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 107 112 95.5 %
Date: 2019-11-15 23:07:02 Functions: 4 4 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * gistscan.c
       4             :  *    routines to manage scans on GiST index relations
       5             :  *
       6             :  *
       7             :  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
       8             :  * Portions Copyright (c) 1994, Regents of the University of California
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *    src/backend/access/gist/gistscan.c
      12             :  *
      13             :  *-------------------------------------------------------------------------
      14             :  */
      15             : #include "postgres.h"
      16             : 
      17             : #include "access/gist_private.h"
      18             : #include "access/gistscan.h"
      19             : #include "access/relscan.h"
      20             : #include "utils/float.h"
      21             : #include "utils/lsyscache.h"
      22             : #include "utils/memutils.h"
      23             : #include "utils/rel.h"
      24             : 
      25             : 
      26             : /*
      27             :  * Pairing heap comparison function for the GISTSearchItem queue
      28             :  */
      29             : static int
      30       95334 : pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
      31             : {
      32       95334 :     const GISTSearchItem *sa = (const GISTSearchItem *) a;
      33       95334 :     const GISTSearchItem *sb = (const GISTSearchItem *) b;
      34       95334 :     IndexScanDesc scan = (IndexScanDesc) arg;
      35             :     int         i;
      36             : 
      37             :     /* Order according to distance comparison */
      38       98198 :     for (i = 0; i < scan->numberOfOrderBys; i++)
      39             :     {
      40       53058 :         if (sa->distances[i].isnull)
      41             :         {
      42          40 :             if (!sb->distances[i].isnull)
      43          40 :                 return -1;
      44             :         }
      45       53018 :         else if (sb->distances[i].isnull)
      46             :         {
      47          16 :             return 1;
      48             :         }
      49             :         else
      50             :         {
      51       53002 :             int         cmp = -float8_cmp_internal(sa->distances[i].value,
      52             :                                                    sb->distances[i].value);
      53             : 
      54       53002 :             if (cmp != 0)
      55       50138 :                 return cmp;
      56             :         }
      57             :     }
      58             : 
      59             :     /* Heap items go before inner pages, to ensure a depth-first search */
      60       45140 :     if (GISTSearchItemIsHeap(*sa) && !GISTSearchItemIsHeap(*sb))
      61           0 :         return 1;
      62       45140 :     if (!GISTSearchItemIsHeap(*sa) && GISTSearchItemIsHeap(*sb))
      63           2 :         return -1;
      64             : 
      65       45138 :     return 0;
      66             : }
      67             : 
      68             : 
      69             : /*
      70             :  * Index AM API functions for scanning GiST indexes
      71             :  */
      72             : 
      73             : IndexScanDesc
      74        1286 : gistbeginscan(Relation r, int nkeys, int norderbys)
      75             : {
      76             :     IndexScanDesc scan;
      77             :     GISTSTATE  *giststate;
      78             :     GISTScanOpaque so;
      79             :     MemoryContext oldCxt;
      80             : 
      81        1286 :     scan = RelationGetIndexScan(r, nkeys, norderbys);
      82             : 
      83             :     /* First, set up a GISTSTATE with a scan-lifespan memory context */
      84        1286 :     giststate = initGISTstate(scan->indexRelation);
      85             : 
      86             :     /*
      87             :      * Everything made below is in the scanCxt, or is a child of the scanCxt,
      88             :      * so it'll all go away automatically in gistendscan.
      89             :      */
      90        1286 :     oldCxt = MemoryContextSwitchTo(giststate->scanCxt);
      91             : 
      92             :     /* initialize opaque data */
      93        1286 :     so = (GISTScanOpaque) palloc0(sizeof(GISTScanOpaqueData));
      94        1286 :     so->giststate = giststate;
      95        1286 :     giststate->tempCxt = createTempGistContext();
      96        1286 :     so->queue = NULL;
      97        1286 :     so->queueCxt = giststate->scanCxt;    /* see gistrescan */
      98             : 
      99             :     /* workspaces with size dependent on numberOfOrderBys: */
     100        1286 :     so->distances = palloc(sizeof(so->distances[0]) * scan->numberOfOrderBys);
     101        1286 :     so->qual_ok = true;          /* in case there are zero keys */
     102        1286 :     if (scan->numberOfOrderBys > 0)
     103             :     {
     104          92 :         scan->xs_orderbyvals = palloc0(sizeof(Datum) * scan->numberOfOrderBys);
     105          92 :         scan->xs_orderbynulls = palloc(sizeof(bool) * scan->numberOfOrderBys);
     106          92 :         memset(scan->xs_orderbynulls, true, sizeof(bool) * scan->numberOfOrderBys);
     107             :     }
     108             : 
     109        1286 :     so->killedItems = NULL;      /* until needed */
     110        1286 :     so->numKilled = 0;
     111        1286 :     so->curBlkno = InvalidBlockNumber;
     112        1286 :     so->curPageLSN = InvalidXLogRecPtr;
     113             : 
     114        1286 :     scan->opaque = so;
     115             : 
     116             :     /*
     117             :      * All fields required for index-only scans are initialized in gistrescan,
     118             :      * as we don't know yet if we're doing an index-only scan or not.
     119             :      */
     120             : 
     121        1286 :     MemoryContextSwitchTo(oldCxt);
     122             : 
     123        1286 :     return scan;
     124             : }
     125             : 
     126             : void
     127        1298 : gistrescan(IndexScanDesc scan, ScanKey key, int nkeys,
     128             :            ScanKey orderbys, int norderbys)
     129             : {
     130             :     /* nkeys and norderbys arguments are ignored */
     131        1298 :     GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
     132             :     bool        first_time;
     133             :     int         i;
     134             :     MemoryContext oldCxt;
     135             : 
     136             :     /* rescan an existing indexscan --- reset state */
     137             : 
     138             :     /*
     139             :      * The first time through, we create the search queue in the scanCxt.
     140             :      * Subsequent times through, we create the queue in a separate queueCxt,
     141             :      * which is created on the second call and reset on later calls.  Thus, in
     142             :      * the common case where a scan is only rescan'd once, we just put the
     143             :      * queue in scanCxt and don't pay the overhead of making a second memory
     144             :      * context.  If we do rescan more than once, the first queue is just left
     145             :      * for dead until end of scan; this small wastage seems worth the savings
     146             :      * in the common case.
     147             :      */
     148        1298 :     if (so->queue == NULL)
     149             :     {
     150             :         /* first time through */
     151             :         Assert(so->queueCxt == so->giststate->scanCxt);
     152        1286 :         first_time = true;
     153             :     }
     154          12 :     else if (so->queueCxt == so->giststate->scanCxt)
     155             :     {
     156             :         /* second time through */
     157           8 :         so->queueCxt = AllocSetContextCreate(so->giststate->scanCxt,
     158             :                                              "GiST queue context",
     159             :                                              ALLOCSET_DEFAULT_SIZES);
     160           8 :         first_time = false;
     161             :     }
     162             :     else
     163             :     {
     164             :         /* third or later time through */
     165           4 :         MemoryContextReset(so->queueCxt);
     166           4 :         first_time = false;
     167             :     }
     168             : 
     169             :     /*
     170             :      * If we're doing an index-only scan, on the first call, also initialize a
     171             :      * tuple descriptor to represent the returned index tuples and create a
     172             :      * memory context to hold them during the scan.
     173             :      */
     174        1298 :     if (scan->xs_want_itup && !scan->xs_hitupdesc)
     175             :     {
     176             :         int         natts;
     177             :         int         nkeyatts;
     178             :         int         attno;
     179             : 
     180             :         /*
     181             :          * The storage type of the index can be different from the original
     182             :          * datatype being indexed, so we cannot just grab the index's tuple
     183             :          * descriptor. Instead, construct a descriptor with the original data
     184             :          * types.
     185             :          */
     186         420 :         natts = RelationGetNumberOfAttributes(scan->indexRelation);
     187         420 :         nkeyatts = IndexRelationGetNumberOfKeyAttributes(scan->indexRelation);
     188         420 :         so->giststate->fetchTupdesc = CreateTemplateTupleDesc(natts);
     189         840 :         for (attno = 1; attno <= nkeyatts; attno++)
     190             :         {
     191         420 :             TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
     192         420 :                                scan->indexRelation->rd_opcintype[attno - 1],
     193             :                                -1, 0);
     194             :         }
     195             : 
     196         420 :         for (; attno <= natts; attno++)
     197             :         {
     198             :             /* taking opcintype from giststate->tupdesc */
     199           0 :             TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
     200           0 :                                TupleDescAttr(so->giststate->leafTupdesc,
     201             :                                              attno - 1)->atttypid,
     202             :                                -1, 0);
     203             :         }
     204         420 :         scan->xs_hitupdesc = so->giststate->fetchTupdesc;
     205             : 
     206             :         /* Also create a memory context that will hold the returned tuples */
     207         420 :         so->pageDataCxt = AllocSetContextCreate(so->giststate->scanCxt,
     208             :                                                 "GiST page data context",
     209             :                                                 ALLOCSET_DEFAULT_SIZES);
     210             :     }
     211             : 
     212             :     /* create new, empty pairing heap for search queue */
     213        1298 :     oldCxt = MemoryContextSwitchTo(so->queueCxt);
     214        1298 :     so->queue = pairingheap_allocate(pairingheap_GISTSearchItem_cmp, scan);
     215        1298 :     MemoryContextSwitchTo(oldCxt);
     216             : 
     217        1298 :     so->firstCall = true;
     218             : 
     219             :     /* Update scan key, if a new one is given */
     220        1298 :     if (key && scan->numberOfKeys > 0)
     221             :     {
     222        1234 :         void      **fn_extras = NULL;
     223             : 
     224             :         /*
     225             :          * If this isn't the first time through, preserve the fn_extra
     226             :          * pointers, so that if the consistentFns are using them to cache
     227             :          * data, that data is not leaked across a rescan.
     228             :          */
     229        1234 :         if (!first_time)
     230             :         {
     231          12 :             fn_extras = (void **) palloc(scan->numberOfKeys * sizeof(void *));
     232          24 :             for (i = 0; i < scan->numberOfKeys; i++)
     233          12 :                 fn_extras[i] = scan->keyData[i].sk_func.fn_extra;
     234             :         }
     235             : 
     236        1234 :         memmove(scan->keyData, key,
     237        1234 :                 scan->numberOfKeys * sizeof(ScanKeyData));
     238             : 
     239             :         /*
     240             :          * Modify the scan key so that the Consistent method is called for all
     241             :          * comparisons. The original operator is passed to the Consistent
     242             :          * function in the form of its strategy number, which is available
     243             :          * from the sk_strategy field, and its subtype from the sk_subtype
     244             :          * field.
     245             :          *
     246             :          * Next, if any of keys is a NULL and that key is not marked with
     247             :          * SK_SEARCHNULL/SK_SEARCHNOTNULL then nothing can be found (ie, we
     248             :          * assume all indexable operators are strict).
     249             :          */
     250        1234 :         so->qual_ok = true;
     251             : 
     252        2556 :         for (i = 0; i < scan->numberOfKeys; i++)
     253             :         {
     254        1322 :             ScanKey     skey = scan->keyData + i;
     255             : 
     256             :             /*
     257             :              * Copy consistent support function to ScanKey structure instead
     258             :              * of function implementing filtering operator.
     259             :              */
     260        2644 :             fmgr_info_copy(&(skey->sk_func),
     261        1322 :                            &(so->giststate->consistentFn[skey->sk_attno - 1]),
     262        1322 :                            so->giststate->scanCxt);
     263             : 
     264             :             /* Restore prior fn_extra pointers, if not first time */
     265        1322 :             if (!first_time)
     266          12 :                 skey->sk_func.fn_extra = fn_extras[i];
     267             : 
     268        1322 :             if (skey->sk_flags & SK_ISNULL)
     269             :             {
     270          18 :                 if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
     271           0 :                     so->qual_ok = false;
     272             :             }
     273             :         }
     274             : 
     275        1234 :         if (!first_time)
     276          12 :             pfree(fn_extras);
     277             :     }
     278             : 
     279             :     /* Update order-by key, if a new one is given */
     280        1298 :     if (orderbys && scan->numberOfOrderBys > 0)
     281             :     {
     282         100 :         void      **fn_extras = NULL;
     283             : 
     284             :         /* As above, preserve fn_extra if not first time through */
     285         100 :         if (!first_time)
     286             :         {
     287           8 :             fn_extras = (void **) palloc(scan->numberOfOrderBys * sizeof(void *));
     288          16 :             for (i = 0; i < scan->numberOfOrderBys; i++)
     289           8 :                 fn_extras[i] = scan->orderByData[i].sk_func.fn_extra;
     290             :         }
     291             : 
     292         100 :         memmove(scan->orderByData, orderbys,
     293         100 :                 scan->numberOfOrderBys * sizeof(ScanKeyData));
     294             : 
     295         100 :         so->orderByTypes = (Oid *) palloc(scan->numberOfOrderBys * sizeof(Oid));
     296             : 
     297             :         /*
     298             :          * Modify the order-by key so that the Distance method is called for
     299             :          * all comparisons. The original operator is passed to the Distance
     300             :          * function in the form of its strategy number, which is available
     301             :          * from the sk_strategy field, and its subtype from the sk_subtype
     302             :          * field.
     303             :          */
     304         200 :         for (i = 0; i < scan->numberOfOrderBys; i++)
     305             :         {
     306         100 :             ScanKey     skey = scan->orderByData + i;
     307         100 :             FmgrInfo   *finfo = &(so->giststate->distanceFn[skey->sk_attno - 1]);
     308             : 
     309             :             /* Check we actually have a distance function ... */
     310         100 :             if (!OidIsValid(finfo->fn_oid))
     311           0 :                 elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
     312             :                      GIST_DISTANCE_PROC, skey->sk_attno,
     313             :                      RelationGetRelationName(scan->indexRelation));
     314             : 
     315             :             /*
     316             :              * Look up the datatype returned by the original ordering
     317             :              * operator. GiST always uses a float8 for the distance function,
     318             :              * but the ordering operator could be anything else.
     319             :              *
     320             :              * XXX: The distance function is only allowed to be lossy if the
     321             :              * ordering operator's result type is float4 or float8.  Otherwise
     322             :              * we don't know how to return the distance to the executor.  But
     323             :              * we cannot check that here, as we won't know if the distance
     324             :              * function is lossy until it returns *recheck = true for the
     325             :              * first time.
     326             :              */
     327         100 :             so->orderByTypes[i] = get_func_rettype(skey->sk_func.fn_oid);
     328             : 
     329             :             /*
     330             :              * Copy distance support function to ScanKey structure instead of
     331             :              * function implementing ordering operator.
     332             :              */
     333         100 :             fmgr_info_copy(&(skey->sk_func), finfo, so->giststate->scanCxt);
     334             : 
     335             :             /* Restore prior fn_extra pointers, if not first time */
     336         100 :             if (!first_time)
     337           8 :                 skey->sk_func.fn_extra = fn_extras[i];
     338             :         }
     339             : 
     340         100 :         if (!first_time)
     341           8 :             pfree(fn_extras);
     342             :     }
     343             : 
     344             :     /* any previous xs_hitup will have been pfree'd in context resets above */
     345        1298 :     scan->xs_hitup = NULL;
     346        1298 : }
     347             : 
     348             : void
     349        1252 : gistendscan(IndexScanDesc scan)
     350             : {
     351        1252 :     GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
     352             : 
     353             :     /*
     354             :      * freeGISTstate is enough to clean up everything made by gistbeginscan,
     355             :      * as well as the queueCxt if there is a separate context for it.
     356             :      */
     357        1252 :     freeGISTstate(so->giststate);
     358        1252 : }

Generated by: LCOV version 1.13