Обсуждение: Speeding Up Bitmapset

On Mon, 26 Jun 2023 at 00:29, Ranier Vilela <ranier.vf@gmail.com> wrote:
> Yuya Watari presented a series of patches, with the objective of improving the Bitmapset [1].
> After reading through the patches, I saw a lot of good ideas and thought I'd help.
> Unfortunately, my suggestions were not well received.

For the future, I recommend if you do have ideas that you wish to
convey and think a patch is the easiest way to do that, then it's best
to send those with an extension that won't cause the CFbot to pickup
your patch instead. You patch did and still does seem to have a load
of extra changes that are unjustified by your claims.  There are quite
a lot of white space changes going on. There's no reason in the world
that those will speed up Bitmapsets, so why include them?

> v7 outperforms v4 by 29% (Query A)

I tested v7 with query-a and I also see additional gains. However,
it's entirely down to your changes to bms_is_subset(). It seems, by
chance, with the given Bitmapsets that looping backwards for the given
sets is able to determine the result more quickly

Here's some results from "perf top"

query-a
v4

  30.08%  postgres          [.] bms_is_subset
  15.84%  postgres          [.] create_join_clause
  13.54%  postgres          [.] bms_equal
  11.03%  postgres          [.] get_eclass_for_sort_expr
   8.53%  postgres          [.] generate_implied_equalities_for_column
   3.11%  postgres          [.] generate_join_implied_equalities_normal
   1.03%  postgres          [.] add_child_rel_equivalences
   0.82%  postgres          [.] SearchCatCacheInternal
   0.73%  postgres          [.] AllocSetAlloc
   0.53%  postgres          [.] find_ec_member_matching_expr
   0.40%  postgres          [.] hash_search_with_hash_value
   0.36%  postgres          [.] palloc
   0.36%  postgres          [.] palloc0

latency average = 452.480 ms

v7
  20.51%  postgres          [.] create_join_clause
  15.33%  postgres          [.] bms_equal
  14.17%  postgres          [.] get_eclass_for_sort_expr
  12.05%  postgres          [.] bms_is_subset
  10.40%  postgres          [.] generate_implied_equalities_for_column
   3.90%  postgres          [.] generate_join_implied_equalities_normal
   1.34%  postgres          [.] add_child_rel_equivalences
   1.06%  postgres          [.] AllocSetAlloc
   1.00%  postgres          [.] SearchCatCacheInternal
   0.72%  postgres          [.] find_ec_member_matching_expr
   0.58%  postgres          [.] palloc0
   0.49%  postgres          [.] palloc
   0.47%  postgres          [.] hash_search_with_hash_value
   0.44%  libc.so.6         [.] __memmove_avx_unaligned_erms


latency average = 350.543 ms

modified v7's bms_is_subset to go forwards then I get latency average
= 445.987 ms.

If I add some debugging to bms_is_subset to have it record how many
words it checks, I see:

postgres=# select sum(nwords) from forward;
    sum
-----------
 181490660
(1 row)

postgres=# select sum(nwords) from backwards;
   sum
----------
 11322564
(1 row)

So, it took about 181 million loops in bms_is_member to plan query-a
when looping forward, but only 11 million when looping backwards.

I think unless you've got some reason that you're able to justify why
we're always more likely to have to perform fewer word checks in
bms_is_subset() by looping backwards instead of forwards then I think
the performance gains you're showing here only happen to show better
results due to the given workload.  It's just as easy to imagine that
you'll apply the equivalent slowdown for some other workload where the
initial words differ but all the remaining words all match.

This seems equivalent to someone suggesting that looping backwards in
list_member() is better than looping forwards because it'll find the
member more quickly.  I can't imagine us ever considering that would
be a good change to make and I think the same for bms_is_member().

David

On Mon, 26 Jun 2023 at 12:55, Ranier Vilela <ranier.vf@gmail.com> wrote:
> Have you seen bms_compare?
> For some reason someone thought it would be better to loop backward the array.

That's nothing to do with efficiency. It's related to behaviour. Have
a look at the function's header comment, it's trying to find the set
with the highest value member.  It wouldn't make much sense to start
at the lowest-order words for that.

David

On Mon, 26 Jun 2023 at 12:55, Ranier Vilela <ranier.vf@gmail.com> wrote:
>
> Em dom., 25 de jun. de 2023 às 17:49, David Rowley <dgrowleyml@gmail.com> escreveu:
>>
>> There's no reason in the world
>> that those will speed up Bitmapsets, so why include them?
>
> Of course optimization is the most important thing,
> but since you're going to touch the source, why not make it more readable.

Have a look at [1]. In particular "Reasons your patch might be
returned" and precisely "Reformatting lines that haven't changed"

That entire page is quite valuable and I'd recommend having a read of all of it.

David

[1] https://wiki.postgresql.org/wiki/Submitting_a_Patch