Re: [HACKERS] path toward faster partition pruning

On 2018/03/28 12:58, David Rowley wrote:
> On 27 March 2018 at 23:42, Amit Langote <Langote_Amit_f8(at)lab(dot)ntt(dot)co(dot)jp> wrote:
>> I have managed to make the recursion go away in the attached updated
>> version. I guess that's the result of employing the idea of a "output
>> register" for individual pruning steps as mentioned in Robert's email
>> upthread where he detailed the "pruning steps" approach [1].
>
> Thanks for making that work. I've only glanced at the patch, and not
> taken enough time to understand how the new parts work yet.
>
> In the meantime, I've attached some fixes for v41 which I previously
> submitted for v40.

Thank you. I've merged it.

Also, I have redesigned how we derive partition indexes after running
pruning steps. Previously, for each step we'd determine the indexes of
"partitions" that are not pruned leading to a list partition not being
pruned sometimes, as shown in the two recent examples. Instead, in the
new approach, we only keep track of the indexes of the "datums" that
satisfy individual pruning steps (both base pruning steps and combine
steps) and only figure out the partition indexes after we've determined
set of datums that survive all pruning steps. That is, after we're done
executing all pruning steps. Whether we need to scan special partitions
like null-only and default partition is tracked along with datum indexes
for each step. With this change, pruning works as expected in both examples:

create table lp (a char) partition by list (a);
create table lp_ad partition of lp for values in ('a', 'd');
create table lp_bc partition of lp for values in ('b', 'c');
create table lp_default partition of lp default;
explain (costs off) select * from lp where a > 'a' and a < 'd';
QUERY PLAN
-----------------------------------------------------------
Append
-> Seq Scan on lp_bc
Filter: ((a > 'a'::bpchar) AND (a < 'd'::bpchar))
-> Seq Scan on lp_default
Filter: ((a > 'a'::bpchar) AND (a < 'd'::bpchar))
(5 rows)

CREATE TABLE listp (a INT) PARTITION BY LIST(a);
CREATE TABLE listp1_3 PARTITION OF listp FOR VALUES IN (1, 3);
EXPLAIN SELECT * FROM listp WHERE a > 1 AND a < 3;
QUERY PLAN
------------------------------------------
Result (cost=0.00..0.00 rows=0 width=4)
One-Time Filter: false
(2 rows)

Moreover, with pruning now working at a high-level with datum indexes
instead of partition indexes, pruning for PartitionPruneStepOpNe is
simplified greatly. We simply delete from a bitmapset initially
containing the indexes of all datums in boundinfo the indexes of those
that appear in the query. So:

explain (costs off) select * from lp where a <> 'a' and a <> 'd';
QUERY PLAN
-------------------------------------------------------------
Append
-> Seq Scan on lp_bc
Filter: ((a <> 'a'::bpchar) AND (a <> 'd'::bpchar))
-> Seq Scan on lp_default
Filter: ((a <> 'a'::bpchar) AND (a <> 'd'::bpchar))
(5 rows)

where we delete indexes of 'a' and 'd' from the bitmapset initially
containing indexes of all datums, leaving us with only those of 'b' and
'c'. Also, the default partition is scanned as it would always be for a
PartitionPruneStepOpNe step.

Attached is the updated set of patches, which contains other miscellaneous
changes such as updated comments, beside the main changes described above.

Regards,
Amit