Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1uzfpJ-0061nF-4o for pgsql-performance@arkaria.postgresql.org; Fri, 19 Sep 2025 18:27:21 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1uzfpF-008ps1-Jf for pgsql-performance@arkaria.postgresql.org; Fri, 19 Sep 2025 18:27:17 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1uzfpF-008prt-6a for pgsql-performance@lists.postgresql.org; Fri, 19 Sep 2025 18:27:17 +0000 Received: from mail-wr1-x431.google.com ([2a00:1450:4864:20::431]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.96) (envelope-from ) id 1uzfpA-001k8N-18 for pgsql-performance@lists.postgresql.org; Fri, 19 Sep 2025 18:27:16 +0000 Received: by mail-wr1-x431.google.com with SMTP id ffacd0b85a97d-3ef166e625aso874444f8f.2 for ; Fri, 19 Sep 2025 11:27:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mattlong.org; s=google; t=1758306430; x=1758911230; darn=lists.postgresql.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=SCjsbH0gJJPThLrdJBdOZmNAb/DXg4Qxj4B8uC+DUfQ=; b=Urf+xJeLRQ13hb5eyEfffuWkCtaKStmh/A6mJwC7MvU+OggKClOVDmFw1RTKBsHHlY dZ+AlnSMMw8AzCB8VwnHTWLPhNOqHM03D8FJ1ZFlvKdl6Zy0rtuVA4T+jQzA9joUym7o fUUkoK1tmufJpVPhM+9v8X6dk+Q8TmH8XqGhxrMkEAREBc3D8j6GismvPBfwThxIMKrn 5dUBDflgWd2hoV+5CheKeVyUOr7hBgERogGuDDRshq8O7K7z1qXfIq/bDQjDGEhaiSz8 ZuX3JK8b/ex6ZUyrmoOVXieMO8Qc5+b4CClyFJuqv01ncwAgyqb5DuC6QtMVtDUq3wBD t54w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1758306430; x=1758911230; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=SCjsbH0gJJPThLrdJBdOZmNAb/DXg4Qxj4B8uC+DUfQ=; b=bjyOe6Uh17ACoNdguMa4HowpG6qgQr9KdGZuMb0NWoKYnm6fkPUvLDVFQ61pCJRTk6 2MXoIE/LlAprhTnOt3xuv3gd1EL3JD+1UBY7U0PNGuXN8BJDn7Nk2xZsGlyKyACZuo4J m0rrO162y6lFkNIEPwKt2+b2bi6qc/+5Z5ChpZNhP/kNCS+DOLLn02MI3mjZFETw11Dv PZej3kl0ZsExZAqkmeWi/kW2AsHZomxlPNWHeb/42RhbFQKXTFP7NJAhKpVPO5k+4v5W bdpr72XJKOH9EmyZB1xXy54GDNUmdJdaQ2xeAj90/+P7y8ekopf5MtsxIcptH1KHjT19 qXFw== X-Forwarded-Encrypted: i=1; AJvYcCX9bUCMcvLvwQwMRZ4szlnOBxrck2DS3XCxBEwJSRpb/DSUP+wZPhKLF3Go/Rugu3+EUG5g/fK3S6jePSp9zHfQIg==@lists.postgresql.org X-Gm-Message-State: AOJu0YygZ3cOyTQgxOkAkpoWdtrptisSZDCBzIi0BoqXXFnaXUOzacYy UrIIWNHNd8/h+nID7rJ6c/ozDg6gu56zbRlNdx3hnkpGSdIlHoixhKTrxVvdgA4r//QehrhUSlY Bg6Mid6VFJ9wRei5qB/oWYCkC7PM+cFtvXHvzEEP1nw== X-Gm-Gg: ASbGncvGxExdvMdF4cfIsfsDuPTjpXKvcY5IVWyeM+JBbUPOvrtFRO4cTpjj7k3p41x 7ETq7loOLIuXFEN8d2sEyUgP2UExsV/ZghPpHaMACtsIJbKKQaxiZt7LeQ6zYzdPsPf0sTv7xkN oyB6xKNRZizmqjXCD20xgquYWQ9eyo4Vv7A7uQLgAeOiIJBb9P/OjSZC/4fxk5nxx4KrWz9quQm QPP3tWeiMEszUja X-Google-Smtp-Source: AGHT+IHBJ7Pl2XT+HvmwzjfWwDd9PLPbh32SrYYAaHtzMoHnC1pNTSHHta8AvT4xBybaiFCQaIB4xDI4YV4gogCK5KI= X-Received: by 2002:a05:6000:3109:b0:3ec:db18:aa37 with SMTP id ffacd0b85a97d-3ee8863edf3mr3603168f8f.60.1758306430004; Fri, 19 Sep 2025 11:27:10 -0700 (PDT) MIME-Version: 1.0 References: <3e539c8b-c95a-4ba9-8462-04045b2da2b0@dalibo.com> <1751511.1749259794@sss.pgh.pa.us> <2194366.1752875645@sss.pgh.pa.us> <987464.1757374621@sss.pgh.pa.us> <1209259.1757445586@sss.pgh.pa.us> In-Reply-To: <1209259.1757445586@sss.pgh.pa.us> From: Matt Long Date: Fri, 19 Sep 2025 11:26:59 -0700 X-Gm-Features: AS18NWBvskFyIlfqUONmXY-4ipUB0Y-e8wrLdolBFsKy0L51tPeWDi_n-sPnKmE Message-ID: Subject: Re: Poor row estimates from planner, stat `most_common_elems` sometimes missing for a text[] column To: Tom Lane Cc: Mark Frost , "pgsql-performance@lists.postgresql.org" Content-Type: multipart/alternative; boundary="0000000000002ac60f063f2b9eb5" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --0000000000002ac60f063f2b9eb5 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable I finally got around to testing your patch on a realistic data set. In short, the patch worked beautifully even with the division by 2 removed. In case it's helpful, the full write up of my investigation can be found at https://gist.github.com/mattlong/0617bec6e1cf5bc6b70c6c2951901df7 Your reasoning about the division by 2 being a way to approximate the "average" non-MCE value seems logical. The patch as tested above without a division yielded a row estimate of 28 for a non-MCE element on a table with ~2.1 million rows where all non-MCE elements occur exactly once. For our scenario/distribution of the data, the most conservative option, i.e. no division, was good enough to produce optimal query plans, but this is of course a very specific data distribution. Thinking more generally, there are two cases: When the MCE list is full and when the MCE list is NOT full. When the MCE list is NOT full, the case that this patch addresses, the data is definitionally heavily skewed; minfreq will already be quite low. Whether or not it gets divided by 2 (or some other number) probably won't make much of a difference either way. When the MCE list is full, the data is less skewed; there will generally be a longer tail of element frequencies. Dividing by 2 will be more impactful here in an attempt to approximate the "average" non-MCE element frequency. Putting that together, it seems like keeping the division by 2 would be preferable? On Tue, Sep 9, 2025 at 12:19=E2=80=AFPM Tom Lane wrote: > > I wrote: > > * The selectivity functions believe that the upper bound on the > > frequency of non-MCEs is minfreq / 2, not the stored minfreq. > > This seems like complete brain fade: there could easily be > > elements with frequency just less than minfreq, and probably are > > if the data distribution follows Zipf's law. I did not dig into > > the git history, but I wonder if the divide-by-two business > > predates the introduction of the lossy-counting algorithm, and > > if so whether it was less insane with the original collection > > algorithm. In any case, this patch removes the divisions by 2, > > and makes some nearby cosmetic improvements. > > In the light of morning, I started to have second thoughts about > this aspect of the patch. I checked the git history this time, > and found that the oldest instance of "minfreq / 2" dates to > 4e57668da which originated from this discussion: > > https://www.postgresql.org/message-id/flat/488DAEB8.3000402%40students.mimu= w.edu.pl > > It's already coded like that in Jan's initial patch, and there > was no discussion in the thread, so not a lot to be gleaned: > > + /* > + * The element is not in MCELEM. Punt, but assure that the > + * selectivity cannot be more than minfreq / 2. > + */ > + return (Selectivity) Min(DEFAULT_TS_SEL, minfreq / 2); > > But looking at this, I think the problem is really that the comment > fails to describe his thought process. We know that the frequency > of this not-in-the-MCE-list value cannot be more than minfreq, but > we have no idea how much less it is. I think the idea of the > division might have been to assume that an "average" non-MCE value > would have a frequency about half that of the lowest MCE. It does > seem reasonable to use some number lower than the cutoff, although > I dunno if 0.5 is exactly the right factor. > > So now I'm wondering if we should leave the divisions alone and > instead fix the comments to explain why they are there. Bolstering > this is that on the two test cases you guys submitted, the patch > with the divisions gets a spot-on estimate (1 row) while removing > the divisions yields an estimate of 2 rows. I don't put a lot of > weight on that, since these are toy examples. But I wonder if you > guys could test the patch on some of your real-world cases and > see if it looks like we should keep the divisions. > > regards, tom lane --0000000000002ac60f063f2b9eb5 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I finally got around to testing your patch on a realistic = data set. In short, the patch worked beautifully even with the division by = 2 removed. In case it's helpful, the full write up of my investigation = can be found at https://gist.github.com/mattlong/0617bec6e1cf5bc6b70c6c2= 951901df7

Your reasoning about the division by 2 bei= ng a way to approximate the "average" non-MCE value seems logical= . The patch as tested above without a division yielded a row estimate of 28= for a non-MCE element on a table with ~2.1 million rows where all non-MCE = elements occur exactly once. For our scenario/distribution of the data, the= most conservative option, i.e. no division, was good enough to produce opt= imal query plans, but this is of course a very specific data distribution.<= /div>

Thinking more generally, there are two cases: When= the MCE list is full and when the MCE list is NOT full.

When the MCE list is NOT full, the case that this patch addresses, t= he data is definitionally heavily skewed; minfreq will already be quite low= . Whether or not it gets divided by 2 (or some other number) probably won&#= 39;t make much of a difference either way.

When th= e MCE list is full, the data is less skewed; there will generally be a long= er tail of element frequencies. Dividing by 2 will be more impactful here i= n an attempt to approximate the "average" non-MCE element frequen= cy.

Putting that together, it seems like keeping t= he division by 2 would be preferable?

On Tue, Sep 9, 2025 at 12:19= =E2=80=AFPM Tom Lane <tgl@sss.pgh.p= a.us> wrote:
>
> I wrote:
> > * The selectivity= functions believe that the upper bound on the
> > frequency of no= n-MCEs is minfreq / 2, not the stored minfreq.
> > This seems like= complete brain fade: there could easily be
> > elements with freq= uency just less than minfreq, and probably are
> > if the data dis= tribution follows Zipf's law.=C2=A0 I did not dig into
> > the= git history, but I wonder if the divide-by-two business
> > preda= tes the introduction of the lossy-counting algorithm, and
> > if s= o whether it was less insane with the original collection
> > algo= rithm.=C2=A0 In any case, this patch removes the divisions by 2,
> &g= t; and makes some nearby cosmetic improvements.
>
> In the ligh= t of morning, I started to have second thoughts about
> this aspect o= f the patch.=C2=A0 I checked the git history this time,
> and found t= hat the oldest instance of "minfreq / 2" dates to
> 4e57668= da which originated from this discussion:
>
> https://www.postgresql.org/message-id/flat/488DAEB8.3000402%40students.= mimuw.edu.pl
>
> It's already coded like that in Jan= 9;s initial patch, and there
> was no discussion in the thread, so no= t a lot to be gleaned:
>
> + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0/*
> + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 * The element= is not in MCELEM. Punt, but =C2=A0assure that the
> + =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 * selectivity cannot be more than minfreq / 2.<= br>> + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 */
> + =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return (Selectivity) Min(DEFAULT_TS_SEL, min= freq / 2);
>
> But looking at this, I think the problem is real= ly that the comment
> fails to describe his thought process.=C2=A0 We= know that the frequency
> of this not-in-the-MCE-list value cannot b= e more than minfreq, but
> we have no idea how much less it is.=C2=A0= I think the idea of the
> division might have been to assume that an= "average" non-MCE value
> would have a frequency about hal= f that of the lowest MCE.=C2=A0 It does
> seem reasonable to use some= number lower than the cutoff, although
> I dunno if 0.5 is exactly t= he right factor.
>
> So now I'm wondering if we should leav= e the divisions alone and
> instead fix the comments to explain why t= hey are there.=C2=A0 Bolstering
> this is that on the two test cases = you guys submitted, the patch
> with the divisions gets a spot-on est= imate (1 row) while removing
> the divisions yields an estimate of 2 = rows.=C2=A0 I don't put a lot of
> weight on that, since these ar= e toy examples.=C2=A0 But I wonder if you
> guys could test the patch= on some of your real-world cases and
> see if it looks like we shoul= d keep the divisions.
>
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 regards, tom lane
--0000000000002ac60f063f2b9eb5--