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

Commitca2d6a6

Browse files
committed
Limit the number of rel sets considered in consider_index_join_outer_rels.
In bug #7626, Brian Dunavant exposes a performance problem created bycommit3b8968f: that commit attempted toconsider *all* possible combinations of indexable join clauses, but if saidclauses join to enough different relations, there's an exponential increasein the number of outer-relation sets considered.In Brian's example, all the clauses come from the same equivalence class,which means it's redundant to use more than one of them in an indexscananyway. So we can prevent the problem in this class of cases (which isprobably the majority of real examples) by rejecting combinations thatwould only serve to add a known-redundant clause.But that still leaves us exposed to exponential growth of planning timewhen the query has a lot of non-equivalence join clauses that are usablewith the same index. I chose to prevent such cases by setting an upperlimit on the number of relation sets considered, equal to ten times thenumber of index clauses considered so far. (This sliding limit stillallows new relsets to be added on as we move to additional index columns,which is probably more important than considering even more combinations ofclauses for the previous column.) This should keep the amount of work doneroughly linear rather than exponential in the apparent query complexity.This part of the fix is pretty ad-hoc; but without a clearer idea ofreal-world cases for which this would result in markedly inferior plans,it's hard to see how to do better.
1 parentec397c9 commitca2d6a6

File tree

1 file changed

+61
-3
lines changed

1 file changed

+61
-3
lines changed

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

Lines changed: 61 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -92,6 +92,7 @@ static void consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel,
9292
IndexClauseSet*eclauseset,
9393
List**bitindexpaths,
9494
List*indexjoinclauses,
95+
intconsidered_clauses,
9596
List**considered_relids);
9697
staticvoidget_join_index_paths(PlannerInfo*root,RelOptInfo*rel,
9798
IndexOptInfo*index,
@@ -101,6 +102,8 @@ static void get_join_index_paths(PlannerInfo *root, RelOptInfo *rel,
101102
List**bitindexpaths,
102103
Relidsrelids,
103104
List**considered_relids);
105+
staticbooleclass_already_used(EquivalenceClass*parent_ec,Relidsoldrelids,
106+
List*indexjoinclauses);
104107
staticboolbms_equal_any(Relidsrelids,List*relids_list);
105108
staticvoidget_index_paths(PlannerInfo*root,RelOptInfo*rel,
106109
IndexOptInfo*index,IndexClauseSet*clauses,
@@ -416,6 +419,7 @@ consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel,
416419
IndexClauseSet*eclauseset,
417420
List**bitindexpaths)
418421
{
422+
intconsidered_clauses=0;
419423
List*considered_relids=NIL;
420424
intindexcol;
421425

@@ -429,8 +433,11 @@ consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel,
429433
* filter (qpqual); which is where an available clause would end up being
430434
* applied if we omit it from the indexquals.
431435
*
432-
* This looks expensive, but in practical cases there won't be very many
433-
* distinct sets of outer rels to consider.
436+
* This looks expensive, but in most practical cases there won't be very
437+
* many distinct sets of outer rels to consider. As a safety valve when
438+
* that's not true, we use a heuristic: limit the number of outer rel sets
439+
* considered to a multiple of the number of clauses considered. (We'll
440+
* always consider using each individual join clause, though.)
434441
*
435442
* For simplicity in selecting relevant clauses, we represent each set of
436443
* outer rels as a maximum set of clause_relids --- that is, the indexed
@@ -440,16 +447,20 @@ consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel,
440447
for (indexcol=0;indexcol<index->ncolumns;indexcol++)
441448
{
442449
/* Consider each applicable simple join clause */
450+
considered_clauses+=list_length(jclauseset->indexclauses[indexcol]);
443451
consider_index_join_outer_rels(root,rel,index,
444452
rclauseset,jclauseset,eclauseset,
445453
bitindexpaths,
446454
jclauseset->indexclauses[indexcol],
455+
considered_clauses,
447456
&considered_relids);
448457
/* Consider each applicable eclass join clause */
458+
considered_clauses+=list_length(eclauseset->indexclauses[indexcol]);
449459
consider_index_join_outer_rels(root,rel,index,
450460
rclauseset,jclauseset,eclauseset,
451461
bitindexpaths,
452462
eclauseset->indexclauses[indexcol],
463+
considered_clauses,
453464
&considered_relids);
454465
}
455466
}
@@ -463,6 +474,7 @@ consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel,
463474
* 'rel', 'index', 'rclauseset', 'jclauseset', 'eclauseset', and
464475
*'bitindexpaths' as above
465476
* 'indexjoinclauses' is a list of RestrictInfos for join clauses
477+
* 'considered_clauses' is the total number of clauses considered (so far)
466478
* '*considered_relids' is a list of all relids sets already considered
467479
*/
468480
staticvoid
@@ -473,6 +485,7 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel,
473485
IndexClauseSet*eclauseset,
474486
List**bitindexpaths,
475487
List*indexjoinclauses,
488+
intconsidered_clauses,
476489
List**considered_relids)
477490
{
478491
ListCell*lc;
@@ -491,7 +504,9 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel,
491504
/*
492505
* Generate the union of this clause's relids set with each
493506
* previously-tried set. This ensures we try this clause along with
494-
* every interesting subset of previous clauses.
507+
* every interesting subset of previous clauses. However, to avoid
508+
* exponential growth of planning time when there are many clauses,
509+
* limit the number of relid sets accepted to 10 * considered_clauses.
495510
*
496511
* Note: get_join_index_paths adds entries to *considered_relids, but
497512
* it prepends them to the list, so that we won't visit new entries
@@ -512,6 +527,27 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel,
512527
if (bms_subset_compare(clause_relids,oldrelids)!=BMS_DIFFERENT)
513528
continue;
514529

530+
/*
531+
* If this clause was derived from an equivalence class, the
532+
* clause list may contain other clauses derived from the same
533+
* eclass. We should not consider that combining this clause with
534+
* one of those clauses generates a usefully different
535+
* parameterization; so skip if any clause derived from the same
536+
* eclass would already have been included when using oldrelids.
537+
*/
538+
if (rinfo->parent_ec&&
539+
eclass_already_used(rinfo->parent_ec,oldrelids,
540+
indexjoinclauses))
541+
continue;
542+
543+
/*
544+
* If the number of relid sets considered exceeds our heuristic
545+
* limit, stop considering combinations of clauses. We'll still
546+
* consider the current clause alone, though (below this loop).
547+
*/
548+
if (list_length(*considered_relids) >=10*considered_clauses)
549+
break;
550+
515551
/* OK, try the union set */
516552
get_join_index_paths(root,rel,index,
517553
rclauseset,jclauseset,eclauseset,
@@ -616,6 +652,28 @@ get_join_index_paths(PlannerInfo *root, RelOptInfo *rel,
616652
*considered_relids=lcons(relids,*considered_relids);
617653
}
618654

655+
/*
656+
* eclass_already_used
657+
*True if any join clause usable with oldrelids was generated from
658+
*the specified equivalence class.
659+
*/
660+
staticbool
661+
eclass_already_used(EquivalenceClass*parent_ec,Relidsoldrelids,
662+
List*indexjoinclauses)
663+
{
664+
ListCell*lc;
665+
666+
foreach(lc,indexjoinclauses)
667+
{
668+
RestrictInfo*rinfo= (RestrictInfo*)lfirst(lc);
669+
670+
if (rinfo->parent_ec==parent_ec&&
671+
bms_is_subset(rinfo->clause_relids,oldrelids))
672+
return true;
673+
}
674+
return false;
675+
}
676+
619677
/*
620678
* bms_equal_any
621679
*True if relids is bms_equal to any member of relids_list

0 commit comments

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