本文共 9194 字，大约阅读时间需要 30 分钟。
PostgreSQL , visilibity map , offset , skip heap scan , index only scan
OFFSE limit是分页常用的功能。很多人可能有过这样的感受，分页越到后面越慢。
实际上原因是由于数据库在OFFSET指定记录数之前，是需要扫过这么多的符合条件的TUPLE才能知道应该从哪里开始返回。
比如
1、索引扫描时，并不知道一个索引页有多少条有效记录（因为索引中没有版本号，需要回表才知道这条记录是否对当前事务可见）。
优化手段：
PostgreSQL 9.1开始支持了index only scan，如果查询只包含索引列，并且索引(item)对应heap page是完全可见的（通过扫描visibility map标记得到），那么不需要回HEAP PAGE TOUCH TUPLE。这样的话在offset比较大时，可以用来优化翻页的CASE。
1、创建测试表
postgres=# create table t_only (id int primary key, info text); CREATE TABLE
2、写入测试数据
postgres=# insert into t_only select t, 'test' from generate_series(1,10000000) t ;
3、生成visilibity map文件
postgres=# vacuum ANALYZE t_only ; VACUUM
4、使用index only scan，OFFSET 10万记录。扫描了277个数据块（里面包含多次TOUCH的visibility map BLOCK）
postgres=# explain (analyze,verbose,timing,costs,buffers) select id from t_only order by id offset 100000 limit 10; QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=1774.64..1774.82 rows=10 width=4) (actual time=20.556..20.558 rows=10 loops=1) Output: id Buffers: shared hit=277 -> Index Only Scan using t_only_pkey on public.t_only (cost=0.43..177422.89 rows=10000097 width=4) (actual time=0.031..12.721 rows=100010 loops=1) Output: id Heap Fetches: 0 Buffers: shared hit=277 Planning time: 0.146 ms Execution time: 20.579 ms (9 rows)
5、关闭index only scan，需要扫描817个数据块。这里涉及到大量的回表操作。
postgres=# set enable_indexonlyscan =off; SET postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_only order by id offset 100000 limit 10; QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=2315.20..2315.43 rows=10 width=9) (actual time=27.388..27.391 rows=10 loops=1) Output: id, info Buffers: shared hit=817 -> Index Scan using t_only_pkey on public.t_only (cost=0.43..231475.26 rows=9999922 width=9) (actual time=0.022..19.013 rows=100010 loops=1) Output: id, info Buffers: shared hit=817 Planning time: 0.081 ms Execution time: 27.414 ms (8 rows)
前面说了index only scan仅仅适合于SELECT中包含的字段都在INDEX中，如果扫描的字段不在index中，是绝对用不到index only scan的。
但是我们可以强制使用index only scan，改写SQL。
例如我们要输出2个字段，而索引只是ID字段。那么可以改写SQL如下。
1、修改SQL如下。
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_only where id= any( array(select id from t_only order by id offset 100000 limit 10) -- 这里使用index only scan ); QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Index Scan using t_only_pkey on public.t_only (cost=1775.26..1790.35 rows=10 width=9) (actual time=22.359..22.371 rows=10 loops=1) Output: t_only.id, t_only.info Index Cond: (t_only.id = ANY ($0)) Buffers: shared hit=311 InitPlan 1 (returns $0) -> Limit (cost=1774.65..1774.82 rows=10 width=4) (actual time=22.311..22.314 rows=10 loops=1) Output: t_only_1.id Buffers: shared hit=277 -> Index Only Scan using t_only_pkey on public.t_only t_only_1 (cost=0.43..177420.27 rows=9999922 width=4) (actual time=0.026..13.821 rows=100010 loops=1) Output: t_only_1.id Heap Fetches: 0 Buffers: shared hit=277 Planning time: 0.165 ms Execution time: 22.400 ms (14 rows) postgres=# select * from t_only where id= any(array(select id from t_only order by id offset 100000 limit 10)); id | info --------+------ 100001 | test 100002 | test 100003 | test 100004 | test 100005 | test 100006 | test 100007 | test 100008 | test 100009 | test 100010 | test (10 rows)
使用以上方法，我们在offset时，用到了index only scan使得大部分TUPLE不需要回表就可以判断是否可见。
2、而使用正常的SQL写法，走了index scan需要回表来判断tuple的可见性。扫描了更多的数据块。
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_only order by id offset 100000 limit 10; QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=2315.20..2315.43 rows=10 width=9) (actual time=27.388..27.391 rows=10 loops=1) Output: id, info Buffers: shared hit=817 -> Index Scan using t_only_pkey on public.t_only (cost=0.43..231475.26 rows=9999922 width=9) (actual time=0.022..19.013 rows=100010 loops=1) Output: id, info Buffers: shared hit=817 Planning time: 0.081 ms Execution time: 27.414 ms (8 rows) postgres=# select * from t_only order by id offset 100000 limit 10; id | info --------+------ 100001 | test 100002 | test 100003 | test 100004 | test 100005 | test 100006 | test 100007 | test 100008 | test 100009 | test 100010 | test (10 rows)
既然手工修改可以达到避免回表判断TUPLE可见性的效果，那么在内核层面实际上也能使用同样的方法来优化。
PATCH如下
Hello. WIP-Patch for optimisation of OFFSET + IndexScan using visibility map. Patch based on idea of Maxim Boguk [1] with some inspiration from Douglas Doole [2]. --------- Everyone knows - using OFFSET (especially big) is not an good practice. But in reality they widely used mostly for paging (because it is simple). Typical situation is some table (for example tickets) with indexes used for paging\sorting: VACUUM FULL; VACUUM ANALYZE ticket; SET work_mem = '512MB'; SET random_page_cost = 1.0; CREATE TABLE ticket AS SELECT id, TRUNC(RANDOM() * 100 + 1) AS project_id, NOW() + (RANDOM() * (NOW()+'365 days' - NOW())) AS created_date, repeat((TRUNC(RANDOM() * 100 + 1)::text), 1000) as payload FROM GENERATE_SERIES(1, 1000000) AS g(id); CREATE INDEX simple_index ON ticket using btree(project_id, created_date); And some typical query to do offset on tickets of some project with paging, some filtration (based on index) and sorting: SELECT * FROM ticket WHERE project_id = ? AND created_date > '20.06.2017' ORDER BY created_date offset 500 limit 100; At the current moment IndexScan node will be required to do 600 heap fetches to execute the query. But first 500 of them are just dropped by the NodeLimit. The idea of the patch is to push down offset information in ExecSetTupleBound (like it done for Top-sort) to IndexScan in case of simple scan (without projection, reordering and qual). In such situation we could use some kind of index only scan (even better because we dont need index data) to avoid fetching tuples while they are just thrown away by nodeLimit. Patch is also availble on Github: https://github.com/michail-nikolaev/postgres/commit/a368c3483250e4c02046d418a27091678cb963f4?diff=split And some test here: https://gist.github.com/michail-nikolaev/b7cbe1d6f463788407ebcaec8917d1e0 So, at the moment everything seems to work (check-world is ok too) and I got next result for test ticket table: | offset | master | patch | 100 | ~1.3ms | ~0.7ms | 1000 | ~5.6ms | ~1.1ms | 10000 | ~46.7ms | ~3.6ms To continue development I have following questions: 0) Maybe I missed something huge... 1) Is it required to support non-mvvc (dirty) snapshots? They are not supported for IndexOnlyScan - not sure about IndexScan. 2) Should I try to pass informaiton about such optimisation to planner/optimizer? It is not too easy with current desigh but seems possible. 3) If so, should I add something to EXPLAIN? 4) If so, should I add some counters to EXPLAIN ANALYZE? (for example number of heap fetch avoided). 5) Should I add description of optimisation to https://www.postgresql.org/docs/10/static/queries-limit.html ? 6) Maybe you have some ideas for additional tests I need to add. Thanks a lot. [1] https://www.postgresql.org/message-id/CAK-MWwQpZobHfuTtHj9%2B9G%2B5%3Dck%2BaX-ANWHtBK_0_D_qHYxWuw%40mail.gmail.com [2] https://www.postgresql.org/message-id/CADE5jYLuugnEEUsyW6Q_4mZFYTxHxaVCQmGAsF0yiY8ZDggi-w%40mail.gmail.com
visilibity map文件，除了能用在本文提到的offset优化。
还能用在vacuum，vacuum freeze, index only scan等场景。用来跳过不需要垃圾回收的页，跳过不需要freeze的页，跳过扫描不需要回表扫描的页。
visilibity map文件的结构，每个HEAP页对应2个比特位。
/* Flags for bit map */ #define VISIBILITYMAP_ALL_VISIBLE 0x01 #define VISIBILITYMAP_ALL_FROZEN 0x02 #define VISIBILITYMAP_VALID_BITS 0x03 /* OR of all valid visibilitymap * flags bits */
其他分页优化技巧，比index only scan优化效果还要更佳(可以达到每一页都丝般柔滑)：
转载地址：http://hwkdo.baihongyu.com/