On Mon, Mar 31, 2025 at 8:27 AM David Rowley <dgrowle...@gmail.com> wrote:
>
> On Sat, 29 Mar 2025 at 05:46, Ashutosh Bapat
> <ashutosh.bapat....@gmail.com> wrote:
> > PFA patches. 0001 and 0002 are the same as the previous set. 0003
> > changes the initial hash table size to the length of ec_derives.
>
> I'm just not following the logic in making it the length of the
> ec_derives List. If you have 32 buckets and try to insert 32 elements,
> you're guaranteed to need a resize after inserting 28 elements. See
> the grow_threshold logic SH_UPDATE_PARAMETERS(). The point of making
> it 64 was to ensure the table is never unnecessarily sparse and to
> also ensure we make it at least big enough for the minimum number of
> ec_derives that we're about to insert.
If I am reading SH_CREATE correctly, it will initially set the size to
32/.9 = 36 and in SH_UPDATE_PARAMETERS will set grow_threshold to 36 *
.9 = 32. So it will leave some room even after inserting the initial
elements. But looking at SH_INSERT_HASH_INTERNAL(), it will soon
expand the table even if there's space. We certainly need a size much
more than 32. 32 is an arbitrary/empirical threshold to create a hash
table. Using that threshold as initial hash table size means the table
size would be arbitrary too. Using twice the length of
ec_derives_list seems more reasonable since the length will decide the
initial number of entries.
>
> Looking more closely at the patch's ec_add_clause_to_derives_hash()
> function, I see you're actually making two hash table entries for each
> RestrictInfo, so without any em_is_const members, you'll insert 64
> entries into the hash table with a ec_derives list of 32, in which
> case 64 buckets isn't enough and the table will end up growing to 128
> elements.
>
Yes, that's right.
> I think you'd be better off coming up with some logic like putting the
> lowest pointer value'd EM first in the key and ensure that all lookups
> do that too by wrapping the lookups in some helper function. That'll
> half the number of hash table entries at the cost of some very cheap
> comparisons.
That's a good suggestion. I searched for C standard documentation
which specifies that the pointer comparison, especially inequality, is
stable and safe to use. But I didn't find any. While according to the
C standard, the result
of comparison between pointers within the same array or a struct is
specified, that between pointers from two different objects is
unspecified. The existing code relies on the EM pointers being stable
and also relies on equality between
them to be stable. It has withstood the test of time and a variety of
compilers. Hence I think it should be safe to rely on pointer
comparisons being stable. But since I didn't find any documentation
which confirms it, I have left those changes as a separate patch. Some
internet sources discussing pointer comparison can be found at [1],
[2] (which mentions the C standard but doesn't provide a link).
PFA the next patchset
0001, 0002 are same as in the previous set
0003 changes the initial hash table size to
length(ec->ec_derives_list) * 4 to accomodate for commuted entries.
0004 uses canonical keys per your suggestion and also reduces the
initial hash table size to length(ec->ec_derives_list) * 2.
When the number of initial elements to be added to the hash table is
known, I see users of simplehash.h using that as an estimate rather
than the nearest power of two. Hence following the logic here.
[1]
https://stackoverflow.com/questions/59516346/how-does-pointer-comparison-work-in-c-is-it-ok-to-compare-pointers-that-dont-p
[2]
https://www.gnu.org/software/c-intro-and-ref/manual/html_node/Pointer-Comparison.html
--
Best Wishes,
Ashutosh Bapat
From ccb72663e55f5ffe67595366e4a110685f647fc6 Mon Sep 17 00:00:00 2001
From: Amit Langote <amit...@postgresql.org>
Date: Mon, 24 Mar 2025 21:17:46 +0900
Subject: [PATCH 1/4] Add assertion to verify derived clause has constant RHS
find_derived_clause_for_ec_member() searches for a previously-derived
clause that equates a non-constant EquivalenceMember to a constant.
It is only called for EquivalenceClasses with ec_has_const set, and
with a non-constant member as the target.
The matched clause is expected to have the non-constant member on the
left-hand side and the constant EquivalenceMember on the right.
Assert that the RHS is indeed a constant, to catch violations of this
structure and enforce assumptions made by
generate_base_implied_equalities_const().
Author: Ashutosh Bapat <ashutosh.bapat....@gmail.com>
Discussion: https://postgr.es/m/caexhw5scmxyfrqofe6odmbiw2rnvbemeeca-p4w_cyueiku...@mail.gmail.com
---
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: e2809e3a1015697832ee4d37b75ba1cd0caac0f0
--
2.34.1
From 9a9934d9b5f8f82fc73d89f5e9faa746e176936b Mon Sep 17 00:00:00 2001
From: Ashutosh Bapat <ashutosh.bapat....@gmail.com>
Date: Fri, 28 Mar 2025 21:12:04 +0530
Subject: [PATCH 3/4] Use length of ec_derives clause list as initial hash
table size estimation
ec_add_clause_to_derives_hash() adds two entries for every clause which does not
have a constant EM in it. Hence initially the hash table may contain twice the
number of derived clauses. Specify the initial hash table size as four times the
number of existing derived clauses in the list so that we don't require to
expand the hash table immediately when inserting the next clause.
Ashutosh Bapat
---
src/backend/optimizer/path/equivclass.c | 15 +++++++++++++--
1 file changed, 13 insertions(+), 2 deletions(-)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index b988db4d7b3..76b8179e285 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -3457,8 +3457,19 @@ ec_build_derives_hash(PlannerInfo *root, EquivalenceClass *ec)
{
Assert(!ec->ec_derives_hash);
- /* Create the hash table */
- ec->ec_derives_hash = derives_create(root->planner_cxt, 256, NULL);
+ /*
+ * Create the hash table.
+ *
+ * ec_add_clause_to_derives_hash() adds two entries for every clause which
+ * does not have a constant EM in it. Hence initially the hash table may
+ * contain twice the number of derived clauses. Specify the initial hash
+ * table size as four times the number of existing derived clauses in the
+ * list so that we don't require to expand the hash table immediately when
+ * inserting the next clause.
+ */
+ ec->ec_derives_hash = derives_create(root->planner_cxt,
+ list_length(ec->ec_derives_list) * 4,
+ NULL);
foreach_node(RestrictInfo, rinfo, ec->ec_derives_list)
ec_add_clause_to_derives_hash(ec, rinfo);
--
2.34.1
From 3eb7577727ff04bbc254c94e653f6f30d809fe24 Mon Sep 17 00:00:00 2001
From: Amit Langote <amit...@postgresql.org>
Date: Tue, 25 Mar 2025 20:36:26 +0900
Subject: [PATCH 2/4] Make derived clause lookup in EquivalenceClass more
efficient
Previously, derived clauses were stored in ec_derives, a List of
RestrictInfos. These clauses are looked up later using the left and
right EquivalenceMembers and the clause's parent EC, typically during
join clause generation.
This lookup becomes expensive in queries with many partitions or
joins, where ec_derives may contain thousands of entries. In
particular, create_join_clause() can spend significant time scanning
this list.
To improve performance, a hash table (ec_derives_hash) is now built
when ec_derives_list exceeds 32 entries. This is the same threshold
used for join_rel_hash. To reflect this dual structure, the
ec_derives field is renamed to ec_derives_list. The list is retained
alongside the hash table to support _outEquivalenceClass() and
EquivalenceClass merging, which both operate on ec_derives_list.
Lookup logic is updated to consult the hash table when available. For
ECs with a constant EM, lookups are done using only the non-constant
EM; the constant EM is assumed to be unique and may not be available
at lookup time. In such cases, the hash table stores em2 = NULL, which
can be matched by using NULL for em2 in the lookup key.
An assertion originally placed in find_derived_clause_for_ec_member()
is moved into ec_search_derived_clause_for_ems() to enforce the same
invariant in both hash and list lookup paths.
The new ec_clear_derived_clauses() always frees ec_derives_list, even
though some of the original code paths that cleared the old ec_derives
field did not. This ensures consistent cleanup and avoids leaking
memory when the list grows large.
Author: Ashutosh Bapat <ashutosh.bapat....@gmail.com>
Reviewed-by: Amit Langote <amitlangot...@gmail.com>
Tested-by: Dmitry Dolgov <9erthali...@gmail.com>
Tested-by: Alvaro Herrera <alvhe...@alvh.no-ip.org>
Tested-by: Amit Langote <amitlangot...@gmail.com>
Discussion: https://postgr.es/m/caexhw5vziqtwu6moszlp5iz8glx_zaubgex0dxglx9pgwct...@mail.gmail.com
---
src/backend/nodes/outfuncs.c | 3 +-
src/backend/optimizer/path/costsize.c | 3 +-
src/backend/optimizer/path/equivclass.c | 403 ++++++++++++++++++----
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, 357 insertions(+), 80 deletions(-)
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index bb9bdd67192..557f06e344f 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -467,7 +467,8 @@ _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);
+ /* Only ec_derives_list is written; hash is not serialized. */
+ WRITE_NODE_FIELD(ec_derives_list);
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 f6f77b8fe19..c474c7a06af 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -5848,7 +5848,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..b988db4d7b3 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,7 +73,50 @@ 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 ec_build_derives_hash(PlannerInfo *root, EquivalenceClass *ec);
+static void ec_add_derived_clauses(EquivalenceClass *ec, List *clauses);
+static void ec_add_derived_clause(EquivalenceClass *ec, RestrictInfo *clause);
+static void ec_add_clause_to_derives_hash(EquivalenceClass *ec, RestrictInfo *rinfo);
+static RestrictInfo *ec_search_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec,
+ EquivalenceMember *leftem,
+ EquivalenceMember *rightem,
+ EquivalenceClass *parent_ec);
+static RestrictInfo *ec_search_derived_clause_for_ems(PlannerInfo *root,
+ EquivalenceClass *ec,
+ EquivalenceMember *leftem,
+ EquivalenceMember *rightem,
+ EquivalenceClass *parent_ec);
+/*
+ * Hash key identifying a derived clause by EquivalenceMembers and parent EC.
+ */
+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
@@ -342,7 +386,12 @@ 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);
+
+ /*
+ * Appends ec2's derived clauses to ec1->ec_derives_list and adds them
+ * to ec1->ec_derives_hash if present.
+ */
+ ec_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 +404,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;
+ ec_clear_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 +461,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 +721,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,8 +1077,8 @@ 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
- * seem worth the trouble to do so.
+ * don't search existing source or derived clauses in the EC for matches. It
+ * doesn't really seem worth the trouble to do so.
*/
void
generate_base_implied_equalities(PlannerInfo *root)
@@ -1188,11 +1239,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 +1251,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);
+ ec_add_derived_clause(ec, rinfo);
}
}
}
@@ -1265,10 +1316,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 record
+ * it as a derived clause, since we don't currently need to
+ * re-find such clauses, and don't want to clutter the
+ * derived-clause set with non-join clauses.
*/
if (rinfo && rinfo->mergeopfamilies)
{
@@ -1369,7 +1420,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 +1805,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 included in EC's 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
@@ -1823,43 +1874,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 = ec_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 +1942,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);
+ ec_add_derived_clause(ec, rinfo);
MemoryContextSwitchTo(oldcontext);
@@ -2648,28 +2667,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 ec_search_derived_clause_for_ems(root, ec, em, NULL, NULL);
}
@@ -3442,3 +3447,255 @@ 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);
}
+
+/*
+ * ec_build_derives_hash
+ * Construct the auxiliary hash table for derived clauses.
+ */
+static void
+ec_build_derives_hash(PlannerInfo *root, EquivalenceClass *ec)
+{
+ Assert(!ec->ec_derives_hash);
+
+ /* Create the hash table */
+ ec->ec_derives_hash = derives_create(root->planner_cxt, 256, NULL);
+
+ foreach_node(RestrictInfo, rinfo, ec->ec_derives_list)
+ ec_add_clause_to_derives_hash(ec, rinfo);
+}
+
+/*
+ * ec_add_derived_clause
+ * Add a clause to the set of derived clauses for the given
+ * EquivalenceClass. Always appends to ec_derives_list; also adds
+ * to ec_derives_hash if it exists.
+ */
+static void
+ec_add_derived_clause(EquivalenceClass *ec, RestrictInfo *clause)
+{
+ ec->ec_derives_list = lappend(ec->ec_derives_list, clause);
+ if (ec->ec_derives_hash)
+ ec_add_clause_to_derives_hash(ec, clause);
+}
+
+/*
+ * ec_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
+ec_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)
+ ec_add_clause_to_derives_hash(ec, rinfo);
+}
+
+/*
+ * ec_add_clause_to_derives_hash
+ * Add a derived clause to the ec_derives_hash of the given
+ * EquivalenceClass.
+ */
+static void
+ec_add_clause_to_derives_hash(EquivalenceClass *ec, RestrictInfo *rinfo)
+{
+ ECDerivesKey key;
+ ECDerivesEntry *entry;
+ bool found;
+
+ /*
+ * Constants are always placed on the RHS; see
+ * generate_base_implied_equalities_const().
+ */
+ Assert(!rinfo->left_em->em_is_const);
+
+ if (rinfo->right_em->em_is_const)
+ {
+ /*
+ * Clauses containing a constant are never considered redundant, so
+ * parent_ec is not set.
+ */
+ Assert(!rinfo->parent_ec);
+
+ /*
+ * find_derived_clause_for_ec_member() performs lookup of a clause
+ * involving a constant using only the non-constant EM and NULL for
+ * the RHS. Since there's only one constant EM per EC, we don't need
+ * to store or match it during lookup. We set key.em2 = NULL to
+ * reflect this.
+ */
+ 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;
+
+ /*
+ * Insert the clause under the given EM pair key, and also under the
+ * reverse order. This ensures we can find the clause regardless of
+ * the order in which EMs are passed to the lookup function.
+ */
+ 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 ec_derives_list and ec_derives_hash.
+ *
+ * We destroy the hash table explicitly, since it may consume significant
+ * space. The list holds the same set of entries and can become equally large
+ * when thousands of partitions are involved, so we free it as well -- even
+ * though we do not typically free lists.
+ */
+void
+ec_clear_derived_clauses(EquivalenceClass *ec)
+{
+ list_free(ec->ec_derives_list);
+ ec->ec_derives_list = NIL;
+
+ if (ec->ec_derives_hash)
+ {
+ derives_destroy(ec->ec_derives_hash);
+ ec->ec_derives_hash = NULL;
+ }
+}
+
+/*
+ * ec_search_clause_for_ems
+ * Search for an existing RestrictInfo that equates the given pair
+ * of EquivalenceMembers, either from ec_sources or ec_derives.
+ *
+ * We accept clauses in either operand order, so commutators are matched. We
+ * used to require matching operator OIDs, but dropped that since any
+ * semantically different operator here would indicate a broken operator
+ * family.
+ *
+ * Returns NULL if no matching clause is found.
+ */
+
+static RestrictInfo *
+ec_search_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec,
+ EquivalenceMember *leftem, EquivalenceMember *rightem,
+ EquivalenceClass *parent_ec)
+{
+ /* Check original source clauses */
+ 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;
+ }
+
+ /* Not found in ec_sources; search derived clauses */
+ return ec_search_derived_clause_for_ems(root, ec, leftem, rightem,
+ parent_ec);
+}
+
+/*
+ * ec_search_derived_clause_for_ems
+ * Search for an existing derived clause between two EquivalenceMembers.
+ *
+ * If the number of derived clauses exceeds a threshold, switch to hash table
+ * lookup; otherwise, scan ec_derives_list linearly.
+ *
+ * Clauses involving constants are looked up using only the non-const EM
+ * (leftem) and a NULL rightem. In that case, we expect to find a clause with
+ * a constant on the RHS.
+ *
+ * We do not attempt a second lookup with EMs swapped when using the hash
+ * table; such clauses are inserted under both orderings at the time of
+ * insertion.
+ */
+static RestrictInfo *
+ec_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)
+ ec_build_derives_hash(root, ec);
+
+ /* Perform hash table lookup if available */
+ if (ec->ec_derives_hash)
+ {
+ ECDerivesKey key;
+ RestrictInfo *rinfo;
+ ECDerivesEntry *entry;
+
+ /*
+ * See ec_add_clause_to_derives_hash() for rationale: derived clauses
+ * are inserted into the hash table under both (em1, em2) and (em2,
+ * em1), so a single lookup with the original order is sufficient.
+ */
+ 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);
+
+ /*
+ * If this is a lookup in a const-containing EC, the RHS must be a
+ * constant. The caller signals this by passing NULL for rightem.
+ */
+ Assert(rightem || rinfo->right_em->em_is_const);
+ return rinfo;
+ }
+ }
+ else
+ {
+ /* Fallback to linear search over ec_derives_list */
+ foreach_node(RestrictInfo, rinfo, ec->ec_derives_list)
+ {
+ /* Handle special case: lookup by non-const EM alone */
+ if (!rightem &&
+ rinfo->left_em == leftem)
+ {
+ /* See the comment above in hash path for rationale. */
+ 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;
+}
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 8a8d4a2af33..ae20691ca91 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -749,7 +749,7 @@ remove_rel_from_eclass(EquivalenceClass *ec, SpecialJoinInfo *sjinfo,
* drop them. (At this point, any such clauses would be base restriction
* clauses, which we'd not need anymore anyway.)
*/
- ec->ec_derives = NIL;
+ ec_clear_derived_clauses(ec);
}
/*
@@ -1544,8 +1544,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;
+ ec_clear_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 c24a1fc8514..e29d26a1814 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1403,6 +1403,18 @@ typedef struct JoinDomain
* entry: consider SELECT random() AS a, random() AS b ... ORDER BY b,a.
* So we record the SortGroupRef of the originating sort clause.
*
+ * Derived equality clauses are stored in ec_derives_list. For small queries,
+ * this list is scanned directly during lookup. For larger queries -- e.g.,
+ * with many partitions or joins -- a hash table (ec_derives_hash) is built
+ * when the list grows beyond a threshold, for faster lookup. When present,
+ * the hash table contains the same RestrictInfos and is maintained alongside
+ * the list. We retain the list even when the hash is used to simplify
+ * serialization (e.g., in _outEquivalenceClass()) and support
+ * EquivalenceClass merging.
+ *
+ * In contrast, ec_sources holds equality clauses that appear directly in the
+ * query. These are typically few and do not require a hash table for lookup.
+ *
* NB: if ec_merged isn't NULL, this class has been merged into another, and
* should be ignored in favor of using the pointed-to class.
*
@@ -1422,7 +1434,10 @@ 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 */
+ List *ec_derives_list; /* list of derived RestrictInfos */
+ struct derives_hash *ec_derives_hash; /* optional hash table for fast
+ * lookup; contains same
+ * RestrictInfos as list */
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..16dc4d5ee82 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 ec_clear_derived_clauses(EquivalenceClass *ec);
/*
* pathkeys.c
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index b66cecd8799..997abe1427c 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -667,6 +667,8 @@ DumpableObjectWithAcl
DynamicFileList
DynamicZoneAbbrev
EC_KEY
+ECDerivesKey
+ECDerivesEntry
EDGE
ENGINE
EOM_flatten_into_method
--
2.34.1
From 95cefd94e2130bf7802c5d1a95fd9e212a78f06b Mon Sep 17 00:00:00 2001
From: Ashutosh Bapat <ashutosh.bapat....@gmail.com>
Date: Mon, 31 Mar 2025 13:50:01 +0530
Subject: [PATCH 4/4] Canonical keys for ec_derives_hash
The derived clauses are looked up by the EMs that they contain by providing the
EMs in the same order as they appear in the clause or in commuted order. We use
canonical key to store and search the clauses either way. The lower of the EM
pointers is used as the first part of the key and other EM is used as the second
part of the key. parent_ec is the third part of the key. This avoids storing
each derived clause twice with keys corresponding to either order of EMs.
Similary it avoids looking up a clause twice using either order of given EMs.
The derived clauses containing constant EM are looked with a key with NULL as
the first part, non-constant EM pointer as the second part and parent_ec as the
third part.
Since this reduces the number of entries in the hash table at the time
of its creation by half, the patches reduces the specified initial size
of hash table by half.
NOTE:
This patch relies on the C pointer comparison operators to be stable in the
sense that they will return the same value every time the same operands are
passed to them in the same order. While according to the C standard, the result
of comparison between pointers within the same array or a struct is specified,
that between pointers from two different objects is unspecified. The existing
code relies on the EM pointers being stable and also relies on equality between
them to be stable. It has withstood the test of time and a variety of compilers.
Hence it should be safe to rely on pointer comparisons being stable.
Further, if we rely on NULL pointer being always lower than any of non-NULL
pointers, we could avoid one condition each while inserting the clause and
looking up. According to C standard, a NULL pointer has value 0 but it doesn't
specify its order with respect to non-NULL pointers.
Author: Ashutosh Bapat, per suggestion by David Rowley
---
src/backend/optimizer/path/equivclass.c | 86 +++++++++++++------------
1 file changed, 44 insertions(+), 42 deletions(-)
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 76b8179e285..51a333469c5 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -3450,7 +3450,7 @@ get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
/*
* ec_build_derives_hash
- * Construct the auxiliary hash table for derived clauses.
+ * Construct the auxiliary hash table for derived clause lookups.
*/
static void
ec_build_derives_hash(PlannerInfo *root, EquivalenceClass *ec)
@@ -3460,15 +3460,12 @@ ec_build_derives_hash(PlannerInfo *root, EquivalenceClass *ec)
/*
* Create the hash table.
*
- * ec_add_clause_to_derives_hash() adds two entries for every clause which
- * does not have a constant EM in it. Hence initially the hash table may
- * contain twice the number of derived clauses. Specify the initial hash
- * table size as four times the number of existing derived clauses in the
- * list so that we don't require to expand the hash table immediately when
- * inserting the next clause.
+ * Specify the initial hash table size as twice the number of existing
+ * derived clauses in the list so that we don't require to expand the hash
+ * table immediately when inserting the next clause.
*/
ec->ec_derives_hash = derives_create(root->planner_cxt,
- list_length(ec->ec_derives_list) * 4,
+ list_length(ec->ec_derives_list) * 2,
NULL);
foreach_node(RestrictInfo, rinfo, ec->ec_derives_list)
@@ -3533,14 +3530,13 @@ ec_add_clause_to_derives_hash(EquivalenceClass *ec, RestrictInfo *rinfo)
Assert(!rinfo->parent_ec);
/*
- * find_derived_clause_for_ec_member() performs lookup of a clause
- * involving a constant using only the non-constant EM and NULL for
- * the RHS. Since there's only one constant EM per EC, we don't need
- * to store or match it during lookup. We set key.em2 = NULL to
- * reflect this.
+ * find_derived_clause_for_ec_member() looks up a clause involving a
+ * constant EM using only the non-constant EM. Since there's only one
+ * constant EM per EC, we don't need to store or match it during
+ * lookup. We set key.em1 = NULL to reflect this.
*/
- key.em1 = rinfo->left_em;
- key.em2 = NULL;
+ key.em1 = NULL;
+ key.em2 = rinfo->left_em;;
key.parent_ec = rinfo->parent_ec;
entry = derives_insert(ec->ec_derives_hash, key, &found);
Assert(!found);
@@ -3548,20 +3544,23 @@ ec_add_clause_to_derives_hash(EquivalenceClass *ec, RestrictInfo *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;
-
/*
- * Insert the clause under the given EM pair key, and also under the
- * reverse order. This ensures we can find the clause regardless of
- * the order in which EMs are passed to the lookup function.
+ * A clause may be looked up by EMs in the same order in which they
+ * appear in the clause or in commuted order. To serve both the
+ * requests, store the clause using a canonical key with the lower of
+ * the EM pointers as first part of the key and the other as the
+ * second part of the key.
*/
- key.em1 = rinfo->right_em;
- key.em2 = rinfo->left_em;
+ if (rinfo->left_em < rinfo->right_em)
+ {
+ key.em1 = rinfo->left_em;
+ key.em2 = rinfo->right_em;
+ }
+ else
+ {
+ 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);
@@ -3629,7 +3628,7 @@ ec_search_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec,
/*
* ec_search_derived_clause_for_ems
- * Search for an existing derived clause between two EquivalenceMembers.
+ * Search an existing derived clause containing given EquivalenceMembers.
*
* If the number of derived clauses exceeds a threshold, switch to hash table
* lookup; otherwise, scan ec_derives_list linearly.
@@ -3638,9 +3637,6 @@ ec_search_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec,
* (leftem) and a NULL rightem. In that case, we expect to find a clause with
* a constant on the RHS.
*
- * We do not attempt a second lookup with EMs swapped when using the hash
- * table; such clauses are inserted under both orderings at the time of
- * insertion.
*/
static RestrictInfo *
ec_search_derived_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec,
@@ -3663,23 +3659,30 @@ ec_search_derived_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec,
ECDerivesEntry *entry;
/*
- * See ec_add_clause_to_derives_hash() for rationale: derived clauses
- * are inserted into the hash table under both (em1, em2) and (em2,
- * em1), so a single lookup with the original order is sufficient.
+ * Construct a canonical key with given EMs. See
+ * ec_add_clause_to_derives_hash() for rationale.
*/
- key.em1 = leftem;
- key.em2 = rightem;
+ if (!rightem)
+ {
+ key.em1 = NULL;
+ key.em2 = leftem;
+ }
+ if (leftem < rightem)
+ {
+ key.em1 = leftem;
+ key.em2 = rightem;
+ }
+ else
+ {
+ key.em1 = rightem;
+ key.em2 = leftem;
+ }
key.parent_ec = parent_ec;
entry = derives_lookup(ec->ec_derives_hash, key);
if (entry)
{
rinfo = entry->rinfo;
Assert(rinfo);
-
- /*
- * If this is a lookup in a const-containing EC, the RHS must be a
- * constant. The caller signals this by passing NULL for rightem.
- */
Assert(rightem || rinfo->right_em->em_is_const);
return rinfo;
}
@@ -3693,7 +3696,6 @@ ec_search_derived_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec,
if (!rightem &&
rinfo->left_em == leftem)
{
- /* See the comment above in hash path for rationale. */
Assert(rinfo->right_em->em_is_const);
return rinfo;
}
--
2.34.1
