Fixing a Query Optimizer Bug in Turso

2026-07-08

I fixed a Turso Greedy Join Planner bug where long chain joins could start from a bad table and fail to produce a plan. The fix makes the starting-table score index-aware.

Fixing a Query Optimizer Bug in Turso

While contributing to Turso, I ran into a flaky CI failure.

At first, it looked like an unrelated failure from another change. After digging into it, I found that the Query Optimizer's Greedy Join Planner could pick a bad starting table for a long JOIN chain, eventually failing to produce a valid plan.

This post is about what was broken and how I fixed it with an index-aware heuristic.

PR: https://github.com/tursodatabase/turso/pull/6607

Background

The failing test was a fuzz test around the Join Optimizer.

The error looked like this:

called `Result::unwrap()` on an `Err` value: PlanningError("Greedy join ordering: no valid next table")

During planning, the optimizer failed to find a valid next table to join.

At this point, it only looked like a flaky test failure. The root cause turned out to be the way the Greedy Join Planner chose its starting table.

Join Order and Indexes

In a JOIN, the order in which tables are processed can make a large difference in cost.

Consider this query:

SELECT *
FROM users
JOIN orders ON orders.user_id = users.id
WHERE users.country = 'JP';

If orders.user_id has an index, starting from users is the natural choice.

First, users can be filtered by users.country = 'JP'. Then the remaining users.id values can be used to look up rows through the orders.user_id index. This avoids scanning a broad range of orders.

Starting from orders is less attractive. At that point, the planner does not yet have a concrete users.id, so the orders.user_id index is harder to use. The plan is more likely to scan orders broadly before the join can narrow it down.

So even for the same JOIN, the starting point determines whether an index can be used effectively.

Turso's Greedy Join Planner

Trying every possible JOIN order becomes expensive as the number of tables grows.

For larger joins, Turso uses a Greedy Join Planner. Instead of trying every join order, it repeatedly picks the next table that looks good at that step.

Because the planner is greedy, the starting table matters. If it starts from a bad table, the rest of the plan can be pulled in the wrong direction.

The bug was in the score used to choose that starting table.

What Was Broken

The failing fuzz test generated a long chain-shaped JOIN.

Conceptually, it looked like this:

t1 -> t2 -> t3 -> ... -> t61

The test joined 61 tables, with each table connected to the next one in the chain.

The existing implementation used a score called a hub score to choose the starting table. Roughly speaking, it counted how much a table was referenced by JOIN conditions, and treated highly referenced tables as better starting points.

That was too simple for a chain-shaped join. In this shape, the head and tail of the chain can look similar under the hub score. As a result, a table near the end of the chain, such as t61, could be selected as the starting table.

Then the planner would proceed backwards through the chain:

t61 -> t60 -> t59 -> ...

If the indexes are useful in the forward direction, walking the chain backwards prevents those index seeks from being used. Each backward step tends to add another full scan. In a long chain, those nested full scans compound quickly.

Eventually the estimated cost reaches inf, and the planner can no longer find a valid next table.

The failure flow was:

  1. A table near the end of the chain, such as t61, is selected as the starting table
  2. The planner proceeds backwards, like t61 -> t60 -> t59
  3. Index seeks are not usable in that direction, so full scans accumulate
  4. The nested full scan cost eventually reaches inf
  5. Planning fails because there is no valid next table

In short, the old score captured something like "centrality in the JOIN graph", but it did not capture whether starting from that table would make later index seeks possible.

The Fix

After discussing the issue with the reviewer, I changed the starting-table score to be index-aware.

Instead of only looking at how often a table is referenced by JOIN conditions, the new score also asks: if we start from this table, can later tables be reached through index seeks?

The new score looks at three things:

  1. The base row count of the table
  2. How much the table can be filtered by conditions that apply to that table alone
  3. How much starting from this table enables indexed seeks into later tables

Roughly, the score looks like this:

score = base_rows * local_selectivity * indexed_seek_multiplier

Lower scores are better starting tables.

base_rows is the original row count of the table. local_selectivity estimates how much the table can be reduced by filters that do not depend on other tables.

For example, a filter like users.country = 'JP' can be applied before any other table is joined, so it makes users a slightly better starting point.

The key part of the fix is indexed_seek_multiplier.

It is built from reward and penalty:

  • reward: how much starting from this table enables indexed seeks into other tables
  • penalty: how much this table would rather be reached through an indexed seek from another table

The multiplier is:

indexed_seek_multiplier = (1 + penalty) / (1 + reward)

If a table enables later indexed seeks, its reward increases and the multiplier gets smaller. If a table is better reached through an indexed seek from another table, its penalty increases and the multiplier gets larger.

Going back to the users / orders example, starting from users enables an index seek into orders.user_id.

In that case, users receives a reward because it unlocks a later indexed seek. orders receives a penalty as a starting table because it is better reached after users has been joined.

This makes long chain joins more likely to start from the direction where indexes can actually be used.

Complexity

I also changed how the score is computed.

The old hub score was roughly:

  1. Look at the JOIN conditions attached to each table
  2. Keep only the conditions related to index use
  3. For each condition, find the other tables it references
  4. Increment the hub_score for those tables

The core looked like this:

let mut hub_score = vec![0usize; num_tables];
for (t, tc) in constraints.iter().enumerate() {
    for c in &tc.constraints {
        if c.usable && c.table_col_pos.is_some() {
            for other in (0..num_tables).filter(|&x| x != t && c.lhs_mask.get(x)) {
                hub_score[other] += 1;
            }
        }
    }
}

For each JOIN condition, it scans 0..num_tables to find related tables. If T is the number of joined tables and C is the number of relevant JOIN conditions, this is roughly O(C * T).

The new logic looks at each table and the index access candidates attached to that table. While scanning those candidates, it updates the reward and penalty for the related tables.

The rough flow is:

  1. For each table that may be reached through an index, look at its index access candidates
  2. Collect the earlier tables that can make that index seek possible
  3. Add reward to those earlier tables
  4. Add penalty to the table that would be reached through the index
  5. Convert (1 + penalty) / (1 + reward) into the multiplier

Instead of scanning every table for every JOIN condition, the new logic walks the tables and their index access candidates once. That makes the scoring logic O(C + T), where T is the number of joined tables and C is the number of JOIN-condition references used by the index access candidates.

So the starting-table choice became index-aware while keeping the score computation linear.

Alternatives

A more fundamental approach would be to avoid committing to a single greedy path immediately. The planner could keep multiple candidate paths and continue expanding them.

SQLite does something closer to this. It builds candidates for scans and indexed lookups, then keeps multiple candidate paths at each JOIN depth.

https://github.com/sqlite/sqlite/blob/002d33d8c569ce25f5001ae627a4e73dd52bf98d/src/where.c#L5836

That approach is less likely to get stuck in a local optimum. If the first path becomes expensive after a few joins, another retained path can still win.

But that was too large in scope for this fix.

  • Planning work increases by a constant factor
  • The greedy join implementation would need to carry multiple join_order and current_plan states
  • Pruning and outer join ordering constraints would need to be handled per path

For this PR, I kept the existing Greedy Join Planner structure and improved the starting-table heuristic.

A SQLite-style bounded path search may be a better fit for a larger follow-up refactor.

Result

After the change, the fuzz test that reproduced the issue passed.

The other reported flaky failures were also confirmed to have the same root cause.

My main takeaway is that score design matters a lot in a greedy planner. Once the planner starts from the wrong table, the later choices tend to move in the wrong direction too.