#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, 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, ItemPointer heapPtr, 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, bool recheck, bool recheckDistances, double *distances)

int64	spggetbitmap (IndexScanDesc scan, TIDBitmap *tbm)

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

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, 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 672 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 39 of file spgscan.c.

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

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->numberOfOrderBys; 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 145 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 100 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 122 of file spgscan.c.

References FirstOffsetNumber, SpGistSearchItem::heapPtr, SpGistSearchItem::isLeaf, ItemPointerSet, 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->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 106 of file spgscan.c.

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

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

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

◆ spgbeginscan()

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

Definition at line 267 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 indexTupDesc and xs_hitupdesc in case it's an index-only scan */
     so->indexTupDesc = scan->xs_hitupdesc = RelationGetDescr(rel);
 
     /* 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);
 
         /* 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 968 of file spgscan.c.

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

Referenced by spghandler().

 {
     SpGistCache *cache;
 
     /* 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 381 of file spgscan.c.

References SpGistState::deadTupleStorage, SpGistScanOpaqueData::infDistances, SpGistScanOpaqueData::keyData, MemoryContextDelete(), IndexScanDescData::numberOfOrderBys, IndexScanDescData::opaque, SpGistScanOpaqueData::orderByTypes, pfree(), 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.deadTupleStorage)
         pfree(so->state.deadTupleStorage);
 
     if (scan->numberOfOrderBys > 0)
     {
         pfree(so->orderByTypes);
         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 82 of file spgscan.c.

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

Referenced by spgWalk().

 {
     if (!so->state.attLeafType.attbyval &&
         DatumGetPointer(item->value) != NULL)
         pfree(DatumGetPointer(item->value));
 
     if (item->traversalValue)
         pfree(item->traversalValue);
 
     pfree(item);
 }

◆ spggetbitmap()

int64 spggetbitmap	(	IndexScanDesc	scan,
		TIDBitmap *	tbm
	)

Definition at line 858 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 663 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 910 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 526 of file spgscan.c.

Referenced by spgInnerTest().

 {
     in->scankeys = so->keyData;
     in->orderbys = so->orderByData;
     in->nkeys = so->numberOfKeys;
     in->norderbys = so->numberOfOrderBys;
     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 583 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 437 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->numberOfOrderBys;
         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->numberOfOrderBys > 0)
         {
             /* the scan is ordered -> add the item to the queue */
             MemoryContext oldCxt = MemoryContextSwitchTo(so->traversalCxt);
             SpGistSearchItem *heapItem = spgNewHeapItem(so, item->level,
                                                         &leafTuple->heapPtr,
                                                         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,
                      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 548 of file spgscan.c.

References SpGistTypeDesc::attbyval, SpGistState::attLeafType, SpGistTypeDesc::attlen, datumCopy(), SpGistSearchItem::heapPtr, i, SpGistSearchItem::isLeaf, 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 */
     item->value = out->reconstructedValues
         ? datumCopy(out->reconstructedValues[i],
                     so->state.attLeafType.attbyval,
                     so->state.attLeafType.attlen)
         : (Datum) 0;
 
     /*
      * 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,
		ItemPointer	heapPtr,
		Datum	leafValue,
		bool	recheck,
		bool	recheckDistances,
		bool	isnull,
		double *	distances
	)

static

Definition at line 410 of file spgscan.c.

References SpGistTypeDesc::attbyval, SpGistState::attLeafType, SpGistTypeDesc::attlen, datumCopy(), SpGistSearchItem::heapPtr, SpGistSearchItem::isLeaf, SpGistSearchItem::level, SpGistSearchItem::recheck, SpGistSearchItem::recheckDistances, spgAllocSearchItem(), SpGistScanOpaqueData::state, SpGistSearchItem::traversalValue, and SpGistSearchItem::value.

Referenced by spgLeafTest().

 {
     SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
 
     item->level = level;
     item->heapPtr = *heapPtr;
     /* copy value to queue cxt out of tmp cxt */
     item->value = isnull ? (Datum) 0 :
         datumCopy(leafValue, so->state.attLeafType.attbyval,
                   so->state.attLeafType.attlen);
     item->traversalValue = NULL;
     item->isLeaf = true;
     item->recheck = recheck;
     item->recheckDistances = recheckDistances;
 
     return item;
 }

◆ spgPrepareScanKeys()

static void spgPrepareScanKeys ( IndexScanDesc scan )

static

Definition at line 199 of file spgscan.c.

References i, IndexScanDescData::keyData, SpGistScanOpaqueData::keyData, IndexScanDescData::numberOfKeys, SpGistScanOpaqueData::numberOfKeys, IndexScanDescData::numberOfOrderBys, SpGistScanOpaqueData::numberOfOrderBys, IndexScanDescData::opaque, IndexScanDescData::orderByData, SpGistScanOpaqueData::orderByData, SpGistScanOpaqueData::searchNonNulls, SpGistScanOpaqueData::searchNulls, ScanKeyData::sk_flags, SK_ISNULL, SK_SEARCHNOTNULL, and SK_SEARCHNULL.

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

References FmgrInfo::fn_oid, get_func_rettype(), i, IndexScanDescData::keyData, memmove, 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 680 of file spgscan.c.

References Assert, elog, ERROR, SpGistSearchItem::heapPtr, SpGistLeafTupleData::heapPtr, InvalidOffsetNumber, ItemPointerGetBlockNumber, ItemPointerGetOffsetNumber, ItemPointerIsValid, SpGistLeafTupleData::nextOffset, PageGetItem, PageGetItemId, 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(leafTuple->nextOffset == 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 leafTuple->nextOffset;
 }

◆ spgWalk()

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

static

Definition at line 734 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, LockBuffer(), MemoryContextReset(), SpGistScanOpaqueData::numberOfOrderBys, 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->numberOfOrderBys > 0);
             storeRes(so, &item->heapPtr, item->value, item->isNull,
                      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,
		bool	recheck,
		bool	recheckDistances,
		double *	distances
	)

static

Definition at line 848 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,
		bool	recheck,
		bool	recheckDistances,
		double *	distances
	)

static

Definition at line 875 of file spgscan.c.

References Assert, SpGistScanOpaqueData::distances, heap_form_tuple(), SpGistScanOpaqueData::heapPtrs, SpGistScanOpaqueData::indexTupDesc, MaxIndexTuplesPerPage, SpGistScanOpaqueData::nPtrs, SpGistScanOpaqueData::numberOfOrderBys, palloc(), SpGistScanOpaqueData::recheck, SpGistScanOpaqueData::recheckDistances, SpGistScanOpaqueData::reconTups, and SpGistScanOpaqueData::want_itup.

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->distances[so->nPtrs] = NULL;
         else
         {
             Size        size = sizeof(double) * so->numberOfOrderBys;
 
             so->distances[so->nPtrs] = memcpy(palloc(size), distances, size);
         }
     }
 
     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.
          */
         so->reconTups[so->nPtrs] = heap_form_tuple(so->indexTupDesc,
                                                    &leafValue,
                                                    &isnull);
     }
     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()