O(n*m) Architecture in Open Source. What Could Possibly Go Wrong?

Summary

This video explains the O(n×m) problem in open source table formats, where every new encoding feature—such as Byte Stream Split added to Parquet in 2020—required updates across multiple reader implementations in Java, Python, C++, and various forks, causing features to take four years to propagate.
Delta Kernel is a single canonical implementation that handles the Delta Lake protocol internally and translates it into engine-readable scan instructions, so each query engine only needs to adopt the Kernel abstraction once rather than implementing every new feature independently.
With Delta Kernel, new Delta Lake features such as deletion vectors and column mapping propagate to all engines automatically through opaque expression passing, without requiring changes to existing engine code or query rewrites from users.

O(n*m) Architecture in Open Source. What Could Possibly Go Wrong?

There's a quiet crisis going on in open source right now — whenever an open table format wants to build a new feature or integration, there's an exponentially more amount of work to do to incorporate it. A project that's increasingly harder to contribute to is the death of innovation. Kernel sets out to solve this problem by rewriting the source of truth. When other projects adopt Kernel, they no longer need to do any additional development for new features — they just appear. Join us for a deep dive into how we turned this project on its head, to solve not just these problems, but future problems we anticipate in open source. What started out as a contribution to Delta, could change the way that open table formats fundamentally integrate everywhere. Join Robert Pack, open-source contributor for Delta, Iceberg, Arrow and all round Rust enthusiast, and Holly Smith, tech communicator, who bullied Robert into this talk.
Talk By: Holly Smith, DevRel, Databricks ; Robert Pack, Staff Developer Advocate, Databricks ;

Chapters

FAQs

What is the O(n×m) problem in open source table formats like Delta Lake?

The O(n×m) problem arises when a table format like Delta Lake has n features and m reader or engine implementations: every new feature requires updates to every implementation, multiplying the development effort. For example, a Parquet encoding feature introduced in 2020 took most readers four years to fully implement across Java, Python, C++, and various forks.

What is Delta Kernel and how does it solve the multi-reader fragmentation problem?

Delta Kernel is a single, canonical implementation of the Delta Lake protocol that any engine can adopt as a shared dependency. Instead of each engine implementing Delta features independently, the Kernel handles protocol translation internally and exposes scan instructions that engines consume, so new Delta features appear in all adopting engines without additional per-engine development.

What are opaque expressions in Delta Kernel and why are they important?

Opaque expressions are a mechanism in Delta Kernel for passing predicate and filter logic from the protocol layer to the engine in a way that the engine can apply without needing to understand the internal Delta representation. This allows Kernel to expose pushdown filters safely to engines that have their own expression systems, maintaining the abstraction boundary between Kernel and engine responsibilities.

Which Delta Lake features benefit most from Delta Kernel adoption?

Complex Delta features such as deletion vectors and column mapping are the clearest examples of the O(n×m) tax: implementing them across every engine and reader combination previously required a large, coordinated development effort. With Delta Kernel, these features are handled once inside the Kernel, and any engine that has adopted the Kernel abstraction gets them automatically.

Full transcript

[00:07] Yep. Oh, yeah. We're on. All right. Hello, everyone. Hello, hello, and welcome to this talk O&M architecture in open source. What could possibly go wrong? Bjarne
[00:19] Stroustrup famously said there are two kinds of languages, the ones that people complain about and the ones that nobody uses. But I would like to posit that we can extend this to open source projects. And one of the most prolific data open
[00:33] source projects that has held the crown, at least in my view, for a very long time, for over a decade, is Parquet. And by definition, because it is so popular, it means we have to complain about it.
[00:46] So, let's complain about Parquet. Uh engines read from file formats, and I hope this is the cutting-edge stuff that you came here for this week. Um and around 2013, uh we had, um this
[00:59] might have been Hadoop uh MapReduce, and that file format might have been Parquet. But this isn't CSV, and so we would need to read it in a very specific way. There's like roughly six steps, uh
[01:11] like reading the footer, uncompressing the code, reassembling it on the other side, um adding the pushdown, and then handing it back in the right format. Uh and this library was called ParquetMR.
[01:23] But because it was implemented in Java and dependent on the JVM, that meant that Python couldn't use it. So, there came along a Python reader. And then there was also a C++ one that came along. Uh and then a group of
[01:35] people weren't happy with the Python reader, so then they made a fork. Uh but then someone else wanted their reader to build on top of C++ to make it work for Python. And on and on it went. So, when Byte Stream Split came along in
[01:47] 2020 as a new way to encode and organize your ones and zeros, um everyone had to update their decoder if they wanted to be able to read this new type of file. And the results were to be as expected.
[02:00] So, for a feature that was designed in 2020, it took most readers 4 years to implement it. Good thing at Databricks, we don't have projects with multiple implementations
[02:12] to manage. Oh, wait, we do. All right, so for >>
[02:25] the road map. I do like Rust quite to an excessive amount. I am contributing to other projects and I talk about it as well. >> And I am Holly Smith. I work in DevRel
[02:37] and I consider myself a kind of technical communicator, which basically means I don't do any real work and I just like the sound of my own voice. >>
[02:49] Delta, one of my passion projects. We just talked about open source project Parquet. We already know Delta ultimately wants to read files from data files, but to make this easier, we track
[03:02] metadata along with those files. And in this metadata, we track things like statistics, maybe correlated indices, stuff like that. And then when the engine wants to read that metadata in the
[03:14] context of a query, it essentially produces instructions on how these files should be read. So, we And this metadata is what makes the backbone of Delta. And the technical
[03:26] name for this is the Delta log. And we'll talk about how this works with Spark and Parquet. And technically for Delta, we have another step. And that's we apply the transformations we learn
[03:39] back as we read those files. However, this high-level overview might just gloss over some of the more interesting details within kind of the Delta protocol. So, we now want to take a quick look at how
[03:52] this works in detail. Quite straightforward, so when you read this, you just build a quick snapshot, locate the latest snapshot, replay a couple of commits onto that, validate the protocol in the feature support, then you process kind
[04:05] of what you got back to this, maybe locate some deletion vectors, do all of this work, then onto reading the actual parquet files. This is what your parquet reader already does, so quite straightforward, skip pages,
[04:17] prune, maybe if you want that extra snapping is do some late materialization on the predicates. And as you read this back, you may want to kind of consider type widening, schema evolution, all of these good
[04:29] features, right? So, of course you obviously all know this. I just kind of for completeness' sake wanted to cover it really quick. >> Okay, then so why do we think that Delta is pretty sweet? So, first of all, you
[04:41] get faster reads from clever metadata. You get a faster writes now that you can be smarter with that metadata. Table locks are also a thing of the past. Um and we also keep that historic metadata
[04:53] around, which also allows for things like time travel. So, it's not just big chunky joints. It's great for streaming and like work different workload patterns. And something I'm sure that won't come back to bite us, and that is a great ecosystem.
[05:11] All right, so once upon a time, we had a feature at Databricks that was originally going to be called Hadron. It was super fast, like a Hadron Collider, but then we noticed there was actually a really unfortunate typo that keep reoccurring.
[05:26] And this would happen more than once, and we'd have a Delta table that needed the columns renaming. So, to fix this, we could just do it brute force, and we could just drop the entire column, and then re-add it again, which is basically
[05:39] like a sledgehammer to crack a walnut, especially when it is terabytes of data. Option two was to implement a feature in Delta called column mapping to work with your engine of choice. It's very simple.
[05:51] Robert would Robert would just walk you through it. >> All right. So, really quick. So, when you read the file, you got to update the protocol. You got to learn what your engine does. You got to um
[06:03] On the way back, you have to read the metadata. You got to translate all your statistics. You got to translate all your predicates. All of this goodness. You go into parquet. You already know all of this, right? So, quite straightforward. Coming back, you may
[06:16] want to rewrite some of your predicates again. You want to apply partition columns. You want to again rename your statistics. All of this goodness. But, we're not quite done yet. You may also want to consider some of the edge cases.
[06:28] So, spread across your code. You need to rename everything, right? And test all of this. And obviously, don't forget writing. Which is the whole thing kind of in reverse. So, >> Simple.
[06:41] It's only 15 steps across 1,600 lines of code. And if that looks like a lot of work, don't worry. It only took Trino 13 months to implement. Flink, 16 months.
[06:54] And Hive and Druid went with option number three. And that is to not bother. And when renaming a column is too much work, how on earth can you be at the cutting edge?
[07:07] And so now when someone is thinking of you adopting Delta, and they want to know what it can do. And we have to do our best consultant impression and say, "What does it do? Well, it depends on
[07:19] your ecosystem." And this is not conducive to a thriving ecosystem. >> All right. But, what if there was a fourth way? So, in fact, what Holly just described
[07:31] is a decades-old problem. And we call it ecosystem fragmentation. We believe we have found a solution for this. So, essentially normalizing on a single library that understands Delta metadata
[07:44] and translates it into instructions that an engine can easily follow. So, what should a kernel's responsibility be? So, when executing a query, there's essentially two phases. There's the
[07:56] planning phase and there is the doing phase. Delta kernel only involves itself in the planning phase and this is not only fortunate, it's by design. Because the metadata you process during the planning phase is orders of magnitude
[08:09] smaller and as the actual data you process in the doing phase and engines tend to care about things like performance and memory. So, if it's metadata, it's probably on
[08:21] the kernel end of things. If it's data and heavy, it's probably on the engine side of things. So, Delta >> Oh, sorry. >> Yeah, no worries. >>
[08:33] on the other end of spectrum, we have this and there is a professional term for this that the experts in the industry use, which is not my circus, not my monkeys. What does that mean in detail though?
[08:45] So, we want to stay away from anything that engines care about and again, this is usually memory and performance-heavy stuff, right? So, we saw earlier even reading a simple parquet file is a very complex process and engines have highly
[08:59] optimized readers that help you do these kind of things. So, we don't want to prescribe to an engine how to do this kind of stuff. And the big one is the data representation. A lot of the engines out there today use Arrow, but
[09:11] there's other formats that you can use to represent the data and kernel doesn't want to take a stance on what that kind of is. So, what does it mean for your column mapping? So,
[09:23] um we have kernel uh and now let's look at kind of the flow we've seen before and see what we need to do for column mapping. The things in green are the things that kernel does for us. So, protocol validation metadata,
[09:36] kernel also does a lot of work for us on the way back, which is good. We already know the parquet reading is kind of that what's what's what parquet reader handles. And on the way back, we do have to kind of do a little bit of work on
[09:50] updating our predicates, the residuals, kind of and do the work that we couldn't push into the parquet reads. Um but it feels like this is considerably easier than the workload we had before to master this.
[10:03] So, prior to kernel, the blast radius, as Holly just mentioned, was massive. And it potentially touches everything within your code base that references a column or field name. But without kernel, we see a much
[10:16] smaller blast radius and a slightly less enthusiastic adoption. It is still an open-source project, after all. So, that's column mapping. What about other features?
[10:29] >> All right, so deletion vectors is a massively requested feature. In short, instead of doing lengthy reads and writes to your data, when you just want to delete teeny tiny amounts, we're just going to pretend that it doesn't
[10:41] exist. And this mostly happens in the last step. And what we're not going to do, we need to remember to not use it for optimizations. We also remember need to remember to really not mess it up,
[10:53] because it has the potential to fail silently. And you can see how this has the potential to go really, really wrong. Now, yes, you had to make changes all over the place, but it's the types of
[11:06] changes that make this so difficult and make it so hard. It is not just a case of updating particular things. You are ripping out the guts and the fundamentals of this to really rewrite it everywhere.
[11:19] So, yes, we you had to make changes all over the place, and it was quite difficult. >> All right, so we have a new to-do, implement deletion vectors. Let's see really quick. Implement this
[11:32] in your parquet reader. You probably want to learn about what the roaring bitmap is, how to process this in your code. You do also want to probably learn something about selection vectors and how you propagate this through your code base. Um, you want to apply these
[11:44] deletion vectors throughout fairly straightforward. And then you want to kind of make testing and uh all your silent failures work because this has the potential of just kind of propagating data that should not be part of it uh forward to your results.
[11:58] And if that sounds like a lot of work, >>
[12:10] so, this is kind of a monolith uh but we really really really wanted implemented. And then my favorite kind of response, why don't you do it? The early adopters of this features made
[12:22] it happen in just under a year, the rest 2 years, and the majority, guess what? Did not bother. >>
[12:35] a bit simpler. So, you add the Kudu library dependency, you do some sanity checks on your parquet reader that it supports file IDs, um and then Kudu hands you the transformations that you need to apply
[12:47] to your data as you read from parquet files. On the read pass, essentially the other way around, you use Kudu provided expressions to transform the data your query produces that you want to write into the table into the physical format
[12:59] that needs to land in the files. You collect stats on this written data. These stats your parquet reader usually already produces on writes because it needs to write this into the footer. And then you tell Kudu about these stats and
[13:11] commit. So, and if that's not enough detail for you, you can find me over there at the booth later on. We have some very detailed tracing of this entire process that
[13:23] maybe expands a little bit on what that exactly looks like. Um So, now that's a simple way to think about kernel. There is a bit more complexity to it.
[13:35] Um and that is kernel kernel Holly already said there is a saying in the industry. So, once you become a senior engineer, you start saying it depends and you don't stop until you retire.
[13:47] Uh same here. There is it depends. So, we already said schemas clearly on this kernel end, data clearly on the engine end, but there is a middle ground and the middle ground is expressions.
[13:59] Expressions need to be formulated by the kernel engine. So, we need to have some knowledge about expressions. But, there is a myriad of things that you can write into a where statement and the kernel engine cannot be kind of the superset of
[14:12] every expression that an engine might want to write. There is so there is an escape hatch for this called an opaque expression, which the engine can populate, but kernel never has to reason about and it
[14:24] transparently flows through the file skipping process. So, um the it depends though is kind of you you see there there is more to it. We could do talk just on this aspect of the
[14:37] opaque expressions if you want to learn more. Again, I'll be over at the booth later and we can chat about it. Uh yeah. >> All right. So, what next? Where where does this all go from here? Um we are
[14:51] undergoing um a bit of a renaissance at the moment. And ecosystem fragmentation candidly is a fact of open source. And again, there is a proliferation of file formats at the moment. Um and I wanted to include
[15:04] and we've got a few of them here. Um I also wanted to include uh Meta's Nimble, uh but they don't have a logo yet. So, I I made one for them. I reckon they'll stick with it. So, Delta might have been one of the first file format formats to feel the
[15:17] pinch here, but it absolutely will not be the last. I'm thinking wider, this isn't just file formats. If you have an engine that is also struggling with managing a partnership, this is maybe another way to think about it. In fact,
[15:30] it's not even a data specific. You if you are in kind of connector maintenance hell, consider adopting a kernel style architecture. All right, thank you very much. If you have any questions, please don't ask me.
[15:44] Please ask Robert. He is going to be over at the booth later, so if you want a hands-on demo on Hydrofoil and how to have that all work, then by all means catch him later. I'm Holly Smith, this is Robert Park, and thank you so much
[15:56] for attending. >> Thank you.

Learn more about the Databricks Data and AI platform.

The information provided herein is for general informational purposes only and may not reflect the most current product capabilities or configurations.