Nested Loop Issue - Oracle

Nested Loop When presented with a join, the Oracle optimizer will evaluate the “cost” for each major join alternative: Nested-loop, hash-join, or sort-merge. All things being equal, the method with the lowest cost “wins,” and will be selected. Generally speaking, the optimizer does a very good job of choosing a good join method. Under certain conditions—especially in data warehouses--the cost of the nested-loop join is grossly underestimated. Specifically, the cost of reading the index on the second table is set to NULL. This leads to a distorted estimate of the cost of performing a nested loop, and faulty selection of the nested-loop join method. When this occurs, this selection is often the worst possible choice, especially if the tables are large. Of course this scenario leads to serious performance degradation. Tests have confirmed this behavior for both Oracle 8i and 9i--even when the statistics have been properly gathered. I have personally seen this scenario many times in production. (In most cases, we used the SQL hint USE_HASH to correct the join method.) The conditions that must be present to elicit this odd behavior are:   

The SQL code must specify a join The join column must match the second table’s primary key. The primary key index on the second table must have “BLEVEL” of 1. 1

In the illustration below, we see this condition satisfied between the two tables BIG and SMALL. They are joined on the column CUST_ID, which also happens to be the primary key in the table SMALL. Our SQL query is: SELECT CUST_NAME FROM BIG, SMALL WHERE BIG.CUST_ID = SMALL_CUST_ID;

BIG 10,000,000 rows

CUST_ID

SMALL 10,000 rows

Primary key = CUST_ID

1

The BLEVEL of an index is easily gleaned from the DBA_INDEXES table. This field stands for the “B*Tree level.” This is the depth of the index from its root block to its leaf blocks. A BLEVEL of 1 suggests that the table is only of moderate size, with less than 1 million rows.

Ramesh Raj

When the above conditions are met, then the cost associated with reading the PK index will be NULL. With the cost of using an index “free,” the nested loop really looks good; this will entice the optimizer to select this join method. After all, what can be better than a “free” join? In reality, the cost of the join will certainly not be free. In some cases, the optimizer’s estimate of the total join cost can easily be off by a factor of 1000. The most egregious example of this is a join in which the PK index on the second table completely satisfies the query, and the table need not be separately accessed. In this case, the nested loop step not only looks cheap, it appears to be free! When the index access cost is zero, the cost of this step never goes up, no matter how many rows are in the driving table! (Of course, if the driving table has only a few thousand rows, the performance impact is probably not noticeable.) Since the conditions of this oddity require that the second table in the join not be very large, one might think that this discussion is only an academic issue. Not so! While it is true that reading the PK index will certainly be fast, the main consideration is how many rows are returned from querying the first table. The number of index reads will be proportional to this set. So, if there are 10 million rows in this driving set, there will be 10 million index reads. We see that the small size of the second table does not really alleviate the problem. Let’s take a look at a few Oracle execution plans to see what is happening. The following execution plan is a “good” one. It correctly shows that the cost associated with the PK index is 1. (That happens because the index used for this example has a value for BLEVEL of greater than one.) COST ID PARENT OPERATION OBJECT_NAME -------- ---- ------ ----------------------------------- ------------20001 0 SELECT STATEMENT 1 0 SORT AGGREGATE 20001 2 1 NESTED LOOPS 1 3 2 INDEX FAST FULL SCAN SYS_C009988 4 2 PARTITION RANGE ITERATOR 2 5 4 TABLE ACCESS BY GLOBAL INDEX RO CUST 1 6 5 INDEX UNIQUE SCAN CUST_PK

We see that the total optimizer cost is 20001, which properly takes into account all of the steps in the nested loop. (Note that even though the above example happens to reflect partitioned tables, this issue is not specific to the partitioning option.)

Ramesh Raj

Let’s now look at the “bad” case. The following SQL requires a simple join between two tables: DRIVER and SMALL. The driving table has 160,000 rows. Here is the SQL: SELECT COUNT(D.CUST_NAME) FROM DRIVER D, SMALL S WHERE D.BILL_ID = S.BILL_ID

Here is the execution plan: COST ID PARENT OPERATION OBJECT_NAME ------ ---- ------ ----------------------------------- --------------2 0 SELECT STATEMENT 1 0 SORT GROUP BY 2 2 1 NESTED LOOPS 2 3 2 TABLE ACCESS FULL DRIVER 4 2 INDEX UNIQUE SCAN S_PK

We notice something odd right away that should alarm us. Why is Oracle using a nested loop when there isn’t any restrictive condition in the SQL? That is, we know that the database engine must process all the rows. Normally, a full-table scan of each table, followed by either a hashjoin or sort-merge join would be the correct choice in this situation. Why would Oracle want to perform a nested-loop, requiring 160,000 index scans? The answer is, Oracle doesn’t mind doing 160,000 index look-ups because it thinks they are free. Notice that there is no entry in the COST column for the index operation (the very last line above). Thus, the optimizer calculates that the total cost of processing the entire SQL statement is just “2,” when it should probably be closer to 1,000. In fact, even the value of 2 is the cost of scanning the DRIVER table; the actual nested loop operation is free! To clarify, even if there were a billion rows in the DRIVER table, a billion index reads would still require “no effort.” In actuality, of course, the work required to process the SQL via nested loop is vastly different than the optimizer thinks. For this particular SQL, testing showed that the nested loop join required 320,000 logical reads. The hash join option, the obvious choice, only required 573 reads.

Ramesh Raj