From e7d8bfb9342622971cfb326672c998934433546a Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Thu, 13 Nov 2008 00:20:45 +0000 Subject: [PATCH] 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. --- src/backend/optimizer/util/predtest.c | 244 +++++++++++++++++++++----- 1 file changed, 197 insertions(+), 47 deletions(-) diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c index f4a84e1072..4ade65037a 100644 --- a/src/backend/optimizer/util/predtest.c +++ b/src/backend/optimizer/util/predtest.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/predtest.c,v 1.21 2008/11/12 23:08:37 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/predtest.c,v 1.22 2008/11/13 00:20:45 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -24,6 +24,7 @@ #include "optimizer/clauses.h" #include "optimizer/predtest.h" #include "utils/array.h" +#include "utils/inval.h" #include "utils/lsyscache.h" #include "utils/syscache.h" @@ -96,6 +97,8 @@ static Node *extract_not_arg(Node *clause); static bool list_member_strip(List *list, Expr *datum); static bool btree_predicate_proof(Expr *predicate, Node *clause, bool refute_it); +static Oid get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it); +static void InvalidateOprProofCacheCallBack(Datum arg, int cacheid, ItemPointer tuplePtr); /* @@ -1279,25 +1282,14 @@ btree_predicate_proof(Expr *predicate, Node *clause, bool refute_it) Const *pred_const, *clause_const; bool pred_var_on_left, - clause_var_on_left, - pred_op_negated; + clause_var_on_left; Oid pred_op, clause_op, - pred_op_negator, - clause_op_negator, - test_op = InvalidOid; - Oid opfamily_id; - bool found = false; - StrategyNumber pred_strategy, - clause_strategy, - test_strategy; - Oid clause_righttype; + test_op; Expr *test_expr; ExprState *test_exprstate; Datum test_result; bool isNull; - CatCList *catlist; - int i; EState *estate; MemoryContext oldcontext; @@ -1387,12 +1379,171 @@ btree_predicate_proof(Expr *predicate, Node *clause, bool refute_it) } /* - * Try to find a btree opfamily containing the needed operators. + * Lookup the comparison operator using the system catalogs and the + * operator implication tables. + */ + test_op = get_btree_test_op(pred_op, clause_op, refute_it); + + if (!OidIsValid(test_op)) + { + /* couldn't find a suitable comparison operator */ + return false; + } + + /* + * Evaluate the test. For this we need an EState. + */ + estate = CreateExecutorState(); + + /* We can use the estate's working context to avoid memory leaks. */ + oldcontext = MemoryContextSwitchTo(estate->es_query_cxt); + + /* Build expression tree */ + test_expr = make_opclause(test_op, + BOOLOID, + false, + (Expr *) pred_const, + (Expr *) clause_const); + + /* Prepare it for execution */ + test_exprstate = ExecPrepareExpr(test_expr, estate); + + /* And execute it. */ + test_result = ExecEvalExprSwitchContext(test_exprstate, + GetPerTupleExprContext(estate), + &isNull, NULL); + + /* Get back to outer memory context */ + MemoryContextSwitchTo(oldcontext); + + /* Release all the junk we just created */ + FreeExecutorState(estate); + + if (isNull) + { + /* Treat a null result as non-proof ... but it's a tad fishy ... */ + elog(DEBUG2, "null predicate test result"); + return false; + } + return DatumGetBool(test_result); +} + + +/* + * We use a lookaside table to cache the result of btree proof operator + * lookups, since the actual lookup is pretty expensive and doesn't change + * for any given pair of operators (at least as long as pg_amop doesn't + * change). A single hash entry stores both positive and negative results + * for a given pair of operators. + */ +typedef struct OprProofCacheKey +{ + Oid pred_op; /* predicate operator */ + Oid clause_op; /* clause operator */ +} OprProofCacheKey; + +typedef struct OprProofCacheEntry +{ + /* the hash lookup key MUST BE FIRST */ + OprProofCacheKey key; + + bool have_implic; /* do we know the implication result? */ + bool have_refute; /* do we know the refutation result? */ + Oid implic_test_op; /* OID of the operator, or 0 if none */ + Oid refute_test_op; /* OID of the operator, or 0 if none */ +} OprProofCacheEntry; + +static HTAB *OprProofCacheHash = NULL; + + +/* + * get_btree_test_op + * Identify the comparison operator needed for a btree-operator + * proof or refutation. + * + * Given the truth of a predicate "var pred_op const1", we are attempting to + * prove or refute a clause "var clause_op const2". The identities of the two + * operators are sufficient to determine the operator (if any) to compare + * const2 to const1 with. + * + * Returns the OID of the operator to use, or InvalidOid if no proof is + * possible. + */ +static Oid +get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it) +{ + OprProofCacheKey key; + OprProofCacheEntry *cache_entry; + bool cfound; + bool pred_op_negated; + Oid pred_op_negator, + clause_op_negator, + test_op = InvalidOid; + Oid opfamily_id; + bool found = false; + StrategyNumber pred_strategy, + clause_strategy, + test_strategy; + Oid clause_righttype; + CatCList *catlist; + int i; + + /* + * Find or make a cache entry for this pair of operators. + */ + if (OprProofCacheHash == NULL) + { + /* First time through: initialize the hash table */ + HASHCTL ctl; + + if (!CacheMemoryContext) + CreateCacheMemoryContext(); + + MemSet(&ctl, 0, sizeof(ctl)); + ctl.keysize = sizeof(OprProofCacheKey); + ctl.entrysize = sizeof(OprProofCacheEntry); + ctl.hash = tag_hash; + OprProofCacheHash = hash_create("Btree proof lookup cache", 256, + &ctl, HASH_ELEM | HASH_FUNCTION); + + /* Arrange to flush cache on pg_amop changes */ + CacheRegisterSyscacheCallback(AMOPOPID, + InvalidateOprProofCacheCallBack, + (Datum) 0); + } + + key.pred_op = pred_op; + key.clause_op = clause_op; + cache_entry = (OprProofCacheEntry *) hash_search(OprProofCacheHash, + (void *) &key, + HASH_ENTER, &cfound); + if (!cfound) + { + /* new cache entry, set it invalid */ + cache_entry->have_implic = false; + cache_entry->have_refute = false; + } + else + { + /* pre-existing cache entry, see if we know the answer */ + if (refute_it) + { + if (cache_entry->have_refute) + return cache_entry->refute_test_op; + } + else + { + if (cache_entry->have_implic) + return cache_entry->implic_test_op; + } + } + + /* + * Try to find a btree opfamily containing the given operators. * * We must find a btree opfamily that contains both operators, else the * implication can't be determined. Also, the opfamily must contain a - * suitable test operator taking the pred_const and clause_const - * datatypes. + * suitable test operator taking the operators' righthand datatypes. * * If there are multiple matching opfamilies, assume we can use any one to * 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) if (!found) { - /* couldn't find a btree opfamily to interpret the operators */ - return false; + /* couldn't find a suitable comparison operator */ + test_op = InvalidOid; } - /* - * Evaluate the test. For this we need an EState. - */ - estate = CreateExecutorState(); - - /* We can use the estate's working context to avoid memory leaks. */ - oldcontext = MemoryContextSwitchTo(estate->es_query_cxt); + /* Cache the result, whether positive or negative */ + if (refute_it) + { + cache_entry->refute_test_op = test_op; + cache_entry->have_refute = true; + } + else + { + cache_entry->implic_test_op = test_op; + cache_entry->have_implic = true; + } - /* Build expression tree */ - test_expr = make_opclause(test_op, - BOOLOID, - false, - (Expr *) pred_const, - (Expr *) clause_const); + return test_op; +} - /* Prepare it for execution */ - test_exprstate = ExecPrepareExpr(test_expr, estate); - /* And execute it. */ - test_result = ExecEvalExprSwitchContext(test_exprstate, - GetPerTupleExprContext(estate), - &isNull, NULL); +/* + * Callback for pg_amop inval events + */ +static void +InvalidateOprProofCacheCallBack(Datum arg, int cacheid, ItemPointer tuplePtr) +{ + HASH_SEQ_STATUS status; + OprProofCacheEntry *hentry; - /* Get back to outer memory context */ - MemoryContextSwitchTo(oldcontext); + Assert(OprProofCacheHash != NULL); - /* Release all the junk we just created */ - FreeExecutorState(estate); + /* Currently we just reset all entries; hard to be smarter ... */ + hash_seq_init(&status, OprProofCacheHash); - if (isNull) + while ((hentry = (OprProofCacheEntry *) hash_seq_search(&status)) != NULL) { - /* Treat a null result as non-proof ... but it's a tad fishy ... */ - elog(DEBUG2, "null predicate test result"); - return false; + hentry->have_implic = false; + hentry->have_refute = false; } - return DatumGetBool(test_result); } -- 2.40.0