Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

lemire.me

Post reply on HN
Print view View original

61–70 of 73 posts

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

#61

Post by dustingetz »

noahdesu wrote: post #59
dustingetz wrote: post #56

Earlier quoted context omitted.

Datomic is my default choice for any data processing software (which is almost everything). Immutability in-and-of-itself is not the selling point. Consider why everyone moved from CVS/SVN to Git/dvcs. The number of people who moved to git then and said "man I really wish I could go back to SVN" is approximately zero. Immutability isn't why. Git is just better at everything, that's why. Immutability is the "how". I d…

Thanks for the explanation, and I definitely agree with all your points. The reason I ask is that over the past year or so, we have been hacking on a little side project that maps a copy-on-write tree to a distributed shared log ( https://nwat.io/blog/2016/08/02/introduction-to-the-zlog-tra... ). This design effectively produces an append-only database with transactions (similar to the rocksdb interface), and means t…

A lot of stuff in those links that I'm not familiar with. I'd expect challenges around what will happen when the log doesn't fit in memory? What if even the index you need doesn't fit in memory? If I understand, zlog is key-value-time, so I'm not sure what type of queries are interesting on that. Datomic is essentially a triple store with a time dimension so it can do what triple stores do. What do you think the use cases are for a key-value-time store?

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

#62

Post by noahdesu »

dustingetz wrote: post #61
noahdesu wrote: post #59

Earlier quoted context omitted.

Thanks for the explanation, and I definitely agree with all your points. The reason I ask is that over the past year or so, we have been hacking on a little side project that maps a copy-on-write tree to a distributed shared log ( https://nwat.io/blog/2016/08/02/introduction-to-the-zlog-tra... ). This design effectively produces an append-only database with transactions (similar to the rocksdb interface), and means t…

A lot of stuff in those links that I'm not familiar with. I'd expect challenges around what will happen when the log doesn't fit in memory? What if even the index you need doesn't fit in memory? If I understand, zlog is key-value-time, so I'm not sure what type of queries are interesting on that. Datomic is essentially a triple store with a time dimension so it can do what triple stores do. What do you think the use…

The log is mapped onto a distributed storage system, so fitting it in memory isn't a concern, though effective caching is important. The index / database also doesn't need to fit into memory. We cap memory utilization and resolve pointers within the index down into the storage system. Again, caching is important.

If I understand Datomic correctly, I can think of the time dimension in the triple store as a sequence of transactions each of which produces a new state. How that maps onto real storage is flexible (Datomic supports a number of backends which don't explicitly support the notion of immutable database).

So what would a key-value-time store be useful for? Conceptually it seems that if Datomic triples are mapped onto the key-value database then time in Datomic becomes transactions over the log. So one area of interest is as a database backend for Datomic that is physically designed to be immutable. There is a lot of hand waving, and Datomic has a large number of optimizations. Thanks for answering some of those questions about Datomic. It's a really fascinating system.

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

#63

Post by dustingetz »

noahdesu wrote: post #62
dustingetz wrote: post #61

Earlier quoted context omitted.

A lot of stuff in those links that I'm not familiar with. I'd expect challenges around what will happen when the log doesn't fit in memory? What if even the index you need doesn't fit in memory? If I understand, zlog is key-value-time, so I'm not sure what type of queries are interesting on that. Datomic is essentially a triple store with a time dimension so it can do what triple stores do. What do you think the use…

The log is mapped onto a distributed storage system, so fitting it in memory isn't a concern, though effective caching is important. The index / database also doesn't need to fit into memory. We cap memory utilization and resolve pointers within the index down into the storage system. Again, caching is important. If I understand Datomic correctly, I can think of the time dimension in the triple store as a sequence of…

My questions were in the context of effective caching in the query process, sorry that wasn't clear. A process on a single machine somewhere has to get enough of the indexes and data into memory to answer questions about it. Though I guess there are other types of queries you might want to do, like streamy mapreduce type stuff that doesn't need the whole log.

I will have to think about if a key-value-time storage backend would have any implications in Datomic. One thing Datomic Pro doesn't have is low-cost database clones through structure sharing, and it doesn't make sense to me why.

Here is a description of some storage problems that arise with large Datomic databases, though it's not clear to me if ZLog can help with this http://www.dustingetz.com/ezpyZXF1ZXN0LXBhcmFtcyB7OmVudGl0eS..., >

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

#64

Post by jimktrains2 »

mikecb wrote: post #52
Joeri wrote: post #39

Earlier quoted context omitted.

It is frustrating that google is always 5 to 10 years ahead of everyone else but they never open source their back-end technologies (except recently with the ML stuff). The whole reason hadoop exists is because google only released whitepapers (which was good) but not code. I wonder whether google really benefits by this strategy, given that they have to be an ecosystem instead of benefitting from being a part of one…

Apache Beam, gRPC/protobuf, Kubernetes. There are examples besides Tensorflow.

Not code but they do publish papers that contain decent detail.

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

#65

Post by geocar »

dozzie wrote: post #54
geocar wrote: post #43

Earlier quoted context omitted.

Unlikely. Two reasons are at the top of my mind: 1. The current best efforts in benchmarking are focusing on queries that "look" similar, and yet kdb is still 400x faster than Hadoop for those queries. For example: select avg size by sym,time.hh from trade where date=d,sym in S SELECT sym,HOUR(time),AVG(size) FROM trade NATURAL JOIN s WHERE date=d GROUP BY sym,HOUR(time); To answer this question, the database has to…

> it's hard to be much faster than kdb: 10 billion rows completes in 70msec on kdb, but Hadoop takes something like 30 seconds. Indeed, it's hard for exhaustive search beat index lookup.

> it's hard for exhaustive search beat index lookup.

kdb isn't using any indexes for this query.

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

#66

Post by dustingetz »

elvinyung wrote: post #60
redditaddict wrote: post #55

Earlier quoted context omitted.

"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." SAP Hana is an example of a system that fits into this category. This isn't new either and has been existing since the 90s. Sybase IQ (which SAP acquired) was the first commercially successful columnar database. They have an in-memory row engine to hand…

Oh, I don't mean a database frontend that can handle both OLTP and OLAP workloads, usually by having some kind of OLAP column-store and some kind of OLTP main memory row-store. I know there's a lot of those (not only HANA, but also MemSQL, SQL Server, etc.) The fun thing to try and imagine here is having literally the same physical data format that works for both kinds of workloads.

You actually don't need to have the same storage data layout if you use a time series as a starting point; because you can maintain different data layouts in parallel, and the time dimension permits strong consistency across them all.

If this is what you mean by a "database frontend", I am really confused as to why you object to this?

I think this property of time series is going to prove very important in the 2020s

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

#67

Post by noahdesu »

dustingetz wrote: post #63
noahdesu wrote: post #62

Earlier quoted context omitted.

The log is mapped onto a distributed storage system, so fitting it in memory isn't a concern, though effective caching is important. The index / database also doesn't need to fit into memory. We cap memory utilization and resolve pointers within the index down into the storage system. Again, caching is important. If I understand Datomic correctly, I can think of the time dimension in the triple store as a sequence of…

My questions were in the context of effective caching in the query process, sorry that wasn't clear. A process on a single machine somewhere has to get enough of the indexes and data into memory to answer questions about it. Though I guess there are other types of queries you might want to do, like streamy mapreduce type stuff that doesn't need the whole log. I will have to think about if a key-value-time storage bac…

> A process on a single machine somewhere has to get enough of the indexes and data into memory to answer questions about it.

This common challenge is perhaps magnified in systems that have deep storage indexes. For example, the link you posted seems to suggest that queries in Datomic may have cache misses that require pointer chasing down into storage, adding latency. Depending on where that latency cost is eaten, it could have a lot of side effects (e.g. long running query vs reducing transaction throughput).

This problem is likely exacerbated in the key-value store running on zlog because the red-black tree can become quite tall. Aggressive, optimistic caching on the db nodes, and server-side pointer chasing helps. It's definitely an issue.

I don't know anything about Datomic internals, so disclaimer, I'm only speculating about why Datomic doesn't have low cost clones: which is that the underlying storage solution isn't inherently copy-on-write. That is, Datomic emulates this so when a clone is made there isn't an easy metadata change that creates the logical clone.

Despite the lack of features etc in the kv-store running on zlog, database snapshots and clones are both the same cost of updating the root pointer of the tree.

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

#68

Post by [deleted] »

dustingetz wrote: post #66
elvinyung wrote: post #60

Earlier quoted context omitted.

Oh, I don't mean a database frontend that can handle both OLTP and OLAP workloads, usually by having some kind of OLAP column-store and some kind of OLTP main memory row-store. I know there's a lot of those (not only HANA, but also MemSQL, SQL Server, etc.) The fun thing to try and imagine here is having literally the same physical data format that works for both kinds of workloads.

You actually don't need to have the same storage data layout if you use a time series as a starting point; because you can maintain different data layouts in parallel, and the time dimension permits strong consistency across them all. If this is what you mean by a "database frontend", I am really confused as to why you object to this? I think this property of time series is going to prove very important in the 2020s

[deleted]

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

#69

Post by elvinyung »

dustingetz wrote: post #66
elvinyung wrote: post #60

Earlier quoted context omitted.

Oh, I don't mean a database frontend that can handle both OLTP and OLAP workloads, usually by having some kind of OLAP column-store and some kind of OLTP main memory row-store. I know there's a lot of those (not only HANA, but also MemSQL, SQL Server, etc.) The fun thing to try and imagine here is having literally the same physical data format that works for both kinds of workloads.

You actually don't need to have the same storage data layout if you use a time series as a starting point; because you can maintain different data layouts in parallel, and the time dimension permits strong consistency across them all. If this is what you mean by a "database frontend", I am really confused as to why you object to this? I think this property of time series is going to prove very important in the 2020s

Again, I don't care about distributed consistency here, nor is it mutually exclusive with what I'm talking about.

The question we're trying to answer is whether there exists at all a storage engine, at the scope of a single node (obviously generalizable/scalable), that can fit all use cases well. Once you figure out the answer to that, obviously having one storage engine is simpler than having two storage engines.

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

#70

Post by SamReidHughes »

geocar wrote: post #44
alberth wrote: post #32

Are column-store databases relevant on SSD/NVME? I ask because on a physical medium like hard disk, storing data on physical disk in column orientation can make a significant improvement to read operations. But with SSD/NVME, you don’t have to worry about the inherent slowness of physical platters that exist in hard disk.

> Are column-store databases relevant on SSD/NVME? Yes. SSD generally has lower latency for responses. While sending data (throughput) is similar, the operating system doesn't ask for all of the blocks of a file at once -- even if you read(fd,buf,size) -- because other processes might ask for other blocks in the meantime. An IO schedular is making decisions, and that latency helps turn around those decisions faster.…

Hard drives exhibit the straightforward performance that you'd expect from block addresses linearly increasing around the circle according to all the experiments I've done.
Post reply on HN