9.1-planner-speedup-v5.patch

diff -dcrpN postgresql.orig/src/backend/nodes/Makefile postgresql.1/src/backend/nodes/Makefile
*** postgresql.orig/src/backend/nodes/Makefile	2010-09-21 13:49:56.000000000 +0200
--- postgresql.1/src/backend/nodes/Makefile	2010-10-26 16:37:27.000000000 +0200
*************** subdir = src/backend/nodes
*** 12,18 ****
  top_builddir = ../../..
  include $(top_builddir)/src/Makefile.global
  
! OBJS = nodeFuncs.o nodes.o list.o bitmapset.o tidbitmap.o \
         copyfuncs.o equalfuncs.o makefuncs.o \
         outfuncs.o readfuncs.o print.o read.o params.o value.o
  
--- 12,18 ----
  top_builddir = ../../..
  include $(top_builddir)/src/Makefile.global
  
! OBJS = nodeFuncs.o nodes.o list.o tree.o bitmapset.o tidbitmap.o \
         copyfuncs.o equalfuncs.o makefuncs.o \
         outfuncs.o readfuncs.o print.o read.o params.o value.o
  
diff -dcrpN postgresql.orig/src/backend/nodes/outfuncs.c postgresql.1/src/backend/nodes/outfuncs.c
*** postgresql.orig/src/backend/nodes/outfuncs.c	2010-10-15 10:31:47.000000000 +0200
--- postgresql.1/src/backend/nodes/outfuncs.c	2010-10-25 13:13:00.000000000 +0200
*************** _outList(StringInfo str, List *node)
*** 175,180 ****
--- 175,197 ----
  	appendStringInfoChar(str, ')');
  }
  
+ static void
+ _outTree(StringInfo str, Tree *node)
+ {
+ 	TreeCell   *tc;
+ 	ListCell   *lc;
+ 
+ 	appendStringInfoChar(str, '(');
+ 
+ 	tforeach(tc, lc, node)
+ 	{
+ 		Node	   *node = lfirst(lc);
+ 		_outNode(str, node);
+ 	}
+ 
+ 	appendStringInfoChar(str, ')');
+ }
+ 
  /*
   * _outBitmapset -
   *	   converts a bitmap set of integers
*************** _outPlannerInfo(StringInfo str, PlannerI
*** 1595,1601 ****
  	WRITE_NODE_FIELD(init_plans);
  	WRITE_NODE_FIELD(cte_plan_ids);
  	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);
--- 1612,1618 ----
  	WRITE_NODE_FIELD(init_plans);
  	WRITE_NODE_FIELD(cte_plan_ids);
  	WRITE_NODE_FIELD(eq_classes);
! 	WRITE_NODE_FIELD(rb_canon_pathkeys);
  	WRITE_NODE_FIELD(left_join_clauses);
  	WRITE_NODE_FIELD(right_join_clauses);
  	WRITE_NODE_FIELD(full_join_clauses);
*************** _outNode(StringInfo str, void *obj)
*** 2506,2511 ****
--- 2523,2530 ----
  		appendStringInfo(str, "<>");
  	else if (IsA(obj, List) ||IsA(obj, IntList) || IsA(obj, OidList))
  		_outList(str, obj);
+ 	else if (IsA(obj, Tree))
+ 		_outTree(str, obj);
  	else if (IsA(obj, Integer) ||
  			 IsA(obj, Float) ||
  			 IsA(obj, String) ||
diff -dcrpN postgresql.orig/src/backend/nodes/tree.c postgresql.1/src/backend/nodes/tree.c
*** postgresql.orig/src/backend/nodes/tree.c	1970-01-01 01:00:00.000000000 +0100
--- postgresql.1/src/backend/nodes/tree.c	2010-10-19 11:58:52.000000000 +0200
***************
*** 0 ****
--- 1,223 ----
+ /*-------------------------------------------------------------------------
+  *
+  * tree.c
+  *	  implementation for PostgreSQL generic rbtree package
+  *
+  *
+  * Portions Copyright (c) 1996-2010, PostgreSQL Global Development Group
+  * Portions Copyright (c) 1994, Regents of the University of California
+  *
+  *
+  * IDENTIFICATION
+  *	  $PostgreSQL: pgsql/src/backend/nodes/list.c,v 1.74 2010/02/13 02:34:11 tgl Exp $
+  *
+  *-------------------------------------------------------------------------
+  */
+ #include "postgres.h"
+ 
+ #include "nodes/pg_tree.h"
+ #include "utils/rbtree.h"
+ 
+ 
+ /*
+  * RBTree allocfunc function
+  *
+  * Allocate memory in the MemoryContext given to new_tree().
+  */
+ static RBNode *
+ tree_allocfunc(void *arg)
+ {
+ 	MemoryContext	context = arg;
+ 	MemoryContext	oldcontext;
+ 	RBNode	   *node;
+ 
+ 	oldcontext = MemoryContextSwitchTo(context);
+ 
+ 	node = palloc0(sizeof(TreeCell));
+ 
+ 	MemoryContextSwitchTo(oldcontext);
+ 
+ 	return node;
+ }
+ 
+ 
+ /*
+  * RBTree combiner function
+  *
+  * Because we store lists of Node pointers, we simply concatenate
+  * the lists together. Do this in the MemoryContext given to new_tree().
+  */
+ static void
+ tree_combiner(RBNode *existing, const RBNode *newdata, void *arg)
+ {
+ 	MemoryContext	context = arg;
+ 	MemoryContext	oldcontext;
+ 	TreeCell   *tc1 = (TreeCell *)existing;
+ 	TreeCell   *tc2 = (TreeCell *)newdata;
+ 
+ 	oldcontext = MemoryContextSwitchTo(context);
+ 
+ 	tc1->list = list_concat(tc1->list, tc2->list);
+ 
+ 	MemoryContextSwitchTo(oldcontext);
+ }
+ 
+ 
+ /*
+  * RBTree freefunc function.
+  *
+  * We must not do list_free(((TreeCell *)x)->list) because some code
+  * may still reference it. The RBNode itself can be freed.
+  */
+ static void
+ tree_freefunc(RBNode *x, void *arg)
+ {
+ 	pfree(x);
+ }
+ 
+ /*
+  * new_tree
+  *
+  * Return a freshly allocated Tree.
+  *
+  * Parameters:
+  *	comparator	- comparator function for RBTree
+  *	context		- MemoryContext to allocate the tree, its nodes and
+  *			  the list elements.
+  */
+ Tree *
+ new_tree(rb_comparator comparator, MemoryContext context)
+ {
+ 	MemoryContext	oldcontext;
+ 	Tree	   *tree;
+ 
+ 	Assert((context != NULL));
+ 
+ 	oldcontext = MemoryContextSwitchTo(context);
+ 
+ 	tree = makeNode(Tree);
+ 	tree->n_elems = 0;
+ 	tree->context = context;
+ 	tree->tree = rb_create(sizeof(TreeCell), comparator, tree_combiner, tree_allocfunc, tree_freefunc, context);
+ 
+ 	MemoryContextSwitchTo(oldcontext);
+ 
+ 	return tree;
+ }
+ 
+ /*
+  * tree_find
+  *
+  * Find the element(s) that match the node's key according to
+  * the comparator
+  */
+ List *
+ tree_find(Tree *tree, Node *node)
+ {
+ 	MemoryContext	oldcontext;
+ 	TreeCell   *cell;
+ 	TreeCell   *result;
+ 
+ 	oldcontext = MemoryContextSwitchTo(tree->context);
+ 	cell = palloc0(sizeof(TreeCell));
+ 	cell->list = list_make1(node);
+ 	MemoryContextSwitchTo(oldcontext);
+ 
+ 	result = (TreeCell *)rb_find(tree->tree, (RBNode *)cell);
+ 
+ 	list_free(cell->list);
+ 	pfree(cell);
+ 
+ 	if (result)
+ 		return result->list;
+ 	else
+ 		return NULL;
+ }
+ 
+ /*
+  * tree_add
+  *
+  * Add a Node to the tree.
+  */
+ void
+ tree_add(Tree *tree, Node *node)
+ {
+ 	TreeCell   *cell;
+ 	bool		isNew;
+ 	MemoryContext	oldcontext;
+ 
+ 	if (node == NULL)
+ 		return;
+ 
+ 	oldcontext = MemoryContextSwitchTo(tree->context);
+ 	cell = palloc0(sizeof(TreeCell));
+ 	cell->list = list_make1(node);
+ 	MemoryContextSwitchTo(oldcontext);
+ 
+ 	rb_insert(tree->tree, (RBNode *)cell, &isNew);
+ 	tree->n_elems++;
+ }
+ 
+ /*
+  * tree_add_list
+  *
+  * Add a list of Nodes to the tree.
+  */
+ void
+ tree_add_list(Tree *tree, List *list)
+ {
+ 	TreeCell   *cell;
+ 	bool		isNew;
+ 	MemoryContext	oldcontext;
+ 
+ 	if (list_length(list) == 0)
+ 		return;
+ 
+ 	oldcontext = MemoryContextSwitchTo(tree->context);
+ 	cell = palloc0(sizeof(TreeCell));
+ 	cell->list = list;
+ 	MemoryContextSwitchTo(oldcontext);
+ 
+ 	rb_insert(tree->tree, (RBNode *)cell, &isNew);
+ 	tree->n_elems += list_length(list);
+ }
+ 
+ 
+ /*
+  * tree_delete_ptr
+  *
+  * Delete a Node from the tree. Use the pointer itself
+  * for comparison with list elements.
+  */
+ void
+ tree_delete_ptr(Tree *tree, Node *node)
+ {
+ 	MemoryContext	oldcontext;
+ 	TreeCell   *cell = palloc(sizeof(TreeCell));
+ 	TreeCell   *result;
+ 	List	   *list;
+ 
+ 	/*
+ 	 * First, find the Node in the tree. rb_delete() only works on
+ 	 * RBNodes * that are actually in the tree, we have to use the
+ 	 * pointer rb_find() returns.
+ 	 */
+ 	oldcontext = MemoryContextSwitchTo(tree->context);
+ 	cell->list = list_make1(node);
+ 	MemoryContextSwitchTo(oldcontext);
+ 
+ 	result = (TreeCell *)rb_find(tree->tree, (RBNode *)cell);
+ 
+ 	if (result)
+ 	{
+ 		list = result->list;
+ 
+ 		rb_delete(tree->tree, (RBNode *)result);
+ 
+ 		tree->n_elems -= list_length(list);
+ 
+ 		list = list_delete_ptr(list, node);
+ 
+ 		tree_add_list(tree, list);
+ 	}
+ }
diff -dcrpN postgresql.orig/src/backend/optimizer/path/equivclass.c postgresql.1/src/backend/optimizer/path/equivclass.c
*** postgresql.orig/src/backend/optimizer/path/equivclass.c	2010-10-15 10:31:47.000000000 +0200
--- postgresql.1/src/backend/optimizer/path/equivclass.c	2010-10-26 17:01:57.000000000 +0200
***************
*** 24,29 ****
--- 24,30 ----
  #include "optimizer/planmain.h"
  #include "optimizer/prep.h"
  #include "optimizer/var.h"
+ #include "utils/hsearch.h"
  #include "utils/lsyscache.h"
  
  
*************** add_eq_member(EquivalenceClass *ec, Expr
*** 360,434 ****
  
  
  /*
!  * get_eclass_for_sort_expr
!  *	  Given an expression and opfamily info, find an existing equivalence
!  *	  class it is a member of; if none, build a new single-member
!  *	  EquivalenceClass for it.
!  *
!  * sortref is the SortGroupRef of the originating SortGroupClause, if any,
!  * or zero if not.	(It should never be zero if the expression is volatile!)
!  *
!  * This can be used safely both before and after EquivalenceClass merging;
!  * since it never causes merging it does not invalidate any existing ECs
!  * or PathKeys.
!  *
!  * Note: opfamilies must be chosen consistently with the way
!  * process_equivalence() would do; that is, generated from a mergejoinable
!  * equality operator.  Else we might fail to detect valid equivalences,
!  * generating poor (but not incorrect) plans.
   */
! EquivalenceClass *
! get_eclass_for_sort_expr(PlannerInfo *root,
! 						 Expr *expr,
! 						 Oid expr_datatype,
! 						 List *opfamilies,
! 						 Index sortref)
  {
! 	EquivalenceClass *newec;
! 	EquivalenceMember *newem;
  	ListCell   *lc1;
! 	MemoryContext oldcontext;
  
  	/*
! 	 * Scan through the existing EquivalenceClasses for a match
  	 */
! 	foreach(lc1, root->eq_classes)
  	{
! 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
! 		ListCell   *lc2;
  
  		/*
! 		 * Never match to a volatile EC, except when we are looking at another
! 		 * reference to the same volatile SortGroupClause.
  		 */
! 		if (cur_ec->ec_has_volatile &&
! 			(sortref == 0 || sortref != cur_ec->ec_sortref))
! 			continue;
! 
! 		if (!equal(opfamilies, cur_ec->ec_opfamilies))
  			continue;
  
! 		foreach(lc2, cur_ec->ec_members)
  		{
! 			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
! 
! 			/*
! 			 * If below an outer join, don't match constants: they're not as
! 			 * constant as they look.
! 			 */
! 			if (cur_ec->ec_below_outer_join &&
! 				cur_em->em_is_const)
! 				continue;
  
! 			if (expr_datatype == cur_em->em_datatype &&
! 				equal(expr, cur_em->em_expr))
! 				return cur_ec;	/* Match! */
  		}
  	}
  
  	/*
- 	 * No match, so build a new single-member EC
- 	 *
  	 * Here, we must be sure that we construct the EC in the right context. We
  	 * can assume, however, that the passed expr is long-lived.
  	 */
--- 361,463 ----
  
  
  /*
!  * eq_classes_match - matching function for eq_classes_hash in PlannerInfo
   */
! static int
! eq_classes_match(const void *key1, const void *key2, Size keysize)
  {
! 	EquivalenceClass *ec1 = (EquivalenceClass *) key1; /* this is in the hashtable */
! 	EquivalenceClass *ec2 = (EquivalenceClass *) key2; /* this is the new matched entry */
  	ListCell   *lc1;
! 	ListCell   *lc2;
  
  	/*
! 	 * Never match to a volatile EC, except when we are looking at another
! 	 * reference to the same volatile SortGroupClause.
  	 */
! 	if (ec1->ec_has_volatile &&
! 		(ec2->ec_sortref == 0 || ec2->ec_sortref != ec1->ec_sortref))
! 		return 1;
! 
! 	if (!equal(ec1->ec_opfamilies, ec2->ec_opfamilies))
! 		return 1;
! 
! 	foreach(lc1, ec1->ec_members)
  	{
! 		EquivalenceMember *em1 = (EquivalenceMember *) lfirst(lc1);
  
  		/*
! 		 * If below an outer join, don't match constants: they're not as
! 		 * constant as they look.
  		 */
! 		if (ec1->ec_below_outer_join &&
! 			em1->em_is_const)
  			continue;
  
! 		foreach(lc2, ec2->ec_members)
  		{
! 			EquivalenceMember *em2 = (EquivalenceMember *) lfirst(lc2);
  
! 			if (em1->em_datatype == em2->em_datatype &&
! 				equal(em1->em_expr, em2->em_expr))
! 				return 0;
  		}
  	}
  
+ 	return 1;
+ }
+ 
+ 
+ /*
+  * build_eq_classes_hash
+  *	Build the initial contents of PlannerInfo.eq_classes_hash
+  *	for faster search in PlannerInfo.eq_classes. This is used
+  *	to  make   get_eclass_for_sort_expr()  faster  for  large
+  *	inheritance trees.
+  */
+ static void
+ build_eq_classes_hash(PlannerInfo *root)
+ {
+ 	MemoryContext	oldcontext;
+ 	HASHCTL	info;
+ 	
+ 	ListCell   *lc;
+ 
+ 	info.match = eq_classes_match;
+ 	info.hcxt = root->planner_cxt;
+ 	info.keysize = sizeof(Relids);
+ 	info.entrysize = sizeof(EquivalenceClass);
+ 
+ 	oldcontext = MemoryContextSwitchTo(root->planner_cxt);
+ 
+ 	root->eq_classes_hash = hash_create("eq_classes", 2048, &info,
+ 						HASH_ELEM | HASH_COMPARE | HASH_CONTEXT);
+ 
+ 	foreach(lc, root->eq_classes)
+ 	{
+ 		EquivalenceClass *ec = lfirst(lc);
+ 		bool	found;
+ 
+ 		hash_search_with_hash_value(root->eq_classes_hash, ec,
+ 								bms_hash_value(ec->ec_relids),
+ 								HASH_ENTER, &found);
+ 		Assert(!found);
+ 	}
+ }
+ 
+ 
+ static EquivalenceClass *
+ build_new_ec(PlannerInfo *root,
+ 						 Expr *expr,
+ 						 Oid expr_datatype,
+ 						 List *opfamilies,
+ 						 Index sortref)
+ {
+ 	MemoryContext	oldcontext;
+ 	EquivalenceClass *newec;
+ 	EquivalenceMember *newem;
+ 
  	/*
  	 * Here, we must be sure that we construct the EC in the right context. We
  	 * can assume, however, that the passed expr is long-lived.
  	 */
*************** get_eclass_for_sort_expr(PlannerInfo *ro
*** 471,483 ****
  		}
  	}
  
- 	root->eq_classes = lappend(root->eq_classes, newec);
- 
  	MemoryContextSwitchTo(oldcontext);
  
  	return newec;
  }
  
  
  /*
   * generate_base_implied_equalities
--- 500,631 ----
  		}
  	}
  
  	MemoryContextSwitchTo(oldcontext);
  
  	return newec;
  }
  
+ /*
+  * get_eclass_for_sort_expr
+  *	  Given an expression and opfamily info, find an existing equivalence
+  *	  class it is a member of; if none, build a new single-member
+  *	  EquivalenceClass for it.
+  *
+  * sortref is the SortGroupRef of the originating SortGroupClause, if any,
+  * or zero if not.	(It should never be zero if the expression is volatile!)
+  *
+  * This can be used safely both before and after EquivalenceClass merging;
+  * since it never causes merging it does not invalidate any existing ECs
+  * or PathKeys.
+  *
+  * Note: opfamilies must be chosen consistently with the way
+  * process_equivalence() would do; that is, generated from a mergejoinable
+  * equality operator.  Else we might fail to detect valid equivalences,
+  * generating poor (but not incorrect) plans.
+  */
+ EquivalenceClass *
+ get_eclass_for_sort_expr(PlannerInfo *root,
+ 						 Expr *expr,
+ 						 Oid expr_datatype,
+ 						 List *opfamilies,
+ 						 Index sortref)
+ {
+ 	EquivalenceClass *newec;
+ 	ListCell   *lc1;
+ 	MemoryContext oldcontext;
+ 
+ 	if (root->eq_classes_hash == NULL &&
+ 		list_length(root->eq_classes) > 32)
+ 		build_eq_classes_hash(root);
+ 
+ 	if (root->eq_classes_hash == NULL)
+ 	{
+ 		/*
+ 		 * Scan through the existing EquivalenceClasses for a match
+ 		 */
+ 		foreach(lc1, root->eq_classes)
+ 		{
+ 			EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
+ 			ListCell   *lc2;
+ 
+ 			/*
+ 			 * Never match to a volatile EC, except when we are looking at another
+ 			 * reference to the same volatile SortGroupClause.
+ 			 */
+ 			if (cur_ec->ec_has_volatile &&
+ 				(sortref == 0 || sortref != cur_ec->ec_sortref))
+ 				continue;
+ 
+ 			if (!equal(opfamilies, cur_ec->ec_opfamilies))
+ 				continue;
+ 
+ 			foreach(lc2, cur_ec->ec_members)
+ 			{
+ 				EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
+ 
+ 				/*
+ 				 * If below an outer join, don't match constants: they're not as
+ 				 * constant as they look.
+ 				 */
+ 				if (cur_ec->ec_below_outer_join &&
+ 					cur_em->em_is_const)
+ 					continue;
+ 
+ 				if (expr_datatype == cur_em->em_datatype &&
+ 					equal(expr, cur_em->em_expr))
+ 					return cur_ec;	/* Match! */
+ 			}
+ 		}
+ 
+ 		/*
+ 		 * No match, so build a new single-member EC
+ 		 */
+ 		newec = build_new_ec(root, expr, expr_datatype, opfamilies, sortref);
+ 
+ 		oldcontext = MemoryContextSwitchTo(root->planner_cxt);
+ 		root->eq_classes = lappend(root->eq_classes, newec);
+ 		MemoryContextSwitchTo(oldcontext);
+ 
+ 		return newec;
+ 	}
+ 	else
+ 	{
+ 		EquivalenceClass *ec_found;
+ 		bool	found;
+ 		uint32	hashval;
+ 
+ 		/*
+ 		 * Build the new single-member EC to match against in hash_search()
+ 		 */
+ 		newec = build_new_ec(root, expr, expr_datatype, opfamilies, sortref);
+ 
+ 		hashval = bms_hash_value(newec->ec_relids);
+ 
+ 		ec_found = hash_search_with_hash_value(root->eq_classes_hash, newec, hashval, HASH_FIND, &found);
+ 
+ 		if (found)
+ 		{
+ 			list_free(newec->ec_opfamilies);
+ 			list_free_deep(newec->ec_members);
+ 			bms_free(newec->ec_relids);
+ 			pfree(newec);
+ 			return ec_found;
+ 		}
+ 
+ 		oldcontext = MemoryContextSwitchTo(root->planner_cxt);
+ 
+ 		root->eq_classes = lappend(root->eq_classes, newec);
+ 
+ 		hash_search_with_hash_value(root->eq_classes_hash, newec, hashval, HASH_ENTER, &found);
+ 
+ 		Assert(!found);
+ 
+ 		MemoryContextSwitchTo(oldcontext);
+ 
+ 		return newec;
+ 	}
+ }
+ 
  
  /*
   * generate_base_implied_equalities
diff -dcrpN postgresql.orig/src/backend/optimizer/path/pathkeys.c postgresql.1/src/backend/optimizer/path/pathkeys.c
*** postgresql.orig/src/backend/optimizer/path/pathkeys.c	2010-09-21 13:49:57.000000000 +0200
--- postgresql.1/src/backend/optimizer/path/pathkeys.c	2010-10-26 14:27:20.000000000 +0200
*************** makePathKey(EquivalenceClass *eclass, Oi
*** 71,76 ****
--- 71,112 ----
  	return pk;
  }
  
+ int
+ pathkeys_comparator(const RBNode *a, const RBNode *b, void *arg)
+ {
+ 	TreeCell   *left = (TreeCell *)a;
+ 	TreeCell   *right = (TreeCell *)b;
+ 	PathKey	   *pk_left = (PathKey *)linitial(left->list);
+ 	PathKey	   *pk_right = (PathKey *)linitial(right->list);
+ 
+ 	Assert((pk_left != NULL));
+ 	Assert((pk_right != NULL));
+ 
+ 	if (pk_left->pk_eclass < pk_right->pk_eclass)
+ 		return -1;
+ 	else if (pk_left->pk_eclass > pk_right->pk_eclass)
+ 		return 1;
+ 
+ 	if (pk_left->pk_opfamily < pk_right->pk_opfamily)
+ 		return -1;
+ 	else if (pk_left->pk_opfamily > pk_right->pk_opfamily)
+ 		return 1;
+ 
+ 	if (pk_left->pk_strategy < pk_right->pk_strategy)
+ 		return -1;
+ 	else if (pk_left->pk_strategy > pk_right->pk_strategy)
+ 		return 1;
+ 
+ 	if (pk_left->pk_nulls_first < pk_right->pk_nulls_first)
+ 		return -1;
+ 	else if (pk_left->pk_nulls_first > pk_right->pk_nulls_first)
+ 		return 1;
+ 
+ 	return 0;
+ }
+ 
+ 
+ 
  /*
   * make_canonical_pathkey
   *	  Given the parameters for a PathKey, find any pre-existing matching
*************** make_canonical_pathkey(PlannerInfo *root
*** 85,119 ****
  					   EquivalenceClass *eclass, Oid opfamily,
  					   int strategy, bool nulls_first)
  {
! 	PathKey    *pk;
! 	ListCell   *lc;
  	MemoryContext oldcontext;
  
  	/* The passed eclass might be non-canonical, so chase up to the top */
  	while (eclass->ec_merged)
  		eclass = eclass->ec_merged;
  
- 	foreach(lc, root->canon_pathkeys)
- 	{
- 		pk = (PathKey *) lfirst(lc);
- 		if (eclass == pk->pk_eclass &&
- 			opfamily == pk->pk_opfamily &&
- 			strategy == pk->pk_strategy &&
- 			nulls_first == pk->pk_nulls_first)
- 			return pk;
- 	}
- 
  	/*
  	 * Be sure canonical pathkeys are allocated in the main planning context.
  	 * Not an issue in normal planning, but it is for GEQO.
  	 */
  	oldcontext = MemoryContextSwitchTo(root->planner_cxt);
  
! 	pk = makePathKey(eclass, opfamily, strategy, nulls_first);
! 	root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
  
  	MemoryContextSwitchTo(oldcontext);
  
  	return pk;
  }
  
--- 121,157 ----
  					   EquivalenceClass *eclass, Oid opfamily,
  					   int strategy, bool nulls_first)
  {
! 	PathKey    *pk, *pk_new;
! 	List	   *list;
  	MemoryContext oldcontext;
  
  	/* The passed eclass might be non-canonical, so chase up to the top */
  	while (eclass->ec_merged)
  		eclass = eclass->ec_merged;
  
  	/*
  	 * Be sure canonical pathkeys are allocated in the main planning context.
  	 * Not an issue in normal planning, but it is for GEQO.
  	 */
  	oldcontext = MemoryContextSwitchTo(root->planner_cxt);
  
! 	pk_new = makePathKey(eclass, opfamily, strategy, nulls_first);
  
  	MemoryContextSwitchTo(oldcontext);
  
+ 	list = tree_find(root->rb_canon_pathkeys, (Node *)pk_new);
+ 
+ 	if (list)
+ 	{
+ 		pfree(pk_new);
+ 		pk = (PathKey *) linitial(list);
+ 	}
+ 	else
+ 	{
+ 		tree_add(root->rb_canon_pathkeys, (Node *)pk_new);
+ 		pk = pk_new;
+ 	}
+ 
  	return pk;
  }
  
diff -dcrpN postgresql.orig/src/backend/optimizer/plan/planmain.c postgresql.1/src/backend/optimizer/plan/planmain.c
*** postgresql.orig/src/backend/optimizer/plan/planmain.c	2010-10-08 11:04:23.000000000 +0200
--- postgresql.1/src/backend/optimizer/plan/planmain.c	2010-10-26 14:13:59.000000000 +0200
***************
*** 21,26 ****
--- 21,27 ----
  #include "postgres.h"
  
  #include "miscadmin.h"
+ #include "nodes/pg_tree.h"
  #include "optimizer/cost.h"
  #include "optimizer/pathnode.h"
  #include "optimizer/paths.h"
*************** query_planner(PlannerInfo *root, List *t
*** 117,123 ****
  		 * We still are required to canonicalize any pathkeys, in case it's
  		 * something like "SELECT 2+2 ORDER BY 1".
  		 */
! 		root->canon_pathkeys = NIL;
  		root->query_pathkeys = canonicalize_pathkeys(root,
  													 root->query_pathkeys);
  		root->group_pathkeys = canonicalize_pathkeys(root,
--- 118,124 ----
  		 * We still are required to canonicalize any pathkeys, in case it's
  		 * something like "SELECT 2+2 ORDER BY 1".
  		 */
! 		root->rb_canon_pathkeys = new_tree(pathkeys_comparator, root->planner_cxt);
  		root->query_pathkeys = canonicalize_pathkeys(root,
  													 root->query_pathkeys);
  		root->group_pathkeys = canonicalize_pathkeys(root,
*************** query_planner(PlannerInfo *root, List *t
*** 145,151 ****
  	root->join_rel_hash = NULL;
  	root->join_rel_level = NULL;
  	root->join_cur_level = 0;
! 	root->canon_pathkeys = NIL;
  	root->left_join_clauses = NIL;
  	root->right_join_clauses = NIL;
  	root->full_join_clauses = NIL;
--- 146,152 ----
  	root->join_rel_hash = NULL;
  	root->join_rel_level = NULL;
  	root->join_cur_level = 0;
! 	root->rb_canon_pathkeys = new_tree(pathkeys_comparator, root->planner_cxt);
  	root->left_join_clauses = NIL;
  	root->right_join_clauses = NIL;
  	root->full_join_clauses = NIL;
diff -dcrpN postgresql.orig/src/backend/optimizer/plan/planner.c postgresql.1/src/backend/optimizer/plan/planner.c
*** postgresql.orig/src/backend/optimizer/plan/planner.c	2010-10-08 11:04:23.000000000 +0200
--- postgresql.1/src/backend/optimizer/plan/planner.c	2010-10-26 13:52:08.000000000 +0200
*************** subquery_planner(PlannerGlobal *glob, Qu
*** 306,311 ****
--- 306,312 ----
  	root->init_plans = NIL;
  	root->cte_plan_ids = NIL;
  	root->eq_classes = NIL;
+ 	root->rb_canon_pathkeys = new_tree(pathkeys_comparator, root->planner_cxt);
  	root->append_rel_list = NIL;
  	root->rowMarks = NIL;
  	root->hasInheritedTarget = false;
diff -dcrpN postgresql.orig/src/backend/optimizer/prep/prepjointree.c postgresql.1/src/backend/optimizer/prep/prepjointree.c
*** postgresql.orig/src/backend/optimizer/prep/prepjointree.c	2010-09-21 13:49:57.000000000 +0200
--- postgresql.1/src/backend/optimizer/prep/prepjointree.c	2010-10-26 13:53:15.000000000 +0200
***************
*** 27,32 ****
--- 27,33 ----
  #include "nodes/nodeFuncs.h"
  #include "optimizer/clauses.h"
  #include "optimizer/placeholder.h"
+ #include "optimizer/paths.h"
  #include "optimizer/prep.h"
  #include "optimizer/subselect.h"
  #include "optimizer/tlist.h"
*************** pull_up_simple_subquery(PlannerInfo *roo
*** 627,632 ****
--- 628,634 ----
  	subroot->init_plans = NIL;
  	subroot->cte_plan_ids = NIL;
  	subroot->eq_classes = NIL;
+ 	subroot->rb_canon_pathkeys = new_tree(pathkeys_comparator, subroot->planner_cxt);
  	subroot->append_rel_list = NIL;
  	subroot->rowMarks = NIL;
  	subroot->hasRecursion = false;
diff -dcrpN postgresql.orig/src/include/nodes/nodes.h postgresql.1/src/include/nodes/nodes.h
*** postgresql.orig/src/include/nodes/nodes.h	2010-10-15 10:31:47.000000000 +0200
--- postgresql.1/src/include/nodes/nodes.h	2010-10-26 16:45:56.000000000 +0200
*************** typedef enum NodeTag
*** 256,261 ****
--- 256,266 ----
  	T_OidList,
  
  	/*
+ 	 * TAGS FOR TREE NODES (pg_tree.h)
+ 	 */
+ 	T_Tree,
+ 
+ 	/*
  	 * TAGS FOR STATEMENT NODES (mostly in parsenodes.h)
  	 */
  	T_Query = 700,
diff -dcrpN postgresql.orig/src/include/nodes/pg_tree.h postgresql.1/src/include/nodes/pg_tree.h
*** postgresql.orig/src/include/nodes/pg_tree.h	1970-01-01 01:00:00.000000000 +0100
--- postgresql.1/src/include/nodes/pg_tree.h	2010-10-19 11:50:31.000000000 +0200
***************
*** 0 ****
--- 1,60 ----
+ /*-------------------------------------------------------------------------
+  *
+  * pg_tree.h
+  *	  interface for PostgreSQL generic rbtree package
+  *
+  * This package implements rbtree of Node * elements of the same type.
+  * It is a replacement of List for dealing with O(n^2) behaviour
+  * found with long lists.
+  *
+  * Portions Copyright (c) 1996-2010, PostgreSQL Global Development Group
+  * Portions Copyright (c) 1994, Regents of the University of California
+  *
+  * $PostgreSQL$
+  *
+  *-------------------------------------------------------------------------
+  */
+ #ifndef PG_TREE_H
+ #define PG_TREE_H
+ 
+ #include "nodes/nodes.h"
+ #include "nodes/pg_list.h"
+ #include "utils/rbtree.h"
+ 
+ typedef struct TreeCell
+ {
+ 	RBNode		treenode;	/* base RBTree node, required by the rbtree.c code */
+ 	List	   *list;		/* multiple elements with the same key can be stored */
+ } TreeCell;
+ 
+ typedef struct Tree
+ {
+ 	NodeTag		type;		/* T_Tree */
+ 	int32		n_elems;	/* current number of stored elements */
+ 	MemoryContext	context;	/* context to allocate nodes and list elements in */
+ 	RBTree	   *tree;
+ } Tree;
+ 
+ 
+ extern Tree *new_tree(rb_comparator comparator, MemoryContext context);
+ extern List *tree_find(Tree *tree, Node *node);
+ extern void tree_add(Tree *tree, Node *node);
+ extern void tree_add_list(Tree *tree, List *list);
+ extern void tree_delete_ptr(Tree *tree, Node *node);
+ 
+ 
+ /*
+  * tforeach -
+  *	a convenience macro which loops through the tree elements
+  *	in "inorder" walk to make it look like a list
+  *
+  * WARNING WARNING WARNING
+  *
+  * Only one walk of the tree can be active at a time, it's the
+  * limitation of the current backend/utils/misc/rbtree.c code.
+  */
+ #define tforeach(tc, lc, t)	\
+ 	for (rb_begin_iterate(t->tree, LeftRightWalk) , (tc) = (TreeCell *)rb_iterate(t->tree); (tc); (tc) = (TreeCell *)rb_iterate(t->tree)) \
+ 	foreach (lc, tc->list)
+ 
+ #endif   /* PG_TREE_H */
diff -dcrpN postgresql.orig/src/include/nodes/primnodes.h postgresql.1/src/include/nodes/primnodes.h
*** postgresql.orig/src/include/nodes/primnodes.h	2010-09-21 13:49:59.000000000 +0200
--- postgresql.1/src/include/nodes/primnodes.h	2010-10-18 13:07:22.000000000 +0200
***************
*** 19,24 ****
--- 19,25 ----
  
  #include "access/attnum.h"
  #include "nodes/pg_list.h"
+ #include "nodes/pg_tree.h"
  
  
  /* ----------------------------------------------------------------
diff -dcrpN postgresql.orig/src/include/nodes/relation.h postgresql.1/src/include/nodes/relation.h
*** postgresql.orig/src/include/nodes/relation.h	2010-10-15 10:31:47.000000000 +0200
--- postgresql.1/src/include/nodes/relation.h	2010-10-26 13:44:14.000000000 +0200
*************** typedef struct PlannerInfo
*** 159,166 ****
  	List	   *cte_plan_ids;	/* per-CTE-item list of subplan IDs */
  
  	List	   *eq_classes;		/* list of active EquivalenceClasses */
  
! 	List	   *canon_pathkeys; /* list of "canonical" PathKeys */
  
  	List	   *left_join_clauses;		/* list of RestrictInfos for
  										 * mergejoinable outer join clauses
--- 159,167 ----
  	List	   *cte_plan_ids;	/* per-CTE-item list of subplan IDs */
  
  	List	   *eq_classes;		/* list of active EquivalenceClasses */
+ 	struct HTAB *eq_classes_hash;	/* optional hashtable for equivalence classes */
  
! 	Tree	   *rb_canon_pathkeys;	/* tree of "canonical" PathKeys */
  
  	List	   *left_join_clauses;		/* list of RestrictInfos for
  										 * mergejoinable outer join clauses
diff -dcrpN postgresql.orig/src/include/optimizer/paths.h postgresql.1/src/include/optimizer/paths.h
*** postgresql.orig/src/include/optimizer/paths.h	2010-09-21 13:49:59.000000000 +0200
--- postgresql.1/src/include/optimizer/paths.h	2010-10-26 16:46:45.000000000 +0200
***************
*** 15,20 ****
--- 15,21 ----
  #define PATHS_H
  
  #include "nodes/relation.h"
+ #include "utils/rbtree.h"
  
  
  /*
*************** typedef enum
*** 152,157 ****
--- 153,160 ----
  	PATHKEYS_DIFFERENT			/* neither pathkey includes the other */
  } PathKeysComparison;
  
+ extern int pathkeys_comparator(const RBNode *a, const RBNode *b, void *arg);
+ 
  extern List *canonicalize_pathkeys(PlannerInfo *root, List *pathkeys);
  extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
  extern bool pathkeys_contained_in(List *keys1, List *keys2);
Binary files postgresql.orig/src/test/regress/gmon.out and postgresql.1/src/test/regress/gmon.out differ
Binary files postgresql.orig/src/timezone/gmon.out and postgresql.1/src/timezone/gmon.out differ