db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Satheesh Bandaram <sathe...@Sourcery.Org>
Subject Re: [PATCH] (DERBY-251) DISTINCT query is returning duplicate rows
Date Thu, 12 May 2005 00:08:03 GMT
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
  <title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
Submitted this patch. Thanks for addressing the review comments quickly.<br>
<br>
Satheesh<br>
<br>
Sending&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
java\engine\org\apache\derby\impl\sql\compile\FromList.java<br>
Sending&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
java\testing\org\apache\derbyTesting\functionTests\master\distinctElimination.out<br>
Sending&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
java\testing\org\apache\derbyTesting\functionTests\tests\lang\distinctElimination.sql<br>
Transmitting file data ...<br>
Committed revision 169735.<br>
<br>
Mamta Satoor wrote:<br>
<blockquote cite="midd9619e4a05051113014bcc4dd2@mail.gmail.com"
 type="cite">
  <pre wrap="">Hi Jack,

Appreciate you taking the time to do the review and catching the
predicate with expression. I have changed the code and also added a
test case for it. I have fired the derbyall suite on my codeline to
make sure everything else runs smoothly. Attached is the updated patch
anyways.

thanks,
Mamta

On 5/11/05, Jack Klebanoff <a class="moz-txt-link-rfc2396E" href="mailto:klebanoff-derby@sbcglobal.net">&lt;klebanoff-derby@sbcglobal.net&gt;</a>
wrote:
  </pre>
  <blockquote type="cite">
    <pre wrap="">The patch does not completely fix the problem. It does not handle the
case where the exists table column is embedded in an expression. Try the
following variation on the test select:

select  distinct  q1."NO1" from IDEPT q1, IDEPT q2
where  ( q2."DISCRIM_DEPT" = 'HardwareDept')
and  ( q1."DISCRIM_DEPT" = 'SoftwareDept')  and  ( q1."NO1" &lt;&gt; ALL
(select  q3."NO1" from IDEPT q3 where  ( ABS(q3."REPORTTO_NO") =  q2."NO1")))

Because q3."REPORTTO_NO" is inside a call to ABS the code added to
FromList.returnsAtMostSingleRow does not see it.

I would suggest using

                       JBitSet referencedTables =
and.getLeftOperand().getTablesReferenced();
                       if( referencedTables.get( existsTableNumber))
                       {

predicatesTemp.removeElementAt(predicatesTempIndex);
                           break;
                       }

instead of
                       BinaryRelationalOperatorNode beon =
(BinaryRelationalOperatorNode)
                           and.getLeftOperand();
                       ValueNode left = beon.getLeftOperand();
                       ValueNode right = beon.getRightOperand();

                       /* If left or right side of predicate refer to
exists base table,
                       then remove it */
                       if ((left instanceof ColumnReference) &amp;&amp;
                           ((ColumnReference) left).getTableNumber() ==
existsTableNumber)
                       {

predicatesTemp.removeElementAt(predicatesTempIndex);
                           break;
                       }
                       else if ((right instanceof ColumnReference) &amp;&amp;
                           ((ColumnReference) right).getTableNumber()
== existsTableNumber)
                       {

predicatesTemp.removeElementAt(predicatesTempIndex);
                           break;
                       }

I have tried it out and it seems to work.

Jack Klebanoff

Mamta Satoor wrote:

    </pre>
    <blockquote type="cite">
      <pre wrap="">Hi,

I have a patch for this optimizer bug. Basically, the issue turned out
to be the logic for DISTINCT elimination. During the optimization
phase, if a query has DISTINCT clause, then impl.sql.compile.FromList
class's returnsAtMostSingleRow() method gets called. This method
returns true if the method concludes that DISTINCT in the query is
redundant (based on a complex logic that decides that the query is
going to return distinct rows on its own without the DISTINCT clause.
The details of the current logic for DISTINCT elimination can be found
in the comments at the method level.)

For the query in question in this bug, the method returned true for
DISTINCT elimination which is wrong. The explanation is as follows.

First of all, I was able to simplify the query reported in the bug to
following query.
select  distinct  q1."NO1" from IDEPT q1, IDEPT q2
where  ( q2."DISCRIM_DEPT" = 'HardwareDept')
and  ( q1."DISCRIM_DEPT" = 'SoftwareDept')  and  ( q1."NO1" &lt;&gt; ALL
(select  q3."NO1" from IDEPT q3 where  (q3."REPORTTO_NO" =  q2."NO1")))

This query gets converted to following during optimization
select  distinct  q1."NO1" from IDEPT q1, IDEPT q2
where  ( q2."DISCRIM_DEPT" = 'HardwareDept')
and  ( q1."DISCRIM_DEPT" = 'SoftwareDept')  and  not exists (
(select  q3."NO1" from IDEPT q3 where
(  q3."REPORTTO_NO" =  q2."NO1"  and q3."NO1" = q1."NO1") ) )  ;

This optimized query has 4 predicates associated with it
q3.reportto_no = q2.no1
q2.discrim_dept = 'HardwareDept'
q1.descrim_dept = 'SoftwareDept'
q1.no1 = q3.no1

Next, on this optimized query(since it has DISTINCT clause in it), the
returnsAtMostSingleRow() method gets called. The method incorrectly
returns true indicating that DISTINCT can be eliminated. The reason
for this is that method is looking at predicates that belong to the
inside query with the exists clause (which is on table IDEPT q3) to
determine DISTINCT elimination for the outer level.

The fix is that the predicates from the exists query, (in this
particular case, q3."NO1" = q1."NO1" and q3.reportto_no = q2.no1)
should not be considered when deciding elimination of DISTINCT in the
outer query. That is what the attached patch does.

Hope this helps understand the problem and the proposed fix for it.
The files impacted by the change are as follows
svn stat
M java\engine\org\apache\derby\impl\sql\compile\FromList.java
M java\testing\org\apache\derbyTesting\functionTests\tests\lang\distinctElimination.sql
M java\testing\org\apache\derbyTesting\functionTests\master\distinctElimination.out

Please send in comments you may have. I have run the existing tests
and the patch didn't cause any failures.

thanks,
Mamta


      </pre>
    </blockquote>
  </blockquote>
  <pre wrap=""><!---->&gt;
  </pre>
  <pre wrap="">
<hr size="4" width="90%">
Index: java/engine/org/apache/derby/impl/sql/compile/FromList.java
===================================================================
--- java/engine/org/apache/derby/impl/sql/compile/FromList.java	(revision 169642)
+++ java/engine/org/apache/derby/impl/sql/compile/FromList.java	(working copy)
@@ -1040,7 +1040,7 @@
 	}
 
 	/**
-	 * Decrement (query block) level (0-based) for 
+	 * Decrement (query block) level (0-based) for
 	 * all of the tables in this from list.
 	 * This is useful when flattening a subquery.
 	 *
@@ -1069,7 +1069,7 @@
 		}
 	}
 
-	
+
 	/**
 	 * This method is used for both subquery flattening and distinct
 	 * elimination based on a uniqueness condition.  For subquery
@@ -1079,7 +1079,7 @@
 	 * any duplicates.
 	 * This is true if every table in the from list is
 	 * (a base table and the set of columns from the table that
-	 * are in equality comparisons with expressions that do not include columns 
+	 * are in equality comparisons with expressions that do not include columns
 	 * from the same table is a superset of any unique index
 	 * on the table) or an EXISTS FBT.  In addition, at least 1 of the tables
 	 * in the list has a set of columns in equality comparisons with expressions
@@ -1105,28 +1105,28 @@
 	 *		create an array of columns from the table(eqOuterCol)
 	 *		(this is used to determine that only one row will be returned
 	 *		from a join)
-	 *			
+	 *
 	 *		if the current table is the table for the result columns
 	 *			set the result columns in the eqOuterCol and tableColMap
 	 *			(if these columns are a superset of a unique index and
 	 *			all joining tables result in only one row, the
 	 *			results will be distinct)
 	 *		go through all the predicates and update tableColMap  and
-	 *		eqOuterCol with join columns and correlation variables, 
+	 *		eqOuterCol with join columns and correlation variables,
 	 *		parameters and constants
 	 *		since setting constants, correlation variables and parameters,
-	 * 		reduces the number of columns required for uniqueness in a 
+	 * 		reduces the number of columns required for uniqueness in a
 	 *		multi-column index, they are set for all the tables (if the
 	 *		table is not the result table, in this case only the column of the
      *		result table is set)
 	 *		join columns are just updated for the column in the row of the
 	 *		joining table.
-	 *		
-	 *		check if the marked columns in tableColMap are a superset of a unique 
-	 *			index		
+	 *
+	 *		check if the marked columns in tableColMap are a superset of a unique
+	 *			index
 	 *			(This means that the join will only produce 1 row when joined
 	 *			with 1 row of another table)
-	 *		check that there is a least one table for which the columns in 
+	 *		check that there is a least one table for which the columns in
 	 *			eqOuterCol(i.e. constant values) are a superset of a unique index
 	 *			(This quarantees that there will be only one row selected
 	 *			from this table).
@@ -1134,8 +1134,8 @@
 	 *	Once all tables have been evaluated, check that all the tables can be
 	 * 	joined by unique index or will have only one row
 	 *
-	 *	
 	 *
+	 *
 	 * @param rcl				If non-null, the RCL from the query block.
 	 *							If non-null for subqueries, then entry can
 	 *							be considered as part of an = comparison.
@@ -1150,8 +1150,8 @@
 	 *
 	 * @exception StandardException		Thrown on error
 	 */
-	boolean returnsAtMostSingleRow(ResultColumnList rcl, 
-								   ValueNode whereClause, 
+	boolean returnsAtMostSingleRow(ResultColumnList rcl,
+								   ValueNode whereClause,
 								   PredicateList wherePredicates,
 								   DataDictionary dd)
 		throws StandardException
@@ -1160,6 +1160,13 @@
 		int[]			tableNumbers;
 		ColumnReference	additionalCR = null;
 
+		PredicateList predicatesTemp;
+		predicatesTemp = (PredicateList) getNodeFactory().getNode(
+			C_NodeTypes.PREDICATE_LIST,	getContextManager());
+		int wherePredicatesSize = wherePredicates.size();
+		for (int index = 0; index &lt; wherePredicatesSize; index++)
+			predicatesTemp.addPredicate((Predicate)wherePredicates.elementAt(index));
+
 		/* When considering subquery flattening, we are interested
 		 * in the 1st (and only) entry in the RCL.  (The RCL will be
 		 * null if result column is not of interest for subquery flattening.)
@@ -1193,6 +1200,77 @@
 			{
 				return false;
 			}
+			FromBaseTable fbt = (FromBaseTable) prn.getChildResult();
+			//Following for loop code is to take care of Derby-251 (DISTINCT returns
+			//duplicate rows).
+			//Derby-251 returned duplicate rows because we were looking at predicates
+			//that belong to existsTable to determine DISTINCT elimination
+			//
+			//(Check method level comments to understand DISTINCT elimination rules.)
+			//
+			//For one specific example, consider the query below
+			//select  distinct  q1."NO1" from IDEPT q1, IDEPT q2
+			//where  ( q2."DISCRIM_DEPT" = 'HardwareDept')
+			//and  ( q1."DISCRIM_DEPT" = 'SoftwareDept')  and  ( q1."NO1" &lt;&gt; ALL
+			//(select  q3."NO1" from IDEPT q3 where  (q3."REPORTTO_NO" =  q2."NO1")))
+			//(select  q3."NO1" from IDEPT q3 where  ( ABS(q3."REPORTTO_NO") =  q2."NO1")))
+			//
+			//Table IDEPT in the query above has a primary key defined on column "NO1"
+			//This query gets converted to following during optimization
+			//
+			//select  distinct  q1."NO1" from IDEPT q1, IDEPT q2
+			//where  ( q2."DISCRIM_DEPT" = 'HardwareDept')
+			//and  ( q1."DISCRIM_DEPT" = 'SoftwareDept')  and  not exists (
+			//(select  q3."NO1" from IDEPT q3 where
+			//(  ( ABS(q3."REPORTTO_NO") =  q2."NO1")  and q3."NO1" = q1."NO1") ) )  ;
+			//
+			//For the optimized query above, Derby generates following predicates.
+			//ABS(q3.reportto_no) = q2.no1
+			//q2.discrim_dept = 'HardwareDept'
+			//q1.descrim_dept = 'SoftwareDept'
+			//q1.no1 = q3.no1
+			//The predicate ABS(q3."NO1") = q1."NO1" should not be considered when trying
+			//to determine if q1 in the outer query has equality comparisons. 
+			//Similarly, the predicate q3.reportto_no = q2.no1 should not be
+			//considered when trying to determine if q2 in the outer query has
+			//equality comparisons. To achieve this, predicates based on exists base
+			//table q3 (the first and the last predicate) should be removed while
+			//evaluating outer query for uniqueness.
+			//
+			if (fbt.getExistsBaseTable())
+			{
+				int existsTableNumber = fbt.getTableNumber();
+				int predicatesTempSize = predicatesTemp.size();
+				for (int predicatesTempIndex = predicatesTempSize-1;
+					predicatesTempIndex &gt;= 0; predicatesTempIndex--)
+				{
+					AndNode topAndNode = (AndNode)
+						((Predicate) predicatesTemp.elementAt(predicatesTempIndex)).getAndNode();
+
+					for (ValueNode whereWalker = topAndNode; whereWalker instanceof AndNode;
+						whereWalker = ((AndNode) whereWalker).getRightOperand())
+					{
+						// See if this is a candidate =
+						AndNode and = (AndNode) whereWalker;
+
+						//we only need to worry about equality predicates because only those
+						//predicates are considered during DISTINCT elimination.
+						if (!and.getLeftOperand().isRelationalOperator() ||
+							!(((RelationalOperator)(and.getLeftOperand())).getOperator() ==
+							RelationalOperator.EQUALS_RELOP))
+						{
+							continue;
+						}
+
+						JBitSet referencedTables = and.getLeftOperand().getTablesReferenced();
+						if (referencedTables.get(existsTableNumber))
+						{
+							predicatesTemp.removeElementAt(predicatesTempIndex);
+							break;
+						}
+					}
+				}
+			}
 		}
 
 		/* Build an array of tableNumbers from this query block.
@@ -1245,7 +1323,7 @@
 			/* Now see if there are any equality conditions
 			 * of interest in the where predicates.
 			 */
-			wherePredicates.checkTopPredicatesForEqualsConditions(
+			predicatesTemp.checkTopPredicatesForEqualsConditions(
 								tableNumber, eqOuterCols, tableNumbers,
 								tableColMap[index], resultColTable);
 
@@ -1298,7 +1376,7 @@
 							/* unique key join - exists tables already marked as 
 							 * 1 row - so don't need to look at them
 							 */
-							if (!oneRow[i] &amp;&amp; tableColMap[i][index].get(0))	
+							if (!oneRow[i] &amp;&amp; tableColMap[i][index].get(0))
 							{
 								oneRow[i] = true;
 								foundOneRow = true;
Index: java/testing/org/apache/derbyTesting/functionTests/tests/lang/distinctElimination.sql
===================================================================
--- java/testing/org/apache/derbyTesting/functionTests/tests/lang/distinctElimination.sql
(revision 169642)
+++ java/testing/org/apache/derbyTesting/functionTests/tests/lang/distinctElimination.sql
(working copy)
@@ -12,6 +12,11 @@
 create unique index three_c1 on three(c1);
 create table four(c1 int, c2 int, c3 int, c4 int, c5 int);
 create unique index four_c1c3 on four(c1, c3);
+CREATE TABLE "APP"."IDEPT" ("DISCRIM_DEPT" VARCHAR(32), "NO1" INTEGER NOT NULL, 
+"NAME" VARCHAR(50), "AUDITOR_NO" INTEGER, "REPORTTO_NO" INTEGER, "HARDWAREASSET"
+ VARCHAR(15), "SOFTWAREASSET" VARCHAR(15));
+-- primary/unique
+ALTER TABLE "APP"."IDEPT" ADD CONSTRAINT "PK_IDEPT" PRIMARY KEY ("NO1");
 
 insert into one values (1, 1, 1, 1, 1);
 insert into one values (2, 1, 1, 1, 1);
@@ -51,6 +56,12 @@
 insert into four values (3, 1, 2, 1, 1);
 insert into four values (3, 1, 3, 1, 1);
 
+insert into idept values ('Dept', 1, 'Department1', null, null, null, null);
+insert into idept values ('HardwareDept', 2, 'Department2', 25, 1, 'hardwareaset2', null);
+insert into idept values ('HardwareDept', 3, 'Department3', 25, 2, 'hardwareaset3', null);
+insert into idept values ('SoftwareDept', 4, 'Department4', 25, 1, null, 'softwareasset4');
+insert into idept values ('SoftwareDept', 5, 'Department5', 30, 4, null, 'softwareasset5');
+
 call SYSCS_UTIL.SYSCS_SET_RUNTIMESTATISTICS(1);
 maximumdisplaywidth 20000;
 
@@ -61,6 +72,24 @@
 -- Following runtime statistics output should have Distinct Scan in it
 values SYSCS_UTIL.SYSCS_GET_RUNTIMESTATISTICS();
 
+--Derby251 Distinct should not get eliminated for following query
+--because there is no equality condition on unique column of table
+--in the outside query
+select  distinct  q1."NO1",  q1."NAME",  q1."AUDITOR_NO",  
+q1."REPORTTO_NO",  q1."DISCRIM_DEPT",  q1."SOFTWAREASSET" from 
+IDEPT q1, IDEPT q2 where  ( q2."DISCRIM_DEPT" = 'HardwareDept') 
+ and  ( q1."DISCRIM_DEPT" = 'SoftwareDept')  and  ( q1."NO1" 
+&lt;&gt; ALL  ( select  q3."NO1" from IDEPT q3 where  ( ( 
+q3."DISCRIM_DEPT" = 'Dept')  or  ( q3."DISCRIM_DEPT" = 
+'HardwareDept')  or  ( q3."DISCRIM_DEPT" = 'SoftwareDept') )  
+and  ( q3."REPORTTO_NO" =  q2."NO1") ) )  ;
+--
+--Another test case of Derby251 where the exists table column is embedded in an expression.
+select  distinct  q1."NO1" from IDEPT q1, IDEPT q2
+where  ( q2."DISCRIM_DEPT" = 'HardwareDept')
+and  ( q1."DISCRIM_DEPT" = 'SoftwareDept')  and  ( q1."NO1" &lt;&gt; ALL
+(select  q3."NO1" from IDEPT q3 where  ( ABS(q3."REPORTTO_NO") =  q2."NO1")));
+
 -- result ordering is not guaranteed, but order by clause will change how
 -- distinct is executed.  So test by retrieving data into a temp table and
 -- return results ordered after making sure the query was executed as expected.
@@ -170,3 +199,4 @@
 drop table two;
 drop table three;
 drop table four;
+drop table idept;
Index: java/testing/org/apache/derbyTesting/functionTests/master/distinctElimination.out
===================================================================
--- java/testing/org/apache/derbyTesting/functionTests/master/distinctElimination.out	(revision
169642)
+++ java/testing/org/apache/derbyTesting/functionTests/master/distinctElimination.out	(working
copy)
@@ -19,6 +19,13 @@
 0 rows inserted/updated/deleted
 ij&gt; create unique index four_c1c3 on four(c1, c3);
 0 rows inserted/updated/deleted
+ij&gt; CREATE TABLE "APP"."IDEPT" ("DISCRIM_DEPT" VARCHAR(32), "NO1" INTEGER NOT NULL,

+"NAME" VARCHAR(50), "AUDITOR_NO" INTEGER, "REPORTTO_NO" INTEGER, "HARDWAREASSET"
+ VARCHAR(15), "SOFTWAREASSET" VARCHAR(15));
+0 rows inserted/updated/deleted
+ij&gt; -- primary/unique
+ALTER TABLE "APP"."IDEPT" ADD CONSTRAINT "PK_IDEPT" PRIMARY KEY ("NO1");
+0 rows inserted/updated/deleted
 ij&gt; insert into one values (1, 1, 1, 1, 1);
 1 row inserted/updated/deleted
 ij&gt; insert into one values (2, 1, 1, 1, 1);
@@ -87,6 +94,16 @@
 1 row inserted/updated/deleted
 ij&gt; insert into four values (3, 1, 3, 1, 1);
 1 row inserted/updated/deleted
+ij&gt; insert into idept values ('Dept', 1, 'Department1', null, null, null, null);
+1 row inserted/updated/deleted
+ij&gt; insert into idept values ('HardwareDept', 2, 'Department2', 25, 1, 'hardwareaset2',
null);
+1 row inserted/updated/deleted
+ij&gt; insert into idept values ('HardwareDept', 3, 'Department3', 25, 2, 'hardwareaset3',
null);
+1 row inserted/updated/deleted
+ij&gt; insert into idept values ('SoftwareDept', 4, 'Department4', 25, 1, null, 'softwareasset4');
+1 row inserted/updated/deleted
+ij&gt; insert into idept values ('SoftwareDept', 5, 'Department5', 30, 4, null, 'softwareasset5');
+1 row inserted/updated/deleted
 ij&gt; call SYSCS_UTIL.SYSCS_SET_RUNTIMESTATISTICS(1);
 0 rows inserted/updated/deleted
 ij&gt; maximumdisplaywidth 20000;
@@ -143,6 +160,31 @@
 None
 	next qualifiers:
 None
+ij&gt; --Derby251 Distinct should not get eliminated for following query
+--because there is no equality condition on unique column of table
+--in the outside query
+select  distinct  q1."NO1",  q1."NAME",  q1."AUDITOR_NO",  
+q1."REPORTTO_NO",  q1."DISCRIM_DEPT",  q1."SOFTWAREASSET" from 
+IDEPT q1, IDEPT q2 where  ( q2."DISCRIM_DEPT" = 'HardwareDept') 
+ and  ( q1."DISCRIM_DEPT" = 'SoftwareDept')  and  ( q1."NO1" 
+&lt;&gt; ALL  ( select  q3."NO1" from IDEPT q3 where  ( ( 
+q3."DISCRIM_DEPT" = 'Dept')  or  ( q3."DISCRIM_DEPT" = 
+'HardwareDept')  or  ( q3."DISCRIM_DEPT" = 'SoftwareDept') )  
+and  ( q3."REPORTTO_NO" =  q2."NO1") ) )  ;
+NO1        |NAME                                              |AUDITOR_NO |REPORTTO_NO|DISCRIM_DEPT
                   |SOFTWAREASSET  
+---------------------------------------------------------------------------------------------------------------------------------------
+4          |Department4                                       |25         |1          |SoftwareDept
                   |softwareasset4 
+5          |Department5                                       |30         |4          |SoftwareDept
                   |softwareasset5 
+ij&gt; --
+--Another test case of Derby251 where the exists table column is embedded in an expression.
+select  distinct  q1."NO1" from IDEPT q1, IDEPT q2
+where  ( q2."DISCRIM_DEPT" = 'HardwareDept')
+and  ( q1."DISCRIM_DEPT" = 'SoftwareDept')  and  ( q1."NO1" &lt;&gt; ALL
+(select  q3."NO1" from IDEPT q3 where  ( ABS(q3."REPORTTO_NO") =  q2."NO1")));
+NO1        
+-----------
+4          
+5          
 ij&gt; -- result ordering is not guaranteed, but order by clause will change how
 -- distinct is executed.  So test by retrieving data into a temp table and
 -- return results ordered after making sure the query was executed as expected.
@@ -2319,4 +2361,6 @@
 0 rows inserted/updated/deleted
 ij&gt; drop table four;
 0 rows inserted/updated/deleted
+ij&gt; drop table idept;
+0 rows inserted/updated/deleted
 ij&gt; 
  </pre>
</blockquote>
</body>
</html>


Mime
View raw message