Access Path Selection

主要是System R的那篇文章的一个笔记。

数据库的基本流程

1. 解析SQL，生成语法树
2. 根据关系代数重写，包括谓词下推等。(逻辑计划)
3. 生成物理计划
4. 执行物理计划

这一篇主要讲的就是利用Cost模型来最优化物理计划。

一些基本概念

• predicate，中文叫谓词，但其实就是 一个 逻辑语句？比如 t.a < 1 这种
• Cost_total = Cost_io + W * Cost_cpu ：这是一个整体的公式，主要的Cost还是在IO方面。后文基本就是在具体的讨论如何计算 Cost_io的大小。通常CPU的cost比起IO小的太多了，所以加了一个权重W。
• Selective Factor： 这个东西就是给定了谓词，之后的概率估算。其实可以写成这个样子 F(Pred)是一个给定了Pred就确定了的值。F(a=1)就是a == 1在当前这个表里的概率。
• Statistics：顾名思义就是统计量呗。比如某个键的最大最小值，以及表里的Tuple数。（跑题一下：之前看ClickHouse的语法里有一个Sample，我是一直没理解数据库要采样做啥。知道看到这里，我才明白优化器在做优化时直接使用采样的结果，避免全局扫描，减少计算量。）

单表Cost

Cost_IO = Sel(Pred) * Statistics

多表Cost

Join

N 路Join就可以转为多次2路join