Under 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 comm

Under 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.