Introducing Apollo’s Next Generation Query Planner
Taylor Ninesling
Today we are launching a new query planning algorithm which is built to scale to the most complex graphs, as part of GraphOS Router 3.0. The existing planning algorithm has brought us a long way, and two years ago we completed our project to reimplement it with the native performance of Rust. This brought a step change improvement in speed compared to our TypeScript implementation.
Our customers with the most complex graphs and operations still saw long planning times and high memory usage. Some users aggressively cache query plans to do the work before taking live traffic, while others have considered splitting the compute-heavy planning process out of the router entirely. These treat the symptoms of the core problem: the query planner itself is not as efficient as it should be.
For Router 3.0, we aimed to create a planner that was fast, even for those complex operations, with bounded and predictable memory usage. This required a ground-up reimplementation of the core search algorithm and the representation of candidate plans during that search, resulting in what we call the Incremental Query Planner.
Planning Operations, Incrementally
In our existing planner, the search algorithm is primarily a Breadth-First Search (BFS) over the possible options for each set of fields to plan. When the planner considers which paths to take, it considers all possible combinations of paths extending from the set of decisions made so far. This is fast when there are relatively few options, but the number of options explodes when uses of @key and @shareable create many options at multiple levels of the search. Within each plan candidate, the planner models the fetches it will make to the upstream subgraphs, optimizes the candidate plan, and compares it to the other candidates. The best candidate should parallelize as much work as possible, with the fewest number of fetches. There are three core observations about this process:
- Running a BFS over the search space means we must run the search to completion to get a plan
- Creating a fresh model of each plan candidate will result in many allocations for large search spaces
- Optimizing a candidate plan is wasted computation when that plan is not better than the best plan so far
The Incremental Planner takes a fundamentally different approach, starting with a Depth-First Search (DFS). This allows the planner to quickly find an initial draft of the plan, progressively optimizing the plan as it explores and finds better options in the search space. The planner mutates a single candidate plan in place, instead of creating a fresh copy for each combination of search options, and the cost heuristic used to evaluate those plans takes future graph reductions into account, allowing the planner to skip wasteful optimization steps when comparing candidates.
Bounding Memory During Search
Since we want to make memory usage more predictable, we implemented an algorithm called BULB search (Beam search Using Limited discrepancy Backtracking) from Furcy and Koenig’s Limited Discrepancy Beam Search. Variants of Beam Search limit the set of possible choices in the search by only keeping a subset of options at each decision point. This subset is called a beam, and the maximum number of options is called the beam width. Traditional Beam Search may prune globally optimal options, which is why we selected BULB. The backtracking introduced in BULB allows the planner to revisit locally suboptimal options that plain beam search would have pruned permanently, so a bad early decision doesn’t lock in a bad plan.
The second modification is the in-place mutation of the candidate plan, which we call the Fetch Graph. Modifications to the Fetch Graph are tracked as a stack of operations with corresponding undo actions. When the planner backtracks to a previously explored decision, we undo the actions performed since that particular decision, then continue exploring in the new direction. If the in-progress candidate has routed all fields in the operation, and the candidate is more optimal than the best plan found thus far, the planner takes a snapshot of the plan and records it as the best candidate so far. This is the only time the Incremental Planner creates a full copy of the candidate plan.
Optimizing the Candidate Plan
The Incremental Planner will start by finding a draft of the query plan by making locally optimal routing decisions for each field, as defined by its internal heuristics. This means it will prefer a local selection in the current subgraph over jumping to another subgraph, which is typically more efficient but can lead to suboptimal plans. After creating a draft, the search process will revisit previous decisions, trying locally suboptimal decisions which could result in a globally optimal plan.
Once the planner creates the initial draft, it starts considering a parameter we call fuel. Each time the planner encounters a field which could come from multiple sources, the decision of where to route that field deducts from fuel. If the globally optimal plan could not be found before the fuel was exhausted, the planner returns the best plan found thus far. This provides a deterministic way to limit the amount of computation in the planning process. Customers who need extremely fast plans can set fuel to zero, always returning the first draft of the plan. Other customers who want to find the optimal plan can use a much higher fuel budget, so the planner continues exploring well beyond the first draft.
The fuel parameter dovetails with the other primary configuration option for the search algorithm, beam width. The beam width determines how many options are tracked in memory for each decision point. A smaller beam width will use less memory for planning but may require more backtracking to find the best plan. Note that the backtracking will be limited by the fuel budget, so these two parameters work in tandem to limit the amount of compute and memory used to find the plan.
The Results
We validated the Incremental Planner head-to-head against the existing planner on a set of 200,000 operations on our most complex customer graphs, some of which took nearly a minute to plan. The Incremental Planner plans each of them in less than two seconds, with a staggering 300x speedup on the slowest operations and using 97% less memory!
It is important to note that the Incremental Planner can generate plans which are different from the existing planner. In simple cases, it often finds the same plan, or a plan with the same number of fetches with slightly different fetch content. There are large operations for which the Incremental Planner is not yet optimized, and it may find a less optimal plan. In these cases, try increasing your fuel to give the planner more time to optimize. On the other hand, the Incremental Planner can find more efficient plans for cases where the existing planner hits its maximum evaluated plans cap.
Try it out today
The Incremental Planner is available as an opt-in configuration in GraphOS Router 3.0. Simply enable it in your Router config:
supergraph:
query_planning:
incremental_planner:
enabled: trueThat’s it! The defaults should work well for nearly all graphs, but fuel and beam width are both configurable if you want to trade planning effort against speed and memory. To help you tune against real traffic, the planner also ships two new histogram metrics: apollo.router.query_planning.plan.fuel_consumed and apollo.router.query_planning.plan.fuel_remaining.
If remaining fuel stays above zero, the planner explored every option it wanted to within your budget. If it hits zero, a larger budget may find better plans. Check out our documentation for details.
Since the Incremental Planner is opt-in during this release, your feedback directly shapes when it becomes the default. If you run a complex graph, we’d especially like to hear how it performs for you. File issues on GitHub or share your results in the Apollo Community.
