Index: src/backend/optimizer/path/joinpath.c =================================================================== RCS file: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v retrieving revision 1.131 diff -c -r1.131 joinpath.c *** src/backend/optimizer/path/joinpath.c 22 Mar 2010 13:57:15 -0000 1.131 --- src/backend/optimizer/path/joinpath.c 28 Mar 2010 03:50:58 -0000 *************** *** 22,32 **** #include "optimizer/paths.h" - static bool join_is_removable(PlannerInfo *root, RelOptInfo *joinrel, - RelOptInfo *outerrel, RelOptInfo *innerrel, - List *restrictlist, JoinType jointype); - static void generate_outer_only(PlannerInfo *root, RelOptInfo *joinrel, - RelOptInfo *outerrel); static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, List *mergeclause_list, --- 22,27 ---- *************** *** 84,109 **** List *mergeclause_list = NIL; /* - * 0. Consider join removal. This is always the most efficient strategy, - * so if it works, there's no need to consider anything further. - */ - if (join_is_removable(root, joinrel, outerrel, innerrel, - restrictlist, jointype)) - { - generate_outer_only(root, joinrel, outerrel); - return; - } - - /* * Find potential mergejoin clauses. We can skip this if we are not * interested in doing a mergejoin. However, mergejoin is currently our * only way of implementing full outer joins, so override mergejoin * disable if it's a full join. - * - * Note: do this after join_is_removable(), because this sets the - * outer_is_left flags in the mergejoin clauses, while join_is_removable - * uses those flags for its own purposes. Currently, they set the flags - * the same way anyway, but let's avoid unnecessary entanglement. */ if (enable_mergejoin || jointype == JOIN_FULL) mergeclause_list = select_mergejoin_clauses(root, --- 79,88 ---- *************** *** 165,182 **** * we set the transient flag outer_is_left to identify which side is which. */ static inline bool ! clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel, ! RelOptInfo *innerrel) { ! if (bms_is_subset(rinfo->left_relids, outerrel->relids) && ! bms_is_subset(rinfo->right_relids, innerrel->relids)) { /* lefthand side is outer */ rinfo->outer_is_left = true; return true; } ! else if (bms_is_subset(rinfo->left_relids, innerrel->relids) && ! bms_is_subset(rinfo->right_relids, outerrel->relids)) { /* righthand side is outer */ rinfo->outer_is_left = false; --- 144,161 ---- * we set the transient flag outer_is_left to identify which side is which. */ static inline bool ! clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids, ! Relids innerrelids) { ! if (bms_is_subset(rinfo->left_relids, outerrelids) && ! bms_is_subset(rinfo->right_relids, innerrelids)) { /* lefthand side is outer */ rinfo->outer_is_left = true; return true; } ! else if (bms_is_subset(rinfo->left_relids, innerrelids) && ! bms_is_subset(rinfo->right_relids, outerrelids)) { /* righthand side is outer */ rinfo->outer_is_left = false; *************** *** 187,193 **** /* * join_is_removable ! * Determine whether we need not perform the join at all, because * it will just duplicate its left input. * * This is true for a left join for which the join condition cannot match --- 166,172 ---- /* * join_is_removable ! * Determine whether we need not perform a special join at all, because * it will just duplicate its left input. * * This is true for a left join for which the join condition cannot match *************** *** 195,213 **** * cases, but we don't have the infrastructure to prove them.) We also * have to check that the inner side doesn't generate any variables needed * above the join. - * - * Note: there is no need to consider the symmetrical case of duplicating the - * right input, because add_paths_to_joinrel() will be called with each rel - * on the outer side. */ ! static bool ! join_is_removable(PlannerInfo *root, ! RelOptInfo *joinrel, ! RelOptInfo *outerrel, ! RelOptInfo *innerrel, ! List *restrictlist, ! JoinType jointype) { List *clause_list = NIL; ListCell *l; int attroff; --- 174,186 ---- * cases, but we don't have the infrastructure to prove them.) We also * have to check that the inner side doesn't generate any variables needed * above the join. */ ! bool ! join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo) { + int innerrelid; + RelOptInfo *innerrel; + Relids joinrelids; List *clause_list = NIL; ListCell *l; int attroff; *************** *** 220,227 **** * now we just make sure there are indexes of some sort or other. If none * of them are unique, join removal will still fail, just slightly later. */ ! if (jointype != JOIN_LEFT || ! innerrel->reloptkind == RELOPT_JOINREL || innerrel->rtekind != RTE_RELATION || innerrel->indexlist == NIL) return false; --- 193,207 ---- * now we just make sure there are indexes of some sort or other. If none * of them are unique, join removal will still fail, just slightly later. */ ! if (sjinfo->jointype != JOIN_LEFT || ! sjinfo->delay_upper_joins || ! bms_membership(sjinfo->min_righthand) != BMS_SINGLETON) ! return false; ! ! innerrelid = bms_singleton_member(sjinfo->min_righthand); ! innerrel = find_base_rel(root, innerrelid); ! ! if (innerrel->reloptkind != RELOPT_BASEREL || innerrel->rtekind != RTE_RELATION || innerrel->indexlist == NIL) return false; *************** *** 239,249 **** * theory that the system attributes are somewhat less likely to be wanted * and should be tested last. */ for (attroff = innerrel->max_attr - innerrel->min_attr; attroff >= 0; attroff--) { ! if (!bms_is_subset(innerrel->attr_needed[attroff], joinrel->relids)) return false; } --- 219,231 ---- * theory that the system attributes are somewhat less likely to be wanted * and should be tested last. */ + joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); + for (attroff = innerrel->max_attr - innerrel->min_attr; attroff >= 0; attroff--) { ! if (!bms_is_subset(innerrel->attr_needed[attroff], joinrelids)) return false; } *************** *** 256,262 **** PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l); if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids) && ! !bms_is_subset(phinfo->ph_needed, joinrel->relids)) return false; } --- 238,244 ---- PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l); if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids) && ! !bms_is_subset(phinfo->ph_needed, joinrelids)) return false; } *************** *** 267,282 **** * it's what we want. The mergejoinability test also eliminates clauses * containing volatile functions, which we couldn't depend on. */ ! foreach(l, restrictlist) { RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l); /* * If we find a pushed-down clause, it must have come from above the * outer join and it must contain references to the inner rel. (If it * had only outer-rel variables, it'd have been pushed down into the * outer rel.) Therefore, we can conclude that join removal is unsafe * without any examination of the clause contents. */ if (restrictinfo->is_pushed_down) return false; --- 249,270 ---- * it's what we want. The mergejoinability test also eliminates clauses * containing volatile functions, which we couldn't depend on. */ ! foreach(l, innerrel->joininfo) { RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l); + /* Ignore clauses not pertinent to this join */ + if (!bms_is_subset(restrictinfo->required_relids, joinrelids)) + continue; + /* * If we find a pushed-down clause, it must have come from above the * outer join and it must contain references to the inner rel. (If it * had only outer-rel variables, it'd have been pushed down into the * outer rel.) Therefore, we can conclude that join removal is unsafe * without any examination of the clause contents. + * + * XXX still appropriate? */ if (restrictinfo->is_pushed_down) return false; *************** *** 289,295 **** /* * Check if clause has the form "outer op inner" or "inner op outer". */ ! if (!clause_sides_match_join(restrictinfo, outerrel, innerrel)) continue; /* no good for these input relations */ /* OK, add to list */ --- 277,284 ---- /* * Check if clause has the form "outer op inner" or "inner op outer". */ ! if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand, ! innerrel->relids)) continue; /* no good for these input relations */ /* OK, add to list */ *************** *** 1031,1037 **** /* * Check if clause has the form "outer op inner" or "inner op outer". */ ! if (!clause_sides_match_join(restrictinfo, outerrel, innerrel)) continue; /* no good for these input relations */ hashclauses = lappend(hashclauses, restrictinfo); --- 1020,1027 ---- /* * Check if clause has the form "outer op inner" or "inner op outer". */ ! if (!clause_sides_match_join(restrictinfo, outerrel->relids, ! innerrel->relids)) continue; /* no good for these input relations */ hashclauses = lappend(hashclauses, restrictinfo); *************** *** 1216,1222 **** /* * Check if clause has the form "outer op inner" or "inner op outer". */ ! if (!clause_sides_match_join(restrictinfo, outerrel, innerrel)) { have_nonmergeable_joinclause = true; continue; /* no good for these input relations */ --- 1206,1213 ---- /* * Check if clause has the form "outer op inner" or "inner op outer". */ ! if (!clause_sides_match_join(restrictinfo, outerrel->relids, ! innerrel->relids)) { have_nonmergeable_joinclause = true; continue; /* no good for these input relations */ Index: src/backend/optimizer/plan/planmain.c =================================================================== RCS file: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v retrieving revision 1.117 diff -c -r1.117 planmain.c *** src/backend/optimizer/plan/planmain.c 2 Jan 2010 16:57:47 -0000 1.117 --- src/backend/optimizer/plan/planmain.c 28 Mar 2010 03:50:58 -0000 *************** *** 29,34 **** --- 29,37 ---- #include "utils/selfuncs.h" + static List *remove_useless_joins(PlannerInfo *root, List *joinlist); + + /* * query_planner * Generate a path (that is, a simplified plan) for a basic query, *************** *** 249,254 **** --- 252,264 ---- fix_placeholder_eval_levels(root); /* + * Remove any useless outer joins. Ideally this would be done during + * jointree preprocessing, but the necessary information isn't available + * until now. + */ + joinlist = remove_useless_joins(root, joinlist); + + /* * Ready to do the primary planning. */ final_rel = make_one_rel(root, joinlist); *************** *** 404,406 **** --- 414,579 ---- *cheapest_path = cheapestpath; *sorted_path = sortedpath; } + + extern bool + join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo); + static void + remove_rel_from_query(PlannerInfo *root, int relid); + static List * + remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved); + + static List * + remove_useless_joins(PlannerInfo *root, List *joinlist) + { + ListCell *lc; + + restart: + foreach(lc, root->join_info_list) + { + SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc); + int innerrelid; + int nremoved; + + if (!join_is_removable(root, sjinfo)) + continue; + + /* + * Currently, join_is_removable can only succeed when the sjinfo's + * righthand is a single baserel. Remove that rel from the joinlist. + */ + innerrelid = bms_singleton_member(sjinfo->min_righthand); + + remove_rel_from_query(root, innerrelid); + + nremoved = 0; + joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved); + if (nremoved != 1) + elog(ERROR, "failed to find relation %d in joinlist", innerrelid); + + /* + * We can delete this SpecialJoinInfo too, since it's no longer of + * interest. + */ + root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo); + + /* + * Restart the scan. This is necessary to ensure we find all removable + * joins independently of ordering of the join_info_list (note that + * removal of attr_needed bits may make a join appear removable that + * did not before). Also, since we just deleted the current list + * cell, we'd have to have some hack to continue the list search + * anyway. + */ + goto restart; + } + + return joinlist; + } + + /* + * Remove the target relid from the planner's data structures. + * + * We are not terribly thorough here. We must make sure that the rel is + * no longer visible as a baserel, and that attributes of other baserels + * are no longer marked as being needed at joins involving this rel. + * We don't have to bother removing join quals involving the rel from the + * joininfo lists; they'll just get ignored since we will never form a + * join relation that appears to match them. + */ + static void + remove_rel_from_query(PlannerInfo *root, int relid) + { + RelOptInfo *rel = find_base_rel(root, relid); + Index rti; + ListCell *l; + + /* + * Mark the rel as an "other" rel instead of a "base" rel, since it + * is no longer part of the join tree. (Could we remove it from + * the baserel array altogether? Or use a dedicated reloptkind?) + */ + rel->reloptkind = RELOPT_OTHER_MEMBER_REL; + + /* + * Remove references to the rel from other baserels' attr_needed arrays. + */ + for (rti = 1; rti < root->simple_rel_array_size; rti++) + { + RelOptInfo *otherrel = root->simple_rel_array[rti]; + int attroff; + + /* there may be empty slots corresponding to non-baserel RTEs */ + if (otherrel == NULL) + continue; + + Assert(otherrel->relid == rti); /* sanity check on array */ + + for (attroff = otherrel->max_attr - otherrel->min_attr; + attroff >= 0; + attroff--) + { + otherrel->attr_needed[attroff] = + bms_del_member(otherrel->attr_needed[attroff], relid); + } + } + + /* + * Likewise remove references from PlaceHolderVar data structures. + */ + foreach(l, root->placeholder_list) + { + PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l); + + phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid); + phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid); + } + } + + /* + * Remove any occurrences of the target relid from a joinlist structure. + * + * It's easiest to build a whole new list structure, so we handle it that + * way. Efficiency is not a big deal here. + * + * *nremoved is incremented by the number of occurrences removed (there + * should be exactly one, but the caller checks that). + */ + static List * + remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved) + { + List *result = NIL; + ListCell *jl; + + foreach(jl, joinlist) + { + Node *jlnode = (Node *) lfirst(jl); + + if (IsA(jlnode, RangeTblRef)) + { + int varno = ((RangeTblRef *) jlnode)->rtindex; + + if (varno == relid) + (*nremoved)++; + else + result = lappend(result, jlnode); + } + else if (IsA(jlnode, List)) + { + /* Recurse to handle subproblem */ + List *sublist; + + sublist = remove_rel_from_joinlist((List *) jlnode, + relid, nremoved); + /* Avoid including empty sub-lists in the result */ + if (sublist) + result = lappend(result, sublist); + } + else + { + elog(ERROR, "unrecognized joinlist node type: %d", + (int) nodeTag(jlnode)); + } + } + + return result; + } Index: src/test/regress/expected/join.out =================================================================== RCS file: /cvsroot/pgsql/src/test/regress/expected/join.out,v retrieving revision 1.44 diff -c -r1.44 join.out *** src/test/regress/expected/join.out 22 Mar 2010 13:57:16 -0000 1.44 --- src/test/regress/expected/join.out 28 Mar 2010 03:50:59 -0000 *************** *** 2494,2499 **** --- 2494,2531 ---- -- -- test join removal -- + begin; + CREATE TEMP TABLE a (id int PRIMARY KEY, b_id int); + NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "a_pkey" for table "a" + CREATE TEMP TABLE b (id int PRIMARY KEY, c_id int); + NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "b_pkey" for table "b" + CREATE TEMP TABLE c (id int PRIMARY KEY); + NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "c_pkey" for table "c" + INSERT INTO a VALUES (0, 0), (1, NULL); + INSERT INTO b VALUES (0, 0), (1, NULL); + INSERT INTO c VALUES (0), (1); + -- all three cases should be optimizable into a simple seqscan + explain (costs off) SELECT a.* FROM a LEFT JOIN b ON a.b_id = b.id; + QUERY PLAN + --------------- + Seq Scan on a + (1 row) + + explain (costs off) SELECT b.* FROM b LEFT JOIN c ON b.c_id = c.id; + QUERY PLAN + --------------- + Seq Scan on b + (1 row) + + explain (costs off) + SELECT a.* FROM a LEFT JOIN (b left join c on b.c_id = c.id) + ON (a.b_id = b.id); + QUERY PLAN + --------------- + Seq Scan on a + (1 row) + + rollback; create temp table parent (k int primary key, pd int); NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "parent_pkey" for table "parent" create temp table child (k int unique, cd int); *************** *** 2540,2542 **** --- 2572,2595 ---- -> Seq Scan on child c (5 rows) + -- bug 5255: this is not optimizable by join removal + begin; + CREATE TEMP TABLE a (id int PRIMARY KEY); + NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "a_pkey" for table "a" + CREATE TEMP TABLE b (id int PRIMARY KEY, a_id int); + NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "b_pkey" for table "b" + INSERT INTO a VALUES (0), (1); + INSERT INTO b VALUES (0, 0), (1, NULL); + SELECT * FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0); + id | a_id | id + ----+------+---- + 1 | | + (1 row) + + SELECT b.* FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0); + id | a_id + ----+------ + 1 | + (1 row) + + rollback; Index: src/test/regress/sql/join.sql =================================================================== RCS file: /cvsroot/pgsql/src/test/regress/sql/join.sql,v retrieving revision 1.33 diff -c -r1.33 join.sql *** src/test/regress/sql/join.sql 22 Mar 2010 13:57:16 -0000 1.33 --- src/test/regress/sql/join.sql 28 Mar 2010 03:50:59 -0000 *************** *** 572,577 **** --- 572,595 ---- -- test join removal -- + begin; + + CREATE TEMP TABLE a (id int PRIMARY KEY, b_id int); + CREATE TEMP TABLE b (id int PRIMARY KEY, c_id int); + CREATE TEMP TABLE c (id int PRIMARY KEY); + INSERT INTO a VALUES (0, 0), (1, NULL); + INSERT INTO b VALUES (0, 0), (1, NULL); + INSERT INTO c VALUES (0), (1); + + -- all three cases should be optimizable into a simple seqscan + explain (costs off) SELECT a.* FROM a LEFT JOIN b ON a.b_id = b.id; + explain (costs off) SELECT b.* FROM b LEFT JOIN c ON b.c_id = c.id; + explain (costs off) + SELECT a.* FROM a LEFT JOIN (b left join c on b.c_id = c.id) + ON (a.b_id = b.id); + + rollback; + create temp table parent (k int primary key, pd int); create temp table child (k int unique, cd int); insert into parent values (1, 10), (2, 20), (3, 30); *************** *** 590,592 **** --- 608,623 ---- select p.*, linked from parent p left join (select c.*, true as linked from child c) as ss on (p.k = ss.k); + + -- bug 5255: this is not optimizable by join removal + begin; + + CREATE TEMP TABLE a (id int PRIMARY KEY); + CREATE TEMP TABLE b (id int PRIMARY KEY, a_id int); + INSERT INTO a VALUES (0), (1); + INSERT INTO b VALUES (0, 0), (1, NULL); + + SELECT * FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0); + SELECT b.* FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0); + + rollback;