#include "postgres.h"
#include "access/genam.h"
#include "access/relscan.h"
#include "access/spgist_private.h"
#include "executor/instrument_node.h"
#include "miscadmin.h"
#include "pgstat.h"
#include "storage/bufmgr.h"
#include "utils/datum.h"
#include "utils/float.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/rel.h"

Include dependency graph for spgscan.c:

Typedefs
typedef void(*	storeRes_func) (SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isNull, SpGistLeafTuple leafTuple, bool recheck, bool recheckDistances, double *distances)

Enumerations
enum	SpGistSpecialOffsetNumbers { SpGistBreakOffsetNumber = InvalidOffsetNumber , SpGistRedirectOffsetNumber = MaxOffsetNumber + 1 , SpGistErrorOffsetNumber = MaxOffsetNumber + 2 }

Functions
static int	pairingheap_SpGistSearchItem_cmp (const pairingheap_node a, const pairingheap_node b, void *arg)

static void	spgFreeSearchItem (SpGistScanOpaque so, SpGistSearchItem *item)

static void	spgAddSearchItemToQueue (SpGistScanOpaque so, SpGistSearchItem *item)

static SpGistSearchItem *	spgAllocSearchItem (SpGistScanOpaque so, bool isnull, double *distances)

static void	spgAddStartItem (SpGistScanOpaque so, bool isnull)

static void	resetSpGistScanOpaque (SpGistScanOpaque so)

static void	spgPrepareScanKeys (IndexScanDesc scan)

IndexScanDesc	spgbeginscan (Relation rel, int keysz, int orderbysz)

void	spgrescan (IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)

void	spgendscan (IndexScanDesc scan)

static SpGistSearchItem *	spgNewHeapItem (SpGistScanOpaque so, int level, SpGistLeafTuple leafTuple, Datum leafValue, bool recheck, bool recheckDistances, bool isnull, double *distances)

static bool	spgLeafTest (SpGistScanOpaque so, SpGistSearchItem item, SpGistLeafTuple leafTuple, bool isnull, bool reportedSome, storeRes_func storeRes)

static void	spgInitInnerConsistentIn (spgInnerConsistentIn in, SpGistScanOpaque so, SpGistSearchItem item, SpGistInnerTuple innerTuple)

static SpGistSearchItem *	spgMakeInnerItem (SpGistScanOpaque so, SpGistSearchItem parentItem, SpGistNodeTuple tuple, spgInnerConsistentOut out, int i, bool isnull, double *distances)

static void	spgInnerTest (SpGistScanOpaque so, SpGistSearchItem *item, SpGistInnerTuple innerTuple, bool isnull)

static SpGistSearchItem *	spgGetNextQueueItem (SpGistScanOpaque so)

static OffsetNumber	spgTestLeafTuple (SpGistScanOpaque so, SpGistSearchItem item, Page page, OffsetNumber offset, bool isnull, bool isroot, bool reportedSome, storeRes_func storeRes)

static void	spgWalk (Relation index, SpGistScanOpaque so, bool scanWholeIndex, storeRes_func storeRes)

static void	storeBitmap (SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isnull, SpGistLeafTuple leafTuple, bool recheck, bool recheckDistances, double *distances)

int64	spggetbitmap (IndexScanDesc scan, TIDBitmap *tbm)

static void	storeGettuple (SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isnull, SpGistLeafTuple leafTuple, bool recheck, bool recheckDistances, double *nonNullDistances)

bool	spggettuple (IndexScanDesc scan, ScanDirection dir)

bool	spgcanreturn (Relation index, int attno)

Typedef Documentation

◆ storeRes_func

typedef void(* storeRes_func) (SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isNull, SpGistLeafTuple leafTuple, bool recheck, bool recheckDistances, double *distances)

Definition at line 31 of file spgscan.c.

Enumeration Type Documentation

◆ SpGistSpecialOffsetNumbers

enum SpGistSpecialOffsetNumbers

Enumerator
SpGistBreakOffsetNumber
SpGistRedirectOffsetNumber
SpGistErrorOffsetNumber

Definition at line 750 of file spgscan.c.

{
    SpGistBreakOffsetNumber = InvalidOffsetNumber,
    SpGistRedirectOffsetNumber = MaxOffsetNumber + 1,
    SpGistErrorOffsetNumber = MaxOffsetNumber + 2,
};

Function Documentation

◆ pairingheap_SpGistSearchItem_cmp()

static int pairingheap_SpGistSearchItem_cmp	(	const pairingheap_node *	a,
		const pairingheap_node *	b,
		void *	arg
	)

static

Definition at line 42 of file spgscan.c.

{
    const SpGistSearchItem *sa = (const SpGistSearchItem *) a;
    const SpGistSearchItem *sb = (const SpGistSearchItem *) b;
    SpGistScanOpaque so = (SpGistScanOpaque) arg;
    int         i;
 
    if (sa->isNull)
    {
        if (!sb->isNull)
            return -1;
    }
    else if (sb->isNull)
    {
        return 1;
    }
    else
    {
        /* Order according to distance comparison */
        for (i = 0; i < so->numberOfNonNullOrderBys; i++)
        {
            if (isnan(sa->distances[i]) && isnan(sb->distances[i]))
                continue;       /* NaN == NaN */
            if (isnan(sa->distances[i]))
                return -1;      /* NaN > number */
            if (isnan(sb->distances[i]))
                return 1;       /* number < NaN */
            if (sa->distances[i] != sb->distances[i])
                return (sa->distances[i] < sb->distances[i]) ? 1 : -1;
        }
    }
 
    /* Leaf items go before inner pages, to ensure a depth-first search */
    if (sa->isLeaf && !sb->isLeaf)
        return 1;
    if (!sa->isLeaf && sb->isLeaf)
        return -1;
 
    return 0;
}

References a, arg, b, SpGistSearchItem::distances, i, SpGistSearchItem::isLeaf, SpGistSearchItem::isNull, and SpGistScanOpaqueData::numberOfNonNullOrderBys.

Referenced by resetSpGistScanOpaque().

◆ resetSpGistScanOpaque()

static void resetSpGistScanOpaque ( SpGistScanOpaque so )

static

Definition at line 155 of file spgscan.c.

{
    MemoryContext oldCtx;
 
    MemoryContextReset(so->traversalCxt);
 
    oldCtx = MemoryContextSwitchTo(so->traversalCxt);
 
    /* initialize queue only for distance-ordered scans */
    so->scanQueue = pairingheap_allocate(pairingheap_SpGistSearchItem_cmp, so);
 
    if (so->searchNulls)
        /* Add a work item to scan the null index entries */
        spgAddStartItem(so, true);
 
    if (so->searchNonNulls)
        /* Add a work item to scan the non-null index entries */
        spgAddStartItem(so, false);
 
    MemoryContextSwitchTo(oldCtx);
 
    if (so->numberOfOrderBys > 0)
    {
        /* Must pfree distances to avoid memory leak */
        int         i;
 
        for (i = 0; i < so->nPtrs; i++)
            if (so->distances[i])
                pfree(so->distances[i]);
    }
 
    if (so->want_itup)
    {
        /* Must pfree reconstructed tuples to avoid memory leak */
        int         i;
 
        for (i = 0; i < so->nPtrs; i++)
            pfree(so->reconTups[i]);
    }
    so->iPtr = so->nPtrs = 0;
}

References SpGistScanOpaqueData::distances, i, SpGistScanOpaqueData::iPtr, MemoryContextReset(), MemoryContextSwitchTo(), SpGistScanOpaqueData::nPtrs, SpGistScanOpaqueData::numberOfOrderBys, pairingheap_allocate(), pairingheap_SpGistSearchItem_cmp(), pfree(), SpGistScanOpaqueData::reconTups, SpGistScanOpaqueData::scanQueue, SpGistScanOpaqueData::searchNonNulls, SpGistScanOpaqueData::searchNulls, spgAddStartItem(), SpGistScanOpaqueData::traversalCxt, and SpGistScanOpaqueData::want_itup.

Referenced by spgrescan().

◆ spgAddSearchItemToQueue()

static void spgAddSearchItemToQueue	(	SpGistScanOpaque	so,
		SpGistSearchItem *	item
	)

static

Definition at line 109 of file spgscan.c.

{
    pairingheap_add(so->scanQueue, &item->phNode);
}

References pairingheap_add(), SpGistSearchItem::phNode, and SpGistScanOpaqueData::scanQueue.

Referenced by spgAddStartItem(), spgInnerTest(), and spgLeafTest().

◆ spgAddStartItem()

static void spgAddStartItem	(	SpGistScanOpaque	so,
		bool	isnull
	)

static

Definition at line 131 of file spgscan.c.

{
    SpGistSearchItem *startEntry =
        spgAllocSearchItem(so, isnull, so->zeroDistances);
 
    ItemPointerSet(&startEntry->heapPtr,
                   isnull ? SPGIST_NULL_BLKNO : SPGIST_ROOT_BLKNO,
                   FirstOffsetNumber);
    startEntry->isLeaf = false;
    startEntry->level = 0;
    startEntry->value = (Datum) 0;
    startEntry->leafTuple = NULL;
    startEntry->traversalValue = NULL;
    startEntry->recheck = false;
    startEntry->recheckDistances = false;
 
    spgAddSearchItemToQueue(so, startEntry);
}

References FirstOffsetNumber, SpGistSearchItem::heapPtr, SpGistSearchItem::isLeaf, ItemPointerSet(), SpGistSearchItem::leafTuple, SpGistSearchItem::level, SpGistSearchItem::recheck, SpGistSearchItem::recheckDistances, spgAddSearchItemToQueue(), spgAllocSearchItem(), SPGIST_NULL_BLKNO, SPGIST_ROOT_BLKNO, SpGistSearchItem::traversalValue, SpGistSearchItem::value, and SpGistScanOpaqueData::zeroDistances.

Referenced by resetSpGistScanOpaque().

◆ spgAllocSearchItem()

static SpGistSearchItem * spgAllocSearchItem	(	SpGistScanOpaque	so,
		bool	isnull,
		double *	distances
	)

static

Definition at line 115 of file spgscan.c.

{
    /* allocate distance array only for non-NULL items */
    SpGistSearchItem *item =
        palloc(SizeOfSpGistSearchItem(isnull ? 0 : so->numberOfNonNullOrderBys));
 
    item->isNull = isnull;
 
    if (!isnull && so->numberOfNonNullOrderBys > 0)
        memcpy(item->distances, distances,
               sizeof(item->distances[0]) * so->numberOfNonNullOrderBys);
 
    return item;
}

References SpGistSearchItem::distances, SpGistSearchItem::isNull, SpGistScanOpaqueData::numberOfNonNullOrderBys, palloc(), and SizeOfSpGistSearchItem.

Referenced by spgAddStartItem(), spgMakeInnerItem(), and spgNewHeapItem().

◆ spgbeginscan()

IndexScanDesc spgbeginscan	(	Relation	rel,
		int	keysz,
		int	orderbysz
	)

Definition at line 305 of file spgscan.c.

{
    IndexScanDesc scan;
    SpGistScanOpaque so;
    int         i;
 
    scan = RelationGetIndexScan(rel, keysz, orderbysz);
 
    so = palloc0_object(SpGistScanOpaqueData);
    if (keysz > 0)
        so->keyData = palloc_array(ScanKeyData, keysz);
    else
        so->keyData = NULL;
    initSpGistState(&so->state, scan->indexRelation);
 
    so->tempCxt = AllocSetContextCreate(CurrentMemoryContext,
                                        "SP-GiST search temporary context",
                                        ALLOCSET_DEFAULT_SIZES);
    so->traversalCxt = AllocSetContextCreate(CurrentMemoryContext,
                                             "SP-GiST traversal-value context",
                                             ALLOCSET_DEFAULT_SIZES);
 
    /*
     * Set up reconTupDesc and xs_hitupdesc in case it's an index-only scan,
     * making sure that the key column is shown as being of type attType.
     * (It's rather annoying to do this work when it might be wasted, but for
     * most opclasses we can re-use the index reldesc instead of making one.)
     */
    so->reconTupDesc = scan->xs_hitupdesc =
        getSpGistTupleDesc(rel, &so->state.attType);
 
    /* Allocate various arrays needed for order-by scans */
    if (scan->numberOfOrderBys > 0)
    {
        /* This will be filled in spgrescan, but allocate the space here */
        so->orderByTypes = palloc_array(Oid, scan->numberOfOrderBys);
        so->nonNullOrderByOffsets = palloc_array(int, scan->numberOfOrderBys);
 
        /* These arrays have constant contents, so we can fill them now */
        so->zeroDistances = palloc_array(double, scan->numberOfOrderBys);
        so->infDistances = palloc_array(double, scan->numberOfOrderBys);
 
        for (i = 0; i < scan->numberOfOrderBys; i++)
        {
            so->zeroDistances[i] = 0.0;
            so->infDistances[i] = get_float8_infinity();
        }
 
        scan->xs_orderbyvals = palloc0_array(Datum, scan->numberOfOrderBys);
        scan->xs_orderbynulls = palloc_array(bool, scan->numberOfOrderBys);
        memset(scan->xs_orderbynulls, true,
               sizeof(bool) * scan->numberOfOrderBys);
    }
 
    fmgr_info_copy(&so->innerConsistentFn,
                   index_getprocinfo(rel, 1, SPGIST_INNER_CONSISTENT_PROC),
                   CurrentMemoryContext);
 
    fmgr_info_copy(&so->leafConsistentFn,
                   index_getprocinfo(rel, 1, SPGIST_LEAF_CONSISTENT_PROC),
                   CurrentMemoryContext);
 
    so->indexCollation = rel->rd_indcollation[0];
 
    scan->opaque = so;
 
    return scan;
}

Referenced by spghandler().

◆ spgcanreturn()

bool spgcanreturn	(	Relation	index,
		int	attno
	)

Definition at line 1078 of file spgscan.c.

{
    SpGistCache *cache;
 
    /* INCLUDE attributes can always be fetched for index-only scans */
    if (attno > 1)
        return true;
 
    /* We can do it if the opclass config function says so */
    cache = spgGetCache(index);
 
    return cache->config.canReturnData;
}

References spgConfigOut::canReturnData, SpGistCache::config, and spgGetCache().

Referenced by spghandler().

◆ spgendscan()

void spgendscan ( IndexScanDesc scan )

Definition at line 424 of file spgscan.c.

{
    SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
 
    MemoryContextDelete(so->tempCxt);
    MemoryContextDelete(so->traversalCxt);
 
    if (so->keyData)
        pfree(so->keyData);
 
    if (so->state.leafTupDesc &&
        so->state.leafTupDesc != RelationGetDescr(so->state.index))
        FreeTupleDesc(so->state.leafTupDesc);
 
    if (so->state.deadTupleStorage)
        pfree(so->state.deadTupleStorage);
 
    if (scan->numberOfOrderBys > 0)
    {
        pfree(so->orderByTypes);
        pfree(so->nonNullOrderByOffsets);
        pfree(so->zeroDistances);
        pfree(so->infDistances);
        pfree(scan->xs_orderbyvals);
        pfree(scan->xs_orderbynulls);
    }
 
    pfree(so);
}

References SpGistState::deadTupleStorage, FreeTupleDesc(), SpGistState::index, SpGistScanOpaqueData::infDistances, SpGistScanOpaqueData::keyData, SpGistState::leafTupDesc, MemoryContextDelete(), SpGistScanOpaqueData::nonNullOrderByOffsets, IndexScanDescData::numberOfOrderBys, IndexScanDescData::opaque, SpGistScanOpaqueData::orderByTypes, pfree(), RelationGetDescr, SpGistScanOpaqueData::state, SpGistScanOpaqueData::tempCxt, SpGistScanOpaqueData::traversalCxt, IndexScanDescData::xs_orderbynulls, IndexScanDescData::xs_orderbyvals, and SpGistScanOpaqueData::zeroDistances.

Referenced by spghandler().

◆ spgFreeSearchItem()

static void spgFreeSearchItem	(	SpGistScanOpaque	so,
		SpGistSearchItem *	item
	)

static

Definition at line 85 of file spgscan.c.

{
    /* value is of type attType if isLeaf, else of type attLeafType */
    /* (no, that is not backwards; yes, it's confusing) */
    if (!(item->isLeaf ? so->state.attType.attbyval :
          so->state.attLeafType.attbyval) &&
        DatumGetPointer(item->value) != NULL)
        pfree(DatumGetPointer(item->value));
 
    if (item->leafTuple)
        pfree(item->leafTuple);
 
    if (item->traversalValue)
        pfree(item->traversalValue);
 
    pfree(item);
}

References SpGistTypeDesc::attbyval, SpGistState::attLeafType, SpGistState::attType, DatumGetPointer(), SpGistSearchItem::isLeaf, SpGistSearchItem::leafTuple, pfree(), SpGistScanOpaqueData::state, SpGistSearchItem::traversalValue, and SpGistSearchItem::value.

Referenced by spgWalk().

◆ spggetbitmap()

int64 spggetbitmap	(	IndexScanDesc	scan,
		TIDBitmap *	tbm
	)

Definition at line 937 of file spgscan.c.

{
    SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
 
    /* Copy want_itup to *so so we don't need to pass it around separately */
    so->want_itup = false;
 
    so->tbm = tbm;
    so->ntids = 0;
 
    spgWalk(scan->indexRelation, so, true, storeBitmap);
 
    return so->ntids;
}

References IndexScanDescData::indexRelation, SpGistScanOpaqueData::ntids, IndexScanDescData::opaque, spgWalk(), storeBitmap(), SpGistScanOpaqueData::tbm, and SpGistScanOpaqueData::want_itup.

Referenced by spghandler().

◆ spgGetNextQueueItem()

static SpGistSearchItem * spgGetNextQueueItem ( SpGistScanOpaque so )

static

Definition at line 741 of file spgscan.c.

{
    if (pairingheap_is_empty(so->scanQueue))
        return NULL;            /* Done when both heaps are empty */
 
    /* Return item; caller is responsible to pfree it */
    return (SpGistSearchItem *) pairingheap_remove_first(so->scanQueue);
}

References pairingheap_is_empty, pairingheap_remove_first(), and SpGistScanOpaqueData::scanQueue.

Referenced by spgWalk().

◆ spggettuple()

bool spggettuple	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 1021 of file spgscan.c.

{
    SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
 
    if (dir != ForwardScanDirection)
        elog(ERROR, "SP-GiST only supports forward scan direction");
 
    /* Copy want_itup to *so so we don't need to pass it around separately */
    so->want_itup = scan->xs_want_itup;
 
    for (;;)
    {
        if (so->iPtr < so->nPtrs)
        {
            /* continuing to return reported tuples */
            scan->xs_heaptid = so->heapPtrs[so->iPtr];
            scan->xs_recheck = so->recheck[so->iPtr];
            scan->xs_hitup = so->reconTups[so->iPtr];
 
            if (so->numberOfOrderBys > 0)
                index_store_float8_orderby_distances(scan, so->orderByTypes,
                                                     so->distances[so->iPtr],
                                                     so->recheckDistances[so->iPtr]);
            so->iPtr++;
            return true;
        }
 
        if (so->numberOfOrderBys > 0)
        {
            /* Must pfree distances to avoid memory leak */
            int         i;
 
            for (i = 0; i < so->nPtrs; i++)
                if (so->distances[i])
                    pfree(so->distances[i]);
        }
 
        if (so->want_itup)
        {
            /* Must pfree reconstructed tuples to avoid memory leak */
            int         i;
 
            for (i = 0; i < so->nPtrs; i++)
                pfree(so->reconTups[i]);
        }
        so->iPtr = so->nPtrs = 0;
 
        spgWalk(scan->indexRelation, so, false, storeGettuple);
 
        if (so->nPtrs == 0)
            break;              /* must have completed scan */
    }
 
    return false;
}

Referenced by spghandler().

◆ spgInitInnerConsistentIn()

static void spgInitInnerConsistentIn	(	spgInnerConsistentIn *	in,
		SpGistScanOpaque	so,
		SpGistSearchItem *	item,
		SpGistInnerTuple	innerTuple
	)

static

Definition at line 601 of file spgscan.c.

{
    in->scankeys = so->keyData;
    in->orderbys = so->orderByData;
    in->nkeys = so->numberOfKeys;
    in->norderbys = so->numberOfNonNullOrderBys;
    Assert(!item->isLeaf);      /* else reconstructedValue would be wrong type */
    in->reconstructedValue = item->value;
    in->traversalMemoryContext = so->traversalCxt;
    in->traversalValue = item->traversalValue;
    in->level = item->level;
    in->returnData = so->want_itup;
    in->allTheSame = innerTuple->allTheSame;
    in->hasPrefix = (innerTuple->prefixSize > 0);
    in->prefixDatum = SGITDATUM(innerTuple, &so->state);
    in->nNodes = innerTuple->nNodes;
    in->nodeLabels = spgExtractNodeLabels(&so->state, innerTuple);
}

Referenced by spgInnerTest().

◆ spgInnerTest()

static void spgInnerTest	(	SpGistScanOpaque	so,
		SpGistSearchItem *	item,
		SpGistInnerTuple	innerTuple,
		bool	isnull
	)

static

Definition at line 662 of file spgscan.c.

{
    MemoryContext oldCxt = MemoryContextSwitchTo(so->tempCxt);
    spgInnerConsistentOut out;
    int         nNodes = innerTuple->nNodes;
    int         i;
 
    memset(&out, 0, sizeof(out));
 
    if (!isnull)
    {
        spgInnerConsistentIn in;
 
        spgInitInnerConsistentIn(&in, so, item, innerTuple);
 
        /* use user-defined inner consistent method */
        FunctionCall2Coll(&so->innerConsistentFn,
                          so->indexCollation,
                          PointerGetDatum(&in),
                          PointerGetDatum(&out));
    }
    else
    {
        /* force all children to be visited */
        out.nNodes = nNodes;
        out.nodeNumbers = palloc_array(int, nNodes);
        for (i = 0; i < nNodes; i++)
            out.nodeNumbers[i] = i;
    }
 
    /* If allTheSame, they should all or none of them match */
    if (innerTuple->allTheSame && out.nNodes != 0 && out.nNodes != nNodes)
        elog(ERROR, "inconsistent inner_consistent results for allTheSame inner tuple");
 
    if (out.nNodes)
    {
        /* collect node pointers */
        SpGistNodeTuple node;
        SpGistNodeTuple *nodes = palloc_array(SpGistNodeTuple, nNodes);
 
        SGITITERATE(innerTuple, i, node)
        {
            nodes[i] = node;
        }
 
        MemoryContextSwitchTo(so->traversalCxt);
 
        for (i = 0; i < out.nNodes; i++)
        {
            int         nodeN = out.nodeNumbers[i];
            SpGistSearchItem *innerItem;
            double     *distances;
 
            Assert(nodeN >= 0 && nodeN < nNodes);
 
            node = nodes[nodeN];
 
            if (!ItemPointerIsValid(&node->t_tid))
                continue;
 
            /*
             * Use infinity distances if innerConsistentFn() failed to return
             * them or if is a NULL item (their distances are really unused).
             */
            distances = out.distances ? out.distances[i] : so->infDistances;
 
            innerItem = spgMakeInnerItem(so, item, node, &out, i, isnull,
                                         distances);
 
            spgAddSearchItemToQueue(so, innerItem);
        }
    }
 
    MemoryContextSwitchTo(oldCxt);
}

References SpGistInnerTupleData::allTheSame, Assert(), spgInnerConsistentOut::distances, elog, ERROR, FunctionCall2Coll(), i, SpGistScanOpaqueData::indexCollation, SpGistScanOpaqueData::infDistances, SpGistScanOpaqueData::innerConsistentFn, ItemPointerIsValid(), MemoryContextSwitchTo(), spgInnerConsistentOut::nNodes, SpGistInnerTupleData::nNodes, spgInnerConsistentOut::nodeNumbers, palloc_array, PointerGetDatum(), SGITITERATE, spgAddSearchItemToQueue(), spgInitInnerConsistentIn(), spgMakeInnerItem(), IndexTupleData::t_tid, SpGistScanOpaqueData::tempCxt, and SpGistScanOpaqueData::traversalCxt.

Referenced by spgWalk().

◆ spgLeafTest()

static bool spgLeafTest	(	SpGistScanOpaque	so,
		SpGistSearchItem *	item,
		SpGistLeafTuple	leafTuple,
		bool	isnull,
		bool *	reportedSome,
		storeRes_func	storeRes
	)

static

Definition at line 511 of file spgscan.c.

{
    Datum       leafValue;
    double     *distances;
    bool        result;
    bool        recheck;
    bool        recheckDistances;
 
    if (isnull)
    {
        /* Should not have arrived on a nulls page unless nulls are wanted */
        Assert(so->searchNulls);
        leafValue = (Datum) 0;
        distances = NULL;
        recheck = false;
        recheckDistances = false;
        result = true;
    }
    else
    {
        spgLeafConsistentIn in;
        spgLeafConsistentOut out;
 
        /* use temp context for calling leaf_consistent */
        MemoryContext oldCxt = MemoryContextSwitchTo(so->tempCxt);
 
        in.scankeys = so->keyData;
        in.nkeys = so->numberOfKeys;
        in.orderbys = so->orderByData;
        in.norderbys = so->numberOfNonNullOrderBys;
        Assert(!item->isLeaf);  /* else reconstructedValue would be wrong type */
        in.reconstructedValue = item->value;
        in.traversalValue = item->traversalValue;
        in.level = item->level;
        in.returnData = so->want_itup;
        in.leafDatum = SGLTDATUM(leafTuple, &so->state);
 
        out.leafValue = (Datum) 0;
        out.recheck = false;
        out.distances = NULL;
        out.recheckDistances = false;
 
        result = DatumGetBool(FunctionCall2Coll(&so->leafConsistentFn,
                                                so->indexCollation,
                                                PointerGetDatum(&in),
                                                PointerGetDatum(&out)));
        recheck = out.recheck;
        recheckDistances = out.recheckDistances;
        leafValue = out.leafValue;
        distances = out.distances;
 
        MemoryContextSwitchTo(oldCxt);
    }
 
    if (result)
    {
        /* item passes the scankeys */
        if (so->numberOfNonNullOrderBys > 0)
        {
            /* the scan is ordered -> add the item to the queue */
            MemoryContext oldCxt = MemoryContextSwitchTo(so->traversalCxt);
            SpGistSearchItem *heapItem = spgNewHeapItem(so, item->level,
                                                        leafTuple,
                                                        leafValue,
                                                        recheck,
                                                        recheckDistances,
                                                        isnull,
                                                        distances);
 
            spgAddSearchItemToQueue(so, heapItem);
 
            MemoryContextSwitchTo(oldCxt);
        }
        else
        {
            /* non-ordered scan, so report the item right away */
            Assert(!recheckDistances);
            storeRes(so, &leafTuple->heapPtr, leafValue, isnull,
                     leafTuple, recheck, false, NULL);
            *reportedSome = true;
        }
    }
 
    return result;
}

Referenced by spgTestLeafTuple().

◆ spgMakeInnerItem()

static SpGistSearchItem * spgMakeInnerItem	(	SpGistScanOpaque	so,
		SpGistSearchItem *	parentItem,
		SpGistNodeTuple	tuple,
		spgInnerConsistentOut *	out,
		int	i,
		bool	isnull,
		double *	distances
	)

static

Definition at line 624 of file spgscan.c.

{
    SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
 
    item->heapPtr = tuple->t_tid;
    item->level = out->levelAdds ? parentItem->level + out->levelAdds[i]
        : parentItem->level;
 
    /* Must copy value out of temp context */
    /* (recall that reconstructed values are of type leafType) */
    item->value = out->reconstructedValues
        ? datumCopy(out->reconstructedValues[i],
                    so->state.attLeafType.attbyval,
                    so->state.attLeafType.attlen)
        : (Datum) 0;
 
    item->leafTuple = NULL;
 
    /*
     * Elements of out.traversalValues should be allocated in
     * in.traversalMemoryContext, which is actually a long lived context of
     * index scan.
     */
    item->traversalValue =
        out->traversalValues ? out->traversalValues[i] : NULL;
 
    item->isLeaf = false;
    item->recheck = false;
    item->recheckDistances = false;
 
    return item;
}

References SpGistTypeDesc::attbyval, SpGistState::attLeafType, SpGistTypeDesc::attlen, datumCopy(), SpGistSearchItem::heapPtr, i, SpGistSearchItem::isLeaf, SpGistSearchItem::leafTuple, SpGistSearchItem::level, spgInnerConsistentOut::levelAdds, SpGistSearchItem::recheck, SpGistSearchItem::recheckDistances, spgInnerConsistentOut::reconstructedValues, spgAllocSearchItem(), SpGistScanOpaqueData::state, IndexTupleData::t_tid, SpGistSearchItem::traversalValue, spgInnerConsistentOut::traversalValues, and SpGistSearchItem::value.

Referenced by spgInnerTest().

◆ spgNewHeapItem()

static SpGistSearchItem * spgNewHeapItem	(	SpGistScanOpaque	so,
		int	level,
		SpGistLeafTuple	leafTuple,
		Datum	leafValue,
		bool	recheck,
		bool	recheckDistances,
		bool	isnull,
		double *	distances
	)

static

Definition at line 458 of file spgscan.c.

{
    SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
 
    item->level = level;
    item->heapPtr = leafTuple->heapPtr;
 
    /*
     * If we need the reconstructed value, copy it to queue cxt out of tmp
     * cxt.  Caution: the leaf_consistent method may not have supplied a value
     * if we didn't ask it to, and mildly-broken methods might supply one of
     * the wrong type.  The correct leafValue type is attType not leafType.
     */
    if (so->want_itup)
    {
        item->value = isnull ? (Datum) 0 :
            datumCopy(leafValue, so->state.attType.attbyval,
                      so->state.attType.attlen);
 
        /*
         * If we're going to need to reconstruct INCLUDE attributes, store the
         * whole leaf tuple so we can get the INCLUDE attributes out of it.
         */
        if (so->state.leafTupDesc->natts > 1)
        {
            item->leafTuple = palloc(leafTuple->size);
            memcpy(item->leafTuple, leafTuple, leafTuple->size);
        }
        else
            item->leafTuple = NULL;
    }
    else
    {
        item->value = (Datum) 0;
        item->leafTuple = NULL;
    }
    item->traversalValue = NULL;
    item->isLeaf = true;
    item->recheck = recheck;
    item->recheckDistances = recheckDistances;
 
    return item;
}

References SpGistTypeDesc::attbyval, SpGistTypeDesc::attlen, SpGistState::attType, datumCopy(), SpGistSearchItem::heapPtr, SpGistLeafTupleData::heapPtr, SpGistSearchItem::isLeaf, SpGistState::leafTupDesc, SpGistSearchItem::leafTuple, SpGistSearchItem::level, TupleDescData::natts, palloc(), SpGistSearchItem::recheck, SpGistSearchItem::recheckDistances, SpGistLeafTupleData::size, spgAllocSearchItem(), SpGistScanOpaqueData::state, SpGistSearchItem::traversalValue, SpGistSearchItem::value, and SpGistScanOpaqueData::want_itup.

Referenced by spgLeafTest().

◆ spgPrepareScanKeys()

static void spgPrepareScanKeys ( IndexScanDesc scan )

static

Definition at line 209 of file spgscan.c.

{
    SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
    bool        qual_ok;
    bool        haveIsNull;
    bool        haveNotNull;
    int         nkeys;
    int         i;
 
    so->numberOfOrderBys = scan->numberOfOrderBys;
    so->orderByData = scan->orderByData;
 
    if (so->numberOfOrderBys <= 0)
        so->numberOfNonNullOrderBys = 0;
    else
    {
        int         j = 0;
 
        /*
         * Remove all NULL keys, but remember their offsets in the original
         * array.
         */
        for (i = 0; i < scan->numberOfOrderBys; i++)
        {
            ScanKey     skey = &so->orderByData[i];
 
            if (skey->sk_flags & SK_ISNULL)
                so->nonNullOrderByOffsets[i] = -1;
            else
            {
                if (i != j)
                    so->orderByData[j] = *skey;
 
                so->nonNullOrderByOffsets[i] = j++;
            }
        }
 
        so->numberOfNonNullOrderBys = j;
    }
 
    if (scan->numberOfKeys <= 0)
    {
        /* If no quals, whole-index scan is required */
        so->searchNulls = true;
        so->searchNonNulls = true;
        so->numberOfKeys = 0;
        return;
    }
 
    /* Examine the given quals */
    qual_ok = true;
    haveIsNull = haveNotNull = false;
    nkeys = 0;
    for (i = 0; i < scan->numberOfKeys; i++)
    {
        ScanKey     skey = &scan->keyData[i];
 
        if (skey->sk_flags & SK_SEARCHNULL)
            haveIsNull = true;
        else if (skey->sk_flags & SK_SEARCHNOTNULL)
            haveNotNull = true;
        else if (skey->sk_flags & SK_ISNULL)
        {
            /* ordinary qual with null argument - unsatisfiable */
            qual_ok = false;
            break;
        }
        else
        {
            /* ordinary qual, propagate into so->keyData */
            so->keyData[nkeys++] = *skey;
            /* this effectively creates a not-null requirement */
            haveNotNull = true;
        }
    }
 
    /* IS NULL in combination with something else is unsatisfiable */
    if (haveIsNull && haveNotNull)
        qual_ok = false;
 
    /* Emit results */
    if (qual_ok)
    {
        so->searchNulls = haveIsNull;
        so->searchNonNulls = haveNotNull;
        so->numberOfKeys = nkeys;
    }
    else
    {
        so->searchNulls = false;
        so->searchNonNulls = false;
        so->numberOfKeys = 0;
    }
}

Referenced by spgrescan().

◆ spgrescan()

void spgrescan	(	IndexScanDesc	scan,
		ScanKey	scankey,
		int	nscankeys,
		ScanKey	orderbys,
		int	norderbys
	)

Definition at line 375 of file spgscan.c.

{
    SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
 
    /* copy scankeys into local storage */
    if (scankey && scan->numberOfKeys > 0)
        memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
 
    /* initialize order-by data if needed */
    if (orderbys && scan->numberOfOrderBys > 0)
    {
        int         i;
 
        memcpy(scan->orderByData, orderbys, scan->numberOfOrderBys * sizeof(ScanKeyData));
 
        for (i = 0; i < scan->numberOfOrderBys; i++)
        {
            ScanKey     skey = &scan->orderByData[i];
 
            /*
             * Look up the datatype returned by the original ordering
             * operator. SP-GiST always uses a float8 for the distance
             * function, but the ordering operator could be anything else.
             *
             * XXX: The distance function is only allowed to be lossy if the
             * ordering operator's result type is float4 or float8.  Otherwise
             * we don't know how to return the distance to the executor.  But
             * we cannot check that here, as we won't know if the distance
             * function is lossy until it returns *recheck = true for the
             * first time.
             */
            so->orderByTypes[i] = get_func_rettype(skey->sk_func.fn_oid);
        }
    }
 
    /* preprocess scankeys, set up the representation in *so */
    spgPrepareScanKeys(scan);
 
    /* set up starting queue entries */
    resetSpGistScanOpaque(so);
 
    /* count an indexscan for stats */
    pgstat_count_index_scan(scan->indexRelation);
    if (scan->instrument)
        scan->instrument->nsearches++;
}

References FmgrInfo::fn_oid, get_func_rettype(), i, if(), IndexScanDescData::indexRelation, IndexScanDescData::instrument, IndexScanDescData::keyData, IndexScanInstrumentation::nsearches, IndexScanDescData::numberOfKeys, IndexScanDescData::numberOfOrderBys, IndexScanDescData::opaque, IndexScanDescData::orderByData, SpGistScanOpaqueData::orderByTypes, pgstat_count_index_scan, resetSpGistScanOpaque(), ScanKeyData::sk_func, and spgPrepareScanKeys().

Referenced by spghandler().

◆ spgTestLeafTuple()

static OffsetNumber spgTestLeafTuple	(	SpGistScanOpaque	so,
		SpGistSearchItem *	item,
		Page	page,
		OffsetNumber	offset,
		bool	isnull,
		bool	isroot,
		bool *	reportedSome,
		storeRes_func	storeRes
	)

static

Definition at line 758 of file spgscan.c.

{
    SpGistLeafTuple leafTuple = (SpGistLeafTuple)
        PageGetItem(page, PageGetItemId(page, offset));
 
    if (leafTuple->tupstate != SPGIST_LIVE)
    {
        if (!isroot)            /* all tuples on root should be live */
        {
            if (leafTuple->tupstate == SPGIST_REDIRECT)
            {
                /* redirection tuple should be first in chain */
                Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
                /* transfer attention to redirect point */
                item->heapPtr = ((SpGistDeadTuple) leafTuple)->pointer;
                Assert(ItemPointerGetBlockNumber(&item->heapPtr) != SPGIST_METAPAGE_BLKNO);
                return SpGistRedirectOffsetNumber;
            }
 
            if (leafTuple->tupstate == SPGIST_DEAD)
            {
                /* dead tuple should be first in chain */
                Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
                /* No live entries on this page */
                Assert(SGLT_GET_NEXTOFFSET(leafTuple) == InvalidOffsetNumber);
                return SpGistBreakOffsetNumber;
            }
        }
 
        /* We should not arrive at a placeholder */
        elog(ERROR, "unexpected SPGiST tuple state: %d", leafTuple->tupstate);
        return SpGistErrorOffsetNumber;
    }
 
    Assert(ItemPointerIsValid(&leafTuple->heapPtr));
 
    spgLeafTest(so, item, leafTuple, isnull, reportedSome, storeRes);
 
    return SGLT_GET_NEXTOFFSET(leafTuple);
}

References Assert(), elog, ERROR, SpGistSearchItem::heapPtr, SpGistLeafTupleData::heapPtr, InvalidOffsetNumber, ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), ItemPointerIsValid(), PageGetItem(), PageGetItemId(), SGLT_GET_NEXTOFFSET, SPGIST_DEAD, SPGIST_LIVE, SPGIST_METAPAGE_BLKNO, SPGIST_REDIRECT, SpGistBreakOffsetNumber, SpGistErrorOffsetNumber, SpGistRedirectOffsetNumber, spgLeafTest(), and SpGistLeafTupleData::tupstate.

Referenced by spgWalk().

◆ spgWalk()

static void spgWalk	(	Relation	index,
		SpGistScanOpaque	so,
		bool	scanWholeIndex,
		storeRes_func	storeRes
	)

static

Definition at line 812 of file spgscan.c.

{
    Buffer      buffer = InvalidBuffer;
    bool        reportedSome = false;
 
    while (scanWholeIndex || !reportedSome)
    {
        SpGistSearchItem *item = spgGetNextQueueItem(so);
 
        if (item == NULL)
            break;              /* No more items in queue -> done */
 
redirect:
        /* Check for interrupts, just in case of infinite loop */
        CHECK_FOR_INTERRUPTS();
 
        if (item->isLeaf)
        {
            /* We store heap items in the queue only in case of ordered search */
            Assert(so->numberOfNonNullOrderBys > 0);
            storeRes(so, &item->heapPtr, item->value, item->isNull,
                     item->leafTuple, item->recheck,
                     item->recheckDistances, item->distances);
            reportedSome = true;
        }
        else
        {
            BlockNumber blkno = ItemPointerGetBlockNumber(&item->heapPtr);
            OffsetNumber offset = ItemPointerGetOffsetNumber(&item->heapPtr);
            Page        page;
            bool        isnull;
 
            if (buffer == InvalidBuffer)
            {
                buffer = ReadBuffer(index, blkno);
                LockBuffer(buffer, BUFFER_LOCK_SHARE);
            }
            else if (blkno != BufferGetBlockNumber(buffer))
            {
                UnlockReleaseBuffer(buffer);
                buffer = ReadBuffer(index, blkno);
                LockBuffer(buffer, BUFFER_LOCK_SHARE);
            }
 
            /* else new pointer points to the same page, no work needed */
 
            page = BufferGetPage(buffer);
 
            isnull = SpGistPageStoresNulls(page) ? true : false;
 
            if (SpGistPageIsLeaf(page))
            {
                /* Page is a leaf - that is, all its tuples are heap items */
                OffsetNumber max = PageGetMaxOffsetNumber(page);
 
                if (SpGistBlockIsRoot(blkno))
                {
                    /* When root is a leaf, examine all its tuples */
                    for (offset = FirstOffsetNumber; offset <= max; offset++)
                        (void) spgTestLeafTuple(so, item, page, offset,
                                                isnull, true,
                                                &reportedSome, storeRes);
                }
                else
                {
                    /* Normal case: just examine the chain we arrived at */
                    while (offset != InvalidOffsetNumber)
                    {
                        Assert(offset >= FirstOffsetNumber && offset <= max);
                        offset = spgTestLeafTuple(so, item, page, offset,
                                                  isnull, false,
                                                  &reportedSome, storeRes);
                        if (offset == SpGistRedirectOffsetNumber)
                            goto redirect;
                    }
                }
            }
            else                /* page is inner */
            {
                SpGistInnerTuple innerTuple = (SpGistInnerTuple)
                    PageGetItem(page, PageGetItemId(page, offset));
 
                if (innerTuple->tupstate != SPGIST_LIVE)
                {
                    if (innerTuple->tupstate == SPGIST_REDIRECT)
                    {
                        /* transfer attention to redirect point */
                        item->heapPtr = ((SpGistDeadTuple) innerTuple)->pointer;
                        Assert(ItemPointerGetBlockNumber(&item->heapPtr) !=
                               SPGIST_METAPAGE_BLKNO);
                        goto redirect;
                    }
                    elog(ERROR, "unexpected SPGiST tuple state: %d",
                         innerTuple->tupstate);
                }
 
                spgInnerTest(so, item, innerTuple, isnull);
            }
        }
 
        /* done with this scan item */
        spgFreeSearchItem(so, item);
        /* clear temp context before proceeding to the next one */
        MemoryContextReset(so->tempCxt);
    }
 
    if (buffer != InvalidBuffer)
        UnlockReleaseBuffer(buffer);
}

References Assert(), BUFFER_LOCK_SHARE, BufferGetBlockNumber(), BufferGetPage(), CHECK_FOR_INTERRUPTS, SpGistSearchItem::distances, elog, ERROR, FirstOffsetNumber, SpGistSearchItem::heapPtr, InvalidBuffer, InvalidOffsetNumber, SpGistSearchItem::isLeaf, SpGistSearchItem::isNull, ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), SpGistSearchItem::leafTuple, LockBuffer(), MemoryContextReset(), SpGistScanOpaqueData::numberOfNonNullOrderBys, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), ReadBuffer(), SpGistSearchItem::recheck, SpGistSearchItem::recheckDistances, spgFreeSearchItem(), spgGetNextQueueItem(), spgInnerTest(), SPGIST_LIVE, SPGIST_METAPAGE_BLKNO, SPGIST_REDIRECT, SpGistBlockIsRoot, SpGistPageIsLeaf, SpGistPageStoresNulls, SpGistRedirectOffsetNumber, spgTestLeafTuple(), SpGistScanOpaqueData::tempCxt, true, SpGistInnerTupleData::tupstate, UnlockReleaseBuffer(), and SpGistSearchItem::value.

Referenced by spggetbitmap(), and spggettuple().

◆ storeBitmap()

static void storeBitmap	(	SpGistScanOpaque	so,
		ItemPointer	heapPtr,
		Datum	leafValue,
		bool	isnull,
		SpGistLeafTuple	leafTuple,
		bool	recheck,
		bool	recheckDistances,
		double *	distances
	)

static

Definition at line 926 of file spgscan.c.

{
    Assert(!recheckDistances && !distances);
    tbm_add_tuples(so->tbm, heapPtr, 1, recheck);
    so->ntids++;
}

References Assert(), SpGistScanOpaqueData::ntids, SpGistScanOpaqueData::tbm, and tbm_add_tuples().

Referenced by spggetbitmap().

◆ storeGettuple()

static void storeGettuple	(	SpGistScanOpaque	so,
		ItemPointer	heapPtr,
		Datum	leafValue,
		bool	isnull,
		SpGistLeafTuple	leafTuple,
		bool	recheck,
		bool	recheckDistances,
		double *	nonNullDistances
	)

static

Definition at line 954 of file spgscan.c.

{
    Assert(so->nPtrs < MaxIndexTuplesPerPage);
    so->heapPtrs[so->nPtrs] = *heapPtr;
    so->recheck[so->nPtrs] = recheck;
    so->recheckDistances[so->nPtrs] = recheckDistances;
 
    if (so->numberOfOrderBys > 0)
    {
        if (isnull || so->numberOfNonNullOrderBys <= 0)
            so->distances[so->nPtrs] = NULL;
        else
        {
            IndexOrderByDistance *distances = palloc_array(IndexOrderByDistance,
                                                           so->numberOfOrderBys);
            int         i;
 
            for (i = 0; i < so->numberOfOrderBys; i++)
            {
                int         offset = so->nonNullOrderByOffsets[i];
 
                if (offset >= 0)
                {
                    /* Copy non-NULL distance value */
                    distances[i].value = nonNullDistances[offset];
                    distances[i].isnull = false;
                }
                else
                {
                    /* Set distance's NULL flag. */
                    distances[i].value = 0.0;
                    distances[i].isnull = true;
                }
            }
 
            so->distances[so->nPtrs] = distances;
        }
    }
 
    if (so->want_itup)
    {
        /*
         * Reconstruct index data.  We have to copy the datum out of the temp
         * context anyway, so we may as well create the tuple here.
         */
        Datum       leafDatums[INDEX_MAX_KEYS];
        bool        leafIsnulls[INDEX_MAX_KEYS];
 
        /* We only need to deform the old tuple if it has INCLUDE attributes */
        if (so->state.leafTupDesc->natts > 1)
            spgDeformLeafTuple(leafTuple, so->state.leafTupDesc,
                               leafDatums, leafIsnulls, isnull);
 
        leafDatums[spgKeyColumn] = leafValue;
        leafIsnulls[spgKeyColumn] = isnull;
 
        so->reconTups[so->nPtrs] = heap_form_tuple(so->reconTupDesc,
                                                   leafDatums,
                                                   leafIsnulls);
    }
    so->nPtrs++;
}

Referenced by spggettuple().

Typedefs

Enumerations

Functions

Typedef Documentation

◆ storeRes_func

Enumeration Type Documentation

◆ SpGistSpecialOffsetNumbers

Function Documentation

◆ pairingheap_SpGistSearchItem_cmp()

◆ resetSpGistScanOpaque()

◆ spgAddSearchItemToQueue()

◆ spgAddStartItem()

◆ spgAllocSearchItem()

◆ spgbeginscan()

◆ spgcanreturn()

◆ spgendscan()

◆ spgFreeSearchItem()

◆ spggetbitmap()

◆ spgGetNextQueueItem()

◆ spggettuple()

◆ spgInitInnerConsistentIn()

◆ spgInnerTest()

◆ spgLeafTest()

◆ spgMakeInnerItem()

◆ spgNewHeapItem()

◆ spgPrepareScanKeys()

◆ spgrescan()

◆ spgTestLeafTuple()

◆ spgWalk()

◆ storeBitmap()

◆ storeGettuple()