Challenges in join optimization • Hacker News Board

Re: Challenges in join optimization

#21

Post by akoboldfrying » Thu, Jan 22, 2026, 10:49 AM UTC

akoboldfrying wrote: post #7

j-pb wrote: post #2

Whenever I read join optimisation articles in SQL based systems it feels... off. There is too much heuristic fiddling involved, and way too many niche algorithms that get cobbled together with an optimiser. As if we're missing the theory to actually solve the stuff, so we're instead hobbling along by covering as many corner cases as we can, completely missing some elegant and profound beauty.

Well, it's to be expected that heuristics are needed, since the join ordering subproblem is already NP-hard -- in fact, a special case of it, restricted to left-deep trees and with selectivity a function of only the two immediate child nodes in the join, is already NP-hard, since this is amounts to the problem of finding a lowest-cost path in an edge-weighted graph that visits each vertex exactly once, which is basic…

Self-nitpick (too late to edit my post above): I used the phrase "special case" wrongly here -- restricting the valid inputs to a problem creates a strictly-no-harder special case, but constraining the valid outputs (as I do here regarding left-deep trees) can sometimes actually make the problem harder -- e.g., integer linear programming is harder than plain "fractional" linear programming.

So it's possible that the full optimisation problem over all join tree shapes is "easy", even though an output-constrained version of it is NP-hard... But I think that's unlikely. Having an NP-hard constrained variant like this strongly suggests that the original problem is itself NP-hard, and I suspect this could be shown by some other reduction.

> with selectivity a function of only the two immediate child nodes in the join

This should be "with selectivity a function of the rightmost leaves of the two child subtrees", so that it still makes sense for general ("bushy") join trees. (I know, I'm talking to myself... But I needed to write this down to convince myself that the original unconstrained problem wasn't just the (very easy) minimum spanning tree problem in disguise.)

Re: Challenges in join optimization

#22

Post by 10000truths » Thu, Jan 22, 2026, 7:10 PM UTC

j-pb wrote: post #2

Whenever I read join optimisation articles in SQL based systems it feels... off. There is too much heuristic fiddling involved, and way too many niche algorithms that get cobbled together with an optimiser. As if we're missing the theory to actually solve the stuff, so we're instead hobbling along by covering as many corner cases as we can, completely missing some elegant and profound beauty.

I think it's natural to be uncomfortable with black-box optimizations with unclear boundary conditions, especially when there's no escape hatch or override. Postgres's query planner is notorious for this - some small change in a table's computed statistic shifts the cost estimate ever so slightly to favor some other "optimization" that actually ends up performing significantly worse. It happens rarely, but no one wants to "rarely" be paged at 3 AM on a Saturday.

Optimize for the p99/p99.9/worst case scenarios. Minimize unpredictability in performance where possible, even if it comes at a small cost of median/average performance. Your SREs will thank you.

Re: Challenges in join optimization

#23

Post by mihailstoian » Wed, Jan 28, 2026, 5:36 PM UTC

j-pb wrote: post #2

Whenever I read join optimisation articles in SQL based systems it feels... off. There is too much heuristic fiddling involved, and way too many niche algorithms that get cobbled together with an optimiser. As if we're missing the theory to actually solve the stuff, so we're instead hobbling along by covering as many corner cases as we can, completely missing some elegant and profound beauty.

If you're referring to estimating join sizes, i.e., the stuff you have to estimate before you actually build the query plan, we're _almost_ there (but not yet). Do check out the following papers that show that you can obtain provable bounds on your join sizes. Basically, given a SQL query, they'll tell you how many tuples (max and min, respectively) the query will return.

1. LpBound: join size upper bounds. It still doesn't have full SQL coverage, e.g., string predicates, window functions, subqueries etc., but as with all cool stuff, it takes time to build it.

2. xBound: join size lower bounds. We showed how to do it at least for multi-way joins on the same join key, e.g., many subexpressions of the JOB benchmark have this shape. Still open how to do the rest - I'd say even harder than for upper bounds! (NB: I'm an author.)

[1] LpBound: https://arxiv.org/abs/2502.05912

[2] xBound: https://arxiv.org/abs/2601.13117