關(guān)鍵詞：索引惶我，SimpleDB，查詢計劃
Keyword: Index, SimpleDB, Query Plan
Author: Sixing Yan
在哪兒使用索引冠骄？
在SimpleDB-2中伪煤，執(zhí)行一個SQL查詢，將會為其創(chuàng)建一個查詢計劃（QueryPlan）凛辣，其中囊括了對一個基本SQL語句中的Project抱既，Product，Selection三個部分（見BasicQueryPlan.java）扁誓》辣茫可見阳堕，SimpleDB-2并不會主動使用索引完成查詢?nèi)蝿?wù)。所以择克，如果希望SimpleDB在查詢中使用索引恬总，則需要修改BasicQueryPlan中的creatQueryPlan方法，在其中加入IndexPlan相關(guān)內(nèi)容肚邢。
什么時候使用索引壹堰？
SimpleDB-2中實現(xiàn)（但未部署）了一個可以使用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辖试，以及查詢條件是否適合調(diào)用該index。例如劈狐，如果進(jìn)行一個等值查詢罐孝，那么使用基于Hash的索引可能比基于Tree的索引表現(xiàn)更改。
這里肥缔，首先檢查查詢?nèi)蝿?wù)中莲兢，涉及的field在其對應(yīng)的表上是否存在索引；其次檢查該查詢是否是“等值查詢”续膳，如果是改艇，則使用該索引。（這里貪婪地使用第一個滿足條件的索引）
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的執(zhí)行方式谒兄，把其中的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
上一節(jié)中簡單地展示了如何在createQueryPlan中加入使用索引的操作纪隙。在面對使用場景中，我們可能不會簡單地只執(zhí)行針對等值查詢的索引（還有等域查詢）扛或；同時绵咱，我們還要考慮不同的操作符對應(yīng)不同的索引，其將對應(yīng)“等”查詢或者范圍查詢熙兔。
在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());
