3 ms·
I 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
by wat10000 1y ago
I 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.