Lucene - Core
  1. Lucene - Core
  2. LUCENE-3582

NumericUtils.floatToSortableInt/doubleToSortableLong does not sort certain NaN ranges correctly and NumericRangeQuery produces wrong results for NaNs with half-open ranges

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Trivial Trivial
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 3.5, 4.0-ALPHA
    • Component/s: None
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      The current implementation of floatToSortableInt does not account for different NaN ranges which may result in NaNs sorted before -Infinity and after +Infinity. The default Java ordering is: all NaNs after Infinity.

      A possible fix is to make all NaNs canonic "quiet NaN" as in:

      // Canonicalize NaN ranges. I assume this check will be faster here than 
      // (v == v) == false on the FPU? We don't distinguish between different
      // flavors of NaNs here (see http://en.wikipedia.org/wiki/NaN). I guess
      // in Java this doesn't matter much anyway.
      if ((v & 0x7fffffff) > 0x7f800000) {
        // Apply the logic below to a canonical "quiet NaN"
        return 0x7fc00000 ^ 0x80000000;
      }
      

      I don't commit because I don't know how much of the existing stuff relies on this (nobody should be keeping different NaNs in their indexes, but who knows...).

      1. LUCENE-3582.patch
        2 kB
        Dawid Weiss
      2. LUCENE-3582.patch
        16 kB
        Uwe Schindler
      3. LUCENE-3582.patch
        21 kB
        Uwe Schindler

        Activity

        Hide
        Uwe Schindler added a comment -

        Bulk close after release of 3.5

        Show
        Uwe Schindler added a comment - Bulk close after release of 3.5
        Hide
        Uwe Schindler added a comment -

        Committed trunk revision: 1203966
        Committed 3.x revision: 1203967

        Show
        Uwe Schindler added a comment - Committed trunk revision: 1203966 Committed 3.x revision: 1203967
        Hide
        Dawid Weiss added a comment -

        Isn't that a shocking experience?

        Show
        Dawid Weiss added a comment - Isn't that a shocking experience?
        Hide
        Uwe Schindler added a comment -

        I assume this check will be faster here than (v != v)

        This is the in my opinion the funniest thing you can show your students about floats. Everybody will tell you this can never be true

        Indeed OpenJDKs isNaN() is implemented exactly like that, it returns (v != v).

        Show
        Uwe Schindler added a comment - I assume this check will be faster here than (v != v) This is the in my opinion the funniest thing you can show your students about floats. Everybody will tell you this can never be true Indeed OpenJDKs isNaN() is implemented exactly like that, it returns (v != v).
        Hide
        Uwe Schindler added a comment -

        Improved tests for NRQ. Ready to commit.

        Show
        Uwe Schindler added a comment - Improved tests for NRQ. Ready to commit.
        Hide
        Dawid Weiss added a comment -

        Looks good to me. Thanks Uwe.

        Show
        Dawid Weiss added a comment - Looks good to me. Thanks Uwe.
        Hide
        Uwe Schindler added a comment - - edited

        Here a patch that fixes NumericRangeQuery to correctly handle NaN. If the upper/lower bounds == null, it will replace that by infinity and will never match NaN (this was a bug before). If you want to hit NaN with NRQ, you can do that only by directly hitting it using NumericRangeQuery.newFloatRange("float", Float.NaN, Float.NaN, true, true)

        This patch also handles doubles in addition to floats and uses the native Java method without raw. Tests were modified to check for NaN, too.

        The use of floatToIntBits instead of floatToRawIntBits has no real performance impact, as this method is only used during indexing. Population of FieldCache is unaffected. It just ensures that indexes are built with normalized NaN values, so NRQ can work correctly.

        Stored fields were already stored using the non-raw method, so this is now consistent.

        Show
        Uwe Schindler added a comment - - edited Here a patch that fixes NumericRangeQuery to correctly handle NaN. If the upper/lower bounds == null, it will replace that by infinity and will never match NaN (this was a bug before). If you want to hit NaN with NRQ, you can do that only by directly hitting it using NumericRangeQuery.newFloatRange("float", Float.NaN, Float.NaN, true, true) This patch also handles doubles in addition to floats and uses the native Java method without raw. Tests were modified to check for NaN, too. The use of floatToIntBits instead of floatToRawIntBits has no real performance impact, as this method is only used during indexing. Population of FieldCache is unaffected. It just ensures that indexes are built with normalized NaN values, so NRQ can work correctly. Stored fields were already stored using the non-raw method, so this is now consistent.
        Hide
        Uwe Schindler added a comment -

        I agree that normalizing Nan would be goof for NRQ, because this way you can search for NaN using:
        NumericRangeQuery.newFloatRange(...., Float.NaN, Float.NaN, true, true);

        Otherwise the bits produced for the bounds may not be the same bits like indexed and thats the main problem. This would fix this issue. Another thing to maybe fix would be the half-open ranges to correctly handle infinity. In that case a NRQ would never hit NaN (even when half open) but with the above query you could still search for NaN (as a "point value").

        Show
        Uwe Schindler added a comment - I agree that normalizing Nan would be goof for NRQ, because this way you can search for NaN using: NumericRangeQuery.newFloatRange(...., Float.NaN, Float.NaN, true, true); Otherwise the bits produced for the bounds may not be the same bits like indexed and thats the main problem. This would fix this issue. Another thing to maybe fix would be the half-open ranges to correctly handle infinity. In that case a NRQ would never hit NaN (even when half open) but with the above query you could still search for NaN (as a "point value").
        Hide
        Dawid Weiss added a comment -

        Ok, don't fix it then, no problem from me – like I said, I only found out because I looked inside. It's not a bug, it's a feature

        I personally think utility methods should work correctly for all kinds of input – that utility method in NumericUtils should at least say it doesn't support NaN (or better: assert so).

        Show
        Dawid Weiss added a comment - Ok, don't fix it then, no problem from me – like I said, I only found out because I looked inside. It's not a bug, it's a feature I personally think utility methods should work correctly for all kinds of input – that utility method in NumericUtils should at least say it doesn't support NaN (or better: assert so).
        Hide
        Uwe Schindler added a comment -

        I have no preference to floatToIntBits or floatToRawIntBits. I just copied the code from Yoniks method from Solr, my original NumericRangeQuery code donation back in the past used floatToIntBits. I just said, the behaviour of NaN in NumericRangeQuery is undefined so there was no reason to support NaN with NRQ at all. So I dont care. It does affect NRQ, but to fix NRQ correctly, half open ranges must be modified to end at Positive_infnity, but then NRQ can never match NaN.

        In my opinion, NumericUtils is made for NumericRangeQuery and the raw method is an intrinsic, we should use it. I would simply not like to fix this.

        If we fix it, i have to add some checks in NRQ's ctor, too. So it supports NaN.

        Show
        Uwe Schindler added a comment - I have no preference to floatToIntBits or floatToRawIntBits. I just copied the code from Yoniks method from Solr, my original NumericRangeQuery code donation back in the past used floatToIntBits. I just said, the behaviour of NaN in NumericRangeQuery is undefined so there was no reason to support NaN with NRQ at all. So I dont care. It does affect NRQ, but to fix NRQ correctly, half open ranges must be modified to end at Positive_infnity, but then NRQ can never match NaN. In my opinion, NumericUtils is made for NumericRangeQuery and the raw method is an intrinsic, we should use it. I would simply not like to fix this. If we fix it, i have to add some checks in NRQ's ctor, too. So it supports NaN.
        Hide
        Yonik Seeley added a comment -

        We don't really support NaN as a value in Lucene in general I think. I know that our sorting (priority queue) methods don't support NaN, and this is why FunctionQuery has the following code:

              // Current Lucene priority queues can't handle NaN and -Infinity, so
              // map to -Float.MAX_VALUE. This conditional handles both -infinity
              // and NaN since comparisons with NaN are always false.
              return score>Float.NEGATIVE_INFINITY ? score : -Float.MAX_VALUE;
        
        Show
        Yonik Seeley added a comment - We don't really support NaN as a value in Lucene in general I think. I know that our sorting (priority queue) methods don't support NaN, and this is why FunctionQuery has the following code: // Current Lucene priority queues can't handle NaN and -Infinity, so // map to - Float .MAX_VALUE. This conditional handles both -infinity // and NaN since comparisons with NaN are always false . return score> Float .NEGATIVE_INFINITY ? score : - Float .MAX_VALUE;
        Hide
        Dawid Weiss added a comment -

        So you agree if we exchange with flotToIntBits the bug is fixed.

        Yes, as far as I can see the implementation of floatToIntBits is exactly floatToRawIntBits + normalization of NaN. I doubt there'll be intrinsics for that – the code is short and simple enough that it will probably inline and jit into a few assembly instructions anyway.

        I don't quite understand the other part of your question... the code in my patch is virtually the same as floatToIntBits:

        int result = floatToRawIntBits(value);
        // Check for NaN based on values of bit fields, maximum
        // exponent and nonzero significand.
        if ( ((result & FloatConsts.EXP_BIT_MASK) ==
        FloatConsts.EXP_BIT_MASK) &&
        (result & FloatConsts.SIGNIF_BIT_MASK) != 0)
        result = 0x7fc00000;
        return result;

        The only difference is that this doesn't normalize "significant" NaNs (failing), but I don't know if they're even used in jvm code anywhere.

        Show
        Dawid Weiss added a comment - So you agree if we exchange with flotToIntBits the bug is fixed. Yes, as far as I can see the implementation of floatToIntBits is exactly floatToRawIntBits + normalization of NaN. I doubt there'll be intrinsics for that – the code is short and simple enough that it will probably inline and jit into a few assembly instructions anyway. I don't quite understand the other part of your question... the code in my patch is virtually the same as floatToIntBits: int result = floatToRawIntBits(value); // Check for NaN based on values of bit fields, maximum // exponent and nonzero significand. if ( ((result & FloatConsts.EXP_BIT_MASK) == FloatConsts.EXP_BIT_MASK) && (result & FloatConsts.SIGNIF_BIT_MASK) != 0) result = 0x7fc00000; return result; The only difference is that this doesn't normalize "significant" NaNs (failing), but I don't know if they're even used in jvm code anywhere.
        Hide
        Uwe Schindler added a comment -

        So you agree if we exchange with flotToIntBits the bug is fixed. I would prefer to use the native JDK implementation, maybe it will get replaced by an intrisic

        For NumericRangeQuery any change in this method has no real effect, as its broken/not working for NaN at all. To fix this, NumericRangeQurey.newFloatRange(.., f, null,...) should be explicitely use Float.POSITIVE_INFINITY instead of null, otherwise some NaNs could be selected, too (with your normalization all NaNs would be inside that range).

        What should we do here?

        Show
        Uwe Schindler added a comment - So you agree if we exchange with flotToIntBits the bug is fixed. I would prefer to use the native JDK implementation, maybe it will get replaced by an intrisic For NumericRangeQuery any change in this method has no real effect, as its broken/not working for NaN at all. To fix this, NumericRangeQurey.newFloatRange(.., f, null,...) should be explicitely use Float.POSITIVE_INFINITY instead of null, otherwise some NaNs could be selected, too (with your normalization all NaNs would be inside that range). What should we do here?
        Hide
        Dawid Weiss added a comment -

        Why not simply use floatToIntBits without the raw?

        There is no specific reason – I wrote a similar routine using floatToIntBits, actually, but Robert pointed out that using raw bits may be faster and that NumericUtils already has a method for doing float sorting using fixed precision arithmetic. I checked the source (it's not suitable for my needs because I need unsigned order) but noticed the code is incorrect. That's pretty much it

        I admit I thought floatToIntBits normalizes the representation (mantissa) but it doesn't – in fact, the implementation in OpenJDK is indeed identical to what I suggested.

        Feel free to commit and correct for doubles.

        Show
        Dawid Weiss added a comment - Why not simply use floatToIntBits without the raw? There is no specific reason – I wrote a similar routine using floatToIntBits, actually, but Robert pointed out that using raw bits may be faster and that NumericUtils already has a method for doing float sorting using fixed precision arithmetic. I checked the source (it's not suitable for my needs because I need unsigned order) but noticed the code is incorrect. That's pretty much it I admit I thought floatToIntBits normalizes the representation (mantissa) but it doesn't – in fact, the implementation in OpenJDK is indeed identical to what I suggested. Feel free to commit and correct for doubles.
        Hide
        Uwe Schindler added a comment -

        Why not simply use floatToIntBits without the raw? This one normalized NaN.
        We used the raw methods for speed reasons as we assumed that NaN sorting makes no sense and NumericRangeQuery cannot usefully select those values. E.g. half open ranges will select NaN values incorrectly, so an index containing NaN values is not useable with NRQ where the upper bound is null.

        The same applies to Doubles, you patch is missing them.

        Show
        Uwe Schindler added a comment - Why not simply use floatToIntBits without the raw? This one normalized NaN. We used the raw methods for speed reasons as we assumed that NaN sorting makes no sense and NumericRangeQuery cannot usefully select those values. E.g. half open ranges will select NaN values incorrectly, so an index containing NaN values is not useable with NRQ where the upper bound is null. The same applies to Doubles, you patch is missing them.

          People

          • Assignee:
            Uwe Schindler
            Reporter:
            Dawid Weiss
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development