0005-Implement-get_partitions_for_keys-v3.patch

From 5760054b91f7f115b3690432d1ee72a3db7770f3 Mon Sep 17 00:00:00 2001
From: amit <amitlangote09@gmail.com>
Date: Wed, 18 Oct 2017 17:14:53 +0900
Subject: [PATCH 5/5] Implement get_partitions_for_keys

Disable constraint_exclusion using internal partition constraints.
---
 src/backend/catalog/partition.c         | 356 +++++++++++++++++++++++++++++++-
 src/test/regress/expected/inherit.out   |   4 +-
 src/test/regress/expected/partition.out |  64 ++----
 3 files changed, 371 insertions(+), 53 deletions(-)

diff --git a/src/backend/catalog/partition.c b/src/backend/catalog/partition.c
index 73f4e7ab95..c5875dc064 100644
--- a/src/backend/catalog/partition.c
+++ b/src/backend/catalog/partition.c
@@ -178,7 +178,7 @@ typedef struct PartitionScanKeyInfo
 typedef struct PartitionSet
 {
 	/*
-	 * If either  empty or all_parts is true, values of the other fields are
+	 * If either  empty or all is true, values of the other fields are
 	 * invalid.
 	 */
 	bool	empty;				/* contains no partitions */
@@ -1121,7 +1121,7 @@ check_default_allows_bound(Relation parent, Relation default_rel,
 {
 	List	   *new_part_constraints;
 	List	   *def_part_constraints;
-	List	   *all_parts;
+	List	   *all;
 	ListCell   *lc;
 
 	new_part_constraints = (new_spec->strategy == PARTITION_STRATEGY_LIST)
@@ -1148,12 +1148,12 @@ check_default_allows_bound(Relation parent, Relation default_rel,
 	 * that do not satisfy the revised partition constraints.
 	 */
 	if (default_rel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
-		all_parts = find_all_inheritors(RelationGetRelid(default_rel),
+		all = find_all_inheritors(RelationGetRelid(default_rel),
 										AccessExclusiveLock, NULL);
 	else
-		all_parts = list_make1_oid(RelationGetRelid(default_rel));
+		all = list_make1_oid(RelationGetRelid(default_rel));
 
-	foreach(lc, all_parts)
+	foreach(lc, all)
 	{
 		Oid			part_relid = lfirst_oid(lc);
 		Relation	part_rel;
@@ -2507,7 +2507,351 @@ partition_cmp_args(Oid partopfamily, Oid partopcintype,
 static PartitionSet *
 get_partitions_for_keys(Relation rel, PartitionScanKeyInfo *keys)
 {
-	return partset_new(false, true);
+	PartitionSet   *partset;
+	int		i,
+			eqoff = -1,
+			minoff = -1,
+			maxoff = -1;
+	PartitionKey	partkey = RelationGetPartitionKey(rel);
+	PartitionDesc	partdesc = RelationGetPartitionDesc(rel);
+	PartitionBoundInfo	boundinfo = partdesc->boundinfo;
+	PartitionBoundCmpArg	arg;
+	bool	is_equal;
+
+	/* Return an empty set if no partitions to see. */
+	if (partdesc->nparts == 0)
+		return partset_new(true, false);
+
+	/*
+	 * Initialize the set as one that's neither empty nor contains all
+	 * partitions.  The code below will set min_part_idx and max_part_idx
+	 * and/or other_parts as found out by comparing keys to the partition
+	 * bounds, as well as considering special partitions like null-accepting
+	 * and default partitions.  If it turns out that no partitions need to
+	 * be scanned, partset->empty will be set to true.
+	 */
+	partset = partset_new(false, false);
+
+	/*
+	 * Check if any of the scan keys are null.  If so, return the only
+	 * null-accepting partition if boundinfo says there is one.
+	 */
+	for (i = 0; i < partkey->partnatts; i++)
+	{
+		if (keys->keynullness[i] == IS_NULL)
+		{
+			int		other_idx = -1;
+
+			/*
+			 * Note that only one of the null-accepting partition and the
+			 * default partition can be holding null values at any given
+			 * time.
+			 */
+			if (partition_bound_accepts_nulls(boundinfo)||
+				partition_bound_has_default(boundinfo))
+				other_idx = partition_bound_accepts_nulls(boundinfo)
+								? boundinfo->null_index
+								: boundinfo->default_index;
+			if (other_idx >= 0)
+				partset->other_parts = bms_make_singleton(other_idx);
+
+			return partset;
+		}
+	}
+
+	/*
+	 * If there are no datums to compare keys with, but there exists a
+	 * partition, the latter must be a partition that accepts only nulls
+	 * or a default partition.  If it is the former and we didn't already
+	 * return it as the only scannable partition, that means the query
+	 * doesn't want null values in its outout.  So, all of what the query
+	 * wants instead must be in the default partition.
+	 */
+	if (boundinfo->ndatums == 0)
+	{
+		if (partition_bound_has_default(boundinfo))
+			partset->other_parts =
+							bms_make_singleton(boundinfo->default_index);
+		else
+			partset->empty = true;
+		return partset;
+	}
+	/* No bounding keys, so just return all partitions. */
+	else if (keys->n_eqkeys + keys->n_minkeys + keys->n_maxkeys == 0)
+	{
+		partset->all_parts = true;
+		return partset;
+	}
+
+	/* Valid keys->eqkeys must provoide all partition keys. */
+	Assert(keys->n_eqkeys == 0 || keys->n_eqkeys == partkey->partnatts);
+	eqoff = -1;
+	if (keys->n_eqkeys > 0)
+	{
+		memset(&arg, 0, sizeof(PartitionBoundCmpArg));
+		arg.datums = keys->eqkeys;
+		arg.ndatums = keys->n_eqkeys;
+		eqoff = partition_bound_bsearch(partkey, boundinfo, &arg, &is_equal);
+
+		if (eqoff >= 0)
+		{
+			switch (partkey->strategy)
+			{
+				case PARTITION_STRATEGY_LIST:
+					/* For list partition, must exactly match the datum. */
+					if (!is_equal)
+						eqoff = -1;
+					break;
+
+				case PARTITION_STRATEGY_RANGE:
+					/*
+					 * eqoff is gives us the bound that is known to be <=
+					 * eqkeys given how partition_bound_bsearch works.  The
+					 * bound at eqoff + 1, then, would be the upper bound of
+					 * the only partition that needs to be scanned.
+					 */
+					if (partkey->strategy == PARTITION_STRATEGY_RANGE)
+						eqoff += 1;
+			}
+		}
+
+		/*
+		 * Ask later code to include the default partition, because eqkeys
+		 * didn't identify a specific partition or identified a range
+		 * of unassigned values.
+		 */
+		if (eqoff >= 0 && boundinfo->indexes[eqoff] >= 0)
+			partset->other_parts =
+							bms_make_singleton(boundinfo->indexes[eqoff]);
+		else if (partition_bound_has_default(boundinfo))
+			partset->other_parts =
+							bms_make_singleton(boundinfo->default_index);
+		else
+			partset->empty = true;
+
+		/* There are no minkeys and maxkeys when eqkeys is valid. */
+		return partset;
+	}
+
+	/*
+	 * Find the leftmost bound that satisfies the query, i.e., one that
+	 * satisfies minkeys.
+	 */
+	minoff = 0;
+	if (keys->n_minkeys > 0)
+	{
+		memset(&arg, 0, sizeof(PartitionBoundCmpArg));
+		arg.datums = keys->minkeys;
+		arg.ndatums = keys->n_minkeys;
+		minoff = partition_bound_bsearch(partkey, boundinfo, &arg, &is_equal);
+
+		switch (partkey->strategy)
+		{
+			case PARTITION_STRATEGY_LIST:
+				/*
+				 * minkeys matched one of the datums (because, is_equal), but
+				 * the query may have asked to exclude that value.  If so,
+				 * move to the bound on the right, which doesn't necessarily
+				 * mean we're excluding the list partition containing that
+				 * value, because there very well might be values in the range
+				 * thus selected that belong to the partition to which the
+				 * matched value (minkeys) also belongs.
+				 */
+				if (is_equal && !keys->min_incl)
+					minoff++;
+				break;
+
+			case PARTITION_STRATEGY_RANGE:
+				/*
+				 * If only a prefix of the whole partition key is provided,
+				 * there will be multiple partitions whose bound share the
+				 * same prefix.  If minkey is inclusive, we must make minoff
+				 * point to the leftmost such bound, making the result contain
+				 * all such partitions.  If it is exclusive, we must move
+				 * minoff to the right such that minoff points to the first
+				 * partition whose bound is greater than this prefix, thus
+				 * excluding all aforementioned partitions from appearing in
+				 * the result.
+				 */
+				if (is_equal && arg.ndatums < partkey->partnatts)
+				{
+					int32	cmpval;
+
+					is_equal = false;
+					do
+					{
+						if (keys->min_incl)
+							minoff -= 1;
+						else
+							minoff += 1;
+						if (minoff < 0 || minoff >= boundinfo->ndatums)
+							break;
+						cmpval = partition_bound_cmp(partkey, boundinfo,
+													 minoff, &arg);
+					} while (cmpval == 0);
+
+					/* Back up if went too far. */
+					if (!keys->min_incl)
+						minoff -= 1;
+				}
+
+				/*
+				 * At this point, minoff gives us the leftmost bound that is
+				 * known to be <= query's minkey.  The bound at minoff + 1,
+				 * then, would be the upper bound of the leftmost partition
+				 * that needs to be scanned.
+				 */
+				minoff += 1;
+				break;
+		}
+	}
+
+	/*
+	 * Find the rightmost bound that satisfies the query, i.e., one that
+	 * satisfies maxkeys.
+	 */
+	maxoff = boundinfo->ndatums - 1;
+	if (keys->n_maxkeys > 0)
+	{
+		memset(&arg, 0, sizeof(PartitionBoundCmpArg));
+		arg.datums = keys->maxkeys;
+		arg.ndatums = keys->n_maxkeys;
+		maxoff = partition_bound_bsearch(partkey, boundinfo, &arg, &is_equal);
+
+		switch (partkey->strategy)
+		{
+			case PARTITION_STRATEGY_LIST:
+				/* See the comment above for minkeys. */
+				if (is_equal && !keys->max_incl)
+					maxoff--;
+				break;
+
+			case PARTITION_STRATEGY_RANGE:
+				/* See the comment above for minkeys. */
+				if (is_equal && arg.ndatums < partkey->partnatts)
+				{
+					int32	cmpval;
+
+					is_equal = false;
+					do
+					{
+						if (keys->max_incl)
+							maxoff += 1;
+						else
+							maxoff -= 1;
+						if (maxoff < 0 || maxoff >= boundinfo->ndatums)
+							break;
+						cmpval = partition_bound_cmp(partkey, boundinfo,
+													 maxoff, &arg);
+					} while (cmpval == 0);
+
+					/* Back up if went too far. */
+					if (keys->max_incl)
+						maxoff -= 1;
+				}
+
+				/*
+				 * At this point, maxoff gives us the rightmost bound that is
+				 * known to be <= query's maxkey.  The bound at maxoff + 1,
+				 * then, would be the upper bound of the rightmost partition
+				 * that needs to be scanned.  Although, if the bound is equal
+				 * to maxkeys and the latter is not inclusive, then the bound
+				 * itself is the upper bound of the rightmost partition that
+				 * needs to be scanned.
+				 */
+				if (!is_equal || keys->max_incl)
+					maxoff += 1;
+
+				break;
+		}
+	}
+
+	if (minoff >= 0 && maxoff >= 0)
+	{
+		bool	include_default = false;
+
+		/*
+		 * If the bound at minoff or maxoff looks like it's an upper bound of a
+		 * range of values unassigned to any partition, move to the adjacent
+		 * bound which instead must be the upper bound of the leftmost or
+		 * rightmost partition, respectively, that needs to be scanned.
+		 *
+		 * By doing that, we skip over a portion of values that do indeed
+		 * satisfy the query, but don't have a valid partition assigned.
+		 * Include the default partition in that case.  Although, if the
+		 * original bound in question is an infinite value, there would not
+		 * be any unassigned range, because the range is unbounded in that
+		 * direction by definition.
+		 */
+		if (boundinfo->indexes[minoff] < 0)
+		{
+			int		last_key;
+
+			Assert(partkey->strategy == PARTITION_STRATEGY_RANGE);
+			last_key = keys->n_minkeys > 0 ? keys->n_minkeys - 1
+										   : partkey->partnatts - 1;
+			if (boundinfo->kind[minoff][last_key] == PARTITION_RANGE_DATUM_VALUE)
+				include_default = true;
+			minoff += 1;
+		}
+
+		if (maxoff >= 1 && boundinfo->indexes[maxoff] < 0)
+		{
+			int		last_key;
+
+			Assert(partkey->strategy == PARTITION_STRATEGY_RANGE);
+			last_key = keys->n_maxkeys > 0 ? keys->n_maxkeys - 1
+										   : partkey->partnatts - 1;
+			maxoff -= 1;
+			if (boundinfo->kind[maxoff][last_key] == PARTITION_RANGE_DATUM_VALUE)
+				include_default = true;
+		}
+
+		switch (partkey->strategy)
+		{
+			case PARTITION_STRATEGY_LIST:
+				/*
+				 * Add to the other_parts, list partition indexes are not
+				 * monotonously increasing like range partitions' are.
+				 */
+				for (i = minoff; i <= maxoff; i++)
+					partset->other_parts =
+								bms_add_member(partset->other_parts,
+											   boundinfo->indexes[i]);
+				/*
+				 * If minoff != maxoff, there might be datums in that range
+				 * range that don't have a non-default partition assigned.
+				 */
+				include_default = (minoff != maxoff);
+				break;
+
+			case PARTITION_STRATEGY_RANGE:
+				partset->min_part_idx = boundinfo->indexes[minoff];
+				partset->max_part_idx = boundinfo->indexes[maxoff];
+				/*
+				 * There might exist a range of values unassigned to any
+				 * non-default range partition between the datums at
+				 * minoff and maxoff.
+				 */
+				for (i = minoff; i <= maxoff; i++)
+				{
+					if (boundinfo->indexes[i] < 0)
+					{
+						include_default = true;
+						break;
+					}
+				}
+				break;
+		}
+
+		if (include_default && partition_bound_has_default(boundinfo))
+			partset->other_parts = bms_add_member(partset->other_parts,
+												  boundinfo->default_index);
+	}
+	else
+		partset->empty = true;
+
+	return partset;
 }
 
 /*
diff --git a/src/test/regress/expected/inherit.out b/src/test/regress/expected/inherit.out
index c698faff2f..661f137122 100644
--- a/src/test/regress/expected/inherit.out
+++ b/src/test/regress/expected/inherit.out
@@ -1713,11 +1713,9 @@ explain (costs off) select * from list_parted where a = 'ab' or a in (null, 'cd'
  Append
    ->  Seq Scan on part_ab_cd
          Filter: (((a)::text = 'ab'::text) OR ((a)::text = ANY ('{NULL,cd}'::text[])))
-   ->  Seq Scan on part_ef_gh
-         Filter: (((a)::text = 'ab'::text) OR ((a)::text = ANY ('{NULL,cd}'::text[])))
    ->  Seq Scan on part_null_xy
          Filter: (((a)::text = 'ab'::text) OR ((a)::text = ANY ('{NULL,cd}'::text[])))
-(7 rows)
+(5 rows)
 
 explain (costs off) select * from list_parted where a = 'ab';
                 QUERY PLAN                
diff --git a/src/test/regress/expected/partition.out b/src/test/regress/expected/partition.out
index 61c4596bc7..69a7819171 100644
--- a/src/test/regress/expected/partition.out
+++ b/src/test/regress/expected/partition.out
@@ -198,16 +198,14 @@ explain (costs off) select * from rlp where 1 > a;	/* commutates */
 (3 rows)
 
 explain (costs off) select * from rlp where a <= 1;
-          QUERY PLAN           
--------------------------------
+        QUERY PLAN        
+--------------------------
  Append
    ->  Seq Scan on rlp1
          Filter: (a <= 1)
    ->  Seq Scan on rlp2
          Filter: (a <= 1)
-   ->  Seq Scan on rlp_default
-         Filter: (a <= 1)
-(7 rows)
+(5 rows)
 
 explain (costs off) select * from rlp where a = 1;
        QUERY PLAN        
@@ -453,15 +451,13 @@ explain (costs off) select * from rlp where (a = 1 and a = 3) or (a > 1 and a =
                             QUERY PLAN                             
 -------------------------------------------------------------------
  Append
-   ->  Seq Scan on rlp2
-         Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
    ->  Seq Scan on rlp3abcd
          Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
    ->  Seq Scan on rlp3efgh
          Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
    ->  Seq Scan on rlp3nullxy
          Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
-(9 rows)
+(7 rows)
 
 -- multi-column keys
 create table mc3p (a int, b int, c int) partition by range (a, abs(b), c);
@@ -475,16 +471,14 @@ create table mc3p5 partition of mc3p for values from (11, 1, 1) to (20, 10, 10);
 create table mc3p6 partition of mc3p for values from (20, 10, 10) to (20, 20, 20);
 create table mc3p7 partition of mc3p for values from (20, 20, 20) to (maxvalue, maxvalue, maxvalue);
 explain (costs off) select * from mc3p where a = 1;
-           QUERY PLAN           
---------------------------------
+       QUERY PLAN        
+-------------------------
  Append
    ->  Seq Scan on mc3p0
          Filter: (a = 1)
    ->  Seq Scan on mc3p1
          Filter: (a = 1)
-   ->  Seq Scan on mc3p_default
-         Filter: (a = 1)
-(7 rows)
+(5 rows)
 
 explain (costs off) select * from mc3p where a = 1 and abs(b) < 1;
                  QUERY PLAN                 
@@ -502,9 +496,7 @@ explain (costs off) select * from mc3p where a = 1 and abs(b) = 1;
          Filter: ((a = 1) AND (abs(b) = 1))
    ->  Seq Scan on mc3p1
          Filter: ((a = 1) AND (abs(b) = 1))
-   ->  Seq Scan on mc3p_default
-         Filter: ((a = 1) AND (abs(b) = 1))
-(7 rows)
+(5 rows)
 
 explain (costs off) select * from mc3p where a = 1 and abs(b) = 1 and c < 8;
                        QUERY PLAN                       
@@ -514,9 +506,7 @@ explain (costs off) select * from mc3p where a = 1 and abs(b) = 1 and c < 8;
          Filter: ((c < 8) AND (a = 1) AND (abs(b) = 1))
    ->  Seq Scan on mc3p1
          Filter: ((c < 8) AND (a = 1) AND (abs(b) = 1))
-   ->  Seq Scan on mc3p_default
-         Filter: ((c < 8) AND (a = 1) AND (abs(b) = 1))
-(7 rows)
+(5 rows)
 
 explain (costs off) select * from mc3p where a = 10 and abs(b) between 5 and 35;
                            QUERY PLAN                            
@@ -530,9 +520,7 @@ explain (costs off) select * from mc3p where a = 10 and abs(b) between 5 and 35;
          Filter: ((a = 10) AND (abs(b) >= 5) AND (abs(b) <= 35))
    ->  Seq Scan on mc3p4
          Filter: ((a = 10) AND (abs(b) >= 5) AND (abs(b) <= 35))
-   ->  Seq Scan on mc3p_default
-         Filter: ((a = 10) AND (abs(b) >= 5) AND (abs(b) <= 35))
-(11 rows)
+(9 rows)
 
 explain (costs off) select * from mc3p where a > 10;
            QUERY PLAN           
@@ -571,16 +559,14 @@ explain (costs off) select * from mc3p where a >= 10;
 (17 rows)
 
 explain (costs off) select * from mc3p where a < 10;
-           QUERY PLAN           
---------------------------------
+        QUERY PLAN        
+--------------------------
  Append
    ->  Seq Scan on mc3p0
          Filter: (a < 10)
    ->  Seq Scan on mc3p1
          Filter: (a < 10)
-   ->  Seq Scan on mc3p_default
-         Filter: (a < 10)
-(7 rows)
+(5 rows)
 
 explain (costs off) select * from mc3p where a <= 10 and abs(b) < 10;
                   QUERY PLAN                   
@@ -592,9 +578,7 @@ explain (costs off) select * from mc3p where a <= 10 and abs(b) < 10;
          Filter: ((a <= 10) AND (abs(b) < 10))
    ->  Seq Scan on mc3p2
          Filter: ((a <= 10) AND (abs(b) < 10))
-   ->  Seq Scan on mc3p_default
-         Filter: ((a <= 10) AND (abs(b) < 10))
-(9 rows)
+(7 rows)
 
 explain (costs off) select * from mc3p where a = 11 and abs(b) = 0;	/* empty */
                  QUERY PLAN                  
@@ -621,8 +605,8 @@ explain (costs off) select * from mc3p where a > 20;
 (3 rows)
 
 explain (costs off) select * from mc3p where a >= 20;
-           QUERY PLAN           
---------------------------------
+        QUERY PLAN         
+---------------------------
  Append
    ->  Seq Scan on mc3p5
          Filter: (a >= 20)
@@ -630,9 +614,7 @@ explain (costs off) select * from mc3p where a >= 20;
          Filter: (a >= 20)
    ->  Seq Scan on mc3p7
          Filter: (a >= 20)
-   ->  Seq Scan on mc3p_default
-         Filter: (a >= 20)
-(9 rows)
+(7 rows)
 
 explain (costs off) select * from mc3p where (a = 1 and abs(b) = 1 and c = 1) or (a = 10 and abs(b) = 5 and c = 10) or (a > 11 and a < 20);
                                                            QUERY PLAN                                                            
@@ -672,9 +654,7 @@ explain (costs off) select * from mc3p where (a = 1 and abs(b) = 1 and c = 1) or
          Filter: (((a = 1) AND (abs(b) = 1) AND (c = 1)) OR ((a = 10) AND (abs(b) = 5) AND (c = 10)) OR ((a > 11) AND (a < 20)) OR (a < 1) OR (a = 1))
    ->  Seq Scan on mc3p5
          Filter: (((a = 1) AND (abs(b) = 1) AND (c = 1)) OR ((a = 10) AND (abs(b) = 5) AND (c = 10)) OR ((a > 11) AND (a < 20)) OR (a < 1) OR (a = 1))
-   ->  Seq Scan on mc3p_default
-         Filter: (((a = 1) AND (abs(b) = 1) AND (c = 1)) OR ((a = 10) AND (abs(b) = 5) AND (c = 10)) OR ((a > 11) AND (a < 20)) OR (a < 1) OR (a = 1))
-(11 rows)
+(9 rows)
 
 explain (costs off) select * from mc3p where a = 1 or abs(b) = 1 or c = 1;
                       QUERY PLAN                      
@@ -712,9 +692,7 @@ explain (costs off) select * from mc3p where (a = 1 and abs(b) = 1) or (a = 10 a
          Filter: (((a = 1) AND (abs(b) = 1)) OR ((a = 10) AND (abs(b) = 10)))
    ->  Seq Scan on mc3p4
          Filter: (((a = 1) AND (abs(b) = 1)) OR ((a = 10) AND (abs(b) = 10)))
-   ->  Seq Scan on mc3p_default
-         Filter: (((a = 1) AND (abs(b) = 1)) OR ((a = 10) AND (abs(b) = 10)))
-(13 rows)
+(11 rows)
 
 explain (costs off) select * from mc3p where (a = 1 and abs(b) = 1) or (a = 10 and abs(b) = 9);
                                  QUERY PLAN                                  
@@ -726,8 +704,6 @@ explain (costs off) select * from mc3p where (a = 1 and abs(b) = 1) or (a = 10 a
          Filter: (((a = 1) AND (abs(b) = 1)) OR ((a = 10) AND (abs(b) = 9)))
    ->  Seq Scan on mc3p2
          Filter: (((a = 1) AND (abs(b) = 1)) OR ((a = 10) AND (abs(b) = 9)))
-   ->  Seq Scan on mc3p_default
-         Filter: (((a = 1) AND (abs(b) = 1)) OR ((a = 10) AND (abs(b) = 9)))
-(9 rows)
+(7 rows)
 
 drop table lp, coll_pruning, rlp, mc3p;
-- 
2.11.0