Re: Making empty Bitmapsets always be NULL

Hello,

On Thu, Mar 16, 2023 at 10:30 AM Yuya Watari <watari.yuya@gmail.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