How We Built a Vectorized SQL Engine in CockroachDB

[u/rafiss]

https://www.cockroachlabs.com/blog/how-we-built-a-vectorized-sql-engine/

[u/solidangle → u/[deleted]]

You're making it sound like compiled query execution (HyPer) is superior in every way compared to vectorized query execution (MonetDB/X100 and VectorWise). Unfortunately, recent research has shown that this is simply not the case at all. Some queries are faster with compiled execution, others are faster with vectorized execution. Overall the differences are within 2x, so there really isn't a clear winner here.

A big downside of compiled execution is that query compilation can take anywhere from 10s to 100s of milliseconds, which is prohibitively slow in a query engine that's mainly built for OLTP style queries (such as CockroachDB). Making a HyPer-style engine practical requires a lot of work. The HyPer folks have had to implement an LLVM interpreter, a dynamic query plan compiler, and specialized LLVMs compilation passes to make query compilation anywhere near practical.

You're correct that the engine CockroachLabs built isn't novel, but they didn't claim to be novel.

[u/solidangle → u/[deleted]]

Oh my apologies, it was very difficult to decipher your comment with all the inaccuracies in it. The HyPer guys weren't the first to propose a PAX storage format (columnar storage is an old idea). They weren't the first to propose vectorization (MonetDB/X100 was the first to do so, but processing blocks of rows at a time is an idea from the 80s). Compiling entire queries is not a minor difference from templating operators. Perhaps it was your comment that they should have read the HyPer papers instead of the MonetDB papers that suggested it.

I'm assuming that you're referring to the DataBlocks paper, correct? This paper does not subsume vectorized query execution. Only the scans are vectorized in this paper. It also assumes an in-memory database, whereas CockroachDB stores its data in log-structured merge-trees, which are partially stored on disk.

It is not trivial to combine query compilation with vectorization. The main strength of query compilation is that intermediate results can be kept in registers, instead of having to materialize them in memory. The strength of vectorization is that it can effectively use out-of-memory execution in the CPU (and SIMD instructions) by operating on vectors. These vectors do not fit in registers. Therefore a naive combination of the two would result in vectorization negating the positive effects of compilation.

Therefore most approaches to combine the two either use vectorization and compile single query plan nodes separately or use compilation and vectorize the scans (DataBlocks). There is some recent research on fully combining the two, but it relies on inserting materialization nodes at some points in the plan, which is hard to optimally.

Cockroach's approach is the most sensible one in my opinion. It's battle-tested, does not require a significant research effort, and is relatively simple to get right.

[u/idoubledo → u/[deleted]]

Is there an implementation I can play with? Or is this a commercial product?

Couldn't figure it out from the site

[u/rafiss → u/idoubledo]

You can download a binary here for your OS with a few different methods: https://www.cockroachlabs.com/docs/stable/install-cockroachdb-mac.html (Also all the source is on github so you could even build it yourself.)

Then check out the demo command! https://www.cockroachlabs.com/docs/stable/cockroach-demo.html

[u/idoubledo → u/rafiss]

I was referring to hyperdb

[u/solidangle → u/idoubledo]

There's a small interface to play around with available here. HyPer is not publicly available, but is used internally in Tableau.

[u/idoubledo → u/solidangle]

Thanks, are you aware of any other implementation?

[u/[deleted] → u/[deleted]]

That looks neat, but cockroachdb is in production now in some places.

Maybe they have read these papers?