6空间查询与优化

第六章查询处理与优化主要内容查询处理概览空间操作计算查询优化关系表达式等价规则选择执行计划查询处理概览查询处理是指从数据库中提取数据的一系列活动。主要包括：将用高层数据库语言表示的查询语句翻译为能在文件系统这一物理层次上实现的表达式为优化查询而进行各种转换查询的实际执行输入：SQL语句；输出：满足查询条件的数据查询处理基本步骤语法分析与翻译优化执行关系代数表达式执行计划查询语句查询结果查询处理概览语法分析与翻译优化器执行引擎数据数据有关数据的统计值查询处理概览查询优化概念查询优化是为关系代数表达式的计算选择最有效的查询计划的过程查询执行计划：用于计算查询的原语序列执行原语：加了“如何执行”注释的关系代数运算（选择、投影……）根据选择的算法对文件记录进行操作查询处理概览查询优化过程代数优化力图找出与给定关系代数表达式等价的但执行效率更高的一个表达式执行策略选择对查询语句处理的详细策略的选择选择执行运算所采用的具体算法选择将使用的特定索引等等查询处理概览可能性SQL语言和关系代数表达式的非过程化特点可行性查询优化器具有丰富的可使用信息数据库发生变化时优化器容易再次进行优化优化器能够对多种实现策略逐一进行考虑优化器集中了最优秀的程序员的智慧和经验空间操作计算和关系数据运算的区别空间数据没有公认标准定义的运算，关系数据库中的运算很固定；空间对象的空间位置和范围在二维平面上定义，不能自然排序成一维数组；检测空间关系计算代价非常高，不能再假定空间数据库中I/O代价仍然远超过CPU代价空间操作计算空间操作的基本类型更新操作空间对象的创建、修改和删除空间选择点查询：给定点，找出包含它的空间对象PointQuery，其中：O.G为对象O的几何信息范围查询：给定多边形（矩形时称作“窗口”），找出与之相交的空间对象RangeQuery空间操作计算空间连接空间谓词作为连接条件空间连接的变形-Overlay（地图覆盖/叠加分析）两个空间对象集合合并形成一个新的集合，新对象的集合边界由覆盖操作所指定的非空间属性来决定如征地管理中，范围涉及一块农用地和一块村镇建设用地，征地后统一变成城镇用地。可以是多种空间关系（谓词）相交、包含、距离、西北（方位）、邻接、交叠……例：查找所有“交叠”关系的林分和冲积平原：SELECTfs.name,fp.nameFROMfrorest_standfs.flppdi_plainfpWHEREoverlay(fs.g,fp.g);空间操作计算空间聚集（聚类）空间聚集通常是按距离进行聚集，查找距离给定对象最近的所有对象。例如：找出距离露营地最近的河流空间操作计算空间操作的两步处理过滤步骤空间对象用MBR表示大大降低计算复杂度得到近似的结果精炼步骤采用精确的几何信息进行精确计算计算代价高可能在SDB之外实现空间操作计算空间选择查询两种常用的查询点查询：检索鼠标点中的林分SELECTf.nameFROMforest_standfWHEREwinthin(:point,f.geometry);找出与当前窗口相交的林分，以便显示林分地图SELECTf.nameFROMforest_standfWHEREintersects(f.geometry,:window);对于点查询和范围查询实现方法依赖于数据文件的存储组织主要是过滤步骤。空间操作计算查询的三种算法未排序无索引的数据文件穷举法全表扫描，判别每条记录根据两步处理（过滤+精炼），利用林分的MBR代价O(n)，n=关系forest_stand存储的页面数具有空间索引的数据文件普遍采用R树，按照MBR索引，代价O(logn)R树的缺点是MBR允许交叠，可能导致需要搜索多个子树R+树解决了上述问题，但副本的存在可能增加搜索时间和节点溢出空间操作计算采用空间填充曲线散列将二维空间的点映射为一维Z序和Hilbert曲线近似实现保持“位置相邻”映射后采用一般的排序树B树或B+树索引点查询代价O(logBn)范围查询代价O(logBn)+查询结果集大小/记录的聚集程度组合空间选择组合条件表示为合取范式非空间谓词计算代价大致相同，处理顺序不重要空间谓词计算代价高而且差别大，处理顺序对总代价影响大对每个空间谓词计算代价等级选择性：输出集合和输入集合数量比，体现I/O代价差异代价：对单个元组处理的平均代价，体现CPU代价按照代价等级的升序来计算空间谓词空间连接实现由于空间索引的限制，主要考虑过滤步骤（MBR近似计算）嵌套循环有空间索引的嵌套循环基于分块的空间连接类似散列连接空间聚集实现最近邻居算法在空间索引树上进行遍历并修剪子树可扩展为K个最近邻居保留K个最好候选子树或对象空间查询优化查询优化的基本步骤与关系数据库相同代数优化找出等价的但执行效率更高的一个表达式执行策略选择（动态规划）选择执行运算所采用的具体算法选择将使用的特定索引等等需要考虑空间谓词特点计算代价高（可能超过I/O代价）代价差异大（注意计算顺序）代数优化：等价变换规则将一个表达式转换为与之等价的另一个表达式的规则规则来源于代数系统的运算性质交换律结合律分配律生成多个等价表达式为可选的执行计划等价变换规则选择运算的级联：组合选择运算可分解为单个选择运算的序列σθ1∧θ2(E)=σθ1(σθ2(E))尽量将所有非空间条件右移选择运算满足交换律1(σθ2(E))=σθ2(σθ1(E))先计算非空间条件，然后代价低的空间条件投影运算的级联：投影运算序列中只有最后一个运算是需要的，其余的可省略∏L1(∏L2(…(∏Ln(E))…))=∏L1(E)等价变换规则选择与笛卡尔积以及theta连接相结合σθ(E1×E2)=E1||θE2σθ1(E1||θ2E2)=E1||θ1∧θ2E2theta连接运算满足交换律E1||θE2=E2||θE1自然连接也满足交换律E1||E2=E2||E1等价变换规则连接运算的结合律自然连接运算满足结合律(E1||E2)||E3=E1||(E2||E3)theta连接具有以下方式的结合律(E1||θ1E2)||θ2∧θ3E3=E1||θ1∧θ3(E2||θ2E3)其中θ2只涉及E2与E3的属性由于任意一个条件都可为空，因此笛卡尔积运算也具有结合律。等价变换规则选择运算在下面两个条件下对theta连接运算具有分配律当选择条件θ0的所有属性只涉及参与连接运算的表达式之一(E1)时：σθ0(E1||θE2)=(σθ0(E1))||θE2当选择条件θ1只涉及E1的属性，选择条件θ2只涉及E2的属性时：σθ1∧θ2(E1||θE2)=(σθ1(E1))||θ(σθ2(E2))等价变换规则投影运算对theta连接运算具有分配律令L1、L2分别是E1、E2的属性。假设连接条件θ只涉及L1∪L2中的属性，则：∏L1∪L2(E1||θE2)=(∏L1(E1))||θ(∏L2(E2))考虑连接E1||θE2。令L1、L2分别是E1、E2的属性；令L3是E1中出现在连接条件θ中但不在L1∪L2中的属性；令L4是E2中出现在连接条件θ中但不在L1∪L2中的属性。那么：∏L1∪L2(E1||θE2)=∏L1∪L2((∏L1∪L3(E1))||θ(∏L2∪L4(E2)))等价变换规则集合运算并与交满足交换律E1∪E2=E2∪E1E1∩E2=E2∩E1集合差运算不满足交换律集合运算并与交满足结合律(E1∪E2)∪E3=E1∪(E2∪E3)(E1∩E2)∩E3=E1∩(E2∩E3)集合差运算不满足结合律等价变换规则选择运算对并、交、差运算具有分配律σp（E1-E2）=σp（E1）-σp（E2）σp（E1∪E2）=σp（E1）∪σp（E2）σp（E1∩E2）=σp（E1）∩σp（E2）进一步有σp（E1-E2）=σp（E1）-E2σp（E1∩E2）=σp（E1）∩E2但对于∪不成立等价变换规则投影运算对并运算具有分配律∏L(E1∪E2)=(∏L(E1))∪(∏L(E2))等价变换规则规则只说明两个表达式等价，并不说明哪一个更好连接的次序很重要，好的连接次序序列产生小的中间结果对于空间数据库考虑空间谓词计算代价I/O和CPU代价的均衡好的空间谓词计算次序产生小的计算代价规则的使用会产生大量的等价表达式，优化器要采用适当的技术来减少所产生的表达式的数量选择执行计划关系代数表达式的基础上，执行计划进一步说明：每个运算的实现算法各运算的执行顺序是否采用流水线技术注意：每个运算的最小代价算法组合起来不一定是整个表达式的最佳算法，必须考虑各个运算之间的相互作用。选择执行计划的优化算法基于代价的方法通过使用等价规则为给定的查询语句产生一系列查询执行计划，并选择其中代价最小或接近最小的启发式方法运用启发式规则，对关系代数表达式进行等价变换常用的规则：尽早进行选择运算尽早进行投影运算避免进行笛卡尔积运算……基于代价的方法等价于给定查询的不同查询计划可能很多，因此优化的代价太大采用一些预设方法来减少需要考虑的表达式的数目采用启发式方法来减少需考虑的表达式的数目基于代价的方法减少需要考虑的表达式只考虑左深连接次序r1r2r3r4r5左深连接树r1r2r3r4r5非左深连接树基于代价的方法找多个关系的最佳连接顺序时，不是简单地考虑所有的可能顺序，而是为每个子集找出最佳连接顺序，这样能大大减少需要检查的连接顺序的总数如果检查一个表达式的某部分后发现这一部分的最小代价已经比先前已检查过的整个表达式的执行计划的最小代价要大，则可以终止对这个表达式的检查。没有必要对包含该子表达式的任何完整表达式进行检查启发式优化将合取选择分解为单个选择运算的序列，这有助于将选择运算往查询树下层移将非空间选择尽量下移代价小的空间选择下移把选择运算在查询树上下推到最早可能执行的地方例如，尽可能将σθ(r||s)转换成σθ(r)||s或r||σθ(s)考虑CPU代价极高的空间谓词，不一定移到最下启发式优化（例）启发式优化（例）启发式优化（例）启发式优化（例）启发式优化通过使用||的结合律，重新组织查询树，使得具有限制比较严格的选择运算的叶结点关系首先执行将跟有选择条件的笛卡尔积运算替换成连接运算将投影属性加以分解并在查询树上尽可能往下推，必要时可以引入新的投影运算识别那些可用流水方式执行其运算的子树，并采用流水线方法执行之分布式数据库的查询优化全局表和本地表分布与冗余分片策略（垂直分片、水平分片）数据的分布性产生了通信代价尽量减少网络传输消除查询运算无关的数据传输分布式数据库的查询优化半连接选择运算提前，减少需要传输的元组只传输主码或连接属性的不重复值连接完成后，只传输输出属性