11 ms·

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

164 points by deafcalculus 9y ago

xoogler_thr 9y ago
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.
- joelwilsson 9y ago
  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 not exist in BigQuery today (as far as I know - definitely not as discussed in the source).
  - xoogler_thr 9y ago
    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++.
- posnet 9y ago
  [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.
  - oaijdsfoaijsf 9y ago
    It would have to depend on the dataset, right? For anyone who doesn't know what Capacitor is: https://cloud.google.com/blog/big-data/2016/04/inside-capacitor-bigquerys-next-generation-columnar-storage-format https://cloud.google.com/blog/big-data/2016/04/inside-capaci...
  - xoogler_thr 9y ago
    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.
  - Diederich 9y ago
    > 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.
- Joeri 9y ago
  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. I also wonder whether the industry is better off by having to cooperatively reinvent the google architecture. I doubt the hadoop ecosystem would have arisen had it been google code at the heart.
  - mikecb 9y ago
    Apache Beam, gRPC/protobuf, Kubernetes. There are examples besides Tensorflow.
    - jimktrains2 9y ago
      Not code but they do publish papers that contain decent detail.
WilsonPhillips 9y ago
I think incorporating a blockchain element could prove an interesting way to implement this in practice.
- deleted 9y ago
  [deleted]
dogruck 9y ago
Sure comes across as arrogant for Prof Abadi to remark: > I assume that the Arrow developers will eventually read my 2006 paper on compression in column-stores and expand their compression options to include other schemes which can be operated on directly (such as run-length-encoding and bit-vector compression). In this blog post, I don’t agree with: > Almost every single major data-processing platform that has emerged in the last decade has been either open source. That’s somewhat true by definition. OTOH, I also know most financial firms use proprietary solutions (which leverage open source components).
lima 9y ago
Yandex's recently open sourced ClickHouse[1] column store does some of these. It heavily relies on compression, data locality and SIMD instructions and supports external dictionaries for lookup. [1]: https://clickhouse.yandex/ https://clickhouse.yandex/
- posnet 9y ago
  I am always impressed with clickhouse, especially when it holds up against massive data processing systems, but running on a laptop http://tech.marksblogg.com/benchmarks.html http://tech.marksblogg.com/benchmarks.html
- spinco 9y ago
  HN discussion on ClickHouse from a few years ago: https://news.ycombinator.com/item?id=11908254 https://news.ycombinator.com/item?id=11908254
misterHN 9y ago
put data in text files, ASCII printable characters, one data point per line put data files in directory name data files after columns use ".data" filename extension for data files write a tool to create index files (append ".index" to the name of the input text file) that map record number to byte offset in data file If data files are all < 4GB, use a 32 bit unsigned integer to represent the byte offset in the index file Each index file is a packed array of 32 bit integers Write a tool to create length files ".length" that count the number of entries in a data file Generate .length files for all data files Use mmap to access index files Use C for all of the above This is for variable-length data values. Not every column will have these, making the .index files redundant in this case; the .index files should not be created in this case and program logic should support both uniform value length access and nonuniform value length access. The reason to prefer two access modes is to keep data from the .index files out of the cache when it is redundant. When all of this is done, the next thing to do is write a tool to test the cache characteristics on your processor by implementing sorting algorithms and testing their performance. Unless you are using a GPU (why?) all data your algorithm touches will go through every level of the cache hierarchy, forcing other data out. If possible, use a tool that reports hardware diagnostics. These tools may be provided by the processor vendor. Now, there is a trend to give the programmer control over cache behavior https://stackoverflow.com/questions/9544094/how-to-mark-some-memory-ranges-as-non-cacheable-from-c https://stackoverflow.com/questions/9544094/how-to-mark-some... I don't know if this is worth exploring or a wild goose chase. It may improve performance for some tasks, but it sounds a little strange for the programmer to tell the computer how to use the cache...shouldn't the operating system do this? Anyway, that's a start.
- posnet 9y ago
  This sounds almost identical to the datastore honeycomb.io built and describe in the talk https://www.youtube.com/watch?v=tr2KcekX2kk https://www.youtube.com/watch?v=tr2KcekX2kk
deleted 9y ago
[deleted]
dustingetz 9y ago
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, as a library in your application process http://www.datomic.com/ http://www.datomic.com/ - it's what you get when Facebook's graph datastore has a baby with immutability.
- SamReidHughes 9y ago
  You can't just say "immutable log" and then be done. You certainly don't want to have just one immutable log, because then unrelated operations, for example to different parts of a key space, have to "see" each other. If you go the route of Datomic, your writes can't outpace the one CPU that processes them. (Correct me if I'm wrong, I'm just reading its documentation.) Git, with a DAG history, is just eventual consistency.
  - dustingetz 9y ago
    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 share the same single-writer process delivering ACID. You do however, on the read side, need to have fluid queries across them all, as if they were one database. RDBMS can't do that, but Datomic can, and Git can too - consider submodules. Immutability is what makes it possible to shard like this without sacrificing query expressiveness, strong consistency or ACID (like every other distributed system that isn't accumulate only)
    - mej10 9y ago
      I was under the impression, based on its docs, that Datomic only supports processing transactions serially through a single transactor.
gopalv 9y ago
(man, I'd love to go work on this for three years, without worrying about a "customer" or "backwards compatability") > That is, if you have N distinct values, you can store them using ceil(log(N)/log(2)) bits Ideally you don't need to do ceil, if you had an low number like 5 items, then it looks like you need 3 bits to store it, but you can store it in 2.4 bits (just pack 10 values into 24 bits instead of 30). Getting distinct and repeated values by tearing apart data so that you can use these algorithms is something which I could use some papers to refer to. For instance, here's[1] what we're trying to do with Double encoding loops, but it still suffers from the problems of a car moving from 0.3 -> 0.2 location. [1] - http://bit.ly/2zt70iL http://bit.ly/2zt70iL
jaffee 9y ago
Pilosa, https://github.com/pilosa/pilosa https://github.com/pilosa/pilosa which is mentioned, is actually open source, and a relatively readable Go codebase if anyone is interested in what "an entire data engine on top of bit-vectors" looks like.
elvinyung 9y ago
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.com/en//pubs/archive/46103.pdf https://static.googleusercontent.com/media/research.google.c...
- redditaddict 9y ago
  "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 handle OLTP. OLAP queries perform exceptionally well due to the column oriented nature of the storage. Customer deployments are in the 100s of TBs and low PBs these days. Blows most open source software in terms of performance if you are willing to shell out the $. Source: I work at SAP.
  - elvinyung 9y ago
    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.
    - dustingetz 9y ago
      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
twotwotwo 9y ago
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/master/drivers/memory/exynos-mcomp.h https://github.com/XileForce/Vindicator-S6-Unified/blob/mast...), that the new Qualcomm Centriq chips use compression (https://3s81si1s5ygj3mzby34dq6qf-wpengine.netdna-ssl.com/wp-content/uploads/2017/08/qualcomm-amberwing-memory-compression.jpg 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/ 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.
rwmj 9y ago
Possibly naive question, but isn't an index (in a classical relational database) the same as a column store?
- setr 9y ago
  An index stores pointers to rows based on the column value; the values are still stored as rows though. So when you query on an indexed column, you'll have contiguous access on the index, but the rows themselves may be stored on disk based on a different column (so you'll could get the row pointers for a range query in one go from the index but fetching the rows would be random lookups). But if you want to view an entire row, its trivial, because the full row data is contiguous on disk. Column store groups the table values by the column, so the values of col A will be contigous, and col B will be contiguous, (but not pairwise!) but if you want to view the entire row, you'll probably have to do 2 lookups in random locations. But the range query on col A, selecting only col A, becomes a trivial fetch. Thats my understanding anyways
- asavinov 9y ago
  An index for a column-store and row-store is (conceptually) the same. Why is different is 1. How data is represented. A database is a collection of column objects. For example, it is easy to create a column or delete a column. 2. How data is being processed (queried). The engine processes columns as objected managed by the system
alberth 9y ago
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.
- azundo 9y ago
  Columnar stores are as much about the compression benefits as the physical layout on disk. The article goes through a bunch of different relevant compression strategies.
- londons_explore 9y ago
  Even SSD's are super slow compared to RAM. When you want to read a few bytes from millions of rows, an SSD has to decode an entire block of data for every read. Also, even with NVMe SSD's, there is a lot of operating system overhead associated with every read. Having layers of drivers to orchestrate the transfer of 2 bytes of data you wanted really slows it down...
- geocar 9y ago
  > 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. > 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. I'm not really sure this is true. Hard Drives have (for over a decade, probably longer) had logic that lies about the physical layout of the disk to the point where all I can believe about the linear block address is that the circuitry "believes" that likelihood software will ask for the next linear block address is higher than any other one. Further that, I imagine SSDs can probably make similar optimisations. The reason column-orientation helps is that it reduces the volume of data that needs reading. If you have a table with 100 columns in it, but a query that operates on 2, then a column-oriented database needs to read 2 things, while the row-oriented database either reads 100 things, or it interleaves reads of 2 things with skips of 98 things. It isn't difficult to believe that the circuitry needed to handle the former will outpace the circuitry needed to handle the latter for a long time.
manigandham 9y ago
Most of these techniques are already in production: Microsoft SQL Server has columnstore indexes and can even be combined with its in-memory tables. MemSQL has been doing this for years and v6 is incredibly fast, also combines in-memory row-stores. ClickHouse is very good if you don't mind more operations work. MariaDB has the ColumnStore storage engine, Postgre has the cstore_fdw extension. Vertica, Greenplum, Druid, etc. EventQL was an interesting project but abandoned now. AWS RedShift, Azure SQL Data Warehouse, Snowflake Data, Google BigQuery are the hosted options, with BQ being the most advanced with its vertical integration. If you want to operationalize Apache Arrow today, Dremio is built around it and works similar to Apache Drill and Spark to run distributed queries and joins across data sources.
- deleted 9y ago
  [deleted]
bboreham 9y ago
I wonder if the 2020s column store would outperform kdb, which was written in the 1990s with a UI from the 1950s.
- throwaway7645 9y ago
  I talked to someone recently who ran kdb using an SSD. Is that the standard approach?
  - bboreham 9y ago
    Whatever works, as much and as fast as you can afford. The kdb disk game is more about serial transfer rates and quantity.
- geocar 9y ago
  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 read two or three columns across ten billion rows -- it's hard to be much faster than kdb: 10 billion rows completes in 70msec on kdb, but Hadoop takes something like 30 seconds. The 2020 column store has to do a lot of work to even match kdb, but assuming it does that, and even ekes out a few extra percent of performance on these queries, there's another issue: 2. Most kdb programmers don't write this way. Sure some write their application in Java and send these queries over to the kdb "server" get the results, and do stuff with the results, etc., just like the application programmers that use Hadoop, but most kdb programmers don't. They just write their application in kdb. That means that there isn't an extra second or two delay while this chunky result set is sent over to another process. UDF/Stored Procedures/Foreign procedures are the rest of the world's solution for this problem, and they are massively under-utilised: Tooling like version control and testing of stored procedures just doesn't work as well, and I don't see any suggestion that's going to change in the next decade or so.
argimenes 9y ago
Not Invented Here, huh?

164 points by deafcalculus 9y ago

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.

joelwilsson 9y ago
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 not exist in BigQuery today (as far as I know - definitely not as discussed in the source).
- xoogler_thr 9y ago
  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++.
posnet 9y ago
[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.
- oaijdsfoaijsf 9y ago
  It would have to depend on the dataset, right? For anyone who doesn't know what Capacitor is: https://cloud.google.com/blog/big-data/2016/04/inside-capacitor-bigquerys-next-generation-columnar-storage-format https://cloud.google.com/blog/big-data/2016/04/inside-capaci...
- xoogler_thr 9y ago
  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.
- Diederich 9y ago
  > 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.
Joeri 9y ago
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. I also wonder whether the industry is better off by having to cooperatively reinvent the google architecture. I doubt the hadoop ecosystem would have arisen had it been google code at the heart.
- mikecb 9y ago
  Apache Beam, gRPC/protobuf, Kubernetes. There are examples besides Tensorflow.
  - jimktrains2 9y ago
    Not code but they do publish papers that contain decent detail.

WilsonPhillips 9y ago

I think incorporating a blockchain element could prove an interesting way to implement this in practice.

deleted 9y ago
[deleted]

dogruck 9y ago

Sure comes across as arrogant for Prof Abadi to remark: > I assume that the Arrow developers will eventually read my 2006 paper on compression in column-stores and expand their compression options to include other schemes which can be operated on directly (such as run-length-encoding and bit-vector compression). In this blog post, I don’t agree with: > Almost every single major data-processing platform that has emerged in the last decade has been either open source. That’s somewhat true by definition. OTOH, I also know most financial firms use proprietary solutions (which leverage open source components).

lima 9y ago

Yandex's recently open sourced ClickHouse[1] column store does some of these. It heavily relies on compression, data locality and SIMD instructions and supports external dictionaries for lookup. [1]: https://clickhouse.yandex/ https://clickhouse.yandex/

posnet 9y ago
I am always impressed with clickhouse, especially when it holds up against massive data processing systems, but running on a laptop http://tech.marksblogg.com/benchmarks.html http://tech.marksblogg.com/benchmarks.html
spinco 9y ago
HN discussion on ClickHouse from a few years ago: https://news.ycombinator.com/item?id=11908254 https://news.ycombinator.com/item?id=11908254

misterHN 9y ago

put data in text files, ASCII printable characters, one data point per line put data files in directory name data files after columns use ".data" filename extension for data files write a tool to create index files (append ".index" to the name of the input text file) that map record number to byte offset in data file If data files are all < 4GB, use a 32 bit unsigned integer to represent the byte offset in the index file Each index file is a packed array of 32 bit integers Write a tool to create length files ".length" that count the number of entries in a data file Generate .length files for all data files Use mmap to access index files Use C for all of the above This is for variable-length data values. Not every column will have these, making the .index files redundant in this case; the .index files should not be created in this case and program logic should support both uniform value length access and nonuniform value length access. The reason to prefer two access modes is to keep data from the .index files out of the cache when it is redundant. When all of this is done, the next thing to do is write a tool to test the cache characteristics on your processor by implementing sorting algorithms and testing their performance. Unless you are using a GPU (why?) all data your algorithm touches will go through every level of the cache hierarchy, forcing other data out. If possible, use a tool that reports hardware diagnostics. These tools may be provided by the processor vendor. Now, there is a trend to give the programmer control over cache behavior https://stackoverflow.com/questions/9544094/how-to-mark-some-memory-ranges-as-non-cacheable-from-c https://stackoverflow.com/questions/9544094/how-to-mark-some... I don't know if this is worth exploring or a wild goose chase. It may improve performance for some tasks, but it sounds a little strange for the programmer to tell the computer how to use the cache...shouldn't the operating system do this? Anyway, that's a start.

posnet 9y ago
This sounds almost identical to the datastore honeycomb.io built and describe in the talk https://www.youtube.com/watch?v=tr2KcekX2kk https://www.youtube.com/watch?v=tr2KcekX2kk

deleted 9y ago

[deleted]

dustingetz 9y ago

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, as a library in your application process http://www.datomic.com/ http://www.datomic.com/ - it's what you get when Facebook's graph datastore has a baby with immutability.

SamReidHughes 9y ago
You can't just say "immutable log" and then be done. You certainly don't want to have just one immutable log, because then unrelated operations, for example to different parts of a key space, have to "see" each other. If you go the route of Datomic, your writes can't outpace the one CPU that processes them. (Correct me if I'm wrong, I'm just reading its documentation.) Git, with a DAG history, is just eventual consistency.
- dustingetz 9y ago
  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 share the same single-writer process delivering ACID. You do however, on the read side, need to have fluid queries across them all, as if they were one database. RDBMS can't do that, but Datomic can, and Git can too - consider submodules. Immutability is what makes it possible to shard like this without sacrificing query expressiveness, strong consistency or ACID (like every other distributed system that isn't accumulate only)
  - mej10 9y ago
    I was under the impression, based on its docs, that Datomic only supports processing transactions serially through a single transactor.

gopalv 9y ago

(man, I'd love to go work on this for three years, without worrying about a "customer" or "backwards compatability") > That is, if you have N distinct values, you can store them using ceil(log(N)/log(2)) bits Ideally you don't need to do ceil, if you had an low number like 5 items, then it looks like you need 3 bits to store it, but you can store it in 2.4 bits (just pack 10 values into 24 bits instead of 30). Getting distinct and repeated values by tearing apart data so that you can use these algorithms is something which I could use some papers to refer to. For instance, here's[1] what we're trying to do with Double encoding loops, but it still suffers from the problems of a car moving from 0.3 -> 0.2 location. [1] - http://bit.ly/2zt70iL http://bit.ly/2zt70iL

jaffee 9y ago

Pilosa, https://github.com/pilosa/pilosa https://github.com/pilosa/pilosa which is mentioned, is actually open source, and a relatively readable Go codebase if anyone is interested in what "an entire data engine on top of bit-vectors" looks like.

elvinyung 9y ago

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.com/en//pubs/archive/46103.pdf https://static.googleusercontent.com/media/research.google.c...

redditaddict 9y ago
"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 handle OLTP. OLAP queries perform exceptionally well due to the column oriented nature of the storage. Customer deployments are in the 100s of TBs and low PBs these days. Blows most open source software in terms of performance if you are willing to shell out the $. Source: I work at SAP.
- elvinyung 9y ago
  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.
  - dustingetz 9y ago
    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

twotwotwo 9y ago

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/master/drivers/memory/exynos-mcomp.h https://github.com/XileForce/Vindicator-S6-Unified/blob/mast...), that the new Qualcomm Centriq chips use compression (https://3s81si1s5ygj3mzby34dq6qf-wpengine.netdna-ssl.com/wp-content/uploads/2017/08/qualcomm-amberwing-memory-compression.jpg 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/ 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.

rwmj 9y ago

Possibly naive question, but isn't an index (in a classical relational database) the same as a column store?

setr 9y ago
An index stores pointers to rows based on the column value; the values are still stored as rows though. So when you query on an indexed column, you'll have contiguous access on the index, but the rows themselves may be stored on disk based on a different column (so you'll could get the row pointers for a range query in one go from the index but fetching the rows would be random lookups). But if you want to view an entire row, its trivial, because the full row data is contiguous on disk. Column store groups the table values by the column, so the values of col A will be contigous, and col B will be contiguous, (but not pairwise!) but if you want to view the entire row, you'll probably have to do 2 lookups in random locations. But the range query on col A, selecting only col A, becomes a trivial fetch. Thats my understanding anyways
asavinov 9y ago
An index for a column-store and row-store is (conceptually) the same. Why is different is 1. How data is represented. A database is a collection of column objects. For example, it is easy to create a column or delete a column. 2. How data is being processed (queried). The engine processes columns as objected managed by the system

alberth 9y ago

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.

azundo 9y ago
Columnar stores are as much about the compression benefits as the physical layout on disk. The article goes through a bunch of different relevant compression strategies.
londons_explore 9y ago
Even SSD's are super slow compared to RAM. When you want to read a few bytes from millions of rows, an SSD has to decode an entire block of data for every read. Also, even with NVMe SSD's, there is a lot of operating system overhead associated with every read. Having layers of drivers to orchestrate the transfer of 2 bytes of data you wanted really slows it down...
geocar 9y ago
> 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. > 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. I'm not really sure this is true. Hard Drives have (for over a decade, probably longer) had logic that lies about the physical layout of the disk to the point where all I can believe about the linear block address is that the circuitry "believes" that likelihood software will ask for the next linear block address is higher than any other one. Further that, I imagine SSDs can probably make similar optimisations. The reason column-orientation helps is that it reduces the volume of data that needs reading. If you have a table with 100 columns in it, but a query that operates on 2, then a column-oriented database needs to read 2 things, while the row-oriented database either reads 100 things, or it interleaves reads of 2 things with skips of 98 things. It isn't difficult to believe that the circuitry needed to handle the former will outpace the circuitry needed to handle the latter for a long time.

manigandham 9y ago

Most of these techniques are already in production: Microsoft SQL Server has columnstore indexes and can even be combined with its in-memory tables. MemSQL has been doing this for years and v6 is incredibly fast, also combines in-memory row-stores. ClickHouse is very good if you don't mind more operations work. MariaDB has the ColumnStore storage engine, Postgre has the cstore_fdw extension. Vertica, Greenplum, Druid, etc. EventQL was an interesting project but abandoned now. AWS RedShift, Azure SQL Data Warehouse, Snowflake Data, Google BigQuery are the hosted options, with BQ being the most advanced with its vertical integration. If you want to operationalize Apache Arrow today, Dremio is built around it and works similar to Apache Drill and Spark to run distributed queries and joins across data sources.

deleted 9y ago
[deleted]

bboreham 9y ago

I wonder if the 2020s column store would outperform kdb, which was written in the 1990s with a UI from the 1950s.

throwaway7645 9y ago
I talked to someone recently who ran kdb using an SSD. Is that the standard approach?
- bboreham 9y ago
  Whatever works, as much and as fast as you can afford. The kdb disk game is more about serial transfer rates and quantity.
geocar 9y ago
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 read two or three columns across ten billion rows -- it's hard to be much faster than kdb: 10 billion rows completes in 70msec on kdb, but Hadoop takes something like 30 seconds. The 2020 column store has to do a lot of work to even match kdb, but assuming it does that, and even ekes out a few extra percent of performance on these queries, there's another issue: 2. Most kdb programmers don't write this way. Sure some write their application in Java and send these queries over to the kdb "server" get the results, and do stuff with the results, etc., just like the application programmers that use Hadoop, but most kdb programmers don't. They just write their application in kdb. That means that there isn't an extra second or two delay while this chunky result set is sent over to another process. UDF/Stored Procedures/Foreign procedures are the rest of the world's solution for this problem, and they are massively under-utilised: Tooling like version control and testing of stored procedures just doesn't work as well, and I don't see any suggestion that's going to change in the next decade or so.

argimenes 9y ago

Not Invented Here, huh?