感谢MaxCompute混合云owner 赵奕捷(陆东) 提供的项目分享和技术经验。陆东 也是该项目的负责人
项目背景:
XX客户需求，对目标表过去3-6个月内的数据做全量查询，查询条件是针对固定3列的任意组合查询，结果集的数据量一般小于万级别。 客户期望能够将执行结果在20s内返回。
当前难点：客户目标表单日分区的大小: 约500亿条，压缩后逻辑大小在4.7T 左右。 那么3个月的数据则大概在432T，按256M一个split算， 查询约要169万的instance实例，远超过MaxC 最大10万的限制，且会占用大量计算资源， 客户集群的规模在万core级别，接近一整天资源都无法执行返回。
我们的目标：是能够帮助客户将上文提到的“3-6个月内的固定3列组合查询，在20s内返回”。
SA的难处: 目前原始数据在200T以上的简单查询（一个or几个where条件），当前市面可以覆盖性能要求的产品，无法同时支持那么大数据量和客户成本。
如何解决问题：
我们想到数据基于某些列hashcluster聚合或者zorder聚合能力后，再按需计算出每个物理文件指定列的BloomFilter作为海量数据的多列索引文件（BloomFilter文件大小相对于原数据文件大小，几乎可以忽略不计，所以遍历查询BloomFilter非常快）。 相当于数据基于某些列的hashcluster或zorder聚合后，不仅能快速查询指定列（hash，zorder聚合列），还能得到指定bloomfilter的列查询性能收益。 尤其是hash或zorder列 和bloomfilter列有很强的业务相关性时
先介绍下什么是bloomfilter:
Question1：
假设一个Int占4字节，那20亿个连续Int，占用的空间约为
(2000000000*4/1024/1024/1024)≈7.45GB
有什么办法可以用小一个数量级的空间存储这20亿个数字呢？
A:如果按位存储就不一样了，20亿个连续Int，占用空间约为
(2000000000/8/1024/1024/1024)≈0.233G
怎么存? bitmap
比如要表示{1,2,4,6} 用连续8个bit ，分别将 index 1，2，4，6位 设置成1 就可以存储，并快速查询了。 （如果有重复？ 怎么办）
21亿 差不多就是正整数int（2^31）的范围。这样想下，正整数范围内，给定任意长度数组。 用bitmap做排序的话 使用0.233G的空间，可以做到O(N)的时间复杂度。 而快排 ，归并，堆排之类的时间复杂度都在O(NlogN)
用处: 很多，高效排序，去重，查询。 这里额外说下数据库的位图索引。
假设某个地域的人口基本信息表，是1000万条记录的表 ， 主要字段为"姓，名，性别，婚姻状态，区，年龄" 。比如要查询 "男并且已婚 and babala"，用bitmap做索引可以做成
2个向量
3个向量
将 男向量 和 已婚向量 与下 ，就能得出“男并且已婚”
位图索引两个优势，1）用很小空间就能知道所有行， 这两个列的状态 ，不需要访问数据 2）求交集的时候 ，不需要两层循环，时间复杂度 从O(n方) 降到 O(N)
Question2:
假设一个爬虫程序，你可能会爬到重复的网页，（网页间错综复杂有无限循环），为了避免，需要知道 每次访问的页面 之前是否已经爬过?
比较高效的方法的 建立一个宽 bitmap 。 每个URL经过一个哈希函数映射到某一bit位。这样基本就能用O(1) 的效率来查询了。 但问题是，随着爬得urls的数量越多，hash冲突的概率就越高。
若要降低冲突发生的概率到1%，现有的hash算法 ，需要要将BitSet的长度设置为URL个数的100倍。
假设一亿条URL(ndv)，就得把BitSet长度设为100亿（将近1G多空间) 。
对于Q2的解法 是BloomFilter
url的字符串str，分别计算h（1，str），h（2，str）…… h（k，str）。然后分别将BitSet的第h（1，str）、h（2，str）…… h（k，str）位设为1
- 若一个字符串对应的Bit不全为1，则可以肯定该字符串一定没有被Bloom Filter记录过。（这是显然的，因为字符串被记录过，其对应的二进制位肯定全部被设为1了）
- 但是若一个字符串对应的Bit全为1，也有小概率是未被记录过的。 （如果我的bit够小，那hash冲突的概率很高）
为了降低冲突率，所以需要了解bloomfilter的参数
m ： BitSet 位数
n ： 插入字符串个数
k ：hash函数个数
当然，哈希函数也是影响的重要因素 （其实可以通过一些机器学习的手段，找出冲突概率最小的几种模型，用于实战）
从表格来看 m/n越大越准，k越大越准。 基本上 有2，3个hash函数， BitSet位数，是插入个数的2倍，就可以将冲突率降低到1%以下， 而上文提到hashmap是需要100倍才可以将冲突率降到1%
冲突率的公式:
再介绍什么是zorder:
Z-Order是一个空间填充曲线，用于把多维数据映射到一维数据上，并且尽可能得保持映射前后的相邻位置关系（locality），也就是说多维空间上相邻的点在一维的线上仍然是相邻的
eg：上图中我要访问x = 0, y = 0、x = 1, y = 0、 x = 0, y = 1 和 x = 1, y = 1 （右图的0，1，2，3）四个数据
- 在Zorder（y，x）排序里，走一个之字形，连续3步访问4点就可以访问全(下图左)
- 在传统按y，x排序，需要9步10个点才可以访问全(下图右)
- 想象下地理位置： 经纬度相近的点，在物理上更靠近的存储，应用中访问更高效。
最终使用BloomFilter+Zorder的方案
如模拟客户表接口, 假定客户user表的userid，作为hashcluster聚合，再指定user的电话号，和 门牌地址码（以上数据均为测试模拟数据） 作为BloomFilter建。 在500亿级别的数据中，指定user 的电话号，或者 按地址查询user,都能秒级返回结果。 因为通过userid hash聚合已经将user按相同userid打散存放在对应hash分桶的物理文件中。
此时通过电话号查询，电话号和user基本是N对1关系（通常N比较小，一个人拥有2,3个电话号），通过电话号的bloomfilter文件过滤出来的真实表物理文件也只有1个（对应userid所在的hash分桶的文件），故查询非常快。
此时通过门牌地址查询，门牌地址和user基本是1对N（且通常N<10，一个地址被几个家庭成员所共享），所以maxcompute最多会启动N个slot去查询，对于maxcompute这样的分布式系统，并发查10个文件是非常快，且占用资源量非常低的。
同样场景如果不做hash聚合或者bloomfilter, 会有两个大劣势：
1）查询电话号码或地址，要去500亿记录的每个物理文件中查询，据上文陈述，这里需要启动169万个slot。相比上面例子的1个 和 N个。差了很多个数据量级
2）如果只做hash聚合不做bloomfilter，那除hash列其他列无查询收益。依然会启动169万个slot。
测试: 模拟单分区60E条 ，针对local_num,id_card, add_num 3列的组合查询 ,每条数据15列包含前3列，大小在0.4k左右，总大小3T。
local号码（电话）、id_card（userid） 组合成zorder聚合 ； local_num（电话）,id_card（userid), add_num（地址）3列分别都设置成BloomFilter
测试如下查询query（测试数据均为模拟数据）
Q1: select * from test_final where local_num='13000002444’;
Q2: select * from test_final where add_num='13000002915’;
Q3: select * from test_final where id_card='130000024443141592’;
Q4: select * from test_final where local_num='13000002444' and add_num='13000002915’;
Q5: select * from test_final where local_num='13000002444' and add_num='13000002915' and id_card='130000024443141592';
能看到其查询性能差异显著甚至是2个数量级的
