4 ms·

Florian Weimer's reply is also interesting: "Why do you think that? I don't see this documented anywhere, and I doubt it is something many readers of the C st

Florian Weimer's reply is also interesting: "Why do you think that? I don't see this documented anywhere, and I doubt it is something many readers of the C standard, the man page, or the glibc manual would expect. The manual suggests to store the strxfrm output and use it for sorting. I expect that some applications put it into on-disk database indexes as a result. This will lead to subtle breakage on glibc updates. (The larger problem is that there are definitely databases out there which use B-tree indexes in locale collation order, which break in even more subtle ways if we make minor changes to the collation order.)"

ajross 10y ago
Which manual suggests storing the output of strxfrm? The glibc man page doesn't seem to. I don't know that this is resolvable. The documented behavior of strxfrm() is just about its output properties. Improvements to the transformation algorithm would be expected to be made, if it's improvable. If a database needs this to be static over time it needs to pick a particular transformation algorithm and specify it exactly, not just rely on whatever the C library happens to provide. I mean, not only are PostgreSQL locale-sorted-indexes not portable across glibc releases. They aren't portable across any other system change either. No moving between distros or doing distro upgrades, etc... Those are all misfeatures probably worth fixing.
- anarazel 10y ago
  > I mean, not only are PostgreSQL locale-sorted-indexes not portable across glibc releases. They aren't portable across any other system change either. No moving between distros or doing distro upgrades, etc... Those are all misfeatures probably worth fixing. Hence ICU support, which allows to address these (because collations are properly versioned).
- pgaddict 10y ago
  This somewhat mixes two issues, really. Firstly, there are issues with glibc versioning, when the collation rules change even without proper version bump. I don't have a link to details at hand, but I've heard a number of complaints about it over the years from various PostgreSQL hackers, including Peter Geoghegan who did a lot of sort optimizations in 9.5 & 9.6. I'm sure there's something deep in the PostgreSQL mailing list archives. You'll have to dig deep, because we learned the lesson years ago. Regarding strxfrm(), PostgreSQL certainly does not store the results anywhere - it's only used during the actual sort, e.g. during CREATE INDEX or to help with ORDER BY in a query, and then thrown away. So either I'm forgetting something, or Robert mixed this up in the blog post. There's however an issue with strxfrm() disagreeing with strcoll(), which is a major problem, of course, because we build and index using strxfrm() and then fail to find the values in it using strcoll(). For more details, including links to pgsql-bugs and RH bugtracker, see https://wiki.postgresql.org/wiki/Abbreviated_keys_glibc_issue https://wiki.postgresql.org/wiki/Abbreviated_keys_glibc_issu... ICU seems not to have these issues, because it has better and more carefully maintained versioning scheme. Perhaps we'll still get broken indexes after an ICU upgrade, but at least we'll know about it.
- petergeoghegan 10y ago
  PostgreSQL never stored strxfrm() output in indexes, but did at one time use it to build indexes (that is, strxfrm() was used to build values when sorting). However, it would be nice to be able to store strxfrm() output on disk, in indexes, which as you say leaves the implementation sensitive to changes in the transformation algorithm, and not just the underlying behavior defined by a collation. Fortunately, it is possible to do this safely with ICU, which explicitly decouples implementation issues from behavioral issues. Maybe this will happen at some point in the future. For now, abbreviated keys are only used for sorting to build an index, and not in any subsequent index scan. If you want much faster text sorting back, using "abbreviated keys", you can use ICU collations in Postgres 10. With the C standard library, strxfrm() was disabled when it was found to be buggy within glibc [1]. [1] https://wiki.postgresql.org/wiki/Abbreviated_keys_glibc_issue https://wiki.postgresql.org/wiki/Abbreviated_keys_glibc_issu...
- petergeoghegan 10y ago
  BTW, the new amcheck tool, available in Postgres 10, lets you validate that an index is consistent with its designated sort order (B-Tree operator class). At least you now have some way of detecting the kind of inconsistency you describe. I wrote amcheck, and maintain a version targeting earlier releases of PostgreSQL on Github: https://github.com/petergeoghegan/amcheck https://github.com/petergeoghegan/amcheck

ajross 10y ago

Which manual suggests storing the output of strxfrm? The glibc man page doesn't seem to. I don't know that this is resolvable. The documented behavior of strxfrm() is just about its output properties. Improvements to the transformation algorithm would be expected to be made, if it's improvable. If a database needs this to be static over time it needs to pick a particular transformation algorithm and specify it exactly, not just rely on whatever the C library happens to provide. I mean, not only are PostgreSQL locale-sorted-indexes not portable across glibc releases. They aren't portable across any other system change either. No moving between distros or doing distro upgrades, etc... Those are all misfeatures probably worth fixing.

anarazel 10y ago
> I mean, not only are PostgreSQL locale-sorted-indexes not portable across glibc releases. They aren't portable across any other system change either. No moving between distros or doing distro upgrades, etc... Those are all misfeatures probably worth fixing. Hence ICU support, which allows to address these (because collations are properly versioned).
pgaddict 10y ago
This somewhat mixes two issues, really. Firstly, there are issues with glibc versioning, when the collation rules change even without proper version bump. I don't have a link to details at hand, but I've heard a number of complaints about it over the years from various PostgreSQL hackers, including Peter Geoghegan who did a lot of sort optimizations in 9.5 & 9.6. I'm sure there's something deep in the PostgreSQL mailing list archives. You'll have to dig deep, because we learned the lesson years ago. Regarding strxfrm(), PostgreSQL certainly does not store the results anywhere - it's only used during the actual sort, e.g. during CREATE INDEX or to help with ORDER BY in a query, and then thrown away. So either I'm forgetting something, or Robert mixed this up in the blog post. There's however an issue with strxfrm() disagreeing with strcoll(), which is a major problem, of course, because we build and index using strxfrm() and then fail to find the values in it using strcoll(). For more details, including links to pgsql-bugs and RH bugtracker, see https://wiki.postgresql.org/wiki/Abbreviated_keys_glibc_issue https://wiki.postgresql.org/wiki/Abbreviated_keys_glibc_issu... ICU seems not to have these issues, because it has better and more carefully maintained versioning scheme. Perhaps we'll still get broken indexes after an ICU upgrade, but at least we'll know about it.
petergeoghegan 10y ago
PostgreSQL never stored strxfrm() output in indexes, but did at one time use it to build indexes (that is, strxfrm() was used to build values when sorting). However, it would be nice to be able to store strxfrm() output on disk, in indexes, which as you say leaves the implementation sensitive to changes in the transformation algorithm, and not just the underlying behavior defined by a collation. Fortunately, it is possible to do this safely with ICU, which explicitly decouples implementation issues from behavioral issues. Maybe this will happen at some point in the future. For now, abbreviated keys are only used for sorting to build an index, and not in any subsequent index scan. If you want much faster text sorting back, using "abbreviated keys", you can use ICU collations in Postgres 10. With the C standard library, strxfrm() was disabled when it was found to be buggy within glibc [1]. [1] https://wiki.postgresql.org/wiki/Abbreviated_keys_glibc_issue https://wiki.postgresql.org/wiki/Abbreviated_keys_glibc_issu...
petergeoghegan 10y ago
BTW, the new amcheck tool, available in Postgres 10, lets you validate that an index is consistent with its designated sort order (B-Tree operator class). At least you now have some way of detecting the kind of inconsistency you describe. I wrote amcheck, and maintain a version targeting earlier releases of PostgreSQL on Github: https://github.com/petergeoghegan/amcheck https://github.com/petergeoghegan/amcheck