从sqlite3看SQL编译

在学习 sql 语句的“编译”、“预编译”相关知识时，我发现互联网上的相关资料是比较匮乏的。本文在 sqlite3 的背景下，简要地介绍 sql 语句的编译与预编译在一个数据库引擎中究竟是如何发生的。

什么是编译和预编译

SQL 是结构化查询语言（Structed Query Language）的简称，它是一种用于处理各种数据库技术的非过程化语言。但是较为特殊的是，SQL 语句只定义了必要的输入和输出参数，但是没有定义任何过程，因此并不能够单独执行，而是需要依赖具体的数据库引擎来处理。由于 SQL 语言是比较复杂的，大多数数据库引擎会将 SQL 语句转换为执行过程依赖于当前数据库的状态的可执行文件或机器码；这个过程就叫做 SQL 的编译。

有时候多个 SQL 语句的结构可能类似，只是某些过滤条件不同，例如SELECT col FROM table WHERE col > 1和SELECT col FROM table WHERE col > 2语句，此时可以先将 col_val 使用占位符 ? 替代传入数据库，得到语句SELECT col FROM table WHERE col > ?进行编译，然后再将 col_val 作为输入参数执行编译文件；这个过程叫做 SQL 的预编译。

可以将编译和预编译过程理解为生成了依赖于数据库引擎运行的函数，其中编译的结果是一个无输入参数的函数，而预编译结果是一个含有输入参数的函数：

// SQL compile result
void ** sql_exec(){

    operation1_rely_on_database_API();
    operation2_rely_on_database_API();
    ...
    return 查询结果;
}

// SQL precompile result
void ** sql_exec(void *placeholders...){

    operation1_rely_on_database_API(placeholders...);
    operation2_rely_on_database_API(placeholders...);
    ...
    return 查询结果;
}

SQL 语句经过预编译后会在数据库引擎中缓存，为了表示区分，将已经完成预编译的 SQL 语句称为 statement。通常一个 statement 只对应一条 SQL 语句，并且不同的 statement 之间并不会共享编译结果：如果两个用户使用不同 statement 完成同一条查询语句，这个语句可能会被编译两次。

sqlite3 编译过程

根据 sqlite3 的官方文档说明：

sqlite3_exec() → A wrapper function that does sqlite3_prepare(), sqlite3_step(), sqlite3_column(), and sqlite3_finalize() for a string of one or more SQL statements.

sqlite3 中不存在单独的 SQL 编译接口，它是依赖于预编译的；sqlite3 中的预编译流程如下：

sqlite3 的预编译接口为sqlite3_prepare()，它会根据输入的 SQL 语句返回一个sqlite3_stmt*指针，该指针实际上会指向一个Vdbe对象，该对象实质上是一段可执行代码。sqlite3 中所有的sqlite3_prepare_XX()函数都是接口函数，会对 SQL 进行一些预处理、加锁后调用函数sqlite3Prepare，将代码简化后，函数的主要逻辑为：

static int sqlite3Prepare(
    sqlite3 *db,              /* Database handle. */
    const char *zSql,         /* UTF-8 encoded SQL statement. */
    int nBytes,               /* Length of zSql in bytes. */
    u32 prepFlags,            /* Zero or more SQLITE_PREPARE_* flags */
    Vdbe *pReprepare,         /* VM being reprepared */
    sqlite3_stmt **ppStmt,    /* OUT: A pointer to the prepared statement */
    const char **pzTail       /* OUT: End of parsed string */
){
    int rc = SQLITE_OK;       /* Result code */
    int i;                    /* Loop counter */
    Parse sParse;             /* Parsing context */

    // 分配内存等预处理工作，db 加锁是在上一层函数中进行的
    ...

    // 尝试对 schema 加锁，如果不成功则释放并返回
    if( !db->noSharedCache ){
        for(i=0; i<db->nDb; i++) {

            ...

            // 如果加锁失败，退出
            if( failed )
                goto end_prepare;
        }
    }

    ...

    // 如果没有指定长度，获取 SQL 长度后进行解析阶段
    if( nBytes>=0 && (nBytes==0 || zSql[nBytes-1]!=0) ){
        
        ...
            
        if( failed )
            goto end_prepare;
        else 
            sqlite3RunParser(&sParse, zSql);

    }else{
        sqlite3RunParser(&sParse, zSql);
    }
    assert( 0==sParse.nQueryLoop );

    // 检查错误以及善后工作
    ...
    
    if( sParse.rc!=SQLITE_OK && sParse.rc!=SQLITE_DONE ){
        // 如果解析失败，进行清理工作
        ...
    }else{
        // 解析成功，将结果绑定到 stmt 
        *ppStmt = (sqlite3_stmt*)sParse.pVdbe;
        rc = SQLITE_OK;
        sqlite3ErrorClear(db);
    }

    // 清理分配的内存空间
    while( sParse.pTriggerPrg ){
        TriggerPrg *pT = sParse.pTriggerPrg;
        sParse.pTriggerPrg = pT->pNext;
        sqlite3DbFree(db, pT);
    }

end_prepare:
    // 清理分配的内存空间
    sqlite3ParseObjectReset(&sParse);
    return rc;
}

可以看到，该函数首先检查是否能够对全部 schema 加锁，以判断当前是否有未完成的写操作；第二步则是调用sqlite3RunParser函数来获取 SQL 语句的解析结果，最后再将解析结果中的Vdbe绑定到用户输入的sqlite3_stmt指针上。由于sqlite3.h头文件中不包含sqlite3_stmt的定义，自然而然地隐藏了内部实现，这是一种零成本抽象。

在sqlite3RunParser()函数中，主要是以状态机的形式对 SQL 语句进行语义分析，即while(1)中的处理逻辑，代码部分进行了删改：

/*
** Run the parser on the given SQL string.
*/
int sqlite3RunParser(Parse *pParse, const char *zSql){
  int nErr = 0;                   /* Number of errors encountered */
  void *pEngine;                  /* The LEMON-generated LALR(1) parser */
  int n = 0;                      /* Length of the next token token */
  int tokenType;                  /* type of the next token */
  int lastTokenParsed = -1;       /* type of the previous token */
  sqlite3 *db = pParse->db;       /* The database connection */
  int mxSqlLen;                   /* Max length of an SQL string */
  Parse *pParentParse = 0;        /* Outer parse context, if any */
#ifdef sqlite3Parser_ENGINEALWAYSONSTACK
  yyParser sEngine;    /* Space to hold the Lemon-generated Parser object */
#endif
  VVA_ONLY( u8 startedWithOom = db->mallocFailed );

  assert( zSql!=0 );
  mxSqlLen = db->aLimit[SQLITE_LIMIT_SQL_LENGTH];
  if( db->nVdbeActive==0 ){
    AtomicStore(&db->u1.isInterrupted, 0);
  }
  pParse->rc = SQLITE_OK;
  pParse->zTail = zSql;

  // 分配内存
  pEngine = sqlite3ParserAlloc(sqlite3Malloc, pParse);
  if( pEngine==0 ){
    sqlite3OomFault(db);
    return SQLITE_NOMEM_BKPT;
  }

  assert( pParse->pNewTable==0 );
  assert( pParse->pNewTrigger==0 );
  assert( pParse->nVar==0 );
  assert( pParse->pVList==0 );
  pParentParse = db->pParse;
  db->pParse = pParse;
    
  // 主要的解析逻辑，利用状态机来进行语义分析
  while( 1 ){
    n = sqlite3GetToken((u8*)zSql, &tokenType);
    mxSqlLen -= n;
    if( mxSqlLen<0 ){
      pParse->rc = SQLITE_TOOBIG;
      pParse->nErr++;
      break;
    }
#ifndef SQLITE_OMIT_WINDOWFUNC
    if( tokenType>=TK_WINDOW ){
      assert( tokenType==TK_SPACE || tokenType==TK_OVER || tokenType==TK_FILTER
           || tokenType==TK_ILLEGAL || tokenType==TK_WINDOW 
      );
#else
    if( tokenType>=TK_SPACE ){
      assert( tokenType==TK_SPACE || tokenType==TK_ILLEGAL );
#endif /* SQLITE_OMIT_WINDOWFUNC */
      if( AtomicLoad(&db->u1.isInterrupted) ){
        pParse->rc = SQLITE_INTERRUPT;
        pParse->nErr++;
        break;
      }
      if( tokenType==TK_SPACE ){
        zSql += n;
        continue;
      }
      if( zSql[0]==0 ){
        /* Upon reaching the end of input, call the parser two more times
        ** with tokens TK_SEMI and 0, in that order. */
        if( lastTokenParsed==TK_SEMI ){
          tokenType = 0;
        }else if( lastTokenParsed==0 ){
          break;
        }else{
          tokenType = TK_SEMI;
        }
        n = 0;
#ifndef SQLITE_OMIT_WINDOWFUNC
      }else if( tokenType==TK_WINDOW ){
        assert( n==6 );
        tokenType = analyzeWindowKeyword((const u8*)&zSql[6]);
      }else if( tokenType==TK_OVER ){
        assert( n==4 );
        tokenType = analyzeOverKeyword((const u8*)&zSql[4], lastTokenParsed);
      }else if( tokenType==TK_FILTER ){
        assert( n==6 );
        tokenType = analyzeFilterKeyword((const u8*)&zSql[6], lastTokenParsed);
#endif /* SQLITE_OMIT_WINDOWFUNC */
      }else{
        Token x;
        x.z = zSql;
        x.n = n;
        sqlite3ErrorMsg(pParse, "unrecognized token: \"%T\"", &x);
        break;
      }
    }
    pParse->sLastToken.z = zSql;
    pParse->sLastToken.n = n;
    // 调用 Lemon 组件生成编译结果
    sqlite3Parser(pEngine, tokenType, pParse->sLastToken);
    lastTokenParsed = tokenType;
    zSql += n;
    assert( db->mallocFailed==0 || pParse->rc!=SQLITE_OK || startedWithOom );
    if( pParse->rc!=SQLITE_OK ) break;
  }
  assert( nErr==0 );

  // 清理中间量
  sqlite3ParserFree(pEngine, sqlite3_free);

  // 清理分配的内存
  if( db->mallocFailed ){
    pParse->rc = SQLITE_NOMEM_BKPT;
  }
  if( pParse->zErrMsg || (pParse->rc!=SQLITE_OK && pParse->rc!=SQLITE_DONE) ){
    if( pParse->zErrMsg==0 ){
      pParse->zErrMsg = sqlite3MPrintf(db, "%s", sqlite3ErrStr(pParse->rc));
    }
    sqlite3_log(pParse->rc, "%s in \"%s\"", pParse->zErrMsg, pParse->zTail);
    nErr++;
  }
  pParse->zTail = zSql;

  if( pParse->pNewTable && !IN_SPECIAL_PARSE ){
    /* If the pParse->declareVtab flag is set, do not delete any table 
    ** structure built up in pParse->pNewTable. The calling code (see vtab.c)
    ** will take responsibility for freeing the Table structure.
    */
    sqlite3DeleteTable(db, pParse->pNewTable);
  }
  if( pParse->pNewTrigger && !IN_RENAME_OBJECT ){
    sqlite3DeleteTrigger(db, pParse->pNewTrigger);
  }
  if( pParse->pVList ) sqlite3DbNNFreeNN(db, pParse->pVList);
  db->pParse = pParentParse;
  assert( nErr==0 || pParse->rc!=SQLITE_OK );
  return nErr;
}

从源码中可以看到，sqlite3 中的语义分析与 SQL 编译实际上是混合在一起的，而不是完成语义分析后再生成可执行代码。在sqlite3Parser函数中，Lemon 解析器会使用 sqlite 中的 code generator 来生成具体的执行计划。Code generator 并不是一个具体的数据结构，而是一系列函数接口，分别对应着不同的功能；这有点类似于深度学习网络中的每一个层级。这些代码生成器分布在不同的文件中，如select.c、where.c 等。Lemon Parser 最终会将这些函数接口组装起来，并进行优化，最终生成一个Vdbe对象。

Vdbe对象是一条 SQL 语句经过 sqlite3 编译后的产物。它是一个虚拟机，其中的程序运行在一个虚拟环境之中，类似于 redis 中的 lua 环境。Vdbe中的程序会直接与数据库中的 B+ 树进行交互，执行事务操作。