pgsql: Have ExecFindPartition cache the last found partition

Have ExecFindPartition cache the last found partition

Here we add code which detects when ExecFindPartition() continually finds
the same partition and add a caching layer to improve partition lookup
performance for such cases.

Both RANGE and LIST partitioned tables traditionally require a binary
search for the set of Datums that a partition needs to be found for. This
binary search is commonly visible in profiles when bulk loading into a
partitioned table.  Here we aim to reduce the overhead of bulk-loading
into partitioned tables for cases where many consecutive tuples belong to
the same partition and make the performance of this operation closer to
what it is with a traditional non-partitioned table.

When we find the same partition 16 times in a row, the next search will
result in us simply just checking if the current set of values belongs to
the last found partition.  For LIST partitioning we record the index into
the PartitionBoundInfo's datum array.  This allows us to check if the
current Datum is the same as the Datum that was last looked up.  This
means if any given LIST partition supports storing multiple different
Datum values, then the caching only works when we find the same value as
we did the last time.  For RANGE partitioning we simply check if the given
Datums are in the same range as the previously found partition.

We store the details of the cached partition in PartitionDesc (i.e.
relcache) so that the cached values are maintained over multiple
statements.

No caching is done for HASH partitions.  The majority of the cost in HASH
partition lookups are in the hashing function(s), which would also have to
be executed if we were to try to do caching for HASH partitioned tables.
Since most of the cost is already incurred, we just don't bother.  We also
don't do any caching for LIST partitions when we continually find the
values being looked up belong to the DEFAULT partition.  We've no
corresponding index in the PartitionBoundInfo's datum array for this case.
We also don't cache when we find the given values match to a LIST
partitioned table's NULL partition.  This is so cheap that there's no
point in doing any caching for this.  We also don't cache for a RANGE
partitioned table's DEFAULT partition.

There have been a number of different patches submitted to improve
partition lookups. Hou, Zhijie submitted a patch to detect when the value
belonging to the partition key column(s) were constant and added code to
cache the partition in that case.  Amit Langote then implemented an idea
suggested by me to remember the last found partition and start to check if
the current values work for that partition.  The final patch here was
written by me and was done by taking many of the ideas I liked from the
patches in the thread and redesigning other aspects.

Discussion: https://postgr.es/m/OS0PR01MB571649B27E912EA6CC4EEF03942D9%40OS0PR01MB5716.jpnprd01.prod.outlook.com
Author: Amit Langote, Hou Zhijie, David Rowley
Reviewed-by: Amit Langote, Hou Zhijie

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/3592e0ff98b130c428c1d8091fc61767f7608732

Modified Files
--------------
src/backend/executor/execPartition.c | 192 +++++++++++++++++++++++++++++++----
src/backend/partitioning/partdesc.c  |   6 ++
src/include/partitioning/partdesc.h  |  25 +++++
3 files changed, 204 insertions(+), 19 deletions(-)