jandrewrogers
today at 7:29 PM
There are several interesting foundational problems around scalability, generality, efficiency, and adaptability. Historically use cases haven't always been there to justify focusing on these problems but that is changing. In my opinion, some of the more important open problems:
Ideally a table should be index-organized across all relevant columns. No public system works anything like this. We don't have single indexing structures that work for a collection of arbitrary types each with possibly unpredictable distributions, never mind ones that mix temporal, geometric, and other difficult types. The AI-complete nature of indexing becomes evident when you dig into this. Downstream from this is an implication of extremely granular and adaptive storage management that current storage engines aren't designed for.
Tractable cache replacement algorithms are broken for many workloads and data models. These algorithms need to be very fast for search, update, and eviction selection but they are also AI-complete; improvements to generality have impractically high computational cost. Storage growth is decoupled from RAM availability thanks to disaggregation, aggravating the problem even for workloads that worked well under tractable cache replacement. In theory we know that cache admission (read: fancy latency-hiding schedules) is more robust and scales better but is so difficult to implement in non-trivial real systems that I don't think anyone has figured out how to reduce that concept to practice yet.
At exabyte scales, conventional database internals have embedded assumptions that no longer hold true. For example, you cannot guarantee even "small" internal control structures are resident in memory. What used to be fairly boring internals bits in databases suddenly have to be redesigned from first principles. This is more applied than theoretical but it suggests a major change in the way we do internal architecture.
Traditionally we've treated spatial and temporal locality as architecturally separate concerns. This is extremely convenient from a building real systems standpoint. Optimizing either one in isolation is adversarial to the efficiency of the other, which becomes increasingly visible as you scale up. Converging these concerns into a single "thing" almost certainly has solving the above problems as a prerequisite. If you squint, you can kind of see this as the last step before databases become literal AI.
All of these have really broad scope. If we could solve even half of these open research problems the resulting database engines would be unrecognizable. There are ton of other narrower interesting research problems around data layouts, compression, join parallelism, etc that still have potential for substantial improvement.
It is a great time to be doing database research, we've barely scratched the surface.