Switching to 64-bit Bitmapsets

As many of you will know, part of my planned work for PG12 is to
further improve the performance of querying partitioned tables. Amit
Langote is doing quite a bit of work on the planner side of things to
remove the per-partition overhead to reduce that to just for
partitions that survive partition pruning. I've mostly turned my
attention to tuning the executor.

Back in PG11, we got faster partition pruning and also run-time
partition pruning. The pruning code uses Bitmapsets to communicate
which partitions survived partition pruning. When many partitions
exist, these Bitmapsets can become quite large, quite a bit larger
than Bitmapsets were designed to be.

A comment in bitmapset.c mentions:

* A bitmap set can represent any set of nonnegative integers, although
* it is mainly intended for sets where the maximum value is not large,
* say at most a few hundred.

I imagine the reason for this comment is that we must allocate storage
space for all bits below the more significant set bit. 64-bit sets
don't change that, but they do speed up various operations that are
commonly performed on Bitmapsets:

* Reduces the number of memory allocations by half for incrementally built sets.
* Faster skipping of 0 words. This improves bms_num_members,
bms_next_member, bms_prev_member for sparsely populated sets.
* Sets can be copied more quickly with bms_copy()
* Improvements to various other operations; bms_overlap,
bms_nonempty_difference, bms_singleton_member, to name a few.

If I patch master with [1] to delay the locking of partitions until
after run-time pruning, then I'm able to see a small gain in
performance with a 10k partition partitioned table. Currently, the
improvement is only around 1%, but at the moment the TPS of the query
is just around 900 tps. I have local patches which push this to around
25k tps, so that 1% overhead becomes much larger in that case.

I tried to design a benchmark that exercises a large Bitmapset. The
32-bit version (master) will use 313 bitmapwords to store this and the
patched version uses just 157 words.

create table listp (a int) partition by list(a);
select 'create table listp'||x::text || ' partition of listp for
values in('||x::text||');' from generate_Series(1,10000)x;
\gexec

select.sql:
\set p_a 5000
select * from listp where a = :p_a and a > (select 0);

Patched:

$ pgbench -n -f select.sql -T 60 -M prepared postgres

tps
901.570528
976.756117
906.503725
932.156778
942.404224
960.889453
962.468714
907.756816
940.468028
906.351704
978.957677
Unpatched:

$ pgbench -n -f select.sql -T 60 -M prepared postgres

tps
903.4159
941.853886
913.956495
949.313422
907.267227
964.118809
941.43603
952.701788
916.757846
929.572794
891.220856
917.235864

Average increase = 0.89%, median = 1.17%

I've attached the trivial patch which implements 64-bit Bitmapsets.

One caveat about this may be that it will likely slow performance for
32-bit machines. My current thinking about that is that such a
platform is likely not that common a target for the latest version of
PostgreSQL. Even mobile phones and Raspberry PIs are all 64-bit these
days. However, I doubt it would take much more effort to maintain
using 32-bit sets on 32-bit machines. If someone feels strongly about
that then I can adjust the patch to allow that.

I'm going to add this to the January commitfest.

[1] https://commitfest.postgresql.org/21/1897/

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services