Author: mikem
Date: Mon Aug 10 23:57:21 2009
New Revision: 802962
URL: http://svn.apache.org/viewvc?rev=802962&view=rev
Log:
DERBY-4331 : Join returns results in wrong order
backporting fix (#801481) from trunk to 10.2 branch.
Fixes a number of sort avoidance bugs that were introduced by the fix
for DERBY-3926. This check in backs out the equi-join part of the DERBY-3926.
The changes for this were isolated and were the only changes to
FromBaseTable.java. Backing out only this part of the 3926 checkin fixes new
problems identified in DERBY-4331, and continues to fix the problem queries in
DERBY-3926. Knowledge of equijoin is no longer used as a factor for
sort avoidance.
Also included is an update to the wisconsin tests. A number of diffs
resulted from different join order to maintain a sort avoidance plan. 2
queries identified in DERBY-4339 no longer use sort avoidance.
Test cases in the junit OrderByAndSortAvoidance test are not backported due
to limited junit support in the 10.2 branch.
The wisconsin.out changes were not a simple backport as 10.1 does not have
forced query plan hints, so the wisconsin.out change was hand done for the
10.1 line.
Modified:
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromBaseTable.java
db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/wisconsin.out
db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/wisc_setup.sql
Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromBaseTable.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromBaseTable.java?rev=802962&r1=802961&r2=802962&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromBaseTable.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromBaseTable.java Mon Aug 10 23:57:21 2009
@@ -465,13 +465,6 @@
for (int i = 0; i < baseColumnPositions.length; i++)
{
- //Check if the order by column has equijoin on another
- //column which is already identified as an ordered column
- if (doesOrderByColumnHaveEquiJoin(
- irg, predList, rowOrdering))
- rowOrdering.columnAlwaysOrdered(this,
- baseColumnPositions[i]);
-
/*
** Don't add the column to the ordering if it's already
** an ordered column. This can happen in the following
@@ -4240,86 +4233,6 @@
return true;
}
- //Check if the columns in the index have an equijoin on them
- //with other already ordered columns from the other optimizables. This
- //is done by going through the columns in the index and checking the
- //predicate list for equijoins on the index columns.
- private boolean doesOrderByColumnHaveEquiJoin(IndexRowGenerator irg,
- OptimizablePredicateList predList, RowOrdering ro)
- throws StandardException
- {
- if (predList == null)
- {
- return false;
- }
-
- // is this a unique index.
- if (! irg.isUnique())
- {
- return false;
- }
-
- PredicateList restrictionList = (PredicateList) predList;
-
- int[] baseColumnPositions = irg.baseColumnPositions();
-
- for (int index = 0; index < baseColumnPositions.length; index++)
- {
- // get the column number at this position
- int curCol = baseColumnPositions[index];
-
- //Check if this column from the index has an equi join predicate
- //on them.
- int j = restrictionList.hasEqualityPredicateOnOrderedColumn(
- this, curCol, true);
- if (j == -1)
- return false;
-
- //We have found a predicate which has an equi join involving the
- //index column. Now ensure that the equi join is with a column
- //which is already identified as always ordered.
- Predicate predicate;
- predicate = (Predicate) restrictionList.elementAt(j);
- ValueNode vn = predicate.getAndNode().getLeftOperand();
- ColumnReference cr;
- if (vn instanceof BinaryRelationalOperatorNode)
- {
- BinaryRelationalOperatorNode bon =
- (BinaryRelationalOperatorNode) vn;
- cr = null;
- if (bon.columnOnOneSide(this) ==
- BinaryRelationalOperatorNode.LEFT)
- {
- //If the index column is on left side, then look for the
- //operand on the other side to see if it is of type
- //ColumnReference. If it is, then check if that column
- //is identified as always ordered
- if (bon.getRightOperand() instanceof ColumnReference)
- cr = (ColumnReference)bon.getRightOperand();
- } else
- {
- //If the index column is on right side, then look for the
- //operand on the other side to see if it is of type
- //ColumnReference. If it is, then check if that column
- //is identified as always ordered
- if (bon.getLeftOperand() instanceof ColumnReference)
- cr = (ColumnReference)bon.getLeftOperand();
- }
- if (cr!=null)
- {
- //We have found that the index column is involved in an
- //equijoin with another column. Now check if that other
- //column is always ordered
- if (ro.orderedOnColumn(1, cr.getTableNumber(),
- cr.getColumnNumber()))
- return true;
- }
- }
- }
-
- return false;
- }
-
/**
* Is this a one-row result set with the given conglomerate descriptor?
*/
Modified: db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/wisconsin.out
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/wisconsin.out?rev=802962&r1=802961&r2=802962&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/wisconsin.out (original)
+++ db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/wisconsin.out Mon Aug 10 23:57:21 2009
@@ -21812,101 +21812,88 @@
Begin Execution Timestamp : null
End Execution Timestamp : null
Statement Execution Plan Text:
-Project-Restrict ResultSet (6):
+Hash Exists Join ResultSet:
<filtered number of opens>
-<filtered rows seen>
+<filtered rows seen from the left>
+<filtered rows seen from the right>
Rows filtered = 0
-restriction = false
-projection = true
+<filtered rows returned>
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- restriction time (milliseconds) = 0
- projection time (milliseconds) = 0
-Source result set:
- Hash Exists Join ResultSet:
+Left result set:
+ Index Row to Base Row ResultSet for TENKTUP1:
<filtered number of opens>
- <filtered rows seen from the left>
- <filtered rows seen from the right>
- Rows filtered = 0
- <filtered rows returned>
+ <filtered rows seen>
+ Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Left result set:
- Index Row to Base Row ResultSet for TENKTUP2:
+ Index Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
<filtered number of opens>
<filtered rows seen>
- Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ Rows filtered = 0
+ Fetch Size = 1
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Index Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
- <filtered number of opens>
- <filtered rows seen>
- Rows filtered = 0
- Fetch Size = 1
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- scan information:
- Bit set of columns fetched=All
- Number of columns fetched=2
- Number of deleted rows visited=0
- <filtered number of pages visited>
- <filtered number of rows qualified>
- <filtered number of rows visited>
- Scan type=btree
- Tree height=2
- start position:
+ scan information:
+ Bit set of columns fetched=All
+ Number of columns fetched=2
+ Number of deleted rows visited=0
+ <filtered number of pages visited>
+ <filtered number of rows qualified>
+ <filtered number of rows visited>
+ Scan type=btree
+ Tree height=2
+ start position:
None
- stop position:
+ stop position:
>= on first 1 column(s).
Ordered null semantics on the following columns:
0
- qualifiers:
+ qualifiers:
None
- Right result set:
- Index Row to Base Row ResultSet for TENKTUP1:
+Right result set:
+ Index Row to Base Row ResultSet for TENKTUP2:
+ <filtered number of opens>
+ <filtered rows seen>
+ Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ constructor time (milliseconds) = 0
+ open time (milliseconds) = 0
+ next time (milliseconds) = 0
+ close time (milliseconds) = 0
+ Hash Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking:
<filtered number of opens>
+ Hash table size = 2500
+ Hash key is column number 0
<filtered rows seen>
- Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ Rows filtered = 0
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Hash Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share row locking:
- <filtered number of opens>
- Hash table size = 2500
- Hash key is column number 0
- <filtered rows seen>
- Rows filtered = 0
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- scan information:
- Bit set of columns fetched=All
- Number of columns fetched=2
- Number of deleted rows visited=0
- <filtered number of pages visited>
- <filtered number of rows qualified>
- <filtered number of rows visited>
- Scan type=btree
- Tree height=2
- start position:
+ scan information:
+ Bit set of columns fetched=All
+ Number of columns fetched=2
+ Number of deleted rows visited=0
+ <filtered number of pages visited>
+ <filtered number of rows qualified>
+ <filtered number of rows visited>
+ Scan type=btree
+ Tree height=2
+ start position:
None
- stop position:
+ stop position:
>= on first 1 column(s).
Ordered null semantics on the following columns:
0
- scan qualifiers:
+ scan qualifiers:
None
- next qualifiers:
+ next qualifiers:
Column[0][0] Id: 0
Operator: =
Ordered nulls: false
@@ -21944,18 +21931,146 @@
Begin Execution Timestamp : null
End Execution Timestamp : null
Statement Execution Plan Text:
-Project-Restrict ResultSet (6):
+Hash Exists Join ResultSet:
<filtered number of opens>
-<filtered rows seen>
+<filtered rows seen from the left>
+<filtered rows seen from the right>
Rows filtered = 0
-restriction = false
-projection = true
+<filtered rows returned>
+ constructor time (milliseconds) = 0
+ open time (milliseconds) = 0
+ next time (milliseconds) = 0
+ close time (milliseconds) = 0
+Left result set:
+ Index Row to Base Row ResultSet for TENKTUP1:
+ <filtered number of opens>
+ <filtered rows seen>
+ Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ constructor time (milliseconds) = 0
+ open time (milliseconds) = 0
+ next time (milliseconds) = 0
+ close time (milliseconds) = 0
+ Index Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
+ <filtered number of opens>
+ <filtered rows seen>
+ Rows filtered = 0
+ Fetch Size = 1
+ constructor time (milliseconds) = 0
+ open time (milliseconds) = 0
+ next time (milliseconds) = 0
+ close time (milliseconds) = 0
+ scan information:
+ Bit set of columns fetched=All
+ Number of columns fetched=2
+ Number of deleted rows visited=0
+ <filtered number of pages visited>
+ <filtered number of rows qualified>
+ <filtered number of rows visited>
+ Scan type=btree
+ Tree height=2
+ start position:
+ None
+ stop position:
+ >= on first 1 column(s).
+ Ordered null semantics on the following columns:
+0
+ qualifiers:
+None
+Right result set:
+ Index Row to Base Row ResultSet for TENKTUP2:
+ <filtered number of opens>
+ <filtered rows seen>
+ Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ constructor time (milliseconds) = 0
+ open time (milliseconds) = 0
+ next time (milliseconds) = 0
+ close time (milliseconds) = 0
+ Hash Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking:
+ <filtered number of opens>
+ Hash table size = 2500
+ Hash key is column number 0
+ <filtered rows seen>
+ Rows filtered = 0
+ constructor time (milliseconds) = 0
+ open time (milliseconds) = 0
+ next time (milliseconds) = 0
+ close time (milliseconds) = 0
+ scan information:
+ Bit set of columns fetched=All
+ Number of columns fetched=2
+ Number of deleted rows visited=0
+ <filtered number of pages visited>
+ <filtered number of rows qualified>
+ <filtered number of rows visited>
+ Scan type=btree
+ Tree height=2
+ start position:
+ None
+ stop position:
+ >= on first 1 column(s).
+ Ordered null semantics on the following columns:
+0
+ scan qualifiers:
+None
+ next qualifiers:
+Column[0][0] Id: 0
+Operator: =
+Ordered nulls: false
+Unknown return value: false
+Negate comparison result: false
+ij> commit;
+ij> -- This time, force TENKTUP2 as the outermost join table to make sure
+-- that still no sorting is necessary. DERBY-3926
+-- DERBY-4331 backs out part of DERBY-3926, the expected plan now does not
+-- do sort avoidance.
+-- When DERBY-4339 is implemented, the following query plan should not have
+-- a sort node.
+-- The plan is forced to use TENKTUP2 as outermost
+-- join. It knows that query result is sorted on TENKTUP2.unique1, but does not
+-- recognize that because "TENKTUP1.unique1 = TENKTUP2.unique1" that query
+-- is also sorted on TENKTUP1.unique1 and could avoid a sort.
+get cursor c as
+ 'select * from --DERBY-PROPERTIES joinOrder=FIXED
+ TENKTUP2, TENKTUP1
+ where TENKTUP1.unique1 = TENKTUP2.unique1
+ and TENKTUP2.unique1 < 2500
+ order by TENKTUP1.unique1';
+ij> close c;
+ij> values SYSCS_UTIL.SYSCS_GET_RUNTIMESTATISTICS();
+1
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------
+Statement Name:
+ C
+Statement Text:
+ select * from --DERBY-PROPERTIES joinOrder=FIXED
+ TENKTUP2, TENKTUP1
+ where TENKTUP1.unique1 = TENKTUP2.unique1
+ and TENKTUP2.unique1 < 2500
+ order by TENKTUP1.unique1
+Parse Time: 0
+Bind Time: 0
+Optimize Time: 0
+Generate Time: 0
+Compile Time: 0
+Execute Time: 0
+Begin Compilation Timestamp : null
+End Compilation Timestamp : null
+Begin Execution Timestamp : null
+End Execution Timestamp : null
+Statement Execution Plan Text:
+Sort ResultSet:
+<filtered number of opens>
+Rows input = 2500
+<filtered rows returned>
+Eliminate duplicates = false
+In sorted order = false
+Sort information:
+ Number of rows input=2500
+ Number of rows output=2500
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- restriction time (milliseconds) = 0
- projection time (milliseconds) = 0
Source result set:
Hash Exists Join ResultSet:
<filtered number of opens>
@@ -21980,7 +22095,7 @@
<filtered number of opens>
<filtered rows seen>
Rows filtered = 0
- Fetch Size = 1
+ Fetch Size = 16
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
@@ -22045,11 +22160,9 @@
Unknown return value: false
Negate comparison result: false
ij> commit;
-ij> -- This time, force TENKTUP2 as the outermost join table to make sure
--- that still no sorting is necessary. DERBY-3926
+ij> -- 25% of rows from joining table
get cursor c as
- 'select * from --DERBY-PROPERTIES joinOrder=FIXED
- TENKTUP2, TENKTUP1
+ 'select * from TENKTUP1, TENKTUP2
where TENKTUP1.unique1 = TENKTUP2.unique1
and TENKTUP2.unique1 < 2500
order by TENKTUP1.unique1';
@@ -22060,8 +22173,7 @@
Statement Name:
C
Statement Text:
- select * from --DERBY-PROPERTIES joinOrder=FIXED
- TENKTUP2, TENKTUP1
+ select * from TENKTUP1, TENKTUP2
where TENKTUP1.unique1 = TENKTUP2.unique1
and TENKTUP2.unique1 < 2500
order by TENKTUP1.unique1
@@ -22087,7 +22199,7 @@
next time (milliseconds) = 0
close time (milliseconds) = 0
Left result set:
- Index Row to Base Row ResultSet for TENKTUP2:
+ Index Row to Base Row ResultSet for TENKTUP1:
<filtered number of opens>
<filtered rows seen>
Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
@@ -22095,7 +22207,7 @@
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Index Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
+ Index Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
<filtered number of opens>
<filtered rows seen>
Rows filtered = 0
@@ -22122,7 +22234,7 @@
qualifiers:
None
Right result set:
- Index Row to Base Row ResultSet for TENKTUP1:
+ Index Row to Base Row ResultSet for TENKTUP2:
<filtered number of opens>
<filtered rows seen>
Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
@@ -22130,7 +22242,7 @@
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Hash Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share row locking:
+ Hash Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking:
<filtered number of opens>
Hash table size = 2500
Hash key is column number 0
@@ -22164,11 +22276,11 @@
Unknown return value: false
Negate comparison result: false
ij> commit;
-ij> -- 25% of rows from joining table
+ij> -- 10% of rows from joining table
get cursor c as
'select * from TENKTUP1, TENKTUP2
where TENKTUP1.unique1 = TENKTUP2.unique1
- and TENKTUP2.unique1 < 2500
+ and TENKTUP2.unique1 < 1000
order by TENKTUP1.unique1';
ij> close c;
ij> values SYSCS_UTIL.SYSCS_GET_RUNTIMESTATISTICS();
@@ -22179,7 +22291,7 @@
Statement Text:
select * from TENKTUP1, TENKTUP2
where TENKTUP1.unique1 = TENKTUP2.unique1
- and TENKTUP2.unique1 < 2500
+ and TENKTUP2.unique1 < 1000
order by TENKTUP1.unique1
Parse Time: 0
Bind Time: 0
@@ -22192,230 +22304,88 @@
Begin Execution Timestamp : null
End Execution Timestamp : null
Statement Execution Plan Text:
-Project-Restrict ResultSet (6):
+Hash Exists Join ResultSet:
<filtered number of opens>
-<filtered rows seen>
+<filtered rows seen from the left>
+<filtered rows seen from the right>
Rows filtered = 0
-restriction = false
-projection = true
+<filtered rows returned>
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- restriction time (milliseconds) = 0
- projection time (milliseconds) = 0
-Source result set:
- Hash Exists Join ResultSet:
+Left result set:
+ Index Row to Base Row ResultSet for TENKTUP1:
<filtered number of opens>
- <filtered rows seen from the left>
- <filtered rows seen from the right>
- Rows filtered = 0
- <filtered rows returned>
+ <filtered rows seen>
+ Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Left result set:
- Index Row to Base Row ResultSet for TENKTUP2:
- <filtered number of opens>
- <filtered rows seen>
- Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- Index Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
- <filtered number of opens>
- <filtered rows seen>
- Rows filtered = 0
- Fetch Size = 1
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- scan information:
- Bit set of columns fetched=All
- Number of columns fetched=2
- Number of deleted rows visited=0
- <filtered number of pages visited>
- <filtered number of rows qualified>
- <filtered number of rows visited>
- Scan type=btree
- Tree height=2
- start position:
- None
- stop position:
- >= on first 1 column(s).
- Ordered null semantics on the following columns:
-0
- qualifiers:
-None
- Right result set:
- Index Row to Base Row ResultSet for TENKTUP1:
+ Index Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
<filtered number of opens>
<filtered rows seen>
- Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ Rows filtered = 0
+ Fetch Size = 1
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Hash Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share row locking:
- <filtered number of opens>
- Hash table size = 2500
- Hash key is column number 0
- <filtered rows seen>
- Rows filtered = 0
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- scan information:
- Bit set of columns fetched=All
- Number of columns fetched=2
- Number of deleted rows visited=0
- <filtered number of pages visited>
- <filtered number of rows qualified>
- <filtered number of rows visited>
- Scan type=btree
- Tree height=2
- start position:
+ scan information:
+ Bit set of columns fetched=All
+ Number of columns fetched=2
+ Number of deleted rows visited=0
+ <filtered number of pages visited>
+ <filtered number of rows qualified>
+ <filtered number of rows visited>
+ Scan type=btree
+ Tree height=2
+ start position:
None
- stop position:
+ stop position:
>= on first 1 column(s).
Ordered null semantics on the following columns:
0
- scan qualifiers:
+ qualifiers:
None
- next qualifiers:
-Column[0][0] Id: 0
-Operator: =
-Ordered nulls: false
-Unknown return value: false
-Negate comparison result: false
-ij> commit;
-ij> -- 10% of rows from joining table
-get cursor c as
- 'select * from TENKTUP1, TENKTUP2
- where TENKTUP1.unique1 = TENKTUP2.unique1
- and TENKTUP2.unique1 < 1000
- order by TENKTUP1.unique1';
-ij> close c;
-ij> values SYSCS_UTIL.SYSCS_GET_RUNTIMESTATISTICS();
-1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------
-Statement Name:
- C
-Statement Text:
- select * from TENKTUP1, TENKTUP2
- where TENKTUP1.unique1 = TENKTUP2.unique1
- and TENKTUP2.unique1 < 1000
- order by TENKTUP1.unique1
-Parse Time: 0
-Bind Time: 0
-Optimize Time: 0
-Generate Time: 0
-Compile Time: 0
-Execute Time: 0
-Begin Compilation Timestamp : null
-End Compilation Timestamp : null
-Begin Execution Timestamp : null
-End Execution Timestamp : null
-Statement Execution Plan Text:
-Project-Restrict ResultSet (6):
-<filtered number of opens>
-<filtered rows seen>
-Rows filtered = 0
-restriction = false
-projection = true
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- restriction time (milliseconds) = 0
- projection time (milliseconds) = 0
-Source result set:
- Hash Exists Join ResultSet:
+Right result set:
+ Index Row to Base Row ResultSet for TENKTUP2:
<filtered number of opens>
- <filtered rows seen from the left>
- <filtered rows seen from the right>
- Rows filtered = 0
- <filtered rows returned>
+ <filtered rows seen>
+ Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Left result set:
- Index Row to Base Row ResultSet for TENKTUP2:
- <filtered number of opens>
- <filtered rows seen>
- Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- Index Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
- <filtered number of opens>
- <filtered rows seen>
- Rows filtered = 0
- Fetch Size = 1
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- scan information:
- Bit set of columns fetched=All
- Number of columns fetched=2
- Number of deleted rows visited=0
- <filtered number of pages visited>
- <filtered number of rows qualified>
- <filtered number of rows visited>
- Scan type=btree
- Tree height=2
- start position:
- None
- stop position:
- >= on first 1 column(s).
- Ordered null semantics on the following columns:
-0
- qualifiers:
-None
- Right result set:
- Index Row to Base Row ResultSet for TENKTUP1:
+ Hash Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking:
<filtered number of opens>
+ Hash table size = 1000
+ Hash key is column number 0
<filtered rows seen>
- Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ Rows filtered = 0
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Hash Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share row locking:
- <filtered number of opens>
- Hash table size = 1000
- Hash key is column number 0
- <filtered rows seen>
- Rows filtered = 0
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- scan information:
- Bit set of columns fetched=All
- Number of columns fetched=2
- Number of deleted rows visited=0
- <filtered number of pages visited>
- <filtered number of rows qualified>
- <filtered number of rows visited>
- Scan type=btree
- Tree height=2
- start position:
+ scan information:
+ Bit set of columns fetched=All
+ Number of columns fetched=2
+ Number of deleted rows visited=0
+ <filtered number of pages visited>
+ <filtered number of rows qualified>
+ <filtered number of rows visited>
+ Scan type=btree
+ Tree height=2
+ start position:
None
- stop position:
+ stop position:
>= on first 1 column(s).
Ordered null semantics on the following columns:
0
- scan qualifiers:
+ scan qualifiers:
None
- next qualifiers:
+ next qualifiers:
Column[0][0] Id: 0
Operator: =
Ordered nulls: false
@@ -22450,101 +22420,88 @@
Begin Execution Timestamp : null
End Execution Timestamp : null
Statement Execution Plan Text:
-Project-Restrict ResultSet (6):
+Hash Exists Join ResultSet:
<filtered number of opens>
-<filtered rows seen>
+<filtered rows seen from the left>
+<filtered rows seen from the right>
Rows filtered = 0
-restriction = false
-projection = true
+<filtered rows returned>
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- restriction time (milliseconds) = 0
- projection time (milliseconds) = 0
-Source result set:
- Hash Exists Join ResultSet:
+Left result set:
+ Index Row to Base Row ResultSet for TENKTUP1:
<filtered number of opens>
- <filtered rows seen from the left>
- <filtered rows seen from the right>
- Rows filtered = 0
- <filtered rows returned>
+ <filtered rows seen>
+ Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Left result set:
- Index Row to Base Row ResultSet for TENKTUP2:
+ Index Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
<filtered number of opens>
<filtered rows seen>
- Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ Rows filtered = 0
+ Fetch Size = 1
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Index Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
- <filtered number of opens>
- <filtered rows seen>
- Rows filtered = 0
- Fetch Size = 1
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- scan information:
- Bit set of columns fetched=All
- Number of columns fetched=2
- Number of deleted rows visited=0
- <filtered number of pages visited>
- <filtered number of rows qualified>
- <filtered number of rows visited>
- Scan type=btree
- Tree height=2
- start position:
+ scan information:
+ Bit set of columns fetched=All
+ Number of columns fetched=2
+ Number of deleted rows visited=0
+ <filtered number of pages visited>
+ <filtered number of rows qualified>
+ <filtered number of rows visited>
+ Scan type=btree
+ Tree height=2
+ start position:
None
- stop position:
+ stop position:
>= on first 1 column(s).
Ordered null semantics on the following columns:
0
- qualifiers:
+ qualifiers:
None
- Right result set:
- Index Row to Base Row ResultSet for TENKTUP1:
+Right result set:
+ Index Row to Base Row ResultSet for TENKTUP2:
+ <filtered number of opens>
+ <filtered rows seen>
+ Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ constructor time (milliseconds) = 0
+ open time (milliseconds) = 0
+ next time (milliseconds) = 0
+ close time (milliseconds) = 0
+ Hash Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking:
<filtered number of opens>
+ Hash table size = 500
+ Hash key is column number 0
<filtered rows seen>
- Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ Rows filtered = 0
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Hash Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share row locking:
- <filtered number of opens>
- Hash table size = 500
- Hash key is column number 0
- <filtered rows seen>
- Rows filtered = 0
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- scan information:
- Bit set of columns fetched=All
- Number of columns fetched=2
- Number of deleted rows visited=0
- <filtered number of pages visited>
- <filtered number of rows qualified>
- <filtered number of rows visited>
- Scan type=btree
- Tree height=2
- start position:
+ scan information:
+ Bit set of columns fetched=All
+ Number of columns fetched=2
+ Number of deleted rows visited=0
+ <filtered number of pages visited>
+ <filtered number of rows qualified>
+ <filtered number of rows visited>
+ Scan type=btree
+ Tree height=2
+ start position:
None
- stop position:
+ stop position:
>= on first 1 column(s).
Ordered null semantics on the following columns:
0
- scan qualifiers:
+ scan qualifiers:
None
- next qualifiers:
+ next qualifiers:
Column[0][0] Id: 0
Operator: =
Ordered nulls: false
@@ -22579,101 +22536,88 @@
Begin Execution Timestamp : null
End Execution Timestamp : null
Statement Execution Plan Text:
-Project-Restrict ResultSet (6):
+Hash Exists Join ResultSet:
<filtered number of opens>
-<filtered rows seen>
+<filtered rows seen from the left>
+<filtered rows seen from the right>
Rows filtered = 0
-restriction = false
-projection = true
+<filtered rows returned>
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- restriction time (milliseconds) = 0
- projection time (milliseconds) = 0
-Source result set:
- Hash Exists Join ResultSet:
+Left result set:
+ Index Row to Base Row ResultSet for TENKTUP1:
<filtered number of opens>
- <filtered rows seen from the left>
- <filtered rows seen from the right>
- Rows filtered = 0
- <filtered rows returned>
+ <filtered rows seen>
+ Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Left result set:
- Index Row to Base Row ResultSet for TENKTUP2:
+ Index Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
<filtered number of opens>
<filtered rows seen>
- Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ Rows filtered = 0
+ Fetch Size = 1
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Index Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
- <filtered number of opens>
- <filtered rows seen>
- Rows filtered = 0
- Fetch Size = 1
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- scan information:
- Bit set of columns fetched=All
- Number of columns fetched=2
- Number of deleted rows visited=0
- <filtered number of pages visited>
- <filtered number of rows qualified>
- <filtered number of rows visited>
- Scan type=btree
- Tree height=2
- start position:
+ scan information:
+ Bit set of columns fetched=All
+ Number of columns fetched=2
+ Number of deleted rows visited=0
+ <filtered number of pages visited>
+ <filtered number of rows qualified>
+ <filtered number of rows visited>
+ Scan type=btree
+ Tree height=2
+ start position:
None
- stop position:
+ stop position:
>= on first 1 column(s).
Ordered null semantics on the following columns:
0
- qualifiers:
+ qualifiers:
None
- Right result set:
- Index Row to Base Row ResultSet for TENKTUP1:
+Right result set:
+ Index Row to Base Row ResultSet for TENKTUP2:
+ <filtered number of opens>
+ <filtered rows seen>
+ Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ constructor time (milliseconds) = 0
+ open time (milliseconds) = 0
+ next time (milliseconds) = 0
+ close time (milliseconds) = 0
+ Hash Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking:
<filtered number of opens>
+ Hash table size = 100
+ Hash key is column number 0
<filtered rows seen>
- Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ Rows filtered = 0
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Hash Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share row locking:
- <filtered number of opens>
- Hash table size = 100
- Hash key is column number 0
- <filtered rows seen>
- Rows filtered = 0
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- scan information:
- Bit set of columns fetched=All
- Number of columns fetched=2
- Number of deleted rows visited=0
- <filtered number of pages visited>
- <filtered number of rows qualified>
- <filtered number of rows visited>
- Scan type=btree
- Tree height=2
- start position:
+ scan information:
+ Bit set of columns fetched=All
+ Number of columns fetched=2
+ Number of deleted rows visited=0
+ <filtered number of pages visited>
+ <filtered number of rows qualified>
+ <filtered number of rows visited>
+ Scan type=btree
+ Tree height=2
+ start position:
None
- stop position:
+ stop position:
>= on first 1 column(s).
Ordered null semantics on the following columns:
0
- scan qualifiers:
+ scan qualifiers:
None
- next qualifiers:
+ next qualifiers:
Column[0][0] Id: 0
Operator: =
Ordered nulls: false
@@ -23849,6 +23793,12 @@
ij> -- Sort avoidance with joins and order by on columns in different tables
--
-- order on joining columns
+-- DERBY-4339, DERBY-4331
+-- until DERBY-4339 is implemented the following query will not do sort
+-- avoidance. The current code does not use the knowledge that
+-- TENKTUP1.unique1 = TENKTUP2.unique1 to infer that a plan that is sorted
+-- on TENKTUP1.unique1 or TENKTUP2.unique1 is also sorted correctly for an
+-- order by TENKTUP1.unique1, TENKTUP2.unique1.
get cursor c as
'select * from TENKTUP1, TENKTUP2
where TENKTUP1.unique1 = TENKTUP2.unique1
@@ -23874,85 +23824,87 @@
Begin Execution Timestamp : null
End Execution Timestamp : null
Statement Execution Plan Text:
-Nested Loop Exists Join ResultSet:
+Sort ResultSet:
<filtered number of opens>
-<filtered rows seen from the left>
-<filtered rows seen from the right>
-Rows filtered = 0
+Rows input = 10000
<filtered rows returned>
+Eliminate duplicates = false
+In sorted order = false
+Sort information:
+ Number of rows input=10000
+ Number of rows output=10000
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
-Left result set:
- Index Row to Base Row ResultSet for TENKTUP1:
+Source result set:
+ Nested Loop Exists Join ResultSet:
<filtered number of opens>
- <filtered rows seen>
- Columns accessed from heap = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
+ <filtered rows seen from the left>
+ <filtered rows seen from the right>
+ Rows filtered = 0
+ <filtered rows returned>
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- Index Scan ResultSet for TENKTUP1 using index TK1UNIQUE1 at serializable isolation level using share table locking chosen by the optimizer
+ Left result set:
+ Table Scan ResultSet for TENKTUP1 at serializable isolation level using share table locking chosen by the optimizer
<filtered number of opens>
<filtered rows seen>
Rows filtered = 0
- Fetch Size = 1
+ Fetch Size = 16
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
scan information:
- Bit set of columns fetched={1}
- Number of columns fetched=1
- Number of deleted rows visited=0
+ Bit set of columns fetched=All
+ Number of columns fetched=16
<filtered number of pages visited>
<filtered number of rows qualified>
<filtered number of rows visited>
- Scan type=btree
- Tree height=2
+ Scan type=heap
start position:
- None
- stop position:
- None
- qualifiers:
+null stop position:
+null qualifiers:
None
-Right result set:
- Index Row to Base Row ResultSet for TENKTUP2:
- <filtered number of opens>
- <filtered rows seen>
- Columns accessed from heap = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
- constructor time (milliseconds) = 0
- open time (milliseconds) = 0
- next time (milliseconds) = 0
- close time (milliseconds) = 0
- Index Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
+ Right result set:
+ Index Row to Base Row ResultSet for TENKTUP2:
<filtered number of opens>
<filtered rows seen>
- Rows filtered = 0
- Fetch Size = 1
+ Columns accessed from heap = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
constructor time (milliseconds) = 0
open time (milliseconds) = 0
next time (milliseconds) = 0
close time (milliseconds) = 0
- scan information:
- Bit set of columns fetched=All
- Number of columns fetched=2
- Number of deleted rows visited=0
- <filtered number of pages visited>
- <filtered number of rows qualified>
- <filtered number of rows visited>
- Scan type=btree
- Tree height=2
- start position:
+ Index Scan ResultSet for TENKTUP2 using index TK2UNIQUE1 at serializable isolation level using share row locking chosen by the optimizer
+ <filtered number of opens>
+ <filtered rows seen>
+ Rows filtered = 0
+ Fetch Size = 1
+ constructor time (milliseconds) = 0
+ open time (milliseconds) = 0
+ next time (milliseconds) = 0
+ close time (milliseconds) = 0
+ scan information:
+ Bit set of columns fetched=All
+ Number of columns fetched=2
+ Number of deleted rows visited=0
+ <filtered number of pages visited>
+ <filtered number of rows qualified>
+ <filtered number of rows visited>
+ Scan type=btree
+ Tree height=2
+ start position:
>= on first 1 column(s).
Ordered null semantics on the following columns:
0
- stop position:
+ stop position:
> on first 1 column(s).
Ordered null semantics on the following columns:
0
- qualifiers:
+ qualifiers:
None
ij> commit;
ij> -- order on joining columns with qualifications on non-joining columns
Modified: db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/wisc_setup.sql
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/wisc_setup.sql?rev=802962&r1=802961&r2=802962&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/wisc_setup.sql (original)
+++ db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/wisc_setup.sql Mon Aug 10 23:57:21 2009
@@ -2702,6 +2702,14 @@
-- This time, force TENKTUP2 as the outermost join table to make sure
-- that still no sorting is necessary. DERBY-3926
+-- DERBY-4331 backs out part of DERBY-3926, the expected plan now does not
+-- do sort avoidance.
+-- When DERBY-4339 is implemented, the following query plan should not have
+-- a sort node.
+-- The plan is forced to use TENKTUP2 as outermost
+-- join. It knows that query result is sorted on TENKTUP2.unique1, but does not
+-- recognize that because "TENKTUP1.unique1 = TENKTUP2.unique1" that query
+-- is also sorted on TENKTUP1.unique1 and could avoid a sort.
get cursor c as
'select * from --DERBY-PROPERTIES joinOrder=FIXED
TENKTUP2, TENKTUP1
@@ -2874,6 +2882,12 @@
-- Sort avoidance with joins and order by on columns in different tables
--
-- order on joining columns
+-- DERBY-4339, DERBY-4331
+-- until DERBY-4339 is implemented the following query will not do sort
+-- avoidance. The current code does not use the knowledge that
+-- TENKTUP1.unique1 = TENKTUP2.unique1 to infer that a plan that is sorted
+-- on TENKTUP1.unique1 or TENKTUP2.unique1 is also sorted correctly for an
+-- order by TENKTUP1.unique1, TENKTUP2.unique1.
get cursor c as
'select * from TENKTUP1, TENKTUP2
where TENKTUP1.unique1 = TENKTUP2.unique1
|