graphql-hive / graphql-hive/router

Dependency-Driven Query Execution Model

Open
#69 3 comments 2 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
103
Forks
23
Avg merge
1d 4h
Merged PRs (30d)
103

Description

## Problem

Our current query execution model, based on the `QueryPlan` structure (composed of `Sequence` and `Parallel` nodes), processes fetches in batches. For example, a `Parallel([f1, f2, f3])` block requires all `f1`, `f2`, and `f3` to complete before the executor moves to the next step in a sequence. Similarly, a `Sequence` implies strict ordering of these (potentially parallel) batches.

While the recent refactoring of the query planner to use Kahn's algorithm improves how these `Parallel` and `Sequence` blocks are *identified*, the execution itself remains batch-oriented. This can lead to inefficiencies: a downstream fetch that depends only on `f1` (from the example above) must wait for `f2` and `f3` to complete, even if `f1` finishes much earlier. This can introduce unnecessary latency.

## Proposed Solution

I propose shifting to a more granular execution model that operates directly on a graph of fetch operations and their dependencies, similar in nature to the `FetchGraph` but representing executable units (`FetchNode` + `Flatten`).

The core ideas are:

1. **Execution Graph:** The executor would work with a directed acyclic graph (DAG) where nodes are individual fetch operations (e.g., a `FetchNode` possibly combined with its `Flatten` operation) and edges represent dependencies.
2. **Node States:** Each node in this execution graph would have a state, such as `Pending`, `ReadyToRun`, `Running`, `Completed`, `Failed` - or less...
3. **In-Degree Tracking for Readiness:** Each node would maintain an "in-degree" counter, representing the number of its direct dependencies (parent nodes) that have not yet completed.
4. **Dynamic Dispatch:**
* Initially, all nodes with an in-degree of 0 (no unresolved dependencies, typically the first fetches in the query) are marked `ReadyToRun` and dispatched for execution (e.g., making HTTP requests). Their state changes to `Running`.
* When a node (fetch operation) completes successfully:
* Its state is marked `Completed`.
* For each of its children (nodes that depend on it), their in-degree is decremented.
* If a child's in-degree becomes 0, it means all its dependencies are met. It is marked `ReadyToRun` and dispatched for execution.
* This process continues until all nodes are `Completed` or some have `Failed`.
5. **Max Concurrency:** A configurable limit on the maximum number of concurrent `Running` fetches can still be maintained to manage resources.

## Benefits

* **Improved Latency:** Fetches can start as soon as their *specific* dependencies are met, rather than waiting for an entire artificial "batch" to complete. This maximizes parallelism and can significantly reduce overall query execution time, especially for queries with varying fetch durations.
* **Closer to True Data Flow:** This model more closely mirrors the actual data dependencies and flow.

## Relationship to Current `QueryPlan`

The current `QueryPlan` (with `Sequence` and `Parallel` nodes) generated by Kahn's algorithm already identifies sets of operations that *can* run in parallel (a `Parallel` block) and the dependencies between these sets (a `Sequence`).
This proposal suggests that the *executor* should use https://dagrs.com/ and schedule fetches as tasks.

## Considerations & Challenges

* **Plan Visualization:** Representing an executing plan might become more complex than the current hierarchical `Sequence/Parallel` view. We'd be looking at a graph of many individual nodes.
* **Complexity of Executor:** The executor logic will need to manage node states, in-degrees, and a queue/pool of ready-to-run tasks.
* **Error Handling:** How failures in one part of the graph affect dependent fetches needs careful consideration (e.g., cancellation, marking dependent tasks as unfulfillable).

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by reading the current QueryPlan, executor, FetchGraph, and FetchNode + Flatten concepts described in the issue, then review how dagrs could support task scheduling. Define node states, dependency tracking, concurrency limits, and failure behavior before implementation. Done means dependent fetches dispatch as soon as their specific prerequisites complete without breaking existing execution behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
graphql, rust
Domain
backend-api-design, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.