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-2010, 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/genam.h"
  18 #include "access/gist_private.h"
  19 #include "access/gistscan.h"
  20 #include "access/relscan.h"
  21 #include "storage/bufmgr.h"
  22 #include "utils/memutils.h"
  23 #include "utils/rel.h"
  24
  25
  26 /*
  27  * RBTree support functions for the GISTSearchTreeItem queue
  28  */
  29
  30 static int
  31 GISTSearchTreeItemComparator(const RBNode *a, const RBNode *b, void *arg)
  32 {
  33         const GISTSearchTreeItem *sa = (const GISTSearchTreeItem *) a;
  34         const GISTSearchTreeItem *sb = (const GISTSearchTreeItem *) b;
  35         IndexScanDesc scan = (IndexScanDesc) arg;
  36         int                     i;
  37
  38         /* Order according to distance comparison */
  39         for (i = 0; i < scan->numberOfOrderBys; i++)
  40         {
  41                 if (sa->distances[i] != sb->distances[i])
  42                         return (sa->distances[i] > sb->distances[i]) ? 1 : -1;
  43         }
  44
  45         return 0;
  46 }
  47
  48 static void
  49 GISTSearchTreeItemCombiner(RBNode *existing, const RBNode *newrb, void *arg)
  50 {
  51         GISTSearchTreeItem *scurrent = (GISTSearchTreeItem *) existing;
  52         const GISTSearchTreeItem *snew = (const GISTSearchTreeItem *) newrb;
  53         GISTSearchItem *newitem = snew->head;
  54
  55         /* snew should have just one item in its chain */
  56         Assert(newitem && newitem->next == NULL);
  57
  58         /*
  59          * If new item is heap tuple, it goes to front of chain; otherwise insert
  60          * it before the first index-page item, so that index pages are visited
  61          * in LIFO order, ensuring depth-first search of index pages.  See
  62          * comments in gist_private.h.
  63          */
  64         if (GISTSearchItemIsHeap(*newitem))
  65         {
  66                 newitem->next = scurrent->head;
  67                 scurrent->head = newitem;
  68                 if (scurrent->lastHeap == NULL)
  69                         scurrent->lastHeap = newitem;
  70         }
  71         else if (scurrent->lastHeap == NULL)
  72         {
  73                 newitem->next = scurrent->head;
  74                 scurrent->head = newitem;
  75         }
  76         else
  77         {
  78                 newitem->next = scurrent->lastHeap->next;
  79                 scurrent->lastHeap->next = newitem;
  80         }
  81 }
  82
  83 static RBNode *
  84 GISTSearchTreeItemAllocator(void *arg)
  85 {
  86         IndexScanDesc scan = (IndexScanDesc) arg;
  87
  88         return palloc(GSTIHDRSZ + sizeof(double) * scan->numberOfOrderBys);
  89 }
  90
  91 static void
  92 GISTSearchTreeItemDeleter(RBNode *rb, void *arg)
  93 {
  94         pfree(rb);
  95 }
  96
  97
  98 /*
  99  * Index AM API functions for scanning GiST indexes
 100  */
 101
 102 Datum
 103 gistbeginscan(PG_FUNCTION_ARGS)
 104 {
 105         Relation        r = (Relation) PG_GETARG_POINTER(0);
 106         int                     nkeys = PG_GETARG_INT32(1);
 107         int                     norderbys = PG_GETARG_INT32(2);
 108         IndexScanDesc scan;
 109         GISTScanOpaque so;
 110
 111         scan = RelationGetIndexScan(r, nkeys, norderbys);
 112
 113         /* initialize opaque data */
 114         so = (GISTScanOpaque) palloc0(sizeof(GISTScanOpaqueData));
 115         so->queueCxt = AllocSetContextCreate(CurrentMemoryContext,
 116                                                                                  "GiST queue context",
 117                                                                                  ALLOCSET_DEFAULT_MINSIZE,
 118                                                                                  ALLOCSET_DEFAULT_INITSIZE,
 119                                                                                  ALLOCSET_DEFAULT_MAXSIZE);
 120         so->tempCxt = createTempGistContext();
 121         so->giststate = (GISTSTATE *) palloc(sizeof(GISTSTATE));
 122         initGISTstate(so->giststate, scan->indexRelation);
 123         /* workspaces with size dependent on numberOfOrderBys: */
 124         so->tmpTreeItem = palloc(GSTIHDRSZ + sizeof(double) * scan->numberOfOrderBys);
 125         so->distances = palloc(sizeof(double) * scan->numberOfOrderBys);
 126         so->qual_ok = true;                     /* in case there are zero keys */
 127
 128         scan->opaque = so;
 129
 130         PG_RETURN_POINTER(scan);
 131 }
 132
 133 Datum
 134 gistrescan(PG_FUNCTION_ARGS)
 135 {
 136         IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
 137         ScanKey         key = (ScanKey) PG_GETARG_POINTER(1);
 138         ScanKey         orderbys = (ScanKey) PG_GETARG_POINTER(3);
 139         /* nkeys and norderbys arguments are ignored */
 140         GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
 141         int                     i;
 142         MemoryContext oldCxt;
 143
 144         /* rescan an existing indexscan --- reset state */
 145         MemoryContextReset(so->queueCxt);
 146         so->curTreeItem = NULL;
 147
 148         /* create new, empty RBTree for search queue */
 149         oldCxt = MemoryContextSwitchTo(so->queueCxt);
 150         so->queue = rb_create(GSTIHDRSZ + sizeof(double) * scan->numberOfOrderBys,
 151                                                   GISTSearchTreeItemComparator,
 152                                                   GISTSearchTreeItemCombiner,
 153                                                   GISTSearchTreeItemAllocator,
 154                                                   GISTSearchTreeItemDeleter,
 155                                                   scan);
 156         MemoryContextSwitchTo(oldCxt);
 157
 158         so->firstCall = true;
 159
 160         /* Update scan key, if a new one is given */
 161         if (key && scan->numberOfKeys > 0)
 162         {
 163                 memmove(scan->keyData, key,
 164                                 scan->numberOfKeys * sizeof(ScanKeyData));
 165
 166                 /*
 167                  * Modify the scan key so that the Consistent method is called for
 168                  * all comparisons. The original operator is passed to the Consistent
 169                  * function in the form of its strategy number, which is available
 170                  * from the sk_strategy field, and its subtype from the sk_subtype
 171                  * field.
 172                  *
 173                  * Next, if any of keys is a NULL and that key is not marked with
 174                  * SK_SEARCHNULL/SK_SEARCHNOTNULL then nothing can be found (ie, we
 175                  * assume all indexable operators are strict).
 176                  */
 177                 so->qual_ok = true;
 178
 179                 for (i = 0; i < scan->numberOfKeys; i++)
 180                 {
 181                         ScanKey         skey = scan->keyData + i;
 182
 183                         skey->sk_func = so->giststate->consistentFn[skey->sk_attno - 1];
 184
 185                         if (skey->sk_flags & SK_ISNULL)
 186                         {
 187                                 if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
 188                                         so->qual_ok = false;
 189                         }
 190                 }
 191         }
 192
 193         /* Update order-by key, if a new one is given */
 194         if (orderbys && scan->numberOfOrderBys > 0)
 195         {
 196                 memmove(scan->orderByData, orderbys,
 197                                 scan->numberOfOrderBys * sizeof(ScanKeyData));
 198
 199                 /*
 200                  * Modify the order-by key so that the Distance method is called for
 201                  * all comparisons. The original operator is passed to the Distance
 202                  * function in the form of its strategy number, which is available
 203                  * from the sk_strategy field, and its subtype from the sk_subtype
 204                  * field.
 205                  */
 206                 for (i = 0; i < scan->numberOfOrderBys; i++)
 207                 {
 208                         ScanKey         skey = scan->orderByData + i;
 209
 210                         skey->sk_func = so->giststate->distanceFn[skey->sk_attno - 1];
 211
 212                         /* Check we actually have a distance function ... */
 213                         if (!OidIsValid(skey->sk_func.fn_oid))
 214                                 elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
 215                                          GIST_DISTANCE_PROC, skey->sk_attno,
 216                                          RelationGetRelationName(scan->indexRelation));
 217                 }
 218         }
 219
 220         PG_RETURN_VOID();
 221 }
 222
 223 Datum
 224 gistmarkpos(PG_FUNCTION_ARGS)
 225 {
 226         elog(ERROR, "GiST does not support mark/restore");
 227         PG_RETURN_VOID();
 228 }
 229
 230 Datum
 231 gistrestrpos(PG_FUNCTION_ARGS)
 232 {
 233         elog(ERROR, "GiST does not support mark/restore");
 234         PG_RETURN_VOID();
 235 }
 236
 237 Datum
 238 gistendscan(PG_FUNCTION_ARGS)
 239 {
 240         IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
 241         GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
 242
 243         freeGISTstate(so->giststate);
 244         MemoryContextDelete(so->queueCxt);
 245         MemoryContextDelete(so->tempCxt);
 246         pfree(so->tmpTreeItem);
 247         pfree(so->distances);
 248         pfree(so);
 249
 250         PG_RETURN_VOID();
 251 }