一种面向并行查询的森林资源小班数据划分粒度研究

卜祥亮，唐小明，殷君茹，李惺颖

（1.北京林业大学 水土保持学院，北京 100083；2.中国林业科学研究院 资源信息研究所，北京100091；3.广西林业勘测设计院，广西 南宁 530011）

一种面向并行查询的森林资源小班数据划分粒度研究

卜祥亮1，2，唐小明2，殷君茹2，李惺颖3

（1.北京林业大学 水土保持学院，北京 100083；2.中国林业科学研究院 资源信息研究所，北京100091；3.广西林业勘测设计院，广西 南宁 530011）

为在并行环境下高效地利用并行计算资源，促进静态负载均衡，从而总体上提高森林资源小班数据在并行环境下查询的响应效率，通过分析数据划分粒度与查询效率的关系，建立了数据划分粒度与查询效率的关系模型。采用辽宁省森林资源小班数据，实验验证了该模型，并取得森林资源小班数据的最佳划分粒度。实验表明，在最佳划分粒度进行并行查询时，查询效率明显优于其它划分粒度。

森林资源小班数据；并行查询；数据划分粒度；查询效率

森林资源小班数据能直观地反映森林资源的动态变化，是森林资源经营现状的直观体现，也是森林资源信息化管理的基础[1]。经过多年的森林资源普查，森林资源小班数据数量巨大，且类型多样。在森林资源信息化管理过程中，对森林资源小班数据实时海量计算能力的要求不断提高，单服务器计算能力越来越不能满足需求，并行计算作为求解各种计算密集型、数据密集型负载调度问题的有效手段，逐渐受到研究学者的关注。

并行计算分为计算并行与数据并行。计算并行是将一个计算任务划分成不同或相同的计算部分分配给不同的处理器同时进行计算。数据并行是将计算数据划分成若干部分，分别映射到不同的处理器中，每个处理器对所分配的数据进行计算。数据划分粒度分别在计算划分和负载均衡控制方面对数据并行计算性能产生关键性的影响，粒度过粗可能达不到并行的效果，难以进行有效的负载均衡调度；而粒度过细虽然能促进负载均衡，但线程等待和调度所花费时间很可能比计算所用时间长，从而降低并行计算的效率。

目前，众多学者对并行计算的研究多集中在并行计算方法[2-6]与计算粒度[7-11]对并行计算效率的影响方面，鲜有涉及到数据划分粒度，有部分学者研究了空间数据的划分方法[12-13]，实现了对空间数据的均衡划分，但没有进一步量化说明数据划分成什么粒度可以实现并行查询效率的最优化。虽然宋效东等[14]分析了数据划分的机制，并对并行地形分析中的数据划分粒度进行量化研究，但这种划分机制只适用于地形分析过程中，具有局限性，不适用于森林资源小班数据的数据粒度划分。

本研究综合考虑了已有的研究成果，探讨将并行计算应用到林业业务中，并进一步展开并行数据粒度的量化研究，通过分析森林资源小班数据的特征及查询特点，分析影响并行计算效率的因素，从而构建数据划分粒度模型，并使用辽宁省森林资源小班对数据划分粒度进行量化研究与实验。

1 森林资源小班数据特点及查询特点

1.1 森林资源小班数据特点

森林资源数据来源广泛，根据调查的地域范围和目的，森林资源数据可分为国家森林资源连续清查数据（一类调查数据）、森林资源规划设计调查数据（二类调查数据）、作业调查数据（三类调查数据）[15]。其中二类调查与三类调查是森林资源小班数据来源的基础。森林资源小班是指经营目的与经营措施相同且连片的森林斑块的集合体，是森林资源管理最基本的经营单位，也是清查森林资源、统计计算和资源管理最基本的单位[16]。

森林资源小班数据由空间信息与属性信息组成。空间信息表示小班的位置、形状、大小及其分布特征诸多方面的信息，是区别于一般信息的标志，主要包括小班边界、小班面积等因子。属性信息是由表示小班属性信息的一系列属性因子组成，这些因子完整描述小班数据所包含的林地调查信息。根据属性因子表达信息类型不同，因子主要分类如表1所示。

表1 属性因子分类Table 1 Classification of attribute factors

1.2 查询特点

森林资源小班数据是森林资源数据的基础，其广泛应用于森林资源管理、公益林建设、森林防火、方针政策制定等多个方面。这些业务的应用需要对森林资源小班数据进行各种统计与分析，而查询是统计与分析的基础。森林资源小班数据根据业务需求，通常分为属性查询与空间查询两种方式。

（1）属性查询。在森林资源小班数据库中获取满足属性约束条件的森林资源小班数据，查询过程中只查询属性因子。属性查询分为单因子查询与多因子查询两种方式，单因子查询为设置一个属性因子查询条件进行查询，如获取林种为“护岸林”的所有数据；多因子查询为设置两个或更多属性因子查询条件，如获取林种为“护岸林”且地类为“造林未成林地” 的所有数据。

（2）空间查询。在森林资源小班数据库中获取所有既满足空间约束条件又满足属性约束条件的森林资源小班数据，查询过程中既需要查询空间因子也需要查询属性因子。空间约束条件包括两个方面：一方面是查询条件的几何形状，即要查询的是点、线还是面等；另一方面是带空间谓词的逻辑表达式，即相交、包含和分离等条件。空间查询结果通过空间约束条件与属性约束条件查询结果求交取得。空间查询一般先通过外包矩形进行初步判断，排除不满足外包矩形的小班数据，对满足的数据分析计算，确定最终结果。通过数据划分，数据由大粒度划分为适当的小粒度，空间查询时可通过初步判断排除更多的无关数据，减少查询扫描的数据量，从而提高查询效率。

2 数据粒度模型

数据粒度划分是并行计算中计算的基础，数据划分的质量和效果影响并行计算的效率[17]。数据划分既要考虑划分数据的特点，也要考虑计算任务的特点。计算任务一般是指分解到各个处理器上执行的计算，对森林资源小班数据的计算为简单的查询计算，这属于计算密集型的计算。对原始数据依赖强的计算，数据划分方式通常比较简单，不需要考虑数据的变化与抽象。本研究针对森林资源小班数据的查询计算，其只针对小班数据本身，所以本文在数据划分时只是对小班数据按记录进行划分。

3 实验分析与验证

为得到森林资源小班数据在并行环境下最佳划分粒度，作者设计了森林资源小班数据的并行查询实验。实验数据为辽宁省森林资源小班数据，数据量为1 535 720条小班记录，3 035 MB。测试环境为一台服务器。服务器配置：处理器为Inter Xeon E5 2609 2×4核，2.40 GHz，内存为24 G。数据存储于oracle spatial中，oracle版本为11 G，初始数据划分粒度Dsize分别设置为0.1万、0.5万、1万、5万、10万、20万、40万、75万、153.572万条小班记录，与之对应的数据表数量分别为1 536、308、154、31、16、8、4、2、1。

图1 tcalculate，tthread与数据粒度的关系Fig.1 Relationship between tcalculate, tthread and data granularity

图2 T与数据粒度关系Fig.2 Relationship between T and data granularity

为使得实验更加公平合理，首先要分析并行查询流程，尽量消除影响查询实验的外部因素。森林资源小数据并行查询流程如图3所示。

从流程图3中可以看出，查询过程主要分为由客户端向服务端发送查询请求，服务端接收到请求首先进行语句解析（查询高速缓存，语句合法性检查，语言含义检查，获得对象解析锁，数据访问权限的核对，确定最佳执行计划），确保处理器理解语句的表达。然后服务端为每个处理器分配查询任务，实现并行查询。处理器执行分配到的查询任务，查询任务结束之后，进行数据提取，最后将结果返回给客户端。在查询过程不存在缓存的情况下，不同查询条件对整个查询流程影响最大的分别是提取数据与查询结果返回客户端这两个操作流程，在这两项流程中，不同查询条件命中的记录数不同，命中记录数越多，数据量越大，提取数据与返回数据越慢，消耗时间越长，这便会涉及到数据传输效率问题，不属于本文求最佳粒度的研究范畴。为消除这种影响，本文在并行查询时只单纯记录命中记录数，不记录整条记录的信息，这样可以最小化提取数据量，不记录查询结果返回时间。因此，本文记录的查询时间分为语句解析、查询任务分配、查询任务执行、数据提取四部分。

图3 并行查询流程Fig.3 Process of parallel query

3.1 属性查询实验

根据上文提出并行查询流程，本实验首先对森林资源小班数据进行属性查询实验，求出属性查询条件下森林资源小班数据的最佳划分粒度。为使得实验更具有说服性，本文设置单因子查询条件（见表2）和多因子查询条件（见表3），不同查询条件查询命中记录数不同。

表2 单因子属性查询条件Table 2 Query conditions of single-factor attribute

图4为不同条件并行查询的结果。2种查询曲线总体上是呈现上文所描述的抛物线类型，证明上述数据粒度模型合理。随着粒度的增大，单粒度查询时间变大，线程等待与调度时间变小，最终在某个点达到极值，总体查询时间最小。

数据粒度在0.1万～5万内查询时间明显降低，这段粒度区间内粒度数量快速减少，但总体上粒度不大，单粒度查询时间相差不大，粒度数量却快速减少，线程等待与调度减少的时间大于由于计算不均衡带来的增加时间，导致总体查询时间减少。

数据粒度在5万～20万内总体查询时间比较低且稳定，这段区间是粒度增大导致计算时间增加与粒度数量减少导致线程等待与调度时间减少两者相互博弈的过程，查询时间相对来说比较稳定且处于最低位。

数据粒度在20万～153.572万内查询时间随着粒度增大逐渐增大，在这段区间内数据粒度数量快速减少，线程等待与调度时间几乎可以忽略不计，但在这段区间内数据粒度特别大，计算过程中容易造成负载不平衡，导致计算时间的增大，从而总体查询时间增大。

表3 多因子属性查询条件Table 3 Query conditions of multiple-factor attribute

图4 属性并行查询时间Fig.4 Attribute parallel query time

因此通过本试验可以得出森林资源小班数据属性并行查询的最佳划分粒度区间为5万～20万。

3.2 空间查询实验

本文设定空间查询实验，实验中随机选定一块空间区域（见图5），然后叠加属性查询条件“地类为阔叶林”，实验结果如图6所示。图6中可以看出查询结果同数据粒度划分模型趋势一致，呈现抛物线类型，最佳划分粒度为5万左右。 数据粒度在小于最佳值时同属性查询耗时相比下降不明显，这是由于数据粒度越小，空间查询通过外包矩形排除的无关数据越多，真正扫描的数据越少，tcalculate越小导致的。

图5 空间并行查询范围Fig.5 Range of spatial parallel query

4 结 论

本研究分析了森林资源小班数据特点及查询特点，结合并行计算效率影响因素和粒度划分最优原则，构建了数据划分粒度模型，探讨最优数据划分粒度，并进行相关实验验证，实验表明森林资源小班数据并行查询效率与数据划分粒度具有很强相关性，不同的数据划分粒度下查询效率有明显的差异。属性查询实验结果显示，森林资源小班数据属性查询最佳划分粒度为5万～20万；空间查询实验结果显示，森林资源小班数据空间查询最佳划分粒度为5万左右；综合2种查询实验结果，其最佳划分粒度应为5万左右。

本研究得出的划分粒度，可为并行环境下森林资源小班数据进行数据划分时提供参考依据，进行更精确化的数据划分，最大程度提高并行查询效率。森林资源小班数据有自己独有的管理特点、应用特点，森林资源数据的管理、应用大多是以行政区范围为单位进行的。森林资源小班数据最佳划分粒度应用到大区域时，数据划分粒度要与某一级行政级别的小班数量之间平衡，适当放宽数据粒度范围，使得查询效率与管理效率达到最优化。

图6 空间并行查询时间Fig.6 Spatial parallel query time

[1] 汪 璀.县级森林资源小班数据更新系统的研建[D].北京:北京林业大学, 2010.

[2] 朱荣华.一种 CRC 并行计算原理及实现方法[J].电子学报,1999, 27(4): 143-145.

[3] 饶文碧,张 莉.网络分布式环境下的并行计算方法[J].武汉工业大学学报, 2000, 22(1): 54-56.

[4] 杨 鑫,许端清,杨 冰.基于不规则性的并行计算方法[J].浙江大学学报:工学版 ,2013,47(11):2057-2064.

[5] 蒋波涛,王艳东.基于MapReduce 的地图代数并行计算方法[J].测绘地理信息, 2014, 39(3): 51-55.

[6] Lowenthal D K, Freeh V W, Andrews G R.Using fine-grain threads and run-time decision making in parallel computing[J].Journal of Parallel and Distributed Computing,1996,37(1):41-54.

[7] 武金瑛,王希诚.一种粗粒度并行遗传算法及其应用[J].计算力学学报, 2002, 19(2): 148-153.

[8] 樊 雷,邵之江,王海清.细粒度并行计算和最佳负载均衡设计[J].中国科学技术大学学报,2005,35(增刊):199-204.

[9] 刘伟峰,王智广.细粒度并行计算编程模型研究[J].微电子学与计算机,2008, 25(10): 103-106.

[10] 胡晓力,田有先.多粒度并行计算集群研究与应用[J].电力学报, 2008, 22(4): 436-438.

[11] Antonopoulos C D, Blagojevic F, Chernikov A N,et al.A multigrain Delaunay mesh generation method for multicore SMT-based architectures[J].Journal of Parallel and Distributed Computing, 2009, 69(7): 589-600.

[12] 赵春宇,孟令奎,林志勇.一种面向并行空间数据库的数据划分算法研究[J].武汉大学学报:信息科学版, 2006, 31(11):962-965.

[13] 贾 婷,魏祖宽,唐曙光,等.一种面向并行空间查询的数据划分方法[J].计算机科学, 2010, 37(8): 198-200.

[14] 宋效东,窦万峰,汤国安,等.分布式并行地形分析中数据划分机制研究[J].国防科技大学学报, 2013, 35(1): 130-135.

[15] 林 辉, 熊育久, 孙 华, 等.湖南省森林资源连续清查遥感应用研究[J].中南林业科技大学学报, 2007, 27(4): 33-38.

[16] 谭 伟,张 雁,许华容.基于 ArcEngine 的森林资源小班编辑功能的探讨[J].林业资源管理, 2012, (5): 122-130.

[17] 胡 霞.并行计算如何用于科学问题研究[J].科技资讯,2009,(27): 176-176.

Study on forest resources sub-compartment data partition granularity oriented parallel query

BU Xiang-liang1,2, TANG Xiao-ming2, YIN Jun-ru2, LI Xing-ying3
(1.College of Soil and Water Conservation, Beijing Forestry University, Beijing 100083, China; 2.Research Institute of Resource Information Techniques , Chinese Academy of Forestry, Beijing 100091, China; 3.Guangxi Forest Inventory & Planning Iinstitute,Nanning 530011, Guangxi, China)

In order to use the parallel computing resources with high-efficiently in parallel environment, promote static load balancing,thus overall improving the response efficiency of forest resources sub-compartment data inquired in parallel environment, through analyzing the relationship between data partition granularity and computational efficiency, the relational model of data partition granularity and query efficiency was established.By using forest resources sub-compartment data of Liaoning Province, the model was verified by the experiments, meanwhile, the optimum data partition granularity of forest resources sub-compartment data was obtained.The experimental validation results show that under the condition of parallel query with the optimal data partition granularity, the query efficiency is significantly higher than that with the other partition granularity.

forest resources sub-compartment data; parallel query; data partition granularity; query efficiency

S757.43+3；F307.2

A

1673-923X(2015)09-0039-06

10.14067/j.cnki.1673-923x.2015.09.007

2015-02-10

国家林业公益性行业科研专项（201304215）

卜祥亮，硕士研究生 通讯作者：唐小明，研究员，博士生导师；E-mail: tangxm@caf.ac.cn

卜祥亮，唐小明，殷君茹，等.一种面向并行查询的森林资源小班数据划分粒度研究[J].中南林业科技大学学报，2015,35(9): 39-44.

[本文编校：谢荣秀]