PostgreSQL アンチパターン: 名前による検索の反復的な改良、つまり「行ったり来たりの最適化」の物語

全国の営業所の数千人のマネージャーが記録 私たちのCRMシステム 毎日数万件のコンタクト - 潜在的または既存の顧客とのコミュニケーションの事実。 そのためには、まずクライアントを、できれば迅速に見つける必要があります。 そして、これは名前によって最も頻繁に起こります。

したがって、最も負荷の高いデータベースの XNUMX つである私たちのデータベースで「重い」クエリを再度分析することは驚くべきことではありません。 VLSI 法人アカウント、「トップにある」を見つけました。 名前による「クイック」検索のリクエスト 組織カード用。

さらに、さらなる調査により、興味深い例が明らかになりました 最初に最適化が行われ、次にパフォーマンスが低下します。 リクエストは複数のチームによって順次改良され、各チームは最善の意図だけを持って行動しました。

0：ユーザーは何を望んでいたのか？

[KDPV 故に]

ユーザーが名前による「クイック」検索について話すとき、通常は何を意味しますか? 次のような部分文字列を「正直に」検索すると判明することはほとんどありません。 ... LIKE '%роза%' - なぜなら、その結果には次のものが含まれるだけではありません 'Розалия' и 'Магазин Роза'しかし 'Гроза' とさえ 'Дом Деда Мороза'.

ユーザーは、日常レベルで、あなたが自分に提供してくれるものと想定しています。 単語の先頭で検索する タイトルに含めて、より関連性の高いものにします から始まる 入りました。 そしてあなたはそれをするでしょう ほぼ瞬時に - インターリニア入力の場合。

1: タスクを制限する

さらに言えば、人が具体的に入るわけではありません。 'роз магаз', そのため、各単語を接頭辞で検索する必要があります。 いいえ、ユーザーにとっては、前の単語を意図的に「過少指定」するよりも、最後の単語の簡単なヒントに応答する方がはるかに簡単です。検索エンジンがこれをどのように処理するかを見てください。

一般的に、 正しく 問題の要件を定式化することは、解決策の半分以上を占めます。 場合によっては慎重なユースケース分析 結果に大きな影響を与える可能性があります.

抽象開発者は何をしますか?

1.0: 外部検索エンジン

ああ、検索は難しい、何もしたくない、DevOps に任せましょう! Sphinx、ElasticSearch などの検索エンジンをデータベースの外部に導入させます。

同期と変更の速度の点で労働集約的ではありますが、実用的なオプションです。 しかし、私たちの場合はそうではありません。検索は各クライアントのアカウントデータの枠組み内でのみ実行されるためです。 そして、データはかなり高い変動性を持っています - そしてマネージャーがカードを入力した場合 'Магазин Роза', その後、5〜10秒後に、彼はそこに自分の電子メールを指定するのを忘れたことをすでに思い出し、それを見つけて修正したいと考えている可能性があります。

したがって、しましょう 「データベースを直接」検索する。 幸いなことに、PostgreSQL ではこれが可能であり、XNUMX つのオプションだけではなく、それらを見ていきます。

1.1: 「正直な」部分文字列

私たちは「部分文字列」という言葉に固執しています。 しかし、部分文字列による (さらには正規表現による) インデックス検索については、優れた機能があります。 モジュールpg_trgm！ その場合にのみ、正しく並べ替える必要があります。

モデルを単純化するために次のプレートを取り上げてみましょう。

CREATE TABLE firms(
  id
    serial
      PRIMARY KEY
, name
    text
);

実際の組織の 7.8 万件のレコードをそこにアップロードし、インデックスを付けます。

CREATE EXTENSION pg_trgm;
CREATE INDEX ON firms USING gin(lower(name) gin_trgm_ops);

線形検索のために最初の 10 レコードを探してみましょう。

SELECT
  *
FROM
  firms
WHERE
  lower(name) ~ ('(^|s)' || 'роза')
ORDER BY
  lower(name) ~ ('^' || 'роза') DESC -- сначала "начинающиеся на"
, lower(name) -- остальное по алфавиту
LIMIT 10;

[explain.tensor.ruを見てください]

まあ、そんな... 26ミリ秒、31MB 読み取りデータと 1.7K を超えるフィルタリングされたレコード - 10 件の検索済みレコード。 諸経費が高すぎるのですが、もっと効率的な方法はないのでしょうか?

1.2: テキストで検索しますか? FTSだよ！

実際、PostgreSQL は非常に強力な機能を提供します。 全文検索エンジン (全文検索)、プレフィックス検索の機能を含む。 優れたオプションであり、拡張機能をインストールする必要さえありません。 やってみよう：

CREATE INDEX ON firms USING gin(to_tsvector('simple'::regconfig, lower(name)));

SELECT
  *
FROM
  firms
WHERE
  to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*')
ORDER BY
  lower(name) ~ ('^' || 'роза') DESC
, lower(name)
LIMIT 10;

[explain.tensor.ruを見てください]

ここではクエリ実行の並列化が少し役に立ち、時間を半分に短縮できました。 11ミリ秒。 そして、読む必要があったのは 1.5 分の XNUMX でした - 合計 20MB。 ただし、ここでは、少ないほど良いのです。読み取るボリュームが大きいほど、キャッシュ ミスが発生する可能性が高くなり、ディスクから読み取られるデータの余分なページがリクエストに対する潜在的な「ブレーキ」になるためです。

1.3: まだ気に入っていますか?

前のお願いは誰にとっても良いことですが、XNUMX日にXNUMX万回引いた場合にのみ叶います 2TB データを読み取ります。 最良の場合はメモリからですが、運が悪ければディスクからです。 そこで、さらに小さくしてみます。

ユーザーが見たいものを思い出そう まず「…から始まるもの」。 これは最も純粋な形です プレフィックス検索 経由 text_pattern_ops！ そして、探している最大 10 レコードが「足りない」場合にのみ、FTS 検索を使用してそれらの読み取りを完了する必要があります。

CREATE INDEX ON firms(lower(name) text_pattern_ops);

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
LIMIT 10;

[explain.tensor.ruを見てください]

優れたパフォーマンス - 合計 0.05msと100KB強 読む！ 私達だけが忘れてた 名前順ユーザーが結果に迷わないように:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
ORDER BY
  lower(name)
LIMIT 10;

[explain.tensor.ruを見てください]

ああ、何かがもうそれほど美しくありません - インデックスがあるようですが、並べ替えはそれを通り過ぎています... もちろん、これはすでに前のオプションよりも何倍も効果的ですが...

1.4: 「やすりで仕上げる」

ただし、範囲で検索し、通常どおりソートを使用できるインデックスがあります。 通常のBツリー!

CREATE INDEX ON firms(lower(name));

それに対するリクエストのみを「手動で収集」する必要があります。

SELECT
  *
FROM
  firms
WHERE
  lower(name) >= 'роза' AND
  lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых - chr(255)
ORDER BY
   lower(name)
LIMIT 10;

[explain.tensor.ruを見てください]

素晴らしい - 仕分けは機能し、リソースの消費は「微視的」なままです。 「純粋な」FTS よりも数千倍効果的！ 残っているのは、それを XNUMX つのリクエストにまとめるだけです。

(
  SELECT
    *
  FROM
    firms
  WHERE
    lower(name) >= 'роза' AND
    lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых кодировок - chr(255)
  ORDER BY
     lower(name)
  LIMIT 10
)
UNION ALL
(
  SELECT
    *
  FROM
    firms
  WHERE
    to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*') AND
    lower(name) NOT LIKE ('роза' || '%') -- "начинающиеся на" мы уже нашли выше
  ORDER BY
    lower(name) ~ ('^' || 'роза') DESC -- используем ту же сортировку, чтобы НЕ пойти по btree-индексу
  , lower(name)
  LIMIT 10
)
LIMIT 10;

XNUMX 番目のサブクエリが実行されることに注意してください 最初の結果が予想よりも少なかった場合のみ 最後の LIMIT 行数。 私はクエリ最適化のこの方法について話しています すでに前に書いた.

はい、現在では btree と gin の両方がテーブルにありますが、統計的には次のことが判明しました。 10 番目のブロックの実行に到達するリクエストは XNUMX% 未満です。 つまり、このような一般的なタスクの制限を事前に知っておくことで、サーバー リソースの総消費量をほぼ XNUMX 分の XNUMX に削減することができました。

1.5*: ファイルなしでも可能

上 LIKE 間違った並べ替えを使用することは防止されました。 ただし、USING 演算子を指定することで「正しいパスに設定」できます。

デフォルトでは次のように想定されます ASC。 さらに、句で特定の並べ替え演算子の名前を指定できます。 USING。 ソート演算子は、B ツリー演算子の一部のファミリーの「より小さい」または「より大きい」メンバーである必要があります。 ASC 通常同等 USING < и DESC 通常同等 USING >.

私たちの場合、「少ない」とは ~<~:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
ORDER BY
  lower(name) USING ~<~
LIMIT 10;

[explain.tensor.ruを見てください]

2: リクエストがどのように悪化するか

さて、私たちは「煮詰める」というリクエストを XNUMX か月または XNUMX 年間放っておくと、毎日のメモリの合計「ポンピング」の指標が表示され、それが再び「トップ」にあることに驚きました。バッファ共有ヒット）で 5.5TB - つまり、当初よりもさらに増加し​​ました。

いいえ、もちろん、私たちのビジネスは成長し、仕事量は増加しましたが、同じ量ではありません。 これは、ここに何か怪しい点があることを意味します。それを理解しましょう。

2.1: ページングの誕生

ある時点で、別の開発チームは、素早い添え字検索からレジストリに「ジャンプ」して、同じだが拡張された結果を表示できるようにしたいと考えていました。 ページ ナビゲーションのないレジストリとは何ですか? めちゃくちゃにしましょう！

( ... LIMIT <N> + 10)
UNION ALL
( ... LIMIT <N> + 10)
LIMIT 10 OFFSET <N>;

開発者にとってストレスなく、「ページごと」に読み込まれて検索結果のレジストリを表示できるようになりました。

もちろん実際には、 後続のデータ ページごとに、さらに多くのデータが読み取られます (前回のすべてを破棄し、必要な「尾部」を加えたもの) - つまり、これは明らかなアンチパターンです。 ただし、次の反復時にインターフェイスに保存されているキーから検索を開始する方が正確ですが、それについてはまた別の機会に説明します。

2.2: エキゾチックなものが欲しい

ある時点で開発者が望んでいたのは、 得られたサンプルをデータで多様化する 前のリクエスト全体が CTE に送信された別のテーブルから:

WITH q AS (
  ...
  LIMIT <N> + 10
)
SELECT
  *
, (SELECT ...) sub_query -- какой-то запрос к связанной таблице
FROM
  q
LIMIT 10 OFFSET <N>;

それでも、サブクエリは返された 10 レコードに対してのみ評価されるため、悪くはありません。

2.3: DISTINCT は無意味で無慈悲である

2 番目のサブクエリからのそのような進化の過程のどこかで 失った NOT LIKE 条件。 この後は明らかです UNION ALL 戻り始めた いくつかのエントリが XNUMX 回あります - 最初に行の先頭で見つかり、次に再び - この行の最初の単語の先頭で見つかります。 制限内では、2 番目のサブクエリのすべてのレコードが最初のサブクエリのレコードと一致する可能性があります。

開発者は原因を探す代わりに何をしますか?... 疑問はありません。

• サイズをXNUMX倍にする オリジナルサンプル
• DISTINCT を適用する各行のインスタンスを XNUMX つだけ取得するには

WITH q AS (
  ( ... LIMIT <2 * N> + 10)
  UNION ALL
  ( ... LIMIT <2 * N> + 10)
  LIMIT <2 * N> + 10
)
SELECT DISTINCT
  *
, (SELECT ...) sub_query
FROM
  q
LIMIT 10 OFFSET <N>;

つまり、結果が最終的にはまったく同じであることは明らかですが、2 番目の CTE サブクエリに「飛ぶ」可能性がはるかに高くなっており、これがなくても、 明らかに読みやすくなりました.

しかし、これは最も悲しいことではありません。 開発者から選択を求められたため、 DISTINCT 特定のフィールドではなく、すべてのフィールドを一度に レコードを追加すると、サブクエリの結果である sub_query フィールドが自動的にそこに組み込まれました。 さて、実行するには DISTINCT、データベースはすでに実行されている必要がありました 10 個のサブクエリではなく、すべて <2 * N> + 10!

2.4: 何よりも協力!

したがって、開発者は生き続けました。ユーザーは明らかに、後続の各「ページ」の受信が慢性的に遅くなり、レジストリを大幅な N 値に「調整」するのに十分な忍耐力を持っていなかったので、開発者は気にしませんでした。

別の部門の開発者がやって来て、そのような便利な方法を使いたがるまでは 反復検索用 - つまり、あるサンプルから部分を取り出し、追加の条件でフィルタリングし、結果を描画し、次に次の部分 (この場合は N を増やすことで実現されます) を画面を満たすまで繰り返します。

一般に、捕獲された標本では、 Nはほぼ17Kの値に達しましたそして、わずか 4 日で少なくとも XNUMX 件のそのようなリクエストが「チェーンに沿って」実行されました。 それらの最後の部分は大胆にスキャンされました 反復ごとに 1GB のメモリ...

合計で

出所： habr.com