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] Updated: (DERBY-3603) 'IN' clause ignores valid results, incorrect qualifier handling suspected
Date Fri, 11 Apr 2008 17:18:04 GMT

     [ https://issues.apache.org/jira/browse/DERBY-3603?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

A B updated DERBY-3603:
-----------------------

    Attachment: d3603_v1.patch

The fact that "oneRowRightSide" is true for the NestedLoop join does indeed appear to be important
here. Good find, Thomas!  With that in mind I did some tracing of the execution path.  My
findings are below.

The query I used for tracing is as follows:

  select account.admin_unit_id, account.account_id,
    booking.booking_id, cast (admin_unit.admin_unit_name as varchar(30))
  from spike.accounts account, spike.bookings booking,
  spike.admin_units admin_unit
  where account.account_id = booking.account_id
    and admin_unit.admin_unit_id = account.admin_unit_id
    and admin_unit.admin_unit_id in (1, 21)
    and booking.child_id = 2;

When I run this query the execution plan shows a join order of:

  (ACCOUNTS x BOOKINGS) x ADMIN_UNITS

That is, we join ACCOUNTS and BOOKINGS to get a row R, then for each row R from that join,
we join it (R) with a row from ADMIN_UNITS.  Due to the presence of the IN list the optimizer
chooses to do multi-probing on ADMIN_UNITS, which means the probe predicate that represents
"admin_unit.admin_unit_id IN (1, 21)" becomes the start and stop key.  Since we only allow
a single start/stop key for any column, the join predicate between ACCOUNTS and ADMIN_UNITS
is relegated to being a store qualifier.  This is notable for two reasons: 1) this explains
the additional qualifier seen by Bryan in the query plan, and 2) as seen below, this qualifier
is what causes the "oneRowRightSide" variable to get set to TRUE for ADMIN_UNITS.

Also note: before the change for DERBY-3061 the optimizer always sorted the join predicate
as "stronger" than the probe predicate, and thus always chose the join predicate as the start/stop
key.  That in turn meant that the probe predicate, which can only be used for probing if it
is the start/stop key, was "reverted" back to a normal IN list qualifier.  So the problem
described below did not show up.  But with DERBY-3061 the probe predicate and the join predicate
have the same "strength" and thus the optimizer is free to use either one as the start/stop
key. In this example it chooses the probe predicate.

All of that said, let's take a step back and note that the join between ACCOUNTS and BOOKINGS
returns three rows:

select account.admin_unit_id, account.account_id, booking.booking_id
 from spike.accounts account, spike.bookings booking
 where account.account_id = booking.account_id
 and booking.child_id = 2;

ADMIN_UNIT&|ACCOUNT_ID |BOOKING_ID
-----------------------------------
1          |10         |1
1          |10         |3
1          |10         |4

So now, for *each* of the above three rows we want to fetch the matching row from ADMIN_UNITS.
 So far so good.

The "oneRowRightSide" variable that Thomas mentioned comes into play because the optimizer
thinks that for every outer row, i.e. for each of the three rows shown above, we will have
at MOST one matching row from ADMIN_UNITS.  At first I thought this was incorrect--but upon
further inspection it turns out be true.  The optimizer deduced this because the predicate
refers to a primary key column, which has to be unique. So when we try to fetch a row such
that the ADMIN_UNIT_ID column of ADMIN_UNITS equals some value, we will get at most one row
back.  And since we have the join predicate as a store qualifier (mentioned above), we know
that we _will_ in fact be trying "to get a row such that the ADMIN_UNIT_ID column of ADMIN_UNITS
equals some value", where "some value" will be the ADMIN_UNIT_ID column from the intermediate
join table shown above. (Note: the intermediate join table doesn't actually exist, it's just
shown as such for discussion).

So at this point things are still working as expected.  We'll take the first row from the
intermediate join, i.e. "(1, 10, 1)", and we'll do two things.  First we'll get the "next"
probe value in the list of values.  Since the probe list is "(1, 21)", the next value is "1".
 Second, we will see if there is a row in ADMIN_UNITS such that: 

  a) the ADMIN_UNIT_ID column of the row equals the current probe
     value, which is "1", AND

  b) the ADMIN_UNIT_ID column of the row equals the ADMIN_UNIT_ID of
     the outer row, which is "(1, 10, 1)".

Since both of these conditions are true, we'll return the first row as expected.  So our result
at this point is:

ADMIN_UNIT&|ACCOUNT_ID |BOOKING_ID
-----------------------------------
1          |10         |1

Now we attempt to fetch the "next" row from ADMIN_UNITS that matches the outer row "(1, 10,
1)".  But as mentioned earlier, the NestedLoop result set that would do so has "oneRowRightSide"
set to TRUE.  This means that the NestedLoop _knows_ it will not find any more rows in ADMIN_UNITS
that satsify conditions "a" and "b" shown above.  So instead of going to the table, >>>
it just QUITS the scan <<<.  See the following in NestedLoopJoinResultSet:

        if (oneRowRightSide && returnedRowMatchingRightSide)
        {
            rightRow = null;
            returnedRowMatchingRightSide = false;
        }

So we quit the inner scan of ADMIN_UNITS, which leads us to get the next "outer" row from
the intermediate join rows shown earlier.  I.e.  we'll now set our outer row to be "(1, 10,
3)".  Then we'll execute:

        if (leftRow == null)
        {
            closeRight();
        }
        else
        {
            rowsSeenLeft++;
            openRight();
        }

"leftRow" here is the same as "outer" row, so it is "(1, 10, 3)" at this point.  Since it's
not null we'll re-open the scan on ADMIN_UNITS, per the "else" branch.  Then, similar to what
we did with the first outer row, we'll get the "next" probe value in the list of values for
ADMIN_UNITS.

But this is where the problem occurs.  When we "quit" the scan in the above IF statement we
left the MultiProbe result set in the middle of a scan.  So when we make the call to re-open
the scan, we need to RESET the probing state.  But the code in MultiProbeTableScanResultSet
does not currently do that.  More on that below.

For the current codeline we do *not* reset the probe scan, and thus the next probe value we
see is "21", from the list (1, 21).  With that we will then try to get a row from ADMIN_UNIT_ID
such that:

  a) the ADMIN_UNIT_ID column of the row equals the current probe
     value, which is >>> "21" <<<, AND

  b) the ADMIN_UNIT_ID column of the row equals the ADMIN_UNIT_ID of
     the outer row, which is "(1, 10, 3)".

But ADMIN_UNITS does not contain any rows which satisfy condition "a", so we will not return
a row. Having no row from ADMIN_UNITS, we go on to fetch the next "outer" row from the intermediate
join table, meaning we end up with "(1, 10, 4)".  So we'll use that outer row and do what
we did with the others: i.e. First we'll get the next probe value in the list of values. 
The logic in MultiProbeTableScan result set sees that we have exhaused the probe list at this
point, so *NOW* it RESETS the probing state.  After that it gets the "next" probe value, which
is the first value in the list (again), and thus we end up with a probe value of "1".  Second,
we will see if there is a row in ADMIN_UNITS such that:

  a) the ADMIN_UNIT_ID column of the row equals the current probe
     value, which is "1", AND

  b) the ADMIN_UNIT_ID column of the row equals the ADMIN_UNIT_ID of
     the outer row, which is "(1, 10, 4)".

Since both of these conditions are true, we'll return the row as expected.  So our result
at this point is:

ADMIN_UNIT&|ACCOUNT_ID |BOOKING_ID
-----------------------------------
1          |10         |1
1          |10         |4

And that's how the query ends--missing a row.

So what's going on with MultiProbeTableScanResultSet?  There are some comments in the "reopenCore()"
method of that class which explain a) why we do NOT reset the probe state in some cases, and
b) why we DO reset the probe state in others.  For reference the comment is:

     /* There are two scenarios for which we reopen this kind of scan:
      *
      *   A - The first is for join processing.  In this case we have
      * a(nother) row from some outer table and we want to reopen this
      * scan to look for rows matching the new outer row.
      *
      *   B - The second is for multi-probing.  Here we want to reopen
      * the scan on this table to look for rows matching the next value
      * in the probe list.
      *
      * If we are reopening the scan for scenario A (join processing)
      * then we need to reset our position within the probe list.
      * If we are reopening the scan for scenario B then we do *not*
      * want to reset our position within the probe list because that
      * position tells us where to find the next probe value.
      *
      * The way we tell the difference between the two scenarios is
      * by looking at our current position in the probe list (i.e. the
      * value of probeValIndex): if our current position is beyond the
      * length of the probe list then we know that we are reopening the
      * scan for scenario A.  Or put another away, we should never get
      * here for scenario B if probeValIndex is greater than or equal
      * to the length of the probe list.  The reason is that the call
      * to reopenCore() for scenario B will only ever happen when
      * moreInListVals() returns true--and in that case we know that
      * probeValIndex will be less than the length of the probeValues.
      */

This comment states one thing and assumes another. First it states (correctly) that if our
current position is beyond the length of the probe list then we must be seeing scenario A.
 It then goes on to assume (incorrectly) that if the current position is LESS than the length
of the probe list we must be seeing scenario B.  It turns out that this is *NOT* true.  The
reason it is not true is because of the "oneRowRightSide" processing described above: when
that flag is set to true we quit the scan early, meaning that the current probe position will
in fact be less than the length of the probe list.  Then we later come back with a(nother)
row from the outer table (i.e. the intermediate join table shown above) and "we want to reopen
this scan to look for rows matching the new outer row".  That means we need to reset the probe
state: but due to the incorrect assumption, we don't reset it.  The result is incorrect results
as described above.

I'm attaching a first attempt at a fix, d3603_v1.patch.  With this patch applied the repro
case correctly returns three rows.  The patch does not include a test case and I don't know
yet if it passes the regression tests.  I'm running them now but they won't complete for several
more hours.  So far the lang/subqueryFlattening test has failed with a plan diff, which may
require some investigation...

I'm still quite limited on time so if it is agreed that this is the correct fix (or at least,
the right direction), it'd be great if someone could add the test and take it to completion--esp.
if it could happen before the next 10.4 release candidate.  If no one picks it up I'll try
to get to it sometime next week, but probably not in time for the second RC...

Regardless of whether or not this writeup proves correct, many thanks again to Bryan and Thomas
for their investigation and comments.  As no one officially assigned the issue to him/herself
I spent some time investigating, as written above.  I hope I didn't step on anyone's toes
in the process.

> 'IN' clause ignores valid results, incorrect qualifier handling suspected
> -------------------------------------------------------------------------
>
>                 Key: DERBY-3603
>                 URL: https://issues.apache.org/jira/browse/DERBY-3603
>             Project: Derby
>          Issue Type: Bug
>          Components: SQL
>    Affects Versions: 10.3.2.1, 10.4.1.1
>            Reporter: David Butterworth
>         Attachments: d3603_v1.patch, derbydb.jar, derbydb.tar.bz2
>
>
> Derbys' 'IN' clause is returning different results depending on which side of a joined
table
> I am doing my 'IN' comparison against. This only occurs when the number of items within
the 'IN' clause is greater then 1.
> This behaviour was also confirmed by Bryan Pendleton in this thread:
> http://mail-archives.apache.org/mod_mbox/db-derby-user/200804.mbox/%3c47FA5974.2060705@amberpoint.com%3e
> Using the test database attatched the following 2 queries produce the issue:
> ij>  select count(*) FROM spike.accounts account, spike.admin_units admin_unit,
>     spike.bookings booking
>     WHERE booking.child_id = 2 AND
>     admin_unit.admin_unit_id IN (1,21) AND
>     booking.booking_date_time_out >= 20080331000000 AND
>     booking.booking_date_time_in <= 20080406235900 AND
>     account.account_id = booking.account_id AND
>     admin_unit.admin_unit_id = account.admin_unit_id;
> 1          
> -----------
> 2          
> 1 row selected
> ij> select count(*) FROM spike.accounts account, spike.admin_units admin_unit,
>     spike.bookings booking
>     WHERE booking.child_id = 2 AND
>     account.admin_unit_id IN (1,21) AND
>     booking.booking_date_time_out >= 20080331000000 AND
>     booking.booking_date_time_in <= 20080406235900 AND
>     account.account_id = booking.account_id AND
>     admin_unit.admin_unit_id = account.admin_unit_id;
> 1          
> -----------
> 3          
> 1 row selected
> ij> 
> The only difference between the 2 statements is which side of a join the 'IN' clause
is matched against.
> Bryan performed some initial testing and stated the following:
> --------------------- SNIP ------------------------
> Interestingly, although the actual results do NOT contain any values
> for admin_unit_id = 21, if I change the query to:
>     admin_unit.admin_unit_id IN (1)
> or
>     account.admin_unit_id IN (1)
> then the problem disappears -- I get 3 rows for both queries.
> I also ran query plans for both the queries (in the IN (1,21) case)
> and have pasted the (simplified) query plans at the end of this message.
> I notice that in the case where the query gives 2 rows, which is
> when we specify admin_unit.admin_unit_id in (1,21), the admin_unit_id
> index scan output in the query plan contains:
>            qualifiers:
> Column[0][0] Id: 0
> Operator: =
> Ordered nulls: false
> Unknown return value: false
> Negate comparison result: false
> However, in the case where the query gives 3 rows, which is
> when we specify account.admin_unit_id in (1,21), the admin_unit_id
> index scan output in the query plan contains:
>            qualifiers:
> None
> I think it is the presence/absence of this qualifier on the query
> scan which is causing the different results in the query, as in
> the first case we see:
>            Number of rows qualified=2
>            Number of rows visited=3
> but in the second case we see:
>            Number of rows qualified=3
>            Number of rows visited=3
> I definitely don't have any explanation for why you are getting
> this odd behavior; it certainly seems like a bug to me.
> -------------END SNIP -----------------------

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