[PoC] Partition path cache
Hello,
I have a patch that seems to be worth community attention.
It is just a PoC for now, but I wonder if it makes sense to continue
development of the idea.
Preface
=======
My team is developing PostgreSQL fork optimized for high OLTP loads.
Our customers use databases (1-10 TB) with big tables. Often these tables are
big and split on sections. For example, we have tables with almost
thousand sections. In most cases, those sections have a similar set of indexes
and contain similar data. Often this partitioned table has multilevel structure
(for example, a per-year section has a per-quarter section, and a per-quarter
section in turn has a per-month simple relation sections).
During the analysis of the planning procedure, we found that the planner
we found that the planner in PostgreSQL 15.7 spents a lot of time building
access paths.
We also knew that fetching information from Syscache takes time. In our case
on PostgreSQL 15.7, if the planner spent 5.7 sec. for planning the query
at the first time, at the second time it takes 4.4 sec.
So fetching data from pg_catalog is not the main reason for slow planning.
We backported new access path build algorithms from PostgreSQL 17 (which
optimizes match_pathkeys_to_index()) and it takes effect:
planner spent 1090 ms for planning query at first time and 320 ms for
second time.
But we still think that planners make unnecessary jobs when building all
types of paths for every section. So we implemented a feature named
"partition path cache" (see next section), and now planner spent 970 ms for
planning query at the first time and 240 ms for the second time.
The comparison table is given below.
PostgreSQL | first time | second time | execution
version | planning, ms | planning, ms | time, ms
-------------------------------------+---------------+--------------+----------
PostrgeSQL 15.7 | 5713 | 4402 | 55
-------------------------------------+---------------+--------------+----------
PostrgeSQL 15.7 + v17 improvements | 1093 | 320 | 52
-------------------------------------+---------------+--------------+----------
PostrgeSQL 15.7 + v17 improvements + | 967 | 240 | 52
partition path cache | | |
Partition path cache
====================
The partition path cache aims to speed up planning for partition scan paths.
Path cache doesn't copy and transform Path nodes directly due to the absence of
Path nodes copy functions. The main aim of this patch is to prove the assumption
that partitions of the same relation that have similar sets of indexes may use
similar access path types. The cache optimizes access path search using the
following methods:
- Omit building of paths other than selected path types (if sequence scan is
selected, no index or bitmap scan paths will be built).
- Omit checking for indexes that are not involved in the selected path on
index or bitmap access path building.
Partition identification
------------------------
For selection of similar partitions, two new ID types are calculated:
- part_group_id (field of RelOptInfo) - hash sum of parent relation id,
number of parent relation's partitions, and 'index_group_id' of all
indexes. This ID is calculated only for partitions (not for any other regular
relations) at get_relation_info();
- index_group_id (field of IndexOptInfo) - hash sum of fields at corresponding
pg_index row (indnatts, indnkeyatts, indisunique, indnullsnotdistinct,
indisprimary, indisexclusion, indimmediate, indkey, indexprs, indpred).
This ID is calculated only for partition's indexes at get_index_group_id().
The algorithm
-------------
During construction of an access path for a partitioned relation, the cache
recursively performs the following steps:
On filling up a RelOptInfo structure for a partition that is a regular
relation, planner calculates part_group_id for it (and index_group_id for its
indexes).
If the cache has not been allocated yet it will be created on the first time the
Append Path for (root) a partitioned relation be requested (this level of
recursive access path building process marked as level 1 in the cache control
structure).
When planner builds an access path list for partitions, it uses the cache
only if a parent of the current partition has at least
partition_path_cache_threshold partitions. If cache can be used, planner
seeks a cache entry with the same values of part_group_id and rtable index as
the parent has. If the entry not found, planner builds access paths list using
standard algorithm and stores cheapest_total_path properties (pathtype, and list
of index_group_id for involved indexes) at the cache.
If the entry found, planner builds only a short list of paths (with the same
pathtype and short list of indexes with the same index_group_id). Building of
this access path shortcut can fail, resulting in the path not being added
into the cache (reason may be part_group_id/index_group_id collision that is
unlikely). In case the shortcut creation failed, standard algorithm for index
scans is used (for index scan paths only) with full list of available indexes.
If an access path still not found planner uses standard access path building
algorithm and rewrites content of the current entry in the cache.
As soon as the building process of Append Path for the root relation
finished, the cache are deleted (append path build finished of recursive scan
path build marked as level 1 in the cache control structure).
GUC parameters
--------------
- partition_path_cache_threshold: integer, default 0, minimum 0,
maximum INT32_MAX, minimum number of partitions for use the access path
cache, for disabling the feature, set it to 0 or 1.
- partition_path_cache_debug: boolean, default is off, print debug messages
for partition access path cache (used for tests).
Feature improvements
--------------------
The cache may construct an access path for the current partition from scratch
using path from the first partition of a group as a template.
This improvement can be the next step in development of the feature,
but for now it seems too complicated for the PoC solution.
index_group_id value depends only on pg_index row content, so it may be
calculated once at index creation or altering and stored at new pg_index
column (may be we would better to add "key=value" text[] column as
reloptions at pg_class).
Patch
=====
I attached a patch, which may be applied on top of REL_17_0
(d7ec59a63d745ba74fba0e280bbf85dc6d1caa3e)
Path tests
==========
The following table shows test results. Qureries and graphs are attached.
Testing method
--------------
For every combination of partition quantity and binary version query performed
in a single session at a time. 9 sessions run a single query, and then
single session runs 11 queries. First 10 planning times taken to get average
value at column "first plan time," second 10 planning times-for
"second plan time". All 20 execution times used to get average
value at column "execute time".
I took queries from this thread
(thanks Yuya Watari <watari(dot)yuya(at)gmail(dot)com>):
/messages/by-id/CAJ2pMkZNCgoUKSE+_5LthD+KbXKvq6h2hQN8Esxpxd+cxmgomg@mail.gmail.com
+-------------------+-------+----------------------+----------------------+----------------------+
| | part. | first plan time, ms | second plan time, ms | execute time, ms |
| PostgreSQL ver. | qty. | ( diff vs 17.0, %) | ( diff vs 17.0, %) | ( diff vs 17.0, %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 2 | 3.1031 | 0.8080 | 2.4993 |
| 17.0 + path cache | | 3.1228 (+0.63 %) | 0.8010 (-0.87 %) | 2.5468 (+1.90 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 4 | 4.5636 | 1.1161 | 4.8888 |
| 17.0 + path cache | | 4.6028 (+0.86 %) | 1.1105 (-0.50 %) | 4.9687 (+1.63 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 8 | 7.5774 | 1.7725 | 9.6441 |
| 17.0 + path cache | | 7.6790 (+1.34 %) | 1.7703 (-0.12 %) | 9.7673 (+1.28 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 12 | 10.7537 | 2.4675 | 14.3911 |
| 17.0 + path cache | | 10.7554 (+0.02 %) | 2.4729 (+0.22 %) | 14.4567 (+0.46 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
Now we reach partition_path_cache_threshold = 16
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 16 | 13.7407 | 3.1827 | 19.1492 |
| 17.0 + path cache | | 12.4823 (-9.16 %) | 1.8434 (-42.08%) | 19.5624 (+2.16 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 24 | 20.0194 | 4.7433 | 28.6824 |
| 17.0 + path cache | | 17.8342 (-10.92%) | 2.5668 (-45.89%) | 29.7417 (+3.69 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 32 | 26.7856 | 6.5625 | 38.5652 |
| 17.0 + path cache | | 23.2506 (-13.20%) | 3.3558 (-48.86%) | 38.6931 (+0.33 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 48 | 40.1678 | 10.5715 | 57.2730 |
| 17.0 + path cache | | 34.2525 (-14.73%) | 5.1433 (-51.35%) | 57.7580 (+0.85 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 64 | 54.1985 | 15.4603 | 76.8278 |
| 17.0 + path cache | | 45.8584 (-15.39%) | 7.4850 (-51.59%) | 77.8530 (+1.33 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 96 | 84.8551 | 27.4972 | 115.8411 |
| 17.0 + path cache | | 68.7432 (-18.99%) | 13.0090 (-52.69%) | 116.0379 (+0.17 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 128 | 118.6081 | 43.0581 | 155.4576 |
| 17.0 + path cache | | 95.0978 (-19.82%) | 20.0807 (-53.36%) | 158.0958 (+1.70 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 256 | 296.5312 | 149.4680 | 322.6102 |
| 17.0 + path cache | | 218.3300 (-26.37%) | 72.0222 (-51.81%) | 325.5720 (+0.92 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 384 | 544.4308 | 318.3988 | 487.2509 |
| 17.0 + path cache | | 380.6742 (-30.08%) | 159.0805 (-50.04%) | 489.8570 (+0.53 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 512 | 855.6576 | 562.1585 | 699.9267 |
| 17.0 + path cache | | 583.7852 (-31.77%) | 289.3476 (-48.53%) | 692.7862 (-1.02 %) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 768 | 1792.3726 | 1354.0600 | 1179.9674 |
| 17.0 + path cache | | 1296.3144 (-27.68%) | 850.4178 (-37.19%) | 1030.4456 (-12.67%) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 1024 | 3102.6455 | 2496.3959 | 1564.7481 |
| 17.0 + path cache | | 2289.7010 (-26.20%) | 1708.7799 (-31.55%) | 1375.4829 (-12.10%) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 1280 | 4918.5399 | 4093.4833 | 1968.9766 |
| 17.0 + path cache | | 3654.1266 (-25.71%) | 2878.6720 (-29.68%) | 1726.8803 (-12.30%) |
+-------------------+-------+----------------------+----------------------+----------------------+
| 17.0 | 1536 | 7230.7103 | 6405.0386 | 2488.1614 |
| 17.0 + path cache | | 5686.7774 (-21.35%) | 4635.5728 (-27.63%) | 2101.5021 (-15.54%) |
+-------------------+-------+----------------------+----------------------+----------------------+
Attachments:
0001-Partition-path-cache.patchapplication/octet-stream; name=0001-Partition-path-cache.patchDownload
From 1a6dcb1b0f144e07e0b2e11967c53a78208fadcc Mon Sep 17 00:00:00 2001
From: Bykov Ivan <i.bykov@modernsys.ru>
Date: Tue, 22 Oct 2024 18:33:00 +0500
Subject: [PATCH] Partition path cache
The partition path cache aims to speed up planning for partition scan paths.
Path cache doesn't copy and transform Path nodes directly due to the absence of
Path nodes copy functions. The main aim of this patch is to prove the assumption
that partitions of the same relation that have similar sets of indexes may use
similar access path types. The cache optimizes access path search using the following
methods:
- Omit building of paths other than selected path types (if sequence scan is selected,
no index or bitmap scan paths will be built).
- Omit checking for indexes that are not involved in the selected path on
index or bitmap access path building.
---
src/backend/optimizer/path/Makefile | 1 +
src/backend/optimizer/path/allpaths.c | 41 +-
src/backend/optimizer/path/pathcache.c | 625 ++++++++++++++++++
src/backend/optimizer/util/plancat.c | 85 +++
src/backend/utils/misc/Makefile | 1 +
src/backend/utils/misc/catalog_id.c | 415 ++++++++++++
src/backend/utils/misc/guc_tables.c | 23 +
src/backend/utils/misc/postgresql.conf.sample | 4 +-
src/include/nodes/pathnodes.h | 16 +
src/include/optimizer/pathnode.h | 1 +
src/include/optimizer/paths.h | 17 +
src/include/utils/catalog_id.h | 18 +
src/test/regress/expected/path_cache.out | 517 +++++++++++++++
src/test/regress/parallel_schedule | 2 +-
src/test/regress/sql/path_cache.sql | 221 +++++++
15 files changed, 1982 insertions(+), 5 deletions(-)
create mode 100644 src/backend/optimizer/path/pathcache.c
create mode 100644 src/backend/utils/misc/catalog_id.c
create mode 100644 src/include/utils/catalog_id.h
create mode 100644 src/test/regress/expected/path_cache.out
create mode 100644 src/test/regress/sql/path_cache.sql
diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile
index 1e199ff66f..d46d4062e4 100644
--- a/src/backend/optimizer/path/Makefile
+++ b/src/backend/optimizer/path/Makefile
@@ -20,6 +20,7 @@ OBJS = \
indxpath.o \
joinpath.o \
joinrels.o \
+ pathcache.o \
pathkeys.o \
tidpath.o
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 4895cee994..2c39667290 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -97,7 +97,6 @@ static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
Index rti, RangeTblEntry *rte);
static void set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel,
RangeTblEntry *rte);
-static void create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel);
static void set_rel_consider_parallel(PlannerInfo *root, RelOptInfo *rel,
RangeTblEntry *rte);
static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
@@ -469,14 +468,32 @@ static void
set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
Index rti, RangeTblEntry *rte)
{
+ bool path_store = false;
+
if (IS_DUMMY_REL(rel))
{
/* We already proved the relation empty, so nothing more to do */
}
else if (rte->inh)
{
+ bool partition_cache_enable = false;
+
+ /*
+ * Unlikely macro used because of less using the partition path cache
+ * is not so common case.
+ */
+ if (unlikely(PARTITION_PATH_CACHE_ENABLED &&
+ rel->nparts >= partition_path_cache_threshold))
+ {
+ partition_cache_enable = true;
+ partition_path_cache_begin();
+ }
+
/* It's an "append relation", process accordingly */
set_append_rel_pathlist(root, rel, rti, rte);
+
+ if (unlikely(partition_cache_enable))
+ partition_path_cache_end();
}
else
{
@@ -495,7 +512,18 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
}
else
{
- /* Plain relation */
+ /*
+ * Using the partition path cache is not a typical
+ * situation for this branch. More frequently, it's set
+ * access paths for regular relations. So it seems worth
+ * using the unlikely macro and checking cache usage
+ * conditions here because, in most cases, no
+ * partition_path_cache_create_paths() call is required.
+ */
+ if (unlikely(PARTITION_PATH_CACHE_ENABLED &&
+ PARTITION_GROUP_ID_VALID(rel->part_group_id)) &&
+ partition_path_cache_create_paths(root, rel, rte, &path_store))
+ break;
set_plain_rel_pathlist(root, rel, rte);
}
break;
@@ -559,6 +587,13 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
/* Now find the cheapest of the paths for this rel */
set_cheapest(rel);
+ /*
+ * Unlikely macro used because of less using the partition path cache is
+ * not so common case.
+ */
+ if (unlikely(path_store))
+ partition_path_cache_store(rel, rte);
+
#ifdef OPTIMIZER_DEBUG
pprint(rel);
#endif
@@ -790,7 +825,7 @@ set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
* create_plain_partial_paths
* Build partial access paths for parallel scan of a plain relation
*/
-static void
+void
create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel)
{
int parallel_workers;
diff --git a/src/backend/optimizer/path/pathcache.c b/src/backend/optimizer/path/pathcache.c
new file mode 100644
index 0000000000..1259b2546f
--- /dev/null
+++ b/src/backend/optimizer/path/pathcache.c
@@ -0,0 +1,625 @@
+/*-------------------------------------------------------------------------
+ *
+ * pathcache.c
+ * The partition path cache aims to speed up planning for partition scan paths.
+ *
+ * Path cache doesn't copy and transform Path nodes directly due to the absence
+ * of Path nodes copy functions. The main aim of this patch is to prove the
+ * assumption that partitions of the same relation that have similar sets of
+ * indexes may use similar access path types. The cache optimizes access path
+ * search using the following methods:
+ * - Omit building of paths other than selected path types (if sequence scan
+ * is selected, no index or bitmap scan paths will be built).
+ * - Omit checking for indexes that are not involved in the selected path on
+ * index or bitmap access path building.
+ *
+ * Partition identification
+ * ------------------------
+ *
+ * For selection of similar partitions, two new ID types are calculated:
+ * - part_group_id (field of RelOptInfo) - hash sum of parent relation id,
+ * number of parent relation’s partitions, and ‘index_group_id’ of all
+ * indexes. This ID is calculated only for partitions (not for any other
+ * regular relation) at get_relation_info();
+ * - index_group_id (field of IndexOptInfo) – hash sum of fields at
+ * corresponding pg_index row (indnatts, indnkeyatts, indisunique,
+ * indnullsnotdistinct, indisprimary, indisexclusion, indimmediate, indkey,
+ * indexprs, indpred). This ID is calculated only for partition's indexes
+ * at pg_index_id_form().
+ *
+ * The algorithm
+ * -------------
+ *
+ * During construction of an access path for a partitioned relation, the cache
+ * recursively performs the following steps:
+ *
+ * On filling up a RelOptInfo structure for a partition that is a regular
+ * relation, planner calculates part_group_id for it (and index_group_id for its
+ * indexes).
+ *
+ * If the cache has not been allocated yet it will be created on the first time
+ * the Append Path for (root) a partitioned relation be requested (this level of
+ * recursive access path building process marked as level 1 in the cache control
+ * structure).
+ *
+ * When planner builds an access path list for partitions, it uses the cache
+ * only if a parent of the current partition has at least
+ * partition_path_cache_threshold partitions. If cache can be used, planner
+ * seeks a cache entry with the same values of part_group_id and rtable index as
+ * the parent has. If the entry not found, planner builds access paths list
+ * using standard algorithm and stores cheapest_total_path properties (pathtype,
+ * and list of index_group_id for involved indexes) at the cache.
+ *
+ * If the entry found, planner builds only a short list of paths (with the same
+ * pathtype and short list of indexes with the same index_group_id). Building of
+ * this access path shortcut can fail, resulting in the path not being added
+ * into the cache (reason may be part_group_id/index_group_id collision that is
+ * unlikely).
+ * In case the shortcut creation failed, standard algorithm for index scans is
+ * used (for index scan paths only) with full list of available indexes. If an
+ * access path still not found planner uses standard access path building
+ * algorithm and rewrites content of the current entry in the cache.
+ *
+ * As soon as the building process of Append Path for the root relation
+ * finished, the cache are deleted (append path build finished of recursive scan
+ * path build marked as level 1 in the cache control structure).
+ *
+ * GUC parameters
+ * --------------
+ *
+ * - partition_path_cache_threshold: integer, default 0, minimum 0,
+ * maximum INT32_MAX, minimum number of partitions for use the access path
+ * cache, for disabling the feature, set it to 0 or 1.
+ * - partition_path_cache_debug: boolean, default is off, print debug messages
+ * for partition access path cache (used for tests).
+ *
+ * Tests
+ * -----
+ * src/test/regress/sql/path_cache.sql
+ *
+ * IDENTIFICATION
+ * src/backend/optimizer/path/pathcache.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "miscadmin.h"
+
+#include "common/hashfn.h"
+
+#include "nodes/nodes.h"
+#include "nodes/primnodes.h"
+#include "nodes/pathnodes.h"
+
+#include "optimizer/paths.h"
+#include "optimizer/pathnode.h"
+
+#include "utils/hsearch.h"
+#include "utils/lsyscache.h"
+#include "utils/memutils.h"
+
+/* GUCs */
+int partition_path_cache_threshold = 0;
+bool partition_path_cache_debug = false;
+
+/* PathCache - path cache global state */
+typedef struct PathCache
+{
+ /* mctx - memory context witch hold all cache data (and this structure) */
+ MemoryContext mctx;
+
+ /*
+ * partPaths - hash table of PartPathsEntry for every partition table
+ * group
+ */
+ HTAB *partPaths;
+
+ /*
+ * level - level of partitioning, used for track cache usage. 1 for root
+ * partition table partitions, >1 for partitions of partitions.
+ */
+ uint32 level;
+} PathCache;
+
+static PathCache * pathCache = NULL;
+
+typedef struct PartPathsKey
+{
+ /* Partition group identifier (not 0) */
+ uint64 part_group_id;
+ /* Parent relation index in RTE table */
+ Index parentRelId;
+} PartPathsKey;
+
+typedef struct PartPathsEntry
+{
+ PartPathsKey key;
+ /* Path type for partition group leader cheapest total path */
+ NodeTag pathtype;
+ /* List of indexids used partition group leader cheapest total path */
+ List *indexes_ids; /* Indexes used in path */
+} PartPathsEntry;
+
+extern void add_path(RelOptInfo *parent_rel, Path *new_path);
+static List *form_path_idx_list(Path *path, List *ids);
+static char *path_type_name(NodeTag tag);
+
+/* 64 bit Id list manipulation for 32 and 64 bit arches */
+#if SIZEOF_VOID_P >= 8
+#define APPEND_ID_LIST(l,id) \
+ lappend((l), (void *)(id));
+#define ID_IS_MEMBER_OF_LIST(l,id)\
+ (list_member_ptr((l), (void *)(id)))
+#define FREE_ID_LIST(l)\
+ list_free((l));
+#else /* SIZEOF_VOID_P >= 8 */
+static inline List *
+append_id(List *l, uint64 id)
+{
+ uint64 *w = palloc(sizeof(uint64));
+
+ *w = id;
+ return lappend(l, w);
+}
+#define APPEND_ID_LIST(l,id) \
+ append_id((l), (id));
+
+static inline bool
+id_is_member(List *l, uint64 id)
+{
+ ListCell *lc;
+
+ foreach(lc, l)
+ {
+ uint64 *v = (uint64 *) lfirst(lc);
+
+ if (*v == id)
+ return true;
+ }
+ return false;
+}
+#define ID_IS_MEMBER_OF_LIST(l,id) \
+ (id_is_member((l), (id)))
+#define FREE_ID_LIST(l)\
+ list_free_deep((l));
+#endif /* SIZEOF_VOID_P >= 8 */
+
+#define PPC_DEBUG(fmt,...) \
+ if(unlikely(partition_path_cache_debug)) \
+ elog(NOTICE,"ppc: " fmt, ##__VA_ARGS__ );
+#define PPC_DEBUG_PATH(e,rte,msg) \
+ PPC_DEBUG("[%d] %-5s: %-14s %s", \
+ pathCache->level, (msg), \
+ path_type_name((e)->pathtype), \
+ get_rel_name((rte)->relid));
+
+
+/*
+ * partition_path_cache_create_paths()
+ *
+ * Try to build partition access path if there is record with
+ * the same `part_group_id`.
+ *
+ * NOTE: `part_group_id` is not zero only if'rel` (built by get_relation_info())
+ * is partitioned table partition, so that path build procedure for all other
+ * types of Append paths is not affected.
+ *
+ * Arguments:
+ * - root, rel, rte - path build context from set_rel_pathlist()
+ * - path_store - pointer to flag, true if standard path build results
+ * should be stored at the cache.
+ *
+ * Returns true if cache seek and path build succeed.
+ * Returns false if:
+ * - No record for presented `part_group_id` found, but the cache may be used
+ * (*path_store = true).
+ * - Path build process for this relation could not use the cache
+ * (*path_store = false).
+ */
+bool
+partition_path_cache_create_paths(PlannerInfo *root, RelOptInfo *rel,
+ RangeTblEntry *rte, bool *path_store)
+{
+ PartPathsKey key = {0};
+ PartPathsEntry *entry = NULL;
+ List *cached_indexes_ids;
+ int prev_pathlist_len;
+
+ Assert(path_store);
+ Assert(pathCache);
+ Assert(PARTITION_GROUP_ID_VALID(rel->part_group_id));
+
+ /* Insert path cache entry required */
+ *path_store = true;
+ key.part_group_id = rel->part_group_id;
+ key.parentRelId = rel->parent->relid;
+ entry = hash_search(pathCache->partPaths, &key, HASH_FIND, NULL);
+ if (!entry)
+ return false;
+
+ /*
+ * No path cache entry update required. We already found the optimal path
+ * for the current partition group.
+ */
+ *path_store = false;
+
+ cached_indexes_ids = entry->indexes_ids;
+ prev_pathlist_len = list_length(rel->pathlist);
+
+ /*
+ * Following code calls only the minimal required set of standard path
+ * build functions. We omit building as many path types as we can for
+ * building only selected path type.
+ */
+ switch (entry->pathtype)
+ {
+
+ case T_IndexScan:
+ case T_IndexOnlyScan:
+ case T_BitmapHeapScan:
+ {
+ /*
+ * For index/bitmap scan, we don’t build sequence scan paths
+ * and also build paths only for the minimal set of indexes
+ * that must be used for the selected index/bitmap scan type.
+ */
+ if (cached_indexes_ids)
+ {
+ /*
+ * The current partition group has more indexes than are
+ * involved in the selected access path type.
+ */
+ List *short_indexlist = NULL;
+ int short_indexlist_len;
+ List *rel_indexlist = rel->indexlist;
+ ListCell *lc;
+
+ /*
+ * Seek indexes for current relation similar to those used
+ * for selected path type.
+ */
+ foreach(lc, rel_indexlist)
+ {
+ IndexOptInfo *ioi = (IndexOptInfo *) lfirst(lc);
+
+ if (ID_IS_MEMBER_OF_LIST(cached_indexes_ids,
+ ioi->index_group_id))
+ short_indexlist = lappend(short_indexlist, ioi);
+ }
+ short_indexlist_len = list_length(short_indexlist);
+
+ /*
+ * If there is no part_group_id hash collision, we should
+ * find a full set of similar indexes.
+ */
+ if (short_indexlist_len &&
+ short_indexlist_len == list_length(cached_indexes_ids))
+ {
+ /*
+ * Create all index paths with the short list of
+ * indexes.
+ *
+ * Excluding not-necessary indexes from the path-build
+ * allows us to find similar path types as fast as we
+ * can.
+ */
+
+ /* Limit RelOptInfo index list */
+ rel->indexlist = short_indexlist;
+ create_index_paths(root, rel);
+ /* Restore RelOptInfo index list */
+ rel->indexlist = rel_indexlist;
+
+ list_free(short_indexlist);
+ if (list_length(rel->pathlist) > prev_pathlist_len)
+ {
+ PPC_DEBUG_PATH(entry, rte, "load ");
+ return true;
+ }
+
+ /* Report log in case the path build failed. */
+ elog(WARNING, "partition path cache usage failed for "
+ "failed, build all index related paths is %s",
+ path_type_name(entry->pathtype));
+ /* Update path cache entry in case of fail. */
+ *path_store = true;
+ }
+ else
+ list_free(short_indexlist);
+ }
+
+ /*
+ * The current partition group involved all available indexes
+ * in the selected access path. Or build a path with a short
+ * list of indexes failed.
+ *
+ * Run the standard index access path build algorithm.
+ */
+ create_index_paths(root, rel);
+ }
+ break;
+ case T_SeqScan:
+ {
+ /*
+ * For sequence scans, we don’t build index/bitmap scan
+ * paths.
+ */
+ Relids required_outer = rel->lateral_relids;
+
+ if (rel->consider_parallel && required_outer == NULL)
+ create_plain_partial_paths(root, rel);
+
+ /*
+ * If we don’t add partial sequence scan paths, we try to
+ * add simple sequence scan.
+ */
+ if (list_length(rel->pathlist) == prev_pathlist_len)
+ add_path(rel, create_seqscan_path(root, rel,
+ required_outer, 0));
+ }
+ break;
+ default:
+ elog(WARNING, "path type %s not supported",
+ path_type_name(entry->pathtype));
+ return false;
+ }
+
+ /*
+ * At least one access path was added at RelOptInfo - path cache usage
+ * succeeded.
+ */
+ if (likely(list_length(rel->pathlist) > prev_pathlist_len))
+ {
+ PPC_DEBUG_PATH(entry, rte, "load ");
+ return true;
+ }
+
+ /*
+ * We use warning message for track partition path cache faults (main
+ * reason is part_group_id or index_group_id hash collisions).
+ */
+ elog(WARNING, "partition path cache usage failed for %s",
+ path_type_name(entry->pathtype));
+ /* Add new path for this partition group */
+ *path_store = true;
+ return false;
+}
+
+/*
+ * partition_path_cache_store()
+ *
+ * Store standard path build results in case of cache may be used at next
+ * partition path planing.
+ *
+ * NOTE: `part_group_id` is not zero only if'rel` (built by get_relation_info())
+ * is partitioned table partition, so that path build procedure for all other
+ * types of Append paths is not affected.
+ *
+ * Argument:
+ * - rel - path build context from set_rel_pathlist()
+ */
+void
+partition_path_cache_store(RelOptInfo *rel, RangeTblEntry *rte)
+{
+ Path *path;
+ List *indexes_ids = NULL;
+
+ Assert(pathCache);
+ Assert(PARTITION_GROUP_ID_VALID(rel->part_group_id));
+
+ path = rel->cheapest_total_path;
+ if (!path)
+ return;
+
+ switch (path->pathtype)
+ {
+ case T_IndexScan:
+ case T_IndexOnlyScan:
+ case T_BitmapHeapScan:
+ {
+ MemoryContext oldctx;
+
+ oldctx = MemoryContextSwitchTo(pathCache->mctx);
+ indexes_ids = form_path_idx_list(path, NULL);
+ MemoryContextSwitchTo(oldctx);
+
+ /*
+ * If the path involves all available indexes, we don't need
+ * to find similar indexes at other group members to exclude
+ * other indexes from the path-build procedure, so we can
+ * delete the path index list right now.
+ */
+ if (list_length(indexes_ids) == list_length(rel->indexlist))
+ {
+ FREE_ID_LIST(indexes_ids);
+ indexes_ids = NULL;
+ }
+ }
+ /* fallthrough */
+ case T_SeqScan:
+ {
+ PartPathsKey key = {0};
+ PartPathsEntry *entry;
+
+ key.part_group_id = rel->part_group_id;
+ key.parentRelId = rel->parent->relid;
+ entry = hash_search(pathCache->partPaths,
+ &key, HASH_ENTER, NULL);
+
+ /*
+ * Even if an entry is presented, if we are here, we should
+ * add a path information to the cache, so we don't check if
+ * an entry is found or not.
+ */
+ entry->pathtype = path->pathtype;
+ entry->indexes_ids = indexes_ids;
+ PPC_DEBUG_PATH(entry, rte, "store");
+ }
+ break;
+ default:
+
+ /*
+ * This scan types are not supported: T_TidScan, T_TidRangeScan,
+ * T_SampleScan, T_SubqueryScan, T_FunctionScan, T_TableFuncScan,
+ * T_ValuesScan, T_CteScan, T_WorkTableScan,
+ * T_NamedTuplestoreScan, T_ForeignScan, T_CustomScan.
+ */
+ PPC_DEBUG("path %s not supported",
+ path_type_name(path->pathtype));
+ return;
+ }
+}
+
+/*
+ * form_path_idx_list()
+ *
+ * Scan path node tree and form a list of used indexes IDs.
+ */
+static List *
+form_path_idx_list(Path *path, List *ids)
+{
+ ListCell *lc;
+ List *quals = NULL;
+
+ switch (path->pathtype)
+ {
+ case T_IndexScan:
+ case T_IndexOnlyScan:
+ {
+ IndexPath *ip = (IndexPath *) path;
+
+ return APPEND_ID_LIST(ids, ip->indexinfo->index_group_id);
+ }
+ case T_BitmapHeapScan:
+ {
+ BitmapHeapPath *bhs = (BitmapHeapPath *) path;
+
+ return form_path_idx_list(bhs->bitmapqual, ids);
+ }
+ case T_BitmapAnd:
+ {
+ BitmapAndPath *bap = (BitmapAndPath *) path;
+
+ quals = bap->bitmapquals;
+ break;
+ }
+ case T_BitmapOr:
+ {
+ BitmapOrPath *bop = (BitmapOrPath *) path;
+
+ quals = bop->bitmapquals;
+ break;
+ }
+ default:
+ list_free(ids);
+ elog(WARNING, "path type %s not supportred at BitmapHeapScan quals",
+ path_type_name(path->pathtype));
+ return NULL;
+ }
+ foreach(lc, quals)
+ {
+ ids = form_path_idx_list((Path *) lfirst(lc), ids);
+ }
+ return ids;
+}
+
+/*
+ * partition_path_cache_begin()
+ *
+ * Initialization the path cache in case of build Append path.
+ */
+void
+partition_path_cache_begin(void)
+{
+ if (!pathCache)
+ {
+ HASHCTL hctl = {0};
+ MemoryContext oldctx;
+
+ MemoryContext ctx = AllocSetContextCreate(CurrentMemoryContext,
+ "path cache",
+ ALLOCSET_DEFAULT_SIZES);
+
+ oldctx = MemoryContextSwitchTo(ctx);
+ pathCache = palloc(sizeof(PathCache));
+ hctl.keysize = sizeof(PartPathsKey);
+ hctl.entrysize = sizeof(PartPathsEntry);
+ hctl.hcxt = ctx;
+ pathCache->mctx = ctx;
+ pathCache->partPaths = hash_create("path cache",
+ 64, &hctl,
+ HASH_ELEM | HASH_BLOBS |
+ HASH_CONTEXT);
+ pathCache->level = 1;
+ MemoryContextSwitchTo(oldctx);
+ PPC_DEBUG("startup");
+ }
+ else
+ ++pathCache->level;
+}
+
+/*
+ * partition_path_cache_end()
+ *
+ * Cleanup the path cache.
+ */
+void
+partition_path_cache_end(void)
+{
+
+ Assert(pathCache);
+ Assert(pathCache->level);
+
+ /* No matter which value part_path_cache_mode has we have to clean up */
+ --pathCache->level;
+ if (pathCache->level == 0)
+ {
+ MemoryContextDelete(pathCache->mctx);
+ pathCache = NULL;
+ PPC_DEBUG("clean");
+ }
+}
+
+static char *
+path_type_name(NodeTag tag)
+{
+ switch (tag)
+ {
+ case T_IndexScan:
+ return "IndexScan";
+ case T_IndexOnlyScan:
+ return "IndexOnlyScan";
+ case T_BitmapHeapScan:
+ return "BitmapHeapScan";
+ case T_SeqScan:
+ return "SeqScan";
+ case T_TidScan:
+ return "TidScan";
+ case T_TidRangeScan:
+ return "TidRangeScan";
+ case T_SampleScan:
+ return "SampleScan";
+ case T_SubqueryScan:
+ return "SubqueryScan";
+ case T_FunctionScan:
+ return "FunctionScan";
+ case T_TableFuncScan:
+ return "TableFuncScan";
+ case T_ValuesScan:
+ return "ValuesScan";
+ case T_CteScan:
+ return "CteScan";
+ case T_WorkTableScan:
+ return "WorkTableScan";
+ case T_NamedTuplestoreScan:
+ return "NamedTuplestoreScan";
+ case T_ForeignScan:
+ return "ForeignScan";
+ case T_CustomScan:
+ return "CustomScan";
+ default:
+ return "Unsupported";
+ }
+ return "Unsupported";
+}
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 86655f05dc..0f78a6af37 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -31,6 +31,7 @@
#include "catalog/pg_proc.h"
#include "catalog/pg_statistic_ext.h"
#include "catalog/pg_statistic_ext_data.h"
+#include "common/hashfn.h"
#include "foreign/fdwapi.h"
#include "miscadmin.h"
#include "nodes/makefuncs.h"
@@ -38,6 +39,7 @@
#include "nodes/supportnodes.h"
#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
+#include "optimizer/paths.h"
#include "optimizer/plancat.h"
#include "parser/parse_relation.h"
#include "parser/parsetree.h"
@@ -47,6 +49,7 @@
#include "storage/bufmgr.h"
#include "tcop/tcopprot.h"
#include "utils/builtins.h"
+#include "utils/catalog_id.h"
#include "utils/lsyscache.h"
#include "utils/partcache.h"
#include "utils/rel.h"
@@ -81,6 +84,7 @@ static void set_baserel_partition_key_exprs(Relation relation,
static void set_baserel_partition_constraint(Relation relation,
RelOptInfo *rel);
+static int idx_hash_cmp(const void *a, const void *b);
/*
* get_relation_info -
@@ -120,6 +124,8 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
Relation relation;
bool hasindex;
List *indexinfos = NIL;
+ uint64 part_group_id = InvalidPartGroupId;
+ RelOptInfo *parent = rel->parent;
/*
* We need not lock the relation since it was already locked, either by
@@ -218,11 +224,38 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
else
hasindex = relation->rd_rel->relhasindex;
+ /*
+ * Initiate calculation of part_group_id for partition path cache.
+ * part_group_id is not zero only for partition relation.
+ *
+ * We already build RelOptInfo for current relation parent, so nparts is
+ * set.
+ */
+ if (unlikely(PARTITION_PATH_CACHE_ENABLED &&
+ relation->rd_rel->relkind == RELKIND_RELATION &&
+ parent && parent->nparts >= partition_path_cache_threshold))
+ {
+ /* Make a nontrivial hash value for a partition without indexes. */
+ part_group_id = hash_combine64(parent->relid, parent->nparts);
+
+ /*
+ * Invalid part_group_id is an indicate state where no partition path
+ * cache operations are required. So, we just use another value if the
+ * hash sum equals InvalidPartGroupId. It may trigger collision
+ * problems with extremely low probability, and in case of this
+ * problem, the standard path-build algorithm will be invoked.
+ */
+ if (unlikely(!PARTITION_GROUP_ID_VALID(part_group_id)))
+ part_group_id = ~InvalidPartGroupId;
+ }
+
if (hasindex)
{
List *indexoidlist;
LOCKMODE lmode;
ListCell *l;
+ uint64 *indexIds = NULL;
+ int indexIdsN = 0;
indexoidlist = RelationGetIndexList(relation);
@@ -236,6 +269,10 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
*/
lmode = root->simple_rte_array[varno]->rellockmode;
+ /* Create array for store index IDs */
+ if (unlikely(PARTITION_GROUP_ID_VALID(part_group_id)))
+ indexIds = palloc_array(uint64, list_length(indexoidlist));
+
foreach(l, indexoidlist)
{
Oid indexoid = lfirst_oid(l);
@@ -309,6 +346,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
}
info->relam = indexRelation->rd_rel->relam;
+ info->index_group_id = InvalidIndexGroupId;
/*
* We don't have an AM for partitioned indexes, so we'll just
@@ -446,6 +484,10 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
*/
info->indexprs = RelationGetIndexExpressions(indexRelation);
info->indpred = RelationGetIndexPredicate(indexRelation);
+ /* Get index ID for child relations only */
+ if (unlikely(PARTITION_GROUP_ID_VALID(part_group_id)))
+ info->index_group_id = get_index_group_id(index,
+ info->indexprs, info->indpred);
if (info->indexprs && varno != 1)
ChangeVarNodes((Node *) info->indexprs, 1, varno, 0);
if (info->indpred && varno != 1)
@@ -517,11 +559,40 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
* that the O(N^2) behavior of lcons() is really a problem.
*/
indexinfos = lcons(info, indexinfos);
+
+ /* Add index ID at array only if it added at indexinfos */
+ if (unlikely(info->index_group_id != InvalidIndexGroupId))
+ indexIds[indexIdsN++] = info->index_group_id;
+ }
+
+ /* Recalculate hash for partition if index IDs are presented */
+ if (unlikely(PARTITION_GROUP_ID_VALID(part_group_id) && indexIdsN))
+ {
+ if (indexIdsN > 1)
+ pg_qsort(indexIds, indexIdsN, sizeof(uint64), idx_hash_cmp);
+ part_group_id = hash_bytes_extended((const unsigned char *) indexIds,
+ indexIdsN * sizeof(uint64),
+ part_group_id);
+
+ /*
+ * Invalid part_group_id is an indicate state where no partition
+ * path cache operations are required. So, we just use another
+ * value if the hash sum equals InvalidPartGroupId. It may trigger
+ * collision problems with extremely low probability, and in case
+ * of this problem, the standard path-build algorithm will be
+ * invoked.
+ */
+ if (unlikely(!PARTITION_GROUP_ID_VALID(part_group_id)))
+ part_group_id = ~InvalidPartGroupId;
+
+ pfree(indexIds);
}
list_free(indexoidlist);
}
+ rel->part_group_id = part_group_id;
+
rel->indexlist = indexinfos;
rel->statlist = get_relation_statistics(rel, relation);
@@ -2590,3 +2661,17 @@ set_baserel_partition_constraint(Relation relation, RelOptInfo *rel)
rel->partition_qual = partconstr;
}
}
+
+/*
+ * Index ID comparator for pg_qsort
+ */
+static int
+idx_hash_cmp(const void *a, const void *b)
+{
+ uint64 av = *(uint64 *) a;
+ uint64 bv = *(uint64 *) b;
+
+ if (av == bv)
+ return 0;
+ return av > bv ? +1 : -1;
+}
diff --git a/src/backend/utils/misc/Makefile b/src/backend/utils/misc/Makefile
index d9f59785b9..1e90f8910d 100644
--- a/src/backend/utils/misc/Makefile
+++ b/src/backend/utils/misc/Makefile
@@ -15,6 +15,7 @@ include $(top_builddir)/src/Makefile.global
override CPPFLAGS := -I. -I$(srcdir) $(CPPFLAGS)
OBJS = \
+ catalog_id.o \
conffiles.o \
guc.o \
guc-file.o \
diff --git a/src/backend/utils/misc/catalog_id.c b/src/backend/utils/misc/catalog_id.c
new file mode 100644
index 0000000000..386d46d89a
--- /dev/null
+++ b/src/backend/utils/misc/catalog_id.c
@@ -0,0 +1,415 @@
+/*-------------------------------------------------------------------------
+ *
+ * catalog_id.c
+ * pg_ctalog rows fingerprinting.
+ *
+ * IDENTIFICATION
+ * src/backend/utils/misc/catalog_id.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "miscadmin.h"
+
+#include "common/hashfn.h"
+
+#include "nodes/nodeFuncs.h"
+#include "nodes/primnodes.h"
+#include "nodes/pathnodes.h"
+
+#include "tcop/utility.h"
+
+#include "utils/builtins.h"
+#include "utils/catalog_id.h"
+#include "utils/datum.h"
+#include "utils/syscache.h"
+#include "utils/memutils.h"
+
+#define HASH_BUFFER_LEN 512
+
+typedef struct CatHashCtx
+{
+ uint64 hash_seed;
+ int len;
+ uint8 buff[HASH_BUFFER_LEN];
+} CatHashCtx;
+
+static bool index_expr_walker(Node *node, CatHashCtx * ctx);
+
+static void hash_add(CatHashCtx * ctx, void *val, int len);
+static uint64 hash_finish(CatHashCtx * ctx);
+
+#define HASH_FIELD(f) hash_add(ctx,&(f),sizeof((f)));
+#define HASH_VECTOR(v,c) hash_add(ctx,(v),sizeof((v)[0])*(c));
+#define HASH_EXP_LIST(elist) \
+ if(elist) \
+ { \
+ ListCell* lc; \
+ foreach(lc,elist) \
+ { \
+ Node* n = (Node*)lfirst(lc); \
+ index_expr_walker(n,ctx); \
+ } \
+ }
+
+/*
+ * get_index_group_id() -- index fingerprinting
+ *
+ * This function is to inspect the index description (in pg_catalog.pg_index)
+ * and make its fingerprint as fast as it can be performed in order to find
+ * similar indexes for different partitions of the same table.
+ *
+ * Arguments:
+ * index - pg_index row representation;
+ * indexprs - unpacked by RelationGetIndexExpressions() index expressions;
+ * indpred - unpacked by RelationGetIndexPredicate() index predicates.
+ *
+ * Return value - index group ID, if its equal InvalidIndexGroupId -
+ * index could not be used (at list in some snapshot).
+ */
+uint64
+get_index_group_id(Form_pg_index index, List *indexprs, List *indpred)
+{
+ CatHashCtx ctx_raw = {.hash_seed = 0,.len = 0};
+ CatHashCtx *ctx = &ctx_raw;
+
+
+ if (!index->indisvalid || /* this index is not valid for use by queries */
+ !index->indisready || /* this index is not ready for inserts */
+ index->indcheckxmin || /* we must wait for xmin to be old */
+ !index->indislive) /* this index is not alive at all */
+ return InvalidIndexGroupId;
+
+ /*
+ * Skip indexrelid and indrelid because we whant to macth same type
+ * indexes for differernt partitions
+ */
+ HASH_FIELD(index->indnatts);
+ HASH_FIELD(index->indnkeyatts);
+
+ HASH_FIELD(index->indisunique);
+ HASH_FIELD(index->indnullsnotdistinct);
+ HASH_FIELD(index->indisprimary);
+ HASH_FIELD(index->indisexclusion);
+ HASH_FIELD(index->indimmediate);
+ /* Skip indisclustered because it is not affect on index usage in path */
+
+ /*
+ * Skip indisvalid, indisready, indcheckxmin and indislive because we have
+ * already made a healthcheck
+ */
+ /* Skip indisreplident because it is not affect on index usage in path */
+ HASH_VECTOR(index->indkey.values, index->indnkeyatts);
+
+ HASH_EXP_LIST(indexprs);
+ HASH_EXP_LIST(indpred);
+
+ return hash_finish(ctx);
+}
+
+/* index_expr_walker() -- get expression fingerprint for pg_index columns.
+ *
+ * Index fingerprinting manipulates with a fixed number of Var nodes (because
+ * we aim to compare indexes for partitions of the same relation),
+ * so we do not have to thoroughly inspect pg_type and pg_collation OIDs and
+ * dig dipper in node fields.
+ */
+static bool
+index_expr_walker(Node *node, CatHashCtx * ctx)
+{
+ if (node == NULL)
+ return false;
+
+ HASH_FIELD(node->type);
+ switch (node->type)
+ {
+ case T_Const:
+ {
+ Const *ConstNode = (Const *) node;
+
+ if (ConstNode->constisnull)
+ {
+ Oid null = 0;
+
+ HASH_FIELD(null);
+ }
+ else if (ConstNode->constbyval)
+ {
+ HASH_FIELD(ConstNode->constvalue);
+ HASH_FIELD(ConstNode->consttype);
+ }
+ else
+ {
+ uint32 hash = datum_image_hash(ConstNode->constvalue,
+ ConstNode->constbyval,
+ ConstNode->constlen);
+
+ HASH_FIELD(hash);
+ }
+ break;
+ }
+ case T_Var:
+ {
+ Var *VarNode = (Var *) node;
+
+ HASH_FIELD(VarNode->varattno);
+ break;
+ }
+ case T_Param:
+ {
+ Param *ParamNode = (Param *) node;
+
+ HASH_FIELD(ParamNode->paramid);
+ break;
+ }
+ case T_Aggref:
+ {
+ Aggref *AggrefNode = (Aggref *) node;
+
+ HASH_FIELD(AggrefNode->aggfnoid);
+ break;
+ }
+ /* Skip GroupingFunc */
+ case T_WindowFunc:
+ {
+ WindowFunc *WindowFuncNode = (WindowFunc *) node;
+
+ HASH_FIELD(WindowFuncNode->winfnoid);
+ break;
+ }
+ /* Skip SubscriptingRef */
+ case T_FuncExpr:
+ {
+ FuncExpr *FuncExprNode = (FuncExpr *) node;
+
+ HASH_FIELD(FuncExprNode->funcid);
+ break;
+ }
+ case T_OpExpr:
+ {
+ OpExpr *OpExprNode = (OpExpr *) node;
+
+ HASH_FIELD(OpExprNode->opno);
+ break;
+ }
+ case T_DistinctExpr:
+ {
+ DistinctExpr *DistinctExprNode = (DistinctExpr *) node;
+
+ HASH_FIELD(DistinctExprNode->opno);
+ break;
+ }
+ case T_NullIfExpr:
+ {
+ NullIfExpr *NullIfExprNode = (NullIfExpr *) node;
+
+ HASH_FIELD(NullIfExprNode->opno);
+ break;
+ }
+ case T_ScalarArrayOpExpr:
+ {
+ ScalarArrayOpExpr *ScalarArrayOpExprNode = (ScalarArrayOpExpr *) node;
+
+ HASH_FIELD(ScalarArrayOpExprNode->opno);
+ break;
+ }
+ case T_BoolExpr:
+ {
+ BoolExpr *BoolExprNode = (BoolExpr *) node;
+
+ HASH_FIELD(BoolExprNode->boolop);
+ break;
+ }
+ /* Skip SubLink, SubPlan, AlternativeSubPlan */
+ case T_FieldSelect:
+ {
+ FieldSelect *FieldSelectNode = (FieldSelect *) node;
+
+ HASH_FIELD(FieldSelectNode->fieldnum);
+ break;
+ }
+
+ /*
+ * Skip FieldStore, RelabelType, CoerceViaIO, ArrayCoerceExpr,
+ * ConvertRowtypeExpr
+ */
+ case T_CollateExpr:
+ {
+ CollateExpr *CollateExprNode = (CollateExpr *) node;
+
+ HASH_FIELD(CollateExprNode->collOid);
+ break;
+ }
+ /* Skip CaseExpr, CaseWhen, CaseTestExpr */
+ case T_ArrayExpr:
+ {
+ ArrayExpr *ArrayExprNode = (ArrayExpr *) node;
+
+ HASH_FIELD(ArrayExprNode->array_typeid);
+ break;
+ }
+ case T_RowExpr:
+ {
+ RowExpr *RowExprNode = (RowExpr *) node;
+
+ HASH_FIELD(RowExprNode->row_typeid);
+ break;
+ }
+ case T_RowCompareExpr:
+ {
+ RowCompareExpr *RowCompareExprNode = (RowCompareExpr *) node;
+
+ HASH_FIELD(RowCompareExprNode->rctype);
+ break;
+ }
+ case T_CoalesceExpr:
+ {
+ CoalesceExpr *CoalesceExprNode = (CoalesceExpr *) node;
+
+ HASH_FIELD(CoalesceExprNode->coalescetype);
+ break;
+ }
+ case T_MinMaxExpr:
+ {
+ MinMaxExpr *MinMaxExprNode = (MinMaxExpr *) node;
+
+ HASH_FIELD(MinMaxExprNode->op);
+ break;
+ }
+ case T_SQLValueFunction:
+ {
+ SQLValueFunction *SQLValueFunctionNode = (SQLValueFunction *) node;
+
+ HASH_FIELD(SQLValueFunctionNode->op);
+ break;
+ }
+ case T_XmlExpr:
+ {
+ XmlExpr *XmlExprNode = (XmlExpr *) node;
+
+ HASH_FIELD(XmlExprNode->op);
+ break;
+ }
+ case T_JsonFormat:
+ {
+ JsonFormat *JsonFormatNode = (JsonFormat *) node;
+
+ HASH_FIELD(JsonFormatNode->format_type);
+ break;
+ }
+ /* Skip JsonReturning, JsonValueExpr */
+ case T_JsonConstructorExpr:
+ {
+ JsonConstructorExpr *JsonConstructorExprNode = (JsonConstructorExpr *) node;
+
+ HASH_FIELD(JsonConstructorExprNode->type);
+ break;
+ }
+ case T_JsonIsPredicate:
+ {
+ JsonIsPredicate *JsonIsPredicateNode = (JsonIsPredicate *) node;
+
+ HASH_FIELD(JsonIsPredicateNode->item_type);
+ break;
+ }
+ case T_NullTest:
+ {
+ NullTest *NullTestNode = (NullTest *) node;
+
+ HASH_FIELD(NullTestNode->nulltesttype);
+ break;
+ }
+ case T_BooleanTest:
+ {
+ BooleanTest *BooleanTestNode = (BooleanTest *) node;
+
+ HASH_FIELD(BooleanTestNode->booltesttype);
+ break;
+ }
+
+ /*
+ * Skip CoerceToDomain, CoerceToDomainValue, SetToDefault,
+ * CurrentOfExpr, NextValueExpr, InferenceElem, TargetEntry
+ */
+ default:
+ {
+ /* Skiped cases */
+ break;
+ }
+ }
+
+ return expression_tree_walker(node,
+ index_expr_walker,
+ (void *) ctx);
+}
+
+
+/*
+ * Buffered hash sum calculation utility
+ *
+ * Inspired by AppendJumble() at src/backend/nodes/queryjumblefuncs.c
+ */
+
+/* hash_add() -- add a chunk of data to the hash buffer; if the buffer is full,
+ * calculate a new seed based on the buffer content.
+ *
+ * This method seems to work faster than recalculating the hash every time
+ * we add new data because we expect a lot of small data chunks will be added
+ * during the pg_catalog row scan and expression tree scan.
+ */
+static void
+hash_add(CatHashCtx * ctx, void *val, int len)
+{
+ if (val == NULL || len <= 0)
+ return;
+
+ while (len)
+ {
+ int wl;
+ const unsigned char *d = (const unsigned char *) val;
+
+ wl = HASH_BUFFER_LEN - ctx->len;
+ if (wl > len)
+ wl = len;
+
+ memcpy(&ctx->buff[ctx->len], d, wl);
+ ctx->len += wl;
+ d += wl;
+ len -= wl;
+
+ if (ctx->len >= HASH_BUFFER_LEN)
+ {
+ ctx->hash_seed = hash_bytes_extended(ctx->buff, ctx->len, ctx->hash_seed);
+ ctx->len = 0;
+ }
+ }
+}
+
+/* hash_finish() -- final hash calculation.
+ *
+ * Calculate the hash for the partially filled buffer if required. Return
+ * hash_seed as result. Result could not be zero (but hash_seed could).
+ */
+static uint64
+hash_finish(CatHashCtx * ctx)
+{
+ if (ctx->len != 0)
+ ctx->hash_seed = hash_bytes_extended(ctx->buff,
+ ctx->len,
+ ctx->hash_seed);
+
+ /*
+ * index_group_id == InvalidIndexGroupId is an indicate state where this
+ * index could not be used in partition path cache operations. So, we just
+ * use another value if the hash sum equals InvalidIndexGroupId. It may
+ * trigger collision problems with extremely low probability, and in case
+ * of this problem, the standard path-build algorithm will be invoked.
+ */
+ if (unlikely(ctx->hash_seed == InvalidIndexGroupId))
+ ctx->hash_seed = ~InvalidIndexGroupId;
+ if (ctx->hash_seed)
+ return ctx->hash_seed;
+ return 1;
+}
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index dc222d98ad..05f668ad35 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -1922,6 +1922,17 @@ struct config_bool ConfigureNamesBool[] =
NULL, NULL, NULL
},
+ {
+ {"partition_path_cache_debug", PGC_USERSET, DEVELOPER_OPTIONS,
+ gettext_noop("Allow printing partition path cache usage log"),
+ NULL,
+ GUC_NOT_IN_SAMPLE
+ },
+ &partition_path_cache_debug,
+ false,
+ NULL, NULL, NULL
+ },
+
{
{"jit_debugging_support", PGC_SU_BACKEND, DEVELOPER_OPTIONS,
gettext_noop("Register JIT-compiled functions with debugger."),
@@ -2093,6 +2104,18 @@ struct config_int ConfigureNamesInt[] =
8, 1, INT_MAX,
NULL, NULL, NULL
},
+
+ {
+ {"partition_path_cache_threshold", PGC_USERSET, QUERY_TUNING_OTHER,
+ gettext_noop("Minimum partition count for use partition path cache"),
+ NULL,
+ GUC_EXPLAIN
+ },
+ &partition_path_cache_threshold,
+ 0, 0, INT_MAX,
+ NULL, NULL, NULL
+ },
+
{
{"geqo_threshold", PGC_USERSET, QUERY_TUNING_GEQO,
gettext_noop("Sets the threshold of FROM items beyond which GEQO is used."),
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index 667e0dc40a..524a4b8e8d 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -457,9 +457,11 @@
# JOIN clauses
#plan_cache_mode = auto # auto, force_generic_plan or
# force_custom_plan
+#partition_path_cache_threshold = 0 # minimum partition count for use
+ # partition path cache,
+ # For disable set it to 0 or 1.
#recursive_worktable_factor = 10.0 # range 0.001-1000000
-
#------------------------------------------------------------------------------
# REPORTING AND LOGGING
#------------------------------------------------------------------------------
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 2ba297c117..f374ec6c81 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -22,6 +22,9 @@
#include "nodes/parsenodes.h"
#include "storage/block.h"
+#define InvalidPartGroupId UINT64CONST(0)
+#define PARTITION_GROUP_ID_VALID(pgi) ((pgi) != InvalidPartGroupId)
+#define InvalidIndexGroupId UINT64CONST(0)
/*
* Relids
@@ -936,6 +939,13 @@ typedef struct RelOptInfo
Relids lateral_referencers;
/* list of IndexOptInfo */
List *indexlist;
+
+ /*
+ * Partition group ID for partition path cache. Not equal
+ * InvalidPartGroupId only in case an access path may be formed by
+ * partition path cahe.
+ */
+ uint64 part_group_id;
/* list of StatisticExtInfo */
List *statlist;
/* size estimates derived from pg_class */
@@ -1201,6 +1211,12 @@ struct IndexOptInfo
/* AM's cost estimator */
/* Rather than include amapi.h here, we declare amcostestimate like this */
void (*amcostestimate) () pg_node_attr(read_write_ignore);
+
+ /*
+ * Index group ID for partition path cache. Not equal InvalidIndexGroupId
+ * only in case an access path may be formed by partition path cahe.
+ */
+ uint64 index_group_id;
};
/*
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 112e7c23d4..42f21345e4 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -36,6 +36,7 @@ extern bool add_partial_path_precheck(RelOptInfo *parent_rel,
extern Path *create_seqscan_path(PlannerInfo *root, RelOptInfo *rel,
Relids required_outer, int parallel_workers);
+extern void create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel);
extern Path *create_samplescan_path(PlannerInfo *root, RelOptInfo *rel,
Relids required_outer);
extern IndexPath *create_index_path(PlannerInfo *root,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 5e88c0224a..fff5c0e81e 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -268,4 +268,21 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root,
extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
List *live_childrels);
+/*
+ * pathcache.c
+ * routines to reuse paths
+ */
+void partition_path_cache_begin(void);
+void partition_path_cache_end(void);
+void partition_path_cache_add(RelOptInfo *rel, Path *path);
+bool partition_path_cache_create_paths(PlannerInfo *root, RelOptInfo *rel,
+ RangeTblEntry *rte, bool *path_store);
+void partition_path_cache_store(RelOptInfo *rel, RangeTblEntry *rte);
+
+/* GUCs */
+
+extern PGDLLIMPORT int partition_path_cache_threshold;
+#define PARTITION_PATH_CACHE_ENABLED (partition_path_cache_threshold >= 2)
+extern PGDLLIMPORT bool partition_path_cache_debug;
+
#endif /* PATHS_H */
diff --git a/src/include/utils/catalog_id.h b/src/include/utils/catalog_id.h
new file mode 100644
index 0000000000..6cc8613302
--- /dev/null
+++ b/src/include/utils/catalog_id.h
@@ -0,0 +1,18 @@
+/*-------------------------------------------------------------------------
+ *
+ * catalog_id.h
+ * pg_ctalog rows fingerprinting.
+ *
+ * IDENTIFICATION
+ * src/include/utils/catalog_id.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef CATALOG_ID_H
+#define CATALOG_ID_H
+
+#include "catalog/pg_index.h"
+
+uint64 get_index_group_id(Form_pg_index index, List *indexprs, List *indpred);
+
+#endif /* CATALOG_ID_H */
diff --git a/src/test/regress/expected/path_cache.out b/src/test/regress/expected/path_cache.out
new file mode 100644
index 0000000000..95207c69d4
--- /dev/null
+++ b/src/test/regress/expected/path_cache.out
@@ -0,0 +1,517 @@
+-- Init
+--------------------------------------------------------------------------------
+-- 'heterogen' table partitions have different set of indexes.
+CREATE TABLE heterogen(id int, name text) PARTITION BY RANGE (id);
+CREATE TABLE child_0_of_heterogen PARTITION OF heterogen FOR VALUES FROM (0) TO (100);
+CREATE INDEX child_0_of_heterogen_id ON child_0_of_heterogen (id);
+CREATE TABLE child_1_of_heterogen PARTITION OF heterogen FOR VALUES FROM (100) TO (200);
+CREATE INDEX child_1_of_heterogen_id ON child_1_of_heterogen (id) INCLUDE (name);
+CREATE TABLE child_2_of_heterogen PARTITION OF heterogen FOR VALUES FROM (200) TO (300);
+CREATE INDEX child_2_of_heterogen_id ON child_2_of_heterogen (id) WHERE (id % 2 = 0);
+CREATE TABLE child_3_of_heterogen PARTITION OF heterogen FOR VALUES FROM (300) TO (400);
+CREATE INDEX child_3_of_heterogen_id ON child_3_of_heterogen (id) INCLUDE (name);
+CREATE TABLE child_4_of_heterogen PARTITION OF heterogen FOR VALUES FROM (400) TO (500);
+CREATE INDEX child_4_of_heterogen_id ON child_4_of_heterogen (id);
+CREATE TABLE child_5_of_heterogen PARTITION OF heterogen FOR VALUES FROM (500) TO (600);
+CREATE INDEX child_5_of_heterogen_id ON child_5_of_heterogen (id) INCLUDE (name);
+CREATE TABLE child_6_of_heterogen PARTITION OF heterogen FOR VALUES FROM (600) TO (700);
+CREATE INDEX child_6_of_heterogen_id ON child_6_of_heterogen (id) INCLUDE (name);
+CREATE TABLE child_7_of_heterogen PARTITION OF heterogen FOR VALUES FROM (700) TO (800);
+CREATE INDEX child_7_of_heterogen_id ON child_7_of_heterogen (id);
+CREATE INDEX child_7_of_heterogen_name ON child_7_of_heterogen (name);
+CREATE TABLE child_8_of_heterogen PARTITION OF heterogen FOR VALUES FROM (800) TO (900);
+CREATE INDEX child_8_of_heterogen_id ON child_8_of_heterogen (id);
+CREATE INDEX child_8_of_heterogen_name ON child_8_of_heterogen (name);
+INSERT INTO heterogen
+ SELECT id, md5(id::text)
+ FROM generate_series(0, 899) AS id;
+ANALYZE heterogen;
+--------------------------------------------------------------------------------
+-- 'multilevel' table partitions have subpartitions witch have subpartitions
+CREATE TABLE child_1_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_1_1_of_multilevel PARTITION OF child_1_of_multilevel FOR VALUES FROM (100) TO (110);
+CREATE TABLE child_1_2_of_multilevel PARTITION OF child_1_of_multilevel FOR VALUES FROM (110) TO (125);
+CREATE TABLE child_1_3_of_multilevel PARTITION OF child_1_of_multilevel FOR VALUES FROM (125) TO (140);
+CREATE TABLE child_1_4_of_multilevel PARTITION OF child_1_of_multilevel FOR VALUES FROM (140) TO (200);
+CREATE TABLE child_2_1_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_2_1_1_of_multilevel PARTITION OF child_2_1_of_multilevel FOR VALUES FROM (200) TO (215);
+CREATE TABLE child_2_1_2_of_multilevel PARTITION OF child_2_1_of_multilevel FOR VALUES FROM (215) TO (225);
+CREATE TABLE child_2_1_3_of_multilevel PARTITION OF child_2_1_of_multilevel FOR VALUES FROM (225) TO (235);
+CREATE TABLE child_2_2_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_2_2_1_of_multilevel PARTITION OF child_2_2_of_multilevel FOR VALUES FROM (235) TO (245);
+CREATE TABLE child_2_2_2_of_multilevel PARTITION OF child_2_2_of_multilevel FOR VALUES FROM (245) TO (265);
+CREATE TABLE child_2_3_3_of_multilevel PARTITION OF child_2_2_of_multilevel FOR VALUES FROM (265) TO (275);
+CREATE TABLE child_2_3_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_2_3_1_of_multilevel PARTITION OF child_2_3_of_multilevel FOR VALUES FROM (275) TO (285);
+CREATE TABLE child_2_3_2_of_multilevel PARTITION OF child_2_3_of_multilevel FOR VALUES FROM (285) TO (300);
+CREATE TABLE child_2_of_multilevel(id int) PARTITION BY RANGE (id);
+ALTER TABLE child_2_of_multilevel ATTACH PARTITION child_2_1_of_multilevel FOR VALUES FROM (200) TO (235);
+ALTER TABLE child_2_of_multilevel ATTACH PARTITION child_2_2_of_multilevel FOR VALUES FROM (235) TO (275);
+ALTER TABLE child_2_of_multilevel ATTACH PARTITION child_2_3_of_multilevel FOR VALUES FROM (275) TO (300);
+CREATE TABLE child_3_1_1_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_3_1_1_1_of_multilevel PARTITION OF child_3_1_1_of_multilevel FOR VALUES FROM (300) TO (310);
+CREATE TABLE child_3_1_1_2_of_multilevel PARTITION OF child_3_1_1_of_multilevel FOR VALUES FROM (310) TO (320);
+CREATE TABLE child_3_1_2_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_3_1_2_1_of_multilevel PARTITION OF child_3_1_2_of_multilevel FOR VALUES FROM (320) TO (330);
+CREATE TABLE child_3_1_2_2_of_multilevel PARTITION OF child_3_1_2_of_multilevel FOR VALUES FROM (330) TO (340);
+CREATE TABLE child_3_1_of_multilevel(id int) PARTITION BY RANGE (id);
+ALTER TABLE child_3_1_of_multilevel ATTACH PARTITION child_3_1_1_of_multilevel FOR VALUES FROM (300) TO (320);
+ALTER TABLE child_3_1_of_multilevel ATTACH PARTITION child_3_1_2_of_multilevel FOR VALUES FROM (320) TO (340);
+CREATE TABLE child_3_2_1_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_3_2_1_1_of_multilevel PARTITION OF child_3_2_1_of_multilevel FOR VALUES FROM (340) TO (350);
+CREATE TABLE child_3_2_1_2_of_multilevel PARTITION OF child_3_2_1_of_multilevel FOR VALUES FROM (350) TO (360);
+CREATE TABLE child_3_2_2_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_3_2_2_1_of_multilevel PARTITION OF child_3_2_2_of_multilevel FOR VALUES FROM (360) TO (370);
+CREATE TABLE child_3_2_2_2_of_multilevel PARTITION OF child_3_2_2_of_multilevel FOR VALUES FROM (370) TO (380);
+CREATE TABLE child_3_2_of_multilevel(id int) PARTITION BY RANGE (id);
+ALTER TABLE child_3_2_of_multilevel ATTACH PARTITION child_3_2_1_of_multilevel FOR VALUES FROM (340) TO (360);
+ALTER TABLE child_3_2_of_multilevel ATTACH PARTITION child_3_2_2_of_multilevel FOR VALUES FROM (360) TO (380);
+CREATE TABLE child_3_3_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_3_3_1_of_multilevel PARTITION OF child_3_3_of_multilevel FOR VALUES FROM (380) TO (390);
+CREATE TABLE child_3_3_2_of_multilevel PARTITION OF child_3_3_of_multilevel FOR VALUES FROM (390) TO (400);
+CREATE TABLE child_3_of_multilevel(id int) PARTITION BY RANGE (id);
+ALTER TABLE child_3_of_multilevel ATTACH PARTITION child_3_1_of_multilevel FOR VALUES FROM (300) TO (340);
+ALTER TABLE child_3_of_multilevel ATTACH PARTITION child_3_2_of_multilevel FOR VALUES FROM (340) TO (380);
+ALTER TABLE child_3_of_multilevel ATTACH PARTITION child_3_3_of_multilevel FOR VALUES FROM (380) TO (400);
+CREATE TABLE multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_0_of_multilevel PARTITION OF multilevel FOR VALUES FROM (0) TO (100);
+ALTER TABLE multilevel ATTACH PARTITION child_1_of_multilevel FOR VALUES FROM (100) TO (200);
+ALTER TABLE multilevel ATTACH PARTITION child_2_of_multilevel FOR VALUES FROM (200) TO (300);
+ALTER TABLE multilevel ATTACH PARTITION child_3_of_multilevel FOR VALUES FROM (300) TO (400);
+CREATE TABLE child_4_of_multilevel PARTITION OF multilevel FOR VALUES FROM (400) TO (500);
+CREATE TABLE child_5_of_multilevel PARTITION OF multilevel FOR VALUES FROM (500) TO (600);
+CREATE TABLE child_6_of_multilevel PARTITION OF multilevel FOR VALUES FROM (600) TO (700);
+CREATE TABLE child_7_of_multilevel PARTITION OF multilevel FOR VALUES FROM (700) TO (800);
+INSERT INTO multilevel SELECT id FROM generate_series(0, 799) AS id;
+CREATE INDEX ON multilevel (id);
+ANALYZE multilevel;
+--------------------------------------------------------------------------------
+-- 'big' table has enough tuples for trigger non sequence scan path generation
+CREATE TABLE big (id serial, num numeric) PARTITION BY RANGE (id);
+CREATE TABLE child_0_of_big PARTITION OF big FOR VALUES FROM (0) TO (2500);
+CREATE INDEX child_0_of_big_id ON child_0_of_big(num);
+CREATE TABLE child_1_of_big PARTITION OF big FOR VALUES FROM (2500) TO (5000);
+CREATE INDEX child_1_of_big_id ON child_1_of_big(num);
+CREATE TABLE child_2_of_big PARTITION OF big FOR VALUES FROM (5000) TO (7500);
+-- NO INDEX
+CREATE TABLE child_3_of_big PARTITION OF big FOR VALUES FROM (7500) TO (10000);
+CREATE INDEX child_3_of_big_id ON child_3_of_big(num);
+INSERT INTO big
+ SELECT random() * 1000, generate_series(1, 9999);
+ANALYZE big;
+--------------------------------------------------------------------------------
+--------------------------------------------------------------------------------
+-- Testing procedure
+--
+-- Because path cache only affects the inner planner path build procedure,
+-- The only way to inspect is to use the result to inspect debug log messages
+-- and query results with results caught without cache.
+--------------------------------------------------------------------------------
+--------------------------------------------------------------------------------
+-- Part 1. Check path cache
+--------------------------------------------------------------------------------
+SET partition_path_cache_threshold = 2;
+SET partition_path_cache_debug = on;
+--------------------------------------------------------------------------------
+--
+-- CASE 1.1: check cache work in case where partitions have different set
+-- of indexes.
+SET enable_seqscan=off;
+EXPLAIN (COSTS FALSE) SELECT id FROM heterogen WHERE id % 8 = 1;
+NOTICE: ppc: startup
+NOTICE: ppc: [1] store: IndexOnlyScan child_0_of_heterogen
+NOTICE: ppc: [1] store: IndexOnlyScan child_1_of_heterogen
+NOTICE: ppc: [1] store: SeqScan child_2_of_heterogen
+NOTICE: ppc: [1] load : IndexOnlyScan child_3_of_heterogen
+NOTICE: ppc: [1] load : IndexOnlyScan child_4_of_heterogen
+NOTICE: ppc: [1] load : IndexOnlyScan child_5_of_heterogen
+NOTICE: ppc: [1] load : IndexOnlyScan child_6_of_heterogen
+NOTICE: ppc: [1] store: IndexOnlyScan child_7_of_heterogen
+NOTICE: ppc: [1] load : IndexOnlyScan child_8_of_heterogen
+NOTICE: ppc: clean
+ QUERY PLAN
+-----------------------------------------------------------------------------------------
+ Append
+ -> Index Only Scan using child_0_of_heterogen_id on child_0_of_heterogen heterogen_1
+ Filter: ((id % 8) = 1)
+ -> Index Only Scan using child_1_of_heterogen_id on child_1_of_heterogen heterogen_2
+ Filter: ((id % 8) = 1)
+ -> Seq Scan on child_2_of_heterogen heterogen_3
+ Filter: ((id % 8) = 1)
+ -> Index Only Scan using child_3_of_heterogen_id on child_3_of_heterogen heterogen_4
+ Filter: ((id % 8) = 1)
+ -> Index Only Scan using child_4_of_heterogen_id on child_4_of_heterogen heterogen_5
+ Filter: ((id % 8) = 1)
+ -> Index Only Scan using child_5_of_heterogen_id on child_5_of_heterogen heterogen_6
+ Filter: ((id % 8) = 1)
+ -> Index Only Scan using child_6_of_heterogen_id on child_6_of_heterogen heterogen_7
+ Filter: ((id % 8) = 1)
+ -> Index Only Scan using child_7_of_heterogen_id on child_7_of_heterogen heterogen_8
+ Filter: ((id % 8) = 1)
+ -> Index Only Scan using child_8_of_heterogen_id on child_8_of_heterogen heterogen_9
+ Filter: ((id % 8) = 1)
+(19 rows)
+
+-- Expected store operations and cache load operations.
+--
+-- CASE 1.2: check cache work in case of multilevel partitioned table used.
+EXPLAIN (COSTS FALSE) SELECT id FROM multilevel WHERE id % 3 = 1;
+NOTICE: ppc: startup
+NOTICE: ppc: [1] store: IndexOnlyScan child_0_of_multilevel
+NOTICE: ppc: [2] store: IndexOnlyScan child_1_1_of_multilevel
+NOTICE: ppc: [2] load : IndexOnlyScan child_1_2_of_multilevel
+NOTICE: ppc: [2] load : IndexOnlyScan child_1_3_of_multilevel
+NOTICE: ppc: [2] load : IndexOnlyScan child_1_4_of_multilevel
+NOTICE: ppc: [3] store: IndexOnlyScan child_2_1_1_of_multilevel
+NOTICE: ppc: [3] load : IndexOnlyScan child_2_1_2_of_multilevel
+NOTICE: ppc: [3] load : IndexOnlyScan child_2_1_3_of_multilevel
+NOTICE: ppc: [3] store: IndexOnlyScan child_2_2_1_of_multilevel
+NOTICE: ppc: [3] load : IndexOnlyScan child_2_2_2_of_multilevel
+NOTICE: ppc: [3] load : IndexOnlyScan child_2_3_3_of_multilevel
+NOTICE: ppc: [3] store: IndexOnlyScan child_2_3_1_of_multilevel
+NOTICE: ppc: [3] load : IndexOnlyScan child_2_3_2_of_multilevel
+NOTICE: ppc: [4] store: IndexOnlyScan child_3_1_1_1_of_multilevel
+NOTICE: ppc: [4] load : IndexOnlyScan child_3_1_1_2_of_multilevel
+NOTICE: ppc: [4] store: IndexOnlyScan child_3_1_2_1_of_multilevel
+NOTICE: ppc: [4] load : IndexOnlyScan child_3_1_2_2_of_multilevel
+NOTICE: ppc: [4] store: IndexOnlyScan child_3_2_1_1_of_multilevel
+NOTICE: ppc: [4] load : IndexOnlyScan child_3_2_1_2_of_multilevel
+NOTICE: ppc: [4] store: IndexOnlyScan child_3_2_2_1_of_multilevel
+NOTICE: ppc: [4] load : IndexOnlyScan child_3_2_2_2_of_multilevel
+NOTICE: ppc: [3] store: IndexOnlyScan child_3_3_1_of_multilevel
+NOTICE: ppc: [3] load : IndexOnlyScan child_3_3_2_of_multilevel
+NOTICE: ppc: [1] load : IndexOnlyScan child_4_of_multilevel
+NOTICE: ppc: [1] load : IndexOnlyScan child_5_of_multilevel
+NOTICE: ppc: [1] load : IndexOnlyScan child_6_of_multilevel
+NOTICE: ppc: [1] load : IndexOnlyScan child_7_of_multilevel
+NOTICE: ppc: clean
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------
+ Append
+ -> Index Only Scan using child_0_of_multilevel_id_idx on child_0_of_multilevel multilevel_1
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_1_1_of_multilevel_id_idx on child_1_1_of_multilevel multilevel_2
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_1_2_of_multilevel_id_idx on child_1_2_of_multilevel multilevel_3
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_1_3_of_multilevel_id_idx on child_1_3_of_multilevel multilevel_4
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_1_4_of_multilevel_id_idx on child_1_4_of_multilevel multilevel_5
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_1_1_of_multilevel_id_idx on child_2_1_1_of_multilevel multilevel_6
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_1_2_of_multilevel_id_idx on child_2_1_2_of_multilevel multilevel_7
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_1_3_of_multilevel_id_idx on child_2_1_3_of_multilevel multilevel_8
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_2_1_of_multilevel_id_idx on child_2_2_1_of_multilevel multilevel_9
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_2_2_of_multilevel_id_idx on child_2_2_2_of_multilevel multilevel_10
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_3_3_of_multilevel_id_idx on child_2_3_3_of_multilevel multilevel_11
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_3_1_of_multilevel_id_idx on child_2_3_1_of_multilevel multilevel_12
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_3_2_of_multilevel_id_idx on child_2_3_2_of_multilevel multilevel_13
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_1_1_1_of_multilevel_id_idx on child_3_1_1_1_of_multilevel multilevel_14
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_1_1_2_of_multilevel_id_idx on child_3_1_1_2_of_multilevel multilevel_15
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_1_2_1_of_multilevel_id_idx on child_3_1_2_1_of_multilevel multilevel_16
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_1_2_2_of_multilevel_id_idx on child_3_1_2_2_of_multilevel multilevel_17
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_2_1_1_of_multilevel_id_idx on child_3_2_1_1_of_multilevel multilevel_18
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_2_1_2_of_multilevel_id_idx on child_3_2_1_2_of_multilevel multilevel_19
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_2_2_1_of_multilevel_id_idx on child_3_2_2_1_of_multilevel multilevel_20
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_2_2_2_of_multilevel_id_idx on child_3_2_2_2_of_multilevel multilevel_21
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_3_1_of_multilevel_id_idx on child_3_3_1_of_multilevel multilevel_22
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_3_2_of_multilevel_id_idx on child_3_3_2_of_multilevel multilevel_23
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_4_of_multilevel_id_idx on child_4_of_multilevel multilevel_24
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_5_of_multilevel_id_idx on child_5_of_multilevel multilevel_25
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_6_of_multilevel_id_idx on child_6_of_multilevel multilevel_26
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_7_of_multilevel_id_idx on child_7_of_multilevel multilevel_27
+ Filter: ((id % 3) = 1)
+(55 rows)
+
+-- Expected store operations and cache load operations operations for all
+-- partitioned tables in multilevel inheritance chain: multilevel,
+-- child_1_of_multilevel, child_2_x_of_multilevel, child_3_1_x_of_multilevel,
+-- child_3_2_x_of_multilevel, child_3_3_of_multilevel, child_3_3_of_multilevel
+--
+-- CASE 1.3: check that partition_path_cache_threshold limits cache usage
+-- for partitioned tables witch has less partition count.
+SET partition_path_cache_threshold = 4;
+EXPLAIN (COSTS FALSE) SELECT id FROM multilevel WHERE id % 3 = 1;
+NOTICE: ppc: startup
+NOTICE: ppc: [1] store: IndexOnlyScan child_0_of_multilevel
+NOTICE: ppc: [2] store: IndexOnlyScan child_1_1_of_multilevel
+NOTICE: ppc: [2] load : IndexOnlyScan child_1_2_of_multilevel
+NOTICE: ppc: [2] load : IndexOnlyScan child_1_3_of_multilevel
+NOTICE: ppc: [2] load : IndexOnlyScan child_1_4_of_multilevel
+NOTICE: ppc: [1] load : IndexOnlyScan child_4_of_multilevel
+NOTICE: ppc: [1] load : IndexOnlyScan child_5_of_multilevel
+NOTICE: ppc: [1] load : IndexOnlyScan child_6_of_multilevel
+NOTICE: ppc: [1] load : IndexOnlyScan child_7_of_multilevel
+NOTICE: ppc: clean
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------
+ Append
+ -> Index Only Scan using child_0_of_multilevel_id_idx on child_0_of_multilevel multilevel_1
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_1_1_of_multilevel_id_idx on child_1_1_of_multilevel multilevel_2
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_1_2_of_multilevel_id_idx on child_1_2_of_multilevel multilevel_3
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_1_3_of_multilevel_id_idx on child_1_3_of_multilevel multilevel_4
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_1_4_of_multilevel_id_idx on child_1_4_of_multilevel multilevel_5
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_1_1_of_multilevel_id_idx on child_2_1_1_of_multilevel multilevel_6
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_1_2_of_multilevel_id_idx on child_2_1_2_of_multilevel multilevel_7
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_1_3_of_multilevel_id_idx on child_2_1_3_of_multilevel multilevel_8
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_2_1_of_multilevel_id_idx on child_2_2_1_of_multilevel multilevel_9
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_2_2_of_multilevel_id_idx on child_2_2_2_of_multilevel multilevel_10
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_3_3_of_multilevel_id_idx on child_2_3_3_of_multilevel multilevel_11
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_3_1_of_multilevel_id_idx on child_2_3_1_of_multilevel multilevel_12
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_2_3_2_of_multilevel_id_idx on child_2_3_2_of_multilevel multilevel_13
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_1_1_1_of_multilevel_id_idx on child_3_1_1_1_of_multilevel multilevel_14
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_1_1_2_of_multilevel_id_idx on child_3_1_1_2_of_multilevel multilevel_15
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_1_2_1_of_multilevel_id_idx on child_3_1_2_1_of_multilevel multilevel_16
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_1_2_2_of_multilevel_id_idx on child_3_1_2_2_of_multilevel multilevel_17
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_2_1_1_of_multilevel_id_idx on child_3_2_1_1_of_multilevel multilevel_18
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_2_1_2_of_multilevel_id_idx on child_3_2_1_2_of_multilevel multilevel_19
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_2_2_1_of_multilevel_id_idx on child_3_2_2_1_of_multilevel multilevel_20
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_2_2_2_of_multilevel_id_idx on child_3_2_2_2_of_multilevel multilevel_21
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_3_1_of_multilevel_id_idx on child_3_3_1_of_multilevel multilevel_22
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_3_3_2_of_multilevel_id_idx on child_3_3_2_of_multilevel multilevel_23
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_4_of_multilevel_id_idx on child_4_of_multilevel multilevel_24
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_5_of_multilevel_id_idx on child_5_of_multilevel multilevel_25
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_6_of_multilevel_id_idx on child_6_of_multilevel multilevel_26
+ Filter: ((id % 3) = 1)
+ -> Index Only Scan using child_7_of_multilevel_id_idx on child_7_of_multilevel multilevel_27
+ Filter: ((id % 3) = 1)
+(55 rows)
+
+-- Expected store operations and cache load operations only for
+-- multilevel and child_1_of_multilevel partitions (because only they have
+-- up to partition_path_cache_threshold (4) partitions).
+--
+-- CASE 1.4: check sequence scan path caching.
+SET enable_bitmapscan = off;
+SET enable_seqscan = on;
+SET enable_indexscan = off;
+SET enable_indexonlyscan = off;
+EXPLAIN (COSTS FALSE) SELECT * FROM big WHERE num = 2100;
+NOTICE: ppc: startup
+NOTICE: ppc: [1] store: SeqScan child_0_of_big
+NOTICE: ppc: [1] load : SeqScan child_1_of_big
+NOTICE: ppc: [1] store: SeqScan child_2_of_big
+NOTICE: ppc: [1] load : SeqScan child_3_of_big
+NOTICE: ppc: clean
+ QUERY PLAN
+-----------------------------------------
+ Append
+ -> Seq Scan on child_0_of_big big_1
+ Filter: (num = '2100'::numeric)
+ -> Seq Scan on child_1_of_big big_2
+ Filter: (num = '2100'::numeric)
+ -> Seq Scan on child_2_of_big big_3
+ Filter: (num = '2100'::numeric)
+ -> Seq Scan on child_3_of_big big_4
+ Filter: (num = '2100'::numeric)
+(9 rows)
+
+-- Expected store operations and cache load operations.
+--
+-- CASE 1.4: check bitmap heap scan path caching.
+SET enable_bitmapscan = on;
+SET enable_seqscan = off;
+EXPLAIN (COSTS FALSE) SELECT * FROM big WHERE num = 2100;
+NOTICE: ppc: startup
+NOTICE: ppc: [1] store: BitmapHeapScan child_0_of_big
+NOTICE: ppc: [1] load : BitmapHeapScan child_1_of_big
+NOTICE: ppc: [1] store: SeqScan child_2_of_big
+NOTICE: ppc: [1] load : BitmapHeapScan child_3_of_big
+NOTICE: ppc: clean
+ QUERY PLAN
+----------------------------------------------------
+ Append
+ -> Bitmap Heap Scan on child_0_of_big big_1
+ Recheck Cond: (num = '2100'::numeric)
+ -> Bitmap Index Scan on child_0_of_big_id
+ Index Cond: (num = '2100'::numeric)
+ -> Bitmap Heap Scan on child_1_of_big big_2
+ Recheck Cond: (num = '2100'::numeric)
+ -> Bitmap Index Scan on child_1_of_big_id
+ Index Cond: (num = '2100'::numeric)
+ -> Seq Scan on child_2_of_big big_3
+ Filter: (num = '2100'::numeric)
+ -> Bitmap Heap Scan on child_3_of_big big_4
+ Recheck Cond: (num = '2100'::numeric)
+ -> Bitmap Index Scan on child_3_of_big_id
+ Index Cond: (num = '2100'::numeric)
+(15 rows)
+
+-- Expected store operations and cache load operations.
+--
+-- CASE 1.5: check index scan path caching.
+SET enable_bitmapscan = off;
+SET enable_indexscan = on;
+EXPLAIN (COSTS FALSE) SELECT * FROM big WHERE num = 2100;
+NOTICE: ppc: startup
+NOTICE: ppc: [1] store: IndexScan child_0_of_big
+NOTICE: ppc: [1] load : IndexScan child_1_of_big
+NOTICE: ppc: [1] store: SeqScan child_2_of_big
+NOTICE: ppc: [1] load : IndexScan child_3_of_big
+NOTICE: ppc: clean
+ QUERY PLAN
+------------------------------------------------------------------
+ Append
+ -> Index Scan using child_0_of_big_id on child_0_of_big big_1
+ Index Cond: (num = '2100'::numeric)
+ -> Index Scan using child_1_of_big_id on child_1_of_big big_2
+ Index Cond: (num = '2100'::numeric)
+ -> Seq Scan on child_2_of_big big_3
+ Filter: (num = '2100'::numeric)
+ -> Index Scan using child_3_of_big_id on child_3_of_big big_4
+ Index Cond: (num = '2100'::numeric)
+(9 rows)
+
+-- Expected store operations and cache load operations.
+--
+-- CASE 1.6: check index only scan path caching.
+SET enable_indexscan = off;
+SET enable_indexonlyscan = on;
+EXPLAIN (COSTS FALSE) SELECT num FROM big WHERE num = 2100;
+NOTICE: ppc: startup
+NOTICE: ppc: [1] store: IndexOnlyScan child_0_of_big
+NOTICE: ppc: [1] load : IndexOnlyScan child_1_of_big
+NOTICE: ppc: [1] store: SeqScan child_2_of_big
+NOTICE: ppc: [1] load : IndexOnlyScan child_3_of_big
+NOTICE: ppc: clean
+ QUERY PLAN
+-----------------------------------------------------------------------
+ Append
+ -> Index Only Scan using child_0_of_big_id on child_0_of_big big_1
+ Index Cond: (num = '2100'::numeric)
+ -> Index Only Scan using child_1_of_big_id on child_1_of_big big_2
+ Index Cond: (num = '2100'::numeric)
+ -> Seq Scan on child_2_of_big big_3
+ Filter: (num = '2100'::numeric)
+ -> Index Only Scan using child_3_of_big_id on child_3_of_big big_4
+ Index Cond: (num = '2100'::numeric)
+(9 rows)
+
+-- Expected store operations and cache load operations.
+--
+-- Gether query results for CASE 2.2
+SET enable_indexscan = on;
+CREATE TEMPORARY TABLE case_1_1 AS
+ SELECT id FROM heterogen WHERE id % 8 = 1;
+NOTICE: ppc: startup
+NOTICE: ppc: [1] store: IndexOnlyScan child_0_of_heterogen
+NOTICE: ppc: [1] store: IndexOnlyScan child_1_of_heterogen
+NOTICE: ppc: [1] store: SeqScan child_2_of_heterogen
+NOTICE: ppc: [1] load : IndexOnlyScan child_3_of_heterogen
+NOTICE: ppc: [1] load : IndexOnlyScan child_4_of_heterogen
+NOTICE: ppc: [1] load : IndexOnlyScan child_5_of_heterogen
+NOTICE: ppc: [1] load : IndexOnlyScan child_6_of_heterogen
+NOTICE: ppc: [1] store: IndexOnlyScan child_7_of_heterogen
+NOTICE: ppc: [1] load : IndexOnlyScan child_8_of_heterogen
+NOTICE: ppc: clean
+CREATE TEMPORARY TABLE case_1_2 AS
+ SELECT id FROM multilevel WHERE id % 3 = 1;
+NOTICE: ppc: startup
+NOTICE: ppc: [1] store: IndexOnlyScan child_0_of_multilevel
+NOTICE: ppc: [2] store: IndexOnlyScan child_1_1_of_multilevel
+NOTICE: ppc: [2] load : IndexOnlyScan child_1_2_of_multilevel
+NOTICE: ppc: [2] load : IndexOnlyScan child_1_3_of_multilevel
+NOTICE: ppc: [2] load : IndexOnlyScan child_1_4_of_multilevel
+NOTICE: ppc: [1] load : IndexOnlyScan child_4_of_multilevel
+NOTICE: ppc: [1] load : IndexOnlyScan child_5_of_multilevel
+NOTICE: ppc: [1] load : IndexOnlyScan child_6_of_multilevel
+NOTICE: ppc: [1] load : IndexOnlyScan child_7_of_multilevel
+NOTICE: ppc: clean
+CREATE TEMPORARY TABLE case_1_4 AS
+ SELECT * FROM big WHERE num = 2100;
+NOTICE: ppc: startup
+NOTICE: ppc: [1] store: IndexScan child_0_of_big
+NOTICE: ppc: [1] load : IndexScan child_1_of_big
+NOTICE: ppc: [1] store: SeqScan child_2_of_big
+NOTICE: ppc: [1] load : IndexScan child_3_of_big
+NOTICE: ppc: clean
+-- Expected store operations and cache load operations.
+--
+--------------------------------------------------------------------------------
+-- Part 2. Compare queries results
+SET partition_path_cache_threshold = 0;
+--------------------------------------------------------------------------------
+SET enable_bitmapscan = on;
+SET enable_seqscan = on;
+SET enable_indexscan = on;
+SET enable_indexonlyscan = on;
+--
+-- CASE 2.1: gether query results when path cache is off.
+CREATE TEMPORARY TABLE results_for_case_1_1 AS
+ SELECT id FROM heterogen WHERE id % 8 = 1;
+CREATE TEMPORARY TABLE results_for_case_1_2 AS
+ SELECT id FROM multilevel WHERE id % 3 = 1;
+CREATE TEMPORARY TABLE results_for_case_1_4 AS
+ SELECT * FROM big WHERE num = 2100;
+-- Expected no cache operations (no `ppc` messages).
+--
+-- CASE 2.2: Compare results
+SELECT * FROM case_1_1 c
+ FULL JOIN results_for_case_1_1 e USING(id)
+ WHERE c.id IS NULL OR e.id IS NULL;
+ id
+----
+(0 rows)
+
+-- Expected 0 rows
+SELECT * FROM case_1_2 c
+ FULL JOIN results_for_case_1_2 e USING(id)
+ WHERE c.id IS NULL OR e.id IS NULL;
+ id
+----
+(0 rows)
+
+-- Expected 0 rows
+SELECT * FROM case_1_3 c
+ FULL JOIN results_for_case_1_4 e USING(id)
+ WHERE c.id IS NULL OR e.id IS NULL;
+ERROR: relation "case_1_3" does not exist
+LINE 1: SELECT * FROM case_1_3 c
+ ^
+-- Expected 0 rows
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index f53a526f7c..68baa693ad 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -119,7 +119,7 @@ test: plancache limit plpgsql copy2 temp domain rangefuncs prepare conversion tr
# The stats test resets stats, so nothing else needing stats access can be in
# this group.
# ----------
-test: partition_join partition_prune reloptions hash_part indexing partition_aggregate partition_info tuplesort explain compression memoize stats predicate
+test: partition_join partition_prune reloptions hash_part indexing partition_aggregate partition_info tuplesort explain compression memoize stats predicate path_cache
# event_trigger depends on create_am and cannot run concurrently with
# any test that runs DDL
diff --git a/src/test/regress/sql/path_cache.sql b/src/test/regress/sql/path_cache.sql
new file mode 100644
index 0000000000..6d1f3910bc
--- /dev/null
+++ b/src/test/regress/sql/path_cache.sql
@@ -0,0 +1,221 @@
+-- Init
+--------------------------------------------------------------------------------
+-- 'heterogen' table partitions have different set of indexes.
+CREATE TABLE heterogen(id int, name text) PARTITION BY RANGE (id);
+CREATE TABLE child_0_of_heterogen PARTITION OF heterogen FOR VALUES FROM (0) TO (100);
+CREATE INDEX child_0_of_heterogen_id ON child_0_of_heterogen (id);
+CREATE TABLE child_1_of_heterogen PARTITION OF heterogen FOR VALUES FROM (100) TO (200);
+CREATE INDEX child_1_of_heterogen_id ON child_1_of_heterogen (id) INCLUDE (name);
+CREATE TABLE child_2_of_heterogen PARTITION OF heterogen FOR VALUES FROM (200) TO (300);
+CREATE INDEX child_2_of_heterogen_id ON child_2_of_heterogen (id) WHERE (id % 2 = 0);
+CREATE TABLE child_3_of_heterogen PARTITION OF heterogen FOR VALUES FROM (300) TO (400);
+CREATE INDEX child_3_of_heterogen_id ON child_3_of_heterogen (id) INCLUDE (name);
+CREATE TABLE child_4_of_heterogen PARTITION OF heterogen FOR VALUES FROM (400) TO (500);
+CREATE INDEX child_4_of_heterogen_id ON child_4_of_heterogen (id);
+CREATE TABLE child_5_of_heterogen PARTITION OF heterogen FOR VALUES FROM (500) TO (600);
+CREATE INDEX child_5_of_heterogen_id ON child_5_of_heterogen (id) INCLUDE (name);
+CREATE TABLE child_6_of_heterogen PARTITION OF heterogen FOR VALUES FROM (600) TO (700);
+CREATE INDEX child_6_of_heterogen_id ON child_6_of_heterogen (id) INCLUDE (name);
+CREATE TABLE child_7_of_heterogen PARTITION OF heterogen FOR VALUES FROM (700) TO (800);
+CREATE INDEX child_7_of_heterogen_id ON child_7_of_heterogen (id);
+CREATE INDEX child_7_of_heterogen_name ON child_7_of_heterogen (name);
+CREATE TABLE child_8_of_heterogen PARTITION OF heterogen FOR VALUES FROM (800) TO (900);
+CREATE INDEX child_8_of_heterogen_id ON child_8_of_heterogen (id);
+CREATE INDEX child_8_of_heterogen_name ON child_8_of_heterogen (name);
+
+INSERT INTO heterogen
+ SELECT id, md5(id::text)
+ FROM generate_series(0, 899) AS id;
+
+ANALYZE heterogen;
+--------------------------------------------------------------------------------
+-- 'multilevel' table partitions have subpartitions witch have subpartitions
+CREATE TABLE child_1_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_1_1_of_multilevel PARTITION OF child_1_of_multilevel FOR VALUES FROM (100) TO (110);
+CREATE TABLE child_1_2_of_multilevel PARTITION OF child_1_of_multilevel FOR VALUES FROM (110) TO (125);
+CREATE TABLE child_1_3_of_multilevel PARTITION OF child_1_of_multilevel FOR VALUES FROM (125) TO (140);
+CREATE TABLE child_1_4_of_multilevel PARTITION OF child_1_of_multilevel FOR VALUES FROM (140) TO (200);
+
+CREATE TABLE child_2_1_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_2_1_1_of_multilevel PARTITION OF child_2_1_of_multilevel FOR VALUES FROM (200) TO (215);
+CREATE TABLE child_2_1_2_of_multilevel PARTITION OF child_2_1_of_multilevel FOR VALUES FROM (215) TO (225);
+CREATE TABLE child_2_1_3_of_multilevel PARTITION OF child_2_1_of_multilevel FOR VALUES FROM (225) TO (235);
+CREATE TABLE child_2_2_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_2_2_1_of_multilevel PARTITION OF child_2_2_of_multilevel FOR VALUES FROM (235) TO (245);
+CREATE TABLE child_2_2_2_of_multilevel PARTITION OF child_2_2_of_multilevel FOR VALUES FROM (245) TO (265);
+CREATE TABLE child_2_3_3_of_multilevel PARTITION OF child_2_2_of_multilevel FOR VALUES FROM (265) TO (275);
+CREATE TABLE child_2_3_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_2_3_1_of_multilevel PARTITION OF child_2_3_of_multilevel FOR VALUES FROM (275) TO (285);
+CREATE TABLE child_2_3_2_of_multilevel PARTITION OF child_2_3_of_multilevel FOR VALUES FROM (285) TO (300);
+
+CREATE TABLE child_2_of_multilevel(id int) PARTITION BY RANGE (id);
+ALTER TABLE child_2_of_multilevel ATTACH PARTITION child_2_1_of_multilevel FOR VALUES FROM (200) TO (235);
+ALTER TABLE child_2_of_multilevel ATTACH PARTITION child_2_2_of_multilevel FOR VALUES FROM (235) TO (275);
+ALTER TABLE child_2_of_multilevel ATTACH PARTITION child_2_3_of_multilevel FOR VALUES FROM (275) TO (300);
+
+CREATE TABLE child_3_1_1_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_3_1_1_1_of_multilevel PARTITION OF child_3_1_1_of_multilevel FOR VALUES FROM (300) TO (310);
+CREATE TABLE child_3_1_1_2_of_multilevel PARTITION OF child_3_1_1_of_multilevel FOR VALUES FROM (310) TO (320);
+CREATE TABLE child_3_1_2_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_3_1_2_1_of_multilevel PARTITION OF child_3_1_2_of_multilevel FOR VALUES FROM (320) TO (330);
+CREATE TABLE child_3_1_2_2_of_multilevel PARTITION OF child_3_1_2_of_multilevel FOR VALUES FROM (330) TO (340);
+
+CREATE TABLE child_3_1_of_multilevel(id int) PARTITION BY RANGE (id);
+ALTER TABLE child_3_1_of_multilevel ATTACH PARTITION child_3_1_1_of_multilevel FOR VALUES FROM (300) TO (320);
+ALTER TABLE child_3_1_of_multilevel ATTACH PARTITION child_3_1_2_of_multilevel FOR VALUES FROM (320) TO (340);
+
+CREATE TABLE child_3_2_1_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_3_2_1_1_of_multilevel PARTITION OF child_3_2_1_of_multilevel FOR VALUES FROM (340) TO (350);
+CREATE TABLE child_3_2_1_2_of_multilevel PARTITION OF child_3_2_1_of_multilevel FOR VALUES FROM (350) TO (360);
+CREATE TABLE child_3_2_2_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_3_2_2_1_of_multilevel PARTITION OF child_3_2_2_of_multilevel FOR VALUES FROM (360) TO (370);
+CREATE TABLE child_3_2_2_2_of_multilevel PARTITION OF child_3_2_2_of_multilevel FOR VALUES FROM (370) TO (380);
+
+CREATE TABLE child_3_2_of_multilevel(id int) PARTITION BY RANGE (id);
+ALTER TABLE child_3_2_of_multilevel ATTACH PARTITION child_3_2_1_of_multilevel FOR VALUES FROM (340) TO (360);
+ALTER TABLE child_3_2_of_multilevel ATTACH PARTITION child_3_2_2_of_multilevel FOR VALUES FROM (360) TO (380);
+
+CREATE TABLE child_3_3_of_multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_3_3_1_of_multilevel PARTITION OF child_3_3_of_multilevel FOR VALUES FROM (380) TO (390);
+CREATE TABLE child_3_3_2_of_multilevel PARTITION OF child_3_3_of_multilevel FOR VALUES FROM (390) TO (400);
+
+CREATE TABLE child_3_of_multilevel(id int) PARTITION BY RANGE (id);
+ALTER TABLE child_3_of_multilevel ATTACH PARTITION child_3_1_of_multilevel FOR VALUES FROM (300) TO (340);
+ALTER TABLE child_3_of_multilevel ATTACH PARTITION child_3_2_of_multilevel FOR VALUES FROM (340) TO (380);
+ALTER TABLE child_3_of_multilevel ATTACH PARTITION child_3_3_of_multilevel FOR VALUES FROM (380) TO (400);
+
+CREATE TABLE multilevel(id int) PARTITION BY RANGE (id);
+CREATE TABLE child_0_of_multilevel PARTITION OF multilevel FOR VALUES FROM (0) TO (100);
+ALTER TABLE multilevel ATTACH PARTITION child_1_of_multilevel FOR VALUES FROM (100) TO (200);
+ALTER TABLE multilevel ATTACH PARTITION child_2_of_multilevel FOR VALUES FROM (200) TO (300);
+ALTER TABLE multilevel ATTACH PARTITION child_3_of_multilevel FOR VALUES FROM (300) TO (400);
+CREATE TABLE child_4_of_multilevel PARTITION OF multilevel FOR VALUES FROM (400) TO (500);
+CREATE TABLE child_5_of_multilevel PARTITION OF multilevel FOR VALUES FROM (500) TO (600);
+CREATE TABLE child_6_of_multilevel PARTITION OF multilevel FOR VALUES FROM (600) TO (700);
+CREATE TABLE child_7_of_multilevel PARTITION OF multilevel FOR VALUES FROM (700) TO (800);
+
+INSERT INTO multilevel SELECT id FROM generate_series(0, 799) AS id;
+
+CREATE INDEX ON multilevel (id);
+
+ANALYZE multilevel;
+--------------------------------------------------------------------------------
+-- 'big' table has enough tuples for trigger non sequence scan path generation
+CREATE TABLE big (id serial, num numeric) PARTITION BY RANGE (id);
+CREATE TABLE child_0_of_big PARTITION OF big FOR VALUES FROM (0) TO (2500);
+CREATE INDEX child_0_of_big_id ON child_0_of_big(num);
+CREATE TABLE child_1_of_big PARTITION OF big FOR VALUES FROM (2500) TO (5000);
+CREATE INDEX child_1_of_big_id ON child_1_of_big(num);
+CREATE TABLE child_2_of_big PARTITION OF big FOR VALUES FROM (5000) TO (7500);
+-- NO INDEX
+CREATE TABLE child_3_of_big PARTITION OF big FOR VALUES FROM (7500) TO (10000);
+
+CREATE INDEX child_3_of_big_id ON child_3_of_big(num);
+
+INSERT INTO big
+ SELECT random() * 1000, generate_series(1, 9999);
+
+ANALYZE big;
+--------------------------------------------------------------------------------
+--------------------------------------------------------------------------------
+-- Testing procedure
+--
+-- Because path cache only affects the inner planner path build procedure,
+-- The only way to inspect is to use the result to inspect debug log messages
+-- and query results with results caught without cache.
+--------------------------------------------------------------------------------
+--------------------------------------------------------------------------------
+-- Part 1. Check path cache
+--------------------------------------------------------------------------------
+SET partition_path_cache_threshold = 2;
+SET partition_path_cache_debug = on;
+--------------------------------------------------------------------------------
+--
+-- CASE 1.1: check cache work in case where partitions have different set
+-- of indexes.
+SET enable_seqscan=off;
+EXPLAIN (COSTS FALSE) SELECT id FROM heterogen WHERE id % 8 = 1;
+-- Expected store operations and cache load operations.
+--
+-- CASE 1.2: check cache work in case of multilevel partitioned table used.
+EXPLAIN (COSTS FALSE) SELECT id FROM multilevel WHERE id % 3 = 1;
+-- Expected store operations and cache load operations operations for all
+-- partitioned tables in multilevel inheritance chain: multilevel,
+-- child_1_of_multilevel, child_2_x_of_multilevel, child_3_1_x_of_multilevel,
+-- child_3_2_x_of_multilevel, child_3_3_of_multilevel, child_3_3_of_multilevel
+--
+-- CASE 1.3: check that partition_path_cache_threshold limits cache usage
+-- for partitioned tables witch has less partition count.
+SET partition_path_cache_threshold = 4;
+EXPLAIN (COSTS FALSE) SELECT id FROM multilevel WHERE id % 3 = 1;
+-- Expected store operations and cache load operations only for
+-- multilevel and child_1_of_multilevel partitions (because only they have
+-- up to partition_path_cache_threshold (4) partitions).
+--
+-- CASE 1.4: check sequence scan path caching.
+SET enable_bitmapscan = off;
+SET enable_seqscan = on;
+SET enable_indexscan = off;
+SET enable_indexonlyscan = off;
+EXPLAIN (COSTS FALSE) SELECT * FROM big WHERE num = 2100;
+-- Expected store operations and cache load operations.
+--
+-- CASE 1.4: check bitmap heap scan path caching.
+SET enable_bitmapscan = on;
+SET enable_seqscan = off;
+EXPLAIN (COSTS FALSE) SELECT * FROM big WHERE num = 2100;
+-- Expected store operations and cache load operations.
+--
+-- CASE 1.5: check index scan path caching.
+SET enable_bitmapscan = off;
+SET enable_indexscan = on;
+EXPLAIN (COSTS FALSE) SELECT * FROM big WHERE num = 2100;
+-- Expected store operations and cache load operations.
+--
+-- CASE 1.6: check index only scan path caching.
+SET enable_indexscan = off;
+SET enable_indexonlyscan = on;
+EXPLAIN (COSTS FALSE) SELECT num FROM big WHERE num = 2100;
+-- Expected store operations and cache load operations.
+--
+-- Gether query results for CASE 2.2
+SET enable_indexscan = on;
+CREATE TEMPORARY TABLE case_1_1 AS
+ SELECT id FROM heterogen WHERE id % 8 = 1;
+CREATE TEMPORARY TABLE case_1_2 AS
+ SELECT id FROM multilevel WHERE id % 3 = 1;
+CREATE TEMPORARY TABLE case_1_4 AS
+ SELECT * FROM big WHERE num = 2100;
+-- Expected store operations and cache load operations.
+--
+--------------------------------------------------------------------------------
+-- Part 2. Compare queries results
+SET partition_path_cache_threshold = 0;
+--------------------------------------------------------------------------------
+SET enable_bitmapscan = on;
+SET enable_seqscan = on;
+SET enable_indexscan = on;
+SET enable_indexonlyscan = on;
+--
+-- CASE 2.1: gether query results when path cache is off.
+CREATE TEMPORARY TABLE results_for_case_1_1 AS
+ SELECT id FROM heterogen WHERE id % 8 = 1;
+CREATE TEMPORARY TABLE results_for_case_1_2 AS
+ SELECT id FROM multilevel WHERE id % 3 = 1;
+CREATE TEMPORARY TABLE results_for_case_1_4 AS
+ SELECT * FROM big WHERE num = 2100;
+-- Expected no cache operations (no `ppc` messages).
+--
+-- CASE 2.2: Compare results
+SELECT * FROM case_1_1 c
+ FULL JOIN results_for_case_1_1 e USING(id)
+ WHERE c.id IS NULL OR e.id IS NULL;
+-- Expected 0 rows
+SELECT * FROM case_1_2 c
+ FULL JOIN results_for_case_1_2 e USING(id)
+ WHERE c.id IS NULL OR e.id IS NULL;
+-- Expected 0 rows
+SELECT * FROM case_1_3 c
+ FULL JOIN results_for_case_1_4 e USING(id)
+ WHERE c.id IS NULL OR e.id IS NULL;
+-- Expected 0 rows
--
2.39.2
partition-path-cache-lin-2-32.pngimage/png; name=partition-path-cache-lin-2-32.pngDownload
�PNG
IHDR � �� sRGB ��� gAMA ���a pHYs � ��o�d ��IDATx^�� X���7�d��2�"��8EP���m�����y��&��e��}�7Mb���^9M�_��4���I��7mZ�%Z�8E���Q@�y���y�"�z{��s.���go=w�g��.���U�u """""""""�G��+�=a������������`������������`������������`������������`������������`��������������d�����Gy0� k��Q���'""""""""���k����CHH�q��|���>�O?�46n�h|BDDDDDDDDDCY������7X�j�q�A��3f�P�����^����+
]�&�=����FB���#G� OOO���GDDDDDDDDD4TY�_g������v�Z�����^�<��������$%%�xw+???��yqqqAMM�qd������]/��^�t=�C��^�O�x��b|�����S/�w��zY��1b������w�d��E���K��M?�0v���Z�M������t�l���5�����j���G����+33aaa����}������\O���1����S/�S/��^\�^�O��N��z�Z�m��%q(`L?2F���X�B�?z����i��%�$;'��e��i�]���?������#�������j$"""""""""�U���W_�eO��U���j$""""""""����+����������n��F"""""""""���F"""""""""���F"""""""""���F"""""""""���F"""""""""���F"""""""""���F"""""""""���F"""""""""���F"""""""""����:�}�JII1��*::�xG4�������k��'�;�(�3�'�3�'�3�'�3��~������7�����X��y����r����Wff&����#�����S/K���1�cT/�S/��^\�^�O��N��zq�z1>����~k���b��b�c"""""""""�_�WN���k���G�����{�=���������� I,���QX����f_���wx=��1�q��l$""""""""��N�M-
�Q���:l>��qt��l$""""""""b�*PR�o��ru����1�HDDDDDDDD4D����/G_�������b����~P��DDDDDDDDD�XKk�&��������H-�������������}��Gw��F""""""""�A���T�����G����Pt-��6��o���1����>\}���cZf#�q�:�L6
"2M��C/���G�'��7� �=s����DX��DSup�1�q�7|��o�L�2������DDDDDDDDDN��X|m��*�( G[;L1=�o��h,�GsS+���1o�<�\�s����k��NNN�5k������`�����������BIk�?R�V���2]Vs ��^���s�~ ����.n���5BBB������8���
���X�l��ILL��D�`����������������!/2�E�����3�k2�����D4_���z�*�+V`������0~���d#���/���`��������W�{[GL�_�����g���Z��� ������Q��'NTI���d#���r�yM
|����
�u�A�0�� 9>�,�W�
������K�t��dcJJ��1�zLDDDDDDDDD[��?g3�����a�:�*���O�����5��GM�0T^����=���������K}w X�_g��S�%����wD��������ya|��c��9c|�9c|�9c|�9��YV[�#�8U�
-�����;&���g�\�T���Vu���
�G�VC^lll��{a�J}/�-�hbJ:����WsU]]���5�S���L���G���]/��^�r=cT/��^\�^�O��N��zq�z1>��:�L�)_�\:�C�!�r�q�� s�v�%���Y�I�������8s�t�w��HDDDDDDDD4 d�E��Q�b�=%�(_��Y��C�C��y�t�F%����e��a��yZ�:1�HDDDDDDDD��.\=��I�Ti�.-S�e���qO�[?G{�H\8S���*Um8u�T,_�\��{�)��DDDDDDDDD}L��������g�Z�W���?�L�9f;������J�ASS��\�
F�d��F�l�L6����S������H}�U�pu�@\�w������"Y�.!??���
��%K�p�B�7��a����������H#�r�h?�9�~wh-��lF}s
�=#�*�g�v�sh�p��c�Q^^L�2����>}:�������0�HDDDDDDDD��|IN�P��h�bkc����N����G�����hhh���'bbb�r�J�?�����d��l$""""""""��WN���$?O�P%G�b���������,���p�����!88�/F||�zoeee�N���F""""""""�;$m��-_6�_����$���3�#1���v��O���+W���^\�b��f���R�l�l$""""""""�%�"�^d��~1
|Y�0~2g"m����<������nnnjFi��}�����ipb�����������-�MH-����>�*]��-�s�|�sxr�p��};!33��������0�|5a������7&���������n���[���|�(�r�u\�z���j�����A��:�M����B�P�����KU��������&���������:9Wr�z �&?�]��/�n����O�-�#"lcqd�I>|pppP-��*--��:=T�[�1%%E��t=&""""""""(�P���$%�( G1�.��}?�~ve#�c�.�9s
���T�^$�(�_d�Pg�~���Ou�X���6�
����!Y�L���I��1J���I���I���I�LW|�U��hA2��S{3���aF���[���F\�xQM�VVV������U�q0quu5���~K6���������\UWWk��}���K6q
3����^�O�,�z
��^�Q��N��zq�z1>��:�b|��u�u/�Y�\�������mj��������yE���\ddd��!�jq��1����:�C��s�F""""""""
*2����������N�^%����(�a������Tl�O�6����7pS�NEbb�z��D�P�d#
Z�}4o'�JY���y�.~���z��o�?�9�O��F.��Y���O������&�9���S��#""`kkk���&��������h�)�+��3�a��������+O��0�
Y�u�����_��u��s7v�����|X[[�V���,Z�j�F�=&��������hPhkoUS��=�5UzO�'�m�B�G��c���W<�?PQX�M�6����(//���&M��+V`��Y���0~G�SL6�E�n�����U���C/!��8lm�0#8?]�;�3�#�S�")) 'O�DCC�J*��9S%%�(IG�7L6�E�p��r�u�����z����/��@$F>�W�|�U�����{����m�������V��p�B�.�w�{�d#Y���������^��{�Ej�^���"*`>��}���sF/Gan�J0J����X
x�A/��-S�_|||���tb������������x�A//n{�:�{�7��i$�N���(-��\�p��i�*}��1TVV���QQQHLL���S���j����l$""""""""���R�������V�Z����'��DB�����(�a\�:����={��������9s�|�r�7vvv��J}��F""""""""2+��G��x��b,�����G�R �'f��Q�QXX�]�va������U�688���X�x1���`ee��S�`�����������T1��~���#��\��ixl���U:a��p����tU��o�>�����E�^���111���4~W�oL6��)��s��Q^�����
BR�^���%&��EC}#RSS�~�'N�@CC��q��iX�r��������]i�0�HDDDDDDDD����I��(�0�z��U������u��q��'0�5���8x� >��S������IM�;v��,�w��f�~���O����nm�#x2
����8"2/�O2w�Q2g�O2g�O2g�O�����
w"�R
Zj�9;D��bZ@F��s�����p�***�9I(���a���>|8�����=�����X��y�����Q�\�^����_D���^�O�,�z
��^�Q��N��zq�z1>��:�b|�5T�)U�g��P���WNg�@�0�� ����Q���EI0fdd���#ioo���P���`|��k���F-I������DDDDDDDD4x���b��?����_�����6v���.����=�A�h������y�f�*�nnn�>}:yK����l$""""""""-��[q�h?�=����(ve|���
����7'?�W�|�U����FQVV��$�L�6��8�|,]�TU4r?F��d#�S���������^z\U1F����o`�7���!��8�E������;v�yomm�1c� !!.�����;��a���������������Z������Q&H�$i�(���a�w���T-J��T1J5�T5���a���X�bf���]�\L6Q�]�.��3��*��{1�����#�>g;7�����(�H�M���+Wr?�A��F""""""""�Q�*��w�{�>AmS�-{1v�b�����������e��$i��8�0�HDDDDDDDD��]�L�^��-{1����(������8�s481�HDDDDDDDD7�&J�T�(��=#�_��~�X�|9���OOO��4�1�HDDDDDDDD7&J�z���D���buuuHMM�e?FgggL�:U%�U�i��1���#������R����[��1YS��qc�tMce�U�������~���4U�����*%�(�R�HCO��FI">��������x�bl�����X���c�=f�%""""""""KPVsIU1�^�R��^z�F���n[�(
�k�.$''#//O�V�"�������y��M6JQ��B����'"""""""�\�'J���qU�X�P��*�����������:^�m��}(--UU������+���D���+**n�`�iB��d�O""""""""2Ow:Q����g��Q����Cuu5\]]�>������������m�V�2��kHKuNN^}�U�L 6I<n���8�����������w�����������:�&�w��zY��d�M��z1>��}������^�O�x�����Y�N�|�A���go� ����0��fmo�������=�&J����s...�������:������d���U�QH����Uw���.�k�3/�l���:����DXX�qd�x��b|�e)�S0F�b���u�������������S��Xg������w���F���uDt�B�� =����\<�<���`J�vioooulN�z�Zg�m�/�����������8�I����G=��b��b�c""""""""�s�-�8t�3�f�3���5���Y%e����~���|�^o�h���}��s��^�����
��e�0o�<�L4���6�8m���2~���7Z�% ��|��j""""""""�{��G��xi�#�U�e�E�Q�a��g�~PU6v%C_�2p���j���+W`oo�I�&a��E�>}�ET����u�.�vjs�jd �^��N�`��u�����1�cT/�S/��^\�^�O��N��z�X�T,J�������^�R�(��������444��*��e ��5�����U��fC����4j""""""""x����/������N�^%���0��U�2]��Dcee%�9�����/�h��hi��viI�I���^1�HDDDDDDDd�j���'�����x{��8��-�M����x�>Db���ue���*))���{�m�6������AAA���G\\� C���DDDDDDDDf$��8�r�u���������pu������\��f����]Zv���������{�n5]���X�|9���OOO��Dz1�HDDDDDDD4�*���+�c���(�=���E[[+"FN�c3�WU�K'� #\�_�UMMMHKK��M�p��!TTT���S�LAbb"�N�
ggg��D}��F"""""""�����s%G����T�q��?�����^x`�j�����%&����U��)������HJJBjj�����Y�fa���?~<���C���DDDDDDDD�H������h������$%�?n�J:�����������������b���HHH��1c`eee|��0�HDDDDDDD��Tc��EZ��;�7��ii�^>� �&-���6�S�(,,��]�������<X[[����%K�`�����$�L6��"C^^�l>>�5�E�LZ�������0=immEVV�l��}�����T�FO�8+V�P-���������DDDDDDDD��6�h�Nl�����!�d}���*�t �7'?�W�|��M[����������x��|���8v��������i����###�"s�d#��������m�`��o"��i��:b�������������p�b���IRQ���d�d�$���0o�<,]�aaa������h �[�1%%E��t=&"""""""�4�-�8t�3�f�3�g�f�7�`�}�*�Y�������#�#��=�r��j��vii�nkkC@@ /^�~�=���9�j��x���K,FGG��^qq���Ed��d��d��d��d���+���c�;p���j�.����3����������f�Zggg���k��T-��/�������������~K6���������\��@0w\�^�������������R��`�������������S/�S/���d���y;p8�s5�E���q#�az�70�ov��������E%��Q>���\���P����s������\O]����DDDDDDDD=� ��y
���V��%���4 ������/c��������'O�DRRN�8��<nnn�9s��,-�*�Ht��l$"""""""����;�7���G���_�T�~u>*`>����J2.�XwG/u�7���p��a5�����hjj���#o} ���xL6]�������zI%��� �u��u�oN~�>��g<��Q���������{���������`$$$`��Ej��`�d#
i�-���&-���J�`��f�~?]�;���07d9����_��dDFnn.�o����w�a&R�����#&&���&�������h�� �G�v�������?���OP�P�`���~�|�c|;�����$2�%==]�J:tj�KTT���0u�TN��A��F"""""""2
*2���������/�����T�����T����0#8�6v�����C_���T���Y��r�J�7��
3�M4x1�HDDDDDDD�ZmS��l���~����[���������|�jo�;UYYy��/���W{2�3VVV���?&�������hPJ/=��}]����S�GqU.\<�(�a5MZ�J�t�;�b�����o�m�v��/����7��&�������h���/Cr��j�������hkk���x|����q����i��+zO�����#99�v�Baa!��u�d#Y���V�*�����d�<�C�������V�*�'f��I~�amec���kmmEff&�n�����\
}���T�1r��ML6�E�\]��g������yM�M���s�d�/U�1~�j�;z��wJ���9sF
}9~�8��������3gb���8q"�����h0c���������,FKk����������bO�'�i���@5���7����#b�4�W�9I*;vL
}�dccc#���1o�<,]�!!!�}�������)))����1Qw
*2�������G���7�}�4�m1#8�9���sq�����l�f��;WVV���H�tVV�����#..N�'��Y��������btt���h�����8"2/�O2w�Q2g�O2g�O2g�
-�8U���Rp�*�8��� �!&������q���������*�(�j100c���^�f��O�\]]�ww����&��cll�z5WR2���5�S/��7,,�82_��z1>����)�z1F��:�b|��u�������k��S���������mZH����X�?z |�F�s&ws=e�K^^��?���*uN�_Ghh� ��S/>?���N��HDDDDDDD���B��(�0�~��/�$�FD��3�������O%�x����T�Q�c<|��J4J��L�����&M��D#�P�d#
� -���o_�&K��i��8b��&����0�6�6�Y&K�8q�7o���'����f������#""�C_�4`����������Ue}ve|�W����SE�����s����U�1a���t������
U��i�&�����F,\� 5j����o��b����������\[{+���{�^RI�������R�P\:��M����c��LX[�{�aii)�����������\pp�J0J�Q�D���DDDDDDD�g��19�C�`�D�$�T1>�KU��(�a�:x���Bf�������]�PTT�Z��Ez������Q��D�w�l$"""""""��V1~���J:�p
��IO��b�9���F&KK����[q���:-C^d�Kbb��b ���&�������Hi��~��[���m���5s��sq�����T1
�r��i���S
���VI�i��a��*�hooo|�����DDDDDDDt���Q���I2�H���*���xc�#�_q�$�x��1|���8{�,�������9s��v���0N�& L6��*F��~�j��5������W�����_q��\��}��a��-���R��������� N�&`L6Q���6�R��+�cT7T�i�}),,��;T��������U�8o�<xyy�&���d#��ru6�y�+U�3���6��>�b�����L5�E����`gg��'��g�� 77}���H&��������+��1�� l�����!�d}���*����7'?�W�|�U��"�3��z466���3j?����������Di�,�&M�yb���������n�\����}d_9}K��o�sC��q���+����$���T�Q&M{xx &&��/GDDlmm�o���j���AJJ���V����;��W\\___����0>��1F��1>��1>�H���C8Y����������/���}�����8�WEE���QZZ��g#G���1c�#���O�\]]�wwo�������;�"�����5�S/�$,,�82_��z1>����)�z1F��:�b|��u�������3�U����6�����u���QM��5*�e�}�2�%##C%�} V�����\o���e)���S/]���6jI*vN,v=&""""""��'U��\|+e-�����?g�J4z���Q?��K>��S�j��Q���.��"�F�2n�85�e��Yw�h$"��=����������{1����+OWU��G?��.�����rN���&�?^
}9|�0������"�1FEEq�� �d#� ����SE����_�2Q�s���q_�����'�y�f�<y����`\�r�j���F"<�l$""""""d*���������#�!������}]�(d��T0J%czz��l��/,@BB��beee|��&��������s%G�����j������
�u�oN~�,������*F!{0�����oW{3
�" �E�qr0��d#�������U�Q��p�������X��}�����\�_�W{{;���T�q��](..V���EZ�c���Q��D440�HDDDDDDd�����_���Z����3��J1�5�'=�� �{����Di�,--�2Y�����uZ��DFF��e������m"*�l$""""""���5���I
{��R��*����X3�
<�G,}�vn���O���9s�6mR�_��������3gb���8q"��
aL6����L�#�m���$�~����4K'� />��?�9���4��7$�x��15�E��2���������e�����hhc�����������6�h�N������]�mm���7O��/��E����o�C,++��}��e�dee����� ,^�qqq�=� ��DDDDDDDf���6�yO�����7�W����X����^D��i���Naa���q����T-����*F�f���2�IDt��DDDDDDD���g.����v<�=Y����J
x�ii���iw��M�I�bNN��"��555j�E��Q�c�>}������;L6
���
�H��W���������������g�6`m�[j����K�������~�G�AUU�J*���2aZ&M}�����}*%%�xw���h���+..����qDd^�d��d��d��C���s8Z�9�.UU����3�1�w.l����V__�. //OU5�����a/~~~())a|����S?���l���5����~s�u�������0��|�������R��`�������������S/s^g}s
�����[�4iame����a#����PQQ���4�d4������#G�c�����������u�[�$;'�
F�U��G��xq�#�����D���;G�R_��|�%�l�����};rss��1c� !!����%�HDt7�g#�f�}�h?���,����p��ghim�X�H5��gs��������!���*�m�6���G�F���q����g����DD���F"""""""ML_�o_�����W����Q
|Y��?`��7��i��k���>|���pvv���S�|�rDEEq�i�d#�=�+O�_����������#\���O������Q?���(��}���'N�@RRN�<���U�����/�T6�&����������E�M��w��[)k�Z�W���/O�����sC��q��:�����q��l�����hiiQC_-Z��d�����m"���d#�(�+��3���/�xE�r����E���/��z#���{�����k������kkk5�e��%�BD���F""""""�^H/=����W����OP�\�`�|o�:���X:��2�E�����l�����Cii�j��8q"V�X�������&"�?L6uC�{�7����������#�����Q�����am�[��P�����8s���r��TUU���U
}�������BD��F""""""�.��r����U�t��wQVs �N#�|�X��!���a���^uu5�;���H�Q��xzzb��9X�t��bc������N���Gy��OVV�qX�f�����,��kko��K���������C?SC`&����_V�1.}�vn���{�-m�[�lQ/����� ���!>>AAA�BDf��d�������~}�/^�l��!!!��|�q�Fu��������I���������O�_A��T5Az���x~��T�Q�����yyyj��~�0R��e��a��y���6�MDd^�M6>��c�[��|)�R�=c����y��G"""""""K��UZ�K����������R�_��$�\��o����&���c���8x�������=&M����L�>]��HDd�z�F]QQ���&���KR����������]O��O�����sC������}���'N�PIFy���UIEI.&&&�d#�����j����!��2R��W_U�5�]�V�o�^x<���*������n����Jt'|}}Q\\l�/�sh�}�����%]O�������S/�w��zY�}ol�CZ�8{u?����9{'����D��n��m��N�{vII��`4qqq�������3�|.�e)���t�uTO�*�(��Q�i�d��U�n$�&��]�166�xg^d��%��s�zeff",��&��-�w��zY���Q��zq�z1>��:�b|��}�4>=�.J������oF>�����U�@����*���(� Y�����Z�h"{0�?eee�X����^^^���`|��u����K�:�m���E�O?����9z��zo�D�u�F!I������DDDDDDDwC���EV������r��������V���VL�������u��f�~�_�2EZ�l��UM��D�}����KUA��%���F���i��������?��
������8~��:����^U5
���@SK�q�����*/���B��� ��za#��o�����>}IIIj�jUU��1<<+W����S-�������M6��+i�6�t��|o������������"�]W�xe�GX>� x:�t�*++q���)x��Y466�}g�����-��vvv������Q�����x��Khjm4��J��6����!{����m�� i���,��%K��d�>MD4X1�HDDDDDDC���MV{1�s�9�+9;;�Z���`o��*��$%�( FI4J�Q�c��ABB�J4J���h(`���������^uC���3�o_��O���LK��$_^���F����;zcU�O0��:�+�--��*--��:moo��'�V�Y�f��JD4T0�HDDDDDDf��"9��J2����MU���c3�WC_d�����3������/%��O�2�E�����"C`d�����������H5��h(b���������J[{+N��[)k��=� �p�:0kc�R?�L�����KKK�w�^l��YYY�}z����7o�-[��r?F"��l$""""""�P�\�=Y����G�����W����z����������������\l���v�BQQ���0j�(���E�`|����l$"""""�u�� �:�{���l>�*������oN~Z�D�����^���GSS��?�M�6���C����������+Wb��������6�l$"""""��^z�z ���!��lV���zG��Y/���������u4��?���q��q�d<y�����N���c�2e
�c$"���DDDDDD�o$�x��g*����_�\����aFp~�h��}��f��?���}��e�dff������~�K�.EDDlmm�oQw�l$"""""�>W�P���?PS�����j�v�s���Ux���*�Y�1��?���XXXxc?���x�������N�%SRR��I�c""""""|���`��o��������m����(<<u-�'|��������>��~���������NX��?���������;��W\\___����0>��1F��1>��
���(����!��i�0��)���z����p�
T��pqq����u�n�����S?���^�[����t���U��J6�q�������f�/�w��zY���Q��zq�z1>��:�L�)�1~���}9I(�����~��b��DU���n�N��1##C�I���� <<�����������%��z
���=���������~�[��/n{�:�{�h�����V�1J�t_'%�({/~��g��mJJJ���T.��� !!.�D#�`�d#����o��PC_ve|���5�E��H�1~��~��Q��E'{/�������w������&M��+V`�������="���&����������[q��!l�������w�s|f��9��g�6`Fp�j��/'N���cg���*�(IFI6J�������DDDDDD���Z�7{^��C���+��rZ%g�~���O�~a#��o�i��v��qt+�r��i~!"�?L6Q�*�����{���!���7�cL�(�'|�oG�#\�o��b���Q{3J��$oG&MQ�b���������������bO�'hh�U�1~o�:�d\�
�vn���GCCN�<���$9rD��(��c����a��ou�����)S�#""�/L6�
�J�|e?�I~�����j?�iAam��m����8x� 6m�����������������+1k�,��=�����NNN�\PP�:&"���d#������y;������t�~��/���"F{N0��?�������;v 99yyy��$������`XYY�����X�l��ILLd���h�0�HDDDDD4D�7�`G�F��������(��U�1>0n����\��o����&�����O?��PVV;;;DDD`����3g����o��a�������h��!/2���m�`��P�P_�Qxx�Z��������c�������U�tjj*���T[���SU���:;;�&""s�d#��W�������w�{�7����Qxb��X��?`��x�>������w�^l�����j����#1o�<,]�TU4��""�L6
rg.��{��[)kq�h�:'�^d��Ss^����\��bVV�m��={����6665j�h�"������,G�%SRR��I�c""""""�G�]���x:�
.\=�a.X�����{���x����!��'O�T����Cee%���1q�D�X�BM����0�MDD���]F|��������;��'-�����ya|��c��9c|�9��5��8V�G�����Z�sw����"��l���TQQ��/���Kj��pss�����i�j$���'�3��~�W����d��)��^�Uuu�����N�d����0��|�������R��`����������������\]���I8��SU5�`�,�&������%���z�_5�������&J�H{������1�������O��N��z�Z'�l$"""""�`�WN�6i�"m�mm�*����obm�[��?���w��� ������~���D������l�25����DD4��l$"""""�0m��H-����y��S`d�����x.��x|��s�������J��(�1����?�T�L�:�����*{����0�HDDDDDd![��7{^��q����(������Z
}�������g|���i2Qz���j��L��������JF�h���5�MDD���DDDDDDf�����������N����R�T�v���� ~�j8����{�P���$%�( G��%K�`���j�
=L6���k9����X�}5�d}����-m��/�f�~P�O�i��ii���ii�vrr��)ST��������n|����"&�������Lz�q�s�9�z��������"�_�}�!/'N�PC_d������BLLV�X���������6
eL6����&�X�������_��a|�����#//�����c�����Q�F!>>�/Fpp0����y"""�d#� jl�����������ii���e������C_U���J<x���ppp@XXV�\���g�����6���l$""""" e5�����f��������HRQ��2YZ������RYY�#G� ))I����� ��9S�J�����#QO�l$"""""�G�x��kx}��7{��U{��IK���M������B�����mCNN����E�!!!!!!j�4Qo0�HDDDDD��\:�
���7{�����hkoU�^��U�_���U�$�ZZZ����-[�`��}())���"""�t�R��7#G�4�MDD�{L6�I(���7��#���+��rZU-�� �_�'U���4��v����VS��UZ^����S�NEbb�z�c""���d#�f��5�Ez���j�KqU.��`q�*5���Q?���/R�(�[�nU�MMM��������l�2U�hkkk|�����Y�_g��S)))��[EGG��^qq1|}}�#"���$s�%s����R�X��y[�e�.4���s���?�AL����^�}����(**Bnn.�]�������������:G�>?��1>���������k��n�����q����wn�������;�bj'0w\�^���3����^�O�,�z
��^�Q��N��zq�_u�� �2���{����������`����b��2EZ~���l�^�i�^�a/�������}��R����^\�^��{�V\�_^���6��dg��b�twk��6jI*vN,v=&"""""�4��S{1�di��Q�a#�������E0����������C��i��=��^^^������+1~���N4������[����
�l�9��HDDDDDt�d���{�U?�^�����$%���Q-??;v�@rr�j��&�x�b�#�����y""���+;���*��h��sL6��T-J��T1J5�T5��:b���x��?�{������ ^����������(++SU�R�(U�R�(U�DDD]54��`�5��R���[�M�\�����DDDDDD=���{�>�+�?�&K����H�(^J�+#����H��}���
��S�����������;�O����DL�2E��HDD�Yym3v�/�������f�D�$e��u�����5�y����d#�mT7T ���x5�1l>��:�r���S���>���Up�b|�o���={�`������R������p�B,Y����j�4�I�����<��������lQ��L�M��9o~g,~��@�����>�a��\?�������DDDDDD�W��
���Wco�&U����g���� �F������v����$%�(�FI8��������-�������c|�������v�L���$%�(�FI::���!nj��;������xp�}�f��N���C�����W��S�Q0�HDDDDDt]���j/�7��#�7c[{+&���������o���AZ��EZZ��eZZ�]]]1u�T�*-�rLDDT��zc�Ei��6ii���io�a����'������;Nv}[ �d#
i2M�������z/U�R��\�U5���&��[2�E�����"C`�rq��yX�t��h�����J""2o�UMH>����Sf��Q������G�W�
�o���}0��6�V���{L6��#���&����j���t�������~��/��@��}������HNN��;���kkk��� !!A�� +���K"����:|��e���9x�����p����C�p�s���U�X�|4������@`���������qW��j���'�BY�%�;z���2Yz���I�}���g��U��.\P G�"�Z�g�� ��_�'�R�2������>���[s��Z���F�-���,
�;���.>����tf����d#
z��ej�����[��YM���U�����0�J��:��;8r����p��i444��� 111X�r%&N�{���F!"��#�,�dT��*��������U��?�c�E�"�^d��~17L6��Ut-GM�~5�Q5Y���c�#�d�/��E0#8�V}�Q��Jb�����};rrr������`,^����W��*MD4���h�X\���� -�����hnmG�}j���V�Q�/�����/�
&�����h����K�~�k��,-������o b�4u�/����y�f���%%%�jQ��+V�P��^^^����h(�$���������,<�����1�r=��X�d�u��%�(�/J���X��?������������wD��������ya|��c��9c|
m�����%�^�.U��s2Yz�f����G��k555�x�"
��������a�������������O2g�O2g��5�m8_�����8]T�����8{k��q�D_GD�;��v`�]]]�wwo�������;�R]]���5�S���L���G���]/��^�r=cT/��^\�^�O��m�2Y�h�N�����"d��4�8�����2����T��_~��EKrQb����D'�S/�S/��^\�^���UM8�W���5�,�Ck����H7;����@��h6m���{��QKR�sb��1�����;�7����H}[%�\����O��>��1���D��J���c��-��w�J4���!""K�.��y�zL4���QR�Z��}��g����GJ�V\�>���U3G����U?O�p'���np�F"""""�(���/n{���&Kz���Y/���?bn�r�>�������j�����A�M����DL�:�"���������2�E����[&^�����\�lTS��qSS����?�'���;&������"W��2YZ��'��V_~��w�}_O���E�`�JF�hliiQ����?��-S�|�������h��nh���J�vg��0o�(@JF%�����y��{�� �x�?��fA b�W�2%L6�Y�p��t������,=#8���U�8�;R��+�P�}��n��={���e�Khh�j�^�`������'���3WU����(������FCs������jr�L��I�2Qz0�G���DDDDDd��\:���>�~���F��/��U����m����Q[[���T�*}��qTUU���QQQX�r%�O���L��c�Q�^4��(��$%�(�EI2J�Q�����F"""""2m���zQ���Q��������xe�GH�|��^���FII ������7#--M
������9s�|�r�7N
�!"�������Q�_�vh�Q���MZ���m����F"""""p�����(�1����?���H�\\��!���������������m��{�n���c��ABB���+���GD4�������w�
�v�EI4J�Q��3^!"""""02I:9�C5YZ&L��i��!�M�������r�t]]N�<�Z��;���J888 22+V���Y����a|���,���f$�-�k�����I)���U7�_L���������=`��������]Y�%�\|��G�y���o�Q�^d���mP`�r���+Wp��|���8�<������g��'N����DDd�.������t?�8.AZq��l��3V���o��������>���c���G��#-��������F�����x}�U���OO�����oa��7���"��.\�����s�N��������X�x1���1j�(�JY8��lQ-�|��l��I���yWT���n�-��<��F�DOx�r�E]�M6J�����G}����/��� ������{�8KDDDDDt{�WN������w�������T/>�GU���������>}ZU1>|�������U�tLL���v�����/�j{v�U����m��g����xfQ������*���n���D�ikb�����������N��t���6�_������uT�0����q�k��M�$�x��Al�� g��UIGwww��9����2e
����o��)�o�v�E?w{���KGa�����\?D�b�
���Z��l<z�(BBB�#`��7��e�""""""i�>����x:�
*2�������K U���/���#//�����*�^`���X�d�����
�Y��,Q��������c�������U3G����������/���c�n��-���7b��
����
A����������bcc�w�����������:����DXX�qd�x��b|�e)�S0F�b���u������u���������O5eZx��a��e��`�N������lu���6l�J,�����ue|��u�������s��bFI��V!5�F�E��� �\�����-z�����2���^R{3vG�{����d��������������82_\������S/K�������]/��^�z��[�q�j
��Dck�:����^�>V�k��+uuu())Aee%����9�"=b�5Q������;>����S/�w�z�M�@��vd��!����8���B���1����������{�&M���_~Y�K��He��������g��)�h��&���,e��W;��N���1F�b���u���������K���h�N�:-�zGbQ�w1r�:��W����������8���$����������Kz1>��}�k �)�_�U����:���LW���3F�b���-m��O�t���d�/�������$e*u����j���F��N����������cT/��^\�^�O�2/����$�+>����r�I~��]z��unllT��)�B�^3f���������0>��sI/��^��z��:��6��hi���&6�V;�S�]1���H��o����K�:�v�F��l�����*��N���1F�b���u����#�r*vflD����X�`�0q�����}E�J�=���EkkGr���Y�S������ e|����^�O�x����uJ�bfi��
�+�7�_tf� ~�w��"�S/]����v"""""(R�x�h?~�k
�9��J4:�:c���x���*��>I4JMD~~>v��������FI4���`��yX�|9���m�����CCs�J,��R���Q&^�,�g�U���yb�����@��:?���0w��B��d#}����?g3^��C��5]����?$�?����O�c����������7����r��j��
���,\����2~��k�-H����;
�����������Vx�#1������V����~��q�
�����DDDDDtC}s
v�o�+�?����#�������d\�JU6�&���;�M�6!55���prr��)S�����3g��Cr����(�j��Sexuk.��-������j������X=��}8��V���d����F"""""BuC�N��W�����c��!xl��x.����\�����Jb�����m���T����7����+V`������7~����:||�2��{����rN�_�;O��������?�����_I���DDDDDC�T.n��M���{�7������xj�����
��?�Vz���V���t�*�o�>�����*-��qqq
b�4��inmW��R�(��R�(��R�h�Q����$%�(�GZx������� ���O�_�k;������$��*��f����TUU����#)) 'N�P�����TU��f�b�4���}e�E�wQ�_�}e?F�������/J�4�_��l$""""B2/�b��uj���K�Tk���8�*���U��nEEE��g�n����L������111X�r%&N����DDd������29Z&H�$i�(-���}����x�;c��C�����F""""�A���U%%������}�4��`���j����g��L��[�l���{Q\\�Z�G����x,^����l�&"2yW����������K��p ��ka}�1����=�����l�F�����&��������&�M��;�Z��u����[���Gb���X���j�"-�1��K��T/J��������i|���Jk[;����C%xfc�J2&�������5����'q����G�W����A��481�HDDDD4����������o�!0R�(�E�d��ZU6�$��R�(��R�(���T���$e_F�J
,i��"�J�E?���j{v�/Gym��T|p�}�r�W������TE#�_�;�o�����c���������MuC��� �&?�����c��Q��eOFi��=u��eF��Q�d���-Z���MZ���mZ����h`H"qWZ�J,���
{
��I<�^������({0��9R��h#��Dw���:�}��.�m�#x�/������ya|��c��9��Y^W�#�8V�S�N���0+p �����u�����PPP���fu���N%����^���������2]������8[\��W;�wAH1l�=��;b��<�l�O,�S?WWW�����d��)��^���-���5�S/�����0��|�������R��`�������k��������O�(�����I~�1/$c�#��N%%%�ZJ������c#�S/>��b|�5������YZ�&F������f��a�5��\0%�U�E���a|�5���{6Y�&-_d���������8�l�<>�E�����Vdeea��m��{7
���� ���!!!!!!l�&"�g�-����w ���L��Y����D�pG[5�e]|�� �fA b��U���^1������,��K����g�a�:�^�_�}e?F��Q�g���������i�;���J�=~�x,Z�s�������m""��
�H����;
�����Y�}����xY6�K
x���0<1��.�B���F"""""3&��G�v�*F�f�p���$����j��L��I��\�r���������J���c���HLL��)S���h|�����T*~v�*^����������j4��e����G�/D��F"""""3$�^�fo��;��_���gtu�P����G����Xi���������s�N�����X�p!�,Y���P�J���e�������?s������H)2J�T��Dg� ��[���G#1�~��E���F"""""3R�\������"���(���*��VU2J��T6������'O")) G�AEE��*=n�8,_���������m""�+2��lQ->8T�g6f����HJ-CaE��gQ�[�}e���'c�8x:3~5�ya�������T7T������������X�`|l��jO�Y����:�������j?�������nnn�Uz�����������m""�2����*��R�'���_m�����(�mV�����*������X���/d�DDDDDH*?>���d<��YU6�4������KO��k�{o_�V���\$''c�����C{{;����`�,]����DD}����Fr��q��B������9��S����1�E���>�e���^��U� _N�k�������{�d#� �=�?�����pn���q������a��76"�����V��g���O?��C�P^^�Z�#""�l�2��?�������H7���T����>����.�A[;T2q�,�\�$�$%�H�o$�xv)P�
�7^=�[\�j|��1�HDDDD���������K�*�����S���&������+I*JrQ���O�VIGi��6m��*=u�T����&""�d��xY�I�����]V��m�T;��E��:L�I�O����4pr~����*�����;�d#Q?8s��JY�
��!����Q����VE?����7���E�$i�(-���6-���[����`kkk�
""����]U+J��x�*F�r��Q%e��$�+�_
z��/Nv���H�I��-��J���q������c������������h�N�*���� �<]M�~`�j���#$F> wG/��wO����b<p� �\��Vi"�>V����[���B�����(�1����nvH���KG�������a6��@���A�������$��J�K]8�2��9&�����4���fo����b��o�ru\<TrQ����V���������c������'O������DD}H��g�����>�T���^�R^�}��P������G��9�~�Sr����F|}������l��1�e�9&�����4�I��ib���H:�.*���������'|����}�^H�taa!v���m��!++���DD}(�j�u�
��tA�Hx�g�:���j�'����E�b�jF�j$�Ww�\���_������'�#�)������?������`u�+��K���r�������;��W\\�#2[�O2w�Q2g}�5������/�v���A��s����T�uhnnFAA.\����zun��a��Q�������������P����vd^n���z�*����V��/���������_����|~����.6��aSs����j�u�K�]Z]���e�z�����1�����X��y�������S���LU `�x��b|�e)�S0F�b���u��W�YVs ;36�D�^�:-�FD!.|�zG��;q��YUU��/I���uNZ��?��1c�������zq�z
���6h��e^5R�k�~�&�m����0����]d|�5$������\=���Zc|h���c�������oQ�}��d��)�h�IF>