PostgreSQL 索引扫描offset内核优化 - case-阿里云开发者社区

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

2016-07-17 5135

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

本文涉及的产品

RDS AI 助手，专业版

RDS MySQL DuckDB 分析主实例，基础系列 4核8GB

PolarClaw，2核4GB

简介： 背景 order by xx offset xx limit xx ，通常被用来做分页的查询，但是你会发现offset越多，越慢。 offset很多的情况下，即使没有sort，走的是索引，也会很慢。原因分析，PostgreSQL的索引上面没有版本信息，所以行是否可见的话，需要通过索

背景

最近写了好几篇与offset有关的文章，上一篇是解offset质变的问题。
https://yq.aliyun.com/articles/57730

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

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

原因分析

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

由于需要从 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并不会太多。
screenshot

小结

.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）

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

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

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

背景

原因分析

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

场景举例

本文涉及的btree索引结构

小结

术语

关系型数据库

热门文章

最新文章

相关产品

相关课程

相关电子书

推荐镜像