6 ms·

How We Built a Vectorized SQL Engine

209 points by rafiss 7y ago

jordanlewis 7y ago
A few Cockroach Labs engineers are hanging out on this thread - happy to answer any questions you might have about how we made Go go faster.
- sujayakar 7y ago
  does Go's compiler emit SIMD instructions? it'd be cool to see the disassembly for the final, column order version since that loop would vectorize well. the same question goes for the speed-of-light benchmark -- there may be room to push even further there if it's doing a single multiply at a time.
  - ryanworl 7y ago
    It does not. You can use something like Avo to lighten the load a bit of writing those assembly routines. It takes care of register allocation, struct fields, and the necessary function stubs.
    - asubiotto 7y ago
      +1 avo is on our radar as a tool to use in the future
    - dilyevsky 7y ago
      I was recently profiling some code in utf8 package and it caught my attention that some easily SIMDable code was lighting up in the flame chart. Kind of lame it can’t do that
georgewfraser 7y ago
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?
- manigandham 7y ago
  > "data needs to be read from disk in its original row-oriented format before processing, which will account for the lion’s share of the query’s execution latency." IO is still a bottleneck without column-stores. The selectivity, compression and encoding alone can generate massive speedups because there's less data to process, and less to move through the execution pipeline. But batch/vectorized processing on row-stores is gaining adoption. MemSQL and SQL Server also use similar techniques.
- rafiss 7y ago
  Thanks! I do think that a columnar on-disk representation would likely help with large analytical queries. But I would imagine they would negatively affect performance of point transactions in an OLTP workload. Note that this vectorized engine we built will only be used on a given query if our SQL planner estimates that a large number of rows will be read.
- asubiotto 7y ago
  It's hard to say whether one would generally be a bigger gain than another without experimenting. We chose to focus on just execution because it was a relatively smaller project (with less side-effects) that still promised a large performance improvement. In the future, we might consider keeping data in columnar format on learner replicas to offer even better performance for users that would like to run OLAP-style queries on slightly stale data, but this would be a larger project.
- jandrewrogers 7y ago
  This is a complicated discussion because the relative performance is greatly impacted by design and implementation details. Broadly speaking, the execution engine and page representation designs are tightly coupled for performance optimization purposes. The kinds of optimizations outlined at the link will have a high return for most kinds of databases. The term "columnar" covers a diverse set of architectures with very different operational characteristics. For OLTP (like CockroachDB), using a classic DSM-style columnar representation is going to offer poor write performance no matter what you do with the execution engine. On the other hand, if you are using one of the newer vectorized page representations (VSM) that are popular for mixed workloads, which are quasi-columnar but not DSM (nor one of the intra-page DSM hybrids like PAX), the loss of write performance may be minimal versus a classic row store (NSM) but with much faster query processing (faster than DSM for some types of queries). The execution engine design you would attach to any of these models is pretty different. Note also that a practical limit on this kind of optimization is code complexity. While VSM-style on-disk representation and matching execution engine sounds like a nearly optimal hybrid of both NSM for write performance and DSM for query performance, an implementation that is general purpose and performs well across a diverse set of data models is massively more difficult and complex to build in practice so most database designers avoid it at all costs due to the engineering overhead. These tend to be more common when the set of supported data models are very limited at design time. It is a research area that still offers a lot of opportunity -- the literature mostly ignores parts of the productive design space that intrinsically have extremely high implementation complexity (too difficult to produce code in support of paper publication).
qaq 7y ago
Didn't CockroachDB target OLTP workloads? What would the write performance be like for a columnar store for OLTP workload?
- asubiotto 7y ago
  CockroachDB does target OLTP workloads. Note that the vectorized SQL engine covered in this blog post is execution-only (and used only for queries that operate on many rows). The storage layer remains row-oriented so the write performance is not affected. Rows are columnarized before processing by the execution engine.
beders 7y ago
When are they going through with a rename? This sub-optimal name is holding them back.
- ticmasta 7y ago
  Why is this sub-optimal? People may not like Cockroaches but they definitely have a reputation for durability, which isn't a bad mental link for a database company. It also provides an identity & personality which is so often missing from modern companies. Maybe they've found they get more from those who really like it than those who really hate it (or maybe they just like it themselves).
  - beders 7y ago
    It still has a negative connotation. That's unavoidable. People don't like cockroaches. From a marketing point of view, it is a very bad name. Unless the perception of cockroaches changes, which is rather unlikely.
    - nitwit005 7y ago
      If you pick a happy name, you get complaints that they sound too generic, sound like a medication name, etc. People also complain if your name ends in .com or .net, as apparently that sounds like something from the mid 90s. People just like complaining about names.
      - james_s_tayler 7y ago
        On the other hand no one brings this point up about Oracle, PostgreSQL, SQL Server, MySQL, MariaDB etc. People like complaining about names that they wish things didn't have.
        nitwit005 7y ago
        I haven't used most of those, but SQL Server is a prime source of griping about names, as Microsoft keeps popping out strangely named variations. See: https://en.wikipedia.org/wiki/Microsoft_SQL_Server#Editions https://en.wikipedia.org/wiki/Microsoft_SQL_Server#Editions
anonu 7y ago
Very nice post. On another note: Kdb has figured out how to optimize the heck out of columnar data stores and vector processing. They would be my benchmark for these types of optimizations.
saagarjha 7y ago
> 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 :(
- echelon 7y ago
  I'm shocked that they chose a garbage-collected language to implement a database with. Golang is great for building servers, but this is domain with potentially much greater resource constraints. How do they deal with GC pause? I'm sure that they have an answer, but they'd have so much more latitude if they had the facility to reason about this from the ground up. They've sort of painted themselves into a corner now. C, C++, or Rust would have been a better match and given me more faith in their product.
  - jordanlewis 7y ago
    We wrote a (brief) blog post about this decision way back in 2015 that you might be interested in: https://www.cockroachlabs.com/blog/why-go-was-the-right-choice-for-cockroachdb/ https://www.cockroachlabs.com/blog/why-go-was-the-right-choi... We're generally pretty happy with our choice to use Go for the database, even when it causes us pain like the kind you see in this post. Rust wasn't really ready when we started working on CockroachDB, and we think that we wouldn't have been able to make progress as quickly as we did if we had used C(++).
    - fouc 7y ago
      How hard would it be to port the code to Rust? (Not trying to make it sound like a "Rewrite in Rust" thing)
xKingfisher 7y ago
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.
- atombender 7y ago
  One interesting solution is in Lucene — which isn't perhaps classically columnar, but something of a hybrid — which uses skip lists to allow random skipping through compressed index ("posting list") data.

209 points by rafiss 7y ago

A few Cockroach Labs engineers are hanging out on this thread - happy to answer any questions you might have about how we made Go go faster.

sujayakar 7y ago
does Go's compiler emit SIMD instructions? it'd be cool to see the disassembly for the final, column order version since that loop would vectorize well. the same question goes for the speed-of-light benchmark -- there may be room to push even further there if it's doing a single multiply at a time.
- ryanworl 7y ago
  It does not. You can use something like Avo to lighten the load a bit of writing those assembly routines. It takes care of register allocation, struct fields, and the necessary function stubs.
  - asubiotto 7y ago
    +1 avo is on our radar as a tool to use in the future
  - dilyevsky 7y ago
    I was recently profiling some code in utf8 package and it caught my attention that some easily SIMDable code was lighting up in the flame chart. Kind of lame it can’t do that

georgewfraser 7y ago

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?

manigandham 7y ago
> "data needs to be read from disk in its original row-oriented format before processing, which will account for the lion’s share of the query’s execution latency." IO is still a bottleneck without column-stores. The selectivity, compression and encoding alone can generate massive speedups because there's less data to process, and less to move through the execution pipeline. But batch/vectorized processing on row-stores is gaining adoption. MemSQL and SQL Server also use similar techniques.
rafiss 7y ago
Thanks! I do think that a columnar on-disk representation would likely help with large analytical queries. But I would imagine they would negatively affect performance of point transactions in an OLTP workload. Note that this vectorized engine we built will only be used on a given query if our SQL planner estimates that a large number of rows will be read.
asubiotto 7y ago
It's hard to say whether one would generally be a bigger gain than another without experimenting. We chose to focus on just execution because it was a relatively smaller project (with less side-effects) that still promised a large performance improvement. In the future, we might consider keeping data in columnar format on learner replicas to offer even better performance for users that would like to run OLAP-style queries on slightly stale data, but this would be a larger project.
jandrewrogers 7y ago
This is a complicated discussion because the relative performance is greatly impacted by design and implementation details. Broadly speaking, the execution engine and page representation designs are tightly coupled for performance optimization purposes. The kinds of optimizations outlined at the link will have a high return for most kinds of databases. The term "columnar" covers a diverse set of architectures with very different operational characteristics. For OLTP (like CockroachDB), using a classic DSM-style columnar representation is going to offer poor write performance no matter what you do with the execution engine. On the other hand, if you are using one of the newer vectorized page representations (VSM) that are popular for mixed workloads, which are quasi-columnar but not DSM (nor one of the intra-page DSM hybrids like PAX), the loss of write performance may be minimal versus a classic row store (NSM) but with much faster query processing (faster than DSM for some types of queries). The execution engine design you would attach to any of these models is pretty different. Note also that a practical limit on this kind of optimization is code complexity. While VSM-style on-disk representation and matching execution engine sounds like a nearly optimal hybrid of both NSM for write performance and DSM for query performance, an implementation that is general purpose and performs well across a diverse set of data models is massively more difficult and complex to build in practice so most database designers avoid it at all costs due to the engineering overhead. These tend to be more common when the set of supported data models are very limited at design time. It is a research area that still offers a lot of opportunity -- the literature mostly ignores parts of the productive design space that intrinsically have extremely high implementation complexity (too difficult to produce code in support of paper publication).

qaq 7y ago

Didn't CockroachDB target OLTP workloads? What would the write performance be like for a columnar store for OLTP workload?

asubiotto 7y ago
CockroachDB does target OLTP workloads. Note that the vectorized SQL engine covered in this blog post is execution-only (and used only for queries that operate on many rows). The storage layer remains row-oriented so the write performance is not affected. Rows are columnarized before processing by the execution engine.

beders 7y ago

When are they going through with a rename? This sub-optimal name is holding them back.

ticmasta 7y ago
Why is this sub-optimal? People may not like Cockroaches but they definitely have a reputation for durability, which isn't a bad mental link for a database company. It also provides an identity & personality which is so often missing from modern companies. Maybe they've found they get more from those who really like it than those who really hate it (or maybe they just like it themselves).
- beders 7y ago
  It still has a negative connotation. That's unavoidable. People don't like cockroaches. From a marketing point of view, it is a very bad name. Unless the perception of cockroaches changes, which is rather unlikely.
  - nitwit005 7y ago
    If you pick a happy name, you get complaints that they sound too generic, sound like a medication name, etc. People also complain if your name ends in .com or .net, as apparently that sounds like something from the mid 90s. People just like complaining about names.
    - james_s_tayler 7y ago
      On the other hand no one brings this point up about Oracle, PostgreSQL, SQL Server, MySQL, MariaDB etc. People like complaining about names that they wish things didn't have.
      - nitwit005 7y ago
        I haven't used most of those, but SQL Server is a prime source of griping about names, as Microsoft keeps popping out strangely named variations. See: https://en.wikipedia.org/wiki/Microsoft_SQL_Server#Editions https://en.wikipedia.org/wiki/Microsoft_SQL_Server#Editions

anonu 7y ago

Very nice post. On another note: Kdb has figured out how to optimize the heck out of columnar data stores and vector processing. They would be my benchmark for these types of optimizations.

saagarjha 7y ago

> 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 :(

echelon 7y ago
I'm shocked that they chose a garbage-collected language to implement a database with. Golang is great for building servers, but this is domain with potentially much greater resource constraints. How do they deal with GC pause? I'm sure that they have an answer, but they'd have so much more latitude if they had the facility to reason about this from the ground up. They've sort of painted themselves into a corner now. C, C++, or Rust would have been a better match and given me more faith in their product.
- jordanlewis 7y ago
  We wrote a (brief) blog post about this decision way back in 2015 that you might be interested in: https://www.cockroachlabs.com/blog/why-go-was-the-right-choice-for-cockroachdb/ https://www.cockroachlabs.com/blog/why-go-was-the-right-choi... We're generally pretty happy with our choice to use Go for the database, even when it causes us pain like the kind you see in this post. Rust wasn't really ready when we started working on CockroachDB, and we think that we wouldn't have been able to make progress as quickly as we did if we had used C(++).
  - fouc 7y ago
    How hard would it be to port the code to Rust? (Not trying to make it sound like a "Rewrite in Rust" thing)

xKingfisher 7y ago

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.

atombender 7y ago
One interesting solution is in Lucene — which isn't perhaps classically columnar, but something of a hybrid — which uses skip lists to allow random skipping through compressed index ("posting list") data.