Age Owner Branch data TLA Line data Source code
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-2026, 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/optimizer.h"
26 : : #include "optimizer/orclauses.h"
27 : : #include "optimizer/pathnode.h"
28 : : #include "optimizer/paths.h"
29 : : #include "optimizer/placeholder.h"
30 : : #include "optimizer/planmain.h"
31 : :
32 : :
33 : : /*
34 : : * query_planner
35 : : * Generate a path (that is, a simplified plan) for a basic query,
36 : : * which may involve joins but not any fancier features.
37 : : *
38 : : * Since query_planner does not handle the toplevel processing (grouping,
39 : : * sorting, etc) it cannot select the best path by itself. Instead, it
40 : : * returns the RelOptInfo for the top level of joining, and the caller
41 : : * (grouping_planner) can choose among the surviving paths for the rel.
42 : : *
43 : : * root describes the query to plan
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 *
2734 tgl@sss.pgh.pa.us 54 :CBC 382874 : query_planner(PlannerInfo *root,
55 : : query_pathkeys_callback qp_callback, void *qp_extra)
56 : : {
57 : : Query *parse;
58 : : List *joinlist;
59 : : RelOptInfo *final_rel;
60 : :
61 : : /*
62 : : * The join simplification steps below work by modifying parse->jointree,
63 : : * and they make no attempt to update the information we derive from it.
64 : : * So whenever one of them succeeds, we must throw away all that derived
65 : : * information and recompute it from scratch, which we do by looping back
66 : : * to "restart". We cannot loop indefinitely, because each successful
67 : : * simplification either deletes a base relation from the jointree or
68 : : * turns a semijoin into an inner join, and neither of those can be undone
69 : : * by a later pass.
70 : : *
71 : : * These initial Asserts check that the state at entry is not too complex
72 : : * for the code below to restore. There mustn't be any EquivalenceClasses
73 : : * yet, and we should have only the top-level JoinDomain.
74 : : */
23 75 [ - + ]: 382874 : Assert(root->eq_classes == NIL);
76 [ + - ]: 382874 : Assert(list_length(root->join_domains) == 1);
77 : :
78 : 391586 : restart:
79 : 391586 : parse = root->parse;
80 : :
81 : : /*
82 : : * Initialize information derived from the jointree to empty.
83 : : *
84 : : * It's critical that this reset every field that the steps below will
85 : : * fill in, since we may be going around this loop more than once.
86 : : *
87 : : * NOTE: append_rel_list was created earlier, so do not clear it here;
88 : : * rowMarks ditto. Join simplification must update those if necessary.
89 : : */
90 : 391586 : root->all_baserels = NULL;
91 : 391586 : root->outer_join_rels = NULL;
92 : 391586 : root->all_query_rels = NULL;
10268 bruce@momjian.us 93 : 391586 : root->join_rel_list = NIL;
7774 tgl@sss.pgh.pa.us 94 : 391586 : root->join_rel_hash = NULL;
6140 95 : 391586 : root->join_rel_level = NULL;
96 : 391586 : root->join_cur_level = 0;
23 97 : 391586 : root->eq_classes = NIL;
98 : 391586 : root->ec_merging_done = false;
7183 99 : 391586 : root->canon_pathkeys = NIL;
7750 100 : 391586 : root->left_join_clauses = NIL;
101 : 391586 : root->right_join_clauses = NIL;
102 : 391586 : root->full_join_clauses = NIL;
6611 103 : 391586 : root->join_info_list = NIL;
23 104 : 391586 : root->last_rinfo_serial = 0;
6542 105 : 391586 : root->placeholder_list = NIL;
1495 106 : 391586 : root->placeholder_array = NULL;
107 : 391586 : root->placeholder_array_size = 0;
23 108 : 391586 : root->placeholdersFrozen = false;
347 rguo@postgresql.org 109 : 391586 : root->agg_clause_list = NIL;
110 : 391586 : root->group_expr_list = NIL;
111 : 391586 : root->tlist_vars = NIL;
3746 tgl@sss.pgh.pa.us 112 : 391586 : root->fkey_list = NIL;
6827 113 : 391586 : root->initial_rels = NIL;
23 114 : 391586 : root->hasPseudoConstantQuals = false;
115 : :
116 : : /*
117 : : * We don't want to delete the top-level join domain, but get rid of other
118 : : * ones so as to reset the list to initial state. deconstruct_jointree
119 : : * will take care of (re)computing the top level's jd_relids.
120 : : */
121 : 391586 : root->join_domains = list_truncate(root->join_domains, 1);
122 : :
123 : : /*
124 : : * Set up arrays for accessing base relations and AppendRelInfos.
125 : : */
5496 126 : 391586 : setup_simple_rel_arrays(root);
127 : :
128 : : /*
129 : : * In the trivial case where the jointree is a single RTE_RESULT relation,
130 : : * bypass all the rest of this function and just make a RelOptInfo and its
131 : : * one access path. This is worth optimizing because it applies for
132 : : * common cases like "SELECT expression" and "INSERT ... VALUES()".
133 : : */
2792 134 [ - + ]: 391586 : Assert(parse->jointree->fromlist != NIL);
135 [ + + ]: 391586 : if (list_length(parse->jointree->fromlist) == 1)
136 : : {
137 : 362094 : Node *jtnode = (Node *) linitial(parse->jointree->fromlist);
138 : :
139 [ + + ]: 362094 : if (IsA(jtnode, RangeTblRef))
140 : : {
141 : 304258 : int varno = ((RangeTblRef *) jtnode)->rtindex;
142 : 304258 : RangeTblEntry *rte = root->simple_rte_array[varno];
143 : :
144 [ - + ]: 304258 : Assert(rte != NULL);
145 [ + + ]: 304258 : if (rte->rtekind == RTE_RESULT)
146 : : {
147 : : /* Make the RelOptInfo for it directly */
148 : 138735 : final_rel = build_simple_rel(root, varno, NULL);
149 : :
150 : : /*
151 : : * If query allows parallelism in general, check whether the
152 : : * quals are parallel-restricted. (We need not check
153 : : * final_rel->reltarget because it's empty at this point.
154 : : * Anything parallel-restricted in the query tlist will be
155 : : * dealt with later.) We should always do this in a subquery,
156 : : * since it might be useful to use the subquery in parallel
157 : : * paths in the parent level. At top level this is normally
158 : : * not worth the cycles, because a Result-only plan would
159 : : * never be interesting to parallelize. However, if
160 : : * debug_parallel_query is on, then we want to execute the
161 : : * Result in a parallel worker if possible, so we must check.
162 : : */
163 [ + + ]: 138735 : if (root->glob->parallelModeOK &&
1165 164 [ + + ]: 76360 : (root->query_level > 1 ||
165 [ + + ]: 71358 : debug_parallel_query != DEBUG_PARALLEL_OFF))
2792 166 : 5082 : final_rel->consider_parallel =
167 : 5082 : is_parallel_safe(root, parse->jointree->quals);
168 : :
169 : : /*
170 : : * The only path for it is a trivial Result path. We cheat a
171 : : * bit here by using a GroupResultPath, because that way we
172 : : * can just jam the quals into it without preprocessing them.
173 : : * (But, if you hold your head at the right angle, a FROM-less
174 : : * SELECT is a kind of degenerate-grouping case, so it's not
175 : : * that much of a cheat.)
176 : : */
177 : 138735 : add_path(final_rel, (Path *)
178 : 138735 : create_group_result_path(root, final_rel,
179 : 138735 : final_rel->reltarget,
180 : 138735 : (List *) parse->jointree->quals));
181 : :
182 : : /* Select cheapest path (pretty easy in this case...) */
183 : 138735 : set_cheapest(final_rel);
184 : :
185 : : /*
186 : : * Fill in all_result_relids and leaf_result_relids, just in
187 : : * case something looks at them (at this writing, the core
188 : : * code won't). This must match the similar stanza below.
189 : : */
23 190 [ + + ]: 138735 : if (parse->resultRelation)
191 : : {
192 : 39464 : int rti = parse->resultRelation;
193 : 39464 : RangeTblEntry *res_rte = root->simple_rte_array[rti];
194 : :
195 : 39464 : root->all_result_relids = bms_make_singleton(rti);
196 [ + - ]: 39464 : if (!res_rte->inh)
197 : 39464 : root->leaf_result_relids = bms_make_singleton(rti);
198 : : }
199 : :
200 : : /*
201 : : * We don't need to run generate_base_implied_equalities, but
202 : : * we do need to pretend that EC merging is complete.
203 : : */
2618 drowley@postgresql.o 204 : 138735 : root->ec_merging_done = true;
205 : :
206 : : /*
207 : : * We still are required to call qp_callback, in case it's
208 : : * something like "SELECT 2+2 ORDER BY 1".
209 : : */
2792 tgl@sss.pgh.pa.us 210 : 138735 : (*qp_callback) (root, qp_extra);
211 : :
212 : 138735 : return final_rel;
213 : : }
214 : : }
215 : : }
216 : :
217 : : /*
218 : : * Construct RelOptInfo nodes for all base relations used in the query.
219 : : * Appendrel member relations ("other rels") will be added later.
220 : : *
221 : : * Note: the reason we find the baserels by searching the jointree, rather
222 : : * than scanning the rangetable, is that the rangetable may contain RTEs
223 : : * for rels not actively part of the query, for example views. We don't
224 : : * want to make RelOptInfos for them.
225 : : */
7777 226 : 252851 : add_base_rels_to_query(root, (Node *) parse->jointree);
227 : :
228 : : /* Remove any redundant GROUP BY columns */
647 drowley@postgresql.o 229 : 252839 : remove_useless_groupby_columns(root);
230 : :
231 : : /*
232 : : * Examine the targetlist and join tree, adding entries to baserel
233 : : * targetlists for all referenced Vars, and generating PlaceHolderInfo
234 : : * entries for all referenced PlaceHolderVars. Restrict and join clauses
235 : : * are added to appropriate lists belonging to the mentioned relations. We
236 : : * also build EquivalenceClasses for provably equivalent expressions. The
237 : : * SpecialJoinInfo list is also built to hold information about join order
238 : : * restrictions. Finally, we form a target joinlist for make_one_rel() to
239 : : * work from.
240 : : */
2734 tgl@sss.pgh.pa.us 241 : 252839 : build_base_rel_tlists(root, root->processed_tlist);
242 : :
5301 243 : 252839 : find_placeholders_in_jointree(root);
244 : :
5138 245 : 252839 : find_lateral_references(root);
246 : :
7579 247 : 252839 : joinlist = deconstruct_jointree(root);
248 : :
249 : : /*
250 : : * Reconsider any postponed outer-join quals now that we have built up
251 : : * equivalence classes. (This could result in further additions or
252 : : * mergings of classes.)
253 : : */
7183 254 : 252839 : reconsider_outer_join_clauses(root);
255 : :
256 : : /*
257 : : * If we formed any equivalence classes, generate additional restriction
258 : : * clauses as appropriate. (Implied join clauses are formed on-the-fly
259 : : * later.)
260 : : */
261 : 252839 : generate_base_implied_equalities(root);
262 : :
263 : : /*
264 : : * We have completed merging equivalence sets, so it's now possible to
265 : : * generate pathkeys in canonical form; so compute query_pathkeys and
266 : : * other pathkeys fields in PlannerInfo.
267 : : */
4892 268 : 252839 : (*qp_callback) (root, qp_extra);
269 : :
270 : : /*
271 : : * Examine any "placeholder" expressions generated during subquery pullup.
272 : : * Make sure that the Vars they need are marked as needed at the relevant
273 : : * join level. This must be done before join removal because it might
274 : : * cause Vars or placeholders to be needed above a join when they weren't
275 : : * so marked before.
276 : : */
5836 277 : 252839 : fix_placeholder_input_needed_levels(root);
278 : :
279 : : /*
280 : : * Remove any useless outer joins. Ideally this would be done during
281 : : * jointree preprocessing, but the necessary information isn't available
282 : : * until we've built baserel data structures and classified qual clauses.
283 : : * If we remove a join, loop back to the top and redo what we did so far.
284 : : */
23 285 [ + + ]: 252839 : if (remove_useless_outer_joins(root))
286 : 8034 : goto restart;
287 : :
288 : : /*
289 : : * Also, reduce any semijoins with unique inner rels to plain inner joins.
290 : : * Likewise, this can't be done until now for lack of needed info, and we
291 : : * must loop around if we find any simplifications.
292 : : */
293 [ + + ]: 244805 : if (reduce_unique_semijoins(root))
294 : 230 : goto restart;
295 : :
296 : : /*
297 : : * Remove self joins on a unique column. Again, this couldn't be done any
298 : : * earlier, and we must loop around if we find anything to remove.
299 : : */
300 [ + + ]: 244575 : if (remove_useless_self_joins(root, joinlist))
301 : 448 : goto restart;
302 : :
303 : : /*
304 : : * No more join simplifications apply, so we're done looping. Code below
305 : : * this point does not need to be able to restart.
306 : : */
307 : :
308 : : /*
309 : : * Now distribute "placeholders" to base rels as needed. This has to be
310 : : * done after join removal because removal could change whether a
311 : : * placeholder is evaluable at a base rel.
312 : : */
6020 313 : 244127 : add_placeholders_to_base_rels(root);
314 : :
315 : : /*
316 : : * Construct the lateral reference sets now that we have finalized
317 : : * PlaceHolderVar eval levels.
318 : : */
4782 319 : 244127 : create_lateral_join_info(root);
320 : :
321 : : /*
322 : : * Match foreign keys to equivalence classes and join quals. This must be
323 : : * done after finalizing equivalence classes, and it's useful to wait till
324 : : * after join removal so that we can skip processing foreign keys
325 : : * involving removed relations.
326 : : */
3746 327 : 244127 : match_foreign_keys_to_quals(root);
328 : :
329 : : /*
330 : : * Look for join OR clauses that we can extract single-relation
331 : : * restriction OR clauses from.
332 : : */
4647 333 : 244127 : extract_restriction_or_clauses(root);
334 : :
335 : : /*
336 : : * Check if eager aggregation is applicable, and if so, set up
337 : : * root->agg_clause_list and root->group_expr_list.
338 : : */
347 rguo@postgresql.org 339 : 244127 : setup_eager_aggregation(root);
340 : :
341 : : /*
342 : : * If there's a result relation, initialize all_result_relids to include
343 : : * it; and if we've verified that it is non-inheriting, mark it as a leaf
344 : : * target. add_other_rels_to_query() will expand these sets if the result
345 : : * relation has children.
346 : : */
23 tgl@sss.pgh.pa.us 347 [ + + ]: 244127 : if (parse->resultRelation)
348 : : {
349 : 23403 : int rti = parse->resultRelation;
350 : 23403 : RangeTblEntry *rte = root->simple_rte_array[rti];
351 : :
352 : 23403 : root->all_result_relids = bms_make_singleton(rti);
353 [ + + ]: 23403 : if (!rte->inh)
354 : 21155 : root->leaf_result_relids = bms_make_singleton(rti);
355 : : }
356 : :
357 : : /*
358 : : * Now expand appendrels by adding "otherrels" for their children. We
359 : : * delay this to the end so that we have as much information as possible
360 : : * available for each baserel, including all restriction clauses. That
361 : : * let us prune away partitions that don't satisfy a restriction clause.
362 : : * Also note that some information such as lateral_relids is propagated
363 : : * from baserels to otherrels here, so we must have computed it already.
364 : : */
2735 365 : 244127 : add_other_rels_to_query(root);
366 : :
367 : : /*
368 : : * Distribute any UPDATE/DELETE/MERGE row identity variables to the target
369 : : * relations. This can't be done till we've finished expansion of
370 : : * appendrels.
371 : : */
1999 372 : 244126 : distribute_row_identity_vars(root);
373 : :
374 : : /*
375 : : * Ready to do the primary planning.
376 : : */
7579 377 : 244126 : final_rel = make_one_rel(root, joinlist);
378 : :
379 : : /* Check that we got at least one usable path */
5135 380 [ + - + - ]: 244104 : if (!final_rel || !final_rel->cheapest_total_path ||
381 [ - + ]: 244104 : final_rel->cheapest_total_path->param_info != NULL)
8458 tgl@sss.pgh.pa.us 382 [ # # ]:UBC 0 : elog(ERROR, "failed to construct the join relation");
383 : :
4794 tgl@sss.pgh.pa.us 384 :CBC 244104 : return final_rel;
385 : : }
|
