Header And Logo

PostgreSQL
| The world's most advanced open source database.

gistscan.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * gistscan.c
00004  *    routines to manage scans on GiST index relations
00005  *
00006  *
00007  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00008  * Portions Copyright (c) 1994, Regents of the University of California
00009  *
00010  * IDENTIFICATION
00011  *    src/backend/access/gist/gistscan.c
00012  *
00013  *-------------------------------------------------------------------------
00014  */
00015 #include "postgres.h"
00016 
00017 #include "access/gist_private.h"
00018 #include "access/gistscan.h"
00019 #include "access/relscan.h"
00020 #include "utils/memutils.h"
00021 #include "utils/rel.h"
00022 
00023 
00024 /*
00025  * RBTree support functions for the GISTSearchTreeItem queue
00026  */
00027 
00028 static int
00029 GISTSearchTreeItemComparator(const RBNode *a, const RBNode *b, void *arg)
00030 {
00031     const GISTSearchTreeItem *sa = (const GISTSearchTreeItem *) a;
00032     const GISTSearchTreeItem *sb = (const GISTSearchTreeItem *) b;
00033     IndexScanDesc scan = (IndexScanDesc) arg;
00034     int         i;
00035 
00036     /* Order according to distance comparison */
00037     for (i = 0; i < scan->numberOfOrderBys; i++)
00038     {
00039         if (sa->distances[i] != sb->distances[i])
00040             return (sa->distances[i] > sb->distances[i]) ? 1 : -1;
00041     }
00042 
00043     return 0;
00044 }
00045 
00046 static void
00047 GISTSearchTreeItemCombiner(RBNode *existing, const RBNode *newrb, void *arg)
00048 {
00049     GISTSearchTreeItem *scurrent = (GISTSearchTreeItem *) existing;
00050     const GISTSearchTreeItem *snew = (const GISTSearchTreeItem *) newrb;
00051     GISTSearchItem *newitem = snew->head;
00052 
00053     /* snew should have just one item in its chain */
00054     Assert(newitem && newitem->next == NULL);
00055 
00056     /*
00057      * If new item is heap tuple, it goes to front of chain; otherwise insert
00058      * it before the first index-page item, so that index pages are visited in
00059      * LIFO order, ensuring depth-first search of index pages.  See comments
00060      * in gist_private.h.
00061      */
00062     if (GISTSearchItemIsHeap(*newitem))
00063     {
00064         newitem->next = scurrent->head;
00065         scurrent->head = newitem;
00066         if (scurrent->lastHeap == NULL)
00067             scurrent->lastHeap = newitem;
00068     }
00069     else if (scurrent->lastHeap == NULL)
00070     {
00071         newitem->next = scurrent->head;
00072         scurrent->head = newitem;
00073     }
00074     else
00075     {
00076         newitem->next = scurrent->lastHeap->next;
00077         scurrent->lastHeap->next = newitem;
00078     }
00079 }
00080 
00081 static RBNode *
00082 GISTSearchTreeItemAllocator(void *arg)
00083 {
00084     IndexScanDesc scan = (IndexScanDesc) arg;
00085 
00086     return palloc(GSTIHDRSZ + sizeof(double) * scan->numberOfOrderBys);
00087 }
00088 
00089 static void
00090 GISTSearchTreeItemDeleter(RBNode *rb, void *arg)
00091 {
00092     pfree(rb);
00093 }
00094 
00095 
00096 /*
00097  * Index AM API functions for scanning GiST indexes
00098  */
00099 
00100 Datum
00101 gistbeginscan(PG_FUNCTION_ARGS)
00102 {
00103     Relation    r = (Relation) PG_GETARG_POINTER(0);
00104     int         nkeys = PG_GETARG_INT32(1);
00105     int         norderbys = PG_GETARG_INT32(2);
00106     IndexScanDesc scan;
00107     GISTSTATE  *giststate;
00108     GISTScanOpaque so;
00109     MemoryContext oldCxt;
00110 
00111     scan = RelationGetIndexScan(r, nkeys, norderbys);
00112 
00113     /* First, set up a GISTSTATE with a scan-lifespan memory context */
00114     giststate = initGISTstate(scan->indexRelation);
00115 
00116     /*
00117      * Everything made below is in the scanCxt, or is a child of the scanCxt,
00118      * so it'll all go away automatically in gistendscan.
00119      */
00120     oldCxt = MemoryContextSwitchTo(giststate->scanCxt);
00121 
00122     /* initialize opaque data */
00123     so = (GISTScanOpaque) palloc0(sizeof(GISTScanOpaqueData));
00124     so->giststate = giststate;
00125     giststate->tempCxt = createTempGistContext();
00126     so->queue = NULL;
00127     so->queueCxt = giststate->scanCxt;  /* see gistrescan */
00128 
00129     /* workspaces with size dependent on numberOfOrderBys: */
00130     so->tmpTreeItem = palloc(GSTIHDRSZ + sizeof(double) * scan->numberOfOrderBys);
00131     so->distances = palloc(sizeof(double) * scan->numberOfOrderBys);
00132     so->qual_ok = true;         /* in case there are zero keys */
00133 
00134     scan->opaque = so;
00135 
00136     MemoryContextSwitchTo(oldCxt);
00137 
00138     PG_RETURN_POINTER(scan);
00139 }
00140 
00141 Datum
00142 gistrescan(PG_FUNCTION_ARGS)
00143 {
00144     IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
00145     ScanKey     key = (ScanKey) PG_GETARG_POINTER(1);
00146     ScanKey     orderbys = (ScanKey) PG_GETARG_POINTER(3);
00147 
00148     /* nkeys and norderbys arguments are ignored */
00149     GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
00150     bool        first_time;
00151     int         i;
00152     MemoryContext oldCxt;
00153 
00154     /* rescan an existing indexscan --- reset state */
00155 
00156     /*
00157      * The first time through, we create the search queue in the scanCxt.
00158      * Subsequent times through, we create the queue in a separate queueCxt,
00159      * which is created on the second call and reset on later calls.  Thus, in
00160      * the common case where a scan is only rescan'd once, we just put the
00161      * queue in scanCxt and don't pay the overhead of making a second memory
00162      * context.  If we do rescan more than once, the first RBTree is just left
00163      * for dead until end of scan; this small wastage seems worth the savings
00164      * in the common case.
00165      */
00166     if (so->queue == NULL)
00167     {
00168         /* first time through */
00169         Assert(so->queueCxt == so->giststate->scanCxt);
00170         first_time = true;
00171     }
00172     else if (so->queueCxt == so->giststate->scanCxt)
00173     {
00174         /* second time through */
00175         so->queueCxt = AllocSetContextCreate(so->giststate->scanCxt,
00176                                              "GiST queue context",
00177                                              ALLOCSET_DEFAULT_MINSIZE,
00178                                              ALLOCSET_DEFAULT_INITSIZE,
00179                                              ALLOCSET_DEFAULT_MAXSIZE);
00180         first_time = false;
00181     }
00182     else
00183     {
00184         /* third or later time through */
00185         MemoryContextReset(so->queueCxt);
00186         first_time = false;
00187     }
00188 
00189     /* create new, empty RBTree for search queue */
00190     oldCxt = MemoryContextSwitchTo(so->queueCxt);
00191     so->queue = rb_create(GSTIHDRSZ + sizeof(double) * scan->numberOfOrderBys,
00192                           GISTSearchTreeItemComparator,
00193                           GISTSearchTreeItemCombiner,
00194                           GISTSearchTreeItemAllocator,
00195                           GISTSearchTreeItemDeleter,
00196                           scan);
00197     MemoryContextSwitchTo(oldCxt);
00198 
00199     so->curTreeItem = NULL;
00200     so->firstCall = true;
00201 
00202     /* Update scan key, if a new one is given */
00203     if (key && scan->numberOfKeys > 0)
00204     {
00205         /*
00206          * If this isn't the first time through, preserve the fn_extra
00207          * pointers, so that if the consistentFns are using them to cache
00208          * data, that data is not leaked across a rescan.
00209          */
00210         if (!first_time)
00211         {
00212             for (i = 0; i < scan->numberOfKeys; i++)
00213             {
00214                 ScanKey     skey = scan->keyData + i;
00215 
00216                 so->giststate->consistentFn[skey->sk_attno - 1].fn_extra =
00217                     skey->sk_func.fn_extra;
00218             }
00219         }
00220 
00221         memmove(scan->keyData, key,
00222                 scan->numberOfKeys * sizeof(ScanKeyData));
00223 
00224         /*
00225          * Modify the scan key so that the Consistent method is called for all
00226          * comparisons. The original operator is passed to the Consistent
00227          * function in the form of its strategy number, which is available
00228          * from the sk_strategy field, and its subtype from the sk_subtype
00229          * field.
00230          *
00231          * Next, if any of keys is a NULL and that key is not marked with
00232          * SK_SEARCHNULL/SK_SEARCHNOTNULL then nothing can be found (ie, we
00233          * assume all indexable operators are strict).
00234          *
00235          * Note: we intentionally memcpy the FmgrInfo to sk_func rather than
00236          * using fmgr_info_copy.  This is so that the fn_extra field gets
00237          * preserved across multiple rescans.
00238          */
00239         so->qual_ok = true;
00240 
00241         for (i = 0; i < scan->numberOfKeys; i++)
00242         {
00243             ScanKey     skey = scan->keyData + i;
00244 
00245             skey->sk_func = so->giststate->consistentFn[skey->sk_attno - 1];
00246 
00247             if (skey->sk_flags & SK_ISNULL)
00248             {
00249                 if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
00250                     so->qual_ok = false;
00251             }
00252         }
00253     }
00254 
00255     /* Update order-by key, if a new one is given */
00256     if (orderbys && scan->numberOfOrderBys > 0)
00257     {
00258         /* As above, preserve fn_extra if not first time through */
00259         if (!first_time)
00260         {
00261             for (i = 0; i < scan->numberOfOrderBys; i++)
00262             {
00263                 ScanKey     skey = scan->orderByData + i;
00264 
00265                 so->giststate->distanceFn[skey->sk_attno - 1].fn_extra =
00266                     skey->sk_func.fn_extra;
00267             }
00268         }
00269 
00270         memmove(scan->orderByData, orderbys,
00271                 scan->numberOfOrderBys * sizeof(ScanKeyData));
00272 
00273         /*
00274          * Modify the order-by key so that the Distance method is called for
00275          * all comparisons. The original operator is passed to the Distance
00276          * function in the form of its strategy number, which is available
00277          * from the sk_strategy field, and its subtype from the sk_subtype
00278          * field.
00279          *
00280          * See above comment about why we don't use fmgr_info_copy here.
00281          */
00282         for (i = 0; i < scan->numberOfOrderBys; i++)
00283         {
00284             ScanKey     skey = scan->orderByData + i;
00285 
00286             skey->sk_func = so->giststate->distanceFn[skey->sk_attno - 1];
00287 
00288             /* Check we actually have a distance function ... */
00289             if (!OidIsValid(skey->sk_func.fn_oid))
00290                 elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
00291                      GIST_DISTANCE_PROC, skey->sk_attno,
00292                      RelationGetRelationName(scan->indexRelation));
00293         }
00294     }
00295 
00296     PG_RETURN_VOID();
00297 }
00298 
00299 Datum
00300 gistmarkpos(PG_FUNCTION_ARGS)
00301 {
00302     elog(ERROR, "GiST does not support mark/restore");
00303     PG_RETURN_VOID();
00304 }
00305 
00306 Datum
00307 gistrestrpos(PG_FUNCTION_ARGS)
00308 {
00309     elog(ERROR, "GiST does not support mark/restore");
00310     PG_RETURN_VOID();
00311 }
00312 
00313 Datum
00314 gistendscan(PG_FUNCTION_ARGS)
00315 {
00316     IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
00317     GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
00318 
00319     /*
00320      * freeGISTstate is enough to clean up everything made by gistbeginscan,
00321      * as well as the queueCxt if there is a separate context for it.
00322      */
00323     freeGISTstate(so->giststate);
00324 
00325     PG_RETURN_VOID();
00326 }