Re: Making empty Bitmapsets always be NULL

Hello,

On Thu, Mar 16, 2023 at 10:30 AM Yuya Watari <watari(dot)yuya(at)gmail(dot)com> wrote:
> My idea is to compute the bitwise OR of all bitmapwords of the result
> Bitmapset. The bitwise OR can be represented as a single operation in
> the machine code and does not require any conditional branches. If the
> bitwise ORed value is zero, we can conclude the result Bitmapset is
> empty. The costs related to this operation can be almost negligible;
> it is significantly cheaper than calling bms_is_empty_internal() and
> less expensive than using a conditional branch such as 'if.'

After posting the patch, I noticed that my patch had some bugs. My
idea above is not applicable to bms_del_member(), and I missed some
additional operations required in bms_del_members(). I have attached
the fixed version to this email. I really apologize for making the
mistakes. Should we add new regression tests to prevent this kind of
bug?

The following tables illustrate the result of a re-run experiment. The
significant improvement was a mistake, but a speedup of about 2% was
still obtained when the number of partitions, namely n, was large.
This result indicates that the optimization regarding
bms_is_empty_internal() is effective on some workloads.

Table 1: Planning time (ms)
(n: the number of partitions of each table)
-----------------------------------------------------------------
n | Master | Patched (trailing-zero) | Patched (bitwise-OR)
-----------------------------------------------------------------
1 | 36.903 | 36.621 | 36.731
2 | 35.842 | 35.031 | 35.704
4 | 37.756 | 37.457 | 37.409
8 | 42.069 | 42.578 | 42.322
16 | 53.670 | 67.792 | 53.618
32 | 88.412 | 100.605 | 89.147
64 | 229.734 | 271.259 | 225.971
128 | 889.367 | 1272.270 | 870.472
256 | 4209.312 | 8223.623 | 4129.594
-----------------------------------------------------------------

Table 2: Planning time speedup (higher is better)
------------------------------------------------------
n | Patched (trailing-zero) | Patched (bitwise-OR)
------------------------------------------------------
1 | 100.8% | 100.5%
2 | 102.3% | 100.4%
4 | 100.8% | 100.9%
8 | 98.8% | 99.4%
16 | 79.2% | 100.1%
32 | 87.9% | 99.2%
64 | 84.7% | 101.7%
128 | 69.9% | 102.2%
256 | 51.2% | 101.9%
------------------------------------------------------

--
Best regards,
Yuya Watari