美文网首页
BosCollege-SimpleDB-在查询中使用索引

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

作者: ArthurN | 来源:发表于2018-10-16 22:57 被阅读0次

    关键词:索引,SimpleDB,查询计划
    Keyword: Index, SimpleDB, Query Plan

    Author: Sixing Yan

    在哪儿使用索引?

    在SimpleDB-2中,执行一个SQL查询,将会为其创建一个查询计划(QueryPlan),其中囊括了对一个基本SQL语句中的ProjectProductSelection三个部分(见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());
    
    

    相关文章

      网友评论

          本文标题:BosCollege-SimpleDB-在查询中使用索引

          本文链接:https://www.haomeiwen.com/subject/ugbkzftx.html