1 /*-------------------------------------------------------------------------
2 *
3 * planmain.c
4 * Routines to plan a single query
5 *
6 * What's in a name, anyway? The top-level entry point of the planner/
7 * optimizer is over in planner.c, not here as you might think from the
8 * file name. But this is the main code for planning a basic join operation,
9 * shorn of features like subselects, inheritance, aggregates, grouping,
10 * and so on. (Those are the things planner.c deals with.)
11 *
12 * Portions Copyright (c) 1996-2016, PostgreSQL Global Development Group
13 * Portions Copyright (c) 1994, Regents of the University of California
14 *
15 *
16 * IDENTIFICATION
17 * src/backend/optimizer/plan/planmain.c
18 *
19 *-------------------------------------------------------------------------
20 */
21 #include "postgres.h"
22
23 #include "optimizer/clauses.h"
24 #include "optimizer/orclauses.h"
25 #include "optimizer/pathnode.h"
26 #include "optimizer/paths.h"
27 #include "optimizer/placeholder.h"
28 #include "optimizer/planmain.h"
29
30
31 /*
32 * query_planner
33 * Generate a path (that is, a simplified plan) for a basic query,
34 * which may involve joins but not any fancier features.
35 *
36 * Since query_planner does not handle the toplevel processing (grouping,
37 * sorting, etc) it cannot select the best path by itself. Instead, it
38 * returns the RelOptInfo for the top level of joining, and the caller
39 * (grouping_planner) can choose among the surviving paths for the rel.
40 *
41 * root describes the query to plan
42 * tlist is the target list the query should produce
43 * (this is NOT necessarily root->parse->targetList!)
44 * qp_callback is a function to compute query_pathkeys once it's safe to do so
45 * qp_extra is optional extra data to pass to qp_callback
46 *
47 * Note: the PlannerInfo node also includes a query_pathkeys field, which
48 * tells query_planner the sort order that is desired in the final output
49 * plan. This value is *not* available at call time, but is computed by
50 * qp_callback once we have completed merging the query's equivalence classes.
51 * (We cannot construct canonical pathkeys until that's done.)
52 */
53 RelOptInfo *
query_planner(PlannerInfo * root,List * tlist,query_pathkeys_callback qp_callback,void * qp_extra)54 query_planner(PlannerInfo *root, List *tlist,
55 query_pathkeys_callback qp_callback, void *qp_extra)
56 {
57 Query *parse = root->parse;
58 List *joinlist;
59 RelOptInfo *final_rel;
60 Index rti;
61 double total_pages;
62
63 /*
64 * If the query has an empty join tree, then it's something easy like
65 * "SELECT 2+2;" or "INSERT ... VALUES()". Fall through quickly.
66 */
67 if (parse->jointree->fromlist == NIL)
68 {
69 /* We need a dummy joinrel to describe the empty set of baserels */
70 final_rel = build_empty_join_rel(root);
71
72 /*
73 * If query allows parallelism in general, check whether the quals are
74 * parallel-restricted. There's currently no real benefit to setting
75 * this flag correctly because we can't yet reference subplans from
76 * parallel workers. But that might change someday, so set this
77 * correctly anyway.
78 */
79 if (root->glob->parallelModeOK)
80 final_rel->consider_parallel =
81 !has_parallel_hazard(parse->jointree->quals, false);
82
83 /* The only path for it is a trivial Result path */
84 add_path(final_rel, (Path *)
85 create_result_path(root, final_rel,
86 final_rel->reltarget,
87 (List *) parse->jointree->quals));
88
89 /* Select cheapest path (pretty easy in this case...) */
90 set_cheapest(final_rel);
91
92 /*
93 * We still are required to call qp_callback, in case it's something
94 * like "SELECT 2+2 ORDER BY 1".
95 */
96 root->canon_pathkeys = NIL;
97 (*qp_callback) (root, qp_extra);
98
99 return final_rel;
100 }
101
102 /*
103 * Init planner lists to empty.
104 *
105 * NOTE: append_rel_list was set up by subquery_planner, so do not touch
106 * here.
107 */
108 root->join_rel_list = NIL;
109 root->join_rel_hash = NULL;
110 root->join_rel_level = NULL;
111 root->join_cur_level = 0;
112 root->canon_pathkeys = NIL;
113 root->left_join_clauses = NIL;
114 root->right_join_clauses = NIL;
115 root->full_join_clauses = NIL;
116 root->join_info_list = NIL;
117 root->placeholder_list = NIL;
118 root->fkey_list = NIL;
119 root->initial_rels = NIL;
120
121 /*
122 * Make a flattened version of the rangetable for faster access (this is
123 * OK because the rangetable won't change any more), and set up an empty
124 * array for indexing base relations.
125 */
126 setup_simple_rel_arrays(root);
127
128 /*
129 * Construct RelOptInfo nodes for all base relations in query, and
130 * indirectly for all appendrel member relations ("other rels"). This
131 * will give us a RelOptInfo for every "simple" (non-join) rel involved in
132 * the query.
133 *
134 * Note: the reason we find the rels by searching the jointree and
135 * appendrel list, rather than just scanning the rangetable, is that the
136 * rangetable may contain RTEs for rels not actively part of the query,
137 * for example views. We don't want to make RelOptInfos for them.
138 */
139 add_base_rels_to_query(root, (Node *) parse->jointree);
140
141 /*
142 * Examine the targetlist and join tree, adding entries to baserel
143 * targetlists for all referenced Vars, and generating PlaceHolderInfo
144 * entries for all referenced PlaceHolderVars. Restrict and join clauses
145 * are added to appropriate lists belonging to the mentioned relations. We
146 * also build EquivalenceClasses for provably equivalent expressions. The
147 * SpecialJoinInfo list is also built to hold information about join order
148 * restrictions. Finally, we form a target joinlist for make_one_rel() to
149 * work from.
150 */
151 build_base_rel_tlists(root, tlist);
152
153 find_placeholders_in_jointree(root);
154
155 find_lateral_references(root);
156
157 joinlist = deconstruct_jointree(root);
158
159 /*
160 * Reconsider any postponed outer-join quals now that we have built up
161 * equivalence classes. (This could result in further additions or
162 * mergings of classes.)
163 */
164 reconsider_outer_join_clauses(root);
165
166 /*
167 * If we formed any equivalence classes, generate additional restriction
168 * clauses as appropriate. (Implied join clauses are formed on-the-fly
169 * later.)
170 */
171 generate_base_implied_equalities(root);
172
173 /*
174 * We have completed merging equivalence sets, so it's now possible to
175 * generate pathkeys in canonical form; so compute query_pathkeys and
176 * other pathkeys fields in PlannerInfo.
177 */
178 (*qp_callback) (root, qp_extra);
179
180 /*
181 * Examine any "placeholder" expressions generated during subquery pullup.
182 * Make sure that the Vars they need are marked as needed at the relevant
183 * join level. This must be done before join removal because it might
184 * cause Vars or placeholders to be needed above a join when they weren't
185 * so marked before.
186 */
187 fix_placeholder_input_needed_levels(root);
188
189 /*
190 * Remove any useless outer joins. Ideally this would be done during
191 * jointree preprocessing, but the necessary information isn't available
192 * until we've built baserel data structures and classified qual clauses.
193 */
194 joinlist = remove_useless_joins(root, joinlist);
195
196 /*
197 * Now distribute "placeholders" to base rels as needed. This has to be
198 * done after join removal because removal could change whether a
199 * placeholder is evaluable at a base rel.
200 */
201 add_placeholders_to_base_rels(root);
202
203 /*
204 * Construct the lateral reference sets now that we have finalized
205 * PlaceHolderVar eval levels.
206 */
207 create_lateral_join_info(root);
208
209 /*
210 * Match foreign keys to equivalence classes and join quals. This must be
211 * done after finalizing equivalence classes, and it's useful to wait till
212 * after join removal so that we can skip processing foreign keys
213 * involving removed relations.
214 */
215 match_foreign_keys_to_quals(root);
216
217 /*
218 * Look for join OR clauses that we can extract single-relation
219 * restriction OR clauses from.
220 */
221 extract_restriction_or_clauses(root);
222
223 /*
224 * We should now have size estimates for every actual table involved in
225 * the query, and we also know which if any have been deleted from the
226 * query by join removal; so we can compute total_table_pages.
227 *
228 * Note that appendrels are not double-counted here, even though we don't
229 * bother to distinguish RelOptInfos for appendrel parents, because the
230 * parents will still have size zero.
231 *
232 * XXX if a table is self-joined, we will count it once per appearance,
233 * which perhaps is the wrong thing ... but that's not completely clear,
234 * and detecting self-joins here is difficult, so ignore it for now.
235 */
236 total_pages = 0;
237 for (rti = 1; rti < root->simple_rel_array_size; rti++)
238 {
239 RelOptInfo *brel = root->simple_rel_array[rti];
240
241 if (brel == NULL)
242 continue;
243
244 Assert(brel->relid == rti); /* sanity check on array */
245
246 if (brel->reloptkind == RELOPT_BASEREL ||
247 brel->reloptkind == RELOPT_OTHER_MEMBER_REL)
248 total_pages += (double) brel->pages;
249 }
250 root->total_table_pages = total_pages;
251
252 /*
253 * Ready to do the primary planning.
254 */
255 final_rel = make_one_rel(root, joinlist);
256
257 /* Check that we got at least one usable path */
258 if (!final_rel || !final_rel->cheapest_total_path ||
259 final_rel->cheapest_total_path->param_info != NULL)
260 elog(ERROR, "failed to construct the join relation");
261
262 return final_rel;
263 }
264