/*-------------------------------------------------------------------------

 *

 * ginscan.c

 *    routines to manage scans of inverted index relations

 *

 *

 * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group

 * Portions Copyright (c) 1994, Regents of the University of California

 *

 * IDENTIFICATION

 *      src/backend/access/gin/ginscan.c

 *-------------------------------------------------------------------------

 */

#include "postgres.h"

#include "access/gin_private.h"

#include "access/relscan.h"

#include "executor/instrument_node.h"

#include "pgstat.h"

#include "utils/memutils.h"

#include "utils/rel.h"

IndexScanDesc

ginbeginscan(Relation rel, int nkeys, int norderbys)

{

  IndexScanDesc scan;

  GinScanOpaque so;

  /* no order by operators allowed */

  Assert(norderbys == 0);

  scan = RelationGetIndexScan(rel, nkeys, norderbys);

  /* allocate private workspace */

  so = (GinScanOpaque) palloc_object(GinScanOpaqueData);

  so->keys = NULL;

  so->nkeys = 0;

  so->tempCtx = AllocSetContextCreate(CurrentMemoryContext,

                    "Gin scan temporary context",

                    ALLOCSET_DEFAULT_SIZES);

  so->keyCtx = AllocSetContextCreate(CurrentMemoryContext,

                     "Gin scan key context",

                     ALLOCSET_DEFAULT_SIZES);

  initGinState(&so->ginstate, scan->indexRelation);

  scan->opaque = so;

  return scan;

}

/*

 * Create a new GinScanEntry, unless an equivalent one already exists,

 * in which case just return it

 */

static GinScanEntry

ginFillScanEntry(GinScanOpaque so, OffsetNumber attnum,

         StrategyNumber strategy, int32 searchMode,

         Datum queryKey, GinNullCategory queryCategory,

         bool isPartialMatch, Pointer extra_data)

{

  GinState   *ginstate = &so->ginstate;

  GinScanEntry scanEntry;

  uint32    i;

  /*

   * Look for an existing equivalent entry.

   *

   * Entries with non-null extra_data are never considered identical, since

   * we can't know exactly what the opclass might be doing with that.

   *

   * Also, give up de-duplication once we have 100 entries.  That avoids

   * spending O(N^2) time on probably-fruitless de-duplication of large

   * search-key sets.  The threshold of 100 is arbitrary but matches

   * predtest.c's threshold for what's a large array.

   */

  if (extra_data == NULL && so->totalentries < 100)

  {

    for (i = 0; i < so->totalentries; i++)

    {

      GinScanEntry prevEntry = so->entries[i];

      if (prevEntry->extra_data == NULL &&

        prevEntry->isPartialMatch == isPartialMatch &&

        prevEntry->strategy == strategy &&

        prevEntry->searchMode == searchMode &&

        prevEntry->attnum == attnum &&

        ginCompareEntries(ginstate, attnum,

                  prevEntry->queryKey,

                  prevEntry->queryCategory,

                  queryKey,

                  queryCategory) == 0)

      {

        /* Successful match */

        return prevEntry;

      }

    }

  }

  /* Nope, create a new entry */

  scanEntry = palloc_object(GinScanEntryData);

  scanEntry->queryKey = queryKey;

  scanEntry->queryCategory = queryCategory;

  scanEntry->isPartialMatch = isPartialMatch;

  scanEntry->extra_data = extra_data;

  scanEntry->strategy = strategy;

  scanEntry->searchMode = searchMode;

  scanEntry->attnum = attnum;

  scanEntry->buffer = InvalidBuffer;

  ItemPointerSetMin(&scanEntry->curItem);

  scanEntry->matchBitmap = NULL;

  scanEntry->matchIterator = NULL;

  scanEntry->matchResult.blockno = InvalidBlockNumber;

  scanEntry->matchNtuples = -1;

  scanEntry->list = NULL;

  scanEntry->nlist = 0;

  scanEntry->offset = InvalidOffsetNumber;

  scanEntry->isFinished = false;

  scanEntry->reduceResult = false;

  /* Add it to so's array */

  if (so->totalentries >= so->allocentries)

  {

    so->allocentries *= 2;

    so->entries = repalloc_array(so->entries, GinScanEntry, so->allocentries);

  }

  so->entries[so->totalentries++] = scanEntry;

  return scanEntry;

}

/*

 * Append hidden scan entry of given category to the scan key.

 *

 * NB: this had better be called at most once per scan key, since

 * ginFillScanKey leaves room for only one hidden entry.  Currently,

 * it seems sufficiently clear that this is true that we don't bother

 * with any cross-check logic.

 */

static void

ginScanKeyAddHiddenEntry(GinScanOpaque so, GinScanKey key,

             GinNullCategory queryCategory)

{

  int     i = key->nentries++;

  /* strategy is of no interest because this is not a partial-match item */

  key->scanEntry[i] = ginFillScanEntry(so, key->attnum,

                     InvalidStrategy, key->searchMode,

                     (Datum) 0, queryCategory,

                     false, NULL);

}

/*

 * Initialize the next GinScanKey using the output from the extractQueryFn

 */

static void

ginFillScanKey(GinScanOpaque so, OffsetNumber attnum,

         StrategyNumber strategy, int32 searchMode,

         Datum query, uint32 nQueryValues,

         Datum *queryValues, GinNullCategory *queryCategories,

         bool *partial_matches, Pointer *extra_data)

{

  GinScanKey  key = &(so->keys[so->nkeys++]);

  GinState   *ginstate = &so->ginstate;

  uint32    i;

  key->nentries = nQueryValues;

  key->nuserentries = nQueryValues;

  /* Allocate one extra array slot for possible "hidden" entry */

  key->scanEntry = palloc_array(GinScanEntry, nQueryValues + 1);

  key->entryRes = palloc0_array(GinTernaryValue, nQueryValues + 1);

  key->query = query;

  key->queryValues = queryValues;

  key->queryCategories = queryCategories;

  key->extra_data = extra_data;

  key->strategy = strategy;

  key->searchMode = searchMode;

  key->attnum = attnum;

  /*

   * Initially, scan keys of GIN_SEARCH_MODE_ALL mode are marked

   * excludeOnly.  This might get changed later.

   */

  key->excludeOnly = (searchMode == GIN_SEARCH_MODE_ALL);

  ItemPointerSetMin(&key->curItem);

  key->curItemMatches = false;

  key->recheckCurItem = false;

  key->isFinished = false;

  key->nrequired = 0;

  key->nadditional = 0;

  key->requiredEntries = NULL;

  key->additionalEntries = NULL;

  ginInitConsistentFunction(ginstate, key);

  /* Set up normal scan entries using extractQueryFn's outputs */

  for (i = 0; i < nQueryValues; i++)

  {

    Datum   queryKey;

    GinNullCategory queryCategory;

    bool    isPartialMatch;

    Pointer   this_extra;

    queryKey = queryValues[i];

    queryCategory = queryCategories[i];

    isPartialMatch =

      (ginstate->canPartialMatch[attnum - 1] && partial_matches)

      ? partial_matches[i] : false;

    this_extra = (extra_data) ? extra_data[i] : NULL;

    key->scanEntry[i] = ginFillScanEntry(so, attnum,

                       strategy, searchMode,

                       queryKey, queryCategory,

                       isPartialMatch, this_extra);

  }

  /*

   * For GIN_SEARCH_MODE_INCLUDE_EMPTY and GIN_SEARCH_MODE_EVERYTHING search

   * modes, we add the "hidden" entry immediately.  GIN_SEARCH_MODE_ALL is

   * handled later, since we might be able to omit the hidden entry for it.

   */

  if (searchMode == GIN_SEARCH_MODE_INCLUDE_EMPTY)

    ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_ITEM);

  else if (searchMode == GIN_SEARCH_MODE_EVERYTHING)

    ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);

}

/*

 * Release current scan keys, if any.

 */

void

ginFreeScanKeys(GinScanOpaque so)

{

  uint32    i;

  if (so->keys == NULL)

    return;

  for (i = 0; i < so->totalentries; i++)

  {

    GinScanEntry entry = so->entries[i];

    if (entry->buffer != InvalidBuffer)

      ReleaseBuffer(entry->buffer);

    if (entry->list)

      pfree(entry->list);

    if (entry->matchIterator)

      tbm_end_private_iterate(entry->matchIterator);

    if (entry->matchBitmap)

      tbm_free(entry->matchBitmap);

  }

  MemoryContextReset(so->keyCtx);

  so->keys = NULL;

  so->nkeys = 0;

  so->entries = NULL;

  so->totalentries = 0;

}

void

ginNewScanKey(IndexScanDesc scan)

{

  ScanKey   scankey = scan->keyData;

  GinScanOpaque so = (GinScanOpaque) scan->opaque;

  int     numExcludeOnly;

  bool    hasNullQuery = false;

  bool    attrHasNormalScan[INDEX_MAX_KEYS] = {false};

  MemoryContext oldCtx;

  /*

   * Allocate all the scan key information in the key context. (If

   * extractQuery leaks anything there, it won't be reset until the end of

   * scan or rescan, but that's OK.)

   */

  oldCtx = MemoryContextSwitchTo(so->keyCtx);

  /* if no scan keys provided, allocate extra EVERYTHING GinScanKey */

  so->keys = (GinScanKey)

    palloc(Max(scan->numberOfKeys, 1) * sizeof(GinScanKeyData));

  so->nkeys = 0;

  /* initialize expansible array of GinScanEntry pointers */

  so->totalentries = 0;

  so->allocentries = 32;

  so->entries = (GinScanEntry *)

    palloc(so->allocentries * sizeof(GinScanEntry));

  so->isVoidRes = false;

  for (int i = 0; i < scan->numberOfKeys; i++)

  {

    ScanKey   skey = &scankey[i];

    Datum    *queryValues;

    int32   nQueryValues = 0;

    bool     *partial_matches = NULL;

    Pointer    *extra_data = NULL;

    bool     *nullFlags = NULL;

    GinNullCategory *categories;

    int32   searchMode = GIN_SEARCH_MODE_DEFAULT;

    /*

     * We assume that GIN-indexable operators are strict, so a null query

     * argument means an unsatisfiable query.

     */

    if (skey->sk_flags & SK_ISNULL)

    {

      so->isVoidRes = true;

      break;

    }

    /* OK to call the extractQueryFn */

    queryValues = (Datum *)

      DatumGetPointer(FunctionCall7Coll(&so->ginstate.extractQueryFn[skey->sk_attno - 1],

                        so->ginstate.supportCollation[skey->sk_attno - 1],

                        skey->sk_argument,

                        PointerGetDatum(&nQueryValues),

                        UInt16GetDatum(skey->sk_strategy),

                        PointerGetDatum(&partial_matches),

                        PointerGetDatum(&extra_data),

                        PointerGetDatum(&nullFlags),

                        PointerGetDatum(&searchMode)));

    /*

     * If bogus searchMode is returned, treat as GIN_SEARCH_MODE_ALL; note

     * in particular we don't allow extractQueryFn to select

     * GIN_SEARCH_MODE_EVERYTHING.

     */

    if (searchMode < GIN_SEARCH_MODE_DEFAULT ||

      searchMode > GIN_SEARCH_MODE_ALL)

      searchMode = GIN_SEARCH_MODE_ALL;

    /* Non-default modes require the index to have placeholders */

    if (searchMode != GIN_SEARCH_MODE_DEFAULT)

      hasNullQuery = true;

    /*

     * In default mode, no keys means an unsatisfiable query.

     */

    if (queryValues == NULL || nQueryValues <= 0)

    {

      if (searchMode == GIN_SEARCH_MODE_DEFAULT)

      {

        so->isVoidRes = true;

        break;

      }

      nQueryValues = 0; /* ensure sane value */

    }

    /*

     * Create GinNullCategory representation.  If the extractQueryFn

     * didn't create a nullFlags array, we assume everything is non-null.

     * While at it, detect whether any null keys are present.

     */

    categories = (GinNullCategory *) palloc0(nQueryValues * sizeof(GinNullCategory));

    if (nullFlags)

    {

      int32   j;

      for (j = 0; j < nQueryValues; j++)

      {

        if (nullFlags[j])

        {

          categories[j] = GIN_CAT_NULL_KEY;

          hasNullQuery = true;

        }

      }

    }

    ginFillScanKey(so, skey->sk_attno,

             skey->sk_strategy, searchMode,

             skey->sk_argument, nQueryValues,

             queryValues, categories,

             partial_matches, extra_data);

    /* Remember if we had any non-excludeOnly keys */

    if (searchMode != GIN_SEARCH_MODE_ALL)

      attrHasNormalScan[skey->sk_attno - 1] = true;

  }

  /*

   * Processing GIN_SEARCH_MODE_ALL scan keys requires us to make a second

   * pass over the scan keys.  Above we marked each such scan key as

   * excludeOnly.  If the involved column has any normal (not excludeOnly)

   * scan key as well, then we can leave it like that.  Otherwise, one

   * excludeOnly scan key must receive a GIN_CAT_EMPTY_QUERY hidden entry

   * and be set to normal (excludeOnly = false).

   */

  numExcludeOnly = 0;

  for (uint32 i = 0; i < so->nkeys; i++)

  {

    GinScanKey  key = &so->keys[i];

    if (key->searchMode != GIN_SEARCH_MODE_ALL)

      continue;

    if (!attrHasNormalScan[key->attnum - 1])

    {

      key->excludeOnly = false;

      ginScanKeyAddHiddenEntry(so, key, GIN_CAT_EMPTY_QUERY);

      attrHasNormalScan[key->attnum - 1] = true;

    }

    else

      numExcludeOnly++;

  }

  /*

   * If we left any excludeOnly scan keys as-is, move them to the end of the

   * scan key array: they must appear after normal key(s).

   */

  if (numExcludeOnly > 0)

  {

    GinScanKey  tmpkeys;

    int     iNormalKey;

    int     iExcludeOnly;

    /* We'd better have made at least one normal key */

    Assert(numExcludeOnly < so->nkeys);

    /* Make a temporary array to hold the re-ordered scan keys */

    tmpkeys = (GinScanKey) palloc(so->nkeys * sizeof(GinScanKeyData));

    /* Re-order the keys ... */

    iNormalKey = 0;

    iExcludeOnly = so->nkeys - numExcludeOnly;

    for (uint32 i = 0; i < so->nkeys; i++)

    {

      GinScanKey  key = &so->keys[i];

      if (key->excludeOnly)

      {

        memcpy(tmpkeys + iExcludeOnly, key, sizeof(GinScanKeyData));

        iExcludeOnly++;

      }

      else

      {

        memcpy(tmpkeys + iNormalKey, key, sizeof(GinScanKeyData));

        iNormalKey++;

      }

    }

    Assert(iNormalKey == so->nkeys - numExcludeOnly);

    Assert(iExcludeOnly == so->nkeys);

    /* ... and copy them back to so->keys[] */

    memcpy(so->keys, tmpkeys, so->nkeys * sizeof(GinScanKeyData));

    pfree(tmpkeys);

  }

  /*

   * If there are no regular scan keys, generate an EVERYTHING scankey to

   * drive a full-index scan.

   */

  if (so->nkeys == 0 && !so->isVoidRes)

  {

    hasNullQuery = true;

    ginFillScanKey(so, FirstOffsetNumber,

             InvalidStrategy, GIN_SEARCH_MODE_EVERYTHING,

             (Datum) 0, 0,

             NULL, NULL, NULL, NULL);

  }

  /*

   * If the index is version 0, it may be missing null and placeholder

   * entries, which would render searches for nulls and full-index scans

   * unreliable.  Throw an error if so.

   */

  if (hasNullQuery && !so->isVoidRes)

  {

    GinStatsData ginStats;

    ginGetStats(scan->indexRelation, &ginStats);

    if (ginStats.ginVersion < 1)

      ereport(ERROR,

          (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),

           errmsg("old GIN indexes do not support whole-index scans nor searches for nulls"),

           errhint("To fix this, do REINDEX INDEX \"%s\".",

               RelationGetRelationName(scan->indexRelation))));

  }

  MemoryContextSwitchTo(oldCtx);

  pgstat_count_index_scan(scan->indexRelation);

  if (scan->instrument)

    scan->instrument->nsearches++;

}

void

ginrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,

      ScanKey orderbys, int norderbys)

{

  GinScanOpaque so = (GinScanOpaque) scan->opaque;

  ginFreeScanKeys(so);

  if (scankey && scan->numberOfKeys > 0)

    memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));

}

void

ginendscan(IndexScanDesc scan)

{

  GinScanOpaque so = (GinScanOpaque) scan->opaque;

  ginFreeScanKeys(so);

  MemoryContextDelete(so->tempCtx);

  MemoryContextDelete(so->keyCtx);

  pfree(so);

}