db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Mamta Satoor <msat...@gmail.com>
Subject Re: [PATCH] (DERBY-251) DISTINCT query is returning duplicate rows
Date Thu, 12 May 2005 03:29:06 GMT
Thanks for committing the patch. Also, the tests ran fine with no
failure with the patch.

Mamta

On 5/11/05, Satheesh Bandaram <satheesh@sourcery.org> wrote:
> Submitted this patch. Thanks for addressing the review comments quickly.
> 
> Satheesh
> 
> Sending       
> java\engine\org\apache\derby\impl\sql\compile\FromList.java
> Sending       
> java\testing\org\apache\derbyTesting\functionTests\master\distinctElimination.out
> Sending       
> java\testing\org\apache\derbyTesting\functionTests\tests\lang\distinctElimination.sql
> Transmitting file data ...
> Committed revision 169735.
> 
> Mamta Satoor wrote:
> 
> 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
> <klebanoff-derby@sbcglobal.net> wrote:
 
> 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" <> 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) &&
 ((ColumnReference) left).getTableNumber()
> ==
existsTableNumber)
> {

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

predicatesTemp.removeElementAt(predicatesTempIndex);
 break;
 }

I have
> tried it out and it seems to work.

Jack Klebanoff

Mamta Satoor wrote:

 
> 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" <> 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


 
> >
 
> ________________________________
> 
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 < 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" <> 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
> >= 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] && tableColMap[i][index].get(0)) 
+ if (!oneRow[i] &&
> 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" 
+<> 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" <> 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>
> create unique index four_c1c3 on four(c1, c3);
 0 rows
> inserted/updated/deleted
+ij> 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> --
> primary/unique
+ALTER TABLE "APP"."IDEPT" ADD CONSTRAINT "PK_IDEPT" PRIMARY
> KEY ("NO1");
+0 rows inserted/updated/deleted
 ij> insert into one values
> (1, 1, 1, 1, 1);
 1 row inserted/updated/deleted
 ij> insert into one values
> (2, 1, 1, 1, 1);
@@ -87,6 +94,16 @@
 1 row inserted/updated/deleted
 ij>
> insert into four values (3, 1, 3, 1, 1);
 1 row
> inserted/updated/deleted
+ij> insert into idept values ('Dept', 1,
> 'Department1', null, null, null, null);
+1 row inserted/updated/deleted
+ij>
> insert into idept values ('HardwareDept', 2, 'Department2', 25, 1,
> 'hardwareaset2', null);
+1 row inserted/updated/deleted
+ij> insert into
> idept values ('HardwareDept', 3, 'Department3', 25, 2, 'hardwareaset3',
> null);
+1 row inserted/updated/deleted
+ij> insert into idept values
> ('SoftwareDept', 4, 'Department4', 25, 1, null, 'softwareasset4');
+1 row
> inserted/updated/deleted
+ij> insert into idept values ('SoftwareDept', 5,
> 'Department5', 30, 4, null, 'softwareasset5');
+1 row
> inserted/updated/deleted
 ij> call
> SYSCS_UTIL.SYSCS_SET_RUNTIMESTATISTICS(1);
 0 rows
> inserted/updated/deleted
 ij> maximumdisplaywidth 20000;
@@ -143,6 +160,31
> @@
 None
 next qualifiers:
 None
+ij> --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"
> 
+<> 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> --
+--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" <>
> ALL
+(select q3."NO1" from IDEPT q3 where ( ABS(q3."REPORTTO_NO") =
> q2."NO1")));
+NO1 
+-----------
+4 
+5 
 ij> -- 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> drop table four;
 0 rows
> inserted/updated/deleted
+ij> drop table idept;
+0 rows
> inserted/updated/deleted
 ij> 
 
>

Mime
View raw message