pgsql: Faster partition pruning

Faster partition pruning

Add a new module backend/partitioning/partprune.c, implementing a more
sophisticated algorithm for partition pruning. The new module uses each
partition's "boundinfo" for pruning instead of constraint exclusion,
based on an idea proposed by Robert Haas of a "pruning program": a list
of steps generated from the query quals which are run iteratively to
obtain a list of partitions that must be scanned in order to satisfy
those quals.

At present, this targets planner-time partition pruning, but there exist
further patches to apply partition pruning at execution time as well.

This commit also moves some definitions from include/catalog/partition.h
to a new file include/partitioning/partbounds.h, in an attempt to
rationalize partitioning related code.

Authors: Amit Langote, David Rowley, Dilip Kumar
Reviewers: Robert Haas, Kyotaro Horiguchi, Ashutosh Bapat, Jesper Pedersen.
Discussion: https://postgr.es/m/098b9c71-1915-1a2a-8d52-1a7a50ce79e8@lab.ntt.co.jp

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/9fdb675fc5d2de825414e05939727de8b120ae81

Modified Files
--------------
src/backend/Makefile | 3 +-
src/backend/catalog/partition.c | 135 +-
src/backend/nodes/copyfuncs.c | 56 +-
src/backend/nodes/equalfuncs.c | 13 -
src/backend/nodes/nodeFuncs.c | 25 +
src/backend/nodes/outfuncs.c | 44 +-
src/backend/nodes/readfuncs.c | 30 +
src/backend/optimizer/path/allpaths.c | 124 +-
src/backend/optimizer/path/indxpath.c | 4 +-
src/backend/optimizer/plan/planner.c | 99 +-
src/backend/optimizer/prep/prepunion.c | 47 +-
src/backend/optimizer/util/plancat.c | 66 +-
src/backend/optimizer/util/relnode.c | 8 +
src/backend/partitioning/Makefile | 17 +
src/backend/partitioning/partprune.c | 2782 +++++++++++++++++++++++++
src/include/catalog/catversion.h | 2 +-
src/include/catalog/partition.h | 3 +-
src/include/catalog/pg_opfamily.h | 3 +
src/include/nodes/nodes.h | 4 +-
src/include/nodes/primnodes.h | 75 +
src/include/nodes/relation.h | 48 +-
src/include/optimizer/planner.h | 5 -
src/include/partitioning/partbounds.h | 124 ++
src/include/partitioning/partprune.h | 49 +
src/test/regress/expected/inherit.out | 4 +-
src/test/regress/expected/partition_prune.out | 515 ++++-
src/test/regress/sql/partition_prune.sql | 125 +-
27 files changed, 3994 insertions(+), 416 deletions(-)