Content-Type: multipart/alternative;
 boundary="------------HUM0S3z2abOrBI0EgJKRqpuY"
Message-ID: <00d52d6f-ae9e-40df-80d3-9e96a23efa70@tantorlabs.com>
Date: Tue, 19 May 2026 01:13:39 +0300
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: Extended statistics improvement: multi-column MCV missing values
To: =?UTF-8?Q?Enrique_S=C3=A1nchez?= <enriqueesanchz@gmail.com>,
 pgsql-hackers@lists.postgresql.org
References: 
 <CAOCkzAkmnAjEWxfP-vBTRta7cHe5CMu8i4SFSeOi2nS8+Kj7Ng@mail.gmail.com>
Content-Language: en-US
From: Ilia Evdokimov <ilya.evdokimov@tantorlabs.com>
In-Reply-To: 
 <CAOCkzAkmnAjEWxfP-vBTRta7cHe5CMu8i4SFSeOi2nS8+Kj7Ng@mail.gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/00d52d6f-ae9e-40df-80d3-9e96a23efa70%40tantorlabs.com>
Precedence: bulk

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

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/

--------------HUM0S3z2abOrBI0EgJKRqpuY
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit

<!DOCTYPE html>
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  </head>
  <body>
    <p>Hi Enrique,</p>
    <p>On 5/18/26 19:09, Enrique Sánchez wrote:</p>
    <blockquote type="cite"
cite="mid:CAOCkzAkmnAjEWxfP-vBTRta7cHe5CMu8i4SFSeOi2nS8+Kj7Ng@mail.gmail.com">
      <meta http-equiv="content-type" content="text/html; charset=UTF-8">
      <div dir="ltr"><span style="font-family:monospace"><br>
          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.<br>
          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.<br>
        </span></div>
    </blockquote>
    <p>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.</p>
    <p><br>
    </p>
    <blockquote type="cite"
cite="mid:CAOCkzAkmnAjEWxfP-vBTRta7cHe5CMu8i4SFSeOi2nS8+Kj7Ng@mail.gmail.com">
      <div dir="ltr"><span style="font-family:monospace"><br>
          2. Estimate selectivity as Postgres does for single-column
          values not in MCVs<br>
=============================================================================<br>
          While that significantly improves estimations, we could mirror
          what Postgres already does for individual MCVs. Quote from the
          official documentation:<br>
          &gt; 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:<br>
          &gt; That is, add up all the frequencies for the MCVs and
          subtract them from one, then divide by the number of other
          distinct values.<br>
          <br>
          To achieve this, we need to store an ndistinct estimation
          alongside the MCVs that can be used for partial or entire
          column match.<br>
          <br>
          P(1, 1, 1) = (1 - sum(MCVs)) / (ndistinct(col_a, col_b, col_c)
          - MCV_list_size)<br>
          <br>
          <br>
          ...<br>
          <br>
          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.</span></div>
    </blockquote>
    <p>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.</p>
    <p><span class="moz-txt-tag">-- <br>
      </span>Best regards,<br>
      Ilia Evdokimov,<br>
      Tantor Labs LLC,<br>
      <a class="moz-txt-link-freetext" href="https://tantorlabs.com/">https://tantorlabs.com/</a></p>
  </body>
</html>

--------------HUM0S3z2abOrBI0EgJKRqpuY--