Line data    Source code

       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * ginscan.c
       4             :  *    routines to manage scans of inverted index relations
       5             :  *
       6             :  *
       7             :  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
       8             :  * Portions Copyright (c) 1994, Regents of the University of California
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *          src/backend/access/gin/ginscan.c
      12             :  *-------------------------------------------------------------------------
      13             :  */
      14             : 
      15             : #include "postgres.h"
      16             : 
      17             : #include "access/gin_private.h"
      18             : #include "access/relscan.h"
      19             : #include "pgstat.h"
      20             : #include "utils/memutils.h"
      21             : #include "utils/rel.h"
      22             : 
      23             : 
      24             : IndexScanDesc
      25        1592 : ginbeginscan(Relation rel, int nkeys, int norderbys)
      26             : {
      27             :     IndexScanDesc scan;
      28             :     GinScanOpaque so;
      29             : 
      30             :     /* no order by operators allowed */
      31             :     Assert(norderbys == 0);
      32             : 
      33        1592 :     scan = RelationGetIndexScan(rel, nkeys, norderbys);
      34             : 
      35             :     /* allocate private workspace */
      36        1592 :     so = (GinScanOpaque) palloc(sizeof(GinScanOpaqueData));
      37        1592 :     so->keys = NULL;
      38        1592 :     so->nkeys = 0;
      39        1592 :     so->tempCtx = AllocSetContextCreate(CurrentMemoryContext,
      40             :                                         "Gin scan temporary context",
      41             :                                         ALLOCSET_DEFAULT_SIZES);
      42        1592 :     so->keyCtx = AllocSetContextCreate(CurrentMemoryContext,
      43             :                                        "Gin scan key context",
      44             :                                        ALLOCSET_DEFAULT_SIZES);
      45        1592 :     initGinState(&so->ginstate, scan->indexRelation);
      46             : 
      47        1592 :     scan->opaque = so;
      48             : 
      49        1592 :     return scan;
      50             : }
      51             : 
      52             : /*
      53             :  * Create a new GinScanEntry, unless an equivalent one already exists,
      54             :  * in which case just return it
      55             :  */
      56             : static GinScanEntry
      57        6692 : ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,
      58             :                  StrategyNumber strategy, int32 searchMode,
      59             :                  Datum queryKey, GinNullCategory queryCategory,
      60             :                  bool isPartialMatch, Pointer extra_data)
      61             : {
      62        6692 :     GinState   *ginstate = &so->ginstate;
      63             :     GinScanEntry scanEntry;
      64             :     uint32      i;
      65             : 
      66             :     /*
      67             :      * Look for an existing equivalent entry.
      68             :      *
      69             :      * Entries with non-null extra_data are never considered identical, since
      70             :      * we can't know exactly what the opclass might be doing with that.
      71             :      */
      72        6692 :     if (extra_data == NULL)
      73             :     {
      74      457010 :         for (i = 0; i < so->totalentries; i++)
      75             :         {
      76      452000 :             GinScanEntry prevEntry = so->entries[i];
      77             : 
      78      452000 :             if (prevEntry->extra_data == NULL &&
      79      451700 :                 prevEntry->isPartialMatch == isPartialMatch &&
      80      451700 :                 prevEntry->strategy == strategy &&
      81      451560 :                 prevEntry->searchMode == searchMode &&
      82      903096 :                 prevEntry->attnum == attnum &&
      83      451536 :                 ginCompareEntries(ginstate, attnum,
      84             :                                   prevEntry->queryKey,
      85      451536 :                                   prevEntry->queryCategory,
      86             :                                   queryKey,
      87             :                                   queryCategory) == 0)
      88             :             {
      89             :                 /* Successful match */
      90           0 :                 return prevEntry;
      91             :             }
      92             :         }
      93             :     }
      94             : 
      95             :     /* Nope, create a new entry */
      96        6692 :     scanEntry = (GinScanEntry) palloc(sizeof(GinScanEntryData));
      97        6692 :     scanEntry->queryKey = queryKey;
      98        6692 :     scanEntry->queryCategory = queryCategory;
      99        6692 :     scanEntry->isPartialMatch = isPartialMatch;
     100        6692 :     scanEntry->extra_data = extra_data;
     101        6692 :     scanEntry->strategy = strategy;
     102        6692 :     scanEntry->searchMode = searchMode;
     103        6692 :     scanEntry->attnum = attnum;
     104             : 
     105        6692 :     scanEntry->buffer = InvalidBuffer;
     106        6692 :     ItemPointerSetMin(&scanEntry->curItem);
     107        6692 :     scanEntry->matchBitmap = NULL;
     108        6692 :     scanEntry->matchIterator = NULL;
     109        6692 :     scanEntry->matchResult = NULL;
     110        6692 :     scanEntry->list = NULL;
     111        6692 :     scanEntry->nlist = 0;
     112        6692 :     scanEntry->offset = InvalidOffsetNumber;
     113        6692 :     scanEntry->isFinished = false;
     114        6692 :     scanEntry->reduceResult = false;
     115             : 
     116             :     /* Add it to so's array */
     117        6692 :     if (so->totalentries >= so->allocentries)
     118             :     {
     119          46 :         so->allocentries *= 2;
     120          46 :         so->entries = (GinScanEntry *)
     121          46 :             repalloc(so->entries, so->allocentries * sizeof(GinScanEntry));
     122             :     }
     123        6692 :     so->entries[so->totalentries++] = scanEntry;
     124             : 
     125        6692 :     return scanEntry;
     126             : }
     127             : 
     128             : /*
     129             :  * Append hidden scan entry of given category to the scan key.
     130             :  *
     131             :  * NB: this had better be called at most once per scan key, since
     132             :  * ginFillScanKey leaves room for only one hidden entry.  Currently,
     133             :  * it seems sufficiently clear that this is true that we don't bother
     134             :  * with any cross-check logic.
     135             :  */
     136             : static void
     137         326 : ginScanKeyAddHiddenEntry(GinScanOpaque so, GinScanKey key,
     138             :                          GinNullCategory queryCategory)
     139             : {
     140         326 :     int         i = key->nentries++;
     141             : 
     142             :     /* strategy is of no interest because this is not a partial-match item */
     143         326 :     key->scanEntry[i] = ginFillScanEntry(so, key->attnum,
     144             :                                          InvalidStrategy, key->searchMode,
     145             :                                          (Datum) 0, queryCategory,
     146             :                                          false, NULL);
     147         326 : }
     148             : 
     149             : /*
     150             :  * Initialize the next GinScanKey using the output from the extractQueryFn
     151             :  */
     152             : static void
     153        1714 : ginFillScanKey(GinScanOpaque so, OffsetNumber attnum,
     154             :                StrategyNumber strategy, int32 searchMode,
     155             :                Datum query, uint32 nQueryValues,
     156             :                Datum *queryValues, GinNullCategory *queryCategories,
     157             :                bool *partial_matches, Pointer *extra_data)
     158             : {
     159        1714 :     GinScanKey  key = &(so->keys[so->nkeys++]);
     160        1714 :     GinState   *ginstate = &so->ginstate;
     161             :     uint32      i;
     162             : 
     163        1714 :     key->nentries = nQueryValues;
     164        1714 :     key->nuserentries = nQueryValues;
     165             : 
     166             :     /* Allocate one extra array slot for possible "hidden" entry */
     167        3428 :     key->scanEntry = (GinScanEntry *) palloc(sizeof(GinScanEntry) *
     168        1714 :                                              (nQueryValues + 1));
     169        3428 :     key->entryRes = (GinTernaryValue *) palloc0(sizeof(GinTernaryValue) *
     170        1714 :                                                 (nQueryValues + 1));
     171             : 
     172        1714 :     key->query = query;
     173        1714 :     key->queryValues = queryValues;
     174        1714 :     key->queryCategories = queryCategories;
     175        1714 :     key->extra_data = extra_data;
     176        1714 :     key->strategy = strategy;
     177        1714 :     key->searchMode = searchMode;
     178        1714 :     key->attnum = attnum;
     179             : 
     180             :     /*
     181             :      * Initially, scan keys of GIN_SEARCH_MODE_ALL mode are marked
     182             :      * excludeOnly.  This might get changed later.
     183             :      */
     184        1714 :     key->excludeOnly = (searchMode == GIN_SEARCH_MODE_ALL);
     185             : 
     186        1714 :     ItemPointerSetMin(&key->curItem);
     187        1714 :     key->curItemMatches = false;
     188        1714 :     key->recheckCurItem = false;
     189        1714 :     key->isFinished = false;
     190        1714 :     key->nrequired = 0;
     191        1714 :     key->nadditional = 0;
     192        1714 :     key->requiredEntries = NULL;
     193        1714 :     key->additionalEntries = NULL;
     194             : 
     195        1714 :     ginInitConsistentFunction(ginstate, key);
     196             : 
     197             :     /* Set up normal scan entries using extractQueryFn's outputs */
     198        8080 :     for (i = 0; i < nQueryValues; i++)
     199             :     {
     200             :         Datum       queryKey;
     201             :         GinNullCategory queryCategory;
     202             :         bool        isPartialMatch;
     203             :         Pointer     this_extra;
     204             : 
     205        6366 :         queryKey = queryValues[i];
     206        6366 :         queryCategory = queryCategories[i];
     207        6366 :         isPartialMatch =
     208        6366 :             (ginstate->canPartialMatch[attnum - 1] && partial_matches)
     209        6366 :             ? partial_matches[i] : false;
     210        6366 :         this_extra = (extra_data) ? extra_data[i] : NULL;
     211             : 
     212        6366 :         key->scanEntry[i] = ginFillScanEntry(so, attnum,
     213             :                                              strategy, searchMode,
     214             :                                              queryKey, queryCategory,
     215             :                                              isPartialMatch, this_extra);
     216             :     }
     217             : 
     218             :     /*
     219             :      * For GIN_SEARCH_MODE_INCLUDE_EMPTY and GIN_SEARCH_MODE_EVERYTHING search
     220             :      * modes, we add the "hidden" entry immediately.  GIN_SEARCH_MODE_ALL is
     221             :      * handled later, since we might be able to omit the hidden entry for it.
     222             :      */
     223        1714 :     if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)
     224          44 :         ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_ITEM);
     225        1670 :     else if (searchMode == GIN_SEARCH_MODE_EVERYTHING)
     226           0 :         ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
     227        1714 : }
     228             : 
     229             : /*
     230             :  * Release current scan keys, if any.
     231             :  */
     232             : void
     233        4788 : ginFreeScanKeys(GinScanOpaque so)
     234             : {
     235             :     uint32      i;
     236             : 
     237        4788 :     if (so->keys == NULL)
     238        3190 :         return;
     239             : 
     240        8290 :     for (i = 0; i < so->totalentries; i++)
     241             :     {
     242        6692 :         GinScanEntry entry = so->entries[i];
     243             : 
     244        6692 :         if (entry->buffer != InvalidBuffer)
     245           0 :             ReleaseBuffer(entry->buffer);
     246        6692 :         if (entry->list)
     247        4436 :             pfree(entry->list);
     248        6692 :         if (entry->matchIterator)
     249           0 :             tbm_end_iterate(entry->matchIterator);
     250        6692 :         if (entry->matchBitmap)
     251         534 :             tbm_free(entry->matchBitmap);
     252             :     }
     253             : 
     254        1598 :     MemoryContextReset(so->keyCtx);
     255             : 
     256        1598 :     so->keys = NULL;
     257        1598 :     so->nkeys = 0;
     258        1598 :     so->entries = NULL;
     259        1598 :     so->totalentries = 0;
     260             : }
     261             : 
     262             : void
     263        1598 : ginNewScanKey(IndexScanDesc scan)
     264             : {
     265        1598 :     ScanKey     scankey = scan->keyData;
     266        1598 :     GinScanOpaque so = (GinScanOpaque) scan->opaque;
     267             :     int         i;
     268        1598 :     bool        hasNullQuery = false;
     269        1598 :     bool        attrHasNormalScan[INDEX_MAX_KEYS] = {false};
     270             :     MemoryContext oldCtx;
     271             : 
     272             :     /*
     273             :      * Allocate all the scan key information in the key context. (If
     274             :      * extractQuery leaks anything there, it won't be reset until the end of
     275             :      * scan or rescan, but that's OK.)
     276             :      */
     277        1598 :     oldCtx = MemoryContextSwitchTo(so->keyCtx);
     278             : 
     279             :     /* if no scan keys provided, allocate extra EVERYTHING GinScanKey */
     280        1598 :     so->keys = (GinScanKey)
     281        1598 :         palloc(Max(scan->numberOfKeys, 1) * sizeof(GinScanKeyData));
     282        1598 :     so->nkeys = 0;
     283             : 
     284             :     /* initialize expansible array of GinScanEntry pointers */
     285        1598 :     so->totalentries = 0;
     286        1598 :     so->allocentries = 32;
     287        1598 :     so->entries = (GinScanEntry *)
     288        1598 :         palloc(so->allocentries * sizeof(GinScanEntry));
     289             : 
     290        1598 :     so->isVoidRes = false;
     291             : 
     292        3312 :     for (i = 0; i < scan->numberOfKeys; i++)
     293             :     {
     294        1726 :         ScanKey     skey = &scankey[i];
     295             :         Datum      *queryValues;
     296        1726 :         int32       nQueryValues = 0;
     297        1726 :         bool       *partial_matches = NULL;
     298        1726 :         Pointer    *extra_data = NULL;
     299        1726 :         bool       *nullFlags = NULL;
     300             :         GinNullCategory *categories;
     301        1726 :         int32       searchMode = GIN_SEARCH_MODE_DEFAULT;
     302             : 
     303             :         /*
     304             :          * We assume that GIN-indexable operators are strict, so a null query
     305             :          * argument means an unsatisfiable query.
     306             :          */
     307        1726 :         if (skey->sk_flags & SK_ISNULL)
     308             :         {
     309           0 :             so->isVoidRes = true;
     310          12 :             break;
     311             :         }
     312             : 
     313             :         /* OK to call the extractQueryFn */
     314             :         queryValues = (Datum *)
     315        5178 :             DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[skey->sk_attno - 1],
     316        1726 :                                               so->ginstate.supportCollation[skey->sk_attno - 1],
     317             :                                               skey->sk_argument,
     318             :                                               PointerGetDatum(&nQueryValues),
     319        1726 :                                               UInt16GetDatum(skey->sk_strategy),
     320             :                                               PointerGetDatum(&partial_matches),
     321             :                                               PointerGetDatum(&extra_data),
     322             :                                               PointerGetDatum(&nullFlags),
     323             :                                               PointerGetDatum(&searchMode)));
     324             : 
     325             :         /*
     326             :          * If bogus searchMode is returned, treat as GIN_SEARCH_MODE_ALL; note
     327             :          * in particular we don't allow extractQueryFn to select
     328             :          * GIN_SEARCH_MODE_EVERYTHING.
     329             :          */
     330        1726 :         if (searchMode < GIN_SEARCH_MODE_DEFAULT ||
     331        1726 :             searchMode > GIN_SEARCH_MODE_ALL)
     332           0 :             searchMode = GIN_SEARCH_MODE_ALL;
     333             : 
     334             :         /* Non-default modes require the index to have placeholders */
     335        1726 :         if (searchMode != GIN_SEARCH_MODE_DEFAULT)
     336         364 :             hasNullQuery = true;
     337             : 
     338             :         /*
     339             :          * In default mode, no keys means an unsatisfiable query.
     340             :          */
     341        1726 :         if (queryValues == NULL || nQueryValues <= 0)
     342             :         {
     343         304 :             if (searchMode == GIN_SEARCH_MODE_DEFAULT)
     344             :             {
     345          12 :                 so->isVoidRes = true;
     346          12 :                 break;
     347             :             }
     348         292 :             nQueryValues = 0;   /* ensure sane value */
     349             :         }
     350             : 
     351             :         /*
     352             :          * Create GinNullCategory representation.  If the extractQueryFn
     353             :          * didn't create a nullFlags array, we assume everything is non-null.
     354             :          * While at it, detect whether any null keys are present.
     355             :          */
     356        1714 :         categories = (GinNullCategory *) palloc0(nQueryValues * sizeof(GinNullCategory));
     357        1714 :         if (nullFlags)
     358             :         {
     359             :             int32       j;
     360             : 
     361        4034 :             for (j = 0; j < nQueryValues; j++)
     362             :             {
     363        3464 :                 if (nullFlags[j])
     364             :                 {
     365           0 :                     categories[j] = GIN_CAT_NULL_KEY;
     366           0 :                     hasNullQuery = true;
     367             :                 }
     368             :             }
     369             :         }
     370             : 
     371        1714 :         ginFillScanKey(so, skey->sk_attno,
     372        1714 :                        skey->sk_strategy, searchMode,
     373             :                        skey->sk_argument, nQueryValues,
     374             :                        queryValues, categories,
     375             :                        partial_matches, extra_data);
     376             : 
     377             :         /* Remember if we had any non-excludeOnly keys */
     378        1714 :         if (searchMode != GIN_SEARCH_MODE_ALL)
     379        1394 :             attrHasNormalScan[skey->sk_attno - 1] = true;
     380             :     }
     381             : 
     382             :     /*
     383             :      * Processing GIN_SEARCH_MODE_ALL scan keys requires us to make a second
     384             :      * pass over the scan keys.  Above we marked each such scan key as
     385             :      * excludeOnly.  If the involved column has any normal (not excludeOnly)
     386             :      * scan key as well, then we can leave it like that.  Otherwise, one
     387             :      * excludeOnly scan key must receive a GIN_CAT_EMPTY_QUERY hidden entry
     388             :      * and be set to normal (excludeOnly = false).
     389             :      */
     390        3312 :     for (i = 0; i < so->nkeys; i++)
     391             :     {
     392        1714 :         GinScanKey  key = &so->keys[i];
     393             : 
     394        1714 :         if (key->searchMode != GIN_SEARCH_MODE_ALL)
     395        1394 :             continue;
     396             : 
     397         320 :         if (!attrHasNormalScan[key->attnum - 1])
     398             :         {
     399         282 :             key->excludeOnly = false;
     400         282 :             ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);
     401         282 :             attrHasNormalScan[key->attnum - 1] = true;
     402             :         }
     403             :     }
     404             : 
     405             :     /*
     406             :      * If there are no regular scan keys, generate an EVERYTHING scankey to
     407             :      * drive a full-index scan.
     408             :      */
     409        1598 :     if (so->nkeys == 0 && !so->isVoidRes)
     410             :     {
     411           0 :         hasNullQuery = true;
     412           0 :         ginFillScanKey(so, FirstOffsetNumber,
     413             :                        InvalidStrategy, GIN_SEARCH_MODE_EVERYTHING,
     414             :                        (Datum) 0, 0,
     415             :                        NULL, NULL, NULL, NULL);
     416             :     }
     417             : 
     418             :     /*
     419             :      * If the index is version 0, it may be missing null and placeholder
     420             :      * entries, which would render searches for nulls and full-index scans
     421             :      * unreliable.  Throw an error if so.
     422             :      */
     423        1598 :     if (hasNullQuery && !so->isVoidRes)
     424             :     {
     425             :         GinStatsData ginStats;
     426             : 
     427         324 :         ginGetStats(scan->indexRelation, &ginStats);
     428         324 :         if (ginStats.ginVersion < 1)
     429           0 :             ereport(ERROR,
     430             :                     (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
     431             :                      errmsg("old GIN indexes do not support whole-index scans nor searches for nulls"),
     432             :                      errhint("To fix this, do REINDEX INDEX \"%s\".",
     433             :                              RelationGetRelationName(scan->indexRelation))));
     434             :     }
     435             : 
     436        1598 :     MemoryContextSwitchTo(oldCtx);
     437             : 
     438        1598 :     pgstat_count_index_scan(scan->indexRelation);
     439        1598 : }
     440             : 
     441             : void
     442        1598 : ginrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
     443             :           ScanKey orderbys, int norderbys)
     444             : {
     445        1598 :     GinScanOpaque so = (GinScanOpaque) scan->opaque;
     446             : 
     447        1598 :     ginFreeScanKeys(so);
     448             : 
     449        1598 :     if (scankey && scan->numberOfKeys > 0)
     450        1598 :         memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
     451        1598 : }
     452             : 
     453             : 
     454             : void
     455        1592 : ginendscan(IndexScanDesc scan)
     456             : {
     457        1592 :     GinScanOpaque so = (GinScanOpaque) scan->opaque;
     458             : 
     459        1592 :     ginFreeScanKeys(so);
     460             : 
     461        1592 :     MemoryContextDelete(so->tempCtx);
     462        1592 :     MemoryContextDelete(so->keyCtx);
     463             : 
     464        1592 :     pfree(so);
     465        1592 : }