使用延迟关联实现高效分页

在Web应用中对大型数据集进行分页看起来是一个简单的问题,但实际上很难扩展。两种主要的分页策略是 偏移量/限制数量(offset/limit) 和 游标(cursors)。

我们先来看看这两种方法,然后再介绍一种稍微改进的方法,可以让偏移/限制非常高效。

偏移量 / 限制数量(Offset / Limit) 分页

偏移量/限制数量(offset/limit) 方法是目前最常见的,它的原理是跳过一定数量的记录(页数),并将结果限制为一页。

举个例子,假设你的应用程序设置为每页显示15条记录。你的SQL语句会像这样:

-- 第一页
select * from users order by created_at desc limit 15 offset 0;

-- 第二页
select * from users order by created_at desc limit 15 offset 15;

-- 第三页
select * from users order by created_at desc limit 15 offset 30;

这是最常见的,因为它非常简单明了,容易理解,而且几乎每个框架都支持它。

除了容易实现之外,它还有一个很好的优点,那就是页面可以直接定位。例如,如果你想直接跳转到第20页,你可以做到,因为那个偏移量很容易计算出来。

但是,它也有一个很大的问题,就是数据库处理偏移量的方法不好。Offset让数据库把查询出来的前N个结果舍弃。不过,数据库仍然需要从磁盘中提取这些结果。

如果你只舍弃100行,这并不重要,但如果你舍弃100,000行,数据库就要做很多工作来舍弃结果。

在实际中,就是说第一页会加载得很快,之后的每一页都会越来越慢,直到web请求可能会超时的点。

基于游标的分页

基于游标的分页弥补了 偏移量/限制数量(offset/limit) 的一些缺陷,同时也引入了一些自己的问题。

基于游标的分页的原理是,存储关于最后一条展示给用户的记录的状态,然后根据这个状态来构建下一个查询。

所以,它不是按顺序获取所有记录并丢弃前N个记录,而是只获取最后一个位置N之后的记录。

如果按ID排序,SQL语句可能像这样:

-- 第1页
select * from users where id > 0 order by id limit 15;

-- 第2页(假设第一页的最大ID是24。)
select * from users where id > 24 order by id limit 15;

-- 第3页(假设第二页的最大ID是72。)
select * from users where id > 72 order by id limit 15;

你可能已经看到了好处。因为我们知道向用户显示的最后一个ID,所以我们知道下一个页面将以更高的ID开始。我们甚至不必检查ID较低的行,因为我们100%确定不需要显示这些行。

在上面的示例中,我特别展示了ID可能不是连续的,即可能缺少记录。这使得无法计算某个页面上会显示哪些记录,你必须跟踪页面上的最后一条记录。

与 偏移量/限制数量(offset/limit) 分页不同,在使用游标分页时,页面不能直接定位,你只能导航到“下一页”或“上一页”。

不过,游标分页有一个优点就是,在任何数量的页面上都很快速。它也非常适合无限滚动,因为页面本来就不需要直接定位。

Laravel 的文档有一些关于 偏移量(offset)和游标(cursors) 之间权衡取舍的内容:[分页《Laravel 9 中文文档》)

了解了这些之后,让我们看一看 偏移量/限制数量(offset/limit) 优化,它可以使其性能足以在数千页中使用。

偏移量 / 限制数量(Offset / Limit)与延迟关联

延迟关联(deferred join)是一种技术,它将对请求的列的访问推迟到 偏移量 / 限制数量(Offset / Limit) 已经应用之后。

使用这种技术,我们可以创建一个内部查询,该查询可以使用特定的索引进行优化,以获得最大的速度,然后将结果连接回同一个表以获取完整的行。

它看起来像这样:

select * from contacts          -- 你想要展示给用户的完整数据。
    inner join (                -- "延迟关联"。
        select id from contacts -- 使用快速索引进行分页。
            order by id
            limit 15 offset 150000
    ) as tmp using(id)
order by id                     -- 对单个结果页进行排序。

根据数据集的不同,效果可能会有很大的不同,但是会让数据库尽可能少地检索数据,来达到用户的查询结果。

“昂贵”的select *部分只在匹配内部查询的15行上运行。选择的所有数据都已延迟,因此称为延迟关联。

这种方法的性能不太可能比传统的 偏移量/限制数量(Offset / Limit) 更差,尽管这是可能的,所以你一定要对你的数据进行测试!

Laravel 实现

我们如何将这种技术应用到我们喜欢的 Web 框架,比如 Laravel 和 Rails 呢?

让我们具体看看 Laravel,因为我不了解 Rails。

(这个功能已经有一个包:github.com/hammerstonedev/fast-paginate)

感谢 Laravel 的 macroable 特性,我们可以扩展 Eloquent 查询构造器,添加一个新的方法叫做 fastPaginate。我们将模仿常规的 paginate 的命名,以保持一致性:

<?php
//  模仿标准的 `paginate` 命名。
Builder::macro('fastPaginate', function ($perPage = null, $columns = ['*'], $pageName = 'page', $page = null) {
     // 在这里添加我们的新的分页逻辑。
});

// 现在你可以在所有的模型查询上使用它。
Contact::query()->fastPaginate()

我们将尽可能少地做一些自定义工作,并将大部分工作交给Laravel。

下面是我们要做的:

  • 将查询上的select重置为只选择主键
  • 将修改后的查询通过常规的分页过程运行
  • 取得结果中的键,并运行第二个查询来获取完整的行
  • 获取生成的键并运行第二个查询以获取完整的行
  • 将新记录与旧分页器合并

这样我们就可以得到 Laravel 的 LengthAwarePaginator 和 延迟关联(deferred joins)的所有优点!

下面是一个基本的示例(注意:这个包更复杂,涵盖了更多的边缘情况!):

<?php
Builder::macro('fastPaginate', function ($perPage = null, $columns = ['*'], $pageName = 'page', $page = null) {
    $model = $this->newModelInstance();
    $key = $model->getKeyName();
    $table = $model->getTable();

    $paginator = $this->clone()
        //我们不需要它们来进行这个查询,它们将保留在实际获取记录的查询中。
        ->setEagerLoads([])
        //只选择主键,我们将在下面的第二个查询中获得完整记录。
        ->paginate($perPage, ["$table.$key"], $pageName, $page);

    // 直接使用 "raw" 添加我们的值,而不是添加新的绑定。
    // 这基本上是 Laravel 在某些地方使用的 `whereIntegerInRaw`,
    // 但是我们不能保证主键是整数,所以我们不能使用它。
    // 我们确定这些值是安全的,因为它们一开始就直接来自数据库。
    $this->query->wheres[] = [
        'type'   => 'InRaw',
        'column' => "$table.$key",
        // 从 *当前* 页面上的记录中获取键值,而不改变它们。
        'values'  => $paginator->getCollection()->map->getRawOriginal($key)->toArray(),
        'boolean' => 'and'
    ];

    // simplePaginate 递增一来查看是否有另一页。我们将减少一来抵消,
    // 因为在我们的情况下这是不必要的。
    $page = $this->simplePaginate($paginator->perPage(), $columns, $pageName, 1);

    // 创建一个新的分页器,这样我们就可以放入完整的记录,
    // 而不是修改后只选择主键的记录。
    return new LengthAwarePaginator(
        $page->items(),
        $paginator->total(),
        $paginator->perPage(),
        $paginator->currentPage(),
        $paginator->getOptions()
    );
});

Relation::macro('fastPaginate', function ($perPage = null, $columns = ['*'], $pageName = 'page', $page = null) {
    if ($this instanceof HasManyThrough || $this instanceof BelongsToMany) {
        $this->query->addSelect($this->shouldSelect($columns));
    }

    return tap($this->query->fastPaginate($perPage, $columns, $pageName, $page), function ($paginator) {
        if ($this instanceof BelongsToMany) {
            $this->hydratePivotRelation($paginator->items());
        }
    });
});

你会注意到,我们实际上没有在这里使用 join,而是使用了 where in。这主要是因为 Laravel 的分页器已经运行了查询,所以我们可以直接使用返回的键。我们不需要再次运行查询,所以我们不需要。(我们还必须给 Relation 类添加一个 macro,来模仿 Laravel 在底层的工作方式。在这里阅读更多内容。)

上面的 Laravel 代码可以处理整数和字符串主键,但它不能处理复合主键。这应该是可以的,但我还没有做到。我在几个查询上测试过这个,但肯定有一些边缘情况我没有考虑到。请在你们的应用中测试一下,并报告任何问题!

不过我们还没有完全完成……

延迟关联和覆盖索引

使用延迟关联的主要好处是减少数据库必须检索并丢弃的数据量。我们可以通过帮助数据库获取需要的数据,而不用获取底层行,从而进一步实现这一点。

这样做的方法称为“覆盖索引”,它是确保快速 offset / limit 分页的最终解决方案。

覆盖索引是一个索引,其中查询的所有必需字段都包含在索引本身中。当一个查询的所有部分都可以被一个索引“覆盖”时,数据库不需要读取行,它可以从索引中获取所需的一切。

请注意,覆盖索引不是以任何特殊方式创建的。它仅指单个索引满足查询所需的所有条件的情况。一个查询上的覆盖索引可能不是另一个查询的覆盖索引。

在接下来的几个示例中,我们将使用这个基本表,我用大约1000万行填充了这个表:

CREATE TABLE `contacts` (
  `id` bigint unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  `email` varchar(255) NOT NULL,
  `created_at` timestamp NULL,
  `updated_at` timestamp NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `users_email_unique` (`email`)
)

让我们来看一个只选择索引列的简单查询。在这种情况下,我们将从 contacts 表中选择 email

select email from contacts limit 10;

在这种情况下,数据库根本不需要读取底层行。在 MySQL 中,我们可以通过运行 explain 并查看 extra 列来验证这一点:

{
    "id": 1,
    "select_type": "SIMPLE",
    "table": "contacts",
    "partitions": null,
    "type": "index",
    "possible_keys": null,
    "key": "users_email_unique",
    "key_len": "1022",
    "ref": null,
    "rows": 10690173,
    "filtered": 100.00,
    "Extra": "Using index" 
}

extra: using index 告诉我们,MySQL 能够只使用索引来满足整个查询,而不需要查看底层行

如果我们尝试 select name from contacts limit 10,我们预计 MySQL 必须去行中获取数据,因为 name 没有索引。这正是发生的情况,如下explain所示:

{
    "id": 1,
    "select_type": "SIMPLE",
    "table": "contacts",
    "partitions": null,
    "type": "ALL",
    "possible_keys": null,
    "key": null,
    "key_len": null,
    "ref": null,
    "rows": 10690173,
    "filtered": 100.00,
    "Extra": null 
}

extra不再显示using index,所以我们没有使用覆盖索引。

如果在使用覆盖索引进行分页的情况下,你必须小心只使用索引中可用的列,否则你可能会强迫数据库读取行。

假设你每页有15条记录,你的用户想要查看第10001页,你的内部查询可能会像这样:

select id from contacts order by id limit 15 OFFSET 150000

explain再次显示了覆盖索引的使用。

{
    "id": 1,
    "select_type": "SIMPLE",
    "table": "contacts",
    "partitions": null,
    "type": "index",
    "possible_keys": null,
    "key": "PRIMARY",
    "key_len": "8",
    "ref": null,
    "rows": 150015,
    "filtered": 100.00,
    "Extra": "Using index" 
}

MySQL能够仅通过查看索引来执行这个查询。它不会简单地跳过前150,000行,用offset无法避免的,但它不用读取150,000行。(只有游标分页才能让你完全跳过行。)

即使使用覆盖索引和延迟关联,当你到达后面的页面时,结果也会变慢,尽管与传统的offset / limit相比应该很小。你可以很轻松地使用这些方法深入到数千页。

更好的覆盖索引

覆盖索引的好处很大程度上取决于你有好的覆盖索引,所以让我们谈谈这个问题。一切都取决于你的数据和用户的使用模式,但你可以做一些事情来确保查询的最高命中率。

这里主要是针对MySQL,因为这是我有经验的地方。在其他数据库中,情况可能会不同。

多列索引(Multi-Column Indexes)

大多数开发者习惯于给单列添加索引,但是你也可以给多列添加索引。事实上,如果你想要为一个耗费资源的分页查询创建一个覆盖索引,你几乎肯定需要一个多列索引。

当你试图优化一个分页查询的索引时,一定要把order by列放在最后。如果你的用户要按照updated_at排序,那么这应该是你的复合索引中的最后一列。

查看以下包含三列的索引:

alter table contacts add index `composite`(`is_deleted`, `is_archived`, `updated_at`);

或在Laravel完成:

$table->index(['is_deleted', 'is_archived', 'updated_at'], 'composite');

在MySQL中,复合索引是从左到右访问的,如果某一列缺失,或者在第一个范围条件之后,MySQL就会停止使用索引。

MySQL可以在以下情况下使用这个索引:

  • 你查询is_deleted
  • 你查询is_deletedis_archived
  • 你查询is_deletedis_archivedupdated_at
  • 你查询is_deletedis_archived列,并按照updated_at排序

如果你跳过了 is_archived, MySQL将无法访问 updated_at, 并且不得不在没有这个索引的情况下进行排序,或者干脆不使用这个索引,所以请务必做好计划。

主键始终存在

在MySQL的InnoDB引擎中,所有的索引都会附加主键。这意味着一个在(email)上的索引实际上是一个在(email, id)上的索引,这对于覆盖索引和延迟关联非常重要。

查询select email from contacts order by id完全可以由一个在email上的单一索引覆盖,因为InnoDB会把id附加到这个索引上!

使用我们之前的复合示例,你可以看到这有什么好处:

select
  id                   -- 隐式地在索引中
from
  contacts
where
  is_deleted = 0       -- 显式地在索引中
  and is_archived = 0  -- 显式地在索引中
order by
  updated_at desc      -- 显式地在索引中

因为复合索引覆盖了 is_deleted, is_archived, updated_at, 和 (由于InnoDB的功能) id, 这整个查询可以仅通过索引完成。

降序索引

大多数情况下,用户都是想要查找“最新”的数据,也就是最近更新或创建的数据,这可以通过updated_at DESC 排序来实现。

如果你知道你的用户将主要按降序对其结果进行排序,那么有必要专门创建一个降序索引。

MySQL 8 是第一个支持降序索引的MySQL版本。

如果你在 explain 的 Extra 部分看到了 Backward index scan,你可以配置一个更好的索引。

{
    "id": 1,
    "select_type": "SIMPLE",
    "table": "contacts",
    "partitions": null,
    "type": "index",
    "possible_keys": null,
    "key": "users_email_unique",
    "key_len": "1022",
    "ref": null,
    "rows": 10690173,
    "filtered": 100.00,
    "Extra": "Backward index scan; Using index" 
}

要声明一个降序索引,你只需要在你的索引语句中加上 DESC 关键字。要在 Laravel 中这样做,你需要使用 DB::raw() 方法:

$table->index(['is_deleted', 'is_archived', DB::raw('`updated_at` DESC')], 'composite');

正向索引扫描比反向索引扫描快 约15%,所以你最好按照你认为用户最常用的顺序添加索引,并且为少数情况付出一些代价。

天下无新事

使用 offset / limit 分页和延迟关联 (deferred join) 以及覆盖索引的方法非完美的解决方案。

单纯的延迟关联可能就能让你的速度提升不少,但需要更多的思考来设计正确的索引以获得最大的效益。

有人可能会认为,延迟关联应该是框架中默认的 offset / limit 方法,而任何时候覆盖索引命中都只是一个额外的奖励。我还没有在足够多的生产环境中测试过,所以还不能强烈地主张这一点。

最后,在你向我鼓掌和赞扬之前,请理解这并不是一个原创的概念!这个基本思想在一本叫做“高性能MySQL, 第三版”(现在也有第四版) 的书中概述了。

我之前读过这本书,然后有点忘记了这个小技巧。几天前,我在帮一个朋友优化他们的 Laravel + MySQL 应用时,我们遇到了这个问题,第一页工作得很好,而第 3231 页永远也加载不出来。

我想起了我读过的某些模糊记忆,于是我回到书中去查找并想出了如何针对他们的数据集在 Laravel 中实现它。

我喜欢阅读实体技术书籍就是因为这个原因。我可能只是将一些可能有用的部分标记为有趣,不知道什么时候会真正需要,但是我大致知道某些解决方案存在。然后当我需要使用它时,我可以回头去查找!

我强烈推荐那本 MySQL 书籍。

原文链接:aaronfrancis.com/2022/efficient-pa...

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 3
zhaozhangxiao

select * from contacts -- 你想要展示给用户的完整数据。 inner join ( -- "延迟关联"。 select id from contacts -- 使用快速索引进行分页。 order by id limit 15 offset 150000 ) as tmp using(id) order by id

此sql 查询计划,存在全表扫描。感觉和直接limit 10000 区别不大。

file

1年前 评论
OnlyRed (楼主) 1年前

6得一匹 :+1: :+1: :+1:

11个月前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!