Remove trailing zero words from Bitmapsets
authorDavid Rowley <drowley@postgresql.org>
Tue, 4 Jul 2023 00:34:48 +0000 (12:34 +1200)
committerDavid Rowley <drowley@postgresql.org>
Tue, 4 Jul 2023 00:34:48 +0000 (12:34 +1200)
commita8c09daa8bb1d741bb8b3d31a12752448eb6fb7c
tree198beb47d60d9da82d7833afe80d46823a9605a6
parent44e73a498c5f3ad7e39dc70821c2d8316d3207f2
Remove trailing zero words from Bitmapsets

Prior to this, Bitmapsets could contain trailing words which had no
members set.  Many places in bitmapset.c had to loop over trailing words
to check for empty words.  If we ensure we always remove these trailing
zero words then we can perform various optimizations such as fast
pathing bms_is_subset to return false when 'a' has more words than 'b'.
A similar optimization is possible in bms_equal.  Both of these together
can yield quite significant performance increases in the query planner
when querying a partitioned table with around 100 or more partitions.

While we're at it, since the minimum number of words a Bitmapset can
contain is 1, we can make use of do/while loops instead of for loops
when looping over all words in a set.  This means checking the loop
condition 1 less time, which for single-word sets cuts the loop
condition checks in half.

Author: David Rowley
Reviewed-by: Yuya Watari
Discussion: https://postgr.es/m/CAApHDvr5O41MuUjw0DQKqmAnv7QqvmLqXReEd5o4nXTzWp8-+w@mail.gmail.com
src/backend/nodes/bitmapset.c