8000 Limit the number of rel sets considered in consider_index_join_outer_… · danielcode/postgres@ca2d6a6 · GitHub
[go: up one dir, main page]
Skip to content

Commit ca2d6a6

Browse files
tglsfdctglsfdc
committed
Limit the number of rel sets considered in consider_index_join_outer_rels.
In bug #7626, Brian Dunavant exposes a performance problem created by commit 3b8968f: that commit attempted to consider *all* possible combinations of indexable join clauses, but if said clauses join to enough different relations, there's an exponential increase in 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 indexscan anyway. So we can prevent the problem in this class of cases (which is probably the majority of real examples) by rejecting combinations that would only serve to add a known-redundant clause. But that still leaves us exposed to exponential growth of planning time when the query has a lot of non-equivalence join clauses that are usable with the same index. I chose to prevent such cases by setting an upper limit on the number of relation sets considered, equal to ten times the number of index clauses considered so far. (This sliding limit still allows new relsets to be added on as we move to additional index columns, which is probably more important than considering even more combinations of clauses for the previous column.) This should keep the amount of work done roughly linear rather than exponential in the apparent query complexity. This part of the fix is pretty ad-hoc; but without a clearer idea of real-world cases for which this would result in markedly inferior plans, it's hard to see how to do better.
1 parent ec397c9 commit ca2d6a6

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+
int considered_clauses,
9596
List **considered_relids);
9697
static void get_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
Relids relids,
103104
List **considered_relids);
105+
static bool eclass_already_used(EquivalenceClass *parent_ec, Relids oldrelids,
106+
List *indexjoinclauses);
104107
static bool bms_equal_any(Relids relids, List *relids_list);
105108
static void get_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+
int considered_clauses = 0;
419423
List *considered_relids = NIL;
420424
int indexcol;
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
static void
@@ -473,6 +485,7 @@ consider_index_join_outer_rels(PlannerInfo *root, RelOptInfo *rel,
473485
IndexClauseSet *eclauseset,
474486
List **bitindexpaths,
475487
List *indexjoinclauses,
488+
int considered_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+
static bool
661+
eclass_already_used(EquivalenceClass *parent_ec, Relids oldrelids,
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)
0