#include "postgres.h"
#include "access/genam.h"
#include "access/relscan.h"
#include "access/spgist_private.h"
#include "miscadmin.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, Snapshot snapshot)

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 29 of file spgscan.c.

Enumeration Type Documentation

◆ SpGistSpecialOffsetNumbers

enum SpGistSpecialOffsetNumbers

Enumerator
SpGistBreakOffsetNumber
SpGistRedirectOffsetNumber
SpGistErrorOffsetNumber

Definition at line 751 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 40 of file spgscan.c.

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

Referenced by resetSpGistScanOpaque().

 {
     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;
 }

◆ resetSpGistScanOpaque()

static void resetSpGistScanOpaque ( SpGistScanOpaque so )

static

Definition at line 153 of file spgscan.c.

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().

 {
     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;
 }

◆ spgAddSearchItemToQueue()

static void spgAddSearchItemToQueue	(	SpGistScanOpaque	so,
		SpGistSearchItem *	item
	)

static

Definition at line 107 of file spgscan.c.

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

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

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

◆ spgAddStartItem()

static void spgAddStartItem	(	SpGistScanOpaque	so,
		bool	isnull
	)

static

Definition at line 129 of file spgscan.c.

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().

 {
     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);
 }

◆ spgAllocSearchItem()

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

static

Definition at line 113 of file spgscan.c.

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

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

 {
     /* 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;
 }

◆ spgbeginscan()

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

Definition at line 303 of file spgscan.c.

Referenced by spghandler().

 {
     IndexScanDesc scan;
     SpGistScanOpaque so;
     int         i;
 
     scan = RelationGetIndexScan(rel, keysz, orderbysz);
 
     so = (SpGistScanOpaque) palloc0(sizeof(SpGistScanOpaqueData));
     if (keysz > 0)
         so->keyData = (ScanKey) palloc(sizeof(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 = (Oid *)
             palloc(sizeof(Oid) * scan->numberOfOrderBys);
         so->nonNullOrderByOffsets = (int *)
             palloc(sizeof(int) * scan->numberOfOrderBys);
 
         /* These arrays have constant contents, so we can fill them now */
         so->zeroDistances = (double *)
             palloc(sizeof(double) * scan->numberOfOrderBys);
         so->infDistances = (double *)
             palloc(sizeof(double) * scan->numberOfOrderBys);
 
         for (i = 0; i < scan->numberOfOrderBys; i++)
         {
             so->zeroDistances[i] = 0.0;
             so->infDistances[i] = get_float8_infinity();
         }
 
         scan->xs_orderbyvals = (Datum *)
             palloc0(sizeof(Datum) * scan->numberOfOrderBys);
         scan->xs_orderbynulls = (bool *)
             palloc(sizeof(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;
 }

◆ spgcanreturn()

bool spgcanreturn	(	Relation	index,
		int	attno
	)

Definition at line 1081 of file spgscan.c.

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

Referenced by spghandler().

 {
     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;
 }

◆ spgendscan()

void spgendscan ( IndexScanDesc scan )

Definition at line 425 of file spgscan.c.

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().

 {
     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);
 }

◆ spgFreeSearchItem()

static void spgFreeSearchItem	(	SpGistScanOpaque	so,
		SpGistSearchItem *	item
	)

static

Definition at line 83 of file spgscan.c.

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

Referenced by spgWalk().

 {
     /* 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);
 }

◆ spggetbitmap()

int64 spggetbitmap	(	IndexScanDesc	scan,
		TIDBitmap *	tbm
	)

Definition at line 939 of file spgscan.c.

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

Referenced by spghandler().

 {
     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, scan->xs_snapshot);
 
     return so->ntids;
 }

◆ spgGetNextQueueItem()

static SpGistSearchItem* spgGetNextQueueItem ( SpGistScanOpaque so )

static

Definition at line 742 of file spgscan.c.

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

Referenced by spgWalk().

 {
     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);
 }

◆ spggettuple()

bool spggettuple	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 1023 of file spgscan.c.

Referenced by spghandler().

 {
     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,
                 scan->xs_snapshot);
 
         if (so->nPtrs == 0)
             break;              /* must have completed scan */
     }
 
     return false;
 }

◆ spgInitInnerConsistentIn()

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

static

Definition at line 602 of file spgscan.c.

Referenced by spgInnerTest().

 {
     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);
 }

◆ spgInnerTest()

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

static

Definition at line 663 of file spgscan.c.

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(), PointerGetDatum, SGITITERATE, spgAddSearchItemToQueue(), spgInitInnerConsistentIn(), spgMakeInnerItem(), IndexTupleData::t_tid, SpGistScanOpaqueData::tempCxt, and SpGistScanOpaqueData::traversalCxt.

Referenced by spgWalk().

 {
     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 = (int *) palloc(sizeof(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 = (SpGistNodeTuple *) palloc(sizeof(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);
 }

◆ spgLeafTest()

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

static

Definition at line 512 of file spgscan.c.

Referenced by spgTestLeafTuple().

 {
     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;
 }

◆ spgMakeInnerItem()

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

static

Definition at line 625 of file spgscan.c.

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().

 {
     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;
 }

◆ spgNewHeapItem()

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

static

Definition at line 459 of file spgscan.c.

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().

 {
     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;
 }

◆ spgPrepareScanKeys()

static void spgPrepareScanKeys ( IndexScanDesc scan )

static

Definition at line 207 of file spgscan.c.

Referenced by spgrescan().

 {
     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;
     }
 }

◆ spgrescan()

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

Definition at line 379 of file spgscan.c.

References FmgrInfo::fn_oid, get_func_rettype(), i, IndexScanDescData::keyData, IndexScanDescData::numberOfKeys, IndexScanDescData::numberOfOrderBys, IndexScanDescData::opaque, IndexScanDescData::orderByData, SpGistScanOpaqueData::orderByTypes, resetSpGistScanOpaque(), ScanKeyData::sk_func, and spgPrepareScanKeys().

Referenced by spghandler().

 {
     SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
 
     /* copy scankeys into local storage */
     if (scankey && scan->numberOfKeys > 0)
         memmove(scan->keyData, scankey,
                 scan->numberOfKeys * sizeof(ScanKeyData));
 
     /* initialize order-by data if needed */
     if (orderbys && scan->numberOfOrderBys > 0)
     {
         int         i;
 
         memmove(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);
 }

◆ 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 759 of file spgscan.c.

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().

 {
     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);
 }

◆ spgWalk()

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

static

Definition at line 813 of file spgscan.c.

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, TestForOldSnapshot(), true, SpGistInnerTupleData::tupstate, UnlockReleaseBuffer(), and SpGistSearchItem::value.

Referenced by spggetbitmap(), and spggettuple().

 {
     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);
             TestForOldSnapshot(snapshot, index, page);
 
             isnull = SpGistPageStoresNulls(page) ? true : false;
 
             if (SpGistPageIsLeaf(page))
             {
                 /* Page is a leaf - that is, all it's 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);
 }

◆ storeBitmap()

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

static

Definition at line 928 of file spgscan.c.

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

Referenced by spggetbitmap().

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

◆ storeGettuple()

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

static

Definition at line 956 of file spgscan.c.

Referenced by spggettuple().

 {
     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(sizeof(distances[0]) * 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++;
 }

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()