SQLite changes how star joins survive query planning

A query planner can discard the beginning of a good plan before it has enough information to recognize the plan's value. That is the problem behind the star-join work in SQLite 3.49.0, released on 6 February. Several individually cheap scans of small tables can displace a more expensive fact-table operation during planning. Their eventual combination can be far worse than the path the planner discarded.

The release changes the heuristic used to prevent that outcome. It also addresses three reported performance regressions associated with the earlier approach. The interesting part is the location of the adjustment. SQLite now raises selected dimension-table scan costs, while leaving fact-table access costs alone. That is a narrower intervention in the planner's estimates.

I value having SQLite execute relational queries inside the application process. That convenience depends on work well beyond parsing SQL or reading a file. A bounded planner must find useful join orders without allowing statement preparation to become an exhaustive search through every possibility.

A bounded search can lose a useful beginning

The planner implementation at the release tag describes the constraint directly. Query planning is NP-hard, so the solver limits the paths retained at each stage. For a query with one table it keeps one path. For two tables it keeps five. Larger joins retain twelve paths, or eighteen when the star-query heuristic applies.

Each retained path is a partial choice of the operations that will implement the join. Extending a path adds another loop. Paths compete on estimated cost as the solver proceeds, and only a limited number continue to the next stage. A discarded beginning does not remain available for reconsideration after all the later choices become visible.

This makes a cheap beginning different from a cheap complete plan. Scanning one small dimension table may look attractive in isolation. Scanning several such tables before constraining the large fact table can create a costly intermediate combination. The fact-table path needs to survive long enough for its useful continuations to compete.

A star schema is a particularly clear case because a central fact table connects to several dimensions. The source comments define the heuristic's candidate as a large central table with inner joins to at least four smaller tables. A query does not qualify merely because an application developer calls it a reporting query. SQLite applies structural criteria to the joins it is planning.

Why the earlier correction caused problems

The historical comments in computeMxChoice() date the original optimization to 9 May 2024. That version reduced estimates associated with fact-table access so those paths could compete against dimension scans. It reduced the fact table's cost and output-size estimate. Preserving the promising path solved one planning problem, but changed the comparisons used elsewhere in a complex join.

The same comments cite regression reports from December and January. They explain that the response tightens star-query detection and changes the direction of the cost adjustment. Outer joins can impose ordering restrictions that make the simple star interpretation inappropriate. The revised detection excludes cases where an outer or cross join separates candidate facts and dimensions.

This is a useful example of the difference between an estimated cost and a property of the database. The engine does not make reading a dimension table physically slower. It changes a planning number to compensate for a limitation in how much of the search it retains. That number influences which alternatives remain eligible for extension.

The earlier approach affected all access methods for a fact table. A targeted change to dimension scans leaves other estimates available for their usual comparisons. The scope of an adjustment matters because a cost model participates in many decisions beyond the single query family that motivated a patch.

What the new heuristic adjusts

The release-tag implementation finds a candidate fact table and dimensions whose access depends on it. It excludes self-joins from dimension classification. After identifying at least four qualifying dimensions, it computes a threshold from the fact table's candidate running costs and adds a small increment.

Qualifying dimension scans whose estimated running costs fall below that threshold are raised to it. Constrained searches retain their estimates. The source distinguishes scan operations from search operations here, so saying that SQLite makes every dimension-table operation expensive would misdescribe the change.

This protects paths that put the fact table in an outer loop. It also allows the solver to keep eighteen alternatives for the detected star query. The wider retained set and the cost adjustment address the same practical difficulty, but they are separate mechanisms. Keeping more paths alone would still leave an increasing number of attractive dimension-scan combinations competing for finite space.

The star-schema regression test makes the scale of that problem concrete. It defines a central table with sixty-three dimension references and corresponding dimension tables. This is a deliberately large construction for exercising the planner. It is evidence of the case the algorithm must handle, not a claim that a typical application needs a join of that size.

No schema declaration turns this heuristic on. Fact and dimension are roles inferred during planning. Applications continue to express the desired join through SQL, and the engine chooses an execution strategy. This preserves the benefit of keeping operational choices out of application query text when the planner can make them itself.

The surrounding release changes are consistent with that goal

The February notes also extend query-time indexes to WITHOUT ROWID tables. Another adjustment prefers fewer bytes per row when estimated query costs tie. Neither item establishes a universal speedup. They expand the cases the planner can handle and refine a choice that previously had equal estimated costs.

These improvements matter independently of whether a database resembles a warehouse. The release can help a workload through a query-time index while its star-query heuristic never applies. Conversely, a complicated reporting join can benefit from the revised search without changing the persistent indexes in the schema. The release notes describe several separate planner changes, and an explanation should preserve that separation.

I prefer the revised star heuristic because its intervention is easier to justify. It compensates for premature pruning of fact-table paths by changing the competing scans that cause the problem. The tagged comments also preserve the reports and historical reasoning, which makes the implementation more intelligible than a collection of unexplained cost constants.

For a qualifying join, 3.49.0 therefore changes which partial plans survive long enough to become complete candidates. A small dimension scan remains a real scan with the same physical work. Its adjusted estimate keeps that locally cheap choice from eliminating the fact-table path before the planner can evaluate the useful join order.