Hi,
On Thu, Feb 20, 2025 at 5:28 PM Ashutosh Bapat
<ashutosh.bapat....@gmail.com> wrote:
>
> On Tue, Feb 4, 2025 at 4:07 PM Ashutosh Bapat
> <ashutosh.bapat....@gmail.com> wrote:
> >
> > If we are not interested in saving memory, there is a simpler way to
> > improve planning time by adding a hash table per equivalence class to
> > store the derived clauses, instead of a linked list, when the number
> > of derived clauses is higher than a threshold (say 32 same as the
> > threshold for join_rel_list. Maybe that approach will yield stable
> > planning time.
> >
I implemented the above idea in attached patches. I also added the
following query, inspired from Alvaro's query, to summarise the
results.
with master_avgs as
(select code_tag, num_parts, num_joins, pwj, avg(planning_time_ms)
avg_pt, stddev(planning_time_ms) stddev_pt
from msmts where code_tag = 'master'
group by code_tag, num_parts, num_joins, pwj),
patched_avgs as
(select code_tag, num_parts, num_joins, pwj, avg(planning_time_ms)
avg_pt, stddev(planning_time_ms) stddev_pt
from msmts where code_tag = 'patched'
group by code_tag, num_parts, num_joins, pwj)
select num_parts,
num_joins,
format('s=%s%% md=%s%% pd=%s%%',
((m.avg_pt - p.avg_pt)/m.avg_pt * 100)::numeric(6, 2),
(m.stddev_pt/m.avg_pt * 100)::numeric(6, 2),
(p.stddev_pt/p.avg_pt * 100)::numeric(6, 2))
from master_avgs m join patched_avgs p using (num_parts, num_joins,
pwj) where not pwj order by 1, 2, 3;
\crosstabview 1 2 3
not pwj in the last line should be changed to pwj to get results with
enable_partitionwise_join = true.
With the attached patches, I observe following results
With PWJ disabled
num_parts | 2 | 3
| 4 | 5
-----------+-------------------------------+------------------------------+----------------------------+-----------------------------
0 | s=-4.44% md=17.91% pd=23.05% | s=-0.83% md=11.10%
pd=19.58% | s=0.87% md=4.04% pd=7.91% | s=-35.24% md=7.63% pd=9.69%
10 | s=30.13% md=118.18% pd=37.44% | s=-3.49% md=0.58%
pd=0.49% | s=-0.83% md=0.29% pd=0.35% | s=-0.24% md=0.35% pd=0.32%
100 | s=1.94% md=13.19% pd=4.08% | s=-0.27% md=0.18%
pd=0.44% | s=7.04% md=3.05% pd=3.11% | s=12.75% md=1.69% pd=0.81%
500 | s=4.39% md=1.71% pd=1.33% | s=10.17% md=1.28%
pd=1.90% | s=23.04% md=0.24% pd=0.58% | s=30.87% md=0.30% pd=1.11%
1000 | s=4.27% md=1.21% pd=1.97% | s=13.97% md=0.44%
pd=0.79% | s=24.05% md=0.63% pd=1.02% | s=30.77% md=0.77% pd=0.17%
Each cell is a triple (s, md, pd) where s is improvement in planning
time using the patches in % as compared to the master (higher the
better), md = standard deviation as % of the average planning time on
master, pd = is standard deviation as % of the average planning time
with patches.
With PWJ enabled
num_parts | 2 | 3
| 4 | 5
-----------+------------------------------+------------------------------+-----------------------------+------------------------------
0 | s=-94.25% md=6.98% pd=56.03% | s=44.10% md=141.13%
pd=9.32% | s=42.71% md=46.00% pd=6.55% | s=-26.12% md=6.72% pd=15.20%
10 | s=-25.89% md=4.29% pd=63.75% | s=-1.34% md=3.15% pd=3.26%
| s=0.31% md=4.13% pd=4.34% | s=-1.34% md=3.10% pd=6.73%
100 | s=-2.83% md=0.94% pd=1.31% | s=-2.17% md=4.57% pd=4.41%
| s=0.98% md=1.59% pd=1.81% | s=1.87% md=1.10% pd=0.79%
500 | s=1.57% md=3.01% pd=1.70% | s=6.99% md=1.58% pd=1.68%
| s=11.11% md=0.24% pd=0.62% | s=11.65% md=0.18% pd=0.90%
1000 | s=3.59% md=0.98% pd=1.78% | s=10.83% md=0.88% pd=0.46%
| s=15.62% md=0.46% pd=0.13% | s=16.38% md=0.63% pd=0.29%
Same numbers measured for previous set of patches [1], which improves
both memory consumption as well as planning time.
With PWJ disabled
num_parts | 2 | 3
| 4 | 5
-----------+-------------------------------+------------------------------+------------------------------+--------------------------------
0 | s=4.68% md=18.17% pd=22.09% | s=-2.54% md=12.00%
pd=13.81% | s=-2.02% md=3.84% pd=4.43% | s=-69.14% md=11.06%
pd=126.87%
10 | s=-24.85% md=20.42% pd=35.69% | s=-4.31% md=0.73%
pd=1.53% | s=-14.97% md=0.32% pd=31.90% | s=-0.57% md=0.79% pd=0.50%
100 | s=0.27% md=4.69% pd=1.55% | s=4.16% md=0.29% pd=0.18%
| s=11.76% md=0.85% pd=0.49% | s=15.76% md=1.64% pd=2.32%
500 | s=0.54% md=1.88% pd=1.81% | s=9.36% md=1.17% pd=0.87%
| s=21.45% md=0.74% pd=0.88% | s=30.47% md=0.17% pd=1.17%
1000 | s=3.22% md=1.36% pd=0.99% | s=14.74% md=0.86%
pd=0.44% | s=24.50% md=0.36% pd=0.31% | s=27.97% md=0.27% pd=0.25%
With PWJ enabled
num_parts | 2 | 3
| 4 | 5
-----------+-----------------------------+----------------------------+----------------------------+-----------------------------
0 | s=11.07% md=19.28% pd=8.70% | s=-1.18% md=5.88% pd=4.31%
| s=-2.25% md=8.42% pd=3.77% | s=25.07% md=11.48% pd=3.87%
10 | s=-9.07% md=2.65% pd=14.58% | s=0.55% md=3.10% pd=3.41%
| s=3.89% md=3.94% pd=3.79% | s=7.25% md=2.87% pd=3.03%
100 | s=-4.53% md=0.49% pd=8.53% | s=2.24% md=4.24% pd=3.96%
| s=6.70% md=1.30% pd=2.08% | s=9.09% md=1.39% pd=1.50%
500 | s=-1.65% md=1.59% pd=1.44% | s=6.31% md=0.89% pd=1.11%
| s=12.72% md=0.20% pd=0.29% | s=15.02% md=0.28% pd=0.83%
1000 | s=1.53% md=1.01% pd=1.66% | s=11.80% md=0.66% pd=0.71%
| s=16.23% md=0.58% pd=0.18% | s=17.16% md=0.67% pd=0.68%
There are a few things to notice
1. There is not much difference in the planning time improvement by
both the patchsets. But the patchset attached to [1] improves memory
consumption as well. So it looks more attractive.
2. The performance regressions usually coincide with higher standard
deviation. This indicates that both the performance gains or losses
seen at lower numbers of partitions and joins are not real and
possibly ignored. I have run the script multiple times but some or
other combination of lower number of partitions and lower number of
joins shows higher deviation and thus unstable results. I have not be
able to find a way where all the combinations show a stable result.
I think the first patch in the attached set is worth committing, just
to tighten things up.
[1]
https://www.postgresql.org/message-id/caexhw5t6npgaif6zo_p+l1cpzk27+ye2lxfqrvxf0oissw9...@mail.gmail.com
--
Best Wishes,
Ashutosh Bapat
From b374c889e646fffac56785cb79031fd172a40b11 Mon Sep 17 00:00:00 2001
From: Ashutosh Bapat <ashutosh.bapat....@gmail.com>
Date: Thu, 20 Feb 2025 11:45:28 +0530
Subject: [PATCH 1/2] Add Assert in find_derived_clause_for_ec_member()
find_derived_clause_for_ec_member() should find a clause of equating the given
EM to a constant. Assert the same.
Author: Ashutosh Bapat
---
src/backend/optimizer/path/equivclass.c | 3 +++
1 file changed, 3 insertions(+)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 0f9ecf5ee8b..493a95d26cc 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -2664,7 +2664,10 @@ find_derived_clause_for_ec_member(EquivalenceClass *ec,
* members on the left side of derived clauses.
*/
if (rinfo->left_em == em)
+ {
+ Assert(rinfo->right_em->em_is_const);
return rinfo;
+ }
}
return NULL;
}
base-commit: 363a6e8c6fcf9f3e19fe673ae02554645974a388
--
2.34.1
From 8a147b3871d06aa00b5786f9b820f48459ff044d Mon Sep 17 00:00:00 2001
From: Ashutosh Bapat <ashutosh.bapat....@gmail.com>
Date: Tue, 18 Feb 2025 17:06:35 +0530
Subject: [PATCH 2/2] Make EquivalenceClass clause lookup faster
EquivalenceClass::ec_derives is used to lookup a clause derived from the
EquivalenceClass by one or both the EquivalenceMembers that it contains.
The derived clauses are maintained as a list. For a small number of
clauses looking up a list of does not impact performance much. When
there are thousands of partitions in a partitioned table, there can be
thousands of derived clauses in the list making it inefficient for a
lookup. In order to improve the lookup performance, we convert the list
into a hash table similar to PlannerInfo::join_rel_list. When the number
of entries in ec_derives grows beyond 32, same threshold at which
PlannerInfo::join_rel_hash is created, we create
EquivalenceClass::ec_derives_hash from EquivalenceClass::ec_derives_list
(new name for EquivalenceClass:ec_derives). After that both the list and
hash table are maintained because of _outEquivalenceClass, which can
output the list easily instead of a hash table. Hash table and the list
both are looked up by left_em, right_em and parent_ec members of the
RestrictInfo.
When a clause is looked up by one EquivalenceMember it is expected that
the other EquivalenceMember in the clause is constant, which is the only
constant EquivalenceMember of in the EquivalenceClass. All the clauses
derived from such an EquivalenceClass have their RHS as the constant
EquivalenceMember. The derived clauses are looked up only by the
non-constant EquivalenceMember. The constant EquivalenceMember may
not be available at the time of lookup and is not required. Hence we use
NULL instead of right_em in the hash table key.
Ashutosh Bapat
---
src/backend/nodes/outfuncs.c | 7 +-
src/backend/optimizer/path/costsize.c | 3 +-
src/backend/optimizer/path/equivclass.c | 353 +++++++++++++++++-----
src/backend/optimizer/plan/analyzejoins.c | 5 +-
src/include/nodes/pathnodes.h | 17 +-
src/include/optimizer/paths.h | 4 +-
src/tools/pgindent/typedefs.list | 2 +
7 files changed, 312 insertions(+), 79 deletions(-)
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index bb9bdd67192..642ead7e629 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -467,7 +467,12 @@ _outEquivalenceClass(StringInfo str, const EquivalenceClass *node)
WRITE_OID_FIELD(ec_collation);
WRITE_NODE_FIELD(ec_members);
WRITE_NODE_FIELD(ec_sources);
- WRITE_NODE_FIELD(ec_derives);
+ WRITE_NODE_FIELD(ec_derives_list);
+
+ /*
+ * ec_derives_list and ec_derives_hash contain the same set of
+ * RestrictInfos, hence no need to write contents of ec_derives_hash.
+ */
WRITE_BITMAPSET_FIELD(ec_relids);
WRITE_BOOL_FIELD(ec_has_const);
WRITE_BOOL_FIELD(ec_has_volatile);
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 73d78617009..cc62be7221e 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -5839,7 +5839,8 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
if (ec && ec->ec_has_const)
{
EquivalenceMember *em = fkinfo->fk_eclass_member[i];
- RestrictInfo *rinfo = find_derived_clause_for_ec_member(ec,
+ RestrictInfo *rinfo = find_derived_clause_for_ec_member(root,
+ ec,
em);
if (rinfo)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 493a95d26cc..06ab84c0160 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -20,6 +20,7 @@
#include "access/stratnum.h"
#include "catalog/pg_type.h"
+#include "common/hashfn.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/appendinfo.h"
@@ -72,8 +73,41 @@ static Bitmapset *get_eclass_indexes_for_relids(PlannerInfo *root,
Relids relids);
static Bitmapset *get_common_eclass_indexes(PlannerInfo *root, Relids relids1,
Relids relids2);
+static void add_derived_clauses(EquivalenceClass *ec, List *clauses);
+static void add_derived_clause(EquivalenceClass *ec, RestrictInfo *clause);
+static RestrictInfo *search_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec);
+static RestrictInfo *search_derived_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec);
+static void add_clause_to_derives_hash(EquivalenceClass *ec, RestrictInfo *rinfo);
+static void build_ec_derives_hash(PlannerInfo *root, EquivalenceClass *ec);
+/* Hash key for derived clause lookup by EquivalenceMembers. */
+typedef struct
+{
+ EquivalenceMember *em1;
+ EquivalenceMember *em2;
+ EquivalenceClass *parent_ec;
+} ECDerivesKey;
+
+/* Hash table entry in ec_derives_hash. */
+typedef struct
+{
+ uint32 status;
+ ECDerivesKey key;
+ RestrictInfo *rinfo;
+} ECDerivesEntry;
+
+#define SH_PREFIX derives
+#define SH_ELEMENT_TYPE ECDerivesEntry
+#define SH_KEY_TYPE ECDerivesKey
+#define SH_KEY key
+#define SH_HASH_KEY(tb, key) hash_bytes((const unsigned char *) &(key), sizeof(ECDerivesKey))
+#define SH_EQUAL(tb, a, b) ((a).em1 == (b).em1 && (a).em2 == (b).em2 && (a).parent_ec == (b).parent_ec)
+#define SH_SCOPE static inline
+#define SH_DECLARE
+#define SH_DEFINE
+#include "lib/simplehash.h"
+
/*
* process_equivalence
* The given clause has a mergejoinable operator and is not an outer-join
@@ -342,7 +376,7 @@ process_equivalence(PlannerInfo *root,
*/
ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
- ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
+ add_derived_clauses(ec1, ec2->ec_derives_list);
ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
ec1->ec_has_const |= ec2->ec_has_const;
/* can't need to set has_volatile */
@@ -355,7 +389,7 @@ process_equivalence(PlannerInfo *root,
/* just to avoid debugging confusion w/ dangling pointers: */
ec2->ec_members = NIL;
ec2->ec_sources = NIL;
- ec2->ec_derives = NIL;
+ clear_ec_derived_clauses(ec2);
ec2->ec_relids = NULL;
ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
ec1->ec_min_security = Min(ec1->ec_min_security,
@@ -412,7 +446,8 @@ process_equivalence(PlannerInfo *root,
ec->ec_collation = collation;
ec->ec_members = NIL;
ec->ec_sources = list_make1(restrictinfo);
- ec->ec_derives = NIL;
+ ec->ec_derives_list = NIL;
+ ec->ec_derives_hash = NULL;
ec->ec_relids = NULL;
ec->ec_has_const = false;
ec->ec_has_volatile = false;
@@ -671,7 +706,8 @@ get_eclass_for_sort_expr(PlannerInfo *root,
newec->ec_collation = collation;
newec->ec_members = NIL;
newec->ec_sources = NIL;
- newec->ec_derives = NIL;
+ newec->ec_derives_list = NIL;
+ newec->ec_derives_hash = NULL;
newec->ec_relids = NULL;
newec->ec_has_const = false;
newec->ec_has_volatile = contain_volatile_functions((Node *) expr);
@@ -1026,7 +1062,7 @@ relation_can_be_sorted_early(PlannerInfo *root, RelOptInfo *rel,
* scanning of the quals and before Path construction begins.
*
* We make no attempt to avoid generating duplicate RestrictInfos here: we
- * don't search ec_sources or ec_derives for matches. It doesn't really
+ * don't search source or derived clauses for matches. It doesn't really
* seem worth the trouble to do so.
*/
void
@@ -1188,11 +1224,11 @@ generate_base_implied_equalities_const(PlannerInfo *root,
/*
* If the clause didn't degenerate to a constant, fill in the correct
- * markings for a mergejoinable clause, and save it in ec_derives. (We
- * will not re-use such clauses directly, but selectivity estimation
- * may consult the list later. Note that this use of ec_derives does
- * not overlap with its use for join clauses, since we never generate
- * join clauses from an ec_has_const eclass.)
+ * markings for a mergejoinable clause, and save it as a derived
+ * clause. (We will not re-use such clauses directly, but selectivity
+ * estimation may consult those later. Note that this use of derived
+ * clauses does not overlap with its use for join clauses, since we
+ * never generate join clauses from an ec_has_const eclass.)
*/
if (rinfo && rinfo->mergeopfamilies)
{
@@ -1200,7 +1236,7 @@ generate_base_implied_equalities_const(PlannerInfo *root,
rinfo->left_ec = rinfo->right_ec = ec;
rinfo->left_em = cur_em;
rinfo->right_em = const_em;
- ec->ec_derives = lappend(ec->ec_derives, rinfo);
+ add_derived_clause(ec, rinfo);
}
}
}
@@ -1265,10 +1301,10 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
/*
* If the clause didn't degenerate to a constant, fill in the
- * correct markings for a mergejoinable clause. We don't put it
- * in ec_derives however; we don't currently need to re-find such
- * clauses, and we don't want to clutter that list with non-join
- * clauses.
+ * correct markings for a mergejoinable clause. We don't save it
+ * as a derived clause however; we don't currently need to re-find
+ * such clauses, and we don't want to clutter that set with
+ * non-join clauses.
*/
if (rinfo && rinfo->mergeopfamilies)
{
@@ -1369,7 +1405,7 @@ generate_base_implied_equalities_broken(PlannerInfo *root,
* we consider different join paths, we avoid generating multiple copies:
* whenever we select a particular pair of EquivalenceMembers to join,
* we check to see if the pair matches any original clause (in ec_sources)
- * or previously-built clause (in ec_derives). This saves memory and allows
+ * or previously-built derived clause. This saves memory and allows
* re-use of information cached in RestrictInfos. We also avoid generating
* commutative duplicates, i.e. if the algorithm selects "a.x = b.y" but
* we already have "b.y = a.x", we return the existing clause.
@@ -1754,9 +1790,9 @@ generate_join_implied_equalities_broken(PlannerInfo *root,
/*
* If we have to translate, just brute-force apply adjust_appendrel_attrs
* to all the RestrictInfos at once. This will result in returning
- * RestrictInfos that are not listed in ec_derives, but there shouldn't be
- * any duplication, and it's a sufficiently narrow corner case that we
- * shouldn't sweat too much over it anyway.
+ * RestrictInfos that are not part of EC derived clauses , but there
+ * shouldn't be any duplication, and it's a sufficiently narrow corner
+ * case that we shouldn't sweat too much over it anyway.
*
* Since inner_rel might be an indirect descendant of the baserel
* mentioned in the ec_sources clauses, we have to be prepared to apply
@@ -1802,6 +1838,97 @@ select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
return InvalidOid;
}
+/*
+ * search_clause_for_ems
+ * Return an already built RestrictInfo for the given pair of
+ * EquivalenceMembers, if exists.
+ *
+ * We can use either original source clauses or previously-derived clauses, and
+ * a commutator clause is acceptable.
+ *
+ * We used to verify that opno matches, but that seems redundant: even if it's
+ * not identical, it'd better have the same effects, or the operator families
+ * we're using are broken.
+ *
+ * Returns NULL if the required RestrictInfo is not already built.
+ */
+static RestrictInfo *
+search_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
+{
+ foreach_node(RestrictInfo, rinfo, ec->ec_sources)
+ {
+ if (rinfo->left_em == leftem &&
+ rinfo->right_em == rightem &&
+ rinfo->parent_ec == parent_ec)
+ return rinfo;
+ if (rinfo->left_em == rightem &&
+ rinfo->right_em == leftem &&
+ rinfo->parent_ec == parent_ec)
+ return rinfo;
+ }
+
+ return search_derived_clause_for_ems(root, ec, leftem, rightem, parent_ec);
+}
+
+/*
+ * search_derived_clause_for_ems
+ * Similar to search_clause_for_ems() but looks up derived clauses.
+ */
+static RestrictInfo *
+search_derived_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
+{
+ /*
+ * Switch to using hash lookup when list grows "too long". The threshold
+ * is arbitrary and is known only here.
+ */
+ if (!ec->ec_derives_hash && list_length(ec->ec_derives_list) >= 32)
+ build_ec_derives_hash(root, ec);
+
+ /* Perform hash table lookup or linear search as appropriate. */
+ if (ec->ec_derives_hash)
+ {
+ ECDerivesKey key;
+ RestrictInfo *rinfo;
+ ECDerivesEntry *entry;
+
+ /*
+ * add_clause_to_derives_hash() explains why we don't perform a second
+ * search by swapping EquivalenceMembers.
+ */
+ key.em1 = leftem;
+ key.em2 = rightem;
+ key.parent_ec = parent_ec;
+ entry = derives_lookup(ec->ec_derives_hash, key);
+ if (entry)
+ {
+ rinfo = entry->rinfo;
+ Assert(rinfo);
+ return rinfo;
+ }
+ }
+ else
+ {
+ foreach_node(RestrictInfo, rinfo, ec->ec_derives_list)
+ {
+ if (!rightem &&
+ rinfo->left_em == leftem)
+ {
+ Assert(rinfo->right_em->em_is_const);
+ return rinfo;
+ }
+ if (rinfo->left_em == leftem &&
+ rinfo->right_em == rightem &&
+ rinfo->parent_ec == parent_ec)
+ return rinfo;
+ if (rinfo->left_em == rightem &&
+ rinfo->right_em == leftem &&
+ rinfo->parent_ec == parent_ec)
+ return rinfo;
+ }
+ }
+
+ return NULL;
+}
/*
* create_join_clause
@@ -1823,43 +1950,11 @@ create_join_clause(PlannerInfo *root,
{
RestrictInfo *rinfo;
RestrictInfo *parent_rinfo = NULL;
- ListCell *lc;
MemoryContext oldcontext;
- /*
- * Search to see if we already built a RestrictInfo for this pair of
- * EquivalenceMembers. We can use either original source clauses or
- * previously-derived clauses, and a commutator clause is acceptable.
- *
- * We used to verify that opno matches, but that seems redundant: even if
- * it's not identical, it'd better have the same effects, or the operator
- * families we're using are broken.
- */
- foreach(lc, ec->ec_sources)
- {
- rinfo = (RestrictInfo *) lfirst(lc);
- if (rinfo->left_em == leftem &&
- rinfo->right_em == rightem &&
- rinfo->parent_ec == parent_ec)
- return rinfo;
- if (rinfo->left_em == rightem &&
- rinfo->right_em == leftem &&
- rinfo->parent_ec == parent_ec)
- return rinfo;
- }
-
- foreach(lc, ec->ec_derives)
- {
- rinfo = (RestrictInfo *) lfirst(lc);
- if (rinfo->left_em == leftem &&
- rinfo->right_em == rightem &&
- rinfo->parent_ec == parent_ec)
- return rinfo;
- if (rinfo->left_em == rightem &&
- rinfo->right_em == leftem &&
- rinfo->parent_ec == parent_ec)
- return rinfo;
- }
+ rinfo = search_clause_for_ems(root, ec, leftem, rightem, parent_ec);
+ if (rinfo)
+ return rinfo;
/*
* Not there, so build it, in planner context so we can re-use it. (Not
@@ -1923,7 +2018,7 @@ create_join_clause(PlannerInfo *root,
rinfo->left_em = leftem;
rinfo->right_em = rightem;
/* and save it for possible re-use */
- ec->ec_derives = lappend(ec->ec_derives, rinfo);
+ add_derived_clause(ec, rinfo);
MemoryContextSwitchTo(oldcontext);
@@ -2648,28 +2743,14 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
* Returns NULL if no such clause can be found.
*/
RestrictInfo *
-find_derived_clause_for_ec_member(EquivalenceClass *ec,
+find_derived_clause_for_ec_member(PlannerInfo *root,
+ EquivalenceClass *ec,
EquivalenceMember *em)
{
- ListCell *lc;
-
Assert(ec->ec_has_const);
Assert(!em->em_is_const);
- foreach(lc, ec->ec_derives)
- {
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
- /*
- * generate_base_implied_equalities_const will have put non-const
- * members on the left side of derived clauses.
- */
- if (rinfo->left_em == em)
- {
- Assert(rinfo->right_em->em_is_const);
- return rinfo;
- }
- }
- return NULL;
+ return search_derived_clause_for_ems(root, ec, em, NULL, NULL);
}
@@ -3442,3 +3523,131 @@ get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
/* Calculate and return the common EC indexes, recycling the left input. */
return bms_int_members(rel1ecs, rel2ecs);
}
+
+/*
+ * add_derived_clauses
+ * Add given clause to the set of clauses derived from the given EquivalenceClass; adding to the list and hash table if needed.
+ */
+static void
+add_derived_clause(EquivalenceClass *ec, RestrictInfo *clause)
+{
+ ec->ec_derives_list = lappend(ec->ec_derives_list, clause);
+ if (ec->ec_derives_hash)
+ add_clause_to_derives_hash(ec, clause);
+}
+
+/*
+ * add_derived_clauses
+ * Add a list of clauses to the set of clauses derived from the given EquivalenceClass; adding to the list and hash table if needed.
+ *
+ * This function is similar to above function but optimized for adding multiple
+ * clauses at a time to the ec_derives_list.
+ */
+static void
+add_derived_clauses(EquivalenceClass *ec, List *clauses)
+{
+ ec->ec_derives_list = list_concat(ec->ec_derives_list, clauses);
+ if (ec->ec_derives_hash)
+ foreach_node(RestrictInfo, rinfo, clauses)
+ add_clause_to_derives_hash(ec, rinfo);
+}
+
+/*
+ * build_ec_derives_hash
+ * Construct the auxiliary hash table for derived clauses.
+ */
+static void
+build_ec_derives_hash(PlannerInfo *root, EquivalenceClass *ec)
+{
+ Assert(!ec->ec_derives_hash);
+
+ /* Create the hash table */
+ ec->ec_derives_hash = derives_create(root->planner_cxt, 256L, NULL);
+
+ foreach_node(RestrictInfo, rinfo, ec->ec_derives_list)
+ add_clause_to_derives_hash(ec, rinfo);
+}
+
+/*
+ * add_clause_to_derives_hash
+ * Add the given clause to the hash table of derived clauses in the given EquivalenceClass.
+ */
+static void
+add_clause_to_derives_hash(EquivalenceClass *ec, RestrictInfo *rinfo)
+{
+ ECDerivesKey key;
+ ECDerivesEntry *entry;
+ bool found;
+
+ /*
+ * Per generate_base_implied_equalities_const(), a constant always appears
+ * on the RHS of equality.
+ */
+ Assert(!rinfo->left_em->em_is_const);
+
+ if (rinfo->right_em->em_is_const)
+ {
+ /*
+ * generate_base_implied_equalities_const() doesn't set parent_ec
+ * since clauses involving constants are not redundant.
+ */
+ Assert(!rinfo->parent_ec);
+
+ /*
+ * find_derived_clause_for_ec_member() looks up a clause involving a
+ * constant by the non-constant EquivalenceMember. The actual constant
+ * EquivalenceMember is irrelevant for such lookup and is not
+ * available when looking up. Further there is only one constant
+ * EquivalenceMember per EquivalenceClass. For ease of lookup, we set
+ * right_em to NULL in the key.
+ */
+ key.em1 = rinfo->left_em;
+ key.em2 = NULL;
+ key.parent_ec = rinfo->parent_ec;
+ entry = derives_insert(ec->ec_derives_hash, key, &found);
+ Assert(!found);
+ entry->rinfo = rinfo;
+ }
+ else
+ {
+ key.em1 = rinfo->left_em;
+ key.em2 = rinfo->right_em;
+ key.parent_ec = rinfo->parent_ec;
+ entry = derives_insert(ec->ec_derives_hash, key, &found);
+ Assert(!found);
+ entry->rinfo = rinfo;
+
+ /*
+ * Add another entry to match the clause even if left and right EMs
+ * have swapped.
+ */
+ key.em1 = rinfo->right_em;
+ key.em2 = rinfo->left_em;
+ key.parent_ec = rinfo->parent_ec;
+ entry = derives_insert(ec->ec_derives_hash, key, &found);
+ Assert(!found);
+ entry->rinfo = rinfo;
+ }
+
+}
+
+/*
+ * ec_clear_derived_clauses
+ * Reset the ec_derives list and the hash table.
+ *
+ * We destroy the hash table since it consumes more space than the list. But we
+ * don't bother to free the list.
+ *
+ * XXX: when there are thousands of partitions involved, the list can grow
+ * sizable and thus freeing it might be desirable.
+ */
+void
+clear_ec_derived_clauses(EquivalenceClass *ec)
+{
+ ec->ec_derives_list = NIL;
+ if (ec->ec_derives_hash)
+ {
+ derives_destroy(ec->ec_derives_hash);
+ ec->ec_derives_hash = NULL;
+ }
+}
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 3aa04d0d4e1..fb5c010bdad 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -724,7 +724,7 @@ remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid, int subst)
* drop them. (At this point, any such clauses would be base restriction
* clauses, which we'd not need anymore anyway.)
*/
- ec->ec_derives = NIL;
+ clear_ec_derived_clauses(ec);
}
/*
@@ -1518,8 +1518,7 @@ update_eclasses(EquivalenceClass *ec, int from, int to)
list_free(ec->ec_members);
ec->ec_members = new_members;
- list_free(ec->ec_derives);
- ec->ec_derives = NULL;
+ clear_ec_derived_clauses(ec);
/* Update EC source expressions */
foreach_node(RestrictInfo, rinfo, ec->ec_sources)
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index fbf05322c75..61542fc19c3 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1419,7 +1419,22 @@ typedef struct EquivalenceClass
Oid ec_collation; /* collation, if datatypes are collatable */
List *ec_members; /* list of EquivalenceMembers */
List *ec_sources; /* list of generating RestrictInfos */
- List *ec_derives; /* list of derived RestrictInfos */
+
+ /*
+ * ec_derives_list is a list of derived RestrictInfos. For small problems
+ * we just scan the list to lookup RestrictInfos with given
+ * EquivalenceMembers, but when there are many derived clauses, because of
+ * many partitions or many tables being joined or both, we build hash
+ * table for faster lookups. The hash table is present and valid when
+ * ec_derives_hash is not NULL. Note that we still maintain the list even
+ * when using the hash table for lookups; this simplifies life for
+ * _outEquivalenceClass() and when merging two EquivalenceClasses.
+ *
+ * Note that ec_sources contains the clauses, mentioned in the query,
+ * which are fewer. It does not need a hash table for lookups.
+ */
+ List *ec_derives_list;
+ struct derives_hash *ec_derives_hash;
Relids ec_relids; /* all relids appearing in ec_members, except
* for child members (see below) */
bool ec_has_const; /* any pseudoconstants in ec_members? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index bc5dfd7db41..f80fcf606d6 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -167,7 +167,8 @@ extern bool exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2,
extern EquivalenceClass *match_eclasses_to_foreign_key_col(PlannerInfo *root,
ForeignKeyOptInfo *fkinfo,
int colno);
-extern RestrictInfo *find_derived_clause_for_ec_member(EquivalenceClass *ec,
+extern RestrictInfo *find_derived_clause_for_ec_member(PlannerInfo *root,
+ EquivalenceClass *ec,
EquivalenceMember *em);
extern void add_child_rel_equivalences(PlannerInfo *root,
AppendRelInfo *appinfo,
@@ -197,6 +198,7 @@ extern bool eclass_useful_for_merging(PlannerInfo *root,
extern bool is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist);
extern bool is_redundant_with_indexclauses(RestrictInfo *rinfo,
List *indexclauses);
+extern void clear_ec_derived_clauses(EquivalenceClass *ec);
/*
* pathkeys.c
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index e3e09a2207e..788860aefe5 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -659,6 +659,8 @@ DumpableObjectWithAcl
DynamicFileList
DynamicZoneAbbrev
EC_KEY
+ECDerivesKey
+ECDerivesEntry
EDGE
ENGINE
EOM_flatten_into_method
--
2.34.1
