From e3b9852728902bc816bf02574a87eda9a0ca91a1 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Tue, 20 Dec 2005 02:30:36 +0000 Subject: Teach planner how to rearrange join order for some classes of OUTER JOIN. Per my recent proposal. I ended up basing the implementation on the existing mechanism for enforcing valid join orders of IN joins --- the rules for valid outer-join orders are somewhat similar. --- src/include/nodes/nodes.h | 3 ++- src/include/nodes/primnodes.h | 9 ++------ src/include/nodes/relation.h | 47 +++++++++++++++++++++++++++++++--------- src/include/optimizer/clauses.h | 3 ++- src/include/optimizer/paths.h | 9 +++----- src/include/optimizer/planmain.h | 8 ++++--- src/include/optimizer/prep.h | 6 +---- 7 files changed, 52 insertions(+), 33 deletions(-) (limited to 'src/include') diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index e9ec4b8ad65..0d6a4871ac2 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.178 2005/11/22 18:17:30 momjian Exp $ + * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.179 2005/12/20 02:30:36 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -186,6 +186,7 @@ typedef enum NodeTag T_PathKeyItem, T_RestrictInfo, T_InnerIndexscanInfo, + T_OuterJoinInfo, T_InClauseInfo, /* diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h index 1cdd64b26eb..40fda441b97 100644 --- a/src/include/nodes/primnodes.h +++ b/src/include/nodes/primnodes.h @@ -10,7 +10,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/primnodes.h,v 1.109 2005/10/15 02:49:45 momjian Exp $ + * $PostgreSQL: pgsql/src/include/nodes/primnodes.h,v 1.110 2005/12/20 02:30:36 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -845,12 +845,7 @@ typedef struct TargetEntry * or qualified join. Also, FromExpr nodes can appear to denote an * ordinary cross-product join ("FROM foo, bar, baz WHERE ..."). * FromExpr is like a JoinExpr of jointype JOIN_INNER, except that it - * may have any number of child nodes, not just two. Also, there is an - * implementation-defined difference: the planner is allowed to join the - * children of a FromExpr using whatever join order seems good to it. - * At present, JoinExpr nodes are always joined in exactly the order - * implied by the jointree structure (except the planner may choose to - * swap inner and outer members of a join pair). + * may have any number of child nodes, not just two. * * NOTE: the top level of a Query's jointree is always a FromExpr. * Even if the jointree contains no rels, there will be a FromExpr. diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index aa6217d0313..1d490fc17bf 100644 --- a/src/include/nodes/relation.h +++ b/src/include/nodes/relation.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.121 2005/11/26 22:14:57 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.122 2005/12/20 02:30:36 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -97,6 +97,8 @@ typedef struct PlannerInfo List *full_join_clauses; /* list of RestrictInfos for full * outer join clauses */ + List *oj_info_list; /* list of OuterJoinInfos */ + List *in_info_list; /* list of InClauseInfos */ List *query_pathkeys; /* desired pathkeys for query_planner(), and @@ -201,10 +203,6 @@ typedef struct PlannerInfo * participates (only used for base rels) * baserestrictcost - Estimated cost of evaluating the baserestrictinfo * clauses at a single tuple (only used for base rels) - * outerjoinset - For a base rel: if the rel appears within the nullable - * side of an outer join, the set of all relids - * participating in the highest such outer join; else NULL. - * Otherwise, unused. * joininfo - List of RestrictInfo nodes, containing info about each * join clause in which this relation participates * index_outer_relids - only used for base rels; set of outer relids @@ -228,10 +226,6 @@ typedef struct PlannerInfo * We store baserestrictcost in the RelOptInfo (for base relations) because * we know we will need it at least once (to price the sequential scan) * and may need it multiple times to price index scans. - * - * outerjoinset is used to ensure correct placement of WHERE clauses that - * apply to outer-joined relations; we must not apply such WHERE clauses - * until after the outer join is performed. *---------- */ typedef enum RelOptKind @@ -277,7 +271,6 @@ typedef struct RelOptInfo List *baserestrictinfo; /* RestrictInfo structures (if base * rel) */ QualCost baserestrictcost; /* cost of evaluating the above */ - Relids outerjoinset; /* set of base relids */ List *joininfo; /* RestrictInfo structures for join clauses * involving this rel */ @@ -830,6 +823,40 @@ typedef struct InnerIndexscanInfo Path *best_innerpath; /* best inner indexscan, or NULL if none */ } InnerIndexscanInfo; +/* + * Outer join info. + * + * One-sided outer joins constrain the order of joining partially but not + * completely. We flatten such joins into the planner's top-level list of + * relations to join, but record information about each outer join in an + * OuterJoinInfo struct. These structs are kept in the PlannerInfo node's + * oj_info_list. + * + * min_lefthand and min_righthand are the sets of base relids that must be + * available on each side when performing the outer join. lhs_strict is + * true if the outer join's condition cannot succeed when the LHS variables + * are all NULL (this means that the outer join can commute with upper-level + * outer joins even if it appears in their RHS). We don't bother to set + * lhs_strict for FULL JOINs, however. + * + * It is not valid for either min_lefthand or min_righthand to be empty sets; + * if they were, this would break the logic that enforces join order. + * + * Note: OuterJoinInfo directly represents only LEFT JOIN and FULL JOIN; + * RIGHT JOIN is handled by switching the inputs to make it a LEFT JOIN. + * We make an OuterJoinInfo for FULL JOINs even though there is no flexibility + * of planning for them, because this simplifies make_join_rel()'s API. + */ + +typedef struct OuterJoinInfo +{ + NodeTag type; + Relids min_lefthand; /* base relids in minimum LHS for join */ + Relids min_righthand; /* base relids in minimum RHS for join */ + bool is_full_join; /* it's a FULL OUTER JOIN */ + bool lhs_strict; /* joinclause is strict for some LHS rel */ +} OuterJoinInfo; + /* * IN clause info. * diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h index bf00f2cc97e..0d3770dc5c4 100644 --- a/src/include/optimizer/clauses.h +++ b/src/include/optimizer/clauses.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/clauses.h,v 1.80 2005/10/15 02:49:45 momjian Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/clauses.h,v 1.81 2005/12/20 02:30:36 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -57,6 +57,7 @@ extern bool contain_subplans(Node *clause); extern bool contain_mutable_functions(Node *clause); extern bool contain_volatile_functions(Node *clause); extern bool contain_nonstrict_functions(Node *clause); +extern Relids find_nonnullable_rels(Node *clause); extern bool is_pseudo_constant_clause(Node *clause); extern bool is_pseudo_constant_clause_relids(Node *clause, Relids relids); diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index eba65c699c0..afe3a70d71b 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.89 2005/11/25 19:47:50 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.90 2005/12/20 02:30:36 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -23,8 +23,7 @@ extern bool enable_geqo; extern int geqo_threshold; -extern RelOptInfo *make_one_rel(PlannerInfo *root); -extern RelOptInfo *make_fromexpr_rel(PlannerInfo *root, FromExpr *from); +extern RelOptInfo *make_one_rel(PlannerInfo *root, List *joinlist); #ifdef OPTIMIZER_DEBUG extern void debug_print_rel(PlannerInfo *root, RelOptInfo *rel); @@ -88,10 +87,8 @@ extern void add_paths_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, * routines to determine which relations to join */ extern List *make_rels_by_joins(PlannerInfo *root, int level, List **joinrels); -extern RelOptInfo *make_jointree_rel(PlannerInfo *root, Node *jtnode); extern RelOptInfo *make_join_rel(PlannerInfo *root, - RelOptInfo *rel1, RelOptInfo *rel2, - JoinType jointype); + RelOptInfo *rel1, RelOptInfo *rel2); /* * pathkeys.c diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h index 0e78933f792..97d2287b5c8 100644 --- a/src/include/optimizer/planmain.h +++ b/src/include/optimizer/planmain.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/planmain.h,v 1.90 2005/10/15 02:49:45 momjian Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/planmain.h,v 1.91 2005/12/20 02:30:36 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -65,10 +65,12 @@ extern bool is_projection_capable_plan(Plan *plan); /* * prototypes for plan/initsplan.c */ +extern int from_collapse_limit; +extern int join_collapse_limit; + extern void add_base_rels_to_query(PlannerInfo *root, Node *jtnode); extern void build_base_rel_tlists(PlannerInfo *root, List *final_tlist); -extern Relids distribute_quals_to_rels(PlannerInfo *root, Node *jtnode, - bool below_outer_join); +extern List *deconstruct_jointree(PlannerInfo *root); extern void process_implied_equality(PlannerInfo *root, Node *item1, Node *item2, Oid sortop1, Oid sortop2, diff --git a/src/include/optimizer/prep.h b/src/include/optimizer/prep.h index c26e6491f34..ce89771b179 100644 --- a/src/include/optimizer/prep.h +++ b/src/include/optimizer/prep.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/prep.h,v 1.52 2005/10/15 02:49:45 momjian Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/prep.h,v 1.53 2005/12/20 02:30:36 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -21,14 +21,10 @@ /* * prototypes for prepjointree.c */ -extern int from_collapse_limit; -extern int join_collapse_limit; - extern Node *pull_up_IN_clauses(PlannerInfo *root, Node *node); extern Node *pull_up_subqueries(PlannerInfo *root, Node *jtnode, bool below_outer_join); extern void reduce_outer_joins(PlannerInfo *root); -extern Node *simplify_jointree(PlannerInfo *root, Node *jtnode); extern Relids get_relids_in_jointree(Node *jtnode); extern Relids get_relids_for_join(PlannerInfo *root, int joinrelid); -- cgit v1.2.3