5 ms·

Differential Dataflow for Mere Mortals

137 points by luu 5y ago

user3939382 5y ago
I started studying SQL when I was a freshman in high school circa 2000, the book I had was called SQL Queries for Mere Mortals. Is this a play on that, or was that title an homage to something even earlier?
- outside1234 5y ago
  I think it is a slight swipe at how complicated the Materialize OSS projects make everything in this space sound
  - thelastbender12 5y ago
    That is because doing incremental computation efficiently is complicated! I'd think the project idea is that differential dataflow is too useful a technology to only be understood by a few people. By writing it a second time around, it might be feasible to trade off some of its power for a more lean and accessible implementation.
  - FridgeSeal 5y ago
    To be fair, whilst the underlying theory is pretty conceptually straightforward (as illustrated here), fully-featured/non-toy implementations, especially when it intersects with a database are somewhat more complex.
  - deleted 5y ago
    [deleted]
- z3t4 5y ago
  It's a saying that you do not have to be a genius to understand it. For example the em edtior (editor for mere mortals) where you could see what you wrote on the screen instead of having to keep it all in your head... https://en.wikipedia.org/wiki/Vi https://en.wikipedia.org/wiki/Vi
rstuart4133 5y ago
I love clear, simple language like this. Kudo's to the author: > The jargon-free version: You write code that manipulates collections using familiar operations like map, join and loop. You run the code on some input and get some output. Then when the input changes, you get changes to the output, much faster than recomputing the whole thing from scratch. (And the outputs will be correct!) A complete newbie can read those two sentences and get the complete picture.
- zozbot234 5y ago
  That description is clear and simple indeed, but these are generally called "dynamic" https://en.wikipedia.org/wiki/Dynamic_algorithm https://en.wikipedia.org/wiki/Dynamic_algorithm in the literature. "Differential" refers to something else altogether, namely being able to automatically compute the gradient of some general calculation on continuous-valued inputs! (The intersection of differential and dynamic problems, where the point is to recompute answers quickly when some continuous-valued input changes, is called "kinetic".)
  - maweki 5y ago
    Differential Dataflow is (and has been for ages) the name of calculating the result of a Datalog query and yielding delta-sets of the result given delta-sets of the database. The name "differential" is not exclusive to gradients of continuous functions.
    - zozbot234 5y ago
      Could you provide a source that shows "differential" being used in such a context by the Datalog community? Regardless, the proper term for this in the general CS/algorithms literature is "dynamic" as I've shown above. "Differential" is used for something else entirely, and "kinetic" covers the notable shared aspects of the two problem domains.
      - maweki 5y ago
        https://raw.githubusercontent.com/TimelyDataflow/differential-dataflow/master/differentialdataflow.pdf https://raw.githubusercontent.com/TimelyDataflow/differentia...
modeless 5y ago
I wonder if you could implement a compiler with this.
- sriram_malhar 5y ago
  Most language structures are acyclic, so a simple dataflow pipeline is sufficient. Mutual references (class A referring to class B and vice versa) are resolved by separating the signature from method implementation (for example) to break cycles.
- FridgeSeal 5y ago
  Someone who knows more can probably correct/refine me, but I believe Rusts compiler actually has a little “differential datalog” engine it, which uses differential data flow under the hood.
  - akiselev 5y ago
    They used to but Frank McSherry (author of differential dataflow) wrote them a specialized version without all the dataflow infrastructure [1]. It's part of the rust-lang nursery [2] now but hasn't been updated in a while, so I'm not sure what happened to it. Edit: Looks like the rustc_mir crate that implements the non-lexical borrow checker uses `polonius_engine` [3] which uses `datafrog` so it's still used by the compiler! [1] https://github.com/frankmcsherry/blog/blob/master/posts/2018-05-19.md https://github.com/frankmcsherry/blog/blob/master/posts/2018... [2] https://github.com/rust-lang/datafrog https://github.com/rust-lang/datafrog [3] https://crates.io/crates/polonius-engine https://crates.io/crates/polonius-engine
missingstep3 5y ago
With the jargon-free version of this concept I can think of an example. To recompute the sum of the elements of a vector when one of the elements change you just add the new - old value to the sum. I'm I right?
- Garlef 5y ago
  Yes; Or: If you have a very long list of integers, for example [1, 2, ..., 12351234] and your output would be the same list but all numbers increased by one (keeping the index/order): [2, 3, ..., 1235123]. If you now add a new element to the end of the initial list, you'd only have to add one element to your output instead of iterating over the whole list.

137 points by luu 5y ago

I started studying SQL when I was a freshman in high school circa 2000, the book I had was called SQL Queries for Mere Mortals. Is this a play on that, or was that title an homage to something even earlier?

outside1234 5y ago
I think it is a slight swipe at how complicated the Materialize OSS projects make everything in this space sound
- thelastbender12 5y ago
  That is because doing incremental computation efficiently is complicated! I'd think the project idea is that differential dataflow is too useful a technology to only be understood by a few people. By writing it a second time around, it might be feasible to trade off some of its power for a more lean and accessible implementation.
- FridgeSeal 5y ago
  To be fair, whilst the underlying theory is pretty conceptually straightforward (as illustrated here), fully-featured/non-toy implementations, especially when it intersects with a database are somewhat more complex.
- deleted 5y ago
  [deleted]
z3t4 5y ago
It's a saying that you do not have to be a genius to understand it. For example the em edtior (editor for mere mortals) where you could see what you wrote on the screen instead of having to keep it all in your head... https://en.wikipedia.org/wiki/Vi https://en.wikipedia.org/wiki/Vi

rstuart4133 5y ago

I love clear, simple language like this. Kudo's to the author: > The jargon-free version: You write code that manipulates collections using familiar operations like map, join and loop. You run the code on some input and get some output. Then when the input changes, you get changes to the output, much faster than recomputing the whole thing from scratch. (And the outputs will be correct!) A complete newbie can read those two sentences and get the complete picture.

zozbot234 5y ago
That description is clear and simple indeed, but these are generally called "dynamic" https://en.wikipedia.org/wiki/Dynamic_algorithm https://en.wikipedia.org/wiki/Dynamic_algorithm in the literature. "Differential" refers to something else altogether, namely being able to automatically compute the gradient of some general calculation on continuous-valued inputs! (The intersection of differential and dynamic problems, where the point is to recompute answers quickly when some continuous-valued input changes, is called "kinetic".)
- maweki 5y ago
  Differential Dataflow is (and has been for ages) the name of calculating the result of a Datalog query and yielding delta-sets of the result given delta-sets of the database. The name "differential" is not exclusive to gradients of continuous functions.
  - zozbot234 5y ago
    Could you provide a source that shows "differential" being used in such a context by the Datalog community? Regardless, the proper term for this in the general CS/algorithms literature is "dynamic" as I've shown above. "Differential" is used for something else entirely, and "kinetic" covers the notable shared aspects of the two problem domains.
    - maweki 5y ago
      https://raw.githubusercontent.com/TimelyDataflow/differential-dataflow/master/differentialdataflow.pdf https://raw.githubusercontent.com/TimelyDataflow/differentia...

modeless 5y ago

I wonder if you could implement a compiler with this.

sriram_malhar 5y ago
Most language structures are acyclic, so a simple dataflow pipeline is sufficient. Mutual references (class A referring to class B and vice versa) are resolved by separating the signature from method implementation (for example) to break cycles.
FridgeSeal 5y ago
Someone who knows more can probably correct/refine me, but I believe Rusts compiler actually has a little “differential datalog” engine it, which uses differential data flow under the hood.
- akiselev 5y ago
  They used to but Frank McSherry (author of differential dataflow) wrote them a specialized version without all the dataflow infrastructure [1]. It's part of the rust-lang nursery [2] now but hasn't been updated in a while, so I'm not sure what happened to it. Edit: Looks like the rustc_mir crate that implements the non-lexical borrow checker uses `polonius_engine` [3] which uses `datafrog` so it's still used by the compiler! [1] https://github.com/frankmcsherry/blog/blob/master/posts/2018-05-19.md https://github.com/frankmcsherry/blog/blob/master/posts/2018... [2] https://github.com/rust-lang/datafrog https://github.com/rust-lang/datafrog [3] https://crates.io/crates/polonius-engine https://crates.io/crates/polonius-engine

missingstep3 5y ago

With the jargon-free version of this concept I can think of an example. To recompute the sum of the elements of a vector when one of the elements change you just add the new - old value to the sum. I'm I right?

Garlef 5y ago
Yes; Or: If you have a very long list of integers, for example [1, 2, ..., 12351234] and your output would be the same list but all numbers increased by one (keeping the index/order): [2, 3, ..., 1235123]. If you now add a new element to the end of the initial list, you'd only have to add one element to your output instead of iterating over the whole list.