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