EventReduce: An algorithm to optimize database queries that run multiple times • Hacker News Board

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

#21

Post by fastball » Thu, Apr 16, 2020, 12:29 PM UTC

joefreeman wrote: post #10

This sounds like (a simpler version of?) Lambda Architecture [1, 2] [1] https://en.wikipedia.org/wiki/Lambda_architecture [2] https://www.manning.com/books/big-data

To me this sounds a lot like how CRDT works (just simpler and not rigorously proven).

e.g. making deterministic changes to some data before you've heard back from any sort of central single-source-of-truth.

Difference with CRDT is that the goal is to never actually hear back from a central authority and still have consistency between clients.

Maybe this is a sort of hybrid CRDT/OT.

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

#22

Post by superpermutat0r » Thu, Apr 16, 2020, 12:32 PM UTC

eventreduce wrote: post #12

superpermutat0r wrote: post #9

Earlier quoted context omitted.

BDDs you are using, are they zero-supressed decision diagrams or it was not necessary to do these kinds of optimizations?

Yes the BDD is minimized with the two rules (reduction and elimination). Also the sorting of the boolean functions is optimized via plain brute forcing. The was no good JavaScript implementation for BDDs so I had to create my own one https://github.com/pubkey/binary-decision-diagram

Cool, I've checked your code and it's not zero suppressed BDDs, although it might not be a performance gain if you used ZDDs. (zero supressed BDDs are very good at representing sets of permutations/combinations etc. but as far as I understand you have all the possible permutations encoded in the BDD, not a subset of all possible permutations).

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

#23

Post by danbruc » Thu, Apr 16, 2020, 12:33 PM UTC

Did I understand this correctly? You have a single set of items which you query by evaluating a predicate on each of them and then sort the matching ones. After the initial query you update the query result by looking at all the data update events, i.e. you remove delete items from the result, you insert matching new items in the correct position according to the sort order and you insert, remove, or move updated items as they start or stop matching the predicate and change their position according to the sort order.

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

#24

Post by eventreduce » Thu, Apr 16, 2020, 12:36 PM UTC

danbruc wrote: post #23

Did I understand this correctly? You have a single set of items which you query by evaluating a predicate on each of them and then sort the matching ones. After the initial query you update the query result by looking at all the data update events, i.e. you remove delete items from the result, you insert matching new items in the correct position according to the sort order and you insert, remove, or move updated ite…

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.

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

#25

Post by eventreduce » Thu, Apr 16, 2020, 12:37 PM UTC

alecco wrote: post #18

The use case seems better fit for a streaming database.

There is a big difference between a database with an event stream and a 'realtime query' that can be created with event reduce.

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

#26

Post by Laakeri » Thu, Apr 16, 2020, 1:01 PM UTC

eventreduce wrote: post #5

throwaway_pdp09 wrote: post #3

Forgive me if I missed stuff, please point me in the right direction if you've covered it, but some questions if I may (after I've said well done!). I've considered this problem before and it seems very difficult . So: 1. Do you have a paper on this with a rigorous justification of the algorithm? 2. This surely has to rely on the isolation level being pretty high, or EventReduce might be reading while n other process…

1. No I do not have a paper. I thought a lot about publishing a paper first but then decided against it, because I think that good code and tests and demos are more valuable. 2. EventReduce is mostly useful for realtime applications. I myself use it in a NoSQL database (RxDB). There you stream data and events and a single document write is the most atomic 'transaction' you can do. If you need transactional serial wri…

The value of a paper is the peer review by experts.

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

#27

Post by scott_s » Thu, Apr 16, 2020, 1:19 PM UTC

eventreduce wrote: post #25

alecco wrote: post #18

The use case seems better fit for a streaming database.

There is a big difference between a database with an event stream and a 'realtime query' that can be created with event reduce.

What is that difference?

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

#28

Post by scott_s » Thu, Apr 16, 2020, 1:29 PM UTC

fahrradflucht wrote: post #16

pgt wrote: post #2

Materialize exists to efficiently solve the view maintenance problem: https://materialize.io/

There is also noria [0] which is basically a SQL database with integrated materialized views with memcached like perf. - But I think it is more in a research state. [0]: https://github.com/mit-pdos/noria

Any database which offers what are called "continuous queries" also solves this problem. I'm glad the ACM Digital Library is open right now, because I can just point to: https://dl.acm.org/action/doSearch?AllField=continuous+queri...

The work in general purpose streaming grew out of the continuous query work in the early 2000s. Marrying truly general purpose streaming with transactional databases is not a solved problem (as opposed to transactional databases providing streams), but the notion of continuously running database queries has been around for a long time.

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

#29

Post by j-pb » Thu, Apr 16, 2020, 1:41 PM UTC

pgt wrote: post #2

Materialize exists to efficiently solve the view maintenance problem: https://materialize.io/

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?

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

#30

Post by LunaSea » Thu, Apr 16, 2020, 1:58 PM UTC

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?