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

Commit2611285

Browse files
committed
Fix OR-index-scan planner to recognize that a partial index is usable
for scanning one term of an OR clause if the index's predicate is impliedby that same OR clause term (possibly in conjunction with top-level WHEREclauses). Per recent example from Dawid Kuroczko,http://archives.postgresql.org/pgsql-performance/2004-10/msg00095.phpAlso, fix a very long-standing bug in index predicate testing, namely thebizarre ordering of decomposition of predicate and restriction clauses.AFAICS the correct way is to break down the predicate all the way, andthen for each component term see if you can prove it from the entirerestriction set. The original coding had a purely-implementation-artifactdistinction between ANDing at the top level and ANDing below that, andproceeded to get the decomposition order wrong everywhere below the toplevel, with the result that even slightly complicated AND/OR predicatescould not be proven. For instance, givencreate index foop on foo(f2) where f1=42 or f1=1 or (f1 = 11 and f2 = 55);the old code would fail to match this index to the queryselect * from foo where f1 = 11 and f2 = 55;when it obviously ought to match.
1 parentc0c4883 commit2611285

File tree

3 files changed

+101
-74
lines changed

3 files changed

+101
-74
lines changed

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

Lines changed: 67 additions & 68 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.164 2004/08/29 05:06:43 momjian Exp $
12+
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.165 2004/10/11 22:56:56 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -64,10 +64,9 @@ static bool match_join_clause_to_indexcol(RelOptInfo *rel, IndexOptInfo *index,
6464
RestrictInfo*rinfo);
6565
staticOidindexable_operator(Expr*clause,Oidopclass,
6666
boolindexkey_on_left);
67-
staticboolpred_test(List*predicate_list,List*restrictinfo_list);
67+
staticboolpred_test_recurse_pred(Expr*predicate,List*restrictinfo_list);
6868
staticboolpred_test_restrict_list(Expr*predicate,List*restrictinfo_list);
69-
staticboolpred_test_recurse_clause(Expr*predicate,Node*clause);
70-
staticboolpred_test_recurse_pred(Expr*predicate,Node*clause);
69+
staticboolpred_test_recurse_restrict(Expr*predicate,Node*clause);
7170
staticboolpred_test_simple_clause(Expr*predicate,Node*clause);
7271
staticRelidsindexable_outerrelids(RelOptInfo*rel,IndexOptInfo*index);
7372
staticPath*make_innerjoin_index_path(Query*root,
@@ -750,14 +749,13 @@ check_partial_indexes(Query *root, RelOptInfo *rel)
750749
* Recursively checks whether the clauses in restrictinfo_list imply
751750
* that the given predicate is true.
752751
*
753-
* This routine (together with the routines it calls) iterates over
754-
* ANDs in the predicate first, then reduces the qualification
755-
* clauses down to their constituent terms, and iterates over ORs
756-
* in the predicate last. This order is important to make the test
757-
* succeed whenever possible (assuming the predicate has been converted
758-
* to CNF format). --Nels, Jan '93
752+
* This routine (together with the routines it calls) first breaks down
753+
* the predicate to its constituent AND/OR elements, then similarly
754+
* breaks down the restriction clauses to AND/OR elements in an effort
755+
* to prove that each predicate element is implied. The top-level
756+
* List structure of each list corresponds to an AND list.
759757
*/
760-
staticbool
758+
bool
761759
pred_test(List*predicate_list,List*restrictinfo_list)
762760
{
763761
ListCell*pred;
@@ -785,20 +783,63 @@ pred_test(List *predicate_list, List *restrictinfo_list)
785783
{
786784
/*
787785
* if any clause is not implied, the whole predicate is not
788-
* implied. Note we assume that any sub-ANDs have been flattened
789-
* when the predicate was fed through canonicalize_qual().
786+
* implied.
790787
*/
791-
if (!pred_test_restrict_list(lfirst(pred),restrictinfo_list))
788+
if (!pred_test_recurse_pred(lfirst(pred),restrictinfo_list))
792789
return false;
793790
}
794791
return true;
795792
}
796793

797794

798795
/*
799-
*pred_test_restrict_list
796+
*pred_test_recurse_pred
800797
* Does the "predicate inclusion test" for one conjunct of a predicate
801-
* expression.
798+
* expression. Here we recursively deal with the possibility that the
799+
* predicate conjunct is itself an AND or OR structure.
800+
*/
801+
staticbool
802+
pred_test_recurse_pred(Expr*predicate,List*restrictinfo_list)
803+
{
804+
List*items;
805+
ListCell*item;
806+
807+
Assert(predicate!=NULL);
808+
if (or_clause((Node*)predicate))
809+
{
810+
items= ((BoolExpr*)predicate)->args;
811+
foreach(item,items)
812+
{
813+
/* if any item is implied, the whole predicate is implied */
814+
if (pred_test_recurse_pred(lfirst(item),restrictinfo_list))
815+
return true;
816+
}
817+
return false;
818+
}
819+
elseif (and_clause((Node*)predicate))
820+
{
821+
items= ((BoolExpr*)predicate)->args;
822+
foreach(item,items)
823+
{
824+
/*
825+
* if any item is not implied, the whole predicate is not
826+
* implied
827+
*/
828+
if (!pred_test_recurse_pred(lfirst(item),restrictinfo_list))
829+
return false;
830+
}
831+
return true;
832+
}
833+
else
834+
returnpred_test_restrict_list(predicate,restrictinfo_list);
835+
}
836+
837+
838+
/*
839+
* pred_test_restrict_list
840+
* Does the "predicate inclusion test" for one element of a predicate
841+
* expression. Here we take care of the AND semantics of the top-level
842+
* restrictinfo list.
802843
*/
803844
staticbool
804845
pred_test_restrict_list(Expr*predicate,List*restrictinfo_list)
@@ -809,23 +850,25 @@ pred_test_restrict_list(Expr *predicate, List *restrictinfo_list)
809850
{
810851
RestrictInfo*restrictinfo= (RestrictInfo*)lfirst(item);
811852

853+
Assert(IsA(restrictinfo,RestrictInfo));
854+
812855
/* if any clause implies the predicate, return true */
813-
if (pred_test_recurse_clause(predicate,
814-
(Node*)restrictinfo->clause))
856+
if (pred_test_recurse_restrict(predicate,
857+
(Node*)restrictinfo->clause))
815858
return true;
816859
}
817860
return false;
818861
}
819862

820863

821864
/*
822-
*pred_test_recurse_clause
823-
* Does the "predicate inclusion test" fora general restriction-clause
865+
*pred_test_recurse_restrict
866+
* Does the "predicate inclusion test" forone element of a predicate
824867
* expression. Here we recursively deal with the possibility that the
825-
* restriction clause is itself an AND or OR structure.
868+
* restriction-list element is itself an AND or OR structure.
826869
*/
827870
staticbool
828-
pred_test_recurse_clause(Expr*predicate,Node*clause)
871+
pred_test_recurse_restrict(Expr*predicate,Node*clause)
829872
{
830873
List*items;
831874
ListCell*item;
@@ -837,7 +880,7 @@ pred_test_recurse_clause(Expr *predicate, Node *clause)
837880
foreach(item,items)
838881
{
839882
/* if any OR item doesn't imply the predicate, clause doesn't */
840-
if (!pred_test_recurse_clause(predicate,lfirst(item)))
883+
if (!pred_test_recurse_restrict(predicate,lfirst(item)))
841884
return false;
842885
}
843886
return true;
@@ -851,55 +894,11 @@ pred_test_recurse_clause(Expr *predicate, Node *clause)
851894
* if any AND item implies the predicate, the whole clause
852895
* does
853896
*/
854-
if (pred_test_recurse_clause(predicate,lfirst(item)))
897+
if (pred_test_recurse_restrict(predicate,lfirst(item)))
855898
return true;
856899
}
857900
return false;
858901
}
859-
else
860-
returnpred_test_recurse_pred(predicate,clause);
861-
}
862-
863-
864-
/*
865-
* pred_test_recurse_pred
866-
* Does the "predicate inclusion test" for one conjunct of a predicate
867-
* expression for a simple restriction clause. Here we recursively deal
868-
* with the possibility that the predicate conjunct is itself an AND or
869-
* OR structure.
870-
*/
871-
staticbool
872-
pred_test_recurse_pred(Expr*predicate,Node*clause)
873-
{
874-
List*items;
875-
ListCell*item;
876-
877-
Assert(predicate!=NULL);
878-
if (or_clause((Node*)predicate))
879-
{
880-
items= ((BoolExpr*)predicate)->args;
881-
foreach(item,items)
882-
{
883-
/* if any item is implied, the whole predicate is implied */
884-
if (pred_test_recurse_pred(lfirst(item),clause))
885-
return true;
886-
}
887-
return false;
888-
}
889-
elseif (and_clause((Node*)predicate))
890-
{
891-
items= ((BoolExpr*)predicate)->args;
892-
foreach(item,items)
893-
{
894-
/*
895-
* if any item is not implied, the whole predicate is not
896-
* implied
897-
*/
898-
if (!pred_test_recurse_pred(lfirst(item),clause))
899-
return false;
900-
}
901-
return true;
902-
}
903902
else
904903
returnpred_test_simple_clause(predicate,clause);
905904
}

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

Lines changed: 32 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/path/orindxpath.c,v 1.62 2004/08/29 05:06:43 momjian Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/path/orindxpath.c,v 1.63 2004/10/11 22:56:56 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -355,15 +355,42 @@ best_or_subclause_index(Query *root,
355355
List*indexquals;
356356
Pathsubclause_path;
357357

358-
/* Ignore partial indexes that do not match the query */
358+
/*
359+
* Ignore partial indexes that do not match the query. If predOK
360+
* is true then the index's predicate is implied by top-level
361+
* restriction clauses, so we can use it. However, it might also
362+
* be implied by the current OR subclause (perhaps in conjunction
363+
* with the top-level clauses), in which case we can use it for this
364+
* particular scan.
365+
*
366+
* XXX this code is partially redundant with logic in
367+
* group_clauses_by_indexkey_for_or(); consider refactoring.
368+
*/
359369
if (index->indpred!=NIL&& !index->predOK)
360-
continue;
370+
{
371+
List*subclauserinfos;
372+
373+
if (and_clause((Node*)subclause))
374+
subclauserinfos=list_copy(((BoolExpr*)subclause)->args);
375+
elseif (IsA(subclause,RestrictInfo))
376+
subclauserinfos=list_make1(subclause);
377+
else
378+
continue;/* probably can't happen */
379+
if (!pred_test(index->indpred,
380+
list_concat(subclauserinfos,
381+
rel->baserestrictinfo)))
382+
continue;
383+
}
361384

362385
/* Collect index clauses usable with this index */
363386
indexclauses=group_clauses_by_indexkey_for_or(rel,index,subclause);
364387

365-
/* Ignore index if it doesn't match the subclause at all */
366-
if (indexclauses==NIL)
388+
/*
389+
* Ignore index if it doesn't match the subclause at all; except
390+
* that if it's a partial index, consider it anyway, since the
391+
* selectivity of the predicate alone might make the index useful.
392+
*/
393+
if (indexclauses==NIL&&index->indpred==NIL)
367394
continue;
368395

369396
/* Convert clauses to indexquals the executor can handle */

‎src/include/optimizer/paths.h‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
* Portions Copyright (c) 1996-2004, PostgreSQL Global Development Group
99
* Portions Copyright (c) 1994, Regents of the University of California
1010
*
11-
* $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.75 2004/08/29 05:06:57 momjian Exp $
11+
* $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.76 2004/10/11 22:57:00 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -44,6 +44,7 @@ extern List *group_clauses_by_indexkey_for_or(RelOptInfo *rel,
4444
externList*expand_indexqual_conditions(IndexOptInfo*index,
4545
List*clausegroups);
4646
externvoidcheck_partial_indexes(Query*root,RelOptInfo*rel);
47+
externboolpred_test(List*predicate_list,List*restrictinfo_list);
4748
externList*flatten_clausegroups_list(List*clausegroups);
4849
externExpr*make_expr_from_indexclauses(List*indexclauses);
4950

0 commit comments

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