Content-Type: multipart/mixed; boundary="------------7kxtMUWLVbAchXCgNufiHd1u"
Message-ID: <753270d7-a303-d1bb-1291-da717bc615a1@enterprisedb.com>
Date: Sat, 17 Jun 2023 15:45:07 +0200
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.11.1
Subject: Re: Incorrect estimation of HashJoin rows resulted from inaccurate
 small table statistics
Content-Language: en-US
To: Quan Zongliang <quanzongliang@yeah.net>, Tom Lane <tgl@sss.pgh.pa.us>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
References: <bd581c3c-68b5-8ddc-c23c-d3c96f0cd983@yeah.net>
 <a06caba6-6821-9d6c-d799-8db1dd0228d2@enterprisedb.com>
 <83d056c0-c3eb-6ef7-bf3a-7e461fcde74d@yeah.net>
 <2463029.1686955597@sss.pgh.pa.us>
 <4660403b-8df9-2b44-2214-26b21f35b539@yeah.net>
From: Tomas Vondra <tomas.vondra@enterprisedb.com>
In-Reply-To: <4660403b-8df9-2b44-2214-26b21f35b539@yeah.net>
Archived-At: <https://www.postgresql.org/message-id/753270d7-a303-d1bb-1291-da717bc615a1%40enterprisedb.com>
Precedence: bulk

This is a multi-part message in MIME format.
--------------7kxtMUWLVbAchXCgNufiHd1u
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

On 6/17/23 02:02, Quan Zongliang wrote:
> 
> 
> On 2023/6/17 06:46, Tom Lane wrote:
>> Quan Zongliang <quanzongliang@yeah.net> writes:
>>> Perhaps we should discard this (dups cnt > 1) restriction?
>>
>> That's not going to happen on the basis of one test case that you
>> haven't even shown us.  The implications of doing it are very unclear.
>> In particular, I seem to recall that there are bits of logic that
>> depend on the assumption that MCV entries always represent more than
>> one row.  The nmultiple calculation Tomas referred to may be failing
>> because of that, but I'm worried about there being other places.
>>

I don't recall any logic that'd outright fail with MCVs containing
single-row groups, and I haven't noticed anything obvious in analyze.c
during a cursory search. Maybe the paper analyze_mcv_list builds on
makes some assumptions? Not sure.

However, compute_distinct_stats() doesn't seem to have such protection
against single-row MCV groups, so if that's wrong we kinda already have
the issue I think (admittedly, compute_distinct_stats is much less used
than compute_scalar_stats).

> 
> The statistics for the other table look like this:
> stadistinct | 6
> stanumbers1 | {0.50096667,0.49736667,0.0012}
> stavalues1  | {v22,v23,v5}
> 
> The value that appears twice in the small table (v1 and v2) does not
> appear here. The stadistinct's true value is 18 instead of 6 (three
> values in the small table do not appear here).
> 
> When calculating the selectivity:
> if (nd2 > sslot2->nvalues)
>   totalsel1 += unmatchfreq1 * otherfreq2 / (nd2 - sslot2->nvalues);
> 
> totalsel1 = 0
> nd2 = 21
> sslot2->nvalues = 2
> unmatchfreq1 = 0.99990002016420476
> otherfreq2 = 0.82608695328235626
> 
> result: totalsel1 = 0.043473913749706022
> rows = 0.043473913749706022 * 23 * 2,000,000 = 1999800
> 

Attached is a script reproducing this.

I think the fundamental issue here is that the most common element of
the large table - v22 (~50%) is not in the tiny one at all. IIRC the
join estimation assumes the domain of one table is a subset of the
other. The values 22 / 23 violate that assumption, unfortunately.

Including all values into the small MCV fix this because then

  otherfreq1 = 0.0

and that simply eliminates the impact of stuff that didn't have a match
between the two MCV lists. Which mitigates the violated assumption.

But once the small table gets too large for the MCV, this won't work
that well - it probably helps a bit, as it makes otherfreq1 smaller.

Which doesn't mean it's useless, but it's likely a rare combination that
a table is (and remains) smaller than MCV, and the large table contains
values without a match in the smaller one (think foreign keys).

> 
>> Basically, you're proposing a rather fundamental change in the rules
>> by which Postgres has gathered statistics for decades.  You need to
>> bring some pretty substantial evidence to support that.  The burden
>> of proof is on you, not on the status quo.
>>

Right. It's a good example of a "quick hack" fixing one particular case,
without considering the consequences on other cases too much. Good as a
starting point, but plenty of legwork to do.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
--------------7kxtMUWLVbAchXCgNufiHd1u
Content-Type: application/sql; name="script.sql"
Content-Disposition: attachment; filename="script.sql"
Content-Transfer-Encoding: base64

Y3JlYXRlIHRhYmxlIHQxIChhIGludCk7Cmluc2VydCBpbnRvIHQxIHNlbGVjdCBpIGZyb20g
Z2VuZXJhdGVfc2VyaWVzKDEsMjEpIHMoaSk7Cmluc2VydCBpbnRvIHQxIHZhbHVlcyAoMSks
ICgyKTsKYW5hbHl6ZSB0MTsKCnNlbGVjdCBtb3N0X2NvbW1vbl92YWxzLCBtb3N0X2NvbW1v
bl9mcmVxcyBmcm9tIHBnX3N0YXRzIHdoZXJlIHRhYmxlbmFtZSA9ICd0MSc7CgpjcmVhdGUg
dGFibGUgdDIgKGEgaW50KTsKaW5zZXJ0IGludG8gdDIgc2VsZWN0IDIyIGZyb20gZ2VuZXJh
dGVfc2VyaWVzKDEsMTAwMDAwKSBzKGkpOwppbnNlcnQgaW50byB0MiBzZWxlY3QgMjMgZnJv
bSBnZW5lcmF0ZV9zZXJpZXMoMSwxMDAwMDApIHMoaSk7Cmluc2VydCBpbnRvIHQyIHNlbGVj
dCA1IGZyb20gZ2VuZXJhdGVfc2VyaWVzKDEsMTAwMCkgcyhpKTsKYW5hbHl6ZSB0MjsKCnNl
bGVjdCBtb3N0X2NvbW1vbl92YWxzLCBtb3N0X2NvbW1vbl9mcmVxcyBmcm9tIHBnX3N0YXRz
IHdoZXJlIHRhYmxlbmFtZSA9ICd0Mic7CgpleHBsYWluIGFuYWx5emUgc2VsZWN0ICogZnJv
bSB0MSBqb2luIHQyIHVzaW5nIChhKTsK

--------------7kxtMUWLVbAchXCgNufiHd1u--