-
Notifications
You must be signed in to change notification settings - Fork 51
distinct
muyannian edited this page Mar 15, 2013
·
15 revisions
1.将每个值转换为整形，目前是通过crc32,但目的是能将数据打散的均匀。
2.将crc32的值进行抽样,存储到hashset中。
3.使用局部的haseset来估算整体。
下面为海狗中的使用示例
最基本的使用 ./bluewhale higo sql "\" select count(empty_l),dist(alipay_direct_amt),dist(is_3c) from rpt_p4padhoc_cust where thedate range '20130201,20130220' limit 0,40 \"" Running: select count(empty_l),dist(alipay_direct_amt),dist(is_3c) from rpt_p4padhoc_cust where thedate range '20130201,20130220' limit 0,40 totalRecords:1 count(empty_l) dist(alipay_direct_amt) dist(is_3c) ***24374 148224.0 2.0 times taken 4 seconds 来个复杂点的 bash-3.2$ ./bluewhale higo sql "\" select thedate,count(empty_l),dist(alipay_direct_amt),dist(is_3c) from rpt_p4padhoc_cust where thedate range '20130201,20130220' group by thedate limit 0,40 \"" Running: select thedate,count(empty_l),dist(alipay_direct_amt),dist(is_3c) from rpt_p4padhoc_cust where thedate range '20130201,20130220' group by thedate limit 0,40 totalRecords:20 thedate count(empty_l) dist(alipay_direct_amt) dist(is_3c) 20130201 **54258 *6*36.0 2.0 20130202 **54506 *2*37.0 2.0 20130203 **54678 *9*56.0 2.0 20130204 **54843 *6*46.0 2.0 20130205 **55023 *3*00.0 2.0 20130206 **55166 *0*99.0 2.0 20130207 **55297 *5*9.0 2.0 20130208 **55415 *8*7.0 2.0 20130209 **55474 *2*6.0 2.0 20130210 **55551 *9*0.0 2.0 20130211 **55655 *0*3.0 2.0 20130212 **55809 *5*0.0 2.0 20130213 **55997 *1*56.0 2.0 20130214 **56145 *5*83.0 2.0 20130215 **56368 *8*82.0 2.0 20130216 **56737 *5*78.0 2.0 20130217 **57801 *8*01.0 2.0 20130218 **58805 *3*12.0 2.0 20130219 **59845 *4*74.0 2.0 20130220 1361001 *8*93.0 2.0 times taken 2 seconds 按照省的 bash-3.2$ ./bluewhale higo sql "\" select prov,count(empty_l),dist(alipay_direct_amt),dist(prov),dist(city) from rpt_p4padhoc_cust where thedate range '20130201,20130220' group by prov limit 0,40 \"" Running: select prov,count(empty_l),dist(alipay_direct_amt),dist(prov),dist(city) from rpt_p4padhoc_cust where thedate range '20130201,20130220' group by prov limit 0,40 totalRecords:36 prov count(empty_l) dist(alipay_direct_amt) dist(prov) dist(city) _ *77**0 *55.0 1.0 1.0 上海 *19**77 *3400.0 1.0 1.0 云南省 *22**1 *420.0 1.0 16.0 内蒙古自治区 *0257 956.0 1.0 12.0 北京 **33323 *8675.0 1.0 1.0 台湾省 **34 *6.0 1.0 22.0 吉林省 **023 *865.0 1.0 9.0 四川省 **4638 *812.0 1.0 21.0 天津 **3930 *060.0 1.0 1.0 宁夏回族自治区 *1830 242.0 1.0 5.0 安徽省 **6278 *320.0 1.0 17.0 山东省 **0588 *4635.0 1.0 17.0 山西省 **536 *044.0 1.0 11.0 广东省 **04653 *4576.0 1.0 21.0 广西壮族自治区 **6561 *529.0 1.0 14.0 新疆维吾尔自治区 *5886 881.0 1.0 18.0 江苏省 **04074 *9993.0 1.0 13.0 江西省 **7868 *096.0 1.0 11.0 河北省 **8196 *480.0 1.0 11.0 河南省 **1900 *316.0 1.0 18.0 浙江省 **67889 *3800.0 1.0 11.0 海南省 **504 *68.0 1.0 20.0 海外 **311 *335.0 1.0 1.0 湖北省 **2981 *796.0 1.0 17.0 湖南省 **7559 *883.0 1.0 14.0 澳门特别行政区 *267 34.0 1.0 2.0 甘肃省 **847 *22.0 1.0 14.0 福建省 **69715 *9638.0 1.0 9.0 西藏自治区 *765 115.0 1.0 7.0 贵州省 **567 *43.0 1.0 9.0 辽宁省 **0806 *416.0 1.0 14.0 重庆 **9921 *824.0 1.0 1.0 陕西省 **0812 *496.0 1.0 10.0 青海省 **83 *16.0 1.0 8.0 香港特别行政区 *986 55.0 1.0 3.0 黑龙江省 *07418 1541.0 1.0 13.0 times taken 3 seconds 在来个复杂点的 ./bluewhale higo sql "\" select prov,count(empty_l) as cnt,dist(custid) as cid,dist(prov) as pro,dist(city) as city from rpt_p4padhoc_cust where thedate range '20130201,20130220' group by prov order by city desc limit 0,40 \"" Running: select prov,count(empty_l) as cnt,dist(custid) as cid,dist(prov) as pro,dist(city) as city from rpt_p4padhoc_cust where thedate range '20130201,20130220' group by prov order by city desc limit 0,40 totalRecords:36 prov cnt cid pro city 台湾省 *534 *35.0 1.0 22.0 四川省 *44638 *5124.0 1.0 21.0 广东省 *104653 *54304.0 1.0 21.0 海南省 *9504 *955.0 1.0 20.0 新疆维吾尔自治区 45886 2401.0 1.0 18.0 河南省 *31900 *6568.0 1.0 18.0 安徽省 *66278 *7625.0 1.0 17.0 山东省 *90588 *5152.0 1.0 17.0 湖北省 *52981 *7164.0 1.0 17.0 云南省 *22941 *260.0 1.0 16.0 广西壮族自治区 *96561 9624.0 1.0 14.0 湖南省 *37559 *9664.0 1.0 14.0 甘肃省 *6847 *560.0 1.0 14.0 辽宁省 *00806 *5448.0 1.0 14.0 江苏省 *404074 *17504.0 1.0 13.0 黑龙江省 *07418 5812.0 1.0 13.0 内蒙古自治区 *0257 2626.0 1.0 12.0 山西省 *7536 *896.0 1.0 11.0 江西省 *77868 *3307.0 1.0 11.0 河北省 *88196 *2272.0 1.0 11.0 浙江省 *867889 *33472.0 1.0 11.0 陕西省 *40812 *332.0 1.0 10.0 吉林省 *6023 *532.0 1.0 9.0 福建省 *669715 *2160.0 1.0 9.0 贵州省 *5567 *097.0 1.0 9.0 青海省 *283 *36.0 1.0 8.0 西藏自治区 *765 256.0 1.0 7.0 宁夏回族自治区 *1830 624.0 1.0 5.0 香港特别行政区 *986 359.0 1.0 3.0 澳门特别行政区 *267 67.0 1.0 2.0 _ *77450 *1576.0 1.0 1.0 上海 *198277 *06688.0 1.0 1.0 北京 *633323 *2016.0 1.0 1.0 天津 *83930 *964.0 1.0 1.0 海外 *9311 *849.0 1.0 1.0 重庆 *59921 *888.0 1.0 1.0 times taken 5 seconds 多个列的情形 ./bluewhale higo sql "\" select prov,city,count(empty_l) as cnt,dist(custid) as cid from rpt_p4padhoc_cust where thedate range '20130201,20130220' group by prov,city order by cid desc limit 0,40 \"" Running: select prov,city,count(empty_l) as cnt,dist(custid) as cid from rpt_p4padhoc_cust where thedate range '20130201,20130220' group by prov,city order by cid desc limit 0,40 totalRecords:393 prov city cnt cid 广东省 广州市 *116213 *49312.0 上海 上海市 *198277 *06688.0 广东省 深圳市 *966038 *6768.0 北京 北京市 *633323 *2016.0 浙江省 杭州市 *632057 *7792.0 浙江省 金华市 *008819 *3504.0 _ _ *77450 *1576.0 江苏省 苏州市 *42152 *4169.0 福建省 泉州市 *54617 *1265.0 浙江省 嘉兴市 *95311 *8225.0 广东省 东莞市 *81284 *7686.0 浙江省 温州市 *19859 *3630.0 福建省 莆田市 *15188 *1448.0 四川省 成都市 *07932 *9390.0 湖北省 武汉市 *78516 *8516.0 广东省 佛山市 *57025 *8486.0 湖南省 郴州市 *42621 *8188.0 浙江省 台州市 *80656 *7284.0 浙江省 宁波市 *19761 *6201.0 河南省 郑州市 *05171 *5112.0 江苏省 南通市 *86953 *3998.0 江苏省 南京市 *89873 *3921.0 广东省 中山市 *73193 *2864.0 福建省 厦门市 *28397 *1956.0 福建省 福州市 *18773 *1131.0 江苏省 徐州市 *13849 *0009.0 山东省 青岛市 *85912 *441.0 天津 天津市 *83930 *964.0 广东省 汕头市 *75460 *821.0 河北省 邢台市 *77557 *648.0 湖南省 长沙市 *59106 *954.0 重庆 重庆市 *59921 *888.0 河北省 保定市 *50348 *637.0 河北省 石家庄市 *52024 *438.0 江苏省 无锡市 *50836 *348.0 浙江省 绍兴市 *42036 *059.0 山东省 济南市 *49028 *046.0 安徽省 合肥市 *39657 *972.0 江苏省 扬州市 *31576 *593.0 广东省 揭阳市 *29265 *519.0 times taken 6 seconds 对查询速度影响 bash-3.2$ ./bluewhale higo sql "\" select count(empty_l) as cnt,dist(custid) as cid from rpt_p4padhoc_product where thedate range '20130201,20130228' limit 0,40 \"" Running: select count(empty_l) as cnt,dist(custid) as cid from rpt_p4padhoc_product where thedate range '20130201,20130228' limit 0,40 totalRecords:1 cnt cid *1*****7 ****4374 times taken 26 seconds bash-3.2$ ./bluewhale higo sql "\" select count(empty_l) as cnt from rpt_p4padhoc_product where thedate range '20130201,20130228' limit 0,40 \"" Running: select count(empty_l) as cnt from rpt_p4padhoc_product where thedate range '20130201,20130228' limit 0,40 totalRecords:1 cnt 411697758 times taken 3 seconds ./bluewhale higo sql "\" select count(empty_l) as cnt,sum(e_alipay_direct_amt) from rpt_p4padhoc_product where thedate range '20130201,20130228' limit 0,40 \"" Running: select count(empty_l) as cnt,sum(e_alipay_direct_amt) from rpt_p4padhoc_product where thedate range '20130201,20130228' limit 0,40 totalRecords:1 cnt sum(e_alipay_direct_amt) **1*****8 ****4464 times taken 11 seconds
关于计算精度的精度 请参见excel做的测试，10万个bit，能达到99%的精度 精度
有必要贴下实现的伪代码，供参考
public class DistinctCountExample {
public static void main(String[] args) {
run(1000);
run(10000);
run(100000);
run(1000000);
run(10000000);
}
public static void run(int uniq)
{
for(int j=1;j<10;j++)
{
DistinctCount dc=new DistinctCount();
dc.setMaxUniqSize(10000);
for(int i=0;i<uniq*j;i++)
{
dc.set("test_bit_"+i);
}
long uv=dc.getValue();
int rate=(int) (Math.abs(uv-(uniq*j))*1000/(uniq*j));
System.out.println("近似值："+uv+",真实值:"+(uniq*j)+",误差：千分之"+rate);
}
}
}