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-2019, 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 */
54RelOptInfo *
55query_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 * Make a flattened version of the rangetable for faster access (this is
83 * OK because the rangetable won't change any more), and set up an empty
84 * array for indexing base relations.
85 */
86 setup_simple_rel_arrays(root);
87
88 /*
89 * In the trivial case where the jointree is a single RTE_RESULT relation,
90 * bypass all the rest of this function and just make a RelOptInfo and its
91 * one access path. This is worth optimizing because it applies for
92 * common cases like "SELECT expression" and "INSERT ... VALUES()".
93 */
94 Assert(parse->jointree->fromlist != NIL);
95 if (list_length(parse->jointree->fromlist) == 1)
96 {
97 Node *jtnode = (Node *) linitial(parse->jointree->fromlist);
98
99 if (IsA(jtnode, RangeTblRef))
100 {
101 int varno = ((RangeTblRef *) jtnode)->rtindex;
102 RangeTblEntry *rte = root->simple_rte_array[varno];
103
104 Assert(rte != NULL);
105 if (rte->rtekind == RTE_RESULT)
106 {
107 /* Make the RelOptInfo for it directly */
108 final_rel = build_simple_rel(root, varno, NULL);
109
110 /*
111 * If query allows parallelism in general, check whether the
112 * quals are parallel-restricted. (We need not check
113 * final_rel->reltarget because it's empty at this point.
114 * Anything parallel-restricted in the query tlist will be
115 * dealt with later.) This is normally pretty silly, because
116 * a Result-only plan would never be interesting to
117 * parallelize. However, if force_parallel_mode is on, then
118 * we want to execute the Result in a parallel worker if
119 * possible, so we must do this.
120 */
121 if (root->glob->parallelModeOK &&
122 force_parallel_mode != FORCE_PARALLEL_OFF)
123 final_rel->consider_parallel =
124 is_parallel_safe(root, parse->jointree->quals);
125
126 /*
127 * The only path for it is a trivial Result path. We cheat a
128 * bit here by using a GroupResultPath, because that way we
129 * can just jam the quals into it without preprocessing them.
130 * (But, if you hold your head at the right angle, a FROM-less
131 * SELECT is a kind of degenerate-grouping case, so it's not
132 * that much of a cheat.)
133 */
134 add_path(final_rel, (Path *)
135 create_group_result_path(root, final_rel,
136 final_rel->reltarget,
137 (List *) parse->jointree->quals));
138
139 /* Select cheapest path (pretty easy in this case...) */
140 set_cheapest(final_rel);
141
142 /*
143 * We still are required to call qp_callback, in case it's
144 * something like "SELECT 2+2 ORDER BY 1".
145 */
146 (*qp_callback) (root, qp_extra);
147
148 return final_rel;
149 }
150 }
151 }
152
153 /*
154 * Populate append_rel_array with each AppendRelInfo to allow direct
155 * lookups by child relid.
156 */
157 setup_append_rel_array(root);
158
159 /*
160 * Construct RelOptInfo nodes for all base relations used in the query.
161 * Appendrel member relations ("other rels") will be added later.
162 *
163 * Note: the reason we find the baserels by searching the jointree, rather
164 * than scanning the rangetable, is that the rangetable may contain RTEs
165 * for rels not actively part of the query, for example views. We don't
166 * want to make RelOptInfos for them.
167 */
168 add_base_rels_to_query(root, (Node *) parse->jointree);
169
170 /*
171 * Examine the targetlist and join tree, adding entries to baserel
172 * targetlists for all referenced Vars, and generating PlaceHolderInfo
173 * entries for all referenced PlaceHolderVars. Restrict and join clauses
174 * are added to appropriate lists belonging to the mentioned relations. We
175 * also build EquivalenceClasses for provably equivalent expressions. The
176 * SpecialJoinInfo list is also built to hold information about join order
177 * restrictions. Finally, we form a target joinlist for make_one_rel() to
178 * work from.
179 */
180 build_base_rel_tlists(root, root->processed_tlist);
181
182 find_placeholders_in_jointree(root);
183
184 find_lateral_references(root);
185
186 joinlist = deconstruct_jointree(root);
187
188 /*
189 * Reconsider any postponed outer-join quals now that we have built up
190 * equivalence classes. (This could result in further additions or
191 * mergings of classes.)
192 */
193 reconsider_outer_join_clauses(root);
194
195 /*
196 * If we formed any equivalence classes, generate additional restriction
197 * clauses as appropriate. (Implied join clauses are formed on-the-fly
198 * later.)
199 */
200 generate_base_implied_equalities(root);
201
202 /*
203 * We have completed merging equivalence sets, so it's now possible to
204 * generate pathkeys in canonical form; so compute query_pathkeys and
205 * other pathkeys fields in PlannerInfo.
206 */
207 (*qp_callback) (root, qp_extra);
208
209 /*
210 * Examine any "placeholder" expressions generated during subquery pullup.
211 * Make sure that the Vars they need are marked as needed at the relevant
212 * join level. This must be done before join removal because it might
213 * cause Vars or placeholders to be needed above a join when they weren't
214 * so marked before.
215 */
216 fix_placeholder_input_needed_levels(root);
217
218 /*
219 * Remove any useless outer joins. Ideally this would be done during
220 * jointree preprocessing, but the necessary information isn't available
221 * until we've built baserel data structures and classified qual clauses.
222 */
223 joinlist = remove_useless_joins(root, joinlist);
224
225 /*
226 * Also, reduce any semijoins with unique inner rels to plain inner joins.
227 * Likewise, this can't be done until now for lack of needed info.
228 */
229 reduce_unique_semijoins(root);
230
231 /*
232 * Now distribute "placeholders" to base rels as needed. This has to be
233 * done after join removal because removal could change whether a
234 * placeholder is evaluable at a base rel.
235 */
236 add_placeholders_to_base_rels(root);
237
238 /*
239 * Construct the lateral reference sets now that we have finalized
240 * PlaceHolderVar eval levels.
241 */
242 create_lateral_join_info(root);
243
244 /*
245 * Match foreign keys to equivalence classes and join quals. This must be
246 * done after finalizing equivalence classes, and it's useful to wait till
247 * after join removal so that we can skip processing foreign keys
248 * involving removed relations.
249 */
250 match_foreign_keys_to_quals(root);
251
252 /*
253 * Look for join OR clauses that we can extract single-relation
254 * restriction OR clauses from.
255 */
256 extract_restriction_or_clauses(root);
257
258 /*
259 * Now expand appendrels by adding "otherrels" for their children. We
260 * delay this to the end so that we have as much information as possible
261 * available for each baserel, including all restriction clauses. That
262 * let us prune away partitions that don't satisfy a restriction clause.
263 * Also note that some information such as lateral_relids is propagated
264 * from baserels to otherrels here, so we must have computed it already.
265 */
266 add_other_rels_to_query(root);
267
268 /*
269 * Ready to do the primary planning.
270 */
271 final_rel = make_one_rel(root, joinlist);
272
273 /* Check that we got at least one usable path */
274 if (!final_rel || !final_rel->cheapest_total_path ||
275 final_rel->cheapest_total_path->param_info != NULL)
276 elog(ERROR, "failed to construct the join relation");
277
278 return final_rel;
279}
280