TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

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

208 点作者 eventreduce大约 5 年前

19 条评论

danbruc大约 5 年前
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.
评论 #22888713 未加载
pgt大约 5 年前
Materialize exists to efficiently solve the view maintenance problem: <a href="https:&#x2F;&#x2F;materialize.io&#x2F;" rel="nofollow">https:&#x2F;&#x2F;materialize.io&#x2F;</a>
评论 #22888579 未加载
评论 #22889230 未加载
评论 #22927257 未加载
评论 #22888431 未加载
cryptonector大约 5 年前
How does this work for complex queries with sub-queries, LEFT OUTER JOINs, LATERAL JOINs, aggregation (DISTINCT&#x2F;GROUP BY), window functions, CTEs, RECURSIVE CTEs?<p>I&#x27;ve a radically different approach: can the queries in question as VIEWs, materialize them, use triggers to update materializations where you can write those triggers easily and the updates are quick, or schedule an update where they&#x27;re not.<p>If your RDBMS is very good about pushing WHERE constraints into VIEWs, and depending on how complex a VIEW query is, you might be able to make the update automatic by just querying the materialization&#x27;s underlying VIEW with appropriate WHERE constraints from the ROWs being INSERTed&#x2F;UPDATEd&#x2F;DELETEd. You can tell which VIEWs might suitable for this by checking that the TABLE whose row the trigger is running for is a &quot;top-level&quot; table source for the VIEW&#x27;s query: meaning a table source that&#x27;s either the left side of a top-level LEFT JOIN, or either side of an INNER JOIN. If you can run a query on the VIEW with a timeout then you can just do that in the trigger and mark the materialization as needing an update if the query is too slow. Lastly, a scheduled or NOTIFYed job can run to perform any slower updates to a materialization.
评论 #22897081 未加载
throwaway_pdp09大约 5 年前
Forgive me if I missed stuff, please point me in the right direction if you&#x27;ve covered it, but some questions if I may (after I&#x27;ve said well done!). I&#x27;ve considered this problem before and it seems very difficult . So:<p>1. Do you have a paper on this with a rigorous justification of the algorithm?<p>2. This surely has to rely on the isolation level being pretty high, or EventReduce might be reading while n other processes are updating. I don&#x27;t see that mentioned.<p>3. Surely you need logical clocks for this? If not, could you point me to a high-level description of the algorithm to show why they aren&#x27;t necessary.<p>4. Why does sort order matter? A timestamp yes (see 3. above), but I don&#x27;t understand why the order matters.<p>thanks (and trying to understand this might be the thing to get me into looking at BDDs again. I never understood their value).
评论 #22888460 未加载
telekid大约 5 年前
This seems conceptually similar to differential dataflow.<p><a href="https:&#x2F;&#x2F;github.com&#x2F;timelydataflow&#x2F;differential-dataflow&#x2F;blob&#x2F;master&#x2F;differentialdataflow.pdf" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;timelydataflow&#x2F;differential-dataflow&#x2F;blob...</a>
cntlzw大约 5 年前
&quot;EventReduce can be used with relational databases but not on relational queries that run over multiple tables&#x2F;collections.&quot;<p>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.
评论 #22890312 未加载
评论 #22890178 未加载
joefreeman大约 5 年前
This sounds like (a simpler version of?) Lambda Architecture [1, 2]<p>[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Lambda_architecture" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Lambda_architecture</a> [2] <a href="https:&#x2F;&#x2F;www.manning.com&#x2F;books&#x2F;big-data" rel="nofollow">https:&#x2F;&#x2F;www.manning.com&#x2F;books&#x2F;big-data</a>
评论 #22888676 未加载
评论 #22888535 未加载
Zaheer大约 5 年前
The goal of this is to reduce DB queries? Why not just queue up &#x2F; batch writes? What benefits does this provide over application side batching of the event.<p>EvenReduce assumes there are no other systems interacting with the DB state (by using the old state that the current system saw). If there are no other systems, simple batching would work fine.
评论 #22893739 未加载
pfarrell大约 5 年前
I’m going to look at the code, but how does are transactions in the database handled in eventreduce?<p>Specifically, I’m wondering about isolation levels which determine whether uncommitted changes are queryable before commit&#x2F;rollback.
truth_seeker大约 5 年前
IMO An open cursor of Change Stream with Aggregation pipeline (for given use-case) in MongoDB is more flexible solution to achieve this functionality.<p>In addition, it also tracks the history of changes and hence allows the cursor to go back if needed with &quot;resumeToken&quot;<p><a href="https:&#x2F;&#x2F;docs.mongodb.com&#x2F;manual&#x2F;changeStreams&#x2F;" rel="nofollow">https:&#x2F;&#x2F;docs.mongodb.com&#x2F;manual&#x2F;changeStreams&#x2F;</a>
评论 #22889918 未加载
marceloabsousa大约 5 年前
Very cool! This reminds me of some research I did a few years ago on program consolidation: <a href="https:&#x2F;&#x2F;dl.acm.org&#x2F;doi&#x2F;10.1145&#x2F;2594291.2594305" rel="nofollow">https:&#x2F;&#x2F;dl.acm.org&#x2F;doi&#x2F;10.1145&#x2F;2594291.2594305</a>
评论 #22890323 未加载
LunaSea大约 5 年前
Databases like PostgreSQL don&#x27;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?
评论 #22889877 未加载
评论 #22889979 未加载
评论 #22889682 未加载
评论 #22889535 未加载
AmericanBlarney大约 5 年前
Many applications solve this by using memory caching (e.g. Redid, memcached, etc.) of performance sensitive datasets. There are a lot of drawbacks to the approach, to the point that I would avoid it altogether.
评论 #22893779 未加载
pfarrell大约 5 年前
Have you compared with an in-memory data store like Redis? Due to the lack of support for joins, that seems like a more natural comparison than A relational database.
gitgud大约 5 年前
Interesting, seems similar to Firebase&#x27;s Firestore NoSQL database. In that you can create a complex query and receive real-time updates on each query.
regularfry大约 5 年前
So... a write-through cache?
alecco大约 5 年前
The use case seems better fit for a streaming database.
评论 #22888728 未加载
dahauns大约 5 年前
Sooo...Materialized&#x2F;Indexed Views?
评论 #22888467 未加载
评论 #22888474 未加载
Asraful56大约 5 年前
Nice