A-A+

Extensible/Rule Based Query Rewrite Optimization in Starburst

2021年02月13日 数据库 暂无评论 阅读 49 次
      《Extensible/Rule Based Query Rewrite Optimization in Starburst》SIGMOD 1992

这篇文章是介绍Starburst的基于规则的优化器实现框架。

背景

很多业务的SQL语句或类SQL语句,尤其是中间件软件自动生成的SQL语句,主要面向业务模型,如果不做query rewrite,可能执行非常慢。

例如:

 

这条类SQL语句(某些OO中间件生成的)查询了所有在10/10/89之前被诊断为Malaria和Smallpox的男性病人。

如果按照SQL语句直观的查询计划,需要先遍历每一个男性病人,然后对每一个病人查阅其诊断记录。但实际上,男性病人中得Malaria和Smallpox的是少数,如果可以先查阅得此病的人,再过滤男性,执行效率更高。这就是Query Rewrite的价值。

 

 

Query Graph Model

Query在内部用Query Graph Model (QGM) 来表示,QGM表达能力很强,支持任意的表操作,它的输入和输出都是表。

例如如下的查询

 

对应的QGM图为

Box1和Box2是对应q1和q2,Box3对应主查询,Box4对应嵌套查询。

以Box3为例,head表示该box的输出表,并且有一个属性head.distinct。body表示生成输出表的过程,黑色圆点表示quantifier (quantified tuple variable),它的含义类似于参与计算的操作数的输入源,例如q1(F)表示类型为F(来自FROM)、关联到Box1输出的quantifier。q4(A)表示类型为ALL、关联到Box4的quantifier。q1和q2之间的方形代表join predicate。q1左侧圈代表在q1上的local predicate。body也有一个distinct属性,取值ENFORCE / PRESERVE / PERMIT,含义分别是 必须去重 / 保留含重复的数量 / 允许重复,该值和head.distinct直接关联。

 

 

Rewrite Rules

设计rewrite engine和rule的核心 Rewrite Philosophy : Whenever possible, a query should be converted to a single SELECT operator。其原因是单个SELECT操作简单,容易得出最优路径。

Starburst支持的rules

其中箭头表示一个rule应用完成后可能使得另一个rule满足条件。

因为Rewrite Philosophy,所以有很多最终的箭头指向SELMERGE。

 

Rule 1. SELECT Merge (SELMERGE)

 

例子:

 

Rewrite后的结果:

 

这样,查询优化器就可以从新的查询将view的内部查询考虑进去进行优化。

 

Rule 2. Distinct Pullup (DISTPU)

 

其中 one-tuple-condition 指的是只会吐出一条满足条件的结果,quantifier-nodup-condition 指的是可能吐出多条记录,但记录包含候选码(候选码唯一,例如输出列含主键),也就是说,这两个条件自动保证了输出无重复。这种情况下,box的head/body的distinct可以提前明确到代价低的情况(比如不需要再进行额外的去重)。

 

Rule 3. Distinct Pushdown From/To (DISTPDFR/DISTPDTO)

这条rule也比较简单,如果查询允许重复,那么例如子查询等quantifier也不必去重。

 

Rule 4. E or A Distinct Pushdown From (EorAPDFR)

意指quantifier如果是E或者A量词,则quantifier本身可以不去重。

 

Rule 5. Common Subexpression Replication (BOXCOPY)

公共子表达式复制。

 

Rule 6. Add keys (ADDKEYS)

 

如果原SELECT输出非distinct,则可以在quantifier多输出唯一性的列用到外层SELECT。

例子:

 

Rewrite后的结果:

 

Rule 7. E to F Quantifier Conversion (EtoF)

 

例子:

 

Rewrite后的结果:

 

Rule 8. INTERSECT to Exists (INT2EXIST)

将INTERSECT查询改写为EXISTS子查询,进而通过EtoF改写为SELMERGE。

 

Rule Engine

Starburst的Rule Engine的特点:

1. 支持任意复杂度的规则

规则定义为两个(C语言)函数,一个是condition函数,返回true/false表示是否满足该规则应用条件,一个是action函数,在满足条件时被调用,可以执行任意操作。

 

2. 上下文

规则引擎执行操作时,带有上下文参数,该参数包含指向用户查询信息的指针。

 

3. 规则分类和扩展的冲突解决

规则分类的好处:有利于对规则的理解;有利于规则condition/action函数的模块化和可理解性;不同的规则类的冲突解决方式不一样。

规则冲突及解决规则冲突是指当前存在规则可以应用。解决的两种模式:sequential(对所有规则按某个顺序一轮轮地尝试) 和 priority(总是应用满足条件的优先级最高的规则)。

 

4. 保证终止

 

5. 规则控制

支持在线enable/disable某些rule。

 

标签:

给我留言