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

Commitbae3fef

Browse files
committed
Tweak choose_bitmap_and() heuristics in the light of example provided in bug
#2075: consider an index redundant if any of its index conditions were alreadyused, rather than if all of them were. Also, make the selectivity comparisona bit fuzzy, so that very small differences in estimated selectivities don'tskew the results.
1 parent150131d commitbae3fef

File tree

1 file changed

+54
-8
lines changed

1 file changed

+54
-8
lines changed

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

Lines changed: 54 additions & 8 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.194 2005/11/25 19:47:49 tgl Exp $
12+
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.195 2005/11/30 17:10:19 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -53,6 +53,7 @@ static List *find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
5353
staticPath*choose_bitmap_and(PlannerInfo*root,RelOptInfo*rel,List*paths);
5454
staticintbitmap_path_comparator(constvoid*a,constvoid*b);
5555
staticCostbitmap_and_cost_est(PlannerInfo*root,RelOptInfo*rel,List*paths);
56+
staticboollists_intersect_ptr(List*list1,List*list2);
5657
staticboolmatch_clause_to_indexcol(IndexOptInfo*index,
5758
intindexcol,Oidopclass,
5859
RestrictInfo*rinfo,
@@ -562,20 +563,28 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
562563
* In theory we should consider every nonempty subset of the given paths.
563564
* In practice that seems like overkill, given the crude nature of the
564565
* estimates, not to mention the possible effects of higher-level AND and
565-
* OR clauses.As a compromise, we sort the paths by selectivity. We
566+
* OR clauses.As a compromise, we sort the paths by selectivity.We
566567
* always take the first, and sequentially add on paths that result in a
567568
* lower estimated cost.
568569
*
569570
* We also make some effort to detect directly redundant input paths, as
570571
* can happen if there are multiple possibly usable indexes. For this we
571572
* look only at plain IndexPath and single-element BitmapOrPath inputs
572573
* (the latter can arise in the presence of ScalarArrayOpExpr quals). We
573-
* consider an index redundant ifall its index conditions were already
574+
* consider an index redundant ifany of its index conditions were already
574575
* used by earlier indexes. (We could use predicate_implied_by to have a
575576
* more intelligent, but much more expensive, check --- but in most cases
576577
* simple pointer equality should suffice, since after all the index
577578
* conditions are all coming from the same RestrictInfo lists.)
578579
*
580+
* You might think the condition for redundancy should be "all index
581+
* conditions already used", not "any", but this turns out to be wrong.
582+
* For example, if we use an index on A, and then come to an index with
583+
* conditions on A and B, the only way that the second index can be later
584+
* in the selectivity-order sort is if the condition on B is completely
585+
* non-selective. In any case, we'd surely be drastically misestimating
586+
* the selectivity if we count the same condition twice.
587+
*
579588
* XXX is there any risk of throwing away a useful partial index here
580589
* because we don't explicitly look at indpred? At least in simple cases,
581590
* the partial index will sort before competing non-partial indexes and so
@@ -620,7 +629,7 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
620629
if (IsA(newpath,IndexPath))
621630
{
622631
newqual= ((IndexPath*)newpath)->indexclauses;
623-
if (list_difference_ptr(newqual,qualsofar)==NIL)
632+
if (lists_intersect_ptr(newqual,qualsofar))
624633
continue;/* redundant */
625634
}
626635
elseif (IsA(newpath,BitmapOrPath))
@@ -630,7 +639,7 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
630639
if (list_length(orquals)==1&&
631640
IsA(linitial(orquals),IndexPath))
632641
newqual= ((IndexPath*)linitial(orquals))->indexclauses;
633-
if (list_difference_ptr(newqual,qualsofar)==NIL)
642+
if (lists_intersect_ptr(newqual,qualsofar))
634643
continue;/* redundant */
635644
}
636645

@@ -665,19 +674,27 @@ bitmap_path_comparator(const void *a, const void *b)
665674
Costbcost;
666675
Selectivityaselec;
667676
Selectivitybselec;
677+
Selectivitydiff;
668678

669679
cost_bitmap_tree_node(pa,&acost,&aselec);
670680
cost_bitmap_tree_node(pb,&bcost,&bselec);
671681

672-
if (aselec<bselec)
682+
/*
683+
* Since selectivities are often pretty crude, don't put blind faith
684+
* in them; if the selectivities are within 1% of being the same, treat
685+
* them as equal and sort by cost instead.
686+
*/
687+
diff=aselec-bselec;
688+
if (diff<-0.01)
673689
return-1;
674-
if (aselec>bselec)
690+
if (diff>0.01)
675691
return1;
676-
/* if identical selectivity, sort by cost */
692+
677693
if (acost<bcost)
678694
return-1;
679695
if (acost>bcost)
680696
return1;
697+
681698
return0;
682699
}
683700

@@ -704,6 +721,35 @@ bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel, List *paths)
704721
}
705722

706723

724+
/*
725+
* lists_intersect_ptr
726+
*Detect whether two lists have a nonempty intersection,
727+
*using pointer equality to compare members.
728+
*
729+
* This possibly should go into list.c, but it doesn't yet have any use
730+
* except in choose_bitmap_and.
731+
*/
732+
staticbool
733+
lists_intersect_ptr(List*list1,List*list2)
734+
{
735+
ListCell*cell1;
736+
737+
foreach(cell1,list1)
738+
{
739+
void*datum1=lfirst(cell1);
740+
ListCell*cell2;
741+
742+
foreach(cell2,list2)
743+
{
744+
if (lfirst(cell2)==datum1)
745+
return true;
746+
}
747+
}
748+
749+
return false;
750+
}
751+
752+
707753
/****************************************************************************
708754
*---- ROUTINES TO CHECK RESTRICTIONS ----
709755
****************************************************************************/

0 commit comments

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