HN user
Sounds like basic memoization and topological sort gets you all the way there?
I don't really want to pull rank here, but for the benefit of other readers: 100% nope.
I personally find the "make toxic comments to draw folks out" rhetorical style frustrating, so I'll just leave you with a video from Clojure/conj about how nice it would be to be able to use DD from Clojure, to get a proper reactive Datomic experience.
I think maybe they were confused by this text (which I agree has nothing to do with Rust itself breaking):
With the release of Apache Arrow 3.0.0 there are many breaking changes in the Rust implementation and as a result it has been necessary to comment out much of the code in this repository and gradually get each Rust module working again with the 3.0.0 release.
If SQL had a way of picking one row from a group, rather than aggregating over it, that would be immensely useful.
You can do this with a LATERAL join, if you want to avoid the jankiness of window functions. Lateral joins are just a programmatic way to introduce a correlated subquery. For example
SELECT department, first_name, gross_salary FROM
(SELECT DISTINCT department FROM salary) depts,
LATERAL (
SELECT first_name, gross_salary
FROM salary
WHERE department = depts.department
ORDER BY gross_salary DESC
LIMIT 3
)
TD lets you write whatever logic you want (it is fairly unopinionated on your logic and state).
Differential dataflow plugs in certain logic there, and it does indeed maintain a synopsis of what data have gone past, sufficient to respond to future updates but not necessarily the entirety of data that it has seen.
It would be tricky to implement DD over classic Spark, as DD relies on these synopses for its performance. There are some changes to Spark proposed in recent papers where it can pull in immutable LSM layers w/o reading them (e.g. just mmapping them) that might improve things, but until that happens there will be a gap.
It just comes down to something as simple as: "if I have shown you 1M different things, and now show you one more thing, what do you have to do to tell me whether that one thing is new or not?"
If you can keep a hash map of the things you've seen, then it is easy to respond quickly to that one new thing. If you are not allowed to maintain any state, then you don't have a lot of options to efficiently respond to the new thing, and most likely need to re-read the 1M things.
That's the benefit of being stateful. There is a cost too, which is that you need to be able to reconstruct your state in the case of a failure, but fortunately things like differential dataflow (built on TD) are effectively deterministic.
Also, I suspect "Spark" is a moving target. The original paper described something that was very much a batch processor; they've been trying to fix that since, and perhaps they've made some progress in the intervening years.
There are a few differences, the main one between Spark and timely dataflow is that TD operators can be stateful, and so can respond to new rounds of input data in time proportional to the new input data, rather than that plus accumulated state.
So, streaming one new record in and seeing how this changes the results of a multi-way join with many other large relations can happen in milliseconds in TD, vs batch systems which will re-read the large inputs as well.
This isn't a fundamentally new difference; Flink had this difference from Spark as far back as 2014. There are other differences between Flink and TD that have to do with state sharing and iteration, but I'd crack open the papers and check out the obligatory "related work" sections each should have.
For example, here's the first para of the Related Work section from the Naiad paper:
Dataflow Recent systems such as CIEL [30], Spark [42], Spark Streaming [43], and Optimus [19] extend acyclic batch dataflow [15, 18] to allow dynamic modification of the dataflow graph, and thus support iteration and incremental computation without adding cycles to the dataflow. By adopting a batch-computation model, these systems inherit powerful existing techniques including fault tolerance with parallel recovery; in exchange each requires centralized modifications to the dataflow graph, which introduce substantial overhead that Naiad avoids. For example, Spark Streaming can process incremental updates in around one second, while in Section 6 we show that Naiad can iterate and perform incremental updates in tens of milliseconds.
I think the main distinction is around "interactivity" and how long it takes from typing a query to getting results out. Once you stand up a Flink dataflow, it should move along a brisk clip. But standing up a new dataflow is relatively heavy-weight for them; typically you have to re-flow all of the data that feeds the query.
Materialize has a different architecture that allows more state-sharing between operators, and allows many queries to spin up in milliseconds. Primarily, this is when your query depends on existing relational data in pre-indexed form (e.g. joining by primary and foreign keys).
You can read a bit more in an overview blog post [0] and in more detail in a VLDB paper [1]. I'm sure there are a number of other quirks distinguishing Flink and Materialize, probably several in their favor, but this is the high-order bit for me.
[0] https://materialize.com/materialize-under-the-hood/ [1]: http://www.vldb.org/pvldb/vol13/p1793-mcsherry.pdf
It's a good question, but you'd have to ask them I think. Tamas (from Itemis) and I were in touch for a while, mostly shaking out why DD was out-performing their previous approach, but I haven't heard from him since.
My context at the time was that they were focused on doing single rounds of incremental updates, as in a PL UX, whereas DD aims at high throughput changes across multiple concurrent timestamps. That's old information though, so it could be very different now!
Here's my take on this, from a few months back:
https://materialize.com/lateral-joins-and-demand-driven-quer...
Min and max work using a hierarchical reduction tree, the dataflow equivalent of a priority queue. They will update, under arbitrary changes to the input relation, in time proportional to the number of those changes.
[...] it's hard for me to believe that your list of constraints is "there are none" especially when there are explicit-but-vague performance warnings in the docs.
I think we're done here. There's plenty to read if you are sincerely interested, it's all public to both try and read, but you'll need to find someone new to ask, ideally with a less adversarial communication style.
All queries are incrementally maintained with the property that we do work proportional to the number of records in difference at each intermediate stage of the query plan. That includes those with lateral joins; they are not an exception.
I'm not clear on your "all sorts of limitations"; you'll have to fill me in on them?
I don't think there is anything fundamentally different from an existing database. In all relational databases, some lateral joins can be expensive to compute. In Materialize, those same lateral joins will also be expensive to maintain.
I'd be surprised to hear you beat up postgres or SQL Server because they claim they can evaluate any SQL query, but it turns out that some SQL queries can be expensive. That's all we're talking about here.
I take this to mean that Materialize cannot efficiently maintain a view with lateral joins [...]
Well, no this isn't a correct take. Lateral joins introduce what is essentially a correlated subquery, and that can be surprisingly expensive, or it can be fine. If you aren't sure that it will be fine, check out the plan with the EXPLAIN statement.
Here's some more to read about lateral joins in Materialize:
https://materialize.com/lateral-joins-and-demand-driven-quer...
It's easier to describe the things that cannot be materialized.
The only rule at the moment is that you cannot currently maintain queries that use the functions `current_time()`, `now()`, and `mz_logical_timestamp()`. These are quantities that change automatically without data changing, and shaking out what maintaining them should mean is still open.
Other than that, any SELECT query you can write can be materialized and incrementally maintained.
Hi! I work at Materialize.
I think the right starter take is that Materialize is a deterministic compute engine, one that relies on other infrastructure to act as the source of truth for your data. It can pull data out of your RDBMS's binlog, out of Debezium events you've put in to Kafka, out of local files, etc.
On failure and restart, Materialize leans on the ability to return to the assumed source of truth, again a RDBMS + CDC or perhaps Kafka. I don't recommend thinking about Materialize as a place to sink your streaming events at the moment (there is movement in that direction, because the operational overhead of things like Kafka is real).
The main difference is that unlike an OLTP system, Materialize doesn't have to make and persist non-deterministic choices about e.g. which transactions commit and which do not. That makes fault-tolerance a performance feature rather than a correctness feature, at which point there are a few other options as well (e.g. active-active).
Hope this helps!
Hi, I work at Materialize.
You can read about Vertica's "Live Aggregate Projections" here:
https://www.vertica.com/docs/9.2.x/HTML/Content/Authoring/An...
In particular, there are important constraints like (among others)
The projections can reference only one table.
In Materialize you can spin up just about any SQL92 query, join eight relations together, have correlated subqueries, count distinct if you want. It is then all maintained incrementally.
The lack of caveats is the main difference from the existing systems.
Data anonymized with Amnesia are statistically guaranteed that they cannot be linked to the original data.
It looks like (from other text on their site) they use variants on k-anonymity. This can prevent re-linking attacks back to the original data, but we've also known for a decade that this isn't especially strong. For example, two independent k-anonymous releases can unique identify everyone in the dataset[0].
Naming things is hard.
In this case, the command does not create a new dataflow, it creates a new timely dataflow computation by executing the closure on multiple workers. The computation can then spin zero, one, or many dataflows interactively. Dataflows come and go as the computation runs.
It's a bit different, right, because that paper presents better algorithms on the same datasets as the work it cites.
Yeah, for example I have an open PR in differential dataflow to make some changes to avoid a planned break in the future.
https://github.com/TimelyDataflow/differential-dataflow/pull...
I think they are doing the right thing with the break (it adds something I've wanted) but at the same time it's another break.
That's not accurate.
Fwiw, I recorded at least four different times a Rust release broke timely / differential dataflow, and have seen a few others in other folks' code. Afaict, none of them were soundness related, and were instead due to ergonomic additions and performance improvements.
They haven't been recent (e.g. were 1.17, 1.20, and 1.22, and the others earlier) and I agree that things are much more stable now.
In SQL you would most likely be directed to use `WITH RECURSIVE`, which is something we plan to do, but not yet.
It can be a bit gross to use WITH RECURSIVE, because there are often some constraints on the types of queries you can express (e.g. that the recursive body must conclude with a UNION/UNION ALL with some base case). Differential dataflow doesn't have that requirement, but we'll have to sort out whether we'll remove that requirement for Materialize, or impose the traditional constraints. There is a Chesterton's fence moment to have first.
Whether it ends up being "appropriate" or not will be a great thing to determine. I anticipate eating a lot of crow when it turns out to be lots slower than bespoke graph processors. :)
edit: Thanks, btw!
By moving up the stack a bit (managing computation, rather than storage) we can provide consistency using techniques other than just using the guarantees provided by the storage itself. This isn't a new observation (Dryad/DryadLINQ made it wrt MapReduce/Hadoop, among other examples I'm sure) but that is where the trade-off lies.
If you instead implement low-latency systems where each step along a dataflow involves a round-trip through replicated highly available storage, Spanner if you like or even just Kafka, then 100% you might reasonably conclude that eventual consistency is the right call. This is roughly the situation that microservice implementors currently find themselves in. I don't think it is a great situation to be in, personally.
The value proposition with something like Materialize (and there are other options) is that you can get consistency and performance if you can express your computation as something more structured than imperative code that writes to and reads from storage. In our case, the "something" is SQL.
Hope that helps!
That title goes to "no tracking"
This is roughly analogous to "abstinence is the best form of birth control". It's not wrong, but it also isn't particularly realistic or helpful. The reality is that people often do want to exchange data, some times because it is legally or morally mandated, and tools that allow this to be done as safely as possible are important.
If you have free cycles, you can read more here:
https://github.com/frankmcsherry/blog/blob/master/posts/2017...
The projects you've mentioned are attempts to address stream processing needs with a SQL-like language. That is fundamentally different from providing incremental view maintenance of actual SQL using streaming techniques (what Materialize does).
If you want to maintain the results of a SQL query with a correlated subquery, StreamSQL in Aurora did not do that (full query decorrelation is relatively recent, afaiu). I have no idea what TIBCO's current implementation does.
If you want to maintain the results of a SQL query containing a WITH RECURSIVE fragment, you can do this in differential dataflow today (and in time, Materialize). I'm pretty sure you have no chance of doing this in StreamSQL or CCL or CQL or BEAM or ...
The important difference is that lots of people do actually want to maintain their SQL queries, and are not satisfied with "SQL inspired" languages that are insert-only (Aurora), or require windows on joins, or only cover the easy cases.
Hi folks. Frank from Materialize here.
The main differences you should expect to see are generality and performance.
Generality, in that there are fewer limitations on what you can express. Oracle (and most RDBMSs) build their Incremental View Maintenance on their existing execution infrastructure, and are limited by the queries whose update rules they can fit in that infrastructure. We don't have that limitation, and are able to build dataflows that update arbitrary SQL92 at the moment. Outer joins with correlated subqueries in the join constraint; fine.
Performance, in that we have the ability to specialize computation for incremental maintenance in a way that RDBMSs are less well equipped to do. For example, if you want to maintain a MIN or MAX query, it seems Oracle will do this quickly only for insert-only workloads; on retractions it re-evaluates the whole group. Materialize maintains a per-group aggregation tree, the sort of which previously led to a 10,000x throughput increase for TPCH Query 15 [0]. Generally, we'll build and maintain a few more indexes for you (automatically) burning a bit more memory but ensuring low latencies.
As far as I know, Timescale's materialized views are for join-free aggregates. Systems like Druid were join-free and are starting to introduce limited forms. KSQLdb has the same look and feel, but a. is only eventually consistent and b. round-trips everything through Kafka. Again, all AFAIK and could certainly change moment by moment.
Obviously we aren't allowed to benchmark against Oracle, but you can evaluate our stuff and let everyone know. So that's one difference.
[0] https://github.com/TimelyDataflow/differential-dataflow/tree...
The Tightyl is gorgeous, btw, and made me start to think about what a 3d printer could do for me. For others, check it out at:
I think the median of the results works great in any case (but, you are the expert here). If we find the result median in each of the two inputs, say 'a' and 'b' we have four merges (two forward, two reverse):
[0, ..) w (0, ..)
(.., a) w (.., b)
[a, ..) w [b, ..)
(.., n) w (.., n)
If the array is already sorted then great; that split will just "merge":
[0, ..) w nothing
(.., n/2) w nothing
nothing w [n/2, ..)
nothing w (.., n)
Thanks for the interesting post! I liked the MergeDouble approach which I hadn’t seen before. Couldn’t that be extended to finding the median of the results using binary search and then doing four concurrent merges, for even more ILP?
Your example join output at https://imply.io/post/introducing-apache-druid-0-18-0 has the incorrect answers for the join.