ginscan.c

Go to the documentation of this file.

/*-------------------------------------------------------------------------
 *
 * ginscan.c
 *    routines to manage scans of inverted index relations
 *
 *
 * Portions Copyright (c) 1996-2025, 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 "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         i;
    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 (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 (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 (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);
}