designing a query system

The initial design relied on tasks pushing their results to later tasks, which seemed simple because early dependencies were known. As work progressed, the author noticed that the global table tracking pending references behaved like a query system. Because entries were added long before they were first used, the CPU cache was not used efficiently. Long chains of dependent tasks caused one core to stay busy after the rest finished.

Switching to a pull-based model means data is fetched only when a task actually needs it. This improves cache locality because recently fetched data is still hot when used. The scheduler can also prioritize work that matches a user’s immediate request, reducing unrelated computation. For interactive tools such as language servers, this leads to faster response times.

To make the query system practical, it must run many fine-grained tasks on multiple threads. The system needs to distribute work evenly, handle cases where two threads try to compute the same value, and detect dependency loops between threads. Tasks should also be able to pause execution and resume later without losing intermediate state. These features shape the overall architecture, influencing how data structures are shared and how synchronization is performed.

Building such a system requires careful design of lock-free or mutex-protected containers to avoid race conditions. Cycle detection adds overhead, especially when the graph is large and changes frequently. Supporting task suspension means storing stacks or continuations, which increases memory usage. All of this raises the engineering effort compared with the original push-based prototype.

The approach works best when tasks are reasonably sized; extremely tiny tasks can make scheduling overhead dominate. If the dependency graph contains many long chains that cannot be parallelized, some latency will remain. Finally, if the system cannot predict which pieces of data will be needed, it may still end up computing more than necessary.