Speeding Up Bitmapset

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 7ba3cf635b..2e8258140c 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -5,8 +5,16 @@
  *
  * A bitmap set can represent any set of nonnegative integers, although
  * it is mainly intended for sets where the maximum value is not large,
- * say at most a few hundred.  By convention, we always represent the
- * empty set by a NULL pointer.
+ * say at most a few hundred.  By convention, we always represent a set with
+ * the minimum possible number of words, i.e, there are never any trailing
+ * zero words. Enforcing this requires that an empty set is represented as
+ * NULL. Because an empty Bitmapset is represented as NULL, a non-NULL
+ * Bitmapset always has at least 1 Bitmapword. We can exploit this fact to
+ * speedup various loops over the Bitmapset's words array by using "do while"
+ * loops instead of "for" loops. This means the code does not waste time
+ * checking the loop condition before the first iteration. For Bitmapsets
+ * containing only a single word (likely the majority of them) this reduces
+ * the loop condition tests by half.
  *
  *
  * Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -64,8 +72,6 @@
 #error "invalid BITS_PER_BITMAPWORD"
 #endif
 
-static bool bms_is_empty_internal(const Bitmapset *a);
-
 
 /*
  * bms_copy - make a palloc'd copy of a bitmapset
@@ -85,18 +91,11 @@ bms_copy(const Bitmapset *a)
 }
 
 /*
- * bms_equal - are two bitmapsets equal?
- *
- * This is logical not physical equality; in particular, a NULL pointer will
- * be reported as equal to a palloc'd value containing no members.
+ * bms_equal - are two bitmapsets equal? or both NULL?
  */
 bool
 bms_equal(const Bitmapset *a, const Bitmapset *b)
 {
-	const Bitmapset *shorter;
-	const Bitmapset *longer;
-	int			shortlen;
-	int			longlen;
 	int			i;
 
 	/* Handle cases where either input is NULL */
@@ -108,30 +107,19 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
 	}
 	else if (b == NULL)
 		return false;
-	/* Identify shorter and longer input */
-	if (a->nwords <= b->nwords)
-	{
-		shorter = a;
-		longer = b;
-	}
-	else
-	{
-		shorter = b;
-		longer = a;
-	}
-	/* And process */
-	shortlen = shorter->nwords;
-	for (i = 0; i < shortlen; i++)
-	{
-		if (shorter->words[i] != longer->words[i])
-			return false;
-	}
-	longlen = longer->nwords;
-	for (; i < longlen; i++)
+
+	/* can't be equal if the word counts don't match */
+	if (a->nwords != b->nwords)
+		return false;
+
+	/* check each word matches */
+	i = a->nwords - 1;
+	do
 	{
-		if (longer->words[i] != 0)
+		if (a->words[i] != b->words[i])
 			return false;
-	}
+	} while (--i >= 0);
+
 	return true;
 }
 
@@ -146,7 +134,6 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
 int
 bms_compare(const Bitmapset *a, const Bitmapset *b)
 {
-	int			shortlen;
 	int			i;
 
 	/* Handle cases where either input is NULL */
@@ -154,28 +141,21 @@ bms_compare(const Bitmapset *a, const Bitmapset *b)
 		return (b == NULL) ? 0 : -1;
 	else if (b == NULL)
 		return +1;
-	/* Handle cases where one input is longer than the other */
-	shortlen = Min(a->nwords, b->nwords);
-	for (i = shortlen; i < a->nwords; i++)
-	{
-		if (a->words[i] != 0)
-			return +1;
-	}
-	for (i = shortlen; i < b->nwords; i++)
-	{
-		if (b->words[i] != 0)
-			return -1;
-	}
-	/* Process words in common */
-	i = shortlen;
-	while (--i >= 0)
+
+	/* the set with the most words must be greater */
+	if (a->nwords != b->nwords)
+		return (a->nwords - b->nwords);
+
+	i = a->nwords - 1;
+	do
 	{
 		bitmapword	aw = a->words[i];
 		bitmapword	bw = b->words[i];
 
 		if (aw != bw)
-			return (aw > bw) ? +1 : -1;
-	}
+			return (aw - bw);
+	} while (--i >= 0);
+
 	return 0;
 }
 
@@ -227,7 +207,6 @@ bms_union(const Bitmapset *a, const Bitmapset *b)
 {
 	Bitmapset  *result;
 	const Bitmapset *other;
-	int			otherlen;
 	int			i;
 
 	/* Handle cases where either input is NULL */
@@ -235,6 +214,7 @@ bms_union(const Bitmapset *a, const Bitmapset *b)
 		return bms_copy(b);
 	if (b == NULL)
 		return bms_copy(a);
+
 	/* Identify shorter and longer input; copy the longer one */
 	if (a->nwords <= b->nwords)
 	{
@@ -246,10 +226,14 @@ bms_union(const Bitmapset *a, const Bitmapset *b)
 		result = bms_copy(a);
 		other = b;
 	}
+
 	/* And union the shorter input into the result */
-	otherlen = other->nwords;
-	for (i = 0; i < otherlen; i++)
+	i = other->nwords - 1;
+	do
+	{
 		result->words[i] |= other->words[i];
+	} while (--i >= 0);
+
 	return result;
 }
 
@@ -261,12 +245,13 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
 {
 	Bitmapset  *result;
 	const Bitmapset *other;
-	int			resultlen;
+	int			lastnonzero;
 	int			i;
 
 	/* Handle cases where either input is NULL */
 	if (a == NULL || b == NULL)
 		return NULL;
+
 	/* Identify shorter and longer input; copy the shorter one */
 	if (a->nwords <= b->nwords)
 	{
@@ -278,16 +263,27 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
 		result = bms_copy(b);
 		other = a;
 	}
+
 	/* And intersect the longer input with the result */
-	resultlen = result->nwords;
-	for (i = 0; i < resultlen; i++)
+	lastnonzero = -1;
+	i = result->nwords - 1;
+	do
+	{
 		result->words[i] &= other->words[i];
+
+		if (lastnonzero == -1 && result->words[i])
+			lastnonzero = i;
+	} while (--i >= 0);
+
 	/* If we computed an empty result, we must return NULL */
-	if (bms_is_empty_internal(result))
+	if (lastnonzero == -1)
 	{
 		pfree(result);
 		return NULL;
 	}
+
+	/* get rid of trailing zero words */
+	result->nwords = lastnonzero + 1;
 	return result;
 }
 
@@ -298,7 +294,6 @@ Bitmapset *
 bms_difference(const Bitmapset *a, const Bitmapset *b)
 {
 	Bitmapset  *result;
-	int			shortlen;
 	int			i;
 
 	/* Handle cases where either input is NULL */
@@ -317,10 +312,40 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
 
 	/* Copy the left input */
 	result = bms_copy(a);
+
 	/* And remove b's bits from result */
-	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
-		result->words[i] &= ~b->words[i];
+	if (result->nwords > b->nwords)
+	{
+		/*
+		 * We'll never need to remove trailing zero words when 'a' has more
+		 * words than 'b' as the additional words must be non-zero.
+		 */
+		i = b->nwords - 1;
+		do
+		{
+			result->words[i] &= ~b->words[i];
+		} while (--i >= 0);
+	}
+	else
+	{
+		int			lastnonzero = -1;
+
+		/* we may need to remove trailing zero words from the result. */
+		i = result->nwords - 1;
+		do
+		{
+			result->words[i] &= ~b->words[i];
+
+			/* remember the last non-zero word */
+			if (lastnonzero == -1 && result->words[i])
+				lastnonzero = i;
+		} while (--i >= 0);
+
+		/* trim off trailing zero words */
+		result->nwords = lastnonzero + 1;
+	}
+	Assert(result->nwords != 0);
+
 	/* Need not check for empty result, since we handled that case above */
 	return result;
 }
@@ -331,8 +356,6 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
 bool
 bms_is_subset(const Bitmapset *a, const Bitmapset *b)
 {
-	int			shortlen;
-	int			longlen;
 	int			i;
 
 	/* Handle cases where either input is NULL */
@@ -340,23 +363,19 @@ bms_is_subset(const Bitmapset *a, const Bitmapset *b)
 		return true;			/* empty set is a subset of anything */
 	if (b == NULL)
 		return false;
-	/* Check common words */
-	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
+
+	/* 'a' can't be a subset of 'b' if it contains more words */
+	if (a->nwords > b->nwords)
+		return false;
+
+	/* Check all 'a' members are set in 'b' */
+	i = a->nwords - 1;
+	do
 	{
 		if ((a->words[i] & ~b->words[i]) != 0)
 			return false;
-	}
-	/* Check extra words */
-	if (a->nwords > b->nwords)
-	{
-		longlen = a->nwords;
-		for (; i < longlen; i++)
-		{
-			if (a->words[i] != 0)
-				return false;
-		}
-	}
+	} while (--i >= 0);
+
 	return true;
 }
 
@@ -370,7 +389,6 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
 {
 	BMS_Comparison result;
 	int			shortlen;
-	int			longlen;
 	int			i;
 
 	/* Handle cases where either input is NULL */
@@ -382,10 +400,12 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
 	}
 	if (b == NULL)
 		return BMS_SUBSET2;
+
 	/* Check common words */
 	result = BMS_EQUAL;			/* status so far */
 	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
+	i = 0;
+	do
 	{
 		bitmapword	aword = a->words[i];
 		bitmapword	bword = b->words[i];
@@ -404,35 +424,22 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
 				return BMS_DIFFERENT;
 			result = BMS_SUBSET1;
 		}
-	}
+	} while (++i < shortlen);
+
 	/* Check extra words */
 	if (a->nwords > b->nwords)
 	{
-		longlen = a->nwords;
-		for (; i < longlen; i++)
-		{
-			if (a->words[i] != 0)
-			{
-				/* a is not a subset of b */
-				if (result == BMS_SUBSET1)
-					return BMS_DIFFERENT;
-				result = BMS_SUBSET2;
-			}
-		}
+		/* if a has more words then a is not a subset of b */
+		if (result == BMS_SUBSET1)
+			return BMS_DIFFERENT;
+		return BMS_SUBSET2;
 	}
 	else if (a->nwords < b->nwords)
 	{
-		longlen = b->nwords;
-		for (; i < longlen; i++)
-		{
-			if (b->words[i] != 0)
-			{
-				/* b is not a subset of a */
-				if (result == BMS_SUBSET2)
-					return BMS_DIFFERENT;
-				result = BMS_SUBSET1;
-			}
-		}
+		/* if b has more words then b is not a subset of a */
+		if (result == BMS_SUBSET2)
+			return BMS_DIFFERENT;
+		return BMS_SUBSET1;
 	}
 	return result;
 }
@@ -467,7 +474,7 @@ bms_is_member(int x, const Bitmapset *a)
  * Returns (-1) when x is not a member.
  */
 int
-bms_member_index(Bitmapset *a, int x)
+bms_member_index(const Bitmapset *a, int x)
 {
 	int			i;
 	int			bitnum;
@@ -488,7 +495,7 @@ bms_member_index(Bitmapset *a, int x)
 		bitmapword	w = a->words[i];
 
 		/* No need to count the bits in a zero word */
-		if (w != 0)
+		if (w)
 			result += bmw_popcount(w);
 	}
 
@@ -516,13 +523,16 @@ bms_overlap(const Bitmapset *a, const Bitmapset *b)
 	/* 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++)
+	i = shortlen - 1;
+	do
 	{
 		if ((a->words[i] & b->words[i]) != 0)
 			return true;
-	}
+	} while (--i >= 0);
+
 	return false;
 }
 
@@ -533,8 +543,6 @@ bool
 bms_overlap_list(const Bitmapset *a, const List *b)
 {
 	ListCell   *lc;
-	int			wordnum,
-				bitnum;
 
 	if (a == NULL || b == NIL)
 		return false;
@@ -542,6 +550,8 @@ bms_overlap_list(const Bitmapset *a, const List *b)
 	foreach(lc, b)
 	{
 		int			x = lfirst_int(lc);
+		int			wordnum,
+					bitnum;
 
 		if (x < 0)
 			elog(ERROR, "negative bitmapset member not allowed");
@@ -563,7 +573,6 @@ bms_overlap_list(const Bitmapset *a, const List *b)
 bool
 bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
 {
-	int			shortlen;
 	int			i;
 
 	/* Handle cases where either input is NULL */
@@ -571,19 +580,19 @@ bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
 		return false;
 	if (b == NULL)
 		return true;
-	/* Check words in common */
-	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
+
+	/* if 'a' has more words then it must contain additional members */
+	if (a->nwords > b->nwords)
+		return true;
+
+	/* Check all 'a' members are set in 'b' */
+	i = a->nwords - 1;
+	do
 	{
 		if ((a->words[i] & ~b->words[i]) != 0)
 			return true;
-	}
-	/* Check extra words in a */
-	for (; i < a->nwords; i++)
-	{
-		if (a->words[i] != 0)
-			return true;
-	}
+	} while (--i >= 0);
+
 	return false;
 }
 
@@ -602,20 +611,22 @@ bms_singleton_member(const Bitmapset *a)
 	if (a == NULL)
 		elog(ERROR, "bitmapset is empty");
 	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
+	wordnum = 0;
+	do
 	{
 		bitmapword	w = a->words[wordnum];
 
-		if (w != 0)
+		if (w)
 		{
 			if (result >= 0 || HAS_MULTIPLE_ONES(w))
 				elog(ERROR, "bitmapset has multiple members");
 			result = wordnum * BITS_PER_BITMAPWORD;
 			result += bmw_rightmost_one_pos(w);
 		}
-	}
-	if (result < 0)
-		elog(ERROR, "bitmapset is empty");
+	} while (++wordnum < nwords);
+
+	/* we don't expect non-NULL sets to be empty */
+	Assert(result >= 0);
 	return result;
 }
 
@@ -640,20 +651,22 @@ bms_get_singleton_member(const Bitmapset *a, int *member)
 	if (a == NULL)
 		return false;
 	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
+	wordnum = 0;
+	do
 	{
 		bitmapword	w = a->words[wordnum];
 
-		if (w != 0)
+		if (w)
 		{
 			if (result >= 0 || HAS_MULTIPLE_ONES(w))
 				return false;
 			result = wordnum * BITS_PER_BITMAPWORD;
 			result += bmw_rightmost_one_pos(w);
 		}
-	}
-	if (result < 0)
-		return false;
+	} while (++wordnum < nwords);
+
+	/* we don't expect non-NULL sets to be empty */
+	Assert(result >= 0);
 	*member = result;
 	return true;
 }
@@ -665,20 +678,21 @@ int
 bms_num_members(const Bitmapset *a)
 {
 	int			result = 0;
-	int			nwords;
-	int			wordnum;
+	int			i;
 
 	if (a == NULL)
 		return 0;
-	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
+
+	i = a->nwords - 1;
+	do
 	{
-		bitmapword	w = a->words[wordnum];
+		bitmapword	w = a->words[i];
 
 		/* No need to count the bits in a zero word */
-		if (w != 0)
+		if (w)
 			result += bmw_popcount(w);
-	}
+	} while (--i >= 0);
+
 	return result;
 }
 
@@ -690,49 +704,27 @@ bms_num_members(const Bitmapset *a)
 BMS_Membership
 bms_membership(const Bitmapset *a)
 {
-	BMS_Membership result = BMS_EMPTY_SET;
-	int			nwords;
-	int			wordnum;
+	BMS_Membership result;
+	int			i;
 
 	if (a == NULL)
 		return BMS_EMPTY_SET;
-	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
+
+	result = BMS_EMPTY_SET;
+	i = a->nwords - 1;
+	do
 	{
-		bitmapword	w = a->words[wordnum];
+		bitmapword	w = a->words[i];
 
-		if (w != 0)
+		if (w)
 		{
 			if (result != BMS_EMPTY_SET || HAS_MULTIPLE_ONES(w))
 				return BMS_MULTIPLE;
 			result = BMS_SINGLETON;
 		}
-	}
-	return result;
-}
-
-/*
- * bms_is_empty_internal - is a set empty?
- *
- * This is now used only locally, to detect cases where a function has
- * computed an empty set that we must now get rid of.  Hence, we can
- * assume the input isn't NULL.
- */
-static bool
-bms_is_empty_internal(const Bitmapset *a)
-{
-	int			nwords;
-	int			wordnum;
+	} while (--i >= 0);
 
-	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
-	{
-		bitmapword	w = a->words[wordnum];
-
-		if (w != 0)
-			return false;
-	}
-	return true;
+	return result;
 }
 
 
@@ -767,14 +759,11 @@ bms_add_member(Bitmapset *a, int x)
 	/* enlarge the set if necessary */
 	if (wordnum >= a->nwords)
 	{
-		int			oldnwords = a->nwords;
-		int			i;
-
-		a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
+		size_t	oldsize;
+	
+		oldsize = BITMAPSET_SIZE(a->nwords);
+		a = (Bitmapset *) repalloc0(a, oldsize, BITMAPSET_SIZE(wordnum + 1));
 		a->nwords = wordnum + 1;
-		/* zero out the enlarged portion */
-		for (i = oldnwords; i < a->nwords; i++)
-			a->words[i] = 0;
 	}
 
 	a->words[wordnum] |= ((bitmapword) 1 << bitnum);
@@ -792,7 +781,8 @@ Bitmapset *
 bms_del_member(Bitmapset *a, int x)
 {
 	int			wordnum,
-				bitnum;
+				bitnum,
+				i;
 
 	if (x < 0)
 		elog(ERROR, "negative bitmapset member not allowed");
@@ -800,14 +790,32 @@ bms_del_member(Bitmapset *a, int x)
 		return NULL;
 	wordnum = WORDNUM(x);
 	bitnum = BITNUM(x);
-	if (wordnum < a->nwords)
-		a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
-	/* If we computed an empty result, we must return NULL */
-	if (bms_is_empty_internal(a))
+
+	/* member can't exist.  Return 'a' unmodified */
+	if (unlikely(wordnum >= a->nwords))
+		return a;
+
+	a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
+
+	/* when last word becomes empty, trim off all trailing empty words */
+	i = a->nwords - 1;
+	if (wordnum == i && a->words[i] == 0)
 	{
+		/* find the last non-empty word and make that the new final word */
+		do
+		{
+			if (a->words[i])
+			{
+				a->nwords = i + 1;
+				return a;
+			}
+		} while (--i >= 0);
+
+		/* the set is now empty */
 		pfree(a);
 		return NULL;
 	}
+
 	return a;
 }
 
@@ -819,7 +827,6 @@ bms_add_members(Bitmapset *a, const Bitmapset *b)
 {
 	Bitmapset  *result;
 	const Bitmapset *other;
-	int			otherlen;
 	int			i;
 
 	/* Handle cases where either input is NULL */
@@ -827,6 +834,7 @@ bms_add_members(Bitmapset *a, const Bitmapset *b)
 		return bms_copy(b);
 	if (b == NULL)
 		return a;
+
 	/* Identify shorter and longer input; copy the longer one if needed */
 	if (a->nwords < b->nwords)
 	{
@@ -838,10 +846,14 @@ bms_add_members(Bitmapset *a, const Bitmapset *b)
 		result = a;
 		other = b;
 	}
+
 	/* And union the shorter input into the result */
-	otherlen = other->nwords;
-	for (i = 0; i < otherlen; i++)
+	i = other->nwords - 1;
+	do
+	{
 		result->words[i] |= other->words[i];
+	} while (--i >= 0);
+
 	if (result != a)
 		pfree(a);
 	return result;
@@ -880,15 +892,12 @@ bms_add_range(Bitmapset *a, int lower, int upper)
 	}
 	else if (uwordnum >= a->nwords)
 	{
-		int			oldnwords = a->nwords;
-		int			i;
+		size_t	oldsize;
 
 		/* ensure we have enough words to store the upper bit */
-		a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
+		oldsize = BITMAPSET_SIZE(a->nwords);
+		a = (Bitmapset *) repalloc0(a, oldsize, BITMAPSET_SIZE(uwordnum + 1));
 		a->nwords = uwordnum + 1;
-		/* zero out the enlarged portion */
-		for (i = oldnwords; i < a->nwords; i++)
-			a->words[i] = 0;
 	}
 
 	wordnum = lwordnum = WORDNUM(lower);
@@ -927,6 +936,7 @@ bms_add_range(Bitmapset *a, int lower, int upper)
 Bitmapset *
 bms_int_members(Bitmapset *a, const Bitmapset *b)
 {
+	int			lastnonzero;
 	int			shortlen;
 	int			i;
 
@@ -938,18 +948,28 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
 		pfree(a);
 		return NULL;
 	}
+
 	/* Intersect b into a; we need never copy */
 	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
+	lastnonzero = -1;
+	i = shortlen - 1;
+	do
+	{
 		a->words[i] &= b->words[i];
-	for (; i < a->nwords; i++)
-		a->words[i] = 0;
+
+		if (lastnonzero == -1 && a->words[i])
+			lastnonzero = i;
+	} while (--i >= 0);
+
 	/* If we computed an empty result, we must return NULL */
-	if (bms_is_empty_internal(a))
+	if (lastnonzero == -1)
 	{
 		pfree(a);
 		return NULL;
 	}
+
+	/* get rid of trailing zero words */
+	a->nwords = lastnonzero + 1;
 	return a;
 }
 
@@ -959,7 +979,6 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
 Bitmapset *
 bms_del_members(Bitmapset *a, const Bitmapset *b)
 {
-	int			shortlen;
 	int			i;
 
 	/* Handle cases where either input is NULL */
@@ -967,16 +986,46 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
 		return NULL;
 	if (b == NULL)
 		return a;
+
 	/* Remove b's bits from a; we need never copy */
-	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
-		a->words[i] &= ~b->words[i];
-	/* If we computed an empty result, we must return NULL */
-	if (bms_is_empty_internal(a))
+	if (a->nwords > b->nwords)
 	{
-		pfree(a);
-		return NULL;
+		/*
+		 * We'll never need to remove trailing zero words when 'a' has more
+		 * words than 'b'.
+		 */
+		i = b->nwords - 1;
+		do
+		{
+			a->words[i] &= ~b->words[i];
+		} while (--i >= 0);
 	}
+	else
+	{
+		int			lastnonzero = -1;
+
+		/* we may need to remove trailing zero words from the result. */
+		i = a->nwords - 1;
+		do
+		{
+			a->words[i] &= ~b->words[i];
+
+			/* remember the last non-zero word */
+			if (lastnonzero == -1 && a->words[i])
+				lastnonzero = i;
+		} while (--i >= 0);
+
+		/* check if 'a' has become empty */
+		if (lastnonzero == -1)
+		{
+			pfree(a);
+			return NULL;
+		}
+
+		/* trim off any trailing zero words */
+		a->nwords = lastnonzero + 1;
+	}
+
 	return a;
 }
 
@@ -988,7 +1037,6 @@ bms_join(Bitmapset *a, Bitmapset *b)
 {
 	Bitmapset  *result;
 	Bitmapset  *other;
-	int			otherlen;
 	int			i;
 
 	/* Handle cases where either input is NULL */
@@ -996,6 +1044,7 @@ bms_join(Bitmapset *a, Bitmapset *b)
 		return b;
 	if (b == NULL)
 		return a;
+
 	/* Identify shorter and longer input; use longer one as result */
 	if (a->nwords < b->nwords)
 	{
@@ -1007,10 +1056,14 @@ bms_join(Bitmapset *a, Bitmapset *b)
 		result = a;
 		other = b;
 	}
+
 	/* And union the shorter input into the result */
-	otherlen = other->nwords;
-	for (i = 0; i < otherlen; i++)
+	i = other->nwords - 1;
+	do
+	{
 		result->words[i] |= other->words[i];
+	} while (--i >= 0);
+
 	if (other != result)		/* pure paranoia */
 		pfree(other);
 	return result;
@@ -1054,7 +1107,7 @@ bms_next_member(const Bitmapset *a, int prevbit)
 		/* ignore bits before prevbit */
 		w &= mask;
 
-		if (w != 0)
+		if (w)
 		{
 			int			result;
 
@@ -1123,7 +1176,7 @@ bms_prev_member(const Bitmapset *a, int prevbit)
 		/* mask out bits left of prevbit */
 		w &= mask;
 
-		if (w != 0)
+		if (w)
 		{
 			int			result;
 
@@ -1140,28 +1193,14 @@ bms_prev_member(const Bitmapset *a, int prevbit)
 
 /*
  * bms_hash_value - compute a hash key for a Bitmapset
- *
- * Note: we must ensure that any two bitmapsets that are bms_equal() will
- * hash to the same value; in practice this means that trailing all-zero
- * words must not affect the result.  Hence we strip those before applying
- * hash_any().
  */
 uint32
 bms_hash_value(const Bitmapset *a)
 {
-	int			lastword;
-
 	if (a == NULL)
 		return 0;				/* All empty sets hash to 0 */
-	for (lastword = a->nwords; --lastword >= 0;)
-	{
-		if (a->words[lastword] != 0)
-			break;
-	}
-	if (lastword < 0)
-		return 0;				/* All empty sets hash to 0 */
 	return DatumGetUInt32(hash_any((const unsigned char *) a->words,
-								   (lastword + 1) * sizeof(bitmapword)));
+								   a->nwords * sizeof(bitmapword)));
 }
 
 /*
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index 14de6a9ff1..a4c2ba6712 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -90,7 +90,7 @@ extern Bitmapset *bms_difference(const Bitmapset *a, const Bitmapset *b);
 extern bool bms_is_subset(const Bitmapset *a, const Bitmapset *b);
 extern BMS_Comparison bms_subset_compare(const Bitmapset *a, const Bitmapset *b);
 extern bool bms_is_member(int x, const Bitmapset *a);
-extern int	bms_member_index(Bitmapset *a, int x);
+extern int	bms_member_index(const Bitmapset *a, int x);
 extern bool bms_overlap(const Bitmapset *a, const Bitmapset *b);
 extern bool bms_overlap_list(const Bitmapset *a, const struct List *b);
 extern bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b);