pgsql: Support partition pruning at execution time

Support partition pruning at execution time

Existing partition pruning is only able to work at plan time, for query
quals that appear in the parsed query. This is good but limiting, as
there can be parameters that appear later that can be usefully used to
further prune partitions.

This commit adds support for pruning subnodes of Append which cannot
possibly contain any matching tuples, during execution, by evaluating
Params to determine the minimum set of subnodes that can possibly match.
We support more than just simple Params in WHERE clauses. Support
additionally includes:

1. Parameterized Nested Loop Joins: The parameter from the outer side of the
join can be used to determine the minimum set of inner side partitions to
scan.

2. Initplans: Once an initplan has been executed we can then determine which
partitions match the value from the initplan.

Partition pruning is performed in two ways. When Params external to the plan
are found to match the partition key we attempt to prune away unneeded Append
subplans during the initialization of the executor. This allows us to bypass
the initialization of non-matching subplans meaning they won't appear in the
EXPLAIN or EXPLAIN ANALYZE output.

For parameters whose value is only known during the actual execution
then the pruning of these subplans must wait. Subplans which are
eliminated during this stage of pruning are still visible in the EXPLAIN
output. In order to determine if pruning has actually taken place, the
EXPLAIN ANALYZE must be viewed. If a certain Append subplan was never
executed due to the elimination of the partition then the execution
timing area will state "(never executed)". Whereas, if, for example in
the case of parameterized nested loops, the number of loops stated in
the EXPLAIN ANALYZE output for certain subplans may appear lower than
others due to the subplan having been scanned fewer times. This is due
to the list of matching subnodes having to be evaluated whenever a
parameter which was found to match the partition key changes.

This commit required some additional infrastructure that permits the
building of a data structure which is able to perform the translation of
the matching partition IDs, as returned by get_matching_partitions, into
the list index of a subpaths list, as exist in node types such as
Append, MergeAppend and ModifyTable. This allows us to translate a list
of clauses into a Bitmapset of all the subpath indexes which must be
included to satisfy the clause list.

Author: David Rowley, based on an earlier effort by Beena Emerson
Reviewers: Amit Langote, Robert Haas, Amul Sul, Rajkumar Raghuwanshi,
Jesper Pedersen
Discussion: https://postgr.es/m/CAOG9ApE16ac-_VVZVvv0gePSgkg_BwYEV1NBqZFqDR2bBE0X0A@mail.gmail.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/499be013de65242235ebdde06adb08db887f0ea5

Modified Files
--------------
doc/src/sgml/perform.sgml | 12 +
src/backend/commands/explain.c | 51 +-
src/backend/executor/execPartition.c | 419 +++++++++
src/backend/executor/nodeAppend.c | 268 ++++--
src/backend/nodes/copyfuncs.c | 21 +
src/backend/nodes/nodeFuncs.c | 28 +-
src/backend/nodes/outfuncs.c | 28 +
src/backend/nodes/readfuncs.c | 20 +
src/backend/optimizer/path/allpaths.c | 12 +-
src/backend/optimizer/path/joinrels.c | 2 +-
src/backend/optimizer/plan/createplan.c | 45 +-
src/backend/optimizer/plan/planner.c | 8 +-
src/backend/optimizer/prep/prepunion.c | 6 +-
src/backend/optimizer/util/pathnode.c | 26 +-
src/backend/partitioning/partprune.c | 267 +++++-
src/include/executor/execPartition.h | 77 ++
src/include/nodes/execnodes.h | 12 +-
src/include/nodes/nodes.h | 1 +
src/include/nodes/plannodes.h | 5 +
src/include/nodes/primnodes.h | 23 +
src/include/optimizer/pathnode.h | 2 +-
src/include/partitioning/partprune.h | 14 +
src/test/regress/expected/partition_prune.out | 1135 +++++++++++++++++++++++++
src/test/regress/sql/partition_prune.sql | 344 ++++++++
24 files changed, 2714 insertions(+), 112 deletions(-)