| 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 |
|
| 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 * |
| 54 |
query_planner(PlannerInfo *root, |
| 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 |
*/ |
| 85 |
setup_simple_rel_arrays(root); |
| 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 || |
| 124 |
debug_parallel_query != DEBUG_PARALLEL_OFF)) |
| 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 *) |
| 137 |
create_group_result_path(root, final_rel, |
| 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 */ |
| 173 |
remove_useless_groupby_columns(root); |
| 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 |
|
| 187 |
find_placeholders_in_jointree(root); |
| 188 |
|
| 189 |
find_lateral_references(root); |
| 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 |
*/ |
| 198 |
reconsider_outer_join_clauses(root); |
| 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 |
*/ |
| 205 |
generate_base_implied_equalities(root); |
| 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 |
*/ |
| 221 |
fix_placeholder_input_needed_levels(root); |
| 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 |
*/ |
| 234 |
reduce_unique_semijoins(root); |
| 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 |
*/ |
| 246 |
add_placeholders_to_base_rels(root); |
| 247 |
|
| 248 |
/* |
| 249 |
* Construct the lateral reference sets now that we have finalized |
| 250 |
* PlaceHolderVar eval levels. |
| 251 |
*/ |
| 252 |
create_lateral_join_info(root); |
| 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 |
*/ |
| 260 |
match_foreign_keys_to_quals(root); |
| 261 |
|
| 262 |
/* |
| 263 |
* Look for join OR clauses that we can extract single-relation |
| 264 |
* restriction OR clauses from. |
| 265 |
*/ |
| 266 |
extract_restriction_or_clauses(root); |
| 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 |
*/ |
| 276 |
add_other_rels_to_query(root); |
| 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 |
*/ |
| 283 |
distribute_row_identity_vars(root); |
| 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 |
} |