SQL的诞生

SQL英文全称是Structured Query Language，中文名即结构化查询语言，是一门专门用来查询数据的声明式编程语言。

我先解释一下声明式语言的概念，编程语言有两个分类：

• 命令式：手把手教机器做事情
• 声明式：告诉机器任务，让它自己想办法解决

举个例子，假设你家里有机器人，你想让它帮忙拿一个在客厅桌子上的白色杯子给你。

如果用命令式编程的方式来实现，你需要给机器人输入指令：把第一个房间的第二个家具上的第五个东西拿给我。然后机器人会按照你的指示先找到第一个房间，然后找到第二个家具，最后再找到第五个东西。

如果是用声明式编程的方式来实现，你只会说：帮忙拿一下客厅桌子上面的白色杯子给我。然后机器人就会先找到客厅对应的房间编号，再找到桌子对应的编号，最后找到白色杯子对应的编号，然后根据编号去找对应的东西。

上面哪张方式对人来说更简单呢？显然是第二种，第一种你需要告诉机器人具体怎么做，第二种你只需要说出你要想的结果。

回到我们SQL查询的主题上，假设现在给你一个文件，里面包含了100个人的姓名和性别，让你从里面查找李四的性别。数据格式如下：

在没有SQL之前，我们是用命令式编程的方式来手把手教机器完成一次查询的，如下面的代码所示：

String findGenderByName(List<Person> persons, String name) {
  for (Person person: persons) {
    if (person.getName().equals(name)) {
      return person.getGender();
    }
  }
  return null;
}

可以发现用命令式编程的方式在面对海量的查询需求时，需要编写很多的类似的代码。比如根据某个字段进行过滤是一个通用查询需求，但是如果用命令式编程的语言来写，换一个数据模型就需要重新开发类似的代码。当然聪明的程序员会想到用泛型来解决这个问题，但是针对这种非常通用的场景，有没有更好的方案呢？

答案是肯定的，那就是针对数据查询定义一门领域语言，而且是声明式的。SQL的出现使得声明式查询成为可能，让查询场景的编程门槛大大降低了。要查询李四的性别，只需要将上面的数据导入到数据库中，然后执行下面的SQL语句：

select gender from person where name = '李四';

SQL的语法相比Java等语言要简单得多， 使得复杂查询的代码编写工作量大大减少了，从上面的查询语句示例可以看到，SQL的代码量远远少于Java。此外，SQL是面向查询场景的领域语言，降低了查询数据的编程门槛，你不需要为了查询数据专门去学Java，只需要学一下SQL，即使是运营和产品也能够掌握。

Calcite的诞生

一直以来SQL都是关系型数据库的专属，后来随着NoSQL数据库的发展，大家发现关系型数据库虽然有局限，但是SQL本身是个好东西，因为SQL极大的降低了查询数据库门槛。所以很多NoSQL都开始支持SQL查询。大部分的NoSQL只支持简单的基于key的查询，而SQL的查询能力无疑是强大的，那么从KV查询到SQL查询中间的鸿沟要如何跨越呢？Calcite这个开源项目就给出了答案。Calcite是一个支持异构数据源的SQL查询框架，它只专注于SQL的查询和优化，数据引擎交给使用方自定义。也就是说任何NoSQL数据库可以只要实现了Calcite的数据源适配器，就能直接支持SQL查询。

举一个简单的例子，基于Calcite框架，我们只要实现了CSV文件的适配器，就能在CSV文件上面使用SQL来查询。这是一个Calcite的官方例子。首先引入包：

        <dependency>
            <groupId>org.apache.calcite</groupId>
            <artifactId>calcite-core</artifactId>
            <version>1.31.0</version>
        </dependency>
        <dependency>
            <groupId>org.apache.calcite</groupId>
            <artifactId>calcite-example-csv</artifactId>
            <version>1.21.0</version>
        </dependency>

下面是一个公司职员的CSV表格，Calcite提供了一个CSV的适配器，基于这个适配器可以直接在CSV文件上面支持SQL查询。下面的文件放到resource/sales的目录下面，命名为：EMPS.csv。

EMPNO:int,NAME:string,DEPTNO:int,GENDER:string,CITY:string,EMPID:int,AGE:int,SLACKER:boolean,MANAGER:boolean,JOINEDAT:date
100,"Fred",10,male,,30,25,true,false,"1996-08-03"
110,"Eric",20,"M","San Francisco",3,80,,false,"2001-01-01"
110,"John",40,"M","Vancouver",2,,false,true,"2002-05-03"
120,"Wilma",20,"F",,1,5,,true,"2005-09-07"
130,"Alice",40,"F","Vancouver",2,,false,true,"2007-01-01"

然后是CSV数据库的schema定义，这个放到resource目录下面，命名为：model.json

{
  "version": "1.0",
  "defaultSchema": "SALES",
  "schemas": [
    {
      "name": "SALES",
      "type": "custom",
      "factory": "org.apache.calcite.adapter.csv.CsvSchemaFactory",
      "operand": {
        "directory": "sales"
      }
    }
  ]
}

最后是一段测试代码：

public class CalciteTest {
    public static void main(String[] args) throws SQLException {
        String sql = "select gender from SALES.EMPS where name = 'Fred'";
        String model = "/model.json";

        Properties info = new Properties();
        info.put("model", CalciteTest.class.getResource(model).getPath());
        try (Connection connection = DriverManager.getConnection("jdbc:calcite:", info)) {
            Statement statement = connection.createStatement();
            ResultSet resultSet = statement.executeQuery(sql);

            while(resultSet.next()){
                String gender = resultSet.getString("gender");
                System.out.println(gender);
            }
        }
    }
}

可以看到只要使用了CSV文件的Calcite适配器，就可以直接把CSV文件当做关系数据库使用SQL来进行查询。

SQL查询的实现原理

那么问题来了，Calcite是怎么做到的让CSV文件也能当成关系型数据库用SQL来查询的呢？我们自己可以推演一下，要实现SQL查询功能需要做哪些事情。一个很简单的想法就是实现一个编译器，将SQL语句直接编译成机器码，就像C语言用GCC编译成机器码一样。这种实现方式难度比较高，你需要精通编译原理。如果我只会Java，那要怎么实现这个SQL查询引擎呢？可以参考Java的思路，Java也不是直接编译成机器码执行的，而是编译成字节码，然后再让字节码在JVM上面执行。那么我们也可以将SQL先编译成Java代码，然后再执行。如下图所示：

想法看起来很美好，但是怎么实现呢？Calcite这个项目给了我们答案，它将这个过程分为了三步：

1. 将SQL语句使用JavaCC解析成SQL对象。
2. 要把查询请求转化成逻辑计划。
3. 把逻辑计划进行优化，并且生成物理计划。

看到这里一下子引入了很多没听说的概念，你可能已经晕了，没关系，接下来我就按顺序逐个解释一下。

SQL解析

首先是SQL解析做了啥。既然是用Java来实现SQL查询的功能，那么肯定第一步是要对SQL查询进行建模，一切的逻辑都围绕这个SQL对象展开。如下图所示，这个就是我们例子中查询语句生成的SqlNode对象。可以看到，这个对象就是将SQL语句结构化了，对SQL的各个部分都定义了相应的对象，比如where的查询条件定义成了SqlBasicCall对象。通过将SQL语句解析成对象，我们就可以围绕这个对象编写相应的处理逻辑。

Calcite直接复用了JavaCC编译器的能力来构建SQL解析器，因为编译器是一个非常成熟的领域，没有必要重复造轮子。关于JavaCC的使用我这里就不展开了，你如果感兴趣可以去网上搜索相关的内容，这里只需要知道SQL对象的解析是使用JavaCC做到的就足够了。

逻辑计划与关系代数

有了SQL对象之后，下一步就是基于SQL对象生成逻辑计划。SQL是基于关系代数设计出来的语言，所以它需要先翻译成关系代数的逻辑结构，这个逻辑结构跟关系代数的数学形式是等价的。

下面是关系代数与SQL语法的对照表，比较大的不同就是SQL中的select在关系代数中叫project，where在关系代数中叫select。

那么关系代数有啥用呢？听到代数这个词你可能会闻到一股数学的味道，实际上关系代数就像线性代数一样属于数学领域，线性代数是研究如何高效的解决线性问题，类似的，关系代数是就研究如何高效的解决查询问题。关系代数定义了查询问题中的运算符号，如上面的表格所示，同时还有运算规律，例如连接与笛卡尔积结合律、连接与笛卡尔积交换律。通过这些运算规律，我们可以对查询操作进行等价变换，从而找到更加简单高效的解法。这里我们不上数学课，所以我只简单举一个选择操作下移的等价变换例子。

假设我们有一个SQL请求：

SELECT A.a1 FROM A，B，C WHERE A. a1 =C. a1 AND B. b1 =C. b1 AND f(c1)

翻译成关系代数

左边的关系代数指的是从A、B、C三个表做笛卡尔积之后，再执行三次条件判断，首先是f(c1)，表示对c1字段执行一个f布尔函数，然后是判断B.b1=C.b1，最后是A.a1=C.a1。

右边是经过等价变换之后的关系代数，把f(c1)的条件判断移到了C执行笛卡尔积之前，这里很容易看出来，这样查询的结果是等价的，但是查询的性能肯定是右边的更高，因为在B和C笛卡尔积之前就先对C进行过滤操作，这样能够减少笛卡尔积的数据量。

到这里你应该知道为什么要先将SQL翻译成关系代数（逻辑计划），而不是直接生成可执行的代码了。在上面的例子，如果我们直接将SQL翻译成可执行的代码，那么显然查询性能会很差，浪费了资源。如果我们先翻译成关系代数，就能利用关系代数对查询操作进行优化，从而提高查询的效率。

回到我们的例子，前面的查询性别的SQL：select gender from SALES.EMPS where name = 'Fred'被翻译成下面的逻辑计划。

• LogicalProject是选择操作，也就是选择GENDER这个字段，因为GENDER字段在CSV表中是第三个字段，所以用$3指代。
• LogicalFilter是过滤操作，比较条件为"=($1, 'Fred')"，这里$1是NAME在表中的位置。
• LogicalTableScan是扫描操作，也就是扫描EMPS表，SALES是数据库名。

逻辑计划的执行是自底向上的，整个逻辑计划翻译成大白话就是把EMPS表所有数据查询出来，然后执行过滤操作把姓名为Fred的数据记录查询出来，最后在数据记录只选择第三个字段（性别）作为结果返回。

物理计划与代码生成

有了逻辑计划之后，我们就可以基于逻辑计划进行优化并且生成物理计划了。下面是逻辑计划经过优化之后生成的物理执行计划。

可以看到，逻辑计划原来是有三个操作的，这里被优化成了两个操作：

• EnumerableCalc（可枚举计算）：这个是Calcite的计算算子，括号里面是它的逻辑语法。回顾一下我们的SQL：select gender from SALES.EMPS where name = 'Fred'

  • expr#0..9=[{inputs}]：数据表的字段分别被映射为0\~9的10个字段，这里表示输入参数的第0到9是数据表的输入字段，比如：t0表示EMPNO
  • expr#10=['Fred':VARCHAR]：这里用t10表示SQL中的'Fred'
  • expr#11=[=($t1, $t10)]：这里表示一个等于的函数表达式，指代了name = 'Fred'，t1是NAME字段，t10前面说了是Fred的字符串
  • GENDER=[$t3]：进行select（选择字段）的操作，表示输出结果中的GENDER从计算结果中的t3字段获取
  • $condition=[t11]：即where操作，这里的where条件是t11表达式，即expr#11=[=($t1, $t10)]也就是name = 'Fred'

• EnumerableTableScan（可枚举表扫描）：前面的算子是进行计算，但计算需要要输入数据，输入数据就通过这个算子来提供。

  • table=[[SALES, EMPS]]：这里表示从SALES库中的EMPS表中获取所有数据。

总结一下逻辑计划到物理计划的过程，逻辑计划是完全按照关系代数的方式来描述的，并且还没有经过优化。而物理计划是完全按照实际执行时来分配算子的。在上面的例子，逻辑计划的选择和过滤操作在物理计划中被合并成为了一个EnumerableCalc算子。

EnumerableCalc算子的设计很巧妙，可以拿CPU来类比，你可以把t1\~t11当做是寄存器，操作指令只会从寄存器中获取数据计算，并且把计算结果放回寄存器，这样就不需要像Java编程一样用变量名称来指代要操作的数据，更加灵活。

但这里有一个问题还悬而未决，那就是寄存器有了，那么操作指令从哪里来的呢？我们写SQL的时候可没有告诉计算机要怎么进行条件判断。

答案是Calcite是使用代码生成技术对每个算子都生成一段Java代码，这段代码就是对数据的操作指令。下面的代码就是前面EnumerableCalc算子对应的Java代码。

这里先简单说一下代码的逻辑：

1. 获取数据表的迭代器作为数据输入，对应了from SALES.EMPS
2. 对数据进行遍历操作
3. 获取t1的数据
4. 将t1的数据跟字符串Fred进行比较，如果相等就直接返回，如果不相等就继续循环直到找到相等数据或者遍历完数据，对应了name = 'Fred'
5. 这里是Enumerable迭代器获取当前数据的方法，可以看到它是从完整的数据行里面获取到t3（GENDER）的数据返回，对应了select gender

在了解了EnumerableCalc算子是怎么实现了之后，我们再来看一下EnumerableTableScan是怎么实现的。

EnumerableTableScan实际上被翻译成了Enumerable _inputEnumerable = Schemas.enumerable((ScannableTable) root.getRootSchema().getSubSchema("SALES").getTable("EMPS"), root)，并没有像EnumerableCalc一样生成一份代码。上面的代码实际上就是获取了ScannableTable之后将数据表封装成了Enumerable数据迭代器。Calcite提供的CSV例子中，CsvScannableTable就是实现了ScannableTable。

下面是CsvScannableTable的代码，它实现了ScannableTable的接口，主要就是Enumerable<Object[]> scan(DataContext root)方法，这个方法就是返回一个能够把CVS文件中的数据都遍历一遍的迭代器。在上面EnumerableCalc的_inputEnumerable实际获取到的就是CsvScannableTable.scan方法返回的Enumerable。

进阶用法：可过滤的数据源

到这里，基于CSV的文件SQL查询原理就讲解完毕了。你可能还有一个疑问：实际问题并不像上面例子这样数据量很小可以全表扫描返回结果，遇到数据量大的情况怎么办呢？Calcite当然也考虑到了这种情况，解决方法就是提高一个支持过滤条件的数据源接口：FilterableTable，FilterableTable的方法是：Enumerable<@Nullable Object[]> scan(DataContext root, List<RexNode> filters);，相比ScannableTable的方法多了一个filters的字段。filters是Calcite通过解析SQL得到的查询条件，一般来说NoSQL数据库至少也会支持基于Key的索引查询，你可以使用filters在真实数据源上进行过滤之后再返回，这样可以大大减少返回给Calcite的数据量。

下面我们来看一下当CSV文件实现了FilterableTable接口之后的查询过程，在model.json文件中新增："flavor": "FILTERABLE"，表示对CSV文件使用支持FilterableTable的数据源实现。

{
  "version": "1.0",
  "defaultSchema": "SALES",
  "schemas": [
    {
      "name": "SALES",
      "type": "custom",
      "factory": "org.apache.calcite.adapter.csv.CsvSchemaFactory",
      "operand": {
        "directory": "sales",
        "flavor": "FILTERABLE"
      }
    }
  ]
}

然后执行同样的代码，看看生成的逻辑计划和物理计划有没有变化。

从上面的图片可以看到，逻辑计划跟之前相比没有变化，而物理计划则有很大的变化。

首先是EnumerableCalc的入参少了条件判断，然后EnumerableTableScan变成EnumerableInterpreter和BindableTableScan。

EnumerableCalc的变化是因为我们提供了支持条件过滤的数据源，所以在逻辑计划优化成物理计划的时候，Calcite的优化器使用了关系代数中的谓词下推，即将查询条件下放到TableScan的时候，这个逻辑也很好理解：比起全表扫描然后在内存中过滤，使用谓词下推将查询条件放到扫描数据阶段，可以使得返回的数据量减少从而提升查询效率。因此EnumerableCalc的条件过滤逻辑被下放到了BindableTableScan阶段。

EnumerableTableScan的变化是因为谓词下推的优化时查询条件的入参是动态变化，没有全表扫描那么简单，EnumerableCalc代码生成的时候不能直接写死，需要通过EnumerableInterpreter解释器进行解释执行来获取BindableTableScan的内容。看一下生成的代码会比较直观：

可以看到，这次EnumerableCalc生成的代码里面获取Enumerable数据迭代器的方式是：Enumerator inputEnumerator = interpreter.enumerator();，而不是像之前一样：Enumerable _inputEnumerable = Schemas.enumerable((ScannableTable) root.getRootSchema().getSubSchema("SALES").getTable("EMPS"), root); 。原因很好理解：全表扫描的写法是固定的，不需要额外入参，所以可以直接写死用Schemas.enumerable来获取，而谓词下推后的数据查询则每次SQL的入参都可能变化，所以要interpreter解释器来执行，这样入参怎么变化都不会影响EnumerableCalc的代码生成方式。

总结

SQL查询引擎的实现本质上是实现SQL语言的编译器，Calcite将SQL解析成语法树，然后转成逻辑计划，经过优化器优化之后转成物理计划，最后是生成Java代码来执行。这个过程就类似于将C语言编译成机器码，GCC编译器在编译过程中先是将C代码进行语法分析生成语法树，然后生成汇编语言，最后进行优化之后才生成机器码。