Chris Pollett >
Old Classes
>
CS157b
( Print
View )
Student Corner:
[Grades Sec1]
[Grades Sec2]
[Submit Sec1]
[Submit Sec2]
[Email List Sec1]
[Email List Sec2]
[Lecture Notes]
Course Info:
[Texts & Links]
[Topics]
[Grading]
[HW Info]
[Exam Info]
[Regrades]
[Honesty]
[Announcements]
HW Assignments:
[Hw1]
[Hw2]
[Hw3]
[Hw4]
[Hw5]
Practice Exams:
[Mid1]
[Mid2]
[Final]
HW3 Solutions Page
5.3.8
6.4.3
The equation to estimate the number of I/Os for a block nested loop join is: I/Os = B(S) + [B(S)/(M-1)]*B(R). The square brackets mean we round up to the next larger integer. We are given B(S)=B(R)= 10,000.
(a) If we want to join S, R in no more than 100,000 I/Os, then we need that 90,000 > [10,000/(M-1)]*10,000. Solving for M and accounting for the fact that we need to round up gives M = 1113 blocks of memory.
(b) If we want to join S, R in no more that 25,000 I/Os, then we need that 15,000 > [10,000/(M-1)]*10,000. Dividing by 10,000, notice this time we get 3/2 > [10,000/(M-1)] and the expression on the right should be an integer. So it must be 1, which means 10,000 = M-1, so M = 10,001. Thus, we end up doing essentially the one pass algorithm.
(c) Let's consider what happens if we want to join S and R in 15,000 I/Os. Immediately, we should see we are being asked the impossible as R and S together are stored in 20,000 blocks. So to compute the join we need to read at least this many blocks.
7.1.2
(a) OR and NOT rules
OR rule: <Condition> ::= <Condition> OR <Condition>
NOT rule: <Condition> ::= NOT <Condition>
(b) Other Comparisons:
LESS THAN <Condition> ::= <Attibute> < <Attibute>
LESS THAN EQUAL <Condition> ::= <Attibute> <= <Attibute>
GREATER THAN <Condition> ::= <Attibute> > <Attibute>
GREATER THAN EQUAL <Condition> ::= <Attibute> >= <Attibute>
(c) Parenthesized Conditions: <Condition> ::= (<Condition>)
(d) EXISTS Conditions: <Condition> ::= EXISTS (<Condition>)
DataGenerator.java
import java.util.*;
import java.io.*;
/**
This class consists of a bunch of public static methods used to generate
row data for the CS157B HW3.
Typically one would run this program from the command line with a line like:
java DataGenerator start_value num wrap_number txtfile
here start_value is the initial value for the A column, num is the number of
rows to be generated, wrap_number is the number of rows before which the B column
cycles back to 1, and finally, txtfile is the file to write the data to.
@author Chris Pollett
@version 4.26.2005
*/
public class DataGenerator
{
/**
Generates and writes the data file to be used in CS157B HW3.
This data consists of numRows many rows each consisting of two
columns of int's the first column is a counter starting with value
startNum, the second column starts at value 1 and counts mod wrapNumber
@param startNum -- initial value for the columnA counter
@param numRows -- number of rows of data to create
@param wrapNumber -- number of rows of before the columnB value repeats
@param file -- file to write data to
*/
public static void createData( int startNum, int numRows, int wrapNumber, String file)
{
try
{
PrintStream outFile = new PrintStream(
new FileOutputStream(file));
int columnB = 1;
int endNum = startNum + numRows;
String row;
for(int columnA = startNum; columnA < endNum; columnA++)
{
row = "" + columnA + " " + columnB;
outFile.println(row);
columnB = (columnB >= wrapNumber) ? 1 : columnB + 1;
}
outFile.close();
}
catch(IOException ie)
{
ie.printStackTrace();
}
}
/**
Calls createData with the command line arguments to generate data for Hw3
data
@param args - array of command line arguments.
*/
public static void main (String [] args)
{
if(args.length < 4)
{
System.out.println("To use:");
System.out.println("java DataGenerator start_value num wrap_number txtfile");
System.out.println("Here start_value is the initial value for the A column,");
System.out.println("num is how many rows you'd like generated,");
System.out.println("wrap_number is the number of rows before which the B column" +
"cycles back to 1,,");
System.out.println("and txtfile is the file you'd like data written to");
}
else
createData(Integer.parseInt(args[0]), Integer.parseInt(args[1]), Integer.parseInt(args[2]),
args[3]);
}
}
Here is a spool of me generating my data:
|sigma:hw3:96>java DataGenerator 0 1000 100 R1data.txt |sigma:hw3:97*gt;java DataGenerator 1000 1000 100 R2data.txt |sigma:hw3:98>java DataGenerator 2000 1000 100 R3data.txt |sigma:hw3:99>java DataGenerator 3000 1000 100 R4data.txt |sigma:hw3:100>java DataGenerator 4000 1000 100 R5data.txt
CreateTables.sql
This was a short script I had to create my tables:
create table R1 ( A INTEGER, B INTEGER ); create table R2 ( A INTEGER, B INTEGER ); create table R3 ( A INTEGER, B INTEGER ); create table R4 ( A INTEGER, B INTEGER ); create table R5 ( A INTEGER, B INTEGER );
Here is what the session looked like where I ran this:
SQL*Plus: Release 10.1.0.3.0 - Production on Tue Apr 26 23:46:53 2005 Copyright (c) 1982, 2004, Oracle. All rights reserved. Enter password: Connected to: Oracle8i Enterprise Edition Release 8.1.7.0.0 - Production With the Partitioning option JServer Release 8.1.7.0.0 - Production SQL> @CreateTables.sql Table created. Table created. Table created. Table created. Table created. SQL>
Control Files
Here are the control files I used to bulk load my data:
LoadDataR1.ctl
LOAD DATA INFILE R1data.txt INTO TABLE R1 FIELDS TERMINATED BY ' ' ( A, B)
LoadDataR2.ctl
LOAD DATA INFILE R2data.txt INTO TABLE R2 FIELDS TERMINATED BY ' ' ( A, B)
LoadDataR3.ctl
LOAD DATA INFILE R3data.txt INTO TABLE R3 FIELDS TERMINATED BY ' ' ( A, B)
LoadDataR4.ctl
LOAD DATA INFILE R4data.txt INTO TABLE R4 FIELDS TERMINATED BY ' ' ( A, B)
LoadDataR5.ctl
LOAD DATA INFILE R5data.txt INTO TABLE R5 FIELDS TERMINATED BY ' ' ( A, B)
Here is a snippet from the session where I did the bulk loading:
|sigma:hw3:107>sqlldr pollett_ora control=LoadDataR1.ctl log=LoadR1.log Password: SQL*Loader: Release 8.1.7.0.0 - Production on Wed Apr 27 00:07:06 2005 (c) Copyright 2000 Oracle Corporation. All rights reserved. Commit point reached - logical record count 64 Commit point reached - logical record count 128 Commit point reached - logical record count 192 Commit point reached - logical record count 256 Commit point reached - logical record count 320 Commit point reached - logical record count 384 Commit point reached - logical record count 448 Commit point reached - logical record count 512 Commit point reached - logical record count 576 Commit point reached - logical record count 640 Commit point reached - logical record count 704 Commit point reached - logical record count 768 Commit point reached - logical record count 832 Commit point reached - logical record count 896 Commit point reached - logical record count 960 Commit point reached - logical record count 1000 |sigma:hw3:108>sqlldr pollett_ora control=LoadDataR2.ctl log=LoadR2.log Password: SQL*Loader: Release 8.1.7.0.0 - Production on Wed Apr 27 00:10:21 2005 (c) Copyright 2000 Oracle Corporation. All rights reserved. Commit point reached - logical record count 64 Commit point reached - logical record count 128 Commit point reached - logical record count 192 Commit point reached - logical record count 256 Commit point reached - logical record count 320 Commit point reached - logical record count 384 Commit point reached - logical record count 448 Commit point reached - logical record count 512 Commit point reached - logical record count 576 Commit point reached - logical record count 640 Commit point reached - logical record count 704 Commit point reached - logical record count 768 Commit point reached - logical record count 832 Commit point reached - logical record count 896 Commit point reached - logical record count 960 Commit point reached - logical record count 1000 |sigma:hw3:109>sqlldr pollett_ora control=LoadDataR3.ctl log=LoadR3.log Password: SQL*Loader: Release 8.1.7.0.0 - Production on Wed Apr 27 00:10:32 2005 (c) Copyright 2000 Oracle Corporation. All rights reserved. Commit point reached - logical record count 64 Commit point reached - logical record count 128 Commit point reached - logical record count 192 Commit point reached - logical record count 256 Commit point reached - logical record count 320 Commit point reached - logical record count 384 Commit point reached - logical record count 448 Commit point reached - logical record count 512 Commit point reached - logical record count 576 Commit point reached - logical record count 640 Commit point reached - logical record count 704 Commit point reached - logical record count 768 Commit point reached - logical record count 832 Commit point reached - logical record count 896 Commit point reached - logical record count 960 Commit point reached - logical record count 1000 |sigma:hw3:110>sqlldr pollett_ora control=LoadDataR4.ctl log=LoadR4.log Password: SQL*Loader: Release 8.1.7.0.0 - Production on Wed Apr 27 00:10:44 2005 (c) Copyright 2000 Oracle Corporation. All rights reserved. Commit point reached - logical record count 64 Commit point reached - logical record count 128 Commit point reached - logical record count 192 Commit point reached - logical record count 256 Commit point reached - logical record count 320 Commit point reached - logical record count 384 Commit point reached - logical record count 448 Commit point reached - logical record count 512 Commit point reached - logical record count 576 Commit point reached - logical record count 640 Commit point reached - logical record count 704 Commit point reached - logical record count 768 Commit point reached - logical record count 832 Commit point reached - logical record count 896 Commit point reached - logical record count 960 Commit point reached - logical record count 1000 |sigma:hw3:111>sqlldr pollett_ora control=LoadDataR5.ctl log=LoadR5.log Password: SQL*Loader: Release 8.1.7.0.0 - Production on Wed Apr 27 00:10:54 2005 (c) Copyright 2000 Oracle Corporation. All rights reserved. Commit point reached - logical record count 64 Commit point reached - logical record count 128 Commit point reached - logical record count 192 Commit point reached - logical record count 256 Commit point reached - logical record count 320 Commit point reached - logical record count 384 Commit point reached - logical record count 448 Commit point reached - logical record count 512 Commit point reached - logical record count 576 Commit point reached - logical record count 640 Commit point reached - logical record count 704 Commit point reached - logical record count 768 Commit point reached - logical record count 832 Commit point reached - logical record count 896 Commit point reached - logical record count 960 Commit point reached - logical record count 1000 |sigma:hw3:112>
Bulk Load Log Files
LoadR1.log
SQL*Loader: Release 8.1.7.0.0 - Production on Wed Apr 27 00:07:06 2005 (c) Copyright 2000 Oracle Corporation. All rights reserved. Control File: LoadDataR1.ctl Data File: R1data.txt Bad File: R1data.bad Discard File: none specified (Allow all discards) Number to load: ALL Number to skip: 0 Errors allowed: 50 Bind array: 64 rows, maximum of 65536 bytes Continuation: none specified Path used: Conventional Table R1, loaded from every logical record. Insert option in effect for this table: INSERT Column Name Position Len Term Encl Datatype ------------------------------ ---------- ----- ---- ---- --------------------- A FIRST * WHT CHARACTER B NEXT * WHT CHARACTER Table R1: 1000 Rows successfully loaded. 0 Rows not loaded due to data errors. 0 Rows not loaded because all WHEN clauses were failed. 0 Rows not loaded because all fields were null. Space allocated for bind array: 33024 bytes(64 rows) Space allocated for memory besides bind array: 0 bytes Total logical records skipped: 0 Total logical records read: 1000 Total logical records rejected: 0 Total logical records discarded: 0 Run began on Wed Apr 27 00:07:06 2005 Run ended on Wed Apr 27 00:07:10 2005 Elapsed time was: 00:00:04.01 CPU time was: 00:00:00.05
LoadR2.log
SQL*Loader: Release 8.1.7.0.0 - Production on Wed Apr 27 00:10:21 2005 (c) Copyright 2000 Oracle Corporation. All rights reserved. Control File: LoadDataR2.ctl Data File: R2data.txt Bad File: R2data.bad Discard File: none specified (Allow all discards) Number to load: ALL Number to skip: 0 Errors allowed: 50 Bind array: 64 rows, maximum of 65536 bytes Continuation: none specified Path used: Conventional Table R2, loaded from every logical record. Insert option in effect for this table: INSERT Column Name Position Len Term Encl Datatype ------------------------------ ---------- ----- ---- ---- --------------------- A FIRST * WHT CHARACTER B NEXT * WHT CHARACTER Table R2: 1000 Rows successfully loaded. 0 Rows not loaded due to data errors. 0 Rows not loaded because all WHEN clauses were failed. 0 Rows not loaded because all fields were null. Space allocated for bind array: 33024 bytes(64 rows) Space allocated for memory besides bind array: 0 bytes Total logical records skipped: 0 Total logical records read: 1000 Total logical records rejected: 0 Total logical records discarded: 0 Run began on Wed Apr 27 00:10:21 2005 Run ended on Wed Apr 27 00:10:24 2005 Elapsed time was: 00:00:02.88 CPU time was: 00:00:00.04
LoadR3.log
SQL*Loader: Release 8.1.7.0.0 - Production on Wed Apr 27 00:10:32 2005 (c) Copyright 2000 Oracle Corporation. All rights reserved. Control File: LoadDataR3.ctl Data File: R3data.txt Bad File: R3data.bad Discard File: none specified (Allow all discards) Number to load: ALL Number to skip: 0 Errors allowed: 50 Bind array: 64 rows, maximum of 65536 bytes Continuation: none specified Path used: Conventional Table R3, loaded from every logical record. Insert option in effect for this table: INSERT Column Name Position Len Term Encl Datatype ------------------------------ ---------- ----- ---- ---- --------------------- A FIRST * WHT CHARACTER B NEXT * WHT CHARACTER Table R3: 1000 Rows successfully loaded. 0 Rows not loaded due to data errors. 0 Rows not loaded because all WHEN clauses were failed. 0 Rows not loaded because all fields were null. Space allocated for bind array: 33024 bytes(64 rows) Space allocated for memory besides bind array: 0 bytes Total logical records skipped: 0 Total logical records read: 1000 Total logical records rejected: 0 Total logical records discarded: 0 Run began on Wed Apr 27 00:10:32 2005 Run ended on Wed Apr 27 00:10:36 2005 Elapsed time was: 00:00:03.90 CPU time was: 00:00:00.08
LoadR4.log
SQL*Loader: Release 8.1.7.0.0 - Production on Wed Apr 27 00:10:44 2005 (c) Copyright 2000 Oracle Corporation. All rights reserved. Control File: LoadDataR4.ctl Data File: R4data.txt Bad File: R4data.bad Discard File: none specified (Allow all discards) Number to load: ALL Number to skip: 0 Errors allowed: 50 Bind array: 64 rows, maximum of 65536 bytes Continuation: none specified Path used: Conventional Table R4, loaded from every logical record. Insert option in effect for this table: INSERT Column Name Position Len Term Encl Datatype ------------------------------ ---------- ----- ---- ---- --------------------- A FIRST * WHT CHARACTER B NEXT * WHT CHARACTER Table R4: 1000 Rows successfully loaded. 0 Rows not loaded due to data errors. 0 Rows not loaded because all WHEN clauses were failed. 0 Rows not loaded because all fields were null. Space allocated for bind array: 33024 bytes(64 rows) Space allocated for memory besides bind array: 0 bytes Total logical records skipped: 0 Total logical records read: 1000 Total logical records rejected: 0 Total logical records discarded: 0 Run began on Wed Apr 27 00:10:44 2005 Run ended on Wed Apr 27 00:10:46 2005 Elapsed time was: 00:00:02.65 CPU time was: 00:00:00.09
LoadR5.log
SQL*Loader: Release 8.1.7.0.0 - Production on Wed Apr 27 00:10:54 2005 (c) Copyright 2000 Oracle Corporation. All rights reserved. Control File: LoadDataR5.ctl Data File: R5data.txt Bad File: R5data.bad Discard File: none specified (Allow all discards) Number to load: ALL Number to skip: 0 Errors allowed: 50 Bind array: 64 rows, maximum of 65536 bytes Continuation: none specified Path used: Conventional Table R5, loaded from every logical record. Insert option in effect for this table: INSERT Column Name Position Len Term Encl Datatype ------------------------------ ---------- ----- ---- ---- --------------------- A FIRST * WHT CHARACTER B NEXT * WHT CHARACTER Table R5: 1000 Rows successfully loaded. 0 Rows not loaded due to data errors. 0 Rows not loaded because all WHEN clauses were failed. 0 Rows not loaded because all fields were null. Space allocated for bind array: 33024 bytes(64 rows) Space allocated for memory besides bind array: 0 bytes Total logical records skipped: 0 Total logical records read: 1000 Total logical records rejected: 0 Total logical records discarded: 0 Run began on Wed Apr 27 00:10:54 2005 Run ended on Wed Apr 27 00:10:57 2005 Elapsed time was: 00:00:02.76 CPU time was: 00:00:00.08
Working with EXPLAIN PLAN
I next used the following script, CreatePlan.sql, to create my plan_table:
CREATE TABLE plan_table ( statement_id VARCHAR2(30), timestamp DATE, remarks VARCHAR2(80), operation VARCHAR2(30), options VARCHAR2(30), object_node VARCHAR2(128), object_owner VARCHAR2(30), object_name VARCHAR2(30), object_instance NUMBER, object_type VARCHAR2(30), optimizer VARCHAR2(255), search_columns NUMBER, id NUMBER, parent_id NUMBER, position NUMBER, other LONG );
I ran it like this:
SQL> @CreatePlan Table created. SQL>
Plan's Tested
The following script, ExplainPlan.sql, contains the plans I tested:
/* Get rid of the query buffer */
clear buffer
/*Delete old stuff */
delete from plan_table;
commit;
COL operation FORMAT A20
COL options FORMAT A15
COL object_name FORMAT A20
COL id FORMAT 999999999
COL parent_id FORMAT 999999999
set echo on
/* Explaining the Plan1
This plan is roughly what one gets by reading
off the HW problem. I tried this next query
with and without the NO_CACHE hint (what a
hint is, is explained in the comment before Plan 4)
and it took about the same time
*/
EXPLAIN PLAN set statement_id = 'PLAN1' for
select *
from R1, R2, R3, R4, R5
where
R1.B=51 and
R1.B=R2.B and R2.B=R3.B and
R3.B=R4.B and R4.B=R5.B;
select operation, options, object_name, id, parent_id
from plan_table
where statement_id = 'PLAN1' ;
/* Explaining the Plan2.
This is essentially a similar plan to plan 1 but table order changed.
If all tables are the same size, the order in the from clause seems
to be what Oracle uses.
*/
EXPLAIN PLAN set statement_id = 'PLAN2' for
select *
from R5, R1, R2, R3, R4
where
R1.B=51 and R1.B=R2.B and R2.B=R3.B and
R3.B=R4.B and R4.B=R5.B ;
select operation, options, object_name, id, parent_id
from plan_table
where statement_id = 'PLAN2' ;
/* Explaining the Plan3
What happens when you use OR's and NOT's in the where clause?
Seems Oracle gives you same plan. So it looks like Oracle is swallowing
selection into the join. Problem the sort step makes checking the condition fast.
*/
EXPLAIN PLAN set statement_id = 'PLAN3' for
select *
from R1,R2, R3,R4, R5
where
R1.B=R2.B and R2.B=R3.B and
R3.B=R4.B and R4.B=R5.B and not ( R1.B < 51 or R5.B > 51);
select operation, options, object_name, id, parent_id
from plan_table
where statement_id = 'PLAN3' ;
/* Explaining the Plan4.
In this query views are used to try to force the order of operation
Notice I am using the hint to the Oracle Optimizer not to use merge
joins (so will get nested loop joins). The comment with the + NO_MERGE
is not a comment but an optimizer hint.
*/
create or replace view T1 as
select A, B from R1 where B=51;
create or replace view T2 as
select A, B from R2 where B=51;
create or replace view T3 as
select A, B from R3 where B=51;
create or replace view T4 as
select A, B from R4 where B=51;
create or replace view T5 as
select A, B from R5 where B=51;
EXPLAIN PLAN set statement_id = 'PLAN3' for
select /*+ NO_MERGE */ *
from
T1, T2, T3, T4, T5;
select operation, options, object_name, id, parent_id
from plan_table
where statement_id = 'PLAN4' ;
/* Explaining the Plan5
Here's what NO_MERGE looks like on the original query
*/
EXPLAIN PLAN set statement_id = 'PLAN5' for
select /*+NO_MERGE */ *
from R1, R2, R3, R4, R5
where
R1.B=51 and
R1.B=R2.B and R2.B=R3.B and
R3.B=R4.B and R4.B=R5.B;
select operation, options, object_name, id, parent_id
from plan_table
where statement_id = 'PLAN5' ;
/* Explaining the Plan6
Here's a plan attempting using hash joins.
When I did explain plan on it seemed Oracle
Left it as a sort-merge join
*/
EXPLAIN PLAN set statement_id = 'PLAN6' for
select /*+USE_HASH */ *
from R1,R2, R3,R4, R5
where
R1.B=51 and R1.B=R2.B and R2.B=R3.B and
R3.B=R4.B and R4.B=R5.B ;
select operation, options, object_name, id, parent_id
from plan_table
where statement_id = 'PLAN6' ;
/* Explaining the Plan7
Here's what NO_REWRITE looks like on the view
based query
*/
create or replace view S1 as
select R1.A A1, R1.B B1 , R2.A A2, R2.b B2 from R1, R2 where R1.B=R2.B;
create or replace view S2 as
select /*+NO_MERGE USE_NL */ S1.*, R3.A A3, R3.B B3 from S1, R3 where S1.B1=R3.B;
create or replace view S3 as
select /*+NO_MERGE USE_NL */ S2.*, R4.A A4, R4.B B4 from S2, R4 where S2.B1=R4.B;
create or replace view S4 as
select /*+NO_MERGE USE_NL */ S3.*, R5.A A5, R5.B B5 from S3, R5 where S3.B1=R5.B;
EXPLAIN PLAN set statement_id = 'PLAN7' for
select * from S4 where B5=51;
select operation, options, object_name, id, parent_id
from plan_table
where statement_id = 'PLAN7' ;
/*
Miscellaneous Plans Testing what explain plan lists
*/
/* Explaining the Plan8
Here' s a plan to see what the select statement in explain plan means.
I have nothing in the where clause, but there is still a select statement.
This and further testing seemed to indicate
select statement is probably just used to indicate the root of the query.
*/
EXPLAIN PLAN set statement_id = 'PLAN8' for
select *
from R1;
select operation, options, object_name, id, parent_id
from plan_table
where statement_id = 'PLAN8' ;
/* Explaining the Plan9
Here' s another plan that seems to illustrate what I was saying under Plan 8.
It returns only on select statement as in Plan 8. Another thing it shows
is that things in the where class do not really seem to show up in the plan.
They seemed to be swallowed up in the TABLE ACCESS lines.
*/
EXPLAIN PLAN set statement_id = 'PLAN9' for
select T.A
from
(select A,B
from R1
where B=51) T,
(select A,B
from R2
where B=51) S;
select operation, options, object_name, id, parent_id
from plan_table
where statement_id = 'PLAN9' ;
set echo off
Script results
Here is the result of running my script:
SQL> SQL> set echo off SQL> @ExplainPLan SP2-0103: Nothing in SQL buffer to run. 107 rows deleted. Commit complete. SQL> SQL> /* Explaining the Plan1 SQL> SQL> This plan is roughly what one gets by reading SQL> off the HW problem. I tried this next query SQL> with and without the NO_CACHE hint (what a SQL> hint is, is explained in the comment before Plan 4) SQL> and it took about the same time SQL> */ SQL> EXPLAIN PLAN set statement_id = 'PLAN1' for 2 select * 3 from R1, R2, R3, R4, R5 4 where 5 R1.B=51 and 6 R1.B=R2.B and R2.B=R3.B and 7 R3.B=R4.B and R4.B=R5.B; Explained. SQL> SQL> select operation, options, object_name, id, parent_id 2 from plan_table 3 where statement_id = 'PLAN1' ; OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- MERGE JOIN 1 0 MERGE JOIN 2 1 MERGE JOIN 3 2 MERGE JOIN 4 3 SORT JOIN 5 4 TABLE ACCESS FULL R5 6 5 SORT JOIN 7 4 TABLE ACCESS FULL R4 8 7 SORT JOIN 9 3 TABLE ACCESS FULL R3 10 9 SORT JOIN 11 2 OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- TABLE ACCESS FULL R2 12 11 SORT JOIN 13 1 TABLE ACCESS FULL R1 14 13 SELECT STATEMENT 0 15 rows selected. SQL> SQL> SQL> /* Explaining the Plan2. SQL> This is essentially a similar plan to plan 1 but table order changed. SQL> If all tables are the same size, the order in the from clause seems SQL> to be what Oracle uses. SQL> */ SQL> SQL> EXPLAIN PLAN set statement_id = 'PLAN2' for 2 select * 3 from R5, R1, R2, R3, R4 4 where 5 R1.B=51 and R1.B=R2.B and R2.B=R3.B and 6 R3.B=R4.B and R4.B=R5.B ; Explained. SQL> SQL> select operation, options, object_name, id, parent_id 2 from plan_table 3 where statement_id = 'PLAN2' ; OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- SELECT STATEMENT 0 MERGE JOIN 1 0 MERGE JOIN 2 1 MERGE JOIN 3 2 MERGE JOIN 4 3 SORT JOIN 5 4 TABLE ACCESS FULL R4 6 5 SORT JOIN 7 4 TABLE ACCESS FULL R3 8 7 SORT JOIN 9 3 TABLE ACCESS FULL R2 10 9 OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- SORT JOIN 11 2 TABLE ACCESS FULL R1 12 11 SORT JOIN 13 1 TABLE ACCESS FULL R5 14 13 15 rows selected. SQL> SQL> /* Explaining the Plan3 SQL> SQL> What happens when you use OR's and NOT's in the where clause? SQL> Seems Oracle gives you same plan. So it looks like Oracle is swallowing SQL> selection into the join. Problem the sort step makes checking the condition fast. SQL> */ SQL> SQL> SQL> EXPLAIN PLAN set statement_id = 'PLAN3' for 2 select * 3 from R1,R2, R3,R4, R5 4 where 5 R1.B=R2.B and R2.B=R3.B and 6 R3.B=R4.B and R4.B=R5.B and not ( R1.B < 51 or R5.B > 51); Explained. SQL> SQL> select operation, options, object_name, id, parent_id 2 from plan_table 3 where statement_id = 'PLAN3' ; OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- SELECT STATEMENT 0 MERGE JOIN 1 0 MERGE JOIN 2 1 MERGE JOIN 3 2 MERGE JOIN 4 3 SORT JOIN 5 4 TABLE ACCESS FULL R5 6 5 SORT JOIN 7 4 TABLE ACCESS FULL R4 8 7 SORT JOIN 9 3 TABLE ACCESS FULL R3 10 9 OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- SORT JOIN 11 2 TABLE ACCESS FULL R2 12 11 SORT JOIN 13 1 TABLE ACCESS FULL R1 14 13 15 rows selected. SQL> SQL> SQL> /* Explaining the Plan4. SQL> In this query views are used to try to force the order of operation SQL> Notice I am using the hint to the Oracle Optimizer not to use merge SQL> joins (so will get nested loop joins). The comment with the + NO_MERGE SQL> is not a comment but an optimizer hint. SQL> */ SQL> SQL> create or replace view T1 as 2 select A, B from R1 where B=51; View created. SQL> SQL> create or replace view T2 as 2 select A, B from R2 where B=51; View created. SQL> SQL> create or replace view T3 as 2 select A, B from R3 where B=51; View created. SQL> SQL> create or replace view T4 as 2 select A, B from R4 where B=51; View created. SQL> SQL> create or replace view T5 as 2 select A, B from R5 where B=51; View created. SQL> SQL> SQL> EXPLAIN PLAN set statement_id = 'PLAN3' for 2 select /*+ NO_MERGE */ * 3 from 4 T1, T2, T3, T4, T5; Explained. SQL> SQL> select operation, options, object_name, id, parent_id 2 from plan_table 3 where statement_id = 'PLAN4' ; no rows selected SQL> SQL> /* Explaining the Plan5 SQL> SQL> Here's what NO_MERGE looks like on the original query SQL> */ SQL> EXPLAIN PLAN set statement_id = 'PLAN5' for 2 select /*+NO_MERGE */ * 3 from R1, R2, R3, R4, R5 4 where 5 R1.B=51 and 6 R1.B=R2.B and R2.B=R3.B and 7 R3.B=R4.B and R4.B=R5.B; Explained. SQL> SQL> select operation, options, object_name, id, parent_id 2 from plan_table 3 where statement_id = 'PLAN5' ; OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- TABLE ACCESS FULL R1 5 4 SORT JOIN 6 4 TABLE ACCESS FULL R2 7 6 SORT JOIN 8 3 TABLE ACCESS FULL R3 9 8 SORT JOIN 10 2 TABLE ACCESS FULL R4 11 10 SORT JOIN 12 1 TABLE ACCESS FULL R5 13 12 SELECT STATEMENT 0 MERGE JOIN CARTESIAN 1 0 OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- MERGE JOIN CARTESIAN 2 1 MERGE JOIN CARTESIAN 3 2 MERGE JOIN CARTESIAN 4 3 14 rows selected. SQL> SQL> /* Explaining the Plan6 SQL> SQL> Here's a plan attempting using hash joins. SQL> When I did explain plan on it seemed Oracle SQL> Left it as a sort-merge join SQL> */ SQL> SQL> SQL> EXPLAIN PLAN set statement_id = 'PLAN6' for 2 select /*+USE_HASH */ * 3 from R1,R2, R3,R4, R5 4 where 5 R1.B=51 and R1.B=R2.B and R2.B=R3.B and 6 R3.B=R4.B and R4.B=R5.B ; Explained. SQL> SQL> select operation, options, object_name, id, parent_id 2 from plan_table 3 where statement_id = 'PLAN6' ; OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- SELECT STATEMENT 0 MERGE JOIN 1 0 MERGE JOIN 2 1 MERGE JOIN 3 2 MERGE JOIN 4 3 SORT JOIN 5 4 TABLE ACCESS FULL R5 6 5 SORT JOIN 7 4 TABLE ACCESS FULL R4 8 7 SORT JOIN 9 3 TABLE ACCESS FULL R3 10 9 OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- SORT JOIN 11 2 TABLE ACCESS FULL R2 12 11 SORT JOIN 13 1 TABLE ACCESS FULL R1 14 13 15 rows selected. SQL> SQL> /* Explaining the Plan7 SQL> SQL> Here's what NO_REWRITE looks like on the view SQL> based query SQL> */ SQL> create or replace view S1 as 2 select R1.A A1, R1.B B1 , R2.A A2, R2.b B2 from R1, R2 where R1.B=R2.B; View created. SQL> SQL> create or replace view S2 as 2 select /*+NO_MERGE USE_NL */ S1.*, R3.A A3, R3.B B3 from S1, R3 where S1.B1=R3.B; View created. SQL> SQL> create or replace view S3 as 2 select /*+NO_MERGE USE_NL */ S2.*, R4.A A4, R4.B B4 from S2, R4 where S2.B1=R4.B; View created. SQL> SQL> create or replace view S4 as 2 select /*+NO_MERGE USE_NL */ S3.*, R5.A A5, R5.B B5 from S3, R5 where S3.B1=R5.B; View created. SQL> SQL> EXPLAIN PLAN set statement_id = 'PLAN7' for 2 select * from S4 where B5=51; Explained. SQL> SQL> select operation, options, object_name, id, parent_id 2 from plan_table 3 where statement_id = 'PLAN7' ; OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- SELECT STATEMENT 0 VIEW S4 1 0 MERGE JOIN CARTESIAN 2 1 TABLE ACCESS FULL R5 3 2 SORT JOIN 4 2 VIEW S3 5 4 MERGE JOIN CARTESIAN 6 5 TABLE ACCESS FULL R4 7 6 SORT JOIN 8 6 VIEW S2 9 8 MERGE JOIN CARTESIAN 10 9 OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- MERGE JOIN CARTESIAN 11 10 TABLE ACCESS FULL R1 12 11 SORT JOIN 13 11 TABLE ACCESS FULL R2 14 13 SORT JOIN 15 10 TABLE ACCESS FULL R3 16 15 17 rows selected. SQL> SQL> SQL> SQL> /* SQL> Miscellaneous Plans Testing what explain plan lists SQL> */ SQL> SQL> /* Explaining the Plan8 SQL> SQL> Here' s a plan to see what the select statement in explain plan means. SQL> I have nothing in the where clause, but there is still a select statement. SQL> This and further testing seemed to indicate SQL> select statement is probably just used to indicate the root of the query. SQL> */ SQL> EXPLAIN PLAN set statement_id = 'PLAN8' for 2 select * 3 from R1; Explained. SQL> SQL> select operation, options, object_name, id, parent_id 2 from plan_table 3 where statement_id = 'PLAN8' ; OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- SELECT STATEMENT 0 TABLE ACCESS FULL R1 1 0 SQL> SQL> SQL> /* Explaining the Plan8 SQL> SQL> Here' s a plan to see what the select statement in explain plan means. SQL> I have nothing in the where clause, but there is still a select statement. SQL> So select_statement is probably just used to indicate projections. SQL> */ SQL> EXPLAIN PLAN set statement_id = 'PLAN9' for 2 select T.A 3 from 4 (select A,B 5 from R1 6 where B=51) T, 7 (select A,B 8 from R2 9 where B=51) S; Explained. SQL> SQL> select operation, options, object_name, id, parent_id 2 from plan_table 3 where statement_id = 'PLAN9' ; OPERATION OPTIONS OBJECT_NAME ID PARENT_ID -------------------- --------------- -------------------- ---------- ---------- SELECT STATEMENT 0 NESTED LOOPS 1 0 TABLE ACCESS FULL R2 2 1 TABLE ACCESS FULL R1 3 1 SQL> SQL> set echo off SQL>
Further Experiments and Conclusion
Experiments 1,2,4,5,7 all yield distinct plans according to Oracle so I do have five distinct plans for the query. To figure out what the tree is for each plan look at a given explain plan result table, make a tree whose vertices are all the distinct id's (labelled also with the operation are the start of the row) and have edges between id's if one is the parent_id of the other.
In addition to the experiments in my script, I tried executing the actual queries listed above from the SQL prompt. That is, I ran commands like:
SQL> edit Wrote file afiedt.buf 1 select * 2 from R1, R2, R3, R4, R5 3 where 4 R1.B=51 and 5 R1.B=R2.B and R2.B=R3.B and 6* R3.B=R4.B and R4.B=R5.B SQL> /
When I did this for each of experiments 1-7, I got 100,000 rows returned. Oracle took in each case about twenty minutes. So which was the better query? My guess is that the actual time was dominated by the time to display the results to the screen. I noticed for each query a lag of 2-3 seconds before the first result was returned. Measuring this more accurately would tell us which plan was better. Our accounts on Oracle 8 don't allow us to use TKPROF or even do: alter system set timed_statistics=true; so it is a little hard to time things from the SQLPLUS prompt. Another way to do this is I suppose to write a little Java program and time that. This, however, was beyond the scope of what I intended for the homework. In any event, the main interesting thing about all these experiments, is that Oracle seems to implicitly swallow selection operations into the table accesses at the leaves. This is what experiments 8 and 9 illustrate. The optimizer is not easily fooled in doing this as Experiment 3 illustrates. Finally, Oracle does seem to provide good facilities for controlling join order and and join type and these can be controlled by the use of hints as done above in Experiment 4 and 5.