间隔查询作为重要的查询类型, 在多个领域得到广泛应用, 如信息检索领域查找某个时间内所有Web文档的所有版本.Web文档在不断更新, 因而网络爬虫在不同时刻抓取到的Web文档不同, 相邻的2次抓取时间形成一个间隔, 构成文档的一个版本.图 1给出仅有1个版本的6篇文档, 现在查找“时间间隔q内的所有Web文档的所有版本”.由于网络爬虫仅记录Web文档的抓取时间, 间隔信息是隐含的, 且间隔查询有别于范围查询, 研究间隔查询优化技术是一件有趣且富有挑战的事情.而随着间隔数据增多, 间隔查询负载增大, 实时地响应间隔查询的任务更加艰巨.

为了高效处理间隔查询, 多种集中式/分布式索引和检索算法被提出.现代技术的发展使得集中式索引已不能满足快速增长的间隔数据的存储和检索需求, 基于分布式系统(如Bigtable^[1], HBase^[2], PNUTS^[3], Cassandra^[4], Dynamo^[5]等)的分布式间隔索引能够适应海量实时间隔数据的需求而成为研究热点.尽管分布式间隔索引能够高效地响应单个间隔查询, 但是当海量间隔查询急速到来时, 超过70%^[6]的用户不能在期望时间内得到反馈, 这正是本文所关注的问题.

图 2展示了单台服务器中查询负载对查询响应时间的影响^[6].

图 2中, PA_r为真实情况下查询负载的峰值, PA_e为服务器处理能力的峰值, PR_r为实际最长响应时间, PR_e为用户期望的最长响应时间.t₁时刻前, 服务器的处理能力大于查询到来的速度, 服务器能够很快响应查询; t₁时刻之后到来的查询数超过服务器的处理能力, 此时查询在队列中累积, t₃时刻, 队列中累积的查询最多, 查询的平均响应时间最长, 远远超过用户期望的响应时间PR_e; t₃之后到来的查询数小于服务器的处理能力, 查询的响应时间下降, 直到t₂时刻查询的响应时间才符合用户期望.t₁到t₂范围内提交的查询均不能在期望时间内得到反馈.

产生这种现象的主要原因是, 服务器采用每次处理一个(one-by-one)的方式处理间隔查询.当大量查询到来时, 查询需要排队以等待服务器响应查询, 查询等待时间在查询响应时间占更大比例.同时, 间隔查询属于数据密集型任务, 涉及频繁的数据访问和网络通信.One-by-One的处理模式需要多次访问相同的数据并传递到客户端, 浪费磁盘I/O和网络资源, 严重影响查询的检索性能.

为了减少查询等待时间、避免重复访问和传递相同的数据, 本文提出共享执行策略优化间隔查询的方法SESIQ (shared execution strategy for interval queries), 解决分布式间隔索引不能适应单点上的高并发间隔查询的问题.SESIQ的思想是:服务器采用每次处理一组(group-by-group)的方式处理接收到的查询, 通过复用一组查询间的公共操作, 从而减少查询的响应时间, 提高服务器响应查询的能力.SESIQ面临的挑战在于分析一组间隔查询间可共享的操作, 生成全局访问计划并执行.本文主要有3点贡献.

(1) 首次采用共享执行策略优化间隔查询.本文从查询特性出发, 首次提出基于共享执行策略的间隔查询优化技术SESIQ.SESIQ和基于索引技术优化间隔查询的方法是正交的, 以已有的索引结构为基础, 进一步优化间隔查询;

(2) 设计并实现了SESIQ引擎, 给出关键技术的算法实现和时空开销分析.SESIQ引擎能够分析一组查询间的特性, 为该组查询建立全局访问计划并执行, 从而减少重复数据的访问和网络通信开销, 降低响应时间.本文给出了详细的算法实现阐述SESIQ批量处理间隔查询的过程.同时, 提供了形式化方法分析SESIQ的性能收益以及空间开销;

(3) 实验证明共享执行策略的有效性和高效性.基于真实数据集的大量实验评估表明:SESIQ是有效且高效的, 共享执行策略能够显著提升检索性能, 间隔查询的响应时间降低数十倍.

1 问题阐述

以一维间隔查询为例, 阐述本文要解决的问题, 多维间隔查询可以从一维间隔查询扩展后获得.本节给出间隔的表示方法并探索两个间隔间的关系, 提出间隔查询、范围查询和覆盖查询的形式化描述, 分析三者之间的关联, 最后定义间隔查询间的共享关系.

定义1(间隔).对于一维间隔, 本文给出两种不同表示.间隔I可以由起始点begin和终止点end确定(begin≤end), 标记I=[begin, end], 如图 1(a)所示; 也可以由二维空间中的二维点I(begin, end)表示, 这个二维空间由起始维和终止维构成, begin位于起始维, end位于终止维, 如图 1(b)所示.由于begin≤end, 间隔数据仅分布在有颜色填充的等腰直角三角形区域.

定义2(间隔间的关系).依据间隔端点之间的关系, 定义间隔I=[begin, end]和间隔q=[a, b]的5种关系, 分别为覆盖、左相交、右相交、包含和不相交, I和q具有前4种关系的任一种, 均表明I和q是相交的.

(1) 覆盖:如果begin≤a且end≥b, 则称I覆盖q;

(2) 左相交:如果begin≥a且begin≤b, 即I的左边部分在q范围内, 则称I左相交q;

(3) 右相交:如果end≥a且end≤b, 即I的右边部分在q范围内, 则称I右相交q;

(4) 包含:如果a≤begin≤end≤b, 则称I被q包含, 即q覆盖I;

(5) 不相交:如果b < begin或end < a, 则称I和q不相交.

定义3(间隔查询).间隔查询可以用三元组(q, D, O)形式化表示, 其中:q表示查询间隔; D表示检索目标, 由多个对象组成, D中的每个对象o由二元组(id, I)构成, id标识对象o, I是对象o的间隔; O为检索结果集合, 对于O中的任意对象o∈O, o.I和q相交.

当查询间隔q的起点等于终点, 即a=b时, 这样的查询又称为点查询.

定义4(范围查询).给定一个查询间隔q, 范围查询从对象集合D中返回所有在查询范围内出现的对象构成集合R, 对于R中的任意对象o∈R, o.I和q满足定义2中第(2)种~第(4)种这3种关系的任意一种.类似于间隔查询, 范围查询可用三元组(q, D, R)表示.

定义5(覆盖查询).给定一个查询间隔q, 覆盖查询从对象集合D中返回所有间隔I覆盖q的对象形成结果集C, 使用三元组标记为(q, D, C). 定义6(间隔查询的一维转换).依据范围查询、覆盖查询以及间隔查询的定义可知:间隔查询可以分解为范围查询和覆盖查询, 2个子查询可并行执行.间隔查询的一维转换形式化描述为(q, D, O)→(q, D, R)+(q, D, C).

定义7(间隔查询的二维转换).对于二维点q(a, b)表示的任意间隔查询q=[a, b], 其检索空间由左下角(begin, a)、右上角(b, end)定义的矩形框确定, 其中, begin/end为数据阈值的最小值/最大值.一维间隔查询q(a, b)和二维范围查询q'= < (begin, a), (b, end)>的检索空间是一致的.间隔查询的二维转换形式化描述为

$ \left( {q, D, O} \right) \to (q' = \langle \left( {begin, a} \right), \left( {b, end} \right)\rangle, D, R). $

例如, 间隔查询q(11, 20)的检索空间如图 1(b)红色矩形框所示, 其检索空间和范围查询q'= < (0, 11), (20, 24)>的检索空间一致.

定义8(间隔查询间的共享).当间隔查询q₁=[a, b]和q₂=[c, d]相交时, q₁和q₂部分检索结果相同, 则称二者是可共享的.q₁和q₂进行一维转换后, 产生范围查询q_1R=[a, b], q_2R=[c, d]以及覆盖查询q_1C=[a, b], q_2C=[c, d].当q_1R和q_2R相交时, q_1R和q_2R是可共享的; 当q_1C和q_2C存在覆盖关系, q_1C和q_2C是可共享的.q₁和q₂进行二维转换后, 产生范围查询q'₁= < (begin, a), (b, end)>，q'₂= < (begin, c), (d, end)>.q'₁和q'₂相交时, q₁和q₂是可共享的.

例1:如图 1所示, 数据集合D中包含u, v, w, x, y, z共6个间隔对象, 对于查询间隔q=[11, 20], w覆盖q, z左相交q, v右相交q, y被q包含, 最终结果集O={v, w, y, z}.对于范围查询q=[11, 20]和覆盖查询q=[11, 20], 检索结果集分别为R={v, y, z}, O={w}.图 1的数据集合D将作为间隔查询的检索目标贯穿全文实例, 例2将详细阐述间隔间的共享关系.

2 相关工作

间隔查询的执行经过解析查询、生成访问计划、执行访问计划这3个步骤, 如后文图 3所示.已有工作通过设计合理的索引结构提高数据访问速度和分析查询特性共享公共操作两种途径提高间隔查询的检索性能.下面将分别考察基于索引和查询特性的优化技术.

2.1 基于索引的优化技术

依据数据存储在单台机器还是分布式平台, 将支持间隔查询的索引分为集中式和分布式两种.

(1) 集中式索引

早期的数据量小, 索引存储在单台机器中, 这种索引称为集中式索引.支持间隔查询的集中式索引本主要分为以下3类, 文献[7]对这些索引结构和数据访问方法进行了详细对比.

·  基于B+-tree的索引.典型的扩展B+-tree的间隔索引是Time Index^[8].Time Index是为了检索某个间隔内有效的所有对象版本而设计的间隔索引.Time Index+^[9]作为Time Index的改良版降低了其O(n²)(n为间隔数)的空间复杂度.Interval B-tree^[10](IB-tree)进一步解决Time Index和Time Index+空间开销大的问题, 提出新的结构augmented B+-tree代替二叉树结构.TD-tree^[11]为了提高开区间的间隔查询的检索性能而提出的新结构, 它用三角形二分的方式分解间隔查询的检索空间, 并编码路径信息提高检索效率;

·  基于R-tree的索引.间隔查询可以转换为多维范围查询, 因此, 多维索引支持间隔查询, R-tree和R-tree变种(Segment R-tree^[12], 4R-tree^[13]等)主要支持多维时间数据的间隔查询, 可用在双时态数据库^[14]中.由于时间数据自身的特点导致时间间隔的重叠性较大, R-tree索引的检索性能较低, 不适合间隔查询;

·  基于Segment-tree的索引.Segment-tree是一种高效且通用的间隔索引.它不仅支持一维数据的检索还适合多维数据.Segment-tree是二叉树, 结点采用间隔作为key, 每个结点拥有list属性, 用来存储覆盖间隔key的所有对象.为了节省存储空间, 覆盖父节点的对象不会在子节点重复存储.Segment R-tree和Time Index+都利用了Segment tree的特性来降低空间复杂度.

(2) 分布式索引

当间隔数据的数据量逐渐增大、单机不能存储海量数据时, 索引分布式在多台机器.这种索引称为分布式索引.

·  基于P2P架构的分布式索引.文献[15]将节点组织成DHT网络覆盖, 提出分布式线段树Distributed Segment Tree (DST), 主要支持范围查询和覆盖查询.除了明确说明支持间隔查询的分布式索引外, 由于一维间隔查询可以转换为二维范围查询, 支持范围查询的分布式索引能够支持间隔查询, 如RT-CAN^[16], CGIndex^[17]等基于P2P架构的分布式多维索引;

·  基于Master-Slave架构的分布式索引.EPI+MRST^[18]是首个分布式间隔索引.为了高效响应间隔查询, 它将间隔查询进行一维转换, 采用索引结构EPI和MRST分别处理范围查询和覆盖查询.此外, 支持多维范围查询的分布式多维索引也支持间隔索引, 如MD-HBase^[19], KR⁺-tree^[20]等.

间隔查询因重要的理论意义和实践价值而受到持续关注, 从20世纪80年代至今, 优化间隔查询的大量索引技术涌现.然而这些技术仅优化单个查询的数据访问速度, 而没有考虑查询本身的特性, 当单点上海量查询请求急速到来时, 70%的查询不能在期望时间内得到响应.

2.2 基于查询特性的间隔查询优化技术

1) 缓存技术

数据缓存是数据库和信息检索系统优化检索性能的常用方法.依据二八原则, 80%的查询是频繁访问的, 因此将频繁查询和检索结果缓存起来, 当缓存命中时, 可以直接从内存获取结果, 不需要访问磁盘, 从而提高查询的响应时间.缓存技术要求查询或子查询必须和缓存的查询相同, 没有探索不相同的查询间是否存在部分结果复用, 并且缓存技术有很强的时效性, 设计合理的缓存粒度^[21]和淘汰算法^{[22, 23]}是缓存技术的关键, 该方法通过提高缓存命中率来提升检索性能.缓存技术中查询的执行依然采用one-by-one的方式, 不同于本文实施的共享执行策略.

2) 共享执行策略

共享执行策略先将接收到的查询进行缓存, 当查询累计到一定量或一定时间时, 对这组查询进行批处理.共享执行策略的关键技术是探索查询间的相似性, 分析可以共享执行的操作.共享执行的操作可以是计算能力或访问数据, 可以共享部分操作也可以共享全部操作, 共享的粒度更细致更灵活.共享执行策略的有效性和高效性, 使得其在多个应用中均取得显著效果.文献[6]首次关注高并发情况下查询的等待时间对查询的响应时间影响, 探索路网中KNN查询间的同质性, 将一个查询的中间结果给多个查询进行共享, 从而减少计算代价. SeTPR^*-tree^[24]将共享执行策略应用到时空范围查询, 对一批范围查询进行处理, 通过调整查询的执行顺序提高buffer的命中率, 从而提升检索性能.SharedDB^[25]是一次处理多个查询的内存数据库, 为一批查询生成一个全局查询计划, 仅执行该全局查询计划, 从而节省计算资源和数据访问代价.TOF^[26]将共享执行策略应用到移动对象中, 对一组范围查询进行批处理, 从而保证所有高并发的查询请求均能在用户期望时间内得到响应.

本文首次将共享执行策略应用到间隔查询中, 针对目前日益增长的间隔数据和相应的应用需求优化间隔查询, 解决基于索引的优化技术不能满足海量高并发查询的性能要求问题.

3 基于共享执行策略优化间隔查询(SESIQ)

相交的两个间隔查询含有相同的检索结果, 而相同结果可以仅访问一次, 从而减少磁盘I/O和网络传输代价, 提高检索性能.本节将介绍基于此思想所设计的SESIQ的引擎架构及其关键实现技术.

SESIQ的引擎包括计划生成器Planner、执行器Executor和结果重组器Reconstructor这3个核心组件, 关键执行流程如图 3(b)所示.3个核心组件分别完成生成全局访问计划(generating global access plan, 简称GAP)、执行访问计划(executing access plan, 简称EAP)、重构检索结果(reconstructing search result, 简称RSR)这3个任务:(1) GAP负责分析一组间隔查询间是否含有重复访问的数据, 通过查询分解或原子化将原查询转换为子查询集合, 形成全局访问计划; (2) EAP负责执行全局访问计划, 得到每个子查询的检索结果; (3) RSR需要对子查询的检索结果进行重构, 以满足用户提交的原查询的要求.

SESIQ的主要贡献在于对查询进行批处理, 为一组间隔查询生成全局访问计划代替多个查询的局部访问计划, 通过查找间隔查询间的共享操作减少重复数据访问, 提升检索性能.对比图 3(a)和图 3(b)可知:图 3(a)中主要通过间隔索引优化间隔查询; 图 3(b)从查询特性的角度出发, 在间隔索引基础上进一步优化间隔查询的检索性能.由于篇幅受限, 本文主要介绍间隔查询进行一维转换的SESIQ实现技术, 未来详细探讨间隔查询进行二维转换的SESIQ方法.

3.1 生成全局访问计划(GAP)

GAP是SESIQ的计划生成器中最关键的过程, 它需要解决两个技术难点.

a) 分析一组间隔查询间是否含有重复访问的数据;

b) 尽可能地减少重复数据的访问.

对于问题a), 我们可以两两比较间隔查询, 判断是否满足相交关系.然而这种方法的时间复杂度O(M²×T)(M为查询的个数, T为判断是否相交的时间), 效率低下; 对于问题b), 需要获得一组间隔查询最少访问数据量.为此, 本文为一组间隔查询创建内存线段树, 借助线段树回答问题a)和问题b).假设服务器接收到的一组间隔查询S={q, q₁, q₂, q₃, q₄}如图 4所示, 对应图 4查询示例的内存线段树ST如图 5所示.由于对间隔查询进行了一维转换, S分解为一组范围查询S_R={q, q₁, q₂, q₃, q₄}和一组覆盖查询S_C={q, q₁, q₂, q₃, q₄}, 问题a)和问题b)转化为分析S_R/S_C元素间是否相交以及S_R/S_C尽可能地减少重复数据访问的问题.下面介绍GAP处理S_R和S_C的详细过程.

GAP处理S_R主要思想是:分解S_R所有元素构成的范围区间, 得到一组子查询集合R(S_R), 对于任意范围查询p∈R(S_R), 必有q∈S_R, 使得p被q包含, 同时, R(S_R)满足:

a) 如果S_R不存在相交的元素, 则R(S_R)和S_R相等; 否则, S_R中存在相交的元素;

b) R(S_R)的检索结果能够还原S_R的检索结果, 且R(S_R)重复访问的数据最少.

GAP处理S_C的关键, 是判断覆盖集合是否存在互相覆盖的查询:如果两个覆盖查询相交, 即二者满足定义2中的覆盖关系, 则二者的检索结果可共享.例如间隔q覆盖间隔p, 则覆盖查询p的检索结果中必然包含覆盖查询q的结果, 服务器仅需要响应p而省略对q结果的访问, p成为向服务器提交的子查询.

给定一个间隔查询集合S, 算法1描述了借助线段树ST生成S的全局执行计划的过程.

算法1.生成间隔查询集合S的全局执行计划.

输入:间隔查询集合S, 内存线段树ST;

输出:子查询集合R(S_R)和C(S_c), 子查询和原查询的映射关系RMap和Cmap.

1: 初始化集合R(S_R)和NS、队列queue、哈希表RMap和CMap为空, 集合C(S_c)=S;

2: 将ST的根结点node入队列queue;

3: WHILE queue不为空

4:  queue移出队头元素node;

5:  获取node的对象列表list;

6:  IF list不为空THEN

7:    NS.add(node);

8:  ELSE   //list为空

9:    将node的左右孩子结点分别入队列queue;

10: END WHILE

11: FOR node: NS

12:  subquery←node的间隔;

13:  list←node的对象列表;

14:  R(S_R).add(SubQuery);

15: 清空queue;

16: 将node加入队列queue;

17:  WHILE queue不为空

18:  queue移出队头元素subnode;

19:  获取subnode的对象列表sublist;

20:  将subnode的左右孩子结点入队列queue;

21:   IF sublist不为空THEN

22:   FOR o:o∈sublist and q:q∈list

23:     RMap.put(subQuery, o);

24:    IF q∈C(S_c) and q覆盖o THEN

25:      CMap.Put(o, q);

26:      从C(S_c)中删除q;

27:     END IF

28:    END FOR

29:   END IF

30:  END WHILE

31: END FOR

32:返回R(S_R), C(S_c), RMap, CMap;

算法1从根结点开始层次遍历线段树ST(第2行), 如果遇到结点node的对象列表list不为空(第4行~第6行), 将node加入到集合NS(第7行), 处理队列queue中下一个node, 直到queue为空; 否则, 将node的孩子结点加入queue, 需要遍历孩子结点(第8行、第9行).通过步骤3~步骤10, 算法1能够找到ST所有路径中首个对象列表不为空的结点, 这样的结点为关键结点.依据关键结点, 算法1可以获得S_R和S_C子查询集合R(S_R)和C(S_C)以及子查询和原查询的映射关系RMap和CMap (第11行~第31行).对于S_R, 任意关键结点node, 其间隔构成list中原查询的子查询subQuery(第12行), subQuery作为R(S_R)的元素加入到R(S_R)(第14行), 而以node为根的子树中包含的对象(即原查询)和subQuery存在映射关系(第17行~第30行), 添加他们的映射关系到RMap(第23行).对于S_c, 任意关键结点node, 其对象列表list(第13行)中的对象q(即原查询)为覆盖范围最广的查询, 若q覆盖其他的查询o(第24行), 则o存在于以node为根的子树中(第17行~第30行).最终返回R(S_R), C(S_C), Rmap, CMap(第32行).

若算法1中得到的R(S_R)=S_R, RMap为空, 或C(S_C)=S_C, CMap为空, 则S_R/S_C元素间不存在共享的操作, 此时SESIQ没有优化S_R/S_C的检索性能; 当R(S_R)≠S_R时, R(S_R)中的每个元素都是S_R中一个查询的子查询, R(S_R)元素之间互不相交, 不存在重复访问的数据, 服务器仅响应R(S_R)中的查询, 使得能够获得S_R全部检索结果且重复访问数据最少; 当C(S_C)为S_C的真子集时, 此时服务器少响应部分覆盖查询, 减少了数据访问, SESIQ能够优化S_C.

例2:对于S={q, q₁, q₂, q₃, q₄}, 采用算法1层次遍历ST, 依次得到对象列表不为空的结点为11-21, 3-7, 7-11, 覆盖能力最强的原查询为q₃, q₁, q₂, 因此,

$ {R\left( {{S_R}} \right) = \left\{ {{p_3} = \left[{11, 21} \right], {p_1} = \left[{3, 7} \right], {p_2} = \left[{7, 11} \right]} \right\}, } $

$ {RMap = \{ \langle {p_3}, \left\{ {q, {q_2}, {q_3}, {q_4}} \right\}\rangle, \langle {p_1}, \left\{ {{q_1}, {q_2}} \right\}\rangle, \langle {p_2}, \left\{ {{q_2}, {q_3}} \right\}\rangle \}, } $

$ {C\left( {{S_C}} \right) = \left\{ {q, {q_1}, {q_2}, {q_4}} \right\}, } $

$ {CMap = \{ \langle q, {q_3}\rangle \} .} $

由于R(S_R)≠S_R, C(S_c)≠S_c, RMap和CMap不为空, 可知S_R/S_C存在相交的元素, SESIQ可以优化S_R/S_C的性能.

3.2 执行访问计划(EAP)

间隔查询进行一维转换后, 生成范围查询和覆盖查询2个子查询, 因而支持范围查询和覆盖查询的索引均可以用来执行GAP中生成的访问计划.EPI+MRST^[18]中的EPI结构可以用来响应范围查询, MRST结构用来响应覆盖查询, 且EPI+MRST是明确指出支持间隔查询的首个分布式索引, 因而更具借鉴和比较价值, EAP采用EPI+MRST执行GAP产生的子查询集合.

GAP产生S_R和S_C的子查询集合分别为R(S_R)和C(S_C).对于R(S_R)中的任意查询p=[a, b], EPI使用HBase的scan操作获取Rowkey在[a, b]之间的对象, 取得范围查询的结果; 对于C(S_C)中的任意查询p'=[c, d], MRST处理点查询p"=[c, c], 使用HBase的get操作遍历MRST来获得覆盖查询p'的结果.EPI和MRST处理查询的算法描述详见文献[18].

例3:对应例3产生的子查询集合R(S_R)={p₃=[11, 21], p₁=[3, 7], p₂=[7, 11]}和C(S_C)={q₁=[3, 7], q₂=[6, 12], q=[11, 20], q₄=[17, 21]}, 其检索结果见表 1.为了对比, 表 1还给出集合S中元素的检索结果.

3.3 重构检索结果(RSR)

GAP创建了子查询和原查询的映射关系RMap和CMap, 用于重构检索结果.对应例1, 下面详细阐述怎样将EAP执行的结果映射到原查询中, 即RSR的执行过程.因算法较简单, 略去算法描述.

例4:对于间隔查询集合S={q, q₁, q₂, q₃, q₄}, 需要合并S_R和S_C的结果形成最终结果, 即需要建立R(S_R), C(S_C)和S的关系, 对R(S_R)和C(S_C)的检索结果进行分配.表 2展示了原查询和子查询的关系, 并指出得到正确结果要执行的操作.

如:范围查询q和范围查询p₃部分相交, 因此需要精炼p₃的执行结果以过滤不在查询间隔q内的对象x, q的结果为{v, y, z}, 而覆盖查询q的结果为{v, w}, 间隔查询q的最终结果为{v, w, y, z}.类似可获得其他间隔查询的检索结果, 见表 2.

了解SESIQ方法的执行流程后, 第3.4节和第3.5节将定量分析SESIQ的时空开销.

3.4 性能分析

SESIQ能够有效执行的条件是, 一组查询中存在共享执行的操作.当S_R/S_C中没有共享的操作时, 即R(S_R)=S_R, C(S_C)=S_C, 此时SESIQ和NSESIQ (没有采用SESIQ的方法)的性能是相当的, 间隔查询没有得到优化; 当S_R/S_C存在可共享的操作, 减少数据访问的收益大于内存计算开销, SESIQ的性能优于NSESIQ.

下面分别讨论当S_R/S_C存在可共享的操作时, SESIQ和NSESIQ的性能差异.

(1) 范围查询

范围查询的检索结果常通过顺序扫描获得, 如EPI+MRST中采用scan操作访问EPI, 其消耗的时间和访问对象数成正比, SESIQ和NSESIQ的性能比λ_R可用公式(1)描述:

$ {\lambda _R} \propto O\left( {{S_R}} \right)/O\left( {R\left( {{S_R}} \right)} \right) $

(1)

其中, O(S_R)和O(R(S_R))分别表示NSESIQ和SESIQ访问的对象总数, 通过累积S_R和R(S_R)中的每一个范围查询I访问的对象数O^R(I)而获得.由算法1可知, ST中所有对象列表不为空的结点LN构成的集合SLN能够还原S_R.S_R访问的对象总数可用公式(2)计算:

$ O({S_R}) = \sum\limits_{i \in SIN(ST)} {{O^R}({I_i})} \times OL(i, ST) $

(2)

其中, I_i表示结点i的间隔, OL(i, ST)表示ST中覆盖结点i的对象数.R(S_R)访问的对象总数和ULN(ST所有从根开始的路径中首个LN形成的集合)相等, 见公式(3):

$ O(R({S_R})) = \sum\limits_{i \in UIN(ST)} {{O^R}({I_i})} $

(3)

而O^R(I)可通过公式(4)或公式(5)进行估算或精算.

·  仅知道查询信息时, 用公式(4)估算O^R(I), 假设N个间隔数据均匀地分布在范围为[min, max]的一维空间内:

$ {O^R}\left( I \right) = \left\lceil {N \times \left| {\left| I \right|} \right|/||max-min||} \right\rceil $

(4)

·  索引元数据信息和查询信息都获取后, 可用公式(5)精算O^R(I), 其中, df_t表示间隔端点为t的对象总数:

$ {O^R}(I = [a, b]) = \sum\limits_{t = a}^b {d{f_t}} $

(5)

从以上分析可知:范围查询中SESIQ访问的对象总数是NSESIQ的一部分, 利用公式(1)~公式(5)可以粗略估算SESIQ在范围查询中获得的性能收益.

(2) 覆盖查询

支持覆盖查询的索引常为树形结构, 覆盖查询的检索结果通过随机访问获得.如EPI+MRST中, 执行get操作访问MRST, 其消耗的时间和访问结点数成正比, 因此, 访问结点数成为SESIQ和NSESIQ在覆盖查询中性能差异的度量, SESIQ和NSESIQ的性能比可用公式(6)描述:

$ {\lambda _C} \propto N\left( {{S_C}} \right)/N\left( {C\left( {{S_C}} \right)} \right) $

(6)

其中, NSESIQ和SESIQ访问的结点总数用N(S_C), O(C(S_C))表示, 可由公式(7)和公式(8)获得, 通过累积S_C和C(S_C)中的每一个覆盖查询p访问的结点数N^C(p)而获得:

$ N({S_C}) = \sum\limits_{p \in {S_C}} {{N^C}(p)} $

(7)

$ N(C({S_C})) = \sum\limits_{p \in C({S_C})} {{N^C}(p)} $

(8)

在公式(7)和公式(8)中, N^C(p)由索引信息确定:

·  仅知道树形索引的树高h时, 可用公式(9)估算:

$ {N^C}\left( p \right) \approx h = 1 + \left\lceil {lo{g_2}m} \right\rceil $

(9)

·  获得索引从根到叶每条路径的长度和叶结点信息, 可用公式(10)计算覆盖查询p所访问的结点数:

$ {N^C}\left( p \right) = Lpath\left( p \right) $

(10)

覆盖查询中, SESIQ的性能收益来自于S_C中存在具有覆盖关系的查询, 使得SESIQ向后台提交的查询请求数减少, 降低了访问结点数.基于公式(6)~公式(10), 我们可以估算SESIQ在覆盖查询中的性能收益.

例5:假设我们不知道索引的具体信息, 采用第3.4节介绍的公式估算SESIQ和NSESIQ响应图 4示例查询的性能差异, 数据集为图 1所示的6个间隔对象, 因此, N=6, m=8, h=3, max=22, min=3.使用公式(4)可得范围查询访问对象数, 如O^R(q)=3, 公式(2)和公式(3)估算范围查询集合访问对象总数可得O(S_R)=14, O(R(S_R))=8.公式(9)估算覆盖查询访问结点数, 如N^C(q)=4, 公式(7)和公式(8)估算覆盖查询集合访问结点总数可得N(S_C)=20, N(C(S_C))=16.而真实值O(S_R)=14, O(R(S_R))=8, N(S_C)=20, N(C(S_C))=16.对比估算值和真实值可知, 以上公式可以作为性能评估的参考.对比SESIQ和NSESIQ的性能可知:SESIQ在图 4示例查询中是有效的, 其范围查询的性能约为NSESIQ的1.5倍, 覆盖查询的性能约为NSESIQ的1.25倍.

3.5 空间开销分析

SESIQ批处理一组(M个)间隔查询, 并为该组间隔查询建立了内存线段树, 且SESIQ在重构检索结果阶段需要缓存部分检索结果, 下面定量分析SESIQ和NSESIQ的空间开销.

SESIQ的空间开销来源于两部分:

a) 维护M个间隔查询的内存线段树消耗的空间--S_ST;

b) 缓存M个间隔查询的检索结果消耗的空间--S_RSR.

SESIQ的空间开销为这两部分的最大值, 其计算方法见公式(11):

$ {S_{SESIQ}} = max\left( {{S_{ST}}, {S_{RSR}}} \right) $

(11)

而NSESIQ的空间开销主要用于缓存单个查询的检索结果S_r, 其计算方法见公式(12):

$ {S_{NSESIQ}} = {S_r} $

(12)

S_ST, S_RSR的计算方法分别见公式(13)、公式(14):

$ {S_{ST}} = (2M-1) \times {S_{node}} + \sum\limits_{i \in SIN(ST)} {OL(i, ST)} \times {S_q} \approx (M \times 2\mu + M \times \log M) \times {S_q} $

(13)

$ {S_{RSR}}{\kern 1pt} {\kern 1pt} = \left\{ {\begin{array}{*{20}{l}} {M \times {S_r}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} ({\rm{a}})}\\ {{S_r}{\rm{ }} {\kern 1pt} ({\rm{b}})} \end{array}} \right. $

(14)

公式(13)计算S_ST时, 需要统计(2M-1)个结点(不包含对象列表)的空间开销和ST中对象间隔的空间开销, 其中, 单个结点的开销S_node约等于μ个S_q的代价(公式(15)):

$ {S_r} = {r_q} \times {S_q} $

(15)

而最终检索结果的形成, 需要合并每个公共子查询的检索结果.当服务器多次提交子查询的检索结果到客户端, 即, 检索结果的合并在客户端完成时, S_RSR的计算方法见公式(14)(b); 当服务器合并所有子查询的检索结果形成最终结果提交到客户端时, S_RSR的计算方法见公式(14)(a), 其中, S_r表示单个查询的检索结果占用的最大内存, 主要由检索结果数r_q确定, 详见公式(16):

$ {S_{node}} = \mu \times {S_q} $

(16)

对比SESIQ和NSESIQ的空间开销可知:当检索结果缓存在客户端时, SESIQ的空间开销和NSESIQ相差不多, 主要是增加了内存线段树的开销, 其空间复杂度为O(M×logM); 当检索结果缓存在服务器端时, SESIQ的空间开销主要用于缓存检索结果, 空间复杂度为O(M×r_q), 其代价是NSESIQ的M倍.

例6:下面依据例5计算SESIQ和NSESIQ的空间开销, 公式中的参数设置为μ=2, r_q=5, N=5, m=8.M=5. NSESIQ的空间开销依据公式(12)可得S_NSESIQ=5S_q; 由公式(13)、公式(14)分别可得S_ST=15×S_node+8×S_q=38S_q, S_RSR=25S_q.依据公式(11)可知:SESIQ的空间开销为S_SESIQ=38S_q, 是NSESIQ的7.6倍.

4 实验评估

本文使用2种真实数据集评估SESIQ的有效性, 底层索引为EPI+MRST.实验过程中, 将采用共享策略的方法EPIMRST_SQ和没有使用共享策略的方法EPIMRST进行对比, 评估多种影响因子在两种不同方法中对检索性能的影响.程序实现均采用Java完成, EPI+MRST的实现代码来自原作者.所有的实验在一个8台虚拟机组成的分布式集群上完成, 网络带宽为1Gbps.每台虚拟机拥有8GB内存、500GB磁盘空间.EPI+MRST采用分布式数据库HBase-0.94.2做存储系统, 底层分布式文件基于Hadoop-1.0.4.

4.1 数据集

本文选择2个真实数据集DMOZ和Wiki进行实验评估.DMOZ数据集来自网站dmoz.org, 人工记录了不同类别多个网站的版本变更信息, 本文从2004年~2011年的类别变更数据中(约426GB)抽取1 200万个间隔(86 751个间隔端点)组成DMOZ数据集, 其时间间隔以小时为单位; Wiki数据集来自wikimedia.org, 记录Web文档的版本变更信息, 本文从2001年~2015年的Web文档版本变更元数据(约10TB)抽取3.2亿个间隔(120 735 322个间隔端点)形成Wiki数据集, 其时间间隔以ms为单位.

4.2 实验结果及分析

本节评估查询数、选择率、数据量(间隔数)这3种影响因子对间隔查询响应时间的影响, 验证SESIQ的有效性.为了使结果更为可靠, 每个实验重复10次, 并取平均值作为最终结果.表 3给出实验用的参数设置, 缺省值加粗显示.为了测试数据量对检索性能的影响, 选择Wiki数据集20M, 40M, 80M, 160M个间隔评估实验.模拟真实应用中, 服务器接收到的查询是随机的, 本文从原始数据中随机抽取选择率不确定的间隔作为查询用例.除评估选择率对检索性能的影响使用固定选择率的查询, 其他情况均使用随机查询.

1) 查询数对间隔查询检索性能的影响

SESIQ批量处理的查询数是影响SESIQ性能的重要因素, 本节重点评估查询数对间隔查询检索性能的影响.由于本文的间隔查询进行了一维转换, 分解为范围查询和覆盖查询, 本文评估查询数对范围查询和覆盖查询检索性能的影响, 分析访问对象数、访问结点数、响应时间随查询数的变化.

·  访问对象数随范围查询数变化

EPI+MRST中, EPI索引负责处理范围查询, 因此, EPI-SQ区分EPI表示采用共享执行策略的方法.对应于第3.4节的分析, 本文给出EPI和EPI-SQ的估算值, 用~EPI和~EPI-SQ表示.

从图 6展示的DMOZ数据集中访问对象数随范围查询数的变化可知:查询数对EPI检索性能几乎没有影响, 其访问对象数在小范围内波动; 而随着查询数增大, EPI-SQ访问对象数减少, 检索性能线性提升.主要原因是: 4组查询的平均选择率相同, 查询数不影响EPI的检索性能; EPI-SQ中增加查询数增大查询间可共享性, 从而访问的对象总数减少.由于实验所用服务器的物理配置受限, 本文仅评估了100个~800个查询数的性能.而查询数不是越多越好, 有些情况下, 检索性能反而下降.原因在于:分析查询间可共享性会增加内存计算开销, 当增加查询数带来的收益小于开销, 此时检索性能下降.总体来说, EPI访问对象数远大于EPI-SQ, 是EPI-SQ的50倍~500倍.图 6还给出了EPI和EPI-SQ访问对象数的估算值, 对比实测值可知, 估算值和实测值相近, 表明公式(2)~公式(4)是有效的.

类似地, 图 7给出了Wiki数据集中, 访问对象数随范围查询数的变化.Wiki数据集中, EPI-SQ访问对象数随着查询数的增加而下降, 而EPI出现先下降后增加的趋势, 但EPI-SQ的性能依然优于EPI, EPI访问对象数是EPI-SQ的5倍~30倍.从EPI-SQ表现可知:增加范围查询数, 通常会增多范围查询间可共享的操作.EPI访问对象数出现先升后降的原因是:4组查询的平均选择率不同, 100个~400个随机查询中, 选择率小的查询所占比重越来越多, 800个随机查询选择率大的查询的比重更大; 同时也可以看出:相较Wiki以ms为单位, DMOZ中的间隔以小时为单位, 数据分布相对较均匀.图 7给出了EPI和EPI-SQ访问对象数的实测值和估算值, 也验证了公式(2)~公式(4)是有效的.

·  响应时间随范围查询数的变化

图 8和图 9给出DMOZ, Wiki数据集响应时间随范围查询数的变化.为了清晰地描述响应时间和访问对象数的关系, 图 8和图 9采用双纵坐标, 左纵坐标为响应时间, 右纵坐标为访问对象数.由图可知:EPI和EPI-SQ的响应时间随查询数变化趋势和访问对象数随查询数变化趋势是相同的, 可用公式(1)估算EPI和EPI-SQ的性能比.DMOZ和Wiki数据集中, EPI的响应时间分别是EPI-SQ的20倍~150倍和4倍~20倍.从图 6~图 9可知:在查询数相同的情况下, SESIQ方法在DMOZ数据集中访问了更少的对象, 性能收益更加显著.主要原因是:Wiki中的间隔以毫秒为单位, DMOZ中的间隔以小时为单位, DMOZ的数据密度(间隔总数/数据空间体积)相对Wiki更大, 因而DMOZ数据集下, 间隔查询间包含相同数据的几率增大, SESIQ方法使得重复访问的数据减少地更多, 其性能收益更大.

·  访问结点数随覆盖查询数的变化

EPI+MRST中, MRST索引响应覆盖查询.MRST和MRST-SQ区分是否采用SESIQ方法, ~MRST和~MRST-SQ表示MRST和MRST-SQ性能的估算值.DMOZ数据集中, MRST访问结点数随覆盖查询数增多而降低, MRST-SQ访问结点数随覆盖查询数增加而波动, 如图 10所示.产生这种趋势的主要原因依然和选取的随机查询相关:MRST是不平衡的二叉树, 处理覆盖查询时执行点查询, 不同的访问路径导致访问结点数不同. MRST呈现的变化趋势是因为随机查询中访问短路径的查询比重更大, 而MRST-SQ则因为两个查询具有覆盖关系的概率较小, 增加覆盖查询数没有增多共享操作, 因此, MRST-SQ访问结点数随覆盖查询数增多而波动.但总体来说, MRST-SQ访问结点数少于MRST.图 10所给出的访问结点数的估算值也存在波动, 估算值和实际值二者有差异, 但公式(9)获得的估算值依然可以作为评估性能的参考.

图 11展示了Wiki数据集中覆盖查询数对访问结点数的影响, MRST和MRST-SQ访问结点数均随查询数增加而增多, 主要原因是访问长路径的随机覆盖查询所占比重更大.但MRST-SQ性能优于MRST是确定的, MRST访问结点数是MRST-SQ的1.5倍~2倍.图 11中, MRST和MRST-SQ访问结点数的估算值和实际值比较, 也验证了公式(9)的可行性.

·  响应时间随覆盖查询数的变化

本文也给出DMOZ, Wiki数据集响应时间随覆盖查询数的变化, 类似于范围查询, 图 12和图 13采用双纵坐标给出响应时间和访问结点数随查询数的变化趋势.从图 12和图 13可以看到:MRST和MRST-SQ的响应时间和访问结点数二者随查询数变化趋势是相同的, 可用公式(6)估算MRST和MRST-SQ的性能比.DMOZ和Wiki数据集中, MRST覆盖查询的响应时间分别是MRST-SQ的1.2倍~1.6倍和1.7倍~2.3倍.

对比图 10~图 13可知:随着查询数的增加, SESIQ在Wiki数据集中的性能收益更显著.主要原因在于:Wiki中数据较稀疏, 间隔查询间存在覆盖关系的几率更大; 同时, Wiki数据集索引树高更大导致MRST的访问路径较长, 单个覆盖查询的响应时间更多; 而SESIQ减少了向后台提交的查询, 降低了查询的总体响应时间, 因而性能收益较显著.

·  响应时间随间隔查询数变化

本节评估响应时间随间隔查询数的变化情况.从图 14和图 15可知:间隔查询的响应时间随查询数的变化趋势和范围查询接近, 因为间隔查询的时间开销主要用于处理范围查询.EPIMRST-SQ的检索性能明显优于EPIMRST.DMOZ数据集中, EPIMRST-SQ的响应时间不足1s, 而EPIMRST的响应时间远大于1s, 是EPIMRST-SQ的20倍~50倍.Wiki数据量远远大于DMOZ, EPIMRST和EPIMRST-SQ的响应时间均在1s以上, EPIMRST的响应时间是EPIMRST-SQ的4倍~25倍.在间隔查询数相等的情况下, SESIQ方法的性能收益在DMOZ数据集中更显著, 由于DMOZ的数据密度相对Wiki更大导致.

除了查询数这一影响因子, 下面还评估了选择率、数据量对间隔查询检索性能的影响, 主要关注间隔查询的平均响应时间随选择率和数据量的变化.

2) 选择率对响应时间的影响

图 16展示了DMOZ数据集中, 选择率对间隔查询的响应时间的影响.随着选择率增大, EPIMRST-SQ和EPIMRST响应时间均增加.然而EPIMRST-SQ省略重复数据的访问和传输, 增长趋势远低于EPIMRST.同时可知:低选择率的情况下, EPIMRST-SQ没有显露优势.由于分析查询间的可共享操作和重构检索结果增加了内存计算开销, 检索性能甚至劣于EPIMRST.当选择率升高到0.1%后, EPIMRST-SQ的性能显著优于EPIMRST, 且差异越来越大.当选择率为10%时, EPIMRST-SQ的性能比EPIMRST快了20倍.主要原因是高选择率下, 间隔查询间相交的概率变大, 可共享的数据更多, 从而节省时间开销.

Wiki数据集中选择率对间隔查询响应时间的影响如图 17所示:随着选择率增长, EPIMRST-SQ和EPIMRST的响应时间线性增加.而EPIMRST的响应时间远大于EPIMRST-SQ, 特别是10%的选择率下, 其响应时间是EPIMRST-SQ的40倍.

对比图 16和图 17可知, SESIQ在Wiki数据集中的性能提升更显著.因为Wiki数据量较大, 单个查询的响应时间更长, one-by-one处理查询时, 查询的等待时间相对较长, 而SESIQ取消了查询间的等待, 共享执行策略减少了大量重复数据的访问, 因此其性能提升在Wiki中更显著.

3) 数据量对响应时间的影响

图 18展示了间隔查询的响应时间随数据量变化趋势, 实验中仅改变Wiki的数据量, 不同数据量的查询用例是相同的.随着数据量的增加, EPIMRST-SQ和EPIMRST的检索性能均呈线性下降, 二者的下降趋势相同.但EPIMRST-SQ的检索性能依然优于EPIMRST约4倍.

以上实验从查询数、选择率、数据量这3个因子验证SESIQ的有效性.从结果可知:SESIQ方法是有效的, 特别是在数据量大、数据密度大的数据集中能够显著优化间隔查询, 使其性能提升数十倍.

5 总结与展望

针对已有方法不能满足海量间隔查询性能要求的问题, 本文首次将共享执行策略应用到间隔查询中, 提出了采用共享执行策略优化间隔查询的方法SESIQ.SESIQ对接收到的间隔查询进行批处理, 分析查询间可共享的操作, 为多个查询生成一个全局的执行计划, 从而减少重复数据的访问、提高检索性能.本文在已有分布式间隔索引基础上进一步优化间隔查询, 基于理论分析和实验评估表明:SESIQ是有效且高效的, 其检索性能优于NSESIQ数十倍.

尽管本文提出的方案是高效可行的, 然而本文还有一些问题待考虑:

1) 共享执行策略对内存需求相对较大.一般情况下, 采用共享执行策略的应用都假设服务器的内存是足够大的, 然而一些服务器的内存可能不够大, 未来我们将研究内存受限的共享执行策略;

2) 本文在阐述SESIQ具体实施过程中仅对间隔查询进行了一维转换, 然而一维转换使得SESIQ没有充分发掘间隔查询间的共享操作, 因为范围查询的检索结果与覆盖查询的检索结果存在重复, 如表 1范围查询q的检索结果为{v, w}, 覆盖查询q的检索结果为{v, y, z}, 重复访问对象v.

下一步我们将探索基于二维转换的SESIQ实现策略, 从检索空间相交的角度深入挖掘间隔查询间重复访问的数据, 进一步减少访问数据量, 提升间隔查询的检索性能.