0003-Implement-get_partitions_from_clauses-v1.patch

From a484fbf69a1debe97bbc3ef724ad858275a44688 Mon Sep 17 00:00:00 2001
From: amit <amitlangote09@gmail.com>
Date: Tue, 22 Aug 2017 13:48:13 +0900
Subject: [PATCH 3/5] Implement get_partitions_from_clauses

This now actually processes partclauses and classifies them into
a set of keys that can be used to look up partitions in the
partition descriptor, although there is still no support for the
latter.
---
 src/backend/catalog/partition.c | 1034 ++++++++++++++++++++++++++++++++++++++-
 1 file changed, 1031 insertions(+), 3 deletions(-)

diff --git a/src/backend/catalog/partition.c b/src/backend/catalog/partition.c
index f8da91d0fe..abccb77393 100644
--- a/src/backend/catalog/partition.c
+++ b/src/backend/catalog/partition.c
@@ -37,6 +37,8 @@
 #include "nodes/parsenodes.h"
 #include "optimizer/clauses.h"
 #include "optimizer/planmain.h"
+#include "optimizer/planner.h"
+#include "optimizer/predtest.h"
 #include "optimizer/prep.h"
 #include "optimizer/var.h"
 #include "rewrite/rewriteManip.h"
@@ -111,6 +113,100 @@ typedef struct PartitionRangeBound
 	bool		lower;			/* this is the lower (vs upper) bound */
 } PartitionRangeBound;
 
+/*
+ * Information about a clause matched with a partition key column kept to
+ * avoid repeated recomputation in remove_redundant_clauses().
+ */
+typedef struct
+{
+	OpExpr *op;
+	Expr   *constarg;
+
+	/* cached info. */
+	bool	valid_cache;	/* Is the following information initialized? */
+	int		op_strategy;
+	Oid		op_subtype;
+	FmgrInfo op_func;
+} PartClause;
+
+/*
+ * PartitionScanKeyInfo
+ *		Bounding scan keys to look up a table's partitions obtained from
+ *		mutually-ANDed clauses containing partitioning-compatible operators
+ */
+typedef struct PartitionScanKeyInfo
+{
+	/*
+	 * Constants constituting the *whole* partition key compared using
+	 * partitioning-compatible equality operator(s).  When n_eqkeys > 0, other
+	 * keys (minkeys and maxkeys) are irrelevant.
+	 */
+	Datum	eqkeys[PARTITION_MAX_KEYS];
+	int		n_eqkeys;
+
+	/*
+	 * Constants that constitute the lower bound on the partition key or a
+	 * prefix thereof.  The last of those constants is compared using > or >=
+	 * operator compatible with partitioning, making this the lower bound in
+	 * a range query.
+	 */
+	Datum	minkeys[PARTITION_MAX_KEYS];
+	int		n_minkeys;
+	bool	min_incl;
+
+	/*
+	 * Constants that constitute the upper bound on the partition key or a
+	 * prefix thereof.  The last of those constants is compared using < or <=
+	 * operator compatible with partitioning, making this the upper bound in
+	 * a range query.
+	 */
+	Datum	maxkeys[PARTITION_MAX_KEYS];
+	int		n_maxkeys;
+	bool	max_incl;
+
+	/*
+	 * Specifies the type of NullTest that was applied to each of the
+	 * partition key columns or -1 if none was applied.  Partitioning handles
+	 * null partition keys specially depending on the partitioning method in
+	 * use, so get_partitions_for_keys can return partitions according to
+	 * the nullness condition for partition keys.
+	 */
+	NullTestType	keynullness[PARTITION_MAX_KEYS];
+} PartitionScanKeyInfo;
+
+ /* A data structure to represent a partition set. */
+typedef struct PartitionSet
+{
+	/*
+	 * If either  empty or all_parts is true, values of the other fields are
+	 * invalid.
+	 */
+	bool	empty;				/* contains no partitions */
+	bool	all_parts;			/* contains all partitions */
+
+	/*
+	 * In the case of range partitioning, min_part_index contains the index of
+	 * the lowest partition contained in the set and max_datum_index that of
+	 * the highest partition (all partitions between these two indexes
+	 * inclusive are part of the set.)  Since other types of partitioning do
+	 * not impose order on the data contained in successive partitions, these
+	 * fields are not set in that case.
+	 */
+	bool	use_range;
+	int		min_part_idx;
+	int		max_part_idx;
+
+	/*
+	 * other_parts contains the indexes of partitions that are not covered by
+	 * the range defined by min/max indexes.  For example, in the case of
+	 * range partitoning, it will include default partition index (if any).
+	 * Also, this is the only way to return list partitions, because list
+	 * partitions do not have the same ordering property as range partitions,
+	 * so it's pointless to use the min/max range method.
+	 */
+	Bitmapset *other_parts;
+} PartitionSet;
+
 static int32 qsort_partition_list_value_cmp(const void *a, const void *b,
 							   void *arg);
 static int32 qsort_partition_rbound_cmp(const void *a, const void *b,
@@ -150,6 +246,25 @@ static int partition_bound_bsearch(PartitionKey key,
 static void get_partition_dispatch_recurse(Relation rel, Relation parent,
 							   List **pds, List **leaf_part_oids);
 
+static PartitionSet *get_partitions_from_clauses_guts(Relation relation,
+								int rt_index, List *clauses);
+static int classify_partition_bounding_keys(Relation relation, List *clauses,
+								 PartitionScanKeyInfo *keys, bool *constfalse,
+								 List **or_clauses);
+static void remove_redundant_clauses(PartitionKey partkey,
+						 int partattoff, List *all_clauses,
+						 List **result, bool *constfalse);
+static bool partition_cmp_args(Oid partopfamily, Oid partopcintype,
+				   PartClause *op, PartClause *leftarg, PartClause *rightarg,
+				   bool *result);
+static Datum partkey_datum_from_expr(const Expr *expr);
+static PartitionSet *partset_copy(const PartitionSet *in);
+static PartitionSet *partset_intersect(PartitionSet *a, const PartitionSet *b);
+static PartitionSet *partset_union(PartitionSet *a, const PartitionSet *b);
+static PartitionSet *partset_new(bool empty, bool all_parts);
+static PartitionSet *get_partitions_for_keys(Relation rel,
+						PartitionScanKeyInfo *keys);
+
 /*
  * RelationBuildPartitionDesc
  *		Form rel's partition descriptor
@@ -1439,15 +1554,928 @@ get_partitions_from_clauses(Relation relation, int rt_index,
 							Bitmapset **other_parts)
 {
 	PartitionDesc	partdesc = RelationGetPartitionDesc(relation);
+	PartitionSet   *partset;
+
+	partset = get_partitions_from_clauses_guts(relation, rt_index,
+											   partclauses);
+	if (partset->empty)
+	{
+		*min_part_idx = *max_part_idx = -1;
+		*other_parts = NULL;
+	}
+	else if (partset->all_parts)
+	{
+		*min_part_idx = 0;
+		*max_part_idx = partdesc->nparts - 1;
+		*other_parts = NULL;
+	}
+	else
+	{
+		if (partset->use_range)
+		{
+			*min_part_idx = partset->min_part_idx;
+			*max_part_idx = partset->max_part_idx;
+		}
+		else
+			*min_part_idx = *max_part_idx = -1;
 
-	*min_part_idx = 0;
-	*max_part_idx = partdesc->nparts - 1;
-	*other_parts = NULL;
+		*other_parts = partset->other_parts;
+	}
 }
 
 /* Module-local functions */
 
 /*
+ * get_partitions_using_clauses_guts
+ *		Determine relation's partitions that satisfy *all* of the clauses
+ *		in the list (return value describes the set of such partitions)
+ *
+ * rt_index is the table's range table position needed to set varno of Vars
+ * contained in the table's partition constraint that is used in certain
+ * cases.
+ */
+static PartitionSet *
+get_partitions_from_clauses_guts(Relation relation, int rt_index,
+								 List *clauses)
+{
+	PartitionSet *partset;
+	PartitionScanKeyInfo keys;
+	int		nkeys;
+	bool	constfalse;
+	List *or_clauses;
+	ListCell *lc;
+
+	nkeys = classify_partition_bounding_keys(relation, clauses,
+											 &keys, &constfalse,
+											 &or_clauses);
+	if (constfalse)
+		/* None of the partitions will satisfy the clauses. */
+		partset = partset_new(true, false);
+	else if (nkeys > 0)
+		/*
+		 * Only look up in the partition decriptor if the query provides
+		 * constraints on the keys at all.
+		 */
+		partset = get_partitions_for_keys(relation, &keys);
+	else
+		/* No constraints on the keys, so, return *all* partitions. */
+		partset = partset_new(false, true);
+
+	foreach(lc, or_clauses)
+	{
+		BoolExpr *or = (BoolExpr *) lfirst(lc);
+		ListCell *lc1;
+		PartitionSet *or_partset = partset_new(true, false);
+
+		foreach(lc1, or->args)
+		{
+			Expr *orarg = lfirst(lc1);
+			PartitionSet  *arg_partset = partset_new(true, false);
+			List   *partconstr = RelationGetPartitionQual(relation);
+
+			/*
+			 * If this orarg refutes the table's partition constraint (if the
+			 * the table is a partition at all), don't go looking for its
+			 * partitions, that is, leave the partition set we're building
+			 * for this OR clause untouched.
+			 */
+			if (partconstr)
+			{
+				partconstr = (List *) expression_planner((Expr *) partconstr);
+				partconstr = (List *) canonicalize_qual((Expr *) partconstr);
+				Assert(rt_index > 0);
+				if (rt_index != 1)
+					ChangeVarNodes((Node *) partconstr, 1, rt_index, 0);
+
+				/*
+				 * NB: if the clause may contain Param, replace them with
+				 * equivalent Vars before proceeding, because predtest.c does
+				 * not know about Params.
+				 */
+				if (predicate_refuted_by(partconstr,
+										 list_make1(orarg), false))
+					continue;
+			}
+
+			arg_partset = get_partitions_from_clauses_guts(relation, 0,
+														   list_make1(orarg));
+
+			/* Combine partition sets obtained from mutually ORed clauses. */
+			or_partset = partset_union(or_partset, arg_partset);
+		}
+
+		/* Combine partition sets obtained from mutually ANDed clauses. */
+		partset = partset_intersect(partset, or_partset);
+	}
+
+	return partset;
+}
+
+/*
+ * partkey_datum_from_expr
+ *		Extract constant value from expr and set *datum to that value
+ */
+
+static Datum
+partkey_datum_from_expr(const Expr *expr)
+{
+	/*
+	 * Add more expression types here as needed to support higher-level
+	 * code.
+	 */
+	switch (nodeTag(expr))
+	{
+		case T_Const:
+			return ((Const *) expr)->constvalue;
+
+		default:
+			elog(ERROR, "invalid expression for partition key");
+	}
+
+	Assert(false);	/* should never get here! */
+	return 0;
+}
+
+/* Partition set manipulation functions. */
+
+static PartitionSet *
+partset_new(bool empty, bool all_parts)
+{
+	PartitionSet   *result = palloc0(sizeof(PartitionSet));
+
+	result->empty = empty;
+	result->all_parts = all_parts;
+	/*
+	 * Remains true until we explicitly turn it off in partset_union in a
+	 * certain case.
+	 */
+	result->use_range = true;
+	result->min_part_idx = result->max_part_idx = -1;
+	result->other_parts = NULL;
+
+	return result;
+}
+
+static PartitionSet *
+partset_copy(const PartitionSet *in)
+{
+	PartitionSet *result;
+
+	if (in == NULL)
+		return NULL;
+
+	result = partset_new(in->empty, in->all_parts);
+	result->min_part_idx = in->min_part_idx;
+	result->max_part_idx = in->max_part_idx;
+	result->other_parts = in->other_parts;	/* not bms_copy. */
+
+	return result;
+}
+
+/*
+ * Macros to manipulate the range of partitions specified in a given
+ * PartitionSet (s) using its min_part_idx and max_part_idx fields, which are
+ * both inclusive ends of the range.
+ */
+
+#define partset_range_empty(s)\
+		((s)->min_part_idx < 0 && (s)->max_part_idx < 0)
+
+#define partset_range_overlap(s1, s2)\
+		(!partset_range_empty((s1)) && !partset_range_empty((s2)) &&\
+		 (((s1)->min_part_idx >= (s2)->min_part_idx &&\
+		   (s1)->min_part_idx <= (s2)->max_part_idx) ||\
+		  ((s2)->min_part_idx >= (s1)->min_part_idx &&\
+		   (s2)->min_part_idx <= (s1)->max_part_idx)))
+
+#define partset_range_adjacent(s1, s2)\
+		(!partset_range_empty((s1)) && !partset_range_empty((s2)) &&\
+		 (((s1)->max_part_idx == (s2)->min_part_idx) || \
+		  ((s2)->max_part_idx == (s1)->min_part_idx)))
+
+/* The result after intersection is stuffed back into 'a'. */
+static PartitionSet *
+partset_intersect(PartitionSet *a, const PartitionSet *b)
+{
+	Assert(a != NULL && b != NULL);
+
+	if (a->all_parts || b->empty)
+		a = partset_copy(b);
+	else
+	{
+		/*
+		 * Partition set is specified by min_part_idx, max_part_idx and/or
+		 * other_parts, so make the result set using those fields.
+		 */
+
+		/*
+		 * If one or both sets' range is empty, or if they don't overlap,
+		 * then the result's range is empty.
+		 */
+		if (partset_range_empty(a) ||
+			partset_range_empty(a) ||
+			!partset_range_overlap(a, b))
+		{
+			a->min_part_idx = a->max_part_idx = -1;
+		}
+		else
+		{
+			a->min_part_idx = Max(a->min_part_idx, b->min_part_idx);
+			a->max_part_idx = Min(a->max_part_idx, b->max_part_idx);
+		}
+
+		a->other_parts = bms_intersect(a->other_parts, b->other_parts);
+	}
+
+	return a;
+}
+
+/* The result after union is stuffed back into 'a'. */
+static PartitionSet *
+partset_union(PartitionSet *a, const PartitionSet *b)
+{
+	Assert(a != NULL && b != NULL);
+
+	if (a->empty || b->all_parts)
+		a = partset_copy(b);
+	else
+	{
+		/*
+		 * Partition set is specified by min_part_idx, max_part_idx and/or
+		 * other_parts, so make the result set using those fields.
+		 */
+		int		i;
+
+		/*
+		 * Combine b's range into a's only if we're still using the range
+		 * representation.
+		 */
+		if (a->use_range)
+		{
+			if(!partset_range_empty(a) && !partset_range_empty(b))
+			{
+				/*
+				 * Unify into one range using range union only if it makes
+				 * sense, that is only if they are adjacent to or overlap with
+				 * each other.  If not, unify them by adding indexes within
+				 * both ranges to the other_parts bitmap and mark the set as
+				 * no longer using the range representation, because, the
+				 * indexes in this no longer have the property of being
+				 * contiguous.
+				 */
+				if (partset_range_overlap(a, b) ||
+					partset_range_adjacent(a, b))
+				{
+					a->min_part_idx = Min(a->min_part_idx, b->min_part_idx);
+					a->max_part_idx = Max(a->max_part_idx, b->max_part_idx);
+				}
+				else
+				{
+					for (i = a->min_part_idx; i <= a->max_part_idx; i++)
+						a->other_parts = bms_add_member(a->other_parts, i);
+					for (i = b->min_part_idx; i <= b->max_part_idx; i++)
+						a->other_parts = bms_add_member(a->other_parts, i);
+
+					/* The set is no longer to be represented as range. */
+					a->use_range = false;
+					a->min_part_idx = a->max_part_idx = -1;
+				}
+			}
+			else if (partset_range_empty(a))
+			{
+				a->min_part_idx = b->min_part_idx;
+				a->max_part_idx = b->max_part_idx;
+			}
+		}
+		else
+		{
+			if (!partset_range_empty(b))
+			{
+				for (i = b->min_part_idx; i <= b->max_part_idx; i++)
+					a->other_parts = bms_add_member(a->other_parts, i);
+			}
+		}
+
+		a->other_parts = bms_union(a->other_parts, b->other_parts);
+	}
+
+	return a;
+}
+
+/*
+ * classify_partition_bounding_keys
+ *		Classify partition clauses into equal, min, max keys, along with any
+ *		Nullness constraints and return that informatin in the output argument
+ *		*keys (number of keys is the return value)
+ *
+ * Clauses in the provided list are implicitly ANDed, each of which is known
+ * to match some partition key column.  Map them to individual key columns
+ * and for each column, determine the equal bound or "best" min and max bound.
+ * For example, of a > 1, a > 2, and a >= 5, "5" is the best min bound for
+ * for the column a, which also happens to be an inclusive bound.
+ *
+ * For multi-column keys, an equal bound is returned only if all the columns
+ * are constrained by equality clauses.  Min and maximum bounds could contain
+ * bound values for only a prefix of key columns.
+ *
+ * If the list contains a pseudo-constant clause, *constfalse is set to true
+ * and no keys are set.  It is also set if we encounter mutually contradictory
+ * clauses in this function ourselves, for example, having both a > 1 and
+ * a = 0 the list.
+ *
+ * All the OR clauses encountered in the list are added to *or_clauses.  It's
+ * the responsibility of the caller to process the argument clauses of each of
+ * the OR clauses, which would involve recursively calling this function.
+ */
+static int
+classify_partition_bounding_keys(Relation relation, List *clauses,
+								 PartitionScanKeyInfo *keys, bool *constfalse,
+								 List **or_clauses)
+{
+	PartitionKey partkey = RelationGetPartitionKey(relation);
+	int		i;
+	ListCell *lc;
+	List   *keyclauses_all[PARTITION_MAX_KEYS],
+		   *keyclauses[PARTITION_MAX_KEYS];
+	bool	only_bool_clauses = true;
+	Expr   *eqkey_exprs[PARTITION_MAX_KEYS],
+		   *minkey_exprs[PARTITION_MAX_KEYS],
+		   *maxkey_exprs[PARTITION_MAX_KEYS];
+	NullTestType keynullness[PARTITION_MAX_KEYS];
+	bool	need_next_eq,
+			need_next_min,
+			need_next_max,
+			eqkey_set[PARTITION_MAX_KEYS],
+			minkey_set[PARTITION_MAX_KEYS],
+			maxkey_set[PARTITION_MAX_KEYS],
+			min_incl,
+			max_incl;
+	int		n_eqkeys = 0,
+			n_minkeys = 0,
+			n_maxkeys = 0,
+			n_keynullness = 0;
+
+	*or_clauses = NIL;
+	*constfalse = false;
+	memset(keyclauses_all, 0, PARTITION_MAX_KEYS * sizeof(List *));
+	memset(keynullness, 0, PARTITION_MAX_KEYS * sizeof(NullTestType *));
+
+	foreach(lc, clauses)
+	{
+		Expr	   *clause;
+		ListCell   *partexprs_item;
+
+		if (IsA(lfirst(lc), RestrictInfo))
+		{
+			RestrictInfo *rinfo = lfirst(lc);
+
+			clause = rinfo->clause;
+			if (rinfo->pseudoconstant &&
+				!DatumGetBool(((Const *) clause)->constvalue))
+			{
+				*constfalse = true;
+				continue;
+			}
+		}
+		else
+			clause = (Expr *) lfirst(lc);
+
+		/* Get the BoolExpr's out of the way.*/
+		if (IsA(clause, BoolExpr))
+		{
+			if (or_clause((Node *) clause))
+				*or_clauses = lappend(*or_clauses, clause);
+			else
+				clauses = list_concat(clauses,
+									  list_copy(((BoolExpr *) clause)->args));
+			continue;
+		}
+
+		partexprs_item = list_head(partkey->partexprs);
+		for (i = 0; i < partkey->partnatts; i++)
+		{
+			Oid		partopfamily = partkey->partopfamily[i];
+			AttrNumber	partattno = partkey->partattrs[i];
+			Expr *partexpr = NULL;
+			PartClause *pc = palloc0(sizeof(PartClause));
+
+			if (partattno == 0)
+			{
+				partexpr = lfirst(partexprs_item);
+				partexprs_item = lnext(partexprs_item);
+			}
+
+			keynullness[i] = -1;
+
+			if (IsA(clause, OpExpr))
+			{
+				OpExpr	   *opclause;
+				Expr	   *leftop,
+						   *rightop;
+
+				opclause = (OpExpr *) clause;
+				leftop = linitial(opclause->args);
+				if (IsA(leftop, RelabelType))
+					leftop = ((RelabelType *) leftop)->arg;
+				rightop = lsecond(opclause->args);
+				/* Does leftop match with this partition key column? */
+				if ((IsA(leftop, Var) && partattno != 0 &&
+					((Var *) leftop)->varattno == partattno) ||
+					equal(leftop, partexpr))
+				{
+					pc->op = opclause;
+					pc->constarg = rightop;
+					keyclauses_all[i] = lappend(keyclauses_all[i], pc);
+
+					/* A strict operator implies NOT NULL argument. */
+					keynullness[i] = IS_NOT_NULL;
+					n_keynullness++;
+					only_bool_clauses = false;
+				}
+			}
+			else if (IsA(clause, ScalarArrayOpExpr))
+			{
+				ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
+				Oid		saop_op = saop->opno;
+				Oid		saop_opfuncid = saop->opfuncid;
+				Oid		saop_coll = saop->inputcollid;
+				Node   *leftop = (Node *) linitial(saop->args);
+				Const  *arrconst = (Const *) lsecond(saop->args);
+				ArrayType *arrval = DatumGetArrayTypeP(arrconst->constvalue);
+				int16	elemlen;
+				bool	elembyval;
+				char	elemalign;
+				Datum  *elem_values;
+				bool   *elem_nulls;
+				int		num_elems;
+				List   *elem_exprs;
+				bool	negated = false;
+
+				/*
+				 * We would've accepted this saop only if its operator's
+				 * negator was found to be a valid partopfamily member.
+				 */
+				if (!op_in_opfamily(saop_op, partopfamily))
+					negated = true;
+
+				/* Build clauses for the individual values in the array. */
+				get_typlenbyvalalign(ARR_ELEMTYPE(arrval),
+									 &elemlen, &elembyval, &elemalign);
+				deconstruct_array(arrval,
+								  ARR_ELEMTYPE(arrval),
+								  elemlen, elembyval, elemalign,
+								  &elem_values, &elem_nulls,
+								  &num_elems);
+				elem_exprs = NIL;
+				for (i = 0; i < num_elems; i++)
+				{
+					Expr *elem_expr;
+
+					if (!elem_nulls[i])
+					{
+						Const  *rightop;
+						OpExpr *opexpr = makeNode(OpExpr);
+
+						rightop = makeConst(ARR_ELEMTYPE(arrval),
+											-1, arrconst->constcollid,
+											elemlen, elem_values[i],
+											false, elembyval);
+
+						opexpr->opno = saop_op;
+						opexpr->opfuncid = saop_opfuncid;
+						opexpr->opresulttype = BOOLOID;
+						opexpr->opretset = false;
+						opexpr->opcollid = InvalidOid;
+						opexpr->inputcollid = saop_coll;
+						opexpr->args = list_make2(leftop, rightop);
+						opexpr->location = -1;
+						elem_expr = (Expr *) opexpr;
+					}
+					else
+					{
+						NullTest *nulltest = makeNode(NullTest);
+
+						nulltest->arg = (Expr *) leftop;
+						nulltest->nulltesttype = !negated ? IS_NULL
+														  : IS_NOT_NULL;
+						nulltest->argisrow = false;
+						nulltest->location = -1;
+						elem_expr = (Expr *) nulltest;
+					}
+
+					elem_exprs = lappend(elem_exprs, elem_expr);
+				}
+
+				/* Build the OR clause and generate its PartClauseSetOr. */
+				if (saop->useOr)
+				{
+					BoolExpr *orexpr;
+
+					Assert(elem_exprs != NIL);
+					orexpr = (BoolExpr *) makeBoolExpr(OR_EXPR, elem_exprs,
+													   -1);
+					*or_clauses = lappend(*or_clauses, orexpr);
+				}
+				else
+					/*
+					 * To be ANDed with the clauses in the original list, just
+					 * like what we do for the arguments of Boolean AND clause
+					 * above.
+					 */
+					clauses = list_concat(clauses, elem_exprs);
+			}
+			else if (IsA(clause, NullTest))
+			{
+				NullTest *nulltest = (NullTest *) clause;
+				Expr *arg = nulltest->arg;
+
+				/* Does leftop match with this partition key column? */
+				if ((IsA(arg, Var) && partattno != 0 &&
+					((Var *) arg)->varattno == partattno) ||
+					!equal(arg, partexpr))
+				{
+					keynullness[i] = nulltest->nulltesttype;
+					n_keynullness++;
+					only_bool_clauses = false;
+				}
+			}
+		}
+	}
+
+	/* Return if no work to do below. */
+	if (only_bool_clauses || *constfalse)
+		return 0;
+
+	/*
+	 * Redundant key elimination using btree-semantics based tricks.
+	 *
+	 * Only list and range partitioning use btree operator semantics, so
+	 * skip otherwise.   Also, if there are expressions whose value is yet
+	 * unknown, skip this step, because we need to compare actual values
+	 * below.
+	 */
+	memset(keyclauses, 0, PARTITION_MAX_KEYS * sizeof(List *));
+	if (partkey->strategy == PARTITION_STRATEGY_LIST ||
+		partkey->strategy == PARTITION_STRATEGY_RANGE)
+	{
+		for (i = 0; i < partkey->partnatts; i++)
+		{
+			remove_redundant_clauses(partkey, i,
+									 keyclauses_all[i],
+									 &keyclauses[i],
+									 constfalse);
+			if (*constfalse)
+				return 0;
+		}
+	}
+
+	/*
+	 * Now, generate the bounding tuples that can serve as equal, min, and
+	 * max keys.  An equal bounding key must contain all partition key
+	 * columns, whereas a prefix of all partition key columns is addmissible
+	 * as min and max keys.
+	 */
+	memset(eqkey_exprs, 0, sizeof(eqkey_exprs));
+	memset(minkey_exprs, 0, sizeof(minkey_exprs));
+	memset(maxkey_exprs, 0, sizeof(maxkey_exprs));
+	memset(eqkey_set, false, sizeof(eqkey_set));
+	memset(minkey_set, false, sizeof(minkey_set));
+	memset(maxkey_set, false, sizeof(maxkey_set));
+
+	need_next_eq = true;
+	need_next_min = true;
+	need_next_max = true;
+	for (i = 0; i < partkey->partnatts; i++)
+	{
+		/*
+		 * If no scan key existed for the previous column, we are done.
+		 */
+		if (i > n_eqkeys)
+			need_next_eq = false;
+
+		if (i > n_minkeys)
+			need_next_min = false;
+
+		if (i > n_maxkeys)
+			need_next_max = false;
+
+		foreach(lc, keyclauses[i])
+		{
+			PartClause *clause = lfirst(lc);
+			int		strategy = clause->op_strategy;
+
+			switch (strategy)
+			{
+				case BTLessStrategyNumber:
+				case BTLessEqualStrategyNumber:
+					if (need_next_max)
+					{
+						maxkey_exprs[i] = clause->constarg;
+						if (!maxkey_set[i])
+							n_maxkeys++;
+						maxkey_set[i] = true;
+						max_incl = (strategy == BTLessEqualStrategyNumber);
+
+						if (strategy == BTLessStrategyNumber)
+							need_next_eq = need_next_max = false;
+					}
+					break;
+
+				case BTGreaterStrategyNumber:
+				case BTGreaterEqualStrategyNumber:
+					if (need_next_min)
+					{
+						minkey_exprs[i] = clause->constarg;
+						if (!minkey_set[i])
+							n_minkeys++;
+						minkey_set[i] = true;
+						min_incl = (strategy == BTGreaterEqualStrategyNumber);
+
+						if (strategy == BTGreaterStrategyNumber)
+							need_next_eq = need_next_min = false;
+					}
+					break;
+
+				case BTEqualStrategyNumber:
+					if (need_next_eq)
+					{
+						eqkey_exprs[i] = clause->constarg;
+						if (!eqkey_set[i])
+							n_eqkeys++;
+						eqkey_set[i] = true;
+					}
+
+					if (need_next_min)
+					{
+						minkey_exprs[i] = clause->constarg;
+						if (!minkey_set[i])
+							n_minkeys++;
+						minkey_set[i] = true;
+						min_incl = true;
+					}
+
+					if (need_next_max)
+					{
+						maxkey_exprs[i] = clause->constarg;
+						if (!maxkey_set[i])
+							n_maxkeys++;
+						maxkey_set[i] = true;
+						max_incl = true;
+					}
+					break;
+
+				/*
+				 * Ideally, never get here, because 1. we don't support
+				 * operators that are not btree operators and 2. clauses
+				 * containing '<>' which are not listed in the btree operator
+				 * families have already been handled by the higher-level
+				 * code.
+				 */
+				default:
+					break;
+			}
+		}
+	}
+
+	/*
+	 * If we have equal keys for all the partition key columns, then mark
+	 * their copies in minkeys and maxkeys as invalid, so that we perform
+	 * partition lookup using only eqkeys.  Don't pass as the equal key
+	 * otherwise.
+	 */
+	if (n_eqkeys == partkey->partnatts)
+		n_minkeys = n_maxkeys = 0;
+	else
+		n_eqkeys = 0;
+
+	/* Populate PartClauseValSet */
+	for (i = 0; i < n_eqkeys; i++)
+		keys->eqkeys[i] = partkey_datum_from_expr(eqkey_exprs[i]);
+	keys->n_eqkeys = n_eqkeys;
+
+	for (i = 0; i < n_minkeys; i++)
+		keys->minkeys[i] = partkey_datum_from_expr(minkey_exprs[i]);
+	keys->n_minkeys = n_minkeys;
+	keys->min_incl = min_incl;
+
+	for (i = 0; i < n_maxkeys; i++)
+		keys->maxkeys[i] = partkey_datum_from_expr(maxkey_exprs[i]);
+	keys->n_maxkeys = n_maxkeys;
+	keys->max_incl = max_incl;
+
+	for (i = 0; i < partkey->partnatts; i++)
+		keys->keynullness[i] = keynullness[i];
+
+	return n_eqkeys + n_minkeys + n_maxkeys + n_keynullness;
+}
+
+static void
+remove_redundant_clauses(PartitionKey partkey,
+						 int partattoff, List *all_clauses,
+						 List **result, bool *constfalse)
+{
+	Oid			partopfamily = partkey->partopfamily[partattoff];
+	Oid			partopcintype = partkey->partopcintype[partattoff];
+	PartClause *xform[BTMaxStrategyNumber];
+	ListCell *lc;
+	int		s;
+	bool	test_result;
+
+	*result = NIL;
+
+	/*
+	 * xform[s] points to the currently best scan key of strategy type s+1; it
+	 * is NULL if we haven't yet found such a key for this attr.
+	 */
+	memset(xform, 0, sizeof(xform));
+	foreach(lc, all_clauses)
+	{
+		PartClause *cur = lfirst(lc);
+
+		if (!cur->valid_cache)
+		{
+			Oid		lefttype;
+			get_op_opfamily_properties(cur->op->opno, partopfamily, false,
+									   &cur->op_strategy,
+									   &lefttype,
+									   &cur->op_subtype);
+			fmgr_info(get_opcode(cur->op->opno), &cur->op_func);
+			cur->valid_cache = true;
+		}
+
+		s = cur->op_strategy - 1;
+		/* Have we seen a clause of this strategy before?. */
+		if (xform[s] == NULL)
+		{
+			/* nope, so assign. */
+			xform[s] = cur;
+		}
+		else
+		{
+			/* yup, keep only the more restrictive key. */
+			if (partition_cmp_args(partopfamily, partopcintype,
+								   cur, cur, xform[s],
+								   &test_result))
+			{
+				if (test_result)
+					xform[s] = cur;
+				else if (s == BTEqualStrategyNumber - 1)
+				{
+					*constfalse = true;
+					return;
+				}
+				/* else the old key is more restrictive, keep around. */
+			}
+			else
+			{
+				/*
+				 * we couldn't determine which one is more restrictive.  Keep
+				 * the previous one in xform[s] and push this one directly
+				 * to the output list.
+				 */
+				*result = lappend(*result, cur);
+			}
+		}
+	}
+
+	/* Finished processing all clauses.  Now compare across strategies. */
+	if (xform[BTEqualStrategyNumber - 1])
+	{
+		PartClause *eq = xform[BTEqualStrategyNumber - 1];
+
+		for (s = BTMaxStrategyNumber; --s >= 0;)
+		{
+			PartClause *chk = xform[s];
+
+			if (!chk || s == (BTEqualStrategyNumber - 1))
+				continue;
+
+			if (partition_cmp_args(partopfamily, partopcintype, chk, eq, chk,
+								   &test_result))
+			{
+				if (!test_result)
+				{
+					*constfalse = true;
+					return;
+				}
+				/* discard the redundant key. */
+				xform[s] = NULL;
+			}
+		}
+	}
+
+	/* try to keep only one of <, <= */
+	if (xform[BTLessStrategyNumber - 1] &&
+		xform[BTLessEqualStrategyNumber - 1])
+	{
+		PartClause *lt = xform[BTLessStrategyNumber - 1],
+				   *le = xform[BTLessEqualStrategyNumber - 1];
+
+		if (partition_cmp_args(partopfamily, partopcintype, le, lt, le,
+							   &test_result))
+		{
+			if (test_result)
+				xform[BTLessEqualStrategyNumber - 1] = NULL;
+			else
+				xform[BTLessStrategyNumber - 1] = NULL;
+		}
+	}
+
+	/* try to keep only one of >, >= */
+	if (xform[BTGreaterStrategyNumber - 1] &&
+		xform[BTGreaterEqualStrategyNumber - 1])
+	{
+		PartClause *gt = xform[BTGreaterStrategyNumber - 1],
+				   *ge = xform[BTGreaterEqualStrategyNumber - 1];
+
+		if (partition_cmp_args(partopfamily, partopcintype, ge, gt, ge,
+							   &test_result))
+		{
+			if (test_result)
+				xform[BTGreaterEqualStrategyNumber - 1] = NULL;
+			else
+				xform[BTGreaterStrategyNumber - 1] = NULL;
+		}
+	}
+
+	/*
+	 * xform now contains "best" clauses for i'th partition key column
+	 * for given btree strategy number.  Copy them to keyclauses[i].
+	 */
+	for (s = BTMaxStrategyNumber; --s >= 0;)
+		if (xform[s])
+			*result = lappend(*result, xform[s]);
+}
+
+static bool
+partition_cmp_args(Oid partopfamily, Oid partopcintype,
+				   PartClause *op, PartClause *leftarg, PartClause *rightarg,
+				   bool *result)
+{
+	Datum	leftarg_const,
+			rightarg_const;
+
+	Assert(op->valid_cache && leftarg->valid_cache && rightarg->valid_cache);
+	Assert(IsA(leftarg->constarg, Const) &&
+		   IsA(rightarg->constarg, Const));
+	leftarg_const = partkey_datum_from_expr(leftarg->constarg);
+	rightarg_const = partkey_datum_from_expr(rightarg->constarg);
+
+	/*
+	 * If the leftarg and rightarg clauses' constants are both of the type
+	 * expected by "op" clause's operator, then compare then using the
+	 * latter's comparison function.
+	 */
+	if (leftarg->op_subtype == partopcintype &&
+		rightarg->op_subtype == op->op_subtype)
+	{
+		*result = DatumGetBool(FunctionCall2Coll(&op->op_func,
+												 op->op->inputcollid,
+												 leftarg_const,
+												 rightarg_const));
+		return true;
+	}
+	else
+	{
+		/* Otherwise, look one up in the partitioning operator family. */
+		Oid		cmp_op = get_opfamily_member(partopfamily,
+											 leftarg->op_subtype,
+											 rightarg->op_subtype,
+											 op->op_strategy);
+		if (OidIsValid(cmp_op))
+		{
+			*result = DatumGetBool(OidFunctionCall2Coll(get_opcode(cmp_op),
+														op->op->inputcollid,
+														leftarg_const,
+														rightarg_const));
+			return true;
+		}
+	}
+
+	/* Couldn't do the comparison. */
+	*result = false;
+	return false;
+}
+
+/*
+ * get_partitions_for_keys
+ *		Returns the partitions hat will need to be scanned for the given
+ *		bounding keys
+ *
+ * Input:
+ *	See the comments above the definition of PartitionScanKeyInfo to see what
+ *	kind of information is received here.
+ *
+ * Outputs:
+ *	Partition set satisfying the keys.
+ */
+static PartitionSet *
+get_partitions_for_keys(Relation rel, PartitionScanKeyInfo *keys)
+{
+	return partset_new(false, true);
+}
+
+/*
  * get_partition_operator
  *
  * Return oid of the operator of given strategy for a given partition key
-- 
2.11.0