MyException - 我的异常网
当前位置:我的异常网» 互联网 » TB级大表秒级随意维度分析 - 采样估值满足高效TOP N

TB级大表秒级随意维度分析 - 采样估值满足高效TOP N等分析需求

www.MyException.Cn  网友分享于:2013-10-19  浏览:0次
TB级大表秒级任意维度分析 - 采样估值满足高效TOP N等分析需求

原文地址

 

 

标签

 

PostgreSQL , 采样 , sample , TOP N , 统计分析


背景

估值计算是统计学的常用手段。因为数据量庞大,求精确数值需要耗费巨大的资源,而统计分析并不要求完全精确的数据,因此估值计算是一种折中的方法,广泛应用于统计分析场景。

PostgreSQL是一个功能强大的数据库,在估值统计方面,提供了很多方法。

1、PostgreSQL中,求估计的UV,增量UV等(即count distinct),可以通过HLL插件来实现。

《Greenplum 最佳实践 - 估值插件hll的使用(以及hll分式聚合函数优化)》

《PostgreSQL hll (HyperLogLog) extension for "State of The Art Cardinality Estimation Algorithm" - 3》

《PostgreSQL hll (HyperLogLog) extension for "State of The Art Cardinality Estimation Algorithm" - 2》

《PostgreSQL hll (HyperLogLog) extension for "State of The Art Cardinality Estimation Algorithm" - 1》

2、求任意字段的TOP VALUE(包括数组字段的TOP 元素),以及COUNT,可以通过统计信息柱状图得到。

《PostgreSQL pg_stats used to estimate top N freps values and explain rows》

3、求全表记录数可以通过pg_class.reltuples得到。

4、求任意SQL的返回记录数(例如求分页),或者求COUNT(*)的估值(将SQL转换为select 1 from ...即可),可以通过explain的估值得到,例子如下。

《论count与offset使用不当的罪名 和 分页的优化》

5、求多个字段的唯一值个数,可以通过定义自定义统计信息得到非常准确的估值。

《PostgreSQL 10 黑科技 - 自定义统计信息》

6、求带条件的查询的估值,比如某个省的TOP N电影明星,我们可以通过先采样,然后在采样中进行计算的方法得到。

《PostgreSQL 巧妙的数据采样方法》

《PostgreSQL 数据采样与脱敏》

本文将介绍采样估值的方法。

场景设计

之前写过一个场景,是泛内容网站的透视分析,数据量比较庞大,计算全量需要扫描的数据量较大。看看采样的方法是否满足需求?

《音视图(泛内容)网站透视分析 DB设计 - 阿里云(RDS、HybridDB) for PostgreSQL最佳实践》

1、表结构

create table tbl (  
  id int8,  -- 序列    
  tag1 int[],   -- 数组  
  c1 int,       -- 1-100  
  c2 int,       -- 1-10000  
  c3 timestamp   -- 时间戳  
);  

2、生成随机值函数

取值范围$1-$2, 取$3个随机值的数组  
  
create or replace function gen_rand_ints(int, int, int) returns int[] as $$  
  select array(select (random()*($2-$1))::int+$1 from generate_series(1,$3));  
$$ language sql strict;  
  
postgres=# select gen_rand_ints(10,25,5);  
  gen_rand_ints     
------------------  
 {20,19,24,22,21}  
(1 row)  

3、写入测试数据

-- 写入热点数组,5000万条  
insert into tbl select id, gen_rand_ints(1,1000,10), random()*100, random()*10000, clock_timestamp() from generate_series(1,50000000) t(id);  
  
-- 写入非热点数组,1亿条  
insert into tbl select id, gen_rand_ints(1,1000000,10), random()*100, random()*10000, clock_timestamp() from generate_series(1,100000000) t(id);  

数据样式如下

postgres=# select * from tbl limit 10;  
    id    |                   tag1                    | c1 |  c2  |             c3               
----------+-------------------------------------------+----+------+----------------------------  
 38931521 | {424,448,91,420,382,657,677,60,530,503}   | 59 | 6120 | 2017-09-11 14:32:06.610512  
 38931522 | {66,87,468,207,79,780,307,714,520,149}    | 44 | 7848 | 2017-09-11 14:32:06.610522  
 38931523 | {99,628,798,558,415,74,863,839,522,953}   | 26 | 9032 | 2017-09-11 14:32:06.610531  
 38931524 | {610,935,962,140,438,551,752,503,636,220} | 71 | 7136 | 2017-09-11 14:32:06.61054  
 38931525 | {998,16,428,518,164,868,303,263,496,102}  | 82 | 9102 | 2017-09-11 14:32:06.61055  
 38931526 | {175,683,749,696,637,8,599,247,942,561}   | 39 | 3796 | 2017-09-11 14:32:06.610559  
 38931527 | {112,138,882,747,356,591,461,355,605,888} | 87 | 7684 | 2017-09-11 14:32:06.610568  
 38931528 | {756,175,31,252,276,850,162,450,533,910}  | 15 | 1691 | 2017-09-11 14:32:06.610578  
 38931529 | {917,744,416,860,306,801,240,416,937,122} | 16 | 2927 | 2017-09-11 14:32:06.610587  
 38931530 | {712,623,647,317,511,519,86,267,693,116}  | 52 | 9676 | 2017-09-11 14:32:06.610596  
(10 rows)  

求任意条件下的tag1的TOP N元素。

4、分析表,生成柱状图。

postgres=# analyze tbl;  
ANALYZE  

表大小 16 GB。

postgres=# \dt+ tbl  
                   List of relations  
 Schema | Name | Type  |  Owner   | Size  | Description   
--------+------+-------+----------+-------+-------------  
 public | tbl  | table | postgres | 16 GB |   
(1 row)  

5、求某个条件下的精确TOP N元素,实际上有1000个热点ID,所以返回TOP 10的COUNT结果非常近似,后面在使用估值时,得到的TOP 10可能就没这么准了,但是一定是在1000个ID以内的。

-- 开启32个并行的查询时间  
  
postgres=# select unnest(tag1) tag1, count(*) from tbl where c1 between 1 and 10 group by 1 order by 2 desc limit 10;  
 tag1 | count   
------+-------  
  134 | 50935  
  768 | 50915  
  663 | 50876  
  567 | 50821  
  146 | 50821  
  332 | 50814  
  450 | 50807  
  884 | 50789  
   58 | 50781  
  605 | 50774  
(10 rows)  
  
Time: 23441.247 ms (00:23.441)  
  
-- 不开并行的查询时间  
postgres=# select unnest(tag1) tag1, count(*) from tbl where c1 between 1 and 10 group by 1 order by 2 desc limit 10;  
 tag1 | count   
------+-------  
  134 | 50935  
  768 | 50915  
  663 | 50876  
  567 | 50821  
  146 | 50821  
  332 | 50814  
  450 | 50807  
  884 | 50789  
   58 | 50781  
  605 | 50774  
(10 rows)  
  
Time: 154935.686 ms (02:34.936)  

6、求同样条件下的采样TOP N

采样算法参考文章末尾,PostgreSQL内置了2种采样方法,同时支持扩展采样方法,其中有两个内置的扩展采样方法,实际上内置总共有4种采样方法。

使用块级采样(目前采样不支持并行)。

postgres=# select unnest(tag1) tag1, (count(*))*20      -- 乘以100/采样系数  
from   
(select * from tbl TABLESAMPLE system (5)) t     
where c1 between 1 and 10 group by 1 order by 2 desc limit 10;  
 tag1 | ?column?   
------+----------  
  724 |    53380  
  798 |    52680  
   24 |    52640  
  371 |    52480  
  569 |    52400  
  531 |    52280  
  979 |    52160  
  429 |    52140  
  980 |    52080  
  350 |    51920  
(10 rows)  
  
-- 采样5%,约7秒。  
Time: 6887.745 ms (00:06.888)   
  
postgres=# select unnest(tag1) tag1, (count(*))*50    -- 乘以100/采样系数  
from   
(select * from tbl TABLESAMPLE system (2)) t     
where c1 between 1 and 10 group by 1 order by 2 desc limit 10;  
 tag1 | ?column?   
------+----------  
  324 |    55450  
  435 |    55150  
  720 |    55050  
  943 |    54950  
  475 |    54750  
  958 |    54600  
   13 |    54400  
  742 |    54300  
  739 |    54100  
  301 |    53950  
(10 rows)  
  
-- 采样2%, 约3秒。  
Time: 2720.140 ms (00:02.720)  
  
采样越多,精确度越高  

采样的方法,得到的TOP N是很准确的,因为例子用了1000个随机值,并且每个随机值的概率是一样的,如果返回TOP 1000,那就准确无疑了。

大表例子

重新设计热点,总共写入40亿测试数据:

一级热点,1,5亿

二级热点,2-4,5亿

三级热点,5-10,5亿

四级热点,11-30,5亿

普通数据,1-100000,20亿

1、表结构设计

create table tbl1 (  
  id int8,  -- 序列  
  c1 int8,  -- 目标字段  
  c2 int8,  -- 1-100  
  c3 int8,  -- 1-100000  
  c4 timestamp  -- 时间戳  
);  

2、写入测试数据

nohup psql -c "insert into tbl1 select id, 1, random()*100, random()*100000, clock_timestamp() from generate_series(1,500000000) t(id);" >/dev/null 2>&1 &  
nohup psql -c "insert into tbl1 select id, random()*(4-2)+2, random()*100, random()*100000, clock_timestamp() from generate_series(1,500000000) t(id);" >/dev/null 2>&1 &  
nohup psql -c "insert into tbl1 select id, random()*(10-5)+5, random()*100, random()*100000, clock_timestamp() from generate_series(1,500000000) t(id);" >/dev/null 2>&1 &  
nohup psql -c "insert into tbl1 select id, random()*(30-11)+11, random()*100, random()*100000, clock_timestamp() from generate_series(1,500000000) t(id);" >/dev/null 2>&1 &  
nohup psql -c "insert into tbl1 select id, random()*100000, random()*100, random()*100000, clock_timestamp() from generate_series(1,2000000000) t(id);" >/dev/null 2>&1 &  

3、分析表

postgres=# analyze tbl1;  
ANALYZE  
Time: 502.421 ms  

表大小,254 GB。

postgres=# \dt+ tbl1  
                    List of relations  
 Schema | Name | Type  |  Owner   |  Size  | Description   
--------+------+-------+----------+--------+-------------  
 public | tbl1 | table | postgres | 254 GB |   
(1 row)  

4、精确TOP 30

-- 开启32个并行的查询时间  
  
postgres=# select c1,count(*) from tbl1 where c2 between 1 and 10 group by 1 order by 2 desc limit 30;  
 c1 |  count     
----+----------  
  1 | 49991259  
  3 | 25006580  
  2 | 12502559  
  4 | 12498741  
  9 | 10004285  
  6 | 10002597  
  8 |  9999530  
  7 |  9999215  
  5 |  5003219  
 10 |  4998870  
 29 |  2636193  
 18 |  2635457  
 13 |  2635344  
 17 |  2634693  
 26 |  2633965  
 19 |  2633690  
 28 |  2633526  
 14 |  2633512  
 15 |  2633363  
 24 |  2633260  
 20 |  2633014  
 25 |  2632926  
 16 |  2632779  
 22 |  2632508  
 27 |  2632288  
 23 |  2632216  
 21 |  2631443  
 12 |  2631315  
 11 |  1318483  
 30 |  1318451  
(30 rows)  
  
Time: 20845.738 ms (00:20.846)  
  
-- 不开启并行的查询时间  
  
postgres=# select c1,count(*) from tbl1 where c2 between 1 and 10 group by 1 order by 2 desc limit 30;  
  
 c1 |  count     
----+----------  
  1 | 49991259  
  3 | 25006580  
  2 | 12502559  
  4 | 12498741  
  9 | 10004285  
  6 | 10002597  
  8 |  9999530  
  7 |  9999215  
  5 |  5003219  
 10 |  4998870  
 29 |  2636193  
 18 |  2635457  
 13 |  2635344  
 17 |  2634693  
 26 |  2633965  
 19 |  2633690  
 28 |  2633526  
 14 |  2633512  
 15 |  2633363  
 24 |  2633260  
 20 |  2633014  
 25 |  2632926  
 16 |  2632779  
 22 |  2632508  
 27 |  2632288  
 23 |  2632216  
 21 |  2631443  
 12 |  2631315  
 11 |  1318483  
 30 |  1318451  
(30 rows)  
  
Time: 471112.827 ms (07:51.113)  

5、采样TOP 30

select c1,(count(*))*20 from   -- 乘以100/采样系数  
(select * from tbl1 TABLESAMPLE system (5)) t     
where c2 between 1 and 10 group by 1 order by 2 desc limit 30;  
  
 c1 | ?column?   
----+----------  
  1 | 50068840  
  3 | 25108820  
  2 | 12558680  
  4 | 12513080  
  7 | 10009300  
  9 | 10006260  
  6 | 10005400  
  8 |  9987220  
  5 |  5008280  
 10 |  5007980  
 17 |  2652940  
 16 |  2648640  
 25 |  2646800  
 28 |  2646600  
 15 |  2642480  
 20 |  2642220  
 14 |  2641620  
 26 |  2640500  
 23 |  2639420  
 29 |  2637740  
 22 |  2637320  
 13 |  2636900  
 19 |  2636100  
 18 |  2635120  
 24 |  2634440  
 12 |  2631480  
 27 |  2629880  
 21 |  2624940  
 11 |  1330140  
 30 |  1316480  
(30 rows)  
  
Time: 31884.725 ms (00:31.885)  
  
-- 采样5%,约32秒。  
  
select c1,(count(*))*50 from   -- 乘以100/采样系数  
(select * from tbl1 TABLESAMPLE system (2)) t     
where c2 between 1 and 10 group by 1 order by 2 desc limit 30;  
  
 c1 | ?column?   
----+----------  
  1 | 50173200  
  3 | 24993550  
  2 | 12487100  
  4 | 12474100  
  6 |  9998250  
  8 |  9980450  
  7 |  9973950  
  9 |  9960450  
 10 |  4999050  
  5 |  4995000  
 29 |  2642700  
 28 |  2640900  
 16 |  2640300  
 26 |  2630250  
 24 |  2627500  
 23 |  2623700  
 19 |  2622350  
 27 |  2622000  
 18 |  2621200  
 12 |  2619450  
 20 |  2616200  
 17 |  2616050  
 21 |  2615800  
 15 |  2613200  
 22 |  2612200  
 14 |  2607700  
 13 |  2605900  
 25 |  2604150  
 30 |  1312300  
 11 |  1311950  
(30 rows)  
  
Time: 12942.455 ms (00:12.942)  
  
-- 采样2%,约13秒。  
  
postgres=# select c1,(count(*))*1000 from   -- 乘以100/采样系数  
(select * from tbl1 TABLESAMPLE system (0.1)) t     
where c2 between 1 and 10 group by 1 order by 2 desc limit 30;  
 c1 | ?column?   
----+----------  
  1 | 48077000  
  3 | 25061000  
  2 | 12762000  
  4 | 12262000  
  8 |  9851000  
  6 |  9789000  
  7 |  9718000  
  9 |  9654000  
  5 |  4971000  
 10 |  4885000  
 18 |  2731000  
 28 |  2727000  
 29 |  2710000  
 23 |  2697000  
 15 |  2687000  
 27 |  2681000  
 22 |  2672000  
 17 |  2672000  
 25 |  2670000  
 19 |  2637000  
 20 |  2632000  
 12 |  2628000  
 14 |  2628000  
 21 |  2622000  
 26 |  2618000  
 13 |  2601000  
 24 |  2522000  
 16 |  2513000  
 11 |  1406000  
 30 |  1301000  
(30 rows)  
  
Time: 863.604 ms  
  
-- 采样0.1%,约0.86秒。  

OK,采样千分之一的时候(仅需约扫描254MB数据),只花了不到1秒,就算出了准确的TOP 30,而且准确度相当的高。

如果在Greenplum中支持这个功能,会很爽,一万亿的数据,秒级任意维度钻取透视不是梦。

小结

1、采样与精确查询耗时对比

1.1、求数组元素TOP N

查询 表大小 记录数 求TOP N耗时
精确,32并行 16GB 1.5亿 23秒
精确,非并行 16GB 1.5亿 155秒
采样5% 16GB 1.5亿 7秒
采样2% 16GB 1.5亿 3秒

1.2、求scalar类型TOP N

查询 表大小 记录数 求TOP N耗时
精确,32并行 254GB 40亿 21秒
精确,非并行 254GB 40亿 471秒
采样5% 254GB 40亿 32秒
采样2% 254GB 40亿 13秒
采样0.1% 254GB 40亿 0.86秒

2、采样计算达到了很高的精确度,同时耗费资源很少。虽然并行计算也非常快,但是需要消耗更多的CPU和IO资源,并行度就会大打折扣,除非有足够的资源给你折腾,否则能采用估值计算的时候,还是建议估值计算。

3、估值计算的效率评估:

由于目前估值计算不能采用多核并行,处理速度约每秒254MB,那么要达到1秒内的响应,对于254GB的表,采样设置为0.1%,对于1TB的表,可以将采样设置为0.025%)。那么TB级的表,也能实现任意维度秒级估算。

 

原文地址

文章评论

编程语言是女人
编程语言是女人
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
旅行,写作,编程
旅行,写作,编程
代码女神横空出世
代码女神横空出世
如何成为一名黑客
如何成为一名黑客
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
一个程序员的时间管理
一个程序员的时间管理
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
鲜为人知的编程真相
鲜为人知的编程真相
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
10个调试和排错的小建议
10个调试和排错的小建议
 程序员的样子
程序员的样子
总结2014中国互联网十大段子
总结2014中国互联网十大段子
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
为什么程序员都是夜猫子
为什么程序员都是夜猫子
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
中美印日四国程序员比较
中美印日四国程序员比较
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
程序员必看的十大电影
程序员必看的十大电影
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
Java程序员必看电影
Java程序员必看电影
程序员的鄙视链
程序员的鄙视链
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
我是如何打败拖延症的
我是如何打败拖延症的
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员和编码员之间的区别
程序员和编码员之间的区别
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员都该阅读的书
程序员都该阅读的书
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
程序员应该关注的一些事儿
程序员应该关注的一些事儿
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
每天工作4小时的程序员
每天工作4小时的程序员
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
老程序员的下场
老程序员的下场
那些争议最大的编程观点
那些争议最大的编程观点
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
我的丈夫是个程序员
我的丈夫是个程序员
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有