public inbox for [email protected]
help / color / mirror / Atom feedFrom: Ilia Evdokimov <[email protected]>
To: Enrique Sánchez <[email protected]>
To: [email protected]
Subject: Re: Extended statistics improvement: multi-column MCV missing values
Date: Tue, 19 May 2026 01:13:39 +0300
Message-ID: <[email protected]> (raw)
In-Reply-To: <CAOCkzAkmnAjEWxfP-vBTRta7cHe5CMu8i4SFSeOi2nS8+Kj7Ng@mail.gmail.com>
References: <CAOCkzAkmnAjEWxfP-vBTRta7cHe5CMu8i4SFSeOi2nS8+Kj7Ng@mail.gmail.com>
Hi Enrique,
On 5/18/26 19:09, Enrique Sánchez wrote:
>
> Postgres only uses multi-column MCVs when the value we are looking for
> is in the list. If not, it falls back into individual independent
> statistics to estimate selectivity.
> However, a miss in a multi-column MCV list still yields valuable
> information that it currently throws away: we know that the
> combination's frequency is strictly bounded by the frequency of the
> last (least common) item in that MCV list.
LGTM. If the multicolumn MCV statistics exists and the clause
combination is absent from the MCV-list, we can use the least frequent
MCV item as an upper bound. BTW, this only applies to AND-clauses.
>
> 2. Estimate selectivity as Postgres does for single-column values not
> in MCVs
> =============================================================================
> While that significantly improves estimations, we could mirror what
> Postgres already does for individual MCVs. Quote from the official
> documentation:
> > The approach is to use the fact that the value is not in the list,
> combined with the knowledge of the frequencies for all of the MCVs:
> > That is, add up all the frequencies for the MCVs and subtract them
> from one, then divide by the number of other distinct values.
>
> To achieve this, we need to store an ndistinct estimation alongside
> the MCVs that can be used for partial or entire column match.
>
> P(1, 1, 1) = (1 - sum(MCVs)) / (ndistinct(col_a, col_b, col_c) -
> MCV_list_size)
>
>
> ...
>
> I think this is a cheap way to prevent bad estimations. The storage
> overhead of adding an ndistinct field is trivial compared to the MCV
> list itself, and the O(1) arithmetic during planning adds no
> measurable overhead. I look forward to your feedback before drafting a
> patch.
For this, the ndistinct extended statistics already exist. If both MCV
and ndistinct statistics are present on the same column set, the formula
is correct. There are already places in the code that compute ndistinct
for columns without extended ndistinct statistics (see
estimate_num_groups) - but it is worth thinking carefully about whether
the added complexity is justified before going down that path.
--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com/
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: Extended statistics improvement: multi-column MCV missing values
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