Обсуждение: Inconsistent results with libc sorting on Windows
Hi, While trying pg16beta1 libc collations on Windows, I noticed that UTF-8 text sorts sometimes differently across invocations with the same locales, which is wrong since these collations are deterministic. The OS is Windows 10 Home, version 10.0.19045 Build 19045, self-built 16beta1 with VS Community 2022, without ICU, default configuration in postgresql.conf. It seems to occur more or less randomly with all libc locales except C/POSIX, with the probability of getting differences being seemingly much higher when the data gets larger in number of rows and uses higher codepoints (like if all character are in [U+0001,U+0400] the sorts never differ with 40k rows, but they do if there are much more rows or if the range is [U+0001,U+2000]). Also, it does not occur at all if parallel scan is disabled. I've come up with a self-contained script that generates random words and repeatedly sorts and feed them to md5sum. It takes the number of rows and the highest Unicode codepoint as arguments, and shows when the checksums differ across consecutive invocations. Here's a typical run showing how it goes wrong after the 14th sort: $ bash repro-coll-windows.sh 40000 16383 NOTICE: relation "random_words" already exists, skipping CREATE TABLE TRUNCATE TABLE CREATE FUNCTION DROP COLLATION CREATE COLLATION INSERT 0 40000 ANALYZE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 35050d858f4c590788132627e74f62c8 -> e746b626fcc848cbbc67570a7dde03bb (iter=15) 16 e746b626fcc848cbbc67570a7dde03bb -> 35050d858f4c590788132627e74f62c8 (iter=16) 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 35050d858f4c590788132627e74f62c8 -> 6bf38563d1267339122154bd7d4fbfce (iter=38) 39 6bf38563d1267339122154bd7d4fbfce -> 35050d858f4c590788132627e74f62c8 (iter=39) 40 41 42 43 44 45 46 47 48 49 50 51 35050d858f4c590788132627e74f62c8 -> 3d2072698054d0bd57beefea0248b7e6 (iter=51) 52 3d2072698054d0bd57beefea0248b7e6 -> 35050d858f4c590788132627e74f62c8 (iter=52) 53 54 55 56 57 58 59 ^C Would anyone be able to reproduce this? That might be a local problem although there's nothing special installed AFAICS. Initially I saw this with a larger dataset that I can't share, and the diffs between outputs showed that only a few lines out of 2 million lines were getting displaced across sorts. It also happens on the same OS with Pg15.3 (EDB build) and the default libc collation, so I would not immediately suspect new code in Pg16. Best regards, -- Daniel Vérité https://postgresql.verite.pro/ Twitter: @DanielVerite
Вложения
On 6/5/23 18:07, Daniel Verite wrote: > While trying pg16beta1 libc collations on Windows, I noticed that UTF-8 > text sorts sometimes differently across invocations with the same > locales, which is wrong since these collations are deterministic. <snip> > Also, it does not occur at all if parallel scan is disabled. This is a wild shot in the dark, but I wonder if somehow the locale is being initialized (i.e. setlocale) differently in the parallel workers than the backend due to some Windows specific behavior differences? -- Joe Conway PostgreSQL Contributors Team RDS Open Source Databases Amazon Web Services: https://aws.amazon.com
On Tue, Jun 6, 2023 at 10:08 AM Daniel Verite <daniel@manitou-mail.org> wrote: > Also, it does not occur at all if parallel scan is disabled. Could this be a clue that it is failing to be transitive?
On Tue, Jun 6, 2023 at 1:30 PM Thomas Munro <thomas.munro@gmail.com> wrote: > On Tue, Jun 6, 2023 at 10:08 AM Daniel Verite <daniel@manitou-mail.org> wrote: > > Also, it does not occur at all if parallel scan is disabled. > > Could this be a clue that it is failing to be transitive? That vaguely rang a bell for me... and then I remembered this thread: https://www.postgresql.org/message-id/flat/20191206063401.GB1629883%40rfd.leadboat.com
Thomas Munro wrote: > > > Also, it does not occur at all if parallel scan is disabled. > > > > Could this be a clue that it is failing to be transitive? > > That vaguely rang a bell for me... and then I remembered this thread: > > https://www.postgresql.org/message-id/flat/20191206063401.GB1629883%40rfd.leadboat.com Thanks for the pointer, non-transitive comparisons seem a likely cause indeed. The parallel scan appears to imply some randomness in the sequence of comparisons, which makes the problem more visible. After changing the test to shuffle the rows before each sort, non-parallel scans also produce outputs that differ, proving that parallelism is not a root cause. Running the test with all the libc collations with collencoding in (-1,6) shows that the only ones not affected are C/POSIX/ucs_basic. Otherwise the 569 other pre-created libc collations that can be used with UTF-8 are affected, plus the default collation (French_France.1252 in my case). Best regards, -- Daniel Vérité https://postgresql.verite.pro/ Twitter: @DanielVerite
On 6/7/23 07:58, Daniel Verite wrote: > Thomas Munro wrote: > >> > > Also, it does not occur at all if parallel scan is disabled. >> > >> > Could this be a clue that it is failing to be transitive? >> >> That vaguely rang a bell for me... and then I remembered this thread: >> >> https://www.postgresql.org/message-id/flat/20191206063401.GB1629883%40rfd.leadboat.com > > Thanks for the pointer, non-transitive comparisons seem a likely cause > indeed. > > The parallel scan appears to imply some randomness in the sequence of > comparisons, which makes the problem more visible. > After changing the test to shuffle the rows before each sort, > non-parallel scans also produce outputs that differ, proving that > parallelism is not a root cause. > > Running the test with all the libc collations with collencoding in > (-1,6) shows that the only ones not affected are C/POSIX/ucs_basic. > Otherwise the 569 other pre-created libc collations that can be used > with UTF-8 are affected, plus the default collation > (French_France.1252 in my case). Wow, that sounds pretty horrid -- Joe Conway PostgreSQL Contributors Team RDS Open Source Databases Amazon Web Services: https://aws.amazon.com
On 6/7/23 07:58, Daniel Verite wrote:
> Thomas Munro wrote:
>
>> > > Also, it does not occur at all if parallel scan is disabled.
>> >
>> > Could this be a clue that it is failing to be transitive?
>>
>> That vaguely rang a bell for me... and then I remembered this thread:
>>
>> https://www.postgresql.org/message-id/flat/20191206063401.GB1629883%40rfd.leadboat.com
>
> Thanks for the pointer, non-transitive comparisons seem a likely cause
> indeed.
Just to make sure we are all seeing the same problem, does the attached patch fix your test?
Regards,
Juan José Santamaría Flecha
Вложения
Juan José Santamaría Flecha wrote: > Just to make sure we are all seeing the same problem, does the attached > patch fix your test? The problem of the random changes in sorting disappears for all libc locales in pg_collation, so this is very promising. However it persists for the default collation. Best regards, -- Daniel Vérité https://postgresql.verite.pro/ Twitter: @DanielVerite
On Fri, Jun 9, 2023 at 11:18 AM Daniel Verite <daniel@manitou-mail.org> wrote:
Juan José Santamaría Flecha wrote:
> Just to make sure we are all seeing the same problem, does the attached
> patch fix your test?
The problem of the random changes in sorting disappears for all libc
locales in pg_collation, so this is very promising.
Great to hear, I'll try to push the patch to something reviewable as per attached.
However it persists for the default collation.
We can apply a similar approach there.
Regards,
Juan José Santamaría Flecha
Вложения
Trying to follow along here... you're doing the moral equivalent of strxfrm(), so sort keys have the transitive property but direct string comparisons don't? Or is this because LCIDs reach a different algorithm somehow (or otherwise why do you need to use LCIDs for this, when there is a non-LCID version of that function, with a warning not to use the older LCID version[1]?) [1] https://learn.microsoft.com/en-us/windows/win32/api/winnls/nf-winnls-lcmapstringw
On Tue, Jun 13, 2023 at 5:59 PM Thomas Munro <thomas.munro@gmail.com> wrote: > Trying to follow along here... you're doing the moral equivalent of > strxfrm(), so sort keys have the transitive property but direct string > comparisons don't? Or is this because LCIDs reach a different > algorithm somehow (or otherwise why do you need to use LCIDs for this, > when there is a non-LCID version of that function, with a warning not > to use the older LCID version[1]?) I'm reminded of the fact that the abbreviated keys strxfrm() debacle (back when 9.5 was released) was caused by a bug in strcoll() -- not a bug in strxfrm() itself. From our point of view the problem was that strxfrm() failed to be bug compatible with strcoll() due to a buggy strcoll() optimization. I believe that strxfrm() is generally less likely to have bugs than strcoll(). There are far fewer opportunities to dodge unnecessary work in the case of strxfrm()-like algorithms (offering something like ICU's pg_strnxfrm_prefix_icu() prefix optimization is the only one). On the other hand, collation library implementers are likely to heavily optimize strcoll() for typical use-cases such as sorting and binary search. Using strxfrm() for everything is discouraged [1]. There is an important difference between this issue and the various glibc collation related bugs that I've come across, though: to the best of my knowledge there was never a glibc bug that caused strcoll() to violate transitive consistency -- it always agreed with itself. So this is a new one on me. Seems like that might make "always use strxfrm()" (or whatever it's actually called on this platform) acceptable; strxfrm() can't really violate transitive consistency in the same way. (I think -- I'm assuming that it'll always produce a conditioned binary string in a deterministic fashion, since AFAICT even this buggy strcoll()-like function won't ever give an inconsistent answer when it compares the same two strings.) [1] https://unicode-org.github.io/icu/userguide/collation/concepts#sortkeys-vs-comparison -- Peter Geoghegan
On Wed, Jun 14, 2023 at 4:13 AM Peter Geoghegan <pg@bowt.ie> wrote:
On Tue, Jun 13, 2023 at 5:59 PM Thomas Munro <thomas.munro@gmail.com> wrote:
> Trying to follow along here... you're doing the moral equivalent of
> strxfrm(), so sort keys have the transitive property but direct string
> comparisons don't? Or is this because LCIDs reach a different
> algorithm somehow (or otherwise why do you need to use LCIDs for this,
> when there is a non-LCID version of that function, with a warning not
> to use the older LCID version[1]?)
I'm reminded of the fact that the abbreviated keys strxfrm() debacle
(back when 9.5 was released) was caused by a bug in strcoll() -- not a
bug in strxfrm() itself. From our point of view the problem was that
strxfrm() failed to be bug compatible with strcoll() due to a buggy
strcoll() optimization.
I believe that strxfrm() is generally less likely to have bugs than
strcoll(). There are far fewer opportunities to dodge unnecessary work
in the case of strxfrm()-like algorithms (offering something like
ICU's pg_strnxfrm_prefix_icu() prefix optimization is the only one).
On the other hand, collation library implementers are likely to
heavily optimize strcoll() for typical use-cases such as sorting and
binary search. Using strxfrm() for everything is discouraged [1].
Yes, I think the situation is quite similar to what you describe, with its WIN32 peculiarities. Take for example the attached program, it'll output:
s1 = s2
s2 = s3
s1 > s3
c1 > c2
c2 > c3
c1 > c3
s2 = s3
s1 > s3
c1 > c2
c2 > c3
c1 > c3
As you can see the test for CompareStringEx() is broken, but we get a sane answer with LCMapStringEx().
Regards,
Juan José Santamaría Flecha
Вложения
On Wed, Jun 14, 2023 at 10:50 PM Juan José Santamaría Flecha <juanjo.santamaria@gmail.com> wrote: > Yes, I think the situation is quite similar to what you describe, with its WIN32 peculiarities. Take for example the attachedprogram, it'll output: > > s1 = s2 > s2 = s3 > s1 > s3 > c1 > c2 > c2 > c3 > c1 > c3 > > As you can see the test for CompareStringEx() is broken, but we get a sane answer with LCMapStringEx(). Given that the documented behaviour is that ".. the sort key produces the same order as when the source string is used in CompareString or CompareStringEx"[1], this seems like a reportable bug, unless perhaps your test program is hiding an error with that default case you have. [1] https://learn.microsoft.com/en-us/windows/win32/intl/handling-sorting-in-your-applications
On Thu, Jun 15, 2023 at 1:57 AM Thomas Munro <thomas.munro@gmail.com> wrote:
Given that the documented behaviour is that ".. the sort key produces
the same order as when the source string is used in CompareString or
CompareStringEx"[1], this seems like a reportable bug, unless perhaps
your test program is hiding an error with that default case you have.
[1] https://learn.microsoft.com/en-us/windows/win32/intl/handling-sorting-in-your-applications
Ok, let's see where the report goes:
Regards,
Juan José Santamaría Flecha
On 2023-Jun-19, Juan José Santamaría Flecha wrote: > Ok, let's see where the report goes: > > https://developercommunity.visualstudio.com/t/CompareStringEx-non-transitive/10393003?q=comparestringex Hm, so this appears to have been marked as solved by Microsoft. Can you recheck? Also, what does the resolution mean for Postgres, in practical terms? -- Álvaro Herrera PostgreSQL Developer — https://www.EnterpriseDB.com/ "If you have nothing to say, maybe you need just the right tool to help you not say it." (New York Times, about Microsoft PowerPoint)
El lun, 3 jul 2023, 17:42, Alvaro Herrera <alvherre@alvh.no-ip.org> escribió:
On 2023-Jun-19, Juan José Santamaría Flecha wrote:
> Ok, let's see where the report goes:
>
> https://developercommunity.visualstudio.com/t/CompareStringEx-non-transitive/10393003?q=comparestringex
Hm, so this appears to have been marked as solved by Microsoft. Can you
recheck? Also, what does the resolution mean for Postgres, in practical
terms?
It's not really solved, they have just pushed the issue to another team that's only reachable through the Windows feedback hub. I've already provided the feedback, but it's only visible through the proprietary app.
I would say there haven't been any real progress on that front so far.
Regards,
Juan José Santamaría Flecha
On Wed, Jun 14, 2023 at 12:50:28PM +0200, Juan José Santamaría Flecha wrote: > On Wed, Jun 14, 2023 at 4:13 AM Peter Geoghegan <pg@bowt.ie> wrote: > > > On Tue, Jun 13, 2023 at 5:59 PM Thomas Munro <thomas.munro@gmail.com> > > wrote: > > > Trying to follow along here... you're doing the moral equivalent of > > > strxfrm(), so sort keys have the transitive property but direct string > > > comparisons don't? Or is this because LCIDs reach a different > > > algorithm somehow (or otherwise why do you need to use LCIDs for this, > > > when there is a non-LCID version of that function, with a warning not > > > to use the older LCID version[1]?) > > > > I'm reminded of the fact that the abbreviated keys strxfrm() debacle > > (back when 9.5 was released) was caused by a bug in strcoll() -- not a > > bug in strxfrm() itself. From our point of view the problem was that > > strxfrm() failed to be bug compatible with strcoll() due to a buggy > > strcoll() optimization. > > > > I believe that strxfrm() is generally less likely to have bugs than > > strcoll(). There are far fewer opportunities to dodge unnecessary work > > in the case of strxfrm()-like algorithms (offering something like > > ICU's pg_strnxfrm_prefix_icu() prefix optimization is the only one). > > On the other hand, collation library implementers are likely to > > heavily optimize strcoll() for typical use-cases such as sorting and > > binary search. Using strxfrm() for everything is discouraged [1]. > > > > Yes, I think the situation is quite similar to what you describe, with its > WIN32 peculiarities. Take for example the attached program, it'll output: > > s1 = s2 > s2 = s3 > s1 > s3 > c1 > c2 > c2 > c3 > c1 > c3 > > As you can see the test for CompareStringEx() is broken, but we get a sane > answer with LCMapStringEx(). The LCMapStringEx() solution is elegant. I do see https://learn.microsoft.com/en-us/windows/win32/intl/handling-sorting-in-your-applications says, "If an application calls the function to create a sort key for a string containing an Arabic kashida, the function creates no sort key value." That's aggravating.
On Fri, Aug 11, 2023 at 7:29 AM Noah Misch <noah@leadboat.com> wrote:
The LCMapStringEx() solution is elegant. I do see
https://learn.microsoft.com/en-us/windows/win32/intl/handling-sorting-in-your-applications
says, "If an application calls the function to create a sort key for a string
containing an Arabic kashida, the function creates no sort key value." That's
aggravating.
I think the problem there is that it is just poorly explained.
Take for example the attached program that compares "normal" and "kashida" 'Raħīm' taken from [1], you'll get:
c1 = c2
c2 = c1
c2 = c1
meaning that "normal" and "kashida" are the same string. So, probably that phrase should read something like: "If an application calls the function to create a sort key for a string containing an Arabic kashida character, the function will ignore that character and no sort key value will be generated for it."
Regards,
Juan José Santamaría Flecha
Вложения
On Fri, Aug 11, 2023 at 11:48:18AM +0200, Juan José Santamaría Flecha wrote: > On Fri, Aug 11, 2023 at 7:29 AM Noah Misch <noah@leadboat.com> wrote: > > > > > The LCMapStringEx() solution is elegant. I do see > > > > https://learn.microsoft.com/en-us/windows/win32/intl/handling-sorting-in-your-applications > > says, "If an application calls the function to create a sort key for a > > string > > containing an Arabic kashida, the function creates no sort key value." > > That's > > aggravating. > > > > I think the problem there is that it is just poorly explained. > Take for example the attached program that compares "normal" and "kashida" > 'Raħīm' taken from [1], you'll get: > > c1 = c2 > c2 = c1 > > meaning that "normal" and "kashida" are the same string. So, probably that > phrase should read something like: "If an application calls the function to > create a sort key for a string containing an Arabic kashida character, the > function will ignore that character and no sort key value will be generated > for it." Good. That sounds fine. Thanks for clarifying.