h2database源码解析-查询优化器原理

一、成本计算规则

h2的查询优化器基于成本的，因此在执行查询前，会基于成本计算使用哪个索引，如果涉及多表关联，还会计算不同表关联顺序的成本，最终基于最小成本得出执行计划。
单表查询时，遍历表的各个索引，索引遍历的顺序是先主键索引，然后二级索引。h2先假设使用该索引，然后基于该索引计算成本，索引不同，成本的计算规则也不同。
单主键索引的成本计算规则是最简单的，规则为：10*(总记录数+1000) 。但是如果是二级索引或者是主键有多个字段，那计算规则就比较复杂了。在Index.getCostRangeIndex()里面具体描述了成本计算规则，只要是基于索引计算成本（元数据表除外），那么都会调用下面这个方法，该方法的返回值乘以10，就是基于该索引进行查询所需成本：

	//masks：数组中的元素与表的字段一一对应，比如数组第一个元素对应表的第一个字段，依以此类推，数组中的元素值表示该字段在查询语句中的比较类型，比如等值比较，元素值为1，比如大于等于，元素值为2，如果该字段在多个查询条件里面出现，比如既有大于等于也有等于操作，那么元素值为3（计算方式是1|2）//rowCount：表示表里面行记录总数//filters：每个TableFilter代表一个表//filter：如果多表关联查询，该参数表示正在处理filters[filter]//sortOrder：是否有order by子句//allColumnsSet：记录了本次查询涉及到的所有表的所有字段//isScanIndex：当前是否是表扫描，主键索引属于表扫描索引，二级索引不属于protected final long getCostRangeIndex(int[] masks, long rowCount, TableFilter[] filters, int filter,SortOrder sortOrder, boolean isScanIndex, AllColumnsForPlan allColumnsSet) {//成本是按行数+此偏移量计算的，以避免在表中不包含记录时使用错误索引rowCount += Constants.COST_ROW_OFFSET;int totalSelectivity = 0;long rowsCost = rowCount;if (masks != null) {int i = 0, len = columns.length;boolean tryAdditional = false;//从该索引的第一个字段开始遍历while (i < len) {Column column = columns[i++];//按顺序获取索引的每个字段int index = column.getColumnId();//获取字段在表里面的顺序int mask = masks[index];//获取该字段在查询语句里面的比较类型if ((mask & IndexCondition.EQUALITY) == IndexCondition.EQUALITY) {//使用到了索引中的一个字段，并且是等值操作if (i > 0 && i == uniqueColumnColumn) {//该索引是唯一索引，且遍历完索引的所有字段后发现查询语句中对该索引字段都是使用了等值操作//可见使用唯一索引的成本非常低rowsCost = 3;break;}//下面计算公式依赖于该字段的区分度(getSelectivity)，区分度可以根据表优化或者重建重新计算totalSelectivity = 100 - ((100 - totalSelectivity) *(100 - column.getSelectivity()) / 100);long distinctRows = rowCount * totalSelectivity / 100;if (distinctRows <= 0) {distinctRows = 1;}rowsCost = 2 + Math.max(rowCount / distinctRows, 1);} else if ((mask & IndexCondition.RANGE) == IndexCondition.RANGE) {//当前字段是范围比较操作，比如betweenrowsCost = 2 + rowsCost / 4;tryAdditional = true;//tryAdditional表示不是等值操作break;} else if ((mask & IndexCondition.START) == IndexCondition.START) {//大于等于操作rowsCost = 2 + rowsCost / 3;tryAdditional = true;break;} else if ((mask & IndexCondition.END) == IndexCondition.END) {//小于等于操作rowsCost = rowsCost / 3;tryAdditional = true;break;} else {if (mask == 0) {// Adjust counter of used columns (i)i--;}break;}}//在上面遍历索引字段的过程中，一旦发现非等值比较或者该字段不再查询语句里面，便结束字段遍历if (tryAdditional) {//如果为true，表示查询语句里面有非等值比较查询while (i < len && masks[columns[i].getColumnId()] != 0) {//如果索引中某个字段使用了非等值操作，那么后续的字段不能像等值操作一样通过该索引高效过滤数据，但是依然可以使用索引过滤数据，因此下面使用rowsCost--i++;rowsCost--;}}// 增加额外未使用列的索引成本// len表示当前索引中字段的个数rowsCost += len - i;}//如果ORDER BY子句与此索引的排序相一致，那么它的成本将响应降低long sortingCost = 0;if (sortOrder != null) {sortingCost = 100 + rowCount / 10;}//下面的if分支判断为true时表示当前SQL语句有order by子句，且不是使用主键索引查询if (sortOrder != null && !isScanIndex) {//sortOrderMatches表示order by子句的排序规则是否与索引匹配boolean sortOrderMatches = true;int coveringCount = 0;//sortTypes表示order by子句里面各个字段的排序规则，下文有详细介绍int[] sortTypes = sortOrder.getSortTypesWithNullOrdering();TableFilter tableFilter = filters == null ? null : filters[filter];//从order by子句的第一个字段开始遍历for (int i = 0, len = sortTypes.length; i < len; i++) {if (i >= indexColumns.length) {//这里表示当前排序的字段多于索引中的字段，在这种情况下，我们依然可以使用该索引，只是相对于包含更多排序字段的索引，coveringCount值小而已，进而影响其成本break;}//获得对应的数据库表字段Column col = sortOrder.getColumn(i, tableFilter);//如果col为null，表示该排序字段不是当前表的字段if (col == null) {sortOrderMatches = false;break;}IndexColumn indexCol = indexColumns[i];//当前正在遍历order by子句的第i个字段，将该字段与索引中的第i个字段比较，如果字段一致，那么意味着可以使用索引排序，否则不能使用if (!col.equals(indexCol.column)) {sortOrderMatches = false;break;}int sortType = sortTypes[i];//如果order by子句的第i个字段与索引的第i个字段相同，那么比较排序规则，如果也一致，那么可以使用索引排序，否则不能使用if (sortType != indexCol.sortType) {sortOrderMatches = false;break;}//如果排序字段与索引字段相同，而且排序规则也一致，增大coveringCount，coveringCount越大，成本越小coveringCount++;}if (sortOrderMatches) {//coveringCount确保当我们有两个或多个覆盖索引时，我们选择覆盖更多的索引sortingCost = 100 - coveringCount;}}//如果当前的SQL语句，使用主键查询和使用某个二级索引查询的成本相同，而且二级索引可以满足查询需要，那么使用索引查询即可//如果needsToReadFromScanIndex=true，表示查询除了使用二级索引外还需要回表查询boolean needsToReadFromScanIndex;if (!isScanIndex && allColumnsSet != null) {needsToReadFromScanIndex = false;//获取SQL语句中使用到该表的所有字段ArrayList<Column> foundCols = allColumnsSet.get(getTable());if (foundCols != null) {//获取main index column，在h2里面main index比较复杂，//不过可以简单理解为，如果当前主键索引只有一个字段，那么getMainIndexColumn()返回的就是该字段在表中的字段位置，//如果有多个字段或者没有索引，那么该方法返回的是一个常量SearchRow.ROWID_INDEXint main = table.getMainIndexColumn();//遍历SQL语句里面涉及到该表的所有字段，如果这些字段在当前索引中都有，那么表示可以使用该索引查询，不用回表loop: for (Column c : foundCols) {int id = c.getColumnId();//下面判断了id == SearchRow.ROWID_INDEX，因为二级索引里面默认有主键列if (id == SearchRow.ROWID_INDEX || id == main) {continue;}//columns表示当前索引中涉及到表字段for (Column c2 : columns) {if (c == c2) {continue loop;}}//SQL中有一个字段不在索引里面，那么除了使用二级索引查询外，还需要回表查询needsToReadFromScanIndex = true;break;}}} else {needsToReadFromScanIndex = true;}long rc;//下面是计算最终的成本if (isScanIndex) {//如果当前是使用主键查询rc = rowsCost + sortingCost + 20;} else if (needsToReadFromScanIndex) {//如果需要回表查询，那么还要计算上使用主键查询的成本rc = rowsCost + rowsCost + sortingCost + 20;} else {//下面的计算公式使用了索引列的个数，这是因为当我们选择覆盖索引时，//我们选择列数最少的覆盖索引（索引中的列数越多，成本越高）,因为较小的索引占用的数据空间更小。rc = rowsCost + sortingCost + columns.length;}return rc;}

order by子句里面可以指定字段的排序规则，是ASC还是DESC，对于可以为NULL的字段，还有两种排序规则，分别是无论升序还是降序NULL值始终在最前以及无论升序还是降序NULL值始终在最后的排序规则，在h2中使用常量ASCENDING（0）、DESCENDING（1）、NULLS_FIRST（2）、NULLS_LAST（4）表示上述四种排序规则，不过后面两种不能在SQL语句中指定，h2会基于系统默认值设定，默认情况下，升序是NULL值始终在前，降序是NULL值始终在最后。所以默认情况下，对于order by id ,name desc子句，上面代码里面数组变量sortTypes[0]=ASCENDING | NULLS_FIRST=2，sortTypes[1]=DESCENDING | NULLS_LAST=5。

在h2中，全表扫描、回表查询指的都是使用主键查询。h2的表都是使用主键维护的表。

getCostRangeIndex()方法是计算执行计划成本的最核心方法，它的返回值表示的就是当前表使用该索引查询的成本。通过本方法，对表查询时就可以判断出使用哪个索引查询成本最低。上面的方法代码量并不多，但是涉及的内容比较多，通过上面的方法可以看到什么样的索引是“好”索引。下面总结一下“好”索引的特点：

1. 索引能覆盖SQL语句中的所有字段，这种索引也叫作覆盖索引；
2. 索引遵循最左前缀原则，因此尽量不要由对索引中间字段或者开头字段进行范围查询，这会导致后面的字段无法使用索引；
3. 排序的字段及顺序对索引的使用也有影响；
4. 索引是唯一索引，而且查询语句对该索引都是等值查询，这种索引成本最低。

不过，h2的优化器还有有局限性的，比如计算成本时，没有考虑该表或者索引是否已经在缓存中了。
下面分几种场景介绍h2如何使用getCostRangeIndex()方法确定执行计划。

二、单表查询

单表查询是最简单的，首先使用主键索引计算成本，然后遍历各个二级索引计算成本，从这里面选择成本最小的索引，之后便使用该表进行查询。

三、多表关联查询

当关联表的个数小于等于7个时，h2会计算出这些表的所有排列，对每个排列从第一个表开始遍历，根据查询条件，通过getCostRangeIndex()方法确定每个表使用哪个索引的成本最低，并得到最低成本，然后使用如下伪代码计算出该排列的总成本：

	//item.cost是对每个表进行查询的最小成本,double cost = 1;//遍历每个表，tables表示一个排列//tables[i].cost表示表的最小成本for (int i = 0; i < tables.length; i++) {cost += cost * tables[i].cost;}

这样便可以从这些排列里面找到成本最低的排列。之后h2使用该排列中表的顺序依次操作每个表。
不过h2也有一个提前终止条件，可以提前终止对排列的遍历，代码如下：

    private boolean canStop(int x) {return (x & 127) == 0// don't calculate for simple queries (no rows or so)&& cost >= 0// 100 microseconds * cost&& System.nanoTime() - startNs > cost * 100_000L;}

入参x是一个计数器，表示已经遍历了多少个排列了，每遍历一个排列，x会增加1，x从0开始计数。当canStop()返回true时，那么后续的排列便不再遍历。这会导致最优的排列可能没有遍历到。

h2提供了Permutations类用于生成下一个排列，该算法是由Alan Tucker实现的。

如果关联表的个数大于7个，h2是无法遍历所有排列的。h2使用随机+贪心算法来搜索较好的排列。与暴力搜索不同，随机+贪心不一定能找到最好的排列顺序，但是至少可以找到次优的排列。