Hi!

INTERSECT and EXCEPT is available for postgresql-v6.4!

The patch against v6.4 is included at the end of the current text
(in uuencoded form!)

I also included the text of my Master's Thesis. (a postscript
version). I hope that you find something of it useful and would be
happy if parts of it find their way into the PostgreSQL documentation
project (If so, tell me, then I send the sources of the document!)

The contents of the document are:
  -) The first chapter might be of less interest as it gives only an
     overview on SQL.

  -) The second chapter gives a description on much of PostgreSQL's
     features (like user defined types etc. and how to use these features)

  -) The third chapter starts with an overview of PostgreSQL's internal
     structure with focus on the stages a query has to pass (i.e. parser,
     planner/optimizer, executor). Then a detailed description of the
     implementation of the Having clause and the Intersect/Except logic is
     given.

Originally I worked on v6.3.2 but never found time enough to prepare
and post a patch. Now I applied the changes to v6.4 to get Intersect
and Except working with the new version. Chapter 3 of my documentation
deals with the changes against v6.3.2, so keep that in mind when
comparing the parts of the code printed there with the patched sources
of v6.4.

Here are some remarks on the patch. There are some things that have
still to be done but at the moment I don't have time to do them
myself. (I'm doing my military service at the moment) Sorry for that
:-(

-) I used a rewrite technique for the implementation of the Except/Intersect
   logic which rewrites the query to a semantically equivalent query before
   it is handed to the rewrite system (for views, rules etc.), planner,
   executor etc.

-) In v6.3.2 the types of the attributes of two select statements
   connected by the UNION keyword had to match 100%. In v6.4 the types
   only need to be familiar (i.e. int and float can be mixed). Since this
   feature did not exist when I worked on Intersect/Except it
   does not work correctly for Except/Intersect queries WHEN USED IN
   COMBINATION WITH UNIONS! (i.e. sometimes the wrong type is used for the
   resulting table. This is because until now the types of the attributes of
   the first select statement have been used for the resulting table.
   When Intersects and/or Excepts are used in combination with Unions it
   might happen, that the first select statement of the original query
   appears at another position in the query which will be executed. The reason
   for this is the technique used for the implementation of
   Except/Intersect which does a query rewrite!)
   NOTE: It is NOT broken for pure UNION queries and pure INTERSECT/EXCEPT
         queries!!!

-) I had to add the field intersect_clause to some data structures
   but did not find time to implement printfuncs for the new field.
   This does NOT break the debug modes but when an Except/Intersect
   is used the query debug output will be the already rewritten query.

-) Massive changes to the grammar rules for SELECT and INSERT statements
   have been necessary (see comments in gram.y and documentation for
   deatails) in order to be able to use mixed queries like
   (SELECT ... UNION (SELECT ... EXCEPT SELECT)) INTERSECT SELECT...;

-) When using UNION/EXCEPT/INTERSECT you will get:
   NOTICE: equal: "Don't know if nodes of type xxx are equal".
   I did not have  time to add comparsion support for all the needed nodes,
   but the default behaviour of the function equal met my requirements.
   I did not dare to supress this message!

   That's the reason why the regression test for union will fail: These
   messages are also included in the union.out file!

-) Somebody of you changed the union_planner() function for v6.4
   (I copied the targetlist to new_tlist and that was removed and
   replaced by a cleanup of the original targetlist). These chnages
   violated some having queries executed against views so I changed
   it back again. I did not have time to examine the differences between the
   two versions but now it works :-)
   If you want to find out, try the file queries/view_having.sql on
   both versions and compare the results . Two queries won't produce a
   correct result with your version.

regards

    Stefan

1 files changed, 224 insertions, 195 deletions

diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index 3d3ad51c319..dc04e3c5c3d 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/setrefs.c,v 1.29 1998/12/14 00:02:10 thomas Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/setrefs.c,v 1.30 1999/01/18 00:09:48 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -923,173 +923,195 @@ del_agg_clause(Node *clause)
 	return NULL;
 }
 
-
+/***S*H***/ 
 /* check_having_qual_for_vars takes the the havingQual and the actual targetlist as arguments
  * and recursively scans the havingQual for attributes that are not included in the targetlist
  * yet. Attributes contained in the havingQual but not in the targetlist show up with queries
- * like:
- * SELECT sid
+ * like: 
+ * SELECT sid 
  * FROM part
  * GROUP BY sid
- * HAVING MIN(pid) > 1;  (pid is used but never selected for!!!).
+ * HAVING MIN(pid) > 1;  (pid is used but never selected for!!!). 
  * To be able to handle queries like that correctly we have to extend the actual targetlist
- *	(which will be the one used for the GROUP node later on) by these attributes. */
+ *  (which will be the one used for the GROUP node later on) by these attributes. */
 List *
 check_having_qual_for_vars(Node *clause, List *targetlist_so_far)
 {
-	List	   *t;
+  List	   *t;
 
 
-	if (IsA(clause, Var))
-	{
-		RelOptInfo	tmp_rel;
+  if (IsA(clause, Var))
+    {
+      RelOptInfo         tmp_rel;
+      
 
+      tmp_rel.targetlist = targetlist_so_far;
+      
+      /* 
+       * Ha! A Var node!
+       */
 
-		tmp_rel.targetlist = targetlist_so_far;
-
-		/*
-		 * Ha! A Var node!
-		 */
-
-		/* Check if the VAR is already contained in the targetlist */
-		if (tlist_member((Var *) clause, (List *) targetlist_so_far) == NULL)
-			add_tl_element(&tmp_rel, (Var *) clause);
-
-		return tmp_rel.targetlist;
-	}
-
-	else if (is_funcclause(clause) || not_clause(clause) ||
-			 or_clause(clause) || and_clause(clause))
+      /* Check if the VAR is already contained in the targetlist */
+      if (tlist_member((Var *)clause, (List *)targetlist_so_far) == NULL)
 	{
-
-		/*
-		 * This is a function. Recursively call this routine for its
-		 * arguments...
-		 */
-		foreach(t, ((Expr *) clause)->args)
-			targetlist_so_far = check_having_qual_for_vars(lfirst(t), targetlist_so_far);
-		return targetlist_so_far;
-	}
-	else if (IsA(clause, Aggreg))
+	  add_tl_element(&tmp_rel, (Var *)clause); 
+	} 
+	    
+      return tmp_rel.targetlist;
+    }
+  
+  else if (is_funcclause(clause) || not_clause(clause) || 
+	   or_clause(clause) || and_clause(clause))
+    {
+      
+      /*
+       * This is a function. Recursively call this routine for its
+       * arguments...
+       */
+      foreach(t, ((Expr *) clause)->args)
 	{
-		targetlist_so_far =
-			check_having_qual_for_vars(((Aggreg *) clause)->target, targetlist_so_far);
-		return targetlist_so_far;
+	  targetlist_so_far = check_having_qual_for_vars(lfirst(t), targetlist_so_far);
 	}
-	else if (IsA(clause, ArrayRef))
+      return targetlist_so_far;
+    }
+  else if (IsA(clause, Aggreg))
+    {
+	  targetlist_so_far = 
+	    check_having_qual_for_vars(((Aggreg *) clause)->target, targetlist_so_far);
+	  return targetlist_so_far;
+    }
+  else if (IsA(clause, ArrayRef))
+    {
+      ArrayRef   *aref = (ArrayRef *) clause;
+      
+      /*
+       * This is an arrayref. Recursively call this routine for its
+       * expression and its index expression...
+       */
+      foreach(t, aref->refupperindexpr)
 	{
-		ArrayRef   *aref = (ArrayRef *) clause;
-
-		/*
-		 * This is an arrayref. Recursively call this routine for its
-		 * expression and its index expression...
-		 */
-		foreach(t, aref->refupperindexpr)
-			targetlist_so_far = check_having_qual_for_vars(lfirst(t), targetlist_so_far);
-		foreach(t, aref->reflowerindexpr)
-			targetlist_so_far = check_having_qual_for_vars(lfirst(t), targetlist_so_far);
-		targetlist_so_far = check_having_qual_for_vars(aref->refexpr, targetlist_so_far);
-		targetlist_so_far = check_having_qual_for_vars(aref->refassgnexpr, targetlist_so_far);
-
-		return targetlist_so_far;
-	}
-	else if (is_opclause(clause))
-	{
-
-		/*
-		 * This is an operator. Recursively call this routine for both its
-		 * left and right operands
-		 */
-		Node	   *left = (Node *) get_leftop((Expr *) clause);
-		Node	   *right = (Node *) get_rightop((Expr *) clause);
-
-		if (left != (Node *) NULL)
-			targetlist_so_far = check_having_qual_for_vars(left, targetlist_so_far);
-		if (right != (Node *) NULL)
-			targetlist_so_far = check_having_qual_for_vars(right, targetlist_so_far);
-
-		return targetlist_so_far;
+	  targetlist_so_far = check_having_qual_for_vars(lfirst(t), targetlist_so_far);
 	}
-	else if (IsA(clause, Param) ||IsA(clause, Const))
+      foreach(t, aref->reflowerindexpr)
 	{
-		/* do nothing! */
-		return targetlist_so_far;
+	  targetlist_so_far = check_having_qual_for_vars(lfirst(t), targetlist_so_far);
 	}
-
-	/*
-	 * If we get to a sublink, then we only have to check the lefthand
-	 * side of the expression to see if there are any additional VARs
-	 */
-	else if (IsA(clause, SubLink))
+      targetlist_so_far = check_having_qual_for_vars(aref->refexpr, targetlist_so_far);
+      targetlist_so_far = check_having_qual_for_vars(aref->refassgnexpr, targetlist_so_far);
+      
+      return targetlist_so_far;
+    }
+  else if (is_opclause(clause))
+    {
+      
+      /*
+       * This is an operator. Recursively call this routine for both its
+       * left and right operands
+       */
+      Node	   *left = (Node *) get_leftop((Expr *) clause);
+      Node	   *right = (Node *) get_rightop((Expr *) clause);
+      
+      if (left != (Node *) NULL)
+	targetlist_so_far = check_having_qual_for_vars(left, targetlist_so_far);
+      if (right != (Node *) NULL)
+	targetlist_so_far = check_having_qual_for_vars(right, targetlist_so_far);
+      
+      return targetlist_so_far;
+    }
+  else if (IsA(clause, Param) || IsA(clause, Const))
+    {
+      /* do nothing! */
+      return targetlist_so_far;
+    }
+  /* If we get to a sublink, then we only have to check the lefthand side of the expression
+   * to see if there are any additional VARs */
+  else if (IsA(clause, SubLink))
+    {
+      foreach(t,((List *)((SubLink *)clause)->lefthand))
 	{
-		foreach(t, ((List *) ((SubLink *) clause)->lefthand))
-			targetlist_so_far = check_having_qual_for_vars(lfirst(t), targetlist_so_far);
-		return targetlist_so_far;
-	}
-	else
-	{
-
-		/*
-		 * Ooops! we can not handle that!
-		 */
-		elog(ERROR, "check_having_qual_for_vars: Can not handle this having_qual! %d\n",
-			 nodeTag(clause));
-		return NIL;
+	  targetlist_so_far = check_having_qual_for_vars(lfirst(t), targetlist_so_far);
 	}
+      return targetlist_so_far;
+    }
+  else
+    {
+      /*
+       * Ooops! we can not handle that!
+       */
+      elog(ERROR, "check_having_qual_for_vars: Can not handle this having_qual! %d\n",
+	   nodeTag(clause));
+      return NIL;
+    }
 }
 
-/* check_having_qual_for_aggs takes the havingQual, the targetlist and the groupClause
+/* check_having_qual_for_aggs takes the havingQual, the targetlist and the groupClause  
  * as arguments and scans the havingQual recursively for aggregates. If an aggregate is
- * found it is attached to a list and returned by the function. (All the returned lists
+ * found it is attached to a list and returned by the function. (All the returned lists 
  * are concenated to result_plan->aggs in planner.c:union_planner() */
 List *
 check_having_qual_for_aggs(Node *clause, List *subplanTargetList, List *groupClause)
 {
-	List	   *t,
-			   *l1;
+	List	   *t, *l1;
 	List	   *agg_list = NIL;
 
-	int			contained_in_group_clause = 0;
-
+	int contained_in_group_clause = 0;
+	
 
 	if (IsA(clause, Var))
 	{
-		TargetEntry *subplanVar;
-
-		/*
-		 * Ha! A Var node!
-		 */
-		subplanVar = match_varid((Var *) clause, subplanTargetList);
-
-		/*
-		 * Change the varno & varattno fields of the var node to point to
-		 * the resdom->resno fields of the subplan (lefttree)
-		 */
-		((Var *) clause)->varattno = subplanVar->resdom->resno;
-
-		return NIL;
+	  TargetEntry *subplanVar;
+	  
+	  /*
+	   * Ha! A Var node!
+	   */
+	  subplanVar = match_varid((Var *) clause, subplanTargetList);
+	  
+	  /*
+	   * Change the varno & varattno fields of the var node to point to the resdom->resno
+	   * fields of the subplan (lefttree) 
+	   */	  
+	  ((Var *) clause)->varattno = subplanVar->resdom->resno;
+
+	  return NIL;
 
 	}
-	else if (is_funcclause(clause) || not_clause(clause) ||
-			 or_clause(clause) || and_clause(clause))
+        /***S*H***/
+	else if (is_funcclause(clause) || not_clause(clause) || 
+		 or_clause(clause) || and_clause(clause))
 	{
+	  int new_length=0, old_length=0;
+	  
 		/*
 		 * This is a function. Recursively call this routine for its
 		 * arguments... (i.e. for AND, OR, ... clauses!)
 		 */
 		foreach(t, ((Expr *) clause)->args)
 		{
-			agg_list = nconc(agg_list,
-				 check_having_qual_for_aggs(lfirst(t), subplanTargetList,
-											groupClause));
+		  old_length=length((List *)agg_list);
+
+		  agg_list = nconc(agg_list,
+				   check_having_qual_for_aggs(lfirst(t), subplanTargetList,
+							      groupClause));
+
+		  /* The arguments of OR or AND clauses are comparisons or relations 
+		   * and because we are in the havingQual there must be at least one operand
+		   * using an aggregate function. If so, we will find it and the length of the
+		   * agg_list will be increased after the above call to 
+		   * check_having_qual_for_aggs. If there are no aggregates used, the query
+                   * could have been formulated using the 'where' clause */
+		  if(((new_length=length((List *)agg_list)) == old_length) || (new_length == 0))
+		    {
+		      elog(ERROR,"This could have been done in a where clause!!");
+		      return NIL;
+		    } 
 		}
 		return agg_list;
 	}
 	else if (IsA(clause, Aggreg))
 	{
 		return lcons(clause,
-					 check_having_qual_for_aggs(((Aggreg *) clause)->target, subplanTargetList,
-												groupClause));
+		    check_having_qual_for_aggs(((Aggreg *) clause)->target, subplanTargetList,
+					       groupClause));		
 	}
 	else if (IsA(clause, ArrayRef))
 	{
@@ -1102,21 +1124,21 @@ check_having_qual_for_aggs(Node *clause, List *subplanTargetList, List *groupCla
 		foreach(t, aref->refupperindexpr)
 		{
 			agg_list = nconc(agg_list,
-				 check_having_qual_for_aggs(lfirst(t), subplanTargetList,
-											groupClause));
+					 check_having_qual_for_aggs(lfirst(t), subplanTargetList,
+								    groupClause));
 		}
 		foreach(t, aref->reflowerindexpr)
 		{
 			agg_list = nconc(agg_list,
-				 check_having_qual_for_aggs(lfirst(t), subplanTargetList,
-											groupClause));
+					 check_having_qual_for_aggs(lfirst(t), subplanTargetList,
+								    groupClause));
 		}
 		agg_list = nconc(agg_list,
-			 check_having_qual_for_aggs(aref->refexpr, subplanTargetList,
-										groupClause));
+				 check_having_qual_for_aggs(aref->refexpr, subplanTargetList,
+							    groupClause));
 		agg_list = nconc(agg_list,
-		check_having_qual_for_aggs(aref->refassgnexpr, subplanTargetList,
-								   groupClause));
+				 check_having_qual_for_aggs(aref->refassgnexpr, subplanTargetList,
+							    groupClause));
 
 		return agg_list;
 	}
@@ -1132,85 +1154,92 @@ check_having_qual_for_aggs(Node *clause, List *subplanTargetList, List *groupCla
 
 		if (left != (Node *) NULL)
 			agg_list = nconc(agg_list,
-					  check_having_qual_for_aggs(left, subplanTargetList,
-												 groupClause));
+					 check_having_qual_for_aggs(left, subplanTargetList,
+								    groupClause));
 		if (right != (Node *) NULL)
 			agg_list = nconc(agg_list,
 					 check_having_qual_for_aggs(right, subplanTargetList,
-												groupClause));
+								    groupClause));
 
 		return agg_list;
 	}
-	else if (IsA(clause, Param) ||IsA(clause, Const))
+	else if (IsA(clause, Param) || IsA(clause, Const))
 	{
 		/* do nothing! */
 		return NIL;
 	}
-
-	/*
-	 * This is for Sublinks which show up as EXPR nodes. All the other
-	 * EXPR nodes (funcclauses, and_clauses, or_clauses) were caught above
-	 */
+	/* This is for Sublinks which show up as EXPR nodes. All the other EXPR nodes
+         * (funcclauses, and_clauses, or_clauses) were caught above */
 	else if (IsA(clause, Expr))
-	{
-
-		/*
-		 * Only the lefthand side of the sublink has to be checked for
-		 * aggregates to be attached to result_plan->aggs (see
-		 * planner.c:union_planner() )
-		 */
-		foreach(t, ((List *) ((SubLink *) ((SubPlan *)
-						   ((Expr *) clause)->oper)->sublink)->lefthand))
-		{
-			agg_list =
-				nconc(agg_list,
-					  check_having_qual_for_aggs(lfirst(t),
-										subplanTargetList, groupClause));
-		}
-
-
-		/*
-		 * All arguments to the Sublink node are attributes from outside
-		 * used within the sublink. Here we have to check that only
-		 * attributes that is grouped for are used!
-		 */
-		foreach(t, ((Expr *) clause)->args)
-		{
-			contained_in_group_clause = 0;
-
-			foreach(l1, groupClause)
-			{
-				if (tlist_member(lfirst(t), lcons(((GroupClause *) lfirst(l1))->entry, NIL)) !=
-					NULL)
-					contained_in_group_clause = 1;
-			}
-
-			/*
-			 * If the use of the attribute is allowed (i.e. it is in the
-			 * groupClause) we have to adjust the varnos and varattnos
-			 */
-			if (contained_in_group_clause)
-			{
-				agg_list =
-					nconc(agg_list,
-						  check_having_qual_for_aggs(lfirst(t),
-										subplanTargetList, groupClause));
-			}
-			else
-			{
-				elog(ERROR, "You must group by the attribute used from outside!");
-				return NIL;
-			}
+	  {
+	    /* Only the lefthand side of the sublink has to be checked for aggregates
+             * to be attached to result_plan->aggs (see planner.c:union_planner() )
+	     */	    
+	    foreach(t,((List *)((SubLink *)((SubPlan *)
+		       ((Expr *)clause)->oper)->sublink)->lefthand)) 
+	      {
+		agg_list = 
+		  nconc(agg_list,
+			check_having_qual_for_aggs(lfirst(t), 
+						   subplanTargetList, groupClause));
+	      }
+
+            /* The first argument of ...->oper has also to be checked */
+	    {	      
+	      List *tmp_ptr;
+	      
+	      foreach(tmp_ptr, ((SubLink *)((SubPlan *)
+					    ((Expr *)clause)->oper)->sublink)->oper)
+		{		
+  		  agg_list = 
+		    nconc(agg_list,
+			  check_having_qual_for_aggs((Node *)lfirst(((Expr *)
+								     lfirst(tmp_ptr))->args), 
+						     subplanTargetList, groupClause));
 		}
-		return agg_list;
-	}
+	    }
+	      		
+	    /* All arguments to the Sublink node are attributes from outside used within
+	     * the sublink. Here we have to check that only attributes that is grouped for
+	     * are used! */
+	    foreach(t,((Expr *)clause)->args) 
+	      {	
+		contained_in_group_clause = 0;
+
+		foreach(l1,groupClause)
+		  {
+		    if (tlist_member(lfirst(t),lcons(((GroupClause *)lfirst(l1))->entry,NIL)) != 
+			NULL)
+		      {
+			contained_in_group_clause=1;
+		      }
+		  }
+		
+		/* If the use of the attribute is allowed (i.e. it is in the groupClause)
+		 * we have to adjust the varnos and varattnos */
+		if (contained_in_group_clause)
+		  {
+		    agg_list = 
+		      nconc(agg_list,
+			    check_having_qual_for_aggs(lfirst(t), 
+						       subplanTargetList, groupClause));
+		  }
+		else
+		  {
+		    elog(ERROR,"You must group by the attribute used from outside!");
+		    return NIL;
+		  }		
+	      }
+	    return agg_list;
+	  }
 	else
-	{
-		/*
-		 * Ooops! we can not handle that!
-		 */
-		elog(ERROR, "check_having_qual_for_aggs: Can not handle this having_qual! %d\n",
-			 nodeTag(clause));
-		return NIL;
-	}
+	  {
+	    /*
+	     * Ooops! we can not handle that!
+	     */
+	    elog(ERROR, "check_having_qual_for_aggs: Can not handle this having_qual! %d\n",
+		 nodeTag(clause));
+	    return NIL;
+	  }
 }
+/***S*H***/ /* End */