Join order in query optimization using Catalan Numbers

238 Views Asked by At

I am looking for a solution of a problem below:

Show that, with n relations, there are (2(n − 1))!/(n − 1)! different join orders.

For this, I found a help from this slides (slide no - 19). That says

left deep     n!
right deep    n!
zig zag       n!2^(n-2)
bushy         n!C(n-1), Here C(n-1) is Catalan Number
            = (2n-2)!/(n-1)!

But I could not proof the above mathematically. Please help.

If we take only bushy, that is n!C(n-1). That is equal to:

n! * ((2(n-1))!/(n! * (n-1)!)) = (2n-2)!/(n-1)!

So without considering others, it only considered bushy?