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

Commit8309d00

Browse files
committed
Switch the planner over to treating qualifications of a JOIN_SEMI join as
though it is an inner rather than outer join type. This essentially meansthat we don't bother to separate "pushed down" qual conditions from actualjoin quals at a semijoin plan node; which is okay because the restrictions ofSQL syntax make it impossible to have a pushed-down qual that references theinner side of a semijoin. This allows noticeably better optimization ofIN/EXISTS cases than we had before, since the equivalence-class machinery cannow use those quals. Also fix a couple of other mistakes that had essentiallydisabled the ability to unique-ify the inner relation and then join it to justa subset of the left-hand relations. An example case using the regressiondatabase isselect * from tenk1 a, tenk1 bwhere (a.unique1,b.unique2) in (select unique1,unique2 from tenk1 c);which is planned reasonably well by 8.3 and earlier but had been forcing acartesian join of a/b in CVS HEAD.
1 parent86422cb commit8309d00

File tree

6 files changed

+87
-34
lines changed

6 files changed

+87
-34
lines changed

‎src/backend/optimizer/path/costsize.c‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -54,7 +54,7 @@
5454
* Portions Copyright (c) 1994, Regents of the University of California
5555
*
5656
* IDENTIFICATION
57-
* $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.200 2008/10/21 20:42:52 tgl Exp $
57+
* $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.201 2008/11/22 22:47:05 tgl Exp $
5858
*
5959
*-------------------------------------------------------------------------
6060
*/
@@ -2481,7 +2481,7 @@ set_joinrel_size_estimates(PlannerInfo *root, RelOptInfo *rel,
24812481
break;
24822482
caseJOIN_SEMI:
24832483
nrows=outer_rel->rows*jselec;
2484-
nrows *=pselec;
2484+
/* pselec not used */
24852485
break;
24862486
caseJOIN_ANTI:
24872487
nrows=outer_rel->rows* (1.0-jselec);

‎src/backend/optimizer/path/indxpath.c‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.233 2008/09/12 14:56:13 tgl Exp $
12+
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.234 2008/11/22 22:47:05 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -1647,10 +1647,10 @@ best_inner_indexscan(PlannerInfo *root, RelOptInfo *rel,
16471647
switch (jointype)
16481648
{
16491649
caseJOIN_INNER:
1650+
caseJOIN_SEMI:
16501651
isouterjoin= false;
16511652
break;
16521653
caseJOIN_LEFT:
1653-
caseJOIN_SEMI:
16541654
caseJOIN_ANTI:
16551655
isouterjoin= true;
16561656
break;

‎src/backend/optimizer/path/joinpath.c‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/path/joinpath.c,v 1.118 2008/10/04 21:56:53 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/path/joinpath.c,v 1.119 2008/11/22 22:47:06 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -744,12 +744,12 @@ hash_inner_and_outer(PlannerInfo *root,
744744
switch (jointype)
745745
{
746746
caseJOIN_INNER:
747+
caseJOIN_SEMI:
747748
caseJOIN_UNIQUE_OUTER:
748749
caseJOIN_UNIQUE_INNER:
749750
isouterjoin= false;
750751
break;
751752
caseJOIN_LEFT:
752-
caseJOIN_SEMI:
753753
caseJOIN_ANTI:
754754
isouterjoin= true;
755755
break;

‎src/backend/optimizer/path/joinrels.c‎

Lines changed: 48 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/path/joinrels.c,v 1.94 2008/08/17 19:40:11 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/path/joinrels.c,v 1.95 2008/11/22 22:47:06 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -419,6 +419,27 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
419419
match_sjinfo=sjinfo;
420420
reversed= true;
421421
}
422+
elseif (sjinfo->jointype==JOIN_SEMI&&
423+
bms_equal(sjinfo->syn_righthand,rel2->relids))
424+
{
425+
/*
426+
* For a semijoin, we can join the RHS to anything else by
427+
* unique-ifying the RHS.
428+
*/
429+
if (match_sjinfo)
430+
return false;/* invalid join path */
431+
match_sjinfo=sjinfo;
432+
reversed= false;
433+
}
434+
elseif (sjinfo->jointype==JOIN_SEMI&&
435+
bms_equal(sjinfo->syn_righthand,rel1->relids))
436+
{
437+
/* Reversed semijoin case */
438+
if (match_sjinfo)
439+
return false;/* invalid join path */
440+
match_sjinfo=sjinfo;
441+
reversed= true;
442+
}
422443
else
423444
{
424445
/*----------
@@ -444,14 +465,24 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
444465
* We assume that make_outerjoininfo() set things up correctly
445466
* so that we'll only match to some SJ if the join is valid.
446467
* Set flag here to check at bottom of loop.
468+
*
469+
* For a semijoin, assume it's okay if either side fully contains
470+
* the RHS (per the unique-ification case above).
447471
*----------
448472
*/
449-
if (bms_overlap(rel1->relids,sjinfo->min_righthand)&&
473+
if (sjinfo->jointype!=JOIN_SEMI&&
474+
bms_overlap(rel1->relids,sjinfo->min_righthand)&&
450475
bms_overlap(rel2->relids,sjinfo->min_righthand))
451476
{
452477
/* seems OK */
453478
Assert(!bms_overlap(joinrelids,sjinfo->min_lefthand));
454479
}
480+
elseif (sjinfo->jointype==JOIN_SEMI&&
481+
(bms_is_subset(sjinfo->syn_righthand,rel1->relids)||
482+
bms_is_subset(sjinfo->syn_righthand,rel2->relids)))
483+
{
484+
/* seems OK */
485+
}
455486
else
456487
is_valid_inner= false;
457488
}
@@ -612,15 +643,23 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
612643
restrictlist);
613644
break;
614645
caseJOIN_SEMI:
615-
if (is_dummy_rel(rel1)||is_dummy_rel(rel2)||
616-
restriction_is_constant_false(restrictlist))
646+
/*
647+
* Do these steps only if we actually have a regular semijoin,
648+
* as opposed to a case where we should unique-ify the RHS.
649+
*/
650+
if (bms_is_subset(sjinfo->min_lefthand,rel1->relids)&&
651+
bms_is_subset(sjinfo->min_righthand,rel2->relids))
617652
{
618-
mark_dummy_rel(joinrel);
619-
break;
653+
if (is_dummy_rel(rel1)||is_dummy_rel(rel2)||
654+
restriction_is_constant_false(restrictlist))
655+
{
656+
mark_dummy_rel(joinrel);
657+
break;
658+
}
659+
add_paths_to_joinrel(root,joinrel,rel1,rel2,
660+
JOIN_SEMI,sjinfo,
661+
restrictlist);
620662
}
621-
add_paths_to_joinrel(root,joinrel,rel1,rel2,
622-
JOIN_SEMI,sjinfo,
623-
restrictlist);
624663

625664
/*
626665
* If we know how to unique-ify the RHS and one input rel is

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

Lines changed: 17 additions & 11 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.144 2008/10/25 19:51:32 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/plan/initsplan.c,v 1.145 2008/11/22 22:47:06 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -851,16 +851,11 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
851851
maybe_equivalence= false;
852852
maybe_outer_join= false;
853853
}
854-
elseif (bms_overlap(relids,outerjoin_nonnullable)&&
855-
(jointype!=JOIN_SEMI||
856-
bms_nonempty_difference(relids,outerjoin_nonnullable)))
854+
elseif (bms_overlap(relids,outerjoin_nonnullable))
857855
{
858856
/*
859857
* The qual is attached to an outer join and mentions (some of the)
860-
* rels on the nonnullable side, so it's not degenerate. (For a
861-
* JOIN_SEMI qual, we consider it non-degenerate only if it mentions
862-
* both sides of the join --- if it mentions only one side, it can
863-
* be pushed down.)
858+
* rels on the nonnullable side, so it's not degenerate.
864859
*
865860
* We can't use such a clause to deduce equivalence (the left and
866861
* right sides might be unequal above the join because one of them has
@@ -1062,6 +1057,7 @@ distribute_sublink_quals_to_rels(PlannerInfo *root,
10621057
SpecialJoinInfo*sjinfo;
10631058
Relidsqualscope;
10641059
Relidsojscope;
1060+
Relidsouterjoin_nonnullable;
10651061
ListCell*l;
10661062

10671063
/*
@@ -1076,17 +1072,27 @@ distribute_sublink_quals_to_rels(PlannerInfo *root,
10761072
fslink->jointype,
10771073
quals);
10781074

1075+
/* Treat as inner join if SEMI, outer join if ANTI */
10791076
qualscope=bms_union(sjinfo->syn_lefthand,sjinfo->syn_righthand);
1080-
ojscope=bms_union(sjinfo->min_lefthand,sjinfo->min_righthand);
1077+
if (fslink->jointype==JOIN_SEMI)
1078+
{
1079+
ojscope=outerjoin_nonnullable=NULL;
1080+
}
1081+
else
1082+
{
1083+
Assert(fslink->jointype==JOIN_ANTI);
1084+
ojscope=bms_union(sjinfo->min_lefthand,sjinfo->min_righthand);
1085+
outerjoin_nonnullable=fslink->lefthand;
1086+
}
10811087

1082-
/* Distribute the join quals much as for a regularLEFTJOIN */
1088+
/* Distribute the join quals much as for a regular JOIN node */
10831089
foreach(l,quals)
10841090
{
10851091
Node*qual= (Node*)lfirst(l);
10861092

10871093
distribute_qual_to_rels(root,qual,
10881094
false,below_outer_join,fslink->jointype,
1089-
qualscope,ojscope,fslink->lefthand);
1095+
qualscope,ojscope,outerjoin_nonnullable);
10901096
}
10911097

10921098
/* Now we can add the SpecialJoinInfo to join_info_list */

‎src/include/nodes/nodes.h‎

Lines changed: 16 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
10-
* $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.214 2008/10/21 20:42:53 tgl Exp $
10+
* $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.215 2008/11/22 22:47:06 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -542,15 +542,23 @@ typedef enum JoinType
542542

543543
/*
544544
* OUTER joins are those for which pushed-down quals must behave differently
545-
* from the join's own quals. This is in fact everything except INNER joins.
546-
* However, this macro must also exclude the JOIN_UNIQUE symbols since those
547-
* are temporary proxies for what will eventually be an INNER join.
545+
* from the join's own quals. This is in fact everything except INNER and
546+
* SEMI joins. However, this macro must also exclude the JOIN_UNIQUE symbols
547+
* since those are temporary proxies for what will eventually be an INNER
548+
* join.
548549
*
549-
* Note: in some places it is preferable to treat JOIN_SEMI as not being
550-
* an outer join, since it doesn't produce null-extended rows. Be aware
551-
* of that distinction when deciding whether to use this macro.
550+
* Note: semijoins are a hybrid case, but we choose to treat them as not
551+
* being outer joins. This is okay principally because the SQL syntax makes
552+
* it impossible to have a pushed-down qual that refers to the inner relation
553+
* of a semijoin; so there is no strong need to distinguish join quals from
554+
* pushed-down quals. This is convenient because for almost all purposes,
555+
* quals attached to a semijoin can be treated the same as innerjoin quals.
552556
*/
553557
#defineIS_OUTER_JOIN(jointype) \
554-
((jointype) > JOIN_INNER && (jointype) < JOIN_UNIQUE_OUTER)
558+
(((1 << (jointype)) & \
559+
((1 << JOIN_LEFT) | \
560+
(1 << JOIN_FULL) | \
561+
(1 << JOIN_RIGHT) | \
562+
(1 << JOIN_ANTI))) != 0)
555563

556564
#endif/* NODES_H */

0 commit comments

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