PostgreSQL Source Code git master
planmain.c
Go to the documentation of this file.
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-2025, 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
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"
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 */
55 query_pathkeys_callback qp_callback, void *qp_extra)
56{
57 Query *parse = root->parse;
58 List *joinlist;
59 RelOptInfo *final_rel;
60
61 /*
62 * Init planner lists to empty.
63 *
64 * NOTE: append_rel_list was set up by subquery_planner, so do not touch
65 * here.
66 */
67 root->join_rel_list = NIL;
68 root->join_rel_hash = NULL;
69 root->join_rel_level = NULL;
70 root->join_cur_level = 0;
71 root->canon_pathkeys = NIL;
72 root->left_join_clauses = NIL;
73 root->right_join_clauses = NIL;
74 root->full_join_clauses = NIL;
75 root->join_info_list = NIL;
76 root->placeholder_list = NIL;
77 root->placeholder_array = NULL;
78 root->placeholder_array_size = 0;
79 root->fkey_list = NIL;
80 root->initial_rels = NIL;
81
82 /*
83 * Set up arrays for accessing base relations and AppendRelInfos.
84 */
86
87 /*
88 * In the trivial case where the jointree is a single RTE_RESULT relation,
89 * bypass all the rest of this function and just make a RelOptInfo and its
90 * one access path. This is worth optimizing because it applies for
91 * common cases like "SELECT expression" and "INSERT ... VALUES()".
92 */
93 Assert(parse->jointree->fromlist != NIL);
94 if (list_length(parse->jointree->fromlist) == 1)
95 {
96 Node *jtnode = (Node *) linitial(parse->jointree->fromlist);
97
98 if (IsA(jtnode, RangeTblRef))
99 {
100 int varno = ((RangeTblRef *) jtnode)->rtindex;
101 RangeTblEntry *rte = root->simple_rte_array[varno];
102
103 Assert(rte != NULL);
104 if (rte->rtekind == RTE_RESULT)
105 {
106 /* Make the RelOptInfo for it directly */
107 final_rel = build_simple_rel(root, varno, NULL);
108
109 /*
110 * If query allows parallelism in general, check whether the
111 * quals are parallel-restricted. (We need not check
112 * final_rel->reltarget because it's empty at this point.
113 * Anything parallel-restricted in the query tlist will be
114 * dealt with later.) We should always do this in a subquery,
115 * since it might be useful to use the subquery in parallel
116 * paths in the parent level. At top level this is normally
117 * not worth the cycles, because a Result-only plan would
118 * never be interesting to parallelize. However, if
119 * debug_parallel_query is on, then we want to execute the
120 * Result in a parallel worker if possible, so we must check.
121 */
122 if (root->glob->parallelModeOK &&
123 (root->query_level > 1 ||
125 final_rel->consider_parallel =
126 is_parallel_safe(root, parse->jointree->quals);
127
128 /*
129 * The only path for it is a trivial Result path. We cheat a
130 * bit here by using a GroupResultPath, because that way we
131 * can just jam the quals into it without preprocessing them.
132 * (But, if you hold your head at the right angle, a FROM-less
133 * SELECT is a kind of degenerate-grouping case, so it's not
134 * that much of a cheat.)
135 */
136 add_path(final_rel, (Path *)
138 final_rel->reltarget,
139 (List *) parse->jointree->quals));
140
141 /* Select cheapest path (pretty easy in this case...) */
142 set_cheapest(final_rel);
143
144 /*
145 * We don't need to run generate_base_implied_equalities, but
146 * we do need to pretend that EC merging is complete.
147 */
148 root->ec_merging_done = true;
149
150 /*
151 * We still are required to call qp_callback, in case it's
152 * something like "SELECT 2+2 ORDER BY 1".
153 */
154 (*qp_callback) (root, qp_extra);
155
156 return final_rel;
157 }
158 }
159 }
160
161 /*
162 * Construct RelOptInfo nodes for all base relations used in the query.
163 * Appendrel member relations ("other rels") will be added later.
164 *
165 * Note: the reason we find the baserels by searching the jointree, rather
166 * than scanning the rangetable, is that the rangetable may contain RTEs
167 * for rels not actively part of the query, for example views. We don't
168 * want to make RelOptInfos for them.
169 */
170 add_base_rels_to_query(root, (Node *) parse->jointree);
171
172 /* Remove any redundant GROUP BY columns */
174
175 /*
176 * Examine the targetlist and join tree, adding entries to baserel
177 * targetlists for all referenced Vars, and generating PlaceHolderInfo
178 * entries for all referenced PlaceHolderVars. Restrict and join clauses
179 * are added to appropriate lists belonging to the mentioned relations. We
180 * also build EquivalenceClasses for provably equivalent expressions. The
181 * SpecialJoinInfo list is also built to hold information about join order
182 * restrictions. Finally, we form a target joinlist for make_one_rel() to
183 * work from.
184 */
185 build_base_rel_tlists(root, root->processed_tlist);
186
188
190
191 joinlist = deconstruct_jointree(root);
192
193 /*
194 * Reconsider any postponed outer-join quals now that we have built up
195 * equivalence classes. (This could result in further additions or
196 * mergings of classes.)
197 */
199
200 /*
201 * If we formed any equivalence classes, generate additional restriction
202 * clauses as appropriate. (Implied join clauses are formed on-the-fly
203 * later.)
204 */
206
207 /*
208 * We have completed merging equivalence sets, so it's now possible to
209 * generate pathkeys in canonical form; so compute query_pathkeys and
210 * other pathkeys fields in PlannerInfo.
211 */
212 (*qp_callback) (root, qp_extra);
213
214 /*
215 * Examine any "placeholder" expressions generated during subquery pullup.
216 * Make sure that the Vars they need are marked as needed at the relevant
217 * join level. This must be done before join removal because it might
218 * cause Vars or placeholders to be needed above a join when they weren't
219 * so marked before.
220 */
222
223 /*
224 * Remove any useless outer joins. Ideally this would be done during
225 * jointree preprocessing, but the necessary information isn't available
226 * until we've built baserel data structures and classified qual clauses.
227 */
228 joinlist = remove_useless_joins(root, joinlist);
229
230 /*
231 * Also, reduce any semijoins with unique inner rels to plain inner joins.
232 * Likewise, this can't be done until now for lack of needed info.
233 */
235
236 /*
237 * Remove self joins on a unique column.
238 */
239 joinlist = remove_useless_self_joins(root, joinlist);
240
241 /*
242 * Now distribute "placeholders" to base rels as needed. This has to be
243 * done after join removal because removal could change whether a
244 * placeholder is evaluable at a base rel.
245 */
247
248 /*
249 * Construct the lateral reference sets now that we have finalized
250 * PlaceHolderVar eval levels.
251 */
253
254 /*
255 * Match foreign keys to equivalence classes and join quals. This must be
256 * done after finalizing equivalence classes, and it's useful to wait till
257 * after join removal so that we can skip processing foreign keys
258 * involving removed relations.
259 */
261
262 /*
263 * Look for join OR clauses that we can extract single-relation
264 * restriction OR clauses from.
265 */
267
268 /*
269 * Now expand appendrels by adding "otherrels" for their children. We
270 * delay this to the end so that we have as much information as possible
271 * available for each baserel, including all restriction clauses. That
272 * let us prune away partitions that don't satisfy a restriction clause.
273 * Also note that some information such as lateral_relids is propagated
274 * from baserels to otherrels here, so we must have computed it already.
275 */
277
278 /*
279 * Distribute any UPDATE/DELETE/MERGE row identity variables to the target
280 * relations. This can't be done till we've finished expansion of
281 * appendrels.
282 */
284
285 /*
286 * Ready to do the primary planning.
287 */
288 final_rel = make_one_rel(root, joinlist);
289
290 /* Check that we got at least one usable path */
291 if (!final_rel || !final_rel->cheapest_total_path ||
292 final_rel->cheapest_total_path->param_info != NULL)
293 elog(ERROR, "failed to construct the join relation");
294
295 return final_rel;
296}
RelOptInfo * make_one_rel(PlannerInfo *root, List *joinlist)
Definition: allpaths.c:171
List * remove_useless_joins(PlannerInfo *root, List *joinlist)
Definition: analyzejoins.c:88
List * remove_useless_self_joins(PlannerInfo *root, List *joinlist)
void reduce_unique_semijoins(PlannerInfo *root)
Definition: analyzejoins.c:819
void distribute_row_identity_vars(PlannerInfo *root)
Definition: appendinfo.c:985
bool is_parallel_safe(PlannerInfo *root, Node *node)
Definition: clauses.c:752
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
void generate_base_implied_equalities(PlannerInfo *root)
Definition: equivclass.c:1033
void reconsider_outer_join_clauses(PlannerInfo *root)
Definition: equivclass.c:2002
Assert(PointerIsAligned(start, uint64))
void match_foreign_keys_to_quals(PlannerInfo *root)
Definition: initsplan.c:3617
void find_lateral_references(PlannerInfo *root)
Definition: initsplan.c:658
void remove_useless_groupby_columns(PlannerInfo *root)
Definition: initsplan.c:412
void add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
Definition: initsplan.c:158
void build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
Definition: initsplan.c:235
List * deconstruct_jointree(PlannerInfo *root)
Definition: initsplan.c:1084
void add_other_rels_to_query(PlannerInfo *root)
Definition: initsplan.c:196
void create_lateral_join_info(PlannerInfo *root)
Definition: initsplan.c:845
#define IsA(nodeptr, _type_)
Definition: nodes.h:160
@ DEBUG_PARALLEL_OFF
Definition: optimizer.h:106
void extract_restriction_or_clauses(PlannerInfo *root)
Definition: orclauses.c:75
@ RTE_RESULT
Definition: parsenodes.h:1034
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:269
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:461
GroupResultPath * create_group_result_path(PlannerInfo *root, RelOptInfo *rel, PathTarget *target, List *havingqual)
Definition: pathnode.c:1586
static int list_length(const List *l)
Definition: pg_list.h:152
#define NIL
Definition: pg_list.h:68
#define linitial(l)
Definition: pg_list.h:178
void add_placeholders_to_base_rels(PlannerInfo *root)
Definition: placeholder.c:356
void fix_placeholder_input_needed_levels(PlannerInfo *root)
Definition: placeholder.c:300
void find_placeholders_in_jointree(PlannerInfo *root)
Definition: placeholder.c:185
RelOptInfo * query_planner(PlannerInfo *root, query_pathkeys_callback qp_callback, void *qp_extra)
Definition: planmain.c:54
void(* query_pathkeys_callback)(PlannerInfo *root, void *extra)
Definition: planmain.h:26
int debug_parallel_query
Definition: planner.c:68
tree ctl root
Definition: radixtree.h:1857
static struct subre * parse(struct vars *v, int stopper, int type, struct state *init, struct state *final)
Definition: regcomp.c:717
void setup_simple_rel_arrays(PlannerInfo *root)
Definition: relnode.c:94
RelOptInfo * build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
Definition: relnode.c:192
Definition: pg_list.h:54
Definition: nodes.h:131
RTEKind rtekind
Definition: parsenodes.h:1056
struct PathTarget * reltarget
Definition: pathnodes.h:920
bool consider_parallel
Definition: pathnodes.h:914
struct Path * cheapest_total_path
Definition: pathnodes.h:929