Why SQLite Uses Bytecode

Quote from the article:

"The bytecode generated by SQLite is usually smaller than the corresponding AST coming out of the parser. During initial processing of SQL text (during the call to sqlite3_prepare() and similar) both the AST and the bytecode exist in memory at the same time and so more memory is used then. But that is a transient state. The AST is quickly discarded and its memory recycled [...]"

There are three approaches:

1. interpreted code

2. compiled then interpreted bytecode

3. compiled machine code

The further up, the simpler.

The further down, the faster.

Which is why JavaScript engines (and JIT compilers for other languages) are typically designed to:

1. start interpreting the code once it has been parsed, and start jitting a function being called;

2. generate naive bytecode for the function that generates native code equivalents of the run actions of the AST (including some fast-path code for simple cases such as adding two 32-bit integers, and falling back to function calls to perform the add on more complex types);

3. generate more optimal code for sequences of instructions in the background, such as entire for/while loops, then patch in calls to those fast-path versions when ready.

That way you can start running the code immediately after parsing it, and can switch to the faster versions when they are ready if the code takes longer to run in the slower version.

Converting a SELECT to a PRPEPARE does not really require parsing the complete query—or even it it did, some small concessions for this could be implemented in the line protocol to enable the server to do the prepared statement out of client query.

I don't believe *any* SQL client library actually tries to parse e.g. PostgreSQL itself at any point of processing. You can read what the PostgreSQL protocol does here: https://www.postgresql.org/docs/current/protocol-flow.html#P...

How you go from source to target code without an AST is that the syntax-directed translation step in your implementation (that which would build the AST) doesn't bother with that and just builds the output code instead. The extra traversal is skipped; replaced by the original parser's traversal of the raw syntax.

E.g. pseudo-Yacc rules for compiling the while loop in a C-like notation.

  while_loop : WHILE '(' expr ')' statement
               {
                   let back = get_label();
                   let fwd = get_label();
                   let expr = $3; // code for expr recursively generated
                   let stmt = $5; // code for statement, recursively generated
                   $$ = make_code(stmt.reg(),
                                  `$back:\n`
                                  `${expr.code()}\n`
                                  `BF ${expr.reg}, $fwd\n`  // branch if false
                                  `${stmt.code()}\n`
                                  `JMP $back\n`
                                  `$fwd:\n`)                                
               }
               ;

Every code fragment coming out of a rule has .code() and .reg(): the generated code, which is just a string, and the output register where it leaves its value. Such representational details are decided by the compiler writer.

The while statement produces no value, so we just borrow the statement's .reg() as a dummy in the call to make_code; our rule is that every code fragment has an output register, whether it produces a value or not.

When the LALR(1) parser reduces this while loop rule to the while_loop grammar symbol, the expr and statements have already been processed; so the rule action has ready access to the code objects for them. We just synthesize a new code object. We grab a pair of labels that we need for the forward and back jump.

I'm assuming we have a vaguely JS-like programming language being used for the grammar rule actions, in which we have template strings with interpolation, and adjacent strings get merged into one. The bytecode assembly is line oriented, so we have \n breaks.

One possible kind of expression is a simple integer constant, INTEGER:

  expr : INTEGER 
         {
           let reg = allocate_reg();
           let val = $1
           $$ = make_code(reg,
                          `LOAD $reg, #$val\n`)
         }

One possible statement is an empty statement dented by empty curly braces:

  statement : '{' '}'
              {
                $$ = make_code(R0,  // dedicated zero register
                               ""); // no-code solution
              }

So then when we have while (1) { } we might get R1 allocated in the expr rule, like this:

  LOAD R1, #1\n   ; output register is R1

then in the while loop, things get put together like this:

  L0:\n           ; back label
  LOAD R1, #1\n   ; code for expr
  BF R1, L1\n     ; branch if false to L1
                  ; no code came from empty statement
  JMP L0          ; back branch
  L1:\n           ; fwd label