1 files changed, 358 insertions, 0 deletions

diff --git a/src/backend/access/gist/gistscan.c b/src/backend/access/gist/gistscan.c
new file mode 100644
index 0000000..61e92cf
--- /dev/null
+++ b/src/backend/access/gist/gistscan.c
@@ -0,0 +1,358 @@
+/*-------------------------------------------------------------------------
+ *
+ * gistscan.c
+ *	  routines to manage scans on GiST index relations
+ *
+ *
+ * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ *	  src/backend/access/gist/gistscan.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "access/gist_private.h"
+#include "access/gistscan.h"
+#include "access/relscan.h"
+#include "utils/float.h"
+#include "utils/lsyscache.h"
+#include "utils/memutils.h"
+#include "utils/rel.h"
+
+
+/*
+ * Pairing heap comparison function for the GISTSearchItem queue
+ */
+static int
+pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
+{
+	const GISTSearchItem *sa = (const GISTSearchItem *) a;
+	const GISTSearchItem *sb = (const GISTSearchItem *) b;
+	IndexScanDesc scan = (IndexScanDesc) arg;
+	int			i;
+
+	/* Order according to distance comparison */
+	for (i = 0; i < scan->numberOfOrderBys; i++)
+	{
+		if (sa->distances[i].isnull)
+		{
+			if (!sb->distances[i].isnull)
+				return -1;
+		}
+		else if (sb->distances[i].isnull)
+		{
+			return 1;
+		}
+		else
+		{
+			int			cmp = -float8_cmp_internal(sa->distances[i].value,
+												   sb->distances[i].value);
+
+			if (cmp != 0)
+				return cmp;
+		}
+	}
+
+	/* Heap items go before inner pages, to ensure a depth-first search */
+	if (GISTSearchItemIsHeap(*sa) && !GISTSearchItemIsHeap(*sb))
+		return 1;
+	if (!GISTSearchItemIsHeap(*sa) && GISTSearchItemIsHeap(*sb))
+		return -1;
+
+	return 0;
+}
+
+
+/*
+ * Index AM API functions for scanning GiST indexes
+ */
+
+IndexScanDesc
+gistbeginscan(Relation r, int nkeys, int norderbys)
+{
+	IndexScanDesc scan;
+	GISTSTATE  *giststate;
+	GISTScanOpaque so;
+	MemoryContext oldCxt;
+
+	scan = RelationGetIndexScan(r, nkeys, norderbys);
+
+	/* First, set up a GISTSTATE with a scan-lifespan memory context */
+	giststate = initGISTstate(scan->indexRelation);
+
+	/*
+	 * Everything made below is in the scanCxt, or is a child of the scanCxt,
+	 * so it'll all go away automatically in gistendscan.
+	 */
+	oldCxt = MemoryContextSwitchTo(giststate->scanCxt);
+
+	/* initialize opaque data */
+	so = (GISTScanOpaque) palloc0(sizeof(GISTScanOpaqueData));
+	so->giststate = giststate;
+	giststate->tempCxt = createTempGistContext();
+	so->queue = NULL;
+	so->queueCxt = giststate->scanCxt;	/* see gistrescan */
+
+	/* workspaces with size dependent on numberOfOrderBys: */
+	so->distances = palloc(sizeof(so->distances[0]) * scan->numberOfOrderBys);
+	so->qual_ok = true;			/* in case there are zero keys */
+	if (scan->numberOfOrderBys > 0)
+	{
+		scan->xs_orderbyvals = palloc0(sizeof(Datum) * scan->numberOfOrderBys);
+		scan->xs_orderbynulls = palloc(sizeof(bool) * scan->numberOfOrderBys);
+		memset(scan->xs_orderbynulls, true, sizeof(bool) * scan->numberOfOrderBys);
+	}
+
+	so->killedItems = NULL;		/* until needed */
+	so->numKilled = 0;
+	so->curBlkno = InvalidBlockNumber;
+	so->curPageLSN = InvalidXLogRecPtr;
+
+	scan->opaque = so;
+
+	/*
+	 * All fields required for index-only scans are initialized in gistrescan,
+	 * as we don't know yet if we're doing an index-only scan or not.
+	 */
+
+	MemoryContextSwitchTo(oldCxt);
+
+	return scan;
+}
+
+void
+gistrescan(IndexScanDesc scan, ScanKey key, int nkeys,
+		   ScanKey orderbys, int norderbys)
+{
+	/* nkeys and norderbys arguments are ignored */
+	GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
+	bool		first_time;
+	int			i;
+	MemoryContext oldCxt;
+
+	/* rescan an existing indexscan --- reset state */
+
+	/*
+	 * The first time through, we create the search queue in the scanCxt.
+	 * Subsequent times through, we create the queue in a separate queueCxt,
+	 * which is created on the second call and reset on later calls.  Thus, in
+	 * the common case where a scan is only rescan'd once, we just put the
+	 * queue in scanCxt and don't pay the overhead of making a second memory
+	 * context.  If we do rescan more than once, the first queue is just left
+	 * for dead until end of scan; this small wastage seems worth the savings
+	 * in the common case.
+	 */
+	if (so->queue == NULL)
+	{
+		/* first time through */
+		Assert(so->queueCxt == so->giststate->scanCxt);
+		first_time = true;
+	}
+	else if (so->queueCxt == so->giststate->scanCxt)
+	{
+		/* second time through */
+		so->queueCxt = AllocSetContextCreate(so->giststate->scanCxt,
+											 "GiST queue context",
+											 ALLOCSET_DEFAULT_SIZES);
+		first_time = false;
+	}
+	else
+	{
+		/* third or later time through */
+		MemoryContextReset(so->queueCxt);
+		first_time = false;
+	}
+
+	/*
+	 * If we're doing an index-only scan, on the first call, also initialize a
+	 * tuple descriptor to represent the returned index tuples and create a
+	 * memory context to hold them during the scan.
+	 */
+	if (scan->xs_want_itup && !scan->xs_hitupdesc)
+	{
+		int			natts;
+		int			nkeyatts;
+		int			attno;
+
+		/*
+		 * The storage type of the index can be different from the original
+		 * datatype being indexed, so we cannot just grab the index's tuple
+		 * descriptor. Instead, construct a descriptor with the original data
+		 * types.
+		 */
+		natts = RelationGetNumberOfAttributes(scan->indexRelation);
+		nkeyatts = IndexRelationGetNumberOfKeyAttributes(scan->indexRelation);
+		so->giststate->fetchTupdesc = CreateTemplateTupleDesc(natts);
+		for (attno = 1; attno <= nkeyatts; attno++)
+		{
+			TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
+							   scan->indexRelation->rd_opcintype[attno - 1],
+							   -1, 0);
+		}
+
+		for (; attno <= natts; attno++)
+		{
+			/* taking opcintype from giststate->tupdesc */
+			TupleDescInitEntry(so->giststate->fetchTupdesc, attno, NULL,
+							   TupleDescAttr(so->giststate->leafTupdesc,
+											 attno - 1)->atttypid,
+							   -1, 0);
+		}
+		scan->xs_hitupdesc = so->giststate->fetchTupdesc;
+
+		/* Also create a memory context that will hold the returned tuples */
+		so->pageDataCxt = AllocSetContextCreate(so->giststate->scanCxt,
+												"GiST page data context",
+												ALLOCSET_DEFAULT_SIZES);
+	}
+
+	/* create new, empty pairing heap for search queue */
+	oldCxt = MemoryContextSwitchTo(so->queueCxt);
+	so->queue = pairingheap_allocate(pairingheap_GISTSearchItem_cmp, scan);
+	MemoryContextSwitchTo(oldCxt);
+
+	so->firstCall = true;
+
+	/* Update scan key, if a new one is given */
+	if (key && scan->numberOfKeys > 0)
+	{
+		void	  **fn_extras = NULL;
+
+		/*
+		 * If this isn't the first time through, preserve the fn_extra
+		 * pointers, so that if the consistentFns are using them to cache
+		 * data, that data is not leaked across a rescan.
+		 */
+		if (!first_time)
+		{
+			fn_extras = (void **) palloc(scan->numberOfKeys * sizeof(void *));
+			for (i = 0; i < scan->numberOfKeys; i++)
+				fn_extras[i] = scan->keyData[i].sk_func.fn_extra;
+		}
+
+		memmove(scan->keyData, key,
+				scan->numberOfKeys * sizeof(ScanKeyData));
+
+		/*
+		 * Modify the scan key so that the Consistent method is called for all
+		 * comparisons. The original operator is passed to the Consistent
+		 * function in the form of its strategy number, which is available
+		 * from the sk_strategy field, and its subtype from the sk_subtype
+		 * field.
+		 *
+		 * Next, if any of keys is a NULL and that key is not marked with
+		 * SK_SEARCHNULL/SK_SEARCHNOTNULL then nothing can be found (ie, we
+		 * assume all indexable operators are strict).
+		 */
+		so->qual_ok = true;
+
+		for (i = 0; i < scan->numberOfKeys; i++)
+		{
+			ScanKey		skey = scan->keyData + i;
+
+			/*
+			 * Copy consistent support function to ScanKey structure instead
+			 * of function implementing filtering operator.
+			 */
+			fmgr_info_copy(&(skey->sk_func),
+						   &(so->giststate->consistentFn[skey->sk_attno - 1]),
+						   so->giststate->scanCxt);
+
+			/* Restore prior fn_extra pointers, if not first time */
+			if (!first_time)
+				skey->sk_func.fn_extra = fn_extras[i];
+
+			if (skey->sk_flags & SK_ISNULL)
+			{
+				if (!(skey->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL)))
+					so->qual_ok = false;
+			}
+		}
+
+		if (!first_time)
+			pfree(fn_extras);
+	}
+
+	/* Update order-by key, if a new one is given */
+	if (orderbys && scan->numberOfOrderBys > 0)
+	{
+		void	  **fn_extras = NULL;
+
+		/* As above, preserve fn_extra if not first time through */
+		if (!first_time)
+		{
+			fn_extras = (void **) palloc(scan->numberOfOrderBys * sizeof(void *));
+			for (i = 0; i < scan->numberOfOrderBys; i++)
+				fn_extras[i] = scan->orderByData[i].sk_func.fn_extra;
+		}
+
+		memmove(scan->orderByData, orderbys,
+				scan->numberOfOrderBys * sizeof(ScanKeyData));
+
+		so->orderByTypes = (Oid *) palloc(scan->numberOfOrderBys * sizeof(Oid));
+
+		/*
+		 * Modify the order-by key so that the Distance method is called for
+		 * all comparisons. The original operator is passed to the Distance
+		 * function in the form of its strategy number, which is available
+		 * from the sk_strategy field, and its subtype from the sk_subtype
+		 * field.
+		 */
+		for (i = 0; i < scan->numberOfOrderBys; i++)
+		{
+			ScanKey		skey = scan->orderByData + i;
+			FmgrInfo   *finfo = &(so->giststate->distanceFn[skey->sk_attno - 1]);
+
+			/* Check we actually have a distance function ... */
+			if (!OidIsValid(finfo->fn_oid))
+				elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
+					 GIST_DISTANCE_PROC, skey->sk_attno,
+					 RelationGetRelationName(scan->indexRelation));
+
+			/*
+			 * Look up the datatype returned by the original ordering
+			 * operator. 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);
+
+			/*
+			 * Copy distance support function to ScanKey structure instead of
+			 * function implementing ordering operator.
+			 */
+			fmgr_info_copy(&(skey->sk_func), finfo, so->giststate->scanCxt);
+
+			/* Restore prior fn_extra pointers, if not first time */
+			if (!first_time)
+				skey->sk_func.fn_extra = fn_extras[i];
+		}
+
+		if (!first_time)
+			pfree(fn_extras);
+	}
+
+	/* any previous xs_hitup will have been pfree'd in context resets above */
+	scan->xs_hitup = NULL;
+}
+
+void
+gistendscan(IndexScanDesc scan)
+{
+	GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
+
+	/*
+	 * freeGISTstate is enough to clean up everything made by gistbeginscan,
+	 * as well as the queueCxt if there is a separate context for it.
+	 */
+	freeGISTstate(so->giststate);
+}