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

/*+ leading(sales products customers) 
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

About Bobby

I live in Chandler, Arizona with my wife and three daughters. I work for US Foods, the second largest food distribution company in the United States. I've been working as an Oracle database administrator and PeopleSoft administrator since 1994. I'm very interested in Oracle performance tuning.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply