2.1.1　近似查询

近似查询根据技术实现的差别主要分为在线聚合和基于采样的查询两类。在线聚合是基于统计学的采样理论进行近似查询,实时地根据反馈查询结果计算置信区间的过程[3-5]。J.Hellerstein采用了该方法,不仅设置了用户界面,还改变了传统数据库系统中需要长时间才能获取结果的模式[6]。Haas以中心极限原理和间隔公式为基础,实现了具有单表、多表的AVG、COUNT等查询[7],得到置信区间,但该方法存在一定的局限性,它对于空间数据库的效果不太稳定。基于采样的查询方法是通过采样处理预先建立样本集[8]。Joshi针对传统采样技术提出了分层抽样,将分层与贝叶斯框架相结合[9]。X.Meng描述了简单的随机抽样方法,并扩展到分层抽样,在Map Reduce中可以有效地减小中间输出的大小,大大提高负载平衡[10]。Gibbons分析比较了简洁采样和计数抽样方法[11],并提出了快速增量维护技术,该方法在空间数据库中保持元素间的子结构,不能用于空间数据库。Surajif Chaudhuri等人对基于采样的查询进行了详细的理论分析,并提出预先计算的采样方法,弥合了在线和离线的极端性[12]。这一思想是非常有价值的,但在空间查询方面却没有相关的研究成果和现成方案。

实时数据库是早期研究者提出近似查询技术的原因之一,由于短时间内无法反馈精确结果,而采用近似结果以提高处理速度的思想成为查询领域研究的热点。ODGH92针对非聚集查询,提出了基于子集和超集定义模式实现结果的近似[13];Wen-Chi Hou针对实时数据库提出了关联集合的近似查询处理技术[14];Christodoulakis在原型数据库管理系统中提出了一种严格控制聚合关系查询处理时间的算法,称为CASE-DB[15];Vrbsky描述了面向对象的查询处理器,采用了基于近似关系数据模型产生近似结果的框架[16],使得查询更有效率。Barzan Mozafari对近似查询处理的各个方面展开研究,包括不同的采样策略、误差估计机制和数据摘要的构建,重点讲解了面临的挑战和解决对策[17]。(https://www.daowen.com)

国内外研究学者对近似查询的基本原理、实现方法和基本框架展开了一系列讨论[3,4,18]。获取样本数据是近似查询的主流方案,研究学者将其样本数据的获取技术称为数据约简或数据压缩技术。D.Barbara对数据约简技术进行综述,将其分为参数技术和非参数技术,两者的区别在于是否构建模型[19];J.Shanmugasundaram采用了聚类分析技术进行压缩数据方体,将数据看成空间中的点,找到密集区域近似表示cluster,节省数据存储量[20];I.Lazaridis使用了增加节点子树聚集值的多分辨率聚合树的结构完成数据的存储,并逐步按照要求细化,逐步接近精确结果[21];F.Korn则采用了奇异值分解技术对时间序列数据进行交换[22];D.Barbar则采用线性回归技术进行数据建模[23]。D.Margaritis利用了贝叶斯表示数据内在联合概率分布的特点压缩数据[24],对查询生成近似计数。

在近似查询引擎实现方面,Blink DB是基于Shark和Hive所构建的近似查询引擎,是常用的近似查询框架,采用了自适应优化框架和动态样本选择策略,可以在不查询整个数据集的基础上,在规定时间内反馈带有一定误差的结果。S.Agarwal和A.Panda在2012年采用大规模并行的Blink DB框架,扩展了Hive/HDFS堆栈,并且执行各种类型的查询[25]。实验表明,针对存储在100台机器上数据量为50 TB的数据,Blink DB可以执行大范围的查询,其处理速度比Map Reduce上的Hive高出150倍,比Shark快10～150倍,误差范围为2%～10%。2013年,S.Agarwal基于该框架,对部署在多达100个节点的17 TB数据运行点对点(Ad-Hoc)模式的交互式结构化查询(Structured Query Language,SQL)[26],近似查询以误差和时间作为约束条件,在2秒内完成了准确度高达90%～98%的近似查询,上述研究均表明Blink DB框架可以高效地实现近似查询。