Home » RDBMS Server » Performance Tuning » Optimiser Cost Caclulation for nested loop join (linux, oracle 10g)
Optimiser Cost Caclulation for nested loop join [message #548925] Tue, 27 March 2012 04:16 Go to next message
rekha.singhal@tcs.com
Messages: 6
Registered: March 2012
Location: India
Junior Member
Following is the query on TPC-H schema.

explain plan for select
count(*)
from
orders,
lineitem
where
o_orderkey= l_orderkey.

The trace 10053 (as shown below) for this query shows nested loop join with Lineitem as outer table and Orders as inner table. It is effectively join on composite index (pk_lineitem) of Lineitem and unique index(Pk_orderkey) of Orders table. The cost calculation formula as given in the book as "outer table cost + cardinality of outer table * inner table cost " fails here. I am not able to understand this.

BASE STATISTICAL INFORMATION
***********************
Table Stats::
Table: LINEITEM Alias: LINEITEM
#Rows: 6001215 #Blks: 109048 AvgRowLen: 124.00
Column (#1): L_ORDERKEY(NUMBER)
AvgLen: 6.00 NDV: 1500000 Nulls: 0 Density: 6.6667e-07 Min: 1 Max: 6000000
Index Stats::
Index: LINEITEM_PRTK Col#: 2
LVLS: 2 #LB: 12931 #DK: 197757 LB/K: 1.00 DB/K: 29.00 CLUF: 5812082.00
Index: LINEITEM_SI Col#: 14
LVLS: 2 #LB: 29439 #DK: 4 LB/K: 7359.00 DB/K: 109769.00 CLUF: 439077.00
Index: LINEITEM_SM Col#: 15
LVLS: 2 #LB: 18648 #DK: 7 LB/K: 2664.00 DB/K: 112004.00 CLUF: 784030.00
Index: PK_LINEITEM Col#: 1 4
LVLS: 2 #LB: 15440 #DK: 5879916 LB/K: 1.00 DB/K: 1.00 CLUF: 120630.00
***********************
Table Stats::
Table: ORDERS Alias: ORDERS
#Rows: 1500000 #Blks: 24244 AvgRowLen: 110.00
Column (#1): O_ORDERKEY(NUMBER)
AvgLen: 6.00 NDV: 1500000 Nulls: 0 Density: 6.6667e-07 Min: 163 Max: 5998114
Index Stats::
Index: PK_ORDERS Col#: 1
LVLS: 2 #LB: 3307 #DK: 1500000 LB/K: 1.00 DB/K: 1.00 CLUF: 24045.00

Join order[2]: LINEITEM[LINEITEM]#1 ORDERS[ORDERS]#0
***************
Now joining: ORDERS[ORDERS]#0
***************
NL Join
Outer table: Card: 6001215.00 Cost: 2994.16 Resp: 2994.16 Degree: 1 Bytes: 6
Inner table: ORDERS Alias: ORDERS
Access Path: TableScan
NL Join: Cost: 27976374778.51 Resp: 27976374778.51 Degree: 0
Cost_io: 27873478291.00 Cost_cpu: 2386397111117456
Resp_io: 27873478291.00 Resp_cpu: 2386397111117456
Access Path: index (index (FFS))
Index: PK_ORDERS
resc_io: 633.55 resc_cpu: 203550602
ix_sel: 0.0000e+00 ix_sel_with_filters: 1
Inner table: ORDERS Alias: ORDERS
Access Path: index (FFS)
NL Join: Cost: 3854751895.27 Resp: 3854751895.27 Degree: 0
Cost_io: 3802081121.00 Cost_cpu: 1221551742006481
Resp_io: 3802081121.00 Resp_cpu: 1221551742006481
Access Path: index (UniqueScan)
Index: PK_ORDERS
resc_io: 1.00 resc_cpu: 15293
ix_sel: 6.6667e-07 ix_sel_with_filters: 6.6667e-07
NL Join (ordered): Cost: 10714.35 Resp: 10714.35 Degree: 1
Cost_io: 6722.00 Cost_cpu: 92591405803
Resp_io: 6722.00 Resp_cpu: 92591405803
Access Path: index (AllEqUnique)
Index: PK_ORDERS
resc_io: 1.00 resc_cpu: 15293
ix_sel: 6.6667e-07 ix_sel_with_filters: 6.6667e-07
NL Join (ordered): Cost: 10714.35 Resp: 10714.35 Degree: 1
Cost_io: 6722.00 Cost_cpu: 92591405803
Resp_io: 6722.00 Resp_cpu: 92591405803
Best NL cost: 10714.35
resc: 10714.35 resc_io: 6722.00 resc_cpu: 92591405803
resp: 10714.35 resp_io: 6722.00 resp_cpu: 92591405803


Kindly expalin how the cost has been calculated. This does not follow the traditional nested loop cost formula as mentioned in the book.

Thanks
Regards,

Rekha Singhal
  • Attachment: trace_1gb.txt
    (Size: 36.73KB, Downloaded 496 times)
Re: Optimiser Cost Caclulation for nested loop join [message #548935 is a reply to message #548925] Tue, 27 March 2012 05:54 Go to previous messageGo to next message
dbaabdul
Messages: 4
Registered: March 2012
Location: India
Junior Member

Hi Rekha,

Today is my first day in this forum and don't know the proper rules and regulations properly..

While checking the threads, i just came across to your post and seen that you have problem in calculation of optimizations.

Could you please follow the below steps and upload the screen shot of your execution plan, if possible i am not sure if you can attache the secreen shot with your post.

1: SQL> set line 500
2:SQL> SET AUTOTRACE TRACEONLY EXPLAIN
3: SQL> <and your query>

Regards,
Abdul.
Re: Optimiser Cost Caclulation for nested loop join [message #548952 is a reply to message #548935] Tue, 27 March 2012 06:28 Go to previous messageGo to next message
Michel Cadot
Messages: 67923
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
Quote:
Today is my first day in this forum and don't know the proper rules and regulations properly..


OraFAQ Forum Guide
How to use [code] tags and make your code easier to read

Regards
Michel
Re: Optimiser Cost Caclulation for nested loop join [message #548961 is a reply to message #548925] Tue, 27 March 2012 06:37 Go to previous messageGo to next message
dbaabdul
Messages: 4
Registered: March 2012
Location: India
Junior Member

Thanks Michel.
Re: Optimiser Cost Caclulation for nested loop join [message #548965 is a reply to message #548925] Tue, 27 March 2012 06:40 Go to previous messageGo to next message
dbaabdul
Messages: 4
Registered: March 2012
Location: India
Junior Member

Rekha,

Nested Loop Join Costing
As described previously, the optimizer has 3 main join methods available when joining 2 data sets together:

Nested Loop Join
Sort Merge Join
Hash Join
Each method has a different associated formula for its cost of execution. Here I will look at the Nested Loop Join, which is the most straightforward in some respects. Some of this information, such as the costing formula, are given in the Oracle Performance Tuning Guide Manual, in the chapter on the Query Optimizer.

A Nested Loop Join reads data from one data set - the Outer data set - and for each data row retrieves corresponding rows from the other data set - the Inner data set. Clearly the Inner data set is accessed separately for each data row in the Outer data set. And the number of rows in a data set is termed its Cardinality. Hence the cost formula for a Nested Loop Join is as follows, where "Outer" and "Inner" refer to their respective data sets, and square brackets used to enclose each individual element:

[Cost of Outer Access] + ([Cardinality of Outer] * [Cost of Inner Access])
The Outer and Inner costs will have been determined earlier by the Optimizer, either as a single table access cost or as the cost of a previous join between data sets. Thus these component costs do not have to be recalculated by the Optimizer.


Example

Consider the following query using a table with 100,000 rows in it over 1252 * 8 KB blocks:

select it1.i1
from insert_test_1 it1, insert_test_1 it2
where it1.i1 = it2.i4
and it1.i3 = 99

I am using the same table twice in the query, with an alias for each occurrence of it.

There are indexes on each column i.e. on i1, i2 (not used here), i3 and i4. The i1 index is unique, but the others are not.

Remember that the Optimizer starts with the data set with the lowest cardinality (smallest number of data rows). In this case this is "it1", because the "i3" column has 100 rows for each possible value. This gives a cardinality of 100 for "it1" as the Outer data set. The lowest cost access to this is using the index on this, which has a cost of 102 (costed using index range scan described in an earlier post).

To join to "it2" in this case, the index on "i4" can be used. In this case no other data columns are needed from the "it2" table, and thus the cost is really that of reading the index leaf block with that particular value. For this index all entries for one value fit within one leaf block (leaf blocks per key value is 1), so the access cost is just 1 to read that particular leaf block.

The Nested Loop Cost is therefore:-

102 + (100 * 1) = 102 + 100 = 202
This was verified by examining a 10053 event trace file when this SQL was executed. The costs reported differ only after the decimal point, due to a combination of rounding of values within Oracle and additional minor costs such as CPU cost (in 10g).

The 10053 trace file also showed that the Optimizer also costed other variations of the Nested Loop Join. This agrees with the statement that the Optimizer costs all possible access and join plans to determine the cheapest one.

Also considered are a full table scan of it2, at a cost of 243.1. The Nested Loop cost of this should be:

102.1 + (100.2 * 243.1) = 102.1 + 24358.2 = 244460.3
The 10053 trace file actually reported a cost of 24580.26 total. Again this would be different due to rounding of results and additional CPU costs. Nevertheless, it is very close to our calculated value for the I/O cost only.

Regards,
Abdul
Re: Optimiser Cost Caclulation for nested loop join [message #548967 is a reply to message #548965] Tue, 27 March 2012 06:45 Go to previous messageGo to next message
Michel Cadot
Messages: 67923
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
Another point of good behaviour (in addition to follow forum guide) is to NOT appropriate others work.
You took this from John Brady's blog, post a link to the article and do NOT post it as it is from you. We hate thief.

Regards
Michel

[Updated on: Tue, 27 March 2012 06:46]

Report message to a moderator

Re: Optimiser Cost Caclulation for nested loop join [message #548975 is a reply to message #548925] Tue, 27 March 2012 06:50 Go to previous messageGo to next message
dbaabdul
Messages: 4
Registered: March 2012
Location: India
Junior Member

Sure Michel, actually i initially pasted the link it thrown an error message saying you are not allowed to post the link. That is the reason i pasted the body directly.

Sorry for the inconvenience caused!!

Regards,
Abdul
Re: Optimiser Cost Caclulation for nested loop join [message #548977 is a reply to message #548975] Tue, 27 March 2012 06:53 Go to previous message
Michel Cadot
Messages: 67923
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
It's OK. Smile

Regards
Michel
Previous Topic: Understanding Execution Plan of a query
Next Topic: How to decide Partiitioning columns?
Goto Forum:
  


Current Time: Sat Jul 31 16:57:08 CDT 2021