--- title: designing a query system | daily.dev description: A detailed design document for Krabby's query system, a pull-based, concurrent, and asynchronous query engine intended to replace an earlier push-based... canonical: https://daily.dev/posts/designing-a-query-system-kukttmyr0 twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: designing a query system | daily.dev og:description: A detailed design document for Krabby's query system, a pull-based, concurrent, and asynchronous query engine intended to replace an earlier push-based... og:url: https://daily.dev/posts/designing-a-query-system-kukttmyr0 og:image: https://api.daily.dev/og/posts/KuKTtmYr0.png og:image:alt: designing a query system og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # designing a query system **[Lobsters](https://daily.dev/sources/lobsters)** · 33 min read · 0 upvotes · 0 comments ## Summary A detailed design document for Krabby's query system, a pull-based, concurrent, and asynchronous query engine intended to replace an earlier push-based architecture for a Rust compiler. The author explains why the push-based approach was abandoned (cache inefficiency, poor demand-driven prioritization, LSP incompatibility) and outlines an ambitious wish list: concurrency across threads, async task execution without Rust's async machinery, batching for SIMD and cache efficiency, pre-emptive task scheduling, deep Cargo integration, context-free incremental compilation with configurable eviction policies, streaming queries, and accelerated compiler test runs. The design covers task lifecycle, poll functions analogous to Future::poll, worker thread batching strategies, in-memory and on-disk caches with task recordings, an extended red-green incremental algorithm, and a three-tier cycle detection system (eager per-thread, lazy cross-thread deadlock detector, and slow graph walker). The author plans to present the system at EuroRust 2026. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### Why did rustc's query system not fully solve the problem of unnecessary crate rebuilds in Cargo? Cargo has only a simplistic understanding of rustc: any change to a source file's modification time or dependencies triggers a full rebuild, and rustc's own query system only memoizes later compilation stages, not parsing, name resolution, or macro expansion. Additionally, rustc requires a crate's dependencies to be fully compiled before it starts, which serializes work across dependency chains even when not functionally necessary. _Anyone frustrated by slow, single-CPU-bound Rust rebuilds can track compiler and build-tool design discussions like this via daily.dev._ ### How does Krabby's incremental compilation cache differ from rustc's red-green algorithm? Krabby extends the red-green algorithm used by rustc and salsa, which only retains data from the immediately previous compilation, by also checking an on-disk cache of task recordings from older compilations when a task needs recomputing. This lets Krabby reuse cached results even after cache eviction or when Cargo feature flags differ, avoiding full rebuilds that rustc and salsa would otherwise require. _Developers comparing incremental build caching strategies can follow compiler design deep dives like this on daily.dev._ ### What is a streaming query in a compiler query system and why is it useful? A streaming query returns collection results, such as all references found or all glob-imported items, incrementally as they are discovered rather than waiting until the entire collection is complete. Tasks depending on a streaming query can observe partial results and resume as new data arrives, lowering latency, reducing wasted work, and improving parallelism for operations like an IDE's find-all-references or Cargo's --workspace command. _Engineers designing responsive IDE or build tooling can dig into query-system patterns like this on daily.dev._ ## Community take How the wider developer community reacted, aggregated from 2 discussions and 8 comments across lobsters, hackernews (as of 2026-09-13). **TL;DR:** Commenters are broadly impressed by the depth and ambition of the design, with the main thread of discussion centering on the author's decision to avoid Rust's async machinery — a choice that sparked genuine technical debate about async codegen quality, Waker/Context API limitations, and whether the tradeoffs are well-justified. **Sentiment:** 65% positive · 25% mixed · 10% skeptical **The case for** - The design document is praised for its consistently high quality and thoughtful architectural reasoning. - The author's concern about Rust async codegen is validated by references to open Rust project goals specifically targeting async future memory and state-machine optimisation. - The critique of Waker/Context APIs as poorly suited for non-thread-spawning runtimes and contradicting zero-cost abstraction ideals resonates with commenters. - The author's self-awareness about historic design choices limiting codebases is appreciated as both honest and rare. **The pushback** - The rationale for avoiding Rust's async is initially described as vague and unsupported by concrete benchmarks or measurements. - Concerns about async performance may conflate the async model itself with specific runtime implementations like tokio. - The claim that a manual implementation would have less overhead is not substantiated with evidence in the post. **By community** - lobsters (positive): Engaged, technically deep discussion that largely validates the author's async concerns after clarification, while pushing back on the lack of benchmarks and initially calling the performance rationale a 'weapons-grade vaguepost'. - hackernews (mixed): No substantive comments to assess sentiment from. **Hottest debate:** Whether avoiding Rust's async machinery is justified by real performance problems or is an unsupported preference, given the lack of concrete benchmarks. **Open questions** - What statistically significant benchmarks demonstrate that async codegen overhead meaningfully impacts a compiler's throughput? - Is there a path to passing shared mutable context through poll() chains without requiring algebraic effects or breaking Rust's type system? - How does the proposed manual async implementation compare in practice to a thread-per-core runtime like glommio? **Highlights** > It really does need a blog post :) Here's a summary: Codegen for `async` functions is suboptimal. There are two open Rust project goals about it: [Async Future Memory Optimisation](https://rust-lang.github.io/rust-project-goals/2026/async-future-memory-optimisation.html) and [Async statemachine optimisation](https://rust-lang.github.io/rust-project-goals/2026/async-statemachine-optimisation.html). Both the descriptions include examples worth checking out. From personal experiments, I was surprised by the codegen. I'm glad it's being worked on. I worry about the standard library API around `async` functions, specifically `Context` and `Waker` (used by `Future`). These APIs look like they were designed for an async runtime that spawns threads everywhere (e.g. the now-defunct `async-std`), which IMO is the exact thing async should _avoid_. The idiomatic way to implement `Waker` is using `Arc`, thereby requiring heap allocations and atomics, even if your code is single-threaded. (Yes, there is a `LocalWaker` now in the works, but it's still nightly, and you still have to support `Waker` for backwards compatibility.) IMO these limitations contradict the idea of async Rust as a "zero-cost abstraction". My dream feature for futures is, sharing an `&mut` reference throughout an async codebase, by passing it through `poll()`. If you have futures A and B, where A is `.await`-ing B, A's `poll()` could receive an `&mut Foo`, use it however, and pass it down to B's `poll()` -- both functions could have direct mutable access of this thing! Awesome! The first use case is the async executor: you could pass around a handle to the executor's thread-local state using this mechanism, instead of needing real `thread_local!` vars. But more generally, an application could use this to pass around important context (in Krabby's case, query system data) through `&mut`. Why is this not possible with async Rust today? First of all, at a high level, this feature looks a lot like algebraic effects, and Rust is not built for that. Ignoring that, `Context` is a very limited interface. There is a nightly `context_ext` feature to allow passing a user-controlled `&mut` through it, but 1) this requires `dyn Any` i.e. `'static` (mostly fine); 2) only a _single_ `&mut` can be passed around this way, limiting structural composition for its users (e.g. how do you coordinate between two different, independent libraries that want to store data there?). For a while (well before my work on Krabby), I thought "well, I can work around most of these issues by building a custom version of `Future` / `async` using the nightly `Coroutine` / `gen` feature", but that doesn't work! `Coroutine` is, subtly, _not_ a perfect generalization of `Future`. `Future` lets you pass borrowed data through (via the aforementioned `Context`), but `Coroutine`'s trait signature prevents that. (This is sort of understandable, as I think the feature I am describing would expose coroutine witness types to users? That probably has unintended consequences that I don't have the expertise to imagine.) Aside: I am a huge fan of `io_uring` and I would love to make yet another cool `io_uring` based async runtime, but these issues frustrate me too much to try (though I now prioritize Krabby over starting any new side projects). With regards to Krabby: in the OP, I gave an example of a query implementation for name resolution. The structure was "query for pending references; every time a result is available, process the result and possibly generate more queries; save the pending queries for the next iteration." I thought about some other important queries, and AFAICT they all share a similar structure. If I phrased this like an `async` function, it would be a big loop within which I generate a bunch of queries and do a single `.await` at the end of each iteration. I don't `.await` on every query, because I want to collect many queries at a time (this reduces the amount of jumping back and forth bet > — [bal-e on lobsters · 2 points, 2 comments](https://lobste.rs/s/awdorz/designing_query_system#c_ogkyrv) > > I am perpetually saddened by the fact that codebases are fundamentally limited by their historic design choices. The way a program is architected specializes it, and sets it down a path it cannot be shaken from easily. I keep seeing features and optimizations blocked by years-old decisions that never considered their possibility. Big salute to anyone who's capable of worrying about this sort of thing, and *also* actually getting anything real done. I sure as heck can't. > — [icefox on lobsters · 12 points, 1 comments](https://lobste.rs/s/awdorz/designing_query_system#c_ra7wnr) > I messaged the author about this: > 1) I have a personal vendetta against `Waker` > 2) there's a few rust project goals open relating to optimizing async tasks, I would suggest checking them out, and their examples of horrific codegen So still I think the goal is something _like_ `Future`, but without the associated baggage from its current implementation. I have also looked at some of the codegen examples (having a hard time finding them again whoops), you'd be surprised as to how poorly they optimize. > — [polywolf on lobsters · 2 points, 1 comments](https://lobste.rs/s/awdorz/designing_query_system#c_ftjn2o) > > Codegen for async functions is suboptimal. There are two open Rust project goals about it: Async Future Memory Optimisation and Async statemachine optimisation. Both the descriptions include examples worth checking out. From personal experiments, I was surprised by the codegen. I'm glad it's being worked on. I've seen these, and unless someone shows me the impact of those in statistically significant and well designed benchmarks, I'm not going to treat this as more than "sure, this is one area where codegen could be better". Personally I find it difficult to care about binary size. It's often inversely proportional to throughput, too. > I worry about the standard library API around async functions, specifically Context and Waker (used by Future). These APIs look like they were designed for an async runtime that spawns threads everywhere (e.g. the now-defunct async-std), which IMO is the exact thing async should avoid. The idiomatic way to implement Waker is using Arc, thereby requiring heap allocations and atomics, even if your code is single-threaded. (Yes, there is a LocalWaker now in the works, but it's still nightly, and you still have to support Waker for backwards compatibility.) IMO these limitations contradict the idea of async Rust as a "zero-cost abstraction". I fully agree with this. Thank you for making me aware of `LocalWaker` (and the detailed response). > — [prez on lobsters · 1 points](https://lobste.rs/s/awdorz/designing_query_system#c_fkkxnl) **Source threads** - [lobsters](https://lobste.rs/s/awdorz/designing_query_system) · 28 points · 8 comments - [hackernews](https://news.ycombinator.com/item?id=49178085) · 2 points · 0 comments ## Similar posts on daily.dev - [krabby: making a fast Rust compiler](https://daily.dev/posts/krabby-making-a-fast-rust-compiler-rtse29y6c) · Lobsters · 3 upvotes · 0 comments - [Upcoming Rust language features for kernel development](https://daily.dev/posts/upcoming-rust-language-features-for-kernel-development-qkl4smo7p) · Hacker News · 12 upvotes · 0 comments - [The Evolution of Async Rust: From Tokio to High-Level Applications](https://daily.dev/posts/the-evolution-of-async-rust-from-tokio-to-high-level-applications-uwvht0pbc) · JetBrains · 48 upvotes · 0 comments - [Against Query Based Compilers](https://daily.dev/posts/against-query-based-compilers-wfnhfc9q8) · matklad · 4 upvotes · 0 comments --- Tags: [#rust](https://daily.dev/tags/rust), [#compiler](https://daily.dev/tags/compiler) [View this post on daily.dev](https://daily.dev/posts/designing-a-query-system-kukttmyr0) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"designing a query system","url":"https://daily.dev/posts/designing-a-query-system-kukttmyr0","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/designing-a-query-system-kukttmyr0"},"datePublished":"2026-08-05T16:30:22.007Z","dateModified":"2026-09-13T19:31:03.162Z","description":"A detailed design document for Krabby's query system, a pull-based, concurrent, and asynchronous query engine intended to replace an earlier push-based...","image":"https://media.daily.dev/image/upload/s--2-1xRawN--/f_auto/v1722860399/public/Placeholder%2011","thumbnailUrl":"https://media.daily.dev/image/upload/s--2-1xRawN--/f_auto/v1722860399/public/Placeholder%2011","isAccessibleForFree":true,"articleSection":"Lobsters","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Lobsters","logo":"https://media.daily.dev/image/upload/s--tl8v_Fku--/f_auto,t_logo/v1698841318/logos/lobste.jpg","url":"https://daily.dev/sources/lobsters"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/designing-a-query-system-kukttmyr0","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":0},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"rust,compiler","timeRequired":"PT33M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Lobsters","item":"https://daily.dev/sources/lobsters"},{"@type":"ListItem","position":3,"name":"designing a query system"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/designing-a-query-system-kukttmyr0#faq","mainEntity":[{"@type":"Question","name":"Why did rustc's query system not fully solve the problem of unnecessary crate rebuilds in Cargo?","acceptedAnswer":{"@type":"Answer","text":"Cargo has only a simplistic understanding of rustc: any change to a source file's modification time or dependencies triggers a full rebuild, and rustc's own query system only memoizes later compilation stages, not parsing, name resolution, or macro expansion. Additionally, rustc requires a crate's dependencies to be fully compiled before it starts, which serializes work across dependency chains even when not functionally necessary. Anyone frustrated by slow, single-CPU-bound Rust rebuilds can track compiler and build-tool design discussions like this via daily.dev."}},{"@type":"Question","name":"How does Krabby's incremental compilation cache differ from rustc's red-green algorithm?","acceptedAnswer":{"@type":"Answer","text":"Krabby extends the red-green algorithm used by rustc and salsa, which only retains data from the immediately previous compilation, by also checking an on-disk cache of task recordings from older compilations when a task needs recomputing. This lets Krabby reuse cached results even after cache eviction or when Cargo feature flags differ, avoiding full rebuilds that rustc and salsa would otherwise require. Developers comparing incremental build caching strategies can follow compiler design deep dives like this on daily.dev."}},{"@type":"Question","name":"What is a streaming query in a compiler query system and why is it useful?","acceptedAnswer":{"@type":"Answer","text":"A streaming query returns collection results, such as all references found or all glob-imported items, incrementally as they are discovered rather than waiting until the entire collection is complete. Tasks depending on a streaming query can observe partial results and resume as new data arrives, lowering latency, reducing wasted work, and improving parallelism for operations like an IDE's find-all-references or Cargo's --workspace command. Engineers designing responsive IDE or build tooling can dig into query-system patterns like this on daily.dev."}}]} ```