优化一个基于pg_trgm和gin索引的Postgres相似性查询

Question

我定义了以下指数：

CREATE INDEX
    users_search_idx
ON
    auth_user
USING
    gin(
        username gin_trgm_ops,
        first_name gin_trgm_ops,
        last_name gin_trgm_ops
    );

我正在执行以下查询：

PREPARE user_search (TEXT, INT) AS
    SELECT
        username,
        email,
        first_name,
        last_name,
        ( -- would probably do per-field weightings here
            s_username + s_first_name + s_last_name
        ) rank
    FROM
        auth_user,
        similarity(username, $1) s_username,
        similarity(first_name, $1) s_first_name,
        similarity(last_name, $1) s_last_name
    WHERE
        username % $1 OR
        first_name % $1 OR
        last_name % $1
    ORDER BY
        rank DESC
    LIMIT $2;

auth_user表有620万行。

查询速度看起来非常依赖于similarity查询可能返回的结果数量。

通过使用set_limit增加相似度阈值可以提高速度，但是通过消除部分匹配减少了结果的实用性。

某些搜索需要200毫秒，而其他搜索需要大约10秒。

我们已经使用Elasticsearch对此功能进行了现有实现，对于任何查询都可以在＜200毫秒内返回，同时进行更复杂（更好）的排名。

我想知道是否有任何方法可以改进这一点，以获得更一致的性能？

据我所知，GIN索引（倒排索引）是由Elasticsearch使用的相同基本方法，因此我认为可能存在一些优化。

EXPLAIN ANALYZE EXECUTE user_search('mel', 20)显示：

Limit  (cost=54099.81..54099.86 rows=20 width=52) (actual time=10302.092..10302.104 rows=20 loops=1)
  ->  Sort  (cost=54099.81..54146.66 rows=18739 width=52) (actual time=10302.091..10302.095 rows=20 loops=1)
        Sort Key: (((s_username.s_username + s_first_name.s_first_name) + s_last_name.s_last_name)) DESC
        Sort Method: top-N heapsort  Memory: 26kB
        ->  Nested Loop  (cost=382.74..53601.17 rows=18739 width=52) (actual time=118.164..10293.765 rows=8380 loops=1)
              ->  Nested Loop  (cost=382.74..53132.69 rows=18739 width=56) (actual time=118.150..10262.804 rows=8380 loops=1)
                    ->  Nested Loop  (cost=382.74..52757.91 rows=18739 width=52) (actual time=118.142..10233.990 rows=8380 loops=1)
                          ->  Bitmap Heap Scan on auth_user  (cost=382.74..52383.13 rows=18739 width=48) (actual time=118.128..10186.816 rows=8380loops=1)"
                                Recheck Cond: (((username)::text % 'mel'::text) OR ((first_name)::text % 'mel'::text) OR ((last_name)::text %'mel'::text))"
                                Rows Removed by Index Recheck: 2434523
                                Heap Blocks: exact=49337 lossy=53104
                                ->  BitmapOr  (cost=382.74..382.74 rows=18757 width=0) (actual time=107.436..107.436 rows=0 loops=1)
                                      ->  Bitmap Index Scan on users_search_idx  (cost=0.00..122.89 rows=6252 width=0) (actual time=40.200..40.200rows=88908 loops=1)"
                                            Index Cond: ((username)::text % 'mel'::text)
                                      ->  Bitmap Index Scan on users_search_idx  (cost=0.00..122.89 rows=6252 width=0) (actual time=43.847..43.847rows=102028 loops=1)"
                                            Index Cond: ((first_name)::text % 'mel'::text)
                                      ->  Bitmap Index Scan on users_search_idx  (cost=0.00..122.89 rows=6252 width=0) (actual time=23.387..23.387rows=58740 loops=1)"
                                            Index Cond: ((last_name)::text % 'mel'::text)
                          ->  Function Scan on similarity s_username  (cost=0.00..0.01 rows=1 width=4) (actual time=0.004..0.004 rows=1 loops=8380)
                    ->  Function Scan on similarity s_first_name  (cost=0.00..0.01 rows=1 width=4) (actual time=0.002..0.002 rows=1 loops=8380)
              ->  Function Scan on similarity s_last_name  (cost=0.00..0.01 rows=1 width=4) (actual time=0.002..0.002 rows=1 loops=8380)
Execution time: 10302.559 ms

服务器是运行在Amazon RDS上的Postgres 9.6.1。

更新

1.

发布问题后不久，我找到了这些信息：https://www.postgresql.org/message-id/[e-mail]

所以我尝试了一下

-> SHOW work_mem;
4MB
-> SET work_mem='12MB';
-> EXECUTE user_search('mel', 20);
(results returned in ~1.5s)

这大大改善了原来的情况（之前大于10秒）！

虽然1.5秒仍然远慢于类似查询的ES，但我仍然希望听到对查询进行优化的任何建议。

2.

回应评论后，在看到这个问题(Postgresql GIN index slower than GIST for pg_trgm)后，我尝试使用GIST索引替换了GIN索引的设置。

尝试使用上面相同的搜索，它返回约3.5秒，使用默认的work_mem='4MB'。增加work_mem没有任何影响。

由此我得出结论，GIST索引更具有内存效率（没有像GIN一样遇到病理情况），但当GIN正常工作时，速度比GIN慢。这与文档中推荐GIN索引的描述一致。

3.

我仍然不明白为什么这么多时间花在了这里：

 ->  Bitmap Heap Scan on auth_user  (cost=382.74..52383.13 rows=18739 width=48) (actual time=118.128..10186.816 rows=8380loops=1)"
     Recheck Cond: (((username)::text % 'mel'::text) OR ((first_name)::text % 'mel'::text) OR ((last_name)::text %'mel'::text))"
     Rows Removed by Index Recheck: 2434523
     Heap Blocks: exact=49337 lossy=53104

我不明白为什么需要这个步骤或它在做什么。

在它下面有三个Bitmap Index Scan，分别对应每个 username % $1子句...然后将这些结果与BitmapOr步骤组合。所有这些部分都非常快。

但即使在我们没有用完工作内存的情况下，我们仍然花费近一秒钟在Bitmap Heap Scan中。

- Anentropic

---

你为什么要在FROM子句中进行相似性调用？除了在SELECT子句中使用它们，你似乎没有做任何其他事情。 需要注意的是，那里使用的总时间是“实际时间”*“循环次数”，尽管我不会过于信任“实际时间”的数据 - 它太小了，不能作为可靠的数字。 - Richard Huxton

FROM中的相似性是我从某个查询示例中得到的...这使其更易读。我尝试将其移入SELECT部分，但性能没有任何改变。这个查询的实际时间是10秒...对于一些搜索，我得到了与上面EXPLAIN报告完全相同的最坏情况。 - Anentropic

1.3秒并不是非常棒，但比10秒好多了。 - Anentropic

@Anentropic 是的，同时拥有两者可能会让规划器感到困惑——一个基于表达式的单一索引将消除 BitmapOr（在 Bitmap Heap Scan 下）的需要。 - pozs

“Bitmap Heap Scan” 是查询中迄今为止最慢的部分。 - Anentropic

Answer 1

我希望使用这种方法能获得更快的结果：much

1.

创建一个包含连接值的1列GiST索引：

CREATE INDEX users_search_idx ON auth_user
USING gist((username || ' ' || first_name || ' ' || last_name) gist_trgm_ops);

假设所有3个列都被定义为 NOT NULL（您没有指定）。否则，您需要完成更多工作。
为什么不使用 concat_ws() 进行简化？

• 将两个列合并并添加到一个新列中
• 在多个文本字段上进行模式匹配的更快查询
• 将两个列合并并添加到一个新列中

2.

使用适当的最近邻 查询，与上面的索引匹配:

SELECT username, email, first_name, last_name
     , similarity(username  , $1) AS s_username
     , similarity(first_name, $1) AS s_first_name
     , similarity(last_name , $1) AS s_last_name
     , row_number() OVER () AS rank  -- greatest similarity first
FROM   auth_user
WHERE     (username || ' ' || first_name || ' ' || last_name) %   $1  -- !!
ORDER  BY (username || ' ' || first_name || ' ' || last_name) <-> $1  -- !!
LIMIT  $2;

WHERE和ORDER BY中的表达式必须匹配索引表达式！

特别是像你所写的ORDER BY rank，对于从大量合格行中选择少量的LIMIT，性能总是很差，因为它无法直接使用索引：必须为每个合格的行计算rank背后的复杂表达式，然后对所有行进行排序，然后才能返回最佳匹配的少量结果。这比真正的最近邻查询要 昂贵得多，后者可以直接从索引中挑选出最佳结果，甚至不需要查看其余部分。

row_number()与空窗口定义只反映由同一SELECT中的ORDER BY产生的排序。

相关答案：

• 相似函数的最佳索引
• 使用pg_trgm在3亿个地址中搜索

---

至于您的项目3.，我添加了一个答案到您提到的问题，应该可以解释清楚：

• 对于pg_trgm，PostgreSQL GIN索引比GIST索引慢吗？

- Erwin Brandstetter

---

如果我理解正确的话，最重要的更改是 ORDER BY (username || ' ' || first_name || ' ' || last_name) <-> $1。我一直希望稍后调整我的 rank 值以提高用户名匹配度，例如 ((s_username * 2) + s_first_name + s_last_name) rank，但似乎在优化版本中这是不可能的。 - Anentropic

优化的重点在于查询可以直接从索引中选择最佳匹配，这比检索所有候选项、计算每个候选项的排名、按此排名对其进行排序然后丢弃除前几个以外的所有内容要快得多 - 而 LIMIT 明显小于符合条件的总行数。 - Erwin Brandstetter