Re: path toward faster partition pruning

On 2017/08/21 15:37, Amit Langote wrote:
> Meanwhile, I thought I'd share a couple of patches that implement some
> restructuring of the planner code related to partitioned table inheritance
> planning that I think would be helpful. They are to be applied on top of
> the patches being discussed at [1]. Note that these patches themselves
> don't implement the actual code that replaces constraint exclusion as a
> method of performing partition pruning. I will share that patch after
> debugging it some more.
>
> The next patch that will implement
> actual partition-pruning will add some more code that will run under
> find_partitions_for_query().

Attached is now also the set of patches that implement the actual
partition-pruning logic, viz. the last 3 patches (0004, 0005, and 0006) of
the attached.

Because the patch helps avoid performing constraint exclusion on *all*
partitions for a given query, one might expect this to improve performance
for queries on partitioned tables and scale to a fairly large number of
partitions. Here are some numbers for the partitioned table and the query
shown below:

\d+ ptab
Columns: (a date, b int, c text)
Partition key: RANGE (a, b)
Partitions:
ptab_00001 FOR VALUES FROM ('2017-08-31', 1) TO ('2017-08-31', 1000),
ptab_00002 FOR VALUES FROM ('2017-08-31', 1000) TO ('2017-08-31', 2000),
ptab_00003 FOR VALUES FROM ('2017-08-31', 2000) TO ('2017-08-31', 3000),
ptab_00004 FOR VALUES FROM ('2017-08-31', 3000) TO ('2017-08-31', 4000),
ptab_00005 FOR VALUES FROM ('2017-08-31', 4000) TO ('2017-08-31', 5000),

ptab_00006 FOR VALUES FROM ('2017-09-01', 1) TO ('2017-09-01', 1000),
ptab_00007 FOR VALUES FROM ('2017-09-01', 1000) TO ('2017-09-01', 2000),

...
ptab_NNNNN FOR VALUES FROM (..., 4000) TO (..., 5000),

A query that prunes all partitions (empty result!):

explain select * from ptab where a < '2017-08-31';

Comparison of the average response times (in milliseconds) after running
the same query 100 times using pgbench against the database:

#: Number of partitions of ptab
c_e: Constraint exclusion
f_p: Fast pruning

# c_e f_p
===== ===== ====
10 0.7 0.4
50 1.8 0.6
100 3.2 0.8
500 16.8 2.7
1000 36.2 5.0
2000 79.7 10.2
5000 214.7 27.0
10000 443.6 64.8

For each partitioned table in a given partition tree (provided it is not
pruned to begin with), the query's clauses are matched to its partition
key and from the matched clauses, a pair of bounding keys (Datum tuples
with <= key->partnatts values for possibly a prefix of a multi-column key)
is generated. They are passed to partition.c: get_partitions_for_keys()
as Datum *minkeys and Datum *maxkeys. A list of partitions covering that
key range is returned. When generating that list, whether a particular
scan key is inclusive or not is considered along with the partitioning
strategy. It should be possible to support hash partitioning with
(hopefully) minimal changes to get_partitions_for_keys().

There are still certain limitations on the planner side of things:

1. OR clauses are not counted as contributing toward bounding scan keys;
currently only OpExprs and NullTests are recognized, so an OR clause
would get skipped from consideration when generating the bounding keys
to pass to partition.c

2. Redundant clauses are not appropriately pre-processed; so if a query
contains a = 10 and a > 1, the latter clause will be matched and
partitions holding values with a > 1 and a < 10 will not be pruned,
even if none of their rows will pass the query's condition

Fixing these limitations, adding more regression tests and implementing
some of the things suggested by Ashutosh Bapat [1] to prevent conflicting
changes with some preparatory patches in the partitionwise-join patch
series [2] are TODOs.

Adding this to CF-201709 as "faster partition pruning in planner".

To try out the attached patches: apply the patches posted at [3] on HEAD
and then apply these

Thanks,
Amit

[1]
https://postgr.es/m/CAFjFpRdb_fkmJHFjvAbB%2BLn0t45fWjekLd5pY%3Dsv%2BeAhBAKXPQ%40mail.gmail.com

[2]
https://postgr.es/m/CAFjFpRd9Vqh_=-Ldv-XqWY006d07TJ+VXuhXCbdj=P1jukYBrw@mail.gmail.com

[3]
https://www.postgresql.org/message-id/2124e99f-9528-0f71-4e10-ac7974dd7077%40lab.ntt.co.jp