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, 399 insertions, 3 deletions

diff --git a/src/backend/rewrite/rewriteHandler.c b/src/backend/rewrite/rewriteHandler.c
index a8997d5a8ab..b931bc744fe 100644
--- a/src/backend/rewrite/rewriteHandler.c
+++ b/src/backend/rewrite/rewriteHandler.c
@@ -6,7 +6,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/rewrite/rewriteHandler.c,v 1.27 1998/12/14 00:02:16 thomas Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/rewrite/rewriteHandler.c,v 1.28 1999/01/18 00:09:54 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -24,6 +24,13 @@
 #include "parser/parse_relation.h"
 #include "nodes/parsenodes.h"
 
+/***S*I***/
+#include "parser/parse_node.h"
+#include "parser/parse_target.h"
+
+#include "parser/analyze.h"
+#include "optimizer/prep.h"
+
 #include "rewrite/rewriteSupport.h"
 #include "rewrite/rewriteHandler.h"
 #include "rewrite/rewriteManip.h"
@@ -1661,7 +1668,8 @@ apply_RIR_view(Node **nodePtr, int rt_index, RangeTblEntry *rte, List *tlist, in
 
 		case T_SubLink:
 			{
-				SubLink	*sub = (SubLink *)node;
+				SubLink *sub = (SubLink *)node;
+				List *tmp_lefthand, *tmp_oper;
 
 				apply_RIR_view(
 						(Node **)(&(sub->lefthand)),
@@ -1678,6 +1686,15 @@ apply_RIR_view(Node **nodePtr, int rt_index, RangeTblEntry *rte, List *tlist, in
 						tlist,
 						modified,
 						sublevels_up + 1);
+
+				/***S*I***/
+				tmp_lefthand = sub->lefthand;				
+				foreach(tmp_oper, sub->oper)
+				  {				    
+				    lfirst(((Expr *) lfirst(tmp_oper))->args) = 
+				      lfirst(tmp_lefthand);
+				    tmp_lefthand = lnext(tmp_lefthand);
+				  }								
 			}
 			break;
 
@@ -2614,8 +2631,387 @@ QueryRewrite(Query *parsetree)
 		query = (Query *)lfirst(l);
 		results = lappend(results, fireRIRrules(query));
 	}
-
 	return results;
 }
+/***S*I***/
+/* This function takes two targetlists as arguments and checks if the targetlists are compatible
+ * (i.e. both select for the same number of attributes and the types are compatible 
+ */
+void check_targetlists_are_compatible(List *prev_target, List *current_target)
+{
+  List *next_target;
+  
+  if (length(prev_target) != 
+      length(current_target))
+    elog(ERROR,"Each UNION | EXCEPT | INTERSECT query must have the same number of columns.");		      
+  foreach(next_target, current_target)
+    {
+      Oid			itype;
+      Oid			otype;
+      
+      otype = ((TargetEntry *) lfirst(prev_target))->resdom->restype;
+      itype = ((TargetEntry *) lfirst(next_target))->resdom->restype;
+	      
+      /* one or both is a NULL column? then don't convert... */
+      if (otype == InvalidOid)
+	{
+	  /* propagate a known type forward, if available */
+	  if (itype != InvalidOid)
+	    ((TargetEntry *) lfirst(prev_target))->resdom->restype = itype;
+#if FALSE
+	  else
+	    {
+	      ((TargetEntry *) lfirst(prev_target))->resdom->restype = UNKNOWNOID;
+	      ((TargetEntry *) lfirst(next_target))->resdom->restype = UNKNOWNOID;
+	    }
+#endif
+	}
+      else if (itype == InvalidOid)
+	{
+	}
+      /* they don't match in type? then convert... */
+      else if (itype != otype)
+	{
+	  Node	   *expr;
+	  
+	  expr = ((TargetEntry *) lfirst(next_target))->expr;
+	  expr = CoerceTargetExpr(NULL, expr, itype, otype);
+	  if (expr == NULL)
+	    {
+	      elog(ERROR, "Unable to transform %s to %s"
+		   "\n\tEach UNION | EXCEPT | INTERSECT clause must have compatible target types",
+		   typeidTypeName(itype),
+		   typeidTypeName(otype));
+	    }
+	  ((TargetEntry *) lfirst(next_target))->expr = expr;
+	  ((TargetEntry *) lfirst(next_target))->resdom->restype = otype;
+	}
+	      
+      /* both are UNKNOWN? then evaluate as text... */
+      else if (itype == UNKNOWNOID)
+	{
+	  ((TargetEntry *) lfirst(next_target))->resdom->restype = TEXTOID;
+	  ((TargetEntry *) lfirst(prev_target))->resdom->restype = TEXTOID;
+	}
+      prev_target = lnext(prev_target);
+    }
+}
+
+/***S*I***/
+/* Rewrites UNION INTERSECT and EXCEPT queries to semantiacally equivalent
+ * queries that use IN and NOT IN subselects. 
+ * 
+ * The operator tree is attached to 'intersectClause' (see rule
+ * 'SelectStmt' in gram.y) of the 'parsetree' given as an
+ * argument. First we remember some clauses (the sortClause, the
+ * unique flag etc.)  Then we translate the operator tree to DNF
+ * (disjunctive normal form) by 'cnfify'. (Note that 'cnfify' produces
+ * CNF but as we exchanged ANDs with ORs in function A_Expr_to_Expr()
+ * earlier we get DNF after exchanging ANDs and ORs again in the
+ * result.) Now we create a new query by evaluating the new operator
+ * tree which is in DNF now. For every AND we create an entry in the
+ * union list and for every OR we create an IN subselect. (NOT IN
+ * subselects are created for OR NOT nodes). The first entry of the
+ * union list is handed back but before that the remembered clauses
+ * (sortClause etc) are attached to the new top Node (Note that the 
+ * new top Node can differ from the parsetree given as argument because of
+ * the translation to DNF. That's why we have to remember the sortClause or
+ * unique flag!) */
+Query *
+Except_Intersect_Rewrite (Query *parsetree)
+{
+ 
+  SubLink *n;
+  Query	  *result, *intersect_node;
+  List	  *elist, *intersect_list = NIL, *intersect, *intersectClause;
+  List	  *union_list = NIL, *sortClause;  
+  List	  *left_expr, *right_expr, *resnames = NIL;
+  char	  *op, *uniqueFlag, *into;
+  bool	  isBinary, isPortal;  
+  CmdType commandType = CMD_SELECT;
+  List	  *rtable_insert = NIL;  
+
+  List	  *prev_target = NIL;
+
+  /* Remember the Resnames of the given parsetree's targetlist
+   * (these are the resnames of the first Select Statement of 
+   * the query formulated by the user and he wants the columns
+   * named by these strings. The transformation to DNF can
+   * cause another Select Statment to be the top one which
+   * uses other names for its columns. Therefore we remeber
+   * the original names and attach them to the targetlist
+   * of the new topmost Node at the end of this function */
+  foreach(elist, parsetree->targetList)
+    {
+      TargetEntry *tent = (TargetEntry *)lfirst(elist);
+      
+      resnames = lappend(resnames, tent->resdom->resname);	
+    }
+  
+  /* If the Statement is an INSERT INTO ... (SELECT...) statement
+   * using UNIONs, INTERSECTs or EXCEPTs and the transformation
+   * to DNF makes another Node to the top node we have to transform
+   * the new top node to an INSERT node and the original INSERT node
+   * to a SELECT node */
+  if (parsetree->commandType == CMD_INSERT) 
+    {
+      parsetree->commandType = CMD_SELECT;
+      commandType = CMD_INSERT;
+      parsetree->resultRelation	 = 0;
+      
+      /* The result relation ( = the one to insert into) has to be
+       * attached to the rtable list of the new top node */
+      rtable_insert = nth(length(parsetree->rtable) - 1, parsetree->rtable);	 
+    }
+    
+  /* Save some items, to be able to attach them to the resulting top node
+   * at the end of the function */
+  sortClause = parsetree->sortClause;
+  uniqueFlag = parsetree->uniqueFlag;
+  into = parsetree->into;
+  isBinary = parsetree->isBinary;
+  isPortal = parsetree->isPortal;  
+  
+  /* The operator tree attached to parsetree->intersectClause is still 'raw'
+   * ( = the leaf nodes are still SelectStmt nodes instead of Query nodes)
+   * So step through the tree and transform the nodes using parse_analyze().
+   *
+   * The parsetree (given as an argument to
+   * Except_Intersect_Rewrite()) has already been transformed and
+   * transforming it again would cause troubles.  So we give the 'raw'
+   * version (of the cooked parsetree) to the function to
+   * prevent an additional transformation. Instead we hand back the
+   * 'cooked' version also given as an argument to
+   * intersect_tree_analyze() */
+  intersectClause = 
+    (List *)intersect_tree_analyze((Node *)parsetree->intersectClause, 
+				   (Node *)lfirst(parsetree->unionClause),
+				   (Node *)parsetree);
+  
+  /* intersectClause is no longer needed so set it to NIL */
+  parsetree->intersectClause = NIL;  
+  /* unionClause will be needed later on but the list it delivered
+   * is no longer needed, so set it to NIL */
+  parsetree->unionClause = NIL;	 
+  
+  /* Transform the operator tree to DNF (remember ANDs and ORs have been exchanged,
+   * that's why we get DNF by using cnfify) 
+   * 
+   * After the call, explicit ANDs are removed and all AND operands
+   * are simply items in the intersectClause list */
+  intersectClause = cnfify((Expr *)intersectClause, true);
+ 
+  /* For every entry of the intersectClause list we generate one entry in 
+   * the union_list */
+  foreach(intersect, intersectClause)
+    {	   
+      /* for every OR we create an IN subselect and for every OR NOT
+       * we create a NOT IN subselect, so first extract all the Select
+       * Query nodes from the tree (that contains only OR or OR NOTs
+       * any more because we did a transformation to DNF 
+       *
+       * There must be at least one node that is not negated
+       * (i.e. just OR and not OR NOT) and this node will be the first
+       * in the list returned */
+      intersect_list = NIL; 
+      create_list((Node *)lfirst(intersect), &intersect_list);
+      
+      /* This one will become the Select Query node, all other
+       * nodes are transformed into subselects under this node! */
+      intersect_node = (Query *)lfirst(intersect_list);
+      intersect_list = lnext(intersect_list);
+      
+      /* Check if all Select Statements use the same number of attributes and
+       * if all corresponding attributes are of the same type */
+      if (prev_target)
+	check_targetlists_are_compatible(prev_target, intersect_node->targetList);	     
+      prev_target = intersect_node->targetList;	 
+      /* End of check for corresponding targetlists */
+      
+      /* Transform all nodes remaining into subselects and add them to
+       * the qualifications of the Select Query node */
+      while(intersect_list != NIL) { 
+	
+	n = makeNode(SubLink);
+	
+	/* Here we got an OR so transform it to an IN subselect */
+	if(IsA(lfirst(intersect_list), Query)) 
+	  {	      
+	    /* Check if all Select Statements use the same number of attributes and
+	     * if all corresponding attributes are of the same type */
+	    check_targetlists_are_compatible(prev_target, 
+                                  ((Query *)lfirst(intersect_list))->targetList);  
+	    /* End of check for corresponding targetlists */
+	    
+	    n->subselect = lfirst(intersect_list);
+	    op = "=";	   
+	    n->subLinkType = ANY_SUBLINK;  
+	    n->useor = false;
+	  }
+	/* Here we got an OR NOT node so transform it to a NOT IN  subselect */
+	else 
+	  {
+	    /* Check if all Select Statements use the same number of attributes and
+	     * if all corresponding attributes are of the same type */
+	    check_targetlists_are_compatible(prev_target,
+                   ((Query *)lfirst(((Expr *)lfirst(intersect_list))->args))->targetList);
+	    /* End of check for corresponding targetlists */
+	    
+	    n->subselect = (Node *)lfirst(((Expr *)lfirst(intersect_list))->args);
+	    op = "<>";    
+	    n->subLinkType = ALL_SUBLINK;  
+	    n->useor = true;
+	  }
+	
+	/* Prepare the lefthand side of the Sublinks: All the entries of the
+	 * targetlist must be (IN) or must not be (NOT IN) the subselect */
+	foreach(elist, intersect_node->targetList)
+	  {
+	    Node	  *expr = lfirst(elist);
+	    TargetEntry *tent = (TargetEntry *)expr;
+	    
+	    n->lefthand = lappend(n->lefthand, tent->expr);	  
+	  }
+	
+	/* The first arguments of oper also have to be created for the
+	 * sublink (they are the same as the lefthand side!) */
+	left_expr = n->lefthand;
+	right_expr = ((Query *)(n->subselect))->targetList;
+	
+	foreach(elist, left_expr)
+	  {
+	    Node	   *lexpr = lfirst(elist);
+	    Node	   *rexpr = lfirst(right_expr);
+	    TargetEntry *tent = (TargetEntry *) rexpr;
+	    Expr	   *op_expr;
+	    
+	    op_expr = make_op(op, lexpr, tent->expr);
+	    
+	    n->oper = lappend(n->oper, op_expr);
+	    right_expr = lnext(right_expr);
+	  }
+	
+	/* If the Select Query node has aggregates in use
+	 * add all the subselects to the HAVING qual else to
+	 * the WHERE qual */
+	if(intersect_node->hasAggs == false) {    
+	  AddQual(intersect_node, (Node *)n);
+	}
+	else {
+	  AddHavingQual(intersect_node, (Node *)n);
+	} 
+	
+	/* Now we got sublinks */
+	intersect_node->hasSubLinks = true;	  
+	intersect_list = lnext(intersect_list);      
+      }      
+      intersect_node->intersectClause = NIL;
+      union_list = lappend(union_list, intersect_node);
+    }
+  
+  /* The first entry to union_list is our new top node */
+  result = (Query *)lfirst(union_list);
+  /* attach the rest to unionClause */
+  result->unionClause = lnext(union_list);  
+  /* Attach all the items remembered in the beginning of the function */
+  result->sortClause = sortClause;  
+  result->uniqueFlag = uniqueFlag;  
+  result->into = into;
+  result->isPortal = isPortal;
+  result->isBinary = isBinary;
+  /* The relation to insert into is attached to the range table
+   * of the new top node */
+  if (commandType == CMD_INSERT)  
+    {	   
+      result->rtable = lappend(result->rtable, rtable_insert);	
+      result->resultRelation = length(result->rtable);
+      result->commandType = commandType;  
+    }  
+  /* The resnames of the originally first SelectStatement are 
+   * attached to the new first SelectStatement */
+  foreach(elist, result->targetList)
+    {
+      TargetEntry *tent = (TargetEntry *)lfirst(elist);
+      
+      tent->resdom->resname = lfirst(resnames);
+      resnames = lnext(resnames);
+    }
+  return  result;  
+}
+
+/* Create a list of nodes that are either Query nodes of NOT Expr
+ * nodes followed by a Query node. The tree given in ptr contains at
+ * least one non negated Query node. This node is attached to the
+ * beginning of the list */
+
+void create_list(Node *ptr, List **intersect_list)
+{
+  List *arg;
+  
+  if(IsA(ptr,Query))
+    {
+      /* The non negated node is attached at the beginning (lcons) */
+      *intersect_list = lcons(ptr, *intersect_list);
+      return;	   
+    }
+  
+  if(IsA(ptr,Expr))
+    {
+      if(((Expr *)ptr)->opType == NOT_EXPR)
+	{
+	  /* negated nodes are appended to the end (lappend) */
+	  *intersect_list = lappend(*intersect_list, ptr);	  
+	  return;	  
+	}
+      else
+	{
+	  foreach(arg, ((Expr *)ptr)->args)
+	    {
+	      create_list(lfirst(arg), intersect_list);
+	    }	  
+	  return;	  
+	}
+      return;	   
+    }
+}
+
+/* The nodes given in 'tree' are still 'raw' so 'cook' them using parse_analyze().
+ * The node given in first_select has already been cooked, so don't transform
+ * it again but return a pointer to the previously cooked version given in 'parsetree' 
+ * instead. */
+Node *intersect_tree_analyze(Node *tree, Node *first_select, Node *parsetree)
+{
+  Node *result = (Node *)NIL;
+  List *arg;
+  
+  if(IsA(tree, SelectStmt))
+    {
+      QueryTreeList *qtree;
+      
+      /* If we get to the tree given in first_select return
+       * parsetree instead of performing parse_analyze() */
+      if(tree == first_select){
+	result = parsetree;
+      }
+      else {	
+	/* transform the 'raw' nodes to 'cooked' Query nodes */ 
+	qtree = parse_analyze(lcons(tree, NIL), NULL);
+	result = (Node *)qtree->qtrees[0];	
+      }
+      
+    }  
+  if(IsA(tree,Expr))
+    {
+      /* Call recursively for every argument of the node */
+      foreach(arg, ((Expr *)tree)->args)
+	{
+	  lfirst(arg) = intersect_tree_analyze(lfirst(arg), first_select, parsetree);
+	}
+      result = tree;	  
+    }
+  return result;  
+}
+
+