查询计划枚举中的空间启发式规则研究  

Study on Spatial Heuristic Rules for Query Plan Enumeration

作　　者：程昌秀[1,2,3,4] 沈石 杨山力 

机构地区：[1]北京师范大学地表过程与资源生态国家重点实验室,北京100875 [2]北京师范大学环境演变与自然灾害教育部重点实验室,北京100875 [3]北京师范大学地理科学学部,北京100875 [4]北京师范大学地理数据与应用分析中心,北京100875

出　　处：《地球信息科学学报》2017年第5期581-586,共6页Journal of Geo-information Science

基　　金：国家自然科学基金优秀青年科学基金项目(41222009);国家自然科学基金面上项目(41271405);中央高校基本科研业务费专项资金项目

摘　　要：在查询计划枚举空间巨大的情况下,空间启发式规则对排除一些不可行或低效的查询计划、提高系统的执行效率有重要意义。本文基于空间等价类、空间约束对的概念,提出了空间连接应建立在空间等价类或空间约束对上的启发式规则,构建了查询计划树中各类连接关系的放置规则以及空间等价类的连接递推规则,提出了空间索引替换表以及空间索引的若干放置规则。论文阐述了如何尽可能用低代价的空间操作,尽早过滤出较少的数据结果,降低参与后续运算的数据量,提高系统查询效率。最后,以空间查询案例为例,展示了这些规则在缩小枚举空间方面的作用。Query plan enumeration and query cost estimation are two important steps in a query optimizer of DBMS. The query plan enumeration is responsible for enumerating some candidate query plans with best or better plan. The query cost estimation is used to choose the best plan for execution. However, if the candidate query plans in the first step are too many, the second step has to spend more time on estimating them. In order to save the cost of estimation time and improve execution efficiency of the system, spatial heuristic rules are used to eliminate some impracticable query plans. This paper firstly explained some basic concepts, i.e. query graph, joined tree, and query plan. Then, we put forward three heuristic rules for spatial equal classes and spatial constrained pairs. The first is that spatial join operators should be established on spatial equal classes or spatial constrained pairs. The second is that the orders of join operators should be equal classes, spatial equal classes, non-Cartesian products of ordinary attributes, spatial constrained pairs and Cartesian products of ordinary attributes. The last one is a recursion rules about spatial equal classes. It means, only the attributes in spatial equal classes of a query plan could be transmitted each other. After that, this paper puts forward two rules for spatial indexing tables. The first is that it＇s better to replace a spatial table with its spatial indexing, when there is a spatial predicate on some spatial attributes. The second is the spatial indexing table must be on the top of its original table in a query plan and there should be a TID join between spatial index table and its original table. In the following sections, we explains the rules mentioned above and analyses how to improve query efficiency by using low cost operation as soon as possible and how to filter out candidate data as few as possible. At last, we present a sample to show how to eliminate some impracticable query plans by those spatial heuristic rules. Those rules are not only

关 键 词：空间查询 计划枚举 空间启发式规则 空间约束对 连接树 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]