PG中文社区 /
mdi-home
首页 社区新闻 中文文档 加入ACE {{ item.text }} 登录
mdi-home 首页 mdi-chat-processing 社区新闻 mdi-book-open-variant 中文文档 mdi-account-multiple-check 加入ACE mdi-file-multiple-outline 相关资料 mdi-blank {{item.text}} mdi-exit-to-app 退出账号
用PostgreSQL找回618秒逝去的青春 - 递归收敛优化

原作者:digoal/德哥  创作时间:2016-12-01 13:10:48+08  
doudou586 发布于2016-12-06 13:10:48           评论: 1   浏览: 5611   顶: 763  踩: 760 

用PostgreSQL找回618秒逝去的青春 - 递归收敛优化

作者: digoal

日期: 2016-12-01

标签: PostgreSQL , 少量not in大量 , 收敛优化 , 递归优化 , 收敛查询优化 select (300 ids) not in (select ids from 300万)


背景

有一个这样的场景,一张小表A,里面存储了一些ID,大约几百个。(比如说巡逻车辆ID,环卫车辆的ID,公交车,微公交的ID)。

另外有一张日志表B,每条记录中的ID是来自前面那张小表的,但不是每个ID都出现在这张日志表中,比如说一天可能只有几十个ID会出现在这个日志表的当天的数据中。 (比如车辆的行车轨迹数据,每秒上报轨迹,数据量就非常庞大)。

那么我怎么快速的找出今天没有出现的ID呢。(哪些巡逻车辆没有出现在这个片区,是不是偷懒了?哪些环卫车辆没有出行,哪些公交或微公交没有出行)?

select id from A where id not in (select id from B where time between ? and ?);

这个QUERY会很慢,有什么优化方法呢?

当然,你还可以让车辆签到的方式来解决这个问题,但是总有未签到的,或者没有这种设计的时候,那么怎么解决呢?

优化方法

其实方法也很精妙,和我之前做的两个CASE很相似。

《时序数据合并场景加速分析和实现 - 复合索引,窗口分组查询加速,变态递归加速》

《distinct xx和count(distinct xx)的变态递归优化方法 - 索引收敛(skip scan)扫描》

在B表中,其实ID的值是很稀疏的,只是由于是流水,所以总量大。

优化的手段就是对B的取值区间,做递归的收敛查询,然后再做NOT IN就很快了。

例子

建表

create table a(id int primary key, info text);

create table b(id int primary key, aid int, crt_time timestamp);
create index b_aid on b(aid);

插入测试数据

-- a表插入1000条
insert into a select generate_series(1,1000), md5(random()::text);

-- b表插入500万条,只包含aid的500个id。
insert into b select generate_series(1,5000000), generate_series(1,500), clock_timestamp();

优化前的性能

\timing

explain (analyze,verbose,timing,costs,buffers) select * from a where id not in (select aid from b); 

                                          QUERY PLAN            
----------------------------------------------------------------------------------------------------
 Seq Scan on public.a  (cost=0.00..67030021.50 rows=500 width=37) 
                       (actual time=2932.080..618776.881 rows=500 loops=1)
   Output: a.id, a.info
   Filter: (NOT (SubPlan 1))
   Rows Removed by Filter: 500
   Buffers: shared hit=27037, temp read=4264454 written=8545
   SubPlan 1
     ->  Materialize  (cost=0.00..121560.00 rows=5000000 width=4) 
                      (actual time=0.002..298.049 rows=2500125 loops=1000)
           Output: b.aid
           Buffers: shared hit=27028, temp read=4264454 written=8545
           ->  Seq Scan on public.b  (cost=0.00..77028.00 rows=5000000 width=4) 
                                     (actual time=0.009..888.427 rows=5000000 loops=1)
                 Output: b.aid
                 Buffers: shared hit=27028
 Planning time: 0.969 ms
 Execution time: 618794.299 ms
(14 rows)
另外你有一种选择是使用outer join, b表同样需要全扫一遍,有很大的改进,不过还可以更好,继续往后看。

postgres=# explain (analyze,verbose,timing,costs,buffers) 
                    select a.id from a left join b on (a.id=b.aid) where b.* is null;
                                       QUERY PLAN                             
----------------------------------------------------------------------------------------------------
 Hash Right Join  (cost=31.50..145809.50 rows=25000 width=4) 
                  (actual time=2376.777..2376.862 rows=500 loops=1)
   Output: a.id
   Hash Cond: (b.aid = a.id)
   Filter: (b.* IS NULL)
   Rows Removed by Filter: 5000000
   Buffers: shared hit=27037
   ->  Seq Scan on public.b  (cost=0.00..77028.00 rows=5000000 width=44) 
                             (actual time=0.012..1087.997 rows=5000000 loops=1)
         Output: b.aid, b.*
         Buffers: shared hit=27028
   ->  Hash  (cost=19.00..19.00 rows=1000 width=4) (actual time=0.355..0.355 rows=1000 loops=1)
         Output: a.id
         Buckets: 1024  Batches: 1  Memory Usage: 44kB
         Buffers: shared hit=9
         ->  Seq Scan on public.a  (cost=0.00..19.00 rows=1000 width=4) 
                                   (actual time=0.010..0.183 rows=1000 loops=1)
               Output: a.id
               Buffers: shared hit=9
 Planning time: 0.302 ms
 Execution time: 2376.934 ms
(18 rows)
递归收敛优化后的性能

explain (analyze,verbose,timing,costs,buffers) 
select * from a where id not in 
(
with recursive skip as (  
  (  
    select min(aid) aid from b where aid is not null  
  )  
  union all  
  (  
    select (select min(aid) aid from b where b.aid > s.aid and b.aid is not null)   
      from skip s where s.aid is not null  
  )  -- 这里的where s.aid is not null 一定要加,否则就死循环了.  
)   
select aid from skip where aid is not null
);

                                           QUERY PLAN 
------------------------------------------------------------------------------------------------
 Seq Scan on public.a  (cost=54.98..76.48 rows=500 width=37) 
                       (actual time=10.837..10.957 rows=500 loops=1)
   Output: a.id, a.info
   Filter: (NOT (hashed SubPlan 5))
   Rows Removed by Filter: 500
   Buffers: shared hit=2012
   SubPlan 5
     ->  CTE Scan on skip  (cost=52.71..54.73 rows=100 width=4) 
                           (actual time=0.042..10.386 rows=500 loops=1)
           Output: skip.aid
           Filter: (skip.aid IS NOT NULL)
           Rows Removed by Filter: 1
           Buffers: shared hit=2003
           CTE skip
             ->  Recursive Union  (cost=0.46..52.71 rows=101 width=4) 
                                  (actual time=0.037..10.104 rows=501 loops=1)
                   Buffers: shared hit=2003
                   ->  Result  (cost=0.46..0.47 rows=1 width=4) (actual time=0.036..0.036 rows=1 loops=1)
                         Output: $1
                         Buffers: shared hit=4
                         InitPlan 3 (returns $1)
                           ->  Limit  (cost=0.43..0.46 rows=1 width=4) (actual time=0.031..0.032 rows=1 loops=1)
                                 Output: b_1.aid
                                 Buffers: shared hit=4
                                 ->  Index Only Scan using b_aid on public.b b_1  (cost=0.43..131903.43 rows=5000000 width=4) 
                                                                                    (actual time=0.030..0.030 rows=1 loops=1)
                                       Output: b_1.aid
                                       Index Cond: (b_1.aid IS NOT NULL)
                                       Heap Fetches: 1
                                       Buffers: shared hit=4
                   ->  WorkTable Scan on skip s  (cost=0.00..5.02 rows=10 width=4) (actual time=0.019..0.019 rows=1 loops=501)
                         Output: (SubPlan 2)
                         Filter: (s.aid IS NOT NULL)
                         Rows Removed by Filter: 0
                         Buffers: shared hit=1999
                         SubPlan 2
                           ->  Result  (cost=0.47..0.48 rows=1 width=4) (actual time=0.018..0.018 rows=1 loops=500)
                                 Output: $3
                                 Buffers: shared hit=1999
                                 InitPlan 1 (returns $3)
                                   ->  Limit  (cost=0.43..0.47 rows=1 width=4) (actual time=0.017..0.017 rows=1 loops=500)
                                         Output: b.aid
                                         Buffers: shared hit=1999
                                         ->  Index Only Scan using b_aid on public.b  (cost=0.43..66153.48 rows=1666667 width=4) 
                                                                                     (actual time=0.017..0.017 rows=1 loops=500)
                                               Output: b.aid
                                               Index Cond: ((b.aid > s.aid) AND (b.aid IS NOT NULL))
                                               Heap Fetches: 499
                                               Buffers: shared hit=1999
 Planning time: 0.323 ms
 Execution time: 11.082 ms
(46 rows)

采用收敛查询优化后,耗时从最初的 618794毫秒 降低到了 11毫秒 ,感觉一下子节约了好多青春。

pg_bot_banner.jpg


评论:1   浏览: 5611                   顶: 763  踩: 760 

请在登录后发表评论,否则无法保存。

1# __ xiaowu 回答于 2024-04-22 09:34:26+08
团员自我小结:https://www.nanss.com/gongzuo/2576.html 期中总结:https://www.nanss.com/xuexi/2881.html 出去玩的文案短句朋友圈:https://www.nanss.com/wenan/2399.html 大熊猫作文:https://www.nanss.com/xuexi/2883.html 车位租赁合同:https://www.nanss.com/shenghuo/2772.html 会议纪要:https://www.nanss.com/gongzuo/2640.html 预备党员半年总结:https://www.nanss.com/xuexi/2992.html 高中周记300字:https://www.nanss.com/xuexi/2961.html 超级温柔的神仙句子:https://www.nanss.com/yulu/2722.html 疫情防控心得体会:https://www.nanss.com/gongzuo/3001.html 个人思想汇报:https://www.nanss.com/xuexi/2697.html 红楼梦读后感:https://www.nanss.com/xuexi/2757.html 作文300字:https://www.nanss.com/xuexi/2848.html 运动会口号:https://www.nanss.com/xuexi/2432.html 学习总结:https://www.nanss.com/xuexi/2908.html 教学工作反思:https://www.nanss.com/xuexi/2803.html 跑步文案短句干净:https://www.nanss.com/wenan/1636.html 撤诉申请书:https://www.nanss.com/shenghuo/2927.html 读后感500字:https://www.nanss.com/xuexi/2942.html 生日赠言古风八个字:https://www.nanss.com/shenghuo/2525.html 妇产科工作总结:https://www.nanss.com/gongzuo/2588.html 雷锋作文:https://www.nanss.com/xuexi/2177.html 给同学的一封信:https://www.nanss.com/xuexi/2948.html 形容自己又大了一岁生日感慨:https://www.nanss.com/wenan/2228.html 班主任寄语:https://www.nanss.com/gongzuo/2691.html 整改方案:https://www.nanss.com/gongzuo/2699.html 支部委员会会议记录:https://www.nanss.com/gongzuo/2621.html 令我难忘的一件事:https://www.nanss.com/xuexi/2836.html 母亲作文:https://www.nanss.com/xuexi/2959.html 日记300字:https://www.nanss.com/xuexi/2941.html



发表评论:
加入我们
QQ群1:5276420
QQ群2:3336901
QQ群3:254622631
文档群:150657323
文档翻译平台:按此访问
社区邮件列表:按此订阅
商业支持
扫码关注
加入我们
QQ群1:5276420
QQ群2:3336901
QQ群3:254622631
文档群:150657323
文档翻译平台:按此访问
社区邮件列表:按此订阅
商业支持
扫码关注
© PostgreSQL中文社区 ... (自2010年起)