Add bms_offset_members() function for bitshifting Bitmapsets

On Apr 13, 2026, at 12:35, David Rowley <dgrowleyml@gmail.com> wrote:

(v20 material)

While working on some new code which required offsetting the members
of a Bitmapset, I decided to go and write a function to do this rather
than copy the various other places where we manually construct a new
set with a bms_next_member() -> bms_add_member() loop. The new use
case I have is from pulling varattnos from a scan's targetlist, which
there could be several hundred Vars in. I considered this might be
noticeably expensive.

The current manual way we have of doing this is a bit laborious since
we're only doing 1 member per bms_next_member() loop, and also, if the
set has multiple words, we may end up doing several repallocs to
expand the set, perhaps as little as 1 word at a time. That's not to
mention the rather repetitive code that we have to do this in various
places that might be nice to consolidate.

I've attached a patch which adds bms_offset_members(), which does
bitshifting to move the members up or down by the given offset. While
working on this I made a few choices which might be worth a revisit:

1) The function modifies the given set in-place rather than making a new set.
2) The function will ERROR if any member would go above INT_MAX. These
would be inaccessible, and that seems weird/wrong.
3) When offsetting by a negative value, members that would go below
zero fall out of the set silently.

For #1; my original use-case that made me write this didn't need a
copy, so I wrote the function to modify the set in-place. After
hunting down and replacing the relevant existing bms_next_member()
loops with the new function, I noticed all these seem to need a copy.
Currently, I have coded the patch to do
bms_offset_members(bms_copy(set), ...), but that's a little
inefficient as it *could* result in a palloc for the copy then a
repalloc in the offset. If bms_offset_members() just created a new
set, then it could palloc() a set to the exact required size. The
counterargument to that is that I don't really want to copy the set
for my intended use case. I thought about two versions, but thought
that might be overkill. There could be a boolean parameter to define
that, but we don't do that anywhere else in bitmapset.c, or we could
avoid a copy-paste of the code with an always-inlined helper function.
I couldn't decide, so left it as-is.

For #2, I could have equally made these fall off the top of the set,
but I thought we might want to know about it in the unlikely event
that this ever happens.

#3 We commonly want to get rid of system columns from a
pull_varattnos() set which is offset by
FirstLowInvalidHeapAttributeNumber, so those disappearing silently is
what most use cases seem to want. I expect that's not for revisiting,
but I listed this one anyway as it flies in the face of #2.

Patch attached. Comments welcome.

David
<v1-0001-Introduce-bms_offset_members-function.patch>

I basically agree with design choices 1/2/3. And the implementation of v1 overall looks good to me.

The only issue I found is this overflow check:
```
+	/* Handle a positive offset (bitshift left) */
+	if (offset > 0)
+	{
+		/*
+		 * An unlikely scenario, but check we're not going to create a member
+		 * greater than PG_INT32_MAX.
+		 */
+		if (((uint64) new_nwords - 1) * BITS_PER_BITMAPWORD + high_bit + offset_bits > PG_INT32_MAX)
+			elog(ERROR, "bitmapset overflow");
```

This overflow check seems wrong. Because when high_bit + offset_bits > BITS_PER_BITMAPWORD, new_nwords has been increased by 1, so there high_bit + offset_bits are double counted.

To verify that, I added a new test:
```
-- 2147483583 is PG_INT32_MAX - 64, so offsetting by 1 should succeed,
-- but offsetting it by 65 should fail with overflow error
SELECT test_random_offset_operations_check_highest(2147483583, 1) AS result;
SELECT test_random_offset_operations_check_highest(2147483583, 65) AS result;
```

With v1, test_random_offset_operations_check_highest(2147483583, 1) reports an overflow error, but it should not.

Please see the attached diff for the test I added. In that diff, I also included a fix, and with that fix, the tests pass.

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/

Thanks for looking.

On Tue, 14 Apr 2026 at 20:46, Chao Li <li.evan.chao@gmail.com> wrote:

+               if (((uint64) new_nwords - 1) * BITS_PER_BITMAPWORD + high_bit + offset_bits > PG_INT32_MAX)
+                       elog(ERROR, "bitmapset overflow");

This overflow check seems wrong. Because when high_bit + offset_bits > BITS_PER_BITMAPWORD, new_nwords has been increased by 1, so there high_bit + offset_bits are double counted.

Your idea of checking the old highest member plus the offset seems a
more robust method, so I've adjusted the patch to use that.

David

David Rowley <dgrowleyml@gmail.com> writes:

Your idea of checking the old highest member plus the offset seems a
more robust method, so I've adjusted the patch to use that.

I question the decision to make this change the set in-place.
Wouldn't it be cheaper and less surprise-prone to always make
a copy?

regards, tom lane

On Wed, 15 Apr 2026 at 12:29, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I question the decision to make this change the set in-place.
Wouldn't it be cheaper and less surprise-prone to always make
a copy?

I'd not considered surprise-prone as an aspect. I understand we have
bms_join and bms_union, which do the same thing if you only care about
the value of the result and not what happens to the inputs. So I
didn't think I was introducing anything too surpising given we've got
various other Bitmapset functions that modify the input in-place. My
expectation there was that people are used to checking what the
behaviour of the bitmapset function is.

For the current use cases of the function in the patch, I agree that
it would likely be better for performance if the new function
allocated a new set. It was more a question of whether we want to
throw away performance for other cases which are fine with an in-place
update and have a positive offset. Those will never repalloc(). I
didn't really know the answer. I suspect with the current patch that
each of the existing cases will be faster than today's bms_next_member
loops, regardless. When I wrote the function, I was mainly thinking
of the new use-case that I was working on, which won't require any
palloc() or repalloc() with the current design. Since I was adding
that to a fairly common code path, I thought I had more of a chance of
not having to jump through too many hoops to ensure I don't cause any
performance regressions.

In short, I don't really know what's best. I'm certainly open to
changing it if someone comes up with a good reason to do it the other
way. Maybe catering for the majority of callers is a good enough
reason to change it.

David

David Rowley <dgrowleyml@gmail.com> writes:

On Wed, 15 Apr 2026 at 12:29, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I question the decision to make this change the set in-place.
Wouldn't it be cheaper and less surprise-prone to always make
a copy?

I'd not considered surprise-prone as an aspect. I understand we have
bms_join and bms_union, which do the same thing if you only care about
the value of the result and not what happens to the inputs.

Sure, but bms_join is an optional optimization of the far safer
bms_union operation. It bothers me to create the optimized case
but not the base case.

regards, tom lane

On Wed, 15 Apr 2026 at 14:30, Tom Lane <tgl@sss.pgh.pa.us> wrote:

David Rowley <dgrowleyml@gmail.com> writes:

I'd not considered surprise-prone as an aspect. I understand we have
bms_join and bms_union, which do the same thing if you only care about
the value of the result and not what happens to the inputs.

Sure, but bms_join is an optional optimization of the far safer
bms_union operation. It bothers me to create the optimized case
but not the base case.

Hmm, yeah. That seems like a good argument for making a new set. I'll
go make it so.

David

On 15.04.26 04:33, David Rowley wrote:

On Wed, 15 Apr 2026 at 14:30, Tom Lane <tgl@sss.pgh.pa.us> wrote:

David Rowley <dgrowleyml@gmail.com> writes:

I'd not considered surprise-prone as an aspect. I understand we have
bms_join and bms_union, which do the same thing if you only care about
the value of the result and not what happens to the inputs.

Sure, but bms_join is an optional optimization of the far safer
bms_union operation. It bothers me to create the optimized case
but not the base case.

Hmm, yeah. That seems like a good argument for making a new set. I'll
go make it so.

Depending on what you end up doing, maybe a sprinkling of pg_nodiscard
could be appropriate.

On Wed, 15 Apr 2026 at 14:33, David Rowley <dgrowleyml@gmail.com> wrote:

On Wed, 15 Apr 2026 at 14:30, Tom Lane <tgl@sss.pgh.pa.us> wrote:

David Rowley <dgrowleyml@gmail.com> writes:

I'd not considered surprise-prone as an aspect. I understand we have
bms_join and bms_union, which do the same thing if you only care about
the value of the result and not what happens to the inputs.

Sure, but bms_join is an optional optimization of the far safer
bms_union operation. It bothers me to create the optimized case
but not the base case.

Hmm, yeah. That seems like a good argument for making a new set. I'll
go make it so.

Patch attached for the version that creates a new set rather than
modifying the input set in-place.

David

On Thu, 16 Apr 2026 at 07:17, Peter Eisentraut <peter@eisentraut.org> wrote:

Depending on what you end up doing, maybe a sprinkling of pg_nodiscard
could be appropriate.

Yeah maybe. It wouldn't do any harm, at least.

I didn't do that in the patch I just sent as it felt like something we
should do or not do for all the bitmapset functions it's relevant for.
REALLOCATE_BITMAPSETS is meant to give us a stronger guarantee of
people forgetting to do this, as it would cause a breakage if there
were multiple pointers to the same set and only one of them got
updated.

David

David Rowley <dgrowleyml@gmail.com> writes:

On Thu, 16 Apr 2026 at 07:17, Peter Eisentraut <peter@eisentraut.org> wrote:

Depending on what you end up doing, maybe a sprinkling of pg_nodiscard
could be appropriate.

Yeah maybe. It wouldn't do any harm, at least.

I didn't do that in the patch I just sent as it felt like something we
should do or not do for all the bitmapset functions it's relevant for.

Agreed, seems like it should be a separate patch.

regards, tom lane

On Sat, Apr 18, 2026, at 3:49 AM, David Rowley wrote:

On Wed, 15 Apr 2026 at 14:33, David Rowley <dgrowleyml@gmail.com> wrote:

On Wed, 15 Apr 2026 at 14:30, Tom Lane <tgl@sss.pgh.pa.us> wrote:

David Rowley <dgrowleyml@gmail.com> writes:

I'd not considered surprise-prone as an aspect. I understand we have
bms_join and bms_union, which do the same thing if you only care about
the value of the result and not what happens to the inputs.

Sure, but bms_join is an optional optimization of the far safer
bms_union operation. It bothers me to create the optimized case
but not the base case.

Hmm, yeah. That seems like a good argument for making a new set. I'll
go make it so.

Patch attached for the version that creates a new set rather than
modifying the input set in-place.

David

Hey David,

Attachments:
* v2-0001-Introduce-bms_offset_members-function.patch

I applied, tested, and reviewed these changes. Thanks for doing this, only a few small things jumped out.

nit: in bitmapset.c there is a new line added above bms_add_range()

+ * Arguments:
+ *	arg1: optional random seed, or < 0 to use a random seed.
+ *  arg2: the number of operations to perform.
+ *  arg3: the maximum bitmapset member number to use in the random set.
+ *  arg4: the minimum bitmapset member number to use in the random set.

nit: whitespace ahead of arg1, also should be "NULL" not "< 0"

in test_bitmapset.sql

+-- perform some random test on bms_offset_members()

nit: "tests"

Also, I think the random testing will likely cover these, but here are a few more explicit tests for odd corner cases.

-- shift that shrinks nwords
SELECT test_bms_offset_members('(b 64 65 66)', -64); -- drops into word 0

-- shift that drops some low members and keeps others
SELECT test_bms_offset_members('(b 0 1 2 10)', -2); -- expect (b 0 8)

-- entire set shifts below zero -> empty
SELECT test_bms_offset_members('(b 1 2 3)', -10); -- expect empty

-- word-aligned positive and negative shifts
SELECT test_bms_offset_members('(b 1 2 3)', 64);
SELECT test_bms_offset_members('(b 65 66 67)', -64);

-- INT_MIN boundary
SELECT test_bms_offset_members('(b 1)', -2147483648);

I like the functionality and the reduction of repeated code that you've identified and fixed.

best.

-greg

On Mon, 20 Apr 2026 at 07:22, Greg Burd <greg@burd.me> wrote:

I applied, tested, and reviewed these changes. Thanks for doing this, only a few small things jumped out.

Many thanks. I took all of those suggestions.

SELECT test_bms_offset_members('(b 1)', -2147483648);

I made that one use member 0 instead of 1. That'll mean "new_highest"
goes to INT_MIN rather than INT_MIN + 1.

David

On Sun, Apr 19, 2026, at 7:52 PM, David Rowley wrote:

On Mon, 20 Apr 2026 at 07:22, Greg Burd <greg@burd.me> wrote:

I applied, tested, and reviewed these changes. Thanks for doing this, only a few small things jumped out.

Many thanks. I took all of those suggestions.

Happy to help.

SELECT test_bms_offset_members('(b 1)', -2147483648);

I made that one use member 0 instead of 1. That'll mean "new_highest"
goes to INT_MIN rather than INT_MIN + 1.

Perfect, that covers the gap nicely.

Were you planning on writing the optimized non-copy version as well? I don't think it is strictly necessary, more a curiosity.

bms_offset_members() -> new bms, might repalloc() replaces existing loops you've found
bms_shift_members() -> bms is modified in place and fits your new use case a bit better

best.

-greg

On Tue, 21 Apr 2026 at 02:55, Greg Burd <greg@burd.me> wrote:

Were you planning on writing the optimized non-copy version as well? I don't think it is strictly necessary, more a curiosity.

bms_offset_members() -> new bms, might repalloc() replaces existing loops you've found
bms_shift_members() -> bms is modified in place and fits your new use case a bit better

Not at this stage. The v1 patch did modify the set in-place, so the
code is there if we ever need it. I didn't find any need for it in our
current code. The selective tuple deforming patch I'm working on could
use it, but I doubt it's worth the trouble for 1 caller. It's just for
something that happens during create_plan(), so 1 more allocation in
that code likely isn't going to be noticed.

David