Re: Speeding Up Bitmapset

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.