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

Streaming joins are hard

estuary.dev

Post reply on HN
Print view View original

31–40 of 60 posts

Re: Streaming joins are hard

#31

Post by ryzhyk »

incr_me wrote: post #27
ryzhyk wrote: post #22

Earlier quoted context omitted.

We have our own formal model called DBSP: https://docs.feldera.com/papers It is indeed inspired by timely/differential, but is not exactly comparable to it. One nice property of DBSP is that the theory is very modular and allows adding new incremental operators with strong correctness guarantees, kind of LEGO brick for incremental computation. For example we have a fully incremental implementation of rolling aggregat…

Are you aware of any efforts to apply DBSP's theory to a general programming language/environment? From my perspective, DDlog was the most inspiring project in the field of incremental computation, but it seems like all of these projects just lead to implementations of streaming databases or other similar commercial products that fit into Data™ pipelines (no offense). Incremental computation pops up everywhere, from…

Thanks for the kind words about DDlog :)

The reason DBSP and Differential Dataflow work so well is because they are specialized to relational computations. Relational operators have nice properties that allow evaluating them incrementally. Incremental evaluation for a general purpose language like Rust is a much, much harder problem.

FWIW, DBSP is available as a Rust crate (https://crates.io/crates/dbsp), so you can use it as an embedded incremental compute engine inside your program.

Re: Streaming joins are hard

#32

Post by qazxcvbnm »

ryzhyk wrote: post #18

The correct way to think about the problem is in terms of evaluating joins (or any other queries) over changing datasets. And for that you need an engine designed for *incremental* processing from the ground up: algorithms, data structures, the storage layer, and of course the underlying theory. If you don't have such an engine, you're doomed to build layer of hacks, and still fail to do it well. We've been building…

Hi, I’ve read the DBSP paper and it’s a really well-thought out framework; all the magic seemed so simple with the way the paper laid things out. However, the paper dealt with abelian Z-sets only, and mentioned that in your implementation, you also handle the non-abelian aspect of ordering. I was wondering if you guys have published about how did you that?

Re: Streaming joins are hard

#33

Post by [deleted] »

ryzhyk wrote: post #18

The correct way to think about the problem is in terms of evaluating joins (or any other queries) over changing datasets. And for that you need an engine designed for *incremental* processing from the ground up: algorithms, data structures, the storage layer, and of course the underlying theory. If you don't have such an engine, you're doomed to build layer of hacks, and still fail to do it well. We've been building…

[deleted]

Re: Streaming joins are hard

#34

Post by majormajor »

crazygringo wrote: post #21
BeefWellington wrote: post #9

Earlier quoted context omitted.

I'll use a contrived example here to explain what the value of streaming the data itself is. Let's say you run a large installation that has a variety of very important gauges and sensors. Due to the size and complexity of this installation, these gauges and sensors need to be fed back to a console somewhere so that an overseer role of sorts can get that big picture view to ensure the installation is functioning full…

I definitely understand the value of streaming. Your gauges example is great. What I don't understand is streaming joins. None of your gauge values need to join to anything. And if they did -- if something needed to join ID values to display names, presumably those would sit in a database, not a different stream?

> And if they did -- if something needed to join ID values to display names, presumably those would sit in a database, not a different stream?

At a high level the push-instead-of-pull benefit here is "you don't have to query the ID values to get the display names every time" which will reduce your latency. (You can cache but then you might get into invalidation issues and start thinking "why not just send the updates directly to my cache instead")

There's also a less cacheable version where both sides are updating more frequently and you have logic like "if X=1 and Y=2 do Z."

For small enough batches streaming and micro-batching do often end up very similar.

Re: Streaming joins are hard

#35

Post by majormajor »

ryzhyk wrote: post #18

The correct way to think about the problem is in terms of evaluating joins (or any other queries) over changing datasets. And for that you need an engine designed for *incremental* processing from the ground up: algorithms, data structures, the storage layer, and of course the underlying theory. If you don't have such an engine, you're doomed to build layer of hacks, and still fail to do it well. We've been building…

Does this offer any non-SQL programmatic interfaces or ways to do Complex Event Processing (e.g. https://www.databricks.com/glossary/complex-event-processing )? A lot of those scenarios would be tough to express in SQL.

Re: Streaming joins are hard

#36

Post by fnordpiglet »

crazygringo wrote: post #7

Can someone explain what the use case is for streaming joins in the first place? I've written my fair share of joins in SQL. They're indispensable. But I've never come across a situation where I needed to join data from two streams in real time as they're both coming in. I'm not sure I even understand what that's supposed to mean conceptually. It's easy enough to dump streams into a database and query the database bu…

This is extremely common in trading systems where real time data is joined against reference data and grouped, etc for a variety of purposes including consumption by algorithms and display.

Re: Streaming joins are hard

#37

Post by anonymoushn »

ryzhyk wrote: post #22
d0mine wrote: post #19

Earlier quoted context omitted.

Is it related to Differential Dataflow / timely dataflow https://github.com/TimelyDataflow/differential-dataflow

We have our own formal model called DBSP: https://docs.feldera.com/papers It is indeed inspired by timely/differential, but is not exactly comparable to it. One nice property of DBSP is that the theory is very modular and allows adding new incremental operators with strong correctness guarantees, kind of LEGO brick for incremental computation. For example we have a fully incremental implementation of rolling aggregat…

Fast rolling aggregates are swell. I meet a lot of people who are building trading systems and want this sort of thing, but it usually isn't a great choice because the perfectly rectangular kernel probably isn't the best possible version of the feature and because arbitrary kernels can be well approximated using a state of constant size rather than a large buffer storing a sliding window.

Re: Streaming joins are hard

#38

Post by incr_me »

ryzhyk wrote: post #31
incr_me wrote: post #27

Earlier quoted context omitted.

Are you aware of any efforts to apply DBSP's theory to a general programming language/environment? From my perspective, DDlog was the most inspiring project in the field of incremental computation, but it seems like all of these projects just lead to implementations of streaming databases or other similar commercial products that fit into Data™ pipelines (no offense). Incremental computation pops up everywhere, from…

Thanks for the kind words about DDlog :) The reason DBSP and Differential Dataflow work so well is because they are specialized to relational computations. Relational operators have nice properties that allow evaluating them incrementally. Incremental evaluation for a general purpose language like Rust is a much, much harder problem. FWIW, DBSP is available as a Rust crate ( https://crates.io/crates/dbsp ), so you ca…

Indeed. I've experimented a bit with abusing DD/DBSP for my purposes by modeling various kinds of data structures in terms of Z-sets, but these efforts have not yielded very impressive results. :)

For how elegant DBSP is I still found the paper a tough nut to crack, and it really is one of the more accessible theoretical contributions in the space, at least from this grubby programmer's perspective... I hope to devote some time to study and play around more, but in the meantime I'm rooting for you!

Re: Streaming joins are hard

#39

Post by trollied »

crazygringo wrote: post #24
GeneralMayhem wrote: post #15

Earlier quoted context omitted.

Event correlations are a typical one. Think about ad tech: you want every click event to be hydrated with information about the impression or query that led to it. Both of those are high-volume log streams. You want to end up with the results of: ``` select * from clicks left join impressions on (clicks.impression_id=impressions.id) ``` but you want to see incremental results - for instance, because you want to feed…

That's helpful, thanks. I was definitely under the impression that ad impressions and clicks would be written to databases immediately and queried from there. I'm still having a hard time imagining in what case you'd need a "live" aggregating display that needed to join data from multiple streams, rather than just accumulating from individual streams, but I guess I can imagine that there are circumstances where that…

I have worked on systems that used Oracle Materialised Views for this. The aggregates get updated in realtime, and you don't need to run a heavy query every time.

Re: Streaming joins are hard

#40

Post by kalaracey »

incr_me wrote: post #27
ryzhyk wrote: post #22

Earlier quoted context omitted.

We have our own formal model called DBSP: https://docs.feldera.com/papers It is indeed inspired by timely/differential, but is not exactly comparable to it. One nice property of DBSP is that the theory is very modular and allows adding new incremental operators with strong correctness guarantees, kind of LEGO brick for incremental computation. For example we have a fully incremental implementation of rolling aggregat…

Are you aware of any efforts to apply DBSP's theory to a general programming language/environment? From my perspective, DDlog was the most inspiring project in the field of incremental computation, but it seems like all of these projects just lead to implementations of streaming databases or other similar commercial products that fit into Data™ pipelines (no offense). Incremental computation pops up everywhere, from…

(Not who you are replying to) Not sure if it’s specifically related to DBSP but checkout incremental DataFun (slide ~55 of https://www.rntz.net/files/stl2017-datafun-slides.pdf) and the paper cited there: A Theory of Changes for Higher Order Languages: Incrementalizing Lambda-calculi by Static Differentiation (Cai et. al, PLDI 2014).
Post reply on HN