PostgreSQL 索引扫描offset内核优化 - case

背景

最近写了好几篇与offset有关的文章，上一篇是解offset质变的问题。

这一篇要解的是offset偏移量越大，越慢的问题。

offset偏移量很大的情况下，即使走的是索引（没有使用额外的sort），也会很慢，这是为什么呢？

原因分析

.1. PostgreSQL的索引里面没有版本信息，所以判断行是否可见，需要通过索引的CTID定位并访问到HEAP TUPLE，在tuple head中的信息，结合clog，snapshot等信息判断该tuple是否可见。

由于需要从 HEAP page判断tuple可见性，order by xx offset xx limit xx，offset的tuple全部都要扫一遍，offset偏移量越大越慢。

后来PostgreSQL引入了VISIBILITY MAP，以及INDEX ONLY SCAN，对于没有dead tuple的HEAP PAGE，从索引访问时，不需要到HEAP PAGE判断行的可见性，如果大多数heap page都是clean的，可以降低额外的heap page scan的概率。
(visibility map用于记录heap page中是否有dirty tuple)

那么什么情况下所有的heap page都是clean的呢？ 如果表是insert only的，并且使用read uncommitted的隔离级别，那么就不需要到heap page判断可见性，直接读索引即可。

insert only table的index only scan + offset 这种应用场景，是可以从内核层面进行优化的，并且可以取得非常好的优化效果。

.2. 即使使用了index only scan，你会发现，PostgreSQL扫描的PAGE也比预想的多，并没有使用index leaf page的pt_next直接搜索next index page?
(下面的例子中会看到)

insert only table + index only scan + 大量offset 场景内核优化手段

因为数据是只插入的，对于read uncommitted的事务隔离级别，不需要从heap中通过版本判断行是否对用户可见。

所以对于insert only table, read uncommitted 事务隔离级别，可以直接访问index。

场景举例

insert only table + index only scan + 大量offset 场景.

测试表, 以及PK离散随机数据

postgres=# create unlogged table tbl(id int primary key, info text, crt_time timestamp);
postgres=# insert into tbl select trunc(random()*100000000),'test',now() from generate_series(1,50000000) on conflict on constraint tbl_pkey do nothing;
postgres=# vacuum analyze tbl;

索引和heap的pages占用

postgres=# select relpages from pg_class where relname='tbl';
 relpages
----------
   250600
(1 row)

postgres=# select relpages from pg_class where relname='tbl_pkey';
 relpages
----------
   107881
(1 row)

offset 1000000行，如果走index only scan，使用index page的"双向链表"进行index range scan， 理论上不需要访问747849 个数据块，BTPageOpaqueData中包含了左右BLOCK ID，跨页访问不需要再回到root page。

但是从测试结果来看，确实访问了过多的数据块，即使是index only scan。

这是内核优化需要做的，把index only scan的page scan降低到实际需要扫的pages。

postgres=# explain (analyze,verbose,timing,costs,buffers) select id from tbl order by id offset 1000000 limit 10;
                                                                     QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=25968.49..25968.75 rows=10 width=4) (actual time=547.094..547.101 rows=10 loops=1)
   Output: id
   Buffers: shared hit=747849 read=2705
   ->  Index Only Scan using tbl_pkey on public.tbl  (cost=0.56..1021687.32 rows=39344184 width=4) (actual time=0.031..360.758 rows=1000010 loops=1)
         Output: id
         Heap Fetches: 0
         Buffers: shared hit=747849 read=2705
 Planning time: 0.107 ms
 Execution time: 547.131 ms
(9 rows)

postgres=# explain (analyze,verbose,timing,costs,buffers) select * from tbl order by id offset 1000000 limit 10;
                                                                    QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=51443.93..51444.45 rows=10 width=17) (actual time=2646.299..2646.316 rows=10 loops=1)
   Output: id, info, crt_time
   Buffers: shared hit=828838 read=173904 written=17651
   ->  Index Scan using tbl_pkey on public.tbl  (cost=0.56..2023997.81 rows=39344184 width=17) (actual time=0.044..2445.983 rows=1000010 loops=1)
         Output: id, info, crt_time
         Buffers: shared hit=828838 read=173904 written=17651
 Planning time: 0.114 ms
 Execution time: 2646.349 ms
(8 rows)

本文涉及的btree索引结构

.1. 索引页中包含相邻PAGE信息，结构如下，存放在index page的special space里面（index页尾）。
使用它来做index range scan可以大大降低本文提到的大批量数据扫描所需扫描的pages。
src/include/access/nbtree.h

typedef struct BTPageOpaqueData
{
        BlockNumber btpo_prev;          /* left sibling, or P_NONE if leftmost */
        BlockNumber btpo_next;          /* right sibling, or P_NONE if rightmost */
        union
        {
                uint32          level;          /* tree level --- zero for leaf pages */
                TransactionId xact;             /* next transaction ID, if deleted */
        }                       btpo;
        uint16          btpo_flags;             /* flag bits, see below */
        BTCycleId       btpo_cycleid;   /* vacuum cycle ID of latest split */
} BTPageOpaqueData;

.2. b-tree索引的叶子节点，相邻块并不一定是物理相邻的BLOCK，看例子：

postgres=#  select * from bt_metap('tbl1_pkey');
 magic  | version |  root  | level | fastroot | fastlevel
--------+---------+--------+-------+----------+-----------
 340322 |       2 | 117123 |     3 |   117123 |         3
(1 row)

postgres=#  select * from bt_page_items('tbl1_pkey',117123);
 itemoffset |    ctid    | itemlen | nulls | vars |          data
------------+------------+---------+-------+------+-------------------------
          1 | (412,1)    |       8 | f     | f    |
          2 | (117122,1) |      16 | f     | f    | b5 0f 31 04 00 00 00 00
(2 rows)

postgres=#  select * from bt_page_items('tbl1_pkey',412);
 itemoffset |    ctid    | itemlen | nulls | vars |          data
------------+------------+---------+-------+------+-------------------------
          1 | (19325,1)  |      16 | f     | f    | b5 0f 31 04 00 00 00 00
          2 | (3,1)      |       8 | f     | f    |
          3 | (109431,1) |      16 | f     | f    | 9f b5 02 00 00 00 00 00
          4 | (52242,1)  |      16 | f     | f    | 06 cf 05 00 00 00 00 00
          5 | (95690,1)  |      16 | f     | f    | bf f4 08 00 00 00 00 00
...
postgres=#  select * from bt_page_items('tbl1_pkey',3);  -- 返回的是叶子节点的数据块
 itemoffset |    ctid    | itemlen | nulls | vars |          data
------------+------------+---------+-------+------+-------------------------
          1 | (88774,1)  |      16 | f     | f    | 9f b5 02 00 00 00 00 00
          2 | (1,1)      |       8 | f     | f    |
          3 | (100620,1) |      16 | f     | f    | b5 02 00 00 00 00 00 00
          4 | (50720,1)  |      16 | f     | f    | 8b 05 00 00 00 00 00 00
...
postgres=#  select * from bt_page_items('tbl1_pkey',1);  --  叶子节点，返回heap ctid
 itemoffset |     ctid     | itemlen | nulls | vars |          data
------------+--------------+---------+-------+------+-------------------------
          1 | (147618,75)  |      16 | f     | f    | b5 02 00 00 00 00 00 00
          2 | (215874,86)  |      16 | f     | f    | 02 00 00 00 00 00 00 00
          3 | (26831,109)  |      16 | f     | f    | 03 00 00 00 00 00 00 00
          4 | (74722,117)  |      16 | f     | f    | 04 00 00 00 00 00 00 00
          5 | (186526,71)  |      16 | f     | f    | 08 00 00 00 00 00 00 00
          6 | (105855,132) |      16 | f     | f    | 0e 00 00 00 00 00 00 00
...
        272 | (166516,27)  |      16 | f     | f    | b3 02 00 00 00 00 00 00
(272 rows)

叶子节点 block 1的相邻节点是block 100620，显然是不相邻的。

因此根据索引的范围查询，仅索引BLOCK的访问就是非常离散的，再加上HEAP PAGE的访问，都是非常离散的。 好在索引页每一页都能放几百条，所以几百条的查询，实际上被访问的INDEX PAGE并不会太多。

小结

.1. 对于查询结果可以直接在索引输出的，带上OFFSET输出的话，可以用上 index only scan，但是从现在社区版本的情况来看，还有优化余地，至少能把需要访问的block下降。

PostgreSQL的b-tree是类似"双向链表"的结构，内核层面根据index leaf page的btpo_next，实施index range scan，不需要额外的INDEX PAGE访问。

.2. 索引的leaf page(s)，branch page(s)都是离散的，只是逻辑结构上是树状的，同级page之间是通过类似双向链表的形式组织的。

因此index range scan时，index page扫描也是离散的。 比如做一个index only scan，offset一批数据或者直接scan一堆数据，都是离散的扫描。

postgres=# explain (analyze,verbose,timing,costs,buffers) select id from tbl offset 1000000 limit 10;
                                                                     QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=25968.49..25968.75 rows=10 width=4) (actual time=528.914..528.921 rows=10 loops=1)
   Output: id
   Buffers: shared hit=750554
   ->  Index Only Scan using tbl_pkey on public.tbl  (cost=0.56..1021687.32 rows=39344184 width=4) (actual time=0.030..347.409 rows=1000010 loops=1)
         Output: id
         Heap Fetches: 0
         Buffers: shared hit=750554  -- offset与直接scan输出扫描的pages一致。
 Planning time: 0.083 ms
 Execution time: 528.948 ms
(9 rows)

postgres=# explain (analyze,verbose,timing,costs,buffers) select id from tbl limit 1000010;
                                                                     QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.56..25968.75 rows=1000010 width=4) (actual time=0.032..736.929 rows=1000010 loops=1)
   Output: id
   Buffers: shared hit=750554
   ->  Index Only Scan using tbl_pkey on public.tbl  (cost=0.56..1021687.32 rows=39344184 width=4) (actual time=0.031..362.791 rows=1000010 loops=1)
         Output: id
         Heap Fetches: 0
         Buffers: shared hit=750554  -- offset与直接scan输出扫描的pages一致。
 Planning time: 0.097 ms
 Execution time: 916.256 ms
(9 rows)

术语

.1. tuple，row
.2. ctid，行号（blocknum, 页内offset）

祝大家玩得开心，欢迎随时来阿里云促膝长谈业务需求 ，恭候光临。

阿里云的小伙伴们加油，努力做 最贴地气的云数据库 。

时间： 2024-08-19 10:20:14

PostgreSQL 索引扫描offset内核优化 - case的相关文章

懒人促进社会进步 - 5种索引的原理和优化Case (btree,hash,gin,gist,brin)

标签 PostgreSQL , 多列聚合 , gin , btree , n_distinct , 选择性 , 如何选择索引方法(hash,btree,gin,gist,brin) , 如何优化索引 , 相关性 背景 在广告行业,精准营销是一个较热的话题,之前写过一个案例,如何使用PostgreSQL的array类型和GIN索引实时圈人的场景. <万亿级营销(圈人)迈入毫秒时代 - 万亿user_tags级实时推荐系统数据库设计> 使用以上方法,程序需要作出一些调整(当然,如果用户原本就是Po

PostgreSQL 数据访问 offset 的质变 case

背景 offset limit是一个多么常见的需求啊,但是你知道offset的数据可能隐藏着质变吗? 如图 node有30W条数据,其中前100条是满足条件的,然后100条到20W条都是不满足条件的.所以offset 10 limit 10非常的快.但是offset 100 limit 10,就要扫描从100到20W条记录,然后再往后才是满足条件的记录.这就是质变的原因. 例子 生成1000万测试记录. postgres=# create table tbl(id int primary key

《高并发Oracle数据库系统的架构与设计》一2.1　索引扫描识别

2.1 索引扫描识别 如果把我们的数据库比喻成一座图书馆,那表作为数据的载体,则是一本一本的图书,而索引则是图书的目录.目录不仅让图书阅读和查找变得方便,更是图书成败的关键. 也许有人会说,我翻阅的是一本杂志,内容本就不多,我甚至不需要目录.是的,Oracle数据库也考虑到了这一点,对于数据量很小的表,我们可以不建索引,在查询时可以进行全表扫描(FULL TABLE SCAN),这种方式对于小表来说更适合.但是,如果我们手上是一本大字典呢?你甚至一个人都搬不动它,当然你也不必像看杂志一样每页都去

PostgreSQL 9.6 内核优化 - sort性能增强(batch化quicksort代替replacement selection when work_mem small)

PostgreSQL 9.6 内核优化 - sort性能增强(batch化quicksort代替replacement selection when work_mem small) 作者 digoal 日期 2016-10-08 标签 PostgreSQL , 9.6 , 内核优化 , sort , replacement selection , quciksort 背景 排序是比较常见的业务需求,为了降低排序的CPU开销,通常会使用索引来满足排序的需求. 但是并不是所有的QUERY都能使用索引

PostgreSQL 10.0 preview 多核并行增强 - 索引扫描、子查询、VACUUM、fdw/csp钩子

标签 PostgreSQL , 10.0 , 并行计算 , 索引扫描 , 子查询 , VACUUM , 外部表并行 背景 PostgreSQL 9.6推出的多核并行计算特性,支持全表扫描,hash join,聚合操作. 10.0 在此基础上,增加了更多的支持. 1. Parallel bitmap heap scan 2. Parallel Index Scans 3. Parallel Merge Join 4. parallelize queries containing subplans

PostgreSQL 9.6 内核优化 - sort 性能增强

PostgreSQL 9.6 内核优化 - sort 性能增强 作者 digoal 日期 2016-10-09 标签 PostgreSQL , sort , 内核优化 背景 PostgreSQL 9.6在排序这块做了一些性能增强,前面一篇主要讲了排序算法的变更. <PostgreSQL 9.6 内核优化 - sort性能增强(batch化quicksort代替replacement selection when work_mem small)> 本文针对另外几个SORT增强的点再简单介绍一下.

第六章——根据执行计划优化性能（2）——查找表/索引扫描

原文:第六章--根据执行计划优化性能(2)--查找表/索引扫描 前言:       在绝大部分情况下,特别是从一个大表中返回少量数据时,表扫描或者索引扫描并不是一种高效的方式.这些必须找出来并解决它们从而提高性能,因为扫描将遍历每一行,查找符合条件的数据,然后返回结果.这种处理是相当耗时耗资源的.在性能优化过程中,一般集中于: 1.  CPU 2.  Network 3.  磁盘IO 而扫描操作会增加这三种资源的开销.   准备工作: 下面将创建两个表来查看不同的物理关联操作的不同影响.创建脚本

PostgreSQL 9.6 检查点柔性优化(SYNC_FILE_RANGE) - 在单机多实例下的IO Hang问题浅析与优化

背景 PostgreSQL检查点是将shared buffer中的脏页打标记,并集中将其刷到磁盘的动作(fsync).(期间可能有刷盘的调度,降低当脏页很多时带来的IO影响) 在检查点之外,平时bgwriter进程则会使用bufferio的方式(write)将脏页写到OS的dirty page. 如果shared buffer非常大,而且数据库应用如果是频繁产生脏页的应用,那么检查点带来的性能影响会非常的明显. 例如shared buffer有100G,活跃数据有100G,同时活跃数据在不停的被

mysql降序索引和减轻索引扫描

Descending indexing and loose index scan 降序索引和减轻索引扫描 Comments to my previous posts, especially this one by Gokhan inspired me to write a bit about descending indexes and about loose index scan, or what Gokhan calls "better range" support. None o