1 files changed, 81 insertions, 24 deletions

diff --git a/src/backend/partitioning/partbounds.c b/src/backend/partitioning/partbounds.c
index 25018b1a8b7..fdfe712f917 100644
--- a/src/backend/partitioning/partbounds.c
+++ b/src/backend/partitioning/partbounds.c
@@ -395,6 +395,7 @@ create_hash_bounds(PartitionBoundSpec **boundspecs, int nparts,
 	boundinfo->ndatums = nparts;
 	boundinfo->datums = (Datum **) palloc0(nparts * sizeof(Datum *));
 	boundinfo->kind = NULL;
+	boundinfo->interleaved_parts = NULL;
 	boundinfo->nindexes = greatest_modulus;
 	boundinfo->indexes = (int *) palloc(greatest_modulus * sizeof(int));
 	for (i = 0; i < greatest_modulus; i++)
@@ -543,6 +544,7 @@ create_list_bounds(PartitionBoundSpec **boundspecs, int nparts,
 	boundinfo->ndatums = ndatums;
 	boundinfo->datums = (Datum **) palloc0(ndatums * sizeof(Datum *));
 	boundinfo->kind = NULL;
+	boundinfo->interleaved_parts = NULL;
 	boundinfo->nindexes = ndatums;
 	boundinfo->indexes = (int *) palloc(ndatums * sizeof(int));
 
@@ -607,6 +609,69 @@ create_list_bounds(PartitionBoundSpec **boundspecs, int nparts,
 		boundinfo->default_index = (*mapping)[default_index];
 	}
 
+	/*
+	 * Calculate interleaved partitions.  Here we look for partitions which
+	 * might be interleaved with other partitions and set a bit in
+	 * interleaved_parts for any partitions which may be interleaved with
+	 * another partition.
+	 */
+
+	/*
+	 * There must be multiple partitions to have any interleaved partitions,
+	 * otherwise there's nothing to interleave with.
+	 */
+	if (nparts > 1)
+	{
+		/*
+		 * Short-circuit check to see if only 1 Datum is allowed per
+		 * partition.  When this is true there's no need to do the more
+		 * expensive checks to look for interleaved values.
+		 */
+		if (boundinfo->ndatums +
+			partition_bound_accepts_nulls(boundinfo) +
+			partition_bound_has_default(boundinfo) != nparts)
+		{
+			int			last_index = -1;
+
+			/*
+			 * Since the indexes array is sorted in Datum order, if any
+			 * partitions are interleaved then it will show up by the
+			 * partition indexes not being in ascending order.  Here we check
+			 * for that and record all partitions that are out of order.
+			 */
+			for (i = 0; i < boundinfo->nindexes; i++)
+			{
+				int			index = boundinfo->indexes[i];
+
+				if (index < last_index)
+					boundinfo->interleaved_parts = bms_add_member(boundinfo->interleaved_parts,
+																  index);
+
+				/*
+				 * Mark the NULL partition as interleaved if we find that it
+				 * allows some other non-NULL Datum.
+				 */
+				if (partition_bound_accepts_nulls(boundinfo) &&
+					index == boundinfo->null_index)
+					boundinfo->interleaved_parts = bms_add_member(boundinfo->interleaved_parts,
+																  boundinfo->null_index);
+
+				last_index = index;
+			}
+		}
+
+		/*
+		 * The DEFAULT partition is the "catch-all" partition that can contain
+		 * anything that does not belong to any other partition.  If there are
+		 * any other partitions then the DEFAULT partition must be marked as
+		 * interleaved.
+		 */
+		if (partition_bound_has_default(boundinfo))
+			boundinfo->interleaved_parts = bms_add_member(boundinfo->interleaved_parts,
+														  boundinfo->default_index);
+	}
+
+
 	/* All partitions must now have been assigned canonical indexes. */
 	Assert(next_index == nparts);
 	return boundinfo;
@@ -750,6 +815,7 @@ create_range_bounds(PartitionBoundSpec **boundspecs, int nparts,
 	boundinfo->kind = (PartitionRangeDatumKind **)
 		palloc(ndatums *
 			   sizeof(PartitionRangeDatumKind *));
+	boundinfo->interleaved_parts = NULL;
 
 	/*
 	 * For range partitioning, an additional value of -1 is stored as the last
@@ -993,6 +1059,9 @@ partition_bounds_copy(PartitionBoundInfo src,
 	else
 		dest->kind = NULL;
 
+	/* copy interleaved partitions for LIST partitioned tables */
+	dest->interleaved_parts = bms_copy(src->interleaved_parts);
+
 	/*
 	 * For hash partitioning, datums array will have two elements - modulus
 	 * and remainder.
@@ -2780,13 +2849,15 @@ add_merged_range_bounds(int partnatts, FmgrInfo *partsupfuncs,
  *		that is partitions appearing earlier in the PartitionDesc sequence
  *		contain partition keys strictly less than those appearing later.
  *		Also, if NULL values are possible, they must come in the last
- *		partition defined in the PartitionDesc.
+ *		partition defined in the PartitionDesc.  'live_parts' marks which
+ *		partitions we should include when checking the ordering.  Partitions
+ *		that do not appear in 'live_parts' are ignored.
  *
  * If out of order, or there is insufficient info to know the order,
  * then we return false.
  */
 bool
-partitions_are_ordered(PartitionBoundInfo boundinfo, int nparts)
+partitions_are_ordered(PartitionBoundInfo boundinfo, Bitmapset *live_parts)
 {
 	Assert(boundinfo != NULL);
 
@@ -2798,38 +2869,24 @@ partitions_are_ordered(PartitionBoundInfo boundinfo, int nparts)
 			 * RANGE-type partitioning guarantees that the partitions can be
 			 * scanned in the order that they're defined in the PartitionDesc
 			 * to provide sequential, non-overlapping ranges of tuples.
-			 * However, if a DEFAULT partition exists then it doesn't work, as
-			 * that could contain tuples from either below or above the
-			 * defined range, or tuples belonging to gaps between partitions.
+			 * However, if a DEFAULT partition exists and it's contained
+			 * within live_parts, then the partitions are not ordered.
 			 */
-			if (!partition_bound_has_default(boundinfo))
+			if (!partition_bound_has_default(boundinfo) ||
+				!bms_is_member(boundinfo->default_index, live_parts))
 				return true;
 			break;
 
 		case PARTITION_STRATEGY_LIST:
 
 			/*
-			 * LIST partitioning can also guarantee ordering, but only if the
-			 * partitions don't accept interleaved values.  We could likely
-			 * check for this by looping over the PartitionBound's indexes
-			 * array to check that the indexes are in order.  For now, let's
-			 * just keep it simple and just accept LIST partitioning when
-			 * there's no DEFAULT partition, exactly one value per partition,
-			 * and optionally a NULL partition that does not accept any other
-			 * values.  Such a NULL partition will come last in the
-			 * PartitionDesc, and the other partitions will be properly
-			 * ordered.  This is a cheap test to make as it does not require
-			 * any per-partition processing.  Maybe we'd like to handle more
-			 * complex cases in the future.
+			 * LIST partitioned are ordered providing none of live_parts
+			 * overlap with the partitioned table's interleaved partitions.
 			 */
-			if (partition_bound_has_default(boundinfo))
-				return false;
-
-			if (boundinfo->ndatums + partition_bound_accepts_nulls(boundinfo)
-				== nparts)
+			if (!bms_overlap(live_parts, boundinfo->interleaved_parts))
 				return true;
-			break;
 
+			break;
 		default:
 			/* HASH, or some other strategy */
 			break;