効率的なIN 演算子クエリ
このドキュメントでは、IN SQL演算子を使った効率的な順序付きデータベースクエリを構築するテクニックと、そのテクニックを適用するためのGitLabユーティリティモジュールの使い方について説明します。
動機
GitLabでは、Issue のような多くのドメインオブジェクトが、プロジェクトやグループのネストした階層の下に存在します。グループレベルのドメインオブジェクトのネストしたデータベースレコードを取得するために、IN SQL演算子でクエリを実行することがよくあります。通常、ORDER BY 節やLIMIT 節を使用して、レコードをいくつかの属性で並べ替えたり、レコード数を制限してパ フォーマンスを向上させることに関心があります。ページネーションは、後続のレコードをフェッチするために使用されます。
ネストされたドメイン・オブジェクトをグループ・レベルからクエリする必要があるタスクの例：
- グループ
gitlab-orgから、作成日または期限別に最初の20件のイシューを表示します。 - グループからマージされた日付で最初の20件のマージリクエストを表示
gitlab-com.
残念なことに、順序付けされたグループレベルクエリは、実行に重いI/O、メモリ、計算を必要とするため、一般的にパフォーマンスが悪くなります。このようなクエリの実行について詳しく調べてみましょう。
IN クエリのパフォーマンス問題
以下のクエリで、gitlab-org グループから最も古く作成された20個のイシューをフェッチするタスクを考えてみましょう：
SELECT "issues".*
FROM "issues"
WHERE "issues"."project_id" IN
(SELECT "projects"."id"
FROM "projects"
WHERE "projects"."namespace_id" IN
(SELECT traversal_ids[array_length(traversal_ids, 1)] AS id
FROM "namespaces"
WHERE (traversal_ids @> ('{9970}'))))
ORDER BY "issues"."created_at" ASC,
"issues"."id" ASC
LIMIT 20
クエリの実行は大きく3つのステップに分けることができます：
- データベースは、
namespacesとprojectsの両方のテーブルにアクセスし、グループ階層内のすべてのグループからすべてのプロジェクトを検索します。 - データベースはプロジェクトごとに
issuesレコードを取得するため、ディスク I/O が大きくなります。理想的には、適切なインデックス設定でこの処理を最適化する必要があります。 - データベースは、メモリ内の
issues行をcreated_atでソートし、LIMIT 20行をエンドユーザーに返します。大規模なグループの場合、この最終ステップには大量のメモリとCPUリソースの両方が必要になります。
このDBクエリの実行計画：
Limit (cost=90170.07..90170.12 rows=20 width=1329) (actual time=967.597..967.607 rows=20 loops=1)
Buffers: shared hit=239127 read=3060
I/O Timings: read=336.879
-> Sort (cost=90170.07..90224.02 rows=21578 width=1329) (actual time=967.596..967.603 rows=20 loops=1)
Sort Key: issues.created_at, issues.id
Sort Method: top-N heapsort Memory: 74kB
Buffers: shared hit=239127 read=3060
I/O Timings: read=336.879
-> Nested Loop (cost=1305.66..89595.89 rows=21578 width=1329) (actual time=4.709..797.659 rows=241534 loops=1)
Buffers: shared hit=239121 read=3060
I/O Timings: read=336.879
-> HashAggregate (cost=1305.10..1360.22 rows=5512 width=4) (actual time=4.657..5.370 rows=1528 loops=1)
Group Key: projects.id
Buffers: shared hit=2597
-> Nested Loop (cost=576.76..1291.32 rows=5512 width=4) (actual time=2.427..4.244 rows=1528 loops=1)
Buffers: shared hit=2597
-> HashAggregate (cost=576.32..579.06 rows=274 width=25) (actual time=2.406..2.447 rows=265 loops=1)
Group Key: namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1)]
Buffers: shared hit=334
-> Bitmap Heap Scan on namespaces (cost=141.62..575.63 rows=274 width=25) (actual time=1.933..2.330 rows=265 loops=1)
Recheck Cond: (traversal_ids @> '{9970}'::integer[])
Heap Blocks: exact=243
Buffers: shared hit=334
-> Bitmap Index Scan on index_namespaces_on_traversal_ids (cost=0.00..141.55 rows=274 width=0) (actual time=1.897..1.898 rows=265 loops=1)
Index Cond: (traversal_ids @> '{9970}'::integer[])
Buffers: shared hit=91
-> Index Only Scan using index_projects_on_namespace_id_and_id on projects (cost=0.44..2.40 rows=20 width=8) (actual time=0.004..0.006 rows=6 loops=265)
Index Cond: (namespace_id = (namespaces.traversal_ids)[array_length(namespaces.traversal_ids, 1)])
Heap Fetches: 51
Buffers: shared hit=2263
-> Index Scan using index_issues_on_project_id_and_iid on issues (cost=0.57..10.57 rows=544 width=1329) (actual time=0.114..0.484 rows=158 loops=1528)
Index Cond: (project_id = projects.id)
Buffers: shared hit=236524 read=3060
I/O Timings: read=336.879
Planning Time: 7.750 ms
Execution Time: 967.973 ms
(36 rows)
クエリのパフォーマンスはデータベース内の行数に依存します。平均すると以下のようになります：
- グループ階層内のグループ数: 1,000未満
- プロジェクト数：5,000未満
- イシュー数：100,000以下
このリストから、issues のレコード数がパフォーマンスに最も大きな影響を与えることがわかります。典型的な使用方法として、イシュー・レコードの数はnamespaces やprojects レコードよりも速い速度で増加すると言えます。
この問題は、グループレベルのissue、マージリクエストページ、APIなど、レコードが特定の順序でリストされるグループレベルの機能のほとんどに影響します。非常に大きなグループの場合、データベースのクエリは簡単にタイムアウトし、HTTP 500エラーが発生します。
順序付きIN クエリの最適化
How to teach an elephant to dance rock and roll “という講演で、Maxim Bogukは、順序付きグループレベルクエリのような、特別なクラスの順序付きIN クエリを最適化するテクニックを示しました。
典型的な順序付きIN クエリは以下のようなものです：
SELECT t.* FROM t
WHERE t.fkey IN (value_set)
ORDER BY t.pkey
LIMIT N;
t.fkey IN value_set (|value_set| はvalue_set の値の数 ) の条件を満たすすべてのレコードを検索するのではなく、最大でも|value_set| + N レコードの検索が必要です。
私たちはこのテクニックをGitLabで使うために採用し、一般化しました。Gitlab::Pagination::Keyset::InOperatorOptimization クラスにユーティリティを実装することで、効率的なIN クエリの構築を容易にしました。
要件
このテクニックは、IN 演算子を使用した既存のグループレベルクエリの置き換えではありません。このテクニックは、以下の要件を満たすIN クエリのみを最適化することができます：
-
LIMITこれは通常、クエリがページ分割されていることを意味します（オフセットまたはキーセットのページ分割）。 -
INクエリで使用されるカラムとORDER BY節のカラムは、データベース・インデックスでカバーされます。インデックス内の列は以下の順序でなければなりません：column_for_the_in_queryorder by column 1、およびorder by column 2。 -
ORDER BY節の列は区別されます（列の組み合わせにより、テーブル内の特定の行が一意に識別されます）。
COUNT(*) クエリのパフォーマンスを向上させません。
InOperatorOptimization モジュールは
GitLab 14.3で導入されました。
Gitlab::Pagination::Keyset::InOperatorOptimization モジュールは、前のセクションで説明した効率的なIN クエリ技術の一般化バージョンを適用するためのユーティリティを実装しています。
要件を満たす最適化された順序付きクエリIN を構築するには、このモジュールのユーティリティクラスQueryBuilder を使用してください。
Gitlab::Pagination::Keyset::InOperatorOptimization のテクニックの一般化された実装で基本的な役割を果たしています。基本的なQueryBuilder
基本的な使い方を説明するために、グループgitlab-org から最も古いcreated_at を含む 20 のイシューをフェッチするクエリを作成します。
以下のActiveRecordクエリは、先ほど検討した最適化されていないクエリと同様のクエリを生成します：
scope = Issue
.where(project_id: Group.find(9970).all_projects.select(:id)) # `gitlab-org` group and its subgroups
.order(:created_at, :id)
.limit(20)
代わりに、クエリビルダInOperatorOptimization::QueryBuilder を使用して最適化されたバージョンを生成します：
scope = Issue.order(:created_at, :id)
array_scope = Group.find(9970).all_projects.select(:id)
array_mapping_scope = -> (id_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)) }
finder_query = -> (created_at_expression, id_expression) { Issue.where(Issue.arel_table[:id].eq(id_expression)) }
Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder.new(
scope: scope,
array_scope: array_scope,
array_mapping_scope: array_mapping_scope,
finder_query: finder_query
).execute.limit(20)
-
scopeは、INクエリを除いたオリジナルのActiveRecord::Relationオブジェクトを表します。リレーションは、キーセットのページネーションライブラリがサポートしなければならない順序を定義しなければなりません。 -
array_scopeは、IN (subquery)を表すActiveRecord::Relationオブジェクトをコンテナとして持ちます。select値には、サブクエリがメインクエリに “接続 “されるカラムが含まれていなければなりません：プロジェクトレコードのid。 -
array_mapping_scopeは、ActiveRecord::Relationオブジェクトを返すラムダを定義します。このラムダは、(=) の単一の selearray_scopect 値にマッチします。 ラムダは、( ) で定義された select 値と同じ数の引数を返しますarray_scope。 引数は、Arel SQL 式です。 -
finder_queryはデータベースから実際のレコード行をロードします。また、これはラムダでなければならず、カラムによる順序式がレコードを見つけるために利用できます。この例では、created_atとidSQL式です。レコードの検索は主キーによって非常に高速に行われるため、created_atの値は使用しません。finder_queryラムダの指定は内部で任意です。指定しなかった場合、IN演算子の最適化はORDER BY列のみをエンドユーザーが利用できるようにし、データベース行全体を利用できるようにはしません。
クエリを効率的に実行するためには、issues テーブルに以下のデータベースインデックスが存在しなければなりません：
"idx_issues_on_project_id_and_created_at_and_id" btree (project_id, created_at, id)
SQL クエリ：
SELECT "issues".*
FROM
(WITH RECURSIVE "array_cte" AS MATERIALIZED
(SELECT "projects"."id"
FROM "projects"
WHERE "projects"."namespace_id" IN
(SELECT traversal_ids[array_length(traversal_ids, 1)] AS id
FROM "namespaces"
WHERE (traversal_ids @> ('{9970}')))),
"recursive_keyset_cte" AS ( -- initializer row start
(SELECT NULL::issues AS records,
array_cte_id_array,
issues_created_at_array,
issues_id_array,
0::bigint AS COUNT
FROM
(SELECT ARRAY_AGG("array_cte"."id") AS array_cte_id_array,
ARRAY_AGG("issues"."created_at") AS issues_created_at_array,
ARRAY_AGG("issues"."id") AS issues_id_array
FROM
(SELECT "array_cte"."id"
FROM array_cte) array_cte
LEFT JOIN LATERAL
(SELECT "issues"."created_at",
"issues"."id"
FROM "issues"
WHERE "issues"."project_id" = "array_cte"."id"
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
LIMIT 1) issues ON TRUE
WHERE "issues"."created_at" IS NOT NULL
AND "issues"."id" IS NOT NULL) array_scope_lateral_query
LIMIT 1)
-- initializer row finished
UNION ALL
(SELECT
-- result row start
(SELECT issues -- record finder query as the first column
FROM "issues"
WHERE "issues"."id" = recursive_keyset_cte.issues_id_array[position]
LIMIT 1),
array_cte_id_array,
recursive_keyset_cte.issues_created_at_array[:position_query.position-1]||next_cursor_values.created_at||recursive_keyset_cte.issues_created_at_array[position_query.position+1:],
recursive_keyset_cte.issues_id_array[:position_query.position-1]||next_cursor_values.id||recursive_keyset_cte.issues_id_array[position_query.position+1:],
recursive_keyset_cte.count + 1
-- result row finished
FROM recursive_keyset_cte,
LATERAL
-- finding the cursor values of the next record start
(SELECT created_at,
id,
position
FROM UNNEST(issues_created_at_array, issues_id_array) WITH
ORDINALITY AS u(created_at, id, position)
WHERE created_at IS NOT NULL
AND id IS NOT NULL
ORDER BY "created_at" ASC, "id" ASC
LIMIT 1) AS position_query,
-- finding the cursor values of the next record end
-- finding the next cursor values (next_cursor_values_query) start
LATERAL
(SELECT "record"."created_at",
"record"."id"
FROM (
VALUES (NULL,
NULL)) AS nulls
LEFT JOIN
(SELECT "issues"."created_at",
"issues"."id"
FROM (
(SELECT "issues"."created_at",
"issues"."id"
FROM "issues"
WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[position]
AND recursive_keyset_cte.issues_created_at_array[position] IS NULL
AND "issues"."created_at" IS NULL
AND "issues"."id" > recursive_keyset_cte.issues_id_array[position]
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)
UNION ALL
(SELECT "issues"."created_at",
"issues"."id"
FROM "issues"
WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[position]
AND recursive_keyset_cte.issues_created_at_array[position] IS NOT NULL
AND "issues"."created_at" IS NULL
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)
UNION ALL
(SELECT "issues"."created_at",
"issues"."id"
FROM "issues"
WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[position]
AND recursive_keyset_cte.issues_created_at_array[position] IS NOT NULL
AND "issues"."created_at" > recursive_keyset_cte.issues_created_at_array[position]
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)
UNION ALL
(SELECT "issues"."created_at",
"issues"."id"
FROM "issues"
WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[position]
AND recursive_keyset_cte.issues_created_at_array[position] IS NOT NULL
AND "issues"."created_at" = recursive_keyset_cte.issues_created_at_array[position]
AND "issues"."id" > recursive_keyset_cte.issues_id_array[position]
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)) issues
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
LIMIT 1) record ON TRUE
LIMIT 1) AS next_cursor_values))
-- finding the next cursor values (next_cursor_values_query) END
SELECT (records).*
FROM "recursive_keyset_cte" AS "issues"
WHERE (COUNT <> 0)) issues -- filtering out the initializer row
LIMIT 20
IN クエリ最適化の使用
フィルタの追加
この例では、milestone_id によってフィルタを追加してみましょう。
クエリにフィルタを追加する際には注意が必要です。カラムが同じインデックスでカバーされていない場合、クエリのパフォーマンスは最適化されていないクエリよりも悪くなる可能性があります。issues テーブルのmilestone_id カラムは現在、別のインデックスでカバーされています：
"index_issues_on_milestone_id" btree (milestone_id)
scope 引数または最適化されたスコープにmilestone_id = X フィルタを追加すると、パフォーマンスが低下します。
例（悪い）：
Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder.new(
scope: scope,
array_scope: array_scope,
array_mapping_scope: array_mapping_scope,
finder_query: finder_query
).execute
.where(milestone_id: 5)
.limit(20)
この問題にアドレスするには、別のインデックスを定義します：
"idx_issues_on_project_id_and_milestone_id_and_created_at_and_id" btree (project_id, milestone_id, created_at, id)
issues テーブルにさらにインデックスを追加すると、UPDATE クエリのパフォーマンスに大きな影響を与える可能性があります。この場合、元のクエリに依存する方が良いでしょう。フィルタリングされていないページの最適化を使用したい場合、アプリケーションコードに追加のロジックを追加する必要があることを意味します：
if optimization_possible? # no extra params or params covered with the same index as the ORDER BY clause
run_optimized_query
else
run_normal_in_query
end
複数のIN クエリ
グループレベルのクエリを拡張して、インシデントおよびテスト・ケースのイシュー・タイプのみを含めるとします。
元のActiveRecordクエリは以下のようになります：
scope = Issue
.where(project_id: Group.find(9970).all_projects.select(:id)) # `gitlab-org` group and its subgroups
.where(issue_type: [:incident, :test_case]) # 1, 2
.order(:created_at, :id)
.limit(20)
配列スコープを構築するには、project_id IN とissue_type IN クエリのデカルト積を取る必要があります。issue_type は ActiveRecord の列挙型なので、以下のテーブルを構築する必要があります：
project_id | issue_type_value |
|---|---|
| 2 | 1 |
| 2 | 2 |
| 5 | 1 |
| 5 | 2 |
| 10 | 1 |
| 10 | 2 |
| 9 | 1 |
| 9 | 2 |
issue_types クエリでは、テーブルをクエリせずに値リストを作成できます：
value_list = Arel::Nodes::ValuesList.new([[WorkItems::Type.base_types[:incident]],[WorkItems::Type.base_types[:test_case]]])
issue_type_values = Arel::Nodes::Grouping.new(value_list).as('issue_type_values (value)').to_sql
array_scope = Group
.find(9970)
.all_projects
.from("#{Project.table_name}, #{issue_type_values}")
.select(:id, :value)
array_mapping_scope クエリを構築するには、id とissue_type_value の2つの引数が必要です：
array_mapping_scope = -> (id_expression, issue_type_value_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)).where(Issue.arel_table[:issue_type].eq(issue_type_value_expression)) }
scope とfinder クエリは変わりません：
scope = Issue.order(:created_at, :id)
finder_query = -> (created_at_expression, id_expression) { Issue.where(Issue.arel_table[:id].eq(id_expression)) }
Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder.new(
scope: scope,
array_scope: array_scope,
array_mapping_scope: array_mapping_scope,
finder_query: finder_query
).execute.limit(20)
SQL クエリ：
SELECT "issues".*
FROM
(WITH RECURSIVE "array_cte" AS MATERIALIZED
(SELECT "projects"."id", "value"
FROM projects, (
VALUES (1), (2)) AS issue_type_values (value)
WHERE "projects"."namespace_id" IN
(WITH RECURSIVE "base_and_descendants" AS (
(SELECT "namespaces".*
FROM "namespaces"
WHERE "namespaces"."type" = 'Group'
AND "namespaces"."id" = 9970)
UNION
(SELECT "namespaces".*
FROM "namespaces", "base_and_descendants"
WHERE "namespaces"."type" = 'Group'
AND "namespaces"."parent_id" = "base_and_descendants"."id")) SELECT "id"
FROM "base_and_descendants" AS "namespaces")),
"recursive_keyset_cte" AS (
(SELECT NULL::issues AS records,
array_cte_id_array,
array_cte_value_array,
issues_created_at_array,
issues_id_array,
0::bigint AS COUNT
FROM
(SELECT ARRAY_AGG("array_cte"."id") AS array_cte_id_array,
ARRAY_AGG("array_cte"."value") AS array_cte_value_array,
ARRAY_AGG("issues"."created_at") AS issues_created_at_array,
ARRAY_AGG("issues"."id") AS issues_id_array
FROM
(SELECT "array_cte"."id",
"array_cte"."value"
FROM array_cte) array_cte
LEFT JOIN LATERAL
(SELECT "issues"."created_at",
"issues"."id"
FROM "issues"
WHERE "issues"."project_id" = "array_cte"."id"
AND "issues"."issue_type" = "array_cte"."value"
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
LIMIT 1) issues ON TRUE
WHERE "issues"."created_at" IS NOT NULL
AND "issues"."id" IS NOT NULL) array_scope_lateral_query
LIMIT 1)
UNION ALL
(SELECT
(SELECT issues
FROM "issues"
WHERE "issues"."id" = recursive_keyset_cte.issues_id_array[POSITION]
LIMIT 1), array_cte_id_array,
array_cte_value_array,
recursive_keyset_cte.issues_created_at_array[:position_query.position-1]||next_cursor_values.created_at||recursive_keyset_cte.issues_created_at_array[position_query.position+1:], recursive_keyset_cte.issues_id_array[:position_query.position-1]||next_cursor_values.id||recursive_keyset_cte.issues_id_array[position_query.position+1:], recursive_keyset_cte.count + 1
FROM recursive_keyset_cte,
LATERAL
(SELECT created_at,
id,
POSITION
FROM UNNEST(issues_created_at_array, issues_id_array) WITH
ORDINALITY AS u(created_at, id, POSITION)
WHERE created_at IS NOT NULL
AND id IS NOT NULL
ORDER BY "created_at" ASC, "id" ASC
LIMIT 1) AS position_query,
LATERAL
(SELECT "record"."created_at",
"record"."id"
FROM (
VALUES (NULL,
NULL)) AS nulls
LEFT JOIN
(SELECT "issues"."created_at",
"issues"."id"
FROM (
(SELECT "issues"."created_at",
"issues"."id"
FROM "issues"
WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[POSITION]
AND "issues"."issue_type" = recursive_keyset_cte.array_cte_value_array[POSITION]
AND recursive_keyset_cte.issues_created_at_array[POSITION] IS NULL
AND "issues"."created_at" IS NULL
AND "issues"."id" > recursive_keyset_cte.issues_id_array[POSITION]
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)
UNION ALL
(SELECT "issues"."created_at",
"issues"."id"
FROM "issues"
WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[POSITION]
AND "issues"."issue_type" = recursive_keyset_cte.array_cte_value_array[POSITION]
AND recursive_keyset_cte.issues_created_at_array[POSITION] IS NOT NULL
AND "issues"."created_at" IS NULL
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)
UNION ALL
(SELECT "issues"."created_at",
"issues"."id"
FROM "issues"
WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[POSITION]
AND "issues"."issue_type" = recursive_keyset_cte.array_cte_value_array[POSITION]
AND recursive_keyset_cte.issues_created_at_array[POSITION] IS NOT NULL
AND "issues"."created_at" > recursive_keyset_cte.issues_created_at_array[POSITION]
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)
UNION ALL
(SELECT "issues"."created_at",
"issues"."id"
FROM "issues"
WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[POSITION]
AND "issues"."issue_type" = recursive_keyset_cte.array_cte_value_array[POSITION]
AND recursive_keyset_cte.issues_created_at_array[POSITION] IS NOT NULL
AND "issues"."created_at" = recursive_keyset_cte.issues_created_at_array[POSITION]
AND "issues"."id" > recursive_keyset_cte.issues_id_array[POSITION]
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)) issues
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
LIMIT 1) record ON TRUE
LIMIT 1) AS next_cursor_values)) SELECT (records).*
FROM "recursive_keyset_cte" AS "issues"
WHERE (COUNT <> 0)) issues
LIMIT 20
project_id issue_type,created_at, andid.計算されたORDER BY 式を使用します。
以下の例では、作成時刻とクローズ時刻の間の期間によってエピックレコードを並べ替えます。これは以下の式で計算されます：
SELECT EXTRACT('epoch' FROM epics.closed_at - epics.created_at) FROM epics
上記のクエリは、2 つのタイムスタンプ列間の秒単位の継続時間 (double precision) を返します。この式でレコードを順序付けるには、ORDER BY 節でこの式を参照する必要があります：
SELECT EXTRACT('epoch' FROM epics.closed_at - epics.created_at)
FROM epics
ORDER BY EXTRACT('epoch' FROM epics.closed_at - epics.created_at) DESC
オペレータ内最適化でグループレベルでこの順序付けを効率的に行うには、ORDER BY のカスタム設定を使用してください。durationは明確な値ではありません（一意なインデックスが存在しません）ので、タイブレーク列（id ）を追加する必要があります。
次の例は、最後のORDER BY 節を示しています：
ORDER BY extract('epoch' FROM epics.closed_at - epics.created_at) DESC, epics.id DESC
計算された期間順にレコードをロードするスニペット：
arel_table = Epic.arel_table
order = Gitlab::Pagination::Keyset::Order.build([
Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
attribute_name: 'duration_in_seconds',
order_expression: Arel.sql('EXTRACT(EPOCH FROM epics.closed_at - epics.created_at)').desc,
distinct: false,
sql_type: 'double precision' # important for calculated SQL expressions
),
Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
attribute_name: 'id',
order_expression: arel_table[:id].desc
)
])
records = Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder.new(
scope: Epic.where.not(closed_at: nil).reorder(order), # filter out NULL values
array_scope: Group.find(9970).self_and_descendants.select(:id),
array_mapping_scope: -> (id_expression) { Epic.where(Epic.arel_table[:group_id].eq(id_expression)) }
).execute.limit(20)
puts records.pluck(:duration_in_seconds, :id) # other columns are not available
クエリの構築にはかなりの設定が必要です。オーダーの設定に関しては、キーセットのページ分割データベースクエリの複雑なオーダーの設定セクションでより多くの情報を得ることができます。
クエリには専用のデータベースインデックスが必要です：
CREATE INDEX index_epics_on_duration ON epics USING btree (group_id, EXTRACT(EPOCH FROM epics.closed_at - epics.created_at) DESC, id DESC) WHERE (closed_at IS NOT NULL);
finder_query パラメータが使用されていないことに注意してください。クエリはduration_in_seconds (計算カラム) とid カラムであるORDER BY カラムのみを返します。これは機能の制限で、ORDER BY の計算式でfinder_query を定義することはサポートされていません。完全なデータベースレコードを取得するには、返されたid カラムを使用して追加のクエリを実行します：
records_by_id = records.index_by(&:id)
complete_records = Epic.where(id: records_by_id.keys).index_by(&:id)
# Printing the complete records according to the `ORDER BY` clause
records_by_id.each do |id, _|
puts complete_records[id].attributes
end
JOIN カラムによる順序付け
1つ以上のカラムがJOIN テーブルから来ている混合カラムによるレコードの順序付けは、制限付きで動作します。これには、共通テーブル式JOIN による特別な設定が必要です。マテリアライズされていない CTE を使用して、必要なカラムをすべて公開する「偽の」テーブルとして動作させることです。
IN クエリと比べて向上しない可能性があります。常にクエリプランを確認してください。例: グループ階層内でイシューをprojects.name, issues.id 。
最初の手順は、SELECT 節に必要な列をすべて集めた CTE を作成することです。
cte_query = Issue
.select('issues.id AS id', 'issues.project_id AS project_id', 'projects.name AS projects_name')
.joins(:project)
cte = Gitlab::SQL::CTE.new(:issue_with_projects, cte_query, materialized: false)
カスタム注文オブジェクトの設定：
order = Gitlab::Pagination::Keyset::Order.build([
Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
attribute_name: 'projects_name',
order_expression: Issue.arel_table[:projects_name].asc,
sql_type: 'character varying',
nullable: :nulls_last,
distinct: false
),
Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
attribute_name: :id,
order_expression: Issue.arel_table[:id].asc
)
])
クエリを生成します：
scope = cte.apply_to(Issue.where({}).reorder(order))
opts = {
scope: scope,
array_scope: Project.where(namespace_id: top_level_group.self_and_descendants.select(:id)).select(:id),
array_mapping_scope: -> (id_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)) }
}
records = Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder
.new(**opts)
.execute
.limit(20)
バッチ反復
キーセットIterator クラスを使用すると、レコードを一括して反復処理することができます。
scope = Issue.order(:created_at, :id)
array_scope = Group.find(9970).all_projects.select(:id)
array_mapping_scope = -> (id_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)) }
finder_query = -> (created_at_expression, id_expression) { Issue.where(Issue.arel_table[:id].eq(id_expression)) }
opts = {
in_operator_optimization_options: {
array_scope: array_scope,
array_mapping_scope: array_mapping_scope,
finder_query: finder_query
}
}
Gitlab::Pagination::Keyset::Iterator.new(scope: scope, **opts).each_batch(of: 100) do |records|
puts records.select(:id).map { |r| [r.id] }
end
UPDATE やDELETE 。id 列はORDER BY 列 (created_at とid) の内部に含まれており、既にロードされています。この場合、finder_query パラメータは省略できます。ORDER BY 列のみをロードする例：
scope = Issue.order(:created_at, :id)
array_scope = Group.find(9970).all_projects.select(:id)
array_mapping_scope = -> (id_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)) }
opts = {
in_operator_optimization_options: {
array_scope: array_scope,
array_mapping_scope: array_mapping_scope
}
}
Gitlab::Pagination::Keyset::Iterator.new(scope: scope, **opts).each_batch(of: 100) do |records|
puts records.select(:id).map { |r| [r.id] } # only id and created_at are available
end
キーセットのページ分割
この最適化は、GraphQLとkeyset_paginate ヘルパーメソッドですぐに機能します。キーセットのページネーションについてもっと読む
array_scope = Group.find(9970).all_projects.select(:id)
array_mapping_scope = -> (id_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)) }
finder_query = -> (created_at_expression, id_expression) { Issue.where(Issue.arel_table[:id].eq(id_expression)) }
opts = {
in_operator_optimization_options: {
array_scope: array_scope,
array_mapping_scope: array_mapping_scope,
finder_query: finder_query
}
}
issues = Issue
.order(:created_at, :id)
.keyset_paginate(per_page: 20, keyset_order_options: opts)
.records
Kaminariによるオフセットページネーション
InOperatorOptimization クラスが生成するActiveRecord スコープは、オフセットページ分割されたクエリで使用することができます。
Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder
.new(...)
.execute
.page(1)
.per(20)
.without_count
一般化されたIN 最適化テクニック
一般化されたIN 最適化テクニックを使用して、gitlab-org グループから最も古く作成された20のイシューをフェッチするために、QueryBuilder がどのように最適化されたクエリを構築するかを見てみましょう。
配列CTE
最初のステップとして、projects.id の値を収集するために Common Table Expression(CTE) を使用します。これは、array_scope ActiveRecordリレーション・パラメータをCTEでラップすることで行います。
WITH array_cte AS MATERIALIZED (
SELECT "projects"."id"
FROM "projects"
WHERE "projects"."namespace_id" IN
(SELECT traversal_ids[array_length(traversal_ids, 1)] AS id
FROM "namespaces"
WHERE (traversal_ids @> ('{9970}')))
)
このクエリは、1 つの列 (projects.id) を持つ以下の結果セットを生成します：
| ID |
|---|
| 9 |
| 2 |
| 5 |
| 10 |
配列マッピング
各プロジェクト(つまり、array_cte にプロジェクトIDを格納する各レコード)について、ORDER BY 節に従った最初のイシューを識別するカーソル値をフェッチします。
例として、array_cte から最初のレコードID=9 を選択してみましょう。以下のクエリは、ID=9 を持つプロジェクトのORDER BY 節を尊重する最初のissueレコードを識別するカーソル値(created_at, id) をフェッチするはずです：
SELECT "issues"."created_at", "issues"."id"
FROM "issues"."project_id"=9
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
LIMIT 1;
LATERAL JOIN を使用して、array_cte のレコードをループし、各プロジェクトのカーソル値を見つけます。このクエリはarray_mapping_scope ラムダ関数を使用して作成されます。
SELECT ARRAY_AGG("array_cte"."id") AS array_cte_id_array,
ARRAY_AGG("issues"."created_at") AS issues_created_at_array,
ARRAY_AGG("issues"."id") AS issues_id_array
FROM (
SELECT "array_cte"."id" FROM array_cte
) array_cte
LEFT JOIN LATERAL
(
SELECT "issues"."created_at", "issues"."id"
FROM "issues"
WHERE "issues"."project_id" = "array_cte"."id"
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
LIMIT 1
) issues ON TRUE
project_id 、created_at 、id にインデックスがあるので、インデックスのみのスキャンで全てのカーソル値を素早く見つけることができます。
このクエリはRubyに変換することができます：
created_at_values = []
id_values = []
project_ids.map do |project_id|
created_at, id = Issue.select(:created_at, :id).where(project_id: project_id).order(:created_at, :id).limit(1).first # N+1 but it's fast
created_at_values << created_at
id_values << id
end
結果セットはこのようになります：
project_ids | created_at_values | id_values |
|---|---|---|
| 2 | 2020-01-10 | 5 |
| 5 | 2020-01-05 | 4 |
| 10 | 2020-01-15 | 7 |
| 9 | 2020-01-05 | 3 |
この表は、ORDER BY 節に従った各プロジェクトの最初のレコードのカーソル値(created_at, id)を示しています。
この時点で、初期データが得られました。データベースから実際のレコードを収集し始めるために、LIMIT に達するか、それ以上データが見つからなくなるまで、各再帰が1行を検索する再帰 CTE クエリを使用します。
以下は、再帰 CTE クエリのステップの概要です（SQL でステップを表現するのは簡単ではありませんが、次に説明します）：
-
ORDER BY節に従って、最初のresultsetを並べ替えます。 - レコードを取得するために一番上のカーソルを選択します。この例では、このカーソルは
project_id=9の (2020-01-05,3) となります。 - (
2020-01-05,3) を使用して、ORDER BY節project_id=9フィルタに従った次のイシューをフェッチすることができます。これにより、更新されたresultsetが生成されます。
project_ids | created_at_values | id_values |
|---|---|---|
| 2 | 2020-01-10 | 5 |
| 5 | 2020-01-05 | 4 |
| 10 | 2020-01-15 | 7 |
| 9 | 2020-01-06 | 6 |
-
N=20のレコードを取得するまで、更新されたresultsetで 1 から 3 を繰り返します。
再帰 CTE クエリの初期化
最初の再帰クエリでは、正確に 1 行を生成する必要があります。これを初期化クエリ (initializer_query) と呼びます。
ARRAY_AGG 関数を使用して、初期結果セットを 1 行にまとめ、その行を再帰 CTE クエリの初期値として使用します：
初期化子行の例：
records | project_ids | created_at_values | id_values | Count | Position |
|---|---|---|---|---|---|
NULL::issues | [9, 2, 5, 10] | [...] | [...] | 0 | NULL |
-
records列には、ソートされたデータベース・レコードが含まれています。イニシャライザ・クエリは、最初の値をNULLに設定し、後でフィルタリングされます。 -
count列は、見つかったレコードの数を追跡します。この列を使用して、結果セットからイニシャライザ行をフィルタリングします。
CTE クエリの再帰部分
結果行は以下の手順で生成されます：
キーセット配列を整列
UNNEST [] WITH ORDINALITY テーブル関数を使用して、元のORDER BY 句とLIMIT 1 に従ってキーセット配列を並べ替えます。この関数は “最も低い “キーセットのカーソル値を見つけ、配列の位置を与えます。これらのカーソル値はレコードを見つけるために使用されます。
project_ids | created_at_values | id_values |
|---|---|---|
| 2 | 2020-01-10 | 5 |
| 5 | 2020-01-05 | 4 |
| 10 | 2020-01-15 | 7 |
| 9 | 2020-01-05 | 3 |
最初の行は、created_at とid の値が最も小さいので、4番目の行 (position = 4) です。また、UNNEST 関数は、余分な列（注：PostgreSQLは1ベースのインデックスを使用します）を使用して位置を公開しています。
UNNEST [] WITH ORDINALITY テーブル関数のデモ：
SELECT position FROM unnest('{2020-01-10, 2020-01-05, 2020-01-15, 2020-01-05}'::timestamp[], '{5, 4, 7, 3}'::int[])
WITH ORDINALITY AS t(created_at, id, position) ORDER BY created_at ASC, id ASC LIMIT 1;
結果
position
----------
4
(1 row)
次のカーソルを検索
では、id = 9 のプロジェクトの次のカーソル値(next_cursor_values_query)を見つけましょう。そのために、キーセットのページ分割SQLクエリを構築します。created_at = 2020-01-05 とid = 3 の次の行を探します。2つのデータベース列で順序付けを行うため、2つのケースが考えられます：
-
created_at = 2020-01-05とid > 3を持つ行があります。 -
created_at > 2020-01-05を含む行があります。
このクエリの生成は、汎用キーセットページ分割ライブラリによって行われます。クエリが終了すると、次のカーソル値を持つ一時テーブルができます：
created_at | ID |
|---|---|
| 2020-01-06 | 6 |
新しい行の作成
最後のステップとして、イニシャライザ行 (data_collector_query メソッド) を操作して新しい行を作成する必要があります。ここで2つのことが起こります：
- DBから行全体を読み込み、
recordsのカラムに返します。(result_collector_columnsメソッド) - 現在の位置のカーソル値をキーセットクエリの結果で置き換えます。
データベースから完全な行を読み出すには、主キーによるインデックススキャンを1回行うだけです。finder_query として渡された ActiveRecord クエリを使用します：
(SELECT "issues".* FROM issues WHERE id = id_values[position] LIMIT 1)
括弧を追加することで、結果の行をrecords 列に入れることができます。
カーソル値をposition 、PostgreSQLの標準的な配列演算子で置き換えることができます：
-- created_at_values column value
created_at_values[:position-1]||next_cursor_values.created_at||created_at_values[position+1:]
-- id_values column value
id_values[:position-1]||next_cursor_values.id||id_values[position+1:]
Rubyでは以下のようになります：
id_values[0..(position - 1)] + [next_cursor_values.id] + id_values[(position + 1)..-1]
この後、再帰は次の最も低いカーソル値を見つけることから始まります。
クエリの最終処理
最後のissues 行を生成するために、クエリをSELECT 文で囲みます：
SELECT "issues".*
FROM (
SELECT (records).* -- similar to ruby splat operator
FROM recursive_keyset_cte
WHERE recursive_keyset_cte.count <> 0 -- filter out the initializer row
) AS issues
パフォーマンス比較
データベースのインデックスが正しく設定されていると仮定すると、クエリによってアクセスされるデータベースの行数を調べることで、クエリのパフォーマンスを比較することができます。
- グループの数: 100
- プロジェクト数500
- イシュー数（グループ階層内）：50 000
標準IN クエリ：
| クエリ | インデックスからの読み込み | テーブルから読み込まれた行 | メモリ内でソートされた行 |
|---|---|---|---|
| グループ階層サブクエリ | 100 | 0 | 0 |
| プロジェクトルックアップクエリ | 500 | 0 | 0 |
| イシュー・ルックアップ・クエリ | 50 000 | 20 | 50 000 |
最適化されたIN クエリ：
| クエリ | インデックスからの読み込み | テーブルから読み込まれた行 | メモリ内でソートされた行 |
|---|---|---|---|
| グループ階層サブクエリ | 100 | 0 | 0 |
| プロジェクトルックアップクエリ | 500 | 0 | 0 |
| イシュー・ルックアップ・クエリ | 519 | 20 | 10 000 |
グループクエリとプロジェクトクエリはソートを使用しておらず、必要な列はデータベースのインデックスから読み込んでいます。これらの値は頻繁にアクセスされるので、ほとんどのデータはPostgreSQLのバッファキャッシュにある可能性が高いです。
最適化されたIN クエリは、インデックスから最大519エントリ（カーソル値）を読み取ります：
- 500回のインデックスのみのスキャンにより、各プロジェクトの配列が生成されます。最初のレコードのカーソル値はこちらです。
- 連続するレコードのインデックスのみの追加スキャンは最大19回です。
最適化されたIN クエリは、配列（プロジェクト配列ごとのカーソル値）を20回ソートします。しかし、これは10,000行を一度にソートするよりもメモリ負荷の低いタスクかもしれません。
gitlab-org グループのパフォーマンス比較：
| クエリ | 8Kバッファの数 | キャッシュされない実行時間 | キャッシュ実行時間 |
|---|---|---|---|
IN クエリ | 240833 | 1.2s | 660ms |
最適化されたIN クエリ | 9783 | 450ms | 22ms |