Thread

1. Add bms_offset_members() function for bitshifting Bitmapsets

   David Rowley <dgrowleyml@gmail.com> — 2026-04-13T04:35:03Z

   (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
   

2. Re: Add bms_offset_members() function for bitshifting Bitmapsets

   Chao Li <li.evan.chao@gmail.com> — 2026-04-14T08:46:11Z

   
   > 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/
   
   
   
   
   

3. Re: Add bms_offset_members() function for bitshifting Bitmapsets

   David Rowley <dgrowleyml@gmail.com> — 2026-04-14T23:45:12Z

   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
   

4. Re: Add bms_offset_members() function for bitshifting Bitmapsets

   Tom Lane <tgl@sss.pgh.pa.us> — 2026-04-15T00:29:08Z

   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
   
   
   
   

5. Re: Add bms_offset_members() function for bitshifting Bitmapsets

   David Rowley <dgrowleyml@gmail.com> — 2026-04-15T02:21:36Z

   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
   
   
   
   

6. Re: Add bms_offset_members() function for bitshifting Bitmapsets

   Tom Lane <tgl@sss.pgh.pa.us> — 2026-04-15T02:30:47Z

   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
   
   
   
   

7. Re: Add bms_offset_members() function for bitshifting Bitmapsets

   David Rowley <dgrowleyml@gmail.com> — 2026-04-15T02:33:36Z

   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
   
   
   
   

8. Re: Add bms_offset_members() function for bitshifting Bitmapsets

   Peter Eisentraut <peter@eisentraut.org> — 2026-04-15T19:17:12Z

   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.
   
   
   
   
   

9. Re: Add bms_offset_members() function for bitshifting Bitmapsets

   David Rowley <dgrowleyml@gmail.com> — 2026-04-18T07:49:57Z

   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
   

10. Re: Add bms_offset_members() function for bitshifting Bitmapsets

    David Rowley <dgrowleyml@gmail.com> — 2026-04-18T07:53:40Z

    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
    
    
    
    

11. Re: Add bms_offset_members() function for bitshifting Bitmapsets

    Tom Lane <tgl@sss.pgh.pa.us> — 2026-04-18T15:09:31Z

    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
    
    
    
    

12. Re: Add bms_offset_members() function for bitshifting Bitmapsets

    Greg Burd <greg@burd.me> — 2026-04-19T19:21:41Z

    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
    
    
    
    
    

13. Re: Add bms_offset_members() function for bitshifting Bitmapsets

    David Rowley <dgrowleyml@gmail.com> — 2026-04-19T23:52:58Z

    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
    

14. Re: Add bms_offset_members() function for bitshifting Bitmapsets

    Greg Burd <greg@burd.me> — 2026-04-20T14:55:09Z

    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
    
    
    > David
    >
    > Attachments:
    > * v3-0001-Introduce-bms_offset_members-function.patch
    
    
    
    

15. Re: Add bms_offset_members() function for bitshifting Bitmapsets

    David Rowley <dgrowleyml@gmail.com> — 2026-04-21T01:40:17Z

    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
    
    
    
    

16. Re: Add bms_offset_members() function for bitshifting Bitmapsets

    David Rowley <dgrowleyml@gmail.com> — 2026-07-08T13:20:43Z

    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