A-A+

Grammar-like Functional Rules - for Representing Query Optimization Alternatives

2021年02月13日 数据库 暂无评论 阅读 50 次

 

《Grammar-like Functional Rules - for Representing Query Optimization Alternatives》 SIGMOD 1988

概述

优化器如果要做到可扩展,则要求执行计划的变换策略需要作为数据而不是代码存在。本质上优化器就是一个专家系统,使用strategy rules将一个查询计划变成另一个等价的更好的计划。这种灵活可扩展带来一个问题是 不够高效:在任意一步,都需要检查很多转换规则的使用条件,而且可能有多个规则可以应用。

这篇论文提出了一种新的组织和应用rule的思路,其本质是construct一个计划,而不是alter或match一个计划。

核心的想法是使用一种类似于文法的方法,以DB操作接口(如TableAccess)作为终结符,以优化等价变换规则作为文法的推导。Token本身还需要实现参数化,以支持丰富的关系操作语义。

Foundamental Observations

  1. 所有的算子都以表对象作为输入和输出。
  2. 优化器构造的计划最终是一串算子,该串算子可被执行器执行,也就是说合法的执行计划可被定义为某个文法的language。
  3. 转换规则的应用之间存在一些依赖,例如join order规则应该在table access之前。
  4. 一些等价的计划会存在一部分相同的计划片段。
  5. 指定规则应用条件比指定规则转换难。

Plan

文法的终结符是一些基本操作,文中称为LOLEPOP (LOw-LEvel Plan OPerator),例如JOIN、UNION、SHIP、ACCESS、SORT等等。一个执行计划 Plan或者叫QEP(query evaluation plan)是LOLEPOP的有向无环图。

Rules

规则 STAR (STrategy Alternative Rules) 是一个命名的参数对象,包含一个或多个转换的定义。一个转换的定义包括应用条件,一个计划或者其他STAR。从这里可以看出,STAR实际上就是映射到文法中的非终结符。

例如,可以定义OrderedStream1和OrderedStream2:

 

或者定义有两个转换的OrderedStream:

类似于文法的初始状态,这里也有一个root STAR。从root STAR开始,以一种top-down的方式进行,每个推导的fanout一般不多,而且多个推导之间可以并行进行。

Property

每张表都有一组属性,分为三类:relational(例如projection/join), physical(例如tuple order), estimated(基于前两者的代价模型)。

Glue

Glue机制是实现某些属性的粘合剂。例如下图中的SHIP(修改site属性,即执行的机器节点)、SORT(修改order属性)等。

 

JOIN START的例子

 

 

 

 

 

 

标签:

给我留言