基于过滤率估算的WFS服务空间连接优化策略

蓝贵文, 陈　骐, 陈天伟

(桂林理工大学 a.测绘地理信息学院;b.广西空间信息与测绘重点实验室, 广西 桂林　541004)



基于过滤率估算的WFS服务空间连接优化策略

蓝贵文, 陈骐, 陈天伟

(桂林理工大学 a.测绘地理信息学院;b.广西空间信息与测绘重点实验室, 广西 桂林541004)

摘要：网络要素服务是一种基于HTTP协议访问和更新矢量地理要素的接口规范。在面向Web服务的应用环境下, 用户的查询请求往往需要访问多个WFS服务，并且将服务的结果综合后得到最终结果。由于在WFS服务端生成GML、 网络间传输、 客户端解析等都需要耗费较长时间, 成为WFS服务分布式集成应用的瓶颈。本文基于空间半连接和迭代区域划分的分布式WFS服务查询优化策略, 为避免针对各子区域盲目地执行空间半连接, 提出一种基于过滤率估算的改进方法, 即根据在各子区域采用不同下载方法的空间对象过滤预估效果, 决定其数据下载方法。实验证明, 预先估算过滤率可提高优化策略的稳定性。

关键词：网络要素服务;空间连接;过滤率;查询优化

开放式地理信息联盟(open GIS consortium,OGC)制定的网络要素服务(web featire services,WFS)规范[1]定义了基于HTTP协议访问和更新矢量地理要素的接口, 被认为是功能最为强大、 应用前景最好的一种数据服务[2]。在面向WEB服务的应用环境下, 用户的查询请求往往需要访问多个服务并且将服务结果综合后得到最终结果[3-5]。由于在WFS服务器端生成GML、 网络间传输、 客户端解析都需要较长时间, 研究如何从不同站点的WFS服务中查询符合条件的空间对象集合, 减少查询执行代价, 具有重要的应用价值。

面向WFS服务的空间连接查询, 是一种特殊的分布式空间连接。目前国内外在分布式空间连接方面, 已进行了大量的研究, 典型者如陈荦[6]、 David.J.Abel等[7], 其应用目的主要针对分布式数据库环境。在此环境下, 各个网络节点可以感知其他节点数据的数据组织结构甚至索引结构并加以利用, 如陈荦[6]基于此特点提出了一种空间半联接索引的解决方案。与上述应用环境不同, WFS服务作为一个软件组件, 除了提供数据访问接口之外, 服务内部的数据组织、 索引结构对客户端是完全封闭的, 各WFS服务之间不能相互直接通信, 所有数据交换都以客户端为中转站, 使得常用的分布式空间连接优化策略难以用于提高WFS服务之间的空间连接查询效率。

要提高多个WFS服务的空间连接查询速度, 一是要确保各WFS服务能具有较好的响应速度, 如在服务器端采用空间索引技术, 或是优化GML Application Schema的定义降低GML 文档的内容冗余[3]；二是在客户端进行优化, 如文献[7-9], 总体而言还没有引起太多关注，客户端主要通过尽量过滤掉那些不可能出现在查询结果中的空间对象, 以减少查询导致的网络传输代价, 以及服务端生成及客户端解析GML文档所产生的开销。针对面向二路的WFS服务空间连接查询, 笔者曾结合空间半连接的思想, 通过对整体上没有表现出数据倾斜的两个数据集进行区域划分, 利用各局部区域表现出的数据倾斜特性, 采用相应的查询处理策略, 以达到降低网络数据传输费用的目的[8]，但未对各子区域的非备选空间对象的过滤效果进行评估, 因此在处理策略的选择上具有一定的盲目性。本文对二路空间连接查询中两个数据集在各子区域中的过滤效果进行评估, 以达到在各子区域选择合适的处理策略之目的。

1研究思路和方法

1.1面向WFS服务的二路空间半连接

David.J.Abel等提出了分布式空间数据库中空间半连接处理的思想[8],由于WFS服务作为一个软件组件,除了提供数据访问接口之外,服务内部的数据组织对客户端是完全封闭的,在两个WFS服务之间采用空间半连接处理,其过程如图1所示。

图1　面向WFS服务的二路空间半连接处理过程Fig.1　Workflow of spatial semi-join between two WFSs

设数据集R、 S由A、B两个服务提供, 可以根据一定的评判条件选择从A服务下载符合查询条件的数据R到本地, 然后把R中各空间对象的MBR(R)传送到B, MBR(R)作为用于查询的几何过滤条件, 获取数据集S的子集, 在本地对R和S′连接, 得到结果。显然, 空间半连接策略通过过滤掉非候选对象达到减少网络传输代价的目的。

需要注意的是, 图1中查询也可能先请求B, 这取决于采用何种评判条件, 一般先分别向A、B服务查询R、 S的对象数目|R|、 |S|, 优先下载对象数目为min(|R|, |S|)的数据集, 在已知两个数据集中每个对象的平均数据量r0、 s0时, 也可优先下载数据量为min(|R|×r0, |S|×s0)的数据集, 再在另一服务上作空间半连接。空间半连接策略并非对每种情形都有效, 最恶劣情况下被过滤的对象数目为0, 因此需要对过滤效果进行估算。

1.2非备选空间对象过滤率估计

进行空间半连接的作用在于过滤掉一些不可能在最终结果集中出现的空间对象, 以达到减少网络数据传输代价、 GML生成及解析代价的目的。本文用过滤率来评定空间半连接的过滤效果, 即被过滤掉的空间对象个数与不作优化时所需传输的空间对象个数的比值。

设R、 S两个数据集的对象数目|R|、 |S|, 执行某空间连接后的配对数为N，N可表示[10]为

(1)

NingAn等[11]、ChengyuSun等[12]提出改进的估算公式:

(2)

(3)

假定空间对象均匀分布, 可知, R中任一空间对象的最小包围矩形(MBR), 与S中任一空间对象的MBR, 相互碰撞的概率为SelectivityA, B。对于R数据集任一空间对象, S数据集中与其发生碰撞的空间对象数目的数学期望为

ER(NS)=|S|×SelectivityA, B,

(4)R中最终出现在结果中的空间对象个数估值为|rR|=min(|R|, N)。反之,也可以用同样的方法来估算ES(NR)、 |rS|。对R、 S的过滤率可定义为

(5)

可知, 如果过滤率FR太低, 执行空间半连接策略难以起到过滤效果。

对于图1中A、B两个WFS服务, 若先下载R到客户端, 再在B服务上执行空间半连接策略, 网络传输代价预期为|S|×s0-rS×s0+|R|×r0;反之，|R|×r0-rR×r0+|S|×s0。

d=(|S|×s0-rS×s0+|R|×r0)-

(|R|×r0-rR×r0+|S|×s0)

=rR×r0-rS×s0。

(6)

显然, 若d≪0, 应采用先从A服务下载R的策略;d≫0，则应采用先从B服务下载S的策略;d≈0空间半连接策略效果不明显。

2基于区域划分的二路WFS服务空间连接优化策略

以上选择率、 过滤率的估算公式是基于空间对象在概率意义上呈均匀空间分布情形下推导而得的, 因此如果在大范围内应用, 当空间对象数目较多时, 估算值与实际情况差距较大。一般将查询范围划分为多个相对小的子区域, 本文采用文献[7]中提出的迭代区域划分方法, 然后测定两个数据集子区域范围的空间对象数目。对任一子区域, 当其中的一个数据集在该范围内的对象数目少于一个设定的值M时, 认为不再需要进一步划分。本文对每个子区域分别用式(3)、 式(5)计算其选择率、 过滤率, 通过式(5)、 式(6)确定各子区域应采用的下载策略。由于空间对象在各子区域比整个查询区域更趋近均匀空间分布, 选择率、 过滤率估值更准确, 同时可以更好地利用子区域的数据倾斜来改进过滤效果。

以子区域边界作为几何查询条件, 各子区域边界上的空间对象存在重复计数现象。作为WFS服务的客户端, 数据未下载前, 无法确定重复计数。为了消除重复计数, 采用以下解决方法:(1)获取数据集在查询范围内空间对象的总数目及包含在各子区域内的空间对象数目;(2)以各子区域内部的空间对象个数为权, 利用加权法把跨越各边界的对象分配给各网格区域, 减少利用边界作为几何条件查询边界要素的代价。

各子区域的下载策略确定之后,调用WFS服务的GetFeature接口下载数据。以4×4格网区域划分为例(图2),用黑色、白色填充表达适用空间半连接策略的子区域,对黑色区域,应为先从A服务下载数据,然后在B服务对该子区域进行空间半连接;反之，白色子区域为先从B服务下载数据;斜线填充表达不适用空间半连接策略的子区域。由于WFS服务协议支持一个请求内可以包含多个查询条件,为避免多次请求,所有数据下载过程采用如下方式:(1)以所有黑色子区域、 斜线子区域的空间范围作为查询几何条件,从A服务下载数据;以所有白色子区域、 斜线子区域的空间范围作为查询几何条件, 从B服务下载数据。(2)在B服务对黑色区域进行空间半连接, 在A服务对白色区域进行空间半连接,获取备选空间对象到客户端。

图2　各子区域的空间连接执行策略选择Fig.2　Determination of execution plans for spatial joins of sub-areas

3实验结果及分析

本文设计了模拟实验对所提出的优化策略进行性能测试, 并与直接下载方法进行性能比较分析。

在实验中, 设置3个计算机节点, 其中两台为数据集服务器, 安装ArcGIS Engine Runtime、 .Net Framework 3.5、 IIS7.5, 部署使用C#语言编写的查询请求处理程序及相关空间数据集;一台客户端计算机, 部署使用C#语言编写的执行查询请求的客户端程序。实验环境为100 M局域网, 网络响应速度小于1 ms。实验数据取自ArcGIS 9.3附带的实验数据中美国铁路数据集(图层名为rail100k, Polyline型要素, 约13万条记录)、 水系数据集(图层名为dtl_wat, Polygon 型要素, 约39万条记录)。 查询条件为在查询窗口内相距不超过1.0 km的所有铁路与水系要素的配对。

设定3种查询范围300 km×300 km、 200 km×200 km、 100 km×100 km。随机选定查询区域后, 对该查询区域内分别采用M=100、 50、 10以及直接下载方法, 对其所耗费的时间进行对比分析。令X为直接下载方法所需时间与优化方法所需时间的比值, 则 “明显优于”定义为X>1.5;“略优于”, 1.0

当查询范围为300 km×300 km时, 在查询范围内的两个空间数据集中空间对象数目之和基本在1 000左右。对实验结果进行分析发现, 该优化方法在绝大多数情形下取得了较好的优化效果;约10%劣于直接下载法的情形, 主要是随机选中之区域, 在区域划分之后子区域仍不适于作空间半连接, 而区域划分及过滤率计算引起开销所致。当M值设置得过大时, 导致区域划分不充分, 会导致过滤效果不明显;当查询范围较小、 两个数据集数据分布比较均匀时, 过滤效果也会不明显, 需要设置合理的M值来抑制过度区域划分。此外, 在同等条件下与未采用过滤率作为子区域执行策略选择依据, 进行对比实验, 约17%(38次)略劣于或劣于直接下载法, 显然本文算法的稳定性得以提高。

表1　实验结果对比Table 1　Experiment comparison of two strategies　　　次

参考文献:

[1]OGC 09-025r2, OpenGIS Web Feature Service 2.0 Interface Standard[S].

[2]贾文珏, 龚健雅, 李斌. Web 要素服务的优化方法[J].测绘学报, 2005, 34(2):168-174.

[3]白玉琪, 杨崇俊.空间信息搜索引擎研究[J].中国矿业大学学报, 2004, 33(1):90-94.

[4]Jiang J, Yang C J, Ren Y C. A spatial information crawler for open GIS WFS[C]//Geoinformatics 2008 and Joint Conference on GIS and Built Environment(Volume 7143), Guangzhou:SPIE, 2008, 7143:2C-1-C-9.

[5]吴华意, 刘哲, 徐开明.地理信息服务集成的级联模式及其应用[J].测绘科学, 2010, 35(6):212-214.

[6]陈荤.分布式地理空间数据服务集成研究技术研究[D]. 长沙:国防科学技术大学, 2005.

[7]Abel D J, Ooi B C, Tan K L, et al. Spatial join strategies in distributed spatial DBMS[C]//Max J. Egenhofer, John R. Herring. Advances in Spatial Databases, Lecture Notes in Computer Science, 1995, 951:348-367.

[8]蓝贵文, 黄全义, 周晓青.一种面向WFS服务的分布式空间连接查询优化策略[J]. 武汉大学学报:信息科学版, 2009, 34(6):654-658.

[9]Gao B B, Xie C J, Sheng W T. Spatial grid services for adaptive spatial query optimization[C]//Geoinformatics 2008 and Joint Conference on GIS and Built Environment. Guangzhou: SPIE, 2008, 7143:0P-1-0P-9.

[10]Mamoulis N, Papadias D. Multiway spatial joins[J]. ACM Transactions on Database Systems, 2001, 26(4): 424-475.

[11]An N, Yang Z Y, Sivasubramanium A. Selectivity estimation for spatial joins[C]//Proceedings of 17th IEEE International Conference on Data Engineering.IEEE Computer Society,2001:368-375.

[12]Sun C Y, Agrawal D, El Abbadi A. Selectivity estimation for spatial joins with geometric selections[C]//Proceeding of 8th International Conference on Extending Database Technology Prague,Advances in Database Technolog—EDBT 2002.Heidelberg:Springer, 2002,2287:609-626.

文章编号:1674-9057(2016)02-0310-04

doi:10.3969/j.issn.1674-9057.2016.02.019

收稿日期：2014-10-28

基金项目：国家自然科学基金项目(41261088);广西空间信息与测绘重点实验室主任基金项目(桂科能1207115-11);广西“八桂学者”专项经费项目

作者简介：蓝贵文(1977—), 男, 博士, 副教授, 研究方向:地理信息系统,gwlan_770728@163.com。

中图分类号：P208

文献标志码：A

Spatial join optimization of web feature services based on early filtering estimation

LAN Gui-wen, CHEN Qi, CHEN Tian-wei

(a.College of Geomatics and Geoinformation; b.Guangxi Key Laboratory of Spatial Information and Geomatics, Guilin University of Technology, Guilin 541004,China)

Abstract:The OpenGIS Web Feature Service (WFS) Interface Standard provides an interface allowing requests and updates for geographical features across the web by the HTTP protocol. In such a web-service-oriented environment, an issued query may invovle two or more spatial datasets that are provided by different services at different sites. The processes of generating GML document in the WFS server, transmitting it to and parsing it at the client site, are very time-consuming, which causes a bottleneck to application of WFSs for distributed spatial data integration. This paper examines the query optimization strategy of spatial joins between OGC-compliant WFSs, based on the methods of spatial semi-join and partition based spatial-merge join. To avoid blindness of spatial semi-join operations of sub-areas, an improved strategy is proposed in this paper. In early phase the filtering ratios of spatial semi-joins for all the sub-areas are estimated and used to generate execution plans of spatial semi-join operations. The experimental result illustrates that compared with the previous methods, the proposed strategy can improve the performance of spatial joins between two WFSs.

Key words:web feature service; spatial join; filter ratio; query optimization

引文格式：蓝贵文, 陈骐, 陈天伟.基于过滤率估算的WFS服务空间连接优化策略[J].桂林理工大学学报，2016,36(2):310-313.