<commit_before>/*-------------------------------------------------------------------------
 *
 * shard_pruning.c
 *   Shard pruning related code.
 *
 * The goal of shard pruning is to find a minimal (super)set of shards that
 * need to be queried to find rows matching the expression in a query.
 *
 * In PruneShards, we first compute a simplified disjunctive normal form (DNF)
 * of the expression as a list of pruning instances. Each pruning instance
 * contains all AND-ed constraints on the partition column. An OR expression
 * will result in two or more new pruning instances being added for the
 * subexpressions. The "parent" instance is marked isPartial and ignored
 * during pruning.
 *
 * We use the distributive property for constraints of the form P AND (Q OR R)
 * to rewrite it to (P AND Q) OR (P AND R) by copying constraints from parent
 * to "child" pruning instances. However, we do not distribute nested
 * expressions. While (P OR Q) AND (R OR S) is logically equivalent to (P AND
 * R) OR (P AND S) OR (Q AND R) OR (Q AND S), in our implementation it becomes
 * P OR Q OR R OR S. This is acceptable since this will always result in a
 * superset of shards.  If this proves to be a issue in practice, a more
 * complete algorithm could be implemented.
 *
 * We then evaluate each non-partial pruning instance in the disjunction
 * through the following, increasingly expensive, steps:
 *
 * 1) If there is a constant equality constraint on the partition column, and
 *    no overlapping shards exist, find the shard interval in which the
 *    constant falls
 *
 * 2) If there is a hash range constraint on the partition column, find the
 *    shard interval matching the range
 *
 * 3) If there are range constraints (e.g. (a > 0 AND a < 10)) on the
 *    partition column, find the shard intervals that overlap with the range
 *
 * 4) If there are overlapping shards, exhaustively search all shards that are
 *    not excluded by constraints
 *
 * Finally, the union of the shards found by each pruning instance is
 * returned.
 *
 * Copyright (c) 2014-2017, Citus Data, Inc.
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "distributed/shard_pruning.h"

#include "access/nbtree.h"
#include "catalog/pg_am.h"
#include "catalog/pg_collation.h"
#include "catalog/pg_type.h"
#include "distributed/metadata_cache.h"
#include "distributed/distributed_planner.h"
#include "distributed/multi_join_order.h"
#include "distributed/multi_physical_planner.h"
#include "distributed/shardinterval_utils.h"
#include "distributed/pg_dist_partition.h"
#include "distributed/worker_protocol.h"
#include "nodes/nodeFuncs.h"
#include "nodes/makefuncs.h"
#include "optimizer/clauses.h"
#include "parser/parse_coerce.h"
#include "utils/arrayaccess.h"
#include "utils/catcache.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"

/*
 * A pruning instance is a set of ANDed constraints on a partition key.
 */
typedef struct PruningInstance
{
	/* Does this instance contain any prunable expressions? */
	bool hasValidConstraint;

	/*
	 * This constraint never evaluates to true, i.e. pruning does not have to
	 * be performed.
	 */
	bool evaluatesToFalse;

	/*
	 * Constraints on the partition column value.  If multiple values are
	 * found the more restrictive one should be stored here.  Even in case of
	 * a hash-partitioned table, actual column-values are stored here, *not*
	 * hashed values.
	 */
	Const *lessConsts;
	Const *lessEqualConsts;
	Const *equalConsts;
	Const *greaterEqualConsts;
	Const *greaterConsts;

	/*
	 * Constraint using a pre-hashed column value. The constant will store the
	 * hashed value, not the original value of the restriction.
	 */
	Const *hashedEqualConsts;

	/*
	 * Types of constraints not understood.  We could theoretically try more
	 * expensive methods of pruning if any such restrictions are found.
	 *
	 * TODO: any actual use for this? Right now there seems little point.
	 */
	List *otherRestrictions;

	/*
	 * Has this PruningInstance been added to
	 * ClauseWalkerContext->pruningInstances? This is not done immediately,
	 * but the first time a constraint (independent of us being able to handle
	 * that constraint) is found.
	 */
	bool addedToPruningInstances;

	/*
	 * When OR clauses are found, the non-ORed part (think of a < 3 AND (a > 5
	 * OR a > 7)) of the expression is stored in one PruningInstance which is
	 * then copied for the ORed expressions.  The original is marked as
	 * isPartial, to avoid it being used for pruning.
	 */
	bool isPartial;
} PruningInstance;


/*
 * Partial instances that need to be finished building.  This is used to
 * collect all ANDed restrictions, before looking into ORed expressions.
 */
typedef struct PendingPruningInstance
{
	PruningInstance *instance;
	Node *continueAt;
} PendingPruningInstance;


/*
 * Data necessary to perform a single PruneShards().
 */
typedef struct ClauseWalkerContext
{
	Var *partitionColumn;
	char partitionMethod;

	/* ORed list of pruning targets */
	List *pruningInstances;

	/*
	 * Partially built PruningInstances, that need to be completed by doing a
	 * separate PrunableExpressionsWalker() pass.
	 */
	List *pendingInstances;

	/* PruningInstance currently being built, all elegible constraints are added here */
	PruningInstance *currentPruningInstance;

	/*
	 * Information about function calls we need to perform. Re-using the same
	 * FunctionCallInfoData, instead of using FunctionCall2Coll, is often
	 * cheaper.
	 */
	FunctionCallInfoData compareValueFunctionCall;
	FunctionCallInfoData compareIntervalFunctionCall;
} ClauseWalkerContext;

static void PrunableExpressions(Node *originalNode, ClauseWalkerContext *context);
static bool PrunableExpressionsWalker(Node *originalNode, ClauseWalkerContext *context);
static void AddPartitionKeyRestrictionToInstance(ClauseWalkerContext *context,
												 OpExpr *opClause, Var *varClause,
												 Const *constantClause);
static void AddSAOPartitionKeyRestrictionToInstance(ClauseWalkerContext *context,
													ScalarArrayOpExpr *
													arrayOperatorExpression);
static void AddHashRestrictionToInstance(ClauseWalkerContext *context, OpExpr *opClause,
										 Var *varClause, Const *constantClause);
static void AddNewConjuction(ClauseWalkerContext *context, OpExpr *op);
static PruningInstance * CopyPartialPruningInstance(PruningInstance *sourceInstance);
static List * ShardArrayToList(ShardInterval **shardArray, int length);
static List * DeepCopyShardIntervalList(List *originalShardIntervalList);
static int PerformValueCompare(FunctionCallInfoData *compareFunctionCall, Datum a,
							   Datum b);
static int PerformCompare(FunctionCallInfoData *compareFunctionCall);

static List * PruneOne(DistTableCacheEntry *cacheEntry, ClauseWalkerContext *context,
					   PruningInstance *prune);
static List * PruneWithBoundaries(DistTableCacheEntry *cacheEntry,
								  ClauseWalkerContext *context,
								  PruningInstance *prune);
static List * ExhaustivePrune(DistTableCacheEntry *cacheEntry,
							  ClauseWalkerContext *context,
							  PruningInstance *prune);
static bool ExhaustivePruneOne(ShardInterval *curInterval,
							   ClauseWalkerContext *context,
							   PruningInstance *prune);
static int UpperShardBoundary(Datum partitionColumnValue,
							  ShardInterval **shardIntervalCache,
							  int shardCount, FunctionCallInfoData *compareFunction,
							  bool includeMin);
static int LowerShardBoundary(Datum partitionColumnValue,
							  ShardInterval **shardIntervalCache,
							  int shardCount, FunctionCallInfoData *compareFunction,
							  bool includeMax);


/*
 * PruneShards returns all shards from a distributed table that cannot be
 * proven to be eliminated by whereClauseList.
 *
 * For reference tables, the function simply returns the single shard that the
 * table has.
 *
 * When there is a single <partition column> = <constant> filter in the where
 * clause list, the constant is written to the partitionValueConst pointer.
 */
List *
PruneShards(Oid relationId, Index rangeTableId, List *whereClauseList,
			Const **partitionValueConst)
{
	DistTableCacheEntry *cacheEntry = DistributedTableCacheEntry(relationId);
	int shardCount = cacheEntry->shardIntervalArrayLength;
	char partitionMethod = cacheEntry->partitionMethod;
	ClauseWalkerContext context = { 0 };
	ListCell *pruneCell;
	List *prunedList = NIL;
	bool foundRestriction = false;
	bool foundPartitionColumnValue = false;
	Const *singlePartitionValueConst = NULL;

	/* there are no shards to return */
	if (shardCount == 0)
	{
		return NIL;
	}

	/* always return empty result if WHERE clause is of the form: false (AND ..) */
	if (ContainsFalseClause(whereClauseList))
	{
		return NIL;
	}

	/* short circuit for reference tables */
	if (partitionMethod == DISTRIBUTE_BY_NONE)
	{
		prunedList = ShardArrayToList(cacheEntry->sortedShardIntervalArray,
									  cacheEntry->shardIntervalArrayLength);
		return DeepCopyShardIntervalList(prunedList);
	}


	context.partitionMethod = partitionMethod;
	context.partitionColumn = PartitionColumn(relationId, rangeTableId);
	context.currentPruningInstance = palloc0(sizeof(PruningInstance));

	if (cacheEntry->shardIntervalCompareFunction)
	{
		/* initiate function call info once (allows comparators to cache metadata) */
		InitFunctionCallInfoData(context.compareIntervalFunctionCall,
								 cacheEntry->shardIntervalCompareFunction,
								 2, DEFAULT_COLLATION_OID, NULL, NULL);
	}
	else
	{
		ereport(ERROR, (errmsg("shard pruning not possible without "
							   "a shard interval comparator")));
	}

	if (cacheEntry->shardColumnCompareFunction)
	{
		/* initiate function call info once (allows comparators to cache metadata) */
		InitFunctionCallInfoData(context.compareValueFunctionCall,
								 cacheEntry->shardColumnCompareFunction,
								 2, DEFAULT_COLLATION_OID, NULL, NULL);
	}
	else
	{
		ereport(ERROR, (errmsg("shard pruning not possible without "
							   "a partition column comparator")));
	}

	/* Figure out what we can prune on */
	PrunableExpressions((Node *) whereClauseList, &context);

	/*
	 * Prune using each of the PrunableInstances we found, and OR results
	 * together.
	 */
	foreach(pruneCell, context.pruningInstances)
	{
		PruningInstance *prune = (PruningInstance *) lfirst(pruneCell);
		List *pruneOneList;

		/*
		 * If this is a partial instance, a fully built one has also been
		 * added. Skip.
		 */
		if (prune->isPartial)
		{
			continue;
		}

		/*
		 * If the current instance has no prunable expressions, we'll have to
		 * return all shards.  No point in continuing pruning in that case.
		 */
		if (!prune->hasValidConstraint)
		{
			foundRestriction = false;
			break;
		}

		if (context.partitionMethod == DISTRIBUTE_BY_HASH)
		{
			if (!prune->evaluatesToFalse && !prune->equalConsts &&
				!prune->hashedEqualConsts)
			{
				/* if hash-partitioned and no equals constraints, return all shards */
				foundRestriction = false;
				break;
			}
			else if (partitionValueConst != NULL && prune->equalConsts != NULL)
			{
				if (!foundPartitionColumnValue)
				{
					/* remember the partition column value */
					singlePartitionValueConst = prune->equalConsts;
					foundPartitionColumnValue = true;
				}
				else if (singlePartitionValueConst == NULL)
				{
					/* already found multiple partition column values */
				}
				else if (!equal(prune->equalConsts, singlePartitionValueConst))
				{
					/* found multiple partition column values */
					singlePartitionValueConst = NULL;
				}
			}
		}

		pruneOneList = PruneOne(cacheEntry, &context, prune);

		if (prunedList)
		{
			/*
			 * We can use list_union_ptr, which is a lot faster than doing
			 * comparing shards by value, because all the ShardIntervals are
			 * guaranteed to be from
			 * DistTableCacheEntry->sortedShardIntervalArray (thus having the
			 * same pointer values).
			 */
			prunedList = list_union_ptr(prunedList, pruneOneList);
		}
		else
		{
			prunedList = pruneOneList;
		}
		foundRestriction = true;
	}

	/* found no valid restriction, build list of all shards */
	if (!foundRestriction)
	{
		prunedList = ShardArrayToList(cacheEntry->sortedShardIntervalArray,
									  cacheEntry->shardIntervalArrayLength);
	}

	/* if requested, copy the partition value constant */
	if (partitionValueConst != NULL)
	{
		if (singlePartitionValueConst != NULL)
		{
			*partitionValueConst = copyObject(singlePartitionValueConst);
		}
		else
		{
			*partitionValueConst = NULL;
		}
	}

	/*
	 * Deep copy list, so it's independent of the DistTableCacheEntry
	 * contents.
	 */
	return DeepCopyShardIntervalList(prunedList);
}


/*
 * ContainsFalseClause returns whether the flattened where clause list
 * contains false as a clause.
 */
bool
ContainsFalseClause(List *whereClauseList)
{
	bool containsFalseClause = false;
	ListCell *clauseCell = NULL;

	foreach(clauseCell, whereClauseList)
	{
		Node *clause = (Node *) lfirst(clauseCell);

		if (IsA(clause, Const))
		{
			Const *constant = (Const *) clause;
			if (constant->consttype == BOOLOID && !DatumGetBool(constant->constvalue))
			{
				containsFalseClause = true;
				break;
			}
		}
	}

	return containsFalseClause;
}


/*
 * PrunableExpressions builds a list of all prunable expressions in node,
 * storing them in context->pruningInstances.
 */
static void
PrunableExpressions(Node *node, ClauseWalkerContext *context)
{
	/*
	 * Build initial list of prunable expressions.  As long as only,
	 * implicitly or explicitly, ANDed expressions are found, this perform a
	 * depth-first search.  When an ORed expression is found, the current
	 * PruningInstance is added to context->pruningInstances (once for each
	 * ORed expression), then the tree-traversal is continued without
	 * recursing.  Once at the top-level again, we'll process all pending
	 * expressions - that allows us to find all ANDed expressions, before
	 * recursing into an ORed expression.
	 */
	PrunableExpressionsWalker(node, context);

	/*
	 * Process all pending instances.  While processing, new ones might be
	 * added to the list, so don't use foreach().
	 *
	 * Check the places in PruningInstanceWalker that push onto
	 * context->pendingInstances why construction of the PruningInstance might
	 * be pending.
	 *
	 * We copy the partial PruningInstance, and continue adding information by
	 * calling PrunableExpressionsWalker() on the copy, continuing at the the
	 * node stored in PendingPruningInstance->continueAt.
	 */
	while (context->pendingInstances != NIL)
	{
		PendingPruningInstance *instance =
			(PendingPruningInstance *) linitial(context->pendingInstances);
		PruningInstance *newPrune = CopyPartialPruningInstance(instance->instance);

		context->pendingInstances = list_delete_first(context->pendingInstances);

		context->currentPruningInstance = newPrune;
		PrunableExpressionsWalker(instance->continueAt, context);
		context->currentPruningInstance = NULL;
	}
}


/*
 * PrunableExpressionsWalker() is the main work horse for
 * PrunableExpressions().
 */
static bool
PrunableExpressionsWalker(Node *node, ClauseWalkerContext *context)
{
	if (node == NULL)
	{
		return false;
	}

	/*
	 * Check for expressions understood by this routine.
	 */
	if (IsA(node, List))
	{
		/* at the top of quals we'll frequently see lists, those are to be treated as ANDs */
	}
	else if (IsA(node, BoolExpr))
	{
		BoolExpr *boolExpr = (BoolExpr *) node;

		if (boolExpr->boolop == NOT_EXPR)
		{
			return false;
		}
		else if (boolExpr->boolop == AND_EXPR)
		{
			return expression_tree_walker((Node *) boolExpr->args,
										  PrunableExpressionsWalker, context);
		}
		else if (boolExpr->boolop == OR_EXPR)
		{
			ListCell *opCell = NULL;

			/*
			 * "Queue" partial pruning instances.  This is used to convert
			 * expressions like (A AND (B OR C) AND D) into (A AND B AND D),
			 * (A AND C AND D), with A, B, C, D being restrictions.  When the
			 * OR is encountered, a reference to the partially built
			 * PruningInstance (containing A at this point), is added to
			 * context->pendingInstances once for B and once for C.  Once a
			 * full tree-walk completed, PrunableExpressions() will complete
			 * the pending instances, which'll now also know about restriction
			 * D, by calling PrunableExpressionsWalker() once for B and once
			 * for C.
			 */
			foreach(opCell, boolExpr->args)
			{
				AddNewConjuction(context, lfirst(opCell));
			}

			return false;
		}
	}
	else if (IsA(node, OpExpr))
	{
		OpExpr *opClause = (OpExpr *) node;
		PruningInstance *prune = context->currentPruningInstance;
		Node *leftOperand = NULL;
		Node *rightOperand = NULL;
		Const *constantClause = NULL;
		Var *varClause = NULL;

		if (!prune->addedToPruningInstances)
		{
			context->pruningInstances = lappend(context->pruningInstances,
												prune);
			prune->addedToPruningInstances = true;
		}

		if (list_length(opClause->args) == 2)
		{
			leftOperand = get_leftop((Expr *) opClause);
			rightOperand = get_rightop((Expr *) opClause);

			leftOperand = strip_implicit_coercions(leftOperand);
			rightOperand = strip_implicit_coercions(rightOperand);

			if (IsA(rightOperand, Const) && IsA(leftOperand, Var))
			{
				constantClause = (Const *) rightOperand;
				varClause = (Var *) leftOperand;
			}
			else if (IsA(leftOperand, Const) && IsA(rightOperand, Var))
			{
				constantClause = (Const *) leftOperand;
				varClause = (Var *) rightOperand;
			}
		}

		if (constantClause && varClause && equal(varClause, context->partitionColumn))
		{
			/*
			 * Found a restriction on the partition column itself. Update the
			 * current constraint with the new information.
			 */
			AddPartitionKeyRestrictionToInstance(context,
												 opClause, varClause, constantClause);
		}
		else if (constantClause && varClause &&
				 varClause->varattno == RESERVED_HASHED_COLUMN_ID)
		{
			/*
			 * Found restriction that directly specifies the boundaries of a
			 * hashed column.
			 */
			AddHashRestrictionToInstance(context, opClause, varClause, constantClause);
		}

		return false;
	}
	else if (IsA(node, ScalarArrayOpExpr))
	{
		ScalarArrayOpExpr *arrayOperatorExpression = (ScalarArrayOpExpr *) node;
		AddSAOPartitionKeyRestrictionToInstance(context, arrayOperatorExpression);

		return false;
	}
	else
	{
		PruningInstance *prune = context->currentPruningInstance;

		/*
		 * Mark expression as added, so we'll fail pruning if there's no ANDed
		 * restrictions that we know how to deal with.
		 */
		if (!prune->addedToPruningInstances)
		{
			context->pruningInstances = lappend(context->pruningInstances,
												prune);
			prune->addedToPruningInstances = true;
		}

		return false;
	}

	return expression_tree_walker(node, PrunableExpressionsWalker, context);
}


/*
 * AddSAOPartitionKeyRestrictionToInstance adds partcol = arrayelem operator
 * restriction to the current pruning instance for each element of the array. These
 * restrictions are added to pruning instance to prune shards based on IN/=ANY
 * constraints.
 */
static void
AddSAOPartitionKeyRestrictionToInstance(ClauseWalkerContext *context,
										ScalarArrayOpExpr *arrayOperatorExpression)
{
	PruningInstance *prune = context->currentPruningInstance;
	Node *leftOpExpression = linitial(arrayOperatorExpression->args);
	Node *strippedLeftOpExpression = strip_implicit_coercions(leftOpExpression);
	bool usingEqualityOperator = OperatorImplementsEquality(
		arrayOperatorExpression->opno);
	Expr *arrayArgument = (Expr *) lsecond(arrayOperatorExpression->args);

	/* checking for partcol = ANY(const, value, s); or partcol IN (const,b,c); */
	if (usingEqualityOperator && strippedLeftOpExpression != NULL &&
		equal(strippedLeftOpExpression, context->partitionColumn) &&
		IsA(arrayArgument, Const))
	{
		ArrayType *array = NULL;
		int16 typlen = 0;
		bool typbyval = false;
		char typalign = '\0';
		Oid elementType = 0;
		ArrayIterator arrayIterator = NULL;
		Datum arrayElement = 0;
		Datum inArray = ((Const *) arrayArgument)->constvalue;
		bool isNull = false;

		/* check for the NULL right-hand expression*/
		if (inArray == 0)
		{
			return;
		}

		array = DatumGetArrayTypeP(((Const *) arrayArgument)->constvalue);

		/* get the necessary information from array type to iterate over it */
		elementType = ARR_ELEMTYPE(array);
		get_typlenbyvalalign(elementType,
							 &typlen,
							 &typbyval,
							 &typalign);

		/* Iterate over the righthand array of expression */
		arrayIterator = array_create_iterator(array, 0, NULL);
		while (array_iterate(arrayIterator, &arrayElement, &isNull))
		{
			OpExpr *arrayEqualityOp = NULL;
			Const *constElement = makeConst(elementType, -1,
											DEFAULT_COLLATION_OID, typlen, arrayElement,
											isNull, typbyval);

			/* build partcol = arrayelem operator */
			arrayEqualityOp = makeNode(OpExpr);
			arrayEqualityOp->opno = arrayOperatorExpression->opno;
			arrayEqualityOp->opfuncid = arrayOperatorExpression->opfuncid;
			arrayEqualityOp->inputcollid = arrayOperatorExpression->inputcollid;
			arrayEqualityOp->opresulttype = get_func_rettype(
				arrayOperatorExpression->opfuncid);
			arrayEqualityOp->opcollid = DEFAULT_COLLATION_OID;
			arrayEqualityOp->location = -1;
			arrayEqualityOp->args = list_make2(strippedLeftOpExpression, constElement);

			AddNewConjuction(context, arrayEqualityOp);
		}
	}

	/* Since we could not deal with the constraint, add the pruning instance to
	 * pruning instance list and labeled it as added.
	 */
	else if (!prune->addedToPruningInstances)
	{
		context->pruningInstances = lappend(context->pruningInstances, prune);
		prune->addedToPruningInstances = true;
	}
}


/*
 * AddNewConjuction adds the OpExpr to pending instance list of context
 * as conjunction as partial instance.
 */
static void
AddNewConjuction(ClauseWalkerContext *context, OpExpr *op)
{
	PendingPruningInstance *instance = palloc0(sizeof(PendingPruningInstance));

	instance->instance = context->currentPruningInstance;
	instance->continueAt = (Node *) op;

	/*
	 * Signal that this instance is not to be used for pruning on
	 * its own.  Once the pending instance is processed, it'll be
	 * used.
	 */
	instance->instance->isPartial = true;
	context->pendingInstances = lappend(context->pendingInstances, instance);
}


/*
 * AddPartitionKeyRestrictionToInstance adds information about a PartitionKey
 * $op Const restriction to the current pruning instance.
 */
static void
AddPartitionKeyRestrictionToInstance(ClauseWalkerContext *context, OpExpr *opClause,
									 Var *partitionColumn, Const *constantClause)
{
	PruningInstance *prune = context->currentPruningInstance;
	List *btreeInterpretationList = NULL;
	ListCell *btreeInterpretationCell = NULL;
	bool matchedOp = false;

	Assert(IsBinaryCoercible(constantClause->consttype, partitionColumn->vartype));

	btreeInterpretationList =
		get_op_btree_interpretation(opClause->opno);
	foreach(btreeInterpretationCell, btreeInterpretationList)
	{
		OpBtreeInterpretation *btreeInterpretation =
			(OpBtreeInterpretation *) lfirst(btreeInterpretationCell);

		switch (btreeInterpretation->strategy)
		{
			case BTLessStrategyNumber:
			{
				if (!prune->lessConsts ||
					PerformValueCompare(&context->compareValueFunctionCall,
										constantClause->constvalue,
										prune->lessConsts->constvalue) < 0)
				{
					prune->lessConsts = constantClause;
				}
				matchedOp = true;
				break;
			}

			case BTLessEqualStrategyNumber:
			{
				if (!prune->lessEqualConsts ||
					PerformValueCompare(&context->compareValueFunctionCall,
										constantClause->constvalue,
										prune->lessEqualConsts->constvalue) < 0)
				{
					prune->lessEqualConsts = constantClause;
				}
				matchedOp = true;
				break;
			}

			case BTEqualStrategyNumber:
			{
				if (!prune->equalConsts)
				{
					prune->equalConsts = constantClause;
				}
				else if (PerformValueCompare(&context->compareValueFunctionCall,
											 constantClause->constvalue,
											 prune->equalConsts->constvalue) != 0)
				{
					/* key can't be equal to two values */
					prune->evaluatesToFalse = true;
				}
				matchedOp = true;
				break;
			}

			case BTGreaterEqualStrategyNumber:
			{
				if (!prune->greaterEqualConsts ||
					PerformValueCompare(&context->compareValueFunctionCall,
										constantClause->constvalue,
										prune->greaterEqualConsts->constvalue) > 0
					)
				{
					prune->greaterEqualConsts = constantClause;
				}
				matchedOp = true;
				break;
			}

			case BTGreaterStrategyNumber:
			{
				if (!prune->greaterConsts ||
					PerformValueCompare(&context->compareValueFunctionCall,
										constantClause->constvalue,
										prune->greaterConsts->constvalue) > 0)
				{
					prune->greaterConsts = constantClause;
				}
				matchedOp = true;
				break;
			}

			case ROWCOMPARE_NE:
			{
				/* TODO: could add support for this, if we feel like it */
				matchedOp = false;
				break;
			}

			default:
				Assert(false);
		}
	}

	if (!matchedOp)
	{
		prune->otherRestrictions =<commit_msg>Add second assert to guard against future changes<commit_after>/*-------------------------------------------------------------------------
 *
 * shard_pruning.c
 *   Shard pruning related code.
 *
 * The goal of shard pruning is to find a minimal (super)set of shards that
 * need to be queried to find rows matching the expression in a query.
 *
 * In PruneShards, we first compute a simplified disjunctive normal form (DNF)
 * of the expression as a list of pruning instances. Each pruning instance
 * contains all AND-ed constraints on the partition column. An OR expression
 * will result in two or more new pruning instances being added for the
 * subexpressions. The "parent" instance is marked isPartial and ignored
 * during pruning.
 *
 * We use the distributive property for constraints of the form P AND (Q OR R)
 * to rewrite it to (P AND Q) OR (P AND R) by copying constraints from parent
 * to "child" pruning instances. However, we do not distribute nested
 * expressions. While (P OR Q) AND (R OR S) is logically equivalent to (P AND
 * R) OR (P AND S) OR (Q AND R) OR (Q AND S), in our implementation it becomes
 * P OR Q OR R OR S. This is acceptable since this will always result in a
 * superset of shards.  If this proves to be a issue in practice, a more
 * complete algorithm could be implemented.
 *
 * We then evaluate each non-partial pruning instance in the disjunction
 * through the following, increasingly expensive, steps:
 *
 * 1) If there is a constant equality constraint on the partition column, and
 *    no overlapping shards exist, find the shard interval in which the
 *    constant falls
 *
 * 2) If there is a hash range constraint on the partition column, find the
 *    shard interval matching the range
 *
 * 3) If there are range constraints (e.g. (a > 0 AND a < 10)) on the
 *    partition column, find the shard intervals that overlap with the range
 *
 * 4) If there are overlapping shards, exhaustively search all shards that are
 *    not excluded by constraints
 *
 * Finally, the union of the shards found by each pruning instance is
 * returned.
 *
 * Copyright (c) 2014-2017, <NAME>, Inc.
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "distributed/shard_pruning.h"

#include "access/nbtree.h"
#include "catalog/pg_am.h"
#include "catalog/pg_collation.h"
#include "catalog/pg_type.h"
#include "distributed/metadata_cache.h"
#include "distributed/distributed_planner.h"
#include "distributed/multi_join_order.h"
#include "distributed/multi_physical_planner.h"
#include "distributed/shardinterval_utils.h"
#include "distributed/pg_dist_partition.h"
#include "distributed/worker_protocol.h"
#include "nodes/nodeFuncs.h"
#include "nodes/makefuncs.h"
#include "optimizer/clauses.h"
#include "parser/parse_coerce.h"
#include "utils/arrayaccess.h"
#include "utils/catcache.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"

/*
 * A pruning instance is a set of ANDed constraints on a partition key.
 */
typedef struct PruningInstance
{
	/* Does this instance contain any prunable expressions? */
	bool hasValidConstraint;

	/*
	 * This constraint never evaluates to true, i.e. pruning does not have to
	 * be performed.
	 */
	bool evaluatesToFalse;

	/*
	 * Constraints on the partition column value.  If multiple values are
	 * found the more restrictive one should be stored here.  Even in case of
	 * a hash-partitioned table, actual column-values are stored here, *not*
	 * hashed values.
	 */
	Const *lessConsts;
	Const *lessEqualConsts;
	Const *equalConsts;
	Const *greaterEqualConsts;
	Const *greaterConsts;

	/*
	 * Constraint using a pre-hashed column value. The constant will store the
	 * hashed value, not the original value of the restriction.
	 */
	Const *hashedEqualConsts;

	/*
	 * Types of constraints not understood.  We could theoretically try more
	 * expensive methods of pruning if any such restrictions are found.
	 *
	 * TODO: any actual use for this? Right now there seems little point.
	 */
	List *otherRestrictions;

	/*
	 * Has this PruningInstance been added to
	 * ClauseWalkerContext->pruningInstances? This is not done immediately,
	 * but the first time a constraint (independent of us being able to handle
	 * that constraint) is found.
	 */
	bool addedToPruningInstances;

	/*
	 * When OR clauses are found, the non-ORed part (think of a < 3 AND (a > 5
	 * OR a > 7)) of the expression is stored in one PruningInstance which is
	 * then copied for the ORed expressions.  The original is marked as
	 * isPartial, to avoid it being used for pruning.
	 */
	bool isPartial;
} PruningInstance;


/*
 * Partial instances that need to be finished building.  This is used to
 * collect all ANDed restrictions, before looking into ORed expressions.
 */
typedef struct PendingPruningInstance
{
	PruningInstance *instance;
	Node *continueAt;
} PendingPruningInstance;


/*
 * Data necessary to perform a single PruneShards().
 */
typedef struct ClauseWalkerContext
{
	Var *partitionColumn;
	char partitionMethod;

	/* ORed list of pruning targets */
	List *pruningInstances;

	/*
	 * Partially built PruningInstances, that need to be completed by doing a
	 * separate PrunableExpressionsWalker() pass.
	 */
	List *pendingInstances;

	/* PruningInstance currently being built, all elegible constraints are added here */
	PruningInstance *currentPruningInstance;

	/*
	 * Information about function calls we need to perform. Re-using the same
	 * FunctionCallInfoData, instead of using FunctionCall2Coll, is often
	 * cheaper.
	 */
	FunctionCallInfoData compareValueFunctionCall;
	FunctionCallInfoData compareIntervalFunctionCall;
} ClauseWalkerContext;

static void PrunableExpressions(Node *originalNode, ClauseWalkerContext *context);
static bool PrunableExpressionsWalker(Node *originalNode, ClauseWalkerContext *context);
static void AddPartitionKeyRestrictionToInstance(ClauseWalkerContext *context,
												 OpExpr *opClause, Var *varClause,
												 Const *constantClause);
static void AddSAOPartitionKeyRestrictionToInstance(ClauseWalkerContext *context,
													ScalarArrayOpExpr *
													arrayOperatorExpression);
static void AddHashRestrictionToInstance(ClauseWalkerContext *context, OpExpr *opClause,
										 Var *varClause, Const *constantClause);
static void AddNewConjuction(ClauseWalkerContext *context, OpExpr *op);
static PruningInstance * CopyPartialPruningInstance(PruningInstance *sourceInstance);
static List * ShardArrayToList(ShardInterval **shardArray, int length);
static List * DeepCopyShardIntervalList(List *originalShardIntervalList);
static int PerformValueCompare(FunctionCallInfoData *compareFunctionCall, Datum a,
							   Datum b);
static int PerformCompare(FunctionCallInfoData *compareFunctionCall);

static List * PruneOne(DistTableCacheEntry *cacheEntry, ClauseWalkerContext *context,
					   PruningInstance *prune);
static List * PruneWithBoundaries(DistTableCacheEntry *cacheEntry,
								  ClauseWalkerContext *context,
								  PruningInstance *prune);
static List * ExhaustivePrune(DistTableCacheEntry *cacheEntry,
							  ClauseWalkerContext *context,
							  PruningInstance *prune);
static bool ExhaustivePruneOne(ShardInterval *curInterval,
							   ClauseWalkerContext *context,
							   PruningInstance *prune);
static int UpperShardBoundary(Datum partitionColumnValue,
							  ShardInterval **shardIntervalCache,
							  int shardCount, FunctionCallInfoData *compareFunction,
							  bool includeMin);
static int LowerShardBoundary(Datum partitionColumnValue,
							  ShardInterval **shardIntervalCache,
							  int shardCount, FunctionCallInfoData *compareFunction,
							  bool includeMax);


/*
 * PruneShards returns all shards from a distributed table that cannot be
 * proven to be eliminated by whereClauseList.
 *
 * For reference tables, the function simply returns the single shard that the
 * table has.
 *
 * When there is a single <partition column> = <constant> filter in the where
 * clause list, the constant is written to the partitionValueConst pointer.
 */
List *
PruneShards(Oid relationId, Index rangeTableId, List *whereClauseList,
			Const **partitionValueConst)
{
	DistTableCacheEntry *cacheEntry = DistributedTableCacheEntry(relationId);
	int shardCount = cacheEntry->shardIntervalArrayLength;
	char partitionMethod = cacheEntry->partitionMethod;
	ClauseWalkerContext context = { 0 };
	ListCell *pruneCell;
	List *prunedList = NIL;
	bool foundRestriction = false;
	bool foundPartitionColumnValue = false;
	Const *singlePartitionValueConst = NULL;

	/* there are no shards to return */
	if (shardCount == 0)
	{
		return NIL;
	}

	/* always return empty result if WHERE clause is of the form: false (AND ..) */
	if (ContainsFalseClause(whereClauseList))
	{
		return NIL;
	}

	/* short circuit for reference tables */
	if (partitionMethod == DISTRIBUTE_BY_NONE)
	{
		prunedList = ShardArrayToList(cacheEntry->sortedShardIntervalArray,
									  cacheEntry->shardIntervalArrayLength);
		return DeepCopyShardIntervalList(prunedList);
	}


	context.partitionMethod = partitionMethod;
	context.partitionColumn = PartitionColumn(relationId, rangeTableId);
	context.currentPruningInstance = palloc0(sizeof(PruningInstance));

	if (cacheEntry->shardIntervalCompareFunction)
	{
		/* initiate function call info once (allows comparators to cache metadata) */
		InitFunctionCallInfoData(context.compareIntervalFunctionCall,
								 cacheEntry->shardIntervalCompareFunction,
								 2, DEFAULT_COLLATION_OID, NULL, NULL);
	}
	else
	{
		ereport(ERROR, (errmsg("shard pruning not possible without "
							   "a shard interval comparator")));
	}

	if (cacheEntry->shardColumnCompareFunction)
	{
		/* initiate function call info once (allows comparators to cache metadata) */
		InitFunctionCallInfoData(context.compareValueFunctionCall,
								 cacheEntry->shardColumnCompareFunction,
								 2, DEFAULT_COLLATION_OID, NULL, NULL);
	}
	else
	{
		ereport(ERROR, (errmsg("shard pruning not possible without "
							   "a partition column comparator")));
	}

	/* Figure out what we can prune on */
	PrunableExpressions((Node *) whereClauseList, &context);

	/*
	 * Prune using each of the PrunableInstances we found, and OR results
	 * together.
	 */
	foreach(pruneCell, context.pruningInstances)
	{
		PruningInstance *prune = (PruningInstance *) lfirst(pruneCell);
		List *pruneOneList;

		/*
		 * If this is a partial instance, a fully built one has also been
		 * added. Skip.
		 */
		if (prune->isPartial)
		{
			continue;
		}

		/*
		 * If the current instance has no prunable expressions, we'll have to
		 * return all shards.  No point in continuing pruning in that case.
		 */
		if (!prune->hasValidConstraint)
		{
			foundRestriction = false;
			break;
		}

		if (context.partitionMethod == DISTRIBUTE_BY_HASH)
		{
			if (!prune->evaluatesToFalse && !prune->equalConsts &&
				!prune->hashedEqualConsts)
			{
				/* if hash-partitioned and no equals constraints, return all shards */
				foundRestriction = false;
				break;
			}
			else if (partitionValueConst != NULL && prune->equalConsts != NULL)
			{
				if (!foundPartitionColumnValue)
				{
					/* remember the partition column value */
					singlePartitionValueConst = prune->equalConsts;
					foundPartitionColumnValue = true;
				}
				else if (singlePartitionValueConst == NULL)
				{
					/* already found multiple partition column values */
				}
				else if (!equal(prune->equalConsts, singlePartitionValueConst))
				{
					/* found multiple partition column values */
					singlePartitionValueConst = NULL;
				}
			}
		}

		pruneOneList = PruneOne(cacheEntry, &context, prune);

		if (prunedList)
		{
			/*
			 * We can use list_union_ptr, which is a lot faster than doing
			 * comparing shards by value, because all the ShardIntervals are
			 * guaranteed to be from
			 * DistTableCacheEntry->sortedShardIntervalArray (thus having the
			 * same pointer values).
			 */
			prunedList = list_union_ptr(prunedList, pruneOneList);
		}
		else
		{
			prunedList = pruneOneList;
		}
		foundRestriction = true;
	}

	/* found no valid restriction, build list of all shards */
	if (!foundRestriction)
	{
		prunedList = ShardArrayToList(cacheEntry->sortedShardIntervalArray,
									  cacheEntry->shardIntervalArrayLength);
	}

	/* if requested, copy the partition value constant */
	if (partitionValueConst != NULL)
	{
		if (singlePartitionValueConst != NULL)
		{
			*partitionValueConst = copyObject(singlePartitionValueConst);
		}
		else
		{
			*partitionValueConst = NULL;
		}
	}

	/*
	 * Deep copy list, so it's independent of the DistTableCacheEntry
	 * contents.
	 */
	return DeepCopyShardIntervalList(prunedList);
}


/*
 * ContainsFalseClause returns whether the flattened where clause list
 * contains false as a clause.
 */
bool
ContainsFalseClause(List *whereClauseList)
{
	bool containsFalseClause = false;
	ListCell *clauseCell = NULL;

	foreach(clauseCell, whereClauseList)
	{
		Node *clause = (Node *) lfirst(clauseCell);

		if (IsA(clause, Const))
		{
			Const *constant = (Const *) clause;
			if (constant->consttype == BOOLOID && !DatumGetBool(constant->constvalue))
			{
				containsFalseClause = true;
				break;
			}
		}
	}

	return containsFalseClause;
}


/*
 * PrunableExpressions builds a list of all prunable expressions in node,
 * storing them in context->pruningInstances.
 */
static void
PrunableExpressions(Node *node, ClauseWalkerContext *context)
{
	/*
	 * Build initial list of prunable expressions.  As long as only,
	 * implicitly or explicitly, ANDed expressions are found, this perform a
	 * depth-first search.  When an ORed expression is found, the current
	 * PruningInstance is added to context->pruningInstances (once for each
	 * ORed expression), then the tree-traversal is continued without
	 * recursing.  Once at the top-level again, we'll process all pending
	 * expressions - that allows us to find all ANDed expressions, before
	 * recursing into an ORed expression.
	 */
	PrunableExpressionsWalker(node, context);

	/*
	 * Process all pending instances.  While processing, new ones might be
	 * added to the list, so don't use foreach().
	 *
	 * Check the places in PruningInstanceWalker that push onto
	 * context->pendingInstances why construction of the PruningInstance might
	 * be pending.
	 *
	 * We copy the partial PruningInstance, and continue adding information by
	 * calling PrunableExpressionsWalker() on the copy, continuing at the the
	 * node stored in PendingPruningInstance->continueAt.
	 */
	while (context->pendingInstances != NIL)
	{
		PendingPruningInstance *instance =
			(PendingPruningInstance *) linitial(context->pendingInstances);
		PruningInstance *newPrune = CopyPartialPruningInstance(instance->instance);

		context->pendingInstances = list_delete_first(context->pendingInstances);

		context->currentPruningInstance = newPrune;
		PrunableExpressionsWalker(instance->continueAt, context);
		context->currentPruningInstance = NULL;
	}
}


/*
 * PrunableExpressionsWalker() is the main work horse for
 * PrunableExpressions().
 */
static bool
PrunableExpressionsWalker(Node *node, ClauseWalkerContext *context)
{
	if (node == NULL)
	{
		return false;
	}

	/*
	 * Check for expressions understood by this routine.
	 */
	if (IsA(node, List))
	{
		/* at the top of quals we'll frequently see lists, those are to be treated as ANDs */
	}
	else if (IsA(node, BoolExpr))
	{
		BoolExpr *boolExpr = (BoolExpr *) node;

		if (boolExpr->boolop == NOT_EXPR)
		{
			return false;
		}
		else if (boolExpr->boolop == AND_EXPR)
		{
			return expression_tree_walker((Node *) boolExpr->args,
										  PrunableExpressionsWalker, context);
		}
		else if (boolExpr->boolop == OR_EXPR)
		{
			ListCell *opCell = NULL;

			/*
			 * "Queue" partial pruning instances.  This is used to convert
			 * expressions like (A AND (B OR C) AND D) into (A AND B AND D),
			 * (A AND C AND D), with A, B, C, D being restrictions.  When the
			 * OR is encountered, a reference to the partially built
			 * PruningInstance (containing A at this point), is added to
			 * context->pendingInstances once for B and once for C.  Once a
			 * full tree-walk completed, PrunableExpressions() will complete
			 * the pending instances, which'll now also know about restriction
			 * D, by calling PrunableExpressionsWalker() once for B and once
			 * for C.
			 */
			foreach(opCell, boolExpr->args)
			{
				AddNewConjuction(context, lfirst(opCell));
			}

			return false;
		}
	}
	else if (IsA(node, OpExpr))
	{
		OpExpr *opClause = (OpExpr *) node;
		PruningInstance *prune = context->currentPruningInstance;
		Node *leftOperand = NULL;
		Node *rightOperand = NULL;
		Const *constantClause = NULL;
		Var *varClause = NULL;

		if (!prune->addedToPruningInstances)
		{
			context->pruningInstances = lappend(context->pruningInstances,
												prune);
			prune->addedToPruningInstances = true;
		}

		if (list_length(opClause->args) == 2)
		{
			leftOperand = get_leftop((Expr *) opClause);
			rightOperand = get_rightop((Expr *) opClause);

			leftOperand = strip_implicit_coercions(leftOperand);
			rightOperand = strip_implicit_coercions(rightOperand);

			if (IsA(rightOperand, Const) && IsA(leftOperand, Var))
			{
				constantClause = (Const *) rightOperand;
				varClause = (Var *) leftOperand;
			}
			else if (IsA(leftOperand, Const) && IsA(rightOperand, Var))
			{
				constantClause = (Const *) leftOperand;
				varClause = (Var *) rightOperand;
			}
		}

		if (constantClause && varClause && equal(varClause, context->partitionColumn))
		{
			/*
			 * Found a restriction on the partition column itself. Update the
			 * current constraint with the new information.
			 */
			AddPartitionKeyRestrictionToInstance(context,
												 opClause, varClause, constantClause);
		}
		else if (constantClause && varClause &&
				 varClause->varattno == RESERVED_HASHED_COLUMN_ID)
		{
			/*
			 * Found restriction that directly specifies the boundaries of a
			 * hashed column.
			 */
			AddHashRestrictionToInstance(context, opClause, varClause, constantClause);
		}

		return false;
	}
	else if (IsA(node, ScalarArrayOpExpr))
	{
		ScalarArrayOpExpr *arrayOperatorExpression = (ScalarArrayOpExpr *) node;
		AddSAOPartitionKeyRestrictionToInstance(context, arrayOperatorExpression);

		return false;
	}
	else
	{
		PruningInstance *prune = context->currentPruningInstance;

		/*
		 * Mark expression as added, so we'll fail pruning if there's no ANDed
		 * restrictions that we know how to deal with.
		 */
		if (!prune->addedToPruningInstances)
		{
			context->pruningInstances = lappend(context->pruningInstances,
												prune);
			prune->addedToPruningInstances = true;
		}

		return false;
	}

	return expression_tree_walker(node, PrunableExpressionsWalker, context);
}


/*
 * AddSAOPartitionKeyRestrictionToInstance adds partcol = arrayelem operator
 * restriction to the current pruning instance for each element of the array. These
 * restrictions are added to pruning instance to prune shards based on IN/=ANY
 * constraints.
 */
static void
AddSAOPartitionKeyRestrictionToInstance(ClauseWalkerContext *context,
										ScalarArrayOpExpr *arrayOperatorExpression)
{
	PruningInstance *prune = context->currentPruningInstance;
	Node *leftOpExpression = linitial(arrayOperatorExpression->args);
	Node *strippedLeftOpExpression = strip_implicit_coercions(leftOpExpression);
	bool usingEqualityOperator = OperatorImplementsEquality(
		arrayOperatorExpression->opno);
	Expr *arrayArgument = (Expr *) lsecond(arrayOperatorExpression->args);

	/* checking for partcol = ANY(const, value, s); or partcol IN (const,b,c); */
	if (usingEqualityOperator && strippedLeftOpExpression != NULL &&
		equal(strippedLeftOpExpression, context->partitionColumn) &&
		IsA(arrayArgument, Const))
	{
		ArrayType *array = NULL;
		int16 typlen = 0;
		bool typbyval = false;
		char typalign = '\0';
		Oid elementType = 0;
		ArrayIterator arrayIterator = NULL;
		Datum arrayElement = 0;
		Datum inArray = ((Const *) arrayArgument)->constvalue;
		bool isNull = false;

		/* check for the NULL right-hand expression*/
		if (inArray == 0)
		{
			return;
		}

		array = DatumGetArrayTypeP(((Const *) arrayArgument)->constvalue);

		/* get the necessary information from array type to iterate over it */
		elementType = ARR_ELEMTYPE(array);
		get_typlenbyvalalign(elementType,
							 &typlen,
							 &typbyval,
							 &typalign);

		/* Iterate over the righthand array of expression */
		arrayIterator = array_create_iterator(array, 0, NULL);
		while (array_iterate(arrayIterator, &arrayElement, &isNull))
		{
			OpExpr *arrayEqualityOp = NULL;
			Const *constElement = makeConst(elementType, -1,
											DEFAULT_COLLATION_OID, typlen, arrayElement,
											isNull, typbyval);

			/* build partcol = arrayelem operator */
			arrayEqualityOp = makeNode(OpExpr);
			arrayEqualityOp->opno = arrayOperatorExpression->opno;
			arrayEqualityOp->opfuncid = arrayOperatorExpression->opfuncid;
			arrayEqualityOp->inputcollid = arrayOperatorExpression->inputcollid;
			arrayEqualityOp->opresulttype = get_func_rettype(
				arrayOperatorExpression->opfuncid);
			arrayEqualityOp->opcollid = DEFAULT_COLLATION_OID;
			arrayEqualityOp->location = -1;
			arrayEqualityOp->args = list_make2(strippedLeftOpExpression, constElement);

			AddNewConjuction(context, arrayEqualityOp);
		}
	}

	/* Since we could not deal with the constraint, add the pruning instance to
	 * pruning instance list and labeled it as added.
	 */
	else if (!prune->addedToPruningInstances)
	{
		context->pruningInstances = lappend(context->pruningInstances, prune);
		prune->addedToPruningInstances = true;
	}
}


/*
 * AddNewConjuction adds the OpExpr to pending instance list of context
 * as conjunction as partial instance.
 */
static void
AddNewConjuction(ClauseWalkerContext *context, OpExpr *op)
{
	PendingPruningInstance *instance = palloc0(sizeof(PendingPruningInstance));

	instance->instance = context->currentPruningInstance;
	instance->continueAt = (Node *) op;

	/*
	 * Signal that this instance is not to be used for pruning on
	 * its own.  Once the pending instance is processed, it'll be
	 * used.
	 */
	instance->instance->isPartial = true;
	context->pendingInstances = lappend(context->pendingInstances, instance);
}


/*
 * AddPartitionKeyRestrictionToInstance adds information about a PartitionKey
 * $op Const restriction to the current pruning instance.
 */
static void
AddPartitionKeyRestrictionToInstance(ClauseWalkerContext *context, OpExpr *opClause,
									 Var *partitionColumn, Const *constantClause)
{
	PruningInstance *prune = context->currentPruningInstance;
	List *btreeInterpretationList = NULL;
	ListCell *btreeInterpretationCell = NULL;
	bool matchedOp = false;

	Assert(IsBinaryCoercible(constantClause->consttype, partitionColumn->vartype));

	btreeInterpretationList =
		get_op_btree_interpretation(opClause->opno);
	foreach(btreeInterpretationCell, btreeInterpretationList)
	{
		OpBtreeInterpretation *btreeInterpretation =
			(OpBtreeInterpretation *) lfirst(btreeInterpretationCell);

		switch (btreeInterpretation->strategy)
		{
			case BTLessStrategyNumber:
			{
				if (!prune->lessConsts ||
					PerformValueCompare(&context->compareValueFunctionCall,
										constantClause->constvalue,
										prune->lessConsts->constvalue) < 0)
				{
					prune->lessConsts = constantClause;
				}
				matchedOp = true;
				break;
			}

			case BTLessEqualStrategyNumber:
			{
				if (!prune->lessEqualConsts ||
					PerformValueCompare(&context->compareValueFunctionCall,
										constantClause->constvalue,
										prune->lessEqualConsts->constvalue) < 0)
				{
					prune->lessEqualConsts = constantClause;
				}
				matchedOp = true;
				break;
			}

			case BTEqualStrategyNumber:
			{
				if (!prune->equalConsts)
				{
					prune->equalConsts = constantClause;
				}
				else if (PerformValueCompare(&context->compareValueFunctionCall,
											 constantClause->constvalue,
											 prune->equalConsts->constvalue) != 0)
				{
					/* key can't be equal to two values */
					prune->evaluatesToFalse = true;
				}
				matchedOp = true;
				break;
			}

			case BTGreaterEqualStrategyNumber:
			{
				if (!prune->greaterEqualConsts ||
					PerformValueCompare(&context->compareValueFunctionCall,
										constantClause->constvalue,
										prune->greaterEqualConsts->constvalue) > 0
					)
				{
					prune->greaterEqualConsts = constantClause;
				}
				matchedOp = true;
				break;
			}

			case BTGreaterStrategyNumber:
			{
				if (!prune->greaterConsts ||
					PerformValueCompare(&context->compareValueFunctionCall,
										constantClause->constvalue,
										prune->greaterConsts->constvalue) > 0)
				{
					prune->greaterConsts = constantClause;
				}
				matchedOp = true;
				break;
			}

			case ROWCOMPARE_NE:
			{
				/*
				 * This case should only arise when ALL list elements have this
				 * "strategy" number set. Skipping to the end of the list might
				 * protect us if that assumption is violated, and an Assert can
				 * notify us if it ever is...
				 */

				/* should see this value immediately */
				Assert(btreeInterpretationCell == btreeInterpretationList->head);

				/* stop processing early, would only see unsupported nodes anyhow */
				btreeInterpretationCell = btreeInterpretationList->tail;

				/* TODO: could add support for this, if we feel like it */
				matchedOp = false;
				break;
			}

			default:
				Assert(false);
		}
	}

	if (!matchedOp)
	{
		prune->otherRestrictions =
{'fraction_non_alphanumeric': 0.09271536245609881, 'fraction_numerical': 0.0016573931573339647, 'mean_word_length': 3.828791920731707, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 258, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5317761', 'n_tokens_mistral': 17148, 'n_tokens_neox': 14569, 'n_words': 4443}