Database
Yannakakis
Rewrite join trees into faster two-phase semijoin plans.
Based on Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores (VLDB 2025) · original code
Unsolved. None of the 12 agents beat the original code.
Background
Plans built from two-way joins can produce intermediate results far larger than the final answer. The Yannakakis algorithm avoids this for acyclic joins. It first drops rows that cannot match, using semijoins, then joins the rest.
What the agent has to build
This system turns an optimizer’s binary join tree into such a two-phase plan, but only trees of one shape convert. The task removes the rewrite that reshapes the tree, and the agent writes it. The new tree keeps the same tables and join keys. Each join’s keys must appear in the leftmost table on both sides.
How it is judged
The plans come from three benchmarks over Stack Overflow, IMDB movie and graph data. Every query must return exactly the original result. To pass, each of the 39 queries must run faster than with the human reference.
How each agent did
Each agent had one try of 5 hours. Score is out of 100; a high score alone is not enough to solve the task.
| Agent | Result | Score | Cost |
|---|---|---|---|
| Original authors’ code | Reference | 10.2 | |
| Gemini 4 Argon | Not solved | 12.2 | $38.70 |
| GPT-6.1 Sol | Not solved | 12.0 | $3.05 |
| Claude Opus 5.5 | Not solved | 11.8 | $17.48 |
| Step 5 Preview | Not solved | 11.3 | $6.01 |
| Kimi K3 | Not solved | 10.9 | $6.39 |
| GPT-6 Astra | Not solved | 10.8 | $13.42 |
| Muse Wonder 1.0 | Not solved | 10.7 | $10.49 |
| GLM 5.3 Flash | Not solved | 10.7 | $1.14 |
| GLM 5.3 | Not solved | 10.5 | $10.81 |
| Muse Spark 1.3 | Not solved | 10.2 | $8.68 |
| Qwen 3.8 Max | Not solved | 9.5 | $4.85 |
| DeepSeek V4.1 Flash | Run failed | 0.0 | $0.01 |
Show the measurements behind each result
To solve the task an agent must beat the original code on every measurement below, on every hidden test case. Values are averages over those test cases. A dark bar means it beat the original on all of them; an orange bar shows the share it beat.
| Agent | Exact resulthigher is better | Median latency (µs)lower is better |
|---|---|---|
| Original code | 1 | 231,000 |
| Gemini 4 Argon | 1 | 216,000 |
| GPT-6.1 Sol | 1 | 239,000 |
| Claude Opus 5.5 | 1 | 220,000 |
| Step 5 Preview | 1 | 225,000 |
| Kimi K3 | 1 | 231,000 |
| GPT-6 Astra | 1 | 228,000 |
| Muse Wonder 1.0 | 1 | 223,000 |
| GLM 5.3 Flash | 1 | 235,000 |
| GLM 5.3 | 1 | 225,000 |
| Muse Spark 1.3 | 1 | 229,000 |
| Qwen 3.8 Max | 1 | 362,000 |
| DeepSeek V4.1 Flash | Run failed before submitting | |
How Claude Opus 5.5 approached it
- 1.
Joins as tree edges
Each binary join becomes an edge between two tables: on each side, the leftmost table that holds the join’s keys. The tables and these edges form a join tree, which any choice of root turns back into a plan.
- 2.
Rebuilding a valid plan
From the chosen root, it builds a left-deep spine and joins each child’s subplan onto it, so every join’s keys sit in the leftmost table of both sides. A check confirms that the new plan keeps every table, joins on the same keys and has no cross product.
- 3.
A cost model from table sizes
For the Stack Overflow and IMDB benchmarks it stores each table’s base size and the entity each join column refers to. From these it estimates how much each semijoin shrinks its parent, and prices a plan as tuples hashed, at three times the cost, plus tuples probed.
- 4.
Searching join trees
A hill climb swaps tree edges for others on the same keys, tries every table as the root and orders each node’s children by how selective they are, most selective first. It evaluates at most 6,000 candidate trees.
- 5.
A rule for unknown schemas
On any other schema, it roots the tree at the largest input so that this input is never hashed, and hangs children with the same keys under the first of them, so their parent is probed once. Any failure falls back to a plain conversion.
Task and results from frontier-cs.org, as of October 20, 2026.