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

Re:EventReduce: An algorithm to optimize database queries th... by eventreduce on Thursday April 16, 2020 @07:54AM (#22888460)

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 writes and reads that depend on each other, you would not use EventReduce for that.

3. EventReduce is just the algorithm that merges oldResults+Event. It assumes that you feed in the events in the correct order. Mostly this is meant to be used with databases that provide a changeStream where you can be sure that the order is correct.

4. Sort order matters because EventReduce promises you to always return the same results as a fresh query over the database would have returned. When the sort order is not predictable, the returned rows from a query depend on how the data is stored in the database. This order cannot be predicted by EventReduce which means it will then return a wrong result set.

PS: BDDs are awesome :)

[ Parent | on HN ]

Re:EventReduce: An algorithm to optimize database queries th... by DarkWiiPlayer on Thursday April 16, 2020 @08:03AM (#22888523)

It would probably be a good idea to write a paper at some point; it's simply easier to read a document explaining the algorithm with some pseudocode than to dig through an actual codebase with all the messy language-details in between the parts that actually matter.

[ Parent | on HN ]

Re:EventReduce: An algorithm to optimize database queries th... by eventreduce on Thursday April 16, 2020 @11:42AM (#22890540)

I understand that reading the plain source code is more painful then reading a paper.

There are many different trade-offs between a paper and the current repository with source code. For me the biggest argument was that EventReduce is a performance optimization. So to be sure if it really works and is faster, you always need an implementation since you cannot predict the performance from a paper.

Because I did not have time for both, I only created the repository with the implementation. Maybe a paper will be published afterwards.

[ Parent | on HN ]

Re:EventReduce: An algorithm to optimize database queries th... by Laakeri on Thursday April 16, 2020 @09:01AM (#22888897)

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

[ Parent | on HN ]

Re:EventReduce: An algorithm to optimize database queries th... by throwaway_pdp09 on Thursday April 16, 2020 @08:08AM (#22888549)

So if I get you, it's for append-only data - probably no updates, definitely no no deletions? Still don't get how you don't need logical clocks to pick out the delta(s), but thanks for your prompt answer.

Edit: your example gives replaceExisting() so that's supporting an update of some kind.

[ Parent | on HN ]

Re:EventReduce: An algorithm to optimize database queries th... by eventreduce on Thursday April 16, 2020 @08:13AM (#22888573)

No it is explicitly not for append-only data. It works with inserts, updates and deletes. I think I have problems understanding what exactly you mean by the need for a logical clock. The algorithm is feeded with the old query results plus one event, and then returns the new query results. Since there is only one event at each point of time, it does not have to order or maintain them.

[ Parent | on HN ]

Re:EventReduce: An algorithm to optimize database queries th... by tyingq on Thursday April 16, 2020 @08:15AM (#22888584)

I had the same question as #2. Basically, it has to be the front-end to any event that reads/writes the data, in strict order of occurrence?

[ Parent | on HN ]

Re:EventReduce: An algorithm to optimize database queries th... by eventreduce on Thursday April 16, 2020 @08:20AM (#22888614)

Not exactly. To use EventReduce you must have a changestream out of all writes to your data int the correct order. You can do that by wrapping a frontend over your database.

But easier you do that by using a database that already provides a changestream like couchdb, Postgres, mongodb and so on.

[ Parent | on HN ]

Re:EventReduce: An algorithm to optimize database queries th... by superpermutat0r on Thursday April 16, 2020 @08:00AM (#22888501)

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

[ Parent | on HN ]

Re:EventReduce: An algorithm to optimize database queries th... by eventreduce on Thursday April 16, 2020 @08:03AM (#22888526)

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

[ Parent | on HN ]

Re:EventReduce: An algorithm to optimize database queries th... by superpermutat0r on Thursday April 16, 2020 @08:32AM (#22888691)

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).

[ Parent | on HN ]