3 ms·
An interesting article, but I disagree with the first sentence. > The basic promise of a query optimizer is that it picks the “optimal” query plan. This is ki
by remus 1y ago
An interesting article, but I disagree with the first sentence.
> The basic promise of a query optimizer is that it picks the “optimal” query plan.
This is kind of true, but the optimiser has to do all this with very tight constraints on available time and resources. A planner that returned a perfect plan every time would be useless if it took 500ms and 500mb, so I'd say a better phrasing would be
> The basic promise of a query optimizer is that it picks a good plan most of the time and does it quickly and efficiently.
- wat10000 1y agoI imagine that finding the optimal query plan would itself be at least NP-complete in the worst case, so you’ll definitely want to settle for “good” rather than optimal.
- Sesse__ 1y agoUnder fairly reasonable circumstances, finding the optimal join order for N tables in an arbitrary query graph is indeed shown to be NP-hard. However, many common queries are not so difficult, e.g. if you just join A to B, B to C, C to D etc. (a chain join) and allow joining only along join conditions, it's O(n³). But e.g. a star join (A to B, A to C, A to D, etc.) can become much worse IIRC.
- marcosdumay 1y ago> The basic promise of a query optimizer is that it picks a good plan most of the time and does it quickly and efficiently. Hum, no. The basic promise of a query optimizer is that it picks a good plan all of the time. Otherwise it's worse than useless and you would be better with a DB where you can pin the plan for every query. But yes, the goal is on "good", not "optimal".
- RaftPeople 1y ago> The basic promise of a query optimizer is that it picks a good plan all of the time. The poster you responded to is correct, it's a combinatorial problem that can't be expected to pick a good plan all of the time within the normal data and time constraints.