v6-0005-Use-hashing-to-avoid-O-N-2-matching-work-in-eqjoi.patch

From 28a9e2dd123aee5e3c1217fb90bf5b51fdb5d427 Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Mon, 17 Nov 2025 13:12:18 -0500
Subject: [PATCH v6 5/5] Use hashing to avoid O(N^2) matching work in
 eqjoinsel.

Use a simplehash hash table if there are enough MCVs and the
join operator has associated hash functions.  The threshold
for switching to hash mode perhaps could use more research.
---
 src/backend/utils/adt/selfuncs.c | 253 ++++++++++++++++++++++++++++++-
 src/tools/pgindent/typedefs.list |   3 +
 2 files changed, 251 insertions(+), 5 deletions(-)

diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 4335daf9a80..3354fea6a76 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -143,12 +143,47 @@
 
 #define DEFAULT_PAGE_CPU_MULTIPLIER 50.0
 
+/*
+ * In production builds, switch to hash-based MCV matching when lists are
+ * large enough to amortize hash setup cost.  In debug builds, we use a
+ * smaller threshold so that the regression tests cover both paths well.
+ */
+#ifndef USE_ASSERT_CHECKING
+#define EQJOINSEL_MCV_HASH_THRESHOLD 100
+#else
+#define EQJOINSEL_MCV_HASH_THRESHOLD 10
+#endif
+
+/* Entries in the simplehash hash table used by eqjoinsel_find_matches */
+typedef struct MCVHashEntry
+{
+	Datum		value;			/* the value represented by this entry */
+	int			index;			/* its index in the relevant AttStatsSlot */
+	uint32		hash;			/* hash code for the Datum */
+	char		status;			/* status code used by simplehash.h */
+} MCVHashEntry;
+
+/* private_data for the simplehash hash table */
+typedef struct MCVHashContext
+{
+	FunctionCallInfo equal_fcinfo;	/* the equality join operator */
+	FunctionCallInfo hash_fcinfo;	/* the hash function to use */
+	bool		op_is_reversed; /* equality compares hash type to probe type */
+	bool		insert_mode;	/* doing inserts or lookups? */
+	bool		hash_typbyval;	/* typbyval of hashed data type */
+	int16		hash_typlen;	/* typlen of hashed data type */
+} MCVHashContext;
+
+/* forward reference */
+typedef struct MCVHashTable_hash MCVHashTable_hash;
+
 /* Hooks for plugins to get control when we ask for stats */
 get_relation_stats_hook_type get_relation_stats_hook = NULL;
 get_index_stats_hook_type get_index_stats_hook = NULL;
 
 static double eqsel_internal(PG_FUNCTION_ARGS, bool negate);
 static double eqjoinsel_inner(FmgrInfo *eqproc, Oid collation,
+							  Oid hashLeft, Oid hashRight,
 							  VariableStatData *vardata1, VariableStatData *vardata2,
 							  double nd1, double nd2,
 							  bool isdefault1, bool isdefault2,
@@ -158,6 +193,7 @@ static double eqjoinsel_inner(FmgrInfo *eqproc, Oid collation,
 							  bool *hasmatch1, bool *hasmatch2,
 							  int *p_nmatches);
 static double eqjoinsel_semi(FmgrInfo *eqproc, Oid collation,
+							 Oid hashLeft, Oid hashRight,
 							 bool op_is_reversed,
 							 VariableStatData *vardata1, VariableStatData *vardata2,
 							 double nd1, double nd2,
@@ -169,11 +205,14 @@ static double eqjoinsel_semi(FmgrInfo *eqproc, Oid collation,
 							 int *p_nmatches,
 							 RelOptInfo *inner_rel);
 static void eqjoinsel_find_matches(FmgrInfo *eqproc, Oid collation,
+								   Oid hashLeft, Oid hashRight,
 								   bool op_is_reversed,
 								   AttStatsSlot *sslot1, AttStatsSlot *sslot2,
 								   int nvalues1, int nvalues2,
 								   bool *hasmatch1, bool *hasmatch2,
 								   int *p_nmatches, double *p_matchprodfreq);
+static uint32 hash_mcv(MCVHashTable_hash *tab, Datum key);
+static bool mcvs_equal(MCVHashTable_hash *tab, Datum key0, Datum key1);
 static bool estimate_multivariate_ndistinct(PlannerInfo *root,
 											RelOptInfo *rel, List **varinfos, double *ndistinct);
 static bool convert_to_scalar(Datum value, Oid valuetypid, Oid collid,
@@ -229,6 +268,20 @@ static RelOptInfo *find_join_input_rel(PlannerInfo *root, Relids relids);
 static double btcost_correlation(IndexOptInfo *index,
 								 VariableStatData *vardata);
 
+/* Define support routines for MCV hash tables */
+#define SH_PREFIX				MCVHashTable
+#define SH_ELEMENT_TYPE			MCVHashEntry
+#define SH_KEY_TYPE				Datum
+#define SH_KEY					value
+#define SH_HASH_KEY(tab,key)	hash_mcv(tab, key)
+#define SH_EQUAL(tab,key0,key1)	mcvs_equal(tab, key0, key1)
+#define SH_SCOPE				static inline
+#define SH_STORE_HASH
+#define SH_GET_HASH(tab,ent)	(ent)->hash
+#define SH_DEFINE
+#define SH_DECLARE
+#include "lib/simplehash.h"
+
 
 /*
  *		eqsel			- Selectivity of "=" for any data types.
@@ -2316,6 +2369,8 @@ eqjoinsel(PG_FUNCTION_ARGS)
 	bool		isdefault2;
 	Oid			opfuncoid;
 	FmgrInfo	eqproc;
+	Oid			hashLeft = InvalidOid;
+	Oid			hashRight = InvalidOid;
 	AttStatsSlot sslot1;
 	AttStatsSlot sslot2;
 	Form_pg_statistic stats1 = NULL;
@@ -2381,12 +2436,20 @@ eqjoinsel(PG_FUNCTION_ARGS)
 		fmgr_info(opfuncoid, &eqproc);
 		hasmatch1 = (bool *) palloc0(sslot1.nvalues * sizeof(bool));
 		hasmatch2 = (bool *) palloc0(sslot2.nvalues * sizeof(bool));
+
+		/*
+		 * If the MCV lists are long enough to justify hashing, try to look up
+		 * hash functions for the join operator.  XXX should this be Max()?
+		 */
+		if (Min(sslot1.nvalues, sslot2.nvalues) >= EQJOINSEL_MCV_HASH_THRESHOLD)
+			(void) get_op_hash_functions(operator, &hashLeft, &hashRight);
 	}
 	else
 		memset(&eqproc, 0, sizeof(eqproc)); /* silence uninit-var warnings */
 
 	/* We need to compute the inner-join selectivity in all cases */
 	selec_inner = eqjoinsel_inner(&eqproc, collation,
+								  hashLeft, hashRight,
 								  &vardata1, &vardata2,
 								  nd1, nd2,
 								  isdefault1, isdefault2,
@@ -2416,6 +2479,7 @@ eqjoinsel(PG_FUNCTION_ARGS)
 
 			if (!join_is_reversed)
 				selec = eqjoinsel_semi(&eqproc, collation,
+									   hashLeft, hashRight,
 									   false,
 									   &vardata1, &vardata2,
 									   nd1, nd2,
@@ -2428,6 +2492,7 @@ eqjoinsel(PG_FUNCTION_ARGS)
 									   inner_rel);
 			else
 				selec = eqjoinsel_semi(&eqproc, collation,
+									   hashLeft, hashRight,
 									   true,
 									   &vardata2, &vardata1,
 									   nd2, nd1,
@@ -2487,6 +2552,7 @@ eqjoinsel(PG_FUNCTION_ARGS)
  */
 static double
 eqjoinsel_inner(FmgrInfo *eqproc, Oid collation,
+				Oid hashLeft, Oid hashRight,
 				VariableStatData *vardata1, VariableStatData *vardata2,
 				double nd1, double nd2,
 				bool isdefault1, bool isdefault2,
@@ -2528,6 +2594,7 @@ eqjoinsel_inner(FmgrInfo *eqproc, Oid collation,
 
 		/* Fill the match arrays */
 		eqjoinsel_find_matches(eqproc, collation,
+							   hashLeft, hashRight,
 							   false,
 							   sslot1, sslot2,
 							   sslot1->nvalues, sslot2->nvalues,
@@ -2644,6 +2711,7 @@ eqjoinsel_inner(FmgrInfo *eqproc, Oid collation,
  */
 static double
 eqjoinsel_semi(FmgrInfo *eqproc, Oid collation,
+			   Oid hashLeft, Oid hashRight,
 			   bool op_is_reversed,
 			   VariableStatData *vardata1, VariableStatData *vardata2,
 			   double nd1, double nd2,
@@ -2735,6 +2803,7 @@ eqjoinsel_semi(FmgrInfo *eqproc, Oid collation,
 			memset(hasmatch2, 0, clamped_nvalues2 * sizeof(bool));
 			/* Re-fill the match arrays */
 			eqjoinsel_find_matches(eqproc, collation,
+								   hashLeft, hashRight,
 								   op_is_reversed,
 								   sslot1, sslot2,
 								   sslot1->nvalues, clamped_nvalues2,
@@ -2810,6 +2879,8 @@ eqjoinsel_semi(FmgrInfo *eqproc, Oid collation,
  * Inputs:
  *	eqproc: FmgrInfo for equality function to use (might be reversed)
  *	collation: OID of collation to use
+ *	hashLeft, hashRight: OIDs of hash functions associated with equality op,
+ *		or InvalidOid if we're not to use hashing
  *	op_is_reversed: indicates that eqproc compares right type to left type
  *	sslot1, sslot2: MCV values for the lefthand and righthand inputs
  *	nvalues1, nvalues2: number of values to be considered (can be less than
@@ -2821,6 +2892,9 @@ eqjoinsel_semi(FmgrInfo *eqproc, Oid collation,
  *	*p_matchprodfreq: receives sum(sslot1->numbers[i] * sslot2->numbers[j])
  *		for matching MCVs
  *
+ * Note that hashLeft is for the eqproc's left-hand input type, hashRight
+ * for its right, regardless of op_is_reversed.
+ *
  * Note we assume that each MCV will match at most one member of the other
  * MCV list.  If the operator isn't really equality, there could be multiple
  * matches --- but we don't look for them, both for speed and because the
@@ -2828,6 +2902,7 @@ eqjoinsel_semi(FmgrInfo *eqproc, Oid collation,
  */
 static void
 eqjoinsel_find_matches(FmgrInfo *eqproc, Oid collation,
+					   Oid hashLeft, Oid hashRight,
 					   bool op_is_reversed,
 					   AttStatsSlot *sslot1, AttStatsSlot *sslot2,
 					   int nvalues1, int nvalues2,
@@ -2848,12 +2923,119 @@ eqjoinsel_find_matches(FmgrInfo *eqproc, Oid collation,
 	fcinfo->args[0].isnull = false;
 	fcinfo->args[1].isnull = false;
 
-	/*
-	 * The reason for this extra level of braces will become apparent later.
-	 * For now, it just prevents having to re-indent this chunk of code moved
-	 * from eqjoinsel_inner.
-	 */
+	if (OidIsValid(hashLeft) && OidIsValid(hashRight))
+	{
+		/* Use a hash table to speed up the matching */
+		LOCAL_FCINFO(hash_fcinfo, 1);
+		FmgrInfo	hash_proc;
+		MCVHashContext hashContext;
+		MCVHashTable_hash *hashTable;
+		AttStatsSlot *statsProbe;
+		AttStatsSlot *statsHash;
+		bool	   *hasMatchProbe;
+		bool	   *hasMatchHash;
+		int			nvaluesProbe;
+		int			nvaluesHash;
+
+		/* Make sure we build the hash table on the smaller array. */
+		if (sslot1->nvalues >= sslot2->nvalues)
+		{
+			statsProbe = sslot1;
+			statsHash = sslot2;
+			hasMatchProbe = hasmatch1;
+			hasMatchHash = hasmatch2;
+			nvaluesProbe = nvalues1;
+			nvaluesHash = nvalues2;
+		}
+		else
+		{
+			/* We'll have to reverse the direction of use of the operator. */
+			op_is_reversed = !op_is_reversed;
+			statsProbe = sslot2;
+			statsHash = sslot1;
+			hasMatchProbe = hasmatch2;
+			hasMatchHash = hasmatch1;
+			nvaluesProbe = nvalues2;
+			nvaluesHash = nvalues1;
+		}
+
+		/*
+		 * Build the hash table on the smaller array, using the appropriate
+		 * hash function for its data type.
+		 */
+		fmgr_info(op_is_reversed ? hashLeft : hashRight, &hash_proc);
+		InitFunctionCallInfoData(*hash_fcinfo, &hash_proc, 1, collation,
+								 NULL, NULL);
+		hash_fcinfo->args[0].isnull = false;
+
+		hashContext.equal_fcinfo = fcinfo;
+		hashContext.hash_fcinfo = hash_fcinfo;
+		hashContext.op_is_reversed = op_is_reversed;
+		hashContext.insert_mode = true;
+		get_typlenbyval(statsHash->valuetype,
+						&hashContext.hash_typlen,
+						&hashContext.hash_typbyval);
+
+		hashTable = MCVHashTable_create(CurrentMemoryContext,
+										nvaluesHash,
+										&hashContext);
+
+		for (int i = 0; i < nvaluesHash; i++)
+		{
+			bool		found = false;
+			MCVHashEntry *entry = MCVHashTable_insert(hashTable,
+													  statsHash->values[i],
+													  &found);
+
+			/*
+			 * We're not really expecting duplicates in the MCV list, but it
+			 * seems possible that there could be entries that are equal
+			 * according to the operator we're testing even though they are
+			 * unequal according to the datatype's default opclass.  If we
+			 * find a dup, just ignore it, leaving the hash entry's index
+			 * pointing at the first occurrence.
+			 */
+			if (!found)
+				entry->index = i;
+		}
+
+		/*
+		 * Prepare to probe the hash table.  If the probe values are of a
+		 * different data type, then we need to change hash functions.  (This
+		 * code relies on the assumption that since we defined SH_STORE_HASH,
+		 * simplehash.h will never need to compute hash values for existing
+		 * hash table entries.)
+		 */
+		hashContext.insert_mode = false;
+		if (hashLeft != hashRight)
+		{
+			fmgr_info(op_is_reversed ? hashRight : hashLeft, &hash_proc);
+			/* Resetting hash_fcinfo is probably unnecessary, but be safe */
+			InitFunctionCallInfoData(*hash_fcinfo, &hash_proc, 1, collation,
+									 NULL, NULL);
+			hash_fcinfo->args[0].isnull = false;
+		}
+
+		/* Look up each probe value in turn. */
+		for (int i = 0; i < nvaluesProbe; i++)
+		{
+			MCVHashEntry *entry = MCVHashTable_lookup(hashTable,
+													  statsProbe->values[i]);
+
+			/* As in the other code path, skip already-matched hash entries */
+			if (entry != NULL && !hasMatchHash[entry->index])
+			{
+				hasMatchHash[entry->index] = hasMatchProbe[i] = true;
+				nmatches++;
+				matchprodfreq += statsHash->numbers[entry->index] * statsProbe->numbers[i];
+			}
+		}
+
+		MCVHashTable_destroy(hashTable);
+	}
+	else
 	{
+		/* We're not to use hashing, so do it the O(N^2) way */
 		int			index1,
 					index2;
 
@@ -2897,6 +3079,67 @@ eqjoinsel_find_matches(FmgrInfo *eqproc, Oid collation,
 	*p_matchprodfreq = matchprodfreq;
 }
 
+/*
+ * Support functions for the hash tables used by eqjoinsel_find_matches
+ */
+static uint32
+hash_mcv(MCVHashTable_hash *tab, Datum key)
+{
+	MCVHashContext *context = (MCVHashContext *) tab->private_data;
+	FunctionCallInfo fcinfo = context->hash_fcinfo;
+	Datum		fresult;
+
+	fcinfo->args[0].value = key;
+	fcinfo->isnull = false;
+	fresult = FunctionCallInvoke(fcinfo);
+	Assert(!fcinfo->isnull);
+	return DatumGetUInt32(fresult);
+}
+
+static bool
+mcvs_equal(MCVHashTable_hash *tab, Datum key0, Datum key1)
+{
+	MCVHashContext *context = (MCVHashContext *) tab->private_data;
+
+	if (context->insert_mode)
+	{
+		/*
+		 * During the insertion step, any comparisons will be between two
+		 * Datums of the hash table's data type, so if the given operator is
+		 * cross-type it will be the wrong thing to use.  Fortunately, we can
+		 * use datum_image_eq instead.  The MCV values should all be distinct
+		 * anyway, so it's mostly pro-forma to compare them at all.
+		 */
+		return datum_image_eq(key0, key1,
+							  context->hash_typbyval, context->hash_typlen);
+	}
+	else
+	{
+		FunctionCallInfo fcinfo = context->equal_fcinfo;
+		Datum		fresult;
+
+		/*
+		 * Apply the operator the correct way around.  Although simplehash.h
+		 * doesn't document this explicitly, during lookups key0 is from the
+		 * hash table while key1 is the probe value, so we should compare them
+		 * in that order only if op_is_reversed.
+		 */
+		if (context->op_is_reversed)
+		{
+			fcinfo->args[0].value = key0;
+			fcinfo->args[1].value = key1;
+		}
+		else
+		{
+			fcinfo->args[0].value = key1;
+			fcinfo->args[1].value = key0;
+		}
+		fcinfo->isnull = false;
+		fresult = FunctionCallInvoke(fcinfo);
+		return (!fcinfo->isnull && DatumGetBool(fresult));
+	}
+}
+
 /*
  *		neqjoinsel		- Join selectivity of "!="
  */
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 23bce72ae64..57f2a9ccdc5 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1649,6 +1649,9 @@ LtreeGistOptions
 LtreeSignature
 MAGIC
 MBuf
+MCVHashContext
+MCVHashEntry
+MCVHashTable_hash
 MCVItem
 MCVList
 MEMORY_BASIC_INFORMATION
-- 
2.43.7