Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb4c806f

Browse files
committed
Rewrite make_outerjoininfo's construction of min_lefthand and min_righthand
sets for outer joins, in the light of bug #3588 and additional thought andexperimentation. The original methodology was fatally flawed for nests ofmore than two outer joins: it got the relationships between adjacent joinsright, but didn't always come to the right conclusions about whether a joincould be interchanged with one two or more levels below it. This was largelycaused by a mistaken idea that we should use the min_lefthand + min_righthandsets of a sub-join as the minimum left or right input set of an upper joinwhen we conclude that the sub-join can't commute with the upper one. Ifthere's a still-lower join that the sub-join *can* commute with, this methodled us to think that that one could commute with the topmost join; which itcan't. Another problem (not directly connected to bug #3588) was thatmake_outerjoininfo's processing-order-dependent method for enforcing outerjoin identity#3 didn't work right: if we decided that join A could safelycommute with lower join B, we dropped all information about sub-joins under Bthat join A could perhaps not safely commute with, because we removed B'sentire min_righthand from A's.To fix, make an explicit computation of all inner join combinations that occurbelow an outer join, and add to that the full syntactic relsets of any lowerouter joins that we determine it can't commute with. This method gives muchmore direct enforcement of the outer join rearrangement identities, and itturns out not to cost a lot of additional bookkeeping.Thanks to Richard Harris for the bug report and test case.
1 parent24cba4e commitb4c806f

File tree

8 files changed

+189
-51
lines changed

8 files changed

+189
-51
lines changed

‎src/backend/nodes/copyfuncs.c‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515
* Portions Copyright (c) 1994, Regents of the University of California
1616
*
1717
* IDENTIFICATION
18-
* $PostgreSQL: pgsql/src/backend/nodes/copyfuncs.c,v 1.380 2007/07/17 05:02:01 neilc Exp $
18+
* $PostgreSQL: pgsql/src/backend/nodes/copyfuncs.c,v 1.381 2007/08/31 01:44:05 tgl Exp $
1919
*
2020
*-------------------------------------------------------------------------
2121
*/
@@ -1453,6 +1453,8 @@ _copyOuterJoinInfo(OuterJoinInfo *from)
14531453

14541454
COPY_BITMAPSET_FIELD(min_lefthand);
14551455
COPY_BITMAPSET_FIELD(min_righthand);
1456+
COPY_BITMAPSET_FIELD(syn_lefthand);
1457+
COPY_BITMAPSET_FIELD(syn_righthand);
14561458
COPY_SCALAR_FIELD(is_full_join);
14571459
COPY_SCALAR_FIELD(lhs_strict);
14581460
COPY_SCALAR_FIELD(delay_upper_joins);

‎src/backend/nodes/equalfuncs.c‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@
1818
* Portions Copyright (c) 1994, Regents of the University of California
1919
*
2020
* IDENTIFICATION
21-
* $PostgreSQL: pgsql/src/backend/nodes/equalfuncs.c,v 1.311 2007/07/17 05:02:01 neilc Exp $
21+
* $PostgreSQL: pgsql/src/backend/nodes/equalfuncs.c,v 1.312 2007/08/31 01:44:05 tgl Exp $
2222
*
2323
*-------------------------------------------------------------------------
2424
*/
@@ -706,6 +706,8 @@ _equalOuterJoinInfo(OuterJoinInfo *a, OuterJoinInfo *b)
706706
{
707707
COMPARE_BITMAPSET_FIELD(min_lefthand);
708708
COMPARE_BITMAPSET_FIELD(min_righthand);
709+
COMPARE_BITMAPSET_FIELD(syn_lefthand);
710+
COMPARE_BITMAPSET_FIELD(syn_righthand);
709711
COMPARE_SCALAR_FIELD(is_full_join);
710712
COMPARE_SCALAR_FIELD(lhs_strict);
711713
COMPARE_SCALAR_FIELD(delay_upper_joins);

‎src/backend/nodes/outfuncs.c‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.313 2007/07/17 05:02:01 neilc Exp $
11+
* $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.314 2007/08/31 01:44:05 tgl Exp $
1212
*
1313
* NOTES
1414
* Every node type that can appear in stored rules' parsetrees *must*
@@ -1471,6 +1471,8 @@ _outOuterJoinInfo(StringInfo str, OuterJoinInfo *node)
14711471

14721472
WRITE_BITMAPSET_FIELD(min_lefthand);
14731473
WRITE_BITMAPSET_FIELD(min_righthand);
1474+
WRITE_BITMAPSET_FIELD(syn_lefthand);
1475+
WRITE_BITMAPSET_FIELD(syn_righthand);
14741476
WRITE_BOOL_FIELD(is_full_join);
14751477
WRITE_BOOL_FIELD(lhs_strict);
14761478
WRITE_BOOL_FIELD(delay_upper_joins);

‎src/backend/optimizer/plan/initsplan.c‎

Lines changed: 102 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/plan/initsplan.c,v 1.132 2007/05/22 23:23:56 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/plan/initsplan.c,v 1.133 2007/08/31 01:44:05 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -38,9 +38,11 @@ intjoin_collapse_limit;
3838

3939

4040
staticList*deconstruct_recurse(PlannerInfo*root,Node*jtnode,
41-
boolbelow_outer_join,Relids*qualscope);
41+
boolbelow_outer_join,
42+
Relids*qualscope,Relids*inner_join_rels);
4243
staticOuterJoinInfo*make_outerjoininfo(PlannerInfo*root,
4344
Relidsleft_rels,Relidsright_rels,
45+
Relidsinner_join_rels,
4446
boolis_full_join,Node*clause);
4547
staticvoiddistribute_qual_to_rels(PlannerInfo*root,Node*clause,
4648
boolis_deduced,
@@ -204,13 +206,14 @@ List *
204206
deconstruct_jointree(PlannerInfo*root)
205207
{
206208
Relidsqualscope;
209+
Relidsinner_join_rels;
207210

208211
/* Start recursion at top of jointree */
209212
Assert(root->parse->jointree!=NULL&&
210213
IsA(root->parse->jointree,FromExpr));
211214

212215
returndeconstruct_recurse(root, (Node*)root->parse->jointree, false,
213-
&qualscope);
216+
&qualscope,&inner_join_rels);
214217
}
215218

216219
/*
@@ -224,20 +227,24 @@ deconstruct_jointree(PlannerInfo *root)
224227
* Outputs:
225228
**qualscope gets the set of base Relids syntactically included in this
226229
*jointree node (do not modify or free this, as it may also be pointed
227-
*to by RestrictInfo nodes)
230+
*to by RestrictInfo and OuterJoinInfo nodes)
231+
**inner_join_rels gets the set of base Relids syntactically included in
232+
*inner joins appearing at or below this jointree node (do not modify
233+
*or free this, either)
228234
*Return value is the appropriate joinlist for this jointree node
229235
*
230236
* In addition, entries will be added to root->oj_info_list for outer joins.
231237
*/
232238
staticList*
233239
deconstruct_recurse(PlannerInfo*root,Node*jtnode,boolbelow_outer_join,
234-
Relids*qualscope)
240+
Relids*qualscope,Relids*inner_join_rels)
235241
{
236242
List*joinlist;
237243

238244
if (jtnode==NULL)
239245
{
240246
*qualscope=NULL;
247+
*inner_join_rels=NULL;
241248
returnNIL;
242249
}
243250
if (IsA(jtnode,RangeTblRef))
@@ -246,6 +253,8 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
246253

247254
/* No quals to deal with, just return correct result */
248255
*qualscope=bms_make_singleton(varno);
256+
/* A single baserel does not create an inner join */
257+
*inner_join_rels=NULL;
249258
joinlist=list_make1(jtnode);
250259
}
251260
elseif (IsA(jtnode,FromExpr))
@@ -261,6 +270,7 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
261270
* subproblems, since that won't lengthen the joinlist anyway.
262271
*/
263272
*qualscope=NULL;
273+
*inner_join_rels=NULL;
264274
joinlist=NIL;
265275
remaining=list_length(f->fromlist);
266276
foreach(l,f->fromlist)
@@ -271,7 +281,8 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
271281

272282
sub_joinlist=deconstruct_recurse(root,lfirst(l),
273283
below_outer_join,
274-
&sub_qualscope);
284+
&sub_qualscope,
285+
inner_join_rels);
275286
*qualscope=bms_add_members(*qualscope,sub_qualscope);
276287
sub_members=list_length(sub_joinlist);
277288
remaining--;
@@ -282,6 +293,16 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
282293
joinlist=lappend(joinlist,sub_joinlist);
283294
}
284295

296+
/*
297+
* A FROM with more than one list element is an inner join subsuming
298+
* all below it, so we should report inner_join_rels = qualscope.
299+
* If there was exactly one element, we should (and already did) report
300+
* whatever its inner_join_rels were. If there were no elements
301+
* (is that possible?) the initialization before the loop fixed it.
302+
*/
303+
if (list_length(f->fromlist)>1)
304+
*inner_join_rels=*qualscope;
305+
285306
/*
286307
* Now process the top-level quals.
287308
*/
@@ -295,6 +316,8 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
295316
JoinExpr*j= (JoinExpr*)jtnode;
296317
Relidsleftids,
297318
rightids,
319+
left_inners,
320+
right_inners,
298321
nonnullable_rels,
299322
ojscope;
300323
List*leftjoinlist,
@@ -319,44 +342,48 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
319342
caseJOIN_INNER:
320343
leftjoinlist=deconstruct_recurse(root,j->larg,
321344
below_outer_join,
322-
&leftids);
345+
&leftids,&left_inners);
323346
rightjoinlist=deconstruct_recurse(root,j->rarg,
324347
below_outer_join,
325-
&rightids);
348+
&rightids,&right_inners);
326349
*qualscope=bms_union(leftids,rightids);
350+
*inner_join_rels=*qualscope;
327351
/* Inner join adds no restrictions for quals */
328352
nonnullable_rels=NULL;
329353
break;
330354
caseJOIN_LEFT:
331355
leftjoinlist=deconstruct_recurse(root,j->larg,
332356
below_outer_join,
333-
&leftids);
357+
&leftids,&left_inners);
334358
rightjoinlist=deconstruct_recurse(root,j->rarg,
335359
true,
336-
&rightids);
360+
&rightids,&right_inners);
337361
*qualscope=bms_union(leftids,rightids);
362+
*inner_join_rels=bms_union(left_inners,right_inners);
338363
nonnullable_rels=leftids;
339364
break;
340365
caseJOIN_FULL:
341366
leftjoinlist=deconstruct_recurse(root,j->larg,
342367
true,
343-
&leftids);
368+
&leftids,&left_inners);
344369
rightjoinlist=deconstruct_recurse(root,j->rarg,
345370
true,
346-
&rightids);
371+
&rightids,&right_inners);
347372
*qualscope=bms_union(leftids,rightids);
373+
*inner_join_rels=bms_union(left_inners,right_inners);
348374
/* each side is both outer and inner */
349375
nonnullable_rels=*qualscope;
350376
break;
351377
caseJOIN_RIGHT:
352378
/* notice we switch leftids and rightids */
353379
leftjoinlist=deconstruct_recurse(root,j->larg,
354380
true,
355-
&rightids);
381+
&rightids,&right_inners);
356382
rightjoinlist=deconstruct_recurse(root,j->rarg,
357383
below_outer_join,
358-
&leftids);
384+
&leftids,&left_inners);
359385
*qualscope=bms_union(leftids,rightids);
386+
*inner_join_rels=bms_union(left_inners,right_inners);
360387
nonnullable_rels=leftids;
361388
break;
362389
default:
@@ -375,8 +402,11 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
375402
*/
376403
if (j->jointype!=JOIN_INNER)
377404
{
378-
ojinfo=make_outerjoininfo(root,leftids,rightids,
379-
(j->jointype==JOIN_FULL),j->quals);
405+
ojinfo=make_outerjoininfo(root,
406+
leftids,rightids,
407+
*inner_join_rels,
408+
(j->jointype==JOIN_FULL),
409+
j->quals);
380410
ojscope=bms_union(ojinfo->min_lefthand,ojinfo->min_righthand);
381411
}
382412
else
@@ -445,6 +475,7 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
445475
* Inputs:
446476
*left_rels: the base Relids syntactically on outer side of join
447477
*right_rels: the base Relids syntactically on inner side of join
478+
*inner_join_rels: base Relids participating in inner joins below this one
448479
*is_full_join: what it says
449480
*clause: the outer join's join condition
450481
*
@@ -457,17 +488,19 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
457488
*
458489
* Note: we assume that this function is invoked bottom-up, so that
459490
* root->oj_info_list already contains entries for all outer joins that are
460-
* syntactically below this one; and indeed that oj_info_list is ordered
461-
* with syntactically lower joins listed first.
491+
* syntactically below this one.
462492
*/
463493
staticOuterJoinInfo*
464494
make_outerjoininfo(PlannerInfo*root,
465495
Relidsleft_rels,Relidsright_rels,
496+
Relidsinner_join_rels,
466497
boolis_full_join,Node*clause)
467498
{
468499
OuterJoinInfo*ojinfo=makeNode(OuterJoinInfo);
469500
Relidsclause_relids;
470501
Relidsstrict_relids;
502+
Relidsmin_lefthand;
503+
Relidsmin_righthand;
471504
ListCell*l;
472505

473506
/*
@@ -497,6 +530,8 @@ make_outerjoininfo(PlannerInfo *root,
497530
ojinfo->delay_upper_joins= false;
498531

499532
/* If it's a full join, no need to be very smart */
533+
ojinfo->syn_lefthand=left_rels;
534+
ojinfo->syn_righthand=right_rels;
500535
ojinfo->is_full_join=is_full_join;
501536
if (is_full_join)
502537
{
@@ -521,21 +556,17 @@ make_outerjoininfo(PlannerInfo *root,
521556
ojinfo->lhs_strict=bms_overlap(strict_relids,left_rels);
522557

523558
/*
524-
* Required LHS is basically the LHS rels mentioned in the clause... but
525-
* if there aren't any, punt and make it the full LHS, to avoid having an
526-
* empty min_lefthand which will confuse later processing. (We don't try
527-
* to be smart about such cases, just correct.) We may have to add more
528-
* rels based on lower outer joins; see below.
559+
* Required LHS always includes the LHS rels mentioned in the clause.
560+
* We may have to add more rels based on lower outer joins; see below.
529561
*/
530-
ojinfo->min_lefthand=bms_intersect(clause_relids,left_rels);
531-
if (bms_is_empty(ojinfo->min_lefthand))
532-
ojinfo->min_lefthand=bms_copy(left_rels);
562+
min_lefthand=bms_intersect(clause_relids,left_rels);
533563

534564
/*
535-
*Required RHS is normally the full set of RHS rels. Sometimes we can
536-
*exclude some, see below.
565+
*Similarly for required RHS. But here, we must also include any lower
566+
*inner joins, to ensure we don't try to commute with any of them.
537567
*/
538-
ojinfo->min_righthand=bms_copy(right_rels);
568+
min_righthand=bms_int_members(bms_union(clause_relids,inner_join_rels),
569+
right_rels);
539570

540571
foreach(l,root->oj_info_list)
541572
{
@@ -548,23 +579,29 @@ make_outerjoininfo(PlannerInfo *root,
548579
/*
549580
* For a lower OJ in our LHS, if our join condition uses the lower
550581
* join's RHS and is not strict for that rel, we must preserve the
551-
* ordering of the two OJs, so add lower OJ's full required relset to
552-
* min_lefthand.
582+
* ordering of the two OJs, so add lower OJ's full syntactic relset to
583+
* min_lefthand. (We must use its full syntactic relset, not just
584+
* its min_lefthand + min_righthand. This is because there might
585+
* be other OJs below this one that this one can commute with,
586+
* but we cannot commute with them if we don't with this one.)
587+
*
588+
* Note: I believe we have to insist on being strict for at least one
589+
* rel in the lower OJ's min_righthand, not its whole syn_righthand.
553590
*/
554-
if (bms_overlap(ojinfo->min_lefthand,otherinfo->min_righthand)&&
591+
if (bms_overlap(left_rels,otherinfo->syn_righthand)&&
555592
!bms_overlap(strict_relids,otherinfo->min_righthand))
556593
{
557-
ojinfo->min_lefthand=bms_add_members(ojinfo->min_lefthand,
558-
otherinfo->min_lefthand);
559-
ojinfo->min_lefthand=bms_add_members(ojinfo->min_lefthand,
560-
otherinfo->min_righthand);
594+
min_lefthand=bms_add_members(min_lefthand,
595+
otherinfo->syn_lefthand);
596+
min_lefthand=bms_add_members(min_lefthand,
597+
otherinfo->syn_righthand);
561598
}
562599

563600
/*
564601
* For a lower OJ in our RHS, if our join condition does not use the
565602
* lower join's RHS and the lower OJ's join condition is strict, we
566-
* can interchange the ordering of the two OJs, so exclude the lower
567-
*RHS from ourmin_righthand.
603+
* can interchange the ordering of the two OJs; otherwise we must
604+
*add lower OJ's full syntactic relset tomin_righthand.
568605
*
569606
* Here, we have to consider that "our join condition" includes
570607
* any clauses that syntactically appeared above the lower OJ and
@@ -577,20 +614,38 @@ make_outerjoininfo(PlannerInfo *root,
577614
* effect is therefore sufficiently represented by the
578615
* delay_upper_joins flag saved for us by check_outerjoin_delay.
579616
*/
580-
if (bms_overlap(ojinfo->min_righthand,otherinfo->min_righthand)&&
581-
!bms_overlap(clause_relids,otherinfo->min_righthand)&&
582-
otherinfo->lhs_strict&& !otherinfo->delay_upper_joins)
617+
if (bms_overlap(right_rels,otherinfo->syn_righthand))
583618
{
584-
ojinfo->min_righthand=bms_del_members(ojinfo->min_righthand,
585-
otherinfo->min_righthand);
619+
if (bms_overlap(clause_relids,otherinfo->syn_righthand)||
620+
!otherinfo->lhs_strict||otherinfo->delay_upper_joins)
621+
{
622+
min_righthand=bms_add_members(min_righthand,
623+
otherinfo->syn_lefthand);
624+
min_righthand=bms_add_members(min_righthand,
625+
otherinfo->syn_righthand);
626+
}
586627
}
587628
}
588629

589-
/* Neither set should be empty, else we might get confused later */
590-
Assert(!bms_is_empty(ojinfo->min_lefthand));
591-
Assert(!bms_is_empty(ojinfo->min_righthand));
630+
/*
631+
* If we found nothing to put in min_lefthand, punt and make it the full
632+
* LHS, to avoid having an empty min_lefthand which will confuse later
633+
* processing. (We don't try to be smart about such cases, just correct.)
634+
* Likewise for min_righthand.
635+
*/
636+
if (bms_is_empty(min_lefthand))
637+
min_lefthand=bms_copy(left_rels);
638+
if (bms_is_empty(min_righthand))
639+
min_righthand=bms_copy(right_rels);
640+
641+
/* Now they'd better be nonempty */
642+
Assert(!bms_is_empty(min_lefthand));
643+
Assert(!bms_is_empty(min_righthand));
592644
/* Shouldn't overlap either */
593-
Assert(!bms_overlap(ojinfo->min_lefthand,ojinfo->min_righthand));
645+
Assert(!bms_overlap(min_lefthand,min_righthand));
646+
647+
ojinfo->min_lefthand=min_lefthand;
648+
ojinfo->min_righthand=min_righthand;
594649

595650
returnojinfo;
596651
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp