Digoal.zhou

Digoal.zhou

公益是一辈子的事, I'm digoal, Just do it.

PostgreSQL OUTER JOIN 优化的几个知识点 - 语义转换、内存带宽、JOIN算法、FILTER亲和力、TSP、HINT、命中率、存储顺序、扫描顺序、索引深度

4 minute read

背景

一个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表被索引的记录的记录数决定。

原理详见：

《深入浅出PostgreSQL B-Tree索引结构》

《PostgreSQL 9种索引的原理和应用场景》

《自动选择正确索引访问接口(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》

《深入浅出PostgreSQL B-Tree索引结构》

《PostgreSQL 9种索引的原理和应用场景》

《自动选择正确索引访问接口(btree,hash,gin,gist,sp-gist,brin,bitmap…)的方法》

《PostgreSQL nestloop/hash/merge join讲解》

Flag Counter

digoal’s 大量PostgreSQL文章入口

You May Also Enjoy

PostgreSQL(PPAS 兼容Oracle) 从零开始入门手册 - 珍藏版

17 minute read

背景 云数据库PPAS版，是阿里云与EnterpriseDB公司(简称EDB)合作基于PostgreSQL高度兼容Oracle语法的数据库服务，为用户提供易于操作的迁移工具，兼容范围涵盖：PL/SQL、数据类型、高级函数、表分区等。 用户可以直接在阿里云购买PPAS进行使用。 如果在购买PPAS前，想试用一下...

PostgreSQL pipelinedb 流计算插件 - IoT应用 - 实时轨迹聚合

1 minute read

背景 IoT场景，车联网场景，共享单车场景，人的行为位点等，终端实时上报的是孤立的位点，我们需要将其补齐成轨迹。 例如共享单车，下单，开锁，生成订单，骑行，关闭订单，关锁。这个过程有一个唯一的订单号，每次上报的位点会包含时间，订单号，位置。 根据订单号，将点聚合为轨迹。 使用pipelinedb插件，可以实...

PostgreSQL datediff 日期间隔（单位转换）兼容SQL用法

2 minute read

背景 使用datediff，对时间或日期相减，得到的间隔，转换为目标单位(日、月、季度、年、小时、秒。。。等)的数值。 DATEDIFF ( datepart, {date|timestamp}, {date|timestamp} ) 周 select datediff(week,'2009-01-0...