Fix handling of NULL distances in KNN-GiST

In order to implement NULL LAST semantic GiST previously assumed distance to
the NULL value to be Inf.  However, our distance functions can return Inf and
NaN for non-null values.  In such cases, NULL LAST semantic appears to be
broken.  This commit fixes that by introducing separate array of null flags for
distances.

Backpatch to all supported versions.

Discussion: https://postgr.es/m/CAPpHfdsNvNdA0DBS%2BwMpFrgwT6C3-q50sFVGLSiuWnV3FqOJuQ%40mail.gmail.com
Author: Alexander Korotkov
Backpatch-through: 9.4

1 files changed, 52 insertions, 25 deletions

diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index 1a69d40a715..b2ec971156d 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -38,8 +38,9 @@
  * Similarly, *recheck_distances_p is set to indicate whether the distances
  * need to be rechecked, and it is also ignored for non-leaf entries.
  *
- * If we are doing an ordered scan, so->distances[] is filled with distance
- * data from the distance() functions before returning success.
+ * If we are doing an ordered scan, so->distancesValues[] and
+ * so->distancesNulls[] is filled with distance data from the distance()
+ * functions before returning success.
  *
  * We must decompress the key in the IndexTuple before passing it to the
  * sk_funcs (which actually are the opclass Consistent or Distance methods).
@@ -60,7 +61,8 @@ gistindex_keytest(IndexScanDesc scan,
 	GISTSTATE  *giststate = so->giststate;
 	ScanKey		key = scan->keyData;
 	int			keySize = scan->numberOfKeys;
-	double	   *distance_p;
+	double	   *distance_value_p;
+	bool	   *distance_null_p;
 	Relation	r = scan->indexRelation;
 
 	*recheck_p = false;
@@ -78,7 +80,10 @@ gistindex_keytest(IndexScanDesc scan,
 		if (GistPageIsLeaf(page))		/* shouldn't happen */
 			elog(ERROR, "invalid GiST tuple found on leaf page");
 		for (i = 0; i < scan->numberOfOrderBys; i++)
-			so->distances[i] = -get_float8_infinity();
+		{
+			so->distanceValues[i] = -get_float8_infinity();
+			so->distanceNulls[i] = false;
+		}
 		return true;
 	}
 
@@ -161,7 +166,8 @@ gistindex_keytest(IndexScanDesc scan,
 
 	/* OK, it passes --- now let's compute the distances */
 	key = scan->orderByData;
-	distance_p = so->distances;
+	distance_value_p = so->distanceValues;
+	distance_null_p = so->distanceNulls;
 	keySize = scan->numberOfOrderBys;
 	while (keySize > 0)
 	{
@@ -175,8 +181,9 @@ gistindex_keytest(IndexScanDesc scan,
 
 		if ((key->sk_flags & SK_ISNULL) || isNull)
 		{
-			/* Assume distance computes as null and sorts to the end */
-			*distance_p = get_float8_infinity();
+			/* Assume distance computes as null */
+			*distance_value_p = 0.0;
+			*distance_null_p = true;
 		}
 		else
 		{
@@ -213,11 +220,13 @@ gistindex_keytest(IndexScanDesc scan,
 									 ObjectIdGetDatum(key->sk_subtype),
 									 PointerGetDatum(&recheck));
 			*recheck_distances_p |= recheck;
-			*distance_p = DatumGetFloat8(dist);
+			*distance_value_p = DatumGetFloat8(dist);
+			*distance_null_p = false;
 		}
 
 		key++;
-		distance_p++;
+		distance_value_p++;
+		distance_null_p++;
 		keySize--;
 	}
 
@@ -230,7 +239,8 @@ gistindex_keytest(IndexScanDesc scan,
  *
  * scan: index scan we are executing
  * pageItem: search queue item identifying an index page to scan
- * myDistances: distances array associated with pageItem, or NULL at the root
+ * myDistanceValues: distances array associated with pageItem, or NULL at the root
+ * myDistanceNulls: null flags for myDistanceValues array, or NULL at the root
  * tbm: if not NULL, gistgetbitmap's output bitmap
  * ntids: if not NULL, gistgetbitmap's output tuple counter
  *
@@ -247,7 +257,8 @@ gistindex_keytest(IndexScanDesc scan,
  * sibling will be processed next.
  */
 static void
-gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
+gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem,
+			 double *myDistanceValues, bool *myDistanceNulls,
 			 TIDBitmap *tbm, int64 *ntids)
 {
 	GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
@@ -283,7 +294,7 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
 		GISTSearchItem *item;
 
 		/* This can't happen when starting at the root */
-		Assert(myDistances != NULL);
+		Assert(myDistanceValues != NULL && myDistanceNulls != NULL);
 
 		oldcxt = MemoryContextSwitchTo(so->queueCxt);
 
@@ -293,8 +304,10 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
 		item->data.parentlsn = pageItem->data.parentlsn;
 
 		/* Insert it into the queue using same distances as for this page */
-		memcpy(item->distances, myDistances,
-			   sizeof(double) * scan->numberOfOrderBys);
+		memcpy(GISTSearchItemDistanceValues(item, scan->numberOfOrderBys),
+			   myDistanceValues, sizeof(double) * scan->numberOfOrderBys);
+		memcpy(GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys),
+			   myDistanceNulls, sizeof(bool) * scan->numberOfOrderBys);
 
 		pairingheap_add(so->queue, &item->phNode);
 
@@ -370,6 +383,7 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
 			 * search.
 			 */
 			GISTSearchItem *item;
+			int			nOrderBys = scan->numberOfOrderBys;
 
 			oldcxt = MemoryContextSwitchTo(so->queueCxt);
 
@@ -404,8 +418,10 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
 			}
 
 			/* Insert it into the queue using new distance data */
-			memcpy(item->distances, so->distances,
-				   sizeof(double) * scan->numberOfOrderBys);
+			memcpy(GISTSearchItemDistanceValues(item, nOrderBys),
+				   so->distanceValues, sizeof(double) * nOrderBys);
+			memcpy(GISTSearchItemDistanceNulls(item, nOrderBys),
+				   so->distanceNulls, sizeof(bool) * nOrderBys);
 
 			pairingheap_add(so->queue, &item->phNode);
 
@@ -460,6 +476,8 @@ getNextNearest(IndexScanDesc scan)
 	do
 	{
 		GISTSearchItem *item = getNextGISTSearchItem(so);
+		float8 *distanceValues = GISTSearchItemDistanceValues(item, scan->numberOfOrderBys);
+		bool *distanceNulls = GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys);
 
 		if (!item)
 			break;
@@ -479,8 +497,8 @@ getNextNearest(IndexScanDesc scan)
 					if (!scan->xs_orderbynulls[i])
 						pfree(DatumGetPointer(scan->xs_orderbyvals[i]));
 #endif
-					scan->xs_orderbyvals[i] = Float8GetDatum(item->distances[i]);
-					scan->xs_orderbynulls[i] = false;
+					scan->xs_orderbyvals[i] = Float8GetDatum(distanceValues[i]);
+					scan->xs_orderbynulls[i] = distanceNulls[i];
 				}
 				else if (so->orderByTypes[i] == FLOAT4OID)
 				{
@@ -490,8 +508,8 @@ getNextNearest(IndexScanDesc scan)
 					if (!scan->xs_orderbynulls[i])
 						pfree(DatumGetPointer(scan->xs_orderbyvals[i]));
 #endif
-					scan->xs_orderbyvals[i] = Float4GetDatum((float4) item->distances[i]);
-					scan->xs_orderbynulls[i] = false;
+					scan->xs_orderbyvals[i] = Float4GetDatum(distanceValues[i]);
+					scan->xs_orderbynulls[i] = distanceNulls[i];
 				}
 				else
 				{
@@ -519,7 +537,10 @@ getNextNearest(IndexScanDesc scan)
 			/* visit an index page, extract its items into queue */
 			CHECK_FOR_INTERRUPTS();
 
-			gistScanPage(scan, item, item->distances, NULL, NULL);
+			gistScanPage(scan, item,
+						 GISTSearchItemDistanceValues(item, scan->numberOfOrderBys),
+						 GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys),
+						 NULL, NULL);
 		}
 
 		pfree(item);
@@ -559,7 +580,7 @@ gistgettuple(PG_FUNCTION_ARGS)
 
 		fakeItem.blkno = GIST_ROOT_BLKNO;
 		memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
-		gistScanPage(scan, &fakeItem, NULL, NULL, NULL);
+		gistScanPage(scan, &fakeItem, NULL, NULL, NULL, NULL);
 	}
 
 	if (scan->numberOfOrderBys > 0)
@@ -604,7 +625,10 @@ gistgettuple(PG_FUNCTION_ARGS)
 				 * this page, we fall out of the inner "do" and loop around to
 				 * return them.
 				 */
-				gistScanPage(scan, item, item->distances, NULL, NULL);
+				gistScanPage(scan, item,
+							 GISTSearchItemDistanceValues(item, scan->numberOfOrderBys),
+							 GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys),
+							 NULL, NULL);
 
 				pfree(item);
 			} while (so->nPageData == 0);
@@ -637,7 +661,7 @@ gistgetbitmap(PG_FUNCTION_ARGS)
 
 	fakeItem.blkno = GIST_ROOT_BLKNO;
 	memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
-	gistScanPage(scan, &fakeItem, NULL, tbm, &ntids);
+	gistScanPage(scan, &fakeItem, NULL, NULL, tbm, &ntids);
 
 	/*
 	 * While scanning a leaf page, ItemPointers of matching heap tuples will
@@ -652,7 +676,10 @@ gistgetbitmap(PG_FUNCTION_ARGS)
 
 		CHECK_FOR_INTERRUPTS();
 
-		gistScanPage(scan, item, item->distances, tbm, &ntids);
+		gistScanPage(scan, item,
+					 GISTSearchItemDistanceValues(item, scan->numberOfOrderBys),
+					 GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys),
+					 tbm, &ntids);
 
 		pfree(item);
 	}