Refactor planner's pathkeys data structure to create a separate, explicit

representation of equivalence classes of variables.  This is an extensive
rewrite, but it brings a number of benefits:
* planner no longer fails in the presence of "incomplete" operator families
that don't offer operators for every possible combination of datatypes.
* avoid generating and then discarding redundant equality clauses.
* remove bogus assumption that derived equalities always use operators
named "=".
* mergejoins can work with a variety of sort orders (e.g., descending) now,
instead of tying each mergejoinable operator to exactly one sort order.
* better recognition of redundant sort columns.
* can make use of equalities appearing underneath an outer join.

4 files changed, 115 insertions, 70 deletions

diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index 4943bb20297..7b003dc095c 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -15,7 +15,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/copyfuncs.c,v 1.361 2007/01/10 18:06:02 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/copyfuncs.c,v 1.362 2007/01/20 20:45:38 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -1284,16 +1284,18 @@ _copyFromExpr(FromExpr *from)
  */
 
 /*
- * _copyPathKeyItem
+ * _copyPathKey
  */
-static PathKeyItem *
-_copyPathKeyItem(PathKeyItem *from)
+static PathKey *
+_copyPathKey(PathKey *from)
 {
-	PathKeyItem *newnode = makeNode(PathKeyItem);
+	PathKey *newnode = makeNode(PathKey);
 
-	COPY_NODE_FIELD(key);
-	COPY_SCALAR_FIELD(sortop);
-	COPY_SCALAR_FIELD(nulls_first);
+	/* EquivalenceClasses are never moved, so just shallow-copy the pointer */
+	COPY_SCALAR_FIELD(pk_eclass);
+	COPY_SCALAR_FIELD(pk_opfamily);
+	COPY_SCALAR_FIELD(pk_strategy);
+	COPY_SCALAR_FIELD(pk_nulls_first);
 
 	return newnode;
 }
@@ -1316,21 +1318,15 @@ _copyRestrictInfo(RestrictInfo *from)
 	COPY_BITMAPSET_FIELD(left_relids);
 	COPY_BITMAPSET_FIELD(right_relids);
 	COPY_NODE_FIELD(orclause);
+	/* EquivalenceClasses are never copied, so shallow-copy the pointers */
+	COPY_SCALAR_FIELD(parent_ec);
 	COPY_SCALAR_FIELD(eval_cost);
 	COPY_SCALAR_FIELD(this_selec);
-	COPY_SCALAR_FIELD(mergejoinoperator);
-	COPY_SCALAR_FIELD(left_sortop);
-	COPY_SCALAR_FIELD(right_sortop);
-	COPY_SCALAR_FIELD(mergeopfamily);
-
-	/*
-	 * Do not copy pathkeys, since they'd not be canonical in a copied query
-	 */
-	newnode->left_pathkey = NIL;
-	newnode->right_pathkey = NIL;
-
-	COPY_SCALAR_FIELD(left_mergescansel);
-	COPY_SCALAR_FIELD(right_mergescansel);
+	COPY_NODE_FIELD(mergeopfamilies);
+	/* EquivalenceClasses are never copied, so shallow-copy the pointers */
+	COPY_SCALAR_FIELD(left_ec);
+	COPY_SCALAR_FIELD(right_ec);
+	COPY_SCALAR_FIELD(outer_is_left);
 	COPY_SCALAR_FIELD(hashjoinoperator);
 	COPY_SCALAR_FIELD(left_bucketsize);
 	COPY_SCALAR_FIELD(right_bucketsize);
@@ -3033,8 +3029,8 @@ copyObject(void *from)
 			/*
 			 * RELATION NODES
 			 */
-		case T_PathKeyItem:
-			retval = _copyPathKeyItem(from);
+		case T_PathKey:
+			retval = _copyPathKey(from);
 			break;
 		case T_RestrictInfo:
 			retval = _copyRestrictInfo(from);
diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c
index fafd8ae5468..40a91a2b0ed 100644
--- a/src/backend/nodes/equalfuncs.c
+++ b/src/backend/nodes/equalfuncs.c
@@ -18,7 +18,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/equalfuncs.c,v 1.295 2007/01/10 18:06:03 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/equalfuncs.c,v 1.296 2007/01/20 20:45:38 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -596,11 +596,27 @@ _equalFromExpr(FromExpr *a, FromExpr *b)
  */
 
 static bool
-_equalPathKeyItem(PathKeyItem *a, PathKeyItem *b)
+_equalPathKey(PathKey *a, PathKey *b)
 {
-	COMPARE_NODE_FIELD(key);
-	COMPARE_SCALAR_FIELD(sortop);
-	COMPARE_SCALAR_FIELD(nulls_first);
+	/*
+	 * This is normally used on non-canonicalized PathKeys, so must chase
+	 * up to the topmost merged EquivalenceClass and see if those are the
+	 * same (by pointer equality).
+	 */
+	EquivalenceClass *a_eclass;
+	EquivalenceClass *b_eclass;
+
+	a_eclass = a->pk_eclass;
+	while (a_eclass->ec_merged)
+		a_eclass = a_eclass->ec_merged;
+	b_eclass = b->pk_eclass;
+	while (b_eclass->ec_merged)
+		b_eclass = b_eclass->ec_merged;
+	if (a_eclass != b_eclass)
+		return false;
+	COMPARE_SCALAR_FIELD(pk_opfamily);
+	COMPARE_SCALAR_FIELD(pk_strategy);
+	COMPARE_SCALAR_FIELD(pk_nulls_first);
 
 	return true;
 }
@@ -2016,8 +2032,8 @@ equal(void *a, void *b)
 			/*
 			 * RELATION NODES
 			 */
-		case T_PathKeyItem:
-			retval = _equalPathKeyItem(a, b);
+		case T_PathKey:
+			retval = _equalPathKey(a, b);
 			break;
 		case T_RestrictInfo:
 			retval = _equalRestrictInfo(a, b);
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 6137c39af0c..f0b72ea0f64 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.293 2007/01/10 18:06:03 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.294 2007/01/20 20:45:38 tgl Exp $
  *
  * NOTES
  *	  Every node type that can appear in stored rules' parsetrees *must*
@@ -1196,29 +1196,11 @@ _outNestPath(StringInfo str, NestPath *node)
 static void
 _outMergePath(StringInfo str, MergePath *node)
 {
-	int			numCols;
-	int			i;
-
 	WRITE_NODE_TYPE("MERGEPATH");
 
 	_outJoinPathInfo(str, (JoinPath *) node);
 
 	WRITE_NODE_FIELD(path_mergeclauses);
-
-	numCols = list_length(node->path_mergeclauses);
-
-	appendStringInfo(str, " :path_mergeFamilies");
-	for (i = 0; i < numCols; i++)
-		appendStringInfo(str, " %u", node->path_mergeFamilies[i]);
-
-	appendStringInfo(str, " :path_mergeStrategies");
-	for (i = 0; i < numCols; i++)
-		appendStringInfo(str, " %d", node->path_mergeStrategies[i]);
-
-	appendStringInfo(str, " :path_mergeNullsFirst");
-	for (i = 0; i < numCols; i++)
-		appendStringInfo(str, " %d", (int) node->path_mergeNullsFirst[i]);
-
 	WRITE_NODE_FIELD(outersortkeys);
 	WRITE_NODE_FIELD(innersortkeys);
 }
@@ -1241,7 +1223,8 @@ _outPlannerInfo(StringInfo str, PlannerInfo *node)
 	/* NB: this isn't a complete set of fields */
 	WRITE_NODE_FIELD(parse);
 	WRITE_NODE_FIELD(join_rel_list);
-	WRITE_NODE_FIELD(equi_key_list);
+	WRITE_NODE_FIELD(eq_classes);
+	WRITE_NODE_FIELD(canon_pathkeys);
 	WRITE_NODE_FIELD(left_join_clauses);
 	WRITE_NODE_FIELD(right_join_clauses);
 	WRITE_NODE_FIELD(full_join_clauses);
@@ -1284,6 +1267,7 @@ _outRelOptInfo(StringInfo str, RelOptInfo *node)
 	WRITE_NODE_FIELD(subplan);
 	WRITE_NODE_FIELD(baserestrictinfo);
 	WRITE_NODE_FIELD(joininfo);
+	WRITE_BOOL_FIELD(has_eclass_joins);
 	WRITE_BITMAPSET_FIELD(index_outer_relids);
 	WRITE_NODE_FIELD(index_inner_paths);
 }
@@ -1306,13 +1290,48 @@ _outIndexOptInfo(StringInfo str, IndexOptInfo *node)
 }
 
 static void
-_outPathKeyItem(StringInfo str, PathKeyItem *node)
+_outEquivalenceClass(StringInfo str, EquivalenceClass *node)
 {
-	WRITE_NODE_TYPE("PATHKEYITEM");
+	/*
+	 * To simplify reading, we just chase up to the topmost merged EC and
+	 * print that, without bothering to show the merge-ees separately.
+	 */
+	while (node->ec_merged)
+		node = node->ec_merged;
 
-	WRITE_NODE_FIELD(key);
-	WRITE_OID_FIELD(sortop);
-	WRITE_BOOL_FIELD(nulls_first);
+	WRITE_NODE_TYPE("EQUIVALENCECLASS");
+
+	WRITE_NODE_FIELD(ec_opfamilies);
+	WRITE_NODE_FIELD(ec_members);
+	WRITE_NODE_FIELD(ec_sources);
+	WRITE_BITMAPSET_FIELD(ec_relids);
+	WRITE_BOOL_FIELD(ec_has_const);
+	WRITE_BOOL_FIELD(ec_has_volatile);
+	WRITE_BOOL_FIELD(ec_below_outer_join);
+	WRITE_BOOL_FIELD(ec_broken);
+}
+
+static void
+_outEquivalenceMember(StringInfo str, EquivalenceMember *node)
+{
+	WRITE_NODE_TYPE("EQUIVALENCEMEMBER");
+
+	WRITE_NODE_FIELD(em_expr);
+	WRITE_BITMAPSET_FIELD(em_relids);
+	WRITE_BOOL_FIELD(em_is_const);
+	WRITE_BOOL_FIELD(em_is_child);
+	WRITE_OID_FIELD(em_datatype);
+}
+
+static void
+_outPathKey(StringInfo str, PathKey *node)
+{
+	WRITE_NODE_TYPE("PATHKEY");
+
+	WRITE_NODE_FIELD(pk_eclass);
+	WRITE_OID_FIELD(pk_opfamily);
+	WRITE_INT_FIELD(pk_strategy);
+	WRITE_BOOL_FIELD(pk_nulls_first);
 }
 
 static void
@@ -1331,12 +1350,11 @@ _outRestrictInfo(StringInfo str, RestrictInfo *node)
 	WRITE_BITMAPSET_FIELD(left_relids);
 	WRITE_BITMAPSET_FIELD(right_relids);
 	WRITE_NODE_FIELD(orclause);
-	WRITE_OID_FIELD(mergejoinoperator);
-	WRITE_OID_FIELD(left_sortop);
-	WRITE_OID_FIELD(right_sortop);
-	WRITE_OID_FIELD(mergeopfamily);
-	WRITE_NODE_FIELD(left_pathkey);
-	WRITE_NODE_FIELD(right_pathkey);
+	WRITE_NODE_FIELD(parent_ec);
+	WRITE_NODE_FIELD(mergeopfamilies);
+	WRITE_NODE_FIELD(left_ec);
+	WRITE_NODE_FIELD(right_ec);
+	WRITE_BOOL_FIELD(outer_is_left);
 	WRITE_OID_FIELD(hashjoinoperator);
 }
 
@@ -2163,8 +2181,14 @@ _outNode(StringInfo str, void *obj)
 			case T_IndexOptInfo:
 				_outIndexOptInfo(str, obj);
 				break;
-			case T_PathKeyItem:
-				_outPathKeyItem(str, obj);
+			case T_EquivalenceClass:
+				_outEquivalenceClass(str, obj);
+				break;
+			case T_EquivalenceMember:
+				_outEquivalenceMember(str, obj);
+				break;
+			case T_PathKey:
+				_outPathKey(str, obj);
 				break;
 			case T_RestrictInfo:
 				_outRestrictInfo(str, obj);
diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c
index 1a7e1afb71e..e50ebf2bb55 100644
--- a/src/backend/nodes/print.c
+++ b/src/backend/nodes/print.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/print.c,v 1.82 2007/01/05 22:19:30 momjian Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/print.c,v 1.83 2007/01/20 20:45:38 tgl Exp $
  *
  * HISTORY
  *	  AUTHOR			DATE			MAJOR EVENT
@@ -404,7 +404,7 @@ print_expr(Node *expr, List *rtable)
 
 /*
  * print_pathkeys -
- *	  pathkeys list of list of PathKeyItems
+ *	  pathkeys list of PathKeys
  */
 void
 print_pathkeys(List *pathkeys, List *rtable)
@@ -414,17 +414,26 @@ print_pathkeys(List *pathkeys, List *rtable)
 	printf("(");
 	foreach(i, pathkeys)
 	{
-		List	   *pathkey = (List *) lfirst(i);
+		PathKey	   *pathkey = (PathKey *) lfirst(i);
+		EquivalenceClass *eclass;
 		ListCell   *k;
+		bool		first = true;
+
+		eclass = pathkey->pk_eclass;
+		/* chase up, in case pathkey is non-canonical */
+		while (eclass->ec_merged)
+			eclass = eclass->ec_merged;
 
 		printf("(");
-		foreach(k, pathkey)
+		foreach(k, eclass->ec_members)
 		{
-			PathKeyItem *item = (PathKeyItem *) lfirst(k);
+			EquivalenceMember *mem = (EquivalenceMember *) lfirst(k);
 
-			print_expr(item->key, rtable);
-			if (lnext(k))
+			if (first)
+				first = false;
+			else
 				printf(", ");
+			print_expr((Node *) mem->em_expr, rtable);
 		}
 		printf(")");
 		if (lnext(i))