数据库优化-排序篇 (order by)

背景

日常开发工作中, 经常使用order by对结果集进行排序, 但是对其原理和具体实现可能不是很了解. 这样无法进行有效的分析和针对性优化.

因此, 我写下本篇文章介绍一下 order by的基本原理和一些工作中常见的排序相关问题.

数据准备

因为在工作中使用pg多一些, 所以文中的数据库选择了 PostgreSQL 11.14 64-bit

造一些测试数据, 可以参考: pg 快速造1000w测试数据

CREATE TABLE public.testdata (
 id int4 NOT NULL,
 "name" varchar(20) NULL,
 course int4 NULL,
 grade numeric(4, 2) NULL,
 testtime date NULL,
 note text NULL,
 CONSTRAINT testdata_pkey PRIMARY KEY (id)
);
-- 在name字段上有索引
CREATE INDEX idx_testdata_name ON public.testdata USING btree (name);

我造了1亿数据的testdata表, 空间约11G. id为主键, name上有btree索引.

order by的基本原理

数据库在确保能够返回正确的数据集的下, 尽快地返回数据. 如果内存够，就要多利用内存，尽量减少磁盘访问。

在此目的下, 数据库在执行 order by 语句时, 会根据返回的结果集大小和offset等因素选择不同的策略.

一般有4种策略.

• top-N heap sort
• quicksort
• external merge
• index scan

top-N heap sort

如果返回的结果集比较小,且是top-n, 例如返回前10行, 前20行.

数据库会选择top-N heap sort 排序方式.

top-N heap sort 就是堆排序. 举例: 维护一个大小为3的小顶堆, 在遍历表中数据时, 如果发现有比堆中数据小的值, 就放入堆中, 然后将原来堆中最大的一个移除. 等遍历完表中的所有行之后, 小顶堆中的数据就是最小的3个.

这种排序方式的优点是

• 占用内存少, 只需要维护较小数据量的堆
• 排序速度快, 因为直接在内存中排序, 不需要访问硬盘

缺点是:

• 只能适用于前N条数据

explain analyze select * from testdata order by testtime  limit 10

Limit  (cost=2269506.38..2269507.55 rows=10 width=41) (actual time=14447.031..14463.813 rows=10 loops=1)
  ->  Gather Merge  (cost=2269506.38..11992407.50 rows=83333334 width=41) (actual time=14447.030..14463.811 rows=10 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        ->  Sort  (cost=2268506.36..2372673.03 rows=41666667 width=41) (actual time=14408.032..14408.033 rows=10 loops=3)
              Sort Key: testtime
              Sort Method: top-N heapsort  Memory: 26kB
              Worker 0:  Sort Method: top-N heapsort  Memory: 26kB
              Worker 1:  Sort Method: top-N heapsort  Memory: 26kB
              ->  Parallel Seq Scan on testdata  (cost=0.00..1368104.67 rows=41666667 width=41) (actual time=0.061..11891.503 rows=33333334 loops=3)
Planning Time: 0.061 ms
Execution Time: 14463.833 ms

通过执行计划, 我们可以看到: pg 选择了 top-N heapsort 算法, 仅占用了约 26kB * 3 的内存空间.

内存空间乘以3的原因是: pg 使用了并行处理, 将要查询的数据分为了3份, 获取到结果后, 再合并到一起. 具体可见: Parallel Query

quicksort

当查询的数据结果集并不多 (默认小于4MB), 数据可以在内存中放得下.且没有 limit 语句, 则数据库会选择 quicksort 来进行排序.

quicksort 快速排序是O(nlogn)时间复杂度的排序算法. 具体的说明: 快速排序算法详解

quicksort 速度比较快, 和heap sort 没有太大差别 , 但是空间占用较大.

-- id < 10000039 只有38条数据
explain analyse select * from testdata where id < 10000039 order by testtime 

Sort  (cost=10.28..10.38 rows=39 width=41) (actual time=0.053..0.054 rows=38 loops=1)
  Sort Key: testtime
  Sort Method: quicksort  Memory: 28kB
  ->  Index Scan using testdata_pkey on testdata  (cost=0.57..9.25 rows=39 width=41) (actual time=0.003..0.006 rows=38 loops=1)
        Index Cond: (id < 10000039)
Planning Time: 0.100 ms
Execution Time: 0.068 ms

我们看到执行计划中 Sort Method: quicksort Memory: 28kB
说明了 pg 采用了quicksort的策略.

external merge

如果返回的结果集比较大或者是排序中靠后的位置, 数据库选择external merge

例如:

• 查询前100000条数据 (实际开发中没有这么干的, 这里只是为了演示)
• offset 2000000 之后的10行数据

数据库会选择外部排序 external merge

原因是: 数据量太大, 内存放不下. 只能借助硬盘空间. 但由于硬盘IO的速度远远低于内存, 因此external merge是最慢的排序方式.

explain analyze select * from testdata order by testtime limit 100000

Limit  (cost=10487734.89..10499402.37 rows=100000 width=41) (actual time=58074.284..58501.270 rows=100000 loops=1)
  ->  Gather Merge  (cost=10487734.89..20210636.01 rows=83333334 width=41) (actual time=58074.283..58497.653 rows=100000 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        ->  Sort  (cost=10486734.87..10590901.54 rows=41666667 width=41) (actual time=57595.012..57620.062 rows=33609 loops=3)
              Sort Key: testtime
              Sort Method: external merge  Disk: 1842800kB
              Worker 0:  Sort Method: external merge  Disk: 1798536kB
              Worker 1:  Sort Method: external merge  Disk: 1784088kB
              ->  Parallel Seq Scan on testdata  (cost=0.00..1368104.67 rows=41666667 width=41) (actual time=0.057..11149.567 rows=33333334 loops=3)
Planning Time: 0.093 ms
Execution Time: 58606.898 ms

EXPLAIN ANALYZE select * from testdata order by  testtime limit 10 offset 2000000

Limit  (cost=10721084.52..10721085.68 rows=10 width=41) (actual time=58363.311..58557.828 rows=10 loops=1)
  ->  Gather Merge  (cost=10487734.89..20210636.01 rows=83333334 width=41) (actual time=57471.559..58526.523 rows=2000010 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        ->  Sort  (cost=10486734.87..10590901.54 rows=41666667 width=41) (actual time=56984.771..57116.576 rows=666942 loops=3)
              Sort Key: testtime
              Sort Method: external merge  Disk: 1831128kB
              Worker 0:  Sort Method: external merge  Disk: 1792344kB
              Worker 1:  Sort Method: external merge  Disk: 1801960kB
              ->  Parallel Seq Scan on testdata  (cost=0.00..1368104.67 rows=41666667 width=41) (actual time=0.172..10872.959 rows=33333334 loops=3)
Planning Time: 0.064 ms
Execution Time: 58665.506 ms

我们可以看到执行计划中 Sort Method: external merge Disk: 1831128kB , 说明了使用了external merge

work_mem

我们在上面的3中策略中都提到了结果集大小会影响数据库选择不同的策略.
那么, 具体的值是多少呢? 又是如何配置的?

pg的参数 work_mem 用于配置具体多大的空间用于 sorting, joins, group 等操作.

如果操作的数据量大于work_mem指定的大小(默认 4 MB), pg则会选择使用硬盘空间. 小于则会使用内存空间.

-- Sets the maximum memory to be used for query workspaces. This much memory can be used by each internal sort operation and hash table before switching to temporary disk files.
-- SELECT *  FROM pg_settings where name = 'work_mem'
show work_mem;

index scan

刚刚讲得3种策略, 实际上都需要排序. 那么有没有什么方式, 可以让pg不排序?

答案是有的. 我们知道b-tree索引是有顺序的.
如果我们查询时order by的字段是有索引的. 那么pg就可以直接利用现有索引的有序性. 极大加快查询速度.

-- name 是有 btree索引
explain analyse select * from testdata order by name limit 10

Limit  (cost=0.57..23.92 rows=10 width=41) (actual time=0.012..0.019 rows=10 loops=1)
  ->  Index Scan using idx_testdata_name on testdata  (cost=0.57..233497703.30 rows=100000000 width=41) (actual time=0.011..0.018 rows=10 loops=1)
Planning Time: 0.061 ms
Execution Time: 0.028 ms

对比之前根据testtime排序所花的 14463 ms, 根据name排序只需要 0.028 ms.

实际工作中order by的情况, 会更复杂, 有时候会跟多个列.

例如: 下面的语句, 并不会走 Index Scan, 而是 top-N heapsort. 如果想要下面的语句也走index only , 需要有 (name,testtime) 的联合索引.
不能仅仅是testtime的索引.

explain analyse select * from testdata order by name,testtime limit 10

index only scan

如果在有索引的前提下, 查询语句的select的内容也是只有索引列. 那么, pg就不需要回表取数据了.

explain analyse select name from testdata order by name limit 10

Limit  (cost=0.57..23.92 rows=10 width=6) (actual time=0.015..0.020 rows=10 loops=1)
  ->  Index Only Scan using idx_testdata_name on testdata  (cost=0.57..233497703.30 rows=100000000 width=6) (actual time=0.014..0.019 rows=10 loops=1)
        Heap Fetches: 10
Planning Time: 0.082 ms
Execution Time: 0.030 ms

关于排序的问题

了解到排序的基本原理后, 一些问题就很容易解释了

为什么可以排序比内存空间还大的数据库表

我电脑的内存是16G, 但是打开一堆程序之后, 可用只有2GB.
而我的数据库表有11G, 如果将数据都放到内存进行排序, 肯定是放不下的.

那么数据库可以在有限的内存下进行排序, 是如何做到的呢?

这道题比较简单, 就不赘述了. (都在上面的文章里有解释)

为什么第二页的数据会和第一页的重复

问题说明: 有时候, 我们会发现order by 一些列时, 第二页的数据和第一页的数据有重复的.

原因1: order by的列是区分度不高的列(Tie-breaker column), 值并不是唯一的.
例如: order by 性别 或者 order by 状态. 1个字段值能够对应非常多的行.

而数据库在处理大量数据排序时, 有时会选择parallel query execution
同时多个线程分别排序数据, 完成后再拼合成结果.

这意味着: 同样的sql语句可能返回的结果是不同的. 同样值的排序无法保证.

原因2: 排序算法的不稳定性和再一次查询时数据数据又增加了

例如:

-- 返回结果中, 都是按照name进行排序的. 例如: A, B, C
-- 但是 所有name 为 A的数据, 顺序是无法保证的. 
select * from testdata order by name

解决方案:

• 把唯一性的字段, 放到最后一个order by的位置. 例如: order by 性别, id

详细解释: Paging Through Results

Notice that the query also orders the rows by the primary key (id). When paginating data, specifying the order is very important. Without it, the returned rows are non-deterministic and can confuse the end-user.

如何解决深翻页速度慢的问题

问题描述: 大数据量下, 页数较深时会有查询速度缓慢的问题.

如果使用传统的limit offset的形式, 导致查询速度慢的
主要影响因素是: offset, 因为offset的值比较大时, 会让数据库无法使用 heapsort.
只能使用external merge, 涉及到大量的硬盘IO.

我们可以看一下例子:

-- name 有btree索引, 但是也很慢
explain analyse select * from testdata order by name limit 10 offset 1000000

Limit  (cost=2334977.59..2335000.94 rows=10 width=41) (actual time=67462.852..67463.557 rows=10 loops=1)
  ->  Index Scan using idx_testdata_name on testdata  (cost=0.57..233497703.30 rows=100000000 width=41) (actual time=1.040..67421.361 rows=1000010 loops=1)
Planning Time: 0.090 ms
Execution Time: 67463.574 ms

优化的方向就是: 尽量减少offset的值

解决方案:

• Keyset Pagination
• 将数据放入到ES,Solr等文档数据库 (不是本篇文章的重点, 仅做延展)

什么是Keyset Pagination

Keyset Pagination 是一种解决深翻页的方案.
利用了btree索引的有序性, 每次查询时都根据where条件来进行分页. 而不是依靠offset.

我们看一下具体的例子

-- 第一页, 最后一条数据的id是 10000010
select id from testdata 
order by id
limit 10

-- 第二页, 需要获取到上一页数据的最后一条数据的id作为where条件
-- Execution Time: 0.020 ms
select id from testdata 
where id > 10000010
order by id
limit 10

-- 第N页, 需要获取到(N-1)页数据的最后一条数据的id作为where条件
-- Execution Time: 0.034 ms
select id from testdata 
where id > 19000010
order by id
limit 10

-- 最后一页
select id from testdata 
order by id desc
limit 10

我们可以看到由于没有offset, 查询速度维持在1ms以内. 优势很明显: 查询速度稳定, 快

但是, Keyset Pagination也有它的弊端.

• order by 的所有内容都需要有索引. 多字段排序需要联合索引.
• 只能上下翻页, 首页, 最后一页, 不支持随机跳页

此外, 在实际工作中, 我们往往使用ORM框架, 可以直接使用对应的库, 例如:
ruby gem order_query

join表的排序

为了更高的性能, 我们应该避免在 order by 后面加不同表的字段.

具体原因在下面的链接中有很好的演示和说明:

https://docs.gitlab.com/ee/development/database/pagination_performance_guidelines.html#ordering-by-joined-table-column

总结

pg 处理排序的4种方式

• top-N heapsort
• quicksort
• external merge
• index scan

排序相关的一些问题和解决方案

思考题

留给大家一些思考题

已知: testdata表 数据量 1亿, id为主键, name上有btree索引, course为数字
下面sql的排序方式是什么? 为什么?

-- 1 course = 95 数据量 100,000
select id from testdata where course = 95 order by name limit 10
-- 2 name = 'AAA' 数据量 40
select id from testdata where name = 'AAA' order by id limit 10
-- 3
select id from testdata where order by id limit 10 offset 100000
-- 4
select id from testdata order by name, id limit 10

参考

• All you need to know about sorting in Postgres
• Tune sorting operations in PostgreSQL with work_mem
• POSTGRESQL: IMPROVING SORT PERFORMANCE
• Sorting and Grouping, We need tool support for keyset pagination
• PostgreSQL ORDER BY
• 16 | “order by”是怎么工作的？
• PostgreSQL Sort
• docs.gitlab pagination_guidelines, docs.gitlab pagination_performance_guidelines
• Five ways to paginate in Postgres, from the basic to the exotic