How We Built a Vectorized SQL Engine • Hacker News Board

Re: How We Built a Vectorized SQL Engine

#41

Post by xKingfisher » Tue, Nov 12, 2019, 6:19 AM UTC

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.

Re: How We Built a Vectorized SQL Engine

#42

Post by atombender » Tue, Nov 12, 2019, 6:42 AM UTC

xKingfisher wrote: post #41

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 processi…

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.

Re: How We Built a Vectorized SQL Engine

#43

Post by jandrewrogers » Tue, Nov 12, 2019, 6:45 AM UTC

mumblemumble wrote: post #38

jandrewrogers wrote: post #30

Earlier quoted context omitted.

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 actua…

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.

Re: How We Built a Vectorized SQL Engine

#44

Post by pjungwir » Tue, Nov 12, 2019, 6:46 AM UTC

james_s_tayler wrote: post #26

nitwit005 wrote: post #20

Earlier quoted context omitted.

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.

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

Re: How We Built a Vectorized SQL Engine

#45

Post by petepete » Tue, Nov 12, 2019, 7:20 AM UTC

recursivecaveat wrote: post #39

nitwit005 wrote: post #34

Earlier quoted context omitted.

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.

Re: How We Built a Vectorized SQL Engine

#46

Post by roberson87 » Tue, Nov 12, 2019, 8:05 AM UTC

mjibson wrote: post #40

fouc wrote: post #35

Earlier quoted context omitted.

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?

Re: How We Built a Vectorized SQL Engine

#47

Post by endymi0n » Tue, Nov 12, 2019, 8:06 AM UTC

jandrewrogers wrote: post #30

ken wrote: post #25

Earlier quoted context omitted.

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 significant…

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 actua…

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.

Re: How We Built a Vectorized SQL Engine

#48

Post by timClicks » Tue, Nov 12, 2019, 8:12 AM UTC

ryanworl wrote: post #23

echelon wrote: post #21

Earlier quoted context omitted.

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

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 allocat…

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.

Re: How We Built a Vectorized SQL Engine

#49

Post by tom_mellior » Tue, Nov 12, 2019, 9:03 AM UTC

aloknnikhil wrote: post #28

ken wrote: post #25

Earlier quoted context omitted.

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 significant…

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…

> 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?

Re: How We Built a Vectorized SQL Engine

#50

Post by stubish » Tue, Nov 12, 2019, 9:40 AM UTC

endymi0n wrote: post #47

jandrewrogers wrote: post #30

Earlier quoted context omitted.

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 actua…

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…

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.