public inbox for [email protected]  

help / color / mirror / Atom feed

From: Andrey Lepikhov <[email protected]>
To: PostgreSQL-development <[email protected]>
Cc: Tom Lane <[email protected]>
Subject: MergeJoin beats HashJoin in the case of multiple hash clauses
Date: Thu, 15 Jun 2023 14:30:10 +0600
Message-ID: <[email protected]> (raw)

Hi, all.

Some of my clients use JOIN's with three - four clauses. Quite 
frequently, I see complaints on unreasonable switch of JOIN algorithm to 
Merge Join instead of Hash Join. Quick research have shown one weak 
place - estimation of an average bucket size in final_cost_hashjoin (see 
q2.sql in attachment) with very conservative strategy.
Unlike estimation of groups, here we use smallest ndistinct value across 
all buckets instead of multiplying them (or trying to make multivariate 
analysis).
It works fine for the case of one clause. But if we have many clauses, 
and if each has high value of ndistinct, we will overestimate average 
size of a bucket and, as a result, prefer to use Merge Join. As the 
example in attachment shows, it leads to worse plan than possible, 
sometimes drastically worse.
I assume, this is done with fear of functional dependencies between hash 
clause components. But as for me, here we should go the same way, as 
estimation of groups.
The attached patch shows a sketch of the solution.

-- 
regards,
Andrey Lepikhov
Postgres Professional
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index ef475d95a1..26f26d6a40 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -4033,11 +4033,12 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
 				thismcvfreq = restrictinfo->left_mcvfreq;
 			}
 
-			if (innerbucketsize > thisbucketsize)
-				innerbucketsize = thisbucketsize;
-			if (innermcvfreq > thismcvfreq)
-				innermcvfreq = thismcvfreq;
+			innerbucketsize *= thisbucketsize;
+			innermcvfreq *= thismcvfreq;
 		}
+
+		if (innerbucketsize > virtualbuckets)
+			innerbucketsize = 1.0 / virtualbuckets;
 	}
 
 	/*


Attachments:

  [application/sql] q2.sql (1.9K, ../[email protected]/2-q2.sql)
  download

  [text/plain] fix_bucketsize.diff (674B, ../[email protected]/3-fix_bucketsize.diff)
  download | inline diff:
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index ef475d95a1..26f26d6a40 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -4033,11 +4033,12 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
 				thismcvfreq = restrictinfo->left_mcvfreq;
 			}
 
-			if (innerbucketsize > thisbucketsize)
-				innerbucketsize = thisbucketsize;
-			if (innermcvfreq > thismcvfreq)
-				innermcvfreq = thismcvfreq;
+			innerbucketsize *= thisbucketsize;
+			innermcvfreq *= thismcvfreq;
 		}
+
+		if (innerbucketsize > virtualbuckets)
+			innerbucketsize = 1.0 / virtualbuckets;
 	}
 
 	/*

view thread (4+ messages)  latest in thread

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: [email protected]
  Cc: [email protected], [email protected]
  Subject: Re: MergeJoin beats HashJoin in the case of multiple hash clauses
  In-Reply-To: <[email protected]>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox