Cascades

使用规则或函数操作运算符参数

物化视图的特定于 Scheme 的规则

插入 Enforcer 或 Glue 的规则

特定于规则的指导，允许对规则进行分组

并行搜索，局部有序成本度量，动态规划的基础设施

广泛的追踪支持

新特性

DBI 实现可扩展性

特定于模式甚至查询的规则

匹配整个子树的模式（谓词）

启发式或彻底搜索

Ordering of moves by promise

特定于规则的指导

设计

面向对象的任务比过程调用提供更大的灵活性，特别是在搜索算法和搜索控制方面

任务对象可以很容易地在任何时候进行重新排序，从而实现了非常灵活的启发式指导机制。

面向对象的任务

我们计划用一个图来表示任务之间的结构，它捕获任务之间的依赖关系或拓扑顺序，并允许高效的并行搜索（使用共享内存）

数据结构

规则模式的所有绑定都被导出并逐个迭代

对于函数规则，每个绑定可能都有多个新的表达式

对于每个绑定，该规则都用于创建一个新的表达式

新的表达式被整合在 Memo 中

每个不是早期表达式重复的表达式都将使用触发当前规则应用程序的相同目标和上下文进行优化或探索

transformation 流程

Promise：前文中可见，发现一个搜索“分支”对应一个 Rule 的转换。每个 Rule 对外提供一个 Promise值（正整数），越高表示该分支更有可能找到最有计划，而搜索任务调度器会优先选择。

搜索优先级

当参与 Join 的表数量少于上限时（配置参数），遍历所有排列组合。否则，基于启发式规则选择一些Join Order，例如随机生成。此外，允许用户 Explicit 强制设定优化器采用的 Join Order。

如果表更小，对 Join 条件有索引，需扫描的行更少；那么这个表更可能被排列到 Join Order 靠前。

依靠雪花表的图关系（不需代价信息），区分 Satellite 节点（通常为 Fact 表，自带 Filter 条件），和Seed 节点（通常为 Dimension 表）。调整 Join Order 以形成 Bushy Join，方便谓词下推。

针对 OLAP 雪花表（Snowflake Schema），设计了特殊的启发式规则优化 Join Order

Join Order 并没有完美的解决方案，常见方法

Join Order Enumeration

低于预设代价的物理计划被找到

超时

搜索空间穷举完毕

搜索退出条件

例如，子树采用 Hash Join 也许更快，但结果无序，父需额外排序；Sort-merge Join 更慢，但结果有序；两者并无确定优劣。

是否排序

是否已计算 Hash

Physical Property：Operator 返回的结果带有的属性

表达这种差异

稳妥的做法是子树对每种不同的 Physical Property 都返回一个最优计划，供父节点选择。父节点也可指定自己关注的 Physical Property，然后让子树依此开始搜索。相比标准算法只保留一个局部最优结果，查询优化器将所有可能达成全局最优的局部最优列为候选，依次保留和探索。

解决问题

动态规划的基本假设是子树最优导出父最优（最优子结构），但对于查询优化这是不正确的。

局部最优问题

算法设计

Cascades