granicus.if.org Git - postgresql/blob - src/backend/access/gist/gistscan.c

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