高效的IN操作符查询
本文档介绍了一种构建高效有序数据库查询的技术，使用SQL的IN操作符，以及如何利用GitLab实用程序模块来应用该技术。
所描述的技术大量使用了keyset pagination。建议先熟悉该主题。
动机
在GitLab中，许多领域对象（如Issue）存在于项目和组的嵌套层次结构下。为了从组级别获取领域对象的嵌套数据库记录，我们经常执行带有IN SQL操作符的查询。我们通常对按某些属性排序记录感兴趣，并使用ORDER BY和LIMIT子句限制记录数量以提高性能。分页可用于获取后续记录。
示例任务需要从组级别查询嵌套的领域对象：
- 显示gitlab-org组的按创建日期或截止日期排序的前20个issue。
- 显示gitlab-com组的按合并时间排序的前20个merge request。
不幸的是，有序的组级查询通常表现不佳，因为它们的执行需要大量的I/O、内存和计算资源。让我们深入分析一个此类查询的执行过程。
IN查询的性能问题
考虑从gitlab-org组获取二十个最旧的已创建issue的任务，使用以下查询：
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对于分页，仅按created_at列排序是不够的，我们必须添加id列作为tie-breaker。
该查询的执行可大致分为三个步骤：
- 数据库访问namespaces和projects表，以查找组层次结构中所有组下的所有项目。
- 数据库为每个项目检索issues记录，导致大量磁盘I/O。理想情况下，适当的索引配置应优化此过程。
- 数据库将issues行按created_at在内存中排序，并向最终用户返回前20行。对于大型组，这最后一步需要大量的内存和CPU资源。
该DB查询的执行计划：
限制 （成本=90170.07..90170.12 行数=20 宽度=1329）（实际时间=967.597..967.607 行数=20 循环次数=1）
缓冲区：共享命中=239127 读取=3060
I/O 时间：读取=336.879
-> 排序 （成本=90170.07..90224.02 行数=21578 宽度=1329）（实际时间=967.596..967.603 行数=20 循环次数=1）
排序键：issues.created_at, issues.id
排序方法：top-N 堆排序 内存：74kB
缓冲区：共享命中=239127 读取=3060
I/O 时间：读取=336.879
-> 嵌套循环 （成本=1305.66..89595.89 行数=21578 宽度=1329）（实际时间=4.709..797.659 行数=241534 循环次数=1）
缓冲区：共享命中=239121 读取=3060
I/O 时间：读取=336.879
-> 哈希聚合 （成本=1305.10..1360.22 行数=5512 宽度=4）（实际时间=4.657..5.370 行数=1528 循环次数=1）
分组键：projects.id
缓冲区：共享命中=2597
-> 嵌套循环 （成本=576.76..1291.32 行数=5512 宽度=4）（实际时间=2.427..4.244 行数=1528 循环次数=1）
缓冲区：共享命中=2597
-> 哈希聚合 （成本=576.32..579.06 行数=274 宽度=25）（实际时间=2.406..2.447 行数=265 循环次数=1）
分组键：namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1)]
缓冲区：共享命中=334
-> 位图堆扫描 在 namespaces 上 （成本=141.62..575.63 行数=274 宽度=25）（实际时间=1.933..2.330 行数=265 循环次数=1）
重新检查条件：(traversal_ids @> '{9970}'::integer[])
堆块：精确=243
缓冲区：共享命中=334
-> 位图索引扫描 在 index_namespaces_on_traversal_ids 上 （成本=0.00..141.55 行数=274 宽度=0）（实际时间=1.897..1.898 行数=265 循环次数=1）
索引条件：(traversal_ids @> '{9970}'::integer[])
缓冲区：共享命中=91
-> 仅索引扫描 使用 index_projects_on_namespace_id_and_id 在 projects 上 （成本=0.44..2.40 行数=20 宽度=8）（实际时间=0.004..0.006 行数=6 循环次数=265）
索引条件：(namespace_id = (namespaces.traversal_ids)[array_length(namespaces.traversal_ids, 1)])
堆获取：51
缓冲区：共享命中=2263
-> 索引扫描 使用 index_issues_on_project_id_and_iid 在 issues 上 （成本=0.57..10.57 行数=544 宽度=1329）（实际时间=0.114..0.484 行数=158 循环次数=1528）
索引条件：(project_id = projects.id)
缓冲区：共享命中=236524 读取=3060
I/O 时间：读取=336.879
规划时间：7.750 毫秒
执行时间：967.973 毫秒
(36 行)该查询的性能取决于数据库中的行数。 平均而言，我们可以得出以下结论：
- 组层级中的组数量：少于1,000个
- 项目数量：少于5,000个
- 问题数量：少于100,000个
从列表中可以看出，issues记录的数量对性能的影响最大。
按照典型用法，可以说问题记录的增长速度比namespaces和projects记录更快。
此问题影响我们大多数组级功能，这些功能按特定顺序列出记录，例如组级问题、合并请求页面和API。 对于非常大的组，数据库查询很容易超时，导致HTTP 500错误。
优化有序IN查询
在演讲 《如何教大象跳摇滚乐》 中，
Maxim Boguk 展示了一种优化特殊类别有序IN查询的技术，例如我们的有序组级查询。
典型的有序IN查询可能如下所示：
SELECT t.* FROM t
WHERE t.fkey IN (value_set)
ORDER BY t.pkey
LIMIT N;该技术的关键见解是：我们最多需要|value_set| + N次记录查找，
而不是检索满足t.fkey IN value_set条件的所有记录（|value_set|是value_set中的值数量）。
我们在GitLab中采用并推广了该技术，通过在Gitlab::Pagination::Keyset::InOperatorOptimization类中实现工具来构建高效的IN查询。
要求
该技术并非现有使用IN运算符的组级查询的直接替代方案。
该技术只能优化满足以下要求的IN查询：
-
存在
LIMIT子句，这通常意味着查询是分页的（偏移量分页或键集分页）。 -
用于
IN查询的列和ORDER BY子句中的列会被数据库索引覆盖。索引中的列必须按以下顺序：column_for_the_in_query、order by column 1和order by column 2。 -
ORDER BY子句中的列是唯一的（这些列的组合能唯一标识表中的一行）。
此技术不会提升 COUNT(*) 查询的性能。
InOperatorOptimization 模块
Gitlab::Pagination::Keyset::InOperatorOptimization 模块实现了用于应用前文所述高效 IN 查询技术的通用版本的工具。
要构建满足要求的优化且有序的 IN 查询，请使用该模块中的工具类 QueryBuilder。
在合并请求 51481 中引入的通用 keyset 分页模块，在该技术在 Gitlab::Pagination::Keyset::InOperatorOptimization 中的通用实现中扮演着基础角色。
QueryBuilder 的基本用法
为说明基本用法，我们构建一个查询来获取 gitlab-org 组中创建时间最早的 20 个问题。
以下 ActiveRecord 查询会生成类似我们之前分析的 非优化查询：
scope = Issue
.where(project_id: Group.find(9970).all_projects.select(:id)) # `gitlab-org` 组及其子组
.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表示原始的ActiveRecord::Relation对象，不含IN查询。该关系应定义一个由 keyset 分页库 支持的排序。 -
array_scope包含表示原始IN (subquery)的ActiveRecord::Relation对象。选择值必须包含将子查询与主查询“连接”起来的列：项目记录的id。 -
array_mapping_scope定义一个返回ActiveRecord::Relation对象的 lambda。该 lambda 匹配array_scope中的单个选择值。lambda 产生的参数数量与array_scope中定义的选择值相同，参数是 Arel SQL 表达式。 -
finder_query从数据库加载实际记录行。它也必须是 lambda，其中可用于定位记录的ORDER BY列表达式可用。在此示例中，生成的值是created_at和idSQL 表达式。通过主键查找记录非常快，因此我们不使用created_at值。提供finder_querylambda 是可选的。如果未给出，则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)将 milestone_id = X 过滤器添加到 scope 参数或优化范围会导致性能下降。
示例（不良）：
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? # 没有额外参数或参数与 ORDER BY 子句相同的索引覆盖
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` 组及其子组
.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：
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 查询：
```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 不为空
按 "created_at" 升序、"id" 升序排序
限制 1 条) 作为 position_query,
lateral
(选择 "record"."created_at",
"record"."id"
从 (
值 (NULL,
NULL)) 作为 nulls
左连接
(选择 "issues"."created_at",
"issues"."id"
从 (
(选择 "issues"."created_at",
"issues"."id"
从 "issues"
其中 "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[POSITION]
且 "issues"."issue_type" = recursive_keyset_cte.array_cte_value_array[POSITION]
且 recursive_keyset_cte.issues_created_at_array[POSITION] 为空
且 "issues"."created_at" 为空
且 "issues"."id" > recursive_keyset_cte.issues_id_array[POSITION]
按 "issues"."created_at" 升序、"issues"."id" 升序排序)
union all
(选择 "issues"."created_at",
"issues"."id"
从 "issues"
其中 "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[POSITION]
且 "issues"."issue_type" = recursive_keyset_cte.array_cte_value_array[POSITION]
且 recursive_keyset_cte.issues_created_at_array[POSITION] 不为空
且 "issues"."created_at" 为空
按 "issues"."created_at" 升序、"issues"."id" 升序排序)
union all
(选择 "issues"."created_at",
"issues"."id"
从 "issues"
其中 "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[POSITION]
且 "issues"."issue_type" = recursive_keyset_cte.array_cte_value_array[POSITION]
且 recursive_keyset_cte.issues_created_at_array[POSITION] 不为空
且 "issues"."created_at" > recursive_keyset_cte.issues_created_at_array[POSITION]
按 "issues"."created_at" 升序、"issues"."id" 升序排序)
union all
(选择 "issues"."created_at",
"issues"."id"
从 "issues"
其中 "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[POSITION]
且 "issues"."issue_type" = recursive_keyset_cte.array_cte_value_array[POSITION]
且 recursive_keyset_cte.issues_created_at_array[POSITION] 不为空
且 "issues"."created_at" = recursive_keyset_cte.issues_created_at_array[POSITION]
且 "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 和 id。
使用计算后的 ORDER BY 表达式
下面的示例按史诗（epic）记录的创建时间与关闭时间之间的间隔来排序。该间隔通过以下公式计算：
SELECT EXTRACT('epoch' FROM epics.closed_at - epics.created_at) FROM epics上面的查询返回两个时间戳列之间的持续时间（以秒为单位，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要让分组级的排序在使用 IN 操作符优化时更高效，需使用自定义 ORDER BY 配置。由于持续时间并非唯一值（不存在唯一索引），必须添加一个平局列（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,
sql_type: 'double precision' # 重要：针对计算型 SQL 表达式
),
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), # 过滤掉 NULL 值
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) # 其他列不可用构建此类查询需要较多配置。关于排序配置的详细信息，可在用于键集分页数据库查询的 复杂排序配置 部分中找到。
该查询需要一个专门的数据库索引：
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 参数未被使用。该查询仅返回 ORDER BY 列，即 duration_in_seconds（计算列）和 id 列。这是功能的一个限制——不支持定义包含计算 ORDER BY 表达式的 finder_query。若要获取完整的数据库记录，可通过返回的 id 列执行额外的查询：
records_by_id = records.index_by(&:id)
complete_records = Epic.where(id: records_by_id.keys).index_by(&:id)
# 按 `ORDER BY` 子句打印完整记录
records_by_id.each do |id, _|
puts complete_records[id].attributes
end按 JOIN 列排序
当记录按混合列排序（其中一列或多列来自 JOIN 表）时，存在一定限制。这需要通过公共表表达式（CTE）进行额外配置。技巧是使用非物化的 CTE 充当“虚拟”表，暴露所有需要的列。
查询性能可能不会比标准的 IN 查询有所改善。始终检查查询计划。
示例：在组层次结构内按 projects.name, issues.id 对问题排序
第一步是创建一个 CTE，在 SELECT 子句中收集所有必需列：
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
),
Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
attribute_name: :id,
order_expression: Issue.arel_table[:id].asc
)
])生成查询：
scope = cte.apply_to(Issue.where({}).reorder(order))
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该查询会从磁盘加载完整的数据库行。这可能导致I/O增加和数据库查询变慢。根据用例，主键通常只需要用于批处理查询来调用额外的语句（例如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] } # 仅id和created_at可用
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优化技术
让我们深入理解QueryBuilder如何利用通用IN优化技术构建优化查询，以获取组gitlab-org中最古老的二十个创建问题。
数组CTE
作为第一步，我们使用**公用表表达式（CTE）**收集projects.id值。这是通过将传入的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}')))
)该查询生成如下结果集（仅含一列projects.id）：
| ID |
|---|
| 9 |
| 2 |
| 5 |
| 10 |
数组映射
对于每个项目（即array_cte中存储项目ID的每条记录），我们需要获取符合ORDER BY子句的首个问题的游标值。
举例来说，我们从array_cte选取首条记录ID=9。以下查询应获取项目ID=9下首个问题记录的游标值(created_at, id)（该记录需符合ORDER BY子句）：
SELECT "issues"."created_at", "issues"."id"
FROM "issues" WHERE "issues"."project_id"=9
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
LIMIT 1;我们使用LATERAL JOIN循环遍历array_cte中的记录，并为每个项目查找游标值。该查询将由array_mapping_scope lambda函数构建。
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 但速度很快
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 |
该表显示了每个项目的第一条记录的游标值（created_at, id），并遵循 ORDER BY 子句。
此时，我们已经获得了初始数据。为了开始从数据库收集实际记录，我们使用递归 CTE 查询，每次递归定位一行，直到达到 LIMIT 或找不到更多数据为止。
以下是递归 CTE 查询中采取的步骤概述（用 SQL 表达这些步骤并不简单，后续会解释）：
-
根据
ORDER BY子句对初始resultset进行排序。 -
选择顶部的游标来获取记录，这是我们的第一条记录。在示例中，此游标将是项目 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 |
- 使用更新后的
resultset重复步骤 1 到 3，直到我们获取了N=20条记录。
初始化递归 CTE 查询
对于初始递归查询，我们需要生成恰好一行，我们称之为初始化查询（initializer_query）。
使用 ARRAY_AGG 函数将初始结果集压缩为一行，并将该行用作递归 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 子句对键集数组进行排序，并取前 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 |
第一行是第 4 行（position = 4），因为它具有最低的 created_at 和 id 值。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 行记录)查找下一个游标
现在，让我们为 id = 9 的项目查找下一个游标值（next_cursor_values_query）。为此，我们构建一个键集分页 SQL 查询。找到 created_at = 2020-01-05 和 id = 3 之后的那一行。因为我们按两个数据库列排序，所以存在两种情况：
- 存在
created_at = 2020-01-05且id > 3的行。 - 存在
created_at > 2020-01-05的行。
生成此查询由通用键集分页库完成。查询完成后，我们有一个包含下一个游标值的临时表：
created_at |
ID |
|---|---|
| 2020-01-06 | 6 |
生成新行
作为最后一步，我们需要通过操作初始化行（data_collector_query 方法）来生成一个新行。这里发生两件事：
- 从数据库中读取完整行并将其返回到
records列。（result_collector_columns方法） - 将当前位置的游标值替换为键集查询的结果。
从数据库中读取完整行只需一次主键索引扫描。我们使用作为 finder_query 传递的 ActiveRecord 查询：
(SELECT "issues".* FROM issues WHERE id = id_values[position] LIMIT 1)通过添加括号，可以将结果行放入 records 列。
可以通过标准的 PostgreSQL 数组运算符替换 position 处的游标值：
-- created_at_values 列值
created_at_values[:position-1]||next_cursor_values.created_at||created_at_values[position+1:]
-- id_values 列值
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).* -- 类似于 Ruby 的展开运算符
FROM recursive_keyset_cte
WHERE recursive_keyset_cte.count <> 0 -- 过滤掉初始化行
) 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 次，这意味着我们对 20 × 500 行进行排序。然而，这可能比一次性排序 10,000 行内存占用更低。
gitlab-org 组的性能比较：
| 查询 | 涉及的 8KB 缓冲区数量 | 未缓存执行时间 | 已缓存执行时间 |
|---|---|---|---|
IN 查询 |
240833 | 1.2 秒 | 660 毫秒 |
| 优化的 IN 查询 | 9783 | 450ms | 22ms |
在测量前，已单独执行组查找查询，以让组数据在缓冲缓存中可用。由于该查询被频繁调用，在生产环境的查询执行过程中，它会命中大量共享缓冲区。