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....@gmail.com> Reviewed-by: Amit Langote <amitlangot...@gmail.com> Reviewed-by: David Rowley <dgrowle...@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> Tested-by: David Rowley <dgrowle...@gmail.com> Discussion: https://postgr.es/m/caexhw5vziqtwu6moszlp5iz8glx_zaubgex0dxglx9pgwct...@mail.gmail.com Branch ------ master Details ------- https://git.postgresql.org/pg/commitdiff/88f55bc97622bce000a8c90f8ef58dacc926de19 Modified Files -------------- src/backend/nodes/outfuncs.c | 3 +- src/backend/optimizer/path/costsize.c | 3 +- src/backend/optimizer/path/equivclass.c | 435 +++++++++++++++++++++++++----- 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, 389 insertions(+), 80 deletions(-)
