8000 Arrange to cache the results of looking up a btree predicate proof co… · postgrespro/postgres_cluster@e7d8bfb · GitHub
[go: up one dir, main page]
Skip to content

Commit e7d8bfb

Browse files
tglsfdctglsfdc
committed
Arrange to cache the results of looking up a btree predicate proof comparison
operator. The result depends only on the two input operators and the proof direction (imply or refute), so it's easy to cache. This provides a very large savings in cases such as Sergey Konoplev's long NOT-IN-list example, where predtest spends all its time repeatedly figuring out that the same pair of operators cannot be used to prove anything. (But of course the O(N^2) behavior still catches up with you eventually.) I'm not convinced it buys a whole lot when constraint_exclusion isn't turned on, but it's not a lot of added code so we might as well cache all the time.
1 parent fdf8d06 commit e7d8bfb

File tree

1 file changed

+197
-47
lines changed

1 file changed

+197
-47
lines changed

‎src/backend/optimizer/util/predtest.c‎

Lines changed: 197 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $PostgreSQL: pgsql/src/backend/optimizer/util/predtest.c,v 1.21 2008/11/12 23:08:37 tgl Exp $
12+
* $PostgreSQL: pgsql/src/backend/optimizer/util/predtest.c,v 1.22 2008/11/13 00:20:45 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -24,6 +24,7 @@
2424
#include "optimizer/clauses.h"
2525
#include "optimizer/predtest.h"
2626
#include "utils/array.h"
27+
#include "utils/inval.h"
2728
#include "utils/lsyscache.h"
2829
#include "utils/syscache.h"
2930

@@ -96,6 +97,8 @@ static Node *extract_not_arg(Node *clause);
9697
static bool list_member_strip(List *list, Expr *datum);
9798
static bool btree_predicate_proof(Expr *predicate, Node *clause,
9899
bool refute_it);
100+
static Oid get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it);
101+
static void InvalidateOprProofCacheCallBack(Datum arg, int cacheid, ItemPointer tuplePtr);
99102

100103

101104
/*
@@ -1279,25 +1282,14 @@ btree_predicate_proof(Expr *predicate, Node *clause, bool refute_it)
12791282
Const *pred_const,
12801283
*clause_const;
12811284
bool pred_var_on_left,
1282-
clause_var_on_left,
1283-
pred_op_negated;
1285+
clause_var_on_left;
12841286
Oid pred_op,
12851287
clause_op,
1286-
pred_op_negator,
1287-
clause_op_negator,
1288-
test_op = InvalidOid;
1289-
Oid opfamily_id;
1290-
bool found = false;
1291-
StrategyNumber pred_strategy,
1292-
clause_strategy,
1293-
test_strategy;
1294-
Oid clause_righttype;
1288+
test_op;
12951289
Expr *test_expr;
12961290
ExprState *test_exprstate;
12971291
Datum test_result;
12981292
bool isNull;
1299-
CatCList *catlist;
1300-
int i;
13011293
EState *estate;
13021294
MemoryContext oldcontext;
13031295

@@ -1387,12 +1379,171 @@ btree_predicate_proof(Expr *predicate, Node *clause, bool refute_it)
13871379
}
13881380

13891381
/*
1390-
* Try to find a btree opfamily containing the needed operators.
1382+
* Lookup the comparison operator using the system catalogs and the
1383+
* operator implication tables.
1384+
*/
1385+
test_op = get_btree_test_op(pred_op, clause_op, refute_it);
1386+
1387+
if (!OidIsValid(test_op))
1388+
{
1389+
/* couldn't find a suitable comparison operator */
1390+
return false;
1391+
}
1392+
1393+
/*
1394+
* Evaluate the test. For this we need an EState.
1395+
*/
1396+
estate = CreateExecutorState();
1397+
1398+
/* We can use the estate's working context to avoid memory leaks. */
1399+
oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);
1400+
1401+
/* Build expression tree */
1402+
test_expr = make_opclause(test_op,
1403+
BOOLOID,
1404+
false,
1405+
(Expr *) pred_const,
1406+
(Expr *) clause_const);
1407+
1408+
/* Prepare it for execution */
1409+
test_exprstate = ExecPrepareExpr(test_expr, estate);
1410+
1411+
/* And execute it. */
1412+
test_result = ExecEvalExprSwitchContext(test_exprstate,
1413+
GetPerTupleExprContext(estate),
1414+
&isNull, NULL);
1415+
1416+
/* Get back to outer memory context */
1417+
MemoryContextSwitchTo(oldcontext);
1418+
1419+
/* Release all the junk we just created */
1420+
FreeExecutorState(estate);
1421+
1422+
if (isNull)
1423+
{
1424+
/* Treat a null result as non-proof ... but it's a tad fishy ... */
1425+
elog(DEBUG2, "null predicate test result");
1426+
return false;
1427+
}
1428+
return DatumGetBool(test_result);
1429+
}
1430+
1431+
1432+
/*
1433+
* We use a lookaside table to cache the result of btree proof operator
1434+
* lookups, since the actual lookup is pretty expensive and doesn't change
1435+
* for any given pair of operators (at least as long as pg_amop doesn't
1436+
* change). A single hash entry stores both positive and negative results
1437+
* for a given pair of operators.
1438+
*/
1439+
typedef struct OprProofCacheKey
1440+
{
1441+
Oid pred_op; /* predicate operator */
1442+
Oid clause_op; /* clause operator */
1443+
} OprProofCacheKey;
1444+
1445+
typedef struct OprProofCacheEntry
1446+
{
1447+
/* the hash lookup key MUST BE FIRST */
1448+
OprProofCacheKey key;
1449+
1450+
bool have_implic; /* do we know the implication result? */
1451+
bool have_refute; /* do we know the refutation result? */
1452+
Oid implic_test_op; /* OID of the operator, or 0 if none */
1453+
Oid refute_test_op; /* OID of the operator, or 0 if none */
1454+
} OprProofCacheEntry;
1455+
1456+
static HTAB *OprProofCacheHash = NULL;
1457+
1458+
1459+
/*
1460+
* get_btree_test_op
1461+
* Identify the comparison operator needed for a btree-operator
1462+
* proof or refutation.
1463+
*
1464+
* Given the truth of a predicate "var pred_op const1", we are attempting to
1465+
* prove or refute a clause "var clause_op const2". The identities of the two
1466+
* operators are sufficient to determine the operator (if any) to compare
1467+
* const2 to const1 with.
1468+
*
1469+
* Returns the OID of the operator to use, or InvalidOid if no proof is
1470+
* possible.
1471+
*/
1472+
static Oid
1473+
get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it)
1474+
{
1475+
OprProofCacheKey key;
1476+
OprProofCacheEntry *cache_entry;
1477+
bool cfound;
1478+
bool pred_op_negated;
1479+
Oid pred_op_negator,
1480+
clause_op_negator,
1481+
test_op = InvalidOid;
1482+
Oid opfamily_id;
1483+
bool found = false;
1484+
StrategyNumber pred_strategy,
1485+
clause_strategy,
1486+
test_strategy;
1487+
Oid clause_righttype;
1488+
CatCList *catlist;
1489+
int i;
1490+
1491+
/*
1492+
* Find or make a cache entry for this pair of operators.
1493+
*/
1494+
if (OprProofCacheHash == NULL)
1495+
{
1496+
/* First time through: initialize the hash table */
1497+
HASHCTL ctl;
1498+
1499+
if (!CacheMemoryContext)
1500+
CreateCacheMemoryContext();
1501+
1502+
MemSet(&ctl, 0, sizeof(ctl));
1503+
ctl.keysize = sizeof(OprProofCacheKey);
1504+
ctl.entrysize = sizeof(OprProofCacheEntry);
1505+
ctl.hash = tag_hash;
1506+
OprProofCacheHash = hash_create("Btree proof lookup cache", 256,
1507+
&ctl, HASH_ELEM | HASH_FUNCTION);
1508+
1509+
/* Arrange to flush cache on pg_amop changes */
1510+
CacheRegisterSyscacheCallback(AMOPOPID,
1511+
InvalidateOprProofCacheCallBack,
1512+
(Datum) 0);
1513+
}
1514+
1515+
key.pred_op = pred_op;
1516+
key.clause_op = clause_op;
1517+
cache_entry = (OprProofCacheEntry *) hash_search(OprProofCacheHash,
1518+
(void *) &key,
1519+
HASH_ENTER, &cfound);
1520+
if (!cfound)
1521+
{
1522+
/* new cache entry, set it invalid */
1523+
cache_entry->have_implic = false;
1524+
cache_entry->have_refute = false;
1525+
}
1526+
else
1527+
{
1528+
/* pre-existing cache entry, see if we know the answer */
1529+
if (refute_it)
1530+
{
1531+
if (cache_entry->have_refute)
1532+
return cache_entry->refute_test_op;
1533+
}
1534+
else
1535+
{
1536+
if (cache_entry->have_implic)
1537+
return cache_entry->implic_test_op;
1538+
}
1539+
}
1540+
1541+
/*
1542+
* Try to find a btree opfamily containing the given operators.
13911543
*
13921544
* We must find a btree opfamily that contains both operators, else the
13931545
* implication can't be determined. Also, the opfamily must contain a
1394-
* suitable test operator taking the pred_const and clause_const
1395-
* datatypes.
1546+
* suitable test operator taking the operators' righthand datatypes.
13961547
*
13971548
* If there are multiple matching opfamilies, assume we can use any one to
13981549
* determine the logical relationship of the two operators and the correct
@@ -1552,44 +1703,43 @@ btree_predicate_proof(Expr *predicate, Node *clause, bool refute_it)
15521703

15531704
if (!found)
15541705
{
1555-
/* couldn't find a btree opfamily to interpret the operators */
1556-
return false;
1706+
/* couldn't find a suitable comparison operator */
1707+
test_op = InvalidOid;
15571708
}
15581709

1559-
/*
1560-
* Evaluate the test. For this we need an EState.
1561-
*/
1562-
estate = CreateExecutorState();
1563-
1564-
/* We can use the estate's working context to avoid memory leaks. */
1565-
oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);
1710+
/* Cache the result, whether positive or negative */
1711+
if (refute_it)
1712+
{
1713+
cache_entry->refute_test_op = test_op;
1714+
cache_entry->have_refute = true;
1715+
}
1716+
else
1717+
{
1718+
cache_entry->implic_test_op = test_op;
1719+
cache_entry->have_implic = true;
1720+
}
15661721

1567-
/* Build expression tree */
1568-
test_expr = make_opclause(test_op,
1569-
BOOLOID,
1570-
false,
1571-
(Expr *) pred_const,
1572-
(Expr *) clause_const);
1722+
return test_op;
1723+
}
15731724

1574-
/* Prepare it for execution */
1575-
test_exprstate = ExecPrepareExpr(test_expr, estate);
15761725

1577-
/* And execute it. */
1578-
test_result = ExecEvalExprSwitchContext(test_exprstate,
1579-
GetPerTupleExprContext(estate),
1580-
&isNull, NULL);
1726+
/*
1727+
* Callback for pg_amop inval events
1728+
*/
1729+
static void
1730+
InvalidateOprProofCacheCallBack(Datum arg, int cacheid, ItemPointer tuplePtr)
1731+
{
1732+
HASH_SEQ_STATUS status;
1733+
OprProofCacheEntry *hentry;
15811734

1582-
/* Get back to outer memory context */
1583-
MemoryContextSwitchTo(oldcontext);
1735+
Assert(OprProofCacheHash != NULL);
15841736

1585-
/* Release all the junk we just created */
1586-
FreeExecutorState(estate);
1737+
/* Currently we just reset all entries; hard to be smarter ... */
1738+
hash_seq_init(&status, OprProofCacheHash);
15871739

1588-
if (isNull)
1740+
while ((hentry = (OprProofCacheEntry *) hash_seq_search(&status)) != NULL)
15891741
{
1590-
/* Treat a null result as non-proof ... but it's a tad fishy ... */
1591-
elog(DEBUG2, "null predicate test result");
1592-
return false;
1742+
hentry->have_implic = false;
1743+
hentry->have_refute = false;
15931744
}
1594-
return DatumGetBool(test_result);
15951745
}

0 commit comments

Comments
 (0)
0