How We Built a Vectorized SQL Engine | Hacker News Reader

How We Built a Vectorized SQL Engine

cockroachlabs.com

209 pointsrafiss55 comments

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

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.

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-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(++).

How hard would it be to port the code to Rust? (Not trying to make it sound like a "Rewrite in Rust" thing)

Super mega ultra hard. It would take so much time for us to learn rust, port everything including all tooling, and fix new bugs we introduce that we wouldn't add any new features (but lots of new bugs!) for like 2-4 years and the company would die.

Thanks for your input. I have no exp at all on db internals, but could you expand your thoughts on the possibility of moving critical (storage layer?) parts to Rust and leave all the networking stuff/rest in Go? Similar to what TiDb have done?

Writing a program in C++ or Rust will not just make it use memory more efficiently than Go with the GC for free. Many Rust programs do a lot of heap allocations, and lots of people in C++ liberally use reference counted pointers which both require heap allocation and atomics.

It is possible to write Go programs which efficiently use memory using object pooling just as you would in C. Go additionally can stack allocate many variables that would require a heap allocation in Java, where the GC is a much bigger issue.

When you say that Rust uses lots of allocations, are you referring to the heavy use of Vec<_>? My understanding is that almost everything that can be allocated on the stack, is. Boxed types and trait objects are available, but they're opt-in features rather than the default.

A database is a server. Your malloc isn't deterministic, either.

According to the Go Wikipedia article, as of 2017:

> Garbage collection pauses should be significantly shorter than they were in Go 1.7, usually under 100 microseconds and often as low as 10 microseconds.

According to [1], "A trivial SELECT can take in the order of 0.1ms to execute server-side", i.e., 100 microseconds. Any I/O will of course significantly increase that.

This sounds like an entirely reasonable price to pay. Writing high-level functionality in C in 2019 would not give me much faith in their product.

[1]: https://www.2ndquadrant.com/en/blog/postgresql-latency-pipel...

For me, the issue with GC never has been about how long it runs for. It's been about the unpredictability of when it can kick in. Granted a malloc can be unpredictable too (albeit very very rarely), but at least you know a malloc is the only time your process could stall waiting for memory.

Databases make extensive use of scratch space for undo logs and redo logs and especially while processing JOINs. It's tremendous pressure on the GC that results in frequent performance dips. With C/C++/Rust, you'd pipeline the query stages to malloc/free that space outside the hot path to minimize query response times.

I'll repeat what was mentioned elsewhere. The GC pauses in Go are in the order of microseconds. We've done a ton of work keeping our memory usage under tight bounds and keeping a close eye on exactly how the go GC processes interplay with query execution threads (what processors are consumed, GC pressure buildup, where/when the stalls are introduced, etc.) Consistently we've found that given you're invariably dealing with network latencies (it's a distributed db after all), the microsecond GC pauses are almost entirely dwarfed to matter (I'm not excluding p99s here).

> With C/C++/Rust, you'd pipeline the query stages to malloc/free that space outside the hot path to minimize query response times.

I don't understand why you seem to assert that GC'd languages would force you to put allocations on the hot path. Surely in Go you can also allocate that space elsewhere?

I was primarily referring to the free on the hot path. GCd languages don't force any allocation paradigms. But due to the unpredictability of the GC, you could be in the middle of a query execution and the GC can kick in. With C/C++/Rust, you're free to maintain your own a allocator that could have a buffer pool of pages that can be recycled and freed when the database is idle. Under a large load, the micro spikes in latency can have an avalanche effect that leads to a build up of queries. I've dealt with customer cases where the MySQL/InnoDB lock manager caused connection spikes due to a brief (< 10 us) global write lock taken while the system was under load.

> But due to the unpredictability of the GC, you could be in the middle of a query execution and the GC can kick in.

Yes, that is a possibility. Typically there are two ways to deal with this in a GC'd language: (a) You know that GC is only triggered by certain operations that might allocate, and you avoid those operations in your critical hot section, or (b) you know how to disable the GC temporarily, while you are in that critical hot section. For Go the latter is apparently done by calling this function: https://golang.org/pkg/runtime/debug/#SetGCPercent

I'm not a Go developer myself, but I imagine people developing such low-latency software in Go know about this.

Throughput optimization in database engines often relies on operation latency being visible and predictable to the execution scheduler. Disk I/O has this property, a GC does not, so they are not comparable in terms of their impact on throughput. An important class of schedule-based architectural optimizations are rendered ineffective if you are running a GC in the background.

This only matters to databases that actually implement these optimizations. If a database does not then a GC has a much smaller impact. But it also means that, all other things being equal, the database will never be competitive with a non-GC design since those optimizations can provide an integer factor improvement in performance.

Also, many database engines aren't doing malloc() at runtime. 100 microseconds of CPU time is an integer factor larger than many atomic database operations in a fast database engine. An operation taking an order of magnitude longer than the scheduler would expect based on runtime state has real adverse consequences.

So, before we theorize that Cockroach can't possibly be fast enough to meet anyone's needs, perhaps we should look at some performance figures?

I haven't ever touched it myself, but, if the benchmarks that Cockroach Labs posts on their blog are to be believed, it's pretty respectable for what it is.

You are misrepresenting what was written. Most databases don't need to be optimal to be useful, merely adequate, and few attempt to be optimal in any kind of absolute sense. I still use PostgreSQL regularly and it unambiguously falls into this "far from optimal" category.

However, as data velocity and volume grow, optimization of absolute performance and hardware efficiency has an increasingly large impact on the cost of operating a database and the kinds of applications you can economically run. Databases that sacrifice major optimizations at an architectural level will have no chance to be competitive with databases that do not over the long term as average data volume and velocity grows. At the scale of database operations many companies are using today, these optimizations literally save them tens of millions of dollars per year on infrastructure.

CockroachDB produces what looks like a fine product and has every right to make whatever technical decisions they wish. That the architecture has made substantial performance sacrifices is not theoretical though, and they don't pretend to operate in markets that require any kind of absolute operational efficiency.

This seems to me, though, like a spot where the application of Knuth's law is critical. It's not enough to demonstrate that X is slower than it could be, you have to demonstrate that it is that, and that this is also having an appreciable impact on the overall behavior of the system.

So, given that CockroachDB is a distributed system, I'd want to start by seeing some measurements to demonstrate that GC overhead is having a bigger impact than, say, network latency.

This is slightly missing the point. Lots of successful large scale databases have been written in garbage collected languages, including for example Cassandra and ElasticSearch. They're completely fine.

What's important to notice though is that what really matters about latency and predictability is _relative_ performance.

Now there is a category of databases that are built for speed of response first, some of which have some pretty spaced out architecture under the hood. Aerospike comes to my mind, together with ScyllaDB or Redis maybe. They trade off this speed with massive compromises in complexity, consistency and scalability.

GC would be disastrous for these, so they're all written in C(++).

The main premise of CockroachDB is geographic replication, durability and scalability while maintaining full consistence and serialization.

In order just to keep these promises, a large part of the design of Cockroach is that the DB needs to keep _waiting_ most of the time of any request until all geo replicated shards are consistent. We're talking dozens to hundreds of milliseconds here. And even if that wasn't the case, a full GC of 100 microseconds probably isn't even noticeable compared with the weight of complex SQL query planning and execution.

You may stink a lot of valid points about Go, but this isn't one of them.

Cassandra has huge problems with JVM garbage collection, and it still isn't rid of them in the decades it has been in development. The reason for the scary warnings if your partition sizes exceed 100MB is garbage collection. The reason you can't tune it to use all your RAM on a modern box is garbage collection. Picking JVM implementations and tuning mostly seems to revolve around garbage collection and its trade offs. A common symptom of poorly maintained clusters is second long garbage collection pauses.

The trick with Go seems to be that programs don't seem to generate much garbage to collect, so I don't know if there is much use comparing with Java apps. But garbage collection overhead is certainly a major issue to be wary of for any application needing consistently low response times.

C may not be an attractive choice in 2019, but C++ and Rust certainly are.

Especially if you're working at the level where you want/need vectorization.

Go’s GC pauses are on a microsecond scale. If you absolutely need to minimize latency at all costs, I’d be more worried that the Go compiler doesn’t optimize as aggressively as C/C++/Rust.

InfluxDB is written in Golang as well. It's rather performant and scales out nicely, given my experience I don't think I'd consider Golang a big concern.

There is VictoriaMetrics, which is also written in Go and shows much higher performance numbers than InfluxDB, especially on high cardinality data. See [1], [2] and [3].

[1] https://medium.com/@valyala/measuring-vertical-scalability-f...

[2] https://medium.com/@valyala/insert-benchmarks-with-inch-infl...

[3] https://medium.com/@valyala/high-cardinality-tsdb-benchmarks...

For the record, the first approach was just used for simplicity in the blog post. The production system works differently (and doesn't have to waste memory per-datum) - we have typed containers, each of which have a primitive slice within.

https://github.com/cockroachdb/cockroach/blob/master/pkg/col...

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?

> "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.

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.

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.

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).

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.

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.

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.

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.

+1 avo is on our radar as a tool to use in the future

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

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

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.

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.

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.

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

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).

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.

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.

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.

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

My problem with SQL Server is that the name is so generic it sounds more like a product category than a product. Its like naming a word processor "Text Rendering Engine". Microsoft seems to be generally terrible at naming things: I don't know how they expected people to keep .NET Core, Standard, Framework, and Mono separate, not even counting how bad a name .NET is in the first place.

It also has the advantage of slightly-less-technical people thinking it is the SQL Server and there's no other options.

The Biggest Mistake Postgres Ever Made: http://www.craigkerstiens.com/2018/10/30/postgres-biggest-mi...

I’m not a paying customer so my anecdote maybe isn’t useful, but there’s so many databases that typically I just brush them off, but this one grabbed my attention because of the name.

Also, Dung Beetles Navigate Using the Milky Way. Still wouldn't call my new browser Dung Beetle...

You might be interested in BikeshedDB [0].

[0] https://github.com/tbg/bikesheddb

I'm sure even you'll admit that they have a rather cute looking cockroach as a logo.

Bad publicity is better than no publicity.

For their target market, I don't think their name matters nearly as much as you think it does.

Reply on news.ycombinator.com