LCOV - code coverage report
Current view: top level - src/backend/access/gin - ginscan.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 178 189 94.2 %
Date: 2025-04-01 14:15:22 Functions: 8 8 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.14