Wrong Results: Use of decimal values in an IN-list with INTEGER left operand can lead to extra rows.

• Key: DERBY-2256
• Type: Bug
• Status: Closed
• Resolution: Fixed
• Priority: Major
• Assignee: A B
• Reporter: A B
• Component/s: SQL
• Affects Version/s: 10.0.2.0, 10.0.2.1, 10.0.2.2, 10.1.1.0, 10.1.2.1, 10.1.3.1, 10.1.3.2, 10.1.4.0, 10.2.1.6, 10.2.2.0, 10.2.2.1, 10.2.3.0, 10.3.1.4
• Fix Version/s: 10.3.1.4

Description

While trying out some code changes for DERBY-47 I was running a few test cases and happened to notice that there are a couple of cases in which Derby behaves incorrectly (that or my understanding of what should be happening here is way off).

First and most simply: the following query should return zero rows (unless I'm missing something?), but it returns one:

ij> create table t1 (i int);
0 rows inserted/updated/deleted
ij> insert into t1 values 1, 2, 3, 4, 5;
5 rows inserted/updated/deleted

-- Correct returns zero rows.
ij> select * from t1 where i in (4.23);
I
-----------

0 rows selected

-- But this one returns 1 row...
ij> select * from t1 where i in (2.8, 4.23);
I
-----------
4

1 row selected

Secondly, if the IN-list contains a non-constant value then Derby can incorrectly return rows that do not match the IN predicate. I think this is because some internal casting is happening when it shouldn't?

ij> create table t1 (i int);
0 rows inserted/updated/deleted
ij> insert into t1 values 1, 2, 3, 4, 5;
5 rows inserted/updated/deleted

-- Following values clause returns "2.80", as expected.
ij> values cast (2.8 as decimal(4, 2));
1
-------
2.80

1 row selected

-- But if we use it in an IN-list it gets cast to "2" and thus returns a match.
-- We get 2 rows when we should get NONE.
ij> select * from t1 where i in (cast (2.8 as decimal(4, 2)), 4.23);
I
-----------
2
4

2 rows selected

I confirmed that we see these results on trunk, 10.2, 10.1, and even as far back as svn #201660 for 10.0. I also ran the above statements on DB2 v8 as a sanity check to confirm that NO results were returned there.

Comments

[Yip Ng]

Another error cases:

-- ok
ij> select * from t1 where i in (4, 4.23);
I
-----------
4

-- wrong
ij> select * from t1 where i in (4.23, 4);
I
-----------

0 rows selected

[A B]

There is code in InListOperatorNode.java that creates a BETWEEN clause from an IN-list if the size of the IN list is greater than 1 and all values are constants:

if (rightOperandList.size() == 1)
{
// just use an equality predicate
}
else if ((leftOperand instanceof ColumnReference) &&
rightOperandList.containsAllConstantNodes())
{
// convert to BETWEEN.
}

As Bryan Pendleton pointed out on derby-dev, it looks like that could have something to do with why

  select * from t1 where i in (2.8, 4.23);

returns a row ("4" is between 2.8 and 4.23). It also explains why

  select * from t1 where i in (4.23);

correctly returns zero rows (it is simply treated as an equality predicate).

It's not clear to me how (or if) that explains the other error case posted by Yip above (thanks Yip!), but maybe it's related?

[Yip Ng]

I think Derby will transform this statement's IN predicate

i in (2.8, 4.23);

to the following:

i in (2.8, 4.23) AND i >= 2.8 AND i <= 4.23

The original IN predicate should still be there. So, I think perhaps the problem might have to do with row qualification in regard to integer comparison with the transformed query.

[A B]

Yip's most recent comment agrees with what Mike wrote on derby-dev:

  http://thread.gmane.org/gmane.comp.apache.db.derby.devel/35489/focus=35559

To quote Mike: "My guess would be that [...] some problem is applying the real qualifiers to integer comparisons, where for some reason that compare is different for transformed query."

[A B]

It looks like the various incorrect results reported in this Jira are all caused by one of two different but related problems.

Problem I) Compile-time comparisons.

The first problem exists in the preprocessing code of InListOperatorNode, where an IN list comprised exclusively of constant literals undergoes three potential transformations:

  0. First, if the list has a single value in it, it will be replaced by
     an equality predicate, and that's it. So an IN list such as
     "... i in (3)" will become "i = 3".
  1. Else, the list will be sorted in ascending order.
  2. Then, in the special case where the minimum and maximum values are
     the same, the IN list will be replaced with a simple equality
     predicate. So an IN list such as " ... i in (2, 2, 2)" will actually
     turn into an equality of the form "i = 2".

The problem here is that the code to sort the list, and also the code to find the min/max values, always does comparisons using the type of the left operand, as can be seen from the following comment in the code:

    /* When sorting or choosing min/max in the list, if types
     * are not an exact match, we use the left operand's type
     * as the "judge", assuming that they are compatible, as
     * also the case with DB2.
     */

But it turns out that this is *not* always the correct thing to do--and despite what the comment says, this does not appear to be what DB2 does, either (all of the queries referenced in this Jira issue return the correct results on DB2 v8).

To see why this is wrong, let's assume we have a table T1 with an integer column "I" whose rows are simply:

    I
    ----
    1
    2
    3
    4
    5

Now let's take the following query:

  select * from t1 where i in (4.23, 4);

In this case "i" is the left operand, so the left operand's type is INTEGER. Derby will then bubble-sort the IN list values using INTEGER as the "judge" type for comparisons. When doing integer comparisons with decimal values, Derby will compare with a _truncated_ version of the decimal(s), which means that we will effectively end up with something like:

  if (trunc(4.23) > 4)
    <swap "4.23" with "4">

which becomes:

  if (4 > 4)
    <swap "4.23" with "4>

Since 4 is not greater than 4, the "if" condition will return false and thus we will not swap the values; we'll just leave them as they are and consider them "sorted"--which is wrong.

If we keep going, we will then check to see if the mininum value is equal to the maximum value, and if so we'll rewrite the IN list as an equality predicate. That said, the code assumes that the values have been correctly sorted, in which case the minimum value should simply be the first value in the list. So Derby will at this point think that the minimum value is "4.23" (which is wrong).

So in pseudo-code we'll have:

  if (minVal == maxVal)
    <transform to equality>

which becomes

  if (trunc(4.23) == 4)
    <transform to equality>

which becomes

  if (4 == 4)
    <transform to equality>

As a result, we transform the IN list into a simple equality of the form "i = <minValue>". But because of the incorrect sort we still think that our minimum value is "4.23", so the query that we ultimately end up executing is:

  select * from t1 where i = 4.23

Thus the query returns no rows when it should have returned one. Notice that if the IN list values are reversed, i.e.:

  select * from t1 where i in (4, 4.23);

then all of the same (incorrect) logic will apply, except that the minimum value will be "4" instead of "4.23" (because "4" appears first in the list). Thus the query gets rewritten to:

  select * from t1 where i = 4

which returns the expected row (somewhat by accident). So this explains the behavior posted by Yip in an earlier comment.

Problem II) Execution-time comparisons.

Even if the incorrect logic described above is fixed, we will still have cases where certain queries return the wrong results. The reason is that the execution-time logic for IN lists has the same problem as the compilation-time logic: namely, Derby does all of the IN-list comparisons using the left operand's type, which is wrong. The relevant code can be found in the DataType.in() method, where we start with the following comment:

    /* Do a binary search if the list is ordered until the
     * range of values to search is 3 or less.
     *
     * NOTE: We've ensured that the IN list and the left all have
     * the same precedence at compile time. If we don't enforce
     * the same precendence then we could get the wrong result
     * when doing a binary search.
     */

Ironically enough, this comment makes reference to the problem at hand here: if we don't enforce the correct precedence when comparing values, we can get wrong results. The problem is that the "NOTE" in this comment is WRONG--despite what it says, we actually did *NOT* ensure that the IN list and the left operand had the same precedence at compile time. Even if we assume that the preprocessing logic is correct, it doesn't actually *change* the types of any of the IN-list values--so when we get to execution, the values *can* in fact have different type precedences. Because of this broken assumption, the rest of the code in DataType.in() fails in certain cases.

As an example we can use the same T1 mentioned above, but this time let our query be the following:

  select * from t1 where i in (2.8, 4.23)

Notice that the IN-list values are already in sorted order and that, when truncated, "2.8" does NOT equal "4.23"--so the incorrect preprocessing described above will (accidentally) do the correct thing. But now when we get to execution, we're going to search the IN list values for each of the values in T1(i). Since the left operand is INTEGER, all comparisons will be integer-based comparisons, meaning that they will use truncated versions of the decimal values. So we'll see something like:

  Search for "1":

    (1 == trunc(2.8)) --> (1 == 2) --> false (no match)
    (1 == trunc(4.23)) --> (1 == 4) --> false (no match)

  Search for "2":

    (2 == trunc(2.8)) --> (2 == 2) --> true (MATCH -- which is WRONG)

  Search for "3":

    (3 == trunc(2.8)) --> (3 == 2) --> false (no match)
    (3 == trunc(4.23)) --> (3 == 4) --> false (no match)

  Search for "4":

    (4 == trunc(2.8)) --> (4 == 2) --> false (no match)
    (4 == trunc(4.23)) --> (4 == 4) --> true (MATCH -- which is WRONG)

  Search for "5":

    (5 == trunc(2.8)) --> (5 == 2) --> false (no match)
    (5 == trunc(4.23)) --> (5 == 4) --> false (no match)

Thus the query will return two rows when in fact it should return NONE.

One final note here: when this issue was first created, the above query actually only returned 1 row, not two. That was because Derby used to create an additional BETWEEN predicate for the IN-list, and that predicate eliminated the row for "i == 2" (because 2 is not between 2.8 and 4.23). But the changes for DERBY-47 replaced the BETWEEN optimization with a multi-probe approach, thus further exposing (but not causing) the execution-time bug described here. This is further backed up by the fact that even before DERBY-47 the following query returned two rows, as well:

ij> select * from t1 where i in (cast (2.8 as decimal(4, 2)), 4.23);
I
-----------
2
4

2 rows selected

The reason is that the explict CAST disabled the BETWEEN optimization, thereby leading to the same situation as just outlined.

[A B]

Posting d2256_v1.patch, which is a first attempt at a patch for this issue. The general idea is to always make sure that IN-list comparisons are done with the "dominant" type when two values have different type precedences. More specifically:

  - When determining the "judge" type in InListOperatorNode.preprocess(), iterate through
    all of the values to find out what the dominant type is, and then use that as the
    "judge" for sorting. Prior to these changes we just used the type of the left operand
    as judge, but that was not correct (as mentioned in my previous comment).

    The obvious downside to this approach is that we may have to iterate through a potentially
    large list of IN values in order to determine the dominant type. I thought about leaving
    InListOpNode.preprocess() alone and adding new logic to ValueNodeList.sortInAscendingOrder()
    to account for different precedences, but it seemed to me like that wouldn't really save
    us anything and it is not as "clean" as the InListOpNode.preprocess() changes.

    Of course I am open to suggestions if anyone disagrees here.

  - At execution time (i.e. in DataType.in()), add logic to ensure that all search
    comparisons are done using the dominant type of the values being compared.

    An alternative here would have been to explicitly _cast_ the IN-list values to
    the dominant type during preprocessing, in which case we would have satisfied
    the original assumption in DataType.in() and thus no changes to that file would
    have been necessary. But in the end I think it is quite a bit more costly to
    add CAST nodes to every IN value at compile time than it is to just do a
    precedence check at execution-time (which is what d2256_v1.patch does).

    Again, I am willing to change this approach if anyone feels strongly about it.

  - Added the test cases referenced in this Jira to the lang/inbetween.sql test.

I ran derbyall and suites.All on Red Hat Linux with ibm142 and saw no new failures. I think the changes are fairly contained and my hope is that the comments are sufficient, so if anyone is available for a review, that'd be great...

[Bryan Pendleton]

Hi Army, the comments and explanation are great and they make a lot of sense.

   select * from t1 where i in (4.23, 4);

Did you consider having this query return an error? If the user provides a
floating point value for an integer column, wouldn't they prefer to have an
error message, rather than have the database quietly return zero rows?

[A B]

> Did you consider having this query return an error? If the user provides a
> floating point value for an integer column, wouldn't they prefer to have an
> error message, rather than have the database quietly return zero rows?

Well first I should point out that "quietly return[ing] zero rows" is not the correct behavior in the example you gave. That's what Derby currently does (before the patch for this issue) but that is not correct. The correct behavior is to return a single row matching the "4".

Given that, the question becomes "Did you consider having this query return an error?" And this is a great question--thank you for bringing it up.

The short answer is No, I didn't consider throwing an error--but that was just because it didn't occur to me ;) The longer and more relevant answer is that, after looking at the SQL 2003 spec for IN lists, my own reading is that we should not throw an error in the example that you mentioned. Here's why...(feel free to skip if you're not interested):

----

From SQL 2003 spec, 8.4 <in predicate> grammar shows:

  <in predicate> ::= <row value predicand> <in predicate part 2>
  <in predicate part 2> ::= [ NOT ] IN <in predicate value>
  <in value list> ::= <row value expression> [ { <comma> <row value expression> }... ]
  <in predicate value> ::=
       <table subquery>
       | <left paren> <in value list> <right paren>

Note that <in value list> in this grammar does not include parentheses. Now if we look at syntax Rule #2 in the same section, we see:

<begin quote>

  Let IVL be an <in value list>.

    ( IVL )

  is equivalent to the <table value constructor>:

    ( VALUES IVL )

<end quote>

So if our example query is:

  select * from t1 where i in (4.23, 4);

then <in value list> is simply "4.23, 4", and thus

    ( IVL ) ==> ( 4.23, 4 )

  is equivalent to the <table value constructor>:

    ( VALUES 4.23, 4 )

This particular VALUES clause is legal in Derby--i.e. we do not throw an error:

ij> values 4.23, 4;
1
---------------
4.23
4.00

2 rows selected

The next question is whether or not Derby *should* throw an error here. The specs for a VALUES clause are given in section 7.3 as "<table value constructor>" and include the following:

 Section 7.3, Syntax Rule #4:

  The row type of TVC is determined by applying Subclause 9.3, "Data types of results
  of aggregations", to the row types [of the values in the list].

If we go on to look at subclause 9.3 we see the following rule:

 Section 9.3, Syntax Rule #2:

  All of the data types in DTS shall be comparable.

In our example we have an integer column and a decimal value, and those two types are indeed comparable with each other. So we satisfy rule #2 and therefore should not throw an error here.

That said, we now go back to section 8.4 (IN predicate) and look at syntax rules #3 and #5, where we see the following:

<begin quote>

 3) Let RVC be the <row value predicand> and let IPV be the <in predicate value>.

 5) The expression

     RVC IN IPV

    is equivalent to

     RVC = ANY IPV

<end quote>

In our example RVC is the column "i" and IPV is "(4.23, 4)". So then we have:

    i IN (4.23, 4)

  is equivalent to

    i = ANY (4.23, 4)

Then if we use syntax rule #2 again, we end up with:

    i = ANY (VALUES 4.23, 4)

Putting that back into our original query we now have:

   select * from t1 where i = any (values 4.23, 4);

This latter query executes without error in Derby and returns 1 row (even before the patch for this issue is applied):

ij> select * from t1 where i = any (values 4.23, 4);
I
-----------
4

1 row selected

Since the type of the VALUES clause is decimal (section 9.3, rule #3), we are doing a comparison of an integer with a decimal. Such a comparison should not throw an error and should only return true if the values are algebraically equal. Thus the above query is correctly returning a single row--and that's what the equivalent IN list query should be doing, too.

----

Putting all of that together, my conclusion is that we should not throw an error if if the user specifies a decimal or floating point value for an integer column. Whether or not the user would "prefer" an error I can't say, but standards-wise I think the correct thing is to compare using the dominant type and only return the rows that match.

Feel free to comment if I've overlooked something or otherwise misread the spec. Spec-reading is *not* one of my gifts...

[Bryan Pendleton]

I'm sold!

I see that while integer and decimal are compatible, there do exist other
types which are not compatible. For example:

ij> values 4.23, 'hot dog', 4;
ERROR 42X61: Types 'DECIMAL' and 'CHAR' are not UNION compatible.

And therefore, sure enough:

ij> select * from t1 where i in (4, 4.23, 'tomato');
ERROR 42818: Comparisons between 'INTEGER' and 'CHAR' are not supported.

So I believe I'm following along with your chain of reasoning and it seems sound to me.

Thanks for taking the time to clarify the underlying mechanisms.

[A B]

Thank you very much for the review and feedback, Bryan. I committed d2256_v1.patch with svn # 523411:

  URL: http://svn.apache.org/viewvc?view=rev&rev=523411

Marking this issue as resolved...

[A B]

Attaching a simple release note for this issue.

[A B]

Very slight tweak to the release note.

[A B]

Fix is in trunk (10.3) and I haven't heard any objections to the release note, so closing.

[Myrna van Lunteren]

scrubbed releasenote