Grammar-like Functional Rules - for Representing Query Optimization Alternatives
概述
优化器如果要做到可扩展，则要求执行计划的变换策略需要作为数据而不是代码存在。本质上优化器就是一个专家系统，使用strategy rules将一个查询计划变成另一个等价的更好的计划。这种灵活可扩展带来一个问题是 不够高效：在任意一步，都需要检查很多转换规则的使用条件，而且可能有多个规则可以应用。
这篇论文提出了一种新的组织和应用rule的思路，其本质是construct一个计划，而不是alter或match一个计划。
核心的想法是使用一种类似于文法的方法，以DB操作接口（如TableAccess）作为终结符，以优化等价变换规则作为文法的推导。Token本身还需要实现参数化，以支持丰富的关系操作语义。
Foundamental Observations
- 所有的算子都以表对象作为输入和输出。
- 优化器构造的计划最终是一串算子，该串算子可被执行器执行，也就是说合法的执行计划可被定义为某个文法的language。
- 转换规则的应用之间存在一些依赖，例如join order规则应该在table access之前。
- 一些等价的计划会存在一部分相同的计划片段。
- 指定规则应用条件比指定规则转换难。
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的例子
