标签
PostgreSQL , 内存带宽 , JOIN算法 , FILTER亲和力 , TSP , HINT , 索引扫描顺序与命中率 , 语义转换 , 扫描顺序 , 存储顺序 , 命中率 , 索引深度 , partial index
背景
一个OUTER JOIN的SQL优化，引出了一系列的知识点，非常值得深入探讨。
内存带宽 , JOIN算法 , FILTER亲和力 , TSP , HINT , 索引扫描顺序与命中率 , 语义转换 , 扫描顺序 , 存储顺序 , 命中率 , 索引深度 , partial index 。
SQL样例
digoal_tbl_task：8 GB
digoal_tbl_refund：14 GB
SELECT * FROM
digoal_tbl_task task
left outer JOIN
digoal_tbl_refund refund
on
task.biz_id = refund.id
where
refund.refund_digoal_rid_id=35018 and refund.refund_type=3 -- 这个去掉的话，语义则不能互通了。
and task.digoal_dealid=2997380888 and task.task_type=300 and task.status=8
limit 10 offset 20;
一、语义转换
这条SQL虽然是OUTER JOIN，但是Join条件只有一个等值条件，而其他条件都在WHERE中，WHERE条件中同时还包含了可空表的非空查询条件，因此我们可以认为它的语义与INNER JOIN一致。
SELECT * FROM
digoal_tbl_task task
INNER outer JOIN
digoal_tbl_refund refund
on
task.biz_id = refund.id
where
refund.refund_digoal_rid_id=35018 and refund.refund_type=3 -- 这个去掉的话，语义则不能互通了。
and task.digoal_dealid=2997380888 and task.task_type=300 and task.status=8
limit 10 offset 20;
二、性能指标
单次查询响应速度约7毫秒。
扫描了10217个数据块，这个也是后面重点优化的地方。
explain (analyze,verbose,timing,costs,buffers)
SELECT * FROM
digoal_tbl_task task
INNER outer JOIN
digoal_tbl_refund refund
on
task.biz_id = refund.id
where
refund.refund_digoal_rid_id=35018 and refund.refund_type=3 -- 这个去掉的话，语义则不能互通了。
and task.digoal_dealid=2997380888 and task.task_type=300 and task.status=8
limit 10 offset 20;
Limit (cost=64173.00..64173.00 rows=1 width=799) (actual time=4.717..7.064 rows=10 loops=1)
Output: ................
Buffers: shared hit=10217
-> Nested Loop (cost=1.13..64173.00 rows=12 width=799) (actual time=0.248..7.060 rows=30 loops=1)
Output: ...........................
Buffers: shared hit=10217
-> Index Scan using idx_digoal_rid_idtype on public.digoal_tbl_refund refund (cost=0.56..19350.09 rows=5243 width=513) (actual time=0.021..0.802 rows=2513 loops=1)
Output: .......................
Index Cond: ((refund.refund_digoal_rid_id = 35018) AND (refund.refund_type = 3))
Buffers: shared hit=122
-> Index Scan using idx_digoal_tbl_task_2 on public.digoal_tbl_task task (cost=0.56..8.54 rows=1 width=286) (actual time=0.002..0.002 rows=0 loops=2513)
Output: ........................................
Index Cond: ((task.digoal_dealid = 2997380888::bigint) AND (task.task_type = 300) AND (task.status = 8) AND (task.biz_id = refund.id))
Buffers: shared hit=10095
Planning time: 0.420 ms
Execution time: 7.166 ms
(16 rows)
三、内存带宽
测试环境是60核的机器，按单次查询时间，理论上性能应该可以达到60*1000/7.166=8372的TPS。但是，实际上真实的压测，并发查询也只能达到300多的TPS。
原因是什么？
实际上我们通过命中率，我们大概可以推算出来，356的TPS时，占用的内存带宽约 29 GB/s。加上其他的损耗，基本上达到了内存带宽的瓶颈。
postgres=# show block_size;
block_size
------------
8192
(1 row)
postgres=# select 10217*356*8;
?column?
----------
29098016
(1 row)
因为内存读取占用了大量的时间，所以降低CACHE读取，是重点需要优化的。
四、JOIN 算法
PostgreSQL支持三种JOIN算法，嵌套循环、MERGE SORT、哈希JOIN。
详见：
《PostgreSQL nestloop/hash/merge join讲解》
五、SQL HINT
PostgreSQL HINT可以指定执行计划。
详见:
《关键时刻HINT出彩 - PG优化器的参数优化、执行计划固化CASE》
比如
create extension pg_hint_plan;
load 'pg_hint_plan';
set client_min_messages ='notice';
set client_min_messages ='log';
set pg_hint_plan.debug_print =on;
set pg_hint_plan.enable_hint=on;
set pg_hint_plan.message_level =log;
set pg_hint_plan.parse_messages =log;
set pg_hint_plan.enable_hint_table =on;
postgres=> explain (analyze,verbose,timing,costs,buffers)
/*+
NestLoop(task refund)
Leading(task refund)
*/
SELECT * FROM
digoal_tbl_task task
left outer JOIN
digoal_tbl_refund refund
on
task.biz_id = refund.id
where
refund.refund_digoal_rid_id=35018 and refund.refund_type=3
and task.digoal_dealid=2997380888 and task.task_type=300 and task.status=8
limit 10 offset 20;
六、JOIN 索引过滤
在例子中，我们可以看到这样的执行计划，实际上在JOIN时，使用了索引，同时使用了索引过滤，而非查询过滤。
索引过滤的好处是不需要额外的CPU运算。
那么JOIN时，怎么样的条件能过滤呢？
对于NESTLOOP JOIN：
对于外表，除了JOIN都可以作为索引过滤条件。因为外表是需要遍历的，遍历时不知道它的JOIN KEY的VALUE到底是多少，所以作为复合索引没有必要把外表的JOIN字段加进来。
作为内表，所有条件都可以作为索引过滤条件。包括JOIN字段，因为内表不是遍历的，而是通过外表传入的JOIN值来查询的，因此复合索引可以加速JOIN字段。
那么应该如何创建索引呢？
外表：WHERE条件中除了JOIN字段的其他字段，构建BTREE复合索引，等值条件作为驱动列，如果有多个等值条件，那么将稀疏（选择性不好的）列排在前面。
Index Cond: ((refund.refund_digoal_rid_id = 35018) AND (refund.refund_type = 3))
内表，WHERE条件中，所有字段构建BTREE复合索引，等值条件作为驱动列，如果有多个等值条件，那么将稀疏（选择性不好的）列排在前面。
Index Cond: ((task.digoal_dealid = 2997380888::bigint) AND (task.task_type = 300) AND (task.status = 8) AND (task.biz_id = refund.id))
七、nestloop join + limit 命中率优化
在前面的执行计划中，虽然是limit 10 offset 20，最多实际上需要扫描30条外表即可，但是实际上，从LOOP值来看，外表扫描了2513次。
这也是前面提到的问题所在，LOOP 2513次，直接带来了10095个数据块的访问。
实际上每次访问了4个数据块
postgres=# select 10095/2513.0;
?column?
--------------------
4.0171110226820533
(1 row)
这平均4个数据块是内表每一次LOOP时，访问每一条记录的 "索引访问+HEAP访问 (有一些ID不存在所以不需要访问heap)" 命中到的BLOCK，实际上对于单次扫描来说已经很小了。
但是由于内表访问了2000多次，所以造成了IO放大。
那么为什么30次的LIMIT，内表确LOOP了2513次？
这说明外表提供的记录，扫了2513条，在内表中只有30条是满足JOIN和WHERE条件的记录，为了减少内表的扫描次数（最多降低到30次），我们可以通过调整外表的扫描顺序来实现。
做法，只要预先把满足条件的数据，在外表重排一下即可。
create table tmp (like digoal_tbl_refund);
insert into tmp select * from digoal_tbl_refund where id in
(select biz_id from digoal_tbl_refund where id in (select biz_id from digoal_tbl_task task where task.digoal_dealid=2997380888 and task.task_type=300 and task.status=8);
delete from digoal_tbl_refund where id in (select biz_id from digoal_tbl_task task where task.digoal_dealid=2997380888 and task.task_type=300 and task.status=8);
create table tmp1 (like digoal_tbl_refund);
insert into tmp1 select * from tmp;
insert into tmp1 select * from digoal_tbl_refund;
-- 重建索引tmp1
drop table digoal_tbl_refund;
alter table tmp1 rename to digoal_tbl_refund;
当然这个做法不具备通用性，需要预先处理。我只是借机讲解背后的原理。
这样做之后，只需要扫描30次内表了。
Limit (cost=61621.78..61621.78 rows=1 width=784) (actual time=0.479..0.634 rows=10 loops=1)
Output: ......................................
Buffers: shared hit=183
-> Nested Loop (cost=1.13..61621.78 rows=11 width=784) (actual time=0.088..0.629 rows=30 loops=1)
Output: .........................................................
Buffers: shared hit=183
-> Index Scan using idx_digoal_rid_idtype_1 on public.digoal_tbl_refund refund (cost=0.56..10839.91 rows=5945 width=513) (actual time=0.033..0.169 rows=30 loops=1)
Output: .................................................
Index Cond: ((refund.refund_digoal_rid_id = 35018) AND (refund.refund_type = 3))
Buffers: shared hit=32
-> Index Scan using idx_digoal_tbl_task_2 on public.digoal_tbl_task task (cost=0.56..8.53 rows=1 width=271) (actual time=0.014..0.014 rows=1 loops=30)
Output: .........................................................
Index Cond: ((task.digoal_dealid = 2997380888::bigint) AND (task.task_type = 300) AND (task.status = 8) AND (task.biz_id = refund.id))
Buffers: shared hit=151
Planning time: 0.419 ms
Execution time: 0.756 ms
(16 rows)
内表扫描30次，扫描151个BLOCK。(每次访问5个PAGE，root+branch1+branch2+leaf+heap)
create extension pageinspect;
postgres=# select * from bt_metap('idx_digoal_tbl_task_2');
magic | version | root | level | fastroot | fastlevel
--------+---------+-------+-------+----------+-----------
340322 | 2 | 25447 | 3 | 25447 | 3
(1 row)
响应也从7毫秒，降低到了0.7毫秒。
重新压测，性能达到 2万tps。
性能：
tps = 19932.917811 (including connections establishing)
tps = 19934.054737 (excluding connections establishing)
八、索引深度
接着第七个问题，内表每次访问，都是索引访问，那么每次的索引访问需要访问多少个数据块呢？和索引深度有关：
meta page, root page, branch page(optional), leaf page, heap page(optional).
这里索引的深度决定了要访问多少个索引页，有命中时，则需要访问到heap page。
索引深度由索引页内记录数以及整个HEAP表被索引的记录的记录数决定。
原理详见：
《自动选择正确索引访问接口(btree,hash,gin,gist,sp-gist,brin,bitmap...)的方法》
九、partial index
partial index实际上是部分索引，可用来降低索引深度，例如1000万条记录，如果每个索引 BLOCK 可以存放260个ITEM (ctid即行号固定8字节，加上字段本身内容的长度，占一个IDX ITEM的长度)，那么需要3层。
root page(260), branch page(260/root), leaf page(260/branch).
postgres=# select 260*260*260;
?column?
----------
17576000
(1 row)
3层树刚好满足1千多万条记录。
通过降低索引树的层级，在大量LOOP时，可以减少扫描的BLOCK数量。怎么降低层级呢？partial index是一种方法，另一种方法是减少索引字段个数。
比如
Index Cond: ((task.digoal_dealid = 2997380888::bigint) AND (task.task_type = 300) AND (task.status = 8) AND (task.biz_id = refund.id))
原来是多字段复合索引，改成partial index
create index idx on task (biz_id) where digoal_dealid = 2997380888 and task_type = 300 and status = 8;
这样的话被索引的记录变少了，可以直接影响索引层级。
同时索引也从4个字段降到了1个字段，每个IDX ITEM也变短了，一个PAGE可以存储更多的ITEM，因此索引层级再次压缩。
性能再次提升：
Limit (cost=37641.76..37641.76 rows=1 width=784) (actual time=0.174..0.226 rows=10 loops=1)
Output: ..................................
Buffers: shared hit=122
-> Nested Loop (cost=0.86..37641.76 rows=11 width=784) (actual time=0.031..0.222 rows=30 loops=1)
Output: ........................................................
Buffers: shared hit=122
-> Index Scan using idx_digoal_rid_idtype_1 on public.digoal_tbl_refund refund (cost=0.56..10839.91 rows=5945 width=513) (actual time=0.020..0.056 rows=30 loops=1)
Output: ................................................
Index Cond: ((refund.refund_digoal_rid_id = 35018) AND (refund.refund_type = 3))
Buffers: shared hit=32
-> Index Scan using idx on public.digoal_tbl_task task (cost=0.29..4.50 rows=1 width=271) (actual time=0.004..0.004 rows=1 loops=30)
Output: ................................................
Index Cond: (task.biz_id = refund.id)
Buffers: shared hit=90
Planning time: 0.423 ms
Execution time: 0.303 ms
(16 rows)
因为记录数降了，索引层级直接变2级，每次访问3个PAGE(root, leaf, heap)，循环30次仅仅访问了90个BLOCK，达到了极限。
postgres=# select * from bt_metap('idx');
magic | version | root | level | fastroot | fastlevel
--------+---------+------+-------+----------+-----------
340322 | 2 | 3 | 1 | 3 | 1
(1 row)
性能：
tps = 20261.781186 (including connections establishing)
tps = 20263.110009 (excluding connections establishing)
小结
本文通过一个OUTER JOIN的例子，展示了JOIN相关的知识点，涉及内存带宽 , JOIN算法 , FILTER亲和力 , TSP , HINT , 索引扫描顺序与命中率 , 语义转换 , 扫描顺序 , 存储顺序 , 命中率 , 索引深度 , partial index 。
最后通过提高内表命中率，降低索引层级等方法，减少内存访问消耗，性能从300多TPS，提升到了2万多TPS。
更智能的方法是关联分区、TSP算法与数据分区的结合。解决JOIN过滤与亲和, limit的问题。
参考
《关键时刻HINT出彩 - PG优化器的参数优化、执行计划固化CASE》
《自动选择正确索引访问接口(btree,hash,gin,gist,sp-gist,brin,bitmap...)的方法》
