Live data from Hacker News

How should you build a high-performance column store for the 2020s?

lemire.me

21–30 of 73 posts

Re: How should you build a high-performance column store for the 2020s?

#21
post #15

Earlier quoted context omitted.

In RDBMS, when you shard, read shards and write shards are in lock-step, which is the whole problem with sharding. In Datomic (and in git), by sharding writes, it doesn't really impact reads. This is interesting, because consider a large system like Facebook. Transactions naturally fall within certain boundaries. You never transact to Events, Photos, and Instagram all at once - from the write side, they don't have to…

I was under the impression, based on its docs, that Datomic only supports processing transactions serially through a single transactor.

Both what you write and what I wrote are true.

To scale writes you shard writes. This generally means running multiple databases (in any DBMS)

The key insight is that Datomic can cross-query N databases as a first class concept, like a triple store. You can write a sophisticated relational query against Events and Photos and Instagram, as if they are one database (when in fact they are not).

This works because Datomic reads are distributed. You can load some triples from Events, and some triples from Photos, and then once you've got all the triples together in the same place you can do your queries as if they are all the same database. (Except Datomic is a 5-store with a time dimension, not a triple store.)

In this way, a Datomic system-of-systems can scale writes, you have regional ACID instead of global ACID, with little impact to the programming model of the read-side, because reads were already distributed in the first place.

For an example of the type of problems Datomic doesn't have, see the OP paragraph "To sort, or not to sort?" - Datomic maintains multiple indexes sorted in multiple ways (e.g. a column index, a row index, a value index). You don't have to choose. Without immutability, you have to choose.

Re: How should you build a high-performance column store for the 2020s?

#22

This already exists, in Google BigQuery. Uses darn near every trick in the book, and some that aren’t in the book. Source: shipped it.

BigQuery uses a lot of tricks to get efficiency, but this post emphasizes Apache Arrow and open data formats like it as the way forward (in particular the last point, "Be open, or else…") which are not currently supported by BigQuery. If Apache Arrow takes off I hope BigQuery will support it as a data interchange format in the future. Zero-copy is pretty awesome, as are open standards in general. This feature does no…

One thing people commonly miss about this is this is all meaningless if you don’t have the corresponding runtime integration, and these techniques very much imply co-design, and therefore tight coupling, between the format and the runtime. To give a concrete example, to make any of this efficient and fast you must have predicate pushdown directly into decoder such that filters could skip the data they don’t need to decode. Some aggregations could be handled the same way.

So it’s a little incorrect to think of this as a “file format” in the first place. If you end up designing it like that, you’d not be able to have a lot of the gains that the Abadi paper (and others like it) alludes to. My suggestion would be to go whole hog and push down as much filtering and aggregation in there as is feasible, exposing a higher level interface with _at least_ filtering predicate support, and do it in C++.

Re: How should you build a high-performance column store for the 2020s?

#23
post #16

This already exists, in Google BigQuery. Uses darn near every trick in the book, and some that aren’t in the book. Source: shipped it.

[Edit]: Why was the above comment flagged? How much of big queries performance do you think stems from Capacitor versus the rest of the system. For example if you switched it out with parquet, but kept everything else (Colossus, Dremel, Background reordering, metadata stored in Spanner etc) would it still be 10/30/50% worse or would it be an order of magnitude worse.

We looked at Parquet early on and it wasn’t competitive even with what we were using at the time.

And yeah, this really depends not just on the dataset, but also on how selective your queries are, what predicates and aggregations they employ, etc. A significant percentage of queries gets orders of magnitude faster. I can’t disclose how much faster things got on average, but it was a significant gain, way more than would be sufficient to offset the increased cost of encoding (which is another aspect people typically don’t consider), even considering that much of the data people encode is hardly ever touched.

Re: How should you build a high-performance column store for the 2020s?

#24

Datastore of 2020s will be designed around an immutable log because it permits both strong consistency and horizontal scaling (like git). Once you're both distributed and consistent, the problems today's stores are architected around, go away. Your distributed queries can index the immutable log however they like. column-oriented, row-oriented, documents, time-oriented, graphs, immutability means you can do all of it…

Datomic honestly sounds amazing based on everything I've read and heard about it. I wish it wasn't completely proprietary though. Even an open-core model would make it a much more viable option.

Re: How should you build a high-performance column store for the 2020s?

#25
post #16

This already exists, in Google BigQuery. Uses darn near every trick in the book, and some that aren’t in the book. Source: shipped it.

[Edit]: Why was the above comment flagged? How much of big queries performance do you think stems from Capacitor versus the rest of the system. For example if you switched it out with parquet, but kept everything else (Colossus, Dremel, Background reordering, metadata stored in Spanner etc) would it still be 10/30/50% worse or would it be an order of magnitude worse.

> Why was the above comment flagged?

It appears that relatively new accounts that post here are automatically flagged. I've seen it before.

Usually if I click on their specific comment and vouch for them, they get unflagged, but it didn't work this time.

Lame.

Re: How should you build a high-performance column store for the 2020s?

#26

Datastore of 2020s will be designed around an immutable log because it permits both strong consistency and horizontal scaling (like git). Once you're both distributed and consistent, the problems today's stores are architected around, go away. Your distributed queries can index the immutable log however they like. column-oriented, row-oriented, documents, time-oriented, graphs, immutability means you can do all of it…

You're confusing OLTP and OLAP, and it isn't even really relevant to the topic at hand. Column stores are mostly about how to layout the physical representation of data in a single node for read-mostly workloads on wide tables with selective filters and projections. The discussion of how distributed consistency may work is irrelevant here.

Re: How should you build a high-performance column store for the 2020s?

#27
I think one interesting project in the near future could be to try and build a column-oriented storage engine that's "good enough" for both OLAP and OLTP workloads.

The main precedent here is Spanner's Ressi storage engine, which, according to the most recent paper [1], uses a PAX-like format (with blocks arranged row-oriented, but values within a block are column-oriented, so kind of like Parquet) for on-disk data, but combines it with a traditional log-structured merge tree for writes and point queries.

[1] https://static.googleusercontent.com/media/research.google.c...

Re: How should you build a high-performance column store for the 2020s?

#29
post #15

Earlier quoted context omitted.

I was under the impression, based on its docs, that Datomic only supports processing transactions serially through a single transactor.

Both what you write and what I wrote are true. To scale writes you shard writes. This generally means running multiple databases (in any DBMS) The key insight is that Datomic can cross-query N databases as a first class concept, like a triple store. You can write a sophisticated relational query against Events and Photos and Instagram, as if they are one database (when in fact they are not). This works because Datomi…

What is the primary reason people choose Datomic? From reading the website, I get the impression that the append-only nature and time-travel features are a major selling point, but in other places its just the datalog and clojure interfaces. I'm sure it's a mix, but what brings people to the system to begin with?

Re: How should you build a high-performance column store for the 2020s?

#30
If I had to guess new capabilities chips will add in the 2020s, hardware-accelerated compression or compact encoding are near the top of the list. That could be anything from branch-free instructions to read/write varints to fully-self-contained (un)packer(s) you just point at some data and run. I'm most interested in something so fast as to be worth considering to replace fast software algos or to use in places we don't think about compressing at all now, though hardware accelerated zlib would obviously have applications too.

Some existing stabs in this direction include that some Samsung SoCs had a simple "MComp" memory compressor (https://github.com/XileForce/Vindicator-S6-Unified/blob/mast...), that the new Qualcomm Centriq chips use compression (https://3s81si1s5ygj3mzby34dq6qf-wpengine.netdna-ssl.com/wp-...), and that some IBM POWER CPUs have dedicated circuitry for memory compression (http://ibmsystemsmag.com/aix/administrator/lpar/ame-intro/). There's also hardware zlib offload, like Intel QuickAssist.

I'd expect more of this in the future because 1) space-is-speed is just a fundamental thing we deal with computing, 2) chips keep getting faster relative to RAM, 3) you already see lots of special-purpose instructions being added (crypto, strings, fancier vector stuff...) as it gets more expensive to improve general-purpose IPC. Maybe there's some additional value given the arrival of 3D XPoint and (probably) other future NVRAMs--would help you fit more on them without spending more time compressing than writing--but regardless, the trends seem to point to compression assists being interesting.

One reason I could turn out wrong is if the general-purpose facilities we have make software the best place to write compressors anyway, i.e., fast software packers get so good it becomes difficult to justify hardware assists. General-purpose low- and medium-compression algos like LZ4 and Zstd run pretty fast already, and we have even faster memory compressors (WKdm, Density). Of course, that's on big Intel cores; maybe special-purpose compressor hardware will continue to mostly be more interesting alongside smaller cores.

Post reply on HN