成本：对比所有可执行方案，找出成本最低方案（执行计划）
过程：根据条件找出所有可能的索引——>计算全表扫描代价——>计算用各索引的代价——>对比出最优
举例：select * from table where key1 in(a,b,c) and key2 > 10 and key3 > key2 and k_part1 like ‘%hello’；
查询成本 = I/O成本（页数 * 调页成本） + CPU成本（记录数 * 读取/比较成本）
Show table_status like ‘table’，从统计信息表中读取记录数rows和占用字节数data_length，全表扫描成本 = data_length/16k * 1.0 + rows * 0.2 + 微调值 ——data_length这里计算的是所有页面，实际上是搜B+树，大部分非叶节点不需访问
对于非主键索引，MySQL认为每个扫描区间相当于一次调页，而每次回表都相当于一次调页（有点粗糙了）
计算需要回表的记录数：每个页面的page header中有个page_n_recs代表本页的记录数，则对于每个扫描区间，找到最左记录，向右依次读每个页面的page_n_recs并求和，10个页面以内直接加，多于10个页面则用10个页面的平均值 * 页数（页数可由上一级目录项的间隔求出，若上一级也跨页了，就继续向再上一级递归）
——以上求出从二级索引中得到的记录数
二级索引成本 = 扫描区间数 * 1.0 + recs * 1.0 (I/O：扫描，回表)
+ recs * 0.2 + recs * 0.2 （CPU：读二级索引记录，读聚簇索引记录） + 微调值
相比于range访问方法，ref方法得到的id值离得更近，回表调页的消耗一般更低
对于单点扫描区间很多的时候（where k1 in（x1,x2…x2000）），每个区间都去计算recs会消耗很大，so，MySQL规定eq_range_index_dive_limit，默认200，超过此值则不再计算每个区间而是使用统计数据：show index from table 得到每个index的cardinality（不重复数），然后rows / cardinality 可得到平均每个单点区间的记录数（重复数）—— 很不精确
连接成本：单查驱动表成本 + 多次查被驱动表成本（扇出值 * 被驱的成本）——根据情况可精确得到 or 只能通过算法估计
对于内连接，需比较不同连接顺序的成本（是A驱动B or B驱动A），此时对于n表连接，有n!种顺序，搞不过来，so规定：1.维护全局最小成本，提前终止一些成本（超过当前最小就没必要继续了）；2.设置optimizer_search_depth变量，最多只穷举这么多的表；3.其他
成本常数用户可以修改
统计数据：（存在磁盘，或存在内存，可针对单个表，可配置）
Innodb_table_stats:
Database_name
Table_name
Last_update
N_rows：记录数
Clustered_index_size：聚簇索引所占页数
Sum_of_other_index_sizes：其他索引所占页数
N_rows估计值：选几个叶节点页面计算平均记录数，再 * 页面数，变量innode_stats_persistent_sample_pages规定了采样页面数
页面数估计值：在sys_indexs系统表中找到索引对应的B+树根页面，B+树根页面的page header中有叶节点段和非叶节点段两个segment header，可定位到这俩INODE Entry，INODE Entry中有本段所使用的碎片页号数组和三个完整区链表基节点，则可求出总页数
——这里用的是基节点中的list length * 64页（每个区64页），但里面其实是有空闲页的
Innode_index_stats统计项包括：
N_leaf_pages：叶节点占用页数
Size：共占页数，包括已分配未使用
N_diff_pfx01，02…：不重复值个数，主键or唯一二级索引只需要01，普通二级索引还会统计和主键组合后的情况，所以有01，02；对于联合索引如k1_k2，则统计k1，k1_k2以及k1_k2_id的情况则有01，02，03，更多列联合以此类推
Sample_size：为计算不重复值而采样的页面数——so，不重复值也不精确？
统计可配置自动or手动更新
Innode_stats_method决定统计不重复值时如何对待null