EXPLAIN SQL_STMT可以打印生成的operator tree哈希索引：建立哈希表
B树索引：建立B/B+树
优化：对于经常查询的列可以把列的数据直接存储在索引中，省去读取文件的时间
缺点：高并发环境下需要加锁，可以用skip list代替
两种索引相比更建议使用B树索引，且B树索引得到的结果对于索引列是有序的
Because of the limited utility of hash indexes, a B-tree index should generally be preferred over a hash index. We do not have sufficient evidence that hash indexes are actually faster than B-trees even for = comparisons. Moreover, hash indexes require coarser locks.
位图索引：适合基数小的列来做索引
例：
sex: bitmap
male: 10001111
female: 01110000
查询时只需要和位图做与操作，选出结果为1的即可
局限：只适合列基数小的，且不适合高并发环境
用户输入SQL语句
通过编译器把语句编译(parsing)成抽象的语法树
负责将语法树和数据库的metadata结合，附上语义。自底向上对整颗语法树的节点依次检查，同时在节点绑定元数据，最终生成含有语义的语法树。
binding完成之后，SQL语句就算编译通过。
给定语法树，首先生成一个逻辑执行树，执行树上的每一个节点称为逻辑操作符。对应每个逻辑操作符，扩展出所有的物理操作符，逻辑操作符表示某个功能，物理操作符则说明用什么方法来实现这个功能， 可能有多个物理执行树。下一步在多个物理执行树中选出最优的一个，这步操作比较复杂。
从执行树底层开始依次执行。
执行器的执行模式：
需要排序的sql语句：Order By, Distinct
实现：
单项聚合：聚合之后的结果是一个单项值
只需要保存聚合中间值，根据新输入值不断更新即可，且内存消耗不大
组队聚合：结合group by的聚合
使用排序或者哈希表来实现
遇到内存不够大的问题，使用外部哈希表，借助文件系统暂存数据
Table A: M个block m个row
Table B: N个block n个row
Join基于equally join
Join算子实现
NestedLoopJoin
SortMergeJoin
类似Merge的过程，每个表维护一个指针，根据Join的键做排序
时间复杂度 M+N+2M*log2M + 2N *log2N
HashJoin
时间是线性的，在绝大多数情况下，性能是最佳的
优化运行时间
在这一步对原来的语法树进行等价的语义重写，优化掉无效或者无意义的操作
常见规则
优化器如何决定join的顺序来找到最优解？
n个表join的搜索空间是4n，首先要减小搜索空间。
在最早的Valcano Optimizer中，提出了对于Join Order，只考虑left-deep-tree
用于预测哪两个表join之后的cardinality比较小，来决定join ordering。帮助决定logical operator
Selection cardinality:
SC(P,R)表示当predicate是P的时候，对于表R，最后大约会有多少条row输出
需要知道表的一些基本的元信息: 如总行数，表中的每个column有多少个distinct value
数据库会不定期的自动更新每个表以及每个column的统计信息
Join cardinality:
SEL * FROM R1, R2 WHERE R1.a = R2.a;
公式： JC(R1, R2, R1.a = R2.a) = N_R * N_S / max(V(a, R), V(a, S))
V(a,R)表示R中的column a，一共有多少个distinct value
同时还需要知道数据的分布情况，常见的统计数据分布的方法是使用Histogram
不同的算子有不同的实现方法，使用Cost Model决定
每一个operator，有一个cost formula
同一个算子的不同实现方法，可以根据实际语句计算cost formula的值，选择cost比较小的
对于整个logical operator tree, 每个logical operator的选择不是局部最优的问题，使用DP解决
这部分笔者比较熟悉，不再详细记录
数据库内核杂谈(十三)：如何把一个单机数据库扩展成分布式数据库-InfoQ
使用一个leader节点，多个worker节点的架构，leader节点处理客户端的请求，并且对语句进行编译、绑定和优化。仅leader节点需要有优化器的实例，所有节点都会有执行器的实例。
和普通算子相比，分布式算子是节点之间的相互通信，需要RPC调用，调用的成本相对更高。