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: [jira] Created: (DERBY-251) DISTINCT query is returning duplicate rows
Date Wed, 11 May 2005 15:15:19 GMT
Hi Satheesh,

Here is the patch built on the latest codeline (quite a bit of changes
went into the codeline since the time I first submitted the patch last
week. Which is great for Derby!!!)

As for the fix, this is the place where we decide if distinct can be
eliminated abd the code was looking at the wrong predicates to
determine that. But, I have to admit that I have only fixed couple of
optimizer bugs so far in my work with Cloudscape and Derby and hence
would appreciate watchful eyes from reviewers on this patch.

Thanks,
Mamta

On 5/11/05, Satheesh Bandaram <satheesh@sourcery.org> wrote:
> It seems the patch is not built on latest codebase, so I couldn't apply this
> patch. Would it be possible to send updated patch based on latest code?
> 
> I looked at the patch anyway and wonder if we are only fixing a narrow case
> where we are applying DISTINCT elimination logic incorrectly. I suspect
> there may be a few more related cases that the fix might be missing, but
> this could be just my not understanding the patch yet. :-)    I will look at
> this again once updated patch is available.
> 
> Satheesh
> 
> 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


On 4/29/05, Mamta A. Satoor
> (JIRA) <derby-dev@db.apache.org> wrote:
 
> DISTINCT query is returning duplicate
> rows
------------------------------------------

 Key:
> DERBY-251
 URL:
> http://issues.apache.org/jira/browse/DERBY-251
 Project:
> Derby
 Type: Bug
 Components: SQL
 Versions: 10.1.0.0
 Reporter: Mamta A.
> Satoor
Assigned to: Mamta A. Satoor

Following query on a table with primary
> key returns duplicate rows
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") ) ) ;

The sql script to create the table and
> load data into it is as follows
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 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');

The problem appears to be in
> org.apache.derby.impl.sql.compile.FromList.returnsAtMostSingleRow()
> method. This method along with other things tries to determine if the
> DISTINCT can be dropped without causing duplicate rows. For the query in
> question, this method decides that DISTINCT is not necessary which I think
> is incorrect.

If the table above is created with no primary key, the
> DISTINCT query does not return duplicate rows. That is because one of the
> several criterias for dropping DISTINCT is that there should be a unique
> index on the columns in the where clause.

--
This message is automatically
> generated by JIRA.
-
If you think it was sent incorrectly contact one of the
> administrators:
> http://issues.apache.org/jira/secure/Administrators.jspa
-
For
> more information on JIRA, see:
> http://www.atlassian.com/software/jira

 
> >
 
> ________________________________
> 
Index:
> java/engine/org/apache/derby/impl/sql/compile/FromList.java
===================================================================
---
> java/engine/org/apache/derby/impl/sql/compile/FromList.java
> (revision 165681)
+++
> 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,89 @@
 {
 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")))
+ //
+ //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
+ //( q3."REPORTTO_NO" = q2."NO1" and q3."NO1"
> = q1."NO1") ) ) ;
+ //
+ //For the optimized query above, Derby generates
> following predicates.
+ //q3.reportto_no = q2.no1
+ //q2.discrim_dept =
> 'HardwareDept'
+ //q1.descrim_dept = 'SoftwareDept'
+ //q1.no1 = q3.no1
+
> //The predicate 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;
+ }
+
+
> 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;
+ }
+ }
+ }
+
> }
 }
 
 /* Build an array of tableNumbers from this query block.
@@ -1245,7
> +1335,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 +1388,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 165681)
+++
> 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,18 @@
 -- 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") ) ) ;
+
 -- 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 +193,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 165681)
+++
> 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,21
> @@
 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> -- 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 +2351,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