How We Built a Vectorized SQL Engine

A Datum now has a field for each possible type it may contain, rather than having separate interface implementations for each type. There is an additional enum field that serves as a type marker, so that when we do need to, we can inspect a type of a Datum without doing any expensive type assertions. This type uses extra memory due to having a field for each type, even though only one of them will be used at a time.

The Go templating engine allows us to write a code template that, with a bit of work, we can trick our editor into treating as a regular Go file. We have to use the templating engine because the version of Go we are currently using does not have support for generic types.

Go’s lack of an expressive type system continues to disappoint :(

A question I've never found a good answer to for columnar query engines is how to handle indexing.

For queries with very high selectivity it seems like any gains from increased cache-friendliness or SIMD would be erased by still needing to make random forward strides through the data.

The only solution I can really think of is to make the index point to a block of N elements and then take advantage of vector processing on the matching blocks. Have you run into this issue?

I haven't been able to find any examples of column SQL engine discussions that don't require whole-table scans.

This is such a great post! Soooo many databases have implemented some kind of “column store extension” where they change the on disk representation and declare “look now we’re a hybrid database”. But the academic literature suggests that the bigger win for column stores may be in the execution layer. I love that Cockroach has taken the opposite of the usual approach and been so rigorous in measuring everything.

After doing all this work, is it your opinion that (hypothetically) a columnar on-disk representation would be a bigger or smaller win than a fully-built-our vectorized execution engine?