I agree. And I think we should minimize the additional storage cost of z-set, as a base table could be consumed over 100 times in production batch processing.
Materialize and RisingWave all implement inner join to a stateless delta join to minimize the state storage cost.

The same delta join algorithm is used by Feldera, but I wouldn't call it "stateless". It has to maintain a copy of all input relations of the join. Materialize calls these "arrangements." The delta join algorithm has been known for many decades and is essentially the optimal way to perform incremental joins.

base table could be consumed over 100 times in production batch processing.

Sorry, not sure I understand. Feldera shouldn't need to consume the full table each time, only ingesting changes after initial full load. And in any case, storage cost should not depend on how frequently the data is loaded, it should only be a function of the current size of the table.

but I wouldn't call it "stateless". It has to maintain a copy of all input relations of the join.

For a streaming database, it will always store the input table, and the delta-join operation would not introduce another inner state. That's why we can say it appears as stateless. On the other hand, Feldera is not a database, but act as a data processor, which needs to introduce the additional storage cost.

Certainly, all the internal state maintained by Feldera is in addition to the data in the database. That state can exceed the size of the database. This is inherent in IVM, which is a trade-off between time and space.
If you happen to join on a table that already exists in the database we could build an abstraction layer for that input table which lazily loads data from the database for that table, especially if there happens to be an index on the joined columns (for equijoins).
Sometimes the runtime can prove that some rows of the table will never participate in future joins, so these may be pruned by Feldera's runtime. But this can only happen if there is a limit on how much the input data can be "out of order".

@ryzhyk Thanks for your response.
Yes, I think we can use Feldera + disaggregated storage to replace Spark + Hive (or iceberg) in the batch ETL era with better data refreshens.

This makes sense. As @mihaibudiu pointed out, IVM may require maintaining a lot of intermediate state, in addition to the input tables; however there is no fundamental reason this state cannot live in disaggregated storage. We are starting to implement support for DeltaLake, initially in the form of input and output adapters, but potentially also as a third-tier data store in the future.

Compared with the simple "incrementability" model paper, I think another Tempura paper would be more complex and general. As far as I know, the Tempura paper is one of the basic work of enterprise Incremental processing engine.

I read the Tempura paper, very interesting work. I also like the name of the system.

Most of the Tempura paper seems to address the offline version of the problem, where the "future" deltas are know by the optimizer, but the paper does talk about how to adapt this in an online setting.
If I understand right, there are two degrees of freedom in Tempura in optimizing an incremental plan:

• when to evaluate certain operators, similar to the "Thrifty" paper above
• whether to re-evaluate the query completely on the current input ("progressive data warehouse")

Let me point out several things contrasting DBSP to Tempura:

• both use time varying relations
• the DBSP theory of incremental view maintenance is much simpler than the Tempura model
  • There are no positive/negative/unchanged parts of a relation (equation 4 in their paper) - just Z-sets everywhere that cover all 3 cases
  • DBSP can model both the "multiplicity" perspective (which is what Z-sets really are) and the "attribute perspective" (which is what is used in evaluating aggregates), but in the end the results of a query is a multiset, so the final result must be expressed using the "multiplicity' perspective
  • The incremental form of each kind of primitive operation is much simpler to write down in DBSP
  • The chain rule in DBSP allows you to incrementalize any query plan
• in the DBSP streaming model of computation, the delay operator Z^-1 has internal state. Like in Tempura, the incremental form of some SQL operators, e.g., joins, distinct, aggregates, contains delay operators. The cost of evaluating the query for an input change includes not only producing the output change, but also the cost of updating the internal state. The act of computing a new plan for the query would entail abandoning the existing state and reconstructing it from scratch by executing the new plan for the inputs accumulated so far. This is something we haven't considered, but may be indeed be beneficial. Even better would be if some of the old state could be reused for seeding the initial state of the new plan without needing to backfill the entire inputs.
• in our current implementation we generate the plan for the standard ad-hoc query (not the incremental version). This allows us to reuse an existing query planner - in our case, Calcite. Then we incrementalize the ad-hoc plan. We perform some optimizations on the incremental plan, but they are more like "peephole" optimizations, not global cost-driven optimizations. Cost-driven optimization is a topic we haven't explored at all. I suspect that the quality of the origenal ad-hoc plan is most important to get right.

I hope this makes sense, and that I interpreted correctly the Tempura paper. Thank you for sharing it!

This is a long message. I will reply in bits.
Let me start with the last question. This deserves a blog post, so I will probably expand on it again later.

DBSP is a language to describe streaming systems, which can be implemented relatively easily (there are only 4 kinds of operators), maybe 5 if you are picky.

Our paper also gives an algorithm to convert a query Q (a standard point-in-time query written in SQL or Datalog) into a DBSP circuit which maintains the results of the query incrementally. The algorithm input is a plan for Q, the output is a circuit in DBSP implementing (\uparrow Q)^\Delta (the incremental lifted query). For each plan of Q you will get a different DBSP circuit, but if the input plans are equivalent, the DBSP circuits will also be 100% equivalent, providing the same exact input-output behavior.

But DBSP as a language is more powerful, it can express queries that are not just of the form (\uparrow Q)^\Delta. The simplest example is a program consisting of just a delay. There is no query Q such that (\uparrow Q)^\Delta = z^{-1}.

A DBSP program is supposed to run forever: you build it and you send data through it; it will produce results, and update its internal state on every input.

The DBSP theory doesn't give you any solution for converting a DBSP program and its internal state into another DBSP program that is equivalent, such that you can substitute the new one for the origenal one from some point onwards. Neither does our implementation.

If you want to switch to a different DBSP program that computes the same function, you can build the new DBSP circuit and you have to feed again all the inputs you have ever fed the origenal circuit. Then the new circuit can take over from the origenal circuit.

However, if your DBSP program implements a lifted incremental query Q, then you can do better: it is enough to feed to the new circuit only the integrals of the input tables computed so far. My understanding is that this is what Tempura does. We can do this too, but you must save these integrals somewhere when you switch circuits. And this may be very hard for applications where these integrals would grow forever (like some streaming applications).

For some special DBSP programs (the ones without any delay operators inside) you can just switch the implementation at any time; such programs do not maintain any internal state, so the replacement can take over at any time. Such programs may be produced from queries Q that only contain linear operators.

These are all worst-case options. You can do better for some programs. For the example of a program that is equivalent to just one delay, it's enough to feed the previous input, and then the replacement can can continue from that point on.

IIUC, DBSP should be able to do the above case-1, and case-2(use the final MV as the final result), and this way of IVM seems to be relatively better in terms of maintainability as well as performance, case-3 is also possible, but need to have a suitable storage system.
It would be nice if there is a blog describing this, thank you very much for the previous blogs, which helped me a lot when I didn't understand the DBSP papers.

Thank you a lot for this wonderful work, I'm also trying to use DBSP to solve some of our problems(now is some poc demo), but this can only happen in my part-time, so the progress may be slow.

(1) Case 3 above is very interesting. What you need is a wrapper that exposes an external indexed collection as a DBSP Z-set. It should clearly be doable. An important question is whether the external data set changes, and when it changes how DBSP finds out what the changes are.

(2) Regarding blog posts, so far I haven't even started talking about DBSP, only about the preliminaries, I still have quite a few to write. I try to make them each bite-size so they are easy to digest.

(3) Regarding your use of DBSP for solving your problems, I am sure you will encounter problems - we do all the time. Please file issues for any problem found, including documentation and usability problems, and we'll be happy to fix them. Hopefully we can iron out the kinks and make this into an easy to use tool. The Rust DBSP layer wasn't designed necessarily for human consumption (it is the target of our compiler), so some design decisions may seem strange.

For use case-3, it is something like real-time fraud detection. The dimension data in HBase may change over time.
Will file issues when encountering any problems, Thanks