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

Commite7d8bfb

Browse files
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 proofdirection (imply or refute), so it's easy to cache. This provides a verylarge 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 pairof 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 buysa whole lot when constraint_exclusion isn't turned on, but it's not a lotof added code so we might as well cache all the time.
1 parentfdf8d06 commite7d8bfb

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
staticboollist_member_strip(List*list,Expr*datum);
9798
staticboolbtree_predicate_proof(Expr*predicate,Node*clause,
9899
boolrefute_it);
100+
staticOidget_btree_test_op(Oidpred_op,Oidclause_op,boolrefute_it);
101+
staticvoidInvalidateOprProofCacheCallBack(Datumarg,intcacheid,ItemPointertuplePtr);
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
boolpred_var_on_left,
1282-
clause_var_on_left,
1283-
pred_op_negated;
1285+
clause_var_on_left;
12841286
Oidpred_op,
12851287
clause_op,
1286-
pred_op_negator,
1287-
clause_op_negator,
1288-
test_op=InvalidOid;
1289-
Oidopfamily_id;
1290-
boolfound= false;
1291-
StrategyNumberpred_strategy,
1292-
clause_strategy,
1293-
test_strategy;
1294-
Oidclause_righttype;
1288+
test_op;
12951289
Expr*test_expr;
12961290
ExprState*test_exprstate;
12971291
Datumtest_result;
12981292
boolisNull;
1299-
CatCList*catlist;
1300-
inti;
13011293
EState*estate;
13021294
MemoryContextoldcontext;
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+
returnDatumGetBool(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+
typedefstructOprProofCacheKey
1440+
{
1441+
Oidpred_op;/* predicate operator */
1442+
Oidclause_op;/* clause operator */
1443+
}OprProofCacheKey;
1444+
1445+
typedefstructOprProofCacheEntry
1446+
{
1447+
/* the hash lookup key MUST BE FIRST */
1448+
OprProofCacheKeykey;
1449+
1450+
boolhave_implic;/* do we know the implication result? */
1451+
boolhave_refute;/* do we know the refutation result? */
1452+
Oidimplic_test_op;/* OID of the operator, or 0 if none */
1453+
Oidrefute_test_op;/* OID of the operator, or 0 if none */
1454+
}OprProofCacheEntry;
1455+
1456+
staticHTAB*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+
staticOid
1473+
get_btree_test_op(Oidpred_op,Oidclause_op,boolrefute_it)
1474+
{
1475+
OprProofCacheKeykey;
1476+
OprProofCacheEntry*cache_entry;
1477+
boolcfound;
1478+
boolpred_op_negated;
1479+
Oidpred_op_negator,
1480+
clause_op_negator,
1481+
test_op=InvalidOid;
1482+
Oidopfamily_id;
1483+
boolfound= false;
1484+
StrategyNumberpred_strategy,
1485+
clause_strategy,
1486+
test_strategy;
1487+
Oidclause_righttype;
1488+
CatCList*catlist;
1489+
inti;
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+
HASHCTLctl;
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+
returncache_entry->refute_test_op;
1533+
}
1534+
else
1535+
{
1536+
if (cache_entry->have_implic)
1537+
returncache_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 abtree opfamily to interpret the operators */
1556-
return false;
1706+
/* couldn't find asuitable 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+
returntest_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+
staticvoid
1730+
InvalidateOprProofCacheCallBack(Datumarg,intcacheid,ItemPointertuplePtr)
1731+
{
1732+
HASH_SEQ_STATUSstatus;
1733+
OprProofCacheEntry*hentry;
15811734

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

1585-
/*Releaseallthe junk we just created */
1586-
FreeExecutorState(estate);
1737+
/*Currently we just resetallentries; 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-
returnDatumGetBool(test_result);
15951745
}

0 commit comments

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