Skip to content

Commit cad5f4a

Browse files
tglsfdctglsfdc
committed
Make some improvements in the intelligence of the partial-index
predicate tester. It can now deal with commuted clauses (for instance, 4 < x implies x > 3), subclauses more complicated than a simple Var (for example, upper(x) = 't' implies upper(x) > 'a'), and <> operators (for example, x < 3 implies x <> 4). Still only understands operators associated with btree opclasses, though. Inspired by example from Martin Hampl.
1 parent 5049838 commit cad5f4a

File tree

1 file changed

+190
-52
lines changed

1 file changed

+190
-52
lines changed

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

Lines changed: 190 additions & 52 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.155 2004/01/05 23:39:54 tgl Exp $
12+
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.156 2004/01/07 22:02:48 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -918,13 +918,18 @@ pred_test_recurse_pred(Expr *predicate, Node *clause)
918918

919919
/*
920920
* Define an "operator implication table" for btree operators ("strategies").
921-
* The "strategy numbers" are: (1) < (2) <= (3) = (4) >= (5) >
921+
*
922+
* The strategy numbers defined by btree indexes (see access/skey.h) are:
923+
* (1) < (2) <= (3) = (4) >= (5) >
924+
* and in addition we use (6) to represent <>. <> is not a btree-indexable
925+
* operator, but we assume here that if the equality operator of a btree
926+
* opclass has a negator operator, the negator behaves as <> for the opclass.
922927
*
923928
* The interpretation of:
924929
*
925930
* test_op = BT_implic_table[given_op-1][target_op-1]
926931
*
927-
* where test_op, given_op and target_op are strategy numbers (from 1 to 5)
932+
* where test_op, given_op and target_op are strategy numbers (from 1 to 6)
928933
* of btree operators, is as follows:
929934
*
930935
* If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
@@ -933,17 +938,30 @@ pred_test_recurse_pred(Expr *predicate, Node *clause)
933938
* then the target expression must be true; if the test returns false, then
934939
* the target expression may be false.
935940
*
936-
* An entry where test_op==0 means the implication cannot be determined, i.e.,
937-
* this test should always be considered false.
941+
* An entry where test_op == 0 means the implication cannot be determined,
942+
* i.e., this test should always be considered false.
938943
*/
939944

945+
#define BTLT BTLessStrategyNumber
946+
#define BTLE BTLessEqualStrategyNumber
947+
#define BTEQ BTEqualStrategyNumber
948+
#define BTGE BTGreaterEqualStrategyNumber
949+
#define BTGT BTGreaterStrategyNumber
950+
#define BTNE 6
951+
940952
static const StrategyNumber
941-
BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = {
942-
{4, 4, 0, 0, 0},
943-
{5, 4, 0, 0, 0},
944-
{5, 4, 3, 2, 1},
945-
{0, 0, 0, 2, 1},
946-
{0, 0, 0, 2, 2}
953+
BT_implic_table[6][6] = {
954+
/*
955+
* The target operator:
956+
*
957+
* LT LE EQ GE GT NE
958+
*/
959+
{BTGE, BTGE, 0, 0, 0, BTGE}, /* LT */
960+
{BTGT, BTGE, 0, 0, 0, BTGT}, /* LE */
961+
{BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE}, /* EQ */
962+
{ 0, 0, 0, BTLE, BTLT, BTLT}, /* GE */
963+
{ 0, 0, 0, BTLE, BTLE, BTLE}, /* GT */
964+
{ 0, 0, 0, 0, 0, BTEQ} /* NE */
947965
};
948966

949967

@@ -969,12 +987,19 @@ static const StrategyNumber
969987
static bool
970988
pred_test_simple_clause(Expr *predicate, Node *clause)
971989
{
972-
Var *pred_var,
990+
Node *leftop,
991+
*rightop;
992+
Node *pred_var,
973993
*clause_var;
974994
Const *pred_const,
975995
*clause_const;
996+
bool pred_var_on_left,
997+
clause_var_on_left,
998+
pred_op_negated;
976999
Oid pred_op,
9771000
clause_op,
1001+
pred_op_negator,
1002+
clause_op_negator,
9781003
test_op = InvalidOid;
9791004
Oid opclass_id;
9801005
bool found = false;
@@ -997,40 +1022,89 @@ pred_test_simple_clause(Expr *predicate, Node *clause)
9971022

9981023
/*
9991024
* Can't do anything more unless they are both binary opclauses with a
1000-
* Var on the left and a Const on the right. (XXX someday try to
1001-
* commute Const/Var cases?) Note we don't have to think about binary
1002-
* relabeling of the Const node, since that would have been folded right
1003-
* into the Const.
1025+
* Const on one side, and identical subexpressions on the other sides.
1026+
* Note we don't have to think about binary relabeling of the Const node,
1027+
* since that would have been folded right into the Const.
1028+
*
1029+
* If either Const is null, we also fail right away; this assumes that
1030+
* the test operator will always be strict.
10041031
*/
10051032
if (!is_opclause(predicate))
10061033
return false;
1007-
pred_var = (Var *) get_leftop(predicate);
1008-
pred_const = (Const *) get_rightop(predicate);
1034+
leftop = get_leftop(predicate);
1035+
rightop = get_rightop(predicate);
1036+
if (rightop == NULL)
1037+
return false; /* not a binary opclause */
1038+
if (IsA(rightop, Const))
1039+
{
1040+
pred_var = leftop;
1041+
pred_const = (Const *) rightop;
1042+
pred_var_on_left = true;
1043+
}
1044+
else if (IsA(leftop, Const))
1045+
{
1046+
pred_var = rightop;
1047+
pred_const = (Const *) leftop;
1048+
pred_var_on_left = false;
1049+
}
1050+
else
1051+
return false; /* no Const to be found */
1052+
if (pred_const->constisnull)
1053+
return false;
10091054

10101055
if (!is_opclause(clause))
10111056
return false;
1012-
clause_var = (Var *) get_leftop((Expr *) clause);
1013-
clause_const = (Const *) get_rightop((Expr *) clause);
1014-
1015-
if (!IsA(clause_var, Var) ||
1016-
clause_const == NULL ||
1017-
!IsA(clause_const, Const) ||
1018-
!IsA(pred_var, Var) ||
1019-
pred_const == NULL ||
1020-
!IsA(pred_const, Const))
1057+
leftop = get_leftop((Expr *) clause);
1058+
rightop = get_rightop((Expr *) clause);
1059+
if (rightop == NULL)
1060+
return false; /* not a binary opclause */
1061+
if (IsA(rightop, Const))
1062+
{
1063+
clause_var = leftop;
1064+
clause_const = (Const *) rightop;
1065+
clause_var_on_left = true;
1066+
}
1067+
else if (IsA(leftop, Const))
1068+
{
1069+
clause_var = rightop;
1070+
clause_const = (Const *) leftop;
1071+
clause_var_on_left = false;
1072+
}
1073+
else
1074+
return false; /* no Const to be found */
1075+
if (clause_const->constisnull)
10211076
return false;
10221077

10231078
/*
1024-
* The implication can't be determined unless the predicate and the
1025-
* clause refer to the same attribute.
1079+
* Check for matching subexpressions on the non-Const sides. We used to
1080+
* only allow a simple Var, but it's about as easy to allow any
1081+
* expression. Remember we already know that the pred expression does
1082+
* not contain any non-immutable functions, so identical expressions
1083+
* should yield identical results.
10261084
*/
1027-
if (clause_var->varno != pred_var->varno ||
1028-
clause_var->varattno != pred_var->varattno)
1085+
if (!equal(pred_var, clause_var))
10291086
return false;
10301087

1031-
/* Get the operators for the two clauses we're comparing */
1088+
/*
1089+
* Okay, get the operators in the two clauses we're comparing.
1090+
* Commute them if needed so that we can assume the variables are
1091+
* on the left.
1092+
*/
10321093
pred_op = ((OpExpr *) predicate)->opno;
1094+
if (!pred_var_on_left)
1095+
{
1096+
pred_op = get_commutator(pred_op);
1097+
if (!OidIsValid(pred_op))
1098+
return false;
1099+
}
1100+
10331101
clause_op = ((OpExpr *) clause)->opno;
1102+
if (!clause_var_on_left)
1103+
{
1104+
clause_op = get_commutator(clause_op);
1105+
if (!OidIsValid(clause_op))
1106+
return false;
1107+
}
10341108

10351109
/*
10361110
* Try to find a btree opclass containing the needed operators.
@@ -1052,6 +1126,28 @@ pred_test_simple_clause(Expr *predicate, Node *clause)
10521126
ObjectIdGetDatum(pred_op),
10531127
0, 0, 0);
10541128

1129+
/*
1130+
* If we couldn't find any opclass containing the pred_op, perhaps it
1131+
* is a <> operator. See if it has a negator that is in an opclass.
1132+
*/
1133+
pred_op_negated = false;
1134+
if (catlist->n_members == 0)
1135+
{
1136+
pred_op_negator = get_negator(pred_op);
1137+
if (OidIsValid(pred_op_negator))
1138+
{
1139+
pred_op_negated = true;
1140+
ReleaseSysCacheList(catlist);
1141+
catlist = SearchSysCacheList(AMOPOPID, 1,
1142+
ObjectIdGetDatum(pred_op_negator),
1143+
0, 0, 0);
1144+
}
1145+
}
1146+
1147+
/* Also may need the clause_op's negator */
1148+
clause_op_negator = get_negator(clause_op);
1149+
1150+
/* Now search the opclasses */
10551151
for (i = 0; i < catlist->n_members; i++)
10561152
{
10571153
HeapTuple pred_tuple = &catlist->members[i]->tuple;
@@ -1071,6 +1167,14 @@ pred_test_simple_clause(Expr *predicate, Node *clause)
10711167
pred_strategy = (StrategyNumber) pred_form->amopstrategy;
10721168
Assert(pred_strategy >= 1 && pred_strategy <= 5);
10731169

1170+
if (pred_op_negated)
1171+
{
1172+
/* Only consider negators that are = */
1173+
if (pred_strategy != BTEqualStrategyNumber)
1174+
continue;
1175+
pred_strategy = BTNE;
1176+
}
1177+
10741178
/*
10751179
* From the same opclass, find a strategy number for the clause_op,
10761180
* if possible
@@ -1087,31 +1191,65 @@ pred_test_simple_clause(Expr *predicate, Node *clause)
10871191
clause_strategy = (StrategyNumber) clause_form->amopstrategy;
10881192
Assert(clause_strategy >= 1 && clause_strategy <= 5);
10891193
clause_subtype = clause_form->amopsubtype;
1090-
1091-
/* done with clause_tuple */
10921194
ReleaseSysCache(clause_tuple);
1093-
1094-
/*
1095-
* Look up the "test" strategy number in the implication table
1096-
*/
1097-
test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
1098-
if (test_strategy == 0)
1195+
}
1196+
else if (OidIsValid(clause_op_negator))
1197+
{
1198+
clause_tuple = SearchSysCache(AMOPOPID,
1199+
ObjectIdGetDatum(clause_op_negator),
1200+
ObjectIdGetDatum(opclass_id),
1201+
0, 0);
1202+
if (HeapTupleIsValid(clause_tuple))
10991203
{
1100-
/* Can't determine implication using this interpretation */
1101-
continue;
1204+
Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
1205+
1206+
/* Get the restriction clause operator's strategy/subtype */
1207+
clause_strategy = (StrategyNumber) clause_form->amopstrategy;
1208+
Assert(clause_strategy >= 1 && clause_strategy <= 5);
1209+
clause_subtype = clause_form->amopsubtype;
1210+
ReleaseSysCache(clause_tuple);
1211+
1212+
/* Only consider negators that are = */
1213+
if (clause_strategy != BTEqualStrategyNumber)
1214+
continue;
1215+
clause_strategy = BTNE;
11021216
}
1217+
else
1218+
continue;
1219+
}
1220+
else
1221+
continue;
11031222

1104-
/*
1105-
* See if opclass has an operator for the test strategy and the
1106-
* clause datatype.
1107-
*/
1223+
/*
1224+
* Look up the "test" strategy number in the implication table
1225+
*/
1226+
test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
1227+
if (test_strategy == 0)
1228+
{
1229+
/* Can't determine implication using this interpretation */
1230+
continue;
1231+
}
1232+
1233+
/*
1234+
* See if opclass has an operator for the test strategy and the
1235+
* clause datatype.
1236+
*/
1237+
if (test_strategy == BTNE)
1238+
{
11081239
test_op = get_opclass_member(opclass_id, clause_subtype,
1109-
test_strategy);
1240+
BTEqualStrategyNumber);
11101241
if (OidIsValid(test_op))
1111-
{
1112-
found = true;
1113-
break;
1114-
}
1242+
test_op = get_negator(test_op);
1243+
}
1244+
else
1245+
{
1246+
test_op = get_opclass_member(opclass_id, clause_subtype,
1247+
test_strategy);
1248+
}
1249+
if (OidIsValid(test_op))
1250+
{
1251+
found = true;
1252+
break;
11151253
}
11161254
}
11171255

@@ -1143,7 +1281,7 @@ pred_test_simple_clause(Expr *predicate, Node *clause)
11431281

11441282
/* And execute it. */
11451283
test_result = ExecEvalExprSwitchContext(test_exprstate,
1146-
GetPerTupleExprContext(estate),
1284+
GetPerTupleExprContext(estate),
11471285
&isNull, NULL);
11481286

11491287
/* Get back to outer memory context */

0 commit comments

Comments
 (0)