《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的有向无环图。

http://loopjump.com/wp-content/uploads/2022/04/image-20220426095737882-841x1024.png

!http://loopjump.com/wp-content/uploads/2022/04/image-20220426095737882-841x1024.png

Rules

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

例如，可以定义OrderedStream1和OrderedStream2：

http://loopjump.com/wp-content/uploads/2022/04/image-20220426102330915-300x92.png

!http://loopjump.com/wp-content/uploads/2022/04/image-20220426102330915-300x92.png

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

http://loopjump.com/wp-content/uploads/2022/04/image-20220426102346075.png

!http://loopjump.com/wp-content/uploads/2022/04/image-20220426102346075.png

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

Property

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

http://loopjump.com/wp-content/uploads/2022/04/image-20220426104512607-284x300.png

!http://loopjump.com/wp-content/uploads/2022/04/image-20220426104512607-284x300.png

Glue

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

http://loopjump.com/wp-content/uploads/2022/04/image-20220426104812197-1024x848.png

!http://loopjump.com/wp-content/uploads/2022/04/image-20220426104812197-1024x848.png

JOIN START的例子

http://loopjump.com/wp-content/uploads/2022/04/1-300x58.png

!http://loopjump.com/wp-content/uploads/2022/04/1-300x58.png

http://loopjump.com/wp-content/uploads/2022/04/2.png

!http://loopjump.com/wp-content/uploads/2022/04/2.png

http://loopjump.com/wp-content/uploads/2022/04/3.png

!http://loopjump.com/wp-content/uploads/2022/04/3.png

http://loopjump.com/wp-content/uploads/2022/04/4.png

!http://loopjump.com/wp-content/uploads/2022/04/4.png

http://loopjump.com/wp-content/uploads/2022/04/6.png

!http://loopjump.com/wp-content/uploads/2022/04/6.png

http://loopjump.com/wp-content/uploads/2022/04/7.png

!http://loopjump.com/wp-content/uploads/2022/04/7.png

http://loopjump.com/wp-content/uploads/2022/04/8.png

!http://loopjump.com/wp-content/uploads/2022/04/8.png

http://loopjump.com/wp-content/uploads/2022/04/9.png

!http://loopjump.com/wp-content/uploads/2022/04/9.png