Feedback-ID: ie8b149e1:Fastmail
User-Agent: Cyrus-JMAP/3.9.0-alpha0-711-g440737448e-fm-20230828.001-g44073744
Mime-Version: 1.0
Message-Id: <84114cba-97e9-49f8-952f-04cf321125c1@app.fastmail.com>
In-Reply-To: 
 <CAKU4AWoKiogNir=ESrm6F9pUwYFDfmsoNG9w9k1MG3VUbKM0Dw@mail.gmail.com>
References: <52257607-57f6-850d-399a-ec33a654457b@postgrespro.ru>
 <CAKU4AWoKiogNir=ESrm6F9pUwYFDfmsoNG9w9k1MG3VUbKM0Dw@mail.gmail.com>
Date: Mon, 11 Sep 2023 15:04:22 +0700
From: "Lepikhov Andrei" <a.lepikhov@postgrespro.ru>
To: "Andy Fan" <zhihui.fan1213@gmail.com>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>,
 "Tom Lane" <tgl@sss.pgh.pa.us>
Subject: Re: MergeJoin beats HashJoin in the case of multiple hash clauses
Content-Type: multipart/mixed;
 boundary=a2aeaf39c1854237bf0ed7550f08ad2a
Archived-At: <https://www.postgresql.org/message-id/84114cba-97e9-49f8-952f-04cf321125c1%40app.fastmail.com>
Precedence: bulk

--a2aeaf39c1854237bf0ed7550f08ad2a
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable


On Mon, Sep 11, 2023, at 11:51 AM, Andy Fan wrote:
> Hi,=20
>
> On Thu, Jun 15, 2023 at 4:30=E2=80=AFPM Andrey Lepikhov=20
> <a.lepikhov@postgrespro.ru> wrote:
>> Hi, all.
>>=20
>> Some of my clients use JOIN's with three - four clauses. Quite=20
>> frequently, I see complaints on unreasonable switch of JOIN algorithm=
 to=20
>> Merge Join instead of Hash Join. Quick research have shown one weak=20
>> place - estimation of an average bucket size in final_cost_hashjoin (=
see=20
>> q2.sql in attachment) with very conservative strategy.
>> Unlike estimation of groups, here we use smallest ndistinct value acr=
oss=20
>> all buckets instead of multiplying them (or trying to make multivaria=
te=20
>> analysis).
>> It works fine for the case of one clause. But if we have many clauses=
,=20
>> and if each has high value of ndistinct, we will overestimate average=20
>> size of a bucket and, as a result, prefer to use Merge Join. As the=20
>> example in attachment shows, it leads to worse plan than possible,=20
>> sometimes drastically worse.
>> I assume, this is done with fear of functional dependencies between h=
ash=20
>> clause components. But as for me, here we should go the same way, as=20
>> 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. =20
>=20
>> The attached patch shows a sketch of the solution.
>
> I understand that this is a sketch of the solution,  but the  below=20
> changes still
> make me confused.=20
>
> + if (innerbucketsize > virtualbuckets)
> +     innerbucketsize =3D 1.0 / virtualbuckets;
>
> innerbucketsize is a fraction of rows in all the rows, so it is betwee=
n=20
> 0.0 and 1.0.
> and virtualbuckets is the number of buckets in total (when considered=20
> the mutli
> batchs),  how is it possible for 'innerbucketsize > virtualbuckets' ? =20
> Am
> I missing something?=20

You are right here. I've made a mistake here. Changed diff is in attachm=
ent.

--=20
Regards,
Andrei Lepikhov
--a2aeaf39c1854237bf0ed7550f08ad2a
Content-Disposition: attachment; filename="fix_bucketsize_v2.diff"
Content-Type: application/octet-stream; name="fix_bucketsize_v2.diff"
Content-Transfer-Encoding: BASE64

ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL2Nvc3RzaXplLmMgYi9z
cmMvYmFja2VuZC9vcHRpbWl6ZXIvcGF0aC9jb3N0c2l6ZS5jCmluZGV4IGQ2Y2VhZmQ1MWMu
LjVjNWIyNGE4NDMgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL2Nv
c3RzaXplLmMKKysrIGIvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BhdGgvY29zdHNpemUuYwpA
QCAtNDI3NCwxMSArNDI3NCwxMiBAQCBmaW5hbF9jb3N0X2hhc2hqb2luKFBsYW5uZXJJbmZv
ICpyb290LCBIYXNoUGF0aCAqcGF0aCwKIAkJCQl0aGlzbWN2ZnJlcSA9IHJlc3RyaWN0aW5m
by0+bGVmdF9tY3ZmcmVxOwogCQkJfQogCi0JCQlpZiAoaW5uZXJidWNrZXRzaXplID4gdGhp
c2J1Y2tldHNpemUpCi0JCQkJaW5uZXJidWNrZXRzaXplID0gdGhpc2J1Y2tldHNpemU7Ci0J
CQlpZiAoaW5uZXJtY3ZmcmVxID4gdGhpc21jdmZyZXEpCi0JCQkJaW5uZXJtY3ZmcmVxID0g
dGhpc21jdmZyZXE7CisJCQlpbm5lcmJ1Y2tldHNpemUgKj0gdGhpc2J1Y2tldHNpemU7CisJ
CQlpbm5lcm1jdmZyZXEgKj0gdGhpc21jdmZyZXE7CiAJCX0KKworCQlpZiAoaW5uZXJidWNr
ZXRzaXplIDwgMS4wIC8gdmlydHVhbGJ1Y2tldHMpCisJCQlpbm5lcmJ1Y2tldHNpemUgPSAx
LjAgLyB2aXJ0dWFsYnVja2V0czsKIAl9CiAKIAkvKgo=

--a2aeaf39c1854237bf0ed7550f08ad2a--