• タイブレーカーカラム
• 結合されたテーブルのカラムによる順序付け
• フィルタリング
  • プロジェクト別
  • グループ別
    • 同じデータベーステーブルの列
    • 特殊なケース：機密フラグ
    • 別のデータベーステーブルのカラム

ページネーション・パフォーマンス・ガイドライン

以下の文書では、ページネーション(ソート)のパフォーマンスを向上させるためのいくつかのアイデアを示しています。これらはオフセットと キーセットの両方のページネーションに適用されます。

タイブレーカーカラム

カラムを並べる際には、明確なカラムのみで並べることをお勧めします。次の例を考えてみましょう：

created_at で並べ替えると、レコードがディスク上にどのように配置されているかによって結果が変わってきます。

データが明確に定義されたインターフェイスを介して公開され、APIのような自動化されたプロセスによって消費される場合は、タイブレーカ列を使用することをお勧めします。タイ・ブレーカー列を使用しないと、行の順序が変更される（データが再インポートされる）可能性があり、以下のようなデバッグが困難な問題が発生する可能性があります：

• 行を比較して変更を判断するインテグレーションが壊れるなど。
• Eタグのキャッシュ値が変更され、完全な再ダウンロードが必要。

SELECT issues.* FROM issues ORDER BY created_at;

この問題は、ORDER BY に2つ目のカラムを追加することで解決できます：

SELECT issues.* FROM issues ORDER BY created_at, id;

この変更によって順序が明確になり、「安定した」並べ替えができるようになります。

結合されたテーブルのカラムによる順序付け

結合されたデータベーステーブルのカラムによってデータを並べ替えたいことがよくあります。次の例は、first_mentioned_in_commit_at メトリック列によってissues レコードを並べ替えます：

SELECT issues.* FROM issues
INNER JOIN issue_metrics on issue_metrics.issue_id=issues.id
WHERE issues.project_id = 2
ORDER BY issue_metrics.first_mentioned_in_commit_at DESC, issues.id DESC
LIMIT 20
OFFSET 0

PostgreSQLバージョン11では、プランナはまずproject_id フィルタに一致する全てのイシューを検索し、次に全てのissue_metrics 行を結合します。行の順序付けはメモリ内で行われます。結合された関係が常に存在する場合（1:1の関係）、データベースはN * 2 行を読み取ります。ここでNはproject_id フィルタに一致する行の数です。

性能上の理由から、ORDER BY 節を指定する際に、異なるテーブルの列を混在させることは避けるべきです。

この特殊なケースでは、クエリを改善する簡単な方法（インデックス作成のような）はありません。issues.id 列をissue_metrics.issue_id に変更することで改善されると思うかもしれませんが、issue_metrics テーブルのすべての行を処理するようデータベースに強制する可能性があるため、クエリのパフォーマンスを悪化させる可能性があります。

この問題にアドレスする1つのアイデアは、非正規化です。issue_metrics テーブルにproject_id 列を追加することで、フィルタリングとソートが効率的になります：

SELECT issues.* FROM issues
INNER JOIN issue_metrics on issue_metrics.issue_id=issues.id
WHERE issue_metrics.project_id = 2
ORDER BY issue_metrics.first_mentioned_in_commit_at DESC, issue_metrics.issue_id DESC
LIMIT 20
OFFSET 0

フィルタリング

プロジェクト別

プロジェクトレベルでのフィルタリングは非常に一般的なユースケースです。例: マージリクエスト、イシュー、ボード、イテレーション。

これらの機能は、基本クエリにproject_id のフィルタを持っています。プロジェクトのイシューを読み込みます：

project = Project.find(5)

# order by internal id
issues = project.issues.order(:iid).page(1).per(20)

ベースクエリを効率的にするために、通常、project_id カラムをカバーするデータベースインデックスがあります。これにより、データベースがスキャンする必要のある行数が大幅に減少します。インデックスがなければ、issues テーブル全体をデータベースが読み込むことになります（フルテーブルスキャン）。

project_id は外部キーなので、次のようなインデックスが利用できるかもしれません：

"index_issues_on_project_id" btree (project_id)

GitLab 13.11では、issues テーブルに次のようなインデックス定義があります：

"index_issues_on_project_id_and_iid" UNIQUE, btree (project_id, iid)

このインデックスはデータベースのクエリとページ分割を完全にカバーします。

グループ別

残念ながら、グループレベルでソートやページ分割を行う効率的な方法はありません。データベースクエリの実行時間はグループ内のレコード数に応じて増加します。

グループレベルが実際にグループとそのサブグループを意味する場合、事態はさらに悪化します。最初のページをロードするために、データベースはグループ階層を検索し、すべてのプロジェクトを見つけ、すべてのイシューを検索します。

グループ・レベルでの非効率なクエリの主な原因は、データベース・スキーマの設計方法にあります。私たちのCoreドメイン・モデルはプロジェクトに関連付けられ、プロジェクトはグループに関連付けられます。これはデータベースの構造が悪いということではなく、グループレベルの効率的なクエリに最適化されていない正規化された形になっているだけです。長期的には非正規化を検討する必要があるかもしれません。

例グループ内のイシューのリスト

group = Group.find(9970)

Issue.where(project_id: group.projects).order(:iid).page(1).per(20)

生成されたSQLクエリ：

SELECT "issues".*
FROM "issues"
WHERE "issues"."project_id" IN
    (SELECT "projects"."id"
     FROM "projects"
     WHERE "projects"."namespace_id" = 5)
ORDER BY "issues"."iid" ASC
LIMIT 20
OFFSET 0

実行計画を見ると、要求されたよりもかなり多くの行（20行）を読み込んでおり、行はメモリ内でソートされています：

 Limit  (cost=10716.87..10716.92 rows=20 width=1300) (actual time=1472.305..1472.308 rows=20 loops=1)
   ->  Sort  (cost=10716.87..10717.03 rows=61 width=1300) (actual time=1472.303..1472.305 rows=20 loops=1)
         Sort Key: issues.iid
         Sort Method: top-N heapsort  Memory: 41kB
         ->  Nested Loop  (cost=1.00..10715.25 rows=61 width=1300) (actual time=0.215..1331.647 rows=177267 loops=1)
               ->  Index Only Scan using index_projects_on_namespace_id_and_id on projects  (cost=0.44..3.77 rows=19 width=4) (actual time=0.077..1.057 rows=270 loops=1)
                     Index Cond: (namespace_id = 9970)
                     Heap Fetches: 25
               ->  Index Scan using index_issues_on_project_id_and_iid on issues  (cost=0.56..559.28 rows=448 width=1300) (actual time=0.101..4.781 rows=657 loops=270)
                     Index Cond: (project_id = projects.id)
 Planning Time: 12.281 ms
 Execution Time: 1472.391 ms
(12 rows)

同じデータベーステーブルの列

同じデータベーステーブルにあるカラムによるフィルタリングはインデックスによって改善できます。state_id カラムによるフィルタリングをサポートしたい場合、次のようなインデックスを追加できます：

"index_issues_on_project_id_and_state_id_and_iid" UNIQUE, btree (project_id, state_id, iid)

Railsでのクエリ例：

project = Project.find(5)

# order by internal id
issues = project.issues.opened.order(:iid).page(1).per(20)

SQLクエリ：

SELECT "issues".*
FROM "issues"
WHERE
  "issues"."project_id" = 5
  AND ("issues"."state_id" IN (1))
ORDER BY "issues"."iid" ASC
LIMIT 20
OFFSET 0

上記のインデックスは、以下のプロジェクト・レベルのクエリをサポートしていません：

SELECT "issues".*
FROM "issues"
WHERE "issues"."project_id" = 5
ORDER BY "issues"."iid" ASC
LIMIT 20
OFFSET 0

特殊なケース：機密フラグ

issues テーブルには、イシューを機密扱いとするブーリアン・フィールド(confidential)があります。これにより、非メンバー・ユーザはイシューを不可視(フィルタアウト)にすることができます。

SQLクエリの例：

SELECT "issues".*
FROM "issues"
WHERE "issues"."project_id" = 5
AND "issues"."confidential" = FALSE
ORDER BY "issues"."iid" ASC
LIMIT 20
OFFSET 0

データベースクエリを改善するために、project_id 、confidential 、iid にインデックスを追加したくなるかもしれませんが、この場合は不要でしょう。テーブルのディストリビューションに基づくと、機密イシューはまれです。これらをフィルタリングしても、データベースクエリが大幅に遅くなることはありません。データベースは数行余分に読み込むかもしれませんが、パフォーマンスの違いはエンドユーザーには見えないかもしれません。

一方、機密イシューのみを表示する特別なフィルタを実装した場合、インデックスが必要になります。20件の機密イシューを見つけるには、データベースで数百行、最悪の場合はプロジェクト内のすべてのイシューをスキャンする必要があるかもしれません。

別のデータベーステーブルのカラム

例: 担当者によるプロジェクトのイシューのフィルタリング

project = Project.find(5)

project
  .issues
  .joins(:issue_assignees)
  .where(issue_assignees: { user_id: 10 })
  .order(:iid)
  .page(1)
  .per(20)

SELECT "issues".*
FROM "issues"
INNER JOIN "issue_assignees" ON "issue_assignees"."issue_id" = "issues"."id"
WHERE "issues"."project_id" = 5
  AND "issue_assignees"."user_id" = 10
ORDER BY "issues"."iid" ASC
LIMIT 20
OFFSET 0

データベースの（単純化しすぎた）実行計画の例：

1. データベースはSQLクエリを解析し、JOIN を検出します。
2. データベースはクエリを2つのサブクエリに分割します。
   • SELECT "issue_assignees".* FROM "issue_assignees" WHERE "issue_assignees"."user_id" = 10
   • SELECT "issues".* FROM "issues" WHERE "issues"."project_id" = 5
3. データベースはこれらのクエリを実行するための行数とコストを見積もります。
4. データベースは最も安価なクエリを最初に実行します。
5. クエリの結果を使用して、JOIN 列を使用して、他のテーブルから（他のクエリから）行をロードし、さらに行をフィルタリングします。

この例では、issue_assignees クエリが最初に実行されます。

GitLab プロジェクトでこのクエリを実行すると、次のような実行計画になります：

 Limit  (cost=411.20..411.21 rows=1 width=1300) (actual time=24.071..24.077 rows=20 loops=1)
   ->  Sort  (cost=411.20..411.21 rows=1 width=1300) (actual time=24.070..24.073 rows=20 loops=1)
         Sort Key: issues.iid
         Sort Method: top-N heapsort  Memory: 91kB
         ->  Nested Loop  (cost=1.00..411.19 rows=1 width=1300) (actual time=0.826..23.705 rows=190 loops=1)
               ->  Index Scan using index_issue_assignees_on_user_id on issue_assignees  (cost=0.44..81.37 rows=92 width=4) (actual time=0.741..13.202 rows=215 loops=1)
                     Index Cond: (user_id = 4156052)
               ->  Index Scan using issues_pkey on issues  (cost=0.56..3.58 rows=1 width=1300) (actual time=0.048..0.048 rows=1 loops=215)
                     Index Cond: (id = issue_assignees.issue_id)
                     Filter: (project_id = 278964)
                     Rows Removed by Filter: 0
 Planning Time: 1.141 ms
 Execution Time: 24.170 ms
(13 rows)

クエリはまずassignees を検索し、user_id (user_id = 4156052) でフィルタリングして 215 行を見つけます。これらの215行を使用して、データベースは主キーによって関連する215のイシュー行を検索します。project_id 列のフィルタがインデックスによってバックアップされていないことに注意してください。

ほとんどの場合、結合リレーションがあまり多くの行を返さないので、少数の行にアクセスする比較的効率的なデータベースクエリで終わります。データベースが大きくなるにつれて、これらのクエリは異なる挙動を示すようになるかもしれません。例えば、あるユーザーのissue_assignees レコード数が数百万件と非常に多いとします。この結合クエリはうまく動作せず、タイムアウトする可能性があります。

同様の問題は二重結合で、2番目のJOIN クエリにフィルタが存在します。例:Issue -> LabelLink -> Label(name=bug).

これらの問題を解決する簡単な方法はありません。データの非正規化は大きな助けになるかもしれませんが、マイナス効果もあります（データの重複やデータの更新）。

issue_assignees フィルタを改善するためのアイデア：

• issue_assignees テーブルにproject_id カラムを追加し、JOIN を実行する際に、project_id フィルタでさらに行をフィルタリングできるようにします。並べ替えはおそらくメモリ内で行われます：

   SELECT "issues".*
   FROM "issues"
   INNER JOIN "issue_assignees" ON "issue_assignees"."issue_id" = "issues"."id"
   WHERE "issues"."project_id" = 5
     AND "issue_assignees"."user_id" = 10
     AND "issue_assignees"."project_id" = 5
   ORDER BY "issues"."iid" ASC
   LIMIT 20
   OFFSET 0
  

• issue_assignees テーブルにiid カラムを追加。ORDER BY 列が異なり、project_id フィルタがissues テーブルから消えていることに注意してください：

   SELECT "issues".*
   FROM "issues"
   INNER JOIN "issue_assignees" ON "issue_assignees"."issue_id" = "issues"."id"
   WHERE "issue_assignees"."user_id" = 10
     AND "issue_assignees"."project_id" = 5
   ORDER BY "issue_assignees"."iid" ASC
   LIMIT 20
   OFFSET 0
  

このクエリは、issue_assignees レコードの数に関係なくうまく機能しますが、非常に高い代償を払うことになります：

• 2つのカラムが重複し、データベースのサイズが大きくなります。
• 2つのカラムを同期させる必要があります。
• クエリをサポートするために、issue_assignees テーブルにさらにインデックスが必要です。
• 新しいデータベースクエリは担当者検索に非常に特化しており、それを構築するには複雑なバックエンドコードが必要です。
  • 担当者がユーザーによってフィルタリングされている場合、別のカラムで並べ替えたり、project_id フィルタを削除したりします。