# More than n! join orders?

Earlier today I was getting paranoid and thought I had found an error in my “Intro to SQL tuning” paper namely that there were more than n! join orders.

Here is what I said in the paper:

There are many possible join orders.  If the variable n represents the number of tables in your from clause there are n! possible join orders.  So, our example query has 3! = 6 join orders:

sales, products, customers
sales, customers, products
products, customers, sales
products, sales, customers
customers, products, sales
customers, sales, products

I knew that my main point was correct – there are a bunch of possible join orders.  But I wasn’t sure that n! was right.  Take the case of the join order sales, products, customers.  First you join sales and products with sales on the left and products on the right.  But when you join the result with customers does customers have to be on the right side of the resulting join?  Finally, late today I did a test script to show customers on either side of the join but with the same leading hint defining the join order.

```/*+ leading(sales products customers)
cardinality(customers 1)
cardinality(sales 1000000)
cardinality(products 1000000) */

-------------------------------------------------
| Id  | Operation           | Name      | Rows  |
-------------------------------------------------
|   0 | SELECT STATEMENT    |           |   250G|
|*  1 |  HASH JOIN          |           |   250G|
|*  2 |   TABLE ACCESS FULL | CUSTOMERS |     1 |
|*  3 |   HASH JOIN         |           |   500G|
|*  4 |    TABLE ACCESS FULL| SALES     |  1000K|
|*  5 |    TABLE ACCESS FULL| PRODUCTS  |  1000K|
-------------------------------------------------

cardinality(customers 1000000)
cardinality(sales 1)
cardinality(products 1) */

-------------------------------------------------
| Id  | Operation           | Name      | Rows  |
-------------------------------------------------
|   0 | SELECT STATEMENT    |           |   500K|
|*  1 |  HASH JOIN          |           |   500K|
|*  2 |   HASH JOIN         |           |     1 |
|*  3 |    TABLE ACCESS FULL| SALES     |     1 |
|*  4 |    TABLE ACCESS FULL| PRODUCTS  |     1 |
|*  5 |   TABLE ACCESS FULL | CUSTOMERS |  1000K|
-------------------------------------------------

```

I used cardinality hints to get customers to go before or after the join of sales and product.  So, I guess the right answer for now is that there are n! ways to list n tables in the from clause in the leading hint.  But there are more than n! execution plans that could result.

– Bobby