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-2020, 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/appendinfo.h"
24 #include "optimizer/clauses.h"
25 #include "optimizer/inherit.h"
26 #include "optimizer/optimizer.h"
27 #include "optimizer/orclauses.h"
28 #include "optimizer/pathnode.h"
29 #include "optimizer/paths.h"
30 #include "optimizer/placeholder.h"
31 #include "optimizer/planmain.h"
32
33
34 /*
35 * query_planner
36 * Generate a path (that is, a simplified plan) for a basic query,
37 * which may involve joins but not any fancier features.
38 *
39 * Since query_planner does not handle the toplevel processing (grouping,
40 * sorting, etc) it cannot select the best path by itself. Instead, it
41 * returns the RelOptInfo for the top level of joining, and the caller
42 * (grouping_planner) can choose among the surviving paths for the rel.
43 *
44 * root describes the query to plan
45 * qp_callback is a function to compute query_pathkeys once it's safe to do so
46 * qp_extra is optional extra data to pass to qp_callback
47 *
48 * Note: the PlannerInfo node also includes a query_pathkeys field, which
49 * tells query_planner the sort order that is desired in the final output
50 * plan. This value is *not* available at call time, but is computed by
51 * qp_callback once we have completed merging the query's equivalence classes.
52 * (We cannot construct canonical pathkeys until that's done.)
53 */
54 RelOptInfo *
query_planner(PlannerInfo * root,query_pathkeys_callback qp_callback,void * qp_extra)55 query_planner(PlannerInfo *root,
56 query_pathkeys_callback qp_callback, void *qp_extra)
57 {
58 Query *parse = root->parse;
59 List *joinlist;
60 RelOptInfo *final_rel;
61
62 /*
63 * Init planner lists to empty.
64 *
65 * NOTE: append_rel_list was set up by subquery_planner, so do not touch
66 * here.
67 */
68 root->join_rel_list = NIL;
69 root->join_rel_hash = NULL;
70 root->join_rel_level = NULL;
71 root->join_cur_level = 0;
72 root->canon_pathkeys = NIL;
73 root->left_join_clauses = NIL;
74 root->right_join_clauses = NIL;
75 root->full_join_clauses = NIL;
76 root->join_info_list = NIL;
77 root->placeholder_list = NIL;
78 root->fkey_list = NIL;
79 root->initial_rels = NIL;
80
81 /*
82 * Set up arrays for accessing base relations and AppendRelInfos.
83 */
84 setup_simple_rel_arrays(root);
85
86 /*
87 * In the trivial case where the jointree is a single RTE_RESULT relation,
88 * bypass all the rest of this function and just make a RelOptInfo and its
89 * one access path. This is worth optimizing because it applies for
90 * common cases like "SELECT expression" and "INSERT ... VALUES()".
91 */
92 Assert(parse->jointree->fromlist != NIL);
93 if (list_length(parse->jointree->fromlist) == 1)
94 {
95 Node *jtnode = (Node *) linitial(parse->jointree->fromlist);
96
97 if (IsA(jtnode, RangeTblRef))
98 {
99 int varno = ((RangeTblRef *) jtnode)->rtindex;
100 RangeTblEntry *rte = root->simple_rte_array[varno];
101
102 Assert(rte != NULL);
103 if (rte->rtekind == RTE_RESULT)
104 {
105 /* Make the RelOptInfo for it directly */
106 final_rel = build_simple_rel(root, varno, NULL);
107
108 /*
109 * If query allows parallelism in general, check whether the
110 * quals are parallel-restricted. (We need not check
111 * final_rel->reltarget because it's empty at this point.
112 * Anything parallel-restricted in the query tlist will be
113 * dealt with later.) This is normally pretty silly, because
114 * a Result-only plan would never be interesting to
115 * parallelize. However, if force_parallel_mode is on, then
116 * we want to execute the Result in a parallel worker if
117 * possible, so we must do this.
118 */
119 if (root->glob->parallelModeOK &&
120 force_parallel_mode != FORCE_PARALLEL_OFF)
121 final_rel->consider_parallel =
122 is_parallel_safe(root, parse->jointree->quals);
123
124 /*
125 * The only path for it is a trivial Result path. We cheat a
126 * bit here by using a GroupResultPath, because that way we
127 * can just jam the quals into it without preprocessing them.
128 * (But, if you hold your head at the right angle, a FROM-less
129 * SELECT is a kind of degenerate-grouping case, so it's not
130 * that much of a cheat.)
131 */
132 add_path(final_rel, (Path *)
133 create_group_result_path(root, final_rel,
134 final_rel->reltarget,
135 (List *) parse->jointree->quals));
136
137 /* Select cheapest path (pretty easy in this case...) */
138 set_cheapest(final_rel);
139
140 /*
141 * We don't need to run generate_base_implied_equalities, but
142 * we do need to pretend that EC merging is complete.
143 */
144 root->ec_merging_done = true;
145
146 /*
147 * We still are required to call qp_callback, in case it's
148 * something like "SELECT 2+2 ORDER BY 1".
149 */
150 (*qp_callback) (root, qp_extra);
151
152 return final_rel;
153 }
154 }
155 }
156
157 /*
158 * Construct RelOptInfo nodes for all base relations used in the query.
159 * Appendrel member relations ("other rels") will be added later.
160 *
161 * Note: the reason we find the baserels by searching the jointree, rather
162 * than scanning the rangetable, is that the rangetable may contain RTEs
163 * for rels not actively part of the query, for example views. We don't
164 * want to make RelOptInfos for them.
165 */
166 add_base_rels_to_query(root, (Node *) parse->jointree);
167
168 /*
169 * Examine the targetlist and join tree, adding entries to baserel
170 * targetlists for all referenced Vars, and generating PlaceHolderInfo
171 * entries for all referenced PlaceHolderVars. Restrict and join clauses
172 * are added to appropriate lists belonging to the mentioned relations. We
173 * also build EquivalenceClasses for provably equivalent expressions. The
174 * SpecialJoinInfo list is also built to hold information about join order
175 * restrictions. Finally, we form a target joinlist for make_one_rel() to
176 * work from.
177 */
178 build_base_rel_tlists(root, root->processed_tlist);
179
180 find_placeholders_in_jointree(root);
181
182 find_lateral_references(root);
183
184 joinlist = deconstruct_jointree(root);
185
186 /*
187 * Reconsider any postponed outer-join quals now that we have built up
188 * equivalence classes. (This could result in further additions or
189 * mergings of classes.)
190 */
191 reconsider_outer_join_clauses(root);
192
193 /*
194 * If we formed any equivalence classes, generate additional restriction
195 * clauses as appropriate. (Implied join clauses are formed on-the-fly
196 * later.)
197 */
198 generate_base_implied_equalities(root);
199
200 /*
201 * We have completed merging equivalence sets, so it's now possible to
202 * generate pathkeys in canonical form; so compute query_pathkeys and
203 * other pathkeys fields in PlannerInfo.
204 */
205 (*qp_callback) (root, qp_extra);
206
207 /*
208 * Examine any "placeholder" expressions generated during subquery pullup.
209 * Make sure that the Vars they need are marked as needed at the relevant
210 * join level. This must be done before join removal because it might
211 * cause Vars or placeholders to be needed above a join when they weren't
212 * so marked before.
213 */
214 fix_placeholder_input_needed_levels(root);
215
216 /*
217 * Remove any useless outer joins. Ideally this would be done during
218 * jointree preprocessing, but the necessary information isn't available
219 * until we've built baserel data structures and classified qual clauses.
220 */
221 joinlist = remove_useless_joins(root, joinlist);
222
223 /*
224 * Also, reduce any semijoins with unique inner rels to plain inner joins.
225 * Likewise, this can't be done until now for lack of needed info.
226 */
227 reduce_unique_semijoins(root);
228
229 /*
230 * Now distribute "placeholders" to base rels as needed. This has to be
231 * done after join removal because removal could change whether a
232 * placeholder is evaluable at a base rel.
233 */
234 add_placeholders_to_base_rels(root);
235
236 /*
237 * Construct the lateral reference sets now that we have finalized
238 * PlaceHolderVar eval levels.
239 */
240 create_lateral_join_info(root);
241
242 /*
243 * Match foreign keys to equivalence classes and join quals. This must be
244 * done after finalizing equivalence classes, and it's useful to wait till
245 * after join removal so that we can skip processing foreign keys
246 * involving removed relations.
247 */
248 match_foreign_keys_to_quals(root);
249
250 /*
251 * Look for join OR clauses that we can extract single-relation
252 * restriction OR clauses from.
253 */
254 extract_restriction_or_clauses(root);
255
256 /*
257 * Now expand appendrels by adding "otherrels" for their children. We
258 * delay this to the end so that we have as much information as possible
259 * available for each baserel, including all restriction clauses. That
260 * let us prune away partitions that don't satisfy a restriction clause.
261 * Also note that some information such as lateral_relids is propagated
262 * from baserels to otherrels here, so we must have computed it already.
263 */
264 add_other_rels_to_query(root);
265
266 /*
267 * Ready to do the primary planning.
268 */
269 final_rel = make_one_rel(root, joinlist);
270
271 /* Check that we got at least one usable path */
272 if (!final_rel || !final_rel->cheapest_total_path ||
273 final_rel->cheapest_total_path->param_info != NULL)
274 elog(ERROR, "failed to construct the join relation");
275
276 return final_rel;
277 }
278