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

51–56 of 56 posts

Re: Feldera Incremental Compute Engine

#51

Post by nikhilsimha »

lsuresh wrote: post #40
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…

We use monotonicity detection for various things. I believe (can double check) that it's used for max as well. But you're correct that in the general case, max is non-linear, so will need to maintain state. Update from Leonid on current implementation: each group is ordered by the column on which we compute max, so it's O(1) to pick the last value from the index.

So the writes are O(N) then - to keeps reads at O(1)?

Re: Feldera Incremental Compute Engine

#52

Post by ryzhyk »

nikhilsimha wrote: post #51
lsuresh wrote: post #40

Earlier quoted context omitted.

We use monotonicity detection for various things. I believe (can double check) that it's used for max as well. But you're correct that in the general case, max is non-linear, so will need to maintain state. Update from Leonid on current implementation: each group is ordered by the column on which we compute max, so it's O(1) to pick the last value from the index.

So the writes are O(N) then - to keeps reads at O(1)?

Both reads and writes are O(1) in time complexity. Writes additionally have the log(N) amortized cost of maintaining the LSM tree.

Re: Feldera Incremental Compute Engine

#53

Post by lsuresh »

nextaccountic wrote: post #47
lsuresh wrote: post #9

Earlier quoted context omitted.

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/

They're quite different from DBSP. Given a program execution, Salsa/adapton seem to reuse prior steps from an execution when the input changes.

In contrast, DBSP has built-in knowledge of incremental versions of operations and composes them. Here's a blurb from a recent paper we submitted:

  DBSP is not tied to databases in any way; it is in fact a Turing-complete language that can be used for many other purposes. But it works particularly well in the area of databases, for two reasons:
  – DBSP operates on values from a commutative group. Databases can be modeled as a commutative group.
  – DBSP reduces the problem of incrementalizing a complex program to the problem of incrementalizing each primitive operation that appears in the program. For databases there are known efficient incremental implementations for all primitive operations.
As to whether DBSP could be used for an incremental compiler backend, we think not (at least not with our current understanding). Would be cool to explore though.

Re: Feldera Incremental Compute Engine

#54

Post by nikhilsimha »

ryzhyk wrote: post #52
nikhilsimha wrote: post #51

Earlier quoted context omitted.

So the writes are O(N) then - to keeps reads at O(1)?

Both reads and writes are O(1) in time complexity. Writes additionally have the log(N) amortized cost of maintaining the LSM tree.

gotcha! thanks for the clarification

Re: Feldera Incremental Compute Engine

#55

Post by YmiYugy »

I tried the demo and it looks quite promising. Right now it seems to be focused on handling a few queries over high throughput streams. I wonder if it could also work for the following scenario. It behaves almost like a normal sql database, i.e. most data is cold on disk, queries are low latency, no need to predefined them, acid compliant, etc. Except you can subscribe to queries. That means the initial response needs to be as fast as in traditional databases and the database needs to be able to scale to large number concurrent subscriptions. If this where possible it could alleviate the common problem, that Web Apps that need to keep UI up to date, need to constantly poll the database, creating a lot of overhead and making anything but trivial queries a non starter.

Re: Feldera Incremental Compute Engine

#56

Post by lsuresh »

YmiYugy wrote: post #55

I tried the demo and it looks quite promising. Right now it seems to be focused on handling a few queries over high throughput streams. I wonder if it could also work for the following scenario. It behaves almost like a normal sql database, i.e. most data is cold on disk, queries are low latency, no need to predefined them, acid compliant, etc. Except you can subscribe to queries. That means the initial response need…

hi YmiYugy. We have a REST API to subscribe to a change stream (basically what the UI uses underneath).

Our ad-hoc query interface is about to receive snapshot-and-follow support as well which should do what you want. That way, you don't need to poll for changes.

Post reply on HN