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

Commit19e3647

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 parent1eb1dde commit19e3647

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,
@@ -447,6 +450,7 @@ consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel,
447450
IndexClauseSet*eclauseset,
448451
List**bitindexpaths)
449452
{
453+
intconsidered_clauses=0;
450454
List*considered_relids=NIL;
451455
intindexcol;
452456

@@ -460,8 +464,11 @@ consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel,
460464
* filter (qpqual); which is where an available clause would end up being
461465
* applied if we omit it from the indexquals.
462466
*
463-
* This looks expensive, but in practical cases there won't be very many
464-
* distinct sets of outer rels to consider.
467+
* This looks expensive, but in most practical cases there won't be very
468+
* many distinct sets of outer rels to consider. As a safety valve when
469+
* that's not true, we use a heuristic: limit the number of outer rel sets
470+
* considered to a multiple of the number of clauses considered. (We'll
471+
* always consider using each individual join clause, though.)
465472
*
466473
* For simplicity in selecting relevant clauses, we represent each set of
467474
* outer rels as a maximum set of clause_relids --- that is, the indexed
@@ -471,16 +478,20 @@ consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel,
471478
for (indexcol=0;indexcol<index->ncolumns;indexcol++)
472479
{
473480
/* Consider each applicable simple join clause */
481+
considered_clauses+=list_length(jclauseset->indexclauses[indexcol]);
474482
consider_index_join_outer_rels(root,rel,index,
475483
rclauseset,jclauseset,eclauseset,
476484
bitindexpaths,
477485
jclauseset->indexclauses[indexcol],
486+
considered_clauses,
478487
&considered_relids);
479488
/* Consider each applicable eclass join clause */
489+
considered_clauses+=list_length(eclauseset->indexclauses[indexcol]);
480490
consider_index_join_outer_rels(root,rel,index,
481491
rclauseset,jclauseset,eclauseset,
482492
bitindexpaths,
483493
eclauseset->indexclauses[indexcol],
494+
considered_clauses,
484495
&considered_relids);
485496
}
486497
}
@@ -494,6 +505,7 @@ consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel,
494505
* 'rel', 'index', 'rclauseset', 'jclauseset', 'eclauseset', and
495506
*'bitindexpaths' as above
496507
* 'indexjoinclauses' is a list of RestrictInfos for join clauses
508+
* 'considered_clauses' is the total number of clauses considered (so far)
497509
* '*considered_relids' is a list of all relids sets already considered
498510
*/
499511
staticvoid
@@ -504,6 +516,7 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel,
504516
IndexClauseSet*eclauseset,
505517
List**bitindexpaths,
506518
List*indexjoinclauses,
519+
intconsidered_clauses,
507520
List**considered_relids)
508521
{
509522
ListCell*lc;
@@ -522,7 +535,9 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel,
522535
/*
523536
* Generate the union of this clause's relids set with each
524537
* previously-tried set. This ensures we try this clause along with
525-
* every interesting subset of previous clauses.
538+
* every interesting subset of previous clauses. However, to avoid
539+
* exponential growth of planning time when there are many clauses,
540+
* limit the number of relid sets accepted to 10 * considered_clauses.
526541
*
527542
* Note: get_join_index_paths adds entries to *considered_relids, but
528543
* it prepends them to the list, so that we won't visit new entries
@@ -543,6 +558,27 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel,
543558
if (bms_subset_compare(clause_relids,oldrelids)!=BMS_DIFFERENT)
544559
continue;
545560

561+
/*
562+
* If this clause was derived from an equivalence class, the
563+
* clause list may contain other clauses derived from the same
564+
* eclass. We should not consider that combining this clause with
565+
* one of those clauses generates a usefully different
566+
* parameterization; so skip if any clause derived from the same
567+
* eclass would already have been included when using oldrelids.
568+
*/
569+
if (rinfo->parent_ec&&
570+
eclass_already_used(rinfo->parent_ec,oldrelids,
571+
indexjoinclauses))
572+
continue;
573+
574+
/*
575+
* If the number of relid sets considered exceeds our heuristic
576+
* limit, stop considering combinations of clauses. We'll still
577+
* consider the current clause alone, though (below this loop).
578+
*/
579+
if (list_length(*considered_relids) >=10*considered_clauses)
580+
break;
581+
546582
/* OK, try the union set */
547583
get_join_index_paths(root,rel,index,
548584
rclauseset,jclauseset,eclauseset,
@@ -647,6 +683,28 @@ get_join_index_paths(PlannerInfo *root, RelOptInfo *rel,
647683
*considered_relids=lcons(relids,*considered_relids);
648684
}
649685

686+
/*
687+
* eclass_already_used
688+
*True if any join clause usable with oldrelids was generated from
689+
*the specified equivalence class.
690+
*/
691+
staticbool
692+
eclass_already_used(EquivalenceClass*parent_ec,Relidsoldrelids,
693+
List*indexjoinclauses)
694+
{
695+
ListCell*lc;
696+
697+
foreach(lc,indexjoinclauses)
698+
{
699+
RestrictInfo*rinfo= (RestrictInfo*)lfirst(lc);
700+
701+
if (rinfo->parent_ec==parent_ec&&
702+
bms_is_subset(rinfo->clause_relids,oldrelids))
703+
return true;
704+
}
705+
return false;
706+
}
707+
650708
/*
651709
* bms_equal_any
652710
*True if relids is bms_equal to any member of relids_list

0 commit comments

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