diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 8ce253c88d..9eb588e3a5 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -157,6 +157,7 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
 	int			shortlen;
 	int			longlen;
 	int			i;
+	int			start;
 
 	/* Handle cases where either input is NULL */
 	if (a == NULL)
@@ -180,7 +181,8 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
 	}
 	/* And process */
 	shortlen = shorter->nwords;
-	for (i = 0; i < shortlen; i++)
+	start = Min(a->minword, b->minword);
+	for (i = start; i < shortlen; i++)
 	{
 		if (shorter->words[i] != longer->words[i])
 			return false;
@@ -207,6 +209,7 @@ bms_compare(const Bitmapset *a, const Bitmapset *b)
 {
 	int			shortlen;
 	int			i;
+	int			start;
 
 	/* Handle cases where either input is NULL */
 	if (a == NULL)
@@ -227,7 +230,8 @@ bms_compare(const Bitmapset *a, const Bitmapset *b)
 	}
 	/* Process words in common */
 	i = shortlen;
-	while (--i >= 0)
+	start = Min(a->minword, b->minword);
+	while (--i >= start)
 	{
 		bitmapword	aw = a->words[i];
 		bitmapword	bw = b->words[i];
@@ -255,6 +259,7 @@ bms_make_singleton(int x)
 	result = (Bitmapset *) palloc0(BITMAPSET_SIZE(wordnum + 1));
 	result->nwords = wordnum + 1;
 	result->words[wordnum] = ((bitmapword) 1 << bitnum);
+	result->minword = wordnum;
 	return result;
 }
 
@@ -304,6 +309,7 @@ bms_union(const Bitmapset *a, const Bitmapset *b)
 		result = bms_copy(a);
 		other = b;
 	}
+	result->minword = Min(a->minword, b->minword);
 	/* And union the shorter input into the result */
 	otherlen = other->nwords;
 	for (i = 0; i < otherlen; i++)
@@ -337,8 +343,9 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
 		other = a;
 	}
 	/* And intersect the longer input with the result */
+	result->minword = Max(a->minword, b->minword);
 	resultlen = result->nwords;
-	for (i = 0; i < resultlen; i++)
+	for (i = result->minword; i < resultlen; i++)
 		result->words[i] &= other->words[i];
 	return result;
 }
@@ -362,7 +369,8 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
 	result = bms_copy(a);
 	/* And remove b's bits from result */
 	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
+	result->minword = Min(a->minword, b->minword);
+	for (i = result->minword; i < shortlen; i++)
 		result->words[i] &= ~b->words[i];
 	return result;
 }
@@ -497,6 +505,8 @@ bms_is_member(int x, const Bitmapset *a)
 	bitnum = BITNUM(x);
 	if (wordnum >= a->nwords)
 		return false;
+	if (wordnum < a->minword)
+		return false;
 	if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
 		return true;
 	return false;
@@ -510,13 +520,15 @@ bms_overlap(const Bitmapset *a, const Bitmapset *b)
 {
 	int			shortlen;
 	int			i;
+	int			start;
 
 	/* Handle cases where either input is NULL */
 	if (a == NULL || b == NULL)
 		return false;
 	/* Check words in common */
 	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
+	start = Min(a->minword, b->minword);
+	for (i = start; i < shortlen; i++)
 	{
 		if ((a->words[i] & b->words[i]) != 0)
 			return true;
@@ -545,7 +557,7 @@ bms_overlap_list(const Bitmapset *a, const List *b)
 			elog(ERROR, "negative bitmapset member not allowed");
 		wordnum = WORDNUM(x);
 		bitnum = BITNUM(x);
-		if (wordnum < a->nwords)
+		if ((wordnum >= a->minword) && (wordnum < a->nwords))
 			if ((a->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
 				return true;
 	}
@@ -561,6 +573,7 @@ bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
 {
 	int			shortlen;
 	int			i;
+	int			start;
 
 	/* Handle cases where either input is NULL */
 	if (a == NULL)
@@ -569,7 +582,8 @@ bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
 		return !bms_is_empty(a);
 	/* Check words in common */
 	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
+	start = Min(a->minword, b->minword);
+	for (i = start; i < shortlen; i++)
 	{
 		if ((a->words[i] & ~b->words[i]) != 0)
 			return true;
@@ -598,7 +612,7 @@ bms_singleton_member(const Bitmapset *a)
 	if (a == NULL)
 		elog(ERROR, "bitmapset is empty");
 	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
+	for (wordnum = a->minword; wordnum < nwords; wordnum++)
 	{
 		bitmapword	w = a->words[wordnum];
 
@@ -641,7 +655,7 @@ bms_get_singleton_member(const Bitmapset *a, int *member)
 	if (a == NULL)
 		return false;
 	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
+	for (wordnum = a->minword; wordnum < nwords; wordnum++)
 	{
 		bitmapword	w = a->words[wordnum];
 
@@ -677,7 +691,7 @@ bms_num_members(const Bitmapset *a)
 	if (a == NULL)
 		return 0;
 	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
+	for (wordnum = a->minword; wordnum < nwords; wordnum++)
 	{
 		bitmapword	w = a->words[wordnum];
 
@@ -734,7 +748,7 @@ bms_is_empty(const Bitmapset *a)
 	if (a == NULL)
 		return true;
 	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
+	for (wordnum = a->minword; wordnum < nwords; wordnum++)
 	{
 		bitmapword	w = a->words[wordnum];
 
@@ -773,6 +787,9 @@ bms_add_member(Bitmapset *a, int x)
 	wordnum = WORDNUM(x);
 	bitnum = BITNUM(x);
 
+	if (a->minword > wordnum)
+		a->minword = wordnum;
+
 	/* enlarge the set if necessary */
 	if (wordnum >= a->nwords)
 	{
@@ -845,6 +862,8 @@ bms_add_members(Bitmapset *a, const Bitmapset *b)
 	otherlen = other->nwords;
 	for (i = 0; i < otherlen; i++)
 		result->words[i] |= other->words[i];
+	if (result->minword > a->minword)
+		result->minword = a->minword;
 	if (result != a)
 		pfree(a);
 	return result;
@@ -898,6 +917,9 @@ bms_add_range(Bitmapset *a, int lower, int upper)
 	lbitnum = BITNUM(lower);
 	ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
 
+	if (a->minword > lwordnum)
+		a->minword = lwordnum;
+
 	/*
 	 * Special case when lwordnum is the same as uwordnum we must perform the
 	 * upper and lower masking on the word.
@@ -931,6 +953,7 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
 {
 	int			shortlen;
 	int			i;
+	int			start;
 
 	/* Handle cases where either input is NULL */
 	if (a == NULL)
@@ -942,7 +965,8 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
 	}
 	/* Intersect b into a; we need never copy */
 	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
+	start = Min(a->minword, b->minword);
+	for (i = start; i < shortlen; i++)
 		a->words[i] &= b->words[i];
 	for (; i < a->nwords; i++)
 		a->words[i] = 0;
@@ -957,6 +981,7 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
 {
 	int			shortlen;
 	int			i;
+	int			start;
 
 	/* Handle cases where either input is NULL */
 	if (a == NULL)
@@ -965,7 +990,8 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
 		return a;
 	/* Remove b's bits from a; we need never copy */
 	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
+	start = Max(a->minword, b->minword);
+	for (i = start; i < shortlen; i++)
 		a->words[i] &= ~b->words[i];
 	return a;
 }
@@ -997,9 +1023,10 @@ bms_join(Bitmapset *a, Bitmapset *b)
 		result = a;
 		other = b;
 	}
+	result->minword = Min(result->minword, other->minword);
 	/* And union the shorter input into the result */
 	otherlen = other->nwords;
-	for (i = 0; i < otherlen; i++)
+	for (i = other->minword; i < otherlen; i++)
 		result->words[i] |= other->words[i];
 	if (other != result)		/* pure paranoia */
 		pfree(other);
@@ -1029,7 +1056,7 @@ bms_first_member(Bitmapset *a)
 	if (a == NULL)
 		return -1;
 	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
+	for (wordnum = a->minword; wordnum < nwords; wordnum++)
 	{
 		bitmapword	w = a->words[wordnum];
 
@@ -1158,7 +1185,7 @@ bms_prev_member(const Bitmapset *a, int prevbit)
 
 	ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
 	mask = (~(bitmapword) 0) >> ushiftbits;
-	for (wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
+	for (wordnum = WORDNUM(prevbit); (wordnum >= 0) && (wordnum >= a->minword); wordnum--)
 	{
 		bitmapword	w = a->words[wordnum];
 
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index 433df8a46d..829290bf9b 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -48,6 +48,7 @@ typedef int32 signedbitmapword; /* must be the matching signed type */
 
 typedef struct Bitmapset
 {
+	int			minword;
 	int			nwords;			/* number of words in array */
 	bitmapword	words[FLEXIBLE_ARRAY_MEMBER];	/* really [nwords] */
 } Bitmapset;