db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "A B (JIRA)" <j...@apache.org>
Subject [jira] Issue Comment Edited: (DERBY-3301) Incorrect result from query with nested EXIST
Date Tue, 22 Jan 2008 17:40:34 GMT

    [ https://issues.apache.org/jira/browse/DERBY-3301?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12561383#action_12561383
] 

army edited comment on DERBY-3301 at 1/22/08 9:39 AM:
-----------------------------------------------------

> Even though the diff works, the condition for skipping flattening should be relaxed
> to only apply to EXISTS subqueries in a WHERE clause

I think the condition may need to be narrowed down even further: EXISTS
subqueries _are_ allowed to be flattened from a WHERE clause _if_ that 
subquery's WHERE clause does not itself contain another subquery.  As an 
example, take a look at the last query on the doc page mentioned above,
namely:

  SELECT t1.* FROM t1, t2
  WHERE EXISTS (SELECT * FROM t3 WHERE t1.c1 = t3.c1)

    gets flattened into

  SELECT t1.* FROM t1, t2, t3 WHERE t1.c1 = t3.c1

If changes are made to completely avoid flattening of EXISTS subqueries in 
WHERE clauses, then the above query will *not* be flattened into an exists join,
even though it's perfectly valid to perform flattening in that case.  With the approach 
that you've outlined the exists join optimization as a whole will be disabled (I think?).
 
I think that has the potential to cause a performance regression for users whose 
queries benefit from the EXISTS join optimization today.

A similar discussion was held for DERBY-3231 and in that case a decision was 
made to deliberately remove an optimization for the sake of correctness.  But the 
use cases affected by that particular optimization were (most likely) few and far
between.  With this issue, though, I think removing EXISTS subquery flattening 
across the board will affect far more users, so I worry about committing such a fix.

The patch as posted does not apply to the current trunk, but from what I can tell, if 
you run a query like the one mentioned in the documentation, ex.:

create table t1 (c1 int, c2 int, c3 int);
create table t2 (i int, j int);
create table t3 (c1 int, vc varchar(10));

insert into t1 values (1, -1, 1), (3, -3, 9), (2, -2, 4);
insert into t2 values (2, 4);
insert into t3 values (1, 'one'), (3, 'three');

select t1.* from t1, t2 where exists (select * from t3 where t1.c1 = t3.c1);

I think derby-3301-1.diff will cause the SELECT to skip flattening of the EXISTS
subquery.  Is that correct?

The core problem for this issue appears to be the specific case where we have a
subquery SQ1 that appears in the whereClause of *another* subquery SQ0.  In that
case disabling the flattening of SQ0 would be appropriate--as the documentation
states.  But if subquery SQ1 appears in the whereClause of an *OUTER* query--as
shown above--I don't think we should disable flattening altogether.

If at all possible, I think it'd be better to fix the flattening condition for the specific
situation of nested subqueries than to completely disable WHERE clause flattening
for EXISTS subqueries.

Or put differently: if the documentation is correct, the _intent_ is to skip flattening of
an EXISTS subquery that has predicates which in turn contain other subqueries.
But the current code does not correctly implement that intent.  So I think it'd be
good to figure out _why_ the current code is wrong for the case of nested 
subqueries, and then try to make a change that addresses that specific problem.

On a slightly different note, have you had a chance to run the regression suites
with this change?  I'm curious to know if any of the existing tests actually test
for EXISTS join flattening--and if so, do those tests still pass with the proposed
change?

      was (Author: army):
    > Even though the diff works, the condition for skipping flattening should be relaxed
> to only apply to EXISTS subqueries in a WHERE clause

I think the condition may need to be narrowed down even further: EXISTS subqueries
_are_ allowed to be flattened from a WHERE clause _if_ the WHERE clause is not
itself part of another subquery.  As an example, take a look at the last query on the
doc page mentioned above, namely:

  SELECT t1.* FROM t1, t2
  WHERE EXISTS (SELECT * FROM t3 WHERE t1.c1 = t3.c1)

    gets flattened into

  SELECT t1.* FROM t1, t2, t3 WHERE t1.c1 = t3.c1

If changes are made to completely avoid flattening of EXISTS subqueries in WHERE
clauses, then the above query will *not* be flattened into an exists join, even though
it's perfectly valid to perform flattening in that case.  With the approach that you've
outlined the exists join optimization as a whole will be disabled (I think?).  I think that
has the potential to cause a performance regression for users whose queries benefit
from the EXISTS join optimization today.

A similar discussion was held for DERBY-3231 and in that case a decision was made
to deliberately remove an optimization for the sake of correctness.  But the use cases
affected by that particular optimization were (most likely) few and far between.  With
this issue, though, I think removing EXISTS subquery flattening across the board will
affect far more users, so I worry about committing such a fix.

The patch as posted does not apply to the current trunk, but from what I can tell, if you
run a query like the one mentioned in the documentation, ex.:

create table t1 (c1 int, c2 int, c3 int);
create table t2 (i int, j int);
create table t3 (c1 int, vc varchar(10));

insert into t1 values (1, -1, 1), (3, -3, 9), (2, -2, 4);
insert into t2 values (2, 4);
insert into t3 values (1, 'one'), (3, 'three');

select t1.* from t1, t2 where exists (select * from t3 where t1.c1 = t3.c1);

I think derby-3301-1.diff will cause the SELECT to skip flattening of the EXISTS
subquery.  Is that correct?

The core problem for this issue appears to be the specific case where we have a
subquery SQ1 that appears in the whereClause of *another* subquery SQ0.  In that
case disabling the flattening of SQ1 would be appropriate--as the documentation
states.  But if subquery SQ1 appears in the whereClause of an *OUTER* query--as
shown above--I don't think we should disable flattening altogether.

If at all possible, I think it'd be better to fix the flattening condition for the specific
situation of nested subqueries than to completely disable WHERE clause flattening
for EXISTS subqueries.

Or put differently: if the documentation is correct, the _intent_ is to skip flattening of
an EXISTS subquery which is itself part of another subquery.  But the current code
does not correctly implement that intent.  So I think it'd be good to figure out _why_
the current code is wrong for the case of nested subqueries, and then try to make
a change that addresses that specific problem.

On a slightly different note, have you had a chance to run the regression suites
with this change?  I'm curious to know if any of the existing tests actually test
for EXISTS join flattening--and if so, do those tests still pass with the proposed
change?
  
> Incorrect result from query with nested EXIST
> ---------------------------------------------
>
>                 Key: DERBY-3301
>                 URL: https://issues.apache.org/jira/browse/DERBY-3301
>             Project: Derby
>          Issue Type: Bug
>          Components: SQL
>    Affects Versions: 10.1.3.1, 10.2.1.6, 10.3.2.1
>            Reporter: Craig Russell
>         Attachments: d3301-queryplan.log, derby-3301-1.diff, derby-3301-1.stat, derby-3301.sql
>
>
> Derby returns unexpected results from a query with embedded EXIST clauses. The query
SQL is generated by the JPOX jdo implementation and is supposed to return all of the PERSONS
and PROJECTS where there is an entry in the join table. This query works as expected when
using MySQL.
> Here's the query:
> SELECT UNBOUND_E.PERSONID, UNBOUND_P.PROJID 
> FROM applicationidentity0.DEPARTMENTS THIS, 
>      applicationidentity0.PERSONS UNBOUND_E, 
>      applicationidentity0.PROJECTS UNBOUND_P 
> WHERE EXISTS ( 
>     SELECT 1 FROM applicationidentity0.PERSONS THIS_EMPLOYEES_E 
>     WHERE EXISTS ( 
>         SELECT 1 FROM applicationidentity0.PROJECT_MEMBER THIS_EMPLOYEES_E_PROJECTS_P

>         WHERE THIS_EMPLOYEES_E_PROJECTS_P."MEMBER" = THIS_EMPLOYEES_E.PERSONID 
>         AND THIS_EMPLOYEES_E_PROJECTS_P."MEMBER" = THIS_EMPLOYEES_E.PERSONID 
>         AND THIS_EMPLOYEES_E.DEPARTMENT = THIS.ID 
>         AND THIS_EMPLOYEES_E.DEPARTMENT = THIS.ID 
>         AND UNBOUND_P.PROJID = THIS_EMPLOYEES_E_PROJECTS_P.PROJID 
>         AND UNBOUND_E.PERSONID = THIS_EMPLOYEES_E.PERSONID) 
>     );
> PERSONID   |PROJID     
> -----------------------
> 3          |1          
> 5          |3          
> 4          |3          
> 2          |1          
> 1          |1          
> 5 rows selected
> I'm expecting 7 rows to be returned here, one row for each row in the join table. 
> Here's the schema:
> CREATE TABLE departments (
>     ID INTEGER NOT NULL,
>     NAME VARCHAR(32) NOT NULL,
>     EMP_OF_THE_MONTH INTEGER,
>     COMPANYID INTEGER,
>     DISCRIMINATOR VARCHAR(255),
>     CONSTRAINT DEPTS_COMP_FK FOREIGN KEY (COMPANYID) REFERENCES companies,
>     CONSTRAINT DEPTS_PK PRIMARY KEY (ID)
> );
> CREATE TABLE persons (
>     PERSONID INTEGER NOT NULL,
>     FIRSTNAME VARCHAR(32) NOT NULL,
>     LASTNAME VARCHAR(32) NOT NULL,
>     MIDDLENAME VARCHAR(32),
>     BIRTHDATE TIMESTAMP NOT NULL,
>     ADDRID INTEGER,
>     STREET VARCHAR(64),
>     CITY VARCHAR(64),
>     STATE CHAR(2),
>     ZIPCODE CHAR(5),
>     COUNTRY VARCHAR(64),
>     HIREDATE TIMESTAMP,
>     WEEKLYHOURS REAL,
>     DEPARTMENT INTEGER,
>     FUNDINGDEPT INTEGER,
>     MANAGER INTEGER,
>     MENTOR INTEGER,
>     HRADVISOR INTEGER,
>     SALARY REAL,
>     WAGE REAL,
>     DISCRIMINATOR varchar(255) NOT NULL,
>     CONSTRAINT PERS_DEPT_FK FOREIGN KEY (DEPARTMENT) REFERENCES departments,
>     CONSTRAINT PERS_FUNDDEPT_FK FOREIGN KEY (FUNDINGDEPT) REFERENCES departments,
>     CONSTRAINT PERS_MANAGER_FK FOREIGN KEY (MANAGER) REFERENCES persons,
>     CONSTRAINT PERS_MENTOR_FK FOREIGN KEY (MENTOR) REFERENCES persons,
>     CONSTRAINT PERS_HRADVISOR_FK FOREIGN KEY (HRADVISOR) REFERENCES persons,
>     CONSTRAINT EMPS_PK PRIMARY KEY (PERSONID)
> );
> CREATE TABLE projects (
>     PROJID INTEGER NOT NULL,
>     NAME VARCHAR(32) NOT NULL,
>     BUDGET DECIMAL(11,2) NOT NULL,
>     DISCRIMINATOR VARCHAR(255),
>     CONSTRAINT PROJS_PK PRIMARY KEY (PROJID)
> );
> CREATE TABLE project_member (
>     PROJID INTEGER REFERENCES projects NOT NULL,
>     MEMBER INTEGER REFERENCES persons NOT NULL
> );
> ij> connect 'jdbc:derby:/Users/clr/apache/jdo/trunk/tck2/target/database/derby/jdotckdb';
> ij> set schema applicationidentity0;
> 0 rows inserted/updated/deleted
> ij> select * from persons;
> PERSONID   |FIRSTNAME                       |LASTNAME                        |MIDDLENAME
                     |BIRTHDATE                 |ADDRID     |STREET                      
                                   |CITY                                                 
          |STA&|ZIPC&|COUNTRY                                                    
    |HIREDATE                  |WEEKLYHOURS  |DEPARTMENT |FUNDINGDEPT|MANAGER    |MENTOR 
   |HRADVISOR  |SALARY       |WAGE         |DISCRIMINATOR                                
                                                                                  
> -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 1          |emp1First                       |emp1Last                        |emp1Middle
                     |1970-06-09 21:00:00.0     |NULL       |NULL                        
                                   |NULL                                                 
          |NULL|NULL |NULL                                                            |1998-12-31
21:00:00.0     |40.0         |NULL       |NULL       |NULL       |NULL       |NULL       |20000.0
     |NULL         |org.apache.jdo.tck.pc.company.FullTimeEmployee                       
                                                          
> 2          |emp2First                       |emp2Last                        |emp2Middle
                     |1975-12-21 21:00:00.0     |NULL       |NULL                        
                                   |NULL                                                 
          |NULL|NULL |NULL                                                            |2003-06-30
21:00:00.0     |40.0         |NULL       |NULL       |NULL       |NULL       |NULL       |10000.0
     |NULL         |org.apache.jdo.tck.pc.company.FullTimeEmployee                       
                                                          
> 3          |emp3First                       |emp3Last                        |emp3Middle
                     |1972-09-04 21:00:00.0     |NULL       |NULL                        
                                   |NULL                                                 
          |NULL|NULL |NULL                                                            |2002-08-14
21:00:00.0     |19.0         |NULL       |NULL       |NULL       |NULL       |NULL       |NULL
        |15.0         |org.apache.jdo.tck.pc.company.PartTimeEmployee                    
                                                             
> 4          |emp4First                       |emp4Last                        |emp4Middle
                     |1973-09-05 21:00:00.0     |NULL       |NULL                        
                                   |NULL                                                 
          |NULL|NULL |NULL                                                            |2001-04-14
21:00:00.0     |0.0          |NULL       |NULL       |NULL       |NULL       |NULL       |NULL
        |13.0         |org.apache.jdo.tck.pc.company.PartTimeEmployee                    
                                                             
> 5          |emp5First                       |emp5Last                        |emp5Middle
                     |1962-07-04 21:00:00.0     |NULL       |NULL                        
                                   |NULL                                                 
          |NULL|NULL |NULL                                                            |1998-08-14
21:00:00.0     |0.0          |NULL       |NULL       |NULL       |NULL       |NULL       |45000.0
     |NULL         |org.apache.jdo.tck.pc.company.FullTimeEmployee                       
                                                          
> 5 rows selected
> ij> select * from projects;
> PROJID     |NAME                            |BUDGET       |DISCRIMINATOR            
                                                                                         
            
> -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 1          |orange                          |2500000.99   |org.apache.jdo.tck.pc.company.Project
                                                                                         

> 2          |blue                            |50000.00     |org.apache.jdo.tck.pc.company.Project
                                                                                         

> 3          |green                           |2000.99      |org.apache.jdo.tck.pc.company.Project
                                                                                         

> 3 rows selected
> ij> select * from project_member;
> PROJID     |MEMBER     
> -----------------------
> 2          |3          
> 1          |3          
> 2          |2          
> 3          |5          
> 3          |4          
> 1          |2          
> 1          |1          
> 7 rows selected

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message