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

Commit3104a92

Browse files
committed
Another go at making pred_test() handle all reasonable combinations
of AND and OR clauses. The key point here is that an OR on thepredicate side has to be treated gingerly: we may be able to provethat the OR is implied even when no one of its components is implied.For example (x OR y) implies (x OR y OR z) even though no one of x,y, or z can be individually proven. This code handles both theexample shown recently by Sergey Koshcheyev and the one shown lastOctober by Dawid Kuroczko.
1 parent47ea714 commit3104a92

File tree

1 file changed

+158
-117
lines changed

1 file changed

+158
-117
lines changed

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

Lines changed: 158 additions & 117 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.168 2005/03/01 00:24:52 tgl Exp $
12+
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.169 2005/03/02 04:10:53 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -64,9 +64,7 @@ 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_restrict_list(Expr*predicate,List*restrictinfo_list);
68-
staticboolpred_test_recurse_restrict(Expr*predicate,Node*clause);
69-
staticboolpred_test_recurse_pred(Expr*predicate,Node*clause);
67+
staticboolpred_test_recurse(Node*clause,Node*predicate);
7068
staticboolpred_test_simple_clause(Expr*predicate,Node*clause);
7169
staticRelidsindexable_outerrelids(RelOptInfo*rel,IndexOptInfo*index);
7270
staticPath*make_innerjoin_index_path(Query*root,
@@ -749,30 +747,17 @@ check_partial_indexes(Query *root, RelOptInfo *rel)
749747
* Recursively checks whether the clauses in restrictinfo_list imply
750748
* that the given predicate is true.
751749
*
752-
* This routine (together with the routines it calls) iterates over
753-
* ANDs in the predicate first, then breaks down the restriction list
754-
* to its constituent AND/OR elements, and iterates over ORs
755-
* in the predicate last. This order is important to make the test
756-
* succeed whenever possible. --Nels, Jan '93
757-
*
758-
* For example, a restriction (a OR b) certainly implies a predicate
759-
* (a OR b OR c), but no one element of the predicate is individually
760-
* implied by the restriction. By expanding the predicate ORs last
761-
* we are able to prove that the whole predicate is implied by each arm
762-
* of the restriction. Conversely consider predicate (a AND b) with
763-
* restriction (a AND b AND c). This should be implied but we will
764-
* fail to prove it if we dissect the restriction first.
765-
*
766750
* The top-level List structure of each list corresponds to an AND list.
767-
* We assume that canonicalize_qual() has been applied and so there
768-
* are no explicit ANDs immediately below the top-level List structure.
769-
* (If this is not true we might fail to prove an implication that is
770-
* valid, but no worse consequences will ensue.)
751+
* We assume that canonicalize_qual() has been applied and so there are
752+
* no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
753+
* including AND just below the top-level List structure).
754+
* If this is not true we might fail to prove an implication that is
755+
* valid, but no worse consequences will ensue.
771756
*/
772757
bool
773758
pred_test(List*predicate_list,List*restrictinfo_list)
774759
{
775-
ListCell*pred;
760+
ListCell*item;
776761

777762
/*
778763
* Note: if Postgres tried to optimize queries by forming equivalence
@@ -793,133 +778,189 @@ pred_test(List *predicate_list, List *restrictinfo_list)
793778
return false;/* no restriction clauses: the test must
794779
* fail */
795780

796-
/* Take care of the AND semantics of the top-level predicate list */
797-
foreach(pred,predicate_list)
781+
/*
782+
* In all cases where the predicate is an AND-clause, pred_test_recurse()
783+
* will prefer to iterate over the predicate's components. So we can
784+
* just do that to start with here, and eliminate the need for
785+
* pred_test_recurse() to handle a bare List on the predicate side.
786+
*
787+
* Logic is: restriction must imply each of the AND'ed predicate items.
788+
*/
789+
foreach(item,predicate_list)
798790
{
799-
/*
800-
* if any clause is not implied, the whole predicate is not
801-
* implied.
802-
*/
803-
if (!pred_test_restrict_list(lfirst(pred),restrictinfo_list))
791+
if (!pred_test_recurse((Node*)restrictinfo_list,lfirst(item)))
804792
return false;
805793
}
806794
return true;
807795
}
808796

809797

810-
/*
811-
* pred_test_restrict_list
812-
* Does the "predicate inclusion test" for one AND clause of a predicate
813-
* expression. Here we take care of the AND semantics of the top-level
814-
* restrictinfo list.
815-
*/
816-
staticbool
817-
pred_test_restrict_list(Expr*predicate,List*restrictinfo_list)
818-
{
819-
ListCell*item;
820-
821-
foreach(item,restrictinfo_list)
822-
{
823-
/* if any clause implies the predicate, return true */
824-
if (pred_test_recurse_restrict(predicate,
825-
(Node*)lfirst(item)))
826-
return true;
827-
}
828-
return false;
829-
}
830-
831-
832-
/*
833-
* pred_test_recurse_restrict
834-
* Does the "predicate inclusion test" for one AND clause of a predicate
835-
* expression. Here we recursively deal with the possibility that the
836-
* restriction-list element is itself an AND or OR structure; also,
837-
* we strip off RestrictInfo nodes to find bare qualifier expressions.
798+
/*----------
799+
* pred_test_recurse
800+
* Does the "predicate inclusion test" for non-NULL restriction and
801+
* predicate clauses.
802+
*
803+
* The logic followed here is ("=>" means "implies"):
804+
*atom A => atom B iff:pred_test_simple_clause says so
805+
*atom A => AND-expr B iff:A => each of B's components
806+
*atom A => OR-expr B iff:A => any of B's components
807+
*AND-expr A => atom B iff:any of A's components => B
808+
*AND-expr A => AND-expr B iff:A => each of B's components
809+
*AND-expr A => OR-expr B iff:A => any of B's components,
810+
**or* any of A's components => B
811+
*OR-expr A => atom B iff:each of A's components => B
812+
*OR-expr A => AND-expr B iff:A => each of B's components
813+
*OR-expr A => OR-expr B iff:each of A's components => any of B's
814+
*
815+
* An "atom" is anything other than an AND or OR node. Notice that we don't
816+
* have any special logic to handle NOT nodes; these should have been pushed
817+
* down or eliminated where feasible by prepqual.c.
818+
*
819+
* We can't recursively expand either side first, but have to interleave
820+
* the expansions per the above rules, to be sure we handle all of these
821+
* examples:
822+
*(x OR y) => (x OR y OR z)
823+
*(x AND y AND z) => (x AND y)
824+
*(x AND y) => ((x AND y) OR z)
825+
*((x OR y) AND z) => (x OR y)
826+
* This is still not an exhaustive test, but it handles most normal cases
827+
* under the assumption that both inputs have been AND/OR flattened.
828+
*
829+
* A bare List node on the restriction side is interpreted as an AND clause,
830+
* in order to handle the top-level restriction List properly. However we
831+
* need not consider a List on the predicate side since pred_test() already
832+
* expanded it.
833+
*
834+
* We have to be prepared to handle RestrictInfo nodes in the restrictinfo
835+
* tree, though not in the predicate tree.
836+
*----------
838837
*/
839838
staticbool
840-
pred_test_recurse_restrict(Expr*predicate,Node*clause)
839+
pred_test_recurse(Node*clause,Node*predicate)
841840
{
842-
List*items;
843841
ListCell*item;
844842

845843
Assert(clause!=NULL);
844+
/* skip through RestrictInfo */
846845
if (IsA(clause,RestrictInfo))
847846
{
848-
RestrictInfo*restrictinfo= (RestrictInfo*)clause;
849-
850-
returnpred_test_recurse_restrict(predicate,
851-
(Node*)restrictinfo->clause);
847+
clause= (Node*) ((RestrictInfo*)clause)->clause;
848+
Assert(clause!=NULL);
849+
Assert(!IsA(clause,RestrictInfo));
852850
}
853-
elseif (or_clause(clause))
851+
Assert(predicate!=NULL);
852+
853+
/*
854+
* Since a restriction List clause is handled the same as an AND clause,
855+
* we can avoid duplicate code like this:
856+
*/
857+
if (and_clause(clause))
858+
clause= (Node*) ((BoolExpr*)clause)->args;
859+
860+
if (IsA(clause,List))
854861
{
855-
items= ((BoolExpr*)clause)->args;
856-
foreach(item,items)
862+
if (and_clause(predicate))
857863
{
858-
/* if any OR item doesn't imply the predicate, clause doesn't */
859-
if (!pred_test_recurse_restrict(predicate,lfirst(item)))
860-
return false;
864+
/* AND-clause => AND-clause if A implies each of B's items */
865+
foreach(item, ((BoolExpr*)predicate)->args)
866+
{
867+
if (!pred_test_recurse(clause,lfirst(item)))
868+
return false;
869+
}
870+
return true;
871+
}
872+
elseif (or_clause(predicate))
873+
{
874+
/* AND-clause => OR-clause if A implies any of B's items */
875+
/* Needed to handle (x AND y) => ((x AND y) OR z) */
876+
foreach(item, ((BoolExpr*)predicate)->args)
877+
{
878+
if (pred_test_recurse(clause,lfirst(item)))
879+
return true;
880+
}
881+
/* Also check if any of A's items implies B */
882+
/* Needed to handle ((x OR y) AND z) => (x OR y) */
883+
foreach(item, (List*)clause)
884+
{
885+
if (pred_test_recurse(lfirst(item),predicate))
886+
return true;
887+
}
888+
return false;
889+
}
890+
else
891+
{
892+
/* AND-clause => atom if any of A's items implies B */
893+
foreach(item, (List*)clause)
894+
{
895+
if (pred_test_recurse(lfirst(item),predicate))
896+
return true;
897+
}
898+
return false;
861899
}
862-
return true;
863900
}
864-
elseif (and_clause(clause))
901+
elseif (or_clause(clause))
865902
{
866-
items= ((BoolExpr*)clause)->args;
867-
foreach(item,items)
903+
if (or_clause(predicate))
868904
{
869905
/*
870-
*if any AND item implies the predicate, the whole clause
871-
*does
906+
*OR-clause => OR-clause if each of A's items implies any of
907+
*B's items. Messy but can't do it any more simply.
872908
*/
873-
if (pred_test_recurse_restrict(predicate,lfirst(item)))
874-
return true;
909+
foreach(item, ((BoolExpr*)clause)->args)
910+
{
911+
Node*citem=lfirst(item);
912+
ListCell*item2;
913+
914+
foreach(item2, ((BoolExpr*)predicate)->args)
915+
{
916+
if (pred_test_recurse(citem,lfirst(item2)))
917+
break;
918+
}
919+
if (item2==NULL)
920+
return false;/* doesn't imply any of B's */
921+
}
922+
return true;
923+
}
924+
else
925+
{
926+
/* OR-clause => AND-clause if each of A's items implies B */
927+
/* OR-clause => atom if each of A's items implies B */
928+
foreach(item, ((BoolExpr*)clause)->args)
929+
{
930+
if (!pred_test_recurse(lfirst(item),predicate))
931+
return false;
932+
}
933+
return true;
875934
}
876-
return false;
877935
}
878936
else
879-
returnpred_test_recurse_pred(predicate,clause);
880-
}
881-
882-
883-
/*
884-
* pred_test_recurse_pred
885-
* Does the "predicate inclusion test" for one conjunct of a predicate
886-
* expression. Here we recursively deal with the possibility that the
887-
* predicate conjunct is itself an AND or OR structure.
888-
*/
889-
staticbool
890-
pred_test_recurse_pred(Expr*predicate,Node*clause)
891-
{
892-
List*items;
893-
ListCell*item;
894-
895-
Assert(predicate!=NULL);
896-
if (or_clause((Node*)predicate))
897937
{
898-
items= ((BoolExpr*)predicate)->args;
899-
foreach(item,items)
938+
if (and_clause(predicate))
900939
{
901-
/* if any item is implied, the whole predicate is implied */
902-
if (pred_test_recurse_pred(lfirst(item),clause))
903-
return true;
940+
/* atom => AND-clause if A implies each of B's items */
941+
foreach(item, ((BoolExpr*)predicate)->args)
942+
{
943+
if (!pred_test_recurse(clause,lfirst(item)))
944+
return false;
945+
}
946+
return true;
904947
}
905-
return false;
906-
}
907-
elseif (and_clause((Node*)predicate))
908-
{
909-
items= ((BoolExpr*)predicate)->args;
910-
foreach(item,items)
948+
elseif (or_clause(predicate))
911949
{
912-
/*
913-
* if any item is not implied, the whole predicate is not
914-
* implied
915-
*/
916-
if (!pred_test_recurse_pred(lfirst(item),clause))
917-
return false;
950+
/* atom => OR-clause if A implies any of B's items */
951+
foreach(item, ((BoolExpr*)predicate)->args)
952+
{
953+
if (pred_test_recurse(clause,lfirst(item)))
954+
return true;
955+
}
956+
return false;
957+
}
958+
else
959+
{
960+
/* atom => atom is the base case */
961+
returnpred_test_simple_clause((Expr*)predicate,clause);
918962
}
919-
return true;
920963
}
921-
else
922-
returnpred_test_simple_clause(predicate,clause);
923964
}
924965

925966

0 commit comments

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