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

On Tue, 21 Apr 2026 at 13:40, David Rowley <dgrowleyml@gmail.com> wrote:

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.

After some small adjustments to some comments and reducing the number
of iterations in test_random_offset_operations(), I pushed the patch.

The 10000 iterations were pushing the test time to about 91ms, which
seemed like quite a big jump from the ~28ms that it was taking on my
machine. With 1000, it takes 36ms, which seems like a more reasonable
increase.

Thank you all for the reviews and feedback.

David

On 20.04.26 01:52, 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.

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.

In the function test_random_offset_operations(), the variable seed is
declared as type uint64, then assigned from GetCurrentTimestamp() or
PG_GETARG_INT64(), both of which return int64, then it is passed to
pg_prng_seed(), which takes uint64, and then it is printed using
INT64_FORMAT. Maybe this could be a bit more consistent?

On Thu, 9 Jul 2026 at 07:24, Peter Eisentraut <peter@eisentraut.org> wrote:

In the function test_random_offset_operations(), the variable seed is
declared as type uint64, then assigned from GetCurrentTimestamp() or
PG_GETARG_INT64(), both of which return int64, then it is passed to
pg_prng_seed(), which takes uint64, and then it is printed using
INT64_FORMAT. Maybe this could be a bit more consistent?

I pushed a change to make seed int64 instead. It's still possible to
specify the full range of possible values that GetCurrentTimestamp()
can (or could ever) return with the int64 type. This way, there's no
longer a mismatch in the format specifier for elog and the type we're
formatting. That's an improvement, so thanks.

David