Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Feldera Incremental Compute Engine

github.com

Post reply on HN
Print view View original

41–50 of 56 posts

Re: Feldera Incremental Compute Engine

#41

Post by lsuresh »

shuaiboi wrote: post #39
nikhilsimha wrote: post #36

Earlier quoted context omitted.

dumb question: how do z-sets or feldera deal with updates to values that were incorporated into the max already? For example - max over {4, 5} is 5. Now I update the 5 to a 3, so the set becomes {4, 3} with a max of 4. This seems to imply that the z-sets would need to store ALL the values - again, in their internal state. Also there needs to be some logic somewhere that says that the data structure for updating value…

Just a guess... wouldl like to hear the answer as well. they probably have a monotonicity detector somewhere, which can decide whether to keep all the values or discard them. If they keep them, they probably use something like a segment tree to index.

Yes, we do a lot of work with monotonicity detection. It's central to we perform automatic garbage collection based on lateness.

Re: Feldera Incremental Compute Engine

#42

Post by lsuresh »

shuaiboi wrote: post #34

would something like dbsp support spreadsheet style computations? Most of the financial world is stuck behind spreadsheets and the entire process of productioinizing spreadsheets is broken: * Engineers don't have time to understand the spreadsheet logic and translate everything into an incremental version for production. * Analysts don't understand the challenges with stream processing. * SQL is still too awkward of…

Great question. DBSP should work here -- spreadsheets are by definition incremental (and there's even recursive queries there with cells depending on each other).

Note that we use Z-Sets to bridge SQL/tables with DBSP, but Z-Sets aren't general enough for spreadsheets.

Re: Feldera Incremental Compute Engine

#43

Post by rebanevapustus »

shuaiboi wrote: post #38
rebanevapustus wrote: post #30

Big fan of Feldera here. I would advise everybody to stay clear of anything that isn't Feldera or Materialize. Nobody aside from these guys have a IVM product that is grounded on proper theory. If you are interested in trying out the theory (DBSP) underneath Feldera, but in Python, then check this out: https://github.com/brurucy/pydbsp It works with pandas, polars...anything.

This is pretty neat but I'm wondering how well this implementation obeys dataframe algebra. Ponder goes into detail about how dataframes and relations aren't the same, but your dataframe zset seems to be more or less the exact same thing as the relation zset? https://youtu.be/7TyIjqvfWto?si=CMFH30DFEWxkltlw&t=1095

It does not. The example I give on the README is only meant to show how easy it is to use it to "streamify" regular relational Dataframe operations.

Re: Feldera Incremental Compute Engine

#44

Post by ryzhyk »

shuaiboi wrote: post #39
nikhilsimha wrote: post #36

Earlier quoted context omitted.

dumb question: how do z-sets or feldera deal with updates to values that were incorporated into the max already? For example - max over {4, 5} is 5. Now I update the 5 to a 3, so the set becomes {4, 3} with a max of 4. This seems to imply that the z-sets would need to store ALL the values - again, in their internal state. Also there needs to be some logic somewhere that says that the data structure for updating value…

Just a guess... wouldl like to hear the answer as well. they probably have a monotonicity detector somewhere, which can decide whether to keep all the values or discard them. If they keep them, they probably use something like a segment tree to index.

That's right, we perform static dataflow analysis to determine what data can get discarded. GC itself is done lazily as part of LSM tree maintenance. For MAX specifically, we don't have this optimization yet. In the general case, incrementally maintaining the MAX aggregate in the presence of insertions and deletions requires tracking the entire contents of the group, which is what we do. If the collection can be proved to be append-only, then it's sufficient to store only the current max element. This optimization is yet coming to Feldera.

Re: Feldera Incremental Compute Engine

#45

Post by nextaccountic »

lsuresh wrote: post #14
arn3n wrote: post #13

If you don’t want to change your whole stack, ClickHouse’s Materialized Views do something extraordinarily similar, where computations are ran on inserts to the source table in an online/streaming manner. I’m curious how this solution compares in its set of features/gaurantees.

For incremental computation, Feldera is just way more powerful and general. It can evaluate arbitrarily sophisticated SQL programs incrementally (tables and deeply nested layers of views). For example, it can do rolling aggregates over joins, handle late and out-of-order arrivals, can compute over infinite streams with finite state (via automatic garbage collection), and it's strongly consistent. Clickhouse's materia…

Could Feldera be a Postgres extension?

Re: Feldera Incremental Compute Engine

#46

Post by nextaccountic »

jamesblonde wrote: post #33
rebanevapustus wrote: post #30

Big fan of Feldera here. I would advise everybody to stay clear of anything that isn't Feldera or Materialize. Nobody aside from these guys have a IVM product that is grounded on proper theory. If you are interested in trying out the theory (DBSP) underneath Feldera, but in Python, then check this out: https://github.com/brurucy/pydbsp It works with pandas, polars...anything.

It's based on Z-Sets - a generalization of relational algebra. Many of the aggregations, projections, filters from SQL are associative and can be implemented in Z-Sets. Z-Sets supports incremental operations (adding one value to a set while computing the 'max' is just the max of the two arguments - rather than requiring recomputing the 'max' over the entire set.

> Z-Sets - a generalization of relational algebra

Does this have a paper or some material describing the theory?

Re: Feldera Incremental Compute Engine

#47

Post by nextaccountic »

lsuresh wrote: post #9
Nelkins wrote: post #4

I would love if something like this that exposed C bindings so that every language with an FFI could use the library. I’d love to be able to define pipelines and queries in .NET instead of having to use SQL.

Hi Nelkins. We do have a Rust crate you could consider using directly: https://docs.rs/dbsp/latest/dbsp/ . Our SQL compiler puts together a pipeline by generating a Rust program that uses this crate.

How do you compare the dbsp crate with other libraries for incremental computation, like salsa [0] and adapton [1]?

Could dbsp work as a backend for an incremental compiler?

[0] https://github.com/salsa-rs/salsa

[1] https://docs.rs/adapton/latest/adapton/

Re: Feldera Incremental Compute Engine

#48

Post by lsuresh »

nextaccountic wrote: post #46
jamesblonde wrote: post #33

Earlier quoted context omitted.

It's based on Z-Sets - a generalization of relational algebra. Many of the aggregations, projections, filters from SQL are associative and can be implemented in Z-Sets. Z-Sets supports incremental operations (adding one value to a set while computing the 'max' is just the max of the two arguments - rather than requiring recomputing the 'max' over the entire set.

> Z-Sets - a generalization of relational algebra Does this have a paper or some material describing the theory?

This is our paper describing the theory underlying Feldera: https://www.vldb.org/pvldb/vol16/p1601-budiu.pdf

Re: Feldera Incremental Compute Engine

#49

Post by Nelkins »

Does anybody have a good resource to learn about the differences between things like Feldera, Materialize, Adapton, and other developments in the incremental computation space? Where are the experts hanging out? What are they reading?

Re: Feldera Incremental Compute Engine

#50

Post by lsuresh »

Nelkins wrote: post #49

Does anybody have a good resource to learn about the differences between things like Feldera, Materialize, Adapton, and other developments in the incremental computation space? Where are the experts hanging out? What are they reading?

We have a small community over at the Feldera Slack channel you could join. We often have have deeply technical discussions about the incremental computation space, papers, concepts etc over there.
Post reply on HN