代价模型

总代价 = IO 代价 + CPU 代价
COST = P * a_page_cpu_time + W * T

P：计划运行时访问的页数，a_page_cpu_time 是每个页读取的时间花费，其积反映了IO代价
T：访问的元组。反映了CPU花费。（存储层是以页面为单位，数据以页面的形式读入内存，每个页面上可能有多个元组，访问元组需要解析元组结构，才能把元组上的字段读出，这消耗的是CPU）。如果是索引扫描，则还会包括索引读取的花费。
W：权重因子。表明IO到CPU的相关性，又称选择率（selectivity）。选择率用于表示在关系R中，满足条件“A<op>a”的元组数与R的所有元组N的比值。

单表扫描算法

全表扫描，局部扫描。单表扫描与IO操作密切相关。

1）顺序扫描（SeqScan）。当无索引可用，或访问表中的大部分数据，或表的数据量很小时，使用顺序扫描效果较好。

2）索引扫描（IndexScan）。根据索引键读索引，找出物理元组的位置。【如果选择率很高，不适宜使用索引扫描】

3）只读索引扫描（IndexOnlyScan）。根据索引键读索引，索引中的数据能够满足条件判断，不需要读取数据页面。比索引扫描少了读取数据的IO花费。

4）行扫描（RowIdScan）。用于直接定位表中的某一行。对于元组，通常为元组增加特殊的列，通过特殊的列计算出元组r物理位置，然后直接读取元组对应的页面，获取元组。在PostgreSQL中称为【Tid】扫描，此种方式是在元组头上增加名为【CTID】的列，用这列的值可直接计算本条元组的物理存储位置。

5）并行表扫描（ParallelTableScan）。对同一个表，并行地、通过顺序的方式获取表的数据，结果是得到一个完整的表数据。

6）并行索引扫描（ParallelIndexScan）。对同一个表，并行地、通过索引的方式获取表的数据，将结果合并在一起。

7）组合多个索引扫描（MultipleIndexScan）。

顺序扫描代价估算公式

COST = N_page * a_tuple_IO_time + N_tuple * a_tuple_CPU_time

索引扫描代价估算公式

COST = C_index + N_page_index * a_tuple_IO_time
C_index：索引的IO花费。C_index = N_page_index * a_page_IO_time
N_page_index：索引作用下的可用元组数。N_page_index = N_tuple * 索引选择率

索引

本质上是通过索引直接定位表的物理元组，加快数据获取的方式，所以索引优化的手段是物理查询优化。

如何利用索引

1）索引列作为条件出现在 WHERE，HAVING， ON 子句中。

2）索引列是被连接的表（内表）对象的列且存在于连接条件中

除了上述两种情况，还有一些特殊情况可以使用索引，如：排序操作、在索引列上求MIN、MAX值等。

（1）对表做查询，没有列对应作为过滤条件（如出现在WHERE子句中），只能做顺序扫描。

（2）对表做查询，有列对象且索引列作为过滤条件，可做索引扫描。

（3）对表做查询，有列对象作为过滤条件，但索引列被运算符“-”处理，查询优化器不能在执行前进行取反运算，这时不可利用索引扫描，只能做顺序扫描。

（4）对表做查询，有列对象作为过滤条件，且目标列没有超出索引列，可做只读索引扫描，这种扫描方式比单纯的索引扫描的效率更高。

（5）对表做查询，有索引存在，但选择条件不包括索引列对象，只能使用顺序扫描。

（6）对表做查询，有索引存在，选择条件包括索引列对象，可使用索引扫描，对选择条件中不存在索引的列作为过滤器被使用。

（7）对表做查询，有索引存在，选择条件包括索引列对象，但索引列对象位于一个表达式中，参与了运算，不是“key=常量”格式，则索引不可使用，只能是顺序扫描。如：
select a. from a where a.a1 + a.a3 = 2；（a1列是索引），这时只能做顺序扫描。
或
select a. from a where a.a1 = 2 - a.a3 ；（a1列是索引），这时只能做顺序扫描。

（8）对表做查询，有索引列对象作为过滤条件，操作符是范围操作符 > 或 < ，可做索引扫描。

（9）对表做查询，有索引列对象作为过滤条件，操作符是范围操作符 <> ，不可做索引扫描。

（10）对表做查询，有索引列对象作为过滤条件，操作符是范围操作符BETWEEN-AND ，可做索引扫描。

索引列的位置对使用索引的影响

（1）索引列出现在目标列，通常不可使用索引（但不是全部情况下不能使用索引）

（2）聚集函数MIN / MAX用在索引列上，出现在目标列，可使用索引。

（3）索引列出现在WHERE子句中，可使用索引。

（4）索引列出现在 JOIN / ON 子句中，作为连接条件，有时不可使用索引。（这取决于代价估算模型）

（5）索引列出现在 JOIN / ON 子句中，作为限制条件满足“key <op> 常量 ”格式可用索引。

（6）（5）索引列出现在 WHERE子句中，但与子查询比较，格式上不满足"key <op> 常量"，不可用索引。

索引列对GROUP BY子句的影响

（1）索引列出现在 group by 子句中，不触发索引扫描。

（2）WHERE子句出现索引列，【且】GROUP BY 子句出现索引列，索引扫描被使用。

（3）WHERE子句中出现非索引列，且GROUP BY子句出现索引列，索引扫描不被使用。

索引列对HAVING子句的影响

（1）WHERE子句出现非索引列，且GROUP BY和HAVING子句出现索引列，索引扫描被使用。

索引列对ORDER BY子句的影响

（1）ORDER BY子句出现索引列，可使用索引。

（2）ORDER BY子句使用非索引列，不可使用索引扫描。

索引列对 DISTINCT 的影响

（1）DISTINCT 子句管辖范围内出现索引列，不可使用索引。

联合索引对索引使用的影响

（1）使用联合索引的全部索引键，可触发索引的使用。

（2）使用联合索引的前缀部分索引键。如：key_part_1 <op> 常量。可触发索引的使用。

（3）使用部分索引，但不是联合索引的前缀部分，如“key_part_2 <op> 常量"，不可触发索引的使用。

（4）使用索引索引的全部索引键，但索引键不是AND操作，不可触发索引的使用。

多个索引对索引使用的影响

（1）WHERE子句出现两个可利用的索引，优选最简单的索引。（但这也是要根据代价估算模型来决定的）

（2）WHERE子句出现两个可利用的索引且索引键有重叠部分，优选最简单的索引。

聚簇索引

是指表的一个或多个列作为索引的关键字，以关键字的具体值为依据，把所有具有相同值的元组连续放在外存上。当从磁盘扫描读取的块进入内存时，相同值的其他元组在内存中的概率增大，能有效减少IO。即：聚簇索引确定表中数据的物理顺序。聚簇索引对于那些经常要搜索范围值的列特别有效。使用聚簇索引找到包含第一个值的行后，便可以确保包含后续索引值的行在物理相邻。