Re: Record a Bitmapset of non-pruned partitions

On Thu, 1 Jul 2021 at 17:49, Amit Langote <amitlangote09(at)gmail(dot)com> wrote:
> Given that you're proposing more uses for live_parts, maybe he'd be
> open to the idea.

Just to make sure the new field in the 0001 patch gets good enough
use, I've attached the patch which includes more usages of the field.

0002 adds a new field named interleaved_parts to PartitionBoundInfo
which is populated for LIST partitioned tables with any partitions
which have interleaved values, e.g FOR VALUES IN(3,5) and another
partition with FOR VALUES IN(4), the 3,5 partition is "interleaved"
around the partition for 4.

This combined with recording "live_parts" in the 0001 patch allows us
to do ordered partition scans in many more cases for LIST partitioning
and 1 more case with RANGE partitioning.

create table mclparted (a int) partition by list(a);
create table mclparted1 partition of mclparted for values in(1);
create table mclparted2 partition of mclparted for values in(2);
create table mclparted3_5 partition of mclparted for values in(3,5);
create table mclparted4 partition of mclparted for values in(4);
create index on mclparted (a);

set enable_bitmapscan=0;
set enable_sort=0;

-- ordered scan using Append
explain (costs off) select * from mclparted where a in(1,2) order by a;
QUERY PLAN
------------------------------------------------------------------------
Append
-> Index Only Scan using mclparted1_a_idx on mclparted1 mclparted_1
Index Cond: (a = ANY ('{1,2}'::integer[]))
-> Index Only Scan using mclparted2_a_idx on mclparted2 mclparted_2
Index Cond: (a = ANY ('{1,2}'::integer[]))

-- no ordered scan due to interleaved partition. Must use Merge Append
explain (costs off) select * from mclparted where a in(3,4) order by a;
QUERY PLAN
----------------------------------------------------------------------------
Merge Append
Sort Key: mclparted.a
-> Index Only Scan using mclparted3_5_a_idx on mclparted3_5 mclparted_1
Index Cond: (a = ANY ('{3,4}'::integer[]))
-> Index Only Scan using mclparted4_a_idx on mclparted4 mclparted_2
Index Cond: (a = ANY ('{3,4}'::integer[]))

Currently, this is a bit more strict than maybe it needs to be. I'm
disabling the optimisation if any interleaved partitions remain after
pruning, however, it would be ok to allow them providing their
interleaved partner(s) were pruned. I think making that work might be
a bit more costly as we'd need to track all partitions that were
interleaved with each interleaved partition and ensure those were all
pruned. As far as I can see that requires storing a Bitmapset per
interleaved partition and makes the whole thing not so cheap. I'd
really like to keep all this stuff cheap as possible. That's why I
ended up calculating the interleaved partitions in
create_list_bounds() rather than partitions_are_ordered().

The good news is that the code in partitions_are_ordered() became even
more simple as a result of this change. We can do ordered scan simply
when !bms_overlap(live_parts, boundinfo->interleaved_parts).

The additional case we can now allow for RANGE partition is that we
can now do ordered scan when there is a DEFAULT partition but it was
pruned. Previously we had to disable the optimisation when there was a
DEFAULT partition as we had no idea if it was pruned or not.

David