How do databases execute expressions?

Databases are enjoyable. They sit on the confluence of Pc
Science subjects which may in any other case not appear sensible in life as a
developer. For instance, each database with a question language can also be a
programming language implementation of some caliber. That does not
embrace all databases although in fact; see: RocksDB, FoundationDB,
TigerBeetle, and so on.

This put up appears at how varied databases execute expressions of their
question language.

tldr; Most surveyed databases use a tree-walking interpreter. A number of
use stack- or register-based digital machines. A pair have
just-in-time compilers. And, tangentially, a couple of do vectorized
interpretation.

All through this put up I am going to use “digital machine” as a shorthand for
stack- or register-based loops that course of a linearized
set of directions. I say this since it’s generally truthful to name a
tree-walking interpreter a digital machine. However that’s not what I
imply after I say digital machine on this put up.

Stepping again

Programming languages are sometimes carried out by turning an
Summary Syntax Tree (AST) right into a linear set of directions
for a digital machine (e.g. CPython, Java, C#) or native code
(e.g. GCC’s C compiler, Go, Rust). A number of the former implementations
additionally generate and run Simply-In-Time (JIT) compiled native code
(e.g. Java and C#).

Much less generally nowadays in programming languages does the
implementation interpret off the AST or another tree-like
intermediate illustration. This type is usually referred to as
tree-walking.

Shell languages generally do tree-walking. In any other case, implementations
that interpret instantly off of a tree usually accomplish that as a short-term
measure earlier than switching to compiled digital machine code or JIT-ed
native code (e.g. some JavaScript implementations, GraalVM, RPython,
and so on.)

That’s, whereas some main programming language implementations began
out with tree-walking interpreters, they largely moved away from solely
tree-walking over a decade in the past. See JSC in
2008, Ruby
in 2007, and so on.

My instinct is that tree-walking takes up extra reminiscence and is much less
cache-friendly than the linear directions you give to a digital
machine or to your CPU. There are some folks who
disagree,
however they largely discuss tree-walking while you’ve additionally obtained a JIT
compiler connected. Which is not fairly the identical factor. There has additionally
been some early exploration and
improvements
reported when tree-walking with a tree organized as an array.

And databases?

Databases usually interpret instantly off a tree. (It is not, typically
talking, truthful to say they’re AST-walking interpreters as a result of
databases sometimes remodel and optimize past simply an AST as
parsed from consumer code.)

However not all databases interpret a tree. Some have a digital
machine. And a few generate and run JIT-ed native code.

Methodology

If a core operate (within the question execution path that does one thing
like arithmetic or comparability) returns a price, that is an indication it is a
tree-walking interpreter. Or, in case you see code that’s evaluating its
arguments throughout execution, that is additionally an indication of a tree-walking
interpreter.

Then again, if the operate mutates inner state resembling by
assigning a price to a context or pushing to a stack, that is an indication
it is a stack- or register-based digital machine. If a operate pulls
its arguments from reminiscence and does not consider the arguments, that is
additionally a sign it is a stack- or register-based digital machine.

This strategy can lead to false-positives relying on the
structure of the interpreter. Person-defined features (UDFs) would
most likely settle for evaluated arguments and return a price no matter
how the interpreter is carried out. So it is essential to search out not simply
features that could possibly be carried out like UDFs, however core builtin
conduct. Management stream implementations of features like if or
case might be nice locations to look.

And tactically, I clone the supply code and run stuff like git grep
-i eval | grep -v take a look at | grep .java | grep -i eval or git grep -i
expr | grep -v take a look at | grep .go | grep -i expr till I persuade
myself I am someplace attention-grabbing.

Notice: In speaking a couple of broad swath of tasks, possibly I’ve
misunderstood one or some. In the event you’ve obtained a correction, let me know! If
there is a proprietary database you’re employed on the place you may hyperlink to the
(publicly described) execution technique, be happy to move it alongside!
Or if I am lacking your public-source database on this record, ship me a
message!

Survey

Cockroach (Ruling: Tree Walker)

Judging by features like func (e *evaluator)
EvalBinaryExpr
that evaluates the left-hand
side
after which evaluates the right-hand
side
and returns a price, Cockroach appears like a tree strolling interpreter.

It will get a bit extra attention-grabbing although, since Cockroach additionally
supports
vectorized expression execution. Vectorizing is a elaborate time period for
appearing on many items of information without delay quite than one after the other. It
does not essentially suggest SIMD. Right here is an instance of a vectorized
addition
of two int64 columns.

ClickHouse (Ruling: ? + JIT)

The ClickHouse structure is a bit distinctive and troublesome for me to
learn by way of – seemingly as a consequence of it being pretty mature, with severe
optimization. However they have an inclination to doc their header information effectively. So
information like
src/Functions/IFunction.h
and
src/Interpreters/ExpressionActions.h
had been useful.

They’ve additionally spoken publicly about their pipeline execution mannequin;
e.g. this
presentation
and this roadmap
issue. However it
is not utterly clear how a lot pipeline execution (which is broader
than simply expression analysis) connects to expression analysis.

Furthermore, they’ve publicly
spoken
about their assist for JIT compilation for question execution. However how
execution works when the JIT is just not enabled continues to be unclear to me
after some time of digging.

For instance, If we check out how if is
implemented,
we all know that the then and else rows have to be conditionally
evaluated. We are able to see the place the vector result’s being constructed up such
as
here.

Nevertheless, I am unable to actually see something apparent there that exhibits that
cell being inserted into the end result column as being evaluated. In a
stack- or register-based digital machine, it would not be apparent that
analysis is occurring because it occurs implicitly throughout
execution. But when it was a tree-walker we would count on to see one thing
like result_column->insertFrom(eval(*col_then), then_is_short ?
then_index++ : i);. Or it is attainable that IColumn is barely evaluated
afterward as wanted. But when that had been the case, I might count on that the
cond column must be evaluated by this code and I did not
discover something like that both.

Both method it is clear that the interpreted execution is over
vectorized information, much like Cockroach. Nevertheless in ClickHouse execution
is at all times over column vectors.

However on the precise interpreter technique I am unclear. Pointers welcome!

DuckDB (Ruling: Tree Walker)

If we check out how function expressions are
executed,
we are able to see every argument in the function being
evaluated
earlier than being handed to the precise operate. So that appears like a tree
strolling interpreter.

Like ClickHouse, DuckDB expression execution is at all times over column
vectors. You possibly can learn extra about this structure
here and
here.

Influx (Ruling: Tree Walker)

Inflow initially had a SQL-like question language referred to as InfluxQL. If we
have a look at how it evaluates a binary
expression,
it first evaluates the left-hand facet after which the right-hand facet
earlier than working on the perimeters and returning a price. That is a
tree-walking interpreter.

Flux was the brand new question language
for Inflow. Whereas the Flux
docs
counsel they remodel to an intermediate illustration that’s
executed on a digital machine, there’s nothing I am seeing that appears
like a stack- or register-based digital machine. All of the evaluation
functions
consider their arguments and return a price. That appears like a
tree-walking interpreter to me.

Immediately Inflow
announced
that Flux is in upkeep mode and they’re specializing in InfluxQL
once more.

MariaDB / MySQL (Ruling: Tree Walker)

Management stream strategies are usually a great way to see how an interpreter
is carried out. The implementation of COALESCE looks pretty
simple. We
see it call
val_str()
for every argument to COALESCE. However I can solely appear to search out
implementations of val_str() on uncooked values and never
expressions. Item_func_coalesce itself doesn’t implement
val_str() for instance, which might be a robust indication of a tree
walker. Possibly it does implement val_str() by way of inheritance.

It turns into a bit clearer if we have a look at non-control stream strategies
like
acos. In
this technique we see Item_func_acos itself implement val_real() and
additionally name val_real() on all its arguments. On this case it is apparent
how the management stream of acos(acos(.5)) would work. In order that appears to
point out expressions are executed with a tree strolling interpreter.

I additionally seen
sql/sp_instr.cc. That
is frightening (when it comes to invalidating my evaluation) because it appears like a
digital machine. However after wanting by way of it, I believe this digital
machine solely corresponds to how saved procedures are executed, therefore
the sp_ prefix for Saved Applications. MySQL
docs
additionally clarify that saved procedures are executed with a bytecode
digital machine.

I am curious why they do not use that digital machine for question
execution.

So far as I can inform MySQL and MariaDB don’t differ on this regard.

MongoDB (Ruling: Digital Machine)

Mongo recently
introduced
a digital machine for executing queries, referred to as Slot Based mostly Execution
(SBE). We are able to discover the SBE code in
src/mongo/db/exec/sbe/vm/vm.cpp
and the principle digital machine entrypoint
here. Looks
like
a traditional stack-based digital machine!

It is not utterly clear to me if the SBE path is at all times used or if
there are nonetheless circumstances the place it falls again to their previous execution
mannequin. You possibly can learn extra about Mongo execution
here
and here.

PostgreSQL (Ruling: Digital Machine + JIT)

The highest of PostgreSQL’s
src/backend/executor/execExprInterp.c
clearly explains that expression execution makes use of a digital machine. You
see all of the hallmarks: opcodes, a loop over an enormous swap, and so on. And
if we have a look at how function expressions are
executed,
we see one other hallmark which is that the operate expression code
does not consider its arguments. They’ve already been evaluated. And
operate expression code simply acts on the outcomes of its arguments.

PostgreSQL additionally
supports
JIT-ing expression execution. And we are able to discover the swap between
decoding and JIT-compiling an expression
here.

QuestDB (Ruling: Tree Walker + JIT)

QuestDB wrote about their execution engine
recently. When
the situations are proper, they will switch over to a JIT
compiler
and run native code.

However let’s take a look at the default path. For instance, how AND is
implemented. AndBooleanFunction
implements BooleanFunction which implements Operate. An
expression might be evaluated by calling a getX() technique on the
expression sort that implements Operate. AndBooleanFunction calls
getBool() on its left and proper hand sides. And if we have a look at the
partial
implementation
of BooleanFunction we’ll additionally see it doing getX() particular
conversions throughout the name of getX(). In order that’s a tree-walking
interpreter.

Scylla (Ruling: Tree Walker)

If we check out how functions are
evaluated
in Scylla, we see operate analysis first evaluating all of its
arguments. And
the operate analysis operate itself returns a
cql3::raw_value. In order that’s a tree-walking interpreter.

SQLite (Ruling: Digital Machine)

SQLite’s digital machine is comprehensive and
well-documented. It encompasses
extra than simply expression analysis however the entirety of question
execution.

We are able to discover the huge digital machine swap in
src/vdbe.c.

And if we glance, for instance, at how AND is carried out, we see it
pulling its arguments out of
memory
(already evaluated) and assigning the end result again to a designated
point in
memory.

SingleStore (Ruling: Digital Machine + JIT)

Whereas there is no supply code to hyperlink to, SingleStore gave a talk at
CMU that broke
down their question execution pipeline. Their
docs
additionally cowl the subject.

TiDB (Ruling: Tree Walker)

Much like DuckDB and ClickHouse, TiDB implements vectorized
interpretation. They’ve written publicly about their switch to this
method.

Let’s check out how if is carried out in TiDB. There’s a
vectorized and non-vectorized model of if (in
expression/control_builtin.go
and
expression/control_builtin_generated.go
respectively). So possibly they have not utterly converted to
vectorized execution or possibly it may possibly solely be utilized in some situations.

If we have a look at the non-vectorized version of
if,
we see the condition
evaluated. And
then the then or else is evaluated depending on the result of the
condition. That is
a tree-walking interpreter.

Conclusion

Because the DuckDB workforce points out,
vectorized interpretation or JIT compilation seem like the
future for
database expression execution. These methods appear significantly
essential for analytics or time-series workloads. However vectorized
interpretation appears to take advantage of sense for column-wise storage
engines. And column-wise storage usually solely is smart for
analytics workloads. Nonetheless, TiDB and Cockroach are transactional
databases that additionally vectorize execution.

And whereas SQLite and PostgreSQL use the digital machine mannequin, it is
attainable databases with tree-walking interpreters like Scylla and
MySQL/MariaDB have determined there may be not important sufficient good points to be
had (for transactional workloads) to justify the complexity of transferring
to a compiler + digital machine structure.

Tree-walking interpreters and digital machines are additionally impartial
from whether or not or not execution is vectorized. In order that can be one other
attention-grabbing dimension to observe: if extra databases transfer towards
vectorized execution even when they do not adapt JIT compilation.

Yet one more different is that possibly as databases mature we’ll see
compilation tiers much like what browsers
do
with JavaScript.

Credit: Thanks Max Bernstein, Alex Miller, and Justin Jaffray for
reviewing a draft model of this! And due to the #dbs channel on
Discord for instigating this
put up!

I spent a while wanting into how varied databases execute expressions of their question language.

Most of them have a tree-walking interpreter, some have a digital machine, and a few do just-in-time compilation.

Let’s dig into some database code to see!https://t.co/BIGtHKh1X4 pic.twitter.com/nmhe9HmYw7

— Phil Eaton (@eatonphil) September 21, 2023