Abbreviated keys glibc issue

PostgreSQL 9.5 Abbreviated Keys Regression

PostgreSQL 9.5.0 shipped with a feature which sped up sorts and indexing for character/string columns (text and varchar(n)) by using an algorithm called "abbreviated keys". This was quite a compelling feature because it sped up sorts and index builds for some users as much as 20X.

As of 9.5.2, the project has had to disable this feature for text/varchar(n) index builds for any non-C locale because it produces corrupt indexes when certain C standard libraries are in use that have bugs in standard collation functions. Users may need to REINDEX some indexes.

What's the bug?

Users whose text data uses a collation other than "C" locale found that, in some cases, indexes built with the abbreviated key feature would fail to find existing rows. An investigation in pgsql-bugs identified the problem.

Locale support refers to an application respecting cultural preferences regarding alphabets, sorting, number formatting, etc. PostgreSQL uses the standard ISO C and POSIX locale facilities provided by the server operating system. A locale's "collation" controls how types like text are collated during sorting. In non-C locales, the abbreviated keys feature uses the strxfrm() standard library function to create a sortable binary key (only a prefix of this binary key is actually used during sorting). After the bug report, developers discovered that many versions of glibc (the C standard library in widespread use on Linux systems) have buggy implementations of strcoll() that, at least in some locales, can produce string comparison results that do not match strxfrm(), resulting in indexes which give wrong answers (strcoll() should still give self-consistent answers, though, which is what really matters). This behavior is contrary to ISO C90 and POSIX standards, which require that a strxfrm() + strcmp() comparison give the same answer as a simple strcoll().

This bug certainly applies to versions of glibc before 2.22, and may apply to other versions as well. Since older versions of glibc are far more widespread than the newer versions, it is not safe to depend on correct behavior from collation functions. See the Red Hat bug for more discussion of this.

This issue definitely does not affect the "C" locale because it does not use either of those functions (the "C" locale does still support abbreviated keys, and will continue to do so in PostgreSQL 9.5.2). It probably does not affect many locales and most standard library implementations (there is no evidence of issues any C standard library implementation that is not some particular version of glibc, for example). However, as there is no way to do exhaustive testing on all locales on all platforms, it is currently considered generally unsafe in any non-C locale with PostgreSQL 9.5.1 or 9.5.0. On glibc systems where problems arise, the locale "de_DE.UTF-8" appears to be particularly badly affected.

What do I have to do?

Reindexing

After updating your server to 9.5.2 (or later), you will want to REINDEX any possibly affected index. Since REINDEX is a blocking operation, however, you may wish to instead do this as a two-step concurrent operation, for example:

 CREATE INDEX CONCURRENTLY table1_charcol2_a ON table1(charcol2);
 DROP INDEX CONCURRENTLY table_charcol2;

How critical doing this reindexing is depends on whether you believe you are likely to experience the issue. Note that you should connect to every database in the installation/cluster, to ensure that nothing is missed.

SQL query to show potentially affected indexes

You must determine which indexes might be affected and must therefore be reindexed. Since PostgreSQL allows you to set collations per column, it's possible that the issue could occur even if the database collation is "C". A query to search all potentially affected indexes, including those potentially affected due to using the default collation (the common case) is as follows:

 SELECT pg_namespace.nspname AS schema_name,
    reltable.relname AS table_name,
    relindex.relname AS index_name,
    t.typname AS type_name,
    op.opcname AS operator_class_name,
    CASE WHEN collname = 'default' THEN
      (SELECT datcollate FROM pg_database WHERE datname = current_database())
    ELSE collname END AS collation_name
  FROM pg_index
    JOIN pg_class as reltable ON indrelid = reltable.oid
    JOIN pg_class as relindex ON indexrelid = relindex.oid
    JOIN pg_collation ON indcollation[0] = pg_collation.oid
    JOIN pg_namespace ON reltable.relnamespace = pg_namespace.oid
    JOIN pg_opclass op ON indclass[0] = op.oid
    JOIN pg_type t ON (op.opcintype = t.oid OR op.opckeytype = t.oid)
  WHERE collcollate NOT IN ('C', 'POSIX')
  AND op.opcname IN ('text_ops', 'varchar_ops')
  ORDER BY schema_name, table_name, index_name;

The query will report indexes that are in the "C" locale if that happens to be the default for the database (these indexes do not require a REINDEX). Note that this query only shows indexes where the "leading" pg_index column is affected, since that's the only column that CREATE INDEX could have used abbreviated keys for.

Using amcheck

The third party amcheck module will detect which indexes are affected with a high degree of reliability:

https://github.com/petergeoghegan/amcheck

This can be an effective way to be far more discriminating about which indexes are reindexed, potentially avoiding significant disruption to busy production systems.

What kinds of indexes may be affected?

• Indexes created with PostgreSQL 9.5.0 or 9.5.1 only.
• Where columns of text, varchar(n), or domains of those types were indexed (default operator classes only)
• Where the first/leading column in the index used those types, and the collation used by the index is not "C"/POSIX

Typically, this means that the majority of indexes on text/varchar(n) with PostgreSQL 9.5 systems are theoretically at risk.

What is not affected?

Definitely not affected by this issue:

• Version 9.4 and earlier, since it's a 9.5 feature.
• PostgreSQL 9.5 for Windows (because it never had the feature enabled).
• Any index using an index access method that is not the default access method, B-Tree.
• Columns that use the "C" collation (also known as the POSIX collation). This includes cases where the "C" collation is the database default without that being overridden for the index, cases where the "C" collation was specified in the original CREATE INDEX statement, and cases where the underlying column was specified (e.g. in CREATE TABLE) to use a per-column collation that happened to be the "C" collation.
• Non-default B-Tree operator classes for text/varchar. This includes text_pattern_ops and varchar_pattern_ops.
• Indexes created on columns of type numeric. In PostgreSQL 9.5, the numeric type was enhanced to use a similar abbreviated keys optimization, but that was implemented without the use of any standard collation function.
• Collatable types that are not either text or varchar(n). This includes char(n), and contrib/citext. It also includes composite types that were defined with text (using CREATE TYPE). "Built-in" composite types like arrays of text and jsonb are also not affected.

Additionally, the following are unlikely to be affected, but are not proven safe, so you need to judge the amount of risk you're willing to tolerate in deciding whether to REINDEX or not:

• Systems using glibc 2.22 and later
• Systems using C libraries other than glibc

Columns in the en_US collation can be affected in rare cases. For some reason, these cases involve code points from the Arabic alphabet in all observed instances.

What's my locale?

You can check your database collation and locale with the \l shortcut from psql, for example:

   postgres=# \l+
                      List of databases
     Name     |  Owner   | Encoding | Collate | Ctype |  Size   | 
 -------------+----------+----------+---------+-------+---------+-
  libdata     | libdata  | UTF8     | pt_BR   | pt_BR | 18 MB   | 
  postgres    | postgres | UTF8     | C       | C     | 6976 kB | 
  subscribers | postgres | UTF8     | C       | C     | 7169 kB | 
 (5 rows)

For this example, the "subscribers" database could safely use abbreviated key indexing, whereas the "libdata" database could not.

You can also get this information by querying pg_database:

 SELECT datname, datacollate FROM pg_database;

What's my glibc version?

Typically, it is possible to determine which glibc version is in use on a Linux system by entering the following at the command line:

 $ ldd --version

When will I get my faster index builds back?

Nobody knows at this point. It is a matter of reliably ensuring consistent behavior between strxfrm() and strcoll(). It's generally difficult to prove the absence of such problems, and a blanket disabling of abbreviated keys for text seemed best in light of the glibc issue.

If you have ideas to offer, please join the pgsql-hackers thread discussing the issue.