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

11–20 of 87 posts

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

#11

Post by DarkWiiPlayer »

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…

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.

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

#12

Post by eventreduce »

superpermutat0r wrote: post #9
eventreduce wrote: post #5

Earlier quoted context omitted.

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…

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

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

#13

Post by eventreduce »

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

I do not think this has many in common. Lambda is used for stream processing much data. EventReduce is used for optimizing the latency of much (repeating) queries.

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

#14

Post by throwaway_pdp09 »

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…

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.

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

#15

Post by eventreduce »

throwaway_pdp09 wrote: post #14
eventreduce wrote: post #5

Earlier quoted context omitted.

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…

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.

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.

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

#16

Post by fahrradflucht »

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

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

#17

Post by tyingq »

eventreduce wrote: post #15
throwaway_pdp09 wrote: post #14

Earlier quoted context omitted.

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.

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.

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?

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

#19

Post by [deleted] »

eventreduce wrote: post #15
throwaway_pdp09 wrote: post #14

Earlier quoted context omitted.

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.

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.

[deleted]

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

#20

Post by eventreduce »

tyingq wrote: post #17
eventreduce wrote: post #15

Earlier quoted context omitted.

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.

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?

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.

Post reply on HN