第17章——查询处理

译者注：这一章中有些名词不是很好翻译，例如scan，对于这些不好翻译的词，将直接采用英文。

在前面的两章中，我们已经看到了表中的记录是怎么用记录文件来实现的，也知道了表的元数据是怎么被组织起来的，从而方便以后的记录访问。接下来的三章，我们将会考虑一下数据库系统怎么支持对表的查询。

第4章中介绍了两种查询语言：关系代数(relational algebra)和SQL。关系代数相对来说比较容易实现，因为每个操作都是一个很小的、且定义好的小任务，然而SQL比较难直接去实现，因为一个SQL查询可以嵌入许多的任务和逻辑。事实上，我们在第4章中已经看到了，一个SQL查询语句可以被表达成一个关系代数查询树，这种对应关系提供了实现SQL的关键—数据库系统首先将SQL查询转换为关系代数，然后执行关系代数查询树。

在这章中，我们将研究一下关于如何执行关系代数的问题，而后续的两章将研究如何将SQL翻译成关系代数。

17.1 Scans

一个Scan就是代表一个关系代数查询的对象，Scan在SimpleDB中是通过接口Scan来实现的，接口Scan的方法和RecordFile类中的方法很相似，客户端可以遍历一个scan，移动到下一条记录，并且检索相应的字段的值。代码如下：

public interface Scan {
    // 移动到第一条记录之前
    public void beforeFirst();

    // 移动到下一条记录，如果没有下一条记录，返回false
    public boolean next();

    // 关闭scan，如果有subScan，也会相应关闭
    public void close();

    // 获取当前记录指定字段的值，被抽象成了一个Constant对象
    public Constant getVal(String fieldName);

    // 获取当前字段指定int字段的值
    public int getInt(String fieldName);

    // 获取当前字段指定string字段的值
    public String getString(String fieldName);

    // 判断是否有指定字段
    public boolean hasField(String fieldName);

}

下面的代码演示了如何使用一个scan，方法printNameAndGradYear()会遍历输入的scan，打印出每条记录的字段sname和gradyear取值。因为Scan是一个接口，这个方法其实并不知道这个scan是怎么构造的或者说这个scan代表的具体是哪种查询，凡是输出包含学生名字和毕业年份的查询，其实都是可以成功执行的。

public static void printNameAndGradyear(Scan s) {
    while (s.next()) {
      String sname = s.getString("sname");
      String gradyr = s.getInt("gradyear");
      System.out.println(sname + "\t" + gradyr);
    }
    s.close();
}

Scan接口和RecordFile类主要在下面的3个方面有所不同：

• RecordFile类中包含读/写的方法，而Scan中的方法只支持读，只有Update Scan才有写方法，我们将在17.2小节中讨论。

• RecordFile类需要知道表的schema信息(RecordFile类的构造函数需要提供一个TableInfo对象)，但是在Scan中不需要。相反，在Scan中有一个hasField()方法来判断指定的字段是否被包含在scan的输出中。

• Scan中除了getInt()和getString()之外还包含一个getVal()方法，其返回的是一个Constant类型的对象(详情见17.7小节)，这个类型是对int和string的抽象，这个方法的目的就是允许查询处理器在无需知道具体类型，就可以对字段的值进行比较。

每个Scan对象对应一个查询树中的一个节点，对于每一种关系代数中的操作，都对应有一个具体的Scan接口实现类，而对于查询树中的叶子节点，必定是对一个表的scan，下面的代码中展示了SimpleDB中支持的4种不同的Scan以及它们的构造函数：

public SelectScan(Scan s, Predicate pred);
public ProjectScan(Scan s, Collection<String> fldlist);
public ProductScan(Scan s1, Scan s2);
public TableScan(TableInfo ti, Transaction tx);

考虑一下SelectScan类的构造函数，它接受两个输入，一个Scan对象和一个谓词对象（译者注：这里所的谓词，指的是离散数学中的谓词的概念，如果你有学过，可能会觉得很耳熟）。Scan对象表示的是输入给select运算的表。回想一下，关系运算的输入可以是任何表或中间查询的结果，这刚好用一个类型为Scan的对象来表示。 由于Scan是一个接口，因此，无论具体是一个实际存储的表还是其他查询的结果，SelectScan对象可以对输入的表做同样的操作。

第二个谓词对象是一个Predicate类型的对象，我们将在17.7小节中讨论SimpleDB是怎么实现select运算中的select谓词的，在那之前，我们对谓词的讨论都会比较含糊，不过你可以暂时理解成一个高层次的抽象的概念，即对scan的结果进行比较筛选。

一个查询树可以用许多Scan对象来表示，树上的每个节点代表一个Scan对象。

图17-4和图17-5给出了两个示例，演示了查询树是怎么用scan对象组织起来的。

图17-4（a）展示了一个查询树的情况，该查询的功能是返回所有专业id为10的学生姓名，图17-4（b）则给出了构造这个查询树的具体代码（暂时忽略select谓词的具体实现）。其中Scan类型的变量s1、s2和s3分别对应查询树中的一个节点，并且这个树是自底向上构建的（也就是说，s1对应的是STUDENT结点，s2对应的是Select结点，s3对应的是Project结点），s3是整个查询树的入口，遍历s3，则可以打印出每个专业id为10的学生姓名。

图17-5（a）则展示了另一个查询树的情况，该查询的功能是返回所有的学生信息以及对应的学院。图17-5（b）给出了构造这个查询树的具体代码，和图17-4中的例子很相似。在这个例子中，代码中包含4个scan，因为这个查询树有4个节点，变量s4是整个查询树的入口，然后也和之前一样遍历打印结果。在这里为了节约篇幅，只打印了3个字段，如果你想的话，肯定也是可以打印出两张表join之后的所有字段信息的。

17.2 Update scan

一个query定义了一张虚拟表，而Scan接口给客户端提供了读取这些虚拟表的相关方法，但是无法修改虚拟表。在4.5.3小节中，我们已经讨论了更新一个虚拟表的问题，并且得出了这样的结论：只有对于那些可更新的查询(updatable query)所创建的虚拟表，更新虚拟表才是有意义的。这个结论在这里同样也成立。

当一个scan中的每条记录$r$都在某个数据库表中存在一条对应的$r'$记录时，我们称这个scan是可更新的。可更新的scan是通过接口UpdateScan来实现的，代码如下所示：

public interface UpdateScan extends Scan {
    public void setVal(String fieldName,Constant newVal);
    public void setInt(String fieldName,int newVal);
    public void setString(String fieldName,String newVal);
    public void insert();
    public void delete();

    public RID getRID();
    public void moveToRId(RID rid);
}

前5个方法对应的是一些修改操作，而最后两个方法运行客户端获取到当前记录的rid或者将当前记录移动到指定rid对应的记录。（注意，rid对于非可更新的scan是没什么意义的，因为一个非可更新的scan中的一条记录可能对应的是底层多张表中的多个记录）

SimpleDB中实现了UpdateScan接口的两个类是TableScan和SelectScan，至于如何使用它们，请看下面图17-7中的例子，图17-7（a）中给出了一个SQL语句，该SQL语句的功能是把id为53的那堂课中的所有学生成绩全部改成C，图17-7（b）中给出了实现这个SQL的代码，代码首先创建了一个tableScan对象，随后创建了一个SelectScan对象，最后遍历该SelectScan对象，遍历的过程中会修改每个学生的成绩为C。

注意，变量s2必须被声明成一个update scan，因为遍历的时候回调用setString()方法。此外，SelectScan构造函数的第一个参数是Scan类型的，也就是说，s1不需要被声明为一个update scan；相反，因为有s2.setString()方法的存在，因此会将s1强转为一个update scan，如果这个s1实际上不是一个实现了UpdateScan的对象，那么会抛出一个ClassCastException异常。

17.3 实现Scan接口

SimpleDB中包含4个实现了Scan接口的类，分别是：TableScan、SelectScan、ProjectScan、和ProductScan。下面我们将以此来讨论一下关于这些类的实现细节。

17.3.1 Table Scan

TableScan类的代码如下所示，TableScan是可更新的scan，因此实现的是UpdateScan接口(UpdateScan接口继承了Scan接口)。

public class TableScan implements UpdateScan {
    private RecordFile recordFile;
    private Schema schema;

    public TableScan(TableInfo tableInfo, Transaction tx) throws IOException {
        recordFile = new RecordFile(tableInfo, tx);
        schema = tableInfo.schema();
    }
    //================Scan 接口中的方法实现===================
    @Override
    public void beforeFirst() {
        recordFile.beforeFirst();
    }

    @Override
    public boolean next() throws IOException {
       return recordFile.next();
    }

    @Override
    public void close() {
        recordFile.close();
    }

    @Override
    public Constant getVal(String fieldName) {
        if (schema.type(fieldName)==Schema.VARCHAR)
            return new StringConstant(recordFile.getString(fieldName));
        else
            return new IntConstant(recordFile.getInt(fieldName));
    }

    @Override
    public int getInt(String fieldName) {
        return recordFile.getInt(fieldName);
    }

    @Override
    public String getString(String fieldName) {
        return recordFile.getString(fieldName);
    }

    @Override
    public boolean hasField(String fieldName) {
        return schema.hasFiled(fieldName);
    }

    //================UpdateScan 接口中额外的方法实现===================

    @Override
    public void setVal(String fieldName, Constant newVal) {
        if (schema.type(fieldName)==Schema.VARCHAR)
            recordFile.setString(fieldName,(String) newVal.asJavaVal());
        else
            recordFile.setInt(fieldName,(Integer)newVal.asJavaVal());

    }

    @Override
    public void setInt(String fieldName, int newVal) {
        recordFile.setInt(fieldName,newVal);
    }

    @Override
    public void setString(String fieldName, String newVal) {
        recordFile.setString(fieldName,newVal);
    }

    @Override
    public void insert() throws IOException {
        recordFile.insert();
    }

    @Override
    public void delete() {
        recordFile.delete();
    }

    @Override
    public RID getRID() {
        return recordFile.currentRID();
    }

    @Override
    public void moveToRId(RID rid) {
        recordFile.moveToRID(rid);
    }
}

代码相对来说还是很直观的，构造函数会根据传入的TableInfo对象创造这张RecordFile对象，方法getVal()则会基于具体的字段，创建合适的Constant对象，方法setVal()则刚好执行相反的操作。方法hasField()则会查看一下表的schema，其他的方法则都是通过RecordFile对象提供的方法来完成的。

17.3.2 Select Scan

SelectScan类的代码如下，构造函数也会传入一个实现了Scan接口的对象，该对象可以是一个输入表（即TableScan），一个SelectScan对象的当前记录就是构造函数中传入的Scan对象的当前记录，这也就是说，SelectScan中许多方法的实现都可以通过直接调用传入Scan对象的相关方法来完成。

public class SelectScan implements UpdateScan {

    private Scan scan;
    private Predicate predicate;

    public SelectScan(Scan scan, Predicate predicate) {
        this.scan = scan;
        this.predicate = predicate;
    }

    //================Scan 接口中的方法实现===================

    @Override
    public void beforeFirst() {
        scan.beforeFirst();
    }

    @Override
    public boolean next() throws IOException {
        while (scan.next())
            if (predicate.isSatisified(scan))
                return true;
        return false;
    }

    @Override
    public void close() {
        scan.close();
    }

    @Override
    public Constant getVal(String fieldName) {
        return scan.getVal(fieldName);
    }

    @Override
    public int getInt(String fieldName) {
        return scan.getInt(fieldName);
    }

    @Override
    public String getString(String fieldName) {
        return scan.getString(fieldName);
    }

    @Override
    public boolean hasField(String fieldName) {
        return scan.hasField(fieldName);
    }

    //================UpdateScan 接口中额外的方法实现===================

    @Override
    public void setVal(String fieldName, Constant newVal) {
        // 这里必须把scan强转为UpdateScan类型
        // 也只有UpdateScan类型的对象才有setXXX()方法
        // 如果scan不是一个实现了UpdateScan接口的对象，运行时则会抛出ClassCastException异常
        UpdateScan updateScan = (UpdateScan) scan;
        updateScan.setVal(fieldName,newVal);
    }

    @Override
    public void setInt(String fieldName, int newVal) {
        UpdateScan updateScan = (UpdateScan) scan;
        updateScan.setInt(fieldName, newVal);
    }

    @Override
    public void setString(String fieldName, String newVal) {
        UpdateScan updateScan = (UpdateScan) scan;
        updateScan.setString(fieldName, newVal);
    }

    @Override
    public void insert() throws IOException {
        UpdateScan updateScan = (UpdateScan) scan;
        updateScan.insert();
    }

    @Override
    public void delete() {
        UpdateScan updateScan = (UpdateScan) scan;
        updateScan.delete();
    }

    @Override
    public RID getRID() {
        UpdateScan updateScan = (UpdateScan) scan;
        return updateScan.getRID();
    }

    @Override
    public void moveToRId(RID rid) {
        UpdateScan updateScan = (UpdateScan) scan;
        updateScan.moveToRId(rid);
    }
}

唯一一个需要特别注意的地方就是next()方法，next()方法的作用实际上是判断是否存在下一条记录，而在这里我们又要加上对记录的谓词判断。在代码中，我们必须使用while(scan.next())而不是if(scan.next())，因为，假如当前记录后面还存在3条记录r1、r2和r3，而r1又不满足预定义的谓词，在SelectScan中的next()方法的功能是判断是否存在满足谓词的下一条记录，因此必须找到r2并将之设置为当前记录，然后返回true。

Select scan是updatable的，所以在SelectScan中有关UpdateScan接口中的方法，都会先将scan强转为UpdateScan类型的，然后再调用相关的方法。在SimpleDB中，query planner（后续章节中的内容）只会对table scan和select scan创建updatable scan对象，所以，一旦发现抛出了ClassCaseException异常，肯定是代码中出现了bug。

17.3.3 Project scan

ProjectScan类的实现如下，想要输出的字段列表会通过构造函数传入，随后会判断这些字段是否存在，其他方法的实现也很直接，只要调用scan对象的相关方法即可。

public class ProjectScan implements Scan {
    private Scan scan;
    private Collection<String> fieldList;

    public ProjectScan(Scan scan, Collection<String> fieldList) {
        this.scan = scan;
        this.fieldList = fieldList;
    }

    // ============Scan 接口中相关方法的实现==============

    @Override
    public void beforeFirst() {
        scan.beforeFirst();
    }

    @Override
    public boolean next() throws IOException {
        return scan.next();
    }

    @Override
    public void close() {
        scan.close();
    }

    @Override
    public Constant getVal(String fieldName) {
        if (hasField(fieldName))
            return scan.getVal(fieldName);
        else
            throw new RuntimeException("Field "+fieldName+" is not found!");
    }

    @Override
    public int getInt(String fieldName) {
        if (hasField(fieldName))
            return scan.getInt(fieldName);
        else
            throw new RuntimeException("Field "+fieldName+" is not found!");
    }

    @Override
    public String getString(String fieldName) {
        if (hasField(fieldName))
            return scan.getString(fieldName);
        else
            throw new RuntimeException("Field "+fieldName+" is not found!");
    }

    @Override
    public boolean hasField(String fieldName) {
        return fieldList.contains(fieldName);
    }
}

注意，在SimpleDB中Project Scan被设计成了不可更新的（实际上，是可以设计成可更新的），因此也没必要也不能去实现UpdateScan接口，练习17.16有相关的讨论。

17.3.4 Product scan

ProductScan类的实现代码如下：

public class ProductScan implements Scan {
    private Scan scan1,scan2;

    public ProductScan(Scan scan1, Scan scan2) throws IOException {
        this.scan1 = scan1;
        this.scan2 = scan2;
        scan1.next();
    }

    // ============Scan 接口中相关方法的实现==============

    @Override
    public void beforeFirst() throws IOException {
        scan1.beforeFirst();
        scan1.next();
        scan2.beforeFirst();
    }

    @Override
    public boolean next() throws IOException {
        if (scan2.next())
            return true;
        else {
            scan2.beforeFirst();
            return scan1.next() && scan2.next();
        }
    }

    @Override
    public void close() throws IOException {
        scan1.next();
        scan2.next();
    }

    @Override
    public Constant getVal(String fieldName) {
        if(scan1.hasField(fieldName))
            return scan1.getVal(fieldName);
        else
            return scan2.getVal(fieldName);
    }

    @Override
    public int getInt(String fieldName) {
        if(scan1.hasField(fieldName))
            return scan1.getInt(fieldName);
        else
            return scan2.getInt(fieldName);
    }

    @Override
    public String getString(String fieldName) {
        if(scan1.hasField(fieldName))
            return scan1.getString(fieldName);
        else
            return scan2.getString(fieldName);
    }

    @Override
    public boolean hasField(String fieldName) {
        return scan1.hasField(fieldName) || scan2.hasField(fieldName);
    }
}

product操作对应的是大多数中文数据库书中的联结操作，也就是对两个表中的记录求一个笛卡尔积。在代码中，我们先开始遍历scan1中的所有记录作为笛卡尔积的左侧元素，然后再遍历scan2中所有的记录作为笛卡尔积的右侧元素；也就是类似一个嵌套的循环，scan1为外层循环，scan2为内层性循环。

next()方法是这样实现这个嵌套循环的：每次都调用内层scan2循环的next()，如果scan2有下一条记录，则返回true；如果scan2没有下一条记录，则肯定是内层循环到了底，此时必须调用外层循环的next()方法，于是返回scan1的下一条记录，并且把scan2移动到第一条记录，然后返回true；否则其他情况，返回false。

getXXX()方法则很简单了，只不过多了一个判断指定字段是来自于哪个scan的操作。

17.4 流水线式的查询处理

我们已经知道了simpleDB中几种基本的关系代数操作是如何实现的，实际上，这些实现被称为流水线式的(pipelined),它们有下面的两个特点。

• 按照客户端的需要，每次只会输出一条记录

• 实现中不会保存输出记录，也不会保存任何中间的计算结果。

我们在这里只分析TableScan和SelectScan的特点，ProductScan和ProjectScan的分析则类似。

假设有一个TableScan类型的对象，它的实现中是维护了一个record file的，这个record file又是维护了一个record page的，这个record page又是持有了一个buffer的，buffer中又持有一个页，而这个页中包含的是对应块中的实际内容的。当前记录只是在这个页中的一个位置，每当客户端请求访问一个字段的具体取值时，记录管理器只会提取出这个字段的值而已，随后返回这个值可客户端；而每次调用next()方法后则会将当前记录移动至下一条，这个操作有可能会引发一次缓冲区的换入换出（swapping）。

现在我们继续考虑有一个SelectScan类型的对象，每次调用该对象的next()方法实际上调用的是一个underlying的Scan类型对象的next()方法，直到找到一个满足谓词的记录。但是实际上，这个SelectScan类型的对象根本没有什么“当前记录”——如果这个对象的underlying的Scan类型对象是一个Table Scan, 那么这个当前记录只不过是在页中的一个位置而已了，对吧？也就是说，根本没有一个实际的变量保存了当前记录所有值。每次select scan调用next()方法，实际上都是从上一次的位置往下搜索的。

最后，很重要的一点，一个select scan不会追踪已经选择了的记录，也就是说，如果一个客户端需要连续2次请求同一个记录，select scan必须遍历两次。

术语"流水线"代表的是查询树自顶向下的方法调用流，以及自底向上的结果返回流。举例来说，假如查询树中的某个结点调用了getInt()方法，那么这个结点会一直往下调用它的子结点的方法，直到访问到了叶子节点，叶子节点随后将提取出来的值又一直往它的父结点抛上去。在比如，假如调用next()方法，它可能会调用它的子节点的next()方法多次直到找到了满足条件的下一条记录，这个例子其实就是select scan对table scan的调用，随后也会同样地返回结果。

流水线式的实现是非常高效的，例如，请看图17-12中的查询树的例子，我们可以发现，project结点和select结点的cost实际上是0。

方法调用流程是这样的：

• 我们先考虑最顶层的project结点，每次调用next()方法，都会简单地调用第一个select结点（也就是Select: GradYear=2006结点）的next()方法；

• 第一个select结点又会继续往下调用第二个select结点的next()方法；

• 第二个select结点又会继续往下调用table scan结点的next()方法。

结果返回的流程又是这样的：

• table scan结点会遍历record file，判断是否存在下一条记录，并返回给第二个select结点（返回的是布尔值）；

• 如果子节点抛来的布尔值是true，则第二个select结点会判断当前这条记录是否满足谓词，随后把判断结果也往上抛；

• 如果第二个select结点往上抛出的布尔值是false，那肯定第一个select结点也无需再去做谓词判断了，随后继续把这个值抛给父结点；

• project结点也肯定会接受到这个false值，又重新执行下一轮调用流程了。

这么一分析，project结点和select结点的cost真的是0，只有叶子结点会执行具体的底层遍历逻辑。虽然说，这种流水线的实现方式在某些场合下很高效，但是在某些场合下也不是那么好（译者注：常言道，Every coin has two sides，但是既然有两面，那肯定有Edge，我们站在Edge上同时看两个sides就好了，对吧？）。这种不太好的场合的一个例子是，当一个select scan结点是在一个product scan结点的右边时，会执行很多轮的方法调用（很难用语言描述，看下代码分析一下就可以）。在这种情况下，为了避免一遍又一遍地遍历，选用一种可以将输出记录具体化(materialize)到一个临时表中的实现会更好。这中实现将在第22章中讨论。

17.5 估计Scan的代价

数据库系统的一个职责是对于一个给定的SQL查询，创建一个最高效的scan。于是系统必须去估计一个scan的执行用时大概是多少。由于一个scan所需执行的文件块访问数，是评估执行代价的最关键因素，因此估计所需的块访问次数就足够了。 在本节中，我们将考虑如何估算一个scan的代价，而 在第24章中，我们将了解数据库系统如何利用这些信息。

一个scan的代价可以用类似16.4小节中的数据统计信息术语来评估：

假设有某个scan，记为s，并记s中的某个字段为F。 $B(s)$表示构造s的输出所需的块访问数量。 $R(s)$表示s输出的记录条数。 $V(s, F)$表示s输出的所有记录中，F字段的所有可能取值数。

图17-13包含了每个关系代数操作的代价公式，这些公式的推导我们将一一道来。

17.5.1 Table scan的代价

每个table scan都维护了一个record file，record file又维护了一个当前的record page，record page实际上又是一个buffer中的page，page又实际对应了底层的一个文件块。当某个page上对应的记录全部被读取完毕后，该page所在的缓冲区会被取消固定(unppin)，并且记录文件中的下一个页（说准确点，应该是下一个块）又被读。因此，table scan只需一次遍历就可以访问所有的记录，因此$B(s)$、$R(s)$和$V(s, F)$则很容易计算，和一个表的数据统计信息几乎一样，如17-13中公式所示。

17.5.2 Select scan的代价

一个select scan有一个underlying的scan，我们用$s_1$来表示，每次select scan调用next()方法，则都会相应调用$s_1$的next()方法一次或多次，每次select scan调用getXXX()方法都会执行$s_1$的相应get方法，这些get方法是无需块访问的，于是一个select scan的块访问数和它所拥有的underlying的scan的块访问数是一样的，即$B(s) = B(s_1)$。

至于$R(s)$和$V(s, F)$的计算，则取决于相应具体的谓词了，例如我们先分析一个常见的情况，谓词的判断逻辑是一个字段的取值是一个具体的值，或者一个字段的取值和另一字段的取值相等。

Selection on a constant

假设谓词是形如“A = c”的形式，如果我们假设A字段的所有取值全是均匀的分布（这个假设其实很常见），那么匹配该谓词的所有记录数量则为$R(s_1)/ V(s_1, A)$

在均匀分布的假设下，也意味着输出中的其他字段的取值也是均匀分布的，因此有：

V(s, A)=1 
V(s, F)=min{R(s), V(s_1,F)} , for all other fields F

Selection on a field

现在我们假设谓词的形式是“A = B”，在这种情况下，字段A和字段B肯定是存在某种关系的，尤其是，如果我们假设B字段的所有可能取值数比A多（即$V(s_1, A)<V(s_1, B)$），那么A字段的每个取值必然能在B字段中找到一个对应相等的值，这种情况其实就是B字段是某张表的主键，而字段A是另一张表中外键的情况了！在这种情况下，A字段的每个取值在匹配B字段中取值的概率为$1/ V(s_1, B)$；当然如果我们的假设刚好相反，即B字段的所有可能取值数比A少（即$V(s_1, A) > V(s_1, B)$）,概率值则为$1/ V(s_1, A)$。

无论是上述的哪一种情况，反正概率总是取值数多的的那个字段的倒数，因此$R(s) = R(s_1) / max\{V(s_1, A) , V(s_1, B) \}$。

在均匀分布的假设下，也意味着每个A字段的值也是有相同的概率匹配B字段的值，所以有：

V(s, F) = min {V(s_1,A), V(s_1,B)}, for F=A or B 
V(s, F) = min {R(s), V(s_1,F)}, for all fields F other than A or B

17.5.3 Project scan的代价

和select scan一样，project scan也有一个underlying的scan（记作$s_1$）,这3个值可以很快地算出来，有：

B(s) = B(s1)
R(s) = R(s1)
V(s, F) = V(s1, F), for all fields F

17.5.4 Product scan的代价

一个product scan有两个underlying的scan，记作$s_1$和$s_2$，和之前小节中分析的一样，遍历一次product scan，需要遍历一遍$s_1$，并对于$s_1$中的每一条记录，都要遍历一遍$s_2$，因此有下列的公式：

B(s) = B(s1) + (R(s1) * B(s2)) 
R(s) = R(s1) * R(s2) 
V(s, F) = V(s1, F) or V(s2, F), depending on which table F comes from .

这里非常有趣的一点是，$B(s)$这个公式不是关于$s_1$和$s_2$对称的，也就是说，从逻辑上讲，语句Scan s3 = new ProductScan(s1, s2);和Scan s3 = new ProductScan(s2, s1);的结果是一样的，但是访问代价是不一样的。

差了多少呢？我们现在定义$RPB(s) =R(s) / B(s)$，即scan结果每个块上的记录数，于是上面的公式可以改写为$B(s) = B(s_1) + ( RPB(s_1) * B(s_1) * B(s_2) )$，这个公式的关键项其实就是$RPB(s_1) * B(s_1) * B(s_2)$，而决定该项大小的关键就是$RPB(s_1)$，所以，把RPB小的那个scan放在product scan的左边是会让$B(s)$整体取得最小！

举个例子来说，假设$s_1$是学生表STUDENT，$s_1$是学院表DEPT，因为学生的记录数肯定远大于学院的记录数，并且一条学生的信息一般都比一条学院信息大，也就是说学生表的PRB更小，所以把学生表放在product的左边会更好。

译者注：其实我个人感觉这个推导不完全正确，因为还和$B(s_1)$有关，如果你真的要仔细推导的话，你会发现除了RPB这个因素之外，其实还和$R(s_1)$、$R(s_2)$的具体取值有关，我只能说作者给出的上述结论在大多数情况下是成立的。

17.5.5 一个具体的例子

现在考虑一个SQL查询，其功能是返回所有数学专业的学生名字，图17-14（a）展示了这个query，图17-14（b）给出了相应的SimpleDB代码，图17-14（c）给出了这些scan的数据统计信息，我们假设底层实际表的存储和16章中的图16-7一样。

$s_1$和$s_2$和学生表、学院表的数据统计信息一样，而$s_3$这个select scan只返回1条记录，但需要访问的块数则是所有块；$s_4$这个product scan返回45000条学生记录和一条专业记录的笛卡尔积，输出自然也是45000条记录，但是这个笛卡尔积的操作会需要94500次块访问，因为每个学生记录都会遍历一遍DEPT表，这需要$45000 x 2 = 90000$次块访问，再加上STUDENT表也要遍历一遍，所以就是$90000 +4500 =94500$次块访问。而至于$s_5$这个select scan的话会把笛卡尔积的45000条记录除以40（假设学生的专业是均匀分布的），得到1125条记录，但是需要访问的块数丝毫不会减少。project scan的话，不会改变任何一个值。

数据库系统重新计算数学学院这条记录45,000次，而且代价很高，这似乎很奇怪，我们查看一下STUDENT表和s3的RPB取值，我们会发RPB（STUDENT）= 10，而RPB（s3）= 0.5， 由于把较小RPB的scan放在product scan的左侧时效代价更低，因此将s4定义为以下会更有效：

s4 = new ProductScan(s3, STUDENT)

练习17.7要求您证明在这种情况下，该操作仅需要4502次块访问。

17.6 Plan

一个SQL查询可能对应多个等价的查询树，而每个查询树又对应一个不同的scan，因此又对应有不一样的执行代价。数据中的planner是负责创建最小代价scan的组件。为了实现这个功能，planner需要创建多个可能的查询树，并且分别计算出它们的代价，然而最后，只选择那个代价最小的scan。

为了比较执行代价而构造的查询树称为plan。

plan和scan在概念上相似，因为它们都表示查询树。不同之处在于，plan对象具有估算代价的方法，它访问数据库的元数据，但不访问实际数据，我们 可以创建多个plan，而不会引起过度的磁盘访问开销。 然而，scan对象则是为了访问数据库而创建的， 创建scan对象后，将为查询中提到的每个表打开一个record file，该record file又将其记录文件的第一个块读入缓冲区， 因为打开scan会导致磁盘访问，所以数据库系统在确定是执行查询的最佳方法之前不会创建scan。

一个plan的接口为Plan，如下：

public interface Plan {
    public  Scan open();
    public  int blockAccessed();
    public int recordsOutput();
    public int distinctValues(String fldName);
    public Schema schema();
}

解开了中支持方法blocksAccessed(), recordsOutput()和distinctValues()，就是对应于一个plan的$B(s), R(s), and V(s, F)$三个值。schema()方法则会返回输出表的schema，query planner到时候可以使用这个schema来做类型验证，以及优化plan的工作；最后，每个plan对象也会有一个open()方法来创建一个对应的scan对象。

创建一个plan和创建一个scan类似，对于每个关系代数操作，都会有一个对应实现了Plan接口的具体类，TablePlan类会处理存储的表。例如，考虑一下图17-16中的例子，这个例子和图17-4中的例子是对应一样的query，图17-4（b）和图17-16（b）是类似的，主要的区别就是这里创建了一个plan。

下面将依次给出TablePlan,SelectPlan,ProjectPlan和ProductPlan的实现，其中TablePlan会直接从StatMgr类中估计代价，其他类则会按照17.5小节中的那张表格计算相应的代价。

public class TablePlan implements Plan {
    private Transaction tx;
    private TableInfo tableInfo;
    private StatInfo statInfo;

    public TablePlan(String tblName,Transaction tx) throws IOException {
        this.tx = tx;
        this.tableInfo = SimpleDB.metadataMgr().getTableInfo(tblName,tx);
        this.statInfo = SimpleDB.metadataMgr().getStatInfo(tblName,tx);
    }

    @Override
    public Scan open() throws IOException {
        return new TableScan(tableInfo,tx);
    }

    @Override
    public int blockAccessed() {
        return statInfo.blocksAccessed();
    }

    @Override
    public int recordsOutput() {
        return statInfo.recordsOutput();
    }

    @Override
    public int distinctValues(String fldName) {
        return statInfo.distinctValues(fldName);
    }

    @Override
    public Schema schema() {
        return tableInfo.schema();
    }
}

select plan的代价估计比其他操作复杂一些，因为具体的估计取决于谓词是什么。因此，select plan可以使用谓词的reduceFactor()和equatesWithConstant()方法。 方法recordsAccessed()会调用reductionFactor()方法来计算这个谓词使得输入表记录减小的程度。 distinctValues()会使用方法equatesWithConstant()来判断指定字段的值是否满足谓词中的常量。

public class SelectPlan implements Plan {
    private Plan plan;
    private Predicate predicate;

    public SelectPlan(Plan plan, Predicate predicate) {
        this.plan = plan;
        this.predicate = predicate;
    }

    @Override
    public Scan open() throws IOException {
        Scan scan = plan.open();
        return new SelectScan(scan, predicate);
    }

    @Override
    public int blockAccessed() {
        return plan.blockAccessed();
    }

    @Override
    public int recordsOutput() {
        // predicate.reductionFactor(plan)就是 图17-13 中的 V(s_1, A)
        return plan.recordsOutput() / predicate.reductionFactor(plan);
    }

    @Override
    public int distinctValues(String fldName) {
        if (null != predicate.equatesWithConstant(fldName))
            return 1;
        else {
            String theOtherFldName = predicate.equatesWithField(fldName);
            if (theOtherFldName != null)
                return Math.min(plan.distinctValues(fldName),
                        plan.distinctValues(theOtherFldName));
            else
                return Math.min(recordsOutput(), plan.distinctValues(fldName));
        }

    }

    @Override
    public Schema schema() {
        return plan.schema();
    }
}

ProjectPlan类和ProductPlan类会根据underlying的plan对象的schema创建新的schema结果。具体来说，ProjectPlan类会在underlying plan对象已有schema中筛掉一些字段；ProductPlan类则会取两个schema的并集。

public class ProjectPlan implements Plan {
    private Plan plan;
    private Schema schema = new Schema();

    public ProjectPlan(Plan plan, Collection<String> fieldList) {
        this.plan=plan;
        for (String fieldName : fieldList)
            schema.add(fieldName,plan.schema());
    }

    @Override
    public Scan open() throws IOException {
        Scan scan=plan.open();
        return  new ProjectScan(scan,schema.fields());
    }

    @Override
    public int blockAccessed() {
        return plan.blockAccessed();
    }

    @Override
    public int recordsOutput() {
        return plan.recordsOutput();
    }

    @Override
    public int distinctValues(String fldName) {
        return plan.distinctValues(fldName);
    }

    @Override
    public Schema schema() {
        return schema;
    }
}

public class ProductPlan implements Plan {
    private Plan plan1, plan2;
    private Schema schema = new Schema();

    public ProductPlan(Plan plan1, Plan plan2) {
        this.plan1 = plan1;
        this.plan2 = plan2;
        this.schema.addAll(plan1.schema());
        this.schema.addAll(plan2.schema());
    }

    @Override
    public Scan open() throws IOException {
        Scan scan1 = plan1.open();
        Scan scan2 = plan2.open();
        return new ProductScan(scan1, scan2);
    }

    /**
     * 图17-13中的 B(s_1) + R(s_1) * B(s_2)
     *
     * @return
     */
    @Override
    public int blockAccessed() {
        return plan1.blockAccessed() +
                (plan1.recordsOutput() * plan2.blockAccessed());
    }

    /**
     * 图17-13中的 R(s_1) * R(s_2)
     * @return
     */
    @Override
    public int recordsOutput() {
        return plan1.recordsOutput() * plan2.recordsOutput();
    }

    @Override
    public int distinctValues(String fldName) {
        if(plan1.schema().hasFiled(fldName))
            return plan1.distinctValues(fldName);
        else
            return plan2.distinctValues(fldName);
    }

    @Override
    public Schema schema() {
        return schema;
    }
}

对于每个类中的open()方法则比较简单，通常来说，构造一个plan对应的scan需要2步：

• 首先，对于每个plan，都会先构造其underlying plan的scan（当然，underlying plan可能又有另外的underlying plan，这是一个递归的过程）；

• 随后，把这个构造好的Scan接口对象构造一个具体的Scan类型对象。

17.7 谓词

17.7.1 谓词定义及相关API

现在，我们来考虑一下谓词的结构以及它们在SimpleDB中的实现和使用方式。

从结构上讲，我们有以下定义：

一个谓词(predicate)是一系列项(term)的布尔组合； 一个项(term)是两个表达式(expression)之间的比较； 一个表达式(expression)包含对字段名和常数上的操作。

例如，考虑下面的这个谓词：

(GradYear = 2006 or GradYear = 2007) and MajorId = DId

该谓词包含三个项，前两个项将字段名称GradYear与常量进行比较，而第三项将两个字段名称进行比较；这些项中的每个表达式都不涉及任何运算，并且可以是字段名称或常量。 通常，表达式可以具有运算符（例如算术运算符）或内置函数。

在SimpleDB中，表达式只能是常量或字段名；一个项只支持相等比较；谓词只支持项之间的主合取范式（离散数学中的概念）。 在这里，我们只讨论简化的情况， 练习17.11至17.13要求你考虑更一般的情况。

public class Predicate {
    // 供 Parser调用
    public void conjoinWith(Predicate predicate);

    // 供 SelectScan中的next()方法调用
    public boolean isSatisified(Scan s);

    // 供SelectPlan中的recordsOutput()方法调用
    public  int reductionFactor(Plan p);

    // 供 query planner调用
    public Predicate selectPred(Schema schema);
    public Predicate joinPred(Schema schema1,Schema schema2);
    public Constant equatesWithConstant(String fieldName);
    public String equatesWithField(String fieldName);

}

上面给出了类Predicate的API，这些方法解决了数据库系统中好几个部分的需求：

• parser会在处理SQL的where语句时构建一个谓词，那时会调用方法conjoinWith()来将一个当前这个谓词与另外一个谓词取AND运算。

• 一个select scan会调用isSatisfied()方法来判断一个谓词是否满足。

• 一个select plan会调用reductionFactor()和equatesWithConstant()方法来评估一个谓词的筛选性(selectivity)。

• query planner 需要分析谓词的范围并将其分解为较小的部分。方法selectPred()返回谓词的一部分（如果有的话），该部分是具有指定schema表的选择谓词。 同样，方法joinPred()返回两个指定schema的join谓词（如果有的话）。equatesWithConstant()方法会针对某个指定字段A查找形式为“ A = c”的项； 该项（term）的存在表明可能建立索引。 出于类似的原因，方法equatesWithField()则会查找形式为“ A = B”的项。

simpleDB对应的SQL语句也只支持两种常数：整型和字符串，而在真正的SQL中支持很多数据类型，但是无论有多少数据类型，query是不会具体去处理字段的类型的，而是用一个抽象的Constant类型来描述。考虑这样一个谓词的例子，MajorId=DId,这个谓词并不在意数据到底是什么类型的，谓词只关注这些值是否可以有意义地进行比较。

在SimpleDB中，接口Constant就是来完成这个工作的，其中包含了一些常用的方法（如equals(),hashCode(),compareTo()等），方法asJavaVal()会转化为实际的Java类型，如下所示：

public interface Constant extends Comparable<Constant> {
    public Object asJavaVal();
}

对于每个具体的数据类型，都会有Constant接口的实现，在SimpleDB中，也就有IntConstant和StringConstant类，实现代码如下所示：

// StringConstant.java
public class StringConstant implements Constant {
    private String val;

    public StringConstant(String val) {
        this.val = val;
    }

    @Override
    public int hashCode() {
        return val.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        StringConstant sc = (StringConstant) obj;
        return sc != null && val.equals(sc.val);
    }


    @Override
    public String toString() {
        return val.toString();
    }


    @Override
    public Object asJavaVal() {
        return val;
    }

    @Override
    public int compareTo(Constant o) {
        StringConstant sc = (StringConstant) o;
        return val.compareTo(sc.val);
    }
}

// IntConstant.java
public class IntConstant implements Constant {
    private Integer val;

    public IntConstant(Integer val) {
        this.val = val;
    }

    @Override
    public int hashCode() {
        return val.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        IntConstant ic = (IntConstant) obj;
        return ic != null && val.equals(ic.val);
    }


    @Override
    public String toString() {
        return val.toString();
    }


    @Override
    public Object asJavaVal() {
        return val;
    }

    @Override
    public int compareTo(Constant o) {
        IntConstant ic = (IntConstant) o;
        return val.compareTo(ic.val);
    }
}

17.7.2 谓词的实现

SimpleDB中的表达式则是使用接口Expression来实现的，还记得表达式是什么吗？一个表达式(expression)包含对字段名和常数上的操作。代码如下：

public interface Expression {
    public boolean isConstant();
    public boolean isFieldName();
    public Constant asConstant();
    public String asFieldName();

    public Constant evaluate(Scan scan);
    public boolean appliesTo(Schema schema);
}

这个接口有2个具体的实现类，分别是形如"A=c"和“A=B”这样的表达式。方法isConstant()、isFieldName()、asConstant()、和asFieldName()允许客户端获得表达式的内容，并且会被planner用来分析一个query的格式。方法appliesTo()告诉planner当前表达式是否涉及指定schema中的字段，方法evaluate()则会在返回某个scan的输出记录对应这个表达式的具体取值。如果这个表达式是一个形如“A=c”的常数表达式，则你可以视为这个scan输入参数是无关的，并直接返回这个c；如果这个表达式是一个形如“A=B”的字段表达式，则该方法会返回当前记录对应这个字段的取值。Talk is cheap，show you the code！

// ConstantExpression.java
public class ConstantExpression implements Expression {
    private Constant val;

    public ConstantExpression(Constant val) {
        this.val = val;
    }

    @Override
    public boolean isConstant() {
        return true;
    }

    @Override
    public boolean isFieldName() {
        return false;
    }

    @Override
    public Constant asConstant() {
        return val;
    }

    @Override
    public String asFieldName() {
        throw new ClassCastException();
    }

    @Override
    public Constant evaluate(Scan scan) {
        return val;
    }

    @Override
    public boolean appliesTo(Schema schema) {
        return true;
    }

    public String toString()
    {
        return val.toString();
    }

}

// FieldNameExpression.java
public class FieldNameExpression implements Expression {
    private String fldName;

    public FieldNameExpression(String fldName) {
        this.fldName = fldName;
    }

    @Override
    public boolean isConstant() {
        return false;
    }

    @Override
    public boolean isFieldName() {
        return true;
    }

    @Override
    public Constant asConstant() {
        throw  new ClassCastException();
    }

    @Override
    public String asFieldName() {
        return fldName;
    }

    @Override
    public Constant evaluate(Scan scan) {
        return scan.getVal(fldName);
    }

    @Override
    public boolean appliesTo(Schema schema) {
        return schema.hasFiled(fldName);
    }

    public String toString()
    {
        return fldName;
    }
}

SimpleDB的项是通过类Term来实现的，还记得项的定义吗？一个项(term)是两个表达式(expression)之间的比较，其代码如下所示，方法reductionFactor()是严格按照17.5.2小节中的公式实现的，这个方法有4种可能的形式：

• 表达式等号左右两边都是字段；

• 表达式等号左边是字段，等号右边是一个值；

• 表达式等号左边是一个值，等号右边是一个字段；

• 表达式等号左右两边都是值。

  public class Term {
    private Expression lhs, rhs;
  
    public Term(Expression lhs, Expression rhs) {
        this.lhs = lhs;
        this.rhs = rhs;
    }
  
    /**
     * 一个谓词项使得记录数减少的因子。
     * <p>
     * 详情参见图 17-12
     *
     * @param plan
     * @return
     */
    public int reductionFactor(Plan plan) {
        String lhsName, rhsName;
        // 1. 左右两边都是字段
        // 图17-12 中的 max{V(s_1,A), V(s_1,B)}
        if (lhs.isFieldName() && rhs.isFieldName()) {
            lhsName = lhs.asFieldName();
            rhsName = rhs.asFieldName();
            return Math.max(plan.distinctValues(lhsName),
                    plan.distinctValues(rhsName));
        }
        // 2. 左边是字段名，右边是常量
        if (lhs.isFieldName()) {
            // 图17-12 中的 V(s_1,A)
            lhsName = lhs.asFieldName();
            return plan.distinctValues(lhsName);
        }
        // 3. 左边是常量，右边是字段名
        if (rhs.isFieldName()) {
            // 图17-12 中的 V(s_1,A)
            rhsName = rhs.asFieldName();
            return plan.distinctValues(rhsName);
        }
        // 4. 左右两边全是常量
        if (lhs.asConstant().equals(rhs.asConstant()))
            return 1;
        else
            return Integer.MAX_VALUE;
    }
  
    public Constant equatesWithConstant(String fldName) {
        // 左边是字段名，右边是常量
        if (lhs.isFieldName() && lhs.asFieldName().equals(fldName) && rhs.isConstant())
            return rhs.asConstant();
            // 左边是常量，右边是字段名
        else if (rhs.isFieldName() && rhs.asFieldName().equals(fldName) && lhs.isConstant())
            return lhs.asConstant();
        else
            return null;
    }
  
    public String equatesWithField(String fldName) {
        if (lhs.isFieldName() && lhs.asFieldName().equals(fldName) && rhs.isFieldName()) {
            return rhs.asFieldName();
        } else if (rhs.isFieldName() && rhs.asFieldName().equals(fldName) && lhs.isFieldName()) {
            return lhs.asFieldName();
        } else
            return null;
    }
  
    public boolean appliesTo(Schema schema) {
        return lhs.appliesTo(schema) && rhs.appliesTo(schema);
    }
  
    /**
     * 判断一个项左右两边是否相等
     *
     * @param scan
     * @return
     */
    public boolean isSatisfied(Scan scan) {
        Constant lhsVal = lhs.evaluate(scan);
        Constant rhsVal = rhs.evaluate(scan);
        return lhsVal.equals(rhsVal);
    }
  
    public String toString() {
        return lhs.toString() + " = " + rhs.toString();
    }
  }

  谓词的实现类Predicate代码如下所示，一个谓词就是通过很多个项（term）组成的，谓词中会把各方法实现转发给相应的Term类中的方法。

  public class Predicate {
    private List<Term> terms = new ArrayList<>();
  
    public Predicate() {
    }
  
    /**
     * Creates a predicate containing a single term.
     * @param term
     */
    public Predicate(Term term) {
        this.terms.add(term);
    }
  
    // 供 Parser调用
    public void conjoinWith(Predicate predicate) {
        terms.addAll(predicate.terms);
    }
  
    /**
     * 判断一个谓词是否成立。
     * <p>
     * 只有谓词中所有的项均为真，整个谓词才为真。
     * <p>
     * 该方法供SelectScan中的next()方法调用
     *
     * @param s
     * @return
     */
    public boolean isSatisified(Scan s) {
        for (Term t : terms) {
            if (!t.isSatisfied(s))
                return false;
        }
        return true;
    }
  
    /**
     * 判断一个谓词使得输出记录数减少的因子。
     * <p>
     * 详情计算方法参见图 17-12。
     * <p>
     * 该方法供SelectPlan中的recordsOutput()方法调用
     *
     * @param p
     * @return
     */
    public int reductionFactor(Plan p) {
        int factor = 1;
        for (Term t : terms) {
            factor *= t.reductionFactor(p);
        }
        return factor;
    }
  
    /**
     * 返回满足指定schema的子谓词。
     * <p>
     * 该方法供 query planner调用
     *
     * @param schema
     * @return
     */
    public Predicate selectPred(Schema schema) {
        Predicate newPredicate = new Predicate();
        for (Term t : terms) {
            if (t.appliesTo(schema))
                newPredicate.terms.add(t);
        }
        if (newPredicate.terms.size() == 0)
            return null;
        else
            return newPredicate;
    }
  
    /**
     * 返回满足两个schema并集的子谓词。
     *
     * @param schema1
     * @param schema2
     * @return
     */
    public Predicate joinPred(Schema schema1, Schema schema2) {
        Predicate newPredicate = new Predicate();
        Schema newSchema = new Schema();
        newSchema.addAll(schema1);
        newSchema.addAll(schema2);
        for (Term t : terms) {
            if (!t.appliesTo(schema1) &&
                    !t.appliesTo(schema2) &&
                    t.appliesTo(newSchema))
                newPredicate.terms.add(t);
        }
        if (newPredicate.terms.size() == 0)
            return null;
        else
            return newPredicate;
    }
  
    /**
     * 判断一个谓词中是否存在形如"A=c"的项，
     * 其中A是指定字段名，c是指定的常量。
     * <p>
     * 如果有，返回该常量c；否则返回null。
     *
     * @param fieldName
     * @return
     */
    public Constant equatesWithConstant(String fieldName) {
        for (Term t : terms) {
            Constant result = t.equatesWithConstant(fieldName);
            if (result != null)
                return result;
        }
        return null;
    }
  
    /**
     * 判断一个谓词中是否存在形如"A=B"的项，
     * 其中A是指定字段名，B是另一个字段名
     * <p>
     * 如果有，返回指定字段名；否则返回null。
     *
     * @param fieldName 指定字段名A
     * @return 另一个字段名B
     */
    public String equatesWithField(String fieldName) {
        for (Term t : terms) {
            String result = t.equatesWithField(fieldName);
            if (result != null)
                return result;
        }
        return null;
    }
  
    public String toString() {
        Iterator<Term> iter = terms.iterator();
        if (!iter.hasNext())
            return "";
        String result = iter.next().toString();
        while (iter.hasNext())
            result += " and " + iter.next().toString();
        return result;
    }
  }

  现在我们已经把谓词给实现了，看下怎么使用吧！想必你也肯定知道了。例如，考虑下面这个谓词：

  SName = 'joe' and MajorId = DId

  创建该谓词的客户端代码如下：

  public class PredicateTest {
    public static void main(String[] args) {
        Expression lhs1=new FieldNameExpression("SName");
        Expression rhs1=new ConstantExpression(new StringConstant("joe"));
        Term term1=new Term(lhs1,rhs1);
  
        Expression lhs2=new FieldNameExpression("MajorId");
        Expression rhs2=new FieldNameExpression("DId");
        Term term2=new Term(lhs2,rhs2);
  
        Predicate pred1=new Predicate(term1);
        System.out.println(pred1);
        pred1.conjoinWith(new Predicate(term2));
        System.out.println(pred1);
    }
  }

  显然，这些代码对于人来说是乏味的，但是，parser用这种方式来解析谓词却是很自然的，并且parser就是负责构造谓词的，它知道怎么做。

17.8 章末总结

• 一个scan对象代表了一棵关系代数查询树。每一种关系代数操作都有一个Scan接口的具体实现，且每个操作在查询树中代表一个结点；对于涉及具体表的操作，则在树中是叶子结点。

• Scan接口的方法和RecordFile类很相似，客户端遍历scan，当前记录不断向前移动，客户端可以提取相应的字段值。Scan接口的具体实现类会负责移动指向当前记录的“游标”，移动到合适的位置，比较字段值（例如SelectScan类）。

• 当一个scan中的每条记录$r$都在某个数据库表中存在一条对应的$r'$记录时，我们称这个scan是可更新的。

• 每个具体的Scan接口实现类中，都会存在相应的关系代数操作实现： 1. 一个select scan会检查underlying的scan对象中的每条记录，如果符合谓词，则返回这条记录；否则不断往下遍历。 2. 一个product scan返回的是两个scan对象中所有记录的笛卡尔积。 3. 一个table scan对象会打开指定表的Record File对象，而record file对象会将块固定缓冲区，而在读取相应值的时候又会获取相应的锁。

• 上述这些scan的实现方式被称为基于流水线式的实现，术语"流水线"代表的是查询树自顶向下的方法调用流，以及自底向上的结果返回流。一个查询树的非叶子结点会不断地向子结点forward方法调用，并且只有在叶子结点（也就是table scan）才会真正去访问RecordFile对象，涉及底层的页换入换出、块读写等操作；反过来，一旦叶子结点得到一个记录，就会不断向父结点backward回结果。

• 一条SQL语句可能对应多个查询树，为了构造最高效的查询树，数据库系统必须先估计一下遍历查询树（也就是scan）的代价。为了更好地估计某个scan $s$的执行代价，有下面几个量需要着重关注： 1. B(s)代表遍历s需要的块访问次数。 2. R(s)代表s的输出记录条数。 3. V(s,F)代表s的所有输出记录中，F字段所有可能取值的数量。

• 数据中planner组件负责创建执行代价最低的scan对象，为了比较各个输出结果等价的scan对象的执行代价，planner会创建多个plan对象。plan和scan在概念上几乎是一模一样的，它们都代表着一棵查询树，区别在于，plan中还有相关的评估函数，来评估执行代价，也就是上述的B(s), R(s)和V(s,F),这些评估函数不会访问数据库表中的实际记录，而是访问表的元数据(metadata)。planner会最终选择评估代价最下的plan对象，并调用open()方法来创建一个对应的实际的scan对象。

17.9 建议阅读

17.10 练习