Compiled queries in Scala

Why resort to the complexities of dynamic code generation and compilation at runtime?

Speed.

To demonstrate, lets build an interpreter that runs projection and filtering on a simulated database, then build a compiled version and look at some performance numbers.

This is our goal: compile a data structure representing a query into native code to speed up a query loop. We'll look at two specific code-generation tools to achieve our goal: ASM and Scala Quasiquotes.

ASM has been used by Java developers for years for all sorts of codegen purposes. It's is very fast and has low-memory requirements, but it's also very low-level, making it time-consuming and tedious to use and very difficult to debug.

Quasiquotes are a new Scala tool for code generation. They are similar to macros, except they can be used at runtime whereas macros are compile-time only. They're much higher-level than ASM, so we'll compare benchmarks against the two to see what cost these high-levelel semantics incur, if any.

A query system

First let's define our "database" consisting of a single dataset, represented as a simple in-memory data structure using tuples as rows.

Next, we need structures that hold:

1. fields to be projected
2. filter expression tree

An efficient representation of projection fields is simply storing the ordinals. For example, this is how we'd represent a projection of the name and dissertation columns:

The filter expression is a little more complicated, since it's treeish in nature. Even though we're not supporting SQL, let's use it to help understand:

A tree is a natural way to represent this syntax in abstract form:

In Scala, we can represent this with a Scalaz Tree[String].

The root node of each tree or subtree is always an operator. The sub-forests are the operands, which may be made up of operator trees.

Using this we can build a filter interpreter that evaluates whether a row should be included. Some caveats about limitations of this simple example:

• We'll run filtering before projection. In reality, which to run first is a decision that should be made by a query optimizer.
• I'm only going to implement a few of the most common operators.
• The filter interpreter is doing its own projection, which may overlap with the projected fields requested by the user and create duplicate work.
• I'm only supporting Int for comparison, and I'm doing some nasty type casting. IRL, we'd keep better track of the types with a full blown schema.

These are all issues I won't address.

Here's our limited set of operators:

And the interpreter itself:

And finally, a simple query loop:

NB: we could use ScalaBlitz to optimize that flatMap if this was real and we were ultra-concerned about performance.

Notice how we return Seq[Seq[Any]]. At compile-time we don't know how to typefully represent a row so we have to resort to the lowest-common type, Any. This is another issue that we'll fixup later in the compiled version.

With all this in place, let's run it:

So far so good. Next up, let's dive into some bytecodes to gain a basic understanding of what's going on when we generate code on the JVM.

Bytecode primer

Let's start by looking at the bytecode for a minimum viable Scala class:

Compile it with scalac then view the bytecode with java -c:

From the Java bytecode instructions listings reference we can find out the meaning of these bytecode instructions:

• aload_0 — load a reference onto the stack from local variable 0 (local var 0 is always this)
• invokespecial — invoke instance method on object objectref (this would be the object that we just loaded onto the stack) and puts the result on the stack (might be void)
• return — return void from method

This is the generated constructor for Foo. Since nothing else is going on, it simply returns void after calling the constructor. Now what if we actually do something, like instantiate a Foo?

Compiling this yields a single Foo.class identical to the one above along with two class files: RunFoo.class and RunFoo$.class.

The JVM runs these opcodes in a stack machine: values are pushed on to the stack then used as operands to later operations. For example, this is how you could add two constants:

1. Push 28 onto the stack with bipush
2. Push 14 onto the stack with bipush
3. Execute iadd which adds two ints: it pops two values off the stack to use as its operands: first 14, then 28. It adds those two operands and pushes the result, 28, onto the stack.

At this point we could work with the new 42 value on the stack. This is how we would check that the value is indeed 42:

1. Push the value 42 onto the stack
2. Use if_icmpne to compare two values from the stack. If they are not equal, jump to position 28, which pushes constant #4 onto the stack using ldc. If they are equal, the next code is executed, which instead pushes constant #3 onto the stack, then jumps to position 32.

Tedious, but simple.

This primer is only intended to wet your feet. If you want to learn more about bytecode, see the Further reading section at the end of this post.

ASM

ASM is a bytecode manipulation framework. It's one of several options for manipulating bytecode, but I chose it because it's one of the most mature, requires the least amount of memory, and it's very fast. The downside is it's also quite low level. If you aren't super-concerned with performance, you should check out other options, like Javassist, which is much easier to work with.

Now, to use ASM, the more familiar you are with bytecode the better off you'll be, but for newbs like us, there is ASMifier, which takes a compiled class and generates the ASM code for it. I'm going to avoid Scala for this excercise, since Java maps more closely to bytecode, and we can use the resulting bytecode from Scala either way. I want to use Tuples to represent fully typed rows, so let's see what the ASM code looks like for this Java class:

Compile it, making sure the scala-lib jar is on your classpath:

Then use the ASMifier on the classfile:

Here is the generated ASM code, heavily annotated with comments. It's a little tedious to work through, but if you really want to understand bytecode and ASM, I encourage you to read the comments and work through every line until it's internalized and you feel comfortable with it.

Not too bad. ASMifier helpfully wraps each logical chunk in blocks. The first block creates the tup field. The second block is our public constructor. It calls super, which invokes the constructor on the java.lang.Object superclass, then initializes the tup field, and finally returns void. The third block is the getTup getter.

NB: If you're having trouble following this, I recommend generating some ASM code with ASMifier, then annotating it yourself. It really helps to internalize the JVM bytecodes and how to work on a stack machine.

Inside a method, the parameters can be referenced by corresponding local variable indices. For example:

In this case, x is available at 1 and y is available at 2. To load and use these, we would use visitVarInsn which visits a local variable instruction. Using ASM, this is how we'd add x and y and store the result in local variable 3:

When you generate ASM using ASMifier it can generate all the labels and local var mappings, which is necessary information for debuggers to show you the correct names of the local variables in a given stack, since in the JVM indices are used instead of names. When writing by hand, you could opt to not write these instructions, or add them later if you need them.

Compiled queries with ASM

Let's use this knowledge to compile the query we originally interpreted. To start, let's write a fast but static version of the query so we can quickly figure out which parts need to be made dynamic. When using ASM it's a good idea to distil the essense of which part needs to be made dynamic so the generator code ends up being as small as possible. Since ASM is hard to read, write, and debug, this is very important.

Let's perform the same projection and filtering we used before, but this time without the interpretation.

This should be much faster than our interpreted query because it's running a simple conditional instead of walking and evaluating a FilterExpr on every row.

Let's construct a quick benchmark using ScalaMeter to verify our assumptions.

Results from the last result of each measurement:

• StaticQuery: 1.329709ms
• InterpretedQuery: 6.949921ms

The static query is between 5 and 6 times faster than interpreting.

Let's rewrite StaticQuery in Java and use it as a template for compiling queries. There are at least two reasons why I significantly dislike running ASMifier against Scala classes:

1. It generates a gnarly blob of unreadable bytes for the ScalaSignature (which is apparently used to store Scala-specific bits in class files and is required for reflection and for compiling against).
2. Scala objects and methods get split into separate class files when they're compiled, making it hard to stitch together the results with multiple ASMifier runs.

It's not pretty, but it works, and it happens to be even faster than the static Scala query. We'll start by feeding it to ASMifier, convert the output to Scala, then work on making the result dynamic. Converted output, heavily annotated:

Since we're using ClassWriter.COMPUTE_FRAMES I was able to remove all the visitFrame calls that ASMifier generated. I also deleted the generated FieldVisitor and AnnotationVisitor as they were both unused. I used 0 for all arguments to visitMaxs as COMPUTE_FRAMES implies COMPUTE_MAXS, which still requires calls to visitMaxs but ignores the arguments.

Scala Quasiquotes

This part of the post is not yet written. The intent was to explore Scala Quasiquotes facilities for codegen.

• Quasiquotes.
• Generative Programming Basics
• Introduction to code generation with scalameta

Next steps

An interesting direction to take this, now that we have a foundation for dynamically compiling queries, would be to add a SQL interface. Apache Calcite is well-suited to do just that.

Further reading

• Java bytecode instruction listings (Wikipedia - useful reference)
• Secrets of the Bytecode Ninjas (InfoQ)
• Hacking Java Bytecode for Programmers (part 1 of a 4 part series)
• java-bytecode-asm tag on StackOverflow
• JVM Internals (blog post)
• 3 approaches to Scala code generation