BosCollege-SimpleDB-在查询中使用索引

关键词：索引，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());