Skip to content

Commit 88f55bc

Browse files
amitlanamitlan
committed
Make derived clause lookup in EquivalenceClass more efficient
Derived clauses are stored in ec_derives, a List of RestrictInfos. These clauses are later looked up by matching the left and right EquivalenceMembers along with the clause's parent EC. This linear search becomes expensive in queries with many joins or partitions, where ec_derives may contain thousands of entries. In particular, create_join_clause() can spend significant time scanning this list. To improve performance, introduce a hash table (ec_derives_hash) that is built when the list reaches 32 entries -- the same threshold used for join_rel_hash. The original list is retained alongside the hash table to support EC merging and serialization (_outEquivalenceClass()). Each clause is stored in the hash table using a canonicalized key: the EquivalenceMember with the lower memory address is placed in the key before the one with the higher memory address. This avoids storing or searching for both permutations of the same clause. For clauses involving a constant EM, the key places NULL in the first slot and the non-constant EM in the second. The hash table is initialized using list_length(ec_derives_list) as the size hint. simplehash internally adjusts this to the next power of two after dividing by the fillfactor, so this typically results in at least 64 buckets near the threshold -- avoiding immediate resizing while adapting to the actual number of entries. The lookup logic for derived clauses is now centralized in ec_search_derived_clause_for_ems(), which consults the hash table when available and falls back to the list otherwise. 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 large lists are discarded. An assertion originally placed in find_derived_clause_for_ec_member() is moved into ec_search_derived_clause_for_ems() so that it is enforced consistently, regardless of whether the hash table or list is used for lookup. This design incorporates suggestions by David Rowley, who proposed both the key canonicalization and the initial sizing approach to balance memory usage and CPU efficiency. Author: Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> Reviewed-by: Amit Langote <amitlangote09@gmail.com> Reviewed-by: David Rowley <dgrowleyml@gmail.com> Tested-by: Dmitry Dolgov <9erthalion6@gmail.com> Tested-by: Alvaro Herrera <alvherre@alvh.no-ip.org> Tested-by: Amit Langote <amitlangote09@gmail.com> Tested-by: David Rowley <dgrowleyml@gmail.com> Discussion: https://postgr.es/m/CAExHW5vZiQtWU6moszLP5iZ8gLX_ZAUbgEX0DxGLx9PGWCtqUg@mail.gmail.com
1 parent 887160d commit 88f55bc

File tree

7 files changed

+389
-80
lines changed

7 files changed

+389
-80
lines changed

‎src/backend/nodes/outfuncs.c

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -467,7 +467,8 @@ _outEquivalenceClass(StringInfo str, const EquivalenceClass *node)
467467
WRITE_OID_FIELD(ec_collation);
468468
WRITE_NODE_FIELD(ec_members);
469469
WRITE_NODE_FIELD(ec_sources);
470-
WRITE_NODE_FIELD(ec_derives);
470+
/* Only ec_derives_list is written; hash is not serialized. */
471+
WRITE_NODE_FIELD(ec_derives_list);
471472
WRITE_BITMAPSET_FIELD(ec_relids);
472473
WRITE_BOOL_FIELD(ec_has_const);
473474
WRITE_BOOL_FIELD(ec_has_volatile);

‎src/backend/optimizer/path/costsize.c

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5848,7 +5848,8 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
58485848
if (ec && ec->ec_has_const)
58495849
{
58505850
EquivalenceMember *em = fkinfo->fk_eclass_member[i];
5851-
RestrictInfo *rinfo = find_derived_clause_for_ec_member(ec,
5851+
RestrictInfo *rinfo = find_derived_clause_for_ec_member(root,
5852+
ec,
58525853
em);
58535854

58545855
if (rinfo)

0 commit comments

Comments
 (0)