public inbox for [email protected]
help / color / mirror / Atom feedFrom: Lepikhov Andrei <[email protected]>
To: Andy Fan <[email protected]>
Cc: PostgreSQL-development <[email protected]>
Cc: Tom Lane <[email protected]>
Subject: Re: MergeJoin beats HashJoin in the case of multiple hash clauses
Date: Mon, 11 Sep 2023 15:04:22 +0700
Message-ID: <[email protected]> (raw)
In-Reply-To: <CAKU4AWoKiogNir=ESrm6F9pUwYFDfmsoNG9w9k1MG3VUbKM0Dw@mail.gmail.com>
References: <[email protected]>
<CAKU4AWoKiogNir=ESrm6F9pUwYFDfmsoNG9w9k1MG3VUbKM0Dw@mail.gmail.com>
On Mon, Sep 11, 2023, at 11:51 AM, Andy Fan wrote:
> Hi,
>
> On Thu, Jun 15, 2023 at 4:30 PM Andrey Lepikhov
> <[email protected]> wrote:
>> 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.
>
> I can reproduce the visitation you want to improve and verify the patch
> can do it expectedly. I think this is a right thing to do.
>
>> The attached patch shows a sketch of the solution.
>
> I understand that this is a sketch of the solution, but the below
> changes still
> make me confused.
>
> + if (innerbucketsize > virtualbuckets)
> + innerbucketsize = 1.0 / virtualbuckets;
>
> innerbucketsize is a fraction of rows in all the rows, so it is between
> 0.0 and 1.0.
> and virtualbuckets is the number of buckets in total (when considered
> the mutli
> batchs), how is it possible for 'innerbucketsize > virtualbuckets' ?
> Am
> I missing something?
You are right here. I've made a mistake here. Changed diff is in attachment.
--
Regards,
Andrei Lepikhov
Attachments:
[application/octet-stream] fix_bucketsize_v2.diff (680B, ../[email protected]/2-fix_bucketsize_v2.diff)
download | inline diff:
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index d6ceafd51c..5c5b24a843 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -4274,11 +4274,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 < 1.0 / virtualbuckets)
+ innerbucketsize = 1.0 / virtualbuckets;
}
/*
view thread (3+ 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], [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