Header And Logo

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

ginscan.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * ginscan.c
00004  *    routines to manage scans of inverted 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/gin/ginscan.c
00012  *-------------------------------------------------------------------------
00013  */
00014 
00015 #include "postgres.h"
00016 
00017 #include "access/gin_private.h"
00018 #include "access/relscan.h"
00019 #include "pgstat.h"
00020 #include "utils/memutils.h"
00021 #include "utils/rel.h"
00022 
00023 
00024 Datum
00025 ginbeginscan(PG_FUNCTION_ARGS)
00026 {
00027     Relation    rel = (Relation) PG_GETARG_POINTER(0);
00028     int         nkeys = PG_GETARG_INT32(1);
00029     int         norderbys = PG_GETARG_INT32(2);
00030     IndexScanDesc scan;
00031     GinScanOpaque so;
00032 
00033     /* no order by operators allowed */
00034     Assert(norderbys == 0);
00035 
00036     scan = RelationGetIndexScan(rel, nkeys, norderbys);
00037 
00038     /* allocate private workspace */
00039     so = (GinScanOpaque) palloc(sizeof(GinScanOpaqueData));
00040     so->keys = NULL;
00041     so->nkeys = 0;
00042     so->tempCtx = AllocSetContextCreate(CurrentMemoryContext,
00043                                         "Gin scan temporary context",
00044                                         ALLOCSET_DEFAULT_MINSIZE,
00045                                         ALLOCSET_DEFAULT_INITSIZE,
00046                                         ALLOCSET_DEFAULT_MAXSIZE);
00047     initGinState(&so->ginstate, scan->indexRelation);
00048 
00049     scan->opaque = so;
00050 
00051     PG_RETURN_POINTER(scan);
00052 }
00053 
00054 /*
00055  * Create a new GinScanEntry, unless an equivalent one already exists,
00056  * in which case just return it
00057  */
00058 static GinScanEntry
00059 ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,
00060                  StrategyNumber strategy, int32 searchMode,
00061                  Datum queryKey, GinNullCategory queryCategory,
00062                  bool isPartialMatch, Pointer extra_data)
00063 {
00064     GinState   *ginstate = &so->ginstate;
00065     GinScanEntry scanEntry;
00066     uint32      i;
00067 
00068     /*
00069      * Look for an existing equivalent entry.
00070      *
00071      * Entries with non-null extra_data are never considered identical, since
00072      * we can't know exactly what the opclass might be doing with that.
00073      */
00074     if (extra_data == NULL)
00075     {
00076         for (i = 0; i < so->totalentries; i++)
00077         {
00078             GinScanEntry prevEntry = so->entries[i];
00079 
00080             if (prevEntry->extra_data == NULL &&
00081                 prevEntry->isPartialMatch == isPartialMatch &&
00082                 prevEntry->strategy == strategy &&
00083                 prevEntry->searchMode == searchMode &&
00084                 prevEntry->attnum == attnum &&
00085                 ginCompareEntries(ginstate, attnum,
00086                                   prevEntry->queryKey,
00087                                   prevEntry->queryCategory,
00088                                   queryKey,
00089                                   queryCategory) == 0)
00090             {
00091                 /* Successful match */
00092                 return prevEntry;
00093             }
00094         }
00095     }
00096 
00097     /* Nope, create a new entry */
00098     scanEntry = (GinScanEntry) palloc(sizeof(GinScanEntryData));
00099     scanEntry->queryKey = queryKey;
00100     scanEntry->queryCategory = queryCategory;
00101     scanEntry->isPartialMatch = isPartialMatch;
00102     scanEntry->extra_data = extra_data;
00103     scanEntry->strategy = strategy;
00104     scanEntry->searchMode = searchMode;
00105     scanEntry->attnum = attnum;
00106 
00107     scanEntry->buffer = InvalidBuffer;
00108     ItemPointerSetMin(&scanEntry->curItem);
00109     scanEntry->matchBitmap = NULL;
00110     scanEntry->matchIterator = NULL;
00111     scanEntry->matchResult = NULL;
00112     scanEntry->list = NULL;
00113     scanEntry->nlist = 0;
00114     scanEntry->offset = InvalidOffsetNumber;
00115     scanEntry->isFinished = false;
00116     scanEntry->reduceResult = false;
00117 
00118     /* Add it to so's array */
00119     if (so->totalentries >= so->allocentries)
00120     {
00121         so->allocentries *= 2;
00122         so->entries = (GinScanEntry *)
00123             repalloc(so->entries, so->allocentries * sizeof(GinScanEntry));
00124     }
00125     so->entries[so->totalentries++] = scanEntry;
00126 
00127     return scanEntry;
00128 }
00129 
00130 /*
00131  * Initialize the next GinScanKey using the output from the extractQueryFn
00132  */
00133 static void
00134 ginFillScanKey(GinScanOpaque so, OffsetNumber attnum,
00135                StrategyNumber strategy, int32 searchMode,
00136                Datum query, uint32 nQueryValues,
00137                Datum *queryValues, GinNullCategory *queryCategories,
00138                bool *partial_matches, Pointer *extra_data)
00139 {
00140     GinScanKey  key = &(so->keys[so->nkeys++]);
00141     GinState   *ginstate = &so->ginstate;
00142     uint32      nUserQueryValues = nQueryValues;
00143     uint32      i;
00144 
00145     /* Non-default search modes add one "hidden" entry to each key */
00146     if (searchMode != GIN_SEARCH_MODE_DEFAULT)
00147         nQueryValues++;
00148     key->nentries = nQueryValues;
00149     key->nuserentries = nUserQueryValues;
00150 
00151     key->scanEntry = (GinScanEntry *) palloc(sizeof(GinScanEntry) * nQueryValues);
00152     key->entryRes = (bool *) palloc0(sizeof(bool) * nQueryValues);
00153 
00154     key->query = query;
00155     key->queryValues = queryValues;
00156     key->queryCategories = queryCategories;
00157     key->extra_data = extra_data;
00158     key->strategy = strategy;
00159     key->searchMode = searchMode;
00160     key->attnum = attnum;
00161 
00162     ItemPointerSetMin(&key->curItem);
00163     key->curItemMatches = false;
00164     key->recheckCurItem = false;
00165     key->isFinished = false;
00166 
00167     for (i = 0; i < nQueryValues; i++)
00168     {
00169         Datum       queryKey;
00170         GinNullCategory queryCategory;
00171         bool        isPartialMatch;
00172         Pointer     this_extra;
00173 
00174         if (i < nUserQueryValues)
00175         {
00176             /* set up normal entry using extractQueryFn's outputs */
00177             queryKey = queryValues[i];
00178             queryCategory = queryCategories[i];
00179             isPartialMatch =
00180                 (ginstate->canPartialMatch[attnum - 1] && partial_matches)
00181                 ? partial_matches[i] : false;
00182             this_extra = (extra_data) ? extra_data[i] : NULL;
00183         }
00184         else
00185         {
00186             /* set up hidden entry */
00187             queryKey = (Datum) 0;
00188             switch (searchMode)
00189             {
00190                 case GIN_SEARCH_MODE_INCLUDE_EMPTY:
00191                     queryCategory = GIN_CAT_EMPTY_ITEM;
00192                     break;
00193                 case GIN_SEARCH_MODE_ALL:
00194                     queryCategory = GIN_CAT_EMPTY_QUERY;
00195                     break;
00196                 case GIN_SEARCH_MODE_EVERYTHING:
00197                     queryCategory = GIN_CAT_EMPTY_QUERY;
00198                     break;
00199                 default:
00200                     elog(ERROR, "unexpected searchMode: %d", searchMode);
00201                     queryCategory = 0;  /* keep compiler quiet */
00202                     break;
00203             }
00204             isPartialMatch = false;
00205             this_extra = NULL;
00206 
00207             /*
00208              * We set the strategy to a fixed value so that ginFillScanEntry
00209              * can combine these entries for different scan keys.  This is
00210              * safe because the strategy value in the entry struct is only
00211              * used for partial-match cases.  It's OK to overwrite our local
00212              * variable here because this is the last loop iteration.
00213              */
00214             strategy = InvalidStrategy;
00215         }
00216 
00217         key->scanEntry[i] = ginFillScanEntry(so, attnum,
00218                                              strategy, searchMode,
00219                                              queryKey, queryCategory,
00220                                              isPartialMatch, this_extra);
00221     }
00222 }
00223 
00224 static void
00225 freeScanKeys(GinScanOpaque so)
00226 {
00227     uint32      i;
00228 
00229     if (so->keys == NULL)
00230         return;
00231 
00232     for (i = 0; i < so->nkeys; i++)
00233     {
00234         GinScanKey  key = so->keys + i;
00235 
00236         pfree(key->scanEntry);
00237         pfree(key->entryRes);
00238     }
00239 
00240     pfree(so->keys);
00241     so->keys = NULL;
00242     so->nkeys = 0;
00243 
00244     for (i = 0; i < so->totalentries; i++)
00245     {
00246         GinScanEntry entry = so->entries[i];
00247 
00248         if (entry->buffer != InvalidBuffer)
00249             ReleaseBuffer(entry->buffer);
00250         if (entry->list)
00251             pfree(entry->list);
00252         if (entry->matchIterator)
00253             tbm_end_iterate(entry->matchIterator);
00254         if (entry->matchBitmap)
00255             tbm_free(entry->matchBitmap);
00256         pfree(entry);
00257     }
00258 
00259     pfree(so->entries);
00260     so->entries = NULL;
00261     so->totalentries = 0;
00262 }
00263 
00264 void
00265 ginNewScanKey(IndexScanDesc scan)
00266 {
00267     ScanKey     scankey = scan->keyData;
00268     GinScanOpaque so = (GinScanOpaque) scan->opaque;
00269     int         i;
00270     bool        hasNullQuery = false;
00271 
00272     /* if no scan keys provided, allocate extra EVERYTHING GinScanKey */
00273     so->keys = (GinScanKey)
00274         palloc(Max(scan->numberOfKeys, 1) * sizeof(GinScanKeyData));
00275     so->nkeys = 0;
00276 
00277     /* initialize expansible array of GinScanEntry pointers */
00278     so->totalentries = 0;
00279     so->allocentries = 32;
00280     so->entries = (GinScanEntry *)
00281         palloc0(so->allocentries * sizeof(GinScanEntry));
00282 
00283     so->isVoidRes = false;
00284 
00285     for (i = 0; i < scan->numberOfKeys; i++)
00286     {
00287         ScanKey     skey = &scankey[i];
00288         Datum      *queryValues;
00289         int32       nQueryValues = 0;
00290         bool       *partial_matches = NULL;
00291         Pointer    *extra_data = NULL;
00292         bool       *nullFlags = NULL;
00293         int32       searchMode = GIN_SEARCH_MODE_DEFAULT;
00294 
00295         /*
00296          * We assume that GIN-indexable operators are strict, so a null query
00297          * argument means an unsatisfiable query.
00298          */
00299         if (skey->sk_flags & SK_ISNULL)
00300         {
00301             so->isVoidRes = true;
00302             break;
00303         }
00304 
00305         /* OK to call the extractQueryFn */
00306         queryValues = (Datum *)
00307             DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[skey->sk_attno - 1],
00308                            so->ginstate.supportCollation[skey->sk_attno - 1],
00309                                               skey->sk_argument,
00310                                               PointerGetDatum(&nQueryValues),
00311                                            UInt16GetDatum(skey->sk_strategy),
00312                                            PointerGetDatum(&partial_matches),
00313                                               PointerGetDatum(&extra_data),
00314                                               PointerGetDatum(&nullFlags),
00315                                               PointerGetDatum(&searchMode)));
00316 
00317         /*
00318          * If bogus searchMode is returned, treat as GIN_SEARCH_MODE_ALL; note
00319          * in particular we don't allow extractQueryFn to select
00320          * GIN_SEARCH_MODE_EVERYTHING.
00321          */
00322         if (searchMode < GIN_SEARCH_MODE_DEFAULT ||
00323             searchMode > GIN_SEARCH_MODE_ALL)
00324             searchMode = GIN_SEARCH_MODE_ALL;
00325 
00326         /* Non-default modes require the index to have placeholders */
00327         if (searchMode != GIN_SEARCH_MODE_DEFAULT)
00328             hasNullQuery = true;
00329 
00330         /*
00331          * In default mode, no keys means an unsatisfiable query.
00332          */
00333         if (queryValues == NULL || nQueryValues <= 0)
00334         {
00335             if (searchMode == GIN_SEARCH_MODE_DEFAULT)
00336             {
00337                 so->isVoidRes = true;
00338                 break;
00339             }
00340             nQueryValues = 0;   /* ensure sane value */
00341         }
00342 
00343         /*
00344          * If the extractQueryFn didn't create a nullFlags array, create one,
00345          * assuming that everything's non-null.  Otherwise, run through the
00346          * array and make sure each value is exactly 0 or 1; this ensures
00347          * binary compatibility with the GinNullCategory representation. While
00348          * at it, detect whether any null keys are present.
00349          */
00350         if (nullFlags == NULL)
00351             nullFlags = (bool *) palloc0(nQueryValues * sizeof(bool));
00352         else
00353         {
00354             int32       j;
00355 
00356             for (j = 0; j < nQueryValues; j++)
00357             {
00358                 if (nullFlags[j])
00359                 {
00360                     nullFlags[j] = true;        /* not any other nonzero value */
00361                     hasNullQuery = true;
00362                 }
00363             }
00364         }
00365         /* now we can use the nullFlags as category codes */
00366 
00367         ginFillScanKey(so, skey->sk_attno,
00368                        skey->sk_strategy, searchMode,
00369                        skey->sk_argument, nQueryValues,
00370                        queryValues, (GinNullCategory *) nullFlags,
00371                        partial_matches, extra_data);
00372     }
00373 
00374     /*
00375      * If there are no regular scan keys, generate an EVERYTHING scankey to
00376      * drive a full-index scan.
00377      */
00378     if (so->nkeys == 0 && !so->isVoidRes)
00379     {
00380         hasNullQuery = true;
00381         ginFillScanKey(so, FirstOffsetNumber,
00382                        InvalidStrategy, GIN_SEARCH_MODE_EVERYTHING,
00383                        (Datum) 0, 0,
00384                        NULL, NULL, NULL, NULL);
00385     }
00386 
00387     /*
00388      * If the index is version 0, it may be missing null and placeholder
00389      * entries, which would render searches for nulls and full-index scans
00390      * unreliable.  Throw an error if so.
00391      */
00392     if (hasNullQuery && !so->isVoidRes)
00393     {
00394         GinStatsData ginStats;
00395 
00396         ginGetStats(scan->indexRelation, &ginStats);
00397         if (ginStats.ginVersion < 1)
00398             ereport(ERROR,
00399                     (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
00400                      errmsg("old GIN indexes do not support whole-index scans nor searches for nulls"),
00401                      errhint("To fix this, do REINDEX INDEX \"%s\".",
00402                              RelationGetRelationName(scan->indexRelation))));
00403     }
00404 
00405     pgstat_count_index_scan(scan->indexRelation);
00406 }
00407 
00408 Datum
00409 ginrescan(PG_FUNCTION_ARGS)
00410 {
00411     IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
00412     ScanKey     scankey = (ScanKey) PG_GETARG_POINTER(1);
00413 
00414     /* remaining arguments are ignored */
00415     GinScanOpaque so = (GinScanOpaque) scan->opaque;
00416 
00417     freeScanKeys(so);
00418 
00419     if (scankey && scan->numberOfKeys > 0)
00420     {
00421         memmove(scan->keyData, scankey,
00422                 scan->numberOfKeys * sizeof(ScanKeyData));
00423     }
00424 
00425     PG_RETURN_VOID();
00426 }
00427 
00428 
00429 Datum
00430 ginendscan(PG_FUNCTION_ARGS)
00431 {
00432     IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
00433     GinScanOpaque so = (GinScanOpaque) scan->opaque;
00434 
00435     freeScanKeys(so);
00436 
00437     MemoryContextDelete(so->tempCtx);
00438 
00439     pfree(so);
00440 
00441     PG_RETURN_VOID();
00442 }
00443 
00444 Datum
00445 ginmarkpos(PG_FUNCTION_ARGS)
00446 {
00447     elog(ERROR, "GIN does not support mark/restore");
00448     PG_RETURN_VOID();
00449 }
00450 
00451 Datum
00452 ginrestrpos(PG_FUNCTION_ARGS)
00453 {
00454     elog(ERROR, "GIN does not support mark/restore");
00455     PG_RETURN_VOID();
00456 }