4 ms·
> You may know exactly what information you need for a single given query. But you don't know what the next query will be. You don't know if the next query will
by jandrewrogers 3y ago
> You may know exactly what information you need for a single given query. But you don't know what the next query will be. You don't know if the next query will need the same indices or something else entirely.
I think this misrepresents how many modern database engines work. Queries are generatively decomposed into many thousands (or millions) of independent page operations, depending on the amount of data they necessarily touch, before they get to the execution queue. Ops from concurrent queries are all blended together. The I/O and execution scheduler can, in fact, see upwards of a million page operations into the future across all concurrent operations in some systems and adaptively, dynamically reorder the entire schedule to optimize for locality across concurrent operations while preserving invariants. This enables powerful optimizations that circumvent theoretical limits on cache effectiveness and improves locality under high concurrency in ways simple caching cannot. This is not a new idea, it is how silicon is designed to deal with data access patterns that intrinsically have poor cache locality. A modern server can retire tens of millions of these ops per second, so you can get incredible throughput with tight tail latencies because, again, you control what happens and when. This works beautifully even when the working storage is orders of magnitude larger than available memory. It does require exquisitely fine control of I/O and execution scheduling as a matter of architecture.
It is worth acknowledging that the throughput limits are not an mmap() problem. Most non-mmap() database kernels struggle to saturate modern storage hardware too. Classic database architectures are not effective at consistently and inexpensively generating enough concurrency to use the available hardware.
I used to use mmap for database kernel-y stuff. The recurring pain point was that it is impossible to saturate fast storage arrays using it for many real-world workloads when the data won’t mostly fit in memory, and the computational cost of trying to do so was high. And then I did a stint in supercomputing where it turned out everyone knew you could circumvent these limits in highly parallel systems with precise I/O and execution scheduling, and relying much less on caching, but those people don’t work on databases.
- scrubs 3y ago"circumvent these limits in highly parallel systems with precise I/O and execution scheduling, and relying much less on caching, but those people don’t work on databases." Can I bug you for a library, book, algo, gpu i/o card or whatever good stuff you may be referring to there?
- jandrewrogers 3y agoTragically, supercomputing is mostly dead as a hardcore research area AFAICT, and they rarely published in no small part because so much of the research was funded by US intelligence agencies. It was pure serendipity that I ended up in that world; I solved a theoretical CS problem that was particularly interesting to people working in that space and was given free supercomputing time to do further research (which was awesome). I learned a lot about how to think about software at extreme scales from the graybeards in HPC. I was one of the few young people in the space even back then. To answer your question, almost all of the valuable theory comes from research in silicon architectures designed to hide latency, with graph analysis as the canonical problem case. It is the question of how to get the most throughput out of silicon that is frequently waiting for a cache line to fill or a lock to release. In silicon, this typically refers to barrel processors specifically and the most refined form of that was arguably the Cray XMT. In modern silicon, you don’t have to squint too hard to see that GPUs are a specialized type of barrel processor. The less obvious aspect is that you can do very effective latency-hiding in software, but how is poorly documented. Nonetheless, if you study how latency-hiding silicon works, it isn’t that hard to figure out how to design a software architecture that has similar properties albeit with fewer guarantees than silicon offers. Latency hiding silicon works by having a huge number of operations in flight at any one time, surveying the landscape, and choosing the operation that is mostly likely to make forward progress. Software has the advantage that it can look much further into the future of operations than silicon can and in many ways is actually more efficient even though you have less control of the fine details.