1
/*-------------------------------------------------------------------------
4
* Planner preprocessing for subqueries and join tree manipulation.
6
* NOTE: the intended sequence for invoking these operations is
9
* do expression preprocessing (including flattening JOIN alias vars)
14
* Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
15
* Portions Copyright (c) 1994, Regents of the University of California
19
* $PostgreSQL: pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.25 2004-12-31 22:00:20 pgsql Exp $
21
*-------------------------------------------------------------------------
25
#include "optimizer/clauses.h"
26
#include "optimizer/prep.h"
27
#include "optimizer/subselect.h"
28
#include "optimizer/var.h"
29
#include "parser/parsetree.h"
30
#include "rewrite/rewriteManip.h"
31
#include "utils/lsyscache.h"
34
/* These parameters are set by GUC */
35
int from_collapse_limit;
36
int join_collapse_limit;
39
typedef struct reduce_outer_joins_state
41
Relids relids; /* base relids within this subtree */
42
bool contains_outer; /* does subtree contain outer join(s)? */
43
List *sub_states; /* List of states for subtree components */
44
} reduce_outer_joins_state;
46
static bool is_simple_subquery(Query *subquery);
47
static bool has_nullable_targetlist(Query *subquery);
48
static void resolvenew_in_jointree(Node *jtnode, int varno,
49
List *rtable, List *subtlist);
50
static reduce_outer_joins_state *reduce_outer_joins_pass1(Node *jtnode);
51
static void reduce_outer_joins_pass2(Node *jtnode,
52
reduce_outer_joins_state *state,
54
Relids nonnullable_rels);
55
static Relids find_nonnullable_rels(Node *node, bool top_level);
56
static void fix_in_clause_relids(List *in_info_list, int varno,
58
static Node *find_jointree_node_for_rel(Node *jtnode, int relid);
63
* Attempt to pull up top-level IN clauses to be treated like joins.
65
* A clause "foo IN (sub-SELECT)" appearing at the top level of WHERE can
66
* be processed by pulling the sub-SELECT up to become a rangetable entry
67
* and handling the implied equality comparisons as join operators (with
68
* special join rules).
69
* This optimization *only* works at the top level of WHERE, because
70
* it cannot distinguish whether the IN ought to return FALSE or NULL in
71
* cases involving NULL inputs. This routine searches for such clauses
72
* and does the necessary parsetree transformations if any are found.
74
* This routine has to run before preprocess_expression(), so the WHERE
75
* clause is not yet reduced to implicit-AND format. That means we need
76
* to recursively search through explicit AND clauses, which are
77
* probably only binary ANDs. We stop as soon as we hit a non-AND item.
79
* Returns the possibly-modified version of the given qual-tree node.
82
pull_up_IN_clauses(Query *parse, Node *node)
86
if (IsA(node, SubLink))
88
SubLink *sublink = (SubLink *) node;
91
/* Is it a convertible IN clause? If not, return it as-is */
92
subst = convert_IN_to_join(parse, sublink);
99
List *newclauses = NIL;
102
foreach(l, ((BoolExpr *) node)->args)
104
Node *oldclause = (Node *) lfirst(l);
106
newclauses = lappend(newclauses,
107
pull_up_IN_clauses(parse,
110
return (Node *) make_andclause(newclauses);
112
/* Stop if not an AND */
118
* Look for subqueries in the rangetable that can be pulled up into
119
* the parent query. If the subquery has no special features like
120
* grouping/aggregation then we can merge it into the parent's jointree.
122
* below_outer_join is true if this jointree node is within the nullable
123
* side of an outer join. This restricts what we can do.
125
* A tricky aspect of this code is that if we pull up a subquery we have
126
* to replace Vars that reference the subquery's outputs throughout the
127
* parent query, including quals attached to jointree nodes above the one
128
* we are currently processing! We handle this by being careful not to
129
* change the jointree structure while recursing: no nodes other than
130
* subquery RangeTblRef entries will be replaced. Also, we can't turn
131
* ResolveNew loose on the whole jointree, because it'll return a mutated
132
* copy of the tree; we have to invoke it just on the quals, instead.
135
pull_up_subqueries(Query *parse, Node *jtnode, bool below_outer_join)
139
if (IsA(jtnode, RangeTblRef))
141
int varno = ((RangeTblRef *) jtnode)->rtindex;
142
RangeTblEntry *rte = rt_fetch(varno, parse->rtable);
143
Query *subquery = rte->subquery;
146
* Is this a subquery RTE, and if so, is the subquery simple
147
* enough to pull up? (If not, do nothing at this node.)
149
* If we are inside an outer join, only pull up subqueries whose
150
* targetlists are nullable --- otherwise substituting their tlist
151
* entries for upper Var references would do the wrong thing (the
152
* results wouldn't become NULL when they're supposed to).
154
* XXX This could be improved by generating pseudo-variables for such
155
* expressions; we'd have to figure out how to get the pseudo-
156
* variables evaluated at the right place in the modified plan
157
* tree. Fix it someday.
159
if (rte->rtekind == RTE_SUBQUERY &&
160
is_simple_subquery(subquery) &&
161
(!below_outer_join || has_nullable_targetlist(subquery)))
168
* Need a modifiable copy of the subquery to hack on. Even if
169
* we didn't sometimes choose not to pull up below, we must do
170
* this to avoid problems if the same subquery is referenced
171
* from multiple jointree items (which can't happen normally,
172
* but might after rule rewriting).
174
subquery = copyObject(subquery);
177
* Pull up any IN clauses within the subquery's WHERE, so that
178
* we don't leave unoptimized INs behind.
180
if (subquery->hasSubLinks)
181
subquery->jointree->quals = pull_up_IN_clauses(subquery,
182
subquery->jointree->quals);
185
* Recursively pull up the subquery's subqueries, so that this
186
* routine's processing is complete for its jointree and
189
* Note: 'false' is correct here even if we are within an outer
190
* join in the upper query; the lower query starts with a
191
* clean slate for outer-join semantics.
193
subquery->jointree = (FromExpr *)
194
pull_up_subqueries(subquery, (Node *) subquery->jointree,
198
* Now we must recheck whether the subquery is still simple
199
* enough to pull up. If not, abandon processing it.
201
* We don't really need to recheck all the conditions involved,
202
* but it's easier just to keep this "if" looking the same as
205
if (is_simple_subquery(subquery) &&
206
(!below_outer_join || has_nullable_targetlist(subquery)))
213
* Give up, return unmodified RangeTblRef.
215
* Note: The work we just did will be redone when the
216
* subquery gets planned on its own. Perhaps we could
217
* avoid that by storing the modified subquery back into
218
* the rangetable, but I'm not gonna risk it now.
224
* Adjust level-0 varnos in subquery so that we can append its
225
* rangetable to upper query's.
227
rtoffset = list_length(parse->rtable);
228
OffsetVarNodes((Node *) subquery, rtoffset, 0);
231
* Upper-level vars in subquery are now one level closer to
232
* their parent than before.
234
IncrementVarSublevelsUp((Node *) subquery, -1, 1);
237
* Replace all of the top query's references to the subquery's
238
* outputs with copies of the adjusted subtlist items, being
239
* careful not to replace any of the jointree structure.
240
* (This'd be a lot cleaner if we could use
241
* query_tree_mutator.)
243
subtlist = subquery->targetList;
244
parse->targetList = (List *)
245
ResolveNew((Node *) parse->targetList,
246
varno, 0, parse->rtable,
247
subtlist, CMD_SELECT, 0);
248
resolvenew_in_jointree((Node *) parse->jointree, varno,
249
parse->rtable, subtlist);
250
Assert(parse->setOperations == NULL);
252
ResolveNew(parse->havingQual,
253
varno, 0, parse->rtable,
254
subtlist, CMD_SELECT, 0);
255
parse->in_info_list = (List *)
256
ResolveNew((Node *) parse->in_info_list,
257
varno, 0, parse->rtable,
258
subtlist, CMD_SELECT, 0);
260
foreach(rt, parse->rtable)
262
RangeTblEntry *otherrte = (RangeTblEntry *) lfirst(rt);
264
if (otherrte->rtekind == RTE_JOIN)
265
otherrte->joinaliasvars = (List *)
266
ResolveNew((Node *) otherrte->joinaliasvars,
267
varno, 0, parse->rtable,
268
subtlist, CMD_SELECT, 0);
272
* Now append the adjusted rtable entries to upper query. (We
273
* hold off until after fixing the upper rtable entries; no
274
* point in running that code on the subquery ones too.)
276
parse->rtable = list_concat(parse->rtable, subquery->rtable);
279
* Pull up any FOR UPDATE markers, too. (OffsetVarNodes
280
* already adjusted the marker values, so just list_concat the
283
parse->rowMarks = list_concat(parse->rowMarks, subquery->rowMarks);
286
* We also have to fix the relid sets of any parent
287
* InClauseInfo nodes. (This could perhaps be done by
288
* ResolveNew, but it would clutter that routine's API
291
if (parse->in_info_list)
295
subrelids = get_relids_in_jointree((Node *) subquery->jointree);
296
fix_in_clause_relids(parse->in_info_list, varno, subrelids);
300
* And now append any subquery InClauseInfos to our list.
302
parse->in_info_list = list_concat(parse->in_info_list,
303
subquery->in_info_list);
306
* Miscellaneous housekeeping.
308
parse->hasSubLinks |= subquery->hasSubLinks;
309
/* subquery won't be pulled up if it hasAggs, so no work there */
312
* Return the adjusted subquery jointree to replace the
313
* RangeTblRef entry in my jointree.
315
return (Node *) subquery->jointree;
318
else if (IsA(jtnode, FromExpr))
320
FromExpr *f = (FromExpr *) jtnode;
323
foreach(l, f->fromlist)
324
lfirst(l) = pull_up_subqueries(parse, lfirst(l),
327
else if (IsA(jtnode, JoinExpr))
329
JoinExpr *j = (JoinExpr *) jtnode;
331
/* Recurse, being careful to tell myself when inside outer join */
335
j->larg = pull_up_subqueries(parse, j->larg,
337
j->rarg = pull_up_subqueries(parse, j->rarg,
341
j->larg = pull_up_subqueries(parse, j->larg,
343
j->rarg = pull_up_subqueries(parse, j->rarg,
347
j->larg = pull_up_subqueries(parse, j->larg,
349
j->rarg = pull_up_subqueries(parse, j->rarg,
353
j->larg = pull_up_subqueries(parse, j->larg,
355
j->rarg = pull_up_subqueries(parse, j->rarg,
361
* This is where we fail if upper levels of planner
362
* haven't rewritten UNION JOIN as an Append ...
365
(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
366
errmsg("UNION JOIN is not implemented")));
369
elog(ERROR, "unrecognized join type: %d",
375
elog(ERROR, "unrecognized node type: %d",
376
(int) nodeTag(jtnode));
382
* Check a subquery in the range table to see if it's simple enough
383
* to pull up into the parent query.
386
is_simple_subquery(Query *subquery)
389
* Let's just make sure it's a valid subselect ...
391
if (!IsA(subquery, Query) ||
392
subquery->commandType != CMD_SELECT ||
393
subquery->resultRelation != 0 ||
394
subquery->into != NULL)
395
elog(ERROR, "subquery is bogus");
398
* Can't currently pull up a query with setops. Maybe after querytree
401
if (subquery->setOperations)
405
* Can't pull up a subquery involving grouping, aggregation, sorting,
408
if (subquery->hasAggs ||
409
subquery->groupClause ||
410
subquery->havingQual ||
411
subquery->sortClause ||
412
subquery->distinctClause ||
413
subquery->limitOffset ||
414
subquery->limitCount)
418
* Don't pull up a subquery that has any set-returning functions in
419
* its targetlist. Otherwise we might well wind up inserting
420
* set-returning functions into places where they mustn't go, such as
421
* quals of higher queries.
423
if (expression_returns_set((Node *) subquery->targetList))
427
* Hack: don't try to pull up a subquery with an empty jointree.
428
* query_planner() will correctly generate a Result plan for a
429
* jointree that's totally empty, but I don't think the right things
430
* happen if an empty FromExpr appears lower down in a jointree. Not
431
* worth working hard on this, just to collapse SubqueryScan/Result
434
if (subquery->jointree->fromlist == NIL)
441
* has_nullable_targetlist
442
* Check a subquery in the range table to see if all the non-junk
443
* targetlist items are simple variables or strict functions of simple
444
* variables (and, hence, will correctly go to NULL when examined above
445
* the point of an outer join).
447
* NOTE: it would be correct (and useful) to ignore output columns that aren't
448
* actually referenced by the enclosing query ... but we do not have that
449
* information available at this point.
452
has_nullable_targetlist(Query *subquery)
456
foreach(l, subquery->targetList)
458
TargetEntry *tle = (TargetEntry *) lfirst(l);
460
/* ignore resjunk columns */
461
if (tle->resdom->resjunk)
464
/* Must contain a Var of current level */
465
if (!contain_vars_of_level((Node *) tle->expr, 0))
468
/* Must not contain any non-strict constructs */
469
if (contain_nonstrict_functions((Node *) tle->expr))
472
/* This one's OK, keep scanning */
478
* Helper routine for pull_up_subqueries: do ResolveNew on every expression
479
* in the jointree, without changing the jointree structure itself. Ugly,
480
* but there's no other way...
483
resolvenew_in_jointree(Node *jtnode, int varno,
484
List *rtable, List *subtlist)
488
if (IsA(jtnode, RangeTblRef))
490
/* nothing to do here */
492
else if (IsA(jtnode, FromExpr))
494
FromExpr *f = (FromExpr *) jtnode;
497
foreach(l, f->fromlist)
498
resolvenew_in_jointree(lfirst(l), varno, rtable, subtlist);
499
f->quals = ResolveNew(f->quals,
501
subtlist, CMD_SELECT, 0);
503
else if (IsA(jtnode, JoinExpr))
505
JoinExpr *j = (JoinExpr *) jtnode;
507
resolvenew_in_jointree(j->larg, varno, rtable, subtlist);
508
resolvenew_in_jointree(j->rarg, varno, rtable, subtlist);
509
j->quals = ResolveNew(j->quals,
511
subtlist, CMD_SELECT, 0);
514
* We don't bother to update the colvars list, since it won't be
519
elog(ERROR, "unrecognized node type: %d",
520
(int) nodeTag(jtnode));
525
* Attempt to reduce outer joins to plain inner joins.
527
* The idea here is that given a query like
528
* SELECT ... FROM a LEFT JOIN b ON (...) WHERE b.y = 42;
529
* we can reduce the LEFT JOIN to a plain JOIN if the "=" operator in WHERE
530
* is strict. The strict operator will always return NULL, causing the outer
531
* WHERE to fail, on any row where the LEFT JOIN filled in NULLs for b's
532
* columns. Therefore, there's no need for the join to produce null-extended
533
* rows in the first place --- which makes it a plain join not an outer join.
534
* (This scenario may not be very likely in a query written out by hand, but
535
* it's reasonably likely when pushing quals down into complex views.)
537
* More generally, an outer join can be reduced in strength if there is a
538
* strict qual above it in the qual tree that constrains a Var from the
539
* nullable side of the join to be non-null. (For FULL joins this applies
540
* to each side separately.)
542
* To ease recognition of strict qual clauses, we require this routine to be
543
* run after expression preprocessing (i.e., qual canonicalization and JOIN
544
* alias-var expansion).
547
reduce_outer_joins(Query *parse)
549
reduce_outer_joins_state *state;
552
* To avoid doing strictness checks on more quals than necessary, we
553
* want to stop descending the jointree as soon as there are no outer
554
* joins below our current point. This consideration forces a
555
* two-pass process. The first pass gathers information about which
556
* base rels appear below each side of each join clause, and about
557
* whether there are outer join(s) below each side of each join
558
* clause. The second pass examines qual clauses and changes join
559
* types as it descends the tree.
561
state = reduce_outer_joins_pass1((Node *) parse->jointree);
563
/* planner.c shouldn't have called me if no outer joins */
564
if (state == NULL || !state->contains_outer)
565
elog(ERROR, "so where are the outer joins?");
567
reduce_outer_joins_pass2((Node *) parse->jointree, state, parse, NULL);
571
* reduce_outer_joins_pass1 - phase 1 data collection
573
* Returns a state node describing the given jointree node.
575
static reduce_outer_joins_state *
576
reduce_outer_joins_pass1(Node *jtnode)
578
reduce_outer_joins_state *result;
580
result = (reduce_outer_joins_state *)
581
palloc(sizeof(reduce_outer_joins_state));
582
result->relids = NULL;
583
result->contains_outer = false;
584
result->sub_states = NIL;
588
if (IsA(jtnode, RangeTblRef))
590
int varno = ((RangeTblRef *) jtnode)->rtindex;
592
result->relids = bms_make_singleton(varno);
594
else if (IsA(jtnode, FromExpr))
596
FromExpr *f = (FromExpr *) jtnode;
599
foreach(l, f->fromlist)
601
reduce_outer_joins_state *sub_state;
603
sub_state = reduce_outer_joins_pass1(lfirst(l));
604
result->relids = bms_add_members(result->relids,
606
result->contains_outer |= sub_state->contains_outer;
607
result->sub_states = lappend(result->sub_states, sub_state);
610
else if (IsA(jtnode, JoinExpr))
612
JoinExpr *j = (JoinExpr *) jtnode;
613
reduce_outer_joins_state *sub_state;
615
/* join's own RT index is not wanted in result->relids */
616
if (IS_OUTER_JOIN(j->jointype))
617
result->contains_outer = true;
619
sub_state = reduce_outer_joins_pass1(j->larg);
620
result->relids = bms_add_members(result->relids,
622
result->contains_outer |= sub_state->contains_outer;
623
result->sub_states = lappend(result->sub_states, sub_state);
625
sub_state = reduce_outer_joins_pass1(j->rarg);
626
result->relids = bms_add_members(result->relids,
628
result->contains_outer |= sub_state->contains_outer;
629
result->sub_states = lappend(result->sub_states, sub_state);
632
elog(ERROR, "unrecognized node type: %d",
633
(int) nodeTag(jtnode));
638
* reduce_outer_joins_pass2 - phase 2 processing
640
* jtnode: current jointree node
641
* state: state data collected by phase 1 for this node
642
* parse: toplevel Query
643
* nonnullable_rels: set of base relids forced non-null by upper quals
646
reduce_outer_joins_pass2(Node *jtnode,
647
reduce_outer_joins_state *state,
649
Relids nonnullable_rels)
652
* pass 2 should never descend as far as an empty subnode or base rel,
653
* because it's only called on subtrees marked as contains_outer.
656
elog(ERROR, "reached empty jointree");
657
if (IsA(jtnode, RangeTblRef))
658
elog(ERROR, "reached base rel");
659
else if (IsA(jtnode, FromExpr))
661
FromExpr *f = (FromExpr *) jtnode;
664
Relids pass_nonnullable;
666
/* Scan quals to see if we can add any nonnullability constraints */
667
pass_nonnullable = find_nonnullable_rels(f->quals, true);
668
pass_nonnullable = bms_add_members(pass_nonnullable,
670
/* And recurse --- but only into interesting subtrees */
671
Assert(list_length(f->fromlist) == list_length(state->sub_states));
672
forboth(l, f->fromlist, s, state->sub_states)
674
reduce_outer_joins_state *sub_state = lfirst(s);
676
if (sub_state->contains_outer)
677
reduce_outer_joins_pass2(lfirst(l), sub_state, parse,
680
bms_free(pass_nonnullable);
682
else if (IsA(jtnode, JoinExpr))
684
JoinExpr *j = (JoinExpr *) jtnode;
685
int rtindex = j->rtindex;
686
JoinType jointype = j->jointype;
687
reduce_outer_joins_state *left_state = linitial(state->sub_states);
688
reduce_outer_joins_state *right_state = lsecond(state->sub_states);
690
/* Can we simplify this join? */
694
if (bms_overlap(nonnullable_rels, right_state->relids))
695
jointype = JOIN_INNER;
698
if (bms_overlap(nonnullable_rels, left_state->relids))
699
jointype = JOIN_INNER;
702
if (bms_overlap(nonnullable_rels, left_state->relids))
704
if (bms_overlap(nonnullable_rels, right_state->relids))
705
jointype = JOIN_INNER;
707
jointype = JOIN_LEFT;
711
if (bms_overlap(nonnullable_rels, right_state->relids))
712
jointype = JOIN_RIGHT;
718
if (jointype != j->jointype)
720
/* apply the change to both jointree node and RTE */
721
RangeTblEntry *rte = rt_fetch(rtindex, parse->rtable);
723
Assert(rte->rtekind == RTE_JOIN);
724
Assert(rte->jointype == j->jointype);
725
rte->jointype = j->jointype = jointype;
728
/* Only recurse if there's more to do below here */
729
if (left_state->contains_outer || right_state->contains_outer)
731
Relids local_nonnullable;
732
Relids pass_nonnullable;
735
* If this join is (now) inner, we can add any nonnullability
736
* constraints its quals provide to those we got from above.
737
* But if it is outer, we can only pass down the local
738
* constraints into the nullable side, because an outer join
739
* never eliminates any rows from its non-nullable side. If
740
* it's a FULL join then it doesn't eliminate anything from
743
if (jointype != JOIN_FULL)
745
local_nonnullable = find_nonnullable_rels(j->quals, true);
746
local_nonnullable = bms_add_members(local_nonnullable,
750
local_nonnullable = NULL; /* no use in calculating
753
if (left_state->contains_outer)
755
if (jointype == JOIN_INNER || jointype == JOIN_RIGHT)
756
pass_nonnullable = local_nonnullable;
758
pass_nonnullable = nonnullable_rels;
759
reduce_outer_joins_pass2(j->larg, left_state, parse,
762
if (right_state->contains_outer)
764
if (jointype == JOIN_INNER || jointype == JOIN_LEFT)
765
pass_nonnullable = local_nonnullable;
767
pass_nonnullable = nonnullable_rels;
768
reduce_outer_joins_pass2(j->rarg, right_state, parse,
771
bms_free(local_nonnullable);
775
elog(ERROR, "unrecognized node type: %d",
776
(int) nodeTag(jtnode));
780
* find_nonnullable_rels
781
* Determine which base rels are forced nonnullable by given quals
783
* We don't use expression_tree_walker here because we don't want to
784
* descend through very many kinds of nodes; only the ones we can be sure
785
* are strict. We can descend through the top level of implicit AND'ing,
786
* but not through any explicit ANDs (or ORs) below that, since those are not
787
* strict constructs. The List case handles the top-level implicit AND list
788
* as well as lists of arguments to strict operators/functions.
791
find_nonnullable_rels(Node *node, bool top_level)
793
Relids result = NULL;
799
Var *var = (Var *) node;
801
if (var->varlevelsup == 0)
802
result = bms_make_singleton(var->varno);
804
else if (IsA(node, List))
808
foreach(l, (List *) node)
810
result = bms_join(result, find_nonnullable_rels(lfirst(l),
814
else if (IsA(node, FuncExpr))
816
FuncExpr *expr = (FuncExpr *) node;
818
if (func_strict(expr->funcid))
819
result = find_nonnullable_rels((Node *) expr->args, false);
821
else if (IsA(node, OpExpr))
823
OpExpr *expr = (OpExpr *) node;
825
if (op_strict(expr->opno))
826
result = find_nonnullable_rels((Node *) expr->args, false);
828
else if (IsA(node, BoolExpr))
830
BoolExpr *expr = (BoolExpr *) node;
832
/* NOT is strict, others are not */
833
if (expr->boolop == NOT_EXPR)
834
result = find_nonnullable_rels((Node *) expr->args, false);
836
else if (IsA(node, RelabelType))
838
RelabelType *expr = (RelabelType *) node;
840
result = find_nonnullable_rels((Node *) expr->arg, top_level);
842
else if (IsA(node, ConvertRowtypeExpr))
844
/* not clear this is useful, but it can't hurt */
845
ConvertRowtypeExpr *expr = (ConvertRowtypeExpr *) node;
847
result = find_nonnullable_rels((Node *) expr->arg, top_level);
849
else if (IsA(node, NullTest))
851
NullTest *expr = (NullTest *) node;
854
* IS NOT NULL can be considered strict, but only at top level;
855
* else we might have something like NOT (x IS NOT NULL).
857
if (top_level && expr->nulltesttype == IS_NOT_NULL)
858
result = find_nonnullable_rels((Node *) expr->arg, false);
860
else if (IsA(node, BooleanTest))
862
BooleanTest *expr = (BooleanTest *) node;
865
* Appropriate boolean tests are strict at top level.
868
(expr->booltesttype == IS_TRUE ||
869
expr->booltesttype == IS_FALSE ||
870
expr->booltesttype == IS_NOT_UNKNOWN))
871
result = find_nonnullable_rels((Node *) expr->arg, false);
878
* Attempt to simplify a query's jointree.
880
* If we succeed in pulling up a subquery then we might form a jointree
881
* in which a FromExpr is a direct child of another FromExpr. In that
882
* case we can consider collapsing the two FromExprs into one. This is
883
* an optional conversion, since the planner will work correctly either
884
* way. But we may find a better plan (at the cost of more planning time)
885
* if we merge the two nodes, creating a single join search space out of
886
* two. To allow the user to trade off planning time against plan quality,
887
* we provide a control parameter from_collapse_limit that limits the size
888
* of the join search space that can be created this way.
890
* We also consider flattening explicit inner JOINs into FromExprs (which
891
* will in turn allow them to be merged into parent FromExprs). The tradeoffs
892
* here are the same as for flattening FromExprs, but we use a different
893
* control parameter so that the user can use explicit JOINs to control the
894
* join order even when they are inner JOINs.
896
* NOTE: don't try to do this in the same jointree scan that does subquery
897
* pullup! Since we're changing the jointree structure here, that wouldn't
898
* work reliably --- see comments for pull_up_subqueries().
901
simplify_jointree(Query *parse, Node *jtnode)
905
if (IsA(jtnode, RangeTblRef))
907
/* nothing to do here... */
909
else if (IsA(jtnode, FromExpr))
911
FromExpr *f = (FromExpr *) jtnode;
913
int children_remaining;
916
children_remaining = list_length(f->fromlist);
917
foreach(l, f->fromlist)
919
Node *child = (Node *) lfirst(l);
921
children_remaining--;
922
/* Recursively simplify this child... */
923
child = simplify_jointree(parse, child);
924
/* Now, is it a FromExpr? */
925
if (child && IsA(child, FromExpr))
928
* Yes, so do we want to merge it into parent? Always do
929
* so if child has just one element (since that doesn't
930
* make the parent's list any longer). Otherwise merge if
931
* the resulting join list would be no longer than
932
* from_collapse_limit.
934
FromExpr *subf = (FromExpr *) child;
935
int childlen = list_length(subf->fromlist);
936
int myothers = list_length(newlist) + children_remaining;
939
(childlen + myothers) <= from_collapse_limit)
941
newlist = list_concat(newlist, subf->fromlist);
944
* By now, the quals have been converted to
945
* implicit-AND lists, so we just need to join the
946
* lists. NOTE: we put the pulled-up quals first.
948
f->quals = (Node *) list_concat((List *) subf->quals,
952
newlist = lappend(newlist, child);
955
newlist = lappend(newlist, child);
957
f->fromlist = newlist;
959
else if (IsA(jtnode, JoinExpr))
961
JoinExpr *j = (JoinExpr *) jtnode;
963
/* Recursively simplify the children... */
964
j->larg = simplify_jointree(parse, j->larg);
965
j->rarg = simplify_jointree(parse, j->rarg);
968
* If it is an outer join, we must not flatten it. An inner join
969
* is semantically equivalent to a FromExpr; we convert it to one,
970
* allowing it to be flattened into its parent, if the resulting
971
* FromExpr would have no more than join_collapse_limit members.
973
if (j->jointype == JOIN_INNER && join_collapse_limit > 1)
978
if (j->larg && IsA(j->larg, FromExpr))
979
leftlen = list_length(((FromExpr *) j->larg)->fromlist);
982
if (j->rarg && IsA(j->rarg, FromExpr))
983
rightlen = list_length(((FromExpr *) j->rarg)->fromlist);
986
if ((leftlen + rightlen) <= join_collapse_limit)
988
FromExpr *f = makeNode(FromExpr);
993
if (j->larg && IsA(j->larg, FromExpr))
995
FromExpr *subf = (FromExpr *) j->larg;
997
f->fromlist = subf->fromlist;
998
f->quals = subf->quals;
1001
f->fromlist = list_make1(j->larg);
1003
if (j->rarg && IsA(j->rarg, FromExpr))
1005
FromExpr *subf = (FromExpr *) j->rarg;
1007
f->fromlist = list_concat(f->fromlist,
1009
f->quals = (Node *) list_concat((List *) f->quals,
1010
(List *) subf->quals);
1013
f->fromlist = lappend(f->fromlist, j->rarg);
1015
/* pulled-up quals first */
1016
f->quals = (Node *) list_concat((List *) f->quals,
1024
elog(ERROR, "unrecognized node type: %d",
1025
(int) nodeTag(jtnode));
1030
* fix_in_clause_relids: update RT-index sets of InClauseInfo nodes
1032
* When we pull up a subquery, any InClauseInfo references to the subquery's
1033
* RT index have to be replaced by the set of substituted relids.
1035
* We assume we may modify the InClauseInfo nodes in-place.
1038
fix_in_clause_relids(List *in_info_list, int varno, Relids subrelids)
1042
foreach(l, in_info_list)
1044
InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
1046
if (bms_is_member(varno, ininfo->lefthand))
1048
ininfo->lefthand = bms_del_member(ininfo->lefthand, varno);
1049
ininfo->lefthand = bms_add_members(ininfo->lefthand, subrelids);
1051
if (bms_is_member(varno, ininfo->righthand))
1053
ininfo->righthand = bms_del_member(ininfo->righthand, varno);
1054
ininfo->righthand = bms_add_members(ininfo->righthand, subrelids);
1060
* get_relids_in_jointree: get set of base RT indexes present in a jointree
1063
get_relids_in_jointree(Node *jtnode)
1065
Relids result = NULL;
1069
if (IsA(jtnode, RangeTblRef))
1071
int varno = ((RangeTblRef *) jtnode)->rtindex;
1073
result = bms_make_singleton(varno);
1075
else if (IsA(jtnode, FromExpr))
1077
FromExpr *f = (FromExpr *) jtnode;
1080
foreach(l, f->fromlist)
1082
result = bms_join(result,
1083
get_relids_in_jointree(lfirst(l)));
1086
else if (IsA(jtnode, JoinExpr))
1088
JoinExpr *j = (JoinExpr *) jtnode;
1090
/* join's own RT index is not wanted in result */
1091
result = get_relids_in_jointree(j->larg);
1092
result = bms_join(result, get_relids_in_jointree(j->rarg));
1095
elog(ERROR, "unrecognized node type: %d",
1096
(int) nodeTag(jtnode));
1101
* get_relids_for_join: get set of base RT indexes making up a join
1103
* NB: this will not work reliably after simplify_jointree() is run,
1104
* since that may eliminate join nodes from the jointree.
1107
get_relids_for_join(Query *parse, int joinrelid)
1111
jtnode = find_jointree_node_for_rel((Node *) parse->jointree, joinrelid);
1113
elog(ERROR, "could not find join node %d", joinrelid);
1114
return get_relids_in_jointree(jtnode);
1118
* find_jointree_node_for_rel: locate jointree node for a base or join RT index
1120
* Returns NULL if not found
1123
find_jointree_node_for_rel(Node *jtnode, int relid)
1127
if (IsA(jtnode, RangeTblRef))
1129
int varno = ((RangeTblRef *) jtnode)->rtindex;
1134
else if (IsA(jtnode, FromExpr))
1136
FromExpr *f = (FromExpr *) jtnode;
1139
foreach(l, f->fromlist)
1141
jtnode = find_jointree_node_for_rel(lfirst(l), relid);
1146
else if (IsA(jtnode, JoinExpr))
1148
JoinExpr *j = (JoinExpr *) jtnode;
1150
if (relid == j->rtindex)
1152
jtnode = find_jointree_node_for_rel(j->larg, relid);
1155
jtnode = find_jointree_node_for_rel(j->rarg, relid);
1160
elog(ERROR, "unrecognized node type: %d",
1161
(int) nodeTag(jtnode));
added
removed
src/backend/optimizer/prep/prepjointree.c
