How do databases execute expressions? | Hacker News Reader

How do databases execute expressions?

notes.eatonphil.com

77 pointstodsacerdoti16 comments

Amazing overview. Right now I work on a completely new OLAP database: vectorized query execution is must have nowadays if you want to have competitive performance. What's interesting is that vectorized query engines benefits a lot from SIMD instructions (that is obvious). But what is less obvious is that rising popularity of ARM CPUs made it more complex to developer vectorized query engine because one has to provide support for both architectures.

Related: "Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask"

https://www.vldb.org/pvldb/vol11/p2209-kersten.pdf

Yep that's a great one. Linked to in the conclusion here as well.

> because one has to provide support for both architectures

You aren't using LLVM IR then? I found that if you are a bit careful, LLVM is perfectly capable to lower IR to vector instructions in ARM/X86 automatically.

idk why you would use a virtual machine. clustrix did for a while until the instruction dispatch loop dominated profiling. then one particularly clever and energetic engineer just lowered onto x86

I did the switch from a tree walk interpreter to a VM in postgres - it did lead to substantial speedups.

I've experimented with lowering into x86 "manually" as well, and it did provide gains, but the portability aspects are concerning. And for much of the desirable speedups you ime want more optimization than trivial lowering would give you.

Either way, without the tree walk -> VM move, it'd have been much harder to lower into x86 directly. And you'd still need a fallback for other platforms.

Did the switch? Does postgres use a VM now?

> Did the switch? Does postgres use a VM now?

Yes (to me my comment seemed to make that clear, but...).

Didn't really remember how long ago that was, so I dug up the commit. Main commit went in ~6.5 years ago. There were lots of related changes but the main commit is https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit...

A recent blog post about MongoDB's SBE detailed that the purpose behind their VM is that it serves as a way to re-use an execution component between two different query languages. SQLite's claim was just that the strong separation between compilation and execution makes issues easier to debug.

I wouldn't expect VMs to become the default design in databases, but it seems like it's getting increasingly common as an IR for query compilation. The ability to have a (comparatively simpler) interpreter for the VM also means you can apply simple fuzzing to great effect: if the results of interpretation vs compilation ever diverge, there's a bug.

MonetDB has been doing this (VM for query execution) since 2002-2004ish.

Another related aspect is that the VM approach can allow JITing only some of the opcodes, which makes it more feasible and maintainable.

It would surprise me to see the dispatch loop dominate in a DB? given that on the whole databases tend to block a lot on more expensive things like materialization, joins, etc?

I do think that a VM could mess up CPU branch prediction so I can see that as being a problem?

Some people have gone the route of emitting LLVM IR (or similar) for query plans, but this has a cost, too, so only makes sense for repeatedly used queries.

It really depends on the query. If there's a bunch of math in the select list, it's easy for that to be the biggest bottleneck, even if there are joins etc. Also you'll sometimes have to evaluate expressions to check join conditions depending on the join implementation and condition.

> I do think that a VM could mess up CPU branch prediction so I can see that as being a problem

It definitely happens. It can be partially addressed with things like computed gotos, but it's far from perfect. At least for postgres, it's just that the tree walk overhead was far higher.

The branch prediction handling for opcode dispatch loops definitely improved in CPUs - for Intel somewhere around Haswell (it's been a while, so this is a guess). I remember that, at the time, the gains of using computed goto on my aging workstation (nehalem) were far bigger than a few uarchs later, even when controlling for cache size etc.

Semi related anecdote: Both opcode dispatch switches and computed goto based dispatch are good for stressing compilers. I found newly introduced >= quadratic behavior in all the major c compilers in the years since.

clearly not in I/O bound cases, but in that world everything except the b-tree was done relationally, so yeah joins and view and the whole lot. we may have also had a really poorly though out VM. but direct instruction generation wasn't really a big deal and it helped quite a bit

InfluxDb is going back to InfluxQL? Interesting.

interesting article, was playing with GPT while reading it as well.

The below summarisation was good

Tree Interpretation: Best for lightweight or embedded systems where resource usage is a concern.

Virtual Machines: Suitable for general-purpose databases that need to handle a variety of query complexities.

JIT Compilation: Ideal for databases that handle complex or long-running queries, where the overhead of JIT can be offset by performance gains.

Reply on news.ycombinator.com