地球信息科学学报

地球信息科学学报 ›› 2017, Vol. 19 ›› Issue (5): 581-586.doi: 10.3724/SP.J.1047.2017.00581

• 地球信息科学理论与方法 •    下一篇

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

程昌秀(), 沈石, 杨山力   

  1. 1. 北京师范大学 地表过程与资源生态国家重点实验室,北京 100875;
    2. 北京师范大学 环境演变与自然灾害教育部重点实验室,北京 100875;
    3. 北京师范大学地理科学学部,北京 100875;
    4. 北京师范大学地理数据与应用分析中心,北京 100875
  • 收稿日期:2016-12-16 修回日期:2017-02-20 出版日期:2017-05-20 发布日期:2017-05-20
  • 作者简介:

    作者简介：程昌秀（1973-）,女,博士,教授,研究方向为空间数据库管理系统与GIS应用。 E-mail: chengcx@bnu.edu.cn

  • 基金资助:
    国家自然科学基金优秀青年科学基金项目（41222009）;国家自然科学基金面上项目（41271405）;中央高校基本科研业务费专项资金项目

Study on Spatial Heuristic Rules for Query Plan Enumeration

CHENG Changxiu*(), SHEN Shi, YANG Shanli   

  1. 1. State Key Laboratory of Earth Surface Processes and Resource Ecology, Beijing Normal University, Beijing 100875, China;
    2. Key Laboratory of Environmental Change and Natural Disaster, Beijing Normal University, Beijing 100875, China;
    3. Faculty of Geographical Science, Beijing Normal University, Beijing 100875, China;
    4. Center for Geodata and Analysis, Beijing Normal University, Beijing 100875, China
  • Received:2016-12-16 Revised:2017-02-20 Online:2017-05-20 Published:2017-05-20
  • Contact: CHENG Changxiu E-mail:chengcx@bnu.edu.cn

RichHTML

PDF (PC)

赞

摘要：

在查询计划枚举空间巨大的情况下,空间启发式规则对排除一些不可行或低效的查询计划、提高系统的执行效率有重要意义。本文基于空间等价类、空间约束对的概念,提出了空间连接应建立在空间等价类或空间约束对上的启发式规则,构建了查询计划树中各类连接关系的放置规则以及空间等价类的连接递推规则,提出了空间索引替换表以及空间索引的若干放置规则。论文阐述了如何尽可能用低代价的空间操作,尽早过滤出较少的数据结果,降低参与后续运算的数据量,提高系统查询效率。最后,以空间查询案例为例,展示了这些规则在缩小枚举空间方面的作用。

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

Abstract:

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 for query optimizer, but also for SQL programmer.

Key words: spatial query, enumeration of query plans, spatial heuristic rules, spatial constrain pairs, join tree