Transcript
Speaker: There's a problem with databases that has bugged me for years, and it's probably bugged the industry since the eighty s And it goes like this. Imagine you've got a database of sales figures and you want to know sales by country.
Speaker: So select sum of amount, group by country. right. Let's say you sell to a dozen countries and you've made a lot of sales. So that query is going to have to read 10 million sales rows in to produce 12 summary rows out.
Speaker: And that's probably an important query. So you end up running it a lot, but it's 10 million rows you're processing. So it's an expensive query. So you end up caching it or materializing it.
Speaker: Here's the thing that bugs me. When you make one new sale and it's time to update the cache or update the materialized view, how much work is that? Logically, to me, that's one operation. You find which of the 12 countries the new sale was made in, you add it to the total.
Speaker: But plenty of systems will say, no no, sorry, we're not set up to do that. We have to rerun the entire query from scratch. So it's 10 million and one pieces of work. You say, can't you just add the number in? No, I can't. It's against my principles. It's not I'm designed. You have to rerun queries from scratch every time.
Speaker: That's horrible. Now, in fairness, some systems will say, yes, we can add in the number. We can handle this change incrementally, but only because it's a simple query.
Speaker: Well, then I ask, what counts as a simple query? Ah, the rules to a simple query are completely arbitrary, and you'll only find out that it's not a simple query when it suddenly breaks and you're suddenly paying 10 million times the cost.
Speaker: The incremental view maintenance problem is one we've been wrestling for decades, and it's nasty and it really hurts when it goes wrong. And it was pretty much solved about three years ago with an award-winning paper called DBSP.
Speaker: And that paper proves that the answer is all queries are simple enough. All queries can be turned into an incremental version that only has to consider the new changes. I find that quite exciting because it's like 10 million to one exciting.
Speaker: And the theory has been proven mathematically, and it's been proven in practice with some software called Feldera. Joining me to explain how it works is Lilith Suresh, who's Feldera's CEO. And we're going to discuss...
Speaker: Why in practice it applies to database queries, but also to changing network topologies and live social graphs. We're going to discuss the theory and why it works to unify batch processing and stream processing and a lot more besides.
Speaker: Once I got my head around how this is actually all put together, I've got to say it was the most interesting paper I've read in years. So I hope we do a good job of getting these ideas into your head and it will worm its way into your head too.
Speaker: I'm your host, Chris Jenkins. This is Developer Voices. And today's voice is Lalith Suresh.
Speaker: I'm joined today by Lalith Suresh, CEO of Feldera. Is that correct? That's correct. How's life as CEO in 2026 for a tech company?
Speaker: Well, they call it a rollercoaster for a good reason. right yeah Yeah, I'll bet. yeah Although 2026 is a rollercoaster, and I guess it always is when you're the CEO, i you have hit a problem solution to a problem that I think I first experienced in the early 2000s, which probably dates me. But it's the problem of...
Speaker: This is the way I think of it, right? You've got a database and you're running a view and you want to turn into a materialized view because that sounds like a nice, efficient thing to do.
Speaker: um But then whatever database engine you're using usually says, oh, I can only make it fast to update the materialized view if they're very simple queries. And that's my very vague headline, why I care. But why don't you go into the details of what you're actually solving?
Speaker: Yeah, happy to dive into it. I think the best way to contrast this problem is to just look at how most of the industry goes about large-scale data compute and analytics, right? It really, in my opinion, hasn't changed a whole lot since the 70s. And in fact, the incremental compute problem, i think the first paper on the subject was in 1979 or something, so it's quite an old problem.
Speaker: And so things like Spark, you know Snowflake database, all of these are really good at ah what we call batch compute. right You throw a lot of hardware at them.
Speaker: You aim it at some data that you leave in your database or warehouse or lake house. You write SQL queries against that data. These engines will use whatever resources they have available to them to go over all the data to give you back an answer.
Speaker: Yeah. That's kind of that's so how we understand evaluating a query or a view and database. Now, the question is what happens if you literally read on the same query a second later?
Speaker: They pretty much have to repeat exactly what they just did the last time, even if only 5 out of 50 billion rules have changed in the meantime. but yeah Yeah. This is exactly the thing that bugging me in the 2000s, right? Exactly. And yeah it's very like everyone runs into this at some point working with a database or a warehouse or what have you.
Speaker: And now the question is, ah how do you recover that inefficiency? You'll see it everywhere. And it's one of those things that once like pointed out to people, it's very difficult to unsee it afterwards. Like you look at it around you and you see this everywhere. There's a bit of a, ah it's quite perennial and you leave a lot of inefficiency and you know ah latency on the table, right? Because you need compute proportional to size of the data always.
Speaker: yeah Now, the incremental compute problem is how do you turn this into a problem where the time and computers report on to the size of the change? right By only looking at how your data changes from one moment to the next, can you keep arbitrarily complex queries fresh at any given moment in time? If I've queried a billion rows yeah and got an answer and then one new row comes in, do I have to do one computation or a billion and one?
Speaker: depends on the query, but ideally you're only computing what's like the compute expense proportionally size of the change. right Let's say if your query is, you know, they can be bad queries where let's say one side of join matches a billion rows on the other side of the join. And then you are spending work proportional to a billion instead of, let's say one. But this is yeah this is exactly the idea. right like You want to keep it as close as possible to only what changed and nothing else.
Speaker: um So you touched upon an interesting point when you said databases for a long like for a while, if at all, allows us only for very simple queries. And there's a good reason to it because that generalization has been incredibly hard. so right like How do you do this for any query? right like is Is it even possible to do it for an arbitrary query? Is it even possible? Exactly. right yeah And so if you look at the last, again, 40, 50 years of papers on the subject, there's...
Speaker: there's been some really advanced math thrown at this problem. So people take a very specific type of query or an operation in SQL and they figure out like what kind of advanced math can we do to turn this query into something that computes the derivative of the query. right like How does it work on the changes or something like that? right And these things have never quite hit mainstream.
Speaker: In a way, right? like So differential data flow was a really good piece of work here, but even that's actually quite a hard note to crack, right? Like you um folks who've read the paper would know. um And so the surprising breakthrough that my co-founders came up with wo was that with a very simple bit of math, just four operators, it turns out that any program written using those four operators can be automatically turned into a program that computes on the changes.
Speaker: Now, this is the thing I always like in maths and computer science, when you feel like, when you really hit on the nub of a problem, it breaks down into small, simple pieces. Yes. That's sign that the assign but we might finally have solved this.
Speaker: That's pretty much it. That's kind of how we look at it as well. Even more powerful, and we can get to that in a moment, is that once you've deconstructed it into this piece and then you start to say ask questions like, how do I now do joins using this formulation, you actually recover old results in database literature.
Speaker: Because the way to do joins using DBSP actually recovers the famous delta join algorithm, as an example. Okay. Yeah. So this is a sign that you really found something very fundamental. right Like it's actually recovering the cells that others poured a lot of time into finding for like sort of specific subsets of ah the problem. Right. Again, that's kind of, yeah, again, ah it appeals to researchers a bit more. Yeah, yeah. But in practice, what that means is literally you can throw...
Speaker: 50,000 line SQL programs at us, like you know hundreds of views, deeply nested, thousands of joins, aggregations, sliding windows, whatever. And it does not make any compromises. So it works for inserts, updates, deletes. It works for, again, any composition of these kind of queries on top of each other. It even works for recursive queries.
Speaker: It even works for streaming problems. right like It just covers all of it. Deep down inside, we are not special casing for any one of these cases. It just works across all of them quite uniformly. yeah This very much appeals that you can take an arbitrarily complex SQL statement and reduce it down to four operations.
Speaker: Yes. and We're going to get into those operations because I really want to break down the paper. because it's It's one of those papers that once the penny drops, it starts to think, oh, actually, this is really elegant and probably more simple than I expected before I started reading the symbols.
Speaker: Yes. But before we do, I do want to talk just a bit about how you're applying this theory because I can see how this applies in the world of databases, like make your really changing queries really efficient.
Speaker: But you're saying this applies in the world of Kubernetes and other things as well? Yeah, that's actually quite fascinating because ah a lot of problems start to look like incremental view maintenance or incremental computation problems. right like ah The origin of this work was Leonid, our CTO, looking into ah network control planes.
Speaker: right okay So there was there was this sort of movement called software-defined networking. These days it's become very commoditized, I would say. But the idea is that your your network in a data center, like your switches, your routers, your virtual switches, the VM sitting on it, all the ports, the connection, the the routing table, the rules that govern, what traffic is allowed to go where, all of that state is managed centrally using some kind of network controller.
Speaker: And so that network controller is really what it's doing is it's like a policy. Like it's evaluating policies on this sort of topology and sort of this rich graph of information. And that's really like a view. A policy is really a view over a graph.
Speaker: right. It says, give me the sort of yeah give me the sets of VMs that are in violation of some kind of segmentation policy. Like that's actually the controller trying to maintain a view or a graph. And it maintains a lots and lots and lots of views depending on the policies you're trying to maintain.
Speaker: Okay. so Yeah, I can see how you translate a graph into SQL and therefore watching changes on the graph becomes an incremental view problem. Exactly. Yeah, I can say that. and Yeah. And so generally, sort of if you look at these control plane orchestration or cluster management platforms and things like this, typically the architecture has been, I would say, very stable for a long time.
Speaker: It's that you have some kind of control plane state database behind the scenes, in and then you write controllers. that actuate on that state and also changes to that state.
Speaker: They maintain views over that state, they watch the views, and then they ah take some action against the underlying thing that they're managing. So in Kubernetes, you have controllers that watch the central database, typically at CD, but other distributions have other variations of it.
Speaker: These controllers then listen to changes and then they take some action. They might say, shut down a port or you might move it somewhere, things like that. It's very similar in networking as well. They might listen to these changes, they tittle with some routing rules, things like that.
Speaker: yeah Yeah, and I bet plenty of them have lost a lot of engineering time into optimizing indexes and views and kind of queries so they can be rerun many, many times very fast.
Speaker: Yes, exactly. um And so the funny thing is like a bunch of us come from that background, including myself. like My first entry point into this problem space was also cluster management. I did some work. So we were all researchers at VMware before this, and that's kind of where we all started working with each other. um And there, there's a couple of papers I'd written on sort of using SQL-based declarative cluster management, like how do you write the control plane layer by maintaining your state in a data in a SQL database?
Speaker: And then all the control plane logic becomes views and constraints solving problems that you build on top of that database, right? Yeah, yeah. And so when you work in that space, you very quickly run into the incremental view maintenance problem as well. And so...
Speaker: I remember like one of the early conversations where I had i was talking to Leonid Mihai while they were working on this problem. And I said, like this has to be a solved problem. like Databases should have a problem.
Speaker: ah some kind of IBM capability out of the box, right? And they said, surprisingly, no. No, no. and that's yes I've seen some pretty large companies where they have a version of materialized views. And basically, as as the query gets more complex, it's more likely that they'll say, no, we can't refresh this incrementally. We're just going to re-query the whole thing from scratch every time. of Correct.
Speaker: Or on demand, which is not actually that much better. Yeah, which is why that you see that sort of bias towards you can run very simple queries this way. Whereas in fact, like the the biggest value for this type of computation model is to be able to run really complex stuff the more data you have. like That's when the value of the platform grows and grows and grows. right like So being able to do a couple of simple queries is fine, it's cute, it's a feature.
Speaker: It's not really something you make an architectural decision at all. yeah Yeah, I can imagine that generally the more complex the query, the more it's going to cost you to rerun it every single time and thus yeah the more benefit you get.
Speaker: But for that you have to prove that your theory actually covers every kind of SQL, right? Yes. So you here's the thing. So first of all, the paper proofs that you can cover all the SQL and extensions into this model, right?
Speaker: um I don't think I remember the last time there was some kind of gotcha that we ever run into on the SQL side. like The translation is... the beauty of it is it's completely syntactic.
Speaker: So converting into DBSP is quite straightforward. And then from DBSP into the incremental version of the DBSP program, like there is no guesswork. It's heuristic-free. That's one of the keywords you see in the paper early on.
Speaker: And that's an important detail. There is no cost-based guesswork that we're doing here. It's just complete sort of, you see you see the program, you just mechanically turn it into a program that works on the changes and that's it. Now you have.
Speaker: Right, so you can literally compile down from SQL deterministically to the incremental version. Yeah. Right. So should we try and get into the... There's some creativity involved, no doubt, but... Where does the creativity come in?
Speaker: I think the the SQL to DBSP, so there's a bit of, so if you read the paper, there's this thing of like the actual DBSP theory says nothing about databases. Right?
Speaker: Right. kept Applying it to databases is a transition that we manage by using Zsets.
Speaker: like Applying it to the domain requires some level of creativity. And then from the SQL to DBSP layer, again, we have like a big suite of incryb like handcrafted incremental operators and things like this, as opposed to writing the most general version of everything. right like There are that is room there, but that's again, that comes down into the level but the details, I would say. That it sounds to me a bit like deterministically compiling, but then there are differences between CPUs, so there's still some creative compiler works yeah like that. yeah yeah Okay. yeah
Speaker: So you've mentioned z sets or Z sets, as we say over here. um I guess we'll end up using both terms. I'll call them Z sets, you call them Z sets and we'll move on. But this is this is a fundamental algorithm that no sorry it's fundamental data structure on which we're going to build the rest. So why don't we cut our theoretical teeth in this conversation by you explaining what they are.
Speaker: Sounds good. um So is this set, I mean, just taking one step back on the string, central to making DBSP work, sort of the the map on how do you compute on streams, how do you turn a stream into a stream of changes, how do you turn a of changes back into the original stream. like that's kind of the craft That's kind of the beauty of what the map allows you to do.
Speaker: But there is an assumption that the elements floating through the streams form what's called a group, which is a fancy way of saying There's some well-defined operations to add, subtract elements from each other.
Speaker: And there is sort of the concept of zero value. They're associative, they're commutative. A lot of nice mathematical properties come out of having those assumptions in place. But generally, databases are not groups.
Speaker: Right. So right it is ah inserting two rows is insert one, and like in insert a row, insert another row. Right. We can do that. and But generally, databases cannot delete two rows of like one instance of two rows of the same kind.
Speaker: You get one instance of two of the same row. yeah that doesn't Yeah. That doesn't make sense in database land, does it? Exactly. So ZStats are a very simple way to turn data represent databases in a model that still fits like this group structure. right okay ah All it does is, for every row, there's a weight column.
Speaker: And a weight column is an inger like it's a an integer weight, typically. So plus one means you add one instance of the row. into the database. If I insert one user row then that's going to have a weight of one. and When I delete it, it's going to have a weight of minus one.
Speaker: ah If the row does not exist, it has a weight of zero. If the row doesn't exist, it has a weight of zero. Yeah. But if you add a row to... So first you insert a row with plus one.
Speaker: Then if you insert a row with minus one, it's effectively equivalent to that row only existing zero times. Yeah. Okay. That makes sense. yes Yeah. so this so So this is what allows you to like deal with both positive changes and negative changes symmetrically.
Speaker: Yes. Now, I looked at this paper, I thought this looked to me a bit like um a multi-set in which you say, every row in the database, put it in a set with a value of one as its weight.
Speaker: And the only thing that makes it takes you to this slightly strange version of a Z set is that you're allowed negative weights. to represent the row disappearing.
Speaker: Correct. Yeah, okay. Correct. Yeah, that's that's all there is to it. And now what this Zset allows us to do in conjunction with DBSP is that in FileLyra, inputs, tables, views, outputs, changes to tables, changes to views are all Zsets.
Speaker: Right. like All Z sets, even like literally the on-disk journal format, everything is just Z sets throughout. So in some places in the algorithm, you've got a Z set representing my user with a weight of one.
Speaker: Some places you've got the whole user table with a weight of one. sometimes you've whole database with a way to one, conceptually. yeah Yeah, it's all like uniform and consistent and you know symmetric throughout.
Speaker: And so this is an incredible superpower. I mean, think of like your average transactional rollout database and how hard change data capture is operationally to just set up.
Speaker: Yeah. Right. It comes from the fact that changes are not first-class citizens in those systems. It's not the same data structure to represent your tables versus changes to tables or changes to views, things like that. Right. Like that's basically where that pain comes from.
Speaker: In Feldera, none of that is really an issue because everything is built up on Zsys. Change is a first class citizen. Yeah, i'm going to hold on to that phrase. Yeah. And so from changes, you can, and we can talk a bit more about that as well. like Databases actually work on changes. We just never called it that, right? You have a database with some tables. you apply some You apply a transaction to a database. That's really a bag of changes that you're applying to the database, right? Some number of insights, updates to these.
Speaker: And now you get a new version of the database. right You can think of it. So basically, a database problem can be represented into one where you have these streams of transactions showing up.
Speaker: yeah And out at the other end are coming out a stream of database snapshots, each of which represents the version with the prefix of transactions applied to it.
Speaker: Yeah, okay, yeah. Applying a series of transactions takes a stream of, I want to change this into a stream of the database has changed to this. Yes, exactly. yeah Okay, yeah yeah. Like that's kind of the model. like So we've always actually been operating on changes and with databases. They've just, we're never first class citizens.
Speaker: And so now if you're trying to do an incremental, or rather describe incremental view maintenance on top of this model, it really looks like a view is just a function of that database snapshot.
Speaker: Right? Okay. So when you have a stream of transactions, you can you have a stream of database snapshots, and from that you can have a stream of views over this evolving snapshot as well. The stream of the state of the view. Yeah. Yeah, in fact, the state of the view.
Speaker: And so, with again, so this is how VBSP ends up getting applied into this database realm. Right? Yeah. We have Z sets, we have this model of like databases really are streams.
Speaker: of yeah know transactions, streams of snapshots, streams of views. And over that, we basically find ways to do what's called differentiation and integration, that is, change a stream and do a stream of changes in some sense.
Speaker: Right. yeah So this is yeah my impression of this whole paper is you've got a stream of transactions. You know how to apply those to make a new database, which theoretically gives you a stream of new databases.
Speaker: A view is just a function over it. So that gives you a stream of function, a view results. Yes. That's horribly inefficient, but that's what we're doing. And if we make it maths, we can rearrange it. Yes. Yes. right Yes.
Speaker: So that finding that incremental query operator, the queue and so turning a Q into a Q-delta is basically what Feldera does for you. You tell us a Q, we'll turn it into a Q-delta.
Speaker: You feed us your change, you know, insert some these beliefs. And what we compute internally is the changes to the views and the applied incrementally. That's basically how all of that ties together in dual.
Speaker: For that, you need four pieces. Let's try and break this. And it's my intention. I don't think we can reconstruct the entire paper in speech. Probably not. yeah But what I think we can do is explain all the pieces such that if someone to were to read the paper, it wouldn't be desperately scary to look at. It it would it would demystify it. That's what I want to get to.
Speaker: Sounds good. um So there's four operators in DBSP. Really, like two of them are the most important ones. Two of them are really specific to recursive queries, which we probably don't need to cover. But the first two are very simple.
Speaker: ah One is the lift operator, which you can really think of as a map. Okay. Over some. So you map a list, you get the same list with the function applied to every member of the list.
Speaker: Right? We've almost already talked about this. This is mapping the view function over a stream of databases. Basically. Right? like So that's what the map looks like. And then there's the Z-1 operator, which comes from signal processing. You'll see a shout out to that in the paper. But what it does is if you have a stream, it delays the stream by one time use.
Speaker: It's called the delay operator. Right. So the element that, you know, the... So what this allows you to do is construct these little feedback circuits where you take a stream, let's say you add it with one time unit delayed, and this is how you can do integration, for example, right? Like you can say, take the current value that just showed up and add it to the previous output we computed.
Speaker: and can yeah You can basically describe things like this. and basic what What happens is, out of these out of just the map and the delay operator, you can now construct stream differentiation and stream integration, which is um how do you turn a stream into the changes of the stream?
Speaker: yeah And similarly, how do you do the inverse, which is given a stream of changes, how do you reconstruct the original stream? right like That's what differentiation and integration is. so Let me see if I've got this. because yeah you you You imagine starting with an empty database and you apply a transaction to it.
Speaker: Then if you route the output of that back in,
Speaker: From that, you can you can pull the trick of saying, how do I have a constant input to this function, which is the current state of this database? You just set up a feedback loop. You just set up a feedback loop. Right.
Speaker: So that's what lets us, conceptually, they think of it this way. like You have some delta coming in that you're trying to apply, and what you have with you now is the previous state of the data database.
Speaker: Yeah. So mathematically, you can sort of add the two together. Basically, yeah yeah yeah yeah. So it lets you you know turn this into these little math expressions where you can say like the output now is equal to the latest change that arrived plus the previous output. right It allows you to describe these type of you know by induction type of formulas. Right, yeah. yeah You're formalizing these intuitions we have about the way we say, and now I've got the new state of the database. I want to add another transaction to that and send the differences along.
Speaker: yeah Yes. okay In fact, like we do this all the time in programming. right like You write a for loop and you say i equals I plus one. right That's really a way of describing in some sense take the value you have right now, add it to the previous value. But it's really that sort of model brought into database land.
Speaker: And so, of course, it assumes that there's some notion of what a plus means in databases. And this is the small sort of technical matters of how Z sets help here. where You can add a change to a database, you can subtract a change from a database, and you get the ocean law.
Speaker: Right, yes so you can model a delete as add minus one to the state we previously computed. Okay. yeah Yeah. yeah yeah So from basically stream integration and differentiation, again, constructed out of those the map and delay operators, um we can then keep going and it turns out like all of SQL can be expressed as these little circuits out of just these two operators pretty much. yeah i I just want to, um because there's one part of this paper where a penny dropped for me, which I thought was quite neat, on differentiation.
Speaker: It's like, I can imagine having the state of my large database now, and then after another transaction, and after another transaction. But if you gave me two database states and said, what's changed between them?
Speaker: I think that's a really, really hard thing to compute, right? And yet with Z sets, it seems to be suddenly very easy. Yes. So part of it is you have to look at it as...
Speaker: um
Speaker: you're getting to this you're always spending a little amount of work to get to the final answer, right? like So if two big databases showed up at once and you asked compute the diff, you really do have to spend the time to actually...
Speaker: at least scan both of them. Yes, but if you gave me like two Postgres databases and said spot the difference, that would be a really hard algorithm as well. Yeah, I think so. you kind of have to in You basically have to index both sides in order to so ah compute that. yeah But you've pulled a very neat trick in DBSP to to solve that, right? You just say, since both databases have overlapping data but different weights,
Speaker: you can just sort of take the difference of the weights. You basically can add them up, actually. yeah Yeah. Yeah, you can add them up and you get the reconstituted. Because they're weighted sets, you just do one set minus the other or plus the inversion of the other.
Speaker: Yeah. There is something, that like again, depending on exactly the SQL semantics, except versus intercept intersect have slightly different meanings. right like But yeah, you can you basically can just add up zs.
Speaker: in order to do some of this. Okay, so you have the ability to roll changes into a state and figure out the difference between two states and thus get a sequence of the changes back out. Yeah. Delay a thing and lift a function into working on changes instead of individual states.
Speaker: So... Close form? Not quite, right? Like, so... One thing is
Speaker: a lot of computations when you turn them into the sort of model where you work on changes have to be stateful. And all state in DBSP or Feldera is packed into those E-1 operators.
Speaker: Got it. So in some sense, you can think of like those that they the stuff that we keep behind there. That's the only state that we need to maintain on storage or whatever, the only thing we need to checkpoint. it's also the um ah It's also what you should think of as indexes that we keep.
Speaker: for the computation that you're running. right Okay. Yeah. So anytime there are joints, distincts, or aggregations, or certain kinds of aggregations, actually, these become cases where they have to be stateful, which means we have to keep indexes around these things. And really, fundamentally, what it means that there's a z minus one operator in there.
Speaker: Right. but i so Yeah. Because that's what you're doing, right? when you do When you do a delay on a thing, you're saying, keep hold of the previous version. Correct, correct. Whereas there are operations which are linear operations like filters or projections.
Speaker: These don't need any stages.
Speaker: There are also linear aggregations, like some, for example, right some in count, like they also don't need any state. right you can What this means is by only looking at the delta, you can compute the delta to the function, like the output and stuff. Yes. Now this goes right back to an old complaint with, um I'll mention the specific database because I'm sure they fixed this by now, but with Oracle, you you do a sum of a million rows,
Speaker: You get one new row in, you know intuitively you've just got to add one number to the old number, but you've got to recalculate the whole table. yeah So you're saying certain classes of changes, we know how to do those incrementally.
Speaker: like yes And when one change comes in, we know how to deal with that change on the old state. Yeah, exactly, without keeping any sort of complex memory or you know state of the past version of the database or anything around it. But there are computations where you just can't escape it, like join systems. Let's just tick off the easy ones. So that's got to be sum and can't count. um Average is just sum and count. Min max. Min max or not. Min max or not. Oh, really?
Speaker: mean like oh yeah hu Yeah, so in the general case, when there are updates and deletes, they're not. Oh, deletes. Yeah. These things have to hold across.
Speaker: Again, like ah we are not playing terms and conditions games here. like i like it So the general version of it, ah for min and max, you you do need state. there ah ah They're not linear um aggregations. That said, if you have append-only streams,
Speaker: That is, there's no deletes or updates. They do become linear. That makes sense. They only need the past. Because if I insert one, two, three, four, five, then delete five, four and three, you've got to have had the information available. Right.
Speaker: Okay. Okay. So I don't get those for free. I get selecting columns out of a ah table because I can just look at the new columns for the new row. Right. Correct. Yeah. um Filters. filter losses yeah Yeah. That's also, yeah. the Those also don't need any stick. They're sort of naturally incrementable.
Speaker: Incrementalizable. Yes. yeah Okay. oop um Group I, join distinct. Yeah, Group is also a state form, right? But yeah, join distinct aggregation, certain kinds of aggregations, Group I, things like that actually require the delay operator with the state and therefore we will keep state underneath.
Speaker: Okay, take me through one of the harder ones then. just see if we can tackle that. would say the join is a good example for this, right? um Since I said look we do recover the delta join algorithm.
Speaker: ah So what is a... ah so Again, it's hard to draw circuits here, right? But if you take a look at the that particular figure in the paper where it describes the circuit for the join...
Speaker: You should view it in this lens. It's basically like, what is the change to a join that you're trying to compute? Let's say there's two sides to the join, the left and the right. You need to find all changes to the left relation.
Speaker: find out, like, so let's say there's a new change you're computing. And so you want to compute the changes from the, you take the changes from the left relation, join it against the right, right side. So it's delta A to join B. And then the opposite of it, delta B join A. And then add it to the old value of the join, which is A join B.
Speaker: and So you're really just computing for both sides what changed that would now affect the output of the join. But then you have to add those Z sets to the old value of the join. That's it.
Speaker: So when something new comes in, I'm saying, does this new thing suddenly now join something on the other side? Is there something on the other side now
Speaker: I'm trying to break that down to words. I join user to account. I get a new user in. I've got to scan for to see if there are any existing accounts that that would affect.
Speaker: If I get a new account in, I've got to scan for any existing users. Yes. um And if I get both in I've got to see if they interact as well.
Speaker: Yeah. Right. I think I get that. Yeah, that's it. that's yeah so And that in a nutshell is when Delta joins. right but okay But the the way you construct joins out of DBSP will basically recover that algorithm out of the box quite naturally.
Speaker: so So with those operators in hand, let's go back to the original one. I've got a series of transactions coming in. They go to a database. Yes.
Speaker: I end up conceptually with a stream of what's changed in the database. And I run my function view function over there. I get conceptually a stream of what's changed in the view.
Speaker: Am I eventually then going to have to roll all those view changes up to get the materialized view that people actually want to query? It depends. You don't have to.
Speaker: But so in Feldera, for example, we distinguish between like regular views, which are just computing and pushing deltas through. Materialized views where we do reconstitute the entire tables.
Speaker: And then we have this special thing called a local view, which is views that are not externally observable, which we can do some really aggressive global optimizations over, work but that's kind of a detail. But like there is ah we do distinguish between just propagate deltas. For example, in a ah create table statement in Paldera, where you hook it up to, let's say, your Kafka or whatever, some kind of input connector.
Speaker: If you don't have primary keys or if you don't declare it as materialized, it will not use any state. It's just shoving deltas through it.
Speaker: Yeah, right. do you Are we just talking about um data definition? um Sorry, are we talking about um DDL or DML? are we just talking about inserts, updates, deletes, or are also talking about alter table, create table? Yeah.
Speaker: That's a good question. ah No. we like So generally, we assume the schema is fixed. That is, the create table, create view statements are fixed. These are standing query. You have inserts, updates, deletes coming in.
Speaker: We also do allow you to change the views. but like You can change your pipeline. You can sub out some of the views for other views. You can add new viewsmo views. You can move views. And we have mechanisms to actually compute the new views from the state you already have as well.
Speaker: So the one customer called it the incremental incremental computation or something this like this.
Speaker: I wonder if any of this theory has been applied to the problem of schema migrations.
Speaker: Schema migrations, would yeah we don't handle it out of the box, but it naturally does fit this model. um yeah okay So typically like there are cases where you can't avoid a backfill. but right So if you had 100 tables and you remove one of the tables, for example, right or you add a bunch of columns that you didn't have before, things like that, like this there's a bit of a policy decision on whether you want to backfill completely or you want to you know just assume nulls, recompute what you had before. But we, for today, do require you to backfill just that table.
Speaker: Okay. and So how does this end up getting used? Is it like... Is it backed by some regular database or is it integrated into an existing database? Or is it entirely standalone new kind of database? Or is it attached to Kafka to get like a historical record of stuff?
Speaker: us Standalone. So we've written this query engine from scratch, like I said, because changes are first-class citizens. It's very difficult to bolt this on an existing platform that doesn't have a native understanding of what changes are. right So we wrote the entire thing from scratch.
Speaker: ah We have our own storage layer optimized for dealing with things like Zsets,
Speaker: all kinds of operators to work on different kinds of SQL operations. We have a SQL compiler we wrote and an entire control clean around it.
Speaker: Right, yeah. yeah yeah And so the model is users describe SQL pipelines. A pipeline is just a bunch of create table and create view statements. Tables can be hooked up to input connectors, like zero or four input connectors.
Speaker: Views can be You can have output connectors attached to views. You can have zero or more output connectors per view. ah These connectors can be any combination of live or historical data.
Speaker: It can be any combination from bat streaming um data source of sources or destinations. right So you can have, let's say, get your historical backfill from some kind of Delta Lake snapshot and switch to Kafka or live traffic for this table.
Speaker: Okay. right And you can have a very heterogeneous mix of traffic going in and out. Because you've got a backing theory that says, if I've got a stream of changes coming in from Kafka, I can reconstruct that into a database-like thing. And if I've got a constantly changing database, I can reconstruct that into a stream-like thing.
Speaker: Yeah, yeah they're all they're all changes to us at the at some level. Like a batch of, let's say if you do a backfill from S3, that really just looks like one big batch of changes showing up at once.
Speaker: Right, yes, because there's no difference in your theory between one one change of one row and one change of five rows or a million Yes, exactly. It it it it makes absolutely no difference for us. So the computational model is, um we call it the synchronous computing model, in that you take a batch of changes at the input, you evaluate all of it, and you compute the set of outputs that changed.
Speaker: And this all happens atomically. Right. right yeah So connectors, streaming or batch or what have you, right or whatever combination of, their only job is to interface with the outside world and supply the ne like some set of changes to apply in the next round that you run. right That's all they do. right So it's fairly cleanly decoupled.
Speaker: In fact, like it provides a nice boundary between sort of the messy outside world and this nice clean internal set we have. And then similarly on the output side, it's very similar. right like The engine provides a set of changes that the connector should ship to their destinations, and that's it.
Speaker: yeah so Fundamentally, right yes if the key to this is getting a concept of changes to be first class, and then it seems like a lot of nice things fall out of it,
Speaker: Why do you think it took this many decades to solve the incremental view maintenance problem?
Speaker: It's hard to sometimes answer these questions because it's like it's one of those things that like really good breakthroughs look obvious in hindsight, but getting there is actually quite hard. right like So this was one of those things where really, really, really, really smart people worked on it for very long.
Speaker: And like if my co-founders say the math that came before this was too hard for them to understand, I believe them. but So it just took, I would think, an outsider lens of the problem to basically trap that code. And so bringing sort of digital signal processing into this mix was, I would say, a leap of creativity, I think, from Mihai to pull this off. Because a lot this theory comes from how do you compute functions on audio streams? Yes. I think I did read that. The operator actually comes from digital signal processing, the Z-1 operator.
Speaker: operator yes Right, so the same math that's trying to do chorus pedals and echo effects... Turns out it works in Oracle. I'm a second processing guy. like i barely scraped through that class in undergrad. But Mihaly does does it have a background in it, I think. like He jokes that he finally got got to apply apply i don't know ah his degree in BSP in February or something like that. That's cool. Not the first guess or connection between them programming and audio that we've had in this world. I guess the maths for audio processing gets really hard too.
Speaker: Pretty sure. Again, far beyond my ability ability to process for sure. Okay. So what makes this hard in practice? Because I can just like i can see the four fundamental operators are simple. I can start to see how the paper's built up. And I've been chewing away at this paper in the background too.
Speaker: well Okay. I can see that writing an SQL parser and compiling it down to these maths operators is a lot of work. having an API that slurps changes from S3 and Kafka and Postgres and, and, and, and and that's a lot of legwork.
Speaker: ah um Is it just a tremendous amount of legwork to get this into production or is there other stuff that makes it hard? I think yes and no. It depends on kind of the use cases and scale you're going to. Like for us,
Speaker: Our customers typically show up and re replace these gigantic workloads running on Spark, Snowflake, Databricks with us. right So the bar is very high. like Anyone can do this at very small-ish scales in memory and whatnot. like That's easy. we're not even And I typically am not quite interested in that space. right um right Doing this at scale,
Speaker: like pi Try evaluating 3,000 joins, 100,000 lines of SQL
Speaker: on massive data sets. That's where this gets really interesting. right Because if you think about the value proposition here, it's really the speed up and compute savings is unbounded.
Speaker: and it likes a If you think of like a little graph where if ah but data volumes are the x-axis and you have the time it takes to run a query the old-fashioned way or compute it takes to run a query the old-fashioned way, this number just grows up. The more data you have, the more expensive batch compute gets.
Speaker: Whereas typically the size of the changes are miniscule relative to the overall dataset size. right Yeah, most batch jobs are just recomputing last night's changes to three years worth of data.
Speaker: Exactly. like And so if you draw a flat line, that's what actually incremental compute can be for you. Because the changes are so small, yeah it really starts to be independent of how big your overall data set size is as you grow, right?
Speaker: And so the further along you are, the more bigger data sets you can take on this way, the more dramatic the speed ups keep getting. Right? Like we've seen folks with like, I think our record so far is 48 hours to two seconds at 50 X the scale.
Speaker: Like that is kind of our like record. You're kidding. No, that' that's actually the ah sort of team record so far. But on in general, like most customers, yeah I would say,
Speaker: um two to four hours, if not nightly jobs, things like that, become milliseconds seconds. That's kind of the transition you do. um But with the caveat that you don't have to spend a fortune to get this, right? You only need like a fraction of the compute to keep this big fresh all the time.
Speaker: Yeah, I suppose if the if the query will allow it, you're just you're not actually maintaining a lot of state to process the changes, right? we do have to maintain most like more state than usual because at the end of the day, what we are doing is trading off time for space.
Speaker: Right. We are keeping these indexes so that you can compute efficiently. But in general, like the compute savings and the freshness matters enough that it's worth it. We we save so much on the compute side, like storage has to be cheaper, so it's okay like to make that freedom.
Speaker: That's at least how we look at it. um You've just made me think of another part of implementing this in production that must be hard, which is you've got to worry about checkpointing and state management.
Speaker: checkpointing, state management, fault tolerance. um And of course, like the thing I think we spend a lot of time on is the backfields. That is the at least here, which is how do you run that first query?
Speaker: Yeah. Like the equivalent of the first query. How do you run that? Because there's no shortcut there. it You just have to um process the entire input at some point. um And here we are pretty differentiated in that week.
Speaker: Like I said, there's no distinction in file data between batch and streaming. right So the backfill is really like we can actually run it as this one gigantic transaction upfront. So we don't end up doing a lot of intermediate work computing many small changes.
Speaker: but Think of an aggregation, for example. right like If you process the entire input, like build let's say 50 billion rows one at a time, you might have an aggregation, let's say the total number of users. They just keep going from one to two to three to four to five or whatever, right? um Each of which is a delta for whatever sitting downstream.
Speaker: right which also needs to get processed. So instead of doing that, what you can do is, we call it huge steps ah for efficient backfills. You basically run the entire input backfill as one gigantic transaction in Feldera, which means that each operator pretty much computes on this gigantic batch of changes, and they produce a gigantic delta for whatever's downstream, but you only do that, say, once.
Speaker: right yeah Yeah. yeah so Everything's changed, but some changes are larger than others. Correct. Exactly. okay and every yeah Because of that, there's no in the engine, there's no it's not like a separate mode or anything like that. right like then I think conventional wisdom has been then batch and streaming are completely separate lanes.
Speaker: o We don't make that trade-off here. like It's just one engine that flexes between. So compare this for me to something like Kafka Streams, which is kind of takes in a different approach, which is you've got a long stream of changes, just roll this state machine over it. Mm-hmm.
Speaker: I would say the distinction is the complexity of workloads you can take over it and what the semantics are. but okay So Feldera does not change SQL semantics in any way. In fact, like you can run those crazy workloads I mentioned, right the hundreds of thousands of lines of SQL, and row by row, cell by cell, we guarantee you get exactly what you would have gotten in a batch engine.
Speaker: okay You will never see a state that is inconsistent in Feldera in that sense. right Whereas my understanding of a lot of the sort of you know Kafka Streams, KSQLs, Link, like that universe of stream processors, has been they mostly operate around this eventual consistency model.
Speaker: right They have very low-level ATI, so you can think of them a little bit as assembly. But how you construct more complex and operations out of it has usually been like a hard ceiling that is not at all trivial.
Speaker: And in fact, performance, once you get out of the simplest of settings, starts to fall off very quickly. So that thing of, like can you take on the same complexity as you would with a Spark?
Speaker: why you still operate on deltas has been a bit of a holy grail known as accomplishment. We think we're pretty unmatched there. And I think DBSP is the superpower that allowed us to get there. Okay. Okay. Okay. yeah So what about things like user defined functions?
Speaker: To what degree can you support arbitrary code coming into your SQL queries? We can't in the sense of like one requirement for anything you run inside a pipeline is that it has to be deterministic.
Speaker: Okay, so only pure functions. Yeah, so UDFs. ah We have UDFs and UDAFs. What we do is we take the SQL program, we compile it into a RASP binary that uses the DBSP crate underneath.
Speaker: So UDFs that use UDFs or UDAFs that you write in RASP are also compiled into the same binary. But if these things have a random number generator or they go did they show an external API call, which is not deterministic, things like that, ah that's a lot.
Speaker: Okay. yeah just So we do require you to keep them deterministic. Reminds me, I saw a company recently doing um Rust where they had a similar risk kind um a restriction.
Speaker: And what they did was compile it down to WASM. because they could ensure that there was no the like the execution rules for that Wasm sandbox. like the Interesting. you It couldn't execute impure functions because they didn't supply the means to. I i can see you possibly why.
Speaker: Compiling to Wasm seems like a pretty big lift, I would say. right like We just put the big sticker out there and we're like, use at your own risk. And it's actually for very it's usually for very advanced users anyway. like um Most people don't need it. be also The other thing is, you can also what you can do in shell data is you can turn some of these impure things into inputs to the pipeline, which, as it should, in fact, like now the now function that gives you the current block value is really just another input connector in shell data.
Speaker: Take me through how that works. so A clock is really just a stream of timestamps that comes in on the outside. like we we you So anytime you're basically writing a pipeline with a now function in it, again, it depends on where you apply the now, right? But for example, if you say select star from some table and you say select star comma now, what you're really saying is at every timestep,
Speaker: this view changes. like Every record that you compute is now going to change. yeah right like So that's a bit of a foot gun. Whereas is there are cases where you can use it like as sort of as part of a filter expression, where it becomes what's called a temporal filter, and we have very optimized um data structures handling that efficiently. right like So we do warn you to use now in style of projection, which is kind of an anti-pattern.
Speaker: But a now is basically another, you can think of it as the now table, which has one value, which is the current value of the clock that you're really joining against. So that's how you should model it.
Speaker: But how would you make that work when you start backfilling? Because the now table is going to be completely different. That's correct. Yeah. So i so when you you're backfill, you're really starting from scratch anyway. But if you checkpoint and then you recover, what happen what happens is after the checkpoint, everything is correct. But then when you resume from the checkpoint, the null value will look different. That's all. ah So there's sort of a time leap since you recovered.
Speaker: Correct. Exactly. like it is isn't it doesn't If you rerun a pipeline, you're kind of implicitly saying with now that you're okay with the value changing.
Speaker: right yeah It's not meant to be a statistic at that point. yeah but it's yeah yeah Given the same inputs, it'll always compute the same outputs. there's never a um We never relax that, I would say. right So for testing and things like this, there are ways to actually feed feed the now stream.
Speaker: Makes sense. Right. Yeah. Yeah. i suppose it would be semantically weird to say now means now, except when we've decided it actually means two hours ago because the system crashed for a bit and we're trying to catch up. No, no, no. Yeah. We like we don't get into that mess. It's just a stream of values for us.
Speaker: ah In fact, a bunch of users also do this thing where you can
Speaker: like the timestamps come from the data itself. place So they might have a table, they might have timestamps that they planted on those rows ahead of time. Let's say it's already in their Delta tables or something like that. And then you can just operate on those timestamps inside the pipeline and again, it stays deterministic.
Speaker: Sure, that makes sense. makes sense yeah So how long does it take to go from the paper working out the theory to your first genuine against-production SQL queries working problem.
Speaker: What's that path like? I'd say... We were founded summer of 2023. I would say we built it for a year and a half. e before we felt this was ready to actually take to market.
Speaker: but like It hit certain milestones of, like do we have our own storage engine? There's a bunch of things we were waiting to hit. You could already run a lot before that, but then last year is when we really took this to market. right So that's about the timeline it took us. um But again, i it's never done. right You're constantly... yeah Yeah, you're constantly adding capabilities, you're constantly ah improving your coverage of we know SQL constructs. And it's usually not even things specific to DBSP, it's just making sure the front-end supports things users want to do. right like We are the single largest contributor to Apache Cal site, for example, which is what we use as our front-end.
Speaker: ah We've added things like lateral column aliasing, which is a construct people really like from Spark SQL. Okay. but I think it's Databricks SQL.
Speaker: We added that, but that has nothing to do with BBSPs. That's just a purely front-end ah capability, but there's a lot of work of this shape that keeps showing up. And then optimization is the constant for like query optimization. right like there There are better ways to run some queries than others. And again, that's also very front-end heavy work that we do. We're working on things like scale-out. So this is optimization.
Speaker: Give me an example of when you need to optimize that's not taken care of by these the theory underlying it. Oh, that's just a standard query optimization, right? Like things like predicate pushed down.
Speaker: Oh, okay. Yeah, yeah. Yeah, like, yeah, all of those type of things, right? um And there's always going to be some case that shows up where you're like, this could benefit if we applied this kind of query optimization rule.
Speaker: Yeah. Yeah. All the standard SQL things apply. Like we also do this thing for like sharing indexes. right So if you have a pipeline and you have like a lot of views, they shouldn't all be constructing their own index for similar joins, for example.
Speaker: Right. yeah right yeah Yeah. They could all be sharing the exact like one index. And we've seen customer workloads where there'll be like 30, 40 different views that without that optimization would have each kept their own index for some part of the join. Whereas with this thing, they all end up sharing like one index over the ah info tables or something like that. these are the kinds of things that we constantly improve. yeah Yeah. It's not hard to imagine a company that has 40 riffs on the same basic view.
Speaker: Yeah. so yeah Yeah. Okay. okay So if i I've been in the background. I've been trying to wrap my head around this paper and I've been implementing in Haskell. and I've probably been doing it the hard way, to be honest. But the intellectual curiosity got the better of me.
Speaker: If someone wants to like experiment with this, um there's a paper, there's a Rust library. there's Where would you recommend getting started? So try.fellera.com.
Speaker: is free for everyone to use. You should start there. That's a sandbox. um There's also the open source version that you can run on your laptops wherever you want. right's like It's MIT licensed. Go wild. githar.com slash Feldera slash Feldera. Is that the Rust library or is that something else?
Speaker: It's the open source version of Feldera, so it's not the Rust library. So you can actually write the whole SQL pipelines. You can define connectors, all of that. like Okay. So typically users start there.
Speaker: before they want to go more serious and use the enterprise mission. Take me more serious down into the ah lower level. It's when you really want to run this in production at scale. right like that's usually like And you kind of want someone to answer the phone when things go wrong. That's the cutoff to the enterprise edition. Typically, things like call tolerance, things like that are packaged into the... and It runs in Kubernetes. There's a bit of...
Speaker: Right. yeah ah Yeah. Yeah. Yeah. All those and we've now we've got the thing working, but now we have to live with it. It's a good place to charge money, right? Yeah. Going from individual to reasonable the company needs it as kind of like the things that separate the two is where the open source versus the enterprise edition.
Speaker: But there is also the Rust library. If I wanted to just connect random things to random things incrementally, right? It's very low level, I think, fast-flag. So the DBSP creates, you're not defining SQL or anything anymore. right like It's very low level. So we compile from SQL into a program that uses the DBSP create, but also the other things around it. like So it's not just one create even.
Speaker: There's a bunch of things that get assembled into the pipeline. That's basically where it comes in. And then there's the whole control plane thing of like, orchestrating, provisioning, pipelines, resource management, all of that. like That's the other parts of the platform. Right. Okay. Yeah. yeah yeah And if I want to wrap my head around the paper, how should I have started?
Speaker: yeah I'd say Mihaly's talks on the subject are amazing. That's where I would start. So there's a talk he's given Confluent and constant Current in 2024.
Speaker: oh That's a pretty good... I think it's called Streaming Creatives Without Compromise. That's a very good presentation by him. I would start there. oh There's a talk that he's given at the CMU Database Group, which is like really a deep dive on the paper itself. It's about an hour long.
Speaker: That's another thing I would search for. Okay. Yeah. He's a fantastic speaker if you haven't listened to him already. I haven't. I will do. and I'll link to those in the show notes.
Speaker: And um maybe I should have done that before I started asking Claude to explain mathematical symbols to me. Well, that's one way to go about it. as well Maybe you can ask a lot too. Again, very 2026. Yes, very 2026.
Speaker: On that, I think we've got plenty of brain food to be carrying on with. So Lilith, thank you very much for taking me through that. And... um yeah, I feel like I've got a stream of changes to go into my brain.
Speaker: There's, in fact, a slide in this presentation. This is exactly how we as people process the world around us, right? Like, basically, ah you know, integral of the stream of our experiences day to day, right? That's Yeah, yeah so yeah. Databases are very similar. That's that's how they work too. Nice. But yeah, thank you for having was really awesome to be here. yeah Thanks very much. Thank you, Lilith. So lots of links in the show notes for this one. You'll find Fidera, the company, and the open source edition if you want to go and use it. There's DBSP, the lower level Rust library, if you're interested in diving into the code. And of course, there's the original award-winning paper.
Speaker: Before I researched this, I didn't know that papers won awards, but apparently they do, and it won one, and I'd say it's well-deserved, so congratulations to the team that wrote it. We'll be back as soon as we can with another interesting voice from the software world, so please do take a moment to like this episode, maybe share it around, and make sure you're subscribed to the channel.
Speaker: But until next time, I've been your host Chris Jenkins. This has been Developer Voices with Lilith Suresh. Thanks for listening.
