查询优化

本章讨论的源代码可以在 KQuery 项目的 optimizer 模块中找到。

我们现在有了实用的查询计划，但需要依靠终端用户以有效的方式构建计划。例如，我们希望用户在构建计划时尽可能早地进行过滤，特别是在连接之前，因为这减少了需要处理的数据量。

这是实现一个简单的基于规则的查询优化器的好时机，它可以重新安排查询计划，使其更有效率。

我们在第十一章开始支持 SQL 之后，这将变得更加重要，因为 SQL 语言只定义了查询的工作方式，不允许用户指定运算符和表达式的求值顺序。

基于规则的优化

基于规则的优化是一种简单而实用的方法，可以将常识性的优化应用到查询计划中。这些优化是在创建物理计划之前针对逻辑计划执行的。

这些优化工作是通过使用访问者模式遍历逻辑计划，并在计划中的每一步创建一个副本，并应用任何必要的修改。这种设计比在遍历计划时试图改变状态要简单得多，而且与期望不可变状态的函数式编程风格很一致。

我们将使用以下接口来表示优化器规则。

interface OptimizerRule {
  fun optimize(plan: LogicalPlan) : LogicalPlan
}

投影下推

投影下推规则的目标是在从磁盘读取数据后，在查询执行的其他阶段之前尽快过滤掉列，以减少处理的数据量。

为了知道在查询中引用了哪些列，我们必须编写递归代码来检查表达式，并在累加器中建立一个列的列表。

fun extractColumns(expr: List<LogicalExpr>, 
                   input: LogicalPlan, 
                   accum: MutableSet<String>) {
    
  expr.forEach { extractColumns(it, input, accum) }
}

fun extractColumns(expr: LogicalExpr, 
                   input: LogicalPlan, 
                   accum: MutableSet<String>) {
    
  when (expr) {
    is ColumnIndex -> accum.add(input.schema().fields[expr.i].name)
    is Column -> accum.add(expr.name)
    is BinaryExpr -> {
       extractColumns(expr.l, input, accum)
       extractColumns(expr.r, input, accum)
    }
    is Alias -> extractColumns(expr.expr, input, accum)
    is CastExpr -> extractColumns(expr.expr, input, accum)
    is LiteralString -> {}
    is LiteralLong -> {}
    is LiteralDouble -> {}
    else -> throw IllegalStateException(
        "extractColumns does not support expression: $expr")
  }
}

有了这个实用的代码，我们就可以继续执行优化器规则了。请注意，对于投影、选择和聚合计划，我们正在建立列名列表，但是当我们到达扫描（这是一个叶子节点）时，我们用一个有列名列表的扫描版本来替换它。

class ProjectionPushDownRule : OptimizerRule {

  override fun optimize(plan: LogicalPlan): LogicalPlan {
    return pushDown(plan, mutableSetOf())
  }

  private fun pushDown(plan: LogicalPlan,
                       columnNames: MutableSet<String>): LogicalPlan {
    return when (plan) {
      is Projection -> {
        extractColumns(plan.expr, columnNames)
        val input = pushDown(plan.input, columnNames)
        Projection(input, plan.expr)
      }
      is Selection -> {
        extractColumns(plan.expr, columnNames)
        val input = pushDown(plan.input, columnNames)
        Selection(input, plan.expr)
      }
      is Aggregate -> {
        extractColumns(plan.groupExpr, columnNames)
        extractColumns(plan.aggregateExpr.map { it.inputExpr() }, columnNames)
        val input = pushDown(plan.input, columnNames)
        Aggregate(input, plan.groupExpr, plan.aggregateExpr)
      }
      is Scan -> Scan(plan.name, plan.dataSource, columnNames.toList().sorted())
      else -> throw new UnsupportedOperationException()
    }
  }

}

给出一个输入的逻辑计划：

Projection: #id, #first_name, #last_name
  Filter: #state = 'CO'
    Scan: employee; projection=None

这个优化器规则会把它转化为以下计划。

Projection: #id, #first_name, #last_name
  Filter: #state = 'CO'
    Scan: employee; projection=[first_name, id, last_name, state]

谓词下推

谓词下推优化的目的是在查询中尽可能早地过滤掉行，以避免重复处理。请看下面的例子，它连接了一个雇员表和部门表，然后过滤掉科罗拉多州的雇员。

Projection: #dept_name, #first_name, #last_name
  Filter: #state = 'CO'
    Join: #employee.dept_id = #dept.id
      Scan: employee; projection=[first_name, id, last_name, state]
      Scan: dept; projection=[id, dept_name]

这个查询将产生正确的结果，但是会有对所有雇员执行连接的开销，而不仅仅是那些在科罗拉多州的雇员。谓词下推规则将把过滤器下推到连接中，如下面的查询计划所示。

Projection: #dept_name, #first_name, #last_name
  Join: #employee.dept_id = #dept.id
    Filter: #state = 'CO'
      Scan: employee; projection=[first_name, id, last_name, state]
    Scan: dept; projection=[id, dept_name]

现在，连接将只处理雇员的子集，从而产生更好的性能。

基于成本的优化

基于成本的优化是指使用关于基础数据的统计数据来确定执行一个特定查询的成本，然后通过寻找一个低成本的执行计划来选择一个最佳执行计划。一个很好的例子是，根据被连接的表的大小来选择使用哪种连接算法。

基于成本的优化超出了本书的范围，尽管这个主题可能会被包括在未来的版本中。建议你看看 Apache Calcite 项目，以了解更多关于这个主题的信息。

本书的电子版、MOBI和PDF格式也可从 https://leanpub.com/how-query-engines-work 购买。

Copyright © 2020-2022 Grove Enterprises, LLC。保留所有权利。