Query Optimization
Query Optimization是一个NP-Hard问题。
有两种基本方法，一种是利用一些人为规定的规则将一些无用的条件、查询给扔掉。这些技巧可能需要检查数据库的system catalog，但是不需要真的去获取数据。
另一种方法是利用成本模型计算一些查询计划的成本，选成本最低的查询方案。
查询优化器结构
1.SQL Rewriter将SQL语句重写。
2.Parser将SQL语句中的不同成分解析出来，类似编译器中的Parser。
3.Binder将Parser解析出来的各个标识符用System Catalog中的信息标注为Internal ID。
4.生成Logical Plan，即用关系代数组成的查询树，可以在这一层进行Tree Rewrite，比如将某个逻辑层下放、合并之类的。
5.将生成的Logical Plan传入Optimizer中，用Cost Model来估计“所有”Logical Plan的成本，选一个最优的生成Physical Plan来执行。
Relational Algebra Equivalences
Selections
1.尽量把filter往下放。
2.将最具有筛选性的filter往下放的更多。
3.将复杂的predicate拆分成若干条件，然后下放。例如X = Y AND Y = 3 –> X = 3 AND Y = 3。
Projections
1.也是尽量把projection操作下放，这样就能把更少的数据往上传。
2.可以把额外的数据也上传，并不是只传要求的数据，比如join key。
一些其他优化
1.消除无用predicates：例如WHERE中的1 = 0和1 = 1。
2.忽略无用的projection、merge等等。
3.将Where中的多个条件合并。
Cost-based Query Optimization
一般来说，我们用Cost-based模型计算一个plan的以下几个方面：
1.CPU：最难估计的部分。
2.Disk：在内存和磁盘之间传递了多少block。
3.Memory：用了多少DRAM内存。
4.Network：有多少信息被传递了。
统计信息
可以在数据库中维护直方图来存统计信息，也可以采用取样的方法。因为数据库的信息可能经常会变，所以我们可能需要经常更新统计信息。大部分数据库有ANALYSIS命令来执行分析操作。
我们可以维护每个断言的sel值，即我如果执行这个命令，那么将会有多大比例的tuples被过滤掉。这样可以帮助我们将SQL语句rewrite。如果直接用公式来计算sel值，那么必须先有数据库中数据是均匀分布这样一个假设，在大多数情况下是不成立的，因此我们可以把数据库中的若干个连续数据放到一个桶中，认为桶里的数据是均匀分布的，如果要计算一个操作的sel值就到对应桶中用公式计算。这里的桶可以动态维护，尽量使得每个桶的大小差不多。
Multi-Relation Query Planning
基本顺序是：1.先枚举join的顺序。2.决定对每个operator用什么方法，例如Hash、Sort-Merge等等。3.决定每个方法用什么方式去访问数据，例如Index、循序扫描等等。
OLTP事务类型是非常好解决这个问题的，因为对每个操作我们一般选最佳index，并且基本上都是用外键来进行join。
Join
PostgreSQL的策略是：如果要join的表格数量少于15个，就用Dynamic programming，否则用启发式算法。
Dynamic Programming
这种方法就是每一步选择一个表来join。每次往已有的join表中加一个表上去，选择最合适的方法计算代价，对于每个特定状态都选择一条最优路径。也叫动态规划。
System R
System R这个数据库只会选Left-most tree来作为join的顺序。因为系统中可以只用维护一个join而成的表，并且能够实现fully pipelined。
启发式算法
如果要join的表太多，可能的顺序为卡特兰数，大约为4^n。因此用启发式算法。先随机一批顺序组成一棵join树，在每一步选出最优的、删掉最垃圾的，保留最优的部分结构继续随机，被删除的就重新随机一棵树，这样做直到超时。
Sub-Query
无非就是两种办法，要么把查询重排，将内外查询都放到一起，要么先执行内部查询，把结果放到一个临时的表中，然后执行外部查询。