public inbox for [email protected]
help / color / mirror / Atom feedFrom: Tomas Vondra <[email protected]>
To: 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: Fri, 3 Nov 2023 17:43:26 +0100
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
<CAKU4AWoKiogNir=ESrm6F9pUwYFDfmsoNG9w9k1MG3VUbKM0Dw@mail.gmail.com>
<[email protected]>
On 9/11/23 10:04, Lepikhov Andrei wrote:
>
>
> 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.
>>
Yes, this analysis is correct - final_cost_hashjoin assumes the clauses
may be correlated (not necessarily by functional dependencies, just that
the overall ndistinct is not a simple product of per-column ndistincts).
And it even says so in the comment before calculating bucket size:
* Determine bucketsize fraction and MCV frequency for the inner
* relation. We use the smallest bucketsize or MCV frequency estimated
* for any individual hashclause; this is undoubtedly conservative.
I'm sure this may lead to inflated cost for "good" cases (where the
actual bucket size really is a product), which may push the optimizer to
use the less efficient/slower join method.
Unfortunately, AFAICS the patch simply assumes the extreme in the
opposite direction - it assumes each clause splits the bucket for each
distinct value in the column. Which works great when it's true, but
surely it'd have issues when the columns are correlated?
I think this deserves more discussion, i.e. what happens if the
assumptions do not hold? We know what happens for the conservative
approach, but what's the worst thing that would happen for the
optimistic one?
I doubt e can simply switch from the conservative approach to the
optimistic one. Yes, it'll make some queries faster, but for other
queries it likely causes problems and slowdowns.
IMHO the only principled way forward is to get a better ndistinct
estimate (which this implicitly does), perhaps by using extended
statistics. I haven't tried, but I guess it'd need to extract the
clauses for the inner side, and call estimate_num_groups() on it.
This however reminds me we don't use extended statistics for join
clauses at all. Which means that even with accurate extended statistics,
we can still get stuff like this for multiple join clauses:
Hash Join (cost=1317.00..2386.00 rows=200 width=24)
(actual time=85.781..8574.784 rows=8000000 loops=1)
This is unrelated to the issue discussed here, of course, as it won't
affect join method selection for that join. But it certainly will affect
all estimates/costs above that join, which can be pretty disastrous.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
view thread (3+ messages)
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], [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