Improve INTERSECT/EXCEPT hashing by realizing that we don't need to make any

hashtable entries for tuples that are found only in the second input: they
can never contribute to the output.  Furthermore, this implies that the
planner should endeavor to put first the smaller (in number of groups) input
relation for an INTERSECT.  Implement that, and upgrade prepunion's estimation
of the number of rows returned by setops so that there's some amount of sanity
in the estimate of which one is smaller.

1 files changed, 64 insertions, 40 deletions

diff --git a/src/backend/optimizer/util/tlist.c b/src/backend/optimizer/util/tlist.c
index a2c627fd4d5..b2fb112ebef 100644
--- a/src/backend/optimizer/util/tlist.c
+++ b/src/backend/optimizer/util/tlist.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/util/tlist.c,v 1.80 2008/08/07 01:11:50 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/util/tlist.c,v 1.81 2008/08/07 19:35:02 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -134,6 +134,69 @@ add_to_flat_tlist(List *tlist, List *vars)
 
 
 /*
+ * get_tlist_exprs
+ *		Get just the expression subtrees of a tlist
+ *
+ * Resjunk columns are ignored unless includeJunk is true
+ */
+List *
+get_tlist_exprs(List *tlist, bool includeJunk)
+{
+	List	   *result = NIL;
+	ListCell   *l;
+
+	foreach(l, tlist)
+	{
+		TargetEntry *tle = (TargetEntry *) lfirst(l);
+
+		if (tle->resjunk && !includeJunk)
+			continue;
+
+		result = lappend(result, tle->expr);
+	}
+	return result;
+}
+
+
+/*
+ * Does tlist have same output datatypes as listed in colTypes?
+ *
+ * Resjunk columns are ignored if junkOK is true; otherwise presence of
+ * a resjunk column will always cause a 'false' result.
+ *
+ * Note: currently no callers care about comparing typmods.
+ */
+bool
+tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
+{
+	ListCell   *l;
+	ListCell   *curColType = list_head(colTypes);
+
+	foreach(l, tlist)
+	{
+		TargetEntry *tle = (TargetEntry *) lfirst(l);
+
+		if (tle->resjunk)
+		{
+			if (!junkOK)
+				return false;
+		}
+		else
+		{
+			if (curColType == NULL)
+				return false;	/* tlist longer than colTypes */
+			if (exprType((Node *) tle->expr) != lfirst_oid(curColType))
+				return false;
+			curColType = lnext(curColType);
+		}
+	}
+	if (curColType != NULL)
+		return false;			/* tlist shorter than colTypes */
+	return true;
+}
+
+
+/*
  * get_sortgroupref_tle
  *		Find the targetlist entry matching the given SortGroupRef index,
  *		and return it.
@@ -303,42 +366,3 @@ grouping_is_hashable(List *groupClause)
 	}
 	return true;
 }
-
-
-
-/*
- * Does tlist have same output datatypes as listed in colTypes?
- *
- * Resjunk columns are ignored if junkOK is true; otherwise presence of
- * a resjunk column will always cause a 'false' result.
- *
- * Note: currently no callers care about comparing typmods.
- */
-bool
-tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
-{
-	ListCell   *l;
-	ListCell   *curColType = list_head(colTypes);
-
-	foreach(l, tlist)
-	{
-		TargetEntry *tle = (TargetEntry *) lfirst(l);
-
-		if (tle->resjunk)
-		{
-			if (!junkOK)
-				return false;
-		}
-		else
-		{
-			if (curColType == NULL)
-				return false;	/* tlist longer than colTypes */
-			if (exprType((Node *) tle->expr) != lfirst_oid(curColType))
-				return false;
-			curColType = lnext(curColType);
-		}
-	}
-	if (curColType != NULL)
-		return false;			/* tlist shorter than colTypes */
-	return true;
-}