1. 引言

我们经常会在字符串上创建索引，也会字符串上做LIKE查询，但是大家有没有遇到过字符串的LIKE查询不走索引的问题，这是为何？

2. 字符串的可比较性

我们在以前的文章中提到过，PostgreSQL默认是 UTF-8编码，单个字符预留了4个字节的存储空间，那么就有个问题，编码后的字符应该怎么比较大小？因为用户看到的是字符而不是字节，比如汉字“啊、波、次、得、鹅、佛、哥”这些汉字应该怎么排序？

在PostgreSQL中，COLLATE用来表示该库的排序规则，我们通过\l即可查看出编码方式(Encoding)和排序方式(Collate)。

字符的排序方式不只是数据库需要考虑的问题，而是所有软件都需要考虑的问题，只是我们通常都忽略了。操作系统本身也有COLLATE的设置，这个设置直接影响了某些应用程序的排序行为，举个例子，我们看下Linux中的sort命令在不同语言环境下的行为：

可见当LANG=en_US.UTF-8时的排序结果是“佛、哥、啊、得、次、波、鹅”，很显然，这个排序对于用户来说是没有任何意义的。但是这个结果是按照什么排序算法得到的？我们来看一下这些汉字的编码：

由此可见，字符排序顺序和字符的编码值完全契合，这不是巧合，而是sort命令就是这么实现的。当环境是en_US.UTF-8时，sort命令按照字符的编码值做排序，编码小的字符自然排到了前面。

而当环境是zh_CN.UTF-8时，结果如下所示：

由此可知，当使用zh_CN.UTF-8时是按照汉字拼音排序的，这才符合我们汉字排序的规则。

同样在PostgreSQL上排序也有类似的问题，PostgreSQL库的默认COLLATE是en_US.UTF-8，因此在PostgreSQL下上述汉字的排序也是非预期行为，如下：

那么怎么才能排序符合我们预期？首先我们根据pg_collation查看下当前库支持的排序类型，这些类型可以在编译时指定，查询结果如下：

可见，当前库支持中文排序。实际上我们可以在建库、建表、查询的任何步骤中指定排序规则来实现汉字排序：

• 查询时带上COLLATE “zh_CN” 表示按照中文排序；
  
• 建表时指定字符串列按照中文排序；
  
• 建库时指定库的按照中文排序；
  
  在指定了Collate为zh_CN的库上创建表，按照汉字排序，如下：
  
  综上：我们可以知道，如果想要实现汉字的排序，我们至少要在上述三处的某一处通过设置COLLATE为zh_CN来指定排序策略来实现。

3. 特殊的COLLATE “C”

在PostgreSQL的诸多排序策略中， COLLATE “C” 是一个极其特殊的存在，也是默认场景下字符串查询下LIKE查询走btree索引的唯一排序方式，COLLATE "C"在比较时按字节比较，因此比其他排序方式都要快，类似的实现可以参考varstr_cmp，函数的实现，代码如下：

int
varstr_cmp(const char *arg1, int len1, const char *arg2, int len2, Oid collid)
{
    int     result;
    check_collation_set(collid);

    /* 注释1
     * Unfortunately, there is no strncoll(), so in the non-C locale case we
     * have to do some memory copying.  This turns out to be significantly
     * slower, so we optimize the case where LC_COLLATE is C.  We also try to
     * optimize relatively-short strings by avoiding palloc/pfree overhead.
     */
    if (lc_collate_is_c(collid))
    {
        result = memcmp(arg1, arg2, Min(len1, len2));
        if ((result == 0) && (len1 != len2))
            result = (len1 < len2) ? -1 : 1;
    }
    else
    {
        pg_locale_t mylocale;

        mylocale = pg_newlocale_from_collation(collid);

        /* 注释2
         * memcmp() can't tell us which of two unequal strings sorts first,
         * but it's a cheap way to tell if they're equal.  Testing shows that
         * memcmp() followed by strcoll() is only trivially slower than
         * strcoll() by itself, so we don't lose much if this doesn't work out
         * very often, and if it does - for example, because there are many
         * equal strings in the input - then we win big by avoiding expensive
         * collation-aware comparisons.
         */
        if (len1 == len2 && memcmp(arg1, arg2, len1) == 0)
            return 0;

        result = pg_strncoll(arg1, len1, arg2, len2, mylocale);

        /* Break tie if necessary. */
        if (result == 0 && pg_locale_deterministic(mylocale))
        {
            result = memcmp(arg1, arg2, Min(len1, len2));
            if ((result == 0) && (len1 != len2))
                result = (len1 < len2) ? -1 : 1;
        }
    }
    return result;
}

根据这个代码可以看出，COLLATE "C"的排序做了优化，是调用库函数memcmp来实现的；而对于非COLLATE "C"的场景，最终调用strcoll库函数来比较。

这段代码中有两大块注释，我们大概翻译一下：

注释1：遗憾的是，目前并无 strncoll() 函数可用，因此在非 C 本地化环境（non-C locale）下，我们不得不执行一些内存拷贝操作。这会导致性能显著下降，故而我们针对 LC_COLLATE 为 C 的场景做了优化。同时，为规避 palloc/pfree 内存分配与释放的开销，我们也尝试对相对短的字符串进行了优化。

这里提到了strcoll函数，strcoll是根据本地的环境比较两字符串的先后顺序，与strcmp库函数对比如下：

注释2：memcmp() 函数虽然无法判断两个不相等的字符串谁在前面，但在判断是否相等时又是很快的。测试表明，先调用 memcmp() 再调用 strcoll() 的方式，仅比单独调用 strcoll() 略慢一点点；因此，即便这种方式不常生效，我们的性能损失也微乎其微；而一旦生效 —— 例如输入中存在大量相等的字符串时 —— 我们就能通过规避开销高昂的排序规则感知型比较（collation-aware comparisons），获得极大的性能收益。

这两段注释都给我们说了一个事——非COLLATE "C"的性能很慢，这个慢主要体现在内存拷贝上，可见源码中的pg_strncoll_libc函数。我们用order by的排序测试如下：

可见，"C"排序策略比"en_US"排序策略快了10s，性能提升了40%之多，这也说明当我们能确保字符串仅包含ASIIC时，在排序加上COLLATE "C"是个不错的选择，但这个的前提是必须知道自己在干什么。

4. LIKE为什么不走索引

根据上面我们可以看出来，对于同一个字符串，在不同的COLLATE下的排序方式并不相同，即存储顺序≠逻辑排序。而PostgreSQL中的btree索引需要严格的排序和查找，因此在很多COLLATE下字符串的LIKE都无法走索引。

但特殊在于COLLATE “C”，由上可知，COLLATE "C"比较时直接用memcmp是字节级别的比较，和COLLATE无关，因此当索引是COLLATE "C"时LIKE可以走索引。

关于这一点我们可以查看生成LIKE执行计划生成时是否索引的实现函数match_pattern_prefix的关键代码：

这里有段注释，翻译过来大概就是：由于我们需要一个范围约束，因此只有当索引不区分排序规则（collation-insensitive）或采用 “C” 排序规则时，该约束才能稳定生效。请注意，此处我们关注的是索引的排序规则，而非表达式的排序规则 —— 该测试并不依赖于 LIKE / 正则表达式操作符的排序规则。
同时还有个collation_aware用来表示是否需要考虑排序规则，这个标记的设置如下：

可见，只有TEXT_PATTERN_BTREE_FAM_OID、TEXT_SPGIST_FAM_OID才不需要考虑排序规则，对于其他所有场景都需要考虑，至此我们也在代码层面找到了LIKE查找不走索引的原因。

5. 如何让LIKE走索引

根据上面代码看LIKE不走索引的原因我们可以反推出如何让LIKE走索引，根据if的两个条件，可以得到如下是三个方案：

1. 设置COLLATE "C"排序；

   create index on t1(b COLLATE "C");
   

2. 设置索引PATTER_OPS索引；
PostgreSQL在创建索引时可以指定text_pattern_ops、varchar_pattern_ops、bpchar_pattern_ops等操作符来让text、varchar、bpchar等类型在不指定排序规则时也能走索引；
sql create index on t1(b text_pattern_ops);

3. 使用SPGIST索引；

但我们要知道，这三种解决方法中COLLATE "C"的效率最高，但我们还是需要再次强调，在使用COLLATE "C"时，我们要知道我们是在干什么。

6. 总结

在字符串列上创建索引看似是一个再普通不过的操作，但实际上隐藏着很多“坑”，而这些“坑”的始作俑者就是字符编码，而这又是一个无奈之举，数据库想要支持多国语言，字符排序是个绕不过的坎。而PostgreSQL把这个决策权交给了使用者。

同时我们要特别注意到，在诸多排序策略中，COLLATE "C"的效率是最高的，其他排序策略都需要拷贝内存，带来性能开销，我们在开发/运维中要特别注意这一点。

最后我们也可以看到，面对LIKE不走索引的问题，我们可以有三种不同的手段绕开这一“限制”，让LIKE也能走索引扫描。

---