8 ms·

Memory-Efficient Search Trees for Database Management Systems [pdf]

251 points by ngaut 7y ago

willvarfar 7y ago
A lot to digest. Presumably the compression schemes outlined in the paper would benefit columns generally, and not just keys, and would have a positive impact on row-size which would in turn benefit general performance? One short-string-compression-library to compare with might be https://github.com/antirez/smaz https://github.com/antirez/smaz by the Antirez, the author of redis. In the last decade Tokudb and then MyRocks showed how to do a fast storage engine for data too big to fit in traditional RDBMS. They are multi-level, they do page-level compression etc. And yet there is still so many easy wins yet to be had. Generally, databases are completely inefficient and there is just so much low-hanging fruit; if the team size working on e.g. myrocks could be doubled, and tasked with looking at the inefficiencies in the server as well as the storage engine, things might change. I have a list in my head of the various really-promising-ideas that databases don't actually do: * linux doesn't have a syscall batching system, but if it did, the number of context switches would be cut down dramatically. Research in 2010 https://www.usenix.org/legacy/events/osdi10/tech/full_papers/Soares.pdf https://www.usenix.org/legacy/events/osdi10/tech/full_papers... proved this and it wouldn't just be databases that benefit. These days context switching is more expensive than ever. * database engines all use blocking io. Finally io_uring offers workable async io and that would benefit database storage engines immensely. See https://fosdem.org/2020/schedule/event/rust_techniques_sled/ https://fosdem.org/2020/schedule/event/rust_techniques_sled/ * tokudb showed that simply not tracking the affected row count could speed things up massively (tokudb called it NOAR) * query engines often don't handle things that a few more lines of code would handle efficiently. I've got some tables with big compound keys and often do prefix searches in them, and why isn't mysql evaluating constraints that it can against the other columns in the key before dereferencing the row? Arrgh. Dumb dumb dumb. Etc.
- qaq 7y ago
  "database engines all use blocking io" Well sled is using io_uring
  - samatman 7y ago
    probably why that paragraph had a link to a video titled "sled and rio: modern database engineering with io_uring"...
    - qaq 7y ago
      which was my point :)
  - deleted 7y ago
    [deleted]
  - fnord123 7y ago
    https://github.com/facebook/rocksdb/pull/5881 https://github.com/facebook/rocksdb/pull/5881 I thought I saw a PR fly by for mysql but I can't find it now so maybe I was imagining things.
- the8472 7y ago
  > linux doesn't have a syscall batching system Well, you already mention io_uring. That's your syscall batching system. It doesn't cover all existing syscalls because not everything is safe to do asynchronously.
  - willvarfar 7y ago
    Yes, I'd like both! Asynchronous io_uring is good for things that take a lot of time, e.g. io. Its really just a queue between the user-space and kernel threads. But it doesn't replace just making a synchronous syscall for small things e.g. stating files etc. A lot of those syscalls are called in quick succession, often with no logic between them. The Soares paper I linked too showed how buffering up a list of syscalls, doing a single context switch to the kernel, executing them and then switching back is a major gain to a wide variety of applications. Sychronous syscall batching would be much more straightforward to adopt than aysnc io; imagine if cstdlib file stuff all used buffered syscalls - everyone would benefit! Whereas I would imagine it adopting true async io would be very hard because it is a exposing a blocking api to its user.
    - the8472 7y ago
      You can use io_uring for synchronous batching too. All you have to do is submit a batch and set min_complete to the number of submitted items when calling io_uring_enter. That's a single syscall, assuming you already have some thread-local ring lying around just for batching.
      - yxhuvud 7y ago
        You probably also need to set the flag that enables the events to be linked, so that they happen in the correct order.
        the8472 7y ago
        Only when order matters. For the given example of stating a lot of files it wouldn't.
- jandrewrogers 7y ago
  > database engines all use blocking io Only in open source, most advanced database engines have not been designed with blocking I/O in a very long time in closed source. I have not worked on any database engines with blocking I/O in the last decade. This is an area of easy integer factor performance improvement for open source databases, and one of the primary reasons they are not competitive with the performance of many closed source designs.
  - fractalb 7y ago
    Are there any benchmarks openly available to compare the performance of different open/closed source DB’s?
    - rrrrrrrrrrrryan 7y ago
      An older comparison of MySQL vs SQL Server that I dug up: https://www.ijarcce.com/upload/2015/march-15/IJARCCE%2039.pdf https://www.ijarcce.com/upload/2015/march-15/IJARCCE%2039.pd...
- jiggawatts 7y ago
  > Generally, databases are completely inefficient and there is just so much low-hanging fruit; Not generally, unless you only consider only popular open-source databases on Linux to be the "general" case. > Linux doesn't have a syscall batching system Windows has scatter-gather I/O, and notably SQL Server uses it. > Database engines all use blocking io SQL Server almost exclusively uses asynchronous I/O, and the entire Windows kernel I/O stack has been async since the 1990s. > I've got some tables with big compound keys and often do prefix searches in them, and why isn't mysql That's because MySQL barely qualifies as a database engine. It has a only fraction of the features of any commercial database, but it is cheap and it has low latency for simple queries, which makes it popular. PostgreSQL is substantially more feature rich, but they made tradeoffs elsewhere in the design that results in high write amplification, unfortunately making it a no-go for many potential use cases. You would be shocked at the concurrency levels achievable with modern in-memory databases, and the compression levels available with technologies like SQL Server's ColumnStore. Unfortunately, all of that technology comes with a licensing cost...
  - reborn7 7y ago
    >> the entire Windows kernel I/O stack has been async since the 1990s. Sincere Qs from a novice database developer, what good is all that async IO when you also have to consider data integrity? How would you e.g. uphold the integrity of file that stores the state of a autoincrementing field if you didn't use a singleton writer? In what db layer would I be helped by async IO?
    - willvarfar 7y ago
      Not involved, but giving an educated guess: Imagine a simple search like SELECT * FROM my_table WHERE foo = ? Imagine that the column foo is indexed. With blocking IO, the we go through the foo index, finding the rows that have the correct value of foo. The rows we find are on some kind of pages in the storage of the main table. So we now have a list of pages we have to fetch. With blocking IO, we would fetch a page at a time, process it, then request the next page. With async IO, we would request the fetching of all pages, as we discover we need them, and then process those pages in the order the IO subsystem can return them to us. Writes are the same; we have some number of pages we want to write to disk. With blocking IO, we write a page at a time and wait for it to be written. With async you can buffer up the writes, let the OS write them in the order it chooses, and wait for them all to finish.
- voortuckian 7y ago
  MySql is the original No sql database
- thedance 7y ago
  InnoDB (MySQL) uses aio where available.
alecco 7y ago
Note by compression they mean keeping internal blocks closer to full. It looks like a good thesis and advisors are reputable. But this comes with a trade-off. As blocks are full, inserts trigger more often a cascade effect. Batching inserts helps but once you need to apply the batch that could take a long time to rebalance potentially the whole tree. This adds a fat tail to insert times. But in many read-heavy scenarios it is a good trade-off.
- dgacmu 7y ago
  There was an aspect of that in the first part of the thesis, but the rest has techniques that are independent. You can roughly break the thesis down by paper: * Hybrid Indexes (a read-only, full-block kinda thing where you have to handle inserts by using a second read-write tree) * SuRF, a succinct range filter data structure * Order-Preserving Key Compression for In-Memory Search Trees Each of them can be used independent of the others, or combined. You can find two of those papers on Huanchen's web page: http://www.cs.cmu.edu/~huanche1/ http://www.cs.cmu.edu/~huanche1/ the third is to-appear, but you can find a preprint on arxiv: https://arxiv.org/abs/2003.02391 https://arxiv.org/abs/2003.02391
  - alecco 7y ago
    Excellent. Great job!
rini17 7y ago
Only read the conclusion and it's not mentioned there: did they consider locality and thus cache/paging misses?
jandrewrogers 7y ago
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
scandum 7y ago
How does it perform against googlebtree? https://www.tommyds.it/doc/benchmark https://www.tommyds.it/doc/benchmark
derefr 7y ago
I've always wondered why I haven't seen a DBMS built as a unikernel. A DBMS is already a "managed runtime" for data, with its own memory allocator, scheduler, filesystem (in some sense), etc. And you're almost always going to want to run a DBMS "workload" on its own dedicated hardware/VM, anyway, for predictability. So why not just take that set of DBMS services and put them in ring-0, where they won't need any context-switch overhead, will have fine-grained control over their own queuing for kernel resources, and where they can pass data structures by reference all the way from the network to the disk and back? In Linux, we already have Open-iSCSI, which just has the control plane in userspace, while the data plane is entirely a Linux kernel service, gaining it all these advantages. This architecture works very well there; I'm unclear on why others attempting to provide the higher-level "data-management solutions", with the same high-throughput/low-latency requirements, haven't copied it.
- fnord123 7y ago
  Scylla is available as a unikernel.
- aratno 7y ago
  Sounds like you would be interested in this paper on TabulaROSA: https://arxiv.org/pdf/1807.05308.pdf https://arxiv.org/pdf/1807.05308.pdf
7532yahoogmail 7y ago
Working my way through paper. Looks very cool. And practical ... It's also exceptionally well written. It's clear. Nice job
7532yahoogmail 7y ago
Off topic to OPs paper however consider the case of volt-db an all in memory SQL db with replication. In the sales'y' write speed was written down to less locks, latches, disk I/O. But somewhere else I read that a big culprit in fact isn't that: it's formatting data to be written to disk then decomposing a disk block back into memory for use. All memory dbs avoid that. Thoughts ?

251 points by ngaut 7y ago

A lot to digest. Presumably the compression schemes outlined in the paper would benefit columns generally, and not just keys, and would have a positive impact on row-size which would in turn benefit general performance? One short-string-compression-library to compare with might be https://github.com/antirez/smaz https://github.com/antirez/smaz by the Antirez, the author of redis. In the last decade Tokudb and then MyRocks showed how to do a fast storage engine for data too big to fit in traditional RDBMS. They are multi-level, they do page-level compression etc. And yet there is still so many easy wins yet to be had. Generally, databases are completely inefficient and there is just so much low-hanging fruit; if the team size working on e.g. myrocks could be doubled, and tasked with looking at the inefficiencies in the server as well as the storage engine, things might change. I have a list in my head of the various really-promising-ideas that databases don't actually do: * linux doesn't have a syscall batching system, but if it did, the number of context switches would be cut down dramatically. Research in 2010 https://www.usenix.org/legacy/events/osdi10/tech/full_papers/Soares.pdf https://www.usenix.org/legacy/events/osdi10/tech/full_papers... proved this and it wouldn't just be databases that benefit. These days context switching is more expensive than ever. * database engines all use blocking io. Finally io_uring offers workable async io and that would benefit database storage engines immensely. See https://fosdem.org/2020/schedule/event/rust_techniques_sled/ https://fosdem.org/2020/schedule/event/rust_techniques_sled/ * tokudb showed that simply not tracking the affected row count could speed things up massively (tokudb called it NOAR) * query engines often don't handle things that a few more lines of code would handle efficiently. I've got some tables with big compound keys and often do prefix searches in them, and why isn't mysql evaluating constraints that it can against the other columns in the key before dereferencing the row? Arrgh. Dumb dumb dumb. Etc.

qaq 7y ago
"database engines all use blocking io" Well sled is using io_uring
- samatman 7y ago
  probably why that paragraph had a link to a video titled "sled and rio: modern database engineering with io_uring"...
  - qaq 7y ago
    which was my point :)
- deleted 7y ago
  [deleted]
- fnord123 7y ago
  https://github.com/facebook/rocksdb/pull/5881 https://github.com/facebook/rocksdb/pull/5881 I thought I saw a PR fly by for mysql but I can't find it now so maybe I was imagining things.
the8472 7y ago
> linux doesn't have a syscall batching system Well, you already mention io_uring. That's your syscall batching system. It doesn't cover all existing syscalls because not everything is safe to do asynchronously.
- willvarfar 7y ago
  Yes, I'd like both! Asynchronous io_uring is good for things that take a lot of time, e.g. io. Its really just a queue between the user-space and kernel threads. But it doesn't replace just making a synchronous syscall for small things e.g. stating files etc. A lot of those syscalls are called in quick succession, often with no logic between them. The Soares paper I linked too showed how buffering up a list of syscalls, doing a single context switch to the kernel, executing them and then switching back is a major gain to a wide variety of applications. Sychronous syscall batching would be much more straightforward to adopt than aysnc io; imagine if cstdlib file stuff all used buffered syscalls - everyone would benefit! Whereas I would imagine it adopting true async io would be very hard because it is a exposing a blocking api to its user.
  - the8472 7y ago
    You can use io_uring for synchronous batching too. All you have to do is submit a batch and set min_complete to the number of submitted items when calling io_uring_enter. That's a single syscall, assuming you already have some thread-local ring lying around just for batching.
    - yxhuvud 7y ago
      You probably also need to set the flag that enables the events to be linked, so that they happen in the correct order.
      - the8472 7y ago
        Only when order matters. For the given example of stating a lot of files it wouldn't.
jandrewrogers 7y ago
> database engines all use blocking io Only in open source, most advanced database engines have not been designed with blocking I/O in a very long time in closed source. I have not worked on any database engines with blocking I/O in the last decade. This is an area of easy integer factor performance improvement for open source databases, and one of the primary reasons they are not competitive with the performance of many closed source designs.
- fractalb 7y ago
  Are there any benchmarks openly available to compare the performance of different open/closed source DB’s?
  - rrrrrrrrrrrryan 7y ago
    An older comparison of MySQL vs SQL Server that I dug up: https://www.ijarcce.com/upload/2015/march-15/IJARCCE%2039.pdf https://www.ijarcce.com/upload/2015/march-15/IJARCCE%2039.pd...
jiggawatts 7y ago
> Generally, databases are completely inefficient and there is just so much low-hanging fruit; Not generally, unless you only consider only popular open-source databases on Linux to be the "general" case. > Linux doesn't have a syscall batching system Windows has scatter-gather I/O, and notably SQL Server uses it. > Database engines all use blocking io SQL Server almost exclusively uses asynchronous I/O, and the entire Windows kernel I/O stack has been async since the 1990s. > I've got some tables with big compound keys and often do prefix searches in them, and why isn't mysql That's because MySQL barely qualifies as a database engine. It has a only fraction of the features of any commercial database, but it is cheap and it has low latency for simple queries, which makes it popular. PostgreSQL is substantially more feature rich, but they made tradeoffs elsewhere in the design that results in high write amplification, unfortunately making it a no-go for many potential use cases. You would be shocked at the concurrency levels achievable with modern in-memory databases, and the compression levels available with technologies like SQL Server's ColumnStore. Unfortunately, all of that technology comes with a licensing cost...
- reborn7 7y ago
  >> the entire Windows kernel I/O stack has been async since the 1990s. Sincere Qs from a novice database developer, what good is all that async IO when you also have to consider data integrity? How would you e.g. uphold the integrity of file that stores the state of a autoincrementing field if you didn't use a singleton writer? In what db layer would I be helped by async IO?
  - willvarfar 7y ago
    Not involved, but giving an educated guess: Imagine a simple search like SELECT * FROM my_table WHERE foo = ? Imagine that the column foo is indexed. With blocking IO, the we go through the foo index, finding the rows that have the correct value of foo. The rows we find are on some kind of pages in the storage of the main table. So we now have a list of pages we have to fetch. With blocking IO, we would fetch a page at a time, process it, then request the next page. With async IO, we would request the fetching of all pages, as we discover we need them, and then process those pages in the order the IO subsystem can return them to us. Writes are the same; we have some number of pages we want to write to disk. With blocking IO, we write a page at a time and wait for it to be written. With async you can buffer up the writes, let the OS write them in the order it chooses, and wait for them all to finish.
voortuckian 7y ago
MySql is the original No sql database
thedance 7y ago
InnoDB (MySQL) uses aio where available.

alecco 7y ago

Note by compression they mean keeping internal blocks closer to full. It looks like a good thesis and advisors are reputable. But this comes with a trade-off. As blocks are full, inserts trigger more often a cascade effect. Batching inserts helps but once you need to apply the batch that could take a long time to rebalance potentially the whole tree. This adds a fat tail to insert times. But in many read-heavy scenarios it is a good trade-off.

dgacmu 7y ago
There was an aspect of that in the first part of the thesis, but the rest has techniques that are independent. You can roughly break the thesis down by paper: * Hybrid Indexes (a read-only, full-block kinda thing where you have to handle inserts by using a second read-write tree) * SuRF, a succinct range filter data structure * Order-Preserving Key Compression for In-Memory Search Trees Each of them can be used independent of the others, or combined. You can find two of those papers on Huanchen's web page: http://www.cs.cmu.edu/~huanche1/ http://www.cs.cmu.edu/~huanche1/ the third is to-appear, but you can find a preprint on arxiv: https://arxiv.org/abs/2003.02391 https://arxiv.org/abs/2003.02391
- alecco 7y ago
  Excellent. Great job!

rini17 7y ago

Only read the conclusion and it's not mentioned there: did they consider locality and thus cache/paging misses?

jandrewrogers 7y ago

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

scandum 7y ago

How does it perform against googlebtree? https://www.tommyds.it/doc/benchmark https://www.tommyds.it/doc/benchmark

derefr 7y ago

I've always wondered why I haven't seen a DBMS built as a unikernel. A DBMS is already a "managed runtime" for data, with its own memory allocator, scheduler, filesystem (in some sense), etc. And you're almost always going to want to run a DBMS "workload" on its own dedicated hardware/VM, anyway, for predictability. So why not just take that set of DBMS services and put them in ring-0, where they won't need any context-switch overhead, will have fine-grained control over their own queuing for kernel resources, and where they can pass data structures by reference all the way from the network to the disk and back? In Linux, we already have Open-iSCSI, which just has the control plane in userspace, while the data plane is entirely a Linux kernel service, gaining it all these advantages. This architecture works very well there; I'm unclear on why others attempting to provide the higher-level "data-management solutions", with the same high-throughput/low-latency requirements, haven't copied it.

fnord123 7y ago
Scylla is available as a unikernel.
aratno 7y ago
Sounds like you would be interested in this paper on TabulaROSA: https://arxiv.org/pdf/1807.05308.pdf https://arxiv.org/pdf/1807.05308.pdf

7532yahoogmail 7y ago

Working my way through paper. Looks very cool. And practical ... It's also exceptionally well written. It's clear. Nice job

7532yahoogmail 7y ago

Off topic to OPs paper however consider the case of volt-db an all in memory SQL db with replication. In the sales'y' write speed was written down to less locks, latches, disk I/O. But somewhere else I read that a big culprit in fact isn't that: it's formatting data to be written to disk then decomposing a disk block back into memory for use. All memory dbs avoid that. Thoughts ?