关键词：索引，SimpleDB，查询计划
Keyword: Index, SimpleDB, Query Plan
Author: Sixing Yan
在哪儿使用索引？
在SimpleDB-2中，执行一个SQL查询，将会为其创建一个查询计划（QueryPlan），其中囊括了对一个基本SQL语句中的Project，Product，Selection三个部分（见BasicQueryPlan.java）。可见，SimpleDB-2并不会主动使用索引完成查询任务。所以，如果希望SimpleDB在查询中使用索引，则需要修改BasicQueryPlan中的creatQueryPlan方法，在其中加入IndexPlan相关内容。
什么时候使用索引？
SimpleDB-2中实现（但未部署）了一个可以使用Index的SelectionPlan，显然其中一处可以使用索引的地方就是Selection部分（Product部分也可以使用）。
如何使用索引？
简单来说，就是替换SelectPlan成IndexSelectPlan。
For example, we use SimpleDB to execute SQL with indexing. Supposed there is a table course with an id attribute, the SQL is,
select cid from course where cid=10;
SimpleDB-2
在SimpleDB-2 中，我们需要修改地方是这里的"Step 3":
public class BasicQueryPlanner implements QueryPlanner {
/**
* Creates a query plan as follows. It first takes
* the product of all tables and views; it then selects on the predicate;
* and finally it projects on the field list.
*/
public Plan createPlan(QueryData data, Transaction tx) {
//Step 1: Create a plan for each mentioned table or view
List<Plan> plans = new ArrayList<Plan>();
for (String tblname : data.tables()) {
String viewdef = SimpleDB.mdMgr().getViewDef(tblname, tx);
if (viewdef != null) plans.add(SimpleDB.planner().createQueryPlan(viewdef, tx));
else plans.add(new TablePlan(tblname, tx));
}
//Step 2: Create the product of all table plans
Plan p = plans.remove(0);
for (Plan nextplan : plans) p = new ProductPlan(p, nextplan);
//Step 3: Add a selection plan for the predicate
p = new SelectPlan(p, data.pred());
//Step 4: Project on the field names
p = new ProjectPlan(p, data.fields());
return p;
}
}
SimpleDB-3
使用索引时，一个需要考虑的问题是，where 中涉及的field是否有index，以及查询条件是否适合调用该index。例如，如果进行一个等值查询，那么使用基于Hash的索引可能比基于Tree的索引表现更改。
这里，首先检查查询任务中，涉及的field在其对应的表上是否存在索引；其次检查该查询是否是“等值查询”，如果是，则使用该索引。（这里贪婪地使用第一个满足条件的索引）
public class IndexQueryPlanner implements QueryPlanner {
public Plan createPlan(QueryData data, Transaction tx) {
//Step 1: Create a plan for each mentioned table
//Step 2: Create the product of all table plans
//----above is the same to 2.0.1----
//Step 3: Add a selection plan for the predicate
Map<String, IndexInfo> indexInfoMap = SimpleDB.mdMgr().getIndexInfo(tblname, tx);
Constant cst;
IndexInfo ii;
for (String fldname: indexInfoMap.keySet()){
//check whether there exist condition like 'F=c',
//where 'F' is a fieldname, and 'c' is constant.
cst = data.pred().equatesWithConstant(fldname);
if (cst != null){
//If yes, then check whether there exist indexing on 'F'
ii = indexInfoMap.get(fldname);
//If yes, stop loop
if (ii != null) break;
}
}
//use indexing or non-indexing to operate Selection
if (ii != null) p = new IndexSelectPlan(p, ii, cst, tx);
else p = new SelectPlan(p, data.pred());
//----below is the same to v2.0.1----
//Step 4: Project on the field names
}
}
简单来说，SimpleDB v3.0.0 改变了 exectueQuery的执行方式，把其中的SelectPlan[v2.1.0] 替换成 IndexSelectPlan[v2.1.0]
SelectPlan的next()遍历每一条tuple，用Predicate.isSatisfied(tuple)判断其是否满足where 里的限制
IndexSelectPlan使用上文中找到的 cst:Constant 变量，使用 beforesearch(cst)方法找到 遍历 的起始位置，然后读取这个索引上的所有tuple（直到next()为false）。这个索引的搜索避免了全表扫描的操作。
SimpleDB-3.1
上一节中简单地展示了如何在createQueryPlan中加入使用索引的操作。在面对使用场景中，我们可能不会简单地只执行针对等值查询的索引（还有等域查询）；同时，我们还要考虑不同的操作符对应不同的索引，其将对应“等”查询或者范围查询。
在IndexQueryPlan中，将"step3"更改成：
//Step 3: Add a selection plan for the predicate
IndexFinder ifder = new IndexFinder(data, tx);
p = ifder.hasIndexInfo() ? new IndexSelectPlan(p, ifder.getIndexInfo(), ifder.getSearchKey(), tx) : new SelectPlan(p, data.pred());
