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

EventReduce: An algorithm to optimize database queries that run multiple times

github.com

Post reply on HN
Print view View original

41–50 of 87 posts

Re: EventReduce: An algorithm to optimize database queries that run multiple times

#41

Post by eventreduce »

ComodoHacker wrote: post #37
eventreduce wrote: post #24

Earlier quoted context omitted.

Yes this is correct. The performance benefit comes from doing all this stuff on the CPU instead of using disc-io. Also the internal binary decision diagram of EventReduced is optimized in a way to run less logic then a query would do. This makes it even faster then running the query again with an in-memory database.

And the main cost of this (questionable IMO) benefit is losing consistency, which is losing any change to DB not coming from the calling app. You haven't mentioned this cost anywhere.

The writes are not tunneled somehow through this algorithm. You still use the database like your normally would do. So the consistency is not affected.

Also this is an open source project, not something I want to sell you. Feel free to make a PR/issue with any open topics that are not mentioned in the docs.

Re: EventReduce: An algorithm to optimize database queries that run multiple times

#42

Post by eventreduce »

truth_seeker wrote: post #35

IMO An open cursor of Change Stream with Aggregation pipeline (for given use-case) in MongoDB is more flexible solution to achieve this functionality. In addition, it also tracks the history of changes and hence allows the cursor to go back if needed with "resumeToken" https://docs.mongodb.com/manual/changeStreams/

There is a big difference between a change-stream and a realtime query. For example mongodbs cursor-stream is a good way to observe the events that happen to a specific collection or documents that match some criteria. If you want the realtime-results of a query that has sorting, skip limit etc. than it is really hard to warp the changestream into this. In fact this is exactly what EventReduce could do for you.

For more information about the difference I recommend the video "Real-Time Databases Explained: Why Meteor, RethinkDB, Parse & Firebase Don't Scale" https://www.youtube.com/watch?v=HiQgQ88AdYo&t=1703s

Re: EventReduce: An algorithm to optimize database queries that run multiple times

#43

Post by LunaSea »

theandrewbailey wrote: post #39
LunaSea wrote: post #38

Earlier quoted context omitted.

Right but that's when you explicitly ask for it. However, you can't ask ask PostgreSQL to run a query and also return the query plan used for said query.

Unless there's some weird edge case that I'm not aware of, Postgres will execute what it's planner tells it to. Passing a query to EXPLAIN will show the plan.

Query plans are based on database statistics.

Explain will calculate the query plan for a query.

Explain analyze will calculate the query plan, run the query and compare the query plan expectations to reality.

However, if statistics change, so does the query plan. So if you run a query then run the same query again with explain analyze, you don't have a guarantee of getting the same information back. And since explain analyze doesn't return the query results you are obligated to run two separated queries.

Re: EventReduce: An algorithm to optimize database queries that run multiple times

#44

Post by eventreduce »

LunaSea wrote: post #30

Databases like PostgreSQL don't offer insights into the query plans, does EventReduce parse the SQL statements to determine which tables and rows will be affected by a query and run the appropriate caching or cache invalidation logic?

This is a great question. So EventReduce is only the algorithm that calculates your new results. The parsing of SQL is not done by it, you have to bring it by yourself. This works over providing some information about the query like Sort-fields and query-matchers. This is described good in the JavaScript implementation [1]. Providing this functions works easy for NoSQL-Queries because they are better composable. For SQL-queries you have to do some work before you can use EventReduce.

Also see the limitations of EventReduce in the readme.

[1] https://github.com/pubkey/event-reduce/tree/master/javascrip...

Re: EventReduce: An algorithm to optimize database queries that run multiple times

#45

Post by LunaSea »

theandrewbailey wrote: post #40
LunaSea wrote: post #30

Databases like PostgreSQL don't offer insights into the query plans, does EventReduce parse the SQL statements to determine which tables and rows will be affected by a query and run the appropriate caching or cache invalidation logic?

> Databases like PostgreSQL don't offer insights into the query plans How so? https://www.postgresql.org/docs/current/sql-explain.html https://stackoverflow.com/questions/7359702/how-do-i-obtain-... https://mariadb.com/kb/en/analyze-statement/ https://docs.oracle.com/cd/B19306_01/server.102/b14211/ex_pl...

This is only for queries where you explicitly want the query plan.

However, your query won't return the query results.

And regular PostgreSQL queries don't let you return the query plan they used on top the query results.

Re: EventReduce: An algorithm to optimize database queries that run multiple times

#46

Post by cntlzw »

"EventReduce can be used with relational databases but not on relational queries that run over multiple tables/collections."

Forgive my ignorance, but that is the whole point of working with a relational database. If cannot use JOINS then this solves only a very limited use case.

Re: EventReduce: An algorithm to optimize database queries that run multiple times

#47

Post by j-pb »

pgt wrote: post #33
j-pb wrote: post #29

Earlier quoted context omitted.

They also allow for arbitrary joins. Basically every valid SQL query can be turned into a stream by Materialize which is pretty amazing. This algorithm is limited to single table aggregates I think?

It should be able to aggregate across multiple tables, but it might need intermediate views. Can you give an example?

"EventReduce can be used with relational databases but not on relational queries that run over multiple tables/collections. (you can use views as workarround so that you can query over only one table). In theory Event-Reduce could also be used for realational queries but I did not need this for now. Also it takes about one week on an average machine to run all optimizations, and having more state functions looks like an NP problem."

And this doesn't even take into account recursive queries.

It's to bad that the EventReduce algorithm doesn't come with a paper, I'd love to compare the two.

If EventReduce needs joins to be delegated to views then it doesn't solve the really hard parts of view maintenance. Interleaving nested joins and aggregates also wouldn't be possible, because the aggregation and join live in separate worlds. And a lot of queries actually have that property. I guess you could push down all joins into a single megatable and then group-by the living hell out of stuff to get back the structure but that would create an O(insane) cartesian product from your database.

Materialize on the other hand is basically the holy grail of view maintenance. It supports ANSI SQL, which is a lot, and it's using the culminated work on differential dataflow and timely dataflow. Also it's written in Rust.

My prediction is in 10 years we'll all be using it in our backends and frontends. You'll stream live updates from your sql database to your frontent where it will completely replace React and Js with Rust and a local db that has the UI as a maintained view.

Re: EventReduce: An algorithm to optimize database queries that run multiple times

#49

Post by lovasoa »

cntlzw wrote: post #46

"EventReduce can be used with relational databases but not on relational queries that run over multiple tables/collections." Forgive my ignorance, but that is the whole point of working with a relational database. If cannot use JOINS then this solves only a very limited use case.

Noria [1] is a research database that solves the same problem while still supporting all relational database queries.

[1] https://github.com/mit-pdos/noria

Re: EventReduce: An algorithm to optimize database queries that run multiple times

#50

Post by twic »

ComodoHacker wrote: post #37
eventreduce wrote: post #24

Earlier quoted context omitted.

Yes this is correct. The performance benefit comes from doing all this stuff on the CPU instead of using disc-io. Also the internal binary decision diagram of EventReduced is optimized in a way to run less logic then a query would do. This makes it even faster then running the query again with an in-memory database.

And the main cost of this (questionable IMO) benefit is losing consistency, which is losing any change to DB not coming from the calling app. You haven't mentioned this cost anywhere.

> For the different implementations in common browser databases, we can observe an up to 12 times faster displaying of new query results after a write occurred.

Is this intended to be an optimisation on top of localStorage and so on? If so, at least you don't have to worry about multiple writers.

Post reply on HN