From e7d8bfb9342622971cfb326672c998934433546a Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
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.49.0