diff options
Diffstat (limited to 'src/include')
| -rw-r--r-- | src/include/nodes/relation.h | 54 | ||||
| -rw-r--r-- | src/include/optimizer/cost.h | 10 | ||||
| -rw-r--r-- | src/include/optimizer/pathnode.h | 31 | ||||
| -rw-r--r-- | src/include/optimizer/paths.h | 43 |
4 files changed, 87 insertions, 51 deletions
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index 99254740e78..529aa5cea7a 100644 --- a/src/include/nodes/relation.h +++ b/src/include/nodes/relation.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2000, PostgreSQL, Inc * Portions Copyright (c) 1994, Regents of the University of California * - * $Id: relation.h,v 1.42 2000/01/26 05:58:17 momjian Exp $ + * $Id: relation.h,v 1.43 2000/02/07 04:41:02 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -54,13 +54,26 @@ typedef List *Relids; * * The presence of the remaining fields depends on the restrictions * and joins that the relation participates in: * - * restrictinfo - List of RestrictInfo nodes, containing info about each - * qualification clause in which this relation participates + * baserestrictinfo - List of RestrictInfo nodes, containing info about + * each qualification clause in which this relation + * participates (only used for base rels) * joininfo - List of JoinInfo nodes, containing info about each join * clause in which this relation participates * innerjoin - List of Path nodes that represent indices that may be used * as inner paths of nestloop joins. This field is non-null * only for base rels, since join rels have no indices. + * + * Note: Keeping a restrictinfo list in the RelOptInfo is useful only for + * base rels, because for a join rel the set of clauses that are treated as + * restrict clauses varies depending on which sub-relations we choose to join. + * (For example, in a 3-base-rel join, a clause relating rels 1 and 2 must be + * treated as a restrictclause if we join {1} and {2 3} to make {1 2 3}; but + * if we join {1 2} and {3} then that clause will be a restrictclause in {1 2} + * and should not be processed again at the level of {1 2 3}.) Therefore, + * the restrictinfo list in the join case appears in individual JoinPaths + * (field joinrestrictinfo), not in the parent relation. But it's OK for + * the RelOptInfo to store the joininfo lists, because those are the same + * for a given rel no matter how we form it. */ typedef struct RelOptInfo @@ -86,7 +99,7 @@ typedef struct RelOptInfo double tuples; /* used by various scans and joins: */ - List *restrictinfo; /* RestrictInfo structures */ + List *baserestrictinfo; /* RestrictInfo structures (if base rel) */ List *joininfo; /* JoinInfo structures */ List *innerjoin; /* potential indexscans for nestloop joins */ /* innerjoin indexscans are not in the main pathlist because they are @@ -235,6 +248,10 @@ typedef struct JoinPath Path *outerjoinpath; /* path for the outer side of the join */ Path *innerjoinpath; /* path for the inner side of the join */ + List *joinrestrictinfo; /* RestrictInfos to apply to join */ + /* See the notes for RelOptInfo to understand why joinrestrictinfo is + * needed in JoinPath, and can't be merged into the parent RelOptInfo. + */ } JoinPath; /* @@ -289,18 +306,29 @@ typedef struct HashPath * without having to evaluate the rest. The RestrictInfo node itself stores * data used by the optimizer while choosing the best query plan. * - * A restriction clause will appear in the restrictinfo list of a RelOptInfo - * that describes exactly the set of base relations referenced by the - * restriction clause. It is not possible to apply the clause at any lower - * nesting level, and there is little point in delaying its evaluation to - * higher nesting levels. (The "predicate migration" code was once intended - * to push restriction clauses up and down the plan tree, but it's dead code - * and is unlikely to be resurrected in the foreseeable future.) + * If a restriction clause references a single base relation, it will appear + * in the baserestrictinfo list of the RelOptInfo for that base rel. * - * If a restriction clause references more than one base rel, it will also - * appear in the JoinInfo list of every RelOptInfo that describes a strict + * If a restriction clause references more than one base rel, it will + * appear in the JoinInfo lists of every RelOptInfo that describes a strict * subset of the base rels mentioned in the clause. The JoinInfo lists are * used to drive join tree building by selecting plausible join candidates. + * The clause cannot actually be applied until we have built a join rel + * containing all the base rels it references, however. + * + * When we construct a join rel that describes exactly the set of base rels + * referenced in a multi-relation restriction clause, we place that clause + * into the joinrestrictinfo lists of paths for the join rel. It will be + * applied at that join level, and will not propagate any further up the + * join tree. (Note: the "predicate migration" code was once intended to + * push restriction clauses up and down the plan tree based on evaluation + * costs, but it's dead code and is unlikely to be resurrected in the + * foreseeable future.) + * + * Note that in the presence of more than two rels, a multi-rel restriction + * might reach different heights in the join tree depending on the join + * sequence we use. So, these clauses cannot be associated directly with + * the join RelOptInfo, but must be kept track of on a per-join-path basis. * * In general, the referenced clause might be arbitrarily complex. The * kinds of clauses we can handle as indexscan quals, mergejoin clauses, diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index 0a6e78d676c..79153c01d83 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2000, PostgreSQL, Inc * Portions Copyright (c) 1994, Regents of the University of California * - * $Id: cost.h,v 1.28 2000/01/26 05:58:20 momjian Exp $ + * $Id: cost.h,v 1.29 2000/02/07 04:41:04 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -55,9 +55,11 @@ extern Cost cost_mergejoin(Path *outer_path, Path *inner_path, List *outersortkeys, List *innersortkeys); extern Cost cost_hashjoin(Path *outer_path, Path *inner_path, Selectivity innerdisbursion); -extern void set_rel_rows_width(Query *root, RelOptInfo *rel); -extern void set_joinrel_rows_width(Query *root, RelOptInfo *rel, - JoinPath *joinpath); +extern void set_baserel_size_estimates(Query *root, RelOptInfo *rel); +extern void set_joinrel_size_estimates(Query *root, RelOptInfo *rel, + RelOptInfo *outer_rel, + RelOptInfo *inner_rel, + List *restrictlist); /* * prototypes for clausesel.c diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index a83e743781b..eefb2553b3d 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2000, PostgreSQL, Inc * Portions Copyright (c) 1994, Regents of the University of California * - * $Id: pathnode.h,v 1.24 2000/01/26 05:58:20 momjian Exp $ + * $Id: pathnode.h,v 1.25 2000/02/07 04:41:04 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -21,8 +21,8 @@ */ extern bool path_is_cheaper(Path *path1, Path *path2); extern Path *set_cheapest(RelOptInfo *parent_rel, List *pathlist); -extern List *add_pathlist(RelOptInfo *parent_rel, List *old_paths, - List *new_paths); +extern void add_path(RelOptInfo *parent_rel, Path *new_path); +extern void add_pathlist(RelOptInfo *parent_rel, List *new_paths); extern Path *create_seqscan_path(RelOptInfo *rel); extern IndexPath *create_index_path(Query *root, RelOptInfo *rel, @@ -31,25 +31,34 @@ extern IndexPath *create_index_path(Query *root, RelOptInfo *rel, extern TidPath *create_tidscan_path(RelOptInfo *rel, List *tideval); extern NestPath *create_nestloop_path(RelOptInfo *joinrel, - Path *outer_path, Path *inner_path, + Path *outer_path, + Path *inner_path, + List *restrict_clauses, List *pathkeys); -extern MergePath *create_mergejoin_path(RelOptInfo *joinrel, Path *outer_path, - Path *inner_path, List *pathkeys, +extern MergePath *create_mergejoin_path(RelOptInfo *joinrel, + Path *outer_path, + Path *inner_path, + List *restrict_clauses, + List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys); -extern HashPath *create_hashjoin_path(RelOptInfo *joinrel, Path *outer_path, - Path *inner_path, List *hashclauses, +extern HashPath *create_hashjoin_path(RelOptInfo *joinrel, + Path *outer_path, + Path *inner_path, + List *restrict_clauses, + List *hashclauses, Selectivity innerdisbursion); /* - * prototypes for rel.c + * prototypes for relnode.c */ -extern RelOptInfo *rel_member(Relids relid, List *rels); extern RelOptInfo *get_base_rel(Query *root, int relid); -extern RelOptInfo *get_join_rel(Query *root, Relids relid); +extern RelOptInfo *get_join_rel(Query *root, RelOptInfo *outer_rel, + RelOptInfo *inner_rel, + List **restrictlist_ptr); /* * prototypes for indexnode.h diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index bcecd4c923c..256aac90d75 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -8,7 +8,7 @@ * Portions Copyright (c) 1996-2000, PostgreSQL, Inc * Portions Copyright (c) 1994, Regents of the University of California * - * $Id: paths.h,v 1.41 2000/02/06 03:27:35 tgl Exp $ + * $Id: paths.h,v 1.42 2000/02/07 04:41:04 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -27,15 +27,15 @@ extern bool enable_geqo; extern int geqo_rels; -extern RelOptInfo *make_one_rel(Query *root, List *rels); +extern RelOptInfo *make_one_rel(Query *root); /* * indxpath.c * routines to generate index paths */ extern List *create_index_paths(Query *root, RelOptInfo *rel, List *indices, - List *restrictinfo_list, - List *joininfo_list); + List *restrictinfo_list, + List *joininfo_list); extern Oid indexable_operator(Expr *clause, Oid opclass, Oid relam, bool indexkey_on_left); extern List *extract_or_indexqual_conditions(RelOptInfo *rel, @@ -60,7 +60,22 @@ extern List *create_tidscan_paths(Query *root, RelOptInfo *rel); * joinpath.c * routines to create join paths */ -extern void update_rels_pathlist_for_joins(Query *root, List *joinrels); +extern void add_paths_to_joinrel(Query *root, RelOptInfo *joinrel, + RelOptInfo *outerrel, + RelOptInfo *innerrel, + List *restrictlist); + +/* + * joinrels.c + * routines to determine which relations to join + */ +extern void make_rels_by_joins(Query *root, int level); +extern RelOptInfo *make_rels_by_clause_joins(Query *root, + RelOptInfo *old_rel, + List *other_rels); +extern RelOptInfo *make_rels_by_clauseless_joins(Query *root, + RelOptInfo *old_rel, + List *other_rels); /* * pathkeys.c @@ -90,22 +105,4 @@ extern List *find_mergeclauses_for_pathkeys(List *pathkeys, extern List *make_pathkeys_for_mergeclauses(List *mergeclauses, List *tlist); -/* - * joinrels.c - * routines to determine which relations to join - */ -extern List *make_rels_by_joins(Query *root, List *old_rels); -extern List *make_rels_by_clause_joins(Query *root, RelOptInfo *old_rel, - List *joininfo_list, Relids only_relids); -extern List *make_rels_by_clauseless_joins(RelOptInfo *old_rel, - List *inner_rels); -extern RelOptInfo *get_cheapest_complete_rel(List *join_rel_list); - -/* - * prune.c - */ -extern void merge_rels_with_same_relids(List *rel_list); -extern void rels_set_cheapest(Query *root, List *rel_list); -extern List *del_rels_all_bushy_inactive(List *old_rels); - #endif /* PATHS_H */ |