[PATCH] Fix encoding-dependent LIKE/regex selectivity estimates

Started by Chengpeng Yan4 days ago7 messageshackers
Jump to latest
#1Chengpeng Yan
chengpeng_yan@outlook.com

Hi,

LIKE/regex selectivity estimates for the same pattern depend on the
database encoding, because FIXED_CHAR_SEL is applied per byte rather
than per character. For example, `LIKE '%é'` is estimated at 0.2 in
LATIN1 but 0.04 in UTF8.

Patch attached.

--
Best regards,
Chengpeng Yan

Attachments:

t259348_1
v1-0001-Count-characters-not-bytes-in-pattern-selectivity.patchapplication/octet-stream; name=v1-0001-Count-characters-not-bytes-in-pattern-selectivity.patchDownload+48-6
#2Tom Lane
tgl@sss.pgh.pa.us
In reply to: Chengpeng Yan (#1)
Re: [PATCH] Fix encoding-dependent LIKE/regex selectivity estimates

Chengpeng Yan <chengpeng_yan@outlook.com> writes:

LIKE/regex selectivity estimates for the same pattern depend on the
database encoding, because FIXED_CHAR_SEL is applied per byte rather
than per character. For example, `LIKE '%é'` is estimated at 0.2 in
LATIN1 but 0.04 in UTF8.

I'm not sure what I think about this proposal. I agree it looks dumb
to estimate the selectivity of "é" differently from "e", and even more
so for it to depend on the encoding. However, I believe this per-byte
counting was intentional, with an eye to Far Eastern character sets.
A single ideogram of Chinese or Japanese probably carries about the
same selectivity as a word of English, so giving it the same
selectivity as "e" likewise doesn't sound great. I'm not trying to
claim that per-byte counting is ideal, but there is more here than
meets the eye, so I'm loath to change a longstanding behavior on
the basis of no discussion or evidence. How can we arrive at a
behavior that is sensible for both of those cases?

Some other random comments:

* The fixed_prefix_len correction in regex_selectivity() will
also need adjustment for whatever we do.

* I'm not a fan of removing the case_insensitive flag in
like_selectivity(). Yeah, we've never done anything with it yet,
but it's not the business of a patch like this to decree that
we never will.

* Rather than inserting multiple copies of partial-character-skipping,
I'd be inclined to make the loops advance by characters always.
That will imply making an mb_len call for pattern metacharacters,
but I don't believe the extra cycles are meaningful. This stuff
is not very performance-critical.

* I don't think these test cases are committable as-is: we've
generally found that exposing exact cost estimates results in brittle,
unportable tests. Maybe there's another way, but I'd lean towards
just not bothering. This code is all covered already per
coverage.postgresql.org.

regards, tom lane

#3Tom Lane
tgl@sss.pgh.pa.us
In reply to: Tom Lane (#2)
Re: [PATCH] Fix encoding-dependent LIKE/regex selectivity estimates

I wrote:

I'm not sure what I think about this proposal. I agree it looks dumb
to estimate the selectivity of "é" differently from "e", and even more
so for it to depend on the encoding. However, I believe this per-byte
counting was intentional, with an eye to Far Eastern character sets.
A single ideogram of Chinese or Japanese probably carries about the
same selectivity as a word of English, so giving it the same
selectivity as "e" likewise doesn't sound great. I'm not trying to
claim that per-byte counting is ideal, but there is more here than
meets the eye, so I'm loath to change a longstanding behavior on
the basis of no discussion or evidence. How can we arrive at a
behavior that is sensible for both of those cases?

After noodling about that for awhile, I have a potential answer.
Basically we need (I think) to distinguish letter-y characters
from ideogram-y characters. But there is a serviceable, and
fast, approximation to that in our infrastructure already:
check pg_encoding_dsplen() and see if it's 1 or 2. Double-width
characters can be counted on to carry more information than
regular-width ones. I don't have an immediate proposal about
what selectivity multiplier to assign to double-width characters,
but this approach seems like there's potential to accomplish
what the original hack hoped for without the encoding dependency.

regards, tom lane

#4Chengpeng Yan
chengpeng_yan@outlook.com
In reply to: Tom Lane (#3)
Re: [PATCH] Fix encoding-dependent LIKE/regex selectivity estimates

Hi,

On Nov 19, 2026, at 09:25, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I wrote:

I'm not sure what I think about this proposal. I agree it looks dumb
to estimate the selectivity of "é" differently from "e", and even more
so for it to depend on the encoding. However, I believe this per-byte
counting was intentional, with an eye to Far Eastern character sets.
A single ideogram of Chinese or Japanese probably carries about the
same selectivity as a word of English, so giving it the same
selectivity as "e" likewise doesn't sound great. I'm not trying to
claim that per-byte counting is ideal, but there is more here than
meets the eye, so I'm loath to change a longstanding behavior on
the basis of no discussion or evidence. How can we arrive at a
behavior that is sensible for both of those cases?

After noodling about that for awhile, I have a potential answer.
Basically we need (I think) to distinguish letter-y characters
from ideogram-y characters. But there is a serviceable, and
fast, approximation to that in our infrastructure already:
check pg_encoding_dsplen() and see if it's 1 or 2. Double-width
characters can be counted on to carry more information than
regular-width ones. I don't have an immediate proposal about
what selectivity multiplier to assign to double-width characters,
but this approach seems like there's potential to accomplish
what the original hack hoped for without the encoding dependency.

regards, tom lane

Agreed, and v2 takes that approach. dsplen describes the character
rather than its storage: "é" is narrow in both LATIN1 and UTF-8, and a
double-width character gets extra weight, so an ideograph is estimated
to match far fewer rows than a letter. What the estimate depends on is
how wide the character is, not how many bytes the encoding needs.

The multiplier is the part I can't justify rigorously: how much a
double-width character narrows a match probably differs between scripts,
and I saw no way to derive one value from data. I picked 3 because wide
characters come mostly from the CJK scripts and their common ones take
three bytes in UTF-8, so the estimates in the usual case stay as they
are. Happy to change it.

Your other comments are all in v2. Thanks for the review and the dsplen
suggestion.

--
Best regards,
Chengpeng Yan

Attachments:

t259348_4
v2-0001-Charge-pattern-selectivity-per-character-not-per-.patchapplication/octet-stream; name=v2-0001-Charge-pattern-selectivity-per-character-not-per-.patchDownload+77-27
#5Tom Lane
tgl@sss.pgh.pa.us
In reply to: Chengpeng Yan (#4)
Re: [PATCH] Fix encoding-dependent LIKE/regex selectivity estimates

While trying to test this patch, I was reminded that this logic is
pretty much of a backwater, which likely explains why we've not
gotten more complaints about it. The only code that actually
consumes these pattern-analysis estimates is in patternsel_common(),
and it only uses them if (1) the clause being considered is of the
form "Var Op Const" but (2) we don't have a histogram of at least
100 entries for the Var. I think case (2) is pretty few and far
between in modern Postgres usage; moreover, you have to have a
good deal fewer than 100 entries before we rely heavily on the
estimate rather than the histogram-derived selectivity.

So TBH I'm wondering if this code is worth putting a lot of effort
into, as opposed to just nuking it all from orbit and using some
default number when we lack any histogram. Did your interest in it
stem from any bad real-world experience, and if so what did that
use-case look like?

regards, tom lane

#6Chengpeng Yan
chengpeng_yan@outlook.com
In reply to: Tom Lane (#5)
Re: [PATCH] Fix encoding-dependent LIKE/regex selectivity estimates

Hi,

On Nov 20, 2026, at 02:45, Tom Lane <tgl@sss.pgh.pa.us> wrote:

While trying to test this patch, I was reminded that this logic is
pretty much of a backwater, which likely explains why we've not
gotten more complaints about it. The only code that actually
consumes these pattern-analysis estimates is in patternsel_common(),
and it only uses them if (1) the clause being considered is of the
form "Var Op Const" but (2) we don't have a histogram of at least
100 entries for the Var. I think case (2) is pretty few and far
between in modern Postgres usage; moreover, you have to have a
good deal fewer than 100 entries before we rely heavily on the
estimate rather than the histogram-derived selectivity.

So TBH I'm wondering if this code is worth putting a lot of effort
into, as opposed to just nuking it all from orbit and using some
default number when we lack any histogram. Did your interest in it
stem from any bad real-world experience, and if so what did that
use-case look like?

regards, tom lane

To be honest, no. I have not hit this in production. As you put it
earlier, "é" is estimated below "e" in UTF-8, and it also depends on the
database encoding. Both looked like defects in the model.

You are right that it is rarely reached, so it does not seem worth
continuing to optimize. Looking for what could replace it, I noticed
that generic_restriction_selectivity() does very nearly the same job:
apply the operator to the MCV and histogram samples, and fall back on a
default when there is little data. It is already used for a number of
other operators.

Reusing it for LIKE and regex would make the encoding dependence
disappear by construction, since nothing counts characters any more, and
several hundred lines of bespoke estimation would go away.

Do you think that direction is workable? If so, I'd like to try it
rather than keep improving logic that applies only in a narrow case.

--
Best regards,
Chengpeng Yan

#7Tom Lane
tgl@sss.pgh.pa.us
In reply to: Chengpeng Yan (#6)
Re: [PATCH] Fix encoding-dependent LIKE/regex selectivity estimates

Chengpeng Yan <chengpeng_yan@outlook.com> writes:

On Nov 20, 2026, at 02:45, Tom Lane <tgl@sss.pgh.pa.us> wrote:

So TBH I'm wondering if this code is worth putting a lot of effort
into, as opposed to just nuking it all from orbit and using some
default number when we lack any histogram. Did your interest in it
stem from any bad real-world experience, and if so what did that
use-case look like?

You are right that it is rarely reached, so it does not seem worth
continuing to optimize. Looking for what could replace it, I noticed
that generic_restriction_selectivity() does very nearly the same job:
apply the operator to the MCV and histogram samples, and fall back on a
default when there is little data. It is already used for a number of
other operators.

It is nearly the same logic, but I'm not sure you can easily use that
in combination with the fixed-prefix logic in patternsel_common,
which we should certainly not give up. I'd be inclined to approach
this by just replacing "rest_selec" with a constant and removing all
the subsidiary code that calculates that.

regards, tom lane