6 ms·

This is a good paper and I appreciate the holistic focus on cache efficiency, an area where multiple orders of magnitude of performance improvement are often ea

This is a good paper and I appreciate the holistic focus on cache efficiency, an area where multiple orders of magnitude of performance improvement are often easily attainable compared to many common implementations. However, it also highlights the gap between academic literature and the state-of-the-art in database engine design. For example, adaptive succinct indexing structures have been used for at least a decade in closed source databases. Structures similar to the ideas presented in the paper have been reduced to practice in real systems for a long time. Last month I delivered yet another database engine, benchmarked against the best open source comparables, which provides a rough but concrete example of the gap: The designed memory:storage ratio was 1:1000, an order of magnitude higher than even the 1:100 ratio mentioned as aggressive in the paper. In fairness, my prior systems were designed much closer to 1:100 ratio and it used new CS research to significantly extend the ratio without materially sacrificing performance. For data models with fairly complex indexing requirements, insertion performance was >100x(!) the best open source comparables. A large part of this performance is due to dramatic improvements in cache efficiency that are not even particularly novel -- the gains attributable to improved cache efficiency in the paper are eminently believable. The data-to-index ratio in the above is around a million-to-one, small enough to fit in CPU cache for many TB scale data models. The high data-to-index ratio is largely attributable to using search structures that forego total order and balancing, which enables dramatic improvements in succinctness with minimal reductions in selectivity. The other major contributor to performance is scheduler design, which wasn't really touched on in the paper and is largely ignored entirely in open source databases. tl;dr: current open source database engine designs leave a massive amount of performance on the table due to very poor cache efficiency, and this paper correctly touches on some of the ways this is materially improved in closed source database engines.

willvarfar 7y ago
Can you give names of closed-source database engines that have these kinds of performance improvements? I mean, the mainstream RDBMS like Oracle, DB2 etc don't seem to be ahead of the open source databases; they are all stagnant too!
- einpoklum 7y ago
  Actian Vector, formerly Vectorwise: https://docs.actian.com/vector/5.0/index.html https://docs.actian.com/vector/5.0/index.html From the "vectorized columnar execution, operator at a time" school. HyperDB: https://hyper-db.de/ https://hyper-db.de/ That's from the "row-oriented execution, query plan JIT compilation" school.
  - dgacmu 7y ago
    The hyper-db folks do great work. Indeed, Huanchen collaborated with Viktor Leis (one of the senior folks on HyPer) on the SuRF "Succinct Range Filter" (think Bloom filter but for range queries) work: http://www.cs.cmu.edu/~huanche1/publications/surf_paper.pdf http://www.cs.cmu.edu/~huanche1/publications/surf_paper.pdf and github: https://github.com/efficient/SuRF https://github.com/efficient/SuRF and both Viktor and Thomas Neumann's work in this area is fantastic and everyone should go read it. :) The code for several of Huanchen's projects is available in our group's github repo: https://github.com/efficient/ https://github.com/efficient/ The order-preserving compression work outlined in his thesis will be appearing soon at SIGMOD, but there's no need to wait for it, since it's roughly the same in both. We'll get the source to that released by the time of SIGMOD.
- jandrewrogers 7y ago
  Databases are severely constrained by the architecture choices from when they were designed, you can't back port modern database architecture and computer science to e.g. an Oracle or DB2. To integrate new computer science advances you often need to write a new kernel from first principles. I sunset the designs I license to companies every several years, starting over from a clean sheet. Most new high-performance database engines are intended to give the developing company a new qualitative uplift in capability, scale, or operational efficiency. No one sells public licenses these days. You've heard of the organizations that are buying building these semi-bespoke database engines but they are intended for internal use only. The reason no one sells these capabilities as a product anymore is pragmatic: it is extremely expensive to design a database engine for general public consumption and the economics are difficult to justify as an investment. But many large companies are willing to pay many millions of dollars for a narrowly focused database capabilities, and the reduced scope makes the development cost more palatable.
adamretter 7y ago
Is your benchmark and data published as a paper or article somewhere. I would be interested to see it
- jandrewrogers 7y ago
  Unfortunately, this database engine implementation (like virtually all I work on) was for a customer. The details are not public.
ignoramous 7y ago
Thanks. > ...adaptive succinct indexing structures We've been optimising for low-memory and compact / succinct data-structures have been super impactful (especially, static succinct Radix Tree and Data Sketches like CountMinSketch). Apart from the excellent sdsl-lite [0], roaring-bitmaps [1], apache data-sketches [2], and pizza-chilli [3], what are other resources that you recommend we take a look? > ...storage ratio was 1:1000, an order of magnitude This is insane: Is it due to compression techniques or... Could you please point a few reasons why the gap is this high? > The other major contributor to performance is scheduler design... Out of curiosity: Any pointers to papers that we can take a look at? --- [0] https://github.com/simongog/sdsl-lite https://github.com/simongog/sdsl-lite [1] https://roaringbitmap.org/ https://roaringbitmap.org/ [2] https://datasketches.apache.org/ https://datasketches.apache.org/ [3] http://pizzachili.dcc.uchile.cl/ http://pizzachili.dcc.uchile.cl/
- jandrewrogers 7y ago
  Physical storage density per server is driving this. You can fit upward of a petabyte of physical storage in a server and there are many applications where this makes sense. RAM is still on the order of a terabyte, and expensive. Everything else follows from trying to use all of this physical storage effectively. Needless to say, when working with this much storage you aren't installing a filesystem on it. When working with storage this dense, write performance matters immensely if you can't wait (literally) a year to index your data model. Scaling write throughput on indexing structures has a problem of write sparsity: given a fixed amount of cache, there is a scaling point where virtually every single insert requires at least one page fault. Indexing structures like B+Trees that consume large amounts of space will not only push the data pages out of cache, the index itself may no longer fit into cache at high densities. Every database exhibits this characteristic write cliff with indexing structures but the cache:data ratio where this occurs varies with indexing algorithm design. (This also impacts query performance but we'll ignore that for now.) Succinct indexing structures can eliminate the competition with data pages for cache space. Write sparsity is intrinsic though, so this only lets you maintain write performance for maybe another 1-2 orders of magnitude. Eventually the set of actively written data pages will exceed the size of the cache and write throughput will drop precipitously before leveling off. Being able to index tens of terabytes of data at wire speed is much better than typical but at least an order of magnitude short of what is desirable for a petabyte of storage in a single server. Ideally, you'd want the flat write throughput to extend out to the end of your storage, which means extending the write cliff at least another order of magnitude. There is not an obvious way of doing this without adversely impacting performance in other unacceptable ways. I started researching this problem a few years ago from a very different direction that does not require directly improving cache efficiency per se, since that is essentially tapped out as a strategy. Most software engineers don't understand the nature of caches as abstract mathematical objects but there are some interesting NP-Hard problems surrounding the behavior of caches that we essentially ignore for database architecture purposes because (1) NP-Hard and (2) exploitable efficient approximations are incompatible with many common database architectures in any case. I've worked through a couple new algorithm prototypes that attack these properties to significantly extend the performance party for even higher storage densities. I'm just starting to design kernels that are purpose-built to take advantage of this research but the heavy lifting is done in the schedulers. Yes, I do this kind of thing for fun.

willvarfar 7y ago

Can you give names of closed-source database engines that have these kinds of performance improvements? I mean, the mainstream RDBMS like Oracle, DB2 etc don't seem to be ahead of the open source databases; they are all stagnant too!

einpoklum 7y ago
Actian Vector, formerly Vectorwise: https://docs.actian.com/vector/5.0/index.html https://docs.actian.com/vector/5.0/index.html From the "vectorized columnar execution, operator at a time" school. HyperDB: https://hyper-db.de/ https://hyper-db.de/ That's from the "row-oriented execution, query plan JIT compilation" school.
- dgacmu 7y ago
  The hyper-db folks do great work. Indeed, Huanchen collaborated with Viktor Leis (one of the senior folks on HyPer) on the SuRF "Succinct Range Filter" (think Bloom filter but for range queries) work: http://www.cs.cmu.edu/~huanche1/publications/surf_paper.pdf http://www.cs.cmu.edu/~huanche1/publications/surf_paper.pdf and github: https://github.com/efficient/SuRF https://github.com/efficient/SuRF and both Viktor and Thomas Neumann's work in this area is fantastic and everyone should go read it. :) The code for several of Huanchen's projects is available in our group's github repo: https://github.com/efficient/ https://github.com/efficient/ The order-preserving compression work outlined in his thesis will be appearing soon at SIGMOD, but there's no need to wait for it, since it's roughly the same in both. We'll get the source to that released by the time of SIGMOD.
jandrewrogers 7y ago
Databases are severely constrained by the architecture choices from when they were designed, you can't back port modern database architecture and computer science to e.g. an Oracle or DB2. To integrate new computer science advances you often need to write a new kernel from first principles. I sunset the designs I license to companies every several years, starting over from a clean sheet. Most new high-performance database engines are intended to give the developing company a new qualitative uplift in capability, scale, or operational efficiency. No one sells public licenses these days. You've heard of the organizations that are buying building these semi-bespoke database engines but they are intended for internal use only. The reason no one sells these capabilities as a product anymore is pragmatic: it is extremely expensive to design a database engine for general public consumption and the economics are difficult to justify as an investment. But many large companies are willing to pay many millions of dollars for a narrowly focused database capabilities, and the reduced scope makes the development cost more palatable.

adamretter 7y ago

Is your benchmark and data published as a paper or article somewhere. I would be interested to see it

jandrewrogers 7y ago
Unfortunately, this database engine implementation (like virtually all I work on) was for a customer. The details are not public.

ignoramous 7y ago

Thanks. > ...adaptive succinct indexing structures We've been optimising for low-memory and compact / succinct data-structures have been super impactful (especially, static succinct Radix Tree and Data Sketches like CountMinSketch). Apart from the excellent sdsl-lite [0], roaring-bitmaps [1], apache data-sketches [2], and pizza-chilli [3], what are other resources that you recommend we take a look? > ...storage ratio was 1:1000, an order of magnitude This is insane: Is it due to compression techniques or... Could you please point a few reasons why the gap is this high? > The other major contributor to performance is scheduler design... Out of curiosity: Any pointers to papers that we can take a look at? --- [0] https://github.com/simongog/sdsl-lite https://github.com/simongog/sdsl-lite [1] https://roaringbitmap.org/ https://roaringbitmap.org/ [2] https://datasketches.apache.org/ https://datasketches.apache.org/ [3] http://pizzachili.dcc.uchile.cl/ http://pizzachili.dcc.uchile.cl/

jandrewrogers 7y ago
Physical storage density per server is driving this. You can fit upward of a petabyte of physical storage in a server and there are many applications where this makes sense. RAM is still on the order of a terabyte, and expensive. Everything else follows from trying to use all of this physical storage effectively. Needless to say, when working with this much storage you aren't installing a filesystem on it. When working with storage this dense, write performance matters immensely if you can't wait (literally) a year to index your data model. Scaling write throughput on indexing structures has a problem of write sparsity: given a fixed amount of cache, there is a scaling point where virtually every single insert requires at least one page fault. Indexing structures like B+Trees that consume large amounts of space will not only push the data pages out of cache, the index itself may no longer fit into cache at high densities. Every database exhibits this characteristic write cliff with indexing structures but the cache:data ratio where this occurs varies with indexing algorithm design. (This also impacts query performance but we'll ignore that for now.) Succinct indexing structures can eliminate the competition with data pages for cache space. Write sparsity is intrinsic though, so this only lets you maintain write performance for maybe another 1-2 orders of magnitude. Eventually the set of actively written data pages will exceed the size of the cache and write throughput will drop precipitously before leveling off. Being able to index tens of terabytes of data at wire speed is much better than typical but at least an order of magnitude short of what is desirable for a petabyte of storage in a single server. Ideally, you'd want the flat write throughput to extend out to the end of your storage, which means extending the write cliff at least another order of magnitude. There is not an obvious way of doing this without adversely impacting performance in other unacceptable ways. I started researching this problem a few years ago from a very different direction that does not require directly improving cache efficiency per se, since that is essentially tapped out as a strategy. Most software engineers don't understand the nature of caches as abstract mathematical objects but there are some interesting NP-Hard problems surrounding the behavior of caches that we essentially ignore for database architecture purposes because (1) NP-Hard and (2) exploitable efficient approximations are incompatible with many common database architectures in any case. I've worked through a couple new algorithm prototypes that attack these properties to significantly extend the performance party for even higher storage densities. I'm just starting to design kernels that are purpose-built to take advantage of this research but the heavy lifting is done in the schedulers. Yes, I do this kind of thing for fun.