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

Commit92a43e4

Browse files
committed
Reduce semijoins with unique inner relations to plain inner joins.
If the inner relation can be proven unique, that is it can have no morethan one matching row for any row of the outer query, then we might aswell implement the semijoin as a plain inner join, allowing substantiallymore freedom to the planner. This is a form of outer join strengthreduction, but it can't be implemented in reduce_outer_joins() becausewe don't have enough info about the individual relations at that stage.Instead do it much like remove_useless_joins(): once we've built baserelations, we can make another pass over the SpecialJoinInfo list andget rid of any entries representing reducible semijoins.This is essentially a followon to the inner-unique patch (commit9c7f522)and makes use of the proof machinery that that patch created. We need onlyminor refactoring of innerrel_is_unique's API to support this usage.Per performance complaint from Teodor Sigaev.Discussion:https://postgr.es/m/f994fc98-389f-4a46-d1bc-c42e05cb43ed@sigaev.ru
1 parent2057a58 commit92a43e4

File tree

7 files changed

+181
-27
lines changed

7 files changed

+181
-27
lines changed

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

Lines changed: 21 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -126,13 +126,15 @@ add_paths_to_joinrel(PlannerInfo *root,
126126
*
127127
* We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
128128
* matter since the executor can make the equivalent optimization anyway;
129-
* we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, if
130-
* the LHS covers all of the associated semijoin's min_lefthand, then it's
131-
* appropriate to set inner_unique because the path produced by
132-
* create_unique_path will be unique relative to the LHS. (If we have an
133-
* LHS that's only part of the min_lefthand, that is *not* true.) For
134-
* JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid letting that value escape
135-
* this module.
129+
* we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
130+
* must be considering a semijoin whose inner side is not provably unique
131+
* (else reduce_unique_semijoins would've simplified it), so there's no
132+
* point in calling innerrel_is_unique. However, if the LHS covers all of
133+
* the semijoin's min_lefthand, then it's appropriate to set inner_unique
134+
* because the path produced by create_unique_path will be unique relative
135+
* to the LHS. (If we have an LHS that's only part of the min_lefthand,
136+
* that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
137+
* letting that value escape this module.
136138
*/
137139
switch (jointype)
138140
{
@@ -145,12 +147,20 @@ add_paths_to_joinrel(PlannerInfo *root,
145147
outerrel->relids);
146148
break;
147149
caseJOIN_UNIQUE_OUTER:
148-
extra.inner_unique=innerrel_is_unique(root,outerrel,innerrel,
149-
JOIN_INNER,restrictlist);
150+
extra.inner_unique=innerrel_is_unique(root,
151+
outerrel->relids,
152+
innerrel,
153+
JOIN_INNER,
154+
restrictlist,
155+
false);
150156
break;
151157
default:
152-
extra.inner_unique=innerrel_is_unique(root,outerrel,innerrel,
153-
jointype,restrictlist);
158+
extra.inner_unique=innerrel_is_unique(root,
159+
outerrel->relids,
160+
innerrel,
161+
jointype,
162+
restrictlist,
163+
false);
154164
break;
155165
}
156166

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

Lines changed: 108 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,7 @@ static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel,
4242
List*clause_list);
4343
staticOiddistinct_col_search(intcolno,List*colnos,List*opids);
4444
staticboolis_innerrel_unique_for(PlannerInfo*root,
45-
RelOptInfo*outerrel,
45+
Relidsouterrelids,
4646
RelOptInfo*innerrel,
4747
JoinTypejointype,
4848
List*restrictlist);
@@ -495,6 +495,88 @@ remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
495495
}
496496

497497

498+
/*
499+
* reduce_unique_semijoins
500+
*Check for semijoins that can be simplified to plain inner joins
501+
*because the inner relation is provably unique for the join clauses.
502+
*
503+
* Ideally this would happen during reduce_outer_joins, but we don't have
504+
* enough information at that point.
505+
*
506+
* To perform the strength reduction when applicable, we need only delete
507+
* the semijoin's SpecialJoinInfo from root->join_info_list. (We don't
508+
* bother fixing the join type attributed to it in the query jointree,
509+
* since that won't be consulted again.)
510+
*/
511+
void
512+
reduce_unique_semijoins(PlannerInfo*root)
513+
{
514+
ListCell*lc;
515+
ListCell*next;
516+
517+
/*
518+
* Scan the join_info_list to find semijoins. We can't use foreach
519+
* because we may delete the current cell.
520+
*/
521+
for (lc=list_head(root->join_info_list);lc!=NULL;lc=next)
522+
{
523+
SpecialJoinInfo*sjinfo= (SpecialJoinInfo*)lfirst(lc);
524+
intinnerrelid;
525+
RelOptInfo*innerrel;
526+
Relidsjoinrelids;
527+
List*restrictlist;
528+
529+
next=lnext(lc);
530+
531+
/*
532+
* Must be a non-delaying semijoin to a single baserel, else we aren't
533+
* going to be able to do anything with it. (It's probably not
534+
* possible for delay_upper_joins to be set on a semijoin, but we
535+
* might as well check.)
536+
*/
537+
if (sjinfo->jointype!=JOIN_SEMI||
538+
sjinfo->delay_upper_joins)
539+
continue;
540+
541+
if (!bms_get_singleton_member(sjinfo->min_righthand,&innerrelid))
542+
continue;
543+
544+
innerrel=find_base_rel(root,innerrelid);
545+
546+
/*
547+
* Before we trouble to run generate_join_implied_equalities, make a
548+
* quick check to eliminate cases in which we will surely be unable to
549+
* prove uniqueness of the innerrel.
550+
*/
551+
if (!rel_supports_distinctness(root,innerrel))
552+
continue;
553+
554+
/* Compute the relid set for the join we are considering */
555+
joinrelids=bms_union(sjinfo->min_lefthand,sjinfo->min_righthand);
556+
557+
/*
558+
* Since we're only considering a single-rel RHS, any join clauses it
559+
* has must be clauses linking it to the semijoin's min_lefthand. We
560+
* can also consider EC-derived join clauses.
561+
*/
562+
restrictlist=
563+
list_concat(generate_join_implied_equalities(root,
564+
joinrelids,
565+
sjinfo->min_lefthand,
566+
innerrel),
567+
innerrel->joininfo);
568+
569+
/* Test whether the innerrel is unique for those clauses. */
570+
if (!innerrel_is_unique(root,sjinfo->min_lefthand,innerrel,
571+
JOIN_SEMI,restrictlist, true))
572+
continue;
573+
574+
/* OK, remove the SpecialJoinInfo from the list. */
575+
root->join_info_list=list_delete_ptr(root->join_info_list,sjinfo);
576+
}
577+
}
578+
579+
498580
/*
499581
* rel_supports_distinctness
500582
*Could the relation possibly be proven distinct on some set of columns?
@@ -857,6 +939,10 @@ distinct_col_search(int colno, List *colnos, List *opids)
857939
* Check if the innerrel provably contains at most one tuple matching any
858940
* tuple from the outerrel, based on join clauses in the 'restrictlist'.
859941
*
942+
* We need an actual RelOptInfo for the innerrel, but it's sufficient to
943+
* identify the outerrel by its Relids. This asymmetry supports use of this
944+
* function before joinrels have been built.
945+
*
860946
* The proof must be made based only on clauses that will be "joinquals"
861947
* rather than "otherquals" at execution. For an inner join there's no
862948
* difference; but if the join is outer, we must ignore pushed-down quals,
@@ -867,13 +953,18 @@ distinct_col_search(int colno, List *colnos, List *opids)
867953
*
868954
* The actual proof is undertaken by is_innerrel_unique_for(); this function
869955
* is a frontend that is mainly concerned with caching the answers.
956+
* In particular, the force_cache argument allows overriding the internal
957+
* heuristic about whether to cache negative answers; it should be "true"
958+
* if making an inquiry that is not part of the normal bottom-up join search
959+
* sequence.
870960
*/
871961
bool
872962
innerrel_is_unique(PlannerInfo*root,
873-
RelOptInfo*outerrel,
963+
Relidsouterrelids,
874964
RelOptInfo*innerrel,
875965
JoinTypejointype,
876-
List*restrictlist)
966+
List*restrictlist,
967+
boolforce_cache)
877968
{
878969
MemoryContextold_context;
879970
ListCell*lc;
@@ -900,7 +991,7 @@ innerrel_is_unique(PlannerInfo *root,
900991
{
901992
Relidsunique_for_rels= (Relids)lfirst(lc);
902993

903-
if (bms_is_subset(unique_for_rels,outerrel->relids))
994+
if (bms_is_subset(unique_for_rels,outerrelids))
904995
return true;/* Success! */
905996
}
906997

@@ -912,12 +1003,12 @@ innerrel_is_unique(PlannerInfo *root,
9121003
{
9131004
Relidsunique_for_rels= (Relids)lfirst(lc);
9141005

915-
if (bms_is_subset(outerrel->relids,unique_for_rels))
1006+
if (bms_is_subset(outerrelids,unique_for_rels))
9161007
return false;
9171008
}
9181009

9191010
/* No cached information, so try to make the proof. */
920-
if (is_innerrel_unique_for(root,outerrel,innerrel,
1011+
if (is_innerrel_unique_for(root,outerrelids,innerrel,
9211012
jointype,restrictlist))
9221013
{
9231014
/*
@@ -932,7 +1023,7 @@ innerrel_is_unique(PlannerInfo *root,
9321023
*/
9331024
old_context=MemoryContextSwitchTo(root->planner_cxt);
9341025
innerrel->unique_for_rels=lappend(innerrel->unique_for_rels,
935-
bms_copy(outerrel->relids));
1026+
bms_copy(outerrelids));
9361027
MemoryContextSwitchTo(old_context);
9371028

9381029
return true;/* Success! */
@@ -949,15 +1040,19 @@ innerrel_is_unique(PlannerInfo *root,
9491040
* from smaller to larger. It is useful in GEQO mode, where the
9501041
* knowledge can be carried across successive planning attempts; and
9511042
* it's likely to be useful when using join-search plugins, too. Hence
952-
* cache only when join_search_private is non-NULL. (Yeah, that's a
953-
* hack, but it seems reasonable.)
1043+
* cache when join_search_private is non-NULL. (Yeah, that's a hack,
1044+
* but it seems reasonable.)
1045+
*
1046+
* Also, allow callers to override that heuristic and force caching;
1047+
* that's useful for reduce_unique_semijoins, which calls here before
1048+
* the normal join search starts.
9541049
*/
955-
if (root->join_search_private)
1050+
if (force_cache||root->join_search_private)
9561051
{
9571052
old_context=MemoryContextSwitchTo(root->planner_cxt);
9581053
innerrel->non_unique_for_rels=
9591054
lappend(innerrel->non_unique_for_rels,
960-
bms_copy(outerrel->relids));
1055+
bms_copy(outerrelids));
9611056
MemoryContextSwitchTo(old_context);
9621057
}
9631058

@@ -972,7 +1067,7 @@ innerrel_is_unique(PlannerInfo *root,
9721067
*/
9731068
staticbool
9741069
is_innerrel_unique_for(PlannerInfo*root,
975-
RelOptInfo*outerrel,
1070+
Relidsouterrelids,
9761071
RelOptInfo*innerrel,
9771072
JoinTypejointype,
9781073
List*restrictlist)
@@ -1007,7 +1102,7 @@ is_innerrel_unique_for(PlannerInfo *root,
10071102
* Check if clause has the form "outer op inner" or "inner op outer",
10081103
* and if so mark which side is inner.
10091104
*/
1010-
if (!clause_sides_match_join(restrictinfo,outerrel->relids,
1105+
if (!clause_sides_match_join(restrictinfo,outerrelids,
10111106
innerrel->relids))
10121107
continue;/* no good for these input relations */
10131108

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

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -192,6 +192,12 @@ query_planner(PlannerInfo *root, List *tlist,
192192
*/
193193
joinlist=remove_useless_joins(root,joinlist);
194194

195+
/*
196+
* Also, reduce any semijoins with unique inner rels to plain inner joins.
197+
* Likewise, this can't be done until now for lack of needed info.
198+
*/
199+
reduce_unique_semijoins(root);
200+
195201
/*
196202
* Now distribute "placeholders" to base rels as needed. This has to be
197203
* done after join removal because removal could change whether a

‎src/include/optimizer/planmain.h

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -103,11 +103,12 @@ extern void match_foreign_keys_to_quals(PlannerInfo *root);
103103
* prototypes for plan/analyzejoins.c
104104
*/
105105
externList*remove_useless_joins(PlannerInfo*root,List*joinlist);
106+
externvoidreduce_unique_semijoins(PlannerInfo*root);
106107
externboolquery_supports_distinctness(Query*query);
107108
externboolquery_is_distinct_for(Query*query,List*colnos,List*opids);
108109
externboolinnerrel_is_unique(PlannerInfo*root,
109-
RelOptInfo*outerrel,RelOptInfo*innerrel,
110-
JoinTypejointype,List*restrictlist);
110+
Relidsouterrelids,RelOptInfo*innerrel,
111+
JoinTypejointype,List*restrictlist,boolforce_cache);
111112

112113
/*
113114
* prototypes for plan/setrefs.c

‎src/test/regress/expected/join.out

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5663,3 +5663,31 @@ where exists (select 1 from tenk1 t3
56635663
Index Cond: (t2.hundred = t3.tenthous)
56645664
(18 rows)
56655665

5666+
-- ... unless it actually is unique
5667+
create table j3 as select unique1, tenthous from onek;
5668+
vacuum analyze j3;
5669+
create unique index on j3(unique1, tenthous);
5670+
explain (verbose, costs off)
5671+
select t1.unique1, t2.hundred
5672+
from onek t1, tenk1 t2
5673+
where exists (select 1 from j3
5674+
where j3.unique1 = t1.unique1 and j3.tenthous = t2.hundred)
5675+
and t1.unique1 < 1;
5676+
QUERY PLAN
5677+
------------------------------------------------------------------------
5678+
Nested Loop
5679+
Output: t1.unique1, t2.hundred
5680+
-> Nested Loop
5681+
Output: t1.unique1, j3.tenthous
5682+
-> Index Only Scan using onek_unique1 on public.onek t1
5683+
Output: t1.unique1
5684+
Index Cond: (t1.unique1 < 1)
5685+
-> Index Only Scan using j3_unique1_tenthous_idx on public.j3
5686+
Output: j3.unique1, j3.tenthous
5687+
Index Cond: (j3.unique1 = t1.unique1)
5688+
-> Index Only Scan using tenk1_hundred on public.tenk1 t2
5689+
Output: t2.hundred
5690+
Index Cond: (t2.hundred = j3.tenthous)
5691+
(13 rows)
5692+
5693+
drop table j3;

‎src/test/regress/expected/updatable_views.out

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1673,7 +1673,7 @@ EXPLAIN (costs off) UPDATE rw_view1 SET a = a + 5;
16731673
QUERY PLAN
16741674
-----------------------------------------------------------------
16751675
Update on base_tbl b
1676-
-> HashSemiJoin
1676+
-> Hash Join
16771677
Hash Cond: (b.a = r.a)
16781678
-> Seq Scan on base_tbl b
16791679
-> Hash

‎src/test/regress/sql/join.sql

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1864,3 +1864,17 @@ from onek t1, tenk1 t2
18641864
where exists (select1from tenk1 t3
18651865
wheret3.thousand=t1.unique1andt3.tenthous=t2.hundred)
18661866
andt1.unique1<1;
1867+
1868+
-- ... unless it actually is unique
1869+
createtablej3asselect unique1, tenthousfrom onek;
1870+
vacuum analyze j3;
1871+
createunique indexon j3(unique1, tenthous);
1872+
1873+
explain (verbose, costs off)
1874+
selectt1.unique1,t2.hundred
1875+
from onek t1, tenk1 t2
1876+
where exists (select1from j3
1877+
wherej3.unique1=t1.unique1andj3.tenthous=t2.hundred)
1878+
andt1.unique1<1;
1879+
1880+
droptable j3;

0 commit comments

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